Олимпиада имени Леонарда Эйлера2009-2010 учебный год, II тур дистанционного этапа

Том Сойер взялся покрасить очень длинный забор, соблюдая условие: любые две доски, между которыми ровно две, ровно три или ровно пять досок, должны быть покрашены в разные цвета. Каким наименьшим количеством различных красок он сможет обойтись?

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ. Тремя.
Решение. Заметим, что между первой и четвёртой и четвёртой и седьмой досками — по две доски, а между первой и седьмой досками — пять досок. Поэтому первая, четвёртая и седьмая доски забора должны быть раскрашены в различные цвета, то Тому понадобятся по крайней мере три различные краски. С другой стороны, трёх цветов ему хватит, если красить, например, так: $AAABBBCCCAAABBBCCC\dots$: тут между любыми двумя одноцветными досками не менее 6 досок.