Total Pageviews

Saturday, March 12, 2011

Some basic combinatorics

Pigeonhole principle is known in mathematics as a theorem that states: if n items are put in a m pigeonholes and n > m, then at least two items must be in the same pigeonhole. It sounds quite a simple and it is, but still it can solve some seemingly more complex problems.

Let's think about the following problem; how many rooks can be placed in a chess board so that none of the rooks threatens another?

Quite a quickly it becomes obvious that because only one rook can be placed on the same row or column, the maximum number of the rooks will be equivalent with the number of squares on the diagonal (see the picture).


 
So now we have been able to place eight rooks on the board, but how do we prove that the ninth one cna't be placed there? Well as you probably guessed already, with pigeonhole principle. The right board is split in eight boxes (pigeonholes) and it becames quite obvious that it's impossible to add a rook in anywhere on the board withouth being placed in a box which already contains a rook (so it will threathen).


What about kings?

Well it's quite easy to start looking for the maximum set up by placing the first king in some corner, and then adding the next king not in the next but following square. That is the closest place so that the kings don't threaten one another. We can fit four kings on the same row this way, next row none and four again to the next row etc.


When proving that the 17th king can't be placed, we proceed the same way as before, the board is just divided in the pigeonholes little different.

Knights.

I think this is already a little more complex problem. I'm not sure if this one can be solved as the king problem. At least it's not that clear that if we place the first knight in some corner, will the nearest square be the best place for the next one? Actually the answer is no (or is it?). Let's first look at the movement of the knight (picture on the left).  The key is to notice that if the knight is placed on the white square, it threatens only places on the board that are black. Now it's not very hard to realise that we can place knights on every white (or black) square on the board without any threat.



The boxing in this case is little different. It can't be done by placing only one knight to a box but four. It's quite easy to se this way, that five knights can't be placed in the same box without conflict.

4 comments:

  1. You will make a fine chess player my friend.

    ReplyDelete
  2. actually took my time and thought about these problems

    ReplyDelete
  3. I love the pidgeon hole principle. My discrete math class taught me this. Keep up the math, i look forward to what you post. Followed.

    ReplyDelete
  4. Wow i had to read it 4 times to understand!!

    ReplyDelete