wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Infinite Checkerboard
        
(Message started by: Eric Yeh on Aug 2^nd, 2002, 2:40pm)

Title: Infinite Checkerboard
Post by Eric Yeh on Aug 2^nd, 2002, 2:40pm

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

Title: Re: NEW PROBLEM: Infinite Checkerboard
Post by Paul Hsieh on Aug 5^th, 2002, 6:38pm

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.

Title: Re: NEW PROBLEM: Infinite Checkerboard
Post by Eric Yeh on Aug 5^th, 2002, 8:16pm

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

Title: Re: NEW PROBLEM: Infinite Checkerboard
Post by kid on Aug 9^th, 2002, 9:30pm

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.

Title: Re: NEW PROBLEM: Infinite Checkerboard
Post by Eric Yeh on Aug 10^th, 2002, 10:37am

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

Title: Re: NEW PROBLEM: Infinite Checkerboard
Post by D on Aug 14^th, 2002, 11:01am

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...

Title: Re: NEW PROBLEM: Infinite Checkerboard
Post by Eric Yeh on Aug 14^th, 2002, 11:04am

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

Title: Re: NEW PROBLEM: Infinite Checkerboard
Post by Chronos on Aug 17^th, 2002, 11:51am

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.

Title: Re: NEW PROBLEM: Infinite Checkerboard
Post by Eric Yeh on Aug 18^th, 2002, 8:56am

Intriguing -- I'd love to see the construction! :D

Title: Re: NEW PROBLEM: Infinite Checkerboard
Post by James Fingas on Aug 27^th, 2002, 11:42am

on 08/09/02 at 21:30:53, kid wrote:

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 ;)

Title: Re: NEW PROBLEM: Infinite Checkerboard
Post by Eric Yeh on Aug 27^th, 2002, 11:44am

James,

Are you suggesting the problems are equivalent?

Title: Re: NEW PROBLEM: Infinite Checkerboard
Post by James Fingas on Aug 27^th, 2002, 1:51pm

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...

Title: Re: NEW PROBLEM: Infinite Checkerboard
Post by Eric Yeh on Aug 27^th, 2002, 2:37pm

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

Title: Re: NEW PROBLEM: Infinite Checkerboard
Post by Chronos on Aug 27^th, 2002, 4:04pm

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.

Title: Re: NEW PROBLEM: Infinite Checkerboard
Post by Eric Yeh on Aug 27^th, 2002, 4:07pm

Yep.

Title: Re: NEW PROBLEM: Infinite Checkerboard
Post by James Fingas on Aug 28^th, 2002, 1:01pm

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.

Title: Re: NEW PROBLEM: Infinite Checkerboard
Post by Eric Yeh on Aug 28^th, 2002, 1:05pm

Yep, that's a nice analysis James.

Title: Re: NEW PROBLEM: Infinite Checkerboard
Post by Eric Yeh on Oct 12^th, 2002, 4:41pm

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

Title: Re: Infinite Checkerboard
Post by Barukh on Aug 7^th, 2003, 10:47am

Hint 1: [hide]Associate a certain real number with every square.[/hide]

Hint 2: [hide]Choose the numbers so that any legal move does not increase the sum of the covered squares.[/hide]

Answer: [hide]Diagonal version - 6th row; orthogonal version - 4th row[/hide]

Title: Re: Infinite Checkerboard
Post by James Fingas on Aug 7^th, 2003, 1:22pm

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).

Title: Re: Infinite Checkerboard
Post by Eric Yeh on Aug 7^th, 2003, 1:29pm

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!)

Title: Re: Infinite Checkerboard
Post by Barukh on Aug 8^th, 2003, 4:21am

on 08/07/03 at 13:22:34, 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 08/07/03 at 13:29:42, Eric Yeh wrote:

The following is the solution for the diagonal case (based on JH Conway's approach).

[hide]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^N-2 + 3phi^N-1

S_N < 1 for all N > 6.

[/hide]

Title: Re: Infinite Checkerboard
Post by James Fingas on Aug 8^th, 2003, 6:39am

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.

Title: Re: Infinite Checkerboard
Post by Eric Yeh on Aug 8^th, 2003, 6:48am

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

Title: Re: Infinite Checkerboard
Post by Barukh on Aug 8^th, 2003, 9:20am

on 08/08/03 at 06:48:12, 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...

Title: Re: Infinite Checkerboard
Post by Eric Yeh on Aug 8^th, 2003, 10:09am

o ok, i guess i got them mixed up; its been years. strange tho, i thought i remembered thinking the "normal" checkers version was cooler bc of the limit, but guess i may have mixed up my mnemonic...

Title: Re: Infinite Checkerboard
Post by James Fingas on Aug 8^th, 2003, 12:32pm

Actually, the limit it converges to is 5, but you can never reach it (even a perfect sequence of moves would be infinite). So it's kind of pretty, but ultimately useless :(

Title: Re: Infinite Checkerboard
Post by Eric Yeh on Aug 8^th, 2003, 12:36pm

well, not quite "useless" -- you need to see that every finite set is under 5 or else the answer would (potentially) change. so in my opinion it is pretty AND useful (and hence truly pretty by my defn of it ;) ).

Title: Re: Infinite Checkerboard
Post by James Fingas on Aug 8^th, 2003, 1:33pm

I guess I was misleading in what I said. What I should have said was: the series converges to 1 if you pick a position on the fifth row empty row as the starting point.

But can anybody come up with a way of generating the infinite sequence of moves that would allow you to move to the fifth row? I suspect you'd end up with a finite number of moves, then a well-defined infinite sequence of moves, and then another finite sequence of moves. That would be quite a feat!

Title: Re: Infinite Checkerboard
Post by Eric Yeh on Aug 8^th, 2003, 1:53pm

yeah i thought about that at the time -- its actually impossible bc, since you need EVERY piece to get to the fifth row (thats where the beauty of the exact convergence comes in), and furthermore every piece has to go forward only, youre going to have infinitely many pieces that are too far away horizontally to "help the effort" "in time". anyway, that is a tiny bit hand wavy but very easy to formalize, so im sure you geniuses can handle it ;)

Title: Re: Infinite Checkerboard
Post by James Fingas on Aug 11^th, 2003, 10:55am

Okay, point taken. You couldn't actually solve it. But there are some constructions that can be made that are infinite in extent, but doable in practice (given infinite time or when taking the limit). For instance:

000000 ... 00000000 001111 ... 11111110 000000 ... 00000100 000000 ... 00000100 000000 ... 00000000

can be transformed to:

000000 ... 00000000 100000 ... 00000000 000000 ... 00000000 000000 ... 00000000 000000 ... 00000000

Now this is not particularly helpful for the task, since we can't push that interesting bit at the end off to infinity. But perhaps there is something else we can do.

Title: Re: Infinite Checkerboard
Post by Eric Yeh on Aug 12^th, 2003, 1:03pm

james,

ye sorry i was actually thinking about the diagonal case again. for that it is easy to show that for any finite set S of checkers with value = sum(board), S cannot be achieved.

ok, now on to your intended question, for the horizontal case, which i think is interesting. first, one has to come up w a good interpretation, which i think amounts to a set of allowable transfinite transformations.

first interpretation: allow any infinite string of 1's:

0 0 1 1 1... -> 1 0 0 0...

this is per your msg, and i think is the most "basic" one that needs to be allowed, and hence must be included in our set of allowable transformations.

i played with this forumalation for a bit and am pretty convinced that it is not solveable, but i also couldnt come up w a proof. think i might if given a bit more time but dont quite have it. instead i cheese out and add another allowable transformation on an infinite diagonal sequence of 1's:

0 0 0 0... 0 1 0 0 0 0 0 0
0 1 0 0 0 0 0 0 1 0 0 0
0 0 1 0 -> 0 0 0 0 or equivlently 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0
... ...

and the puzzle is then easily solveable.

comments?

Title: Re: Infinite Checkerboard
Post by Eric Yeh on Aug 12^th, 2003, 1:04pm

agh whats up w yabb squeezing spaces. o well hopefully you see what i mean there.

Title: Re: Infinite Checkerboard
Post by James Fingas on Aug 12^th, 2003, 1:39pm

Eric,

The regular posting script squeezes out spaces, but the modification posting script doesn't. So if you want to put the spaces back, try modifying your post. The preview should show the spaces back in, and once you save, they should stay.

I'll see if I can figure the problem out with the diagonal and orthogonal transfinite moves. I was actually thinking that the orthogonal one I suggest is not very fundamental. A better fundamental move would be this one:

1 0 0 0 0 0 0 => 0 1 0 1 0 1 0 1

But this can't replace the other move I suggested because it's not very useful. Although I like the fact that my original suggestion is just this superposition:

0 1 0 0 0 0 0 => 0 0 1 0 1 0 1
+ 0 0 1 0 0 0 0 => 0 0 0 1 0 1 0
= 0 1 1 0 0 0 0 => 0 0 1 1 1 1 1

But of course this isn't valid in checkers ...

Title: Re: Infinite Checkerboard
Post by Eric Yeh on Aug 12^th, 2003, 1:43pm

cool thanks, now its fixed. wow you are really expert here now ;)

i am sure you will get it very easily -- its almost trivial in that formulation :P i am disappointed in myself for my cheat, haha!

Title: Re: Infinite Checkerboard
Post by Eric Yeh on Aug 12^th, 2003, 1:46pm

ps FWIW, try using the diagonal transformation only finitely many times. maybe even minimize it (i think my soln is optimal).

pps if you define the "infinite case" to mean that for arbitrarily small epsilon you can systematically place less than epsilon worth of extra checkers on the board and still reach your goal, then you cover both of these transfinite transformations (and a hell of a lot more im sure). FWIW :P

Title: Re: Infinite Checkerboard
Post by Bojan_Basic on Jan 26^th, 2008, 2:21am

on 08/08/03 at 13:33:27, James Fingas wrote:

But can anybody come up with a way of generating the infinite sequence of moves that would allow you to move to the fifth row? I suspect you'd end up with a finite number of moves, then a well-defined infinite sequence of moves, and then another finite sequence of moves. That would be quite a feat!

Sorry for coming late, but this (http://www.chiark.greenend.org.uk/~sgtatham/solarmy/) is exactly what you were looking for. I hope you'll like it.