0votos

Veintiuno en Other

por josejuan hace 6 años

Este problema no tiene mucho (o nada) que ver con la programación, es la (probablemente) más famosa versión de los juegos Nim y fácil de resolver para cualquiera que haya estudiado congruencias (y no demasiado difícil para cualquiera que haya estudiado el resto de la división).

Describe si es posible ganar el juego sin importar como juegue tu oponente

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
Tenemos una bolsa con N elementos y dos jugadores A y B. 
 
El juego consiste en que A extrae un nº de elementos comprendido entre 1 y k. 
 
Después B extrae un nº de elementos comprendido entre 1 y k. 
 
Las extracciones se alternan A, B, A, B, ... hasta que no quedan elementos en la bolsa. 
 
Pierde aquel que se ve obligado a dejar vacía la bolsa. 
 
------------------------- 
 
Por intentar hacer algo diferente, resolveré el desafío sin el conocimiento de la aritmética modular (a la vieja escuela): 
 
1 - Es obvio que si ni A ni B son tontos, si en la bolsa quedan k o menos elementos INTENTARÁN NO TOMAR TODOS LOS ELEMENTOS (porque perderían). 
 
2 - por [1], perderá quien en su último turno, únicamente tenga la opción de extraer un único elemento. 
 
3. llamemos M al número de bolas que quedan en cada momento. Entonces, 
 por [2], las decisiones ganadoras podrían describirse así: 
 
   3.1. si M = 1, ¡estoy perdido, no puedo dejar ningún elemento tras mi extracción! 
 
   3.2. si 1 < M <= k + 1, tomaré M - 1 elementos y habré ganado, porque sólo le 
          quedará un elemento a mi oponente (es decir [3.1]). 
 
   3.3. si M = k + 2, ¡estoy perdido!, pues quite los elementos que quite, siempre 
          será un valor que está en [3.2]. 
 
   3.4. si k + 2 < M <= 2k + 1, tomaré M - k - 2, porqué así mi oponente se quedará 
          en la posición [3.3] y perderá. 
 
   3.5. si M = 2k + 2, ¡estoy perdido!, pues quite los elementos que quite, siempre 
          será un valor que está en [3.4] 
 
   3.6. si 2k + 2 < M <= 3k + 1 ¡ganaré! 
   3.7. si M = 3k + 2 ¡perderé! 
   3.8. si 3k + 2 < M <= 4k + 1 ¡ganaré! 
   3.9. si M = 4k + 2 ¡perderé! 
   etc... 
 
4. por [3], queda claro que, salvo la situación [3.2], debo intentar que tras mi extracción, 
    en la bolsa quede un número de elementos tal que, restando 2, sea múltiplo de k. 
 
5. por [4], si ambos jugadores no son tontos, ganará A cuando M <> q k + 2 y perderá 
    cuando M = q k + 2 (decir que M = q k + 2 es lo mismo que decir que "M menos dos 
    es múltiplo de k"). 
 
Así, sea cual sea el lenguaje de programación, la función sería más o menos así: 
 
   Si (M - 2) MOD k == 0 
      Entonces Pierde el primero. 
      Sino        Gana el primero. 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.