(not so) Brute Force! Worked out the first six by hand and then fitted a quadratic.

Sounds like a truly heroic effort, well done! In fact, I believe, in this particular problem coming up with a right conjecture for the answer is the hardest part of the solution.So now it would be nice to prove that the bound is indeed optimal. Any ideas how to go about it?

I wonder, does anyone care about a solution to this problem? In an attempt to jumpstart the discussion, here is a possible configuration for n=3 (we already know that the answer is 5): Again, we view the cube as n layers above an n x n board and the number (1 through n) in a cell is the number of the rook's layer above this cell.

For a cube kxkxk it's easy to put rooks in a way that each row (in all 3 direction) contains 1 rook). Exemple : coordinates i,j,(i-j) mod k for every i,jThan for the cube (k1+k2)x(k1+k2)x(k1+k2) we can put rooks satisfying initial requirements. (Placing in smaller cubes of sizes k1xk1xk1 and k2xk2xk2)This gives us an exemple of solution configuration. (k1=k2 for pair n, k1=k2+1 for odd n)

Yes, that sounds right. It would look something like this:n=4n=5Now the only thing left is to prove that this is indeed the optimal solution.

Move all the rooks o the bottom layer along the vertical (Using sevvost pictures it means that there will be a rook in each square where there is a number). Probably there will be more than 1 rook in certain squares.Let's denote the number of rooks in rows and number of rooks in columns. We can always assume . In the row with rooks there is at least empty squares. In each colunm containing one of this empty squares there should be at least rooks (if it is not the case, this empty square is beaten by less than n rooks it means that one cell is not controled in the initial cube). Now let's count the rooks in all rows. There is at least columns with rooks and in other columns there is rooks. In total we have rooks

Yes, that is exactly right, well done! Another way to put it: the desired result immediately follows from theLemma. An n x n matrix all of whose elements are non-negative integers, satisfies the condition: if any is zero, then the sum of the elements in the ith row and the jth column is . Prove that the sum of all the matrix elements (and hence, for odd n, ).Curiously, this lemma is a worthwhile problem in its own right. At least, the IMO 1971 organizers apparently thought so. Now, getting back to our rooks, any thoughts about taking this problem to higher dimensions?

Speaking of higher dimensions, the question in its most general form (determine - the minimum number of rooks controlling the k-dimensional board n x ... x n), to the best of my knowledge, is still open. The obvious bounds and can be immediately generalized to and , respectively. And given that and (or ), it seems natural to consider a conjecture .However, things are not that simple. The bound in all likelihood holds. I only know a proof of a weaker statement: if R is the number of rooks that control the whole k-dimensional board and do not attack each other, then . It is not very difficult, I can post it here if anyone is interested. The italicized condition, of course, leaves no doubt that we are in the error-correcting coding territory here.But it is clear that can not possibly be the best possible bound. For instance, if n=2, then and the trivial bound happens to be better for k>3 (tends to become almost twice as good for large k.)