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 : 3176

Jamaais 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 : 475

jamais pait

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 : 3176

jamais pait

@ 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 : 45
Messages : 210

Jmais 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 : 3176

Jamasi 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 : 475

jamais oair

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 : 3176

jamaus pair

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 : 3176

Jmais 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 : 475

jamaos pair

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 à la devinette suivante : 

Le père de toto a trois fils : Tim, Tam et ?

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
Gâteau 141 par Vasimolo
12-08-2017 Enigmes Mathématiques
P2T
Fonction composée par Varzmir
01-07-2017 Enigmes Mathématiques
P2T
Polynomes par tiart441
13-07-2013 Enigmes Mathématiques
P2T
29-01-2011 Enigmes Mathématiques
P2T
08-07-2011 Enigmes Mathématiques
P2T
Gâteau 19 par Vasimolo
31-07-2010 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