Лекция 12: Графы - 2 (стр. 15 )

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, только слегка по-другому доказанные. Иногда полезно понимать логику обоих доказательств.

Примеры:

Задача 1. Можно ли разменять 25 советских рублей на 8 купюр в 1, 3 и 5 советских рублей?
Решение: Нет, нельзя. Достоинства всех купюр - нечетные числа, а сумма 8 нечетных чисел - четная (п.2). Поэтому она не может равняться 25.

Задача 2. В ряд выписаны числа от 1 до 10. Можно ли расставить между ними знаки + и -, чтобы получилось выражение, равное нулю?
Решение: Нет, нельзя. По п.6 или 7', четность полученного выражения всегда будет совпадать с четностью суммы 1+2+...+10=55, т. е. сумма всегда будет нечетной. А 0 - четное число?! ч. т.д.
Решение№2: Отрицательные числа тоже бывают четными и нечетными. А здесь мы имеет дело с суммой 10 целых чисел (положительных или отрицательных), среди которых, при любой расстановке знаков, будет 5 нечетных. Тогда, по п.3, сумма всех всегда будет нечетной. Отсюда следует ответ "нельзя".

Задача 3. При каких n сумма чисел от 1 до n нечетна?
Решение: По п.3, сумма чисел от 1 до n нечетна тогдаитолько тогда, когда среди них нечетное число нечетных. Кол-во нечетных чисел от 1 до n - это n/2 при четном n и (n+1)/2 при нечетном. Нечетное n/2 при четном n означает n=4k+2 (остаток 2 от деления на 4), а несчетное (n+1)/2 при нечетном n означает n=4k+1 (остаток 1 от деления на 4). Ответ: n=4k+1 или 4k+2.

(!) Обратите внимание: ответ зависит от остатка n при делении на 4, а не от четности. Подобная зависимость характерна для задач, где что-то происходит с числами от 1 до n или с несколькими последовательными числами.

Идея четности может быть хитро замаскирована, скажем, объекты, к которым она применяется, неочевидны из условия.

Задача *. За круглым столом сидят 25 мальчиков и 25 девочек. Доказать, что у кого-то из сидящих оба соседа - мальчики.
Решение: Рассмотрим замкнутую цепочку из чередующихся объектов: кусков из нескольких подряд сидящих мальчиков или девочек.
1.) Длина любого куска из мальчиков не больше двух. Действительно, если подряд сидят три (или больше) мальчиков, то у среднего из них оба соседа мальчики, поэтому доказывать нечего.
2.) Длина любого куска из девочек не меньше двух. Действительно, если подряд сидит только одна девочка, то у нее оба соседа - мальчики, и опять доказывать нечего.
3.) Кусков из мальчиков и девочек поровну (п.1 в самом начале лекции). Обозначим это число буквой n (есть ровно n кусков из мальчиков и ровно n кусков из девочек).
4.) Из предыдущих пунктов получаем, что за столом сидит не более 2n мальчиков и не менее 2n девочек. Но тех и других по 25, поэтому 2n<=25<=2n. Получаем, что 2n=25, что невозможно. Значит, у нас имеет место случай, характеризуемый в пунктах 1 и 2 словами "доказывать нечего", ч. т.д.

(!) Установить наличие идеи четности в задаче можно, проверяя ответ вручную для небольших входных данных (но не слишком маленьких) и заметив его зависимость от четности n (либо, как в задаче 3, от остатка при делении n на 4). Например, в последней задаче, 1 мальчик и 1 девочка - слишком маленькие входные данные (двух мальчиков нет вообще). 2 мальчика и 2 девочки имеют единственную противоречащую условию рассадку (ММДД). 3 мальчика и 3 девочки не имеют такой рассадки. 4 мальчика и 4 девочки - опять единственная рассадка (ММДДММДД). К этому моменту зависимость от четности обычно становится ясна...

Лекция 11: Инвариант.

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

Задача 1. В файле хранятся 2003 единицы и 232 нуля. Программа читает из файла два произвольных числа, стирает, и записывает на их место 0, если они были равны, и 1, если нет. Программа запускается многократно. В конце в файле остается только одно число. Чему оно равно, 0 или 1?
Решение: Несмотря на то, что вариантов действия программы очень много, мы можем установить ответ однозначно. Что может прочитать программа за каждыйотдельный запуск? Либо 0 и 0 (и записать 0), либо 0 и 1 (и записать 1), либо 1 и 1 (и записать 0). В первых двух случаях сумма всех чисел в файлене меняется, в последнем - уменьшается на 2. В любом случае, четность этой суммы остается прежней. Исходно сумма была 2003*1+232*0=2003 - нечетная, значит, и в конце будет нечетная. Но в конце остается только одно число - оно и равно сумме всех - поэтому оно нечетное. А так как в файле бывают только нули и единицы, то это 1.

