Author 
Topic: 3D Chessboard Full Control (Read 13866 times) 

Patashu
Newbie
Gender:
Posts: 18


Re: 3D Chessboard Full Control
« Reply #25 on: Sep 2^{nd}, 2004, 4:18am » 
Quote Modify

Extension on the riddle: Rooks are considered orthagonal sliders. How many pieces would you need to control a whole NxNxN three dimensional chessboard if the pieces... i) slid diagonally? ii) slid triagonally? iii) slid orthagonally and diagonally? iv) slid orthagonally and triagonally? v) slid diagonally and triagonally? vi) slid orthagonally, diagonally and triagonally? (on a 3D chessboard, orthagonals are from face to face, diagonals are from edge to edge, triagonals are from corner to corner)


IP Logged 



Ace_T
Newbie
Gender:
Posts: 13


Re: 3D Chessboard Full Control
« Reply #26 on: Mar 6^{th}, 2005, 8:02pm » 
Quote Modify

on Feb 19^{th}, 2004, 8:41am, godskook wrote:for all my higher even resultsthose marked with a + I used the following technique... <snip> 
 This problem is the same (as noted by Grimbal...thanks) as the broken combination lock problem http://www.ocf.berkeley.edu/~wwu/cgibin/yabb/YaBB.cgi?board=riddles_har d;action=display;num=1109913027 The solution for an n x n x n cube (assume n is odd, it's easier/symmetrical if even) is: Pick a corner (let's say, starting at (1,1,1)) of a cube of size (n+1)/2 that is in a corner of the big cube, and solve according to below. Then pick the opposite cube (say, starting at ((n+1)/2,(n+1)/2,(n+1)/2)) which will be of size (n1)/2 and solve it as below too. The combination is the total solution. (below ) Starting at one corner (for simplicity, assume (1,1,1) then keeping 'z' constant, for each guess add 1 to each of x and y a total of (n+1)/2 times (or (n1)/2 times for the second cube...let's just call it 'N' for now). Then add 1 to z and start x,y at x+1, y+0 from the starting point of your first guess at z=1. Continue adding 1 to each of x and y, 'rolling over' if you go over N. Continue for each z until z= N, starting each level with x at 1 more than the previous level. So for n=7, a solution is: (1,1,1), (2,2,1), (3,3,1), (4,4,1), (2,1,2), (3,2,2), (4,3,2), (1,4,2), (3,1,3), (4,2,3), (1,3,3), (2,4,3), (4,1,4), (1,2,4), (2,3,4), (3,4,4), (the above handles the cube of size (n+1)/2) (5,5,5), (6,6,5), (7,7,5), (6,5,6), (7,6,6), (5,7,6), (7,5,7), (5,6,7), (6,7,7) (handles the rest)

« Last Edit: Mar 7^{th}, 2005, 5:07pm by Icarus » 
IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: 3D Chessboard Full Control
« Reply #27 on: Mar 7^{th}, 2005, 6:27am » 
Quote Modify

Thanks, Ace_T, for contributing this. Am I right that the proof that this solution is optimal is still missing?


IP Logged 



Ace_T
Newbie
Gender:
Posts: 13


Re: 3D Chessboard Full Control
« Reply #28 on: Mar 7^{th}, 2005, 5:07pm » 
Quote Modify

Yes, unfortunately Given the visualization (see the Broken bike combination lock thread) you *can* see that the solution is optimal if following that approach, but the 'if following that approach' doesn't give you much proof to stand on! I feel that the thought process going into that visualization should be able to show that it is optimal (but by someone much better at proofs). At least the method does come down to the formula noted by a few on this thread. Oh well, off to a different problem!


IP Logged 



Ace_T
Newbie
Gender:
Posts: 13


Re: 3D Chessboard Full Control
« Reply #29 on: Mar 8^{th}, 2005, 8:23pm » 
Quote Modify

