All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Games
A binary enigma (Posted on 2011-01-21) Difficulty: 3 of 5
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.

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer solution | Comment 3 of 5 |

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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information