Straight Dope Message Board > Main Parking-space Nim and other Mathematical Puzzles
 Register FAQ Calendar Mark Forums Read

#1
09-06-2012, 07:02 AM
 septimus Guest Join Date: Dec 2009
Parking-space Nim and other Mathematical Puzzles

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
09-06-2012, 10:13 AM
 twickster Illudium Q-36 Explosive Space Moderator Join Date: Aug 2002 Location: Philadelphia Posts: 37,371
Moved MPSIMS --> the Game Room.
#3
09-06-2012, 12:56 PM
 Enderw24 Charter Member Join Date: Sep 2000 Location: KC. MO -094 35.3 39 4.9 Posts: 10,110
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
09-06-2012, 01:00 PM
 Inner Stickler Guest Join Date: Jul 2005
Except, if I understand the puzzle correctly, you have half your car outside the parking area.
#5
09-07-2012, 08:36 AM
 Snarky_Kong Guest Join Date: Oct 2004
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
09-07-2012, 10:39 AM
 Quercus Guest Join Date: Dec 2000
Quote:
 Originally Posted by 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.)
#7
09-09-2012, 03:37 AM
 septimus Guest Join Date: Dec 2009
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 http://en.wikipedia.org/wiki/Sprague...Grundy_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.

 Bookmarks

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Main     About This Message Board     Comments on Cecil's Columns/Staff Reports     Straight Dope Chicago     General Questions     Great Debates     Elections     Cafe Society     The Game Room     In My Humble Opinion (IMHO)     Mundane Pointless Stuff I Must Share (MPSIMS)     Marketplace     The BBQ Pit Side Conversations     The Barn House

All times are GMT -5. The time now is 02:30 AM.