Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
122 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Un jeu de cartes

Envoyé par Domi 
Un jeu de cartes
il y a sept années
avatar
Bonsoir à tous :D

Un petit problème trouvé sur un autre site, simple ?

Sur une ligne on dispose des cartes portant chacune un numéro (quelconque, possiblement égaux). Deux joueurs à tour de rôle prélèvent une carte à l'une des extrémités de la ligne jusqu'à épuisement des cartes. Puis chacun fait ses comptes et celui qui a récupéré une somme maximale a gagné.

En fonction du nombre de cartes et des numéros choisis, quel joueur a une stratégie gagnante ? Quelle est-elle ? Comment maximiser les gains ou minimiser les pertes ?

Merci d'avance pour la participation.
Domi



Edité 1 fois. La dernière correction date de il y a sept années et a été effectuée par AD.
Re: Un jeu de carte
il y a sept années
avatar
Bonjour Domi,

Je note $n$ le nombre de cartes et $c_1,c_2,\ldots,c_n$ les numéros qu'elles portent. Alors :

1) Si $n=2p$ est pair, le joueur qui commence peut récupérer toutes les cartes de rang pair ou toutes les cartes de rang impair. Il peut donc toujours gagner ou faire match nul.

Je ne pense pas qu'il puisse faire mieux si l'autre joue parfaitement (mais j'ai la flemme de le démontrer proprement). Son gain maximal est donc
$$\max(c_1+c_3+\ldots+c_{2p-1},c_2+c_4+\ldots+c_{2p}).$$

2) Si $n=2p+1$ est impair, alors :

- si le premier joueur choisit $c_1$, alors (si mon idée précédente est correcte) le deuxième peut obtenir au plus $G_2=\max(c_3+c_5+\ldots+c_{2p+1},c_2+c_4+\ldots+c_{2p})$. Le gain du premier est alors $G_1=c_1+\min(c_3+c_5+\ldots+c_{2p+1},c_2+c_4+\ldots+c_{2p})$.

- si le premier joueur choisit $c_{2p+1}$, alors le deuxième peut obtenir au plus $G'_2=\max(c_1+c_3+\ldots+c_{2p-1},c_2+c_4+\ldots+c_{2p})$. Le gain du premier est alors $G'_1=c_{2p+1}+\min(c_1+c_3+\ldots+c_{2p-1},c_2+c_4+\ldots+c_{2p})$.

Le premier joueur peut donc gagner si et seulement si $G_1>G_2$ ou $G'_1>G'_2$.

En bidouillant un peu on voit que c'est équivalent à
$$c_1+c_{2p+1}>c_2+c_4+\ldots+c_{2p}-(c_3+c_5+\ldots+c_{2p-1})>-|c_1-c_{2p+1}|.$$
et la stratégie du premier joueur est simplement de toujours choisir la plus grosse carte.
Re: Un jeu de carte
il y a sept années
avatar
Merci pour ta réponse Juge Ti :D

Tu as raison , pour un nombre pair de cartes le premier joueur va au pire annuler mais dans certains cas il peut faire mieux que la différence entre les sommes de rangs pairs et impairs .

Un exemple : 3 ; 1 ; 2 ; 4 , les rangs pairs et impairs ont la même somme mais le premier joueur gagne au moins 2 .

Pour un nombre impair de cartes , prendre systématiquement la plus grosse carte est clairement mis en défaut par des positions de ce style : 1;1;1;9;2 .

Je soupçonne ce problème d'être très difficile .

Domi



Edité 1 fois. La dernière correction date de il y a sept années et a été effectuée par Domi.
Re: Un jeu de carte
il y a sept années
avatar
Ah oui, tu as raison, mon gain maximal est faux, donc mon raisonnement dans le cas impair ne marche pas.
Re: Un jeu de carte
il y a sept années
Bonsoir à tous,

Je pense aussi que le cas général de ce problème doit être extrêmement difficile.

Pour un nombre pair n de cartes, on a déjà observé que le premier joueur peut imposer de prendre les cases de rang pair ou impair. Le jeu n'a d'intérêt que si les sommes pair et impair sont égales.

On observe qu'après un coup de chaque joueur, on a une situation à n-2 cartes où n-2 est encore pair.

Le joueur 1 peut à nouveau étiqueter pair-impair les cartes restantes et imposer d'avoir au moins la moitié du total restant.

Ce qui veut dire que si le premier joueur a pris un avantage au premier coup, il est assuré de le conserver.

Bien entendu, s'il n'a pas pu prendre l'avanatage au premier coup, il peut éventuellement le prendre plus tard et gagner.

Donc, dans le cas n pair, avec égalité des sommes de rang pair et de rang impair, le premier joueur gagne s'il peut à un moment prendre l'avantage.

Dans cet exemple à 8 cartes :

3 3 4 2 5 6 3 4

le premier joueur gagne en prenant le 4 : quelle que soit la carte choisie par le joueur 2, il a un avantage qu'il est sûr de conserver.

les sommes de rang pair et impair sont égales à 15.

Aldo
Re: Un jeu de cartes
il y a sept années
Dans le cas n impair, après son premier coup, le premier joueur laissera une situation à nombre pair (n-1) de cartes et le joueur 2 sera assuré de marquer au moins la différence entre le total des cartes de rang pair et de rang impair.

Le joueur 1 ne peut donc espérer s'en sortir que si la valeur de la carte qu'il choisit est supérieure à cette différence.

Même sans calculer cette différence, il ne peut faire mieux que de choisir au premier coup la plus grande possible.

Le contre-exemple donné par Domi : 1;1;1;9;2 n'en est pas vraiment un puisque le joueur en premier perd quelle que soit la carte choisie au premier coup.

En quelque sorte, dans le cas n impair, le meilleur jeu du premier joueur est extrêmement simple : prendre toujours la carte la plus grande et advienne que pourra !

Bien entendu, idem pour le meilleur jeu du joueur en second dans le cas n pair.

Aldo
Re: Un jeu de cartes
il y a sept années
avatar
Pas bête l'idée de reconsidérer la situation à chaque étape quand n est pair. Voilà un programme Python basé sur cette stratégie.

def coup(cartes):
    n=len(cartes)
    if n%2==1:
        if cartes[0]>cartes[n-1]:
            return 0
        else:
            return n-1
    elif sum(cartes[::2])>sum(cartes[1::2]):
        return 0
    else:
        return n-1
    
def jeu(cartes):
    n=len(cartes)
    g=[0,0]
    j=0
    while n>0:
        c=coup(cartes)
        print('Joueur',j+1,'prend',cartes[c])
        g[j]+=cartes[c]
        del cartes[c]
        j=1-j
        print('Cartes ',cartes)
        print('Gains ',g)
        n-=1

Voilà ce que ça donne sur les exemples précédents :

>>> jeu([3,1,2,4])
Joueur 1 prend 4
Cartes  [3, 1, 2]
Gains  [4, 0]
Joueur 2 prend 3
Cartes  [1, 2]
Gains  [4, 3]
Joueur 1 prend 2
Cartes  [1]
Gains  [6, 3]
Joueur 2 prend 1
Cartes  []
Gains  [6, 4]

>>> jeu([1,1,1,9,2])
Joueur 1 prend 2
Cartes  [1, 1, 1, 9]
Gains  [2, 0]
Joueur 2 prend 9
Cartes  [1, 1, 1]
Gains  [2, 9]
Joueur 1 prend 1
Cartes  [1, 1]
Gains  [3, 9]
Joueur 2 prend 1
Cartes  [1]
Gains  [3, 10]
Joueur 1 prend 1
Cartes  []
Gains  [4, 10]

>>> jeu([3,3,4,2,5,6,3,4])
Joueur 1 prend 4
Cartes  [3, 3, 4, 2, 5, 6, 3]
Gains  [4, 0]
Joueur 2 prend 3
Cartes  [3, 3, 4, 2, 5, 6]
Gains  [4, 3]
Joueur 1 prend 3
Cartes  [3, 4, 2, 5, 6]
Gains  [7, 3]
Joueur 2 prend 6
Cartes  [3, 4, 2, 5]
Gains  [7, 9]
Joueur 1 prend 5
Cartes  [3, 4, 2]
Gains  [12, 9]
Joueur 2 prend 3
Cartes  [4, 2]
Gains  [12, 12]
Joueur 1 prend 4
Cartes  [2]
Gains  [16, 12]
Joueur 2 prend 2
Cartes  []
Gains  [16, 14]
Re: Un jeu de cartes
il y a sept années
On peut poursuivre un peu l'anayse dans le cas n pair et égalité des sommes des cartes paires et impaires.

