Применение классических комбинаторных методов к разным задачам → .02 Упорядочивание

Рассмотрим какую-нибудь полку. Пусть на ней в некотором порядке стоят тома с номерами Пусть их порядковые номера на полке равны соответственно Инвариантом в этой задаче будет то, что том, стоящий в ряду на -м месте, будет всегда иметь тот же самый порядковый номер на полке. Это связано с тем, что при замене тома номер нового в ряду окажете в том же месте, в котором был номер старого, потому что они соседние. Значит, если том “Письма, часть ” окажется на верхней полке, то он будет там самым левым, что и требовалось.

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

Отсортируем числа из множества по возрастанию:

Для любых трех последовательных чисел число по условию лежит в . Но

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

По условию числа , то есть , где - разность прогрессии.

и в силу того, что , а натуральное. Имеем единственное решение .

Расположим наши числа по убыванию, Имеем

Умножим первое равенство на получим, что

Следовательно,

Сперва докажем следующую лемму.

Лемма. В ряд лежат апельсинов, массы любых двух соседних отличаются не более, чем на г. Тогда если упорядочить апельсины по убыванию массы, то массы любых двух соседних снова будут отличаться не более, чем на г.

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Данное утверждение верно для чисел при любом и доказывается «от противного».

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

где

При четном получаем

значит, разность и не содержится среди остальных чисел.

При нечетном надо рассмотреть пары Для них

при и потому должны выполняться равенства

в частности

что также приводит к противоречию.

Поскольку среди любых 100 карандашей есть хотя бы 7 разных цветов, то в любой шестёрке цветов карандашей суммарно не больше 99 (иначе можно взять 100 карандашей только среди этих шести разных цветов, а по условию обязательно должен найтись седьмой).

Обозначим количества карандашей разных цветов за

Если то получаем противоречие с выводом выше. Значит,

Тогда суммарно в коробке карандашей

Может ли быть ровно 1603 карандаша? Да, например, если было 19 карандашей одного цвета ( и по 16 карандашей всех остальных цветов (

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

1)
Тогда ни один юноша с ростом не сможет танцевать ни с одной девушкой с ростом Но тогда последние юношей могут танцевать не более с чем девушками, противоречие.

2)
Тогда ни один юноша с ростом не сможет танцевать ни с одной девушкой с ростом Но тогда первые юношей могут танцевать не более с чем девушками, противоречие.

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

Разложим коробки от меньшей к большей. Предположим, что в третьей с начала коробке меньше 10 фигурок. Тогда всего в первых трех коробках не больше фигурок — противоречие. Значит, в третьей коробке хотя бы 10 фигурок. Аналогично показывается, что третья коробка с конца содержит не больше 15 фигурок(). Предположим, что эта коробка содержит 14 фигурок или меньше. Тогда суммарное количество фигурок в коробках, отличных от первых трёх и последних трёх, не превосходит , а должно быть . Противоречие. Значит, в третьей с конца коробке ровно 15 фигурок. Тогда в самой большой коробке может быть либо 18 (), либо 19 () фигурок. Больше 19 фигурок быть не может, потому что тогда во второй по величине коробке фигурок не больше, чем а в ней хотя бы 16 коробок. Меньше 18 быть не может, так как тогда фигурок в трех самых больших коробках не больше, чем Оба ответа подходят: (7,8,10,11,12,14,15,17,18) и (7,8,10,11,12,14,15,16,19).

Решение

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

Пусть утверждение задачи неверно: для некоторого . Это означает, что до перестраивания по росту солдат мог стоять только перед одним из солдат . То же справедливо и для солдат , поскольку они не ниже солдата . Итак, до перестраивания шеренг солдат могли стоять только перед солдатами . Противоречие.

