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

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

Тема Всесиб (Всесибирская открытая олимпиада школьников)

Теория чисел на Всесибе

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

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

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

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

Подтемы раздела всесиб (всесибирская открытая олимпиада школьников)

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

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

Задача 1#80744

Какое максимальное количество простых чисел можно записать, использовав каждую из десяти цифр от 0 до 9 ровно по одному разу?

Источники: Всесиб-2024, 11.1 (см. sesc.nsu.ru)

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

Подсказка 1

Если мы понимаем, что простые числа наши составляют все цифры от 0 до

Подсказка 2

Последней цифрой может быть только 1,2,3,5,7,9. Значит, чисел не больше 6. Попробуйте построить пример на 6, и тогда задача будет решена.

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

Последними цифрами простых чисел могут быть только $1,2,3,5,7,9$ . Значит, использовав каждую из десяти цифр от $0$ до $9$ по одному разу, больше шести простых чисел мы получить не сможем.

6 простых чисел уже может быть:

2,3,5,67,89,401

Ответ: 6

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

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

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

Задача 2#71444

Десятичная запись натурального числа $N$ содержит каждую цифру от 0 до 9 ровно один раз. Обозначим через $A$ сумму пяти двузначных чисел, составленных из первой и второй, третьей и четвёртой $,...,$ девятой и десятой цифр $N$ , а через $B$ — сумму четырёх двузначных чисел, составленных из второй и третьей, четвёртой и пятой $,...,$ восьмой и девятой цифр $N.$ Оказалось, что $A$ равно $B,$ может ли $N$ начинаться с чётной цифры?

Источники: Всесиб-2022, 11.1 (см. sesc.nsu.ru)

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

Подсказка 1

Распишем условие с помощью десятичной записи чисел. Какое уравнение на числа A и B у нас получится и что из него будет следовать?

Подсказка 2

Понимаем, что сумма первой и последней цифры числа делится на 9! Какой тогда может быть их сумма? Как найти связь между цифрами на четных позициях и на нечетных?

Подсказка 3

Подставляем в наше уравнение из подсказки 1 сумму первой и последней цифры, которая равна 9(почему?). Теперь мы можем найти связь между суммами цифр на четных позициях и на нечетных, а также мы знаем сумму всех цифр. Остаётся лишь осознать, как это применить)

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

Пусть $N = aa-...aa-a-, 12 8 9 10$ где $a ,a,...,a,a ,a 1 2 8 9 10$ — некоторая перестановка чисел $0,1,2,...,8,9.$ Тогда

---- ---- ----- A = a1a2+ a3a4+ ...+ a9a10 = 10(a1+a3+ ...+ a9)+ (a2+a4+ ...+ a10)

---- ---- ---- B =a2a3+ a4a5+ ...+ a8a9 = 10(a2+a4+ ...+ a8)+ (a3+a5+ ...+ a9)

Если $A= B,$ то

10a + 9(a + ...+ a)+ a = 9(a + a + ...+a ) 1 3 9 10 2 4 8

Отсюда следует, что $a1+ a10$ делится на 9.

Одна из двух различных цифр $a1,a10$ ненулевая, поэтому

a1+ a10 ≥0 +1= 1 и a1+ a10 ≤8+ 9= 17

1 ≤a1+ a10 ≤17⇒ a1 +a10 = 9

Значит,

a1+ a3+...+a9+ 1= a2+ a4 +...+ a8

Вспомним, что $a1,a2,...,a8,a9,a10$ — некоторая перестановка чисел $0,1,2,...,8,9,$ поэтому сумма всех цифр $a1,a2,...,a8,a9,a10$ равна $0+ 1+ 2+...+9 =45$ — нечётна. Тогда

a1+ a3+ ...+ a9 +a2+ a4+...+a8+ a10+1 =46= 2(a2+a4+ ...+ a8)+a10

Следовательно, цифра $a 10$ чётна, а цифра $a =9 − a 1 10$ — нечётная цифра.

Ответ: нет

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

Задача 3#79775

Найти все натуральные $n$ , которые можно представить в виде суммы

2 2 n =a + b,

где $a$ — минимальный делитель $n$ , отличный от $1,$ и $b$ — какой-то делитель $n.$

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

Подсказка 1

По условию a- минимальный делитель n, отличный от 1. В связи с этим хочется попытаться узнать его наверняка. Может даже получится доказать, что он равен 2. Давайте предположим противное. Какое противоречие мы получим?

Подсказка 2

Если минимальный делитель отличен от 2, то n- нечетное число и все его делители также нечетны. Но тогда сумма a²+b² не может быть нечетной. Противоречие. Мы выполнили свою цель и перешли к новой задаче: n=4+b². Какое ограничение возникает на b?

Подсказка 3

