Задача 1.2. Гирлянда из двух цветов

Переводим слова в номера

Пронумеруем шары по порядку: $1, 2, 3, \ldots$ Гирлянду считаем рядом с двумя концами, а не замкнутым кольцом.

Что значит «между шарами ровно три шара»? Возьмём шары $2$ и $6$: между ними стоят шары $3$, $4$ и $5$ — ровно три. Но номера отличаются не на $3$, а на $6-2=4$: от шара $2$ до шара $6$ четыре шага — три шага по шарам между ними и ещё один на сам шар $6$. Так же между шарами $1$ и $8$ стоят шесть шаров (со $2$-го по $7$-й), а номера отличаются на $8-1=7$.

Значит, условие говорит:

• шары, номера которых отличаются на $4$, одного цвета (правило 1);
• шары, номера которых отличаются на $7$, тоже одного цвета (правило 2).

Зачем это нужно: с номерами можно считать, а «три шара между» легко по ошибке превратить в разность $3$.

Правило 1: четыре столбика, каждый одного цвета

Сначала посмотрим только на правило 1. Шар $5$ того же цвета, что шар $1$ (разность $4$), а шар $9$ — того же цвета, что шар $5$. Значит, шары $1$, $5$, $9$, … одного цвета: каждый следующий на $4$ номера дальше предыдущего. Точно так же одного цвета шары $2$, $6$, $10$, …, шары $3$, $7$, $11$, … и шары $4$, $8$, $12$, …

Запишем номера строками по четыре: $1, 2, 3, 4$; под ними $5, 6, 7, 8$; ниже $9, 10, 11, 12$. Каждая такая цепочка встанет в один столбик, и в каждом столбике все шары одного цвета (рисунок ниже). Столбиков четыре, и каждый шар гирлянды стоит ровно в одном из них. Столбик шара легко узнать по остатку от деления его номера на $4$: в 1-м столбике остаток $1$ ($1$, $5$, $9$), во 2-м — остаток $2$, в 3-м — остаток $3$, а в 4-м номера делятся на $4$ нацело.

Как до этого догадаться: правило «шары на одинаковом расстоянии — одного цвета» означает, что раскраска повторяется с этим шагом. Поэтому её удобно записать строками длиной в этот шаг.

Правило 2 склеивает столбики: 10 шаров быть не может

Пусть в гирлянде хотя бы $10$ шаров. Тогда в ней есть три пары, которые связывает правило 2:

• шары $1$ и $8$: шар $1$ стоит в 1-м столбике, шар $8$ — в 4-м. Значит, 4-й столбик того же цвета, что 1-й;
• шары $2$ и $9$: шар $9$ стоит в 1-м столбике, поэтому 2-й столбик того же цвета, что 1-й;
• шары $3$ и $10$: шар $10$ стоит во 2-м столбике, поэтому 3-й столбик того же цвета, что 2-й.

Получилась цепочка из всех столбиков: 4-й — 1-й — 2-й — 3-й (рисунок ниже). Все четыре столбика одного цвета, а каждый шар стоит в одном из них. Значит, вся гирлянда одного цвета. Но по условию в ней есть и красные, и синие шары — противоречие.

Итак, гирлянды из $10$ шаров и больше не бывает: шаров не больше $9$.

Как это заметить: после шага 2 цвет всей гирлянды задают всего четыре столбика. Остаётся выяснить, какие из них правило 2 заставляет быть одинаковыми. Пары правила 2 появляются по одной, когда гирлянда растёт: при $8$ шарах — пара $1$ и $8$ (склеены 1-й и 4-й столбики), при $9$ — ещё $2$ и $9$ (к ним добавился 2-й), при $10$ — ещё $3$ и $10$. Последний свободный столбик, 3-й, склеивается как раз на десятом шаре — поэтому мы и проверяли гирлянду из $10$ шаров. В модели с кнопкой «Группы» видно, как при $7$, $8$, $9$ и $10$ шарах групп становится $4$, $3$, $2$ и $1$.

Девять шаров: один столбик остаётся свободным

Уберём шар $10$. Пропадает только одна склейка — пара $3$ и $10$. Пары $1$ и $8$, $2$ и $9$ остаются, так что 1-й, 2-й и 4-й столбики по-прежнему одного цвета. А 3-й столбик — шары $3$ и $7$ — больше ни с чем не связан. Проверим по номерам: шару $3$ в пару годятся только шары $3+4=7$ и $3+7=10$, но шара $10$ уже нет; шару $7$ — только шар $7-4=3$, потому что шаров $7+4=11$ и $7+7=14$ нет, а $7-7=0$.

Значит, шары $3$ и $7$ можно покрасить иначе, чем остальные. Пусть они синие, а остальные красные. Получим гирлянду ККСКККСКК.

Проверим все пары. С разностью $4$: $1$ и $5$, $2$ и $6$, $4$ и $8$, $5$ и $9$ — красные, $3$ и $7$ — синие. С разностью $7$: $1$ и $8$, $2$ и $9$ — красные. Все семь пар одного цвета, и оба цвета есть. Значит, $9$ шаров быть может — и по шагу 3 это наибольшее количество.