Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/s43/math/uroki/2013_2014/8mat_1314/spec/02_cnk_parity.pdf Дата изменения: Mon Jan 13 12:25:11 2014 Дата индексирования: Sun Mar 2 01:49:19 2014 Кодировка: Windows-1251 Поисковые слова: невооруженным глазом

Напомним, что треугольник Паскаля состоит из чисел . Для этих чисел есть явная формула . Они являются целыми, так как считают число K элементных подмножеств N элементного множества. Они также называются биномиальнымиNкоэффициентами, так как фигурируют в формуле бинома Ньютона: Рассмотрим треугольник Паскаля по моK дулю 2. Т.е. заменим все числа CN на их остатки. Получающийся треугольник строится при помощи той рекуррентной формулы, но со сложением по модулю 2: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0. На рисунке справа выписаны 16 первых строчек этого треугольника, рядом с каждой строкой указан ее номер: число N от 0 до 15. Пусть aN число единиц в N -й строке. Легко посчитать первые несколько чисел из этой последовательности:
a1 = 2, a2 = 2, a3 = 4, a4 = 2, a6 = 4, a7 = 8, a8 = 2, a9 = 4, a11 = 8, a12 = 4, a13 = 8, a15 = a5 a10 a14 16, = = = . 4, 4, 8, .. (a + b)N =
K =0 K C N ak b N -K

Четность биномиальных коэффициентов. K CN N! K CN = K !(N -K )!

.

0 1 2 3 4 5 6 7 8 9 10 11 1 12 1 13 11 14 1 0 15 1 1 1

1 11 101 1111 10001 1001 01010 1111 00000 0000 00000 0000 10001 1001 01010 1111 .........

1 1 1 1 10 1 00 0 10 1 11 0 10 1 11 0 01 1 11

1 1 11 0 01 1 11 0 10 1 11 1 1 01 1 00 0 01 1 1 1 11 01 111

Легко увидеть следующую закономерность: Число aN всегда является степенью двойки. Теорему сразу доказывать непросто, но легко увидеть следующий факт: Число aN является четным. Как мы знаем, что треугольник Паскаля является симметричным. Если N является нечетным, то в N -й строке четное число чисел (а именно N + 1), они разбиваются на пары равных, значит, количество единиц четно. Если N является четным, N = 2M , то среднее число в N -й строке сравнимо с M M M M C2M которое равно сумме двух стоящих над ним C2M-11 + C2M -1 = 2C2M-11 , значит, - - является четным (а в треугольнике Паскаля по модулю 2 стоит 0). Остальные числа в N -й строке опять разбиваются на пары симметричных значит, количество единиц в строке четно. Условие, что aN четно означает, что в строке треугольнике Паскаля по модулю два четное число единиц. Эквивалентно, в исходном треугольнике Паскаля в строке четное число нечетных чисел, а это равносильно, тому, что сумма чисел в строке четна. С другой стороны мы знаем, что эта сумма равна 0 1 N CN + CN + . . . + CN = 2N , т.е. четна. Для изучения последовательности aN удобно вначале изучать крайние случаи: когда aN минимально или максимально.
Теорема 1. Лемма 2.
Доказательство 1. Доказательство 2.


верно неравенство 2 aN N + 1 Первое неравенство следует из того, что по краям строки стоят единицы. Второе следует из того, что в строке всего N + 1 число. Глядя на первые 15 членов последовательности видно, что минимум достигается на номерах 1,2,3,8, а максимум на номерах 1,3,7,15. aN = 2 тогда и только тогда, когда N = 2l . Также aN = N + 1 тогда и только тогда, когда N = 2l - 1. Условие, что aN = N + 1 равносильно тому, что aN +1 = 2. За строкой из одних единиц строит строка, где по краям стоят единицы, а все остальные числа нули. И наоборот. Таким образом два утверждения в лемме 4 равносильны. Индукция по l. База была проверена выше. Переход от l к l + 1. Рассмотрим строчку с номером 2l . В ней сто1 ит 2l + 1 элемент, из которых средние 2l - 1 11 элементов нули. В строчке ниже под этими нулями тоже будут нули, которых будет на один меньше. И так далее, образуется равносторон1 1 ... ... 1 ний треугольник состоящий только из нулей ко1 1 торый занимает 2l - 1 строку. 11 11 0 По краям 2l -й строки стоят единицы. Пока они разделены нулями они не взаимодействуют, и из них происходят треугольники такие-же, 1 1 . . . . . . 1 1 1 . . . . . . как начало треугольника Паскаля. Через 2l строк (т.е. на 2l - 1 + 2l = 2l+1 - 1-й сроке) нули посередине заканчиваются и эти два треугольника сливаются. Получается, что (2l+1 - 1)-я строка состоит из двух строк с номерами 2l - 1. По предположению индукции мы знаем, что в строке треугольника Паскаля с номером 2l - 1 стоят одни единицы. Значит и в полученной строке треугольника Паскаля стоят одни единицы, a2 -1 = 2l+1 и a2 = 2. Из рассуждения выше также видно, что при 2l < N < 2l+1 - 1 верно, что aN > 2.
Лемма 3.

При

N >0

Доказательство.

Лемма 4.

Лемма 5.

Доказательство леммы 5.

Доказательство леммы 4.

1

l+1

l+1

Докажем по индукции утверждение, что при 0 N < 2 верно, что aN стрепень двойки. База была проверена выше. Переход от l к l + 1. Если, N < 2l , то по предположению индукции. Если N = 2l + N1 , где 0 N1 < 2l то из доказательства леммы 4 следует, что aN = 2aN , значит, по предположению индукции aN тоже степень двойки. Из леммы 4 следует, что C2K 0 (mod 2), при K = 0, 2l . Этот факт можно доказать по другому, алгебраически. По биному Ньютона (a + b)2 = 2 K k 2 -K , значит, нам нужно доказать, что K =0 C2 a b
Доказательство теоремы 1.

l

1

Замечание 1.

l

l

l

l

l

(a + b)2 = a2 + b2 + 2 ћ (. . .),

l

l

l

где в скобках стоит какой-то многочлен от

a, b

с целыми коэффициентами. Докажем


это равенство по индукции. База Переход от
l-1
l

l = 1:

(a + b)2 = a2 + 2ab + b2 = a2 + b2 + 2(ab).

к l:
l-1

(a + b)2 = (a + b)2

2

=a

2l

-1

+ b2

l -1

+ 2 ћ (. . .)

2

= a2 + b2 + 2 ћ (. . .),

l

l

где во втором равенстве мы воспользовались предположением индукции, а в последнем расскрыли скобки и привели подобные. Возникшая в треугольнике Паскаля по модулю 2 структура из единиц и нулей напоминает так называемый треугольник Серпинского.
Замечание 2.

https://en.wikipedia.org/wiki/Sierpinski_triangle