4
$\begingroup$

What is the number of ways in which one can choose 60 unit squares from a $11\times 11$ Chessboard such that no two chosen squares have a side common?

My working: I coloured the chess board alternatively with black and white. There will be 61 non adjacent unit squares of one colour and 60 non adjacent of other colour. Now if we choose all 60 squares of same colour they will be definitely non adjacent. There are ${{61}\choose {60}}+{60\choose 60}=62$ ways.

Is there any other way, I mean how to prove some white and some black squares will force us to take adjacent squares at some places.

$\endgroup$
  • $\begingroup$ You have to deal with some squares on the board being on the edge or in the corner, in which case it has fewer neighbors. $\endgroup$ – 4-ier Aug 23 '18 at 6:33
1
$\begingroup$

Let us coloure the chess board alternatively with black and white with corner squares black.

There will be 61 non adjacent unit squares of black colour and 60 non adjacent of white colour.

We can’t choose black and white squares together as Whenever we choose a black square at least two adjacent white squares we can’t select! Say we select $k$ black square then at least $k+1$ adjacent white squares we can’t select implies we left with at most $59-k$ white squares but we need $60-k$ white square which is clearly not possible.

Hence in order to choose 60 non adjacent squares all 60 squares must be of same colour. There are ${{61}\choose {60}}+{60\choose 60}=62$ ways.

$\endgroup$

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.