From a pile of 104 tokens two players pick up some tokens, alternating turns and obeying three rules:
1. First player is allowed to take any amount of tokens, but not all of them.
2. Next quantities are limited , allowing the player to take only
a divisor of the quantity taken by his partner in the preceding move.
3. The player taking the last token wins.
Devise a winning strategy.
DECLARE FUNCTION try% (sz%, p%)
CLEAR , , 25000
DEFINT A-Z
DIM SHARED win(104, 104), pile
CLS
pile = 104
FOR n = 1 TO 101
win(104, n) = try(104, n)
IF win(104, n) = 1 THEN
PRINT n
END IF
NEXT n
PRINT
OPEN "binenigm.txt" FOR OUTPUT AS #2
FOR pl = 1 TO 104
PRINT #2, USING "### "; pl;
FOR tr = 1 TO pl
IF win(pl, tr) = 1 THEN
PRINT #2, "+";
ELSEIF win(pl, tr) = -1 THEN
PRINT #2, "-";
ELSE
IF tr MOD 10 = 0 THEN
PRINT #2, LEFT$(RIGHT$(STR$(tr), 2), 1);
ELSE
PRINT #2, " ";
END IF
END IF
NEXT
PRINT #2,
NEXT
CLOSE 2
END
FUNCTION try (sz, p)
pile = pile - p
IF p = sz THEN
t = 1
ELSE
t = 1
FOR n = 1 TO pile
IF p MOD n = 0 THEN
IF win(pile, n) = 1 THEN
t = -1
ELSEIF win(pile, n) = 0 THEN
IF try((pile), n) = 1 THEN t = -1
END IF
END IF
NEXT
END IF
pile = pile + p
try = t
win(sz, p) = t
END FUNCTION
shows the following possible opening moves that begin a winning strategy:
8
24
40
56
72
88
Each leaves a multiple of 16 in the pile.
The program also produces the following table. The left-hand side shows, for each row, the number of items that may be present in the pile when you are deciding the number of tokens to remove. The remainder of the row shows, for each choice that comes up rationally within the game, whether your taking a given number of tokens represents a winning (+) or losing (-) move. If a given column in that row is blank, then the choice never comes up during the rationally-played game. As an aid in identifying the columns, every column that's a multiple of 10 in which there is no + or - is marked with the 10's digit of the column number. At a given point in the game, some moves marked winning (+), may be outside the current bounds of the allowed choices, but in such circumstances, a lower amount also marked + will also be available.
It turns out that an optimal strategy is to leave a multiple of 16 for the other player. This will always be possible when your previous moves have been played correctly and the opponent has played his maximum move (your last move). Sometimes, however a move by the opponent will lower the power of 2 whose multiples are sought.
1 +
2 -+
3 +
4 -- +
5 + +
6 -+
7 +
8 ---- - +
9 + +
10 -+ 1
11 + + 1
12 -- + 1
13 + + 1 +
14 -+- -+ -+
15 + 1
16 -- - - 1-
17 + + 1
18 -+ 1
19 + + 1 +
20 ---+ -- 1 + - 2
21 + 1 2
22 -+ 1 2
23 + + +1 2
24 -- -- + - - -
25 + 1 2
26 -+- + 1 - 2 +
27 + + 1+ 2
28 -- + 1 -2
29 + + + 1 + 2 +
30 -+ 1 2 3
31 + 1 2 3
32 ---- - --1 - - 2 - 3
33 + 1 2 3
34 -+ - - + + 2 3
35 + + 1 2 + 3
36 -- + 1 - 2 3 -
37 + 1 2 3
38 -+- + 1- 2 + 3 -
39 + + 1 + 2 3
40 -- - + 1 - 2 3 - 4
41 + + + +1 2+ 3 4
42 -+ 1 2 3- 4
43 + 1 2 3 4
44 ---+-- - + - + - 4
45 + 1 2 3 4
46 -+ 1 2 -3 4
47 + + 1 +2 3 4
48 -- - -- 1 - 2 - 3 4
49 + + 1+ 2 3 4
50 -+- + -1 + 2 - 3 4 5
51 + 1 2 3 4 5
52 -- + 1 - 2 - 3 4 5 +
53 + + 1 + 2 3 4 5+
54 -+ - + 2 - 3 4 +
55 + + 1 2 3 4 +5
56 ---- - + 1 - - 2 + 3 4 - 5
57 + 1 2 3 4 + 5
58 -+ 1 2 - 3 4 + 5
59 + + + +1 + 2 3 4 + 5
60 -- + 1- 2 - 3 4 + 5 6
61 + 1 2 3 4 + 5 6
62 -+- +- 1 + 2- 3 4 + 5 6
63 + 1 2 3 4+ 5 6
64 -- -- - - - 3 - 5 6
65 + + 1 + 2 3 +4 5 6
66 -+ 1 -2 3 + 4 5 6
67 + 1 2 3 + 4 5 6
68 ---+ - -1 + - 2 3 + 4 5 6
69 + + + 1 2 3 + 4 5 6
70 -+ 1 - 2 3 + 4 5 6 7
71 + + 1+ 2 3 + 4 5 6 7
72 -- - + 1 - 2 3 - 4 5 6 7
73 + 1 2 3+ 4 5 6 7
74 -+- -+ + - 2 + 4 5 6 7
75 + 1 2 +3 4 5 6 7
76 -- + - 1 - 2 + 3 4 5 6 7
77 + + +1 2 + 3 4 5 6 7
78 -+ 1 - 2 + 3 4 5 6 7
79 + + 1 2 + 3 4 5 6 7
80 ---- - - 1 - 2 - 3 4 5 6 7 8
81 + 1 2 + 3 4 5 6 7 8
82 -+ 1- 2 + 3 4 5 6 7 8
83 + + + 1 2+ 3 4 5 6 7 8
84 -- +- - + 3 4 5 6 7 8
85 + 1 +2 3 4 5 6 7 8
86 -+- + -1 + 2 3 4 5 6 7 8
87 + 1 + 2 3 4 5 6 7 8
88 -- - + 1 - 2 3 4 5 6 7 8
89 + + + 1 + 2 3 4 5 6 7 8
90 -+ - 1 + 2 3 4 5 6 7 8 9
91 + 1 + 2 3 4 5 6 7 8 9
92 ---+ - 1 + 2 3 4 5 6 7 8 9
93 + 1+ 2 3 4 5 6 7 8 9
94 -+ - + 2 3 4 5 6 7 8 9
95 + + +1 2 3 4 5 6 7 8 9
96 -- - - 1 2 3 4 5 6 7 8 9
97 + + 1 2 3 4 5 6 7 8 9
98 -+- + 1 2 3 4 5 6 7 8 9
99 + + 1 2 3 4 5 6 7 8 9
100 -- + 1 2 3 4 5 6 7 8 9 0
101 + + 1 2 3 4 5 6 7 8 9 0
102 -+ 1 2 3 4 5 6 7 8 9 0
103 + 1 2 3 4 5 6 7 8 9 0
104 -------+---------------+---------------+---------------+---------------+---------------+-------------
Note that deviations from the always-leave-a-multiple-of-16 rule are possible, but of course are harder to keep track of. For example, If you've taken away 8, leaving 96, and your opponent has chosen to take away 4, leaving 92, you can't take away the 12 that would be required to bring the pile down to the next lower multiple of 16, so you have to take away 4, leaving the opponent with 88, which is indeed a multiple of 4. From then on, it's always leaving a multiple of 4, until the opponent has reduced the required multiples to 2. That's as low as it can go, when the opponent has brought the take-aways down to 1.
|
|
Posted by Charlie
on 2011-01-21 18:10:52 |
computer solution
