17. [Russia 2005]
100 people from 25 countries, four from each country, sit in a
circle. Prove that one may partition them onto 4
groups in
such way that no two countrymen,
nor two neighboring
people
in the circle, are in the same group.
18. [Saint Petersburg 1997]
An
Aztec diamond of rank n is a
figure consisting of those
squares of a gridded coordinate plane lying inside the square
|
x| + |
y| ≤
n+1. For any covering
of an Aztec diamond by
dominoes, a move consists of selecting a 2x2 square covered
by two dominoes and rotating it by 90 degrees. The aim is to
convert the initial covering into the covering consisting of only
horizontal dominoes. Show that this can be done using at most
n(
n+1)(2
n+1)/6 moves.
