Теория чисел на СПБГУ: десятичная запись, оценка+пример, разные системы счисления —Каталог задач по Олимпиадной математике

Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
Теория чисел на СПБГУ: десятичная запись, оценка+пример, разные системы счисления

Тема СПБГУ

Теория чисел на СПБГУ: десятичная запись, оценка+пример, разные системы счисления

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

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

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

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

Подтемы раздела спбгу

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

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

Задача 1#87412

Решите уравнение в целых числах

2 2 n m + k = 2024 + 33

Источники: СПБГУ - 2024, 11.4 (см. olympiada.spbu.ru)

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

Подсказка 1

Тот факт, что у нас есть слагаемое, которое мало на что делится, говорит о том, что его, в теории, можно использовать при доказательстве в смысле рассмотрения делимости на его множители. Давайте, к тому же, заметим, что 2024 кратно 11 и будем рассматривать делимости на 11. Что вы можете сказать про делимость на 11 обеих частей при разных n? А при фиксированном n и разных m, k?

Подсказка 2

Возможные остатки квадратов mod 11 - это 0, 1, 3, 4 5, 9. Какие пары этих остатков в сумме дают 0(нам ведь нужна делимость на 11 левой части)? Только пара 0 - 0. Значит, что оба числа кратны 11, а значит левая часть кратна 11². Всегда ли кратна правая часть 11²? Если нет, то при каких n кратна 11²?

Подсказка 3

При n ≥ 2 первое слагаемое кратно 11², а 33 нет. Значит, кратность может быть только при n = 0 или n = 1. При n = 1, у нас правая часть превращается в 17 * 11². Значит, все таки есть кратность 11, а значит верны наши рассуждения про m и k. Но тогда мы можем представить их в виде 11t и сократить на 11², после чего, довести до ответа. А случай n = 0 - оставляется читателю в качестве упражнения.

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

Числа $m$ и $k$ являются целыми числами, следовательно, каждое из чисел $m2$ и $k2$ являются целыми, а значит, и их сумма $2 2 m +k$ является целыми числом, таким образом, число $n 2024 +33$ также является целым, т.е. число $n 2024$ целое, откуда $n ≥0$ .

_________________________________________________________________________________________________________________________________________________________________________________

Пусть $n≥ 2$ . Тогда $n 2024 + 33$ делится на 11, поскольку каждое из чисел 2024 и 33 кратно 11, но не делится на $2 11$ , т.к. первое слагаемое кратно $2 11$ , а второе — нет.

Пусть число $x$ дает остаток 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 при делении на 11, тогда число $2 x$ дает соответственно остаток 0, 1, 4, 9, 5, 3, 3, 5, 9, 4, 1 при делении на 11. Докажем, что если хотя бы одно из чисел $m$ и $k$ не делится на 11, то и число $2 2 m +k$ не делится на 11.

Предположим обратное, тогда сумма остатков чисел $m2$ и $k2$ равна 11, следовательно, ровно одно из чисел $m2$ и $k2$ даёт четный остаток при делении 11, а значит, соответствующий квадрат даёт остаток 0 или 4 при делении на 11, но тогда второй остаток равен 0 или 7, что невозможно. Таким образом, каждое из чисел $m$ и $k$ кратно 11, следовательно, каждое из чисел $m2$ и $k2$ кратно $112$ , таким образом, $m2 +k2$ кратно $112$ , но $2024n +33$ не кратно $112$ .

_________________________________________________________________________________________________________________________________________________________________________________

Тогда $n = 0$ или $n =1.$

Пусть $n= 1$ . Тогда $2024n+ 33 =2024+ 33 =2057= 112 ⋅7$ , следовательно, $m2+ k2$ кратно $112$ , а значит, как мы показали выше, каждое из чисел $m$ и $k$ кратно 11. Пусть $m = 11a$ , $k =11b$ , где $a$ и $b$ являются целыми числами, следовательно, $a2+ b2 =17$ . Легко убедиться, что всеми решениями $(a,b)$ данного уравнения являются неупорядоченные пары $(±1,±4).$ Следовательно, все пары решений $(m,k)$ это $(±11,±44)$ , $(±11,±44)$ .

Пусть $n= 0$ . Тогда $2024n+ 33 =1 +33= 34$ . Если каждое из чисел $m$ и $k$ не превосходит по модулю 4, то сумма их квадратов не превосходит 32, следовательно, наибольшее из чисел $m$ и $k$ по модулю не меньше 5. С другой стороны, если какое-то из чисел по модулю больше 5, то его квадрат не меньше 36, что невозможно. Таким образом, в паре чисел $(m,k)$ хотя бы одно равно 5 по модулю, тогда второе равно 3 по модулю. Тем самым, мы показали, что все пары решений $(m,k)$ есть $(±5,±3)$ , $(±3,±5)$ .

Ответ:

$(0;±3;5),(0;±3;− 5),(0;±5;3),(0;±5;−3),$

$(1;±11;44),(1;±11;−44),(1,±44;11),(1,±44;−11)$

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

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

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

Задача 2#87405

Кузнечик прыгает по числовой прямой. Каждый свой прыжок он может совершить в любом направлении. Он начинает в точке 0 прыжком единичной длины. Каждый следующий прыжок должен быть на три больше предыдущего (т.е. первый прыжок длины 1, второй длины 4, третий длины 7 и т.д.). За какое наименьшее число прыжков кузнечик сможет оказаться в точке 2024?

Источники: СПБГУ - 2024, 11.1 (см. olympiada.spbu.ru)

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

Подсказка 1

Попробуем как-то оценить n…а как вообще посчитать, насколько далеко мы ушли от начала координат?

Подсказка 2

Заметим, что наши прыжки - это члены арифметической прогрессии a ₙ = 3n-2. Тогда на какое наибольшее расстояние мы можем уйти от нуля? Каким тогда должно быть n?

Подсказка 3

Максимальное расстояние, на которое мы можем уйти - это (3n-1)n/2. И мы знаем, что это число должно быть не менее 2024. Теперь у нас есть какая-то оценка на n. А как (в зависимости от прыжков влево) посчитать местоположение кузнечика?

Подсказка 4

Обозначим общую длину прыжков влево как х. На какой клетке тогда находится кузнечик? Каким тогда должно быть n?

Подсказка 5

Кузнечик будет стоять на точке (3n-1)n/2 - 2х. Осталось лишь понять, каким должен быть n ;)

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

Процесс прыжков можно описать следующим образом: $n$ прыжков кузнечика — это сумма $n$ первых членов арифметической прогрессии $an =3n− 2$ , в которой перед каждым членом стоит $+$ или $−$ . Ясно, что за $n$ прыжков кузнечик сможет оказаться не более, чем в $(3n−1)n 2$ — сумма $n$ первых членов, в которой все члены взяты с $+$ . Значит, необходимо, чтобы $(3n−1)n- 2$ было не меньше $2024$ . То есть $n ≥37$ .

Пусть кузнечик прыгал влево некоторое количество прыжков, и суммарно он прыгнул влево на $x$ единиц, тогда после $n$ прыжков он окажется в точке $(3n−1)n 2 − 2x$ . Значит, чтобы попасть в $2024$ , необходимо, чтобы $(3n−1)n- 2$ было чётным. Значит, $37$ и $38$ прыжков не хватит. В качестве примера на $39$ можно прыгнуть влево на $2$ и на $39$ прыжках, а на остальных — вправо.

Ответ: 39

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

Задача 3#67958

Найдите все простые $p,$ для которых числа $p+ 1$ и $p2+1$ являются удвоенными квадратами натуральных чисел.

Источники: СПБГУ-23, 11.2 (см. olympiada.spbu.ru)

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

Подсказка 1

Пусть p+1 = 2x², p²+1 = 2y². Вот давайте вычтем эти два выражения: будет p(p-1) = 2(y-x)(y+x). Про что можно тут подумать, раз слева стоит простой множитель?

Подсказка 2

Про делимости! У нас делится на p либо 2, либо y-x, либо y+x. Если проверить p = 2, то он не подойдет. А может ли y-x делится на p?

Подсказка 3

Можно заметить, что т.к. p+1 = 2x², то x<p, а также y<p и x<y. Тогда y-x тем более < p и он на него не делится. Остается, что y+x делится на p. Используя наши оценки на x и y, поймите, чему равно y+x и решите полученную системку!

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

Пусть

2 2 2 p+1 =2x и p +1 =2y ,

тогда

2 2 p(p− 1)= 2(y − x )= 2(y− x)(y+ x)

Поэтому одно из чисел 2, $y− x$ и $y+ x$ кратно $p.$ Если 2 кратно $p,$ то $p= 2,$ что невозможно, поскольку $p+1 =3$ не является удвоенным квадратом.

Первый способ.

Из неравенства $x < y < p$ следует, что

x+ y = p

Таким образом, имеем систему из двух уравнений

( { x +y = p ( 2(y− x) =p− 1

Решаем её

( ( { x+ y = p { 2x +2y = 2p p+1- ( 2(y − x)= p− 1 ⇒ ( 2y − 2x= p− 1 ⇒ 4x =p+ 1⇒ x = 4

Значит,

( p+1-)2 p +1= 2 4

Следовательно, $p= 7.$

Второй способ.

Если $y− x$ делится на $p,$ то

y +x >y− x≥ p⇒ 2(y− x)(y+ x)≥2p2 > p(p − 1)

Значит, это невозможно. Следовательно, $y+x$ делится на $p.$ Заметим, что

y2= p2+-1> p2−-1= p− 1 x2 p +1 p +1

Тогда если $p ≥11,$ то

y2 > 10x2 ⇒ y > 3x

Значит,

2(y− x)> y+ x≥ p

Стало быть,

2(y− x)(y+ x) >p2 > p(p +1)

Но этого не может быть. Таким образом, осталось рассмотреть случаи $p= 3,p =5$ и $p= 7.$ В первых двух из них $p+ 1$ не является удвоенным квадратом, а $p= 7$ подходит.

Ответ: 7

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

Задача 4#70478

Натуральное число $x$ в системе счисления с основанием $r(r≤ 36)$ имеет вид $ppqq,$ причем $2q =5p.$ Оказалось, что $r$ -ичная запись числа $2 x$ представляет собой семизначный палиндром с нулевой средней цифрой. (Палиндромом называется число, которое читается одинаково слева направо и справа налево). Найдите сумму $r$ -ичных цифр числа $2 x.$

Источники: СПБГУ-22, 11.4 (см. olympiada.spbu.ru)

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

Подсказка 1

Давайте потихоньку "причёсывать" задачу. Что даёт равенство из условия на числа p и q? Это значит, что мы можем записать p = 2s, а q = 5s, где s какое-то целое число. Попробуйте теперь записать x и x² в явном виде, учитывая условие с палиндромом. Получается ли там что-то относительно хорошее? Удобно ещё палиндром как-то обозначить.

Подсказка 2

Ага, получается, что после всех преобразований x= s (2r² + 5) (r + 1). Давайте обозначим палиндром abc0cba, где a, b, c соответственно какие-то цифры r - ичной системы. Тогда сгруппировав слагаемые в x² получится a(1 + r⁶) + b(r + r⁵) + c(r² + r⁴). Выходит нам нужно узнать сумму цифр, то есть 2(a+b+c). Давайте теперь приравняем два представления числа x². Учитывая, что у нас r - ичная система счисления, делимость на какое выражение тогда можно рассмотреть? Можете рассмотреть разные варианты и со временем придёте к нужному.

Подсказка 3

Верно, давайте рассмотрим делимость на (r + 1)², так как x² будет делиться на него, но нам интересна другая часть неравенства. Но появляется вопрос, как же находить остаток при делении степеней r на (r + 1)²? Попробуйте это понять, записав r^n = (1 + r -1)^n и раскрыв по биному Ньютона.

Подсказка 4

Ага, аккуратными вычислениями понимаем, что степень числа r даёт остаток (-1)^n (1-n (r+1)). Ничего страшного, если не получилось вывести, можете просто проверить по индукции, что это правда. Теперь попробуйте применить это к нашему выражению. Какой факт тогда можно понять про числа a, b, c?

Подсказка 5

Ага, из-за ограничения на a, b, c(они в r - ичной системе счисления) можно понять, что b = a + c. И раз мы узнали факт про b, то хорошо было бы тогда оценить именно его, чтобы потом сумму цифр легко найти. Поэтому попробуйте по аналогии посмотреть остаток при делении x² на 1 + r², а точнее сравнение. Там будет хорошо пописать неравенства для r и s, учитывая все ограничения, связанные с делимостью, системой счисления и количеством цифр.

Подсказка 6

Ага, для начала получаем, что r⩾6, и из сравнения, записав двойное неравенство для (9s² − b), будет следовать, что b = 9s². Далее останется только получить из верхнего ограничения для r, что s=1, а значит, b=9. Теперь осталось только посчитать правильно сумму цифр, и победа!

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

Договоримся писать $u≡ v (modw ),$ если $.. (u− v) .w.$ Пусть $p= 2s,q = 5s.$ Тогда $---- ( ) ( ) x = ppqqr = pr2+ q (r+ 1)= s2r2+ 5(r+ 1).$ Из условия на $x2$ вытекает равенство

( )( ) ( ) ( ) ( ) s22r2+ 52 r2+ 2r+1 = a 1+ r6 + b r+r5 + cr2+ r4 ,

(1)

где $a,b,c$ — некоторые $r$ -ичные цифры. Сделаем два наблюдения.

1) При любом натуральном $n$

rn =(1+ r− 1)n ≡ (−1)n(1− n(1 +r)) (mod(1+ r)2)

Левая часть $(1)$ кратна $(1+ r)2,$ откуда

0≡ a(2− 6(1 +r))− b(2− 6(1+ r))+ c(2− 6(1+ r))= 2(1− 3(1+ r))(a− b+ c) (mod(1+r)2)

Поскольку $1− 3(1+ r)$ взаимно просто с $(1+ r)2,$ на $(1+ r)2$ делится $2(a− b+ c).$ Но это число лежит в интервале $(−2r,4r)⊂ (− (1 +r)2,(1+r)2),$ откуда $b =a+ c.$

2) Приравняем остатки левой и правой частей $(1)$ от деления на $1+ r2 :$

18s2r≡ br(1+ r4)≡2br (mod (1+r2))

Поскольку $r$ взаимно просто с $1+ r2,$ на $1+r2$ делится $2(9s2− b).$ Заметим, что $4s2 ≤ r− 1$ , иначе число $x2$ будет восьмизначным. Кроме того, $r ≥5s+ 1≥ 6$ . Поэтому

( 2 ) 2 9 2 ( 2 ) 2 2 9s − b < 18s ≤ 2(r− 1) <6r< 1+ r, 2 9s − b ≥− 2b >− 2r >− 1− r

Таким образом, $2 b= 9s.$

Поскольку $b$ — $r$ -ичная цифра, из 2) вытекает, что $2 9s < r≤ 36$ , откуда $2 s < 4.$ Так как $s> 0,$ мы получаем $s= 1$ и $b= 9.$ В силу 1) сумма цифр $x2$ равна $2(a +b+ c)=4b= 36.$

Замечание.

Прямым вычислением проверяется, что $2255221 = 495059421$ . Таким образом, описанная в условии ситуация реализуется.

Ответ: 36

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

Задача 5#70475

На картинке нарисовано несколько кружочков, соединённых отрезками.

$PIC$

Саша выбирает натуральное число $n$ и расставляет в кружочках различные натуральные числа так, чтобы для всех этих чисел выполнялось свойство: если числа $a$ и $b$ не соединены отрезком, то сумма $a+b$ должна быть взаимно проста с $n,$ a если соединены, то числа $a+ b$ и $n$ должны иметь общий натуральный делитель, больший 1.

При каком наименьшем $n$ существует такая расстановка?

Источники: СПБГУ-22, 11.1 (см. olympiada.spbu.ru)

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

Подсказка 1

Чтобы как-то снизить количество вариантов для n, давайте подумаем: а может ли n быть чётным?

Подсказка 2

Нет, поскольку если n чётно, то по принципу Дирихле найдутся два числа одинаковой чётности, которые не будет соединены! А значит их сумма кратна 2, поэтому НОД не будет равен 1. А теперь, зададимся вопросом: а могут ли три суммы четырех последовательно соединенных чисел быть кратны одному и тому же делителю числа n?

Подсказка 3

Нет, ведь в таком случае сумма крайних чисел(которые не соединены ребром) - тоже будет кратна этому делителю! То есть, число n не может равняться степени нечётного простого, поэтому оно кратно хотя бы двум различным нечётным простым! Теперь мы хотим взять минимальные простые(дли минимальности n), то есть, надо узнать, а может ли n быть кратно 3?

Подсказка 4

И опять-таки нет, n не может быть кратно 3. Поскольку, в таком случае найдётся пара чисел, соединенных ребром, сумма которых не будет кратна 3(для этого достаточно рассмотреть остатки при делении 3) То есть тройки не может быть среди простых! Осталось проверить, можно ли составить пример для n=5*7.

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

Сделаем два замечания.

1) $n$ нечетно. Действительно, пусть $n$ четно. Среди семи чисел всегда есть три числа одной четности, и по условию они должны быть попарно соединены. Но на картинке нет циклов длины 3.

2) Если $q$ — простой делитель $n,$ то среди четырех последовательно соединенных чисел существует пара соседних, сумма которых не кратна $q.$ Возьмем цепочку $(a,b,c,d)$ последовательно соединенных чисел. По условию

. a +d= (a+ b)− (b+c)+ (c+ d).. p

Тогда числа $a$ и $d$ тоже соединены, то есть на картинке получился цикл длины 4, которого там нет.

Из 1) и 2) вытекает, что число $n$ имеет по крайней мере два различных нечетных простых делителя. Пусть их ровно два (скажем, $p$ и $q).$ Покажем, что они отличны от 3. Допустим, например, что $p= 3.$ Не более двух чисел делятся на 3 (если их три, то они образуют цикл). Остальные числа разобьем на две группы, дающие при делении на 3 остатки 1 и 2. Одна из этих групп пуста, иначе любое число из меньшей группы будет соединено по крайней мере с тремя числами из другой группы, что невозможно. Сумма чисел из одной группы на 3 не делится. Поэтому существует трехзвенная цепочка, в которой сумма любой пары соединенных чисел не кратна 3 и, значит, делится на $q.$ Но это противоречит 2).

