# Parking-space Nim and other Mathematical Puzzles **URL:** \ **Category:** The Game Room\ **Created:** [September 6, 2012, 11:02am UTC](https://boards.straightdope.com/t/parking-space-nim-and-other-mathematical-puzzles/633841 "2012-09-06T11:02:14Z")\ **Posts on this page:** 7\ **Page:** 1
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [September 6, 2012, 11:02am UTC](https://boards.straightdope.com/t/parking-space-nim-and-other-mathematical-puzzles/633841/1 "2012-09-06T11:02:14Z")
Those who enjoy math-type puzzles should know about [IBM’s monthly puzzle](http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/Challenges/September2012.html). 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.) ---
**Author:** ![twickster](https://avatars.discourse-cdn.com/v4/letter/t/ec9cab/32.png) [@twickster](https://boards.straightdope.com/u/twickster)\ **Post date:** [September 6, 2012, 2:13pm UTC](https://boards.straightdope.com/t/parking-space-nim-and-other-mathematical-puzzles/633841/2 "2012-09-06T14:13:44Z")
Moved MPSIMS --\> the Game Room. ---
**Author:** ![Enderw24](https://avatars.discourse-cdn.com/v4/letter/e/ba9def/32.png) [@Enderw24](https://boards.straightdope.com/u/Enderw24)\ **Post date:** [September 6, 2012, 4:56pm UTC](https://boards.straightdope.com/t/parking-space-nim-and-other-mathematical-puzzles/633841/3 "2012-09-06T16:56:30Z")
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? ---
**Author:** ![Inner\_Stickler](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/inner_stickler/32/318_2.png) [@Inner\_Stickler](https://boards.straightdope.com/u/Inner_Stickler)\ **Post date:** [September 6, 2012, 5:00pm UTC](https://boards.straightdope.com/t/parking-space-nim-and-other-mathematical-puzzles/633841/4 "2012-09-06T17:00:06Z")
Except, if I understand the puzzle correctly, you have half your car outside the parking area. ---
**Author:** ![Snarky\_Kong](https://avatars.discourse-cdn.com/v4/letter/s/a183cd/32.png) [@Snarky\_Kong](https://boards.straightdope.com/u/Snarky_Kong)\ **Post date:** [September 7, 2012, 12:36pm UTC](https://boards.straightdope.com/t/parking-space-nim-and-other-mathematical-puzzles/633841/5 "2012-09-07T12:36:54Z")
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. ---
**Author:** ![Quercus](https://avatars.discourse-cdn.com/v4/letter/q/7ab992/32.png) [@Quercus](https://boards.straightdope.com/u/Quercus)\ **Post date:** [September 7, 2012, 2:39pm UTC](https://boards.straightdope.com/t/parking-space-nim-and-other-mathematical-puzzles/633841/6 "2012-09-07T14:39:57Z")
> [@Inner\_Stickler](#): > > Except, if I understand the puzzle correctly, you have half your car outside the parking area. OK, then N=0000 0010 Binary. (Hey, it’s \*IBM’\*s puzzle.) ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [September 9, 2012, 7:37am UTC](https://boards.straightdope.com/t/parking-space-nim-and-other-mathematical-puzzles/633841/7 "2012-09-09T07:37:36Z")
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](http://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem) 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.