Il semblait difficile d'établir une stratégie pour le joueur en premier mais cela va être grandement facilité par la connaissance de la stratégie adverse !

On suppose que le joueur en premier ne peut pas prendre immédiatement l'avantage.

A partir du moment où le joueur 1 connaît d'avance la meilleure réponse adverse, comme il ne dispose pour son premier coup que de deux possibilités, il n'a en fait que deux variantes à étudier : pour chacune des cartes qu'il peut prendre au premier coup, il peut calculer la différence des cartes de rang pair et impair après le coup du deuxième joueur et opter pour la différence la plus avantageuse.

Mais il faut tenir compte de l'avantage pris par le joueur en second sur la première carte !

On vérifie aisément que dans les deux cas, la différence "cartes de rang pair et impair" est égale à la différence des deux premières cartes prises (on partait d'une différence nulle).

Ce qui veut dire que les deux stratégies sont équivalentes !

Donc, stratégie du joueur en premier dans le cas n pair : jouer n'importe quoi jusqu'à ce que se présente une possibilité de prendre l'avantage, ce qui lui assure la victoire.

Si cette possibilité ne se présente jamais, la partie sera nulle.

Jusqu'ici, on s'est uniquement basé sur l'objectif de remporter la partie. Le fait d'optimiser gains ou pertes est une autre affaire...

Aldo
Re: Un jeu de cartes
il y a sept années
Bon, le cas n impair n'est pas aussi simple.

Par exemple

2 6 3 1 3 1 1

Si le joueur 1 commence modestement par le 1 de droite, il gagne.

S'il commence par le 2 à gauche, il perd. En effet, Joueur 2 prend 6, joueur 1 prend 3 et joueur 2 qui a déjà l'avantage joue dans une configuration paire, il est sûr de gagner.

C'est cette possibilité locale (2 6 3) pour le joueur 2 de prendre l'avantage malgré un coup de moins qui crée le déséquilibre...

Aldo
Re: Un jeu de cartes
il y a sept années
avatar
On peut toujours calculer le gain maximal de manière récursive :
$$\left\{\begin{array}{l}\operatorname{gainmax}(c_1)=c_1\\\operatorname{gainmax}(c_1,\ldots,c_n)=\max(c_1-\operatorname{gainmax}(c_2,\ldots,c_n),c_n-\operatorname{gainmax}(c_1,\ldots,c_{n-1}))\end{array}\right.$$
Ça m'étonnerait qu'on puisse donner à partir de là une expression simple de $\operatorname{gainmax}(c_1,\ldots,c_n)$ en fonction de $c_1,\ldots,c_n$, mais on peut faire un programme pour le calculer et donner la meilleure stratégie :

def gain_max(cartes):
\quad n=len(cartes)
\quad if n==1:
\quad\quad return [[cartes[0]],cartes[0]]
\quad a=gain_max(cartes[1:n])
\quad b=gain_max(cartes[0:n-1])
\quad gain_a=cartes[0]-a[1]
\quad gain_b=cartes[n-1]-b[1]
\quad if gain_a>gain_b:
\quad\quad return [[cartes[0]]+a[0],gain_a]
\quad else:
\quad\quad return [[cartes[n-1]]+b[0],gain_b]

Avec l'exemple d'Aldo ci-dessus :
> gain_max([2,6,3,1,3,1,1])
[[1, 1, 3, 1, 3, 6, 2], 1]
La liste [1, 1, 3, 1, 3, 6, 2] donne l'ordre dans lequel les joueurs prennent les cartes s'ils jouent au mieux, et le 1 est le gain maximal du joueur qui commence.
Re: Un jeu de cartes
il y a sept années
avatar
Ma première idée avait été de faire comme Juge Ti ( la récursivité ) mais je n'ai pas réussi à trouver de relation entre les valeurs des cartes donnant au moins le gagnant pour le cas impair .

Le cas pair est complètement traité par les remarques déjà faites à condition de ne pas chercher pas à maximiser le gain .

Nous avons tous choisi des étiquettes entières et positives alors que rien ne l'imposait . On peut remarquer qu'on ne change pas le problème en multipliant les étiquettes par une constante ( non nulle ) , on peut donc considérer les étiquettes entières . En enlevant à chaque étiquette la plus petite d'entre elles on peut aussi considérer qu'elles sont toutes positives ou nulles , on ne change pas le résultat quand les cartes sont en nombre pair , on le change de +/-1 dans le cas contraire ( sans changer la stratégie ) .

Je ne sais si quelqu'un à d'autres idées , personnellement je garde le problème dans un coin de ma mémoire .

Merci à Juge Ti et Aldo :D

Domi



Edité 1 fois. La dernière correction date de il y a sept années et a été effectuée par Domi.
Re: Un jeu de cartes
il y a sept années
Considérons le cas n pair.

Supposons que « total des cartes de rang pair » = « total des cartes de rang impair ».

On s’intéresse uniquement au cas où les deux joueurs cherchent uniquement à gagner la partie, sans tenter d’optimiser ce gain.

Comme déjà vu, le joueur en premier gagne s’il parvient à un moment quelconque à prendre un avantage malgré la réplique du joueur en second.

Par exemple

8 1……..2

Le joueur 1 prend le 8 à gauche et gagne car le joueur 2 ne peut pas égaliser.

Mais il y a mieux, le joueur 1 ne gagne que si, à un moment du jeu, il prend l’avantage quelle que soit la réplique du joueur 1. Cela semble évident, en effet, dans le cas contraire, on jouera jusqu’à épuisement des cartes sans que le joueur 2 perde.

Mais il n’y a pas toujours un gros 8 aussi "évident" à voir :

1 1 8 1………..

Si le joueur 1 commence par le 1 de gauche, il gagnera lorsque le joueur 2 prendra le 1 qui suit, lui offrant ainsi le magnifique 8.

Mais rien n’oblige le joueur 2 à prendre ce 1, il peut prendre une carte à droite !

Attention aussi à une grosse carte qui pourrait être un leurre :

2 4 9 7………....

Le joueur 1 peut prendre le 2 en espérant que le joueur 2 se précipite sur le 4 et lui offre le magnifique 9.

Et bien, cela ne mène nulle part car le joueur 2 poursuivra sur le 7 et son total des deux premières cartes (4+7) est égal à celui du joueur 1 (2+9).

On va appeler alternance gagnante une suite de cartes telle que le joueur 1 obtienne un avantage après que chacun ait pris une carte alternativement du même côté.

Par exemple :

2 3 2 5 8 1……....

est une alternance gagnante à gauche puisque 2+2+8 > 3+5+1

Autre exemple

………………..2 9 5 1

est une alternance gagnante à droite car 1+9 > 5+2

Supposons que la position initiale comporte une alternance gagnante à gauche.

Le joueur 1 prend la première carte de cette alternance et attend que son adversaire prenne la seconde.

Mais ce n’est pas si simple car le joueur en second peut choisir de jouer à droite !

Ceci nous donne la clé du mystère :

On va aussi calculer l’alternance à droite mais bien sûr en considérant que la carte déjà prise par le joueur 1 fait partie de l’alternance.

Exemple

2 3 8 1 ………….1 9 2 1 2

présente une alternance gagnante à gauche.

Joueur 1 prend donc le 2 de gauche.

Nous calculons donc l’alternance à droite en y ajoutant la première carte de joueur 1 :

…………………1 9 2 1 2 (2)

ce qui donne (2)+ 1 + 9 qui est supérieur à 2 + 2 + 1

Joueur 2 est donc pris dans la tenaille : qu’il choisisse la carte de gauche ou de droite, il tombe dans une alternance gagnante pour joueur 1.

Le jeu est donc résolu : joueur 1 gagne si et seulement si l’une des cartes pour son premier coup lui offre une alternance gagnante à gauche ET à droite.

Exemples :

2 8 6 ………. 7 9 2 1

Joueur 1 gagne en prenant le 1 de droite car (1) + 8 > 2 + 6 ET 1+9 > 2+7.

1 1 3 1 2 4 1 1

Si joueur 1 prend le 1 de gauche, il obtient une alternance gagnante à gauche mais pas à droite, partie nulle !

S’il prend le 1 de droite, il a une alternance gagnante à droite mais pas à gauche, partie nulle.

Bien entendu, cela fonctionne avec toute sorte de nombres, entiers, réels, etc avec quand même une addition et un ordre total.

Le cas n impair nous oblige à entrer dans la considération du meilleur gain possible dans le cas n pair.

En effet, dans le cas n impair, après le premier coup de joueur 1, le joueur 2 se trouve face à une situation paire mais avec un handicap égal à la première carte choisie par 1. Il est donc crucial pour lui de gagner plus que ce handicap, ce qui me semble peu calculable autrement que par ordinateur.

Bien entendu, dans le cas n impair, la partie n’a d’intérêt que si la somme des cartes de rang impair est supérieure ou égale à la somme des cartes de rang pair. Dans le cas contraire, le joueur en second est assuré de la victoire.

Aldo
Re: Un jeu de cartes
il y a sept années
Bonjour,

J'ai l'impression que pour résoudre ce jeu il "suffit" d'appliquer un algorithme minimax : Page wikipedia

A chaque coup le joueur essaye de minimiser le score maximum que l'autre joueur peut atteindre. Pour résoudre le problème on est obligé de dérouler presque tout l'arbre (le "presque" vient du fait qu'on peut sans doute trouver des heuristiques pour stopper la recherche dans certaines branches)
Re: Un jeu de cartes
il y a sept années
Considérons l’exemple suivant (n pair) :

2 3 2 3 2 3 5 1 …………… 3 6 2 1 2 1 2

D’après ce qui a été vu, le joueur 1 devrait l’emporter en prenant le 2 de gauche puisque

2+2+2+5 > 3+3+3+1

et

2+1+1+6 > 2+2+2+3

C'est-à-dire que le joueur 2 se retrouvera en infériorité, qu’il choisisse de jouer à gauche, offrant le 5 ou de jouer à droite, offrant le 6.

Mais le joueur 2 peut subtilement opter pour le choix retardé !

Il prend tout ce qu’il peut à gauche sauf le 3 fatidique qui offrirait le 5, puis il prend à droite.

Avant d’arriver au 2 fatidique qui offrirait le 6, faisons les comptes :

Joueur 1 : 2 + 2 + 2 +1 +1 contre Joueur 2 : 3 + 3 + 2 +2

Il mène déjà de 2 !

Il peut allègrement prendre le 3 de gauche qui offre le 5 (ou même le 2 de droite qui offre le 6 car un 3 suit) sans se retrouver en désavantage.

La condition que nous avions donnée pour une victoire de joueur 1 était nécessaire mais pas suffisante.

Pour que joueur 1 s’impose, il lui faut des conditions encore plus favorables : que chacune des deux fortes cartes de gauche et de droite lui apporte l’avantage, quel que soit le moment où le joueur 2 se décidera à lui offrir une de ces cartes.

Nommons les cartes G1 G2 G3 ….. D3 D2 D1,

Avec G comme gauche et D droite.

Le joueur 1 gagne en prenant la carte G1 si la double condition suivante est réalisée :

Il existe deux cartes Gi et Dj (i impair et j pair) telles que, pour tout p impair (p<j-2) :

G1+G3+G5+…+Gi+D2+D4+D6+…+D(j-2) > G2+G4+G6+...+G(i+1)+D1+D3+D5+.…+Dp

ET

Pour tout q pair (q<i-2)

G1+G3+G5+…+G(i-2)+D2+D4+D6+…+Dj > G2+G4+G6+…+G(i-3)+D1+D3+D5+…+D(j+1)

De la même manière, le joueur 1 gagne en commençant par la carte D1 si la condition symétrique est réalisée (il suffit d’intervertir D et G).

Résumé : le joueur 1 gagne si, pour l’une des cartes G1 ou D1, la double condition est réalisée.

Exemple simple :

2 2 5 4 …. 4 6 2 1 2

Le joueur 1 prend le 2 de gauche.

Si le joueur 2 prend aussi à gauche, joueur 1 prend le 5 et joueur 2 prend le 4

Si le joueur 2 prend uniquement à droite, il perd aussi :

2+1+6=9, alors que 2+2+4=8

Par contre le joueur 2 peut se sauver en prenant une fois seulement à droite (le 2) sur lequel joueur 1 prend le 1 contigu à droite.

Joueur 2 a ainsi grappillé une unité salvatrice, il retourne jouer à gauche, offrant le 5 mais conserve l’équilibre : 2+1+5 = 2+2+4

Joueur 1 ne gagnera que si ce genre de sauvetage n’existe pas :

2 3 2 3 8 1…….1 7 2 2 2

Joueur 1 commence en prenant le 2 de gauche.

Quel que soit le moment choisi par joueur 2 pour offrir le 8 à gauche ou le 7 à droite, il permettra à joueur 1 de prendre l’avantage et donc de gagner la partie.

Nous allons tenter de voir de combien le joueur 1 peut gagner la partie (lorsqu’il gagne !)

Supposons que la double condition ci-dessus soit réalisée.

Joueur 1 est donc gagnant.

Joueur 2 choisira la suite concédant le plus petit avantage possible.

Soit A cet avantage.

On peut vérifier que Joueur 1 et Joueur 2 n’ont pris respectivement que des cartes dont les rangs étaient tous de même parité.

Dans cette situation existe donc une différence de A entre le total des cartes de rang pair et le total des cartes de rang impair.

Joueur 1 peut donc au minimum remporter de A la fin de la partie.

Sur l’ensemble de la partie, il est assuré de gagner au moins de 2A.

Résumé : si joueur 1 trouve un début de partie lui assurant un avantage de A, il peut gagner la partie d’au moins 2A.

Aldo

P.S. Je me rends bien compte que tout cela n'est pas super lisible !
Re: Un jeu de cartes
il y a sept années
Voici une petite explication pour rendre les choses claires (on est toujours dans le cas n pair) :

G1..........G(i-1) Gi G(i+1) ......................D(j+1) Dj D(j-1)............D1

Joueur 1 prend G1

Tôt ou tard, Joueur 2 devra prendre G(i-1) et entrer dans la séquence G(i-1) Gi G(i+1)

ou prendre D(j-1) et entrer dans la séquence D(j-1) Dj D(j+1).

Joueur 1 gagne si ces deux séquences se terminent à son avantage, quelque soit le moment choisi par Joueur 2 pour prendre G(i-1) ou D(j-1).

Aldo
Re: Un jeu de cartes
il y a sept années
Une remarque : la méthode exposée peut sembler purement théorique et peu utilisable. Faut-il tester tous les couples de nombres pour trouver les Gi et Dj ?

Il y a deux moyens qui permettent de s'en sortir rapidement.

Tout d'abord, une carte Gi ne peut être candidate que si elle est supérieure à la suivante G(i+1). En effet, avant de prendre Gi, le joueur 1 n'a pas encore d'avantage. S'il a l'avantage en prenant Gi et en laissant G(i+1) c'est au minimum que Gi > G(i+1)

Ensuite, le critère que nous avions donné précédemment concernant les alternances gagnantes, s'il n'est pas suffisant, permet de sérieusement débroussailler la recherche : on n'aura à considérer que les nombres présentant une alternance gagnante (à gauche pour Gi et à droite pour Dj).

Exemple pratique :

1 2 1 2 4 3 7 3 1 6 2 3 2 2 4 1

On vérifie d'abord que la somme des cartes de rang pair = somme des cartes de rang impair = 22

En prenant le 1 de gauche, le joueur 1 fait apparaître les cartes Gi = le 7 à gauche et Dj = le 4 le plus à droite.

Joueur 2 devra tôt ou tard céder un de ces cartes. Quelle que soit la manière choisie, Joueur 1 prendra alors l'avantage.

Le 4 de gauche était aussi un candidat mais il est éliminé car ne présente même pas le critère de l'alternance gagnante :

1+1+4 n'est pas supérieur à 2+2+3.

Après le premier coup de joueur 1 qui prend le 1 de gauche, le joueur 2 peut limiter la casse en ne perdant que d'une unité en prenant le 2 de gauche : Joueur 1 prend le 1 de gauche - Joueur 2 prend le 1 de droite - Joueur 1 prend le 4 de droite - Joueur 2 prend le 2 à droite.

1+1+4 contre 2+1+2

Comme déjà vu, Joueur 1 pourra par la suite au moins doubler cet avantage et gagner la partie par une différence de 2.

Aldo
Re: Un jeu de cartes
il y a sept années
avatar
Bonsoir Aldo

J'ai pris un moment pour lire ta prose :D

J'ai bien compris que tu te plaçais dans le cas d'un nombre pair de cartes avec des sommes égales sur les pairs et impairs et je vois ce que tu entends par alternance gagnante gauche ou droite , mais je n'ai pas trop compris les Gi et Dj .

En tout cas ça semble compliqué et je ne suis pas sûr que même dans ce cas "simple" on puisse faire beaucoup mieux que la solution électronique du Juge Ti .

J'ai peut-être raté quelque chose .

Domi
Re: Un jeu de cartes
il y a sept années
Bonsoir Domi,

merci d'avoir eu ce courage !

On analyse le cas où Joueur 1 prend la carte à gauche G1.

Il faut bien voir que tout au long de la partie, Joueur 1 est toujours mené (à égalité de coups joués de part et d'autre) ou au mieux à égalité. En effet, s'il prend l'avantage à un moment quelconque, une stratégie simple lui assure la victoire.

Il ne gagnera donc que s'il y a deux cartes de rang impair Gi à gauche et Dj à droite qui lui apportent un avantage s'il prend l'une d'elles. Tôt ou tard, Joueur 2 devra prendre G(i-1) ou D(j-1), offrant ainsi la carte fatidique Gi ou Dj.

Bien entendu, la recherche de ces cartes Gi et Dj n'est pas immédiate. On a le premier critère Gi > G(i+1), puis le critère des alternances gagnantes.

Une fois les cartes candidates repérées, il faudra calculer toutes les possibilités. C'est à ce moment qu'un ordi peut s'avérer utile...

Aldo
Re: Un jeu de cartes
il y a sept années
avatar
Un petit prolongement du problème ( toujours sur le même site ) .

Le premier joueur découpe un gâteau comme il le souhaite .

[attachment 28310 Gteau.png]

Le deuxième choisit une part et ensuite chacun va choisir une part au bord de l'espace laissé vacant . A la fin , celui qui a amassé le plus de gâteau a gagné .

A priori on ne donne aucune chance au "découpeur" mais comment le prouver ?

Domi
Re: Un jeu de cartes
il y a sept années
Le découpeur peut tout de même égaliser s'il partage le gâteau en un nombre pair de parts strictement égales.

Mais peut-être faut-il supposer que des parts strictement égales ça n'existe pas ?
Re: Un jeu de cartes
il y a sept années
avatar
Le but est de manger strictement plus :D

Domi
Re: Un jeu de cartes
il y a sept années
Il s'agit donc de trouver une stratégie gagnante pour le découpeur ou au contraire de démontrer qu'il n'y en a pas.

Pour le moment, je n'ai pas obtenu mieux que 2 7 9 1 4 1 5 (disposés en cercle).

Le découpeur gagne sur tous les choix du premier joueur sauf un ! (lequel ?...).

Bon, la recherche continue.

Aldo
Re: Un jeu de cartes
il y a sept années
avatar
Un petit "up" pour ceux qui n'auraient pas vu ou oublié :D

Domi
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 140 708, Messages: 1 376 285, Utilisateurs: 25 644.
Notre dernier utilisateur inscrit EPFL.


Ce forum
Discussions: 8 468, Messages: 63 329.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page