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

Задача 13. Фишка ходит по доске NxN, сдвигаясь на 1 клетку вверх, вправо или вниз-влево по диагонали. Может ли фишка обойти все клетки доски по разу и закончить путь сверху от начальной клетки.
Решение: Подберем раскраску, при которой фишка будет одинаково менять цвет при любом ходе. Просто шахматная и "матрас" не подойдут. А затошахматная раскраска в 3 цвета - просто замечательно (см. рис. выше). Наша фишка будет ходить с красного на желтый, с желтого на зеленый, с зеленого на красный и т. д. Пусть, скажем, начальная клетка красная - тогда конечная будет желтая. Цвета чередуются по циклу длины 3, поэтому число ходов: 3k+1 (т. е. =1 по mod 3). Но то же число ходов на доске NxN равно N2-1. Отсюда N2=2 (mod 3), чего, по соображениям теории чисел (см. лекцию "Теория чисел-2") не бывает. Ответ "нельзя".

(!) Инвариант инвариантом, но и про другие области математики по ходу дела не надо забывать. Часто решение может придти именно оттуда.

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

Лекция 4: Теория чисел.

Простые и составные числа. Основная теорема арифметики:

Из школьной программы нашим читателям, безусловно, должны быть известны следующие факты:
- натуральное число называется простым, если оно делится только на самого себя и на 1;
- натуральное число называется составным, если оно имеет делитель, отличный от самого себя и 1;
- 1 не считается ни простым, ни составным числом (это связано с тем, что 1 является так называемым обратимым элементом множества целых чисел, т. е. любое число можно поделить на 1, а простые числа этим свойством не обладают);
- любое натуральное число, отличное от 1, можно разложить в произведение простых сомножителей, причем единственным образом (с точностью до перестановки сомножителей) - этот факт называется основной теоремой арифметики.

Вместе с этими фактами следует помнить и следующие:
- составные числа имеют в своем разложении на простые множители хотя бы 2 (не обязательно разных!) множителя, простые - ровно 1 множитель, единица - 0 множителей (!);
- для любого простого числа (p) и любого натурального числа (n) существует целая неотрицательная степень вхождения p в разложение n, и она определена однозначно; если в разложении n нет множителя p, то степень равна 0, если есть - степень вхождения равна количеству простых множителей, равных p, в разложении n (здесь и далее мы повсеместно будем обозначать эту степень вхождения через vp(n), как принято в высшей алгебре; более того, это сделано специально, чтобы читатели хорошо овладели удобным и кратким языком этих обозначений);
- 2 натуральных числа a и b равны тогда и только тогда, когда vp(a)=vp(b) для любого простого p (по-русски: "два числа равны тогда и только тогда, когда степени вождения в них всех простых множителей одинаковы");
- если натуральное число n=a*b, то для любого простого p: vp(n)=vp(a)+vp(b) (по-русски: "степень вхождения любого простого множителя в число n равна сумме его степеней вхождения в a и b"); это следует из того, что разложение произведения чисел на простые множители есть объединение их разложений;
- число n делится на число d если и только если любой простой множитель входит в n в не меньшей степени, чем в d, т. е. vp(n)>=vp(d) для любого простого p; иначе, если для какого-то множителя p это неверно, то при делении образуется дробь с неуничтожаемым множителем p в знаменателе;
- последнее условие достаточно проверять, разумеется, только для простых множителей входящих в разложение d; для невходящих будет vp(d)=0, что в любом случае не больше vp(n);
- при этом, если n делится на d, и частное мы обозначим за q, то vp(q)=vp(n)-vp(d) для любого простого p (по-русски: "степень вхождения любого простого множителя в число q равна разности его степеней вхождения в n и d"); это следует из равенства n=d*q и предыдущих пунктов;
- да, чуть не забыл: для любого простого p, vp(1)=0 (по-русски: "степень вхождения любого простого множителя в единицу равна нулю").

(!) Буква p (а также буква q) в этой лекции будет специально зарезервирована для обозначения только простых чисел. Поэтому слова "для всех p", "для любого q" и т. п. следует понимать как "для всех простых p", "для любого простого q".

Примеры:
Типичные простые числа: 2, 3, 5, 7, 11, 13, 17, 19, 101, 239... (во многих учебниках и справочниках есть полная таблица простых чисел от 1 до 1000; а всего простых чисел бесконечно много).
Типичные составные числа: 4, 6, 8, 10, 12... (делятся на 2), 9, 15, 21, 27... (делятся на 3), 25, 35, 55, 65... (делятся на 5). Нетипичные: 111=37*3, 1001=7*11*13, 10001=73*137... (составных чисел тоже бесконечно много, хотя бы потому, что четных - бесконечно много).
А простого способа определить по виду числа его простоту (если для него не выполняется ни один из признаков делимости на маленькие числа) не существует(!).
Разложение на простые множители - это что-то типа: 72=2*2*2*3*3=23*32; здесь мы имеем v2(72)=3, v3(72)=2 и vp(72)=0 для простого p, отличного от 2 и 3.
Если написать, например, 72=6*12, то для этих чисел будут разложения: 6=2*3, 12=2*2*3==22*3. Тогда получаем: v2(6)=1, v2(12)=2, v3(6)=1, v3(12)=1, vp(6)=vp(12)=0, при p, не равном 2 и 3.
Заметим, что 1+2=3, 1+1=2 и 0+0=0, в соответствии с формулой vp(n)=vp(a)+vp(b) для n=a*b.
Рассмотрим, например, число 18=2*3*3=2*32 - у него будет здесь мы имеем v2(18)=1, v3(18)=2 и vp(18)=0 для всех прочих множителей. 3>=1, 2>=2, 0>=0, поэтому vp(72)>=vp(18) для любого p. И при этом, действительно, 72 делится на 18.
Частное от деления 72 на 18 равно 4=2*2=22, и у него v2(4)=2, v3(4)=0, vp(4)=0 для p, не равного 2 и 3. Как ни странно, 2=3-1, 0=2-2, 0=0-0, т. е. все согласуется с формулой vp(q)=vp(n)-vp(d) для q=n/d.
Если рассмотреть число, на которое 72 вообще не делится, например 48, то оно равно 2*2*2*2*3=24*3. Тогда v2(48)=4>3=v2(72). Именно из-за этого оно и не делится (72/48=3/2 - как раз остается 2 в знаменателе).

