![](/img/vague-bas-gauche.png) |
#1 - 24-03-2017 18:18:31
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
jamaid 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.
#2 - 25-03-2017 22:57:49
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
Jamai 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 : 3801
Jaamais 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 : 45
- Messages : 398
Jamais pai
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 : 3801
Jaamais 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
Jaais pair
Ha ben si, cette piste m'a aidé à trouver une solution, finalement ![smile](img/smilies/smile.png)
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 : 3801
Jaamais 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 : 3801
jamais oair
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
Jamis 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...
|
![](/img/vague-haut-droite.png) |