Таким образом, если $n$ имеет ровно два различных нечетных простых делителя, то $n ≥5 ⋅7 =35.$ Если же таких делителей больше двух, то $n≥ 3⋅5⋅7= 105 >35$ . Расстановка для $n= 35$ приведена на рисунке.

$PIC$

Ответ: 35

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

Задача 6#80508

Петя написал на доске подряд $n$ последовательных двузначных чисел $(n≥ 2)$ , первое из которых не содержит цифру 4, а последнее — цифру 7. Вася подумал, что это десятичная запись натурального числа $x$ и разложил $x$ на простые множители. Оказалось, что их всего два и они различаются на 4. Что написано на доске?

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

Пусть меньшее из простых чисел равно $p$ . Заметим, что так как $p(p+ 4)$ число хотя бы 4-значное, то $p> 10$ . Тогда $p$ может оканчиваться на 1, 3, 7 и 9. В этих случаях $p(p +1)$ будут оканчиваться на 5, 1, 7 и 7 соответственно. Так как последнее из $n$ чисел не содержит 7, то $p$ не может отказываться на 7 и 9. Если $p$ оканчивается на 1, то $p+ 4$ оканчивается на 5, простое и больше 10?! Значит, $p$ оканчивается на 3 и равно $10k +3$ . Тогда число на доске равно $2 (10k+3)(10k+ 7)= 100k + 200k+ 21$ . Значит, последнее написанное число равно 21.

