Четность

Ноя 16 2014

Лекция «Четность.»

В данной лекции «Четность» мы познакомимся с понятием четности и областями ее применения.

Идея четности имеет много разных применений. Самые простые из них:

1. Если в некоторой замкнутой цепочке чередуются объекты двух видов, то их четное число (и каждого вида поровну).

2. Если в некоторой цепочке чередуются объекты двух видов, а начало и конец цепочки разных видов, то в ней четное число объектов, если начало и конец одного вида, то нечетное число. (четное число объектов соответствует нечетному числу переходов между ними и наоборот !!!)

3. ОБРАТНО: по четности длины чередующийся цепочке можно узнать, одного или разных видов ее начало и конец.

4. Если предметы можно разбить на пары, то их количество четно.

5. Если нечетное число предметов почему-то удалось разбить на пары, то какой-то из них будет парой к самому себе, причем такой предмет может быть не один (но их всегда нечетное число).

Примеры:

Задача 1. На плоскости расположено 11 шестеренок, соединенных по цепочке (первая со второй, вторая с третьей … 11-я с первой). Могут ли они вращаться одновременно?
Решение: Нет, не могут. Если бы они могли вращаться, то в замкнутой цепочке чередовалось бы два вида шестеренок: вращающиеся по часовой стрелке и против часовой стрелки (для решения задачи не имеет никакого значения, в каком именно направлении вращается первая шестеренка !) Тогда (по п.1) всего должно быть четное число шестеренок, а их 11 штук?! ч.т.д. (знак «?!» обозначает получение противоречия)

Задача 2. Шахматный конь вышел с некоторой клетки, сделал несколько ходов и вернулся (а)обратно, (б)на клетку того же цвета, с которой он начинал. Доказать, что он сделал четное число ходов.
Решение: (а) Шахматный конь каждым ходом меняет цвет клетки, на которой он стоит. Получаем, что в замкнутой цепочке клеток, по которым прошел конь, чередуются черные и белые. Значит, всего в цепочке четное число клеток. Поскольку она замкнутая, то число ходов будет тоже четным.
(б) На этот раз, поскольку цепочка чередующихся черных и белых клеток под конем не замкнута, то стоит применить п.2 из списка вверху. Получаем неожиданный, на первый взгляд, результат: в цепочке начало и конец одного цвета, поэтому в ней нечетное число клеток. Но надо заметить, что ходы коня — это не объекты цепочки, а переходы между ними. Их здесь (в незамкнутой цепочке) на единицу меньше, чем самих объектов, поэтому число ходов будет четным ч.т.д.

(!) Боже упаси от следующего вида маразма: отдельно рассматривать случай, когда конь вернулся на начальную клетку (пользуясь п.1) и когда он вернулся на какую-то другую клетку (пользуясь п.2). Даже если конечная клетка совпадает с начальной, мы можем считать их разными объектами в цепочке клеток и рассматривать ее как обычную незамкнутую цепочку. Ведь если в середине цепочки несколько раз повторится одна и та же клетка доски, мы все равно считаем ее несколькими разными объектами.

Задача 3. Может ли прямая, не содержащая вершин 239-звенной замкнутой ломаной, пересекать каждое звено ровно 1 раз?
Решение: Будем рассматривать в качестве цепочки последовательность отрезков прямой от одного пересечения до следующего + 2 луча по краям. Понятно, что у нас чередуются куски, лежащие вне и внутри ломаной. Пересечений=переходов между ними ровно 239 штук, т.е. нечетное число, поэтому самих кусков будет четное число (240 штук, из них 2 луча и 238 отрезков между ними). Тогда, по п.3, начало и конец цепочки разных видов, т.е. один луч лежит вне ломаной, а другой — внутри нее. Но луч простирается до бесконечности, следовательно, не может лежать внутри замкнутой ломаной. Ответ: не может.

(!) Любая прямая пересекает границу любой замкнутой кривой четное число раз, если нигде не касается ее (для ломаной «касается» означает «содержит вершины»). Доказывается это по п.2 или п.3, аналогично предыдущей задаче.

Задача 4. Дан осесимметричный выпуклый 101-угольник. Докажите, что ось симметрии проходит через одну из его вершин.
Решение: Для каждой вершины существует симметричная ей относительно оси, причем если вершина А симметрична вершине В, то вершина В симметрична вершине А. Тогда мы можем разбить вершины на пары симметричных. Поскольку вершин нечетное число (101), то, по п.5, есть вершина, которая будет парой к самой себе, т.е. она симметрична самой себе. Эта вершина и будет лежать на оси симметрии.

(!) Вершина, лежащая на оси симметрии, может быть не одна (если мы берем не «нормальный» 101-угольник, а просто 101 точку, симметрично расположенную на плоскости), а 3, 5, 7 и любое нечетное число, хоть все 101. Точек, не лежащих на оси, четное число, поскольку они разбиваются на пары (и не могут быть парой к самим себе), и остается еще какое-то нечетное количество лежащих на оси точек (101-2n, где n — количество пар симметричных).

