Problem:
At each vertex of a regular -gon, lies a coin. Initially coins are heads, and coins are tails. Determine the minimum number such that it's always possible to turn over at most of the coins so that in the resulting -gon, no two adjacent coins are both heads and no two adjacent coins are both tails.
Solution:
Number the vertices from to . We need to make sure that all the even-numbered vertices are tails and all the odd numbered vertices are heads or vice versa.
Let's look at the odd numbered vertices.
Without loss of generality, assume that there are initially more heads than tails on the odd numbered vertices. That is, we assume that there are initially at least heads on odd numbered vertices. This means there are at most tails on odd numbered vertices and at most heads on even numbered vertices. So we flip all the tails on odd numbered vertices and all the heads on even numbered vertices. Then the total number of flips required is at most .
If there are exactly heads (and tails) on odd numbered vertices, then we would require at least flips to make all the odd numbered vertices the same, and similarly at least flips to make the even numbered vertices the same. So we cannot guarantee to be able to achieve our goal in fewer than flips.