Actually, there may be a proof in this approach. See note in the other thread on visualization and follow this through: Two notes initially: 1. The selection of an (x,y,z) covers all guesses (x,y,?), (x,?,z), and (?,y,z) where ? represents any value from 1 to n 2. The guess can be seen to be within a 'subcube' of m x m x m (where 'm' = max value of x,y,z). (sidebar) To help viusalize, imagine initially that n is even, and you divide the cube into 8 equal 'subcubes' of size n/2 x n/2 x n/2 by cutting the larger cube along the lines of symmetry a) The selection of an (x,y,z) within a 'subcube' covers guesses in 4 of the 8 'subcubes' (the one in which the selection is made, plus the three others that contain the same 'x and y', 'x and z' and 'y and z'), but will never cover any guesses in the other 4 'subcubes' (symmetrical). b) The minimum number of guesses to cover the selected 'subcube' (and the 3 other subcubes affected) must be equal to the area of one side of the 'subcube' (n**2 / 4), since each guess can only cover one square in this crosssectional area. c) To complete the overall cube, you must also cover the other 4 'subcubes'. As noted, this can be done in (n**2 / 4) guesses by selecting the 'subcube' that is 'opposite' from (from (n/2,n/2,n/2) to (n,n,n)) the first one selected. The selection of guesses in any other 'subcube' will, by definition, not complete the cube. Now, back to the general proof. The 'subcube' selected (for your x,y,z guess) does not have to be of size n/2. In fact, the cube can be solved by solving any two 'subcubes' where one is of size 'i' (i<=n) (starting at 1,1,1 for simplicity) and the other of size ni which is 'opposite' to the first 'subcube' within the large cube. In these cases, the same '3dimensional L' visualization applies (although the big cube is not divided into 8 subcubes now, just 2 subcubes of different size plus the other volumes that get 'filled' as you solve each subcube). The solution is S = solution for first subcube + solution for second subcube = i**2 + (ni)**2 = n**2 2ni +2(i**2) ==> if n is even, this is optimal (minimum) at i=n/2 If n is odd (actually, even is just a special case of odd) S = solution for first subcube + solution for second subcube = i**2 + (ni)**2 (where i <> ni) = n**2 2ni +2(i**2) (as before) ==> this is optimal (minimum) at n2i=min, or in other words, when the two subcubes are closest in size. This comes down to the familiar equations of S = n**2 / 2 (for n=even) S = (n**2+1) / 2 (for n=odd)


IP Logged 



YADDA
Newbie
Posts: 2


Re: 3D Chessboard Full Control
« Reply #30 on: Mar 26^{th}, 2005, 7:09am » 
Quote Modify

2x2x2:2 3x3x33 nxnxn:n


IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: 3D Chessboard Full Control
« Reply #31 on: Mar 26^{th}, 2005, 8:14am » 
Quote Modify

on Mar 26^{th}, 2005, 7:09am, YADDA wrote: Wow! That is far better than everything suggested over the years! But I don't believe this may be achieved. Could you elaborate, please?


IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: 3D Chessboard Full Control
« Reply #32 on: Mar 26^{th}, 2005, 8:25am » 
Quote Modify

Indeed, it is far better than the easily proven minimum that James Fingas gives in the first reply: N^{3}/(3N2) > N^{2}/3. I.e., it is mistaken.


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



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: 3D Chessboard Full Control
« Reply #33 on: Mar 26^{th}, 2005, 1:37pm » 
Quote Modify

Well going by N^{2}/3, for the first two that works. 4/3 < 2 9/3 = 3 But generalizing it from just those two examples is faux pas..

« Last Edit: Mar 26^{th}, 2005, 1:38pm by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: 3D Chessboard Full Control
« Reply #34 on: Mar 26^{th}, 2005, 8:15pm » 
Quote Modify

It does not work even for 3: N^{3}/(3N2) is the minimum, and for N=3, this is 27/7, so at least 4 rooks are needed. On the other hand, it is fairly obvious how to control a 2x2x2 board with 2 rooks.


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



Deedlit
Senior Riddler
Posts: 476


Re: 3D Chessboard Full Control
« Reply #35 on: Mar 29^{th}, 2005, 11:51pm » 
Quote Modify

