Je dois faire ceci en algotithme:

"vous disposez de 171 bonbons, vous êtes 2 à piocher ds le panier de bonbons. Chaque joueur peut piocher obligatoirement entre 1 et 4 bonbons. Sachant que le dernier qui pioche le dernier bonbon à perdu. Donner l'algorithme qui permet d'avoir une stratégie gagnate en jouant en 2ème position."

Le problème c'est que je n'arrive pas à savoir comment on peux faire ça, déjà que l'algo c'est pas mon fort mais si je pourrai avoir un peu d'aide pour savoir comment ça marche, je me suis penché sur le truc mais je ne vois pas comment faire, le fait que ce soit un nbre impair n'y fait rien puisqu'on peux piocher entre 1 et 4 bonbons

merci pour votre aide...

Le nombre est un multiple de 5 +1, complète la prise du joueur adverse à 5, c'est la stratégie gagnante.

kaoron, une réponse comme cela ne l'aide pas beaucoup.

J'imagine que ce problème arrive dans un cours sur la programmation dynamique. L'idée est de décrire si un état est gagnant ou perdant en fonction des états précédents.
La question est si tu es a l'état n, as tu un coup gagnant ? L'information dont tu disposes est que l'état n=1 est perdant. Tu en déduis que les états n=2,3,4,5 sont gagnant: il suffit de laisser un seul bonbon.
Je te laisse finir.

Bonsoir godrik

Bah elle est pas bien ma réponse ?
La question n'est pas de savoir comment se démerder étant à l'état n pour avoir une stratégie gagnante, mais de trouver la stratégie gagnante avec 171 bonbons, en commençant second. C'est typiquement un problème "la réponse est dans la question".

Tu veux construire une solution par récurrence, moi je vois qu'il suffit juste de reconnaître et travailler sur Z/nZ, et se débrouiller pour ramener le nombre de bonbons à kn+1 à chaque tour.
Donc, je signe : le nombre initial de bonbons est un multiple de 5 + 1, or toutes les prises de l'adversaire peuvent être complétées à 5, c'est la stratégie gagnante... et une preuve par récurrence sur Z/nZ est bien plus simple à mettre en oeuvre que de partir des solutions gagnantes.

Mais je ne comptais pas lui mâcher autant le travail en explicitant l'anneau sur lequel il devait travailler. (D'ailleurs, même pas besoin de connaître la notion d'anneau, un modulo suffit à construire la preuve)

Kao.

Je suis bien plus d'accord avec cette réponse parce qu'elle est détaillé.
Je ne pense pas que la premiere soit vraiment utile pour comprendre pourquoi ca marche. Celle ci l'est beaucoup plus.

Je suis d'accord que la question n'est pas de construire la suite des états gagnants cependant c'est la démarche général pour résoudre ce style de probleme. Tout ne tombe pas toujours aussi bien que kn+1

De plus je pense que c'est assez pédagogique de commencer par construire la suite des états gagnant et de s'apercevoir a posteriori qu'il existe une forme close permetant de savoir quoi faire.

"Tout ne tombe pas toujours aussi bien que kn+1."

Dans ce cas, le joueur adverse peut utiliser cette heuristique et compléter lui même à kn+1, et quelle que soit la stratégie utilisée face à ça, elle sera nécessairement perdante (puisqu'il utilise une stratégie gagnante).

C'est pas juste pour avoir le dernier mot, mais on m'a rétorqué (salut olympi) que le nombre initial de bonbons n'avait pas d'importance...

mmm, je parlais de jeu avec des regles plus compliqués. Il y a plein de variante avec plusierus tas d'allumettes ou le nombre de prise de chaque tas suit une regle precise (au pif, que la somme des allumettes prise dans les deux tas soit un nombre premier sachant que tu es obligé d'en prendre une au moins)

De plus, le nombre d'allumette est important, s'il en reste kn, tu as perdu !

a la relecture, substitué allumette par bonbon

Je remonte ce post pour y appliquer un peu de théorie des jeux.

Soit un entier N, énoncé de ce problème.
On peut construire le graphe des états du jeu, tel que chaque état/noeud n du graphe est étiqueté par le nombre de bonbons restants, et chaque arc représente une transition possible entre deux états.

Exemple de partie :
N=5
5->4->1->0
Tour de J1 : prend 1, reste 4
Tour de J2 : prend 3, reste 1
Tour de J1 : prend 1, reste 0
J1 perd

Le graphe est orienté et sans circuit. Par transition unitaire, on peut démontrer qu'à l'état nk tout état dans [nk-1,0] est accessible par un chemin de longueur finie, et que tout jeu se termine en 0.
L'état n=1 est un état victoire pour le joueur qui l'atteint, car son adversaire n'a plus d'autre choix que de prendre le dernier bonbon, donc de perdre. Tout autre noeud que 1 (et 0 le noeud défaite) permet une transition ne menant pas à la défaite.

On veut déterminer s'il existe une stratégie gagnante pour le joueur 1, ou plus formellement : existe-t-il un noyau de jeu accessible par le joueur 1.

Un noyau est un sous ensemble de sommets S tel que tout successeur d'un sommet x de S n'appartient pas à S (S est stable), et pour tout sommet x hors de S il existe un successeur dans S (S est absorbant).
Pratiquement, si 1 (noeud victoire) appartient à S, alors J1 rejoint S signifie que :
- tout successeur d'un noeud de S n'est pas dans S, donc J2 ne peut pas atteindre le noeud victoire 1.
- tout noeud hors de S a un successeur dans S, donc si J2 est hors de S et n'a pas perdu, J1 peut rejoindre S. De plus par la propriété définie plus haut, puisque l'état atteint par J2 n'est ni 1 ni 0, alors il existe un chemin de longueur finie vers le noeud victoire 1.

L'existence d'un noyau accessible par le joueur 1 signifie donc l'existence d'une stratégie gagnante pour celui-ci (il existe un chemin vers le noeud victoire 1, et J2 peut être maintenu hors du sous ensemble contenant ce noeud).

On considère le graphe de jeu privé de l'état défaite (seul l'état victoire compte car les joueurs sont raisonnables et ne vont pas dans l'état défaite s'il existe une alternative).
On définit une fonction de Grundy toute application g de X dans N (ens des entiers naturels, saloperie de forum qui n'accepte pas l'utf8), g(x) étant le plus petit entier tel que g(x)!=g(y) pour tout y successeur de x. g est unique pour un graphe orienté sans circuit donné (théorème de Grundy).
Cela signifie que pour tout x,y, si g(x)=g(y), alors y n'est pas successeur de x et vice versa (stable), et si g(x) < g(y) alors il existe un successeur z de y tel que g(x)=g(z). Soit k<=g(x) pour tout x, l'ensemble des x tels que g(x)=k est donc absorbant (i.e. : si k est la valeur minimale des g(x), alors k est absorbant par la propriété d'une fonction de grundy)

On construit la fonction g du graphe de jeu privé de 0.
g(1)=0, g(2)=1, g(3)=2, g(4)=3, g(5)=4...
g(6)=0 ! g(7)=1...
g(11)=0...

Les états n=1mod5 ont une valeur égale à 0 (minimale), donc forment un ensemble stable et absorbant. Le noeud victoire en fait partie : cet ensemble est le noyau du jeu. Rejoindre un de ces états est la stratégie gagnante de J1.

CQFD.

Un peu long, et encore j'ai fait pas mal de raccourcis ! Ça change de ma première approche :D

Peut être même que tu pourrais avoir un résultat similaire si tu créais ton graphe au moment ou le nombre de nombre d'éléments à piocher devient inférieur ou égal à 15 voire moins.

Seuls les derniers tirages son véritablement significatifs et amènent dans des situations irréversibles.

Faux. La stratégie gagnante est la même quelle que soit la taille du graphe. Si un joueur peut jouer cette stratégie et ne le fait pas, alors son adversaire peut la jouer a son tour et s'assurer la victoire en jouant optimalement. Tous les coups sont significatifs, même avec un million et un bonbons.

_skip : on joue ensemble ? tu joues au pif jusqu'à ce qu'il ne reste que 15 bonbons ?

Juste, il existe dès le départ une stratégie de sanctuaire...
Honte à moi qui bosse dans la programmation de simulations.

• pointe du doigt*

Bouuuuuuuuhhhh!!!!!!!!

Mais c'est un joli problème quand même.
Si j'avais lu plus attentivement la partie de la fin avec le modulo j'aurai vu qu'on pouvait réguler à 100% la distance de déplacement parcourue entre chacun de ses tours. Ca paraît même super logique now.

Je m'en rappellerai si une fois je suis sélectionné pour fort boyard.

_skip : bof, c'est pas la honte. Les problèmes de la vraie vie ne sont jamais comme ça.
Sinon, fais gaffe, à fort boyard c'est modulo 4 qu'il faut raisonner (et il faut sortir une blague histoire d'avoir le temps de compter le nombre de batonnet, qui est variable me semble-t-il).

Merci kaoron, pour cette preuve detaille
Il y a plein de variante de ce jeu, si vous etes interesse.
une variante:
-on ne peut prendre que 1, 3 ou 5 batons
-il y a plusieurs tas et on ne peux prendre que d'un tas a la fois
-il y a plusieurs tas et soit on retire d'un seul tas ou de tous les tas a la fois.

tiens c'est rigolo ce jeu, je ne connaissais pas. Les regles sont bizarre. J'ai fini par battre l'IA au bout de 5 parties, mais on sent qu'il faut de l'experience pour bien comprendre ce qu'il se passe.

À ma connaissance, ça fait longtemps qu'au contraire, ce jeu est résolu (c'est-à-dire que toutes les positions sont calculé et qu'un ordinateur est imbattable).