Dear Ed, Guess what? My second year class of 12-13 year olds really enjoyed tackling this problem. I started them off on the simpler 4x4 version which of course can be done so that they would be lulled into a false sense of security. The 6x6 cannot be done and a black/white colouring argument proves that it is impossible. Three rooks would have to be on black squares and three on white so that the empty squares have an equal number of black and white as a domino covers one black and one white square. Three rooks on black and three on white is an impossible arrangement so the puzzle cannot be done. Many thanks for providing a such nice Wednesday afternoon lesson! Cheers, Alastair Cuthbertson --------------------------------------------- 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. Andy Latto ---------------------------------------------- Ed, I think, it's impossible. Each domino covers 1 black and 1 white square. So, 3 rooks need to be placed on black squares and 3 - on white squres. ...Which is impossible. It's easy to see - if we place 3 rooks on black squares, the remaining 9 not-attacked squares include 4 white squares, 2 adjusted horizontally and 2 - vertically. Hence, we can't place all 3 remaining rooks on the white squares. Regards, Igor Krivokon ---------------------------------------------- It is impossible. Color the chessboard in the usual way. The 15 dominos will have to cover 15 squares of each color. Start with the rooks. When each rook is placed, cross out the squares in its column and row which have not already been crossed out. The distribution of colors in the row and in the column will always be the same. (eg., if we cross out three white squares and three black in the row of the rook, we will necessarily cross out three whit and three black in the column as well.) So after each rook, we cross out an even number of white squares and an even number of black squares. Each square which is to be covered by a domino will be crossed out exactly once, hence after placing the 6 non-attacking rooks we cannot have 15 white and 15 black squares remaining. This is the kind of thing I'd hoped there'd be more of in the Larson/Vaderlind/Guy book - they wrote on most puzzles "is it possible to do the following?", but it almost always was. David Molnar ---------------------------------------------- Ed -- Your puzzle about putting 15 dominoes and 6 non-attacking rooks on a 6x6 board is not hard -- it's impossible to do it. Here's the not-hard proof: Number the rows and columns of the board from 0 to 5. "White" squares have an *even* sum of row and column number, "Black" squares have an *odd* sum of row and column number. The board has 18 squares of each color. Each domino takes up one black square and one white square, so the rooks must occupy the remaining three white squares and three black squares. But since the rooks are non-attacking, there must be one in each row, and also one in each column. The total sum of row and column numbers for the rooks must then be 2*(0+1+2+3+4+5) = 30, an even number. So six non-attacking rooks must occupy an even number of black squares. This contradicts the domino-imposed requirement that they occupy exactly three black squares, so the placement is impossible. (Solution inspired, of course, by the familiar puzzle about placing 31 dominoes on a chessboard with the corners removed...) -- Alex Ridgway ---------------------------------------------- Impossible. If you color the board checkboard fashion, the rooks always cover an even number of squares of each color. However, the dominoes must cover 15 squares of each color out of the total 18 squares of each color, so they need the rooks to go on 3 squares of each color which they can't do. To see that the rooks must always cover an even number of squares of each color, consider this: Starting with all 6 rooks on the main diagonal all arrangements of 6 non-attacking rooks can be derived from this pattern by a series of moves of this type: Take two rooks, and consider the orthogonal rectangle defined by these rooks on opposite corners. Move the rooks to the other two corners of the rectangle, keeping the non-attacking nature. This is easily seen by moving the rooks to the desired squares starting from the top down -- place a rook on the correct square on the first row, swapping some other rook lower on the board to its former column to maintain the non-attacking state, then repeat on the second row, etc. You never have to move an upper rook again because doing so would mean you had two rooks in the same column in your desired pattern. Each of these moves preserves an even number of rooks on each color. You started with all 6 on one color, and each moves that starts with two rooks on the same color changes both to the other color, while each moves that starts with one rook on each color ends with one rook on each color. Joseph DeVincentis ---------------------------------------------- Can one cover a 6x6 board with 15 dominoes and 6 non-attacking rooks? Nope. First, a little terminology. During this proof, we'll use a "fault line" to refer to a verticle or horizontal line running straight through the 6x6 grid between two grid rows or columns. There are five horizontal and five vertical fault lines. A fault line is broken if it is interrupted by a domino perpendicular to that line. If a domino lies horizontal as far left as possible in the grid, for instance, the first vertical fault line is broken. Otherwise, it is unbroken. An unbroken fault line can be seen by a straight line running from one side of the grid to the other. An odd fault line is broken by an odd number of dominoes, while an even fault line is broken by an even number. Let's examine the first (leftmost) vertical fault line. Can this line be unbroken? Of course not. There are 5 open squares to its left (1x6, minus 1 rook) and 25 to its right (5x6, minus 5 rooks). Since each domino covers two squares, and neither side of the fault line has an even number of squares, it is clear that at least one domino must cross this line. In fact, not only must this fault line be broken, it must be broken by an odd number of dominoes, and is thus an odd fault line. A similar analysis shows that vertical fault lines 3 and 5 are also odd, whereas vertical fault lines 2 and 4 are even. Furthermore, this analysis holds for the horizontal fault lines as well, giving a total of 6 odd fault lines and 4 even fault lines. This sums up to give an even number of fault line breaks. It is also easy to see that each domino breaks one and only one fault line. However, we have an odd number of dominoes that are to break an even number of fault lines. Impossible? You bet. -Jonah Ostroff ---------------------------------------------- Domino Problem No solution exists Proof: Each domino will cover 1 black square and 1 white square. There are 18 of each. Therefore 3 black squares and 3 white squares will be left. Label the points with coordinates from {1,2,3,4,5,6} in such a way that [1,1] is black. The white squares are those for which the sum of the coordinates is odd. Therefore of the 6 remaining squares, the total sum of coordinates is odd. Therefore either the sum of the x-coordinates is not 21 or the sum of the y-coordinates is not 21 (or both). Suppose without losing generality that the sum of the x-coordinates is not 21. 6 numbers from {1,2,3,4,5,6} that do not add to 21 must contain a repetition, meaning that if you place rooks on these 6 squares, at least one will attack another. L T Pebody ---------------------------------------------- > Cover a 6x6 board with 15 dominoes and 6 non-attacking rooks, or show > that it is impossible. It's impossible, by parity arguments. For simplicity, define a binary operation # by x#y = (x+y) mod 2. Then give the 6x6 square its usual coloring, where we'll call a cell (i,j) white if i#j = 0 and black if i#j = 1. As usual, every domino will cover exactly one white and one black square; since the board starts with an equal number of white and black squares, we have to position the rooks such that there are 3 on white squares and 3 on black squares. Define a permutation f such that the 6 rooks are placed on the squares (i, f(i)) for i in 1..6 (this is a permutation on 1..6 because there is exactly one rook per row and exactly one per column). Then the condition that there are three rooks on each color is equivalent to the condition that sum(i=1..6) {i#f(i)) = 3. Reduce both sides of this equation mod 2 and use the definition of x#y; then it becomes #(i=1..6) (i#f(i)) = 1 (where the leftmost # should be thought of as a summation operator for the # function). But # is commutative, so this is just [#(i=1..6) i] # [#(i=1..6) f(i)]; since f is a permutation, #(i=1..6) f(i) has to be the same as #(i=1..6) i (it's just a rearrangement of this 'sum'), and so the # of both of them is necessarily 0. It's thus impossible to place three rooks on black squares and three on white, and so impossible to place the dominoes. This argument doesn't work on 4nx4n boards, and in fact it's easy to see that the 4x4 board can be covered correctly: Raab ccRb dRee dffR using this covering and trivial coverings of a 4x4 empty square, we can cover any 4nx4n square. The same parity argument can be used to show that it's impossible to cover any (4n+3)x(4n+3) square with 4n+3 nonattacking rooks and the appropriate amount of dominoes, and the covering of the 5x5 square below (along with the 4x4 covering above and trivial coverings of 5x4 and 4x4 rectangles without any rooks) shows that any (4n+1)x(4n+1) square can be covered. Raabb cRdde cffRe ggRhh iijjR P.S. Here's a less mathematical version of this parity argument: it's clear that any rook arrangement can be gotten by starting with a trivial rook arrangement (where they're all along the white long diagonal) by a series of file swaps (choose two rooks and keep them on the same rows, but exchange their files) -- just swap the rook in file 1 with the one that's in row f(1), then swap the rook in file 2 with the one that's in row f(2), etc. Every one of these swaps either keeps the number of rooks on white squares the same, or increases or decreases it by 2; since we start with all six rooks on white squares, it's impossible to get three on white squares by doing these swaps. Steven Stadnicki ---------------------------------------------- 1) That "dominoes and rooks was good". It was improved "dominoes with deleted corners". There are a) 36 ways with 0-6 (whites and blacks) b) 324 ways with 2-4 c) 324 ways with 4-2 d) 36 ways with 6-0 ==================== So parity (there should be equal number of free whites and blacks solves it = NOT SOLVABLE. Juha Saukkola ---------------------------------------------- First one is no ,because Assume the board is, like chess board, consist of black and white squares. The 15 dominos will cover 15 white and 15 black squares. We have 3 black and 3 white squares remaining. These squares must contain the rooks. If we put the first rook in a black box. It will attack 6 white and 4 black squares. if we put the second rook in another black box, which is not attacked, It will attack 4 white and 4 black new squares. and if we put the third rook in a not-attacked black square, it will attack 2 black and 4 white new squares. We have a total of 14 attacked white and 10 attacked black squares. Also we put 3 rooks to black squares. So we have 4 free white and 5 free black squares. Now if we put a rook to white square it will attack one free white square. Now we have two free white squares which is in a strait line. So it is impossible to put the other two rooks. ( We can see better if we draw the board.) Abdullah Görkem Gençay ---------------------------------------------- This is impossible. Placing 15 dominoes on the board must leave 3 black and 3 white squares uncovered. Unfortunately, any solution to the 6-rook problem must have an even number of rooks on white squares ("even parity"). Proof: Call a "flip" the operation of taking 2 rooks, and interchanging their rows while keeping them in the same columns. Note that a flip transforms a valid solution into another valid solution, and that it does not change the parity of the solution. Now, assume we have a solution with odd parity. Flip the rook in column 1 with the rook in row 1. Now we have a solution with a rook in square (1,1). Continue down the main diagonal, flipping the rook in column n with the rook in row n. After 5 flips, we have rooks in squares (1,1), ... (5,5). The only place for the remaining rook would be square (6,6), otherwise the arrangement wouldn't be a valid solution. But this solution has all 6 rooks on the same color (6 white or 0 white), and therefore it has even parity. We conclude that the original solution could not have had odd parity, so there does not exist any solution with odd parity. Q.E.D. Mike Malak ---------------------------------------------- Ooh, a puzzle I can answer: 15 dominoes and 6 non-attacking rooks in a 6x6 square is impossible. Here's why: Let's start by numbering the board as follows: 121212 212121 121212 212121 121212 212121 Every domino placed on this board must cover exactly one 1 and exactly one 2. Therefore the six remaining squares the rooks are placed on must consist of three 1's and three 2's if the task is possible. Now consider the arrangement of six non-attacking rooks on the 6x6 board. This is a subtle way of saying each rook is in a different row and column. Here's a sample array for discussion: ....R. .R.... ...R.. .....R R..... ..R... Take the leftmost rook's row, and swap it with the top row, if necessary. R..... .R.... ...R.. .....R ....R. ..R... Repeat for the second leftmost rook's row, and the second row, and so on, until all rooks are on the same diagonal. R..... .R.... ..R... .....R ....R. ...R.. R..... .R.... ..R... ...R.. ....R. .....R This procedure will "sort" any board. Note that the "sorted" board conists of pieces entirely on the "1" spaces of the board above. Now consider the switching operation. Either both rooks will change from 2 to 1 or 1 to 2 (rooks are on a corners of a rectangle where two opposite corners are 2's and 2 are 1's), one rook will change from 1 to 2 while the other changes from 2 to 1 (rooks are on a corners of a rectangle where both pairs of opposite corners are a 1 and 2), or both rooks stay on same-numbered squares (rooks are on a corners of a rectangle where all corners are the same number). As there are no other possible rectangles for swapped rooks to be on the corners of (other rectangles require three and one corner distribution, but if three are the same the fourth must also be the same due constraints of the layout). By exhaustion of the possibilities then, six non-attacing rooks must distibuted as one of: 6 on the 1's, 0 on the 2's 4 on the 1's, 2 on the 2's 2 on the 1's, 4 on the 2's 0 on the 1's, 6 on the 2's None of these distributions are consistent with the domino layout; therefore this cannot be done. Now here's one understood (by me) question and one open question. a) Is it possible to divide a 6x6 square into 9 L-shaped tetrominoes? (If you want to add a warm-up question ask about 9 T-shaped tetrominoes or 4x1 tetrominoes; both are simpler cases.) (I understand this one reasonably well.) b) If you move one square from the outside of the 6x6 square to adjoin the edge of the former square elsewhere, can you create a figure that can then be divided in this way? In particular, can you do this to form a 36-smaller-square near-square figure that can tile the plane? (I suspect no, but I'm far from an answer.) ---------------------------------------------- straightforward parity argument: checkerboard the square into black + white for ease of explanation. Let coordinates be (1..6) x (1...6), with (1,1) being black. A domino must cover a black square and a white square, so we would need 3 of the rooks on black squares, 3 on white. But the sum of the x and y coordinates of the rooks is 2 * (1+2+...+6), an even number, so there must be an even number of rooks on white squares. Not 3. Dean Sturtevant ---------------------------------------------- Hi Ed, 1. Cover a 6x6 board with 15 dominoes and 6 non-attacking rooks, or show that it is impossible It is impossible, and I will attempt to prove this: In order to arrange 15 dominoes on 30 chessboard squares, it is necessary for 15 of those squares to be black, and 15 white (as in the famous mutilated chessboard problem) since it is impossible to place a domino any way other than it covers one white and one black square. So therefore of the 6 non-attacking rooks, 3 have to cover black squares and 3 have to cover white squares. However for the rooks to be non-attacking, they each have to occupy a unique row and unique column in the chessboard. If we arrange the rooks, say, along the black diagonal then they each occupy a black square, so that will not lead to a solution. We must therefore rearrange the rooks, somehow. Let's suppose we move Rook1 from [r1,c1] to [r1,c2] (same row, different column). This will threaten Rook2 on [r2,c2], and the only place it can be moved so that it isn't threatened is to [r2, c1]. We have two different scenarios: a) [r1,c2] is a different colour square than [r1,c1] which means that [r2,c1] is also a different colour square than [r2,c2]. b) [r1,c2] is the same colour square as [r1,c1] which means that [r2,c1] is also the same colour square as [r2,c2]. The same argument applies if you keep the column the same and change the row. And if you change the row and the column, you will need to do this in two steps (first the row then the column, or vice versa), moving each of the two rooks that are threated in the new row and column. In other words you can only rearrange two rooks at a time, and you can change the colour of Rook1's square if and only if you also change the colour of Rook2's square. This means that 6 non-threatening rooks can be arranged on 6 black, 4 black and two white, 2 black and 4 white or 6 white squares, but NOT 3 black and 3 white squares. Consequently it is impossible to cover the board as you say. Hugh Rutherford. ---------------------------------------------- Enclosed is my proof that no solution to your problem exists. You asked if there was any arraignment of 15 dominos and 6 non attacking rooks on a 6x6 grid. The grid will be considered in rows and columns, 1-6. Assume there is an arraignment fitting your criteria. First, note that six non attacking rooks means each row contains a rook and each column contains a rook. Also, without proof, I state that for a figure to be "makable" out of dominos, it must have an even number of squares that need to be covered. Next, consider the border between rows 1 and 2. Let R1 be the number of dominos that cross the border. If you remove all those dominos, you are left with two independant regions, row 1 and rows 2-6, that are both makable out of dominos. But row 1 has [5-R1] squares that have to be made out of dominos, 6 minus one for the rook, and then minus the R1 squares removed for the dominos that cross the border. This implies [5-R1] is even, so R1 must be odd. Similarly, R5, the number of dominos shared by row 5 and row 6, is also odd. Consider the border between rows 3 and 4. Again, find the R3 dominos shared by each, and remove them to create two seperate regions, rows 1-3 and rows 4-6. Each region now contains [15-R3] squares, because each region contained 3 rooks and R3 squares removed by shared dominos. Then [15-R3] is even, so R3 is odd. Now repeat the process for rows 2 and 3. After spliting apart the regions, the region of rows 1 and 2 contains [10-R2] squares. Then [10-R2] is even, so R2 is even. Similarly, R4 is even. But now what if the same process was repeated for column borders, to get C1,C2,C3,C4 and C5? No assumptions were made, so the same logic is all valid. C1,C3 and C5 are odd, C2 and C4 are even. Consider an arbitrary domino in the potential arraignment. It obviously cannot cross more than one border, but it also must cross at least one border, be it column or row. Then the number of dominos in the arraignment must be equal to the sum of all the R's and C's. But [R1+R3+R5+C1+C3+C5] is even, and [R2+R4+C2+C4] is even, so the sum of all of them is even, so the total number of dominos must be even. However, it is already known that the total number of dominos is 15, a contradiction. QED Well, I hope thats right, Im sorta new to rigorous proofs, thanks for the entertaining problem though. Gregory Muller ---------------------------------------------- The checkerboard puzzle was a lovely problem, taking advantage of its colored squares. Assume the upper left corner of our chessboard is black, and the cells directly below and to the right white. The rest are colored in the standard checkerboard pattern. There will be a total of 18 white and 18 black squares. The dominoes will require 15 white and 15 black squares (a domino must cover one of each, no matter how it's placed on the board), so the six rooks must occupy three white and three black squares. For them not to attack each other, they must be positioned so that one is in each row and one in each column. Looking back at the checkerboard, we see that the first, third, and fifth rows have squares in the pattern black-white-black-white-black-white (going from left to right), while the second, fourth, and sixth rows have white-black-white-black-white-black. It will be discovered that the three rooks in the even-numbered rows must be placed on an identical pattern as the three rooks in the odd-numbered rows. Thus, an EVEN number of rooks must be on black squares and an EVEN number on white squares. So the rooks cannot be placed on squares evenly divided three and three. The task is thus impossible. BTW, the same reasoning shows the general problem of putting (n(n-1))/2 dominoes and n non-attacking rooks on a n-by-n chessboard is impossible if n is of the form 4k+2 where k is an integer. I believe it can be done for any other size board if n>=5. Darrel C Jones ---------------------------------------------- Ed, I believe I have an impossibility proof for the Domino/Rook problem. A) For the rooks to be non-attacking, each one must be the only one in its respective row and column. Since there are six rows and six columns, every row and column in the grid will contain exactly one rook. B) With one rook in each row, there are five empty spaces left in each row. C) Since each horizontal domino takes up two spaces, there must be at least one vertical domino present in each row. D) Any horizontal domino would have to be replaced by two vertical dominoes. Given C, there must be an odd number of vertical dominoes in each row. E) The first and sixth rows will always only share vertical dominoes with the second and fifth rows. Therefore, the second and fifth rows will always have at least as many vertical dominoes as the first and sixth. F) Since the first and sixth rows must have and odd number of vertical dominoes, the total dominoes between them must be an even number. G) Any additional vertical dominoes in the second and fifth rows will always be shared with the third and fourth rows. H) Since the second and fifth rows already have an odd number of vertical dominoes shared with the first and sixth rows, the number of vertical dominoes they share with the third and fourth rows must be even. I) Adding this even number of vertical dominoes keeps the total vertical dominoes even. J) The only remaining vertical dominoes placed on the grid will be those that share the third and fourth rows. K) Since there are currently either zero or an even number of vertical dominoes in the third and fourth rows, the number of vertical dominoes shared by the third and fourth rows must be odd. L) Adding an odd number of vertical dominoes makes the total number of vertical dominoes on the grid odd. M) Given all of the above, the total number of vertical dominoes on the grid must always be odd. N) Applying points B through M to columns on the grid shows that there must also always be an odd number of horizontal dominoes on the grid. O) Applying point B to both cases indicates that there must be both vertical and horizontal dominoes on the grid. P) Given M, N, and O, we can see that there must be an even total number of dominoes on the grid. Q) Since the grid can only hold exactly fifteen dominoes, there is therefore no solution to the problem. Clint Weaver ---------------------------------------------- You can't place 15 dominoes and 6 non-attacking rooks on a 6 by 6 chessboard. The 15 dominoes will cover 15 white spaces and 15 black spaces no matter how you arrange them because of parity. This means you have to have 3 rooks on white spaces and 3 rooks on black spaces that aren't attacking each other. After placing two non-attacking rooks on white and 2 more on black, there are only 4 spaces on the board that that aren't under attack. To keep those final two rooks from attacking each other, they have to be on the same color. Which prevents the dominoes from being placed. Warren Phillips ---------------------------------------------- Ed, Below is a solution to the rook and domino problem you posted on 11/24. I started looking at your site a while back, but this is the first problem I've really spent any time on (or at least the first one I've solved). Thanks for the interesting problems and the links. Jason Dieterle There is probably a more concise way to do this, but it shows that the domino/rook tiling is impossible. Number the rows and columns from 1 to 6. Each square for which the sum of the row and column is even is a black square, and where it is odd, the square is white. To leave a board that could be covered by dominoes (which need a black and white square each) after adding the rooks, an equal number (three) of rooks need to go on each color square. This would mean the total of the sum of the row and column for all six rooks would have to be odd (3*even+3*odd=odd). However, to keep the rooks from attacking, each one needs to be on a different row and column than every other rook. That means that total of the sums has to be 42, since row 1-6 and column 1-6 all have to be used. Since 42 is not odd, there is no way to place the rooks such that the dominoes can fit. ---------------------------------------------- hi, I'm a big fan of your site. about the rooks and dominos problem, any resulting arrangement of free squares after placing the rooks in a non attacking pattern, if it is to be domino-coverable, needs to have an equal number of "light" and "dark" squares (when done checkerboard style). this puts a tight restriction on the number of rook arrangements that can solve the problem, meaning that 3 of them are on light squares and that 3 of them are on dark squares. I have not found any arrangements that satisfy the light/dark requirement. i'm not a math professional however like many of the visitors to the site, so i'm not sure about proving it. but there are not very many possible arrangements of non attacking rooks ( on a 6x6 at least ) so an exhaustive search of them for 3 light 3 dark patterns shouldn't be out of the question. Christian Oudard ----------------------------------------------- Problems of the week deal with squares and dominoes: Cover a 6x6 board with 15 dominoes and 6 non-attacking rooks, or show that it is impossible. my answer is "IMPOSSIBLE". I got a complete charcterisation of the possible nxn chessboards with n non-attacking rooks. Here is it. For which positive integers n we can place on an nxn checkerboard n non attacking rooks and fill the rest by domino-stones? We will prove that this is possible iff n=4k or n=4k+1. Proof: A) Sufficiency: Let n=4. We place the rooks on (1,1), (2,3), (3,2) and (4,4). The other squares are easy to fill. E. G. [(1,4)(2,4)], [(3,4)(3,3)], [(4,3)(4,2)], [(4,1)(3,1)], [(2,1)(2,2)] and [(1,2)(1,3)]. It is trivial that we can fill a 4x4 board completely by dominoes. By this we can dissect a 4kx4k board into k^2 blocs of the size 4x4. As blocs in the diagonal we use the „rookblocs" and in the rest we use the blocs without rooks. For n=1 it is trivial. For n=4k+1 we build a 4kx4k field and add a hook with a rook on (4k+1,4k+1) and 2k dominoes in each of the additional column and row. B) Necessity: We color the square (1,1) white and have therefore a unique checkerboard. At an assumed placement let be a the number of rooks on (o,o) with both coordinates odd. Similarly let b be the number of rooks on (e,e) with both coordinates even. Analogously c the number of (o,e) and d the number of (e,o) rooks. At first let n=2m+1 odd. Then we have up to n m+1 odd and m even numbers. Hence, a+c=a+d=m+1 and b+d=b+c=m. Therefore we get c=d and a=b+1. Further on we have one white square more than black squares. Since all dominoes cover equal numbers of white and black squares we must correct it by rooks. Since (o,o) and (e,e) are white and (o,e) and (e,o) are black, we get a+b=c+d+1=m+1. By c=d we have 2c=m and therefore n=4k+1. Let now be n=2m even. We get analogously a+c=a+d=m and b+d=b+c=m. And hence, a=d and a=b. Now we have an equal number of white and black squares and therefore a+b=c+d=m. By c=d we get m=2c even. Hence, n=4k. Sincerely, Yours Gerd Baron. -------------------------------------------------- 1. After placing the rooks, each column and each row will contain an odd number (5) of empty spaces. 2. When the board is covered, each column and each row will contain and even number (0) of empty spaces. 3. So, the process of placing the dominos must change the parity of each row and of each column an odd number of times. The total number of parity changes must be even ((6+6+2n), where n is some nonnegative integer). 4. When placing a single domino, exactly one row or column will change parity. 5. After placing 15 dominos, there will be an odd number (15) of parity changes. 6. Since 3 & 5 require that the total number of parity changes be both odd and even, it is impossible to cover the board this way. bill clagett ---------------------------------------------------- We are given M>0; we ask for a covering of the M X M board with M non-attacking rooks and M(M-1)/2 dominoes. We want to prove that the problem has solutions if and only if M has the form 1, 4, 5, 8, 9, 12, 13 ....; say if and only if M=4n or M=4n+1. Concerning the "only if" part, WLOG we can assume that the square in row #1 and column #1 is black; the claim will then follow from the fact that any solution must satisfy: (1) The number of rooks on white squares must be even. (2) The number of rooks on white squares must be given by M/2 if M is even; and by (M-1)/2 if M is odd. Let us prove these points. First of all we remark that, the square [1,1] being black, the square [r,c] in row r and column c is black if and only if the value of r+c is even. In particular, let [rj,cj] be the coordinates of the rooks; if we look at the parity of the sum in j of all the values rj+cj, the "black" rooks do not give contribution; thus the sum will be even if and only if the number of "white" rooks is even. Point (1) then follows from the fact that this sum must be even. In fact the coordinates (rj,cj) of M non-attacking rooks must be such that each value between 1 and M appears exactly once in the family {rj} and exactly once in the family {cj}; thus the sum takes the even value M(M+1). Concerning point (2) we remark that the M(M-1)/2 dominoes occupy M(M-1)/2 black squares and M(M-1)/2 white squares; if M is even this leaves for the rooks M/2 black squares and M/2 white squares; while for odd M the black squares are one more than the white ones; thus we need (M+1)/2 rooks on black squares and (M-1)/2 rooks on white squares. Concerning the "if" part, let us simply remark that for any EVEN value of n, knowing a solution for the nXn board we can easely construct: - a solution for the (n+1)x(n+1) board; - a solution for the (n+4)x(n+4) board. Such constructions are easier to find than to describe; e.g. by the strategy used in the enclosed picture, that deals whith the case n=8 but can obviously be generalized to any even value of n. In particular, starting from the easy solution for the 4x4 board, we solve the 5x5 and the 8x8 boards; starting from the 8x8 board we solve for the 9x9 and the 12x12 boards; and so on. Claudio Baiocchi ----------------------------------------------------------