Parking-space Nim and other Mathematical Puzzles

The Game Room
1

Those who enjoy math-type puzzles should know about IBM’s monthly puzzle. The archives will lead you a great set of puzzles, including some that yielded novel results, e.g. in theory of markets.

I mentioned the June puzzle in an earlier thread; it was ordinary Nim, thinly-disguised. This month’s puzzle is an interesting, more difficult variant of Nim.

The puzzles are always challenging, but require no more math knowledge than a good programmer should have. (Though programming skill is usually not good enough, by itself, for solution.)

2

Moved MPSIMS --> the Game Room.

3

Find another possible size of the parking space, N, for which the first player has a winning strategy and N consists only of the digits 0 and 1.
Got it.

N=1.

I park first. I win.

Are they all this simple?

4

Except, if I understand the puzzle correctly, you have half your car outside the parking area.

5

Seems like a task for dynamic programming. I’m a pretty lazy/uninformed hobby programmer, but perhaps I’ll give this a shot over the weekend.

6

OK, then N=0000 0010 Binary. (Hey, it’s *IBM’*s puzzle.)

7

I started the thread because Nim was discussed recently, but am afraid Mundane Pointless was the correct forum after all. But since I did start it, I’ll follow up a little. The connection between Parking-space Nim and ordinary Nim sees interesting to me. I’ll try to explain, but probably not do as well as pages like Sprague–Grundy theorem - Wikipedia

Either game can be modeled as a set of subgames; a move in the game consists of a move in exactly one of the subgames. For example, in the position (3,5,9) in ordinary Nim, the only winning move is (3,5,9) -> (3,5,6); that is, (9)->(6) in a subgame. (3,5,6) is (011,101,110) in binary. 011 .xor. 101 .xor. 110 = 0; that’s why it’s a winning position.

The set of legal moves in subgame (9) is {0,1,2,3,4,5,6,7,8} and so on. 9 is called the nim-value of that subgame.

Parking-space Nim is the same as ordinary Nim, as long as you represent subgames with their nim-value.

You can’t move in (0) or (1), so both have nim-value 0. From (2) or (3) you can move only to nim-value 0, so they have nim-value 1. From (4) you can move to (2) with nim-value 1, or to (1,1) with nim-value 0, so (4) has nim-value 2. (5) has nim-value 0. From (6) you can move to (4) with nim-value 2, (3,1) with nim-value 1, or (2,2) with nim-value 0; therefore (6), which can take you to nim-values {0,1,2}, has nim-value 3.

But don’t despair! Unlike ordinary Nim, where a pile of size 900 has nim-value 900, unless I’m mistaken the nim-values in Parking-space Nim have a smallish upper bound.

I’ll write no more. IBM’s monthly puzzle is run as a sort of contest, so it may be best not to post a complete solution until October.