Winning Position

Winning Position

Some puzzles can be categorized as ones seeking the winning strategy if any, in a game. A fair game is one in which each player has the same chance to win. Most games, though they appear to be fair are not so. They offer a better chance to a player who applies a particular strategy. Since both the player could be equally smart, the first player gets the first chance to apply the strategy and stands to win the game. Identification of the winning position needs analysis of what could be done to ensure a win for the first player irrespective of what the other player does. An example will clarify this better.

There is a heap of 40 beads. Any player can remove less than half of the beads from the heap. He has to remove at least 1. The player who cannot remove anything loses.

See what A does to reach a winning position.

1.      A remove 9. 31 remains.

2.      B removes some beads (between 1 and 15). The remaining will be between 16 and 30.

3.    A remove as many beads as required to leave 15 in the heap (between 1 to 15)

4.      B removes at the most 7 and leaves a minimum of 8 in the heap.

5.      A remove as many beads as required to leave 7 in the heap

6.      B removes at the most 3 beads and leaves a minimum of 4 in the heap.

7.      A remove as many beads as required to leave 3 in the heap

8.      B removes 1 bead leaving 2 in the heap.

9.      A remove 1 leaving 1 in the heap.

10.   B cannot remove, and loses the game.

Thus, we see that the first player has a command over the result of the game. Whatever be the number original in the heap he has to remove as many beads as needed to keep the remaining number 1 less than the highest power of 2 possible. (2ⁿ -1; in our case 31). If he maintains this strategy, he is sure to reach 1.

Winning Position Puzzle 2.

First, there is the number 2. Now A and B take turns in incrementing it by a number less than its current value of it. He has to add at least 1.  E.g., A can add 1 only, whereby it becomes 3. Now B can add 1 or 2 to make it 4 or 5. Now A can add 1 to 3 or 1 to 4 depending on what B has added. The person who makes the sum of 1000 wins.

Is this a fair game? If not, how can A ensure a Win?

Hint: Just before 1000, it should be 500 so that the next person cannot add 500 and finish but has to add at least 1 thereby making it possible for the other guy to make it 1000.

What way the game changes if the sum to be achieved is 600?

Winning Position Puzzle 3.

Another problem that attracts a winning strategy, is almost similar to the above.

Start with the number 400. A and B take turns in reducing it by any value not more than half of the current value, at least 1. E.g., A can reduce it by 1 or 200 leaving 399 or 200 (or a value in between). The person who cannot make a move loses.

If both adopt the strategy of reducing the maximum allowed, the situation changes as below.

Step	Move by	A	B	Remaining	Remarks
0	Initial			400
1	A	200		200
2	B		100	100
3	A	50		50
4	B		25	25
5	A	12		13
6	B		6	7
7	A	3		4
8	B		2	2
9	A	1		1
10					B cannot move; loses

 

There is a catch in the above sequence. If B changes his strategy on the 8^th step and reduces only by 1, the end result changes as follows.

Step	Move by	A	B	Remaining	Remarks
0	Initial			400
1	A	200		200
2	B		100	100
3	A	50		50
4	B		25	25
5	A	12		13
6	B		6	7
7	A	3		4
8	B		1	3
9	A	1		2
10	B		1	1	A cannot move; loses

 

A winning strategy is the one in which one of the persons (A or B) can force the whole situation to change in his favor.

 

 

 

 

 

Solution:

The key to success for anyone is to leave a number 2ⁿ-1 as remaining after the reduction. If A takes this step in the first move, he can defeat B as below. Since the highest such number below 400 is 255, A should remove 145 leaving 255 (2⁸ – 1).

Step	Move by	A	B	Remaining	Remarks
0	Initial			400
1	A	145		255
2	B		1…127	254…128	B can remove only 1 to 127
3	A	127…1		127	A remove 127…1 to leave 127
4	B		1…63	126…64
5	A	63…1		63
6	B		1…31	62…32
7	A	31…1		31
8	B		1…15	30…16
9	A	15…1		15
10	B		1…7	14…8
11	A	7…1		7
12	B		1…3	6…4
13	A	3…1		3
14	B		1	2
15	A	1		1	B cannot move; loses