Разложение на простые множители и вопросы делимости:
Свойства делимости числа полностью определяются его разложением на простые множители. Более того, как показывает ряд следующим примеров, это свойства удобнее проверять именно через разложение.

(!) Утверждение "a делится на b" или "b делит a" мы будем записывать общепринятым обозначением b|a. Другое общепринятое обозначение - вертикальное троеточие - мы по техническим причинам использовать не будем.

1. Делится ли 29*3 на 8? А делится ли оно на 9? А на 6?
На 8 это число делится, т. к. 2 входит в его разложение на множители в степени 9, а 8=23.
На 9 это число не делится, так как 3 входит в его разложение на множители только в степени 1, а 9=32.
На 6 оно делится, потому что 6=2*3, а в разложение данного числа на множители входят 2 и 3, каждое в степени не меньше 1.

2. Верно ли, что если натуральное число делится на 3 и на 4, то оно делится на 12? А верно ли, что если число делится на 4 и на 6, то оно делится на 24?
Первое утверждение верно: если 4|n, то v2(n)>=2. Кроме того, 3|n, и поэтому v3(n)>=1. Тогда ясно, что n делится на 22*3=12 ч. т.д.
Второе утверждение неверно: Если 4|n, то v2(n)>=2. Если 6|n, то v2(n)>=1 и v3(n)>=1. В общей сложности получается, что v3(n)>=1, а v2(n)>=max(1,2)=2 (важно, что тут максимум, а не сумма!). Тогда n делится на 22*3=12, но не обязательно на 24. Действительно, числа 12, 36, 60, 84... делятся на 4 и на 6, делятся, как и было доказано, на 12, но они не делятся на 24.

3. Число 5А делится на 3. Верно ли, что А делится на 3? А верно ли, что если 15А делится на 6, то А делится на 6?
Первое утверждение верно: если 3|5А, то v3(5A)>=1. v3(5)=0 (5 на 3 не делится), откуда v3(A)=v3(5A)-v3(5)>=1, т. е. 3|A, ч. т.д.
Второе утверждение неверно: 6=2*3, откуда v2(15A)>=1, v3(15A)>=1. Но 3 входит и в разложение числа 15, поэтому v3(A)=v3(15A)-v3(15)=v3(15A)-1>=0, т. е. может быть и нулем - тогда неверно 6|A. Например, так будет при А=2: 15А=30, 6|30 (а 2|A, т. к. 15 на 2 не делится).

Взаимная простота. НОК и НОД. 2 целых числа называются взаимно простыми, если у них нет общих делителей, кроме 1 (и -1). Это кратко записывается как (m, n)=1.

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

(!) Любые 2 различных простых числа взаимно просты.

2. Если m|A, n|A и (m, n)=1, то mn|A. Действительно, делимость A на m и n означает vp(A)>=vp(m) и vp(A)>=vp(n), то есть vp(A)>=max(vp(m),vp(n)). По п.1 все простые множители m и n различны. Поэтому, если какое-то p входит, например, в разложение m (vp(m)>0), то в разложение n оно не входит (vp(n)=0). Отсюда нетрудно заметить, что max(vp(m),vp(n))=vp(m)+vp(n)=vp(mn) для всех p, входящих в разложение m или n, т. е. входящих в разложение mn. Тогда для таких p vp(A)>=vp(mn), откуда mn|А, ч. т.д.

2'. Вообще говоря, (m, n)=1 равносильно max(vp(m),vp(n))=vp(m)+vp(n) для всех p (то есть, так записывается взаимная простота в терминах степеней вхождения). То, что это равенство имеет место для взаимно простых m и n, мы уже проверяли (и для множителей, не входящих в разложение m или n, это тоже верно: max(vp(m),vp(n))=max(0,0)=0=0+0=vp(m)+vp(n)). Теперь пусть это равенство верно: из двух чисел vp(m), vp(n) большее всегда равно их сумме. Тогда, конечно, меньшее равно нулю. При таком условии быть одновременно ненулевыми эти числа не могут. Значит, нет такого p, которое одновременно входит в разложение m и n. А это, по п.1, и означает взаимную простоту.

3. Если A|mn и (A, m)=1, то А|n. Действительно, т. к. A|mn, то vp(mn)>=vp(A) для всех p. (m, A)=1, поэтому для всех p, входящих в разложение A, vp(m)=0 (такое рассуждение здесь уже было). Значит, vp(n)=vp(mn)>=vp(A) для всех таких p, откуда А|n, ч. т.д.