[superprismatic]

In the game of Subtract-a-Square two

players take alternately from a pile

of counters, the only restriction

being that the number taken must be

a perfect square. The player wins

who succeeds in getting the last

counter. How many should a player

take if there are now 50 counters

in the pile?

[Guest]

non-zero perfect squares?

[superprismatic]

non-zero perfect squares?

Yes.

[Guest]

Taking 16 sets the player up to win.

[Guest]

By leaving 5 counters in the pile you will win (if your opponent chooses 1 then you choose 4 for the win, and vice versa). If you pick second then you can ensure you eventually leave 5 in the pile - have the total of your opponent's pick and yours add up to a multiple of 5. If he picks 16 then you pick 4 or 9. If he picks 4 then you pick 16 or 1. Eventually, you make sure you leave 5 counters in the pot and win. The trouble, though, is if you pick first (which is probably implied in the puzzle). For this, I don't know yet which is best to pick.

[pdqkemp]

If you go first, you can always win if you take away 16 first.

That leaves 34.

If your opponent takes away 25, that leaves 9 - no good - you take 9.

If your opponent takes away 16, that leaves 18. You take away 16, leaving 1 for him, and then 1 for you.

If your opponent takes away 9, that leaves 25 - no good, you take 25.

If your opponent takes away 4, that leaves 30. You take away 25 leaving 5. If your opponent takes away 1, you get 4; if 4, you get 1.

If your opponent takes away 1, that leaves 33. you take away 25 leaving 8. If your opponent takes 4 from the 8, that leaves you 4 to win. If your opponent takes away 1 from the 8, you take 4, leaving 1 for him and then 1 for you.

[Guest]

36. 6x6=36, which leaves 14. The second player could take 8 or 4 leaving 6 or 10. If second takes 8, the first should take 1, which leaves 5. The second could then take 4 or one, but in either case the first gets the last, taking 1 or 4. If however, when there was 14 left and the second player took 4, leaving ten, the first should take .... ok, doesn't work. If he took 9 it would leave one, if he took 4 it would leave 6 and the second could employ the same strategy when the first was left with six. I'll have to think about it more. Unless you don't count 1 as a square in which case the first should take 49, but 1 is a square 1x1=1 so, I'm stuck for now.

[Guest]

Always end your turn with the opponent having one of these numbers of counters: 0, 2, 5, 7, 10, 12, 15, 17, 20, 22, 34, 39, 44. Ending with one of these choices for number of pieces guarantees you can also end in this list again after your opponent plays. Leaving them with zero obviously wins the game. The first move therefore is to take 16, to leave the enemy with 34 pieces. For any possible move the enemy makes at this point on, you can once again leave them with a number of pieces from the list and ultimately leave them with zero.

[Guest]

If you go first, you can always win if you take away 16 first.

That leaves 34.

If your opponent takes away 25, that leaves 9 - no good - you take 9.

If your opponent takes away 16, that leaves 18. You take away 16, leaving 1 for him, and then 1 for you.

If your opponent takes away 9, that leaves 25 - no good, you take 25.

If your opponent takes away 4, that leaves 30. You take away 25 leaving 5. If your opponent takes away 1, you get 4; if 4, you get 1.

If your opponent takes away 1, that leaves 33. you take away 25 leaving 8. If your opponent takes 4 from the 8, that leaves you 4 to win. If your opponent takes away 1 from the 8, you take 4, leaving 1 for him and then 1 for you.

I like it.

[Guest]

Taking 16 sets the player up to win.

The answer to the question is take 16 to reach target 34

Some analysis:

I'm trying to figure a generalization of the following, I just can't quite see the pattern yet...

In general: Player A must Avoid any number that can give player B a target.

Working out Player A's Target numbers from 1-50: 2,5,7,10,12,15,17,20,22,32,34,39,44

In the following: The player that is currently taking must avoid/target leaving the number specified. E.G. Player A (taking) must avoid leaving 1,3.

A player must avoid a number if it leaves the other player any target.

Player A must avoid leaving perfect squares.

1,4,9,16,25,36...

Player A must avoid leaving any number that is one more than a target number. These numbers are:

3,6,8,11,13,18,21,23,33,35,40,45

