Skip to main content
OlympiadHQ

Browse · MathNet

Print

Ukrainian Mathematical Olympiad

Ukraine counting and probability

Problem

Is it possible to fill in a table with ones and zeros so that: 1) for each cell containing one, sum of numbers in neighbour cells equals one, 2) for each cell containing zero, sum of numbers in neighbour cells does not equal one? (Two cells are neighbours if they have a common side.)

problem
Solution
Answer: Yes, it is possible (see the figure).

Final answer
Yes

Techniques

Coloring schemes, extremal argumentsMatchings, Marriage Lemma, Tutte's theorem