Регион 10 класс → .11 Регион 2024

Заметим, что

причем равенство достигается только при Тогда первое слагаемое

То же верно и для других слагаемых. Значит, левая часть уравнения Сергея не превышает причем равенство достигается лишь при равенстве всех переменных значит, равенство невозможно для различных

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

Видим, что

удовлетворяет условию. Далее будет доказано, что других ответов нет.

1) Предположим, что

делится на где

это следует из условия, если дополнительно предполагать, что различны.

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

и аналогично

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

Далее, и поэтому может делиться на только в случае и т.е в случае

Аналогично, может делиться на только при

2) Пусть какие-то два из трех чисел совпадают, скажем, Тогда

Значит, либо либо Первый случай возможен лишь при иначе

— составное число, что дает противоречие. Значит, в любом случае среди присутствует единица, скажем,

Тогда наши данные простые числа — это и и они должны быть делителями

Если хотя бы одно из чисел больше 1, то и на обязан делиться хотя бы один из сомножителей и А поскольку разность

делится на получаем, что оба числа делятся на Тогда если отлично от то делится на что разобрано в случае

Остается вариант

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

Случай уже был ранее. Если то — нечетное простое, значит должно делиться на Отсюда

должно делиться на Но это невозможно, так как

и — простое.

Оценка. Людей обозначим вершинами, номер вершины будет означать ответ соответствующего человека, а если пара людей дружит, то проведем ребро между соответствующими вершинами.

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

Оценим количество ребер между людьми из разных множеств и

С одной стороны, не больше суммы степеней вершин множества откуда

С другой стороны, из каждой вершины множества не более ребер идет в вершины множества и значит, не менее ребер идет в вершины множества Отсюда

Получаем неравенство:

откуда Это означает, что всего лжецов не менее

Пример. Как и прежде, номер человека будет означать его ответ. Возьмем два множества людей:

и

Пусть в множестве никакие двое людей не дружат друг с другом, а в множестве — любые двое дружат. Далее, пусть человек и дружат тогда и только тогда, когда Тогда у человека всего друг:

У человека будет всего друзей:

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