Заметим, что n и b² делятся на b, значит 4 также делится на b. Такое бывает крайне редко, поэтому довести решение до конца вам не составит никого труда!

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

Если $n$ нечётно, то и все его делители нечётны, поэтому правая часть равенства $n= a2+b2$ чётна — противоречие. Следовательно, $n$ чётно и его минимальный неединичный делитель $a$ равен $2,$ а $2 n= 4+ b.$

По условию $b$ делит $2 n= 4+ b,$ значит, делит и разность $2 n − b = 4,$ поэтому $b$ должно быть равно одному из чисел $1, 2, 4.$ При этом $n$ равно $5, 8, 20$ соответственно. Первый случай не подходит ввиду нечётности, остальные два удовлетворяют условию задачи.

Ответ: 8 и 20

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

Задача 4#46228

Пусть $a,b,c$ — натуральные числа. Могут ли наибольшие общие делители пар чисел $a$ и $b,b$ и $c,c$ и $a$ равняться $30!+ 111$ , $40!+234$ и $50!+666$ соответственно?

Источники: Всесиб-2020, 11.2 (см. sesc.nsu.ru)

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

Подсказка!

Мы знаем интересное свойство факториала - он делится на все числа до него. То есть все наши факториалы делятся на 2, 3, 4.... до 30! Попробуйте рассмотреть числа по какому-нибудь полезному модулю

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

Очевидно, что каждый факториал кратен $9$ . При этом $234$ и $666$ делятся на $9$ , откуда $a,b,c$ все кратны $9$ . Но тогда $30!+111$ должно делиться на $9$ , что неверно, поскольку $111 =3⋅37$ .

Ответ:

нет

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

Задача 5#79772

Найти все натуральные числа $n$ , которые можно представить в виде суммы

n = x+ y+(x,y)+ [x,y]

для некоторых натуральных чисел $x$ и $y.$

Здесь $(x,y)$ и $[x,y]$ обозначают наибольший общий делитель и наименьшее общее кратное чисел $x$ и $y$ соответственно.

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

Подсказка 1

Нам хочется что-то понять про число n, поэтому разумно будет попытаться разложить правую часть на множители. С изначальным условием не очень удобно совершать тождественные преобразования. Давайте обозначим НОД(x, y)=d, тогда x=ad, y=bd и как раскладывается правая часть?

Подсказка 2

Верно, n=d(a+1)(b+1)! Как мы понимаем, нам подходят любые d, a и b, удовлетворяющие условию НОД(a, b)=1. При каком b это условие всегда выполнено?

Подсказка 3

Верно, при b=1! Это означает, что любое n вида 2d(a+1) нам подходит. Поэтому появляется предположение о том, что любое четное число, большое 2, нам подойдет. Осталось доказать, что если n раскладывается, то оно обязательно должно быть четным...

Подсказка 4

Так как НОД(a, b)=1, то одновременно a и b делится на 2 не могут. Используйте это и завершите решение!

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

Первое решение.

Если оба числа $x$ и $y$ одной четности, то все четыре слагаемых $x, y, (x, y)$ и $[x, y]$ имеют ту же четность и их сумма четна. Если они имеют разную четность, то $(x, y)$ нечетно, а $[x, y]$ четно, потому в сумме будет два четных и два нечетных числа и она снова будет четна. Каждое ее слагаемое не меньше одного, поэтому вся сумма не меньше $4.$ Следовательно, ответом задачи может быть только четное число больше двух.

С другой стороны, для произвольного четного $n> 2$ положив $n x= 1, y = 2 − 1,$ получим $(x,y)= x= 1$ и $n [x, y]= y = 2 − 1,$ откуда $x +y+ (x, y)+[x, y]=n$ — представляется в требуемом в условии виде.

Второе решение.

Если обозначить $(x, y)= d,$ то

x =x1d, y =y1d, [x, y]= x1y1d,

где $x1, y1$ взаимно просты, значит, одно из них обязательно нечетно. Тогда

n= x+ y+(x, y)+ [x, y]= d(1+ x1)(1+ y1),

где обе скобки не меньше $2$ и одна из них обязательно четна. Следовательно, ответом задачи может быть только четное число, большее двух. Далее все как в первом решении.

Ответ: Все чётные числа, большие двух

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

Задача 6#61460

Про число $N$ известно, что оно равно произведению десяти простых чисел (не обязательно различных). Кроме того, оказалось, что если каждый из этих десяти множителей увеличить на единицу, то полученное произведение будет делиться на $N$ . Чему может быть равно $N?$

Источники: Всесиб-2019, 8.2 (см. sesc.nsu.ru)

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

Подсказка 1

В таких задачах стоит иногда попробовать подобрать какие-то варианты. И здесь начнем замечать интересное: если есть простым делителем 5 или, например, 7, тогда новое число не делится на 5 или 7. Обобщим эту догадку.

