Author |
Topic: Infinite Checkerboard (Read 8671 times) |
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: Infinite Checkerboard
« Reply #25 on: Aug 8th, 2003, 10:09am » |
Quote Modify
|
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...
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Infinite Checkerboard
« Reply #26 on: Aug 8th, 2003, 12:32pm » |
Quote Modify
|
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
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: Infinite Checkerboard
« Reply #27 on: Aug 8th, 2003, 12:36pm » |
Quote Modify
|
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 ).
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Infinite Checkerboard
« Reply #28 on: Aug 8th, 2003, 1:33pm » |
Quote Modify
|
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!
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: Infinite Checkerboard
« Reply #29 on: Aug 8th, 2003, 1:53pm » |
Quote Modify
|
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
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Infinite Checkerboard
« Reply #30 on: Aug 11th, 2003, 10:55am » |
Quote Modify
|
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.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: Infinite Checkerboard
« Reply #31 on: Aug 12th, 2003, 1:03pm » |
Quote Modify
|
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?
|
« Last Edit: Aug 12th, 2003, 1:42pm by Eric Yeh » |
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: Infinite Checkerboard
« Reply #32 on: Aug 12th, 2003, 1:04pm » |
Quote Modify
|
agh whats up w yabb squeezing spaces. o well hopefully you see what i mean there.
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Infinite Checkerboard
« Reply #33 on: Aug 12th, 2003, 1:39pm » |
Quote Modify
|
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 ...
|
« Last Edit: Aug 12th, 2003, 1:45pm 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 #34 on: Aug 12th, 2003, 1:43pm » |
Quote Modify
|
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 i am disappointed in myself for my cheat, haha!
|
« Last Edit: Aug 12th, 2003, 1:47pm by Eric Yeh » |
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: Infinite Checkerboard
« Reply #35 on: Aug 12th, 2003, 1:46pm » |
Quote Modify
|
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
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
Bojan_Basic
Newbie
Posts: 4
|
|
Re: Infinite Checkerboard
« Reply #36 on: Jan 26th, 2008, 2:21am » |
Quote Modify
|
on Aug 8th, 2003, 1:33pm, 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 is exactly what you were looking for. I hope you'll like it.
|
|
IP Logged |
|
|
|
|