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.

Relatively prime graph solution

See the original problem

This is the solution I found:
N=105
M=6201

I tried searching for solutions for which N and M are odd.  That way I automatically get that 2 is a common factor of N+1, N-1, M+1, and M-1.

N needs to have a factor in common with M, M+1, and M-1.  Therefore, N needs at least 3 distinct prime factors.  N is odd, so the smallest N fitting this criteria is 3*5*7=105.

104 has prime factors 2 and 13.  106 has prime factors 2 and 53.  Therefore, M needs to have factors 13 and 53.  That is, M needs to be a multiple of 689.  The rest of my search consisted of trying different odd multiples of 689 until one worked.

There are many other methods to find a solution (and many other solutions), but that's mine.