Подсказка 2

И действительно, при р > 3 всегда будут проблемы при делении числа N на р. Представьте N в виде произведения двоек и троек, где двойки войдут со степенью, например, k.

Подсказка 3

Да, получится N = 2^k * 3^(10-k), а теперь фокус: двойки превращаются в тройки, а тройки - в четверки, то есть в двойки в квадрате! Остается найти k, и так получим ответ!

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

Рассмотрим наибольший простой делитель $p$ числа $N.$

Если $p> 3$ , то все остальные делители меньше его хотя бы на $2$ (иначе есть чётное просто число больше двойки).

После увеличения всех простых множителей на $1$ получатся:

$p+ 1$ : это не кратно $p$ , ведь $p+1-=1 + 1 p p$ , а $1< p.$
любое другое простое после увеличения на $1$ будет меньше $p$ (ведь изначально оно было меньше $p$ хотя бы на $2$ ), значит, также не кратно $p$ .

Отсюда заключаем, что случай $p >3$ невозможен, поскольку новое число не поделится на $p$ и соответственно не поделится на $N.$

Тогда можно представить $N$ в виде $N =2k⋅310− k$ . Увеличим все простые множители на $1$ , получим $3k ⋅410−k = 3k⋅220−2k$ , по условию это кратно $2k ⋅310−k$ .

Значит, $20 − 2k≥ k,k≥ 10 − k ⇐ ⇒ k ∈[5,20∕3]$ . Подходят только $k∈ {5;6}$ . Осталось привести пример этих чисел и написать ответ.

Ответ:

$25⋅35,26⋅34$

Курсы

Всё необходимое для достижения цели

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

Задача 7#32933

Может ли сумма объёма, длин всех рёбер и площадей всех граней некоторого прямоугольного параллелепипеда, длины рёбер которого являются целыми числами, равняться $866$ ?

Источники: Всесиб-2018, 11.3 (см. sesc.nsu.ru)

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

Подсказка 1

Давайте для начала введём неизвестные (скажем, стороны это a,b,c) и попробуем записать сумму из условия через эти неизвестные. По условию эта сумма равна 866

Подсказка 2

Так, Вы должны были получить abc+4(a+ b+c)+ 2(ab+ bc+ ac)=866. Теперь полезно разложить на множители левую часть уравнения. Нужно добавить такое число, чтобы левая часть хорошо свернулась на симметричные относительно a,b,c скобочки. Ну же, не зря мы ботали тождественные преобразования!

Подсказка 3

Добавить нужно 8. У Вас должно получиться (а+2)(b+2)(c+2) = 2*437. Осталось совсем чуть-чуть, подумайте над этим равенством в терминах разложения на множители!

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

Пусть длины сторон $a,b,c$ . Они положительные (как длины сторон) и целые (по условию), значит, натуральные. Сумма объёма, длин всех рёбер и площадей всех граней равна $866$ , то есть:

abc+ 4(a +b+ c)+2(ab +bc+ ac)= 866

3 (a+2)(b+ 2)(c+ 2)=866+ 2 = 2⋅437

Правая часть является произведение простых чисел $2,19$ и $23$ , так что по основной теореме арифметики следует, что это единственное разложение данного числа в произведение трёх натуральных чисел, больших единицы, и одно из них равно $2$ . Однако левая часть уравнения является произведением трёх натуральных чисел, каждое из которых не меньше трёх, что приводит к противоречию. Следовательно, равенство из условия задачи невозможно.

Ответ:

нет

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

Задача 8#77849

Можно ли представить число 2017 в виде суммы двух натуральных чисел, сумма цифр одного из которых вдвое больше суммы цифр другого?

Источники: Всесиб - 2017, 9.3(см. sesc.nsu.ru)

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

Подсказка 1

На что нам намекает сумма чисел? С каким из известных фактов можно попробовать найти противоречие?

Подсказка 2

Сумма чисел намекает на модуль 3! Число дает такой же остаток по модулю 3, что и его сумма цифр :) Разберем случаи!

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

Предположим противное: что $2017$ можно представить как сумму натуральных чисел $A$ и $B,$ причём сумма цифр $A$ вдвое больше суммы цифр $B.$

При сложении двух цифр одного разряда в нём остаётся их сумма (если она меньше $10$ ), либо их сумма минус $10$ (если она больше $10,$ а единица уходит в следующий разряд). Таким образом, сумма цифр $A +B$ равна сумме цифр $A$ плюс сумма цифр $B$ минус число переходов единицы в следующий разряд при сложении, умноженное на $9.$

По условию сумма цифр $A$ вдвое больше суммы цифр $B,$ поэтому их общая сумма делится на $3,$ значит, и сумма цифр $A+ B = 2017$ должна делиться на $3$ — противоречие с тем, что сумма цифр числа $2017$ равна $10.$