Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 20-07-2010 09:02:22

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

du binaire paryout

Un petit énoncé à démontré, volontairement tordu big_smile

On considère n'importe quelle base B. Soit E1 l'ensemble des nombres qui, en base B, ne s'écrivent qu'avec des 1 et des 0 (d'où le titre). Soit E2 l'ensemble des diviseurs des nombres de E1. Pouvez-vous montrer que E2 = N, l'ensemble des entiers naturels ?
C'est bien entendu valable quelque soit la base B

La case réponse valide le nom du mathématicien grâce à qui une démonstration simple est possible

Spoiler : Pour les petits malins Vous êtes dispensés de me fournir une démo pour B=2 big_smile big_smile big_smile De toutes les façons, la démo doit être valable quelque soit B

Spoiler : Pour démarrer L'énoncé est, comme annoncé, volontairement tordu. Du coup, une petite simplification s'impose... une fois simplifié correctement, la démonstration tient en 2 lignes (et j'écris gros)



Annonces sponsorisées :

 
Réponse :
  • |
  • Répondre

#0 Pub

 #2 - 20-07-2010 10:42:07

falcon
Professionnel de Prise2Tete
Enigmes résolues : 26
Messages : 106

du binaire parrout

tien c'est marrant ! J'ai déjà eu ca en kholle cette année.

du coup pas besoin des indices :

le résultat est équivalent à démontrer que tout nombre possede un diviseur s'écrivant avec que des 1 et des 0 en base B.

soit n un nombre

considérons les n+1 nombres suivant écris en base B:
0
1
11
111
11.....1111 (avec n 1)

et maintenant rangeons ces nombres dans les n tiroirs numérotés de 0 à n-1 en fonction de leur reste dans la division euclidienne par n.

n+1 objets dans n tiroirs, donc il y a au moins deux de ces nombres qui sont dans le meme tiroir d'apres le tres réputé principe des tiroirs.

Ainsi la différence du plus grand et du plus petit est un nombre de la forme
1...10....0 et est divisible par n.

On a bien trouvé un multiple de n s'écrivant avec que des 1 et des 0 dans la base B, le résultat est démontré.


Il vaut mieux pomper meme s'il ne se passe rien que risquer qu'il se passe quelque chose de pire en ne pompant pas

 #3 - 21-07-2010 06:17:26

McFlambi
Professionnel de Prise2Tete
Enigmes résolues : 48
Messages : 144

Du binairre partout

Soit [latex]x\in\mathbb{N}[/latex], on va montrer qu'il divise un élément de [latex]E_1[/latex].

Soit, pour tout [latex]n\in\mathbb{N}[/latex],
[TeX]u_{n} = b^n (\textrm{mod }x) \quad \in \mathbb{Z}/x\mathbb{Z}[/latex].

s'il existe un [latex]n[/latex] tel que [latex]u_n = 0[/latex] alors [latex]x |b^n\in E_1[/latex]. Sinon, pour tout [latex]n[/latex], [latex]u_n \ne 0[/latex]. Comme cette suite infine est dans  [latex]\mathbb{Z}/x\mathbb{Z}[/latex] qui est fini, il y a un élément [latex]y\in\mathbb{Z}/x\mathbb{Z}[/latex], tel qu'une infinité de [latex]u_n[/latex] tombent dessus. En particulier, je peux en prendre au nombre de [latex]x[/latex] (je note [latex]f(i)[/latex] ces [latex]x[/latex] indices, pour [latex]i\in\{1,2,\ldots,x\}[/latex]), et alors on a :

[latex]\sum_i u_{f(i)} = \sum_i y = x y = \sum_i b^{f(i)} = 0 (\textrm{mod }x)[/TeX]
Donc [latex]x|\sum_i b^{f(i)}\in E_1[/latex]. Dans les deux cas, [latex]x[/latex] (quelconque) divise un nombre de [latex]E_1[/latex].

 #4 - 22-07-2010 10:40:30

rivas
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1105
Lieu: Jacou

Du bbinaire partout

Bon, ben je n'ai pas trouvé de réponse en 2 lignes. C'est un peu plus long (8). Je propose quand même. smile
Je pense qu'il y a une petite erreur dans l'énoncé smile Il faut montrer que [latex]E2=\mathbb{N}^*[/latex] et non pas [latex]\mathbb{N}[/latex]. En effet 0 ne peut jamais être le diviseur d'aucun nombre.
Le cas de 1 est très simple: 1 est un diviseur de B qui est évidement de la forme que j'appelle "B-binaire".
Pour le reste ma démonstration est encore un bel exemple du principe des tiroirs attribué à Dirichlet (qui valide la case réponse).

Soit dont N [latex] \in \mathbb{N}^*-\{1\}[/latex].
Considérons les [latex]B^k[/latex] modulo N pour k entier de 0 à N. Il y a N+1 valeurs alors qu'il ne peut y en avoir au plus que N différentes.
Il existe donc 2 valeurs de k, k1 et (k2=)k1+p telles que: [latex]B^{k1} \equiv B^{k1+p} [N][/latex].
Donc [latex]\forall k \in \mathbb{N} B^{k1+k.p} \equiv B^{k1} [N][/latex] (trivial par récurrence par exemple).
Considérons donc [latex]X=\sum_{k=0}^{N-1}B^{k1+k.p}[/latex]. X est bien de la forme "B-binaire" (avec les 1 également répartis). X s'écrit avec des 1 tous les p chiffres en commençant au chiffre de rang k1+1 en partant de la droite.
Or [latex]X \equiv N.B^{k1} \equiv 0 [N][/latex]
Cette dernière égalité dit exactement que N est un diviseur de X.
Donc pour tout entier non-nul, il existe au moins un entier "B-binaire" dont il est le diviseur, ce qui montre bien que [latex]E2=\mathbb{N}^*[/latex]

En tout cas, merci, c'est original comme problème. Je ne connaissais pas et j'ai du me creuser la tête, ce qui fait toujours du bien (quand on trouve à la fin smile).

 #5 - 22-07-2010 13:41:01

scrablor
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 931

Du binaire aprtout

Ça m'énerve depuis plusieurs jours, je n'arrive pas à être simple...

Soit N un entier naturel non nul.
Je le factorise N=M*P en mettant dans M les facteurs premiers qui figurent dans la factorisation de la base B et dans P les autres facteurs premiers.
Ainsi M sera un diviseur d'une certaine puissance de B, disons [latex]B^k[/latex].

Par ailleurs P est premier avec B.
Je peux donc appliquer le théorème d'Euler [latex]B^{\varphi(P)} \equiv 1 \pmod P[/latex]

Alors P sera un diviseur de [latex]B^{\varphi(P)}+B^{2\varphi(P)}+...+B^{P\varphi(P)}[/latex]  puisque cette somme est congrue à P modulo P.

Donc N apparaît comme un diviseur du produit [latex]B^k (B^{\varphi(P)}+B^{2\varphi(P)}+...+B^{P\varphi(P)} )[/latex]  qui ne s'écrit en base B qu'avec des 0 et des 1.


Celui qui fuit les casse-tête ne vaut pas un clou.

 #6 - 22-07-2010 15:30:33

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

Du binaire partou

Que des bonnes réponses pour l'instant.
Scrablor part très très loin, mais sa démo est néanmoins valable et intéressante: alors que les autres se contentent d'un laconique "il existe un élément ceci-cela..." (certes valide, mais ô combien non constructiviste), il va plus loin en disant : "c'est celui-là !"

L'énoncé dit une chose compliquée, qu'on peut traduire simplement: dans toute base B, tout nombre N admet un multiple dont l'écriture en base B ne comprend que  des 0 et des 1.

La démonstration quant à elle est assez simple, partant de cet énoncé.
Soit B une base quelconque, N un nombre quelconque et U la suite telle que [latex]U_0 = 1[/latex] et [latex]U_{n+1} = b U_n + 1[/latex]
Par définition, toutes les valeurs de U s'écrivent (en base B), uniquement avec des 1.

Il y a N valeurs possibles de résultats à l'opération "Modulo N", donc parmi les N+1 premiers nombre de U, 2 au moins ont le même résultat modulo N (principe des tiroirs de Dirichlet). La différence entre ces 2 nombres est donc un multiple de N (vu que son résultat modulo N est 0) et par ailleurs s'écrit en base B avec une série de 1, suivie d'une série de 0.

Conclusion: pour toute base B, pour tout nombre N, il existe un multiple de N qui ne s'écrit qu'avec des 0 et des 1 en base B. CQFD

 #7 - 24-07-2010 04:31:19

McFlambi
Professionnel de Prise2Tete
Enigmes résolues : 48
Messages : 144

Du binaire partuot

j'aime bien la démo qui va loin ! par contre il n'exhibe pas plus la solution que les autres solutions. Par exemple le [latex]k[/latex] est défini par un "il existe un rang [latex]k[/latex] à partir duquel [latex]M|B^k[/latex]"...

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Sujets similaires

Sujet Date Forum
03-01-2013 Enigmes Mathématiques
29-08-2011 Enigmes Mathématiques
24-12-2011 Enigmes Mathématiques
P2T
Parité binaire par NickoGecko
09-02-2014 Enigmes Mathématiques
22-06-2011 Enigmes Mathématiques
P2T
Le binaire par missreglisse
09-10-2012 Enigmes Mathématiques
P2T
05-09-2016 Enigmes Mathématiques
P2T
Heures et symétries par Logicia
17-02-2011 Enigmes Mathématiques
P2T
Problème de Cluj par SaintPierre
25-03-2011 Enigmes Mathématiques

Mots clés des moteurs de recherche

Mot clé (occurences)
Enigme binaire (8) — Enigme en binaire (5) — Binaire (2) — Il existe multiple de n s ecrivant avec 0 et 1 (2) — Demonstration binaire (2) — Jeux binaire (1) — Kholle principe des toroirs (1) — Principe des tiroirs (1) — Enigme il est partout (1) — Jeu allumettes 1111+11=1111 (1) — Exercices corrigesdirichlettiroirs (1) — Devinette en binaire (1) — Enigme logique binaire (1) — De quel forme sont les entiers naturels qui admettent 3 diviseurs entiers naturels (1) — Facteur premier tiroir de dirichlet (1) — De quelle forme sont les entiers naturels qui admet trois diviseurs entiers naturels? (1) — Jeu des chiffres binaires (1) — Montrer que tout nombre entier admet en base dix un multiple s?ecrivant uniquement avec des 0 et des 1 tiroir dirichlet (1) — Resoudre des enigmes mathematiques avec le systeme binaire (1) — Principe des tiroirs - jeux (1) — Suite logique enigme binaire (1) — Jeu binaire (1) — Binaire enigme (1) — Il est partout enigme (1) — Jeux binaire dans le passe partout (1) — Jeux de logique binaire (1) — Enigmes nombre binaire (1) — Enigmes mathematiques binaire (1) — Kholle enigme (1) — Enigme sur multiple de 33 qui s ecrit qu avec des 1 (1) — Enigme il est partout? (1) — Enigme mathematiciens tiroirs (1) — Soit le nombre n=11 en base e. combien vaut n en base 10 (1) — Devinette de logique binaire (1) — D?fi ou il faut rouver le plut ptit chifre secrivant avec 4 i (1) — Multiple s ecrivant avec seulement des 1 (1) — Enigme bianaire (1) — Binaire jeux (1) — Enigme binaire objet mathematique (1) — Enigme binaire (1) — Enigme principe des tiroirs (1) — Devinette binaire (1) — Il existe multiple s ecrit qu avec des tiroirs (1) — Reste division euclidienne (n-1)! par n (1) — Enigmes binaire (1) — Solution enigme 33 s ecrit avec des 1 (1) — Enigme du binaire partout (1) — Jeux chiffre binaire logique (1) —

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete