Author |
Topic: 3D Chessboard Full Control (Read 14628 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
3D Chessboard Full Control
« on: Sep 25th, 2003, 12:25pm » |
 Quote  Modify
|
It is known that N rooks may be placed on a 2-dimensional NxN chessboard so that every square is controled by at least one rook.
What's the minimal number of rooks on 3-D chessboard NxNxN to meet this condition?
Generalize to K-dimensional chessboard.
If this is important: I don't know the answer
|
|
 IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: 3D Chessboard Full Control
« Reply #1 on: Sep 25th, 2003, 12:48pm » |
Quote Modify
|
Well, since each rook can control at most 3N-2 squares, it should be evident that we need at least N3/(3N-2), which is a little larger than N2/3.
But we could also show that we can't meet this lower bound, because you can only put N rooks in there before you have at least some squares controlled by more than one rook.
It should also be obvious that we can do it with N2 rooks, but this is not necessarily the best we can do. In fact, it's definitely not the best, because a 2x2x2 board can be controlled by 2 rooks. Hmm ...
|
| « Last Edit: Sep 25th, 2003, 12:50pm by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
visitor
Guest
|
|
Re: 3D Chessboard Full Control
« Reply #2 on: Sep 25th, 2003, 6:46pm » |
Quote Modify
 Remove
|
It's easy enough to figure out a theoretical minimum.
Start by placing N rooks on each horizontal level. Now you will remove M rooks from each level. That will leave M^2 free spaces on that level that are not being controlled. Each of those spaces must have a rook directly above or directly below it, so the remaining N-1 levels must have at least M^2 rooks total.
So for an 8x8x8 board: if M is 4 then N-1 levels will have 28 rooks, more than enough to cover the M^2 free spaces on each level. And in fact you can remove 4 more rooks (from 4 different levels, so M for those 4 levels is 5 (matching the 25 rooks available to cover their free spaces). The total is 28 rooks. Now whether those rooks can actually be given a satisfactory arrangement, I don't know.
And I'm not very good at visualizing a K-dimensional chessboard to generalize.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: 3D Chessboard Full Control
« Reply #3 on: Sep 26th, 2003, 7:18am » |
Quote Modify
|
I think the visitor's method may be assuming too much symmetry. Is it really obvious that there must be an optimum solution with as nearly as possible the same number of rooks per level.
|
|
IP Logged |
|
|
|
visitor
Guest
|
|
Re: 3D Chessboard Full Control
« Reply #4 on: Sep 26th, 2003, 7:26am » |
Quote Modify
Remove
|
My theoretical minimum is too minimum. The best I could come up with is
for N=3: 5
for N=4: 8
for N=5: 13
for N=6: 18
for N=8: 32
To generalize for a K-dimensional board, it's best to define the problem numerically. Create a list of numbers in base N-1, up to K digits long, such that you can generate any number up to K digits long by changing a single digit in one of your numbers.
SUppose N is 11 and K is 4. Then our riddle would be in base 10 and we'd be asking for a list of 4 digit numbers (including leading 0's) that can generate all numbers up to 9999 by changing a single digit. Can any of our local mathematicians solve that?
I figured out the 2x2x2x2 chessboard, at least. It's 4. That is, 1111, 1000, 0001, 0110
|
|
IP Logged |
|
|
|
visitor
Guest
|
|
Re: 3D Chessboard Full Control
« Reply #5 on: Sep 26th, 2003, 9:05am » |
Quote Modify
Remove
|
Duh, change that N-1 to N. I don't know what I was thinking.
Anyway, my first attempt at a solution for 3x3x3x3 is 16. That's probably not optimal, but close.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: 3D Chessboard Full Control
« Reply #6 on: Sep 29th, 2003, 1:16am » |
Quote Modify
|
on Sep 26th, 2003, 7:26am, visitor wrote:My theoretical minimum is too minimum. The best I could come up with is...
|
|
Visitor, this is interesting... Are you confident these are the optimal numbers? How did you get them? I only managed to get the numbers for N = 3, 4. By the way, assuming your numbers are correct: this sequence does not appear in Sloane's Encyclopedia.
I also tried to realize what conditions the optimal placement may satisfy. For instance:
- Is it true that for any N, there exists an optimal placement where N rooks may be chosen so that no two of them control the same field? The answer is No (counterexample given by N=3), meaning that the greedy placement algorithm won't always give an optimum.
- Is it true that for any N, there exists an optimal placement which is symmetric (with respect to a subgroup of a symmetry group of a cube). The answer seems to be Yes, but I haven't got an evidence.
Just thinking aloud...
on Sep 26th, 2003, 7:18am, rmsgrey wrote:| Is it really obvious that there must be an optimum solution with as nearly as possible the same number of rooks per level. |
|
I agree, it's intuitive. Also, the N=3, 4 cases satisfy this.
|
|
IP Logged |
|
|
|
visitor
Guest
|
|
Re: 3D Chessboard Full Control
« Reply #7 on: Sep 29th, 2003, 6:26am » |
Quote Modify
Remove
|
I'm not at all confident that my numbers are optimal, but I used a method that is easy to expand for any N (when K is 2) The formula is simply (N^2)/2 when N is even and
((N-1)/2)^2+((N+1)/2)^2 when N is odd.
Here's my visualized solution for N=5, which should make the method obvious (the numbers are what level the rook is on)
12300 123000
23100 231000
31200 312000
00045 000456
00054 000564
000645
It appears that this method can be expanded to any K as well; (I think you'll just replace the ^2 with ^(K-1).) The 3x3x3x3 board is optimal at 15. Here's my 4x4x4x4 solution (32),
1200 2100 0034 0043
2100 1200 0043 0034
0034 0043 1200 2100
0043 0034 2100 1200
//Corrected by Icarus in accordance with Visitor's later post below.
|
| « Last Edit: Sep 30th, 2003, 7:08pm by Icarus » |
IP Logged |
|
|
|
visitor
Guest
|
|
Re: 3D Chessboard Full Control
« Reply #8 on: Sep 29th, 2003, 6:28am » |
Quote Modify
Remove
|
That first chart is both N=5 and N=6 (not quite formatted correctly)
The second set of numbers shows one set of numbers for each of the 4th dimension levels.
|
|
IP Logged |
|
|
|
visitor
Guest
|
|
Re: 3D Chessboard Full Control
« Reply #9 on: Sep 30th, 2003, 6:45am » |
Quote Modify
Remove
|
In my N=5 and N=6 solutions (for K=3), I made a last minute change that threw in an error. The first line of each should be 12300 or 123000.
I was hoping somebody else would jump in with a better solution. My 4-dimensional method of extending the same method works, but it seems horribly inefficient. But I can't seem to improve on it. In 2 dimensions you needed N rooks per level. In 3 dimensions N/2 rooks per level. But in 4 dimensions (and I presume beyond) my method doesn't reduce that any further. In that 4x4x4x4 solution, by the time you've placed the rooks onthe first 3 boards, those three are completely controlled, and the fourth has 24 of its 64 spaces controlled; yet it's still going to take just as many rooks to finish it off.
Anyone who's good at 4-dimensional analysis should feel free to point me to a better answer.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: 3D Chessboard Full Control
« Reply #10 on: Sep 30th, 2003, 9:51am » |
Quote Modify
|
on Sep 30th, 2003, 6:45am, visitor wrote:| In my N=5 and N=6 solutions (for K=3), I made a last minute change that threw in an error. The first line of each should be 12300 or 123000. |
|
That's OK. I managed to reconstruct the right configuration. It's so simple... I was thinking in a completely different direction.
on Sep 30th, 2003, 6:45am, visitor wrote:| I was hoping somebody else would jump in with a better solution. |
|
There are some hints that your solution for K=3 is optimal. However, the proof is still missing.
on Sep 30th, 2003, 6:45am, visitor wrote:| My 4-dimensional method of extending the same method works, but it seems horribly inefficient. But I can't seem to improve on it. In 2 dimensions you needed N rooks per level. In 3 dimensions N/2 rooks per level. But in 4 dimensions (and I presume beyond) my method doesn't reduce that any further |
|
My friend (who introduced me to this problem) told me that this problem was once proposed at the Soviet Olympiad, and that the exact answer was known just for K=3; for higher dimensions only the bounds were known.
Anyway, I think you made an excellent progress on this puzzlle, Visitor!
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 3D Chessboard Full Control
« Reply #11 on: Sep 30th, 2003, 7:18pm » |
Quote Modify
|
I corrected your original post, so that those reading it for the first time will see it in the right form. May I suggest again that you register. Then you can correct erroneous posts yourself! And as a bonus, you're great knowledge and experience in international investment will be acknowledged with the financial opportunity of a lifetime  (a possibly rather short lifetime if you were to act upon it  )
Okay - so the latter inducement is not exactly a strong selling point. But this is the only time it has happened so far. Hopefully, more of them can be avoided.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Perfection
Newbie
Gender:
Posts: 17
|
|
Re: 3D Chessboard Full Control
« Reply #12 on: Nov 22nd, 2003, 10:45pm » |
Quote Modify
|
Please excuse the [nu]b question, but what exactly is a "3d chessboard" ? Is it just an NxNxN grid? And what exactly are the rules for a rook in a 3d chessboard? And what is defined as full control?
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: 3D Chessboard Full Control
« Reply #13 on: Nov 23rd, 2003, 12:04am » |
Quote Modify
|
A k-dimensional "chessboard" is just a regular grid of k-cubes forming a k-cube of side N - so the 3D chessboard is indeed an NxNxN grid.
A k-rook can move parallel to any of the edges of its k-chessboard, so it "controls" any cell that differs in at most one co-ordinate (so a 3-rook at (1,2,3) on a 3x3x3 board would control (1,2,3), (2,2,3), (3,2,3), (1,1,3), (1,3,3) (1,2,1) and (1,2,2))
"Full control" is the situation where every cell is controlled by at least one rook.
|
|
IP Logged |
|
|
|
godskook
Guest
|
|
Re: 3D Chessboard Full Control
« Reply #14 on: Feb 17th, 2004, 7:58am » |
Quote Modify
Remove
|
This is what I have so far on the 3-dimensional board.
Each NxNxN cube has "S" as a solution. Here are some of the numbers I got.
N=1
S=1
N=2
S=2
N=3
S=5
N=4
S=8
N=5
S=13*
N=6
S=20+
N=7
S=21*
N=8
S=32+
N=9
S=40#
N=10
S=52+
N=12
S=80+
N=14
S=84+
N=16
S=128+
A * means that I am reasonably sure but not positive
A + means that I used a technique which relied on an earlier number, that does give a solution just possibly not the optimal one
A # means that I have good reasons to doubt my answer as the most optimal
I while try and post some of the trends I found later, but I don't have time right now.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: 3D Chessboard Full Control
« Reply #15 on: Feb 19th, 2004, 12:34am » |
Quote Modify
|
godskook, there is a strong evidence (I don’t know the proof, however) that S = N2/2 for N even, and S = (N2 + 1)/2 for N odd.
This contradicts your results for N = 6, 10 and 12. I would like to see the actual configurations, if you have them.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 3D Chessboard Full Control
« Reply #16 on: Feb 19th, 2004, 1:03am » |
Quote Modify
|
he did mark them with a plus, so as he said they might not be optimal (and in all three cases you predict it to be lower, so that fits)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: 3D Chessboard Full Control
« Reply #17 on: Feb 19th, 2004, 4:00am » |
Quote Modify
|
towr, you are right, I missed the direction...
If so, there are N=7 and 9 where goodskook claims to make better than predicted optimum (for N=9 I am not sure 'cause I don't understand exactly the meaning of # sign).
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: 3D Chessboard Full Control
« Reply #18 on: Feb 19th, 2004, 4:41am » |
Quote Modify
|
on Feb 19th, 2004, 4:00am, Barukh wrote:| (for N=9 I am not sure 'cause I don't understand exactly the meaning of # sign). |
|
on Feb 17th, 2004, 7:58am, godskook wrote:| A # means that I have good reasons to doubt my answer as the most optimal |
|
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
godskook
Guest
|
|
Re: 3D Chessboard Full Control
« Reply #19 on: Feb 19th, 2004, 8:41am » |
Quote Modify
Remove
|
for all my higher even results-those marked with a + I used the following technique
1.Divide the cube into eight equal regions each of size N/2
2.Take the solution to the previously solved case of N/2 and insert it into the size N cube so that each S(N/2) solution occuppies one and only one of the regions found in step one without any rook being able to capture any other rook.
Although this technique does not guarentee optimization, it does guarentee a solution. It is easy to check because all you have to consider is any one of the four regions that does not have the N/2 solutions in them(thanks to symmetry) and show that the rooks from the three adjacent regions control all the spaces in this one.
this suggests the relationship: S(2N)<=4S(N)
my solution configs for 6,7,9,10,12 are as follows:
the solutions for 12 and 6 use the solution to 3 and are the the direct result of the above relationship - If someone needs the solution to N=3 let me know
My 10 is base on my 5 using the above technique
the solution to my N=5,and N=7 I use the following placements
for both
<3.3.3>
<3.5.5>
<4.4.4>
<5.5.3>
<5.3.5>
<1.1.1>
<2.2.2>
<4.1.2>
<4.2.1>
<1.4.2>
<2.4.1>
<1.2.4>
<2.1.4>
For just the 7
<6.6.6>
<7.7.7>
<4.6.7>
<4.7.6>
<6.4.7>
<7.4.6>
<7.6.4>
<6.7.4>
Hope that helps
|
|
IP Logged |
|
|
|
Guest
Guest
|
|
Re: 3D Chessboard Full Control
« Reply #20 on: Feb 19th, 2004, 9:26am » |
Quote Modify
Remove
|
In your solution for N=7, I don't see any rook attacking
3,(6 or 7),(1 or 2) or
(6 or 7),3,(1 or 2) or
(1 or 2),(6 or 7),5 or
(6 or 7),(1 or 2),5 or
(1 or 2),(3 or 5),(6 or 7) or
(3 or 5), (1 or 2), (6 or 7)
|
|
IP Logged |
|
|
|
godskook
Guest
|
|
Re: 3D Chessboard Full Control
« Reply #21 on: Feb 22nd, 2004, 3:20pm » |
Quote Modify
Remove
|
You're right  I missed those. thats what I get for thinking I could generalize
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: 3D Chessboard Full Control
« Reply #22 on: Apr 27th, 2004, 12:10am » |
Quote Modify
|
If we reformulate this puzzle in terms of error-correcting codes and link to it from the CS section, we can bring a new life to this thread.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: 3D Chessboard Full Control
« Reply #23 on: Apr 28th, 2004, 1:55pm » |
Quote Modify
|
Except that in error-correcting codes, the aim would be to put as many rooks as possible without having 2 rooks attacking the same cell.
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: 3D Chessboard Full Control
« Reply #24 on: Apr 28th, 2004, 3:09pm » |
Quote Modify
|
on Apr 28th, 2004, 1:55pm, grimbal wrote:| Except that in error-correcting codes, the aim would be to put as many rooks as possible without having 2 rooks attacking the same cell. |
|
Rather "controlling the same cell" (a rook does not attack a cell it is in). My understanding is that our aim is equivalent to constructing a minimal code that has a (weird) property of all single-digit errors being correctable or detectable, but not one double-digit error can as a double-digit error.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print