Если $n= 2$ , то число на доске $2021= 43⋅47$ подходит

Если $n= 3,4,6,7,9,10,12$ , то число на доске $192021$ , 18192021, 161718192021, 15161718192021, 131415161718192021, 12131415161718192021 или 101112131415161718192021 делится на 3, но у числа должны быть только 2 простых делителя и оба больше 10.

Если $n= 5$ , то число на доске 1718192021 делится на 7, но у числа должны быть только 2 простых делителя и оба больше 10.

Если $n= 8$ , то первое число будет 14?!

Если $n= 11$ , то число на доске будет 1112131415161718192021 делится на 11, но точно не равно $11⋅7$ или $11⋅15$ .

Ответ: 2021

Курсы

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

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

Задача 7#80504

В стране Лимонии в обращении используются монеты достоинством $3n,3n−1⋅5,3n−2$ . $52,3n−3⋅53,...,3⋅5n−1,5n$ пиастров, где $n$ — натуральное число. Житель страны зашел в банк, не имея при себе наличных денег. Какую наибольшую сумму ему не смогут выдать в банке?

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

Обозначим нужное число за $A n$ и попробуем его найти по индукции. Заметим, что если из монет $3n,3n−1⋅5,...,3⋅5n−1,5n$ мы можем собрать любое число большее $An$ , то из монет $n+1 n n n+1 3 ,3 ⋅5,...,3⋅5,5$ мы сможем собрать любое число большее $n+1 3An+ 2⋅5$ так: если мы хотим получить число $n+1 A >3An +2⋅5$ , то возьмем такое $k$ от 0 до 2, что $n+1 A − k5$ делилось на 3. Тогда $A−k5n+1- 3 > An$ и значит, его можно представить как $A−k5n+1- n n−1 n 3 = k03 + k13 ⋅5+ ...+ kn5$ , где $ki$ целые и неотрицательные. Тогда $n+1 n+1 n n A = k⋅5 +k03 +k13 ⋅5+ ...+ kn5 ⋅3$ .

Теперь пусть из монет $n+1 n n n+1 3 ,3 ⋅5,...,3⋅5 ,5$ мы сможем собрать число $n+1 B =3An +2 ⋅5$ , то есть $B = k03n+1+ k13n ⋅5 +...+ kn5n⋅3+ kn+1 ⋅5n+1$ , где $ki$ целые и неотрицательные. Заметим, что 3 монеты вида $5n+1$ можно обменять на 5 монет $3⋅5n$ . Значит, можно считать, что $kn+1 ≤2$ . С другой стороны, $B− kn+15n+1 = 3An +(2− kn+1)5n+1$ делится на 3, и значит, $kn+1 ≡ 2 (mod 3)$ и $kn+1 = 2$ . Тогда $n+1 B−2⋅53---= An =k03n+ k13n−1⋅5+ ...+ kn5n$ , где $ki$ целые и неотрицательные. Это значит, что из монет $3n,3n− 1⋅5,...,3⋅5n−1,5n$ мы смогли собрать $An$ ?!