A minor improvement to the lower bound: Let i be the minimum number of rooks in any plane. Then there will be (ni)^{2} squares left unattacked, and each additional rook can attack only one square. So there will be at least i + (ni)^{2} rooks. On the other hand, we need at least n(i+1) rooks if we want every plane to have more than i rooks. So R(n) >= max { min { i + (ni)^{2}, n(i+1)}  i = 1..n} This imples R(n) is at least n^{2}/phi^{2}, where phi is the golden ratio (1 + sqrt(5))/2. Interestingly, for higher dimensions the argument gives a bound worse than n^{k1}/(kn  k +1). I suppose that for higher dimensions, the primary question is the minimum number for n=2; we can then use this case for higher values of n, yielding similar values for R(k,n)/n^{k1}. I'm guessing that we can get close to 2^{k}/(k+1)...


IP Logged 



Joe
Guest


Re: 3D Chessboard Full Control
« Reply #36 on: Jul 11^{th}, 2005, 8:11am » 
Quote Modify
Remove

If the question is referring to the surface of a 3D chess board, the answer is 48, unless pieces can go around corners. Then the answer is 15. If the question refers to the cubic spaces on the inside of the 3D chess board, the answer is 64.


IP Logged 



drifting
Newbie
Gender:
Posts: 1


Re: 3D Chessboard Full Control
« Reply #37 on: Apr 5^{th}, 2007, 11:59am » 
Quote Modify

For k>3 (and maybe k==3 that), I do not believe a general formula exists to determine the minimum number of rooks to control a kdimensional chessboard. It is possible to produce an optimal configuration of rooks where no two rooks attack the same square when certain conditions are met. The formula for the theoretical minimum number of rooks is: n^{k} / k(n  1) + 1 When n = k  1, this reduces to n^{n  1} which seems to hold. I've got rook configurations for k = 2, 3, 4, 5 that support this. I can't prove it however (my days of mathematical proofs are LONG behind me). For n = 2, k = 3 the rooks are 10 02 Number of rooks: 2 (2^{2  1}) For n = 3, k = 4 the rooks are: 100 030 002 020 001 300 003 200 010 Number of rooks: 9 (3^{3  1})


IP Logged 



chetangarg
Newbie
Gender:
Posts: 30

Proof of Optimal solution For the 3D chessboard Here is the attached file.


IP Logged 



Random Lack of Squiggily Lines
Senior Riddler
Everything before 7/1/2008 is now irrelevant.
Gender:
Posts: 460


Re: 3D Chessboard Full Control
« Reply #39 on: Apr 25^{th}, 2007, 12:32pm » 
Quote Modify

on Sep 26^{th}, 2003, 9:05am, visitor wrote:Duh, change that N1 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. 
 I didnt know the forth demension existed could someone explain it, i just cant imagine it


IP Logged 
You can only believe i what you can prove, and since you have nothing proven to cmpare to, you can believe in nothing.
I have ~50 posts to hack a "R" into a "D". Which one?



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: 3D Chessboard Full Control
« Reply #40 on: Apr 25^{th}, 2007, 12:52pm » 
Quote Modify

on Apr 25^{th}, 2007, 12:32pm, tiber13 wrote:I didnt know the forth dimension existed could someone explain it, i just cant imagine it 
 Well, typically, you should be experiencing three spational dimensions (length,width,height) and a temporal one (time), that's 4 dimensions right there. If you consider a movie, it's a succesive series of images that get replaced one after the other. Each image is 2D. If you'd stack them on top of each other, you'd get a 3D block that contains all images at once; two dimensions would represent the image plane, and one dimension would represent time. Now obviously with spacetime that's a bit harder to imagine, because how can you stack spaces the way you stack planes? Obviously it can't be stacked within the three dimension, so it has to be stacked along a fourth.

« Last Edit: Apr 25^{th}, 2007, 12:53pm by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: 3D Chessboard Full Control
« Reply #41 on: Apr 25^{th}, 2007, 7:30pm » 
Quote Modify