I just can't see it....yet....

Avoid leaving 1: Allows player B to take 1 for the 1.

Target leaving 2: Forces player B to take 1 leaving target 1

Avoid leaving 3: Allows player B to take 1 leaving target 2

Avoid leaving 4: Allows player B to take 4 for the win.

Target leaving 5: Forces Player B to take 1/4 leaving 4/1.

Avoid leaving 6: Allows player B to take 1/4 leaving targets 5/2

Target leaving 7: Forces player B to take 1/4 leaving 3/6.

Avoid leaving 8: Allows player B to take 1/4 leaving targets 7/4

Avoid leaving 9: Allows player B to take 9 for the win

Target leaving 10: Forces player B to take 1/4/9 leaving 8/6/1

Avoid leaving 11: Allows player B to take 1/4/9 for targets 10/7/2.

Target leaving 12: Forces player B to take 1/4/9 leaving 11/8/3

Avoid leaving 13: Allows player B to take 1 leaving target 12

Avoid leaving 14: Allows player B to take 4/9 leaving targets

Target leaving 15: Forces player B to take 1/4/9 leaving 14/11/6

Avoid leaving 16: Allows player B to take 16 for the win

Target leaving 17: Forces player B to take 1/4/9/16 leaving 16/13/8/1

Avoid leaving 18: Allows player B to take 1 to leave 17

Avoid leaving 19: Allows player B to take 4/9 leaving targets 15/10

Target leaving 20: Forces player B to take 1/4/9/16 leaving 19/16/11/4

Avoid leaving 21: Gives player B option to target 20

Target leaving 22: Forces player B to take 1/4/9/16 leaving 21/18/13/6

Avoid leaving 23: Allows player B to take 1 for target 22.

Avoid leaving 24: Allows player B to take 4 for target 20

Avoid leaving 25: Allows player B to take 25 for the win.

Avoid leaving 26: Allows player B to take 9 for target 17

Avoid leaving 27: Allows player B to take 25 for target 2.

Avoid leaving 28: Player B takes 16 to target 12

Avoid leaving 29: Player B takes 9 to target 20.

Avoid leaving 30: Player B takes 25 to target 5.

Avoid leaving 31: Player B takes 9 to target 22.

Target leaving 32: player B takes 1/4/9/16/25 to leave 31/28/23/16/7

Avoid leaving 33: player B takes 1 to target 32

Target leaving 34: Player B takes 1/4/9/16/25 to leave 33/30/25/18/9

Avoid leaving 35: Player B takes 1 to hit target 34

Avoid leaving 36: Player B takes 36 for win

Avoid leaving 37: Player B takes 25 to target 12

Avoid leaving 38: Player B takes 16 to target 22

Target leaving 39: Player B takes 1/4/9/16/25/36 leaving 38/35/30/23/14/3

Avoid leaving 40: Player B takes 1 leaving 39

Avoid leaving 41: Player B takes 9/36 leaving 32/5

Avoid leaving 42: Player B takes 25 leaving 17

Avoid leaving 43: Player B takes 4/9/36 leaving 39/34/7

Target leaving 44: Player B takes 1/4/9/16/25/36 leaving 43/40/35/28/19/8

Avoid leaving 45: Player B takes 1/25 leaving targets 44/20

Avoid leaving 46: Player B takes 36 leaving target 10

Avoid leaving 47: Player B takes 25 leaving target 22

Avoid leaving 48: Player B takes 4/9/16/36 leaving targets 44/39/32/12

Avoid leaving 49: Player B takes 49 for win

Avoid leaving 50: Player B takes 16 leaving target 34

[Guest]

If you go first, you can always win if you take away 16 first.

That leaves 34.

If your opponent takes away 25, that leaves 9 - no good - you take 9.

If your opponent takes away 16, that leaves 18. You take away 16, leaving 1 for him, and then 1 for you.

If your opponent takes away 9, that leaves 25 - no good, you take 25.

If your opponent takes away 4, that leaves 30. You take away 25 leaving 5. If your opponent takes away 1, you get 4; if 4, you get 1.