Задача 2. А какое число останется в файле, если программа за один запуск стирает два числа и записывает вместо них их сумму?
Решение: Если в прошлой задаче инвариантом была четность суммы всех чисел в файле, то теперь это будет сама сумма. Ясно, что при замене двух любых чисел на их сумму сумма всех не меняется. Поэтому последнее число - оно же сумма чисел в конце - равно сумме чисел в начале, т. е. 2003 (см. задачу 1).

Задача 3. Имеются три числа, которые можно заменять по следующим правилам: числа a, b и c стираются и вместо них записываются (a+b)/2, (b+c)/2 и (a+c)/2.Можно ли из чисел 101, 73, 125 получить 77, 79 и 83?
Решение: А давайте так, "на всякий случай", посмотрим, как меняется сумма чисел. Было a+b+c, а стало... вместо них записываются (a+b)/2+(b+c)/2+(a+c)/2 = (2a+2b+2c)/2 = a+b+c - не изменилась. То есть, как ни крути, а сумма трех чисел не меняется. Но 101+73+125=299, а 77+79+83=239 - суммы исходной и конечной тройки разные. Поэтому из одной нельзя получить другую.
(!) А те, кто захочет взять в качестве инварианта четность суммы или ее остаток по какому-то модулю, скорее всего, ошибутся, так как начальная и конечная суммы различаются на 60, а делителей у 60 ох как много ;-)

Задача 4. Опять имеются три числа, которые можно заменять уже по другим правилам: a, b и c - на ab/c, ac/b и bc/a. Можно ли из 5, 17/6 и 3/5 получить 16/5, 9/4 и 7/6?
Решение: Ну, о том, куда тут переходит сумма чисел, даже думать не хочется. Что еще бывает, кроме суммы? Произведение, например. Перед операцией произведение чисел - abc, а после: (ab/c)*(ac/b)*(bc/a) = a2b2c2/abc = abc - не изменилось! Значит, произведение трех чисел остается постоянным при всех операцих. Но в начале оно было равно 5*(17/6)*(3/5)=8,5, а в конце (16/5)*(9/4)*(7/6)=8,4 - не равны. Поэтому ответ "нельзя".

(!) Если у нас есть какой-то набор чисел, над которым совершаются операции, то всегда стоит проверить, как изменяются при этих операциях сумма ипроизведение всех чисел. Очень часто они сами или их остатки по какому-то модулю являются инвариантом, с помощью которого решается задача.

Замечание. В задачах, где спрашивается "можно ли" с помощью инварианта можно доказывать только ответ "нельзя"! Если придуманный вами инвариант ничему не противоречит (его значение в начале и конце предполагаемой последовательности операций одинаково), то это не значит, что ответ "можно". Во-первых, обычно это значит, что придуман плохой инвариант. Во-вторых, ответ "можно" доказывается предъявлением конкретного примера и никак иначе.

Инвариант как характеристика нечисловых объектов. Во всех предыдущих примерах в задаче фигурировали числа, от которых мы в качестве инварианта брали какую-то функцию. Но, конечно, в исходной формулировке может ни быть никаких чисел! Что тогда делать? Конечно, эти числапридумать.

Задача 5. В стране серобуромалинии 27 серых, 32 бурых и 45 малиновых хамелеонов. Когда встречаются два хамелеона разных цветов, они оба перекрашиваются в третий цвет. Могут ли когда-нибудь все хамелеоны стать одного и того же цвета?
Решение: Ну где же тут у нас числа? Наверное, количества хамелеонов серого, бурого и малинового цвета. Как же они изменяются? Либо (A, B, C) переходит в (A-1, B-1, C+2) - встречаются серый и бурый хамелеоны и перекрашиваются в малиновый цвет, либо в (A-1, B+2, C-1) - серый и малиновый в бурый, либо, наконец, в (A+2, B-1, C-1) - бурый и малиновый в серый. Сумма всех трех, конечно, сохраняется, но это нам не поможет. А что поможет установить, могут ли два количества из трех стать нулями? Скорее, разности - кстати, еще один из базовых видов инвариантов. Между теми двумя числами, которые уменьшились на 1, разность не поменяется, зато разность между ними и третьим изменится ровно на 3. То есть по модулю 3, все попарные разности неизменны (сравните, как в задаче 1, из того, что сумма может уменьшаться на 2, мы находили, что ее четность неизменна). Значит, инвариант - значения попарных разностей по mod 3. Если какая-то разность в конце стала нулем (а так будет, если два количества станут нулями!), то исходно она делилась на 3. Но разности между исходными количествами на 3 не делится! Значит, не могут...