Комбинаторика и теория чисел на Физтехе
Ошибка.
Попробуйте повторить позже
Даны 
карточек, на которых написаны натуральные числа от 
до 
(на каждой карточке написано ровно одно число, притом
числа не повторяются). Требуется выбрать две карточки, для которых сумма написанных на них чисел делится на 
. Сколькими
способами это можно сделать?
Источники:
Подсказка 1
Понятно, что надо будет как-то смотреть на остатки по модулю 100 и складывать их. Понятно, что число делится на 100, когда сумма будет оканчиваться двумя нулями. В любом случае придётся рассмотреть случаи, поэтому систематизируем их. Давайте начнём с самого простого, когда цифры оканчиваются либо на 50, либо на 00. Сколько же таких карточек в принципе и какую карточку в пару нужно выбирать?
Подсказка 2
Верно, карточек каждого вида по 21 и в пару мы выберем такую же, для сохранения делимости. Получаем, что в каждом виде таких пар будет 21*20/2. Дальше видим, что у нас не очень удачно выбрано ограничение по числам. Давайте сразу разберёмся с карточками с 2101 до 2117. Подумайте над тем, какие числа снова можно подобрать к ним в пару и сколько их?
Подсказка 3
Точно, их тоже по 21 штуке для каждой. То есть количество таких пар будет равно 17*21. Остались карточки с 1 до 2099 и уже можно увидеть какие пары нам нужны. То есть в пару к 01 мы берём 99, к паре 02 - 98 и так далее до 49 и 51. Осталось только понять, сколько для выбранного первого числа есть второе в пару. И умножить это количество выборов первого числа!
Будем называть парной карточкой к данной такую карточку, что их сумма кратна 
, а видом карточки — её последние две цифры.
Рассмотрим несколько случаев
- Номер на карточке кратен
, то есть заканчивается на 
или 
. Карточек каждого вида ровно по 
, а парная карточка
к каждой из них заканчивается на те же самые две цифры. То есть для обоих видов мы получим по 
способов взять две
парные карточки с такими последними цифрами. Всего 
.
- Номер карточки заканчивается на
, при этом он не больше 
. В силу второго ограничения таких карточек
тоже по 
каждого вида. Легко видеть, что в пару им идут виды 
, по одному на каждый, то есть для каждой
выбранной карточки подойдёт 
карточка парного вида. Итак, выбираем вид 
способами, затем его представителя 
и пару ему также 
, итого 
.
- Остались карточки с номерами
. Для каждой из них есть по 
парной, то есть получаем 
способов.
Складывая по всем случаям, получаем 
способов.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
