Inscription / Connexion Nouveau Sujet
Niveau 1 *
Partager :

Juin 2016, énigme 5

Posté par
littleguy
23-06-16 à 18:15

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 ?

Posté par
torio
re : Juin 2016, énigme 5 23-06-16 à 20:13

gagné354224848179261915075  

Posté par
GreenT
re : Juin 2016, énigme 5 23-06-16 à 20:41

gagnéJe dirais qu'il y a 354224848179261915075 dialogues distincts possibles

Merci pour l'énigme

Posté par
trapangle
re : Juin 2016, énigme 5 23-06-16 à 21:19

gagné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)

d(n) = ($$\sum_{i=1}^{n-1} d(i)) + d(n-1)

qui peut se réécrire en

d(n+1) = 3*d(n) - d(n-1)

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 !

Posté par
weierstrass
re : Juin 2016, énigme 5 23-06-16 à 21:21

gagnéBonjour,
je répond :354224848179261915075
Le lien avec Fibonacci est facile à vérifier
Merci pour cette énigme très sympa!

Posté par
masab
re : Juin 2016, énigme 5 23-06-16 à 22:03

gagnéBonjour littleguy,

Le nombre de dialogues distincts est égal à

354224848179261915075

Merci pour cette énigme faisant appel à Fibonacci !

Posté par
Nofutur2
re : Juin 2016, énigme 5 23-06-16 à 22:33

gagné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

Posté par
franz
re : Juin 2016, énigme 5 23-06-16 à 23:53

gagnéLe nombre de dialogues possibles est le 100° terme de la suite de Fibonacci :
354 224 848 179 261 915 075

Posté par
dpi
re : Juin 2016, énigme 5 24-06-16 à 07:57

perduBonjour

Sauf erreur il y a 22100 dialogues possibles pour tout début différent.
Pour mémoire il y aurait 1275  dialogues différents

Posté par
rschoon
re : Juin 2016, énigme 5 24-06-16 à 09:26

gagnéBonjour à tous.

Je propose : 354224848179261915075

Merci pour l'énigme

Posté par
LittleFox
re : Juin 2016, énigme 5 24-06-16 à 11:59

gagné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))


On peut faire plus rapide en utilisant de la memoization ou de la programmation dynamique. Voici une version utilisant la programmation dynamique :
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]

Posté par
Raphi
re : Juin 2016, énigme 5 24-06-16 à 18:28

gagnéSalut, je trouve

\frac {1}{ \sqrt 5} (  \phi^{100} -(1-\phi)^{100} )

avec

 \phi = \frac{1+\sqrt 5}{2}

Posté par
Achdeuzo
re : Juin 2016, énigme 5 25-06-16 à 00:28

gagné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

Posté par
Chatof
re : Juin 2016, énigme 5 25-06-16 à 01:46

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

Posté par
sbarre
re : Juin 2016, énigme 5 26-06-16 à 10:32

perduBonjour à 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.

Posté par
pythamede
re : Juin 2016, énigme 5 27-06-16 à 10:04

gagnéJe trouve 354224848179261915075 dialogues distincts, soit en abrégé \frac{\sqrt{5}+5}{10}\times (\frac{1+\sqrt{5}}{2})^{99}+\frac{5-\sqrt{5}}{10}\times (\frac{1-\sqrt{5}}{2})^{99}

Posté par
saer
re : Juin 2016, énigme 5 29-06-16 à 16:17

perduil 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

Posté par
albatros44
re : Juin 2016, énigme 5 01-07-16 à 09:38

gagnéBonjour

Il  y a 354 224 848 179 261 915 075 solutions

Bonne journée

Posté par
pondy
re : Juin 2016, énigme 5 01-07-16 à 23:05

gagnéBonjour
Je propose:    354224848179261915075 dialogues
Cordialement

Posté par
totti1000
re : Juin 2016, énigme 5 03-07-16 à 16:35

gagnéBonjour littleguy,

Je propose 354224848179261915075 dialogues distincts.

Merci pour l'énigme.

Posté par
LEGMATH
re : Juin 2016, énigme 5 07-07-16 à 13:32

perduBonjour   littleguy ,

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

Merci.

Posté par
benmagnol
re : Juin 2016, énigme 5 09-07-16 à 17:54

perduBonjour

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

Posté par
trapangle
re : Juin 2016, énigme 5 10-07-16 à 10:49

gagné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...

Posté par
benmagnol
re : Juin 2016, énigme 5 10-07-16 à 17:03

perduJ'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.....

Posté par
littleguy
re : Juin 2016, énigme 5 14-07-16 à 18:16

Bonjour,

Clap de fin pour cette énigme et les  \dfrac{(1+\sqrt{5})^{100}-(1-\sqrt{5})^{100}}{2^{100}\times \sqrt{5}} ou bien 3 54224848179261915075 dialogues !

Bravo à ceux qui ont donné la bonne réponse.

Posté par
Chatof
re : Juin 2016, énigme 5 16-07-16 à 12:09

gagné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    a< x\leqslant b
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 !

Posté par
dpi
re : Juin 2016, énigme 5 16-07-16 à 19:01

perduBonjour,

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.

Posté par
dpi
re : Juin 2016, énigme 5 17-07-16 à 07:56

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

Challenge (énigme mathématique) terminé .
Nombre de participations : 21
:)76,19 %23,81 %:(
16 5

Temps de réponse moyen : 84:58:35.
Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !