Олимпиада имени Леонарда Эйлера 2024-2025 учебный год, I тур дистанционного этапа

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

Комментарий/решение

$(a+b+c)(d+e)=ad+ae+bd+be+ce$

$ab+ac+bc+cd+de=c(a+b)+d(c+e)+ab$

И считаем что компьютер хранить. $а+b$ и $c(a+b)+(a+b+c)(d+e)+d(c+e)+ab. c(a+b)$ уже две действия $$c(a+b)+(a+b+c)(d+e)$$. И плюс это третий $(a+b)+c$ четвёртый $(a+b+c)$*$(d+e)$ умножение пятый и $d+e$ шестой. $d(c+e)$ седьмой восьмой $+ab$ плюс девятый $ab$ умножения десятый

Расмотрим сумму:

$ab+ac+ad+ae+bc+bd+be+cd+ce+de$

Её можно переписать так:

$a(b+c+d+e)+b(c+ d+e)+c(d+e)+de.$

Теперь посчитаем затраты:

2. Сложения внутри скобок.

Компьютеру достаточно вычислить суммы:

1) $a+b$,

2) $b+c$

3) $c+d$.

Так как внутри скобок есть сумма этих чисел, и этого достаточно так как компьютер запоминает сумму. На это уйдёт 3 операции сложения, то есть $3кВт/ч$.

3. Умножения:

В выражении требуется $4$ умножения. Это:

1) $a×(a+b+c+d+e)$

2) $b×(c+d+e)$

3) $c×(d+e)$

4) $d×e$.

А эти умножение тратят ещё $4кВт/ч$.

3. Итоговое сложение:

Результаты умножений складываются, и это ещё

3 операции сложения. Это ещё 3 кВт/ч.

В Итоге:

У нас уходит:

$3+4+3=10кВт/ч$

Что доказывает, что компьютер может вычислить это потратив не больше $10кВт/ч$