2
$\begingroup$

Given an $n\times n\times n$ cube, each of the six faces is divided into $n^2$ squares. So there are $6n^2$ squares in total. A rook placed on a square can attack any square, including squares on the other faces, that can be reached vertically or horizontally from its square. In particular, any rook can choose one of the two directions "vertical" or "horizontal", and walk in that direction across other faces until it comes back, spanning a total of $4n$ squares in each direction. What is the maximum number of non-attacking rooks that can be placed?

We can place $n$ rooks on the diagonal of one face -- this already leaves no square unattacked. Unlike the $2$-dimensional case, however, it is unclear if this is the best we can do.

$\endgroup$
  • 1
    $\begingroup$ i don't understand which squares can be attacked by a rook? Is the number of squares $3n-2$ ? $\endgroup$ – Jorge Fernández Hidalgo Aug 27 '16 at 15:41
  • $\begingroup$ would this definition be correct? a rook in position $(a,b,c)$ can attack square $(x,y,z)$ if and only if it shares two coordinates? $\endgroup$ – Jorge Fernández Hidalgo Aug 27 '16 at 15:42
  • $\begingroup$ oh nvm, I think the correct definition is as follows. a rook in position $(a,b,c)$ attacks $(x,y,z)$ if and only if $a=x$ or $b=y$ and $c=z$ $\endgroup$ – Jorge Fernández Hidalgo Aug 27 '16 at 15:44
  • 1
    $\begingroup$ I think the question should give more formal detail which squares are attacked by a rook. I cannot understand it as stated. $\endgroup$ – a3nm Aug 27 '16 at 15:47
1
$\begingroup$

The maximum number of rooks that can be placed is $\left\lfloor \frac{3n}{2} \right\rfloor$.

First, we can prove that you can't do better than $\left\lfloor \frac{3n}{2} \right\rfloor$. Consider "rings" in three directions as described by u8y7541, (each ring contains $4n$ squares). Then there are $3n$ rings, and each rook covers two rings; no other rook may be placed on those rings. So if there are $r$ rooks, then $$2r \text{ (number of rings covered)} \le 3n\text{ (number of rings total)}$$ so $r \le \frac{3n}{2}$. Sine $r$ is an integer, $r \le \left\lfloor \frac{3n}{2} \right\rfloor$.

Now to achieve $r = \left\lfloor \frac{3n}{2} \right\rfloor$, just pick $r$ pairs of rings, such that no pair consists of two parallel (i.e. non-intersecting) rings. Convince yourself that it's always possible to pick the maximum number of pairs of non-parallel rings. Now place a rook at one of the two intersections of each pair, and we have a valid arrangement.

$\endgroup$
1
$\begingroup$

Imagine the cube is made of square-shaped rings. The rings go $3$ ways. When a rook is placed on a square, it rules one ring one way and another ring the other way. This means every rook rules two rings. To find the amount of rooks you can place, all you have to do is find how much rings there are and divide by $2$.

There will be $n$ rings going in three directions, up, horizontal and sideways to cover the whole square with rings (This is hard to describe with words, see image). This means $\frac{3n}{2} = 1.5n$, meaning that the diagonal is not the best you can do.

Here's an image of the cube covered in rings in one direction to help you visualize it. You can tell that if you put rings the other way the cube will be covered.

Edit:

Thanks to @6005 for correcting me. I realized that the rings go in 3 ways instead of 2.

$\endgroup$
  • 1
    $\begingroup$ I don't think this quite settles it. In particular, there are rings going in three directions, not just two. What do you do about a rook that doesn't rule out two of the rings? You either have to count $3n$ rings instead of $2n$, or handle that case. $\endgroup$ – 6005 Aug 27 '16 at 15:42
  • $\begingroup$ @6005 Ah yes, there are 3 ring directions. I'm sorry. However, I don't see a case where the rook will not rule out two rings. $\endgroup$ – u8y7541 Aug 27 '16 at 15:44
  • $\begingroup$ Well, $n$ is not the best you can do. So there are cases. Just imagine the rook is not in one of the two ring directions you counted. $\endgroup$ – 6005 Aug 27 '16 at 15:47
  • $\begingroup$ @6005 I have edited the problem. Now there are 3 directions. I do believe that there is a way to get 1.5n on the cube. $\endgroup$ – u8y7541 Aug 27 '16 at 15:49
  • $\begingroup$ @6005 I don't have enough rep so I can't comment on your answer, but I can say that whenever 2r is smaller than 3n is when 1.5n is not an integer. $\endgroup$ – u8y7541 Aug 27 '16 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.