ПитерГор 2018

Подсказка 1

Будем называть места для карточек клетками. Кажется, что больше всего проблем из-за тех карточек, которых больше всего, потому что они будут встречаться чаще. Может тогда сначала решим проблему соседних одноцветный для них?

Подсказка 2

Пусть наши цвета: красный, синий, зелёный — а их количества К, С, З соответственно. Не умоляя общности будем считать, что K ≥ С ≥ З. Разберёмся сначала с красными. В какой одной из самых известных раскрасок одноцветные точно не соседние?

Подсказка 3

Именно! Прекрасная шахматная раскраска. Попробуем применить эту же идею в нашей задаче. Как тогда нам следует размещать красные карточки?

Подсказка 4

Да! Не умоляя общности, в чёрные клетки шахматной раскраски. Только делать нужно это упорядоченно, а не случайным образом. Как же это сделать?

Подсказка 5

Например, идя по строкам слева направо и по столбцам сверху вниз, начиная с левого нижнего угла (как змейка, сначала нижняя строка, потом над ней и т.д.). Очевидно, что чёрных клеток хватит (вспомним условие). Отлично, с красными разобрались. Теперь логичнее всего разобраться с синими. Подумайте, как разместить их.

Подсказка 6

Ну, можно например делать также, как с чёрными, только начать с самой левой нижней белой клетки. Только вот что там будет наверху квадрата? Может быть там потом зелёные станут соседними. Не годится. Как бы нам сделать так, чтобы после расставления синих, соседних клеток не осталось вообще? Напомним, что C = min(К, С, З) и К + С + З = 100.

Подсказка 7

Будем раскладывать синие, симметрично красным! То есть начнём с правого верхнего угла и пойдём по белым. Знаем, что K + C ≥ 67. Что теперь происходит с квадратом?

Подсказка 8

Синяя и красная змейка не оставляют за собой соседних незанятых клеток. Докажите, что в итоге эти змейки "схлопнуться" и не оставят таких клеток вообще. А дальше останется сказать пару слов про зелёные. У вас всё получится! Успехов!