Задача маляра

[gegmopo4]

Забор раскрашивается 5-ю красками так, что никакие две соседние доски не раскрашены в одинаковый цвет. Какой максимальной длины забор можно раскрасить, чтобы никакая последовательность из 3-х красок не повторялась в узоре? А для 3 красок и последовательности длиной 5? А в общем случае - для n красок и последовательности длиной m? А если забор

Comments

[dimadams]

ну, скоро решение будет? :)

[gegmopo4]

Откуда же мне знать? :)

[urist911]

Сходной проблемой был озабочен немецкий математик Август Фердинанд Мёбиус (1790-1868) - родоначальник науки топологии.
В первом томе Трудов Лондонского географического общества 1879 г. известный британский алгебраист Артур Кэли (1821-1895) поместил статью, где отчетливо сформулировал задачу о четырех красках и полит.карте, которая до этого была известна как занятная головоломка.
И вот если бы я был таким умным, как они, то запросто бы ее решил...
:-((

[gegmopo4]

Эта задача имеет отношение скорее к комбинаторике, чем к топологии.

о комбинаторике...

[urist911]

да, конечно.
Давненько я не слышал ничего о комбинаторике...
Помню, что там для таких задач участвует факториал:
(число красок)!
А вот как решить, не знаю.

[12_natali]

из 3-х составляющих - 12, а дальше по формуле (которую не помню :)