Wednesday, February 29, 2012

The Car Parking game

Let's play a game.

(image borrowed from here)

I call this the car parking game.  There is a curb that can fit up to five cars on it.  We take turns parking new cars on the curb.  You may park your car anywhere on the curb where there is room.  That is, its position can be described by any number between 1 and 5 (inclusive), including fractions.  Cars take up some space, so the minimum distance between any two cars is 1.  So for example, it is not possible to park cars at 1 and 1.5.

If it is your turn and you have no space left to park a car, you have an excuse to double-park, and thus you win.  (I know this win-condition sounds backwards, but the game is more interesting this way).

So here's how we'll play.  Leave a comment, state which game you are playing, and state where you are parking your car.  I'll respond to your comment with my move.  You may try as many times as you want, so persistence can be a substitute for cleverness.

Game 1: The curb can fit up to 5 cars.

Game 2: The curb can fit up to 8 cars

Game 3: The curb can fit up to 17 cars (this one's for the programmers)

I posted some comments on strategy.


Secret Squïrrel said...

Game 1: 3
Game 2: 3

miller said...

I was worried no one would take me up!

Secret Squirrel's games:
Game 1: 1.5
Game 2: 5

Other commenters may also play at the same time.

Secret Squïrrel said...

Game 1: 4
Game 2: I concede. Congratulations!

miller said...

Secret Squirrel's games:
Game 1: 5. You win!

Unknown said...

The secret to winning this game is the same as it is with "Pearls before Swine" or "Misere Pyramid:" If the initial number of spaces is odd then go first. If the number is even, then go second because the player who moves first always loses.


Let our parking spots be denoted by numbers 1-5, 1-8, or 1-17

In the situation of 5 cars taking the space 3 leaves only two decisions for your opponent: Park in space 1.5 or 4.5, or park in an even space. In either situation, you will always make a move which leaves your opponent forced with another space to park in. If they park in a space and a half, you park in a full space (1, 2, 3, and 4 taken) and leave them with the final space. If they park in a single space, then you park in a space and a half to leave them with the final space (and thus successfully Misere them).

In the situation with 8 cars, your objective is to go second always.


We can treat a game of 8 spaces as game of four spaces. The reason behind this is that the player who goes second (to win 100% of the time) will mirror the first players play immediately adjacent to the first move. In a game of four spaces, the player to go first always looses. In this fashion, the game of 8 is identical.

For the game of 17, the theorem is much the same. Go first and take the middle, then copy your opponent.

Why? Because by going first in the game of 17, you essentially make it a game of 16 wherein you go second. A game of 16 is four games of 4, to which we already know the outcome.

Easy stuff.

miller said...

I agree with your solution to Game 1. First player wins. I don't agree with your solutions to the other games.

If you let me go first on game 2, that's fine with me.

Game 2: 2.5

I take it your first move in Game 3 is 9.

Game 3: 2.5