Иногда полезно бывает рассмотрение четности суммы или разности нескольких целых чисел:

0. Сумма двух четных чисел четна. Сумма двух нечетных чисел четна. Сумма четного и нечетного чисел — нечетна.

1. Сумма любого количества четных чисел четна. Это очевидно по многим разным соображениям. Например: при последовательном вычислении суммы всегда все промежуточные результаты будут четными, согласно свойству 0. Либо: все четные числа делятся на 2, поэтому из их суммы можно вынести 2 за скобку; а тогда сумма будет делится на 2, т.е. будет четной.

2. Сумма четного числа нечетных чисел четна, сумма нечетного числа нечетных чисел нечетна.
Доказательство: Если нечетных чисел — четное число (2n), то разобьем их на пары (всего n пар). Сложим числа в каждой паре (сумма двух нечетных чисел — четная !). Получим сумму n четных чисел, которая четна по п.1. Если же было нечетное число (2n+1) нечетных чисел, то возьмем все числа, кроме одного (2n штук) — их сумма четна. Прибавим к ней оставшееся нечетное число и получим, что сумма всех чисел нечетна по п.0 (здесь и далее имеются в виду пункты нового списка), ч.т.д.

3. Сумма нескольких целых чисел четна тогда и только тогда, когда среди них четное число нечетных чисел.
Доказательство: Сложим отдельно все четные и отдельно все нечетные числа. Первая сумма всегда четна (п.1), вторая четна тогда и только тогда, когда в ней четное число нечетных чисел (п.2). Если вторая сумма четна, то сумма всех четна, если она нечетна, то сумма всех нечетна (см. п.0), поэтому четность суммы всех чисел определяется указанным в условии правилом.

4. Разность двух четных чисел четна. Разность двух нечетных чисел четна. Разность четного и нечетного чисел в любом порядке — нечетна.

5. Разность двух чисел имеет ту же четность, что и их сумма.
(напр. 2+3=5 и 2-3=-1 оба нечетны)
Можно доказывать это перебором трех-четырех случаев (сравнивая п.0 с п.4), но проще заметить, что a+b=(a-b)+2b, т.е. сумма и разность двух чисел различаются на четное число, следовательно, имеют одинаковую четность ч.т.д.

6. Алгебраическая (со знаками + или -) сумма целых чисел имеет ту же четность, что и их сумма.
(напр. 2-7+(-4)-(-3)=-6 и 2+7+(-4)+(-3)=2 оба четны)
Доказательство: Возьмем сумму чисел и изменим в ней несколько знаков с + на — (перед первым числом мы тоже можем поставить знак -). Так мы сможем получить любую алгебраическую сумму. При изменении знака перед некоторым числом a значение алгебраической суммы уменьшится на 2a, т.е. четность сохраниться. Поэтому четность сохраниться после изменения любых нескольких (ноль и один — это тоже несколько !) перемен знака, и она в любом случае будет совпадать с четностью исходной суммы.

7. Алгебраическая сумма целых чисел четна тогда и только тогда, когда среди них четное число нечетных чисел.
Доказательство: Очевидно следует из п.3 и п.6.

4′. Противоположные числа имеют одинаковую четность.

5′. Разность двух чисел имеет ту же четность, что и их сумма.
Доказательство: Так как вычитание числа — это прибавление противоположного к нему, то разность чисел — это сумма двух чисел, одно из которых — противоположное к исходному. Т.к., по п.4′, замена числа на противоположное не меняет его четности (а четность суммы зависит только от четности чисел!), то четность этой суммы равна четности суммы исходных чисел.

6′. Алгебраическая сумма целых чисел четна тогда и только тогда, когда среди них четное число нечетных чисел.
Доказательство: Алгебраическая сумма — это сумма нескольких новых чисел, некоторые из которых противоположны исходным (аналогично п.5′), а остальные — равны (напр. 2-7+(-4)-(-3)=2+(-7)+(-4)+3). Согласно п.4′, четность новых чисел равна четности исходных, поэтому условие «среди них четное число нечетных чисел» для новых чисел и для исходных означает одно и то же. А это условие и является, по п.3, необходимым и достаточным, чтобы сумма новых чисел (т.е. исходная алгебраическая сумма) была четной ч.т.д.

7′. Алгебраическая (со знаками + или -) сумма целых чисел имеет ту же четность, что и их сумма.
Доказательство: Следует из п.3 и п.6′: необходимое и достаточное условие четности суммы и четности алгебраической суммы — одно и то же.

(!) Пункты 5′-7′ — это те же пункты 5-7, только слегка по-другому доказанные. Иногда полезно понимать логику обоих доказательств.

Нет ответов пока

Вы должны ввойти чтобы оставить комментарий.