Найдите кол-во натуральных трехзначных чисел, для которых выполняется хотя бы одно из сравнений:
x = 3 (mod 10), x = 2 (mod 4), x = 5 (mod 9).


Мой ход решения: для каждого из сравнений получаются соответствующие уравнения 103 + 10t = 1000, 102 + 4t = 1000, 104 + 9t = 1000. Находим самое близкое к границе трехзначных чисел целое t (оно будет равно 89, 224, 99 соответственно) и прибавляем к каждому единицу, чтобы учесть вариант, когда t = 0. Итого получается 90 + 225 + 100 = 415 вариантов.


Найдите кол-во шестизначных чисел в семеричной системе счисления, в записи которых есть одновременно цифры 2, 3 и 4.


Это задание нужно, скорее всего, считать через дополнение. Однако не получается правильно учесть все варианты

задан 22 Июн '17 14:48

10|600 символов нужно символов осталось
1

Здесь можно применить формулу включений и исключений. Введём множества A, B, C, состоящие из всех трёхзначных чисел, удовлетворяющих указанным сравнениям в порядке следования. Это значит, что A={103,113,...,993}, B={102,106,...,998}, C={104,113,...,995}. Легко найти мощности этих множеств: |A|=900/10=90, |B|=900/4=225, |C|=900/9=100. Поскольку 900 делится на каждое из чисел m=10,4,9, можно разбить 900 трёхзначных чисел на группы из m последовательных, и в каждой из групп будет ровно одно число, дающее фиксированный остаток от деления на m.

Теперь находим попарные пересечения. Очевидно, что AB пусто, так как числа из A нечётны, а числа из B чётны. Далее, |AC|=900/90=10, так как числа 10 и 9 взаимно просты, и тогда по китайской теореме об остатках, система из первого и третьего сравнения равносильна некоторому сравнению x=x0 (mod 90), и таких чисел имеется 10, поскольку 900 делится на 90. Наконец, |BC|=900/36=25 по тому же принципу. Тройное пересечение, очевидно, пустое.

Теперь формула включений и исключений даст нам |A U B U C|=90+225+100-0-10-25+0=380.

Что касается второй задачи, то она может быть решена с использованием той же формулы. Этот вопрос уже не раз звучал в виде аналогичной задачи; см. здесь.

ссылка

отвечен 22 Июн '17 15:15

Спасибо за развернутый ответ

(23 Июн '17 23:17) stalingrad4243

Можете подробнее про момент с китайской теоремой? Как находить пересечения в случае, если речь идет не про взаимно простые числа? Например, x = 2 mod 9, x = 5 mod 15.

(26 Июн '17 15:55) log0
1

@log0: если решается система сравнений типа этой, то способ стандартный. А именно, решаем в общем виде одно из сравнений -- например, последнее. Это даёт x=15y+5. Подставляем в остальные сравнения (по очереди). 15y+3=0 mod 9, полностью сокращаем на 3 и упрощаем: 5y+1=0 mod 3 <=> y=1 mod 3. Тогда y=3k+1, x=15y+5=45k+20. В виде одного сравнения: x=20 mod 45.

Есть ещё быстрый способ нахождения подбором: x=5,20,35,... из второго; проверяем на предмет свойства x=2 mod 9. Подходит 20. Значит, по К.Т.О., x=20 по модулю НОК(9;15)=45 -- единственное решение.

(26 Июн '17 18:59) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,476
×1,296

задан
22 Июн '17 14:48

показан
759 раз

обновлен
26 Июн '17 18:59

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru