Тема ТЕОРИЯ ЧИСЕЛ

Признаки делимости и равноостаточности → .02 Остатки и делимость по модулю степеней тройки

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

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

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

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

Подтемы раздела теория чисел

Разделы подтемы Признаки делимости и равноостаточности

Остатки и делимость по модулю степеней двойки или пятёрки

Остатки и делимость по модулю степеней тройки

Остатки и делимость по модулю 11

Остатки и делимость по модулю 7

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

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

Задача 21#33766Максимум баллов за задание: 7

Копатыч учится делить с остатком. Лосяш дал ему задание поделить натуральное число на сумму его цифр. В результате и неполное частное, и остаток у Копатыча получились равными $2020.$ Докажите, что Копатыч ошибся.

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

Обозначим делимое через $n,$ а сумму его цифр через $s.$ Тогда должно быть верно равенство

n =2020s+2020

Вычтем из обеих частей $2020s.$ Как мы знаем, число дает такой же остаток при делении на $3,$ что и его сумма цифр. Поэтому $n − s$ делится на $3.$ Тогда разность $n− 2020s= n− s− 2019s$ делится на $3,$ так как и $n− s,$ и $2019s$ делятся на $3.$ Но эта разность равна $2020.$ Это число по признаку дает остаток $1$ при делении на $3.$ Противоречие, значит, такое равенство невозможно, и Копатыч ошибся.

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

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

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

Задача 22#33767Максимум баллов за задание: 7

Найдите наименьшее натуральное число, которое делится на 225, и при этом содержит в своей записи только нули и единицы.

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

Число $225= 9⋅25,$ поэтому мы можем отдельно воспользоваться признаками делимости на 9 и на 25.

Начнем с признака равноостаточности при делении на 25: число дает такой же остаток при делении на 25, что и число, образованное его последними двумя цифрами. В нашем случае, чтобы число делилось на 25, оно должно оканчиваться либо на 00, либо на 25, либо на 50, либо на 75. Так как по условию число состоит только из нулей и единиц, подходит лишь 00. Итак, мы выяснили, что число оканчивается на 00.

Теперь, определив однозначно последние две цифры, чтобы сделать число минимальным, нужно минимизировать число без двух последних цифр. Воспользуемся признаком равноостаточности при делении на 9: число дает такой же остаток при делении на 9, что и его сумма цифр. В нашем случае необходимо, чтобы число делилось на 9, поэтому и сумма цифр должна делиться на 9. Нули в записи не меняют сумму цифр числа, поэтому сумму цифр, делящуюся на 9, мы можем получить только из единиц. Если сумма цифр числа будет 18 или больше, то нам придется использовать хотя бы 18 единиц, и тогда в числе будет 20 или больше знаков, а у нас есть пример на меньшее число. Если сумма цифр числа равна 9, то нужно использовать девять единиц. Так как наличие нулей в записи на делимость не повлияет, но лишь увеличит количество знаков в числе, а значит и его значение, то минимальным подходящим числом является 111111111. Приписав к этому числу два нуля в конец, мы получаем искомый ответ.

Замечание. Обратите внимание на два важных момента. Во-первых, мы можем минимизировать число без двух последних цифр только потому, что они определились однозначно. Если бы у нас получилось несколько вариантов последних двух цифр, то мы бы не могли так просто их отбросить, пришлось бы рассматривать несколько случаев и в каждом искать минимум, а уже потом выбирать самое маленькое число.

Во-вторых, было бы грубой ошибкой написать, что число тем меньше, чем меньше его сумма цифр. Это не правда: $9 <111,$ но $9 >1+ 1+ 1.$ Обратите внимание, как мы обошли эту проблему при написании решения: мы отдельно сказали, что случай с суммой цифр 18 или более нам не подходит, так как у нас есть пример на меньшее количество знаков. А уже потом объяснили, почему при сумме цифр 9 наше число минимальное.

Ответ: 11,111,111,100

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

Задача 23#33771Максимум баллов за задание: 7

Найдите минимальное натуральное число вида $111...11$ , которое кратно $333...33 ◟100◝т◜рое◞к$ ?

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

Разложим $333...33= 3⋅ 111...11 ◟100◝т◜рое◞к 1◟00-◝ед◜ин◞иц$ . Пусть число (наш ответ), состоящее из $k$ единиц делится на оба множителя (это необходимое и достаточное условие, так как эти два множителя взаимно просты). Деля его на $1◟11◝..◜.11◞ 100единиц$ в столбик, видно, что $k$ делится на $100$ (каждый раз сносится по $100$ единиц). Кроме того, из признака делимости на $3$ следует, что $k$ кратно $3$ . Значит, минимальное $k =3⋅100= 300$ . Заметим, что оно подходит: $1◟11.◝..◜11◞ 300единиц$ делится на $11◟1.◝◜..11◞ 100единиц$ (в столбик видно) и на $3$ по признаку делимости.

Ответ: 111. . . 11 (300 единиц)

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

Задача 24#33772Максимум баллов за задание: 7

Найдите все такие числа $n$ , для которого выполнено следующее условие: если число $A$ кратно $n$ , то и все числа, которые получаются перестановкой цифр в числе $A$ , кратны $n$ .

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

Пусть число $n$ — $k$ -значное. Тогда среди чисел от $10k+1$ до $10k+1 +n$ найдется число, делящееся на $n$ (среди $n$ последовательных чисел всегда есть число с остатком $0$ при делении на $n$ ). Пусть это число имеет вид $---------- 10akak−1...a1$ . Раз делимость на $n$ не зависит от порядка цифр числа, то на $n$ делятся также числа $---------- akak−1...a110$ и $---------- akak−1...a101$ . Значит, и разность этих двух чисел, равная $9$ , должна делиться на $n$ . А это возможно только при $n = 1$ , $n = 3$ , $n = 9$ . Заметим, что при этих $n$ все условия задачи выполняются, так как признаки делимости на $3$ и на $9$ зависят только от суммы цифр в числе.

Ответ: 1,3,9

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

Задача 25#34650Максимум баллов за задание: 7

На доске написано число $82017.$ У него вычисляется сумма цифр, у полученного числа вновь вычисляется сумма цифр, и так далее, до тех пор, пока не получится однозначное число. Что это за число?

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

Число меняется на сумму цифр: казалось бы, всё очень плохо, это совершенно непонятная для нас операция. Или нет? Всё-таки кое-что мы знаем, благодаря признакам равноостаточности! А именно: остаток при делении на $9$ сохраняется. Поэтому, если мы будем знать остаток у исходного числа, то такой же будет и у оставшегося однозначного, а его уже достаточно легко посчитать. Так как $8 ≡−1 (mod 9),$ то остаток такой же, как у $2 (− 1) 017≡ −1≡ 8 (mod 9).$ Значит, оставшееся однозначное число — это $8.$

Ответ:

$8$

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

Задача 26#34652Максимум баллов за задание: 7

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

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

Подсказка 1

Заметим, что мы знаем все цифры нашего числа! С точки зрения признаков делимости, что о нем можно сказать?

Подсказка 2

Верно, нужно рассмотреть признаки делимости, которые зависят от суммы цифр!

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

Сумма цифр числа равна $10⋅1 +10⋅2= 30.$ Она кратна трём, то есть наше число может быть только квадратом кратного тройке числа, но тогда оно должно быть кратно $9,$ что не выполняется для суммы цифр.

Ответ:

Нет

Курсы

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

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

Задача 27#34654Максимум баллов за задание: 7

На доске написано число $1.$ Каждую секунду к числу на доске прибавляют сумму его цифр и записывают результат вместо предыдущего. Может ли через некоторое время на доске появиться число $123456?$

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

Подсказка 1!

1) Хм, у нас есть интересная операция - прибавление суммы цифр числа! А что мы такого знаем про сумму цифр числа...

Подсказка 2!

2) Да, стоит вспомнить признак делимости на 3! У числа и суммы его цифр есть что-то общее :)

Подсказка 3!

3) А теперь осталось только посмотреть, как будут вести себя остатки, и могут ли они прийти к 123456, как, если да?

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

Заметим, что на каждом шаге остаток числа при делении на $3$ удваивается, поскольку сумма цифр даёт тот же остаток. То есть остатки при делении на три будут $1→ 2 → 1→ 2...$ и среди них не будет нулей. Однако $123456$ кратно трём, поэтому его получить не выйдет.

Ответ:

Нет

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

Задача 28#34658Максимум баллов за задание: 7

В натуральном числе $A$ переставили цифры, получив число $B$ . Известно, что $A− B$ есть число, составленное из $N$ единиц. Найдите наименьшее возможное значение $N$ .

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

