12
$\begingroup$

After however much inordinate time passed for the tree-pruning game to finish, you ended up winning, and Satan was infuriated. He was sure he'd come up with a game keep you in hell.

But once again, he's let go on his promise. This time he's sure he's created a game to foil you once and for all, and to prove it, he's given you a contract signed in his own blood and witnessed by God himself to make sure he doesn't renege on his promise a third time.


He takes you down to an infinitely large checkerboard. You notice a red line drawn between two rows of the squares, extending infinitely in each direction.

"The rules of the game are simple", said Satan. "Every turn, we'll do the following:

  • You can either:

    1. Place one checker down on a square on your side of the board. But be warned, once you've placed a checker, you can never place another checker in that square again.

    2. Jump a checker over another adjacent checker horizontally, vertically, or diagonally, removing the checker you jumped over. You can't jump onto your own checkers, but if you manage to jump onto one of my checkers, I'll just remove it as well.

  • And then I'll:

    1. Place one checker on my side of the board.

If you can jump over any of my checkers, including jumping over one of mine onto another one of mine, then you win the game, and you have that contract witnessed by God that I'll let you go. And I'll be nice," he says with a cackle, "I'll place all my checkers within ten spaces of the line."

"Simple, right?" said Satan. "So... do you accept this game?"


Do you have a winning strategy for this game? Or has Satan finally matched your wits?

$\endgroup$
  • 3
    $\begingroup$ Why should I bother? Satan's word is worth zip. $\endgroup$ – Ben Frankel Apr 19 '15 at 21:53
  • $\begingroup$ But he has a contract signed by God... God can enforce that this time D: $\endgroup$ – Joe Z. Apr 19 '15 at 22:21
  • 1
    $\begingroup$ Even so, I've already spent omegas in hell and I've made a bunch of friends. $\endgroup$ – Ben Frankel Apr 19 '15 at 22:26
  • $\begingroup$ I win. I floodfill with checkers until the mass of my checkers attracts his within range. Thanks to a little physics theorem I will eventually have enough mass to overcome any amount of bonding. $\endgroup$ – Joshua Oct 14 '15 at 2:37
  • $\begingroup$ @Joshua: Good luck doing that in hell where certain laws of physics don't necessarily apply. $\endgroup$ – Joe Z. Oct 14 '15 at 5:17
8
$\begingroup$

The Devil wins.

The Devil places checkers anywhere 10 spaces above the line. We show that you can't reach that far up.

For an arbitrary checker of the Devil, assign each space a value that decays with distance to the target. Let the value be $\alpha^{d}$ where $d$ is the distance to that checker in chess-king moves and $\alpha$ is the inverse of the Golden Ratio, $\alpha = 1 / \phi$. Let your total value be the sum of the values of spaces your checkers occupy.

We'll show that jumps you make don't increase your value and that the total value of all checkers you can place is less than the value of a checker next to one of the devil's. Therefore, you can never get a checker in a position to jump the Devil's checker.

First, we show that any jump move doesn't increase your value. A jump creates a new checker at the landing square and removes two checkers, the one that jumped and the one that was jumped over. Let $d$ be the distance of the reached location. In the case of getting a checker closer to the Devil's, the change is

$$\alpha^{d} - \alpha^{d+1} - \alpha^{d+2} = \alpha^{d} \left( 1-\alpha -\alpha^2 \right) = 0$$

because $\alpha = 1 / \phi$ is a root of that quadratic.

For any other kind of jump, the subtracted values are larger, and so the change is negative. So, no jump can increase value.

Now, we show that the total value of checkers that Johnny can ever place is bounded. Since a space can only have a checker placed once, this bound is the total value of spaces on Johnny's side.

Recall that the Devil's checker is $10$ spaces above the line, so we want to get a checker $9$ spaces above in order to jump over it. Then, of spaces below the line, there's $19$ spaces at distance $9$ from it and thus value $\alpha^{9}$, $23$ spaces at a value of $\alpha^{10}$, $27$ at value $\alpha^{11}$, and so on.

Summing the series gives a total of $\approx 0.877$, which is a bit short of the target value of $1$ of a space next to the Devil's checker. So, Johnny can never get a checker into a position to jump that checker of the Devil, and so WLOG, any checker of the Devil placed on the tenth row.

$\endgroup$
  • $\begingroup$ There are 31 spaces at distance 12, not 29. $\endgroup$ – Mike Earnest Apr 20 '15 at 0:13
  • $\begingroup$ @MikeEarnest I'm still getting 29. Do you get different values for 10 and 11? Surely it goes up linearly. $\endgroup$ – xnor Apr 20 '15 at 0:21
  • $\begingroup$ Sorry, my mistake! I had double counted $\endgroup$ – Mike Earnest Apr 20 '15 at 0:26
  • $\begingroup$ Yep, this is correct. This is a variant on Conway's checker-jumping problem where diagonal jumps are allowed. $\endgroup$ – Joe Z. Apr 20 '15 at 1:39
  • $\begingroup$ You have one small error in your math - since you want to get the checker to the ninth row, you want to count the 19 spaces at a distance 9 from that square, 23 spaces at distance 10, 27 at distance 11, etc. $\endgroup$ – Joe Z. Apr 20 '15 at 17:57
0
$\begingroup$

First I place a single trash checker 1000 squares away from the red line. Then Satan places his checker, and from now on I'll ignore Satan's moves: if Satan places another checker nearby it can only help me as I can't place a checker on his side of the line anyways, and if I jump onto it I win earlier than intended. For the next $N = 10^{10^{100}}$ moves, I'll place a bunch of checkers under the target checker until "everything" is filled up. Now I have a much simpler game: half the plane is full and I must reach a specific distance 1-10 squares from the red line in however many moves I like.

If I want to hop to somewhere but in doing so I will land on a placed checker, I'll plan for this ahead of time and in my googolplex preparation moves I'll skip that spot (and now maybe I can place a checker there later on).

Now I can case check the distance of Satan's checker from the red line.

  1. Hop vertically.
  2. Do 1 then hop diagonally.
  3. Do 2 then in its column hop vertically twice.
  4. Do 3 then to its right do 2 then hop diagonally.
  5. Do 4 then do some simple hops to get a checker diagonally down/right two, then do 3 pretending that the red line is 3 lower than it is to get another checker diagonally down/right three, then hop diagonally twice.

This is all I'll do because I need to go to sleep. I've proved that if Satan places his first checker at a distance of 1-5 then I can win.. it may be that 10 is impossible.

$\endgroup$
  • $\begingroup$ Now, supposing you could only jump horizontally and vertically but Satan only placed his checkers on the 6th line, then even $10^{10^{100}}$ checkers wouldn't be enough. $\endgroup$ – Joe Z. Apr 20 '15 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.