Lege-Wege: A Domino Puzzle Torsten Sillke, Bielefeld ========================== August 1993 The puzzle consits of all black/white colorings of the sements (a,b,c,d,e,f,g) such that at each crossing point there is an even number of black segments. ----------- | f e | |-a-+-g-+-d-| | b c | ----------- There are 2^7 combinations without the even condition. The even condition at each crossing point reduce the number of possibilities by a factor two. So there are 2^5 = 32 combinations if you fix the domino. The number of pointsymmetric configurations is 2^3 = 8, as a=d, b=e, c=f and the even crossing point condition. The number of really different tiles (rotations allowed) is therefor (32 + 8)/2 = 20. The number of endpoints (a,b,c,d,e,f) colored black is even. This is a consequence of the fact, that in each graph is the number of vertices with odd degree even. # black segments at the boundary: 0 2 4 6 # Dominoes: 1 9 9 1 The symmetry in the table is clear, as a bijection given by the color exchange (black <-> white). Table of Dominoes: ------------------ 0-path domino 3-path domino ----------- ----------- | : : | | | | | |...+...+...| |---+---+---| | : : | | | | | ----------- ----------- 1-path dominoes 2-path dominoes ----------- ----------- ----------- ----------- | : : | | : : | | | | | | | | | |...+...+---| |---+...+...| |---+---+...| |...+---+---| | : | | | | : | | | : | | : | | ----------- ----------- ----------- ----------- ----------- ----------- | | : | | : | | |...+...+...| |---+---+---| | | : | | : | | ----------- ----------- ----------- ----------- ----------- ----------- | : : | | : : | | | | | | | | | |...+---+---| |---+---+...| |---+...+...| |...+...+---| | | : | | : | | | : | | | | : | ----------- ----------- ----------- ----------- ----------- ----------- | : : | | | | | |---+---+---| |...+...+...| | : : | | | | | ----------- ----------- ----------- ----------- ----------- ----------- | : | | | | : | | | : | | : | | |...+---+...| |...+---+...| |---+...+---| |---+...+---| | | : | | : | | | : | | | | : | ----------- ----------- ----------- ----------- ----------- ----------- | : : | | | | | |...+---+...| |---+...+---| | | | | | : : | ----------- ----------- Some Puzzles: 1) Build a 3*6 rectangle with the 9 one-path dominoes. The black segments should build a single line. 2) Build a 4*4 square with 8 of the 9 one-path dominoes. The black segments should build a single line. This gives six problems, as you can try to leave each of the 9 dominoes out. One problem is not solvable, but you can manage to connect only two segments to the boundary. 3) Tile k of the 9 one-path dominoes in such a way, that the black segments form a circuit. It is possible to build circuit with k=3..8 dominoes. Find the easy proof, that no circuit can be build with all 9 dominoes. Try to build circuit with different length and different enclosed area. Which combinations (# dominoes, length, area) are possible? One segment is one unit-length. This exercise gives you a hint, why the 9 domino circuit is impossible. 4) Tile a 4*4 square with 8 of all 20 dominoes. No black segment should touch the boundary. Which patterns for the black segments can be build. There are only 10 different pattern, if the zero-path tile is not used. 29 are possible, if it can be used too. If you tile the 4*4 square with fewer than 8 dominoes, - so you get holes - which pattern can you creat? 5) Tile the 6*6 square with the 18 one-path and two-path dominoes. The black segments should build a single line. At which places can the endpoints be placed? Peter Seroka found the first solution by hand. I have drawn the line of black segments he found. How many tilings give this line? 6) Tile the 6*6 square with the 18 one-path and two-path dominoes. No black segment should touch the boundary. This puzzle is impossible, which confirmed Udo Sprute's general puzzle solver 'arrange'. Is there a short proof? 7) Tile the 6*6 square with the 18 of the 20 dominoes. No black segment should touch the boundary. Which combinations are possible? 8) Build a circuit with all 18 one-path and two-path dominoes. (plus the zero-path dominoe marked '- -'.) . x x x x x . . . x . . . . x x x x x . . x x x x x x x x x x x x x x x x x x x x . x x x x x x x x x x x x x x x x x x x x x x x x x x x - x x x x x x x x x x x x x x x x x x x x - x x x x x x x x x x x x x . . x x x x x . x x x x x x x x x x x x . . 9) Tile a 5*8 rectangle with all 20 dominoes. You should build one circuit. There are two solutions. 10) Tile a 4*10 rectangle with all 20 dominoes. A circuit is not possible but a path can be build. The path may end at a short edge of the rectangle. references: - Wer weiss wohin?, Ein Spiel der Sammlung 'Grips + Co' von Triangle Team, 1993. - Anaconda, Heye 1989 <- Wenn Knollennasenmaennchen spielen, spielbox 92:3, 34-36, K-M. Wolf - Irgendwie, Pyramo, 1990?, Dieter Matthes & Silvia Heinz <- spielbox Denkspiele, spielbox 92:1, 32 - ... lege Spiele!, K. H. Koch, dumont TB 192, 1987 - Klassifikation der Legespiele, fachdienst spiel 5/92 Redaktion: Deutsches Spiele-Archiv, Ketzerbach 21 1/2, Marburg