1
$\begingroup$

I remember a long time ago during my university entrance interview I was asked a deceptively simple combinatorics (or what I believe to be combinatorics) question. Imagine you had a rectangle of size 5 x 3, let's say cm, and it was split up into centimetre squares. Imagine you also had a domino two squares long. Is it possible to fill all the squares in the rectangle with dominoes, assuming they couldn't overlap? Clearly, the answer is no.

Could you do it with a 6 x 6 square? Yes, you could. Now, what if you were to remove two opposite corners of the square... would it change anything?

I am convinced it is then impossible to fill up the square with dominoes, but how does one prove it? I couldn't prove this in the interview and I still can't to this day (although admittedly, I've never studied a course in combinatorics).

$\endgroup$
  • 2
    $\begingroup$ This is a classic. No need to study combinatorics, though. $\endgroup$ – leonbloy Aug 31 '11 at 0:06
3
$\begingroup$

Color the squares alternately black and white, as on a chess board. Now, each domino covers equally many white and black squares ...

$\endgroup$
  • $\begingroup$ ... and the two removed corners are coloured ... $\endgroup$ – Henry Aug 31 '11 at 0:05
  • $\begingroup$ Very nice, and somewhat simpler than I expected! $\endgroup$ – Sputnik Aug 31 '11 at 0:14

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.