Значит, мы доказали, что из монет $3n+1,3n ⋅5,...,3⋅5n,5n+1$ можно собрать любое число большее $B = 3An+ 2⋅5n+1$ и нельзя собрать $B = 3An+ 2⋅5n+1$ . Значит $An+1 = 3An +2⋅5n+1$ . Тогда $An+1− 3An +2 ⋅5n+1− 5(An − 3An− 1+2 ⋅5n)= An+1− 8An+ 15An −1 = 0$ . Из этого рекурсивного отношения получаем, что $An =a3n+ b5n$ . Тогда $An+1 − 3An +2⋅5n+1 = a3n+1+b5n+1− a3n+1− 3⋅b5n+2 ⋅5n+1 = 5n(2b− 10)=0$ и значит $b= 5$

Заметим, что для $n =1$ мы можем получить все числа хотя бы 10, так как для любого $A ≥10$ существует $k$ от 0 до 2 такое, что $. A − 5k..3$ и $A − 5k ≥0$ . Значит, $A = 5k +3 ⋅ A−35k$ . Так же $9=3 ⋅3$ , $8 =3+ 5$ , а вот 7 получить уже не получится. Значит $A1 =7 =3a+ 5b= 3a+25$ . Отсюда $a =− 6$ и $A = 5⋅5n− 6⋅3n$ .

Ответ:

$5⋅5n− 6⋅3n,n ∈ℕ$

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

Задача 8#81492

Какое наибольшее количество нечетных натуральных чисел от $1$ до $3600$ можно покрасить в черный цвет, чтобы нельзя было выбрать такую тройку различных черных чисел $a,b$ и $c,$ что $a$ делится на $b$ и $b$ делится на $c?$

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

Для любого нечётного $n ≤3600,$ не кратного $3,$ рассмотрим геометрическую прогрессию $n,3n,32n,...,3tn.$ Очевидно, что прогрессии, у которых различные первые члены, не имеют общих членов. Также отметим, что любое число от $1$ до $3600$ входит в какую-то прогрессию.

Всего существует $1200$ таких прогрессий и $800$ из них имеют первый член, больший $1200.$ По условию в прогрессии может быть не более двух чёрных чисел. В прогрессий, у которой первый член больше $1200,$ не более одного чёрного числа (потому что их вторые члены уже больше $3600$ ). Поэтому, всего не более $(1200− 800)⋅2+ 800= 1600$ чёрных чисел.

Предъявим пример: покрасим все нечётные числа между $400$ и $3600.$ Предположим, что нашлись такие чёрные числа $a,b,c,$ что $.. a.b$ и $.. b.c,$ тогда $a≥ 3b≥ 9c≥ 9⋅401= 3609> 3600,$ поскольку числа нечётные, противоречие.

Ответ:

$1600$

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

Задача 9#73688

Даны натуральные числа от $1$ до $2040,$ причем $n$ чисел покрашены в зеленый цвет. При каком наибольшем $n$ может оказаться так, что ни одна степень двойки не покрашена и не представима в виде суммы двух зеленых чисел?

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

Рассмотрим пары вида $(1024− k,1024+ k)$ где $k∈1,2,...,1016.$ В каждой паре имеется хотя бы одно непокрашенное число, поскольку $11 (1024− k)+ (1024+k)= 2 .$

Аналогичным образом получается, что пары $(1,7),(2,6),(3,5)$ содержат не менее трех непокрашенных чисел. Наконец, числа $4$ и $1024,$ не попавшие ни в одну из пар, по условию тоже не окрашены. Таким образом, имеется не менее $1021$ непокрашенных чисел, откуда $n ≤1019.$

Покажем, что полученная оценка реализуется. Покрасим числа $5,6,7,$ а также все числа от $1025$ до $2040.$ Пусть $m$ и $n$ — зеленые числа. Нам достаточно проверить, что $m + n$ не является степенью двойки. Если $m, n< 8$ то это очевидно. В случае $m,n> 1024$ мы получаем $11 12 2 =2048< m+ n≤ 2040+2040= 4080< 4096= 2 .$

