Покрасим все стороны клеток в красный цвет, кроме одной. Инвариант - чётность количества синих сторон. Пусть у клетки было:
(слева - кол-во красных сторон, справа - кол-во синих сторон)
4/0 --> 0/4
3/1 --> 1/3
2/2 --> 2/2
1/3 --> 3/1
0/4 --> 4/0
Значит, количество синих сторон будет изменяться на 0, 2 или 4. Надо сделать 36 синих сторон, но 36 - число чётное, а 1 - нечётное. Противоречие.
Ответ: Не всегда.