748 Combinatorics and Probability
f(s)=d.Iffwere not one-to-one, that is, iff(s 1 )=f(s 2 )=d, for somes 1 ,s 2 ∈A,
thendwould cover squares directly belows 1 ands 2 as described in Figure 107. Thens 1
ands 2 must be neighbors, so a new domino can be placed to cover them. We conclude
thatfis one-to-one, and hence|A|≤|B|. It follows that|B|≥11. But there are only
11 dominoes, so|B|=11. This means that all 11 dominoes lie completely inS 3 and
the top row is not covered by any dominoes! We could then put three more dominoes
there, contradicting our assumption on the maximality of the arrangement. Hence the
assumption was wrong; one can always add a domino to an arrangement of 11 dominoes.
The answer to the problem is thereforen=11.
tsss
d12Figure 107Second solution: Suppose we have an example withkdominoes to which no more can
be added. LetXbe the number of pairs of an uncovered square and a domino that covers
an adjacent square. Letm= 36 − 2 kbe the number of uncovered squares, letm∂be the
number of uncovered squares that touch the boundary (including corner squares), and
mcthe number of uncovered corner squares. Since any neighbor of an uncovered square
must be covered by some domino, we haveX= 4 m−m∂−mc. Similarly, letk∂be the
number of dominoes that touch the boundary andkcthe number of dominoes that contain
a corner square. A domino in the center of the board can have at most four unoccupied
neighbors, for otherwise, we could place a new domino adjacent to it. Similarly, a
domino that touches the boundary can have at most three unoccupied neighbors, and a
domino that contains a corner square can have at most two unoccupied neighbors. Hence
X≤ 4 k−k∂−kc. Also, note thatk∂ ≥m∂, since as we go around the boundary we
can never encounter two unoccupied squares in a row, andmc+kc≤4, since there are
only four corners. Thus 4m−m∂−mc=X≤ 4 k−k∂−kcgives 4m− 4 ≤ 4 k; hence
35 − 2 k≤kand 3k≥35. Thuskmust be at least 12. This argument also shows that on
ann×nboard, 3k^2 ≥n^2 −1.
(T. Andreescu, Z. Feng, 102Combinatorial Problems, Birkhäuser, 2000, second
solution by R. Stong)
859.Let
Ik=∫π 20(2 sinθ)^2 kdθ, k≥ 0.