Числа, получаемые друг из друга перестановкой цифр, имеют одинаковый остаток от деления на 9, то есть их разность делится на 9. Поэтому и сумма цифр разности, равная n, делится на 9, откуда $N ≥ 9$ .

Значение $N = 9$ получается, например, так: $9012345678− 8901234567= 111111111$ .

Ответ: 9

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

Задача 29#39061Максимум баллов за задание: 7

Лёша выписал на доску числа $1$ , $2$ , $3$ , $4$ и так далее, с пробелами. После этого он стёр каждое второе число написанное на доске (то есть на доске осталось числа $1$ , $3$ , $5$ , $7$ , $9$ , $11$ ,…). Затем он стёр каждое третье число. Чему равна сумма чисел, оставшихся стоять на $2021$ и $2022$ месте?

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

После первого стирания на доске останутся только нечётные числа. Посмотрим на второе. Мы вычеркнем числа $5$ , $11$ , $17$ , …. Это числа, которые при делении на $3$ дают остаток $2$ . Это действительно так, потому что если мы вычернкнули число $x$ , то останутся числа $x +2$ , $x +4$ , а следующее — $x +6$ будет вычеркнуто. Числа $x$ и $x +6$ дают одинаковые остатки при делении на $3$ , а значит, мы действительно вычеркнем все числа, дающие остаток $2$ при делении на $3$ , так как первое вычеркнутое число равно $5$ . То есть оставшиеся числа разбиваются на пары, в которых первое число даёт остаток $1$ при делении на $3$ , а второе — $0$ . А при делении на $2$ эти числа дают остаток $1$ . Это означает, что остались числа дающие остаток $1$ и $3$ при делении на $6$ . Если пронумеровать пары оставшихся чисел, то в паре с номером $k$ будут стоять числа вида $6(k − 1)+ 1$ и $6(k− 1)+3$ . Числа стоящие на $2021$ -ом и $2022$ -ом месте попадают в пару под номером $2022∕2 =1011$ . Это значит, что там будут числа $6⋅1010+ 1= 6061$ и $6063$ . Их сумма равна $12124$ .

Ответ: 12124

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

Задача 30#39070Максимум баллов за задание: 7

Лёша выписал на доску числа $1$ , $2$ , $3$ , $4$ и так далее, без пробелов. После этого он стёр каждую вторую цифру написанную на доске (то есть на доске осталось число $135790123...$ ). Затем, в том что осталось, он стёр каждую третью цифру. Чему равна сумма цифр, стоящих на $2021$ и $2022$ месте оставшегося числа?

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

Посчитаем на каких позициях останутся цифры после двух стираний. После первого стирания на доске останутся только цифры стоящие на нечётные местах. После второго стирания мы вычеркнем цифры на $5$ , $11$ , $17$ , …местах. Это числа, которые при делении на $3$ дают остаток $2$ . Это действительно так, потому что если мы вычернкнули цифру на месте $x$ , то останутся цифры на местах $x+ 2$ , $x +4$ , а следюущая — $x+ 6$ -ая будет вычеркнута. Числа $x$ и $x+ 6$ дают одинаковые остатки при делении на $3$ , а значит, мы действительно вычеркнем все цифры ,позиции которых дают остаток $2$ при делении на $3$ , так как первое вычеркнутое цифра будет $5$ -ой. То есть оставшиеся цифры разбиваются на пары, в которых первая позиция даёт остаток $1$ при делении на $3$ , а второая — $0$ . А при делении на $2$ их позиции дают остаток $1$ . Это означает, что остались цифры стоящие на местах, которые дают остаток $1$ и $3$ при делении на $6$ . Если пронумеровать пары оставшихся цифр, то в паре с номером $k$ будут стоять цифры на местах вида $6(k− 1)+ 1$ и $6(k − 1)+ 3$ . Цифры стоящие на $2021$ -ом и $2022$ -ом месте попадают в пару под номером $2022∕2=1011$ . Это значит, что там будут цифры $6⋅1010 +1= 6061$ и $6063$ исходного числа.

