задачка (математическая)

Вот не очень сложная математическая задачка примерно олимпиадного типа для тех, кому это интересно. Постараюсь описать её в как можно более элементарных терминах.

Возьмём какой-нибудь алфавит из двух символов; для наглядности пусть это будет {1,2}, т.е. разрешённые символы - единица и двойка. Конкретный выбор символов роли не играет.

Рассмотрим какую-нибудь последовательность x₁, x₂, ... , x_n , где каждый член последовательности - символ из нашего алфавита. Например, n может быть 10,
а последовательность может быть 2221112221 . Вместо "последовательности" может оказаться удобным говорить просто о строках, построенных на данном алфавите - это одно и то же.

Рассмотрим все строки вида x_i, x_i+1, ... , x_2*i внутри нашей последовательности (i двигается от единицы и выше; если 2*i > n, то строка заканчивается на n-ном месте). В приведенном выше примере такими будут: x₁...x₂ (то есть "22"); x₂...x₄ (то есть "221"); x₃...x₆ (то есть "2111"); x₄...x₈ (то есть "11122"); и, наконец, x₅...x₁₀ (то есть "112221") (ещё на самом деле x₆...x₁₀ итп., но они неинтересны, как будет ясно из нижеизложенного).

Может случиться так, что какая-то из этих строк такого вида окажется под-последовательностью другой, более длинной строки такого вида. Под под-последовательностью здесь подразумевается то, что первая строка будет заключена "внутри" второй под-строки, но необязательно в идущих подряд местах. Например, "121" - подпоследовательность "1121", очевидно, но кроме того, "121" -- под-последовательность "1221", потому что члены "121" можно найти по порядку внутри "1221", хоть и не подряд.

Если для нашей строки x₁...x_n длиной n окажется, что какая-то из строк вида x_i, x_i+1, ... , x_2*i является под-последовательностью другой более длинной строки вида x_к, x_к+1, ... , x_2*к, то мы скажем, что строка x₁...x_n является плохой. Если же никакая строка такого вида не является под-последовательностью другой строки такого вида, то исходная строка x₁...x_n называется хорошей. Например, приведенная в качестве примера строка из 10 символов, очевидно, плохая.

Требуется: доказать, что существует максимальная длина хорошей строки. Найти хорошую строку максимальной длины.

Галковский в ЛГ

Галковский (это такой гениальный русский философ) зажигает в "Литературке", защищая свою антологию советской поэзии:

Теперь о рецензии Андрея Василевского. Василевский считает, что стихи подобраны в антологию тенденциозно. Это все стихи очень плохие. А были ведь и стихи хорошие. В них отражается подлинная жизнь Страны Советов.

С этим тезисом согласиться невозможно. “Хорошие стихи” предполагают наличие у их авторов определенной КУЛЬТУРЫ. Советские же от мировой культуры отказались. От отечественной тоже. Цитирование Василевским в подтверждение своей мысли стихотворения Мандельштама выглядит кощунственно. Сервантеса поймали алжирские пираты и несколько лет держали в тюрьме. Что же, на этом основании его можно считать алжирским писателем?

А также цитирует один бессмертный стих из этой антологии:

На белизну нетленной кости
Рисунок чукчи нанесли.
Олени мчатся. Едет в гости
Ильич на снежный край земли.

Сидит на первых нартах Ленин,
Сидит в кухлянке меховой.
И серые глаза оленя
Пылают радостью живой.

Пыль снеговую поднимая,
Легко несется он вперед.
Олень как будто понимает,
Кого он в этот раз везет.

Как увижу антологию - сразу куплю.

белорусские свободы

Законопроект «О свободе вероисповедания и религиозных объединений» запрещает гражданам Беларуси собираться вместе для молитв по месту жительства, если они не зарегистрируют религиозные общины.

Вспоминается классический анекдот: ( неприличный анекдот... )

Вот такая вот в Белоруссии свобода вероисповедания.

ещё о дословном переводе

Включаю телевизор. Идёт какой-то средненький американский фильм, с русскими субтитрами (которые я поставил в виде эскперимента).

Герой говорит героине о ком-то третьем: "But he couldn't forgive her... and died of a broken heart".

В титрах русский перевод: "Но он её так и не простил, и умер от разрыва сердца".

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

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

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

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