If your opponent takes away 1, that leaves 33. you take away 25 leaving 8. If your opponent takes 4 from the 8, that leaves you 4 to win. If your opponent takes away 1 from the 8, you take 4, leaving 1 for him and then 1 for you.

"If your opponent takes away 1, that leaves 33. you take away 25 leaving 8. If your opponent takes 4 from the 8, that leaves you 4 to win. If your opponent takes away 1 from the 8, you take 4, leaving 1 for him and then 1 for you."

8 - 1 = 7, 7 - 4 = 3, not 2. But I'm sure that a different winning solution is possible as I arrived at the same answer (see my post above).

[Guest]

If you go first, you can always win if you take away 16 first.

That leaves 34.

If your opponent takes away 25, that leaves 9 - no good - you take 9.

If your opponent takes away 16, that leaves 18. You take away 16, leaving 1 for him, and then 1 for you.

If your opponent takes away 9, that leaves 25 - no good, you take 25.

If your opponent takes away 4, that leaves 30. You take away 25 leaving 5. If your opponent takes away 1, you get 4; if 4, you get 1.

If your opponent takes away 1, that leaves 33. you take away 25 leaving 8. If your opponent takes 4 from the 8, that leaves you 4 to win. If your opponent takes away 1 from the 8, you take 4, leaving 1 for him and then 1 for you.

In the last case:

If your opponent takes away 1, that leaves 33. you take away 25 leaving 8. If your opponent takes 4 from the 8, that leaves you 4 to win. If your opponent takes away 1 from the 8, you take 4, leaving 1 for him and then 1 for you.

You take 25, leaving 8

Opponent takes 1, leaving 7

(at this point your opponent has set himself up to win?)

case1:

You take 4 (as you said), leaving 3

Opponent takes 1, leaving 2

You take 1, leaving 1

Opponent takes 1, leaving 0.

case2:

You take 1, leaving 6

Opponent takes 4, leaving 2

You take 1, leaving 1

Opponent takes 1, leaving 0.

So unless there is another answer other than starting by taking 16, you can't win if you go first.

[Guest]

If you go first, you can always win if you take away 16 first.

That leaves 34.

If your opponent takes away 25, that leaves 9 - no good - you take 9.

If your opponent takes away 16, that leaves 18. You take away 16, leaving 1 for him, and then 1 for you.

If your opponent takes away 9, that leaves 25 - no good, you take 25.

If your opponent takes away 4, that leaves 30. You take away 25 leaving 5. If your opponent takes away 1, you get 4; if 4, you get 1.

If your opponent takes away 1, that leaves 33. you take away 25 leaving 8. If your opponent takes 4 from the 8, that leaves you 4 to win. If your opponent takes away 1 from the 8, you take 4, leaving 1 for him and then 1 for you.

There is an error in the last line here: "your opponent takes away 1 from the 8, you take 4, leaving 1 for him and then 1 for you." Taking 1 from 8 leaves 7, your only adding up to 6.

[Guest]

In the last case:

If your opponent takes away 1, that leaves 33. you take away 25 leaving 8. If your opponent takes 4 from the 8, that leaves you 4 to win. If your opponent takes away 1 from the 8, you take 4, leaving 1 for him and then 1 for you.

You take 25, leaving 8

Opponent takes 1, leaving 7

(at this point your opponent has set himself up to win?)

case1:

You take 4 (as you said), leaving 3

Opponent takes 1, leaving 2

You take 1, leaving 1

Opponent takes 1, leaving 0.

case2:

You take 1, leaving 6

Opponent takes 4, leaving 2

You take 1, leaving 1

Opponent takes 1, leaving 0.

So unless there is another answer other than starting by taking 16, you can't win if you go first.

16 still works, but if at 34 your opponent takes 1, don't take 25, take 16 from 33. You can win from there.

[Guest]

If you go first, you can always win if you take away 16 first.

That leaves 34.

If your opponent takes away 25, that leaves 9 - no good - you take 9.

If your opponent takes away 16, that leaves 18. You take away 16, leaving 1 for him, and then 1 for you.

If your opponent takes away 9, that leaves 25 - no good, you take 25.

If your opponent takes away 4, that leaves 30. You take away 25 leaving 5. If your opponent takes away 1, you get 4; if 4, you get 1.

If your opponent takes away 1, that leaves 33. you take away 25 leaving 8. If your opponent takes 4 from the 8, that leaves you 4 to win. If your opponent takes away 1 from the 8, you take 4, leaving 1 for him and then 1 for you.

If your opponent takes 1 leaving 33, the ways to win are by taking 1 (leaving 32) or 16 (leaving 17). If you take 25 to leave 8, you set your opponent up for the win:

(8 left: opponent takes 1 leaving 7:

You take 4 leaving 3: opponent takes 1, you take 1, opponent takes 1 win.

You take 1 leaving 6: opponent takes 1 leaving 5, you take 4 leaving 1 or 1 leaving 4

[Guest]

ack...too late to edit but I erred on one of them...

32 is *NOT* a valid target.

Working out Player A's Target numbers from 1-50: 2,5,7,10,12,15,17,20,22,34,39,44

Player A must avoid leaving perfect squares.

1,4,9,16,25,36...

Player A must avoid leaving any number that is one more than a target number. These numbers are:

3,6,8,11,13,18,21,23,35,40,45

[Guest]

Correction to the last part

That leaves 34.

If your opponent takes away 25, that leaves 9 - no good - you take 9.

If your opponent takes away 16, that leaves 18. You take away 16, leaving 1 for him, and then 1 for you.

If your opponent takes away 9, that leaves 25 - no good, you take 25.

If your opponent takes away 4, that leaves 30. You take away 25 leaving 5. If your opponent takes away 1, you get 4; if 4, you get 1.

Correct up to this point..........................

If your opponent takes away 1, that leaves 33.

You take away 16, leaving your opponent with 17.

{

Opponent can take 16, leaving you to take 1.

}

OR

{

Opponent can take 9, leaving you with 8, you should then take 1, leaving the opponent with 7,

, at this point the opponent can take 4 or 1, leaving you with 3 or 6. If you are left with 3, take 1, your opponent will take 1, and you will take the last one.

If you are left with 6, take 4, leaving 2. Your opponent will take 1, and you will take the last one, winning again.

}

OR

{

Opponent can take 4, leaving you with 13, you should take 1, leaving the opponent at 12.

The opponent can take:

Opponent takes 9, leaving you at 4, you take 4 to win

opponent takes 4, leaving you at, leaving you at 8, win in the same way as mentioned above.

opponent takes 1, leaving you at 11, take 9 leaving 2, one for your opponent, and the last one for you.

}

OR

{

opponent can take 1, leaving you with 16, take 16 to win.

}

[Guest]

The strategy is much easier to remember by just noting that you should always end your turn by leaving the opponent with

either 0, 2, 5, 7, 10, 12, 15, 17, 20, 22, 34, 39, or 44 pieces.

As you see, by placing the opponent in position 34, after they move, we can always put them back into this list again.

Logically, all possibilities will lead to the opponent ending with 0.

How to get these numbers?

I wrote down a list with 50 entries.

0 is a losing position so I put 'L'.

1 is a winning position because you can put the enemy in losing position 0 with one legal move, so I write 'W'.

2 is a losing position, because all legal moves put the enemy in winning positions (in this case the only legal move is to take away 1, which results in 1 counter being left, a winning position.

Using these simple rules:

Losing position = Counter is zero OR all legal moves result in putting the enemy in a winning position.

Winning position = At least one legal move results in putting the enemy in a losing position.

You can go all the way up to 50 checking these conditions for each number to classify it as a winning or losing position.

If you do this you will find that the numbers: 0, 2, 5, 7, 10, 12, 15, 17, 20, 22, 34, 39, and 44

represent all the losing positions, (even though you can't get to 44 from 50).

This is the complete sequence:

http://www.research.att.com/~njas/sequences/index.html?q=0%2C+2%2C+5%2C+7%2C+10%2C+12%2C+15%2C+17%2C+20%2C+22%2C+34%2C+39%2C+44&language=english&go=Search

Edited August 19, 2009 by mmiguel1

[pdqkemp]

16 still works, but if at 34 your opponent takes 1, don't take 25, take 16 from 33. You can win from there.

Dang - and I was so proud I thought I got the answer first! Thanks for making it the most clear where I went wrong in my figures.