Теория чисел на САММАТе —Каталог задач по Олимпиадной математике

Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
Теория чисел на САММАТе

Тема САММАТ (Самарская математическая олимпиада)

Теория чисел на САММАТе

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела саммат (самарская математическая олимпиада)

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#80195

Число $abccba$ состоит из попарно не совпадающих, отличных от нуля цифр $a,b,c$ и делится на $231.$ Сколько существует таких чисел?

Подсказки к задаче

Подсказка 1

Логично, что рассматривать делимость на число 231 будет неразумно, поскольку оно слишком большое. Давайте разложим 231 на множители и рассмотрим делимость для них.

Подсказка 2

231 = 3 * 7 * 11. Обратите внимание, что для делимости на 11 нам подойдут любые a, b, c, так как a – b + c – c + b – a = 0. Но для делимости на 7 нам необходимо, чтобы число abc – cba делилось на 7. Как можно переписать это условие?

Подсказка 3

Распишем по разрядам числа abc и cba. abc = a*10² + b*10 + c и bca = с*10² + b*10 + a. Разность таких записей должна будет делиться на 7. Какие тогда мы получаем ограничения на a, b, c?

Подсказка 4

Из разности abc – cba следует, что |a – c| должно делиться на 7, а b – любое. Осталось только рассмотреть подходящие случаи a и c, и такие b для них, чтобы число делилось на 3.

Показать ответ и решение

Так как число должно делиться на $231= 3⋅7⋅11,$ то оно должно делиться на $3,7$ и $11.$

a− b+c− c+ b− a =0

делится на $11$ при любом выборе $a,b,c,$ поэтому число $abccba-$ делится на $11.$

По признаку делимости на $7$ разность $|abc− cba|$ должна делиться на $7.$

--- --- || 2 2 || || 2 || |abc− cba|= a ⋅10 + b⋅10 +c− c⋅10 − b⋅10− a = (a − c)10 − (a− c) =|a− c|⋅99

т.е. $|a− c|$ должно делиться на $7.$

Это возможно лишь, если $(a= 9,c =2),(a= 8,c= 1),(a =1,c= 8),(a= 2,c= 9),$ при произвольном $b.$ Осталось выяснить, сколько возможных значений $b$ приходится на каждую из перечисленных пар.

Для нахождения достаточно выяснить делимость на $3$ числа $abc.$

1) $a= 9,c= 2⇒ 9+ b+ 2= 11 +b.$ Делимость на 3 числа $9b2-$ возможна в трех случаях: $b1 =1;b2 = 4;b3 = 7;$

2) $a= 8,c= 1⇒ 8+ b+ 1= 9+b.$ Делимость на 3 числа $8b1$ возможна в трех случаях: $b = 3;b = 6;b = 9;(b⁄= 0). 1 2 3$

Остальные случаи симметричны рассмотренным. Таким образом, на каждую из найденных пар $a$ и $c$ приходится по 3 возможных значения $b.$

Ответ: 12

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#77778

Доказать, что при всех натуральных $n$ число $32n+3+ 40n− 27$ делится на 64.

Подсказки к задаче

Подсказка 1

Для начала давайте преобразуем наше выражение, 3²ⁿ⁺³ можно представить как 27*3²ⁿ. То есть можно вынести что-то за скобочки!

Подсказка 2

Да, после несложных преобразований получим, что исходное выражение преобразуется в 27*(9ⁿ-1) + 40n. Остаётся доказать, что это выражение делится на 64 при любом натуральном n. Каким методом для доказательства лучше воспользоваться?

Подсказка 3

Верно, это может сделать через индукцию! Но перед этим введём вспомогательную лемму. Попробуйте доказать, что 9ⁿ-1 делится на 8 для любого натурального n.

Подсказка 4

Да, 9 сравнимо с 1 по модулю 8, так что доказывается несложно. Пусть 27*(9ⁿ-1) + 40n делится на 64, попробуйте доказать, что оно делится на 64 при n=n+1

Подсказка 5

Да, при переходе к n+1 получим 27*(9ⁿ⁺¹-1) + 40(n+1) = 27*(9ⁿ-1) + 40n + 40 + 27*8*9ⁿ. Остаётся правильно сгруппировать на слагаемые! То есть так, чтобы каждое из них делилось на 64

Показать доказательство

Воспользуемся методом математической индукции.

2n+3 2n n 3 +40n− 27= 27⋅3 − 27+ 40n =27(9 − 1)+ 40n,

