Author |
Topic: Infinite Checkerboard (Read 8654 times) |
|
Eric Yeh
Senior Riddler
Gender: 
Posts: 318
|
 |
Infinite Checkerboard
« on: Aug 2nd, 2002, 2:40pm » |
 Quote  Modify
|
A tough one:
You have a checkerboard which extends infinitely in all four directions. One half-plane 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 half-plane 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 8th, 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 5th, 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 5th, 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 9th, 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 10th, 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 14th, 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 14th, 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 14th, 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 17th, 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 18th, 2002, 8:56am » |
Quote Modify
|
Intriguing -- I'd love to see the construction! 
|
| « Last Edit: Aug 18th, 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 27th, 2002, 11:42am » |
Quote Modify
|
on Aug 9th, 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, however--it'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 27th, 2002, 11:44am » |
Quote Modify
|
James,
Are you suggesting the problems are equivalent?
|
| « Last Edit: Aug 27th, 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 27th, 2002, 1:51pm » |
Quote Modify
|
Eric,
Well, not exactly. Transforming the diagonal problem into a horizontal-vertical 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 27th, 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 27th, 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 j-1. If I can bring the checker at j-1 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 27th, 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 28th, 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 n-1 and a checker on line n-2 (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 n-1, you need a checker on line n-2 and another on line n-3.
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 horizontal-vertical 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 finite-numbered 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 fibonacci-esque sequence grows exponentially! So we can see that the missing-diamond problem has a finite solution. But the missing diamond problem is EASIER than either half-plane problem, because it has more checkers. Therefore, there must also be a finite maximum for both half-plane 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 28th, 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 12th, 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 7th, 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 7th, 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 7th, 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 7th, 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 8th, 2003, 4:21am » |
Quote Modify
Remove
|
on Aug 7th, 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 7th, 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 phiN (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:
SN = (N+2)phiN-2 + 3phiN-1
SN < 1 for all N > 6.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Infinite Checkerboard
« Reply #22 on: Aug 8th, 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 8th, 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 8th, 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 8th, 2003, 9:20am » |
Quote Modify
Remove
|
on Aug 8th, 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print