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

(!) Мы получили, что уравнение не имеет целых решений. Здесь стоит обратить внимание не только на общую идею решения уравнений в целых числах разложением на множители, но и на доказательство важного тождества X2+XY+Y2>=0.

Упражнение. (Для любителей теории чисел.) Решить в целых числах уравнение X2-Y2=232. Положительных решений у него должно быть ровно два: (X=59,Y=57), (X=31,Y=27). А остальные получаются из них естественным для такого уравнения способом - сменой знаков у X и Y.

Задача 3. Доказать, что если P и P2+2 - простые числа, то P3+2 - тоже простое число.
Решение: Нетрудно убедиться, что P=2 не подходит (P2+2 не простое), а P=3 подходит (и условие, и то, что надо доказать). Более того, никаких других подходящих P в первой десятке нет. На самом деле (как обычно и бывает в олимпиадных задачах) подходящих P>3 нет вообще. Действительно, если P>3, то P не делится на 3. Тогда P=1 (mod 3) или P=2 (mod 3). В любом случае, P2=1 (mod 3) и P2+2=0 (mod 3), т. е. делится на 3. Но тогда оно не может быть простым, так как оно явно больше трех! Утверждение доказано.

(!) Вообще, если p и q - два простых числа и p|q, то p=q, и никак иначе.

(!) Обратите внимание: это было типичное "липовое" условие, Хотя она формулируется "доказать, что из А следует В", но на самом деле доказывать надо, что А верно лишь для небольшого конечного количества наборов чисел. Дальше уже не составляет проблемы проверить, что для каждого из них верно условие В.

Задача 4. A+B+C делится на 6. Доказать, что A3+B3+C3 делится на 6.
Решение №1: Рассмотрим, какие остатки могут давать точные кубы по модулю 6. Рассматривая всевозможные остатки, получаем, что каждое число сравнимо с собственным кубом по модулю 6 (легче проверить отдельно, что N сравнимо с N3 по модулю 2 и по модулю 3). Тогда сумма трех чисел сравнима по модулю 6 с суммой их кубов. Первая сумма делится на 6, тогда и вторая делится на 6, ч. т.д.
Решение №2: Воспользуемся тождеством: A3+B3+C3=(A+B+C)(A2+B2+C2-AB-AC-BC)+3ABC (как его вывести, это отдельный алгебраический вопрос). Отсюда сразу следует, что если A+B+C делится на 6, то A3+B3+C3 сравнимо по модулю 6 с 3ABC. Нам осталось доказать, что 3ABC делится на 6, а это равносильно тому, что ABC четно. А ABC действительно четно: в противним случае все три числа A, B и C были бы нечетными, и их сумма тоже была бы нечетной и не могла бы делиться на 6?! ч. т.д.

Задача 5. Найти наименьшее натуральное число, дающее остатки 1 при делении на 2, 2 при делении на 3... 5 при делении на 6.
Решение: Обзовем наше число буквой N. Заметим, что наше условие означает, что N+1 - наименьшее число, которое делится на 2, 3, 4, 5 и 6 одновременно. Такое число - это 60=НОК(2,3,4,5,6). (НОК нескольких чисел определяется так же, как и у двух: наименьшее, которое одновременно делится на них все). Значит, искомое N равно 59.

Теорема. Натуральное число является точным квадратом тогда и только тогда, когда у него нечетное число делителей.
Доказательство: Возьмем натуральное число N и попробуем разбить его делители на пары. Если d|N, то число (N/d) - тоже делитель N. Объединим их в пару, и поступим так со всеми делителями. Либо все делители разбились на пары, либо какой-то делитель оказался парой к самому себе. Последнее означает, что у N есть делитель d, такой, что d=N/d, т. е. N=d2. Понятно, что если N - не точный квадрат, то такого быть не может, и у N - четное число делителей. А если N - точный квадрат, то такое обязательно будет, причем ровно одно, и у N - нечетное число делителей ч. т.д.

Лекция 7: Игры.

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

Игры-шутки.
Самый первый и простой класс игр - игры-шутки, в которых, на самом деле, нет никакой стратегии (а нас хотят обмануть, что она якобы есть!). Просто... как бы кто ни ходил, либо всегда выиграет первый игрок (тот, кто начинает игру), либо всегда второй. Задача - в том, чтобы математически доказать такую закономерность (а заметить ее можно, сыграв самому с собой раза 3-4). Для доказательства обычно находится какая-то величина, которая понятно чему равна в начале и конце и понятно как изменяется на каждом ходу - тут даже частенько число ходов до конца однозначно посчитать можно. Либо какой-то инвариант (т. е. что-то, не меняющееся ни при какой ходе), однозначно зависящий от начальной позиции (чаще всего - от четности) и определяющий выигравшего в конце.

