Высшая проба 2025, 8 класс, задача 2
( баллов) Квадрат состоит из четырёх ячеек. В каждой ячейке изначально записана единица. За один ход можно сделать одно из двух действий. Первое возможное действие: можно выбрать верхнюю или нижнюю строку и любые числа и , каждое из которых не меньше и не больше , а затем умножить левое число в выбранной строке на , а правое — на (числа и не обязаны быть различными). Второе возможное действие: можно выбрать верхнюю или нижнюю строку и заменить ею оставшуюся. Какое минимальное число ходов потребуется, чтобы получить набор чисел , записанный в ячейках так, как на верхнем рисунке?
(Средний рисунок — пример первого действия: в нижней строке числа и умножены на числа и . Нижний рисунок — пример второго действия: нижняя строка заменена на верхнюю.)
Ответ. операций.
Решение. Пример. Начинаем действия над первой строкой: ; ; ; копия из первой строки во вторую; ; . Далее проводим действия над второй строкой: ; ; . Итого операций.
Другой вариант. Начинаем действия над первой строкой: ; ; ; ; копия из первой строки во вторую; ; . Далее проводим действия над второй строкой: ; . Итого операций.
Оценка. Для получения числа во второй строке нужно не меньше первых действий (умножений). Кроме того, если копирований не было, то необходимо ещё не менее пяти умножений, чтобы получить , итого без копирований необходимо не менее действий. Значит, копирований минимум одно, и действий уже . Покажем, что при этом можно обойтись не более чем одним копированием: если после копирования из первой строки во вторую происходит ещё одно копирование из первой строки во вторую, то все промежуточные операции (сделанные во второй строке между этими копированиями) никак не влияют на конечный результат. Значит, можно удалить первое копирование и все эти операции — количество действий не увеличится. Если после копирования из первой строки во вторую происходит копирование из второй строки в первую, то все промежуточные операции можно сделать в первой строке (вместо второй), а потом сделать копирование из первой строки во вторую — конечный результат и количество действий не изменятся.
Вернёмся к оценке. Рассмотрим момент, когда мы сделали копирование. Тогда после копирования в первой ячейке каждой строки у нас число, не превосходящее , а во второй — не превосходящее . Пусть до копирования мы делаем действий, после копирования в верхней строке делаем действий, а в нижней — . Тогда (чтобы получить ), а , так как из необходимо получить . Итого действий должно быть не менее $k + l + m + 1 \geqslant
Верное решение.
Приведен пример с оценкой только на количество действий для получения числа 64.
Приведен пример без оценки.
Приведена только оценка на количество действий для получения числа 64.
Решение не соответствует ни одному из критериев выше.