Skip to main content
OlympiadHQ

Browse · MathNet

Print

Bulgarian National Mathematical Olympiad

Bulgaria counting and probability

Problem

Consider a unit cell table. Ivan puts horizontal domino , which covers exactly of the cells, then Peter puts vertical domino , which covers exactly of the cells then again Ivan puts horizontal domino and so on. The player who has no move loses the game. Determine which of the two players has winning strategy.
Solution
We describe winning strategy for Ivan. He divides the table into tables and a table . Then he puts his first domino in the table (no matter in which row). Peter is forced to put his domino in a table . Now Ivan puts a domino in any place in the same table. It is easy to see that Ivan has one more way to put a domino in the same table and after two moves each the cells from this table are all covered. After covering all cells in all tables it is Peter's turn and he has no move. Therefore Ivan wins.
Final answer
Ivan

Techniques

Games / greedy algorithms