<<
From my site, a few years ago ... At the dinner, I met Bernardo Recaman Santos of Columbia.
Just wondering -- is the Columbia University, or Colombia, the country? --Dan
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
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
Loren Larson would be a good person to ask. R217 in The Inquisitive Problem Solver shows that the 8 queens in the 8 Queens Problem must be 4 each on black & white squares, so that dominoes are not inhibited by coloring. The picture on page 265, for example, can be dominoed as follows: 1 1 2 Q 9 9 a a 3 3 2 c c e Q b 4 4 Q d d e f b 5 5 g g h h f Q 6 Q i i j j k k 6 8 l l Q n m m Q 8 s s u n o o 7 7 t t u Q p p R. On Tue, 19 Nov 2002, ed pegg wrote:
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
participants (4)
-
asimovd＠aol.com -
ed pegg -
Richard Guy -
Thane Plambeck