Упорядочим числа по возрастанию. Если два самых больших числа и () оба положительные, то их сумма которая больше максимального числа ( должна быть тоже на доске. Значит, на доске не больше одного положительного числа.

Аналогично поймем про отрицательные числа. Если два самых маленьких и ( числа оба отрицательные, то их сумма которая меньше минимального числа ( должна быть тоже на доске. Значит, на доске не больше одного отрицательного числа.

Получили оценку: на доске не более двух ненулевых чисел.

Пример на ровно два ненулевых числа простой: и нулей. Все условия задачи в нем выполняются.

Условие выполняется для произвольных девяти чисел, и нам ничего не мешает считать их упорядоченными по возрастанию: . Тогда нам достаточно доказать положительность . Применим условие для тех четырёх чисел, для которых оно “наименее вероятно”, то есть для самых больших четырёх чисел — условие-то всё равно будет выполняться, но мы получим из этого самую классную информацию!

При этом , , , . Тогда при мы ещё уменьшим правую часть, и она будет меньше левой — противоречие. Значит, всё-таки .

Упорядочим коробки по количеству карандашей . Хочется начинать с коробки, где карандашей меньше всего. Почему? Если мы начнем с коробки, где карандашей много, то можем случайно взять тот цвет, который лежит в коробке, где карандашей мало. В коробке есть хотя бы один карандаш, берем любой. В коробке карандашей хотя бы два и все разного цвета, поэтому найдется карандаш, отличный от того, который мы взяли. Те же самые рассуждения работают и дальше: на -ом шаге в коробке хотя бы карандашей разного цвета, мы взяли только карандаш из предыдущих коробок, поэтому можем взять карандаш из коробки , отличный по цвету от ранее взятых. Значит, из каждой коробки можно выбрать по карандашу так, что все они будут разных цветов.

Комментарий Старайтесь, когда пишите решение, избегать слов «и так далее», формализируйте свои рассуждения.

Упорядочим числа по возрастанию. Рассмотрим все разностей соседних чисел (из большего вычитаем меньшее). Предположим, что среди них нет двух одинаковых. Заметим, что разность самого большого числа и самого маленького не превосходит но она равна сумме наших разностей. При этом по нашему предположению у нас не более разностей равны не более двух разностей равны и так далее. Тогда сумма наших разностей не меньше, чем

откуда получаем противоречие.

(a) Упорядочим отмеченные числа по возрастанию и обозначим их через (в порядке возрастания). Заметим, что не меньше как минимум чисел в каждой строке (поскольку не меньше любого другого отмеченного числа, которое является вторым по величине в своей строке). Поэтому Рассмотрим строку, в которой стоит Сумма чисел в этой строке не превосходит

поскольку первое по величине число в этой строке не больше остальные строго меньше и все различны. С другой стороны, сумма отмеченных чисел больше, чем

поскольку То есть мы получили, что сумма отмеченных чисел не меньше суммы чисел в строке, в которой стоит

(b) Упорядочим отмеченные числа по возрастанию и обозначим их через (в порядке возрастания). Заметим, что не меньше как минимум чисел в каждой строке (поскольку не меньше любого другого отмеченного числа, которое является третьим по величине в своей строке). Поэтому Аналогично, не меньше как минимум чисел в каждой строке, кроме строки с Тогда

Рассмотрим строку, в которой стоит Сумма чисел в этой строке не превосходит

поскольку первое по величине число в этой строке не больше второе не больше остальные строго меньше и все различны. С другой стороны, сумма отмеченных чисел равна

поскольку То есть мы получили, что сумма отмеченных чисел не меньше суммы чисел в строке, в которой стоит

Покажем, что среди данных чисел не может быть больше четырёх попарно различных чисел. Объединим равные числа в группы, выберем в каждой группе по одному числу и расположим выбранные числа в порядке убывания Числа по условию образуют геометрическую прогрессию, поэтому откуда Те же самые рассуждения показывают, что противоречие. Из доказанного следует требуемое.

Пусть это не так: есть яблоко веса а следующий вес больше Покрасим яблоки с весом не больше в жёлтый цвет, а яблоки с весом больше — в оранжевый. В исходной расстановке два яблока разных цветов должны лежать рядом, значит, разность их весов не меньше Противоречие.

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

Упорядочим баллоны по весу: Баллоны с нечётными индексами поместим в первый грузовик, баллоны с чётными — в другой. Заметим, что

Тогда понятно, что Таким образом, мы поняли, что больше разности загруженностей грузовиков. Пусть искомая разность равна Разделим на баллон весом и Баллон весом переложим во второй грузовик. Получили искомое распределение весов.

Выложим яблоки по неубыванию масс. Из восьмой задачи понятно, что массы соседних яблок по-прежнему отличаются не больше, чем на грамм. Занумеруем яблоки по неубыванию масс Рассмотрим следующий ряд пар: В нём массы двух соседних пакетов и отличаются на

а с другой стороны

Получили, что модуль разности весов не превосходит что и требовалось доказать.