задачка математическая, часть 2

[avva]

Продолжение задачи, о к-й я написал сегодня утром (несколько человек её правильно решили).

Следующий, уже не такой простой шаг: доказать, что существует максимальная длина "хорошей" строки для любого алфавита конечного размера (необязательно уже из двух символов). Замечу на всякий случай, что меняется только кол-во разрешённых символов, всё остальное в условии остаётся без изменения (в частности, при рассмотрении подстрок вида x_i...x_2*i, коэффициент остаётся всегда двойкой).

Если никто не решит, я завтра помещу доказательство. Оно нетривиальное, но и не слишком сложное.

Comments

[(Anonymous)]

нужно как-то увязать это с арабо-израильским конфликтом, для повышения энтузазима :)

Re:

[avva.livejournal.com]

Я бы рад, но не очень выходит ;-)

please, поместите!

[(Anonymous)]

Поместите, пожалуйста. В школе я очень любила математику, в вашей задаче позавчера вечером дома пыталась что-то увидеть, как то выстроить свое, но погрязла в проблеме разделения последовательностей и под-последовательностей. И вообще логически мыслить я отвыкла уже давно. А это правда, так красиво тоже. Очень заманчиво. Для меня во всяком случае узнать, как будет по-вашему нетривиальное доказательство.

Re: please, поместите!

[avva.livejournal.com]

Уже поместил, см. мою последнюю запись. Она получилась несколько громоздкой, потому что я старался специально разъяснить всё как можно подробнее для тех, кто не привык к терминологии и некоторым стандартным построениям.