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

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.

  • |
  • Répondre

#0 Pub

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

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

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

Jamais paair

@ 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 : 398

Jamais pari

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

Jamaiis 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
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

Jmaais 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 : 3802

Jamas 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 : 3802

JJamais 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
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

Jamais pari

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 : Riri, Fifi et ?

Sujets similaires

Sujet Date Forum
P2T
Infiniment pair ? par nodgim
31-07-2016 Enigmes Mathématiques
P2T
Pair ou impair ? par shadock
26-03-2011 Enigmes Mathématiques
P2T
01-01-2017 Enigmes Mathématiques
P2T
Fête de famille par portugal
01-02-2016 Enigmes Mathématiques
P2T
Trouver 636 par lolek
16-09-2013 Enigmes Mathématiques
03-11-2010 Enigmes Mathématiques
P2T
La Machine v2.0 par SabanSuresh
28-10-2014 Enigmes Mathématiques
25-09-2011 Enigmes Mathématiques
P2T
Magie 4 par Vasimolo
09-09-2012 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