Закл 2019

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

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

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

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

Положим тогда Поскольку все коэффициенты многочлена целые, из следует Отсюда непосредственной индукцией по получаем, что то есть при всех

______________________________________________________________________________________________________________________________________________________

Лемма. делится на

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

Если не делится на то по теореме Эйлера откуда Если же делится на то делится на а значит, и тоже. В любом случае делится на что и требовалось.

_________________________________________________________________________________________________________________________________________________________________________________

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

при бесконечном количестве целых значений (где ).

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

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

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

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

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

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