354224848179261915075  

Je dirais qu'il y a 354224848179261915075 dialogues distincts possibles

Merci pour l'énigme

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

Bonjour à tous.

Je propose : 354224848179261915075

Merci pour l'énigme

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]

Salut, je trouve



avec

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

Il y a 354224848179261915075 dialogues distincts !
Environ 3.54 e+20

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  A_n = 3*A_n-1-A_n-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.

Je trouve 354224848179261915075 dialogues distincts, soit en abrégé

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

Il  y a 354 224 848 179 261 915 075 solutions

Bonne journée

Bonjour
Je propose:    354224848179261915075 dialogues
Cordialement

Bonjour littleguy,

Je propose 354224848179261915075 dialogues distincts.

Merci pour l'énigme.

Bonjour   littleguy ,

Il y a 354 224 848 179 262 000 000 dialogues distincts .

Merci.

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.

suite
>sbarre
il ne te restait qu'à faire la somme ...c'est  dommage.