[math-fun] Puzzle about coloring chess boards
The following puzzle had been knocking around work (actually it was first given in our place in 1994): Given an n x n chessboard we wish to color the squares black and white with the property that for any subsquare (of size at least 2x2) the four corner squares are not all the same color. These are orthogonal squares (and not tilted ones). The original poser of the puzzle gave a number of 5x5 examples, and asked to either prove that it can be done for all n, or to show that it can't be done for some (and therefore all bigger) n0. I coded up this problem as a satisfiability problem and found a solution for 14x14, but, after 1 1/2 hours of computation the SAT solver (SatEliteGTI) reported that 15x15 is unsatisfiable. Has anyone else seen this puzzle? It would be much more satisfying if there were a proof that 15x15 was impossible by hand. Victor
Hello math-fun, Could someone explain me this sequence, designed by a friend of mine? He says it has to do with first differences... S = one, nine, nine, five, five, nine, nine, five, five, nine, one, three, thirteen, seventeen, one, three, thirteen, seventeen, nine, five, five, nine, nine, five, five, nine, one, three, thirteen, seventeen, one, three, thirteen, seventeen,... Best, E.
S = one, nine, nine, five, five, nine, nine, five, five, nine, one, three, thirteen, seventeen, one, three, thirteen, seventeen, nine, five, five, nine, nine, five, five, nine, one, three, thirteen, seventeen, one, three, thirteen, seventeen,... . . . Ok, answer is... . . . O N E N I N E N I N E F I V E F I V E 1 9 9 5 5 9 9 5 5 9 1 3 13 17 1 3 13 17 --> first (letters rank) diff. is seq. itself
Best, E.
I'm sure I've seen 17x17 solutions to this problem. ----- Original Message ----- From: "Victor S. Miller" <victor@idaccr.org> To: <math-fun@mailman.xmission.com> Sent: Tuesday, September 18, 2007 8:55 PM Subject: [math-fun] Puzzle about coloring chess boards
The following puzzle had been knocking around work (actually it was first given in our place in 1994):
Given an n x n chessboard we wish to color the squares black and white with the property that for any subsquare (of size at least 2x2) the four corner squares are not all the same color. These are orthogonal squares (and not tilted ones). The original poser of the puzzle gave a number of 5x5 examples, and asked to either prove that it can be done for all n, or to show that it can't be done for some (and therefore all bigger) n0. I coded up this problem as a satisfiability problem and found a solution for 14x14, but, after 1 1/2 hours of computation the SAT solver (SatEliteGTI) reported that 15x15 is unsatisfiable. Has anyone else seen this puzzle? It would be much more satisfying if there were a proof that 15x15 was impossible by hand.
Victor
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- No virus found in this incoming message. Checked by AVG Free Edition. Version: 7.5.487 / Virus Database: 269.13.21/1012 - Release Date: 9/16/2007 6:32 PM
Up to 9x9 it's nice that you can do it with the first row all one color (view this in fixed-width font): ......... .X.X.X.X. ..XX..XX. X...XXX.. .X.XX.X.X XX....XXX X.X.XX.X. X.XX....X .XX..XX.X So even my stupid computer program can solve it essentially immediately. Starting with 10x10, the lexicographically first solution is no longer with a monochromatic first row: .........X .X.X.X.X.. .XX..XX..X ..XXX...X. .XX.XX.X.X X.X...XXX. .X.XX.X.X. X..X.X..X. XXX....X.. ....XXXXX. In general, it seems up to 9x9 there's a very large proportion of squares that work, and 10x10 it starts to go down, and by 11x11 there's a very small proportion of squares that work. Rather than looking for lexicographically first, I had it look more at random (but keeping track of the tree, just ordering randomly, so it is sure to check all possibilities in looking for a solution) and in about a minute it found OOOXOOOXOXX XOXOOXOXXOX OOXOXXOOXOX OXOOOXXOXOO XXXXOOOOXXO XOOXXOXOOXX XXOOOOXXXXO OXOXXOOXOOO XXXOOXOOOXX OOXOXXOXXXO XXOOOXXXOXX for the 11 by 11 case. (by contrast, finding the lexicographically first 10x10 took it 3 minutes). I'll run it on 15x15 and see if it finds a solution or not ... and meanwhile look for a proof by hand as well. --Joshua Zucker
participants (4)
-
David Wilson -
Eric Angelini -
Joshua Zucker -
victor＠idaccr.org