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 - 24-03-2017 18:18:31

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3133

Jamis pair

Bonjour à tous.

Quel plus grand nombre pouvez vous écrire en base b si, quel que soit un extrait de 2n chiffres consécutifs de ce nombre, il existe au moins un chiffre qui apparait un nombre impair de fois dans cet extrait ?

Bonne recherche.



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 25-03-2017 22:57:49

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 390

kamais pair

Hmm, je cherche... Il me semble que les nombres du type 323132303231323 sont les plus efficaces. Cependant, je n'arrive pas encore à démontrer qu'on ne peut fabriquer un nombre de taille 2^b, je n'ai pas trouvé l'astuce.

Il me semble que le résultat ne change pas si l'on restreint l'énoncé aux extraits commençant à l'endroit d'un chiffre de rang pair, ça va peut être m'aider à trouver la démo.

 #3 - 26-03-2017 09:00:09

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3133

Jamasi pair

@ Ebichu : Comme je m'y attendais, tu as franchi la 1ère étape, à savoir que tu as bien trouvé le meilleur nombre. Reste à passer la seconde étape, celle de la preuve. Ce n'est pas le plus simple. En fait, il te faut un temps de réflexion supplémentaire. Je suis passé par là également....

Oublie ta remarque finale, ce n'est pas la piste.

 #4 - 26-03-2017 14:13:12

caduk
Professionnel de Prise2Tete
Enigmes résolues : 43
Messages : 151

JJamais pair

Bonjour,
En premier lieu, il est facile de remarquer que l'on peut trouver un nombre de longueur 2^b-1 en base b.
Supposons que l'on dispose d'un alphabet de b symboles 0,...,b-1 (permet d'inclure b = 1)
Procédons par récurrence:
Initialisation:
b = 1:
0 est une solution.

Hérédité:
supposons qu'il existe une solution m de longueur 2^b-1
pour b+1, le mot mbm est une solution, et est de longueur 2^(b+1)-1

En revanche, je n'ai pas réussi à montrer que l'on ne pouvait pas aller au delà, ni beaucoup pris de temps pour y trouver un contre exemple

 #5 - 26-03-2017 15:13:52

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3133

amais pair

C'est ça, Caduck, tu as donc rejoint Ebichu pour la même partie de la solution.

 #6 - 26-03-2017 16:40:10

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 390

jalais pair

Ha ben si, cette piste m'a aidé à trouver une solution, finalement smile

Considérons un nombre de taille [latex]2^b[/latex], noté [latex]x_{1}x_{2}...x_{2^b}[/latex]. On regarde les extraits de taille 2, 4, 6... : [latex]x_{1}x_{2}[/latex], [latex]x_{1}...x_{4}[/latex], [latex]x_{1}...x_{6}[/latex], ... , [latex]x_{1}...x_{2^b}[/latex]. Il y a [latex]2^{b-1}[/latex] tels extraits.

Maintenant, étant donné un extrait de longueur paire, on appelle "reste" de cet extrait ce qu'il reste quand on l'a épuré de ses doublons. Par exemple, si l'extrait est 023121312321, alors le reste est 03 (l'ordre n'est pas important). Il y a [latex]2^{b-1}[/latex] restes possibles pour les extraits en base b. Par exemple, les 8 restes des extraits en base 4 sont {},01,02,03,12,13,23,0123.

Reprenons notre nombre de taille [latex]2^b[/latex]. Nous allons démontrer qu'il est possible d'en trouver un extrait dont le reste est {}, ce qui suffira à démontrer le résultat.

Parmi les extraits de taille 2, 4, 6... commençant par [latex]x_{1}[/latex] dont nous parlions, ou bien un extrait a pour reste {}, et c'est gagné. Sinon, il y a [latex]2^{b-1}-1[/latex] restes possibles, et [latex]2^{b-1}[/latex] extraits : par le lemme des tiroirs, il existe deux extraits [latex]x_{1}...x_{i}[/latex] et [latex]x_{1}...x_{j}[/latex] avec le même reste. L'extrait [latex]x_{i+1}...x_{j}[/latex] a donc pour reste {}, cqfd.

 #7 - 26-03-2017 17:45:28

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3133

Jamais ppair

C'est bon Ebichu, bravo à toi !

La variante que j'ai trouvée est un chouia plus courte, par exemple pas besoin de calculer le cardinal des extraits pairs.

 #8 - 28-03-2017 08:35:48

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3133

Jaamis pair

Alors, la variante de la preuve qu'on ne peut pas aller au dela de 2^b -1 chiffres.

On définit un nombre binaire de b chiffres, dont le rang de chaque bit est indexé à un chiffre de b. Un code spécifique k est associé aux k-ièmes premiers chiffres de notre plus grand nombre: il représente, pour chaque chiffre de b, la parité du nombre d'apparitions de ce chiffre depuis 1 jusqu'à k. Comme le nombre de codes possibles est 2^b-1 (le code 000...est exclu, car tout pair), au bout de 2 ^ b chiffres de ce plus grand nombre, il y a forcément 2 codes identiques. Si ces 2 codes sont aux rangs i et j, leur différence étant nulle, dans l'intervalle j-i chaque chiffre apparait un nombre pair de fois. Donc notre plus grand nombre ne peut pas comporter plus de 2^b - 1 chiffres.

CQFD

Peu de réponses, mais c'était tout de même assez particulier.....

 #9 - 28-03-2017 09:59:47

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 390

Jamais pai

Oui, ta démonstration est très jolie, très simple ; mais c'est très difficile à imaginer. Un genre de problème parfait pour clouer le bec à un M. Je-sais-tout...

 

Réponse rapide

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

Répondez (numériquement) à la petite énigme suivante : 

Dans une course, vous doublez le 20ème, en quelle position êtes-vous ?

Sujets similaires

Sujet Date Forum
P2T
Pair ou impair ? par shadock
26-03-2011 Enigmes Mathématiques
P2T
01-01-2017 Enigmes Mathématiques
P2T
Infiniment pair ? par nodgim
31-07-2016 Enigmes Mathématiques
P2T
Araignée par gabrielduflot
17-06-2009 Enigmes Mathématiques
P2T
Pas de jaloux ! par LeSingeMalicieux
17-11-2008 Enigmes Mathématiques
28-12-2010 Enigmes Mathématiques
15-12-2012 Enigmes Mathématiques
P2T
Oooooor par SaintPierre
07-04-2011 Enigmes Mathématiques
P2T
3 sous-ensembles ! par Azdod
14-11-2011 Enigmes Mathématiques

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