Задача 1. Двое по очереди ломают шоколадку 5x8. За ход можно разломать любой кусок по прямой линии между дольками. Проигрывает тот, кто не может сделать ход (И это такое стандартное условие, что мы его будем подразумевать, если не сказано обратное. Вопрос "кто выиграет при правильной игре?" тоже поздразумевается.)
Решение: Что значит, что игра закончилась? Конечно, что шоколадка уже вся разломана на отдельные дольки. Долек всегда будет 5x8=40 штук, а шоколадка в начале была одна. Заметим, что на каждом ходу один кусок шоколадки всегда разламывается на 2, т. е. количество различных кусковшоколадки увеличивается на 1. В начале это кол-во было равно 1, а в конце, как мы заметили, 40. Значит, игра продолжалась ровно 39 ходов ("ходом" мы называем ход одного игрока, а не пару "ход - ответный ход"). Поэтому последний (39-й) ход был обязательно ходом первого (его ходы - первый, третий и все с нечетными номерами) - и первый выиграл.
Вот такая получилась шутка - как ни ходи, первый всегда выигрывает ;-)

Упражнение: Решить ту же задачу в общем виде, про шоколадку MxN. (Должно получиться, что второй выигрывает, если M и N оба нечетные, а иначе выигрывает первый.)

Задача 2. На доске написаны 10 нулей и 10 единиц. За ход можно стереть две любые цифры и написать вместо них 0, если они были одинаковые или 1, если они были разные. Если на доске остается 1 - выигрывает первый. Если 0 - второй.
Решение: Ну, поскольку число цифр с каждым ходом уменьшается ровно на 1 (2 стираем, одну пишем), а исходно их 20 и в конце должна остаться одна, то игра будет продолжаться ровно 19 ходов. Последним ходом будет ход первого... только в этой задаче (в отличие от предыдущей!) не факт, что первый тогда выиграет.
Выигрыш зависит от четности последнего числа, так давайте на нее и посмотрим... Такой стандартный инвариант, как четность суммы всех чисел, не меняется при ходах. Действительно, сумма двух одинаковых цифр - четна и, вычитая ее, мы прибавляем четный ноль. А сумма двух разных цифр - нечетна (0+1=1), и мы прибавляем всесто нее нечетную единицу. Исходно сумма всех чисел четна, т. к. среди них четное число нечетных - единиц - (см. лекцию 1 "Четность"), поэтому и в конце будет четна. А это значит, что последнее число, оставшееся в конце игры, будет четным, т. е. оно будет нулем - и выигрывает второй.
(!) Заодно мы убедились, что не в любой игре тот, кто делает последний ход, выигрывает: можно заставить (как оно тут и происходит) противника сделать ход, после которого он проиграет.

Идея "идиотских ходов":
Задача 3. На доске 10x12 можно за ход вычеркнуть одну линию (горизонталь или вертикаль, т. е. строку или столбец) если в ней еще есть одна невычеркнутая клетка.
Решение: (Да, проигрывает тот, кто не может сделать ход - если кто не понял.) Давайте еще задачу слегка переформулируем: пусть линия не вычеркивается, а вырезается из доски со склеиванием краев разреза. Тогда правило будет "можно вырезать любую существующую линию" и игра заканчивается, когда от доски ничего не остается.
Пусть вдруг мы после своего хода оставили, скажем, доску с одной строкой. Конечно, своим ходом противник может вырезать эту строку - и мы проиграем. Поэтому такой ход был идиотским - давайте так его и называть. Посмотрим, когда нельзя будет не сделать идиотского хода. Если доска 1xN (или Nx1) - то такой ход уже сделал противник. Если ширина и высота доски не меньше 2, а большая из них - не меньше 3 - то вырежем линию поперек большей размерности - и останется доска хотя бы 2x2. А вот если перед ходом доска - 2x2, то ход обязательно будет идиотский (!). Ясно, что выиграет тот, кто оставит противнику доску 2x2. На каждом ходу высота или ширина доски уменьшается на 1 (т. е., их сумма уменьшается на 1). Исходно эта сумма равна 10+12=22, в конце должна стать 2+2=4. Разность 22-4=18 - четное число ходов, поэтому доска 2x2 останется после хода второго - и второй выиграет (как в обычной игре-шутке!).
Строго говоря: стратегия второго - играть как угодно, только не делая идиотских ходов. Если первый где-то сделает идиотский ход (а это формальномешает загнать его на доску 2x2) - следующим ходом мы выигрываем. Если никто не сделает идиотского хода - то после 18 ходов у первого будет доска 2x2 - и тут он все равно сделает идиотский ход.

Упражнение: Решить ту же задачу в общем виде, про доску MxN. (Вроде бы, первый выигрывает при нечетном M+N, второй - при четном.)

Симметрия.
Сейчас мы познакомимся с мощным и красивым, но очень простым методом решения игровых задач - симметричной стратегией. Суть его - делать каждый раз ход, симметричный ходу противника или дополняющий его до чего-либо. Доказательство правильности нашей стратегии будет пользоваться тем, что после каждого нашего хода позиция симметрична: раз так, то если противник сумел сделать свой ход, то и мы сможем сделать ход, симметричный ему. Неправильно думать что симметри - стратегия только для второго игрока. Если исходная позиция - несимметрична, то обычно первый игрок может ее как-то симметризовать, а потом играть по симметрии, отвечая на ходы второго.