?

Log in

No account? Create an account
решение задачки олимпиадного типа - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

решение задачки олимпиадного типа [июн. 26, 2004|05:01 am]
Anatoly Vorobey
Подробный и элементарный разбор решения задачки, которую я запостил утром. Он длинный и даже слишком длинный, по двум причинам: во-первых, я разжевал всё, чтобы было как можно более понятным, включая совершенно очевидные для математика шаги; во-вторых, я решал её в уме и “в лоб”, и все вычисления и проверки тоже делались в уме и очень быстро, поэтому у меня не было стимула искать что-то элегантнее. В записанном виде это получается громоздким, и наверняка есть способы ускорить решение и отбросить множество мелких проверок, просто мне лень этим заниматься.

Кстати, если я упустил какую-то ошибку, что вполне возможно, сообщите мне, пожалуйста.



Итак, нам нужно доказать, что nnnn - nnn делится на 1989 для n>=3. Эта разность имеет вид nx-x, где x=nnn ; но нам окажется удобнее смотреть на неё не так, а как на разность na - nb, где a=nnn, b=nn, и переходить от условий на эти числа к условиям на a и b.

1989 раскладывается на множители так: 1989 = 9*13*17. Для того, чтобы доказать, что исходная разность делится на 1989, необходимо и достаточно доказать, что она делится на 9, 13 и 17 по отдельности. Это значит, в свою очередь, что остатки от деления на 9 чисел nnnn и nnn равны, и то же верно для 13 и 17.

Пусть у нас есть выражение вида na mod d, т.е. остаток от деления na на d. Как мы можем облегчить его вычисление? Во-первых, n можно заменить на n mod d, и смотреть на (n mod d)a mod d - это будет то же самое (т.к. x*y mod d = (x mod d)*(y mod d) mod d : остатки при умножении чисел тоже умножаются). Во-вторых, предположим, что есть какая-то степень k, при возведении в которую n (или, что то же самое, n mod d) даёт при делении на d остаток 1. Тогда показатель степени, т.е. a, мы можем взять по модулю k и получить тот же результат. Действительно, na это просто n*n*n....*n (a раз), и если каждые k из этих раз дают остаток 1, то их можно убрать из произведения, не изменив конечный остаток; в конце концов “a раз” превращается в “a mod k раз”.

Значит, чтобы выполнялось равенство na mod d = nb mod d, при условии, что nk mod d = 1, достаточно потребовать, чтобы a mod k = b mod k: тогда после сокращения показателей мы получаем одно и то же с обеих сторон. А для того, чтобы найти такой удобный k, достаточно смотреть на степени (n mod d) вместо n: это удобнее, т.к. таких чисел мало. Так мы от требований к na и nb переходим к требованиям к a и b.

В нашем случае есть три разных требования: для d=9, 13 и 17. Рассмотрим сначала d=13 и d=17. Согласно малой теореме Ферма (у которой есть несколько простых доказательств для желающих), если d простое число (напр. 13 или 17), и n не делится на d, то nd-1 mod d = 1. Мы можем предположить, что наше число n не делится на 13, т.к. иначе то, что разность nnnn - nnn делится на 13, и так очевидно. Поэтому выходит, что для d=13 в качестве нашего k, модуля, по которому мы можем взять показатель степени, подходит d-1=12. Итак, нам нужно доказать, что nnn mod 12 = nn mod 12. То же самое для d=17: мы переходим к требованию nnn mod 16 = nn mod 16.

d=9 не простое число, но для него мы можем легко подобрать все возможные значения k для разных возможных n mod 9, которых всего 9 штук (от 0 до 8), и потом взять да и потребовать от степеней, чтобы они давали равные остатки для всех этих k, чтобы покрыть все возможные случаи. Если n mod 9 = 0, 3 или 6, то это тривиальный случай: тогда у n есть множитель 3, и очевидно, что в столь больших степенях этот множитель повторится достаточно раз для того, чтобы nnnn и nnn оба делились на 9. n mod 9 = 1 тоже очевидный случай: остаток будет всё время 1 при всех умножениях и останется 1 в обеих степенях, и при вычитании перейдёт в 0. Остаются: n=2 (можно выбрать k=6, т.к. 26= 64 = 7*9+1), n=4 (k=3 по той же причине), n=8 (k=2 по той же причине), n=7 (7^2 mod 9 = 49 mod 9 = 4; 7^3 mod 9 = 4*7 mod 9 = 28 mod 9 = 1, поэтому k=3), и n=5 (5^2 mod 9 = 7; 5^3 mod 9 = 7*5 mod 9 = 8; 5^4 mod 9 = 8*5 mod 9 = 4; 5^5 mod 9 = 4*5 mod 9 = 2; 5^6 mod 9 = 2*5 mod 9 = 1, поэтому k=6). Если мы докажем равенство показателей по модулю всех этих возможных k, этого будет достаточно, чтобы обеспечить (n mod 9)a mod 9 = (n mod 9)b mod 9, а значит и то, что исходная разность делится на 9.