Теперь найдём что за цфиры там стоят. Числа от $1$ до $9$ занимают $9$ цифр, далее от $10$ до $99$ — ещё $90⋅2= 180$ цифр, всего $189$ , числа от $100$ до $999$ — $900 ⋅3$ = $2700$ и всего $2889$ цифр. Числа от $1000$ до $9999$ дают нам $9000⋅4= 36000$ цифр, а значит в этом промежутке стоит искать. Первая цифра встретится в числе $[ ] 999+ 6061−42889 = 999+793= 1792$ , причём так как $6061−24889$ целое число, то это будет последней цифрой в $1792$ . Вторая цифра, соотвественно, будет цифра $7$ в числе $1793$ . В итоге получаем сумму $2+ 7= 9$ .

Ответ: 9

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

Задача 31#100777Максимум баллов за задание: 7

Все натуральные числа от $1$ до $101$ включительно записаны подряд, образуя многозначное число. Докажите, что полученное число составное. Является ли оно квадратом натурального числа?

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

Подсказка 1

Число получается очень большое, поэтому выписывать мы его конечно не будем) Мы знаем, что число состоит из в ряд выписанных чисел от 1 до 101. Тогда мы знаем цифры этого числа! А что можно сделать с цифрами?

Подсказка 2

Можно посчитать сумму цифр нашего числа! И дальше использовать какой-то из признаков делимости…

Подсказка 3

Сумма цифр будет равна 5151. Что можно сказать про число с такой суммой цифр?

Подсказка 4

Конечно, можно проверить делимость этого числа на 3 и 9. Сумма цифр числа 5151 равна 12. Получается, наше начальное число делится на 3, но не делится на 9 (потому что взятие суммы цифр не изменяет остатки от деления числа на 3 и 9). Хм, может ли такое число быть точным квадратом?

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

Заметим, что можно посчитать сумму цифр этого числа.

Сумма цифр от 1 до 9 равна 45. Значит, чтобы посчитать сумму цифр числа, надо сначала посчитать сумму всех однозначных чисел и всех цифр в разряде единиц у двузначных чисел, она равна $45⋅10,$ потом посчитать сумму все первые цифры у двухначных чисел, она равна $10⋅45,$ учесть 100 и 101. В итоге сумма

45⋅10+10⋅45+ 1+ 2= 903

При разложении квадрата на простые множители все простые делители входят в это разложение в чётной степени.

А наша сумма делится на 3, но не делится на 9. Значит, число квадратом являться не может.

Ответ: нет

Интенсивы

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

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

Задача 32#80195Максимум баллов за задание: 7

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

Источники: САММАТ - 2021, 11.1 (см. sammat.samgtu.ru)

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

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

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

Задача 33#99581Максимум баллов за задание: 7

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

Один из возможных вариантов ключа:


1	1	2	2

2	1	1	2

0	0	1	2

0	1	2	0

А сколько всего существует различных ключей?

Источники: Верченко - 2021, 11.3 (см. v-olymp.ru)

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

Подсказка 1

В таких задачах зачастую удобно бывает найти параметры, которые, как в геометрии, фиксируют картинку. То есть, если какие-то числа в табличке определены, то и вся остальная таблица определяется однозначно. При этом, хотелось бы минимизировать число таких параметров, а также что-то понять про множество их значений. Всё это выше рассказано таким общим языком не чтобы вас напугать, а чтобы вы в аналогичных задачах видели схожие паттерны. Так какие же числа можно зафиксировать, чтобы все остальное у нас определялось единственным образом, а также, желательно, чтобы для любого набора параметром у нас восстанавливалась однозначно картинка?

Подсказка 2

Заметим, что если мы определили числа в верхнем левом квадрате 3 на 3, то мы определили всю таблицу. Понятно, что картинка тогда восстанавливается, но не будет ли противоречий при каких-то заполнениях квадрата 3 на 3 на диагонали?

Подсказка 3

Конечно, противоречия могут быть. Поэтому надо добавить еще два линейных равенства на диагонали. А значит, у нас есть 9 переменных и два равенства. Отсюда 7 свободных переменных, а потому вариантов 3⁷.

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

Указанную в условии таблицу $4 ×4$ , можно построить следующим образом: положим элементы верхнего левого угла размеров $3× 3$ произвольным образом, после чего заметим, что все оставшиеся элементы определяются однозначно из линейных (по модулю $3$ ) соотношений для строк и столбцов (при этом элемент в правом нижнем углу будет равен сумме по модулю $3$ всех остальных элементов квадрата). Плюс к этому имеем два линейных соотношения для элементов диагоналей. Таким образом, общее число независимого выбора переменных $ai,j,i,j = 1,2,3$ равно $7.$ Следовательно, общее число ключей равно $7 3 = 2187.$

