Какое наименьшее количество степеней тройки с ЦНП (Целым Неотрицательным Показателем) надо взять, чтобы среди них гарантированно нашлось несколько чисел, сумма которых делится на 13?

задан 22 Дек '19 2:51

1

1, 3, 9 -- остатки от деления. Далее -- период. Ясно, что если взять 12 чисел, то это могут быть одни единицы. То, что 13 чисел всегда хватает -- стандартная задача на принцип Дирихле (надо рассмотреть частичные суммы).

Если я правильно понял условие, то задача начисто лишена "интриги".

(22 Дек '19 3:04) falcao

@falcao, у меня частичные суммы как-то временно выпали из памяти, поэтому решение получилось красивым :)

Пусть у нас 13 степеней. Если среди них есть три с попарно различными остатками на 13, то сумма этих трёх будет кратна 13. Если все 13 дают одинаковый остаток, то, очевидно, тоже. Теперь, пусть есть ровно два различных остатка. Если это 1 и 3, то троек должно быть не более 3 (иначе 4 тройки в сумме с 1 дадут 13), а единиц - не более 9 (иначе 10 единиц в сумме с тройкой дадут 13). Аналогично, если остатки равны 1 и 9, то единиц не более 3, а девяток - не более 9. И наконец, если 3 и 9,

(22 Дек '19 3:12) Казвертеночка

@falcao, в предыдущем комменте не хватило места. Итак, если 3 и 9, то троек не более 9, а девяток не более 3, иначе сумма будет 39, а это кратно 13.

(22 Дек '19 3:14) Казвертеночка
1

@Казвертеночка: может быть, для какого-то другого набора чисел с повторениями (их можно просто взять и указать) и получится что-то не совсем тривиальное, требующее конкретного разбора случаев. Но при этом надо позаботиться о том, чтобы совсем простые соображения напрямую не проходили.

(22 Дек '19 3:45) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×1,399
×251
×141
×98
×3

задан
22 Дек '19 2:51

показан
115 раз

обновлен
22 Дек '19 3:45

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

по почте:

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

по RSS:

Ответы

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

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