-----Original Message----- From: ed pegg [mailto:ed@mathpuzzle.com] Sent: Tuesday, November 19, 2002 12:07 PM To: math-fun@mailman.xmission.com Subject: [math-fun] Dominos and non-attacking rooks.
Can a 6x6 board be covered with 15 dominoes and 6 non-attacking rooks?
I have a nice little proof that it can't be, but I'm wondering if it is a new problem.
Here's my proof: I'm curious if it is the same as yours. Define a function f by f(n) = rank of the rook in file n. None of the rooks attack each other, so f is a permutation on S = {1,2,3,4,5,6}. So the number of elements of f that map an even element of S to an odd element is equal to the number that map an odd element to an even one. So the total number of elements of S that are mapped to an element of opposite parity by f is even. But this is just the number of rooks on white squares, which must be odd, since the number of rooks on white and black squares must be equal (since each domino covers a white and a black square). This proof works for any square chessboard of size 4k+2. Is this the same as your proof? No idea whether it's a new problem. But it's a nice one.