Ответ:

$2187$

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

Задача 34#46228Максимум баллов за задание: 7

Пусть $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.$

Ответ:

нет

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

Задача 35#102526Максимум баллов за задание: 7

Рассмотрим всевозможные 100-значные натуральные числа, в десятичной записи которых встречаются только цифры 1,2. Сколько среди них делятся на 3 нацело?

Источники: Межвед - 2020 (см. v-olymp.ru)

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

Подсказка 1

Давайте попробуем поработать с меньшей длиной чисел, а длину 100 построим дописываем небольшого количества цифр (чтобы нам было удобно видеть всевозможные комбинации для дописывания). Какую длину выберем для подсчета?

Подсказка 2

Давайте попробуем дописать 2 цифры так, чтобы число стало делиться на 3. Какие для этого есть варианты?

Подсказка 3

Количество вариантов для дописывания зависит от того, делилось ли 98-значное число на 3. Попробуем явно рассмотреть случаи, это, кажется, не так сложно!

Подсказка 4

Отлично! Теперь мы умеем выражать ответ для n=100 через ответ для n=98. А что нам мешает "спуститься" ещё ниже, к числам меньшей длины?)

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

Каждое 100-значное натуральное число может быть получено дописыванием двух цифр справа к 98-значному числу. Пусть $x$ — некоторое 98-значное число. Посмотрим какие справа две цифры (каждая из которых равна 1 или 2) нужно к числу $x$ приписать, чтобы получившееся 100значное число делилось на 3. Воспользуемся тем, что остаток от деления натурального числа на 3 равен остатку от деления на 3 суммы его цифр. Пусть наше число $x$ при делении на 3 дает остаток $m$ . Тогда

- если $m = 0$ , то припишем 12 или 21 ;

- если $m = 1$ , то припишем 11 ;

- если $m = 2$ , то припишем 22 ;

Таким образом, из каждого 98-значного числа, кратного 3, можно получить два кратных трем 100 -значных числа. Каждое не кратное трем 98-значное число порождает только одно кратное трем 100-значное число.

Всего 98-значных чисел $298$ . Пусть среди них $A98$ чисел кратно трем. (Далее символом $An$ будем обозначать количество n-значных чисел, кратных 3.) Тогда количество кратных трем 100 -значных чисел может быть найдено по формуле

( ) A100 = 2A98 + 298 − A98 = 298+ A98

Верны, таким образом, следующие соотношения:

98 A100 = 2 + A98 A98 = 296+ A96 ... 4 A6 = 2 +A4 A4 = 22+A2.

Сложив эти равенства (величины $A4,...,A98$ при этом сокращаются), получим

A100 = A2+ 22 +24+ ⋅⋅⋅+ 298

Остается просуммировать геометрическую прогрессию и заметить, что $A =2 2$ . Тогда

50 50 A100 =2+ 4--−-4= 4--+2- 3 3

Ответ:

$450+-2 3$

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

Задача 36#30938Максимум баллов за задание: 7

На столе лежат $130$ различных карточек с числами $502,504,506,...,758,760$ (на каждой карточке написано ровно одно число, каждое число встречается ровно один раз). Сколькими способами можно выбрать $3$ карточки так, чтобы сумма чисел на выбранных карточках делилась на $3?$

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

Подсказка 1

Так, нас просят выбрать три числа так, чтобы их сумма делилась на три. В таком случае, какие остатки должны быть у чисел при делении на 3?

Подсказка 2

Да, числа должны давать либо одинаковые остатки, либо наоборот различные(0, 1, 2). Можно ли посчитать, какие остатки при делении на 3 дают числа в условии задачи?

Подсказка 3

Да, можно, так 502 ≡ 1 (mod=3), 504 ≡ 0 (mod=3), 506 ≡ 2(mod=3), …, 760 ≡ 1(mod=3). То есть, по модулю 3: 44 числа сравнимы с единицей, 43 числа сравнимы с двойкой, 43 числа сравнимы с нулем. Как посчитать общее число способов?

Подсказка 4

Выбрать три числа с разными остатками, это просто 43*43*44. А если мы хотим выбрать три числа с одинаковым остатком, то нужно воспользоваться формулой числа сочетаний. И посчитать сумму всех этих способов!

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

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