The word "dimension" actual refers to a number which specifies a position. Consider a fly crawling on the ceiling of your room. (There are historical reasons for this example. The whole concept I am about to describe was first conceived by a kid watching a fly crawl around on the ceiling of his room. The kid's name was DesCartes, and you will be hearing more about him as you continue your education.) Suppose at first the fly crawled along the edge between the ceiling and wall. If you wanted to tell someone exactly where the fly was at a particular time, you need only measure the distance from the corner to the fly and give them that distance. I.e., if the fly limits itself to that edge, its position can be described by one number, or one "dimension". So the edge is onedimensional. But our brave fly leaves his cozy edge and ventures out onto the ceiling proper. Now to tell someone exactly where the fly is at, you need two numbers  the distance to the north and west walls, for example. So the ceiling is twodimensional. Finally, the fly has a flash of insight: "Wait a minute! I'm called a 'fly' for a reason! What am I crawling around for?", and takes off erratically around the room. Now, in order to describe its position at a particular time, you need 3 numbers: distance to North wall, distance to the West wall, distance to the ceiling. Your room is 3dimensional. But, we've only been describing the fly's position at a given time. In order to truly describe the situation to your demented friend (he listening to you describe fly positions  he can't be all that bright), you also need to tell him when the fly was in the position. This requires a 4th number. So spacetime is 4dimensional. Now, have we finally got the maximum number of dimensions? Nope. Your fly has found buzzing around your room such a jolly experience, he just had to share it. So he goes off and finds a buddy, and next thing you know, both are whipping dizzily around your head. If you fix a particular time again and want to describe this, you are going to need 6 numbers  3 for each fly, to specify positions. Yes  the twofly system is 6dimensional! And that is without time. With time, it becomes 7dimensional (1 for time, 6 to describe the space positions at that time). It doesn't stop there, either. After all, there are plenty more flies where those two came from. Mathematicians generally do not work in a fixed number of dimensions. We will say instead that our construct is "Ndimensional", for some arbitrary number N. Much of what we do actually has an infinite number of dimensions. For example, a basic concept of higher mathematics is a sequence: an infinite list of numbers. For example, 1, 2, 4, 8, 16, 32, ... is a sequence. The set consisting of all possible sequences is an infinite dimensional space (obviously so, since each position in the sequence is an independent number, and there are infinitely many positions).


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



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: 3D Chessboard Full Control
« Reply #42 on: Apr 26^{th}, 2007, 2:28am » 
Quote Modify

on Apr 25^{th}, 2007, 11:05am, chetangarg wrote:Proof of Optimal solution For the 3D chessboard Here is the attached file. 
 Tnanks for posting it here. Unfortunately, I didn't understand the following reasoing in your proof: "..Now consider a cuboid other than layer first (considered previously).The 25 rooks can control the (5x8+5x3=55) places but its other 9 places must be controlled by 9 rooks... "


IP Logged 



chetangarg
Newbie
Gender:
Posts: 30


Re: 3D Chessboard Full Control
« Reply #43 on: Apr 26^{th}, 2007, 5:48am » 
Quote Modify

@ Barukh hey barukh.... At first layer there are 25 uncontrolled positions which are controlled by 25 rooks placed at other 7 layers. Suppose these 25 rooks are all placed on 2nd layer. now at this layer there are still 9 places remaining uncontrolled by these 25 rooks, from these 9 places 3 will be controlled by rooks present at 1st layer. and 6 will be controlled by 6 rooks present at remaining layers. Now still we require 25+3+6=34 rooks.


IP Logged 



Sir_Rogers
Newbie
Posts: 4


Re: 3D Chessboard Full Control
« Reply #44 on: Jun 19^{th}, 2007, 1:37am » 
Quote Modify

Hi folks, my first post here, I just registered because the problem looked interesting. As far as I'm aware there's no correct forumla in this topic yet and there's no proof for an optimal solution. So I want to have a go at it. The key lies in optimal placement of the rooks in a 3D Ngrid. Basically it is the same process for any cube of side N, with N being bigger than 2. Yes, the forumal only works for n>2, for reason I will explain, since we know the optimal solutions for n=1 and n=2, it doesn't really matter. Now lets assume n=5. We have 5 layers, for optimal placement, the first and the last layer will always contain a total of 4 rooks, 2 in the top layer, 2 in the bottom layer, positioned like this: Bottom layer x  x Top layer x  x I'm sorry that I can't provide any hightech visualisation, I'll try to explain it to the best I can. Now this is the optimal placement for the top and bottom layer. All that is left to cover is the "inside" of the cube, all the outer fields have been covered. Now this is variable on the size of the field, but the principle stays the same. In this diagram, o are the fields controlled by the 4 rooks just described above: oo    oo Now as we have 5 layers in total, substracting top and bottom layer, 3 layers are left, that look exactly like this. Now to be able to cover one of these, we need a minimum of 3 rooks at optimal use: oo x x x oo The other 2 would look like this: oo x x x oo oo x x x oo The point is, that eventually they also control the middle squares that were missing in the top and bottom layer. Now this pattern applies to all cubes with a side of N where n>2. The formula we can deduce from this is: 4 + (n2)^2 4 because of the 4 rooks that are always needed in the top and the bottom layer. n2 is the amount of layers that are "in the middle". and ^2 because that's the amount of rooks you need to control the rest. I hope that I explained it correctly. If there are any doubts or questions, please feel free to ask.

« Last Edit: Jun 19^{th}, 2007, 1:42am by Sir_Rogers » 
IP Logged 



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7517


Re: 3D Chessboard Full Control
« Reply #45 on: Jun 19^{th}, 2007, 4:45am » 
Quote Modify

If I take your solution for 6x6x6, I get: o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o . . . . . . . x . . . . . . x . . . . . . x . . . . . . x . . . . . . . . . . . . . . . x . . . . . . x . . . . . . x . . x . . . . . . . . . . . . . . . . . . . x . . . . . . x . . x . . . . . . x . . . . . . . . . . . . . . . . . . . x . . x . . . . . . x . . . . . . x . . . . . . . . . . . . . o . . . . . . . . . . . . . . . . . . . . . . . . o . . . . . which is equivalent, if you group together the outer sides, to . o . . . . o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o . . . . . . o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x . . . . . . x . . . . . . x . . . . . . x . . . . . . . . . . . . . . . x . . . . . . x . . . . . . x . . x . . . . . . . . . . . . . . . . . . . x . . . . . . x . . x . . . . . . x . . . . . . . . . . . . . . . . . . . x . . x . . . . . . x . . . . . . x . with 8 o's and 16 x's But balancing the o's and the x's better, you can do o . . . . . . o . . . . . . o . . . . . . . . . . . . . . . . . . . . . . o . . . . . . o . . . o . . . . . . . . . . . . . . . . . . . . . . . . . o . . . o . . . . . . o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x . . . . . . x . . . . . . x . . . . . . . . . . . . . . . . . . . . . . x . . . . . . x . . . x . . . . . . . . . . . . . . . . . . . . . . . . . x . . . x . . . . . . x . with 18 rooks altogether. I think that is the best solution known so far.


IP Logged 



Random Lack of Squiggily Lines
Senior Riddler
Everything before 7/1/2008 is now irrelevant.
Gender:
Posts: 460


Re: 3D Chessboard Full Control
« Reply #46 on: Jul 8^{th}, 2007, 7:11am » 
Quote Modify

Thanks for the four demension thing, i thought the fourth demension was depth, or something like that, explaining the area in the hole in the shape.


IP Logged 
You can only believe i what you can prove, and since you have nothing proven to cmpare to, you can believe in nothing.
I have ~50 posts to hack a "R" into a "D". Which one?



Hippo
Uberpuzzler
Gender:
Posts: 919


Re: 3D Chessboard Full Control
« Reply #47 on: Mar 9^{th}, 2016, 10:33am » 
Quote Modify

on Apr 26^{th}, 2007, 5:48am, chetangarg wrote:@ Barukh hey barukh.... At first layer there are 25 uncontrolled positions which are controlled by 25 rooks placed at other 7 layers. Suppose these 25 rooks are all placed on 2nd layer. now at this layer there are still 9 places remaining uncontrolled by these 25 rooks, from these 9 places 3 will be controlled by rooks present at 1st layer. and 6 will be controlled by 6 rooks present at remaining layers. Now still we require 25+3+6=34 rooks. 
 But these 6 squares could be covered by 3 additional rooks on 2nd layer. ... 25+3+3=31 ... (of course not all of 25 rooks should be on 2nd layer...) Of course 3*8+25 is too much, but the argument is not clear that way. We have to proove the 3x3x8 box requires at least 9 rooks. (Or in general KxKxn box require K^{2} where K<n/2 is minimal number of rooks per layer).


IP Logged 



