Author 
Topic: Infinite Checkerboard (Read 8370 times) 

Eric Yeh
Senior Riddler
Gender:
Posts: 318


Infinite Checkerboard
« on: Aug 2^{nd}, 2002, 2:40pm » 
Quote Modify

A tough one: You have a checkerboard which extends infinitely in all four directions. One halfplane is covered with checkers on all the black squares. You can jump pieces using normal checker jumps, but must remove the pieces that are jumped. How many rows into the uncovered halfplane can you get a checker? Repeat the problem where all squares are covered, and jumps are vertical and horizontal instead of diagonal as in standard checkers. Happy Puzzling, Eric

« Last Edit: Jan 8^{th}, 2003, 11:07am by william wu » 
IP Logged 
"It is better to have puzzled and failed than never to have puzzled at all."



Paul Hsieh
Guest


Re: NEW PROBLEM: Infinite Checkerboard
« Reply #1 on: Aug 5^{th}, 2002, 6:38pm » 
Quote Modify
Remove

Yes, this is a hard one. I think I can create a construction that sends one checker 4 levels past the border into the empty plane. I have only built part of the move sequence, and have a "plausibility" argument for the creation of the other part. Either way, its not a proof. Though I think I can prove that you can only move a finite number of levels into the empty plane. The orthogonal checkers is even harder  I am not even sure if you cannot move the checkers infinitely.


IP Logged 



Eric Yeh
Senior Riddler
Gender:
Posts: 318


Re: NEW PROBLEM: Infinite Checkerboard
« Reply #2 on: Aug 5^{th}, 2002, 8:16pm » 
Quote Modify

I'm not sure. I'd actually say the orthogonal case is in some sense easier...


IP Logged 
"It is better to have puzzled and failed than never to have puzzled at all."



kid
Guest


Re: NEW PROBLEM: Infinite Checkerboard
« Reply #3 on: Aug 9^{th}, 2002, 9:30pm » 
Quote Modify
Remove

I tried this question Long back. But after long efforts i can only conclude that maximum you can go is till the fourth row. Even if you have Infinte checkers you cant take it till the 5th row. I cant prove it myself but there is some proof from Prof. conway in some book.


IP Logged 



Eric Yeh
Senior Riddler
Gender:
Posts: 318


Re: NEW PROBLEM: Infinite Checkerboard
« Reply #4 on: Aug 10^{th}, 2002, 10:37am » 
Quote Modify

The proof (at least the one I came up with) is actually supremely elegant. I havent seen it written in a book, but I think this problem is one of those that are way too cool not to get yourself! So my highest recommendation to additional puzzlers is to continue thinking about it on your own... Best, Eric


IP Logged 
"It is better to have puzzled and failed than never to have puzzled at all."



D
Guest


Re: NEW PROBLEM: Infinite Checkerboard
« Reply #5 on: Aug 14^{th}, 2002, 11:01am » 
Quote Modify
Remove

Can someone better explain this? 4 infinite directions, so that's like a + shape yes? What are the 2 half planes? I'm sorry I don't understand...


IP Logged 



Eric Yeh
Senior Riddler
Gender:
Posts: 318


Re: NEW PROBLEM: Infinite Checkerboard
« Reply #6 on: Aug 14^{th}, 2002, 11:04am » 
Quote Modify

There are four directions to a plane  two for each axis. Imagine it as the set of points (x,y) where x, y are elements of Z. A half plane is (eg) the set of points with x <= 0. (The "other" half plane would then be the set of point where x > 0.) Best, Eric

« Last Edit: Aug 14^{th}, 2002, 11:05am by Eric Yeh » 
IP Logged 
"It is better to have puzzled and failed than never to have puzzled at all."



Chronos
Full Member
Gender:
Posts: 288


Re: NEW PROBLEM: Infinite Checkerboard
« Reply #7 on: Aug 17^{th}, 2002, 11:51am » 
Quote Modify

In the second case (orthogonal jumps, and red and black squares covered), I think I can get a checker indefinitely far up the y axis, but I'll need to go exponentially far out on the x axis to do it.


IP Logged 



Eric Yeh
Senior Riddler
Gender:
Posts: 318


Re: NEW PROBLEM: Infinite Checkerboard
« Reply #8 on: Aug 18^{th}, 2002, 8:56am » 
Quote Modify

Intriguing  I'd love to see the construction!

« Last Edit: Aug 18^{th}, 2002, 8:56am by Eric Yeh » 
IP Logged 
"It is better to have puzzled and failed than never to have puzzled at all."



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: NEW PROBLEM: Infinite Checkerboard
« Reply #9 on: Aug 27^{th}, 2002, 11:42am » 
Quote Modify

on Aug 9^{th}, 2002, 9:30pm, kid wrote:I tried this question Long back. But after long efforts i can only conclude that maximum you can go is till the fourth row. Even if you have Infinte checkers you cant take it till the 5th row. I cant prove it myself but there is some proof from Prof. conway in some book. 
 After a little experimentation, I was able to get a checker into the sixth row. My solution isn't generalizeable, howeverit's just a large, arbitrary collection of moves. So if there's a finite limit, it's at least six. For the horizontal/vertical problem, here's another way to think about it: just turn the checkerboard to a 45 degree angle. Now the pieces jump horizontally and vertically


IP Logged 
Doc, I'm addicted to advice! What should I do?



Eric Yeh
Senior Riddler
Gender:
Posts: 318


Re: NEW PROBLEM: Infinite Checkerboard
« Reply #10 on: Aug 27^{th}, 2002, 11:44am » 
Quote Modify

James, Are you suggesting the problems are equivalent?

« Last Edit: Aug 27^{th}, 2002, 11:47am by Eric Yeh » 
IP Logged 
"It is better to have puzzled and failed than never to have puzzled at all."



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: NEW PROBLEM: Infinite Checkerboard
« Reply #11 on: Aug 27^{th}, 2002, 1:51pm » 
Quote Modify

Eric, Well, not exactly. Transforming the diagonal problem into a horizontalvertical problem makes the cutoff between filled and unfilled squares at 45 degrees. I doubt that this fundamentally changes the nature of the problem however...


IP Logged 
Doc, I'm addicted to advice! What should I do?



Eric Yeh
Senior Riddler
Gender:
Posts: 318


Re: NEW PROBLEM: Infinite Checkerboard
« Reply #12 on: Aug 27^{th}, 2002, 2:37pm » 
Quote Modify

Exactly. (I briefly had the same thought when I first solved the first half of the problem, but then realized the difference.) Re: the fundamental nature of the problem, I won't spoil it by saying whether it does or doesn't. Best, Eric


IP Logged 
"It is better to have puzzled and failed than never to have puzzled at all."



Chronos
Full Member
Gender:
Posts: 288


Re: NEW PROBLEM: Infinite Checkerboard
« Reply #13 on: Aug 27^{th}, 2002, 4:04pm » 
Quote Modify

Quote:Intriguing  I'd love to see the construction! 
 I don't have a full construction yet, which is why I only said that I think I can do it. The basic idea is this: Assume that I can, somewhere on the board, bring a checker to a height j, and that I can also bring a checker to a height j1. If I can bring the checker at j1 over so it's directly underneath the checker at j, then it can jump over and get to j+1, and I can proceed by induction to get a checker all the way up. The key here is moving checkers horizontally. I can, for instance, move a checker arbitrarily far in the x direction if it's at y=1: I jump a checker up 1 space away from it, then one 3 spaces from it, then one 5 spaces from it, etc., providing a clear path which I can jump down. The problem comes when I try to do this far off the x axis: I might not be able to get "stepping stones" to that height that densly packed. Intuitively, it seems to me that I should be able to get around this by going far enough out on the x axis for my source of each checker, but I haven't proven that. I presume that you know proven answers for both versions of the problem? Without necessarily saying whether the solutions are related, of course.


IP Logged 



Eric Yeh
Senior Riddler
Gender:
Posts: 318


Re: NEW PROBLEM: Infinite Checkerboard
« Reply #14 on: Aug 27^{th}, 2002, 4:07pm » 
Quote Modify

Yep.


IP Logged 
"It is better to have puzzled and failed than never to have puzzled at all."



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: NEW PROBLEM: Infinite Checkerboard
« Reply #15 on: Aug 28^{th}, 2002, 1:01pm » 
Quote Modify

It should be pretty easy to prove that you can't go infinitely far away into the unoccupied zone. The reason for this is based in the way checkers works. If you want to jump a checker to line n, you need a checker on line n1 and a checker on line n2 (okay, you could also use lines n+1 and n+2, but that isn't relevant to this problem). To get the checker to line n1, you need a checker on line n2 and another on line n3. As you keep working backwards, you'll see that this is similar to the fibonacci sequence. How exactly the two are related is a mystery to me, but similar to the fibonacci sequence, the number of checkers required grows exponentially. (fib(n) ~= phi^n, where phi is 1.618...). You might say: big deal, we have an infinite number of checkers on all lines! We can go infinitely far! But this line consideration is not the only constraint. Let's consider a different problem, from the horizontalvertical jumping standpoint. Fill the entire board with checkers, then remove some in a diamond in the middle (remove all checkers (x,y) so that abs(x+y)<=R). Now, how large a diamond can you remove so that you can still jump a checker into the (0,0) position? Let's apply the same logic as we applied before: consider the series of thin diamonds around (0,0). The first diamond is the four squares (0,1), (0,1), (1,0), (1,0), the next diamond is the eight squares immediately outside of those, etc. To jump into the (0,0) position, we need a checker in diamond 1 and a checker in diamond 2. However, every finitenumbered diamond has a finite number of checkers in it! As a function of the diamond number, the number of checkers in the diamond increases linearly (diamond 1 has 4 checkers, diamond 2 has 8 checkers, etc.) But our fibonacciesque sequence grows exponentially! So we can see that the missingdiamond problem has a finite solution. But the missing diamond problem is EASIER than either halfplane problem, because it has more checkers. Therefore, there must also be a finite maximum for both halfplane problems. We should also be able to come up with an upper limit to the distance using these arguments. I don't know how big that limit is however.


IP Logged 
Doc, I'm addicted to advice! What should I do?



Eric Yeh
Senior Riddler
Gender:
Posts: 318


Re: NEW PROBLEM: Infinite Checkerboard
« Reply #16 on: Aug 28^{th}, 2002, 1:05pm » 
Quote Modify

Yep, that's a nice analysis James.


IP Logged 
"It is better to have puzzled and failed than never to have puzzled at all."



Eric Yeh
Senior Riddler
Gender:
Posts: 318


Re: NEW PROBLEM: Infinite Checkerboard
« Reply #17 on: Oct 12^{th}, 2002, 4:41pm » 
Quote Modify

Hm, nobody ever finished off this problem, despite James' strong advancements. Anyone want to take a crack at it now?


IP Logged 
"It is better to have puzzled and failed than never to have puzzled at all."



Barukh
Guest


Re: Infinite Checkerboard
« Reply #18 on: Aug 7^{th}, 2003, 10:47am » 
Quote Modify
Remove

Hint 1: Associate a certain real number with every square. Hint 2: Choose the numbers so that any legal move does not increase the sum of the covered squares. Answer: Diagonal version  6th row; orthogonal version  4th row


IP Logged 



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Infinite Checkerboard
« Reply #19 on: Aug 7^{th}, 2003, 1:22pm » 
Quote Modify

I think you might be off by a factor of 2 in your "diagonal" case. It's quite easy to reach your theoretical limit for the orthogonal case (and my calculations indicate your limit is correct).


IP Logged 
Doc, I'm addicted to advice! What should I do?



Eric Yeh
Senior Riddler
Gender:
Posts: 318


Re: Infinite Checkerboard
« Reply #20 on: Aug 7^{th}, 2003, 1:29pm » 
Quote Modify

hmm, i believe that that [diagonal] answer is the number i remember from when i worked this out years ago. (i know i know, how lazy am i; it would just take a coupla mins to recalc it but i still dont have the time!)

« Last Edit: Aug 7^{th}, 2003, 1:30pm by Eric Yeh » 
IP Logged 
"It is better to have puzzled and failed than never to have puzzled at all."



Barukh
Guest


Re: Infinite Checkerboard
« Reply #21 on: Aug 8^{th}, 2003, 4:21am » 
Quote Modify
Remove

on Aug 7^{th}, 2003, 1:22pm, James Fingas wrote:I think you might be off by a factor of 2 in your "diagonal" case). 
 I would like to see the evidence. on Aug 7^{th}, 2003, 1:29pm, Eric Yeh wrote:hmm, i believe that that [diagonal] answer is the number i remember from when i worked this out years ago. (i know i know, how lazy am i; it would just take a coupla mins to recalc it but i still dont have the time!) 
 The following is the solution for the diagonal case (based on JH Conway's approach). Pick a target square and assign a number 1 to it. Next, assign number phi^{N} (phi is the reciprocal of golden ratio) to a square which is N checkers' moves away from the target. This ensures that any legal move doesn't increase the sum of covered squares. Moreover, when the move is to be the shortest towards the target, the sum is unchanged. My calculations show that if the covered part starts N rows below the target square, the sum of the ocvered area is: S_{N} = (N+2)phi^{N2} + 3phi^{N1} S_{N} < 1 for all N > 6.


IP Logged 



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Infinite Checkerboard
« Reply #22 on: Aug 8^{th}, 2003, 6:39am » 
Quote Modify

Okay, you guys are right. My calculation was correct, but it wasn't the best upper bound. I just tried it out, and yes, you can reach the sixth row.

« Last Edit: Aug 8^{th}, 2003, 7:06am by James Fingas » 
IP Logged 
Doc, I'm addicted to advice! What should I do?



Eric Yeh
Senior Riddler
Gender:
Posts: 318


Re: Infinite Checkerboard
« Reply #23 on: Aug 8^{th}, 2003, 6:48am » 
Quote Modify

yeah, the cool thing about that one (if i recall correctly) was that it converged right to the limit!


IP Logged 
"It is better to have puzzled and failed than never to have puzzled at all."



Barukh
Guest


Re: Infinite Checkerboard
« Reply #24 on: Aug 8^{th}, 2003, 9:20am » 
Quote Modify
Remove

on Aug 8^{th}, 2003, 6:48am, Eric Yeh wrote:yeah, the cool thing about that one (if i recall correctly) was that it converged right to the limit! 
 The orthogonal case converges to the limit, but I don't think the diagonal case does...


IP Logged 



