Browse · MathNet
PrintUkrainian 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.)

Solution
Answer: Yes, it is possible (see the figure).
Final answer
Yes
Techniques
Coloring schemes, extremal argumentsMatchings, Marriage Lemma, Tutte's theorem