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

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

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

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

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

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

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

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

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

Задача 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.$

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

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

Подсказка 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#91342

Пусть $m < n$ — натуральные числа. Доказать, что среди произвольных последовательных $n$ натуральных чисел всегда найдутся два, произведение которых делится на $mn$ .

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

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

Среди $n$ последовательных чисел точно найдется то, которое делится на $n$ и то, которое делится на $m$ (так как $m < n$ ). Если это разные числа, то их произведение делится на $mn$ . Пусть это одно число $a$ , $НОД (m,n)= d$ и $′ m = dm$ , $′ n = dn$ . Тогда $.. ′ ′ a.dm n$ . Значит, нам нужно найти еще одно число, которое делится на $d$ . Так как $n> m ≥d$ , то $n ≥2d$ . Значит, среди $n$ последовательных чисел есть еще хотя бы одно, которое делится на $d.$

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

Задача 5#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.$

Ответ:

нет

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

Задача 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#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$ и одна из них обязательно четна. Следовательно, ответом задачи может быть только четное число, большее двух. Далее все как в первом решении.

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

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

Задача 8#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.$ Однако левая часть уравнения является произведением трёх натуральных чисел, каждое из которых не меньше трёх, что приводит к противоречию. Следовательно, равенство из условия задачи невозможно.

Ответ:

нет

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

Задача 9#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.$

Ответ: нет

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

Задача 10#94457

На доске написаны десять чисел (среди которых могут быть равные) таких, что среднее арифметическое любых трёх из этих чисел тоже написано на доске. Доказать, что все эти числа равны между собой.

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

Подсказка 1

Хм, среднее арифметическое любых трёх чисел тоже записано на доске, довольно сильное заявление. А можем ли мы выбрать 3 числа так, чтобы точно определить, какое из чисел будет их средним арифметическим?

Подсказка 2

Можно упорядочить все числа - допустим это a₁ ≤ a₂ ≤ ... ≤ a₁₀, и выбрать 3 числа, идущие подряд - где тогда должно быть их среднее арифметическое?

Подсказка 3

Конечно, это число, стоящее посередине! А значит, можно записать много уравнений и поработать с ними, или присмотреться ещё к написанному равенству: если привести подобные слагаемые, что можно сказать об этих трёх числах, что они образуют?

Подсказка 4

Арифметическую прогрессию! А что будет с числом справа или слева от тройки, будет ли оно в той же прогрессии? Тогда какой вид имеют все числа на доске? Точно ли все средние арифметические записаны?

Подсказка 5

Получили, что все числа имеют вид a₁ + n ⋅ d, где d - разность прогрессии. Попробуйте теперь рассмотреть тройку не подряд идущих чисел - записано ли её среднее арифметическое на доске?

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

Предположим противное. Упорядочим данные числа и обозначим их за $a ,a,a ,...,a , 1 2 3 10$ что $a ≤a ≤ a ≤ ...≤ a . 1 2 3 10$ Заметим, что если мы рассматриваем тройку вида $ai,ai+1,ai+2,$ то в силу соображения, что среднее арифметическое чисел лежит между их минимумом и максимумом, среднее арифметическое данной тройки будет равно $ai+1.$

Рассмотрим сначала тройку $a1,a2,a3 :$

a1+ a2+a3 ----3---- =a2

a1 +a3 = 2a2

a1+ a3 --2---= a2

Следовательно, $a1,a2$ и $a3$ образуют арифметическую прогрессию. При этом если её разность нулевая, т.е. эти числа равны, то, рассматривая тройки вида $ai,ai+1,ai+2,$ мы получим, что все числа равны, поэтому данная прогрессия имеет ненулевую разность.

Аналогично рассмотрев тройку $a2,a3,a4,$ показываем, что эти числа тоже образуют арифметическую прогрессию. Пусть $a1,a2,a3$ и $a4$ — это арифметическая прогрессия с ненулевой положительной разностью $d,$ тогда $a2 = a1+ d$ и $a4 =a1+ 3d.$ Рассмотрим тройку $a1,a2,a4 :$

a1+a2+-a4 a1+-a1+-d+a1+-3d 3a1+-4d- 4 3 = 3 = 3 = a1+ 3d

Но такого числа нет на доске, противоречие.

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

Задача 11#91461

Найти все решения в натуральных числах уравнения

12⋅x!+2⋅y!= z!

Здесь $n!$ обозначает произведение всех натуральных чисел от 1 до $n$ включительно.

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

Заметим, что $x,y <z$ , так как $x!> y!$ и $x!> z!$ .

Если $x> y$ , то $(z! ) 2y!= z!− 12x!=x! x! − 12 ≥x!$ . Второй множитель целый, так как $z >x$ . Значит, $2y!≥ x!≥ (y+1)!$ . Отсюда $y =1$ , $x!= 2$ и $x= 2$ . Тогда $z!= 24+2 =26$ ?!

Если $y > x$ , то $(z! ) 12x!= z!− 2y!=y! y! − 2 ≥(z− 2)y!$ . Второй множитель целый, так как $z > y$ . Значит, $12x!≥ (z− 2)y!≥(z− 2)(x+ 1)!$ и $12≥ (z− 2)(x +1)$ .

Если $x≥ 4$ , то $y ≥ 5$ , $z ≥6$ и $12≥ (z− 2)(x+1)≥ 20$ ?!

Если $x= 3$ , то $12≥4(z− 2)$ и $5≥ z ≥ x+ 2= 5$ . Отсюда $z = 5$ и $2y!= z!− 12x!=48.$ Откуда $y = 4.$ Значит, подходит тройка $(3;4;5).$

Если $x= 2$ , то $( z! ) y! y! − 2 = 24$ . Так как $z ≥ y+ 1≥ x+ 2= 4$ , то $(z! ) y! − 2 ≥z − 2≥ 2$ и поэтому $y!< 24$ и $y = 3$ . Тогда $z!= 12x!+ 2z!= 36$ ?!

Если $x= 1$ , то $( ) y! z!y! − 2 = 12$ . Так как $y!< 12$ и $y ≤ 3$ . Если $y = 2$ , то $z!= 12x!+2y!=16$ ?! Если $y = 3$ , то $z!= 12x!+ 2y!= 24= 4!$

Если $x= y$ , то $z!= 14x!≥7$ . Раз $. z!..7$ , то $z ≥ 7$ . Если $z ≥ x+2$ , то $14x!= z!≥ z(z − 1)(z− 2)!≥ 7⋅6y!$ ?! Значит, $z = x+ 1$ . Тогда $z =14$ и $y = z = 13.$

Ответ:

( $x= 1,$ $y = 3,$ $z = 4$ ), ( $x= 13,$ $y = 13,$ $z =14$ ), ( $x =3,$ $y = 4,$ $z = 5$ )

Предыдущий раздел

Следующий раздел