Эйлер 2024/25 · Математика · 8 кл., №1 — решение

Условие

Квантовый компьютер расходует $1$ кВт/ч электроэнергии на каждую сделанную им операцию умножения или сложения. При этом он умеет хранить результаты промежуточных действий. Докажите, что для любых пяти хранящихся в компьютере чисел $a$ $b$ $c$ $d$ $e$ можно найти сумму $ab+ac+ad+ae+bc+bd+be+cd+ce+de$ , затратив не более $10$ кВт/ч.

О задаче · 8 класс

Олимпиада: Олимпиада имени Леонарда Эйлера, XVII олимпиада
Этап: Дистанционный этап, I тур
Предмет / класс: Математика · 8 класс
Дата: дата тура не указана в файле заданий

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

Здесь ответ — доказательство: нужно предъявить способ счёта из сложений и умножений и объяснить, почему он даёт нужную сумму при любых числах и укладывается в $10$ кВт/ч. Свою программу можно собрать и проверить в модели «Напиши программу».

Записать идею

Личный черновик для заметок и расчётов. Он никуда не отправляется и не проверяется.

Исследуй задачу

Самостоятельное исследованиеНапиши программу

Пробуй свои варианты. Разбор останется закрытым.

Своя гипотеза

Напиши программу

Составь программу для квантового компьютера: выбирай две ячейки памяти и складывай или умножай их. Модель раскроет скобки в каждой ячейке, покажет, какие из десяти произведений уже получены, и сосчитает киловатты. Уложишься в 10 кВт/ч?

Без JavaScript модель не работает. Запиши программу строками вида x₁ = d + e, раскрой скобки в каждой строке и сосчитай строки: каждая стоит 1 кВт/ч.

Подсказка 1

Сначала сосчитай, сколько стоит счёт «в лоб»: $10$ умножений и ещё сложения. Каких операций больше всего? Посмотри на четыре слагаемых с буквой $a$ что у них общего?

Подсказка 2

Сумму $ab+ac+ad+ae$ можно записать как $a(b+c+d+e)$ — одно умножение вместо четырёх. Сгруппируй так же произведения с $b$ которые ещё не взяты, потом с $c$ Посмотри на получившиеся скобки: каждая получается из следующей добавлением одной буквы, а компьютер хранит промежуточные результаты.

Разобрать решение по шагам

Сколько стоит счёт «в лоб»

Сначала поймём, почему задача не пустяковая. Посчитаем сумму так, как она записана.

Каждое из десяти произведений $ab, ac, \ldots, de$ — одно умножение: $10$ кВт/ч.
Потом десять полученных чисел надо сложить. Каждое сложение превращает два числа в одно, то есть уменьшает количество чисел на $1$ Чтобы из $10$ чисел осталось одно, нужно $9$ сложений.

Итого $10+9=19$ кВт/ч — почти вдвое больше, чем разрешено. Значит, надо экономить, и прежде всего на умножениях: их тут больше всего.

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

Выносим общий множитель

Посмотрим на слагаемые с буквой $a$ $ab+ac+ad+ae$ Во всех четырёх есть множитель $a$ и по распределительному закону

\begin{aligned}&ab+ac+ad+ae\\[0.45em]&{}=a\cdot(b+c+d+e).\end{aligned}

Слева четыре умножения, справа — одно (плюс сложения внутри скобки). Это и есть экономия.

Сделаем так же с остальными. Произведения с $a$ уже собраны; из оставшихся возьмём те, где есть $b$ $bc+bd+be=b\cdot(c+d+e)$ Затем произведения с $c$ $cd+ce=c\cdot(d+e)$ Остаётся одно произведение $de$ Обозначим нужную сумму буквой $S$ получилось

\begin{aligned}S&=a(b+c+d+e)\\[0.45em]&\quad+b(c+d+e)\\[0.45em]&\quad+c(d+e)+de.\end{aligned}

Почему это равенство верно при любых числах? Запишем все произведения лесенкой (рисунок ниже): в строке $a$ — четыре произведения $a$ с буквами после неё, в строке $b$ — три, в строке $c$ — два, в строке $d$ — одно. Каждое произведение двух разных букв стоит ровно в одной строке — в строке той буквы, которая идёт раньше по алфавиту; всего их $4+3+2+1=10$ Если раскрыть скобки, каждая скобка даёт ровно свою строку. Значит, справа те же десять слагаемых, что и в $S$ ни одно не потеряно и ни одно не повторено.

Десять произведений лесенкой: каждая строка — одна скобка,

4+3+2+1=10

и каждое произведение стоит ровно в одной строке.

Скобки строятся одна из другой

Теперь нужны суммы $b+c+d+e$ $c+d+e$ и $d+e$ Если считать каждую отдельно, уйдёт $3+2+1=6$ сложений. Но они вложены друг в друга: $c+d+e$ — это $d+e$ плюс $c$ а $b+c+d+e$ — это $c+d+e$ плюс $b$ Компьютер хранит промежуточные результаты, поэтому считаем так:

$x_1=d+e$
$x_2=c+x_1$ то есть $c+d+e$
$x_3=b+x_2$ то есть $b+c+d+e$

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

Суммы в скобках строятся одна из другой: каждая следующая — предыдущая плюс одна буква, одно сложение.

Вся программа: 10 кВт/ч

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

Скобки (3 сложения): $x_1=d+e$ $x_2=c+x_1$ $x_3=b+x_2$
Произведения (4 умножения): $x_4=d\cdot e$ $x_5=c\cdot x_1$ $x_6=b\cdot x_2$ $x_7=a\cdot x_3$
Итог (3 сложения): $x_8=x_4+x_5$ $x_9=x_8+x_6$ $x_{10}=x_9+x_7$

По шагу 2

\begin{aligned}x_{10}&=de+c(d+e)\\[0.45em]&\quad+b(c+d+e)\\[0.45em]&\quad+a(b+c+d+e)\\[0.45em]&=S.\end{aligned}

Всего $3+4+3=10$ операций, то есть $10$ кВт/ч, — не больше, чем требуется. Программа одна и та же для любых чисел $a$ $b$ $c$ $d$ $e$ что и требовалось доказать.

Мы пользовались только сложением и умножением — ровно тем, за что компьютер берёт плату. Вычитать или делить не понадобилось.

Проверка

Проверим на числах $a=1$ $b=2$ $c=3$ $d=4$ $e=5$ Скобки: $x_1=9$ $x_2=12$ $x_3=14$ Произведения: $x_4=20$ $x_5=27$ $x_6=24$ $x_7=14$ Итог: $x_{10}=20+27+24+14=85$ Напрямую: $2+3+4+5+6+8+10+12+15+20=85$ . Ещё одна проверка: $(1+2+3+4+5)^2=225$ — это сумма квадратов $55$ плюс каждое произведение дважды, и $(225-55):2=85$ На числах $2, -3, 5, 0, 7$ программа и прямой счёт дают $17$ Совпадение на нескольких наборах чисел — только проверка; доказательство для любых чисел — раскрытие скобок в шаге 2. В тесте модели программа прогнана на $300$ случайных пятёрках целых чисел, а сама модель сравнивает результат с суммой по слагаемым, а не по значению.

Ответ

Доказано: сумму $ab+ac+ad+ae+bc+bd+be+cd+ce+de$ можно найти за $10$ операций, то есть за $10$ кВт/ч, — например, как $a(b+c+d+e)+b(c+d+e)+c(d+e)+de$ , где суммы в скобках получаются одна из другой.

Ответ

Главная идея

Распределительный закон превращает несколько умножений в одно: сумма $ab+ac+ad+ae$ равна $a(b+c+d+e)$ Сгруппировав произведения по первой букве, получаем $a(b+c+d+e)+b(c+d+e)+c(d+e)+de$ , а вложенные скобки строим одну из другой, храня промежуточные суммы. Итого $3+4+3=10$ операций.

Признаки: выражение нужно вычислить «дёшево» — за ограниченное число операций, и разрешено запоминать промежуточные результаты. Ищи общий множитель (одно умножение вместо нескольких) и повторяющиеся куски, которые можно посчитать один раз и использовать снова. Так же устроена схема Горнера: $ax^3+bx^2+cx+d=((ax+b)x+c)x+d$ — три умножения вместо шести.

Где легко ошибиться

Идти через квадрат суммы: $(a+b+c+d+e)^2$ содержит каждое произведение дважды и ещё квадраты $a^2, \ldots, e^2$ Чтобы получить нужную сумму, пришлось бы вычесть квадраты и разделить пополам — а это и лишние операции (одни квадраты стоят $5$ умножений), и вычитание с делением, которые здесь не нужны. Другая ошибка — считать каждую скобку заново: $b+c+d+e$ за три сложения, $c+d+e$ за два, $d+e$ за одно. Тогда скобки стоят $6$ сложений вместо $3$ и всего выходит $13$ кВт/ч.

Источник и авторство

Олимпиада имени Леонарда Эйлера · XVII олимпиада, сезон 2024/25 · дистанционный этап, i тур · дата тура не указана в файле заданий · математика · 8 класс. Официальная задача 1, 7 баллов.

Условия задач (PDF организатора) ↗ · Решения организатора ↗ · Архив олимпиады ↗

Условие — из официального файла организатора. Подсказки, объяснение и модели — Popov Academy. Авторский разбор Popov Academy проверен; результат сопоставлен с официальными материалами.

Продолжить тему: Преобразования выражений →

Тема, знания и приёмы

Преобразования выражений · Нужна школьная база

Распределительный закон: a(b + c) = ab + ac
Чтобы сложить n чисел, нужно n-1 сложений
Перебор пар без повторений (лесенка)

Приёмы решения: Разложение на множители · Последовательный подсчёт без повторов

Задать вопрос по задаче →