wu :: forums « wu :: forums - 3D Chessboard Full Control » Welcome, Guest. Please Login or Register. Apr 17th, 2024, 10:03am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: towr, Grimbal, ThudnBlunder, william wu, Icarus, SMQ, Eigenray)    3D Chessboard Full Control « Previous topic | Next topic »
 Pages: 1 2 Reply Notify of replies Send Topic Print
 Author Topic: 3D Chessboard Full Control  (Read 14527 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

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: 2872
 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: 2872
 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: 7526
 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
 Pages: 1 2 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »