0

On a chessboard with 8 × 8 squares a rook threatens all the chess pieces in the the same line or the same column in which it stands, regardless of whether another rook stands in between or not!!

How many rooks can be placed on the chessboard maximally so that each tower threatens at most two more rooks?

The solution is 16 pieces I guess, I tried it with a real chess board, I do just not know how to prove this mathematically.

Maybe any ideas how I can transfer this into the mathematical language? I thought of like 8x8 dots of numbers like (1;1) up to (8;8) but i do not know how to go on

calculatormathematical
  • 2,222

2 Answers2

3

In this problem we ignore the rules of chess and say that two rooks "attack" each other if they are in the same row or the same column, regardless of whether the intervening squares are occupied.

Suppose you had more than $16$ rooks. Then you would have to have $3$ rooks on some row; without loss of generality (since nothing is affected if you swap rows or swap columns) you have rooks at squares a1, b1, and c1. Likewise, you must have $3$ rooks on some column; say you have rooks on d2, d3, d4. Then you must have $11$ more rooks, and they have to be placed on the $4\times4$ chessboard in the upper right corner.

So now you've got $11$ rooks on a $4\times4$ board. So you've got $3$ rooks on one row (otherwise you couldn't have more than $8$ rooks). s those $3$ rooks can't be attacking any additional rooks, that leaves only $3$ squares for the rest of the rooks. But then you've got only $6$ rooks on the board, a contradiction.

More generally, for $n\ge1,$ the maximum number of rooks you can put on an $n\times n$ chessboard with no rook attacking more than $2$ other rooks is $2n.$ This is easily proved by induction.

bof
  • 78,265
0

I have done some further thinking: If we say that one rook is allowed to threaten at the most ONE more rook, then only one rook can stay in 1 column. There are 8 columns so the solution ist 8.

Now we have that the rooks are threatening at the most 2 rooks. So 2*8 =16.

A formula would be for rooks: Amount of other rooks one is able to attack * amount of rows or columns, if its a YxX board for Y ∈ ℕ (without 0) = amount of possible rooks on the board.

And, that is important, n has to be an even number

Am I right or totally wrong?

calculatormathematical
  • 2,222
  • 1
    I should work out what happens with a $3\times 3$ board to get a feel for what is going on here, then go on to $5\times 5$ – Mark Bennet Sep 10 '18 at 16:22
  • No you have to multiply the n of n×n with the amount of attackable rooks. In this case, at the most two rooks are attackable. With 3×3 it would be $3*2=6$ – calculatormathematical Sep 10 '18 at 17:26
  • With 3 other to attack at the most 9 would be definitively right!!! True answer – calculatormathematical Sep 10 '18 at 17:27
  • I guess then, that the amount of attackable rooks has to be smaller than n (n×n) – calculatormathematical Sep 11 '18 at 05:11
  • But on a 3×3 chessboard you can place at the most 5 rooks – calculatormathematical Sep 11 '18 at 05:12
  • Actually you can put $10$ rooks on an $8\times8$ board so that each rook threatens only one other rook: put rooks on a1, b1, c2, c3, d4, e4, f5, f6, g7, h7. – bof Sep 13 '18 at 11:20
  • More than 16 is not possible on an 8×8 chessboard – calculatormathematical Sep 13 '18 at 13:51
  • Yes, as I showed in my answer, $16$ is the maximum number of rooks possible on an $8\times8$ chessboard, if each rook threatens on most *TWO* other rooks. If each rook threatens at most *ONE* other rook, then the maximum possible number of rooks is $10$ on an $8\times8$ chessboard, and $\left\lfloor\frac{4n}3\right\rfloor$ on an $n\times n$ chessboard. – bof Sep 14 '18 at 04:02