На листке бумаги написан набор натуральных чисел. Все числа разные, и каждое из них не больше чем 2015. Известно, что никакое из написанных чисел и никакая сумма нескольких из них не делится на 13. а) Приведите пример такого набора из 7 чисел; б) Какое наибольшее количество чисел может быть в наборе? в) Найдите наибольшую возможную сумму чисел такого набора.

задан 14 Апр '14 16:23

изменен 14 Апр '14 16:26

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

а) Так как числа складываются, и никакие из них не делятся на $%13$%, то их сумма будет делиться на $%13$%, только если сумма их остатков будет делиться на $%13$% (то есть будет давать нулевой остаток), поэтому, если все семь чисел будут давать в остатке единицу, то остаток суммы любых из них (даже если все сложить) будет больше единицы, но не больше $%7$%, чтобы было легче подбирать числа, можно, чтобы у троих были остатки $%2$%, а у четверых -$%1$%, вот мой пример такого набора: $%1,2,14,15,27,28,40$%;
б)Опираясь на рассуждения выше, получаем, что максимум в наборе может быть $%12$% чисел (с остатком $%1$%);
в)Если бы не было ограничения чисел ($%2015$%), то в этом пункте сумма была бесконечно большой, ведь надо найти набор с как можно большим количеством чисел, как можно больших по значениям, суммы остатков которых (в любом наборе) не делились на $%13$%. Заметим, что так $%2015$% делится на $%13$%, то ближайшее наибольшее число, не делящееся на $%13$% - $%2014$% (остаток $%12$%), так же заметим, что, если мы возьмем $%k$% таких чисел (с таким же остатком), где $%k<13$% и $%k \in N$%, то есть если у каждого из них остаток равен $%12$%, а общее их количество меньше $%13$%, то сумма остатков любого набора таких чисел не будет кратна $%13$%, а так как нам нужно как можно большее количество таких числе (с как можно большими значениями самих чисел), то всего их будет $%12$%, а наибольшее, как мы выяснили будет $%2014$%, остальные будут определяться путем вычитания $%13$% из предыдущего. Так же следует отметить случай, если бы мы брали первое число $%2014$% (остаток $%12$%), а дальше брали числа на единицу меньшие, пока их сумма их остатков не кратна $%13$%, мы бы взяли еще $%2013,2012,2011$% (так как дальше можно составить набор, сумма остатков чисел которого будет кратна $%13$%), что дало бы меньшую сумму, чем выше рассмотренным способом. Так же, если мы иногда будет отступать не на $%13$%, например, на $%12$%, то мы будет набирать на единицу (в данном случае, а вообще можем набирать и на $%12$%) больше, но при этом сумма остатков увеличится на $%1$%, (в данном примере) и в результате мы не наберем где-то на $%1000$% меньше, чем если бы отступали на $%13$%.
Заметим, что эти числа будут составлять арифметическую прогрессию, где первый член будет равен $%2014$%, тогда найдя $%12$%-ый член, мы сможем найти их сумму, как сумму первых двенадцати членов этой прогрессии. В результате получается, что их сумма равна $%23310$%.

ссылка

отвечен 14 Апр '14 16:54

изменен 14 Апр '14 20:06

@kirill1771: мне кажется, Ваше рассуждение надо несколько дополнить. Дело в том, что в пункте в) спрашивается о наибольшей сумме чисел набора, удовлетворяющему условиям. Теоретически возможно, что наибольшая сумма получиться не из 12 чисел, а из меньшего количества, за счёт снятия ряда ограничений. В данном случае видно, что это не так, но такую возможность надо оговорить. Далее, здесь есть ещё одно препятствие. А вдруг не все остатки равны 12, а устроены как-то иначе, и тогда не надо отступать назад на 13, набирая больше указанного количества?

(14 Апр '14 18:00) falcao

@falcao:да, согласен я об этом подумал, надо было хотя бы подписать это, скоро дополню.

(14 Апр '14 18:06) kirill1771

@falcao: я дополнил, может быть, что-то не так еще есть? (или я что-то неправильно написал)

(14 Апр '14 20:07) kirill1771
1

@kirill1771: решение, если оно строгое, должно охватывать все случаи, и быть убедительным.

(14 Апр '14 20:29) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×3,927

задан
14 Апр '14 16:23

показан
3199 раз

обновлен
14 Апр '14 20:29

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

по почте:

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

по RSS:

Ответы

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

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