Логические и комбинаторные рассуждения на Курчатове

Возьмём произвольное слово длины 20 и будем последовательно передвигать в нем буквы A, не уменьшая при этом крутизну слова. Ясно, что в нашем слове должно быть хотя бы две буквы B, иначе крутизна слова равна 0. Далее, предположим, что в слове между двумя буквами В есть буква А, т.е. слово имеет вид …В … …В …Посмотрим, с какой стороны от буквы больше букв А, и передвинем выделенную букву в тот конец слова, где их меньше. Заметим, что при таком перемещении буквы А мы могли разрушить лишь слова вида ABBA и ABBA, которые давали вклад в размер крутизны исходного слова. Предположим, что мы переместили букву К налево. Тогда слова вида BBA сохранились, а вместо слов вида ABB , образованных буквой В слева от и двух букв В и буквы , мы получим как минимум столько же слов, которые образуются из нашей передвинутой буквы , двух любых букв У и любой буквы А, которая стояла в исходном слове справа от буквы А. Получается, что мы можем рассматривать только слова вида А...АВ...ВА...А. Если в левом блоке будет букв А, а в правом букв А, то крутизна такого слова равна .

Заметим, что при фиксированной сумме произведение будет максимальным, если числа и отличаются не больше чем на 1: в противном случае, если, например, , то переместим одну букву из левого блока в правый, и крутизна изменится на

Таким образом, можно считать, что или , причем (иначе в нашем слове не будет или букв А, или букв В). Теперь возьмем слово, в котором , и заменим последнюю букву В на букву А. При такой замене крутизна слова изменится на величину

Значит, при крутизна слова после такой замены увеличивается, а при уменьшается. Аналогично, посмотрим, что произойдёт, если в слове, в котором , заменить первую букву В на букву A:

Получается, что при крутизна слова после такой замены увеличивается, а при - уменьшается. Значит, мы можем последовательно совершать такие замены, сводя величину к значению 5 и увеличивая в процессе крутизну. В итоге, наибольшая крутизна будет у слова, в котором , и равна она .

Замечание.

Последнюю часть решения можно провести по-другому. А именно, рассмотрим крутизну слова, в котором , как функцию от . Вычислим ее производную: . Нас интересует натуральная точка из отрезка , которая наиболее близка к нулю этой производной. Поскольку , в качестве такой точки необходимо выбрать число , что и приводит нас к примеру. Аналогичные вычисления для случая также дают значение , но крутизна такого слова оказывается меньше.

Пусть - итоговое шестизначное число. Пусть также и . Заметим, что если Боря своим третьим ходом поставит цифру из множества , Аня выиграет, поскольку полученное число будет делиться на 2 . Значит, .

Пусть Аня первым ходом выберет цифру , а вторым ходом - цифру 9. Если Боря на первом или втором ходу выберет цифру из множества , то своим третьим ходом Аня заберет последнюю оставшуюся цифру из множества , и Боря вынужден будет взять свою цифру из , что приведет к его проигрышу. Значит, Боря вынужден взять первые две свои цифры и взяты из множества . Заметим, что Боря вынужден будет на последнем ходе выбрать либо цифру 1 , либо цифру 7 , которые дают одинаковый остаток 1 при делении на 3. Поэтому Ане достаточно подобрать цифру так, чтобы сумма цифр давала бы остаток 2 при делении на 3 . Поскольку и не влияют на остаток этой суммы, все зависит от остатка суммы . Покажем, как действовать Ане в каждом из случаев.

Если делится на 3 , то Аня выберет цифру из набора : поскольку до этого момента эти цифры мог выбирать только Боря, как минимум одна из этих трех цифр останется не выбранной.

Если дает остаток 1 при делении на 3 , Аня выберет цифру . Как мы помним, Боря не мог ее выбрать на первых двух ходах.

Наконец, если дает остаток 2 при делении на 3 , Аня выберет цифру из набора . Боря не мог выбрать обе эти цифры, поскольку тогда , а мы предположили, что дает остаток 2 при делении на 3 .

Таким образом, Аня выиграет.

Пусть выбрано отрезков. Докажем утверждение методом математической индукции по

1.

База: Для одного отрезка просто отметим его правый конец.

2.

Переход: Пусть мы можем так отмечать для отрезков. Докажем, что мы сможем так сделать для отрезков. Для этого рассмотрим отрезок, у которого конец находится правее всех концов других отрезков. Далее «забудем» про этот отрезок, и для оставшихся отрезков применим предположение. Теперь «вспомним» отрезок. Если он содержит нечетное число отмеченных точек, то мы смогли отметить точки нужным образом. Если же это не так, то дополнительно отметим его конец, так как он самый правый, то остальные отрезки его не содержат и мы получим требуемое.

