1. Оказавшись как-то раз в библиотеке без присмотра, хулиган Вася
переставил 100 томов энциклопедии, стоявших на полке. Библиотекарь заметил это
и стал наводить порядок. Для этого он проделывает каждый день одну из следующих
операций:
a) меняет местами любые два соседних тома.
б) меняет местами любые два тома.
в) берет любые три тома и расставляет их в другом порядке.
г) переставляет в конец любой том (сдвинув остальные тома).
д) ставит любой том в любое другое место.
За какое наименьшее число дней библиотекарь сможет расставить тома в
порядке возрастания номеров в каждом случае?
2. Обнаружив, что библиотекарь исправил его предыдущую шалость,
хулиган Вася снова переставил тома и решил, что будет приходить в библиотеку
каждый день перед закрытием для поддержания беспорядка. Теперь библиотекарь по
утрам вынимает любые k томов и ставит их в другом порядке на те же места, а Вася
каждый вечер проделывает такую же операцию с любыми n томами. В энциклопедии
по-прежнему 100 томов. Теперь библиотекарь уже не надеется расставить все тома
по порядку, а хочет лишь, чтобы на своем месте стояло как можно больше томов.
Пусть P(n,k) - наибольшее количество томов, которое он сможет расставить на свои
места до очередного прихода Васи (при любых действиях Васи; при этом мы всегда
будем предполагать, что исходно тома расставляет Вася).
a) Найдите P(n,k) при k > n+1.
б) Найдите P(2,3).
в) Найдите P(2k, 2k+1).
г) Докажите, что P(3,4) <
28.
д) Найдите P(3,4).
е) Докажите, что P(2k-1, 2k) <
[100/(2k)] + 2k - 1 при k < 20.
ж) Вычислите P(2k-1,2k) с точностью до аддитивной константы, не зависящей от
S и k, если в энциклопедии S >> k томов.
з) Пусть k фиксировано. Верно ли, что P(2k-1, 2k) не убывает при возрастании
S ?
3. Пусть энциклопедия содержит S томов, а подсчет числа томов, стоящих
на своих местах, всегда происходит после хода библиотекаря.
а) Библиотекарь переставляет любые два тома, а Вася - любые два соседних
тома. Какое наибольшее число томов библиотекарь сумеет расставить
на своих местах?
Библиотекарь переставляет любые три тома, а Вася - любые два соседних.
б.1) Докажите, что библиотекарь сможет расставить не менее 1/20 всех
томов, но не более 2/3.
б.2) Докажите, что библиотекарь сможет расставить не менее 1/5 всех томов.
в.1) Лемма о торжестве порядка.
Пусть библиотекарь переставляет любые k>4 томов, а хулиган Вася любые n
подряд стоящих томов. Тогда найдется такое число
a c (0,1), не зависящее от S, что при любых
действиях Васи библиотекарь сумеет поставить на место не менее
aS томов.
в.2) Лемма о торжестве беспорядка.
Пусть библиотекарь переставляет любые k>4 томов, а хулиган Вася любые
n>k подряд стоящих томов. Тогда найдется такое число
b c (0,1), не зависящее от S, что при любых
действиях библиотекаря Вася сумеет добиться того, чтобы не менее
bS томов стояли не на месте.
4. Теперь библиотекарь переставляет любые k подряд стоящих томов,
а Вася - любые n подряд стоящих томов. Пусть Q(n,k) - наибольшее количество
томов, которое библиотекарь сможет поставить на место после своего хода.
а) Докажите, что 0 < Q(2, 3) <
3 при любом S.
б) Найдите Q(2,3) при четном S.
в) Докажите лемму о торжестве беспорядка для рассматриваемых
операций при любых n и k.
г)* Докажите лемму о торжестве порядка при k=5n.
5. Пусть библиотекарь переставляет любые k подряд стоящих томов, а
Вася - 2 любых тома.
а) Лемма о полном торжестве беспорядка.
При любом a > 0 найдется такое (возможно, очень
большое) S, что библиотекарь не сумеет поставить на места более чем
aS томов.
б) Докажите, что количество томов, которые библиотекарь сможет поставить
на место, не превосходит некоторой константы, не зависящей от S.
в) Лемма об абсолютном беспорядке. Если S значительно больше
k, то библиотекарь не сумеет поставить на место ни одного тома.
Точный смысл слов "значительно больше" оставляем на ваше усмотрение.
1.а) Заметим, что число инверсий при выполнении указанной операции изменяется на 1. Если в начале тома расставлены в обратном порядке, то образуется 100*99/2=4950 инверсий, следовательно, чтобы упорядочить тома, потребуется не менее 4950 операций. С другой стороны, этого количества заведомо хватит, если библиотекарь будет переставлять каждый раз два тома, образующих инверсию.
б) При выполнении операции количество независимых циклов изменяется не более чем на 1. Если в начале был только один цикл (меньше не бывает), то библиотекарю понадобится не менее 99 операций. В тоже время этого количества ему заведомо хватит, если каждым ходом он будет ставить один том на свое место.
в) Аналогично пункту б) количество независимых циклов будет изменяться не более чем на 2. Следовательно, понадобится не более 50 операций. Чтобы уложиться в это число операций, библиотекарь должен каждым ходом ставить два тома на свое место.
Замечание. Если библиотекарь переставляет k томов, то своим ходом он может поставить на свои места не более k-1 тома (если было столько томов, стоящих не на месте).
г), д) Ответ: 99 операций. Если библиотекарь будет ставить в конец тома с последовательными номерами, начиная со второго, то 99 операций ему заведомо хватит. Если тома изначально стояли в обратном порядке, то библиотекарь должен будет переставить каждый из томов, кроме, быть может, одного, так как в противном случае, те два тома, которые он не переставил, по-прежнему будут образовывать инверсию.
1.а) Очевидно (см. замечание выше).
б) Ответ: 2. Вася легко может поддерживать ситуацию, в которой все четные тома стоят на нечетных местах, а нечетные - на четных.
в) Та же идея. Ответ: 2k.
Примечание Web-мастера: далее в оригинале порядок циклов заключался в угловые < > скобки, которые здесь заменены на круглые () в связи с особым смыслом символов < и > в языке HTML.
г), е) Перестановкой n томов нельзя изменить количество независимых циклов больше чем на n-1, поскольку в каждом из новообразованных циклов должен содержаться хотя бы один из переставляемых томов. Заметим теперь, что в разложении исходной перестановки на независимые циклы Вася всегда может поддерживать ситуацию, в которой после его хода (2k-1)-циклов не меньше, чем (1)-циклов (если это выполнено в начальной расстановке). Действительно, если перед ходом Васи имеется по крайней мере 2k-1 (1)-циклов, то своим ходом он сможет построить из них (2k-1)-цикл, уменьшив разность количеств (1)-циклов и (2k-1)-циклов на 2k. Если же (1)-циклов было меньше 2k-1, то Вася сможет все их уничтожить. С другой стороны, библиотекарь не может увеличить эту разность больше, чем на количество томов, которое он переставляет. Это нетрудно проверить для каждого цикла по отдельности, а затем просуммировать. Таким образом, после хода Васи количество (1)-циклов не может быть больше [100/(2k)], причем в случае равенства все тома разбиты на 2k-1-циклы (и еще несколько меньших циклов, в которых вместе находится не более (2k-1) томов), и библиотекарь не сможет своим ходом увеличить число (1)-циклов более чем на 2k-1.
д) Пусть сначала библиотекарь стремится увеличить общее количество циклов, а Вася отвечает такими перестановками, что число циклов после его хода всегда оказывается не превосходящим, скажем, m. Поскольку библиотекарь может увеличить количество циклов на 3, развалив один цикл длины больше 3 на четыре цикла, а Вася не может изменить количество циклов больше, чем на 2, то в момент когда после хода Васи имеется ровно m циклов, в каждый из этих циклов должно входить не более трех томов. Если в такой момент имеется два (3)-цикла, то библиотекарь может их разбить на два (2)-цикла и два (1)-цикла, на что Вася может ответить только превращением трех (1)-циклов в (3)-цикл (иначе библиотекарь сможет увеличить число циклов). Таким образом, общее количество циклов после хода Васи не изменилось, а количество (3)-циклов уменьшилось. Следовательно, через некоторое время должно остаться не более одного (3)-цикла. Теперь библиотекарь каждым ходом должен из двух (2)-циклов делать четыре (1)-цикла, а Вася по-прежнему из трех (1)-циклов будет лепить (3)-цикл. Таким образом, число (1)-циклов будет расти, и при этом их будет не меньше, чем (3)-циклов (после хода Васи). Когда все (2)-циклы закончатся (или останется один (2)-цикл), количество (1)-циклов будет не меньше 25, и библиотекарь своим ходом сможет создать еще три (1)-цикла (см. замечание выше). Ответ: 28.
ж) Рассмотрим произвольную перестановку томов. Разобьем циклы, входящие в эту перестановку на (1)-циклы, группы циклов, в сумме охватывающие ровно k томов (будем называть их k-группы), и остальные циклы (по отдельности). Введем "полуинвариант A" для такого разбиения: утроенное количество (1)-циклов плюс удвоенное количество k-групп. Заметим, что своим ходом Вася может уменьшить этот полуинвариант не более чем на 6k-3, причем ровно на 6k-3 он может его уменьшить лишь склеив 2k-1 (1)-цикл в несколько независимых циклов, в сумме затрагивающих 2k-1 томов, эту изощренную форму Васиного сопротивления назовем "операция Ы". Библиотекарь может увеличить этот инвариант на 6k-3, если выберет насколько "остальных" циклов в сумме затрагивающих не меньше 2k томов и разобьет их на 2k-1 (1)-цикл и несколько еще каких-то циклов, назовем такое действие "ответный ход". Если Вася не хочет, чтобы полуинвариант A увеличивался, он после каждого "ответного хода" всегда должен выполнять операцию Ы. Результатом такой пары ходов является образование группы циклов, суммарно затрагивающих 2k-1 том. Пусть теперь библиотекарь выполнит еще один ответный ход, не затрагивая эту свежеобразованную группу циклов. После очередной операции Ы возникнет еще одна такая группа циклов. В этот момент библиотекарь получает возможность проделать следующую "ключевую" операцию, увеличивающую полуинвариант на 6k-2: библиотекарь превращает эти два набора циклов в 2k-2 (1)-циклов и две k-группы. Таким образом, библиотекарь сможет увеличивать полуинвариант A до тех пор, пока не возникнет "острая" ситуация, когда перед ходом библиотекаря все множество томов, за исключением 4k-3 томов, разбито на (1)-циклы и k-группы.
Рассмотрим теперь еще один полуинвариант (полуинвариант B): сумма количества k-групп и удвоенного количества (1)-циклов. Пусть при возникновении острой ситуации библиотекарь разбивает две k-группы на 2k (1)-циклов, увеличивая при этом B на 4k-2. Заметим, что своим ходом Вася не может уменьшить B более чем на 4k-2, и, кроме того, не может уменьшить количество (1)-циклов больше чем на 2k-1. Следовательно, библиотекарь может увеличивать количество (1)-циклов, не уменьшая B, до тех пор, пока количество k-групп перед ходом библиотекаря не станет равно 1 или 0. Сколько же в этот момент у нас имеется (1)-циклов? Так как B в начальный момент времени был не меньше чем (S-(4k-3))/k и с тех пор не уменьшился, то количество (1)-циклов в этот момент времени не меньше, чем (S-(5k-3))(2k)>(S/(2k))-3. Следовательно, после хода библиотекаря их будет не менее чем (S/(2k))+2k-4.
з) Утверждение неверно. Действительно, как мы уже выяснили, P(3,4)=28 при S=100, если же S=101, то согласно решению пункта е) Вася может действовать так, что после его хода количество (3)-циклов будет не меньше количества (1)-циклов. Следовательно, если после хода Васи оказалось 25 (1)-циклов, то должно быть не менее 25 (3)-циклов, что невозможно, а если после хода Васи оказалось 24 (1)-цикла, то в (1)- и (3)-циклах вместе содержится 96 или 99 томов, и значит, нет ни (4)-цикла, ни двух (2)-циклов, и библиотекарь не сможет своим ходом довести количество томов на своих местах до 28.
3. а) Ответ: 1. Вася делает один (S)-цикл, после хода библиотекаря образуется два цикла, которые Вася сможет снова склеить в один цикл.
б.1.) Ответ: 2/3. Пока на своих местах стоит меньше половины томов, Вася ничего не делает. В противном случае найдутся два соседних тома, стоящих на своих местах, и Вася их переставит. В результате такой стратегии разность количеств (1)-циклов и (2)-циклов не будет увеличиваться. Мы приведем несложное доказательство более сильного результата: библиотекарь не сумеет поставить на свои места больше половины томов (точнее, больше [(S+1)/2]+2 томов).
В самом деле, пусть Вася следит за нечетными циклами. Как только два тома из разных нечетных циклов оказываются рядом, Вася их переставляет, уменьшая количество нечетных циклов на 2. Заметим, что библиотекарь не может увеличить общее количество нечетных циклов более чем на 2, а если нечетных циклов больше чем [(S+1)/2], то найдутся два соседних тома, принадлежащие разным нечетным циклам. Поэтому библиотекарь не сможет построить больше [(S+1)/2]+2 нечетных циклов, в частности, не сможет поставить больше [(S+1)/2]+2 томов на свои места.
Второе неравенство следует из пункта б.2).
б.2) Хорошая задача. Докажем, что библиотекарь сможет поставить на свои места не менее S/5 томов, никакие два из которых не являются соседними. Пусть в какой-то момент библиотекарю удалось поставить на свои места k томов, среди которых нет соседних, эти тома назовем основными. Пусть k < S/5. Проверим, что библиотекарь сможет увеличить в этом случае количество основных томов. Назовем места, соседние с основными томами, и тома, которые должны стоять на этих местах, плохими. Остальные тома и места, на которых они должны стоять, назовем хорошими. Если Вася своим ходом не переставляет ни одного основного тома, то очевидно, что на следующем ходу библиотекарь сможет добавить еще один основной том. Пусть Вася поменял местами основной том с хорошим (стоящим, по определению, на плохом месте). Тогда библиотекарь ставит эти основной и хороший тома на свои места, переставляя также том, занимавший место хорошего, на освободившееся место. Таким образом, библиотекарь получает еще один основной том. Осталось разобрать случай, когда Вася все время переставляет основной том с плохим. Заметим, что хотя бы один хороший том стоит на хорошем месте. Действительно, около k основных томов находится не более 2k плохих мест, следовательно, имеется не менее S-3k > 2k хороших томов, что больше числа плохих мест. Библиотекарь теперь делает следующую перестановку: он ставит основной том на место, найденный хороший том - на плохое место, а оставшийся том - на освободившееся хорошее место. Такая стратегия позволяет библиотекарю увеличивать число хороших томов, стоящих на плохих местах. Через некоторое время все плохие места будут заняты хорошими томами, и Вася, как было доказано выше, предоставит библиотекарю возможность увеличить число основных томов.
в.1) Не нужно гнаться за большими a, b. Следует наметить весьма скромную цель и держаться за нее.
Назовем перспективными места, номера которых делятся на n, и тома, которые должны стоять на этих местах. Библиотекарь за один ход может поставить два перспективных тома на свои места, а Вася может передвинуть не более одного стоящего на перспективном месте. Значит, библиотекарь может поставить все перспективные тома на свои места, то есть, утверждение задачи верно при a=1/n, чрезмерно придирчивый читатель может считать, что нумерация томов начинается с нуля.
в.2) Аналогично предыдущей задаче, Вася может добиться того, чтобы каждый k-й том стоял не на своем месте.
4. а) Вася может реализовать стратегию из задачи 2.б (при нечетных S Вася следит за тем, чтобы не более одного тома стояло на месте своей четности).
б) Ответ: 2. Нетрудно проверить, что библиотекарь сможет поставить на свои места второй и третий тома энциклопедии.
в) Как и в задаче 3.в.2), Вася может добиться того, что тома с номерами, делящимися на k, не стоят на своих местах.
г) Назовем ценными тома и места с номерами, делящимися на 3n. Будем называть ценный том важным, если он стоит на своем месте; полезным, если он находится не на своем месте, но на расстоянии не более n-1 от него; места, находящиеся на расстоянии больше n-1 от ближайшего ценного места, назовем "нейтральной зоной". Если Вася своим ходом ставит полезный том в нейтральную зону, то библиотекарь ставит этот том на свое место. Поскольку Вася не может за один ход переставить важный том в нейтральную зону, то через некоторое время Вася будет вынужден сделать ход, не меняющий суммарного количества важных и полезных томов. В этом случае библиотекарь получает возможность сделать "свободный ход": он выбирает ценный том, пока еще не являющийся ни важным ни полезным, и сдвигает его в по направлению к своему месту так, чтобы он оказался в нейтральной зоне, либо на своем месте (если это возможно). Если Вася своим ходом переставляет выбранный том (скажем, вместе с каким-нибудь полезным), то библиотекарь может своим ходом поставить этот полезный том на свое место, а выбранный переставить в следующую нейтральную зону. Проделывая подобные операции, библиотекарь сумеет поставить выбранный том на место. Таким образом, библиотекарь добьется того, что все ценные тома будут важными или полезными. Теперь библиотекарь в каждый свободный ход может два "соседних" полезных тома сделать важными. Значит, a>1/(6n).
5. а), б) Пусть S > 5k2 и к тому же четно. Первые S/2 мест,
а также оставшиеся S/2 мест будем называть зонами. Пусть в начале Вася расставит
тома так, чтобы каждый том находился в "чужой" для него зоне. Расстояние от
каждого тома до чужой для него зоны назовем энергией этого тома (читатель
догадался, что в начале энергия всех томов равна нулю). Каждым своим ходом
библиотекарь может увеличить суммарную энергию всех томов не больше чем на
2k2. Пусть Вася каждым своим ходом меняет местами тома, наиболее
далеко "продвинувшиеся" в свои зоны. Если в после хода библиотекаря суммарная
энергия всех томов (впервые) стала больше, чем
2*(1+2+...+ (2k2-1))=2k2(2k2-1)=M,
то Вася уменьшит ее не менее чем на 2k2, и тем самым сделает ее
снова меньше M. Таким образом, библиотекарь не сумеет поставить на свои места
больше, чем 4k2+k томов. Читатель с необычайной легкостью
модифицирует эту конструкцию на случай нечетного S.
Замечание. При описанных действиях ни один из томов не может иметь энергию больше M+k.
в) Пусть S > 16k4 и делится на 4. Разделим все места на четыре равные зоны - A, B, C и D (в зону A входят тома с номера 1 по номер S/4, в зону B - с номера S/4+1 по номер S/2 и т. д. Пусть вначале тома, которые должны стоять в зоне А, Вася поставит в зону C, тома, чье место в зоне C, он поставит в зону A, и, аналогично, поменяет местами тома из зон B и D. В силу замечания Вася может действовать так, что каждый том будет находиться либо в исходной чужой зоне, либо в соседней с ней. Значит, ни один из томов никогда не попадет на свое место.