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

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

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

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

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

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

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

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

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

Задача 1#119871

Найти все тройки натуральных чисел $a,b,c$ таких, что числа $ab+ 1,ac+ 1,bc+ 1$ являются факториалами некоторых натуральных чисел. Числа в тройках могут совпадать. Напоминаем, что факториалом $n!$ натурального числа $n$ называется произведение всех натуральных чисел от $1$ до $n$ включительно.

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

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

Кроме случая, когда хотя бы два из чисел $a,b,c$ равны $1,$ все числа $ab+ 1,ac+ 1,bc+ 1$ не меньше $3,$ и являются факториалами чисел, не меньших $3.$ Рассмотрим остатки от деления чисел $a,b,c$ от деления на $3.$ Заметим, что при $n≥ 3$ остаток от деления числа $n!$ на $3$ равен $0.$ Несложно убедиться, что для чисел вида $xy+ 1$ такое возможно, только если остаток одного из чисел $x,y$ равен $1,$ а другого $2.$ Следовательно, остатки от деления $a,b,c$ на $3$ могут равняться только $1$ или $2$ среди них есть равные, остаток от деления произведения которых, увеличенный на $1,$ равен $2,$ а не $0,$ как требуется. Значит, среди чисел $a,b,c$ хотя бы два равны $1,$ а третье может быть любым вида $n!− 1$ для некоторого натурального $n ≥2$ и тогда числа вида $ab+ 1,ac +1,bc+ 1$ равны $2!,n!,n!.$

Ответ:

Все тройки натуральных чисел, два из которых равны $1,$ а третье равно $n!− 1$ для произвольного натурального $n≥ 2$

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

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

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

Задача 2#80744

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

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

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

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

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

2,3,5,67,89,401

Ответ: 6

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

Задача 3#71444

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

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

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

Пусть $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$ — нечётная цифра.

Ответ: нет

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

Задача 4#79775

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

2 2 n =a + b,

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

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

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

Если $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

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

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

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

Задача 6#46228

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

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

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

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

Ответ:

нет

Курсы

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

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

Задача 7#61460

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

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

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

Рассмотрим наибольший простой делитель $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$

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

Задача 8#79772

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

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

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

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

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

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

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

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

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

Задача 9#32933

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

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

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

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

Ответ:

нет

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

Задача 10#77849

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

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

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

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

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

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

Ответ: нет

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

Задача 11#94457

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

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

Предположим противное. Упорядочим данные числа и обозначим их за $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

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

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

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

Задача 12#91461

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

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

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

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

Заметим, что $x,y <z,$ так как $12x!< z!$ и $2y!< 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− 2)(x+1)!

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

Если $x≥ 4,$ то $y ≥ 5,$ $z ≥6$ и $12≥ (z− 2)(x+1)≥ 20$ — получили противоречие.

Если $x= 3,$ то $12≥ 4(z− 2)$ и $5≥ x+ 2= 5.$ Отсюда $z = 5$ и

2y!= z!− 12x!= 48

Откуда $y = 4.$ Значит, подходит тройка $(3;4;5).$

Если $x= 2,$ то $( ) y! z!y! − 2 = 24.$ Так как $z ≥ y+ 1≥ x+ 2= 4,$ то

( ) z!− 2 ≥ z− 2≥2 y!

и поэтому $y!< 24$ и $y = 3.$ Тогда $z!= 12x!+ 2x!= 36,$ что невозможно.

Если $x= 1,$ то $y!( z!− 2)= 12. y!$ Так как $y!< 12$ и $y ≤3.$ Если $y = 2$ , то $z!= 12x!+ 2y!= 16,$ что невозможно. Если $y = 3,$ то

z!= 12x!+ 2y!=24= 4!

Значит, подходит тройка $(1;3;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 =x =13$ и тройка $(13;13;14)$ — решение.

Ответ:

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