Рассмотрим любую четвёрку подряд идущих людей. Если бы в ней было хотя бы 3 рыцаря, то самый первый из рыцарей точно сказал бы неправду, что невозможно. Если бы в ней было хотя бы 3 лжеца, то самый первый из лжецов точно сказал бы правду, что тоже невозможно. Значит, в каждой четвёрке подряд идущих людей ровно 2 рыцаря и ровно 2 лжеца. Разбив всех людей на 15 таких четвёрок, получаем, что рыщарей .

Для каждой карточки рассмотрим другую, дополняющую её до полного набора(например, для карточки такой карточкой будет ). Ясно, что все карточки разбиваются на непересекающихся пар карточек, дополняющих друг друга до полного набора. Далее мы докажем, что в любом искомом наборе обязательно есть ровно по одной карточке из каждой такой пары, т. е.

Из условия следует, что максимум одна карточка из пары может быть среди выбранных, иначе уже есть полный набор. Теперь покажем, что из каждой пары должна быть хотя бы одна карточка. Рассмотрим пару дополняющих друг друга карточек, обозначим их и Предположим, что они обе не входят в выбранный набор. По условию при добавлении любой карточки из колоды найдётся полный набор. Добавив в набор мы найдём несколько карточек, дополняющих до полного набора, т. е. все цифры на этих карточках просто совпадают с множеством цифр на карточке . Аналогично, добавив карточку , мы найдём несколько карточек из набора, цифры на которых совпадают с множеством цифр на карточке Тогда объединим все эти карточки (которые совпадают с наборами на карточках и ) и получим полный набор, противоречие.

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

Проведём диаметров нашего -угольника. Нам требуется разбить их на пары так, чтобы в каждой паре было поровну чёрных и белых вершин. Для этого необходимо и достаточно, чтобы полностью чёрных диаметров было столько же, сколько и полностью белых. Действительно, если это не так, то один из таких диаметров останется без пары — ему не подойдут разноцветные диаметры. Если же это так, то мы бьём все одноцветные на пары с одинаковыми цветами, после чего остальных останется чётное количество (всего диаметров ) и их можно разбить как угодно.

Итак, почему же чёрных диаметров столько же, сколько и белых? Каждый разноцветный диаметр содержит одинаковое количество белого и чёрного цвета, потому на одноцветные приходится также равное количество этих двух цветов (изначально каждого по ). Но раз так, то количество чёрных и белых диаметров будет одинаковым, чтобы они содержали равное количество разных цветов, что и требовалось.

Поскольку в каждый из дней более половины жителей Цветочного города ели мороженое, то есть человек, который ел мороженое более чем в половине из этих дней, то есть в хотя бы Возьмем его в искомую десятку. Осталось не более дней. Проделаем ту же процедуру: найдем человека, который ел мороженое более чем в половине из этих дней (хотя бы в ), возьмем его в качестве второго человека из искомой десятки. Осталось не более дней. Продолжим в том же духе. После выбора -го человека останется не более дня, после выбора -го — не более дней, после выбора -го — не более после выбора -го — не более после выбора -го — не более после выбора -го — не более после выбора -го не более Для оставшихся двух дней существует человек, который ел мороженое более чем в половине из этих двух дней, то есть в оба. Возьмем его -м.

Оценим количество троек школьников, не справившихся с первой задачей. Эту задачу не смогли решить школьников или меньше, а значит число таких троек не превосходит . Раз задач всего , то число троек школьников, не осиливших какую-то задачу, не превосходит . С другой стороны, всего существует троек школьников, что больше. Значит, найдутся три школьника, решивших в объединении все задачи.

Будем менять группы монет с разных чаш. Пусть у нас при каждой из следующих замен равновесие сохраняется. Поменяем по одной монете. Они одинаковы. Поменяем одну из этих монет с новой. Теперь три монеты одинаковы: пара на одной и одна — на другой чаше. Поменяем эту пару с парой еще нетронутых. Теперь на одной чаше пара одинаковых, на другой — тройка таких же монет. Поменяем тройку с тройкой нетронутых. Теперь на одной чаше тройка одинаковых монет, на другой — пять таких же монет. Продолжая в том же духе, после k-го шага получим на одной чаше одинаковых монет, а на другой — таких же монет, где — i-ое число Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144. Итак, после 11-го шага на одной из чаш все монеты одинаковы. Но тогда они таковы же и на другой, что по условию невозможно.