Разгадка древнеегипетского способа умножения кроется в весьма нетривиальном факте.
Любое натуральное число можно единственным способом представить в виде суммы различных степеней двойки.
Для доказательства возможности такого разложения, воспользуемся индукцией.
✅База индукции: 1 = 2⁰.
Пусть число N представлено в виде суммы различных степеней двойки.
Докажем, что для числа N +1 найдется разложение.
Если какое-то iₖ=0, то заменим сумму 2⁰ + 2⁰ на 2¹. Если степень 2¹ имеется в разложении, заменим сумму 2¹ + 2¹ на 2². Будем повторять процедуру пока все степени не станут различны.
✅Теперь докажем, что такое разложение единственное.
Предположим, что есть два различных разложения для одного и того числа N.
Приравняем и вычеркнем одинаковые степени слева и справа.
Заметим, что суммы слева и справа - четные. Так как, если 2⁰ было с двух сторон, его вычеркнули на предыдущем шаге. Если 2⁰ есть только с одной стороны, то получаем, что четное число равно нечетному.
В каждом наборе вынесем за скобки общий множитель, то есть степень с самым маленьким показателем.
Разделим обе части равенства на меньшую из вынесенных степеней.
Число слева четное, а справа нечетное, при этом они равны. Получили противоречие, значит эти разложения идентичны.
Алгоритм умножения
В первом столбце выписываются все степени двойки до ближайшего к одному из множителей. По доказанному утверждению среди них найдутся такие, сумма которых равна 35. Второй столбец представляет собой произведение степени двойки на второй множитель.
Тогда можно вынести общий множитель, а оставшаяся в скобках сумма равна второму множителю.
