Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

решение задачки олимпиадного типа

Подробный и элементарный разбор решения задачки, которую я запостил утром. Он длинный и даже слишком длинный, по двум причинам: во-первых, я разжевал всё, чтобы было как можно более понятным, включая совершенно очевидные для математика шаги; во-вторых, я решал её в уме и “в лоб”, и все вычисления и проверки тоже делались в уме и очень быстро, поэтому у меня не было стимула искать что-то элегантнее. В записанном виде это получается громоздким, и наверняка есть способы ускорить решение и отбросить множество мелких проверок, просто мне лень этим заниматься.

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



Итак, нам нужно доказать, что 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.

Вроде всё.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 5 comments