|
||||||
|
Title: 3D Chessboard Full Control Post by Barukh on Sep 25th, 2003, 12:25pm 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: [hide]I don't know the answer[/hide] |
||||||
|
Title: Re: 3D Chessboard Full Control Post by James Fingas on Sep 25th, 2003, 12:48pm 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 ... |
||||||
|
Title: Re: 3D Chessboard Full Control Post by visitor on Sep 25th, 2003, 6:46pm It's easy enough to figure out a theoretical minimum. [hide] 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. [/hide] 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. |
||||||
|
Title: Re: 3D Chessboard Full Control Post by rmsgrey on Sep 26th, 2003, 7:18am 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. |
||||||
|
Title: Re: 3D Chessboard Full Control Post by visitor on Sep 26th, 2003, 7:26am My theoretical minimum is too minimum. The best I could come up with is [hide]for N=3: 5 for N=4: 8 for N=5: 13 for N=6: 18 for N=8: 32 [/hide] 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 [hide]4. That is, 1111, 1000, 0001, 0110 [/hide] |
||||||
|
Title: Re: 3D Chessboard Full Control Post by visitor on Sep 26th, 2003, 9:05am 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. |
||||||
|
Title: Re: 3D Chessboard Full Control Post by Barukh on Sep 29th, 2003, 1:16am on 09/26/03 at 07:26:20, visitor wrote:
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 09/26/03 at 07:18:47, rmsgrey wrote:
I agree, it's intuitive. Also, the N=3, 4 cases satisfy this. |
||||||
|
Title: Re: 3D Chessboard Full Control Post by visitor on Sep 29th, 2003, 6:26am 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. |
||||||
|
Title: Re: 3D Chessboard Full Control Post by visitor on Sep 29th, 2003, 6:28am 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. |
||||||
|
Title: Re: 3D Chessboard Full Control Post by visitor on Sep 30th, 2003, 6:45am 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. |
||||||
|
Title: Re: 3D Chessboard Full Control Post by Barukh on Sep 30th, 2003, 9:51am on 09/30/03 at 06:45:30, visitor wrote:
That's OK. I managed to reconstruct the right configuration. It's so simple... I was thinking in a completely different direction. on 09/30/03 at 06:45:30, visitor wrote:
There are some hints that your solution for K=3 is optimal. However, the proof is still missing. on 09/30/03 at 06:45:30, visitor wrote:
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! |
||||||
|
Title: Re: 3D Chessboard Full Control Post by Icarus on Sep 30th, 2003, 7:18pm 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 (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_suggestions;action=display;num=1064851265) :P (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. |
||||||
|
Title: Re: 3D Chessboard Full Control Post by Perfection on Nov 22nd, 2003, 10:45pm 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? |
||||||
|
Title: Re: 3D Chessboard Full Control Post by rmsgrey on Nov 23rd, 2003, 12:04am 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. |
||||||
|
Title: Re: 3D Chessboard Full Control Post by godskook on Feb 17th, 2004, 7:58am 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. |
||||||
|
Title: Re: 3D Chessboard Full Control Post by Barukh on Feb 19th, 2004, 12:34am 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. |
||||||
|
Title: Re: 3D Chessboard Full Control Post by towr on Feb 19th, 2004, 1:03am 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) |
||||||
|
Title: Re: 3D Chessboard Full Control Post by Barukh on Feb 19th, 2004, 4:00am 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). |
||||||
|
Title: Re: 3D Chessboard Full Control Post by THUDandBLUNDER on Feb 19th, 2004, 4:41am on 02/19/04 at 04:00:27, Barukh wrote:
on 02/17/04 at 07:58:07, godskook wrote:
|
||||||
|
Title: Re: 3D Chessboard Full Control Post by godskook on Feb 19th, 2004, 8:41am 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 |
||||||
|
Title: Re: 3D Chessboard Full Control Post by Guest on Feb 19th, 2004, 9:26am 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) |
||||||
|
Title: Re: 3D Chessboard Full Control Post by godskook on Feb 22nd, 2004, 3:20pm You're right ;D I missed those. thats what I get for thinking I could generalize |
||||||
|
Title: Re: 3D Chessboard Full Control Post by Leonid Broukhis on Apr 27th, 2004, 12:10am 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. |
||||||
|
Title: Re: 3D Chessboard Full Control Post by grimbal on Apr 28th, 2004, 1:55pm 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. |
||||||
|
Title: Re: 3D Chessboard Full Control Post by Leonid Broukhis on Apr 28th, 2004, 3:09pm on 04/28/04 at 13:55:18, grimbal wrote:
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. |
||||||
|
Title: Re: 3D Chessboard Full Control Post by Patashu on Sep 2nd, 2004, 4:18am 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) |
||||||
|
Title: Re: 3D Chessboard Full Control Post by Ace_T on Mar 6th, 2005, 8:02pm on 02/19/04 at 08:41:47, godskook wrote:
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_hard;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) |
||||||
|
Title: Re: 3D Chessboard Full Control Post by Barukh on Mar 7th, 2005, 6:27am Thanks, Ace_T, for contributing this. Am I right that the proof that this solution is optimal is still missing? |
||||||
|
Title: Re: 3D Chessboard Full Control Post by Ace_T on Mar 7th, 2005, 5:07pm 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! |
||||||
|
Title: Re: 3D Chessboard Full Control Post by Ace_T on Mar 8th, 2005, 8:23pm 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) |
||||||
|
Title: Re: 3D Chessboard Full Control Post by YADDA on Mar 26th, 2005, 7:09am 2x2x2:[hide]2[/hide] 3x3x3[hide]3[/hide] nxnxn:[hide]n[/hide] |
||||||
|
Title: Re: 3D Chessboard Full Control Post by Barukh on Mar 26th, 2005, 8:14am on 03/26/05 at 07:09:32, 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? |
||||||
|
Title: Re: 3D Chessboard Full Control Post by Icarus on Mar 26th, 2005, 8:25am 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. |
||||||
|
Title: Re: 3D Chessboard Full Control Post by towr on Mar 26th, 2005, 1:37pm 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.. |
||||||
|
Title: Re: 3D Chessboard Full Control Post by Icarus on Mar 26th, 2005, 8:15pm 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. |
||||||
|
Title: Re: 3D Chessboard Full Control Post by Deedlit on Mar 29th, 2005, 11:51pm 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)... |
||||||
|
Title: Re: 3D Chessboard Full Control Post by Joe on Jul 11th, 2005, 8:11am 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. |
||||||
|
Title: Re: 3D Chessboard Full Control Post by drifting on Apr 5th, 2007, 11:59am 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) |
||||||
|
Title: Re: 3D Chessboard Full Control Post by chetangarg on Apr 25th, 2007, 11:05am Proof of Optimal solution For the 3D chessboard Here is the attached file. |
||||||
|
Title: Re: 3D Chessboard Full Control Post by tiber13 on Apr 25th, 2007, 12:32pm on 09/26/03 at 09:05:53, visitor wrote:
I didnt know the forth demension existed ??? :o could someone explain it, i just cant imagine it :o |
||||||
|
Title: Re: 3D Chessboard Full Control Post by towr on Apr 25th, 2007, 12:52pm on 04/25/07 at 12:32:28, tiber13 wrote:
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. |
||||||
|
Title: Re: 3D Chessboard Full Control Post by Icarus on Apr 25th, 2007, 7:30pm 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). |
||||||
|
Title: Re: 3D Chessboard Full Control Post by Barukh on Apr 26th, 2007, 2:28am on 04/25/07 at 11:05:13, chetangarg wrote:
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... " |
||||||
|
Title: Re: 3D Chessboard Full Control Post by chetangarg on Apr 26th, 2007, 5:48am @ 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. |
||||||
|
Title: Re: 3D Chessboard Full Control Post by Sir_Rogers on Jun 19th, 2007, 1:37am 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. |
||||||
|
Title: Re: 3D Chessboard Full Control Post by Grimbal on Jun 19th, 2007, 4:45am If I take your solution for 6x6x6, I get:
which is equivalent, if you group together the outer sides, to with 8 o's and 16 x's But balancing the o's and the x's better, you can do
with 18 rooks altogether. I think that is the best solution known so far. |
||||||
|
Title: Re: 3D Chessboard Full Control Post by tiber13 on Jul 8th, 2007, 7:11am 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. :D |
||||||
|
Title: Re: 3D Chessboard Full Control Post by Hippo on Mar 9th, 2016, 10:33am on 04/26/07 at 05:48:04, chetangarg wrote:
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). |
||||||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |