wu :: forums « wu :: forums - 3D Chessboard Full Control » Welcome, Guest. Please Login or Register. Jul 2nd, 2022, 4:33am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: ThudnBlunder, Eigenray, towr, Icarus, SMQ, william wu, Grimbal)    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 14023 times)
Patashu
Newbie

Gender:
Posts: 18
 Re: 3D Chessboard Full Control   « Reply #25 on: Sep 2nd, 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 6th, 2005, 8:02pm » Quote Modify

on Feb 19th, 2004, 8:41am, godskook wrote:
 for all my higher even results-those marked with a + I used the following technique...

This problem is the same (as noted by Grimbal...thanks) as the broken combination lock problem http://www.ocf.berkeley.edu/~wwu/cgi-bin/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
(n-1)/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 (n-1)/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 7th, 2005, 5:07pm by Icarus » IP Logged
Barukh
Uberpuzzler

Gender:
Posts: 2276
 Re: 3D Chessboard Full Control   « Reply #27 on: Mar 7th, 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 7th, 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 8th, 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 'sub-cube' 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 'sub-cubes' 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 'sub-cube' covers guesses in 4 of the 8 'sub-cubes' (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 'sub-cubes' (symmetrical).
b) The minimum number of guesses to cover the selected 'sub-cube' (and the 3 other sub-cubes affected) must be equal to the area of one side of the 'sub-cube' (n**2 / 4), since each guess can only cover one square in this cross-sectional area.
c) To complete the overall cube, you must also cover the other 4 'sub-cubes'. As noted, this can be done in (n**2 / 4) guesses by selecting the 'sub-cube' 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 'sub-cube' will, by definition, not complete the cube.

Now, back to the general proof. The 'sub-cube' 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 'sub-cubes' where one is of size 'i' (i<=n) (starting at 1,1,1 for simplicity) and the other of size n-i which is 'opposite' to the first 'sub-cube' within the large cube. In these cases, the same '3-dimensional L' visualization applies (although the big cube is not divided into 8 sub-cubes now, just 2 sub-cubes of different size plus the other volumes that get 'filled' as you solve each sub-cube). The solution is
S = solution for first sub-cube + solution for second sub-cube
= i**2 + (n-i)**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 sub-cube + solution for second sub-cube
= i**2 + (n-i)**2 (where i <> n-i)
= n**2 -2ni +2(i**2)  (as before)
==> this is optimal (minimum) at |n-2i|=min, or in other words, when the two sub-cubes 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
Newbie

Posts: 2
 Re: 3D Chessboard Full Control   « Reply #30 on: Mar 26th, 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 26th, 2005, 8:14am » Quote Modify

on Mar 26th, 2005, 7:09am, YADDA wrote:
 nxnxn:n

Wow! That is far better than everything suggested over the years! But I don't believe this may be achieved.

 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 26th, 2005, 8:25am » Quote Modify

Indeed, it is far better than the easily proven minimum that James Fingas gives in the first reply: N3/(3N-2) > N2/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 26th, 2005, 1:37pm » Quote Modify

Well going by N2/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 26th, 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 26th, 2005, 8:15pm » Quote Modify

It does not work even for 3: N3/(3N-2) 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 29th, 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 (n-i)2 squares left unattacked, and each additional rook can attack only one square. So there will be at least i + (n-i)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 + (n-i)2, n(i+1)} | i = 1..n}

This imples R(n) is at least n2/phi2, where phi is the golden ratio (1 + sqrt(5))/2.

Interestingly, for higher dimensions the argument gives a bound worse than nk-1/(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)/nk-1. I'm guessing that we can get close to 2k/(k+1)...
 IP Logged
Joe
Guest

 Re: 3D Chessboard Full Control   « Reply #36 on: Jul 11th, 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 5th, 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 k-dimensional 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:
nk / k(n - 1) + 1

When n = k - 1, this reduces to nn - 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 (22 - 1)

For n = 3, k = 4 the rooks are:
100   030   002
020   001   300
003   200   010

Number of rooks: 9 (33 - 1)
 IP Logged
chetangarg
Newbie

Gender:
Posts: 30
 Re: 3D Chessboard Full Control   3D_Chessboard_solution.htm « Reply #38 on: Apr 25th, 2007, 11:05am » Quote Modify

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 25th, 2007, 12:32pm » Quote Modify

on Sep 26th, 2003, 9:05am, visitor wrote:
 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.

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 25th, 2007, 12:52pm » Quote Modify

on Apr 25th, 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 space-time 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 25th, 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 25th, 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 one-dimensional. 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 two-dimensional.

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 3-dimensional. 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 4-dimensional.

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 two-fly system is 6-dimensional! And that is without time. With time, it becomes 7-dimensional (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 "N-dimensional", 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 26th, 2007, 2:28am » Quote Modify

on Apr 25th, 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 26th, 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 19th, 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 N-grid.

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 high-tech 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:

o-----o
--------
--------
--------
o-----o

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:

o---o
-x---
--x--
---x-
o---o

The other 2 would look like this:

o---o
--x--
---x-
-x---
o---o

o---o
---x-
-x---
--x---
o---o

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 + (n-2)^2

4 because of the 4 rooks that are always needed in the top and the bottom layer. n-2 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 19th, 2007, 1:42am by Sir_Rogers » IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7519
 Re: 3D Chessboard Full Control   « Reply #45 on: Jun 19th, 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 8th, 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 9th, 2016, 10:33am » Quote Modify

on Apr 26th, 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 K2 where K<n/2 is minimal number of rooks per layer).
 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 »