Seems like it might be related somehow to golomb and jewett's proof that there is no fault free tiling of a 6x6 square by dominos, or at least use a similar argument? Thane Plambeck 650 321 4884 office 650 323 4928 fax http://www.qxmail.com/home.htm ----- Original Message ----- From: "ed pegg" <ed@mathpuzzle.com> To: <math-fun@mailman.xmission.com> Sent: Tuesday, November 19, 2002 9:07 AM 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.
As a follow-up, it is possible to cover an 8x8 board with 28 dominoes and 8 non-attacking rooks. Suppose one row has 1,5,5,4,R,1,4,4. The Union of that row would be 1,4,5,R. We can consider just 1,4,5, since every row and column has one rook. So, this row has a Union size of 3 -- there are 3 distinct numbers on that row. I wondered what the smallest possible average Union Size would be for double-6 dominoes on an 8x8 board. I tried to look at a simpler problem with the double-4 dominoes on a 6x6 board, and rant into the problem above.
--Ed Pegg Jr, www.mathpuzzle.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun