Олимпиадная задача: Том Сойер и забор — комбинаторика, минимальное число цветов
Задача
Том Сойер взялся покрасить очень длинный забор, соблюдая условие: любые две доски, между которыми ровно две, ровно три или ровно пять досок, должны быть окрашены в разные цвета. Какое наименьшее количество красок потребуется Тому для этой работы?
Решение
Двух красок (скажем, белой и красной) не хватит: покрасив доску номер1в белый цвет, Том будет вынужден покрасить в красный цвет доски с номерами4,5и7. Тогда между красными досками номер4и номер7будет ровно две доски, что нарушает требование условия. Трёх красок достаточно: Том может покрасить три доски подряд в белый цвет, потом три доски в синий, потом три — в красный, потом снова три — в белый и так далее. При этом между одинаково окрашенными досками будет либо не более одной доски (если они в одной тройке), либо не менее шести (если они в разных тройках), так что условие задачи будет выполнено.
Ответ
3краски.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь