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
----------------------------------------------------------