Un nou dia, un nou problema:
Tenim una taula amb $n$ monedes i el següent joc per a dos jugadors (que anomenarem el jugador primer i el jugador segon): començant pel primer i per torns, cada jugador agafa una o dues monedes. Dels dos jugadors, el que retiri la última haurà perdut.Doneu una estratègia que permeti guanyar el joc. Si depèn de si s'és el jugador primer o el segon, especifiqueu-ho en cada cas.
Bona caça!
.png)
3 comentaris:
Tot depèn del nombre de monedes (mòdul 3).
Si només hi ha una moneda, òbviament perd el primer jugador.
Si hi ha dos monedes, el primer jugador guanya agafant-ne una.
Si hi ha 3 monedes, el primer jugador guanya agafant-ne 2.
Si hi ha 4 monedes, el primer jugador perd faci el que faci, perquè si n'agafa una, el segon té 3 monedes (i per tant, estratègia guanyadora), i si n'agafa 2, el segon té 2 monedes (altre cop estratègia guanyadora).
D'aquí en endavant, podem demostrar per inducció que si el nombre de monedes és congruent amb 1 mòdul 3, el primer jugador perd, i sinó, té estratègia guanyadora.
- Si el nombre de monedes és múltiple de 3, el primer jugador ha d'agafar 2 monedes, amb el que deixa al segon amb monedes=1(mod 3), i per tant, perdut.
- Si el nombre de monedes és=2(3), el primer jugador agafa 1 moneda i deixa al segon en situació perduda.
A partir d'aquí, el jugador que està perdut només pot agafar una o dues monedes. Si n'agafa una, l'altre n'agafa 2. I si n'agafa 2, l'altre 1. 3 monedes menys, continua tenint un nombre =1(3), i tornem a començar, fins que a l'altre jugador només li quedi 1 moneda (òbviament =1(3)), i l'haurà d'agafar, amb el que perdrà.
Exacte. Si et toca tirar, et trobes amb la situació n=1(3) i l'altre juga bé, has perdut. I si ets el primer jugador i et trobes n=2(3) o n=0(3), extraient una o dues monedes li passes a l'altre la situació n=1(3).
el que estava buscant, gracies
Publica un comentari a l'entrada