Подытожим: мы спустились на одну ступень лесенки, и теперь имеем дело с числами nnn и nn. Нам нужно доказать, что равны остатки от их деления на: 12, 16, 6, 3, 2, 3, 6. Очевидно, достаточно доказать равенство для остатков 16 и 3, а все остальные из этого следуют (т.к. тогда разность этих чисел делится без остатка на 16 и 3, а значит и на 2, 6 и 12, а значит и там остатки равны).

Для d=3 годится тот же трюк, что и раньше, т.к. 3 - простое число: переходим к требованию на показатели для k=d-1=2: т.е. nn и n должны давать одинаковый остаток при делении на 2. Но это очевидно: если n чётно, то и nn чётно, а если n нечётно, то и nn нечётно.

Для d=16 нужно опять перебрать возможные значения n mod d, чтобы спуститься к более простым требованиям для показателей степени (которые теперь равны nn и n). Прежде всего, если n чётное число, то у него есть множитель 2, и учитывая тот факт, что n>=3 и чётное, в обоих наших числах nnn и nn мы возводим n в степень >=4, поэтому этот множитель 2 превращается как минимум в 16. Так что оба числа делятся на 16 без остатка, как и их разность. Именно здесь мы используем условие n>=3, т.к. для n=2 вышесказанное неверно: nn оказывается слишком малым и на 16 не делится.

Остаётся посмотреть на нечётные n, т.е. на остатки от деления на 16: 1, 3, 5, 7, 9, 11, 13, 15. Остаток 1 даёт тривиальный случай, т.к. он сохраняется при умножении (1*1 mod 16 = 1) и даёт в результате остаток 1 в обоих числах. Остатки 7, 9 и 15 приводят к 1 на второй степени, т.е. для них подходит k=2 (7^2 = 48+1, 9^2 = 16*5+1, 15^2 = 16*14+1). Остаток 3: 3^4 = 81 mod 16 = 1 (k=4). Остаток 5: 5^2=25 mod 16 = 9. 5^3 mod 16 = 9*5 mod 16 = 13. 5^4 mod 16 = 13*5 mod 16 = 1 (k=4). Остаток 11: 11^2 = 121 mod 16 = 9. 11^3 mod 16 = 9*11 mod 16 = 3. 11^4 mod 16 = 3*11 mod 16 = 1, т.е. k=4. И для остатка 13: 13^2 = 169 mod 16 = 9. 13^3 mod 16 = 9*13 mod 16 = 117 mod 16 = 5. 13^4 mod 16 = 5*13 mod 16 = 1, т.е. тоже k=4. Подытожим: перебор всех нетривиальных остатков даёт нам требования для показателей для k=2 и k=4.

Переходим опять к степеням: nn и n. Нам нужно показать, что равны остатки при делении на 2 и 4. Для 2 мы уже показали выше. Для 4 тоже просто. Случай чётного n мы уже разобрали как тривиальный на предыдущем уровне (глядя на деление по модулю 16), поэтому достаточно смотреть на нечётные n. Они дают остаток от деления на 4 равный либо 1, либо 3. Если остаток 1, т.е. n=4m+1, то и у nn такой же остаток, т.к. он сохраняется при умножении. Если остаток 3, т.е. n=4m+3, то при умножении всё время на число с остатком 3 конечное значение остатка от деления на 4 прыгает от 1 к 3 и обратно:

3 = 3 mod 4
3*3 = 9 = 1 mod 4
1*3 = 3 mod 4
3*3 = 9 = 1 mod 4
...

Кол-во прыжков равно кол-ву умножений. Если мы возводим в n-ю степень, то перемножаем n-1 раз. Т.к. n у нас нечётное число, то будет чётное число перемножений, т.е. чётное число прыжков от 3 к 1 и обратно, значит, остаток результата будет 3, как и у самого n.

Вроде всё.
СсылкаОтветить

Comments:
[User Picture]From: letaet
2004-06-25 08:02 pm

Когда ты сказал "решал её в уме", я прикинул, что мне это не по силам – и отказался тратить время на бумажные выкладки. Но после того, как ты её "разжевал", я окончательно умываю руки :)

Буду утешать себя влажным от слёз "а помнится... когда-то... квант... олимпиады..."
(Ответить) (Thread)
[User Picture]From: dyak
2004-06-27 07:24 pm
Дык и не мудрено, если Вы только не учились в школе, где Малая теорема Ферам входила в программу.
(Ответить) (Parent) (Thread)
[User Picture]From: max_dnepr
2004-06-25 08:18 pm
Кстати, если я упустил какую-то ошибку
В этой фразе :)
Ошибку можно допустить, вроде так.
(Ответить) (Thread)
From: dontdo
2004-06-26 09:20 am
Ошибку можно и упустить (например, при перечитывании).
(Ответить) (Parent) (Thread)
From: oblomov_jerusal
2004-06-25 10:07 pm

Упрощения

Для 9 можно пользоваться теоремой Эйлера (kφ(N))=1 (mod N) для взаимно простых k, N). Для 16 можно вспомнить, что &Phi(2n) не циклическая и потому порядки элементов в &Phi(16) делят &phi(16)=8 и не равны 8, т.е. делят 4.
(Ответить) (Thread)