Высшая проба - задания по годам → .09 Высшая проба 2023

Пойдём от противного, предположим, что такое возможно. Без ограничения общности можно считать, что число 1 покрашено в красный. Выберем произвольное число покрашенное в синий. Заметим, что тогда должно быть зелёного цвета, — синего, — зелёного и т.д. Таким образом, все числа, большие покрашены в синий или зелёный цвет. С другой стороны, так как покрашен в синий цвет, a — в зелёный, то число должно быть покрашено в красный цвет, противоречие. Значит, такое невозможно.

В данных выражениях умножим числители и знаменатели на соответственно (согласно условию, эти разности ненулевые). Получим те же числа в другом виде:

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

Это симметричное равенство, поэтому теперь можно просто поменять местами две переменные (например, и и проделать те же переходы в обратном порядке, получив равенство третьего и второго чисел:

Деления при этом корректны, так как выражения-делители уже фигурировали ранее в знаменателях, и мы знаем, что они не равны нулю.

Воспользуемся алгоритмом Евклида для получим

Заметим, что, так как НОД двух натуральных чисел не превосходит каждое из них,

Аналогично получаем, что

А также

Складывая эти три неравенства, получаем

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

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

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

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

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

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

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

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

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

Тогда у корнями будут числа 0 и 3; у корнями будут числа -1 и 2; у корнями будут числа -1, 0, 1, 2; у корнями будут числа -1, 1, 2, 4. Итого корни всех многочленов в совокупности: -1, 0, 1, 2, 3, 4.

Оценка. Приведём пример ситуации, в которой 4 дней не хватит. Пусть у каждого из 45 людей будет своя, не совпадающая с другими людьми, пара дней, в которые он не может участвовать во встрече. Так как количество способов выбрать пару дней из 10 предложенных равно , то для любой пары дней найдётся человек, который не может присутствовать ровно в эту пару дней. Предположим, что мы смогли выбрать какие-то 4 дня так, чтобы каждый узнал все новости. Но тогда существует человек , который не может присутствовать в первые два дня из этих четырёх, а также человек , который не может присутствовать в последние два из этих четырёх дней. Заметим, что тогда не сможет узнать новостей . Противоречие.

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