Читать онлайн «Сложение однобитных чисел. Треугольник Паскаля, салфетка Серпинского и теорема Куммера»

Библиотека <Математическое просвещение> Выпуск 38 С. Б. Гашков СЛОЖЕНИЕ ОДНОБИТНЫХ ЧИСЕЛ Треугольник Паскаля, салфетка Серпинского и теорема Куммера Издательство Московского центра непрерывного математического образования Москва • 2014  i i “main” — 2014/3/24 — 15:30 — page 2 — #3 i i УДК 511. 2 ББК 22. 131 Г24 Гашков С. Б. Г24 Сложение однобитных чисел. Треугольник Паскаля, сал- фетка Серпинского и теорема Куммера. — М. : МЦНМО, 2014. — 40 с. ISBN 978-5-4439-0145-9 В книге рассказывается о любопытной связи задачи о сложении чисел в двоичной записи с алгеброй логики, многочленами Жегалкина, треугольником Паскаля, салфеткой Серпинского и теоремой Куммера о делимости биномиальных коэффициентов. Все необходимое для пони- мания разъясняется. Брошюра является расширенным вариантом лек- ции, прочитанной на Малом мехмате в МГУ им. Ломоносова 6 апреля 2013 г. ББК 22. 131 ffi С. Б. Гашков, 2014 ISBN 978-5-4439-0145-9 ffi МЦНМО, 2014 i i i i  i i “main” — 2014/3/24 — 15:30 — page 3 — #4 i i Памяти моих родителей 1. Так ли просто сложение? Всем известно, что самая простая часть школьной математики — это арифметика. А в ней самая простая операция — сложение. Но слово сложность родственно, очевидно, слову сложение. Странно, не правда ли? Что может быть сложного в сложении? Мы постараемся далее показать, что сложение, даже в самой простой позиционной системе — двоичной — не так уж и просто, как это кажется на первый взгляд. Совсем непростой оказывается даже, казалось бы, простейшая задача — сложение одноразрядных (или, как говорят в программировании, однобитных) чисел 1 . Сформулируем эту задачу в общем виде. Задача. Нужно сложить n чисел x𝑖 = 0 или 1 и результат полу- чить в двоичной записи, т. е. найти такие двоичные цифры y𝑖 , чтобы выполнялось равенство x1 + . . . + x𝑛 = ( y𝑚 . . . y0 )2 = y𝑚 2𝑚 + . . . + 2 y1 + y0 , 2𝑚 > n ¾ 2𝑚−1 . Начнем разбираться с простейших частных случаев.