Рассылка решений заочных туров олимпиад по математике

Подписывайтесь на нашу рассылку решений заочных туров всех олимпиад по математике: Ломоносов, Покори Воробьевы горы, Высшая проба, Физтех 2018 и другие перечневые олимпиады.

Подготовка к очному туру ОММО - теория чисел, цифры, делимость, остатки, степени


  • Сезон олимпиад 2016-2017 открыт!
    Идет запись на наши курсы подготовки к олимпиадам по математике с гарантированным результатом.
    image
    1. Индивидуальные занятия и консультации.
    2. Помощь в прохождении заочных туров олимпиад. Одна олимпиада 1-5 тыс. руб.
    3. Помощь эксперта на очных турах олимпиад. Одна олимпиада от 30 тыс. руб.
    4. Гарантия успешного результата (курсы ведутся пятый сезон).

    Стоимость курсов от 3000 до 25000 руб. в месяц. Стандартный курс - 10000 руб. в месяц. Длительность курсов - 6 месяцев.
    В составе стандартного курса заочные туры 10 олимпиад и очные туры 2 олимпиад.
    Посмотреть тарифные планы и подробную информацию по курсам подготовки.


    Материалы для экспресс-подготовки к очному туру ОММО.

    Часть 2. Задания №2 и №3. Теория чисел, цифры (разряды), делимость, остатки, степени.


    Инструкция по работе с материалами:
    1. Материалы состоят из теории, 17 задач с решениями и 12 задач для самостоятельного решения.
    2. Среднее время работы с материалами - 300-360 минут.
    3. Теория переписывается на отдельном листке, запоминается. В дальнейшем листок может использоваться в виде шпаргалки. 30-40 минут.
    4. Все задачи с решениями разбираются письменно. Устное чтение решений не сработает. Общее время - 150-180 минут.
    Записали блок решения, разобрали, записали второй блок, разобрали.
    В решениях желтым фоном выделены ключевые формулы. Красным шрифтом выделены ключевые комментарии и пояснения.
    Такая верстка удобна для восприятия скелета решения и запоминания важнейших переходов.
    5. Только после разбора всех задач с решениями приступаете к самостоятельному решению задач (блок "Аналогичные задачи").
    Решаете все аналогичные задачи, сверяетесь с ответами. Если совпали 10+ ответов, то результат положительный (следовательно, на олимпиаде вы успешно решите задачи №2 и №3). По возможности, исправляете ошибки. Общее время - 100-120 минут.

    Остальные материалы в разделе ОММО.
    Часть первая. Прогрессии и последовательности.
    Часть третья. Системы, параметр, графики, функции, логика.
    Вопросы, комментарии или замечания оставляйте в теме или отправляйте на почту ommo@olympiads.biz.
  • Теория чисел: целые числа, разряды (цифры), делимость, остатки, степени.
    1. `bar(abc...)` - десятичная запись числа, где `a,b,c,...` - цифры. Любая цифра принимает целое значение от `0` до `9`, при этом `a!=0`.
    `bar(ab)=10a+b` - двузначное число,
    `bar(abc)=100a+10b+c` - трехзначное число,
    `bar(abcd)=1000a+100b+10c+d` - четырехзначное число.
    `bar(a_n...a_1)=10^(n-1)a_n+...+10a_2+a_1` - `n`-значное число.
    2. Число `a` делится на `b`, если `a=kb`, где `k` - целое. Обозначается, как `a vdots b`.
    Если `a` не делится нацело на `b`, то дает остаток `d`: `a=kb+d`, при этом `d in [0;b-1]`.
    Например, `n vdots 3 => n=3k, k in ZZ`.
    Или, `n` дает остаток `3` при делении на `5 => n=5k+3, k in ZZ` или `n-3 vdots 5`.
    3. Число делится на `3` (или на `9`) `iff` сумма цифр числа делится на `3` (или на `9`).
    Обощенный признак делимости на `3` (и на `9`): число и сумма цифр числа дают одинаковый остаток при делении на `3` (и на `9`).
    Число делится на `5`, если последняя цифра `5` или `0`.
    4. `a^n-b^n vdots a-b`. Это следует из формулы `a^n-b^n=(a-b)(a^(n-1)+...+b^(n-1))`.
    `a^(2n+1)+b^(2n+1) vdots a+b`. Из формулы суммы нечетных степеней.
    5. Цикл последней цифры.
    Последняя цифра выражения `a^n` (с увеличением `n`) повторяется с каким-то периодом.
    Например, `2^1=2, 2^2=4, 2^3=8, 2^4=16, 2^5=32, 2^6=64` и т.д. Получили `4` цифры `{2,4,8,6}`, которые повторяются в этой же последовательности.
    6. Стратегия решений задач на целые числа - делимость и ограничения.
    То, что задача в целых числах, уже является ограничением. Далее используем типовые свойства целых чисел, чтобы получить новые ограничения на искомую величину. В конечном итоге получаем конечное число вариантов или все решения.
    Максимальные ограничения дают свойства делимости. Положим, мы получили соотношение вида `8a=11(b+...)`. `8` и `11` взаимно-просты, поэтому `a` делится на `11`.
    Либо, `ab=15`. Понятно, что все пары таких целых `(a,b)` легко перечислить.  
    7. Остатки.
    При делении на `d` существует `d` остатков от `0` до `d-1`.
    Некоторые выражения дают не все остатки при делении на какое-либо число.
    Например, `2n` не может дать остаток `3` при делении на `6`, иначе `2n-3 vdots 6`, т.е. нечетное число делится на четное.
    Либо, `k^2` не может дать остаток `2` или `3` при делении на `4`. Для этого достаточно возвести все остатки `k` (от `0` до `3`) в квадрат.
    Если `a` дает остаток `d` при делении на `n`, то `a^k` дает остаток `d^k` при делении на `n`.
  • Задача №1 (ОММО 2015 - №3).
    Четырехзначное число `X` не кратно `10`. Сумма числа `X` и числа, записанного теми же цифрами в обратном порядке, равна `N`. Оказалось, что число `N` делится на `100`. Найдите `N`.

    Решение:
    `X=bar(abcd)=1000a+100b+10c+d`, где `a,d!=0`.
    `X'=bar(dcba)=1000d+100c+10b+a`.
    По условию, `X+X' vdots 100`. Ключевое условие.
    `X+X'=1001a+1001d+110b+110c=a+d+10(b+c)+100(10a+10d+b+c).`
    `a+d+10(b+c) vdots 100 =>` `a+d vdots 10`. Ключевое следствие - делимость.
    Ограничение `a+d in [2;18]` `=> a+d=10`.
    `10+10(b+c) vdots 100 => b+c+1 vdots 10`.
    `b+c+1 in [2;19] => b+c+1=10 => b+c=9`.
    Тогда, `N=1001(a+d)+110(b+c)=1001*10+110*9=11000`. Нет необходимости находить значения всех переменных  `a,b,c,d`.
    Ответ: `11000`.

    Аналогичная задача:
    Четырехзначное число `X` не кратно `10`. Сумма числа `X` и числа, полученного из `X` перестановкой его второй и третьей цифр, делится на `900`. Найдите остаток от деления числа `X` на `90`.
    Ответ: `45`.

    Задача №2 (ОММО 2015 - №3-3).
    Если из четырехзначного числа `X` вычесть сумму его цифр, то получится натуральное число `N=K^2`, причем `K` - натуральное число, дающее остаток `2` при делении на `10` и остаток `6` при делении на `11`. Найдите число `N`.

    Решение:
    `X=bar(abcd)=1000a+100b+10c+d`, где `a!=0`.
    По условию, `X-(a+b+c+d)=``999a+99b+9c=N=K^2`. Условие задачи.
    `K^2=9(111a+11b+c) vdots 9 =>` `K=3M` - делимость.
    `M^2=111a+11b+c<=111*9+11*9+9=1107 =>` `M<=33, K<=99` - ограничения.
    С другой стороны, `K=10n+2, K=11m+6`. Второе условие задачи.
    Перебором легко убедиться, что только одно число от `1` до `99` дает такие остатки. Это число - `72`.
    Проверка: `111a+11b+c=576`,
    `11b+c in [0;108] => a=5 => 11b+c=21`. Решений нет.
    Ответ: решений нет.

    Аналогичная задача:
    Если из четырехзначного числа `X` вычесть сумму его цифр, то получится натуральное число `N=K^2`, причем `K` - натуральное число, дающее остаток `5` при делении на `20` и остаток `3` при делении на `21`. Найдите число `N`.
    Ответ: `2025`.

    Задача №3 (ОММО 2014 - №3).
    Натуральное `61`-значное число `A` записывается только цифрами `2, 3` и `4`. При этом двоек на `19` больше, чем четверок. Найдите остаток от деления числа `A` на `9`.

    Решение:
    Число `A` дает такой же остаток при делении на `9`, что и сумма цифр `A`. Признак делимости на `9`.
    Пусть `f(A)` - сумма цифр, `k` - количество четверок. Тогда, `k+19` - двоек, а троек - `(61-k-k-19)`.
    `f(A)=``4k+2(k+19)+3(42-2k)=6k+38+126-6k=``164`. Ключевое соотношение.
    `f(A)` дает остаток `2` при делении на `9`, поэтому число `A` дает остаток `2` при делении на `9`.
    Ответ: `2`.

    Признак делимости на `9` можно использовать без доказательства, хотя доказательство простое:
    `A=bar(a_na_(n-1)...a_1a_0)=10^na_n+...+10a_1+a_0`.
    `A-f(A)=sum_(k=0)^n(a_k(10^k-1))` - в сумме каждое слагаемое делится на `9`, поскольку `10^k-1 vdots 10-1=9` (особый случай `10^0-1=0`).

    Аналогичная задача:
    Натуральное `59`-значное число `A` записывается только цифрами `3, 4` и `5`. При этом пятерок на `8` больше, чем троек. Найдите остаток от деления числа `A` на `9`.
    Ответ: `1`.

    Задача №4 (ОММО 2013 - №3).
    Докажите, что число `2^2014+1` можно представить в виде произведения трех натуральных чисел, больших `1`.

    Решение:
    `a^(2n+1)+1 vdots a+1`. Формула делимости.
    `2014=2*19*53`, поэтому `2^2014+1=(2^(2*19))^53+1 vdots 2^(2*19)+1`.
    В свою очередь, `2^(2*19)+1=(2^2)^19+1` делится на `2^2+1`.
    Тогда, `2^2014+1=5*(2^38+1)/5*(2^2014+1)/(2^38+1)`.
    Представили наше число в виде произведения трех натуральных чисел, больших `1`.

    Аналогичная задача:
    Докажите, что число `4^2013+1` можно представить в виде произведения трех натуральных чисел, больших `1`.

    Задача №5 (ОММО 2012 - №3).
    Найдите последнюю цифру числа `7^(2012^2011)-3^(12^11)`.

    Решение:
    `7^4=2401, 3^4=81`. Ключевое замечание задачи.
    Пусть `2012^2011=4n, 12^11=4k`, где `n,k` - натуральные числа.
    Тогда, `7^(2012^2011)=7^(4n)=2401^n` - оканчивается на `1` при любых натуральных `n`.
    Аналогично, `3^(12^11)=81^k` - оканчивается на `1` при любых натуральных `k`.
    Разность двух выражений всегда оканчивается на `0`.
    Использовали известный инвариант (постоянная величина) - число с последней цифрой `1` в любой степени будет оканчиваться на `1`.
    Ответ: `0`.

    Аналогичная задача:
    Найдите последнюю цифру числа `7^(2012^2011)+3^(12^11)`.
    Ответ: `2`.

    Задача №6 (ОММО 2011 - №3).
    Одна тетрадь, `3` блокнота и `2` ручки стоят `98` рублей, а `3` тетради и блокнот - на `36` рублей дешевле `5` ручек. Сколько стоит каждый из предметов, если тетрадь стоит четное число рублей? (Каждый из этих предметов стоит целое число рублей).

    Решение:
    Пусть `2n,k,m` - стоимость тетради, блокнота и ручки соответственно.
    По условию, `n,k,m` - натуральные числа.
    `{(2n+3k+2m=98),(6n+k+36=5m):}` - система из двух уравнений с тремя неизвестными, но зато в целых числах.
    `2n=98-2m-3k => 3(98-2m-3k)+k+36=5m`,
    `8k+11m=330 => 8k=11(33-m) vdots 11 =>` `k vdots 11` - ключевая делимость.
    С другой стороны, `3k=2(49-n-m) vdots 2 => k vdots 2 => k vdots 22`.
    При этом, `3k=98-2m-2n<=94 =>` `k<=31 => k=22`. Ограничения.
    Тогда, `m=14, n=2, 2n=4`.
    Ответ: `4,22,14`.

    Аналогичная задача:
    Туземец из племени Танга-Танга за `111` стрел в порядке натурального обмена мог получить `2` барабана, `3` жены и одну леопардовую шкуру. Две леопардовые шкуры ценились на `8` стрел меньше, чем `3` барабана и `4` жены. Сколько стрел по отдельности стоили барабан, жена и леопардовая шкура, если за леопардовую шкуру нужно было отдать четное число стрел? (Каждый из этих предметов стоит целое число стрел).
    Ответ: `20,9,44`.

    Задача №7 (ОММО 2010 - №2).
    В диване живут клопы и блохи. Боря лежит на диване и рассуждает: если клопов станет в несколько раз больше, то всего насекомых будет `2012`, если блох станет во столько же раз больше, а число клопов не изменится, то всего насекомых будет `2011`. Сколько же насекомых живет в диване сейчас?

    Решение:
    `a` - количество клопов, `b` - количество блох, `k` - мультипликатор.
    `{(ak+b=2012),(a+bk=2011):}` - снова система из двух уравнений с тремя неизвестными.
    `ak-a+b-bk=1`,
    `a(k-1)-b(k-1)=1`,
    `(a-b)(k-1)=1 => a-b=k-1=1` - ключевая делимость.
    `k=2 => {(2a+b=2012),(a+2b=2011):} => {(a=671),(b=670):}`,
    `a+b=1341`.
    Ответ: `1341`.

    Задача №8 (ОММО 2009 - №2).
    Докажите, что `6255^3-5995^3` делится на `13`.
    Решение:
    `a^3-b^3 vdots a-b`.

    Задача №9 (ОММО 2013 - №1).
    Ученикам `11`А класса на выбор предложили пройти тестирование ровно по одному из предметов: химии, информатике или физике. Трое ребят приняли участие в тестировании по химии; более `40`%, но менее половины учеников проходили тестирование по информатике и ровно треть - по физике. Сколько ребят участвовало в тестировании по информатике, если в классе присутствовало более `12` учеников?

    Решение:
    `m` прошли тест по информатике, `n` - по физике.
    По условию, `{(m+n+3=3n),(2/5*3n<m<1/2*3n):}`,
    `{(m=2n-3),(6/5n<2n-3<3/2n):}`.
    `4/5n>3 => n>15/4 =>` `n>=4`. Взяли ближайшее целое число.
    Но число учеников (`3n`) больше `12`, поэтому `n>=5`. Новое ограничение.
    `1/2n<3 =>` `n<6 => n<=5`. И еще одно ограничение.
    Следовательно, `n=5 => m=2n-3=7`.
    Ответ: `7`.

    Аналогичная задача:
    Ученикам `11`Б класса на выбор предложили пройти тестирование ровно по одному из предметов: биологии, математике или химии. Двое ребят приняли участие в тестировании по биологии; более трети, но менее `40%` учеников проходили тестирование по химии и ровно половина - по математике. Сколько ребят участвовало в тестировании по химии, если в классе присутствовало более `16` учеников?
    Ответ: `7`.

    Задача №10 (ОММО 2013 - №2).
    Из Москвы на Международный шахматный турнир в Нью-Васюках шахматисты всех команд (одинаковых по численности) добирались двумя способами. Некоторые команды заняли все места в `5`-местных и одной `2`-местной каютах парохода “Повелитель бурь”. Другие команды предпочли занять все места в `7`-местных и одной `4`-местной каютах дирижабля “Скрябин”. Сколько спортсменов было в команде, если занятых `7`-местных кают оказалось на одну больше, чем занятых `5`-местных?

    Решение:
    Пусть в команде `n` человек, `x` - число `7`-местных кают, `a,b` - число команд на параходе и дирижабле.
    Тогда, `{(na=5(x-1)+2),(nb=7x+4):}` - два уравнения, четыре неизвестные.
    `{(7na=35x-21),(5nb=35x+20):} => 5nb-7na=41`,
    Ключевая делимость `n(5b-7a)=41 => 41 vdots n` `=> n=1;41`.
    Ответ: `41` или `1`.

    Аналогичная задача:
    В автомобильном пробеге Москва–Удоев–Москва участвовали несколько (одинаковых по численности) делегаций автолюбителей. Некоторые из этих делегаций заняли все места в `3`-местных “Паккардах” и одном `4`-местном “Лорен-Дитрихе”, а остальные делегации предпочли занять все места в `5`-местных “Студебеккерах” и одном `2`-местном “Фиате”. Сколько автолюбителей было в делегации, если “Студебеккеров” в пробеге оказалось на `5` больше, чем “Паккардов”?
    Ответ: `61` или `1`.
  • Задача №11.
    Можно ли в трехзначном числе, делящемся на `37`, переставить цифры так, чтобы полученное число тоже делилось на `37`?

    Решение:
    Докажем, что если число `A=bar(abc)` делится на `37`, то и число `B=bar(bca)` также делится на `37`.
    Имеем `A=100a+10b+c=37k => c=37k-100a-10b`.
    Тогда `B=100b+10c+a=100b+10(37k-100a-10b)+a=370k-999a vdots 37`.
    Ответ: можно.

    Задача №12.
    В магазине было 6 ящиков с яблоками массой `15` кг, `16` кг, `18` кг, `19` кг, `20` кг, `31` кг. Две организации взяли `5` ящиков, причем одна из них взяла по массе в `2` раза больше яблок, чем другая. Какой ящик остался в магазине?

    Решение:
    Пусть одна организация взяла ящики общей массой `n` кг, тогда другая организация взяла ящики общей массой `2n` кг, а всего они взяли ящики массой `3n` кг, где `n` - натуральное число.
    Общая масса всех ящиков `15+16+18+19+20+31=119` кг. Надо убрать ящик с такой массой, чтобы общая масса остальных делилась на `3`. Подходит только ящик с массой `20` кг.
    Остальные `5` ящиков можно распределить на две группы с массами `n=33` и `2n=66`.
    Ответ: `20`.

    Задача №13.
    Пусть `x` - последняя цифра простого числа `p>3`. Докажите, что `p+2^((x-1)/2)` - число составное.

    Решение:
    `x` может принимать значения `5, 7` и `9`. При этом `x=5` только при `p=5`, все остальные числа с последней цифрой `5` являются составными.
    `x=p=5 => p+2^((x-1)/2)=5+4=9` - число составное.
    `x=7 => p+2^((x-1)/2)=p+8` - число оканчивается на `5` (`p` оканчивается на `7`), а значит составное (делится на `5`).
    `x=9 => p+2^((x-1)/2)=p+16` - аналогично.

    Задача №14.
    Докажите, что если `a^2+b^2` делится на `3`, то `a` и `b` делятся на `3`.

    Решение:
    Пусть `k` дает остатки `0,1,2` при делении на `3`.
    Тогда `k^2` дает остатки `0,1,4` при делении на `3`. Остаток `4` равносилен остатку `1`. Иначе говоря, квадрат целого числа дает остатки `0` или `1` при делении на `3`.
    `a^2+b^2` делится на `3`, значит дает остаток `0` при делении на `3`. Тогда оба квадрата дают остаток `0`, в противном случае один из них должен дать остаток `2`, что невозможно.

    Аналогичные задачи:
    Докажите, что если `a^2+b^2` делится на `7`, то `a` и `b` делятся на `7`.
    Докажите, что `3^n` нельзя представить в виде суммы квадратов двух целых чисел.

    Задача №15.
    Может ли дискриминант квадратного уравнения с целыми коэффициентами равняться `23`?

    Решение:
    Квадратное уравнение `ax^2+bx+c=0`, где `a,b,c` - целые числа.
    `D=b^2-4ac=23 => b^2=4ac+23`.
    `4ac+23` дает остаток `3` при делении на `4`, но квадрат целого числа `b^2` не может давать остаток такой остаток.
    `b^2` дает остаток `0` или `1` при делении на `4`.
    Ответ: нет.

    Задача №16.
    Докажите, что для любого натурального `N` число `N^5` оканчивается на ту же цифру, что и `N`.

    Решение:
    Два числа оканчиваются на одну и ту же цифру `iff` их разность делится на `10`.
    `N^5-N=N(N^4-1)=N(N^2-1)(N^2+1)=N(N-1)(N+1)(N^2+1)`.
    `N(N-1)` всегда четно `=> N^5-N vdots 10`.
    Если `N` дает остаток `0` или `+-1` при делении на `5`, тогда `N^5-N` делится на `5`.
    Пусть `N` дает остаток `2` или `-2`, тогда `N^2+1` дает остаток `4+1=5` при делении на `5`, т.е. делится на `5`.
    Следовательно, `N^5-N vdots 10` при всех натуральных `N`.

    Также эту задачу легко доказать рассмотрев однозначные `N` от `0` до `9`. Для них утверждение верно, а значит оно верно и для любых `N`.

    Аналогичная задача:
    Найдите все натуральные `n`, для которых `n^10+1` делится на `10`.
    Подсказка: `n^10+1=(n^5)^2+1` и `n^2+1` дают одинаковые остатки при делении на `10`.

    Задача №17.
    Докажите, что `2^41+1` делится на `83`.

    Решение:
    `2^8=256` дает остаток `7` при делении на `83`.
    `2^40` дает остаток `7^5` при делении на `83`.
    `2^41` дает остаток `2*7^5` при делении на `83`.
    Далее сами.

    Аналогичная задача:
    Докажите, что `2^70+3^70` делится на `13`.
    Сложный способ аналогичен предыдущей задаче.
    Простой способ основан на формуле `a^(2n+1)+b^(2n+1) vdots a+b`.

Рассылка решений заочных туров олимпиад по математике