Наконец, если $m< 8$ и $n> 1024,$ то $1024< m +n < 2048.$

Ответ:

$1019$

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

Задача 10#72107

Какое наибольшее количество натуральных чисел от $1$ до $2500$ можно покрасить в желтый цвет так, чтобы произведение любых двух желтых чисел не было желтым?

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

Заметим, что единица не окрашена, так как $1⋅1= 1.$ Кроме того, в паре $(50,2500)$ одно из чисел не окрашено. Рассмотрим набор чисел $2 2 2 2 2 2,3,...,49;51,52,...,98;50 − 48,50 − 47 ,...,50 − 1.$ Все эти числа различны, так как $2 2 50− 48 = 98 ⋅2 >98.$ Разобьём их на тройки вида $2 2 (50− n,50+ n,50 − n ),$ где $n ∈[1;48].$ Поскольку $2 2 (50− n)(50+ n)=50 − n ,$ в каждой тройке есть хотя бы одно неокрашенное число, а всего имеется $48$ таких троек. Таким образом, мы нашли $50$ неокрашенных чисел, поэтому количество жёлтых чисел не превосходит $2450.$

Покажем, что эта оценка реализуется. Покрасим все числа от $51$ до $2500.$ Такая раскраска нам подходит, поскольку произведение любых двух жёлтых чисел больше $2500.$

Ответ:

$2450$

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

Задача 11#80505

Дано натуральное число $x$ , десятичная запись которого состоит из $n$ цифр и не содержит нулей. Числа $x$ и $x2$ в десятичной системе одинаково читаются слева направо и справа налево. Найдите все $n,$ при которых такое $x$ существует.

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

Заметим, что

2 1 = 1

112 = 121

1112 = 12321

...

2 111111111 = 12345678987654321

Значит, $n$ от 1 до 9 подходит. Осталось доказать, что $n≥ 10$ не походит. Пусть $x= an=1...a0$ . Тогда $x2 = b0+ 10b1 +...102n−2b2n$ , где $bk = a0ak +a1ak−1+...+aka0$ для $k < n$ и $bk =b2n−2−k$ . Докажем, что $bk ≤ 9$ по индукции.

База: $b0 = a20$ . Значит, нам нужно доказать, что $a0 ≤ 3$ .

Если $a0 =an =4$ , то $5 ⋅5n−1 >x >4⋅10n−1$ и $25 ⋅52n−2 > x2 > 16⋅102n−2$ . Тогда последняя цифра у $x2$ будет 6, так как у $x$ последняя цифра 4, а первая цифра у $x2$ будет 1 или 2?! Аналогично для $an = 5,6,...,9$ .

Переход: Мы доказали, что $b0,...bk− 1 ≤9$ . Теперь докажем, что $bk ≤9$ . Мы знаем, последние $k$ цифр в $x2$ . Значит мы знаем и первые $k$ цифр. Заметим, что $x2 < 42⋅102n−2$ . Если $x2 ≥ 102n−2$ , то первая цифра у $x2$ может быть только 1, с другой стороны для этого $x≥ 3⋅10n−1$ , то есть у $x$ должна быть последняя цифра 3 и тогда у $x2$ последняя цифра 9?! Значит $102n− 1 > x2 >102n−2$ .

2n−2−k 2n−2−k bk10 =b2n−2−k10 ≤

≤x2− b 102n−2− b 102n− 3− ...b 102n−1−k <102n−1− k 2n−2 2n−3 2n−2−k+1

Отсюда $bk < 10.$

С другой стороны, $bk ≥ k+1$ для $k≤ n− 1$ . Значит, при $n ≥10$ число $b9≥ 10$ ?!

Интенсивы

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

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

Задача 12#80507

На доске написано произведение чисел $ИКС-$ и $КСИ-$ , где буквы соответствуют различным ненулевым десятичным цифрам. Это произведение шестизначное и оканчивается на C. Вася стёр с доски все нули, после чего там осталось $---- ИК С$ . Что было написано на доске?

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

Заметим, что $ИКС-⋅К-СИ ≡C ⋅И (mod 10)$ . Значит И $⋅$ С - С = С(И - 1) $..10 .$ . Тогда либо $C$ делится на 5 и С = 5, либо И - 1 делится на 5 и тогда И = 1 или 6.

Так же заметим, что $-------- 2 ИКС ⋅К СИ ≡И + К + С (mod 9)$ , а с другой стороны сумма цифр произведения это И + К + С. Значит (И + К + С) $2$ - И - К - С делится на 9. Значит И + К + С дает остаток 1 или 0 при делении на 9. Так же $6= 1+ 2+3 ≤$ И + К + С $≤9 +8+ 7= 24$ и значит И + К + С = 9, 10, 18 или 19.

