Применение классических комбинаторных методов к разным задачам

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

В разрядах могут стоять как максимум цифры 2, 9, 5, 9 соответственно. Однако, если первая цифра равна 2, то вторая не больше 3, и получается как максимум . Значит, в точности не достижимо, а вот число на 1 меньше мы уже получать умеем: 19:59 даёт сумму 24.

Для начала отметим, что жадность здесь не работает! Казалось бы, мы хотим, чтобы число содержало как можно меньше разрядов. Поэтому надо начать с 777, но тогда остается сумма 4, которую нельзя представить одной цифрой, являющейся простым числом. Поэтому будем решать задачу по-другому.

Сначала докажем, что в числе не может быть 4 или менее знаков. Трёх точно не хватит, так как максимальная сумма цифр . Далее рассмотрим четырёхзначные числа. Так как 25 — нечётное число, то 4 цифры не могут быть нечётными. Поэтому как минимум одна цифра равна 2, и тогда сумма оставшихся равна 23, и тремя цифрами, не превосходящими 7, её не получить.

Итак, в числе как минимум 5 знаков. Заметим, что 22777 подходит. При этом числа с одинаковым количеством разрядов мы сравниваем по цифрам слева направо, и цифра 2 — минимально возможная. Поэтому все числа, начинающиеся не на 22, будут больше нашего примера. Оставшиеся цифры равны по 7, так как сумму 21 можно получить только с помощью трёх семёрок.

Пронумеруем все строчки и все столбцы числами от 1 до 100. Тогда нам нужно попасть из клетки (1, 1) в клетку (100, 100). За каждый ход коня одна координата меняется на 1 (+1 или -1), а вторая на 2 (+2 или -2). Будем жадно прыгать к клетке (100, 100). Сначала в клетку (2, 3), потом в (4, 4). Будем продолжать такие прыжки по 2. Тогда получим последовательность клеточек:

(1, 1) -> (4, 4) -> (7, 7) -> …-> (3k + 1, 3k + 1) -> (3(k + 1) + 1, 3(k + 1) + 1) -> ...

Заметим, что закончим мы именно в клетке (100, 100), так как мы побываем на всех клетках вида (3k + 1, 3k + 1), а число 100 представляется в таком виде (дает остаток 1 при делении на 100).

Нам понадобилось ходов.

Проверим оценкой, что наш жадный алгоритм дал лучший результат. За один ход коня сумма координат клетки меняется не более, чем на 3. Тогда, чтобы из суммы 2 получить сумму 200, нужно как минимум ходов.

Сумму всех чисел таблицы можно посчитать двумя способами, и оба способа должны давать одинаковый ответ. Однако по строкам получаем , а по столбцам — .

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

Ничья взаимна (если A сыграл вничью с B, то B сыграл вничью с A). Пусть за ничью каждый получает по очку. Тогда суммируя эти очки по всем играм вничью, получим четное число (за каждую игру отдаем 2 очка), а по игрокам — нечетное (). Получили противоречие.

Решение

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

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

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

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

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

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

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

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

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

Рассмотрим трёх грибников, собравших вместе максимальное (среди всевозможных троек грибников) количество грибов. Если минимальное (из этих трех) количество грибов не меньше 16, то вместе три грибника собрали грибов не меньше, чем Если указанное минимальное количество не больше 15, то оставшиеся четыре грибника собрали вместе не более грибов. Отсюда заключаем, что первые трое собрали вместе не менее 50 грибов.

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

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

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

Будем действовать по индукции по количеству ладей на доске. База для одной ладьи очевидна.

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

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

Посмотрим, где стоят числа 1 и 64. Заметим, что между этими клетками есть путь, проходящий по соседними по стороне клеткам, имеющий длину не более 14. Предположим, что в любой паре соседних клеток числа отличаются не больше чем на 4. Тогда пройдя по пути от 1 до клетки, где стоит 64, мы получаем, что число в данной клетке не больше, чем — противоречие.

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

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

Заметим, что максимальная возможная сумма 29 чисел это , а минимальная возможная сумма 71 числа это . Значит сумма 71 числа всегда будет больше.