wu :: forums
« wu :: forums - 3D Chessboard Full Control »

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 5:06am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: Icarus, william wu, ThudnBlunder, SMQ, towr, Grimbal, Eigenray)
   3D Chessboard Full Control
« Previous topic | Next topic »
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: 3D Chessboard Full Control  (Read 14503 times)
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
3D Chessboard Full Control  
« on: Sep 25th, 2003, 12:25pm »
Quote Quote Modify 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
*****





   
Email

Gender: male
Posts: 949
Re: 3D Chessboard Full Control  
« Reply #1 on: Sep 25th, 2003, 12:48pm »
Quote Quote Modify 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

Email

Re: 3D Chessboard Full Control  
« Reply #2 on: Sep 25th, 2003, 6:46pm »
Quote Quote Modify Modify Remove 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
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: 3D Chessboard Full Control  
« Reply #3 on: Sep 26th, 2003, 7:18am »
Quote Quote Modify 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

Email

Re: 3D Chessboard Full Control  
« Reply #4 on: Sep 26th, 2003, 7:26am »
Quote Quote Modify Modify Remove 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

Email

Re: 3D Chessboard Full Control  
« Reply #5 on: Sep 26th, 2003, 9:05am »
Quote Quote Modify Modify Remove 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: male
Posts: 2276
Re: 3D Chessboard Full Control  
« Reply #6 on: Sep 29th, 2003, 1:16am »
Quote Quote Modify 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

Email

Re: 3D Chessboard Full Control  
« Reply #7 on: Sep 29th, 2003, 6:26am »
Quote Quote Modify Modify Remove 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

Email

Re: 3D Chessboard Full Control  
« Reply #8 on: Sep 29th, 2003, 6:28am »
Quote Quote Modify Modify Remove 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

Email

Re: 3D Chessboard Full Control  
« Reply #9 on: Sep 30th, 2003, 6:45am »
Quote Quote Modify Modify Remove 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: male
Posts: 2276
Re: 3D Chessboard Full Control  
« Reply #10 on: Sep 30th, 2003, 9:51am »
Quote Quote Modify 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: male
Posts: 4863
Re: 3D Chessboard Full Control  
« Reply #11 on: Sep 30th, 2003, 7:18pm »
Quote Quote Modify 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 Tongue (a possibly rather short lifetime if you were to act upon it Wink)
 
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: male
Posts: 17
Re: 3D Chessboard Full Control  
« Reply #12 on: Nov 22nd, 2003, 10:45pm »
Quote Quote Modify 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
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: 3D Chessboard Full Control  
« Reply #13 on: Nov 23rd, 2003, 12:04am »
Quote Quote Modify 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

Email

Re: 3D Chessboard Full Control  
« Reply #14 on: Feb 17th, 2004, 7:58am »
Quote Quote Modify Modify Remove 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: male
Posts: 2276
Re: 3D Chessboard Full Control  
« Reply #15 on: Feb 19th, 2004, 12:34am »
Quote Quote Modify 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: male
Posts: 13730
Re: 3D Chessboard Full Control  
« Reply #16 on: Feb 19th, 2004, 1:03am »
Quote Quote Modify 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: male
Posts: 2276
Re: 3D Chessboard Full Control  
« Reply #17 on: Feb 19th, 2004, 4:00am »
Quote Quote Modify 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: male
Posts: 4489
Re: 3D Chessboard Full Control  
« Reply #18 on: Feb 19th, 2004, 4:41am »
Quote Quote Modify 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

Email

Re: 3D Chessboard Full Control  
« Reply #19 on: Feb 19th, 2004, 8:41am »
Quote Quote Modify Modify Remove 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

Email

Re: 3D Chessboard Full Control  
« Reply #20 on: Feb 19th, 2004, 9:26am »
Quote Quote Modify Modify Remove 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

Email

Re: 3D Chessboard Full Control  
« Reply #21 on: Feb 22nd, 2004, 3:20pm »
Quote Quote Modify Modify Remove Remove

You're right Grin I missed those. thats what I get for thinking I could generalize
IP Logged
Leo Broukhis
Senior Riddler
****





   


Gender: male
Posts: 459
Re: 3D Chessboard Full Control  
« Reply #22 on: Apr 27th, 2004, 12:10am »
Quote Quote Modify 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: male
Posts: 7526
Re: 3D Chessboard Full Control  
« Reply #23 on: Apr 28th, 2004, 1:55pm »
Quote Quote Modify 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: male
Posts: 459
Re: 3D Chessboard Full Control  
« Reply #24 on: Apr 28th, 2004, 3:09pm »
Quote Quote Modify 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
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board