задачка (математическая)
Oct. 8th, 2002 10:31 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaВот не очень сложная математическая задачка примерно олимпиадного типа для тех, кому это интересно. Постараюсь описать её в как можно более элементарных терминах.
Возьмём какой-нибудь алфавит из двух символов; для наглядности пусть это будет {1,2}, т.е. разрешённые символы - единица и двойка. Конкретный выбор символов роли не играет.
Рассмотрим какую-нибудь последовательность x1, x2, ... , xn , где каждый член последовательности - символ из нашего алфавита. Например, n может быть 10,
а последовательность может быть 2221112221 . Вместо "последовательности" может оказаться удобным говорить просто о строках, построенных на данном алфавите - это одно и то же.
Рассмотрим все строки вида xi, xi+1, ... , x2*i внутри нашей последовательности (i двигается от единицы и выше; если 2*i > n, то строка заканчивается на n-ном месте). В приведенном выше примере такими будут: x1...x2 (то есть "22"); x2...x4 (то есть "221"); x3...x6 (то есть "2111"); x4...x8 (то есть "11122"); и, наконец, x5...x10 (то есть "112221") (ещё на самом деле x6...x10 итп., но они неинтересны, как будет ясно из нижеизложенного).
Может случиться так, что какая-то из этих строк такого вида окажется под-последовательностью другой, более длинной строки такого вида. Под под-последовательностью здесь подразумевается то, что первая строка будет заключена "внутри" второй под-строки, но необязательно в идущих подряд местах. Например, "121" - подпоследовательность "1121", очевидно, но кроме того, "121" -- под-последовательность "1221", потому что члены "121" можно найти по порядку внутри "1221", хоть и не подряд.
Если для нашей строки x1...xn длиной n окажется, что какая-то из строк вида xi, xi+1, ... , x2*i является под-последовательностью другой более длинной строки вида xк, xк+1, ... , x2*к, то мы скажем, что строка x1...xn является плохой. Если же никакая строка такого вида не является под-последовательностью другой строки такого вида, то исходная строка x1...xn называется хорошей. Например, приведенная в качестве примера строка из 10 символов, очевидно, плохая.
Требуется: доказать, что существует максимальная длина хорошей строки. Найти хорошую строку максимальной длины.
Возьмём какой-нибудь алфавит из двух символов; для наглядности пусть это будет {1,2}, т.е. разрешённые символы - единица и двойка. Конкретный выбор символов роли не играет.
Рассмотрим какую-нибудь последовательность x1, x2, ... , xn , где каждый член последовательности - символ из нашего алфавита. Например, n может быть 10,
а последовательность может быть 2221112221 . Вместо "последовательности" может оказаться удобным говорить просто о строках, построенных на данном алфавите - это одно и то же.
Рассмотрим все строки вида xi, xi+1, ... , x2*i внутри нашей последовательности (i двигается от единицы и выше; если 2*i > n, то строка заканчивается на n-ном месте). В приведенном выше примере такими будут: x1...x2 (то есть "22"); x2...x4 (то есть "221"); x3...x6 (то есть "2111"); x4...x8 (то есть "11122"); и, наконец, x5...x10 (то есть "112221") (ещё на самом деле x6...x10 итп., но они неинтересны, как будет ясно из нижеизложенного).
Может случиться так, что какая-то из этих строк такого вида окажется под-последовательностью другой, более длинной строки такого вида. Под под-последовательностью здесь подразумевается то, что первая строка будет заключена "внутри" второй под-строки, но необязательно в идущих подряд местах. Например, "121" - подпоследовательность "1121", очевидно, но кроме того, "121" -- под-последовательность "1221", потому что члены "121" можно найти по порядку внутри "1221", хоть и не подряд.
Если для нашей строки x1...xn длиной n окажется, что какая-то из строк вида xi, xi+1, ... , x2*i является под-последовательностью другой более длинной строки вида xк, xк+1, ... , x2*к, то мы скажем, что строка x1...xn является плохой. Если же никакая строка такого вида не является под-последовательностью другой строки такого вида, то исходная строка x1...xn называется хорошей. Например, приведенная в качестве примера строка из 10 символов, очевидно, плохая.
Требуется: доказать, что существует максимальная длина хорошей строки. Найти хорошую строку максимальной длины.