Если мы возьмём три карточки с числами подряд по возрастанию, то среди них будут по одной карточке с остатками $0,1$ и $2$ при делении на $3.$ Значит, среди карточек $502,504,506,...,758$ по $43$ карточки с каждым остатком (разобьём на $43$ тройки подряд идущих) и ещё есть карточка с числом $760,$ которое дает остаток $1.$

Давайте подумаем, какие есть варианты для остатков трёх карточек, чтобы их сумма делилась на $3:$ либо все три числа должны давать разные остатки (способов выбрать так карточки $43 ⋅44⋅43,$ так как выбрать карточку с остатком $0$ — $43$ способа, способов выбрать карточку с остатком $1$ — $44$ и способов выбрать карточку с остатком $2$ — $43$ ), либо все три остатка $0$ (тогда способов $3 C 43),$ либо все три остатка 1 (тогда способов $3 C44),$ либо все три остатка $2$ (тогда способов $3 C43).$ Итого всего

43⋅44⋅43+C343+ C344+ C343 = 81356+ 12341+ 13244+ 12341= 119282

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

Данные числа, расположенные в порядке возрастания, образуют арифметическую прогрессию с разностью $2≡3 −1.$ Следовательно, остатки от деления на $3$ у этих чисел чередуются (идут по убыванию с шагом $1,$ то есть $0→ 2→ 1→ 0→ ...$ ).

Среди данных нам чисел есть $44,$ дающие остаток $1$ от деления на $3$ (они образуют множество $A ={502;508;514;...;760}$ ), $43$ числа, делящихся на $3$ (образуют $B = {504;510;516;...;756}$ ) и $43$ числа, дающих остаток $2$ от деления на $3$ ( $C ={506;512;518;...;758}$ ).

Сумма трёх чисел может делиться на $3$ в следующих случаях.

1.: Все три числа дают одинаковые остатки от деления на $3.$ Есть $C344$ способов выбрать $3$ числа из множества $A$ и по $C343$ способов выбрать $3$ числа из множеств $B$ и $C.$ В сумме получаем $44⋅436⋅42+ 2⋅ 43⋅462⋅41-=13244+2 ⋅12341= 37926$ способов.
2.: Если не все остатки одинаковы, то подходит только случай, когда все три остатка разные, т.е. мы должны выбрать по одному числу из каждого из множеств $A,B,C.$ Получаем $44 ⋅43⋅43= 81356$ способов. Если есть два равных остатка, то для кратности их суммы трём третий должен быть таким же.

В сумме выходит $119282$ способов.

Ответ:

$119282$

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

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

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

Задача 37#31509Максимум баллов за задание: 7

Есть $200$ различных карточек с числами $2,3,22,32,...,2100,3100$ (на каждой карточке написано ровно одно число, каждое число встречается ровно один раз). Сколькими способами можно выбрать $2$ карточки так, чтобы произведение чисел на выбранных карточках было кубом целого числа?

Источники: Физтех-2019, 10.5, (см. olymp.mipt.ru)

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

Подсказка 1

По сути 2^1 и 2^4 дают нам одно и то же при умножении на какое-то число - либо это в обоих случаях куб, либо в обоих нет. А как мы вообще можем разбить все данные числа на группы с одинаковыми свойствами?

Подсказка 2

Да, числа вида 2^1, 2^4, .. 2^100 будут в одной группе, 2^2, 2^5, .. 2^98 в другой, так же с 2^3, так же и с тройками, получилось 6 групп. Выбирая по одному числу из каждой группы, можно ли понять, будет куб или нет?

Подсказка 3

Да, можем. Например, при перемножении 2^2 и 2^1 куб получился -> значит можно комбинировать числа этих групп. Найдите все возможные подходящие комбинации групп и посчитайте количества способов, помня про правила умножения и сложения и используя наши любимые цэшки :)

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

Чтобы число было кубом, нужно, чтобы степень каждого числа делилась на $3$ . Если мы возьмем одну карточку со степенью $2$ и одну со степенью $3$ , то они в произведении будут кубом только, если изначальные степени были кубами. Значит, в этом случае у нас $33⋅33$ варианта.