Пусть И = 1. Тогда последние 2 цифры произведения такие же как у $2 2 10К⋅И +10С + С⋅И = 10(К+ С )+ С$ . Заметим, что последние 2 цифры или КС или 0C. Если $2 10(К+ С )+С ≡ КС$ , то $2 .. С .10$ , но C не 0?! Значит, $2 10(К +С )+ С≡ C$ и $2.. К + С .10$ . Если С = 2, то К = 6 и тогда $-------- ИКС ⋅К СИ =100602$ нам подходит.

Если С = 3, то К = 1?!

Если С = 4, то К = 4?!

Если С = 5, то К = 5?!

Если С = 6, то К = 4 и С + К + И = 11?!

Если С = 7, то К = 1?!

Если С = 8, то К = 6 и С + К + И = 15?!

Если С = 9, то К = 9 и С + К + И = 11?!

Пусть И = 6. Тогда С нечетное. Так как $-------- ИКС ⋅К СИ≥ 612⋅126 >70000$ и у произведения первая цифра должна быть И = 6, то $---- ---- И КС⋅КСИ ≥ 600000$ . Понятно, что $---- ИКС ≤ 698$ и поэтому $---- КСИ ≥859$ и К $≥ 8$ . Если К = 8, то И + К + С = С + 14 = 9, 10, 18 или 19 и из-за того, что С четное, то оно равно 4, но такие И, К и С нам не подходят (проверяется подстановкой). Если К = 9, то И + К + С = С + 15 = 9, 10, 18 или 19 и из-за того, что С четное, то оно равно 4, но такие И, К и С нам не подходят (проверяется подстановкой).

Если С = 5, то И нечетное, не 1 и не 5. Если И = 3, то И + К + С = K + 8 = 9, 10, 18 или 19 и К = 1 или 2, но ни один из этих вариантов не подходит (проверяется подстановкой). Если И = 7, то И + К + С = K + 12 = 9, 10, 18 или 19 и К = 6 или 7, но ни один из этих вариантов не подходит (проверяется подстановкой). Если И = 9, то И + К + С = K + 14 = 9, 10, 18 или 19 и К = 4 или 5, но ни один из этих вариантов не подходит (проверяется подстановкой).

Ответ:

$И-КС⋅КСИ-= 162 ⋅621$

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

Задача 13#73689

У натурального числа, оканчивающегося не на ноль, стерли одну цифру. В результате число уменьшилось в $6$ раз. Найдите все числа, для которых это возможно.

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

Представим исходное число в виде $m +10ka+10k+1n,$ где $a$ — десятичная цифра, $k,m,n$ — неотрицательные целые числа, причём $k m < 10.$ Стерев цифру $a,$ мы получим число $k m +10 n.$ По условию

k k+1 k m+ 10 a+10 n= 6(m + 10n),

k 5m =10 (a +4n).

Заметим, что $k> 0,$ иначе $m =0$ и $n =a =0.$ Тогда равенство примет вид $m = 10k−1(2a+ 8n).$ В силу условия число $m$ оканчивается не на $0$ и потому не делится на $10.$ Значит, $k= 1$ и $m= 2a+ 8n,$ причём $m <10.$ Поэтому возможны два случая:

$1)n= 0.$ Тогда $m = 2a,$ а исходное число равно $12a,$ где $a= 1,2,3,4.$

$2)n= 1.$ Тогда $a= 0,m = 8,$ а исходное число равно $108.$

Ответ:

$108$ или $12a$ при $a= 1,2,3,4$

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

Задача 14#79756

Натуральные числа $x$ и $y$ равны $2014$ соответственно в десятичной и восьмеричной системе. Будет ли число $x2000− y1000$ точным квадратом?

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

Речь идёт о числе $20142000 − 10361000.$ Покажем, что оно делится на $3,$ но не делится на $9.$ Действительно, $20142000 ≡ 12000 (mod 3).$ То же самое можно сказать про $1000 1036 .$ В то время как

2000 2000 2000 1000 1000 2014 ≡ 7 ≡ 2 (mod 9),1036 ≡ 1 ≡1 (mod 9)

То есть по модулю $9$ число сравнимо с $22000− 1.$ Учитывая, что $26 ≡ 1 (mod 9),$ имеем $22000− 1≡ 22 − 1= 3.$ Значит, $3$ входит в это число в $1$ степени, то есть оно не квадрат.

Ответ:

Нет

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

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