при $n= 1$ выполняется деление на $64.$ Пусть это выражение делится на $64$ при $∀n >1.$

Рассмотрим это выражение при $(n+ 1).$ Имеем

n+1 n 27(9 − 1)+ 40(n +1)= 27(9 ⋅(8+1)− 1)+40n+ 40=

=27(9n − 1)+ 27⋅8⋅9n +40n+ 40=

=(27(9n− 1)+40n)+ 216⋅9n+ 40=

= (27(9n − 1)+ 40n)+ (216(9n − 1))+ 256

Каждое из трех слагаемых делится на $64,$ первое — по предположению, второе — потому что $216$ и $9n−1$ делятся на $8$ каждое ( $9k ≡8 1∀k ∈ℕ.$ ) и $256$ делится на $64$ .

Ошибка.
Попробуйте повторить позже

Задача 3#88136

Найти целое число $N$ , содержащее простыми множителями только 2, 5 и 7, зная, что:

1) $5N$ имеет на 8 делителей больше, чем $N$ ;

2) $7N$ имеет на 12 делителей больше, чем $N$ ;

3) $8N$ имеет на 18 делителей больше, чем $N$ .

Подсказки к задаче

Подсказка 1

Неважно, что даны простые делители именно 2, 5 и 7, важно только, что их ровно три различных. Вспомним волшебную формулу из веба, которая определяет число делителей, зная степени вхождения всех простых!

Подсказка 2

После применения формулы к трем условиям нашей задачи получим три уравнения с тремя неизвестными. После упрощения система приобретает вид: uv=a, vw=b, uw=c. Такие системы встречаются довольно часто, и решаем мы их, перемножив все три выражения, а далее, подставляя полученное значение uvw в изначальные уравнения, находим оттуда u, v, w.

Показать ответ и решение

Число $N$ имеет вид: $N =2x⋅5y⋅7z$ . Число его делителей по известной формуле равно $(x+ 1)(y+ 1)(z+ 1)$ . Число $5N = 2x ⋅5y+1⋅7z$ и число его делителей равно: $(x+ 1)(y+2)(z+1)$ . Согласно условию:

(x+ 1)(y+ 2)(z+ 1)− (x+ 1)(y+1)(z +1)= 8

или $(x+ 1)(z+ 1)=8$ . Число $7N = 2x⋅5y⋅7z+1$ . Аналогично предыдущему, получим: $(x+ 1)(y+1)= 12$ . Наконец, $8N = 2x+3⋅5y⋅7z$ , откуда найдем: $3(y+ 1)(z+ 1)=18$ или: $(y+ 1)(z+ 1)=6$ .

Получили систему трех уравнений с тремя неизвестными, которая обычно решается так. Перемножив три уравнения системы, найдем

2 2 2 (x+ 1) (y +1) (z+ 1) =8⋅12⋅6

откуда

(x+ 1)(y+1)(z +1)= 24.

Деля это уравнение последовательно на первое, второе и третье уравнение системы, получим: $y+ 1= 3;z +1 =2;x+ 1= 4$ . Отсюда: $x =3;y = 2;z =1$ . Следовательно,

N = 23⋅52⋅7= 1400.

Ответ: 1400

Ошибка.
Попробуйте повторить позже

Задача 4#79774

Сколько решений в натуральных числах имеет уравнение

4 4 4 x1 +x2+ ⋅⋅⋅+ x13 =2017?

Подсказки к задаче

Подсказка 1

Можно попробовать написать какие-то оценки, но, кажется, сразу это не сработает. Давайте применим арифметику остатков и вспомним, что по модулю 16 у числа x⁴ существует всего 2 вида остатков...

Подсказка 2

2017 дает остаток 1 при делении на 16, а x⁴ дает остаток 0 или 1. Поэтому ровно одно из чисел xₙ нечетно. Для определенности пока будем считать, что это именно x₁₃. Каким может быть x₁₃?

Подсказка 3

Верно, x₁₃<7. Поэтому нам остается проверить только x₁₃=1,3 и 5. Используя остатки по модулю 16 разберите эти случаи и не забудьте, что переменные можно менять местами.

Показать ответ и решение

Если $x$ — чётно, то $x4 ≡ 0, 16$ а если $x$ – нечётно, то $x4 ≡1. 16$ Так как $2017 =16⋅126+1,$ то $2017 ≡ 1. 16$ Значит, ровно одно из $x k$ нечётно $($ не умаляя общности, возьмём $x13),$ а остальные чётны, так как слагаемых всего $13.$