Bonjour,
Igor et Pierre se livrent à un dialogue bien particulier : ils doivent dire, chacun à son tour, un entier positif inférieur ou égal à 100, mais en respectant le protocole suivant :
- Igor commence et doit dire à chaque fois un nombre impair ; Pierre répond à chaque fois par un nombre pair.
- Chacun d'eux doit dire un nombre plus grand que le nombre donné juste avant par l'autre (hormis Igor dans son premier choix cela va de soi) .
Bien sûr à un moment le dialogue se termine puisque l'un des deux ne peut plus choisir de nombre.
Par jeu ils recommencent l'expérience plusieurs fois, en prenant soin à chaque fois de ne pas répéter un dialogue déjà prononcé. Ils finissent quand même par se lasser en se demandant combien il peut bien y avoir de dialogues distincts !
Pouvez-vous leur donner la réponse ?
Bonsoir,
Je propose 354.224.848.179.261.915.075 dialogues distincts.
Si Igor commence par 99, il n'y a qu'un dialogue possible :
99 - 100
Si Igor commence par 97, il y a deux dialogues possibles :
97 - 100
97 - 98 - 99 - 100
Si Igor commence par 95, deux possibilités :
* soit Pierre dit ensuite 96, puis on peut ajouter tous les dialogues (3) qu'on a trouvés précédemment :
95 - 96 - 99 - 100
95 - 96 - 97 - 100
95 - 96 - 97 - 98 - 99 - 100
* soit Pierre dit ensuite un autre nombre, et ça correspond à remplacer 97 par 95 dans les lignes qui commencent par 97 :
95 - 100
95 - 98 - 99 - 100
Cette méthode est généralisable :
Pour n [1,50], soit d(n) le nombre de dialogues commençant par (101 - 2n)
qui peut se réécrire en
Ce qui donne une suite rapidement croissante : 1, 2, 5, 13, 34, 89, 233, ...
Pour le calcul des plus grands d(n) et de la somme demandée, j'ai du passer par les BigInteger.
C'est vrai que l'énoncé ne donne pas l'impression que la solution est si grande que ça...
Merci littleguy !
Bonjour,
je répond :354224848179261915075
Le lien avec Fibonacci est facile à vérifier
Merci pour cette énigme très sympa!
Bonjour littleguy,
Le nombre de dialogues distincts est égal à
354224848179261915075
Merci pour cette énigme faisant appel à Fibonacci !
Si j'appelle N(i) le nombre de dialogues possible avec les i nombres de 101-i à 100.
Si i est pair, on est dans les conditions du problème, c'est Igor qui commence. Si i est impair c'est comme si c'est Pierre qui commençait.
Par exemple N(6) est le nombre de dialogues avec les nombres de 95 à 100 avec Igor qui commence.
N(100) est le nombre de dialogues avec les nombres de 1 à 100. C'est donc le nombre cherché.
Le nombre N(i) avec i pair comporte :
- Les N(i-2) possibilités si le premier nombre impair proposé par Igor n'est pas 100-i (donc supérieur ou égal à 100-i+2)
- Les N(i-1) possibilités si le premier nombre proposé par Igor est 100-i. En effet, dans ce cas, Pierre a la possibilité de répondre de 101-i+1 à 100.
On a donc la relation N(i)=N(i-1)+N(i-2).. C'est la fameuse suite de Fibonacci.
Donc la solution est la valeur de F(100) avec F(1)=F(2)=1
Le nombre de dialogues distincts est donc F(100) = 354224848179261915075
Le nombre de dialogues possibles est le 100° terme de la suite de Fibonacci :
354 224 848 179 261 915 075
Bonjour
Sauf erreur il y a 22100 dialogues possibles pour tout début différent.
Pour mémoire il y aurait 1275 dialogues différents
Il y a 354224848179261915075 dialogues distincts !
Normal qu'ils se soient lassés avant la fin .
On peut trouver la réponse en utilisant de larécursion comme ceci mais ça prend trop de temps :
def nbDialogue(start=0,end=100) :
if start == end :
return 1
return sum(nbDialogue(s, end) for s in range(start+1,end+1,2))
def nbDialogue(start=0, end = 100) :
count = [0] * (end + 1)
count[end] = 1
for i in reversed(range(start,end)):
count[i] = sum(count[s] for s in range(i+1,end+1,2))
return count[start]
Bonsoir
Je pense que le nombre de dialogues possibles s'élève à 354 224 848 179 261 915 075, qui n'est autre que le 101ème terme de la suite de Fibonacci.
Merci pour cette énigme ! Trop
Bonjour à tous,
pour cette énigme, je dirais qu'il y a
218 922 995 834 555 169 026 combinaisons.
En commençant par la "fin" (c'est à dire si Igor commence par 99 puis par 97 etc.), on trouve une série de combinaisons 1, 2, 5, 13, etc. dont on arrive à déterminer qu'elle est de la forme An = 3*An-1-An-2.
Le problème est pour calculer les itérations! Avec excel à partir de 25 on arrive en écriture scientifique (et avec algobox c'est encore pire puisque cela commence avec 8 chiffres!).
Y a-t-il un moyen facile (ou un "réglage" sur algobox ou excel) pour s'affranchir de l'approximation due à la notation scientifique???
Merci.
il existe 2 dialogues distinctes le premier comme vous l avez ennumere ou igor choisit un nombre paire et Pierre un impaire.Cependant on peut changer le dialogue car en additionnant l ensemle de depart de Igor avec un nombre impaire on n obtient un nombre paire car la somme de 2 impaires et un paire et si on fait de meme pour pierre on obtient un nombre impaire car la somme d'un paire et d'un impaire donnent un impaire.Alors la suite changera car igor devra utiliser un paire et pierre un impair
Bonjour
Je compte
573 147 844 013 817 084 100 possibilités, ce qui peut expliquer un certain niveau de lassitude de nos deux comparses.
J'ai décomposé ainsi qu'il suit ma recherche :
J'ai cherché combien il y avait de possibilités en commençant par 99. une seule
puis par 97, 3 possibilités
puis par 95 8 possibilités
puis par 93 21 possibilités
puis par 91 55 possibilités
puis par 89 144 possiblités
puis par 87 , 377 possiblités.
Et j'ai cherché une relation unissant cette séquence de nombres car Python commençait un peu à fatiguer.
En posant U0 = (séquences commençant par 99) , =1
J'ai conjecturé (et pas prouvé) que
Un+1=2xUn +Un - Un-1.
Autrement dit, c'est deux fois le terme précédent auquel j'ajoute le saut de l'avant dernière étape, suite arithmético géométrique.
Il doit y avoir plus joli, plus propre, mais je ne peux livrer que cela à cette heure, je ne voudrais pas que l'enigme se cloture.
Un grand merci pour avoir fait chauffer mon python et mes deux neurones.
(Je note que la progression est plus forte encore que celle du jeu d'echecs et des grains de riz)
La bise à tous
Ben
Je me suis amusé à calculer le temps qu'il faudrait à Igor et Pierre pour dire tous les dialogues possibles, en supposant qu'ils parlent le français de France ("quatre-vingt-dix-neuf" a 5 syllabes alors que "nonante-neuf" n'en a que 3) et qu'ils parlent au débit moyen de 7,18 syllabes par seconde (source : ). Je n'ai fait qu'un calcul approximatif pour avoir l'ordre de grandeur, et je trouve qu'il leur faudrait à peu près 14000 fois l'âge de l'univers...
J'y reviens, décidément, beaucoup de joies dans cette enigme.
Je n'étais pas du tout satisfait de ne pas comprendre comment exprimer cette suite.
Je me suis apperçu au final que la raison était constante entre le nombre de chemins faisables en partant de 99, puis en partant de 97, puis en partant de 95.
Pour rappel, ce nombre de possibilités était de :
[1, 3, 8, 21, 55, 144, 377, 987, 2584, 6765, 17711, 46368, 121393, 317811, 832040, 2178309, 5702887, 14930352, 39088169, 102334155, 267914296, 701408733, 1836311903, 4807526976L, 12586269025L, 32951280099L, 86267571272L, 225851433717L, 591286729879L, 1548008755920L, 4052739537881L, 10610209857723L, 27777890035288L, 72723460248141L, 190392490709135L, 498454011879264L, 1304969544928657L, 3416454622906707L, 8944394323791464L, 23416728348467685L, 61305790721611591L, 160500643816367088L, 420196140727489673L, 1100087778366101931L, 2880067194370816120L, 7540113804746346429L, 19740274219868223167L, 51680708854858323072L, 135301852344706746049L, 354224848179261915075L]
Il s'ensuit que la raison de cette suite est géométrique de facteur :
2.61818181818
Or ce nombre est égal à 1 + le nombre d'or ( un plus racine de 5 le tout sur deux).
J'ai donc pensé directement à Fibonacci, et j'ai découvert que les termes de ma suite sont tous des membres de la famille Fibonacci.
A partir de là il me manque pas grand chose pour concevoir comment on passe de la théorie des graphes à cette remarquable séquence.
Si il y en a un qui veut éclairer ma route.....
Bonjour,
Clap de fin pour cette énigme et les ou bien dialogues !
Bravo à ceux qui ont donné la bonne réponse.
J'ai oublier de compléter ma réponse.
Soit f(a,b) la fonction qui donne le nombre de dialogues avec des nombres x
On cherche f(0,100)
On remarque que f(i,100)= f(0,100-i) (on retire i à tous les nombres des dialogues).
Et aussi f(i,n)= f(0,n-i)
f(0,1)=1
f(0,2)=1
f(0,3)=2 =f(0,1)+f(0,2)
f(0,4)=3 =f(0,2)+f(0,3)
d=n si n est impair ou d=n-1 si n est pair
f(0,n)=f(1,n)+ f(3,n)...+f(2i-1,n)+ ... +f(d,n) (à Igor de jouer, il choisi un nombre impair entre 1 et n)
or
f(3,n)...+f(2i-1,n)+ ... +f(d,n) = f(1,n-2)...+f(2i-3,n-2)+ ... +f(d-2,n-2) = f(0,n-2)
donc
f(0,n)=f(1,n)+f(0,n-2) =f(0,n-1)+f(0,n-2)
donc
f(0,100) est le 100e terme de la suite de Fibonacci
f(0,100)=354 224 848 179 261 915 075
Il y a 354224848179261915075 dialogues distincts !
Bonjour,
Je n'ai pas répondu à la bonne question...
On remarquera que la formule de trapangle :
d(n+1)=3xd(n)-d(n-1) donne le nombre de dialogues pour une valeur
et qu'en sommant de 1 à 50 on obtient bien l'excellent résultat de beaucoup
de participants.
Le 50 ème nombre de la somme de trapangle est égal au 100 ème de Fibonacci.
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :