Very Odd Rooks

Probability Level 5

Originally, every square of a $8\times8$ chessboard contains a rook. A rook attacks another rook if they are on the same row or column and there are no other rooks between them. You may remove a rook (one at a time) if it currently attacks an odd number of rooks.

Find the maximal number of rooks that can be removed.

The answer is 59.

2 solutions

Zk Lin
Feb 3, 2014

We claim that we can remove at most 59 rooks from the chessboard. First, we note that every rook at the four corners of the chessboard always attack 2 rooks no matter how many rooks we remove. For a corner rook to attack only one rook, another corner rook has to be removed, which is impossible in the first place. Next, note that we cannot leave behind only four corner rooks, because the last rook we remove from the chessboard will either attack no rook or the two corner rooks, which is an even number of rooks. Now, it remains for us to find a configuration where 59 rooks can be removed. There are many possible configurations, one of which include the following:

Key:

XX-corner rook

*- Rook left behind

(The number denotes the order the rooks are removed)

XX 01 02 03 04 05 06 XX

13 50 51 52 53 54 55 07

14 15 16 17 18 19 56 08

20 21 22 23 24 25 57 09

26 27 28 29 30 31 58 10

32 33 34 35 36 37 59 11

38 39 40 41 42 43 ** 12

XX 44 45 46 47 48 49 XX

Problem credit: International Mathematics Tournament of the Towns 2005 Senior A-Levels, problem 3

You should have clearly mentioned that the process of rook removal entails picking them off one by one. I assumed that all the pieces to be removed should be removed simultaneously (i.e at one go). Under my assumption a rook placed on every diagonal square will attack exactly 2 other rooks, and that is the maximum you can go. That will involve removal of 48 rooks

Kabir Chakravarti - 7 years, 3 months ago

I too noticed that the problem never explicitly says that only one rook is to be removed at a time. If rooks can be removed simultaneously, then it is very easy to show that the answer would be 60 (or, as you say, if they must be removed simultaneously, then that's another story) but I guessed that one-at-a-time was the intention of the problem-posed, since that's the only way that it poses a real challenge.

Peter Byers - 7 years, 3 months ago

Well said, Zk Lin.

As you said, there are many possible configurations. Mine's like this:

XX 01 02 03 04 05 54 XX

43 06 07 08 09 10 55 49

44 11 12 13 14 15 56 50

45 16 17 18 19 20 57 51

46 21 22 23 24 25 58 52

47 26 27 28 29 30 59 53

36 37 38 39 40 41 ** 42

XX 31 32 33 34 35 48 XX

Peter Byers - 7 years, 4 months ago

I was doing the same thing. But, i thought of something in between. As, you mentioned the key point, the corner rooks cannot be removed.

If at any point of time, we let the remaining rooks to form a square or a rectangle (barring the a1, a8, h1 and h8 rooks, of course), there will be 4 other rooks left out, which will reduce the no. of rooks removed.

so, there definitely are multiple solutions for this puzzle.

And, as you said, 1 rook at the end can never be removed.

Effectively "1 rook" is virtually a square in itself ;)

Hence, there will be 4 corner rooks and 1 last rook left. So, multiple ways of removing 59 rooks.

Soumya Chakraborty - 7 years, 3 months ago

The agument you gave proved that in the end there had to be atleast 5 rooks, it did not prove, "exactly 5 rooks". So to prove that atleast one configuration with 5 rooks left in the end along with the order of removal had to be shown.

You did give 1 such configuration. How did you find the order in which the rooks had to be removed? Did you write a program for it or you did you manually find it out some methodology( it seems hard to find it by hit and trial)

If you did not use a computer program and did not find it using hit and trial, I am curious about what method you used to find the order in which rooks are removed.

I had to write a program for that :)

Rampal Chaudhary - 7 years, 3 months ago

Hi Rampal. Have you looked at the removal-order I gave? I think it's pretty easy to follow.

Peter Byers - 7 years, 3 months ago

I did not solve this problem (I was off by 2). I think this problem should be categorized under computer science, since it is not about calculating the number of ways, but finding the procedural strategy for optimization.

Steven Zheng - 6 years, 11 months ago

i think this is not the problem of mathematics section

ojas dhiman - 6 years ago

Kristian Vasilev
Dec 5, 2014

I saw that in the end there are at least 5 rooks, and then I tried to fill in the chessboard to the position of the beginning and I did it .So the answer is 64-5=59

Very Odd Rooks

The answer is 59.

2 solutions

0 pending reports