EXO N - C 2 [Proposed]


  • Math&Maroc

    Soit N2N \geq 2 un entier. On dispose de NN boites B1,B2,,BNB_1, B_2,\ldots,B_N chaque boite BiB_i contient ai1a_i \geq 1 boules.

    Deux personnes AA et BB jouent le jeux suivant:

    • A tour de rôle, chaque joueur choisit une boite et prend autant de boules qu'il le veut (sauf 0, bien sûr !) dans la même boite.
    • Celui qui prend la dernière boule a gagné!

    Montrer que l'un des deux joueur AA ou BB a une stratégie gagnante.



  • On note pip_i le poids des boites ( nombre de boules dans une boite)
    LemmeLemme
    Si tous les poids de boites sont représentés de maniere paire. B a une stratégie gagnante qui consiste à imiter les mouvements de A et c est possible comme toute boite a son symétrique. Donc A sera forcé ) consommer une boite au complet le premier à chaque fois.
    Donc B gagnera ( le nombre de boite est pair)
    Passons à la resolution de l exercice
    On dit qu un poids pp est pairpair si il est porté par un nombre pair de boites sinon il est dit impairimpair
    On note AA l ensemble qui contient les pip_i pairs et aa son cardinal
    Et BB l ensemble qui contient les pip_i impairs et bb son cardinal.
    CasCas 11
    aa et bb sont tous les deux pairs au début du jeu.
    Considérons les mouvements possibles et leur influence sur la parité de aa et de bb

    • Si on mange une boite la parité de aa ou de bb va changer. On appelle ce move eateat Si ce mouvement change la parité de a on le note eat+eat+ sinon on le nomme eat-
    • Si on prend une boite avec un poids pip_i et qu on lui atttribue un poids pjp_j inférieur.
      On a deux cas :
    • pip_i et pjp_j ont la meme parité : Donc la parité de aa et de bb ne va pas changer et ce moovemoove peut etre fait un nombre pairpair et fini de fois .On le nomme similarsimilar
    • pjp_j et pip_i sont la meme parité donc le cardinal de aa ou de bb va changer on appelle ce move jumpingjumping. La aussi on distingue jumping+ jumping + jumpingjumping -

    a et b sont tous les deux pairs au niveau du jeu.
    Le joueur B va 'contrecarrer' le joueur A. Si A eat+eat+ alors B eateat-
    Si A jumping+jumping+ alors Bjumpingjumping-
    Si A similarsimilar alors B similarsimilar en sachant que ce move peut etre fait un nombre pair et fini de fois. Au fur et à mesure du jeu il ne sera plus possible
    Alors a chaque début de tour de A on aura aa et bb sont pairs, tandis que pour BB ils ont une parité differente. Hors il y a un nombre fini d 'étapes possibles alors à une etape au tour de A on aura aa pair et bb nul
    Donc d apres le lemme B a une stratégie gagnante
    Cas2Cas 2
    Si aa et bb sont de parité differente au debut du jeu. Il suffit que A fasse un eateat qui rend les deux cardinaux pairs. Puis d apres le cascas 1 il aura une strategie gagnante.
    Donc dans tous les cas A ou B ont une stratégie gagnante.


Log in to reply
 

Looks like your connection to Expii Forum was lost, please wait while we try to reconnect.