Если на обеих карточках степени двойки, то нужно посмотреть на остаток этих степеней при делении на $3$ . Степени могут давать остатки $1$ и $2$ или $0$ и $0$ . В первом случае у нас получится $34⋅33$ вариантов (нам важен порядок), во втором случае у нас получится $33⋅32∕2$ варианта (делим на $2$ , потому что здесь порядок уже не важен). Полностью аналогично со степенями тройки.

Получаем ответ $33⋅33 +2⋅(34⋅33 +33⋅32∕2)= 33⋅33+2 ⋅33⋅50= 33⋅133$ .

Ответ:

$4389$

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

Задача 38#96328Максимум баллов за задание: 7

Отец выдал Алексу и Джеймсу $100$ задач. Тот, кто решает задачу первым, получает за неё $4$ очка, вторым — $1$ очко. В результате каждый из них решил по $60$ задач, не обязательно одних и тех же. Могли ли они набрать в сумме $373$ очков?

Источники: Лига открытий - 2018

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

Рассмотрим остатки количества очков Алекса и Джеймса по модулю $3.$ Заметим, что за одну решенную задачу остаток всегда увеличивается на $1.$ Поэтому, решив $60$ задач, они получат количество очков, кратное $3.$ Но $373$ не делится на $3.$

Ответ:

Нет, не могли

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

Задача 39#102396Максимум баллов за задание: 7

Андрею нравятся все числа, не делящиеся на $3,$ а Тане нравятся все числа, в которых нет цифр, делящихся на $3.$

(a) Сколько четырёхзначных чисел нравятся и Андрею, и Тане?

(b) Найдите общую сумму цифр всех таких четырёхзначных чисел.

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

Пункт а, подсказка 1

Какой должна быть сумма цифр чисел, нравящихся Андрею?

Пункт а, подсказка 2

Посмотрите на остатки цифр, которые можно использовать. Попробуйте разбить их на множества.

Пункт б, подсказка 1

Рассмотрите возможные числа. Есть ли среди них похожие?

Пункт б, подсказка 2

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

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

(a) Искомые числа должны быть составлены из цифр $1,2,4,5,7,8$ , причём по критерию делимости на 3 в каждом числе сумма цифр не должна быть кратной трём. Цифры 1, 4 и 7 (назовём их цифрами множества $A$ ) при делении на 3 дают остаток 1, а цифры $2,5,8$ (цифры множества $B$ ) остаток 2. Значит, удовлетворяющее условию число должно быть составлено одним из следующих способов:

1) 4 цифры из множества $A$ — таких чисел $34$ ;

2) 4 цифры из множества $B$ — таких чисел $34$ ;

3) 3 цифры из множества $A$ и одна цифра из множества $B$ — таких чисел $4⋅34$ ;

4) 3 цифры из множества $B$ и одна цифра из множества $A$ — таких чисел $4⋅34$ .

Всего таких чисел $10 ⋅34 =810$ .

(b) Для поиска общей суммы цифр всех этих чисел разобьём их на пары: второе число получается из первого заменой всех цифр по принципу $1↔ 8, 2 ↔ 7, 4↔ 5.$

Например, число 1545 имеет пару 8454, число 5271 имеет пару 4728 , и т. д.

Сумма цифр любой пары равна $9⋅4$ , а число таких пар равно $10⋅34- 2$ . Значит, искомая сумма всех цифр равна

9⋅4⋅10⋅34- 6 2 = 20 ⋅3 =14580

Ответ:

(a) 810

(b) 14580

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

Задача 40#92480Максимум баллов за задание: 7

Какое минимальное количество лет надо взять, чтобы количество месяцев в них записывалось только нулями и единицами?

Источники: Лига открытий - 2017

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

Переформулируем задачу: нам надо найти наименьшее натуральное число $n,$ записываемое только нулями и единицами, делящееся на $12.$ Тогда мы поделим его на $12$ и узнаем ответ.

Убедимся, что число $11100$ подходит. Во-первых, так как число $n$ делится на $4,$ то число, образованное его двумя последними цифрами, делится на $4.$ Из чисел $00,01,10,11$ подходит только $00.$

Во-вторых, так как число $n$ делится на $3,$ то в нем не менее трех единиц. А наименьшее число, содержащее три единицы и оканчивающееся на два нуля — это как раз $11100.$ Откуда получаем ответ $11100:12= 925.$

Ответ:

$925$ лет

Предыдущая подтема

Следующая подтема