October 8th, 2002

moose, transparent

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

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

Возьмём какой-нибудь алфавит из двух символов; для наглядности пусть это будет {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 символов, очевидно, плохая.

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

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

Галковский (это такой гениальный русский философ) зажигает в "Литературке", защищая свою антологию советской поэзии:
Теперь о рецензии Андрея Василевского. Василевский считает, что стихи подобраны в антологию тенденциозно. Это все стихи очень плохие. А были ведь и стихи хорошие. В них отражается подлинная жизнь Страны Советов.

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

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

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

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

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

moose, transparent

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

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

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

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

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

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

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

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