На листке бумаги написан набор натуральных чисел

[bitcoin]

Добрый вечер! Есть вопрос по задаче.
На листке бумаги написан набор натуральных чисел. Все числа различные, и каждое из них не превосходит $2017$. Известно, что никакое из написанных чисел и никакая сумма нескольких из них не делится на $13$. Какое наибольшее количество чисел может быть в наборе?

Мне вот кажется ответ очевидным, а именно $12$ чисел, которые имеют одинаковые остатки при делении на $13$. Например, $12$ единиц.
Мне ясно, что $13$ или более чисел с одинаковыми остатками быть не может, потому как сумма любых $13$ из них будет делится на $13$.
То есть мы выяснили, что не более $12$ чисел с одинаковыми остатками. Думаю, что если мы будем брать числа с разными остатками, то их будет не более 12, но доказать это не получается. Все рассматриваемые числа можно представить в виде $13n_i+r_i$, где $r_i$ есть остаток при делении на 13.
Каждый остаток $r_i$ имеет "сопряженный" к себе $13-r_i$, сопряженным назвал из-за того, что если есть в наборе число с остатком $r_i$, то число с сопряженным остатком быть не может. Ясно дело, что число с остатком $0$ не может быть в наборе, потому у нас остается 12 различных остатков, из которых можно взять максимум 6 различных, потому как остальные будут сопряженными к уже имеющимся. Но, на самом деле, это число еще меньше 6 из-за того, что сумма некоторых из этих остатков по-любому делится на 13.
1) Не ясно - сколько же максимально можно будет рассматривать чисел с различными остатками? Ведь очень много комбинаций. Может я не в ту сторону думаю?
2) Нужно последовательно рассматривать числа с одним остатком, потом с двумя, потом с тремя итп или как? Можете, пожалуйста, подсказать идею, зашел в тупик.

[mihaild]

Идея рассмотреть остатки - правильная (до 2017 мы наберем сколько понадобится чисел с любым конкретным остатком).
Чтобы доказать верхнюю оценку, попробуйте добавлять числа по одному и следить, как меняется множество остатков, которые можно получить. Пусть мы уже можем получить остаток 1, 2, 3, ..., 12 - можем ли мы добавить еще одно число?
Может ли оказаться, что мы можем добавить еще одно число, а множество остатков, которые можем получить, не изменится?

[bitcoin]

mihaild в сообщении #1348234 писал(а):

Пусть мы уже можем получить остаток 1, 2, 3, ..., 12 - можем ли мы добавить еще одно число?

Кстати, точно, ведь не можем и это связано со следующим вашим вопросом, напрямую.

mihaild в сообщении #1348234 писал(а):

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

Кстати, точно, скорее всего, нет.
Попробую подумать в эту сторону. Пусть мы можем получить следующие остатки от деления на 13 самих чисел или их сумм: 1,..,12. По условию, ни одно из чисел не делится на 13, потому остатка 0 быть не может, значит мы добавляем еще одно число с остатком $r\ne 0$ Тогда мы ведь можем взять число или сумму чисел, у которых остаток $13-r$, а значит новое число в сумме с несколькими старых, у которых накопился остаток $13-r$ будет давать число делящееся на 13, получили противоречие. Извиняюсь за косноязычие, надеюсь, что поймете, что имею ввиду.

И еще вопрос, а ведь еще надо доказать, что если мы взяли 12 чисел, то обязательно можем получить остаток 1, 2, 3, ..., 12 . Ведь еще не факт, что оно именно так, вдруг мы выбрали 12 чисел, но не все остатки пробежались? Как это можно доказать, что-то я не вижу пока что этого.

[mihaild]

bitcoin в сообщении #1348238 писал(а):

Ведь еще не факт, что оно именно так, вдруг мы выбрали 12 чисел, но не все остатки пробежались? Как это можно доказать, что-то я не вижу пока что этого.

Ну так я уже подсказал - добавляйте числа по одному и смотрите, что может происходить с множеством остатков.

[bitcoin]

mihaild в сообщении #1348239 писал(а):

bitcoin в сообщении #1348238 писал(а):

Ведь еще не факт, что оно именно так, вдруг мы выбрали 12 чисел, но не все остатки пробежались? Как это можно доказать, что-то я не вижу пока что этого.

Ну так я уже подсказал - добавляйте числа по одному и смотрите, что может происходить с множеством остатков.

Я посмотрел, каждый раз увеличивается множество остатков, но вот доказать не получается, к сожалению.

-- 22.10.2018, 01:58 --

Может попробовать так начать доказывать, что каждое новое число дает новый остаток? Пусть $f_n=a_1r_1+a_2r_2+...+a_nr_n$, где $a_1,a_2,...,a_n$ могут принимать значения 1 или 0 в зависимости от того, включаем ли мы соответствующий остаток в сумму $f_n$ или нет. Получается, что $f_n$ пробегает всевозможные значения для сумм $r_i$.Теперь добавляем еще один остаток $r_{i+1}$, тогда $f_{n+1}=a_1r_1+...+a_nr_n+a_{n+1}r_{n+1}$. Попробуем предположить, что этот новый остаток совпадает с одним или несколькими предыдущими или с суммами нескольких предыдущих (иначе, тот самый новый остаток, который мы ищем уже есть). На первый взгляд, может показаться, что появился новый остаток, если взять все коэффициенты в $f_{n+1}$ за $1$. Но нет, ведь может случиться так, что $r_1+r_2+..+r_n+r_{n+1}=13k+r_i$, где $i$ принимает одно из значений от $1$ до $n$, таким образом, мы новый остаток не получили, но ведь наверняка $f_{i+1}$ при некоторых значениях коэффициентов примет новое значение...

[mihaild]

Можно проще.
Во-первых, докажите, что множество остатков, которые можно получить из $r_1, \ldots, r_{n+1}$ зависит только от множества остатков, которые можно получить из $r_1, \ldots, r_n$ и остатка $r_{n+1}$.
После этого можно воспользоваться тем, что чисел с одинаковым остатком у нас в итоге не больше $12$...

[ET]

Глядя на тему, вспомнил свое решение одной олимпиадной, которую решал очень давно (даже условие подзабыл), но подход от нее сразу дал доказательство этой.
Пусть есть изначально числа .. Ну, выше писали $r_1,r_2,...r_{13}$ Возьмем последовательность $a_1,a_2,...a_{13}$ где $a_i=\sum\limits_{k=1}^{i}r_k$ Тогда у каких-то двух равные остатки на 13, а следовательно их разность...

[EUgeneUS]

bitcoin в сообщении #1348231 писал(а):

Мне вот кажется ответ очевидным, а именно $12$ чисел, которые имеют одинаковые остатки при делении на $13$. Например, $12$ единиц.

...

bitcoin в сообщении #1348242 писал(а):

Я посмотрел, каждый раз увеличивается множество остатков, но вот доказать не получается, к сожалению.

И не получится. Чисел может быть и $1008$, а не 12. Строится тривиально.

[bitcoin]

ET в сообщении #1348260 писал(а):

Тогда у каких-то двух равные остатки на 13, а следовательно их разность...

Делится на 13, но не понимаю - что это дает.

[Someone]

bitcoin в сообщении #1348286 писал(а):

Делится на 13, но не понимаю - что это дает.

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

[bitcoin]

mihaild в сообщении #1348251 писал(а):

Можно проще.
Во-первых, докажите, что множество остатков, которые можно получить из $r_1, \ldots, r_{n+1}$ зависит только от множества остатков, которые можно получить из $r_1, \ldots, r_n$ и остатка $r_{n+1}$.
После этого можно воспользоваться тем, что чисел с одинаковым остатком у нас в итоге не больше $12$..

Не очень понимаю, что Вы просите доказать, к сожалению. Для меня это выглядит так, как и это: Если функция зависит от $x,y,z$, то попробуйте доказать, что она зависит от $x,y$ и от $z$.

[Someone]

bitcoin в сообщении #1348289 писал(а):

Для меня это выглядит так, как и это

Это потому, что Вы не хотите сделать то, что Вам советуют.

[bitcoin]

EUgeneUS в сообщении #1348268 писал(а):

И не получится. Чисел может быть и $1008$, а не 12. Строится тривиально.

Имеется ввиду, что кол-во остатков увеличивается, пока их не становится 13, а после, ясно дело уже некуда увеличиваться

-- 22.10.2018, 10:31 --

Someone в сообщении #1348290 писал(а):

Это потому, что Вы не хотите сделать то, что Вам советуют.

Я бы очень хотел, но не очень понимаю - что именно советуют

[Someone]

bitcoin в сообщении #1348292 писал(а):

Я бы очень хотел, но не очень понимаю - что именно советуют

Извините, но то, что написал ET — это уже такая подсказка, что чуть больше — и уже получится полное решение простой учебной задачи. А выкладывать решение правила форума запрещают. Поэтому думайте.

Собственно, что Вам непонятно? Вам рекомендуют взять два числа и вычесть одно из другого. И посмотреть на результат.

bitcoin в сообщении #1348292 писал(а):

Имеется ввиду

Совершенно не важно, что имеет в виду EUgeneUS. Он не прав.

[bitcoin]

ET в сообщении #1348260 писал(а):

Глядя на тему, вспомнил свое решение одной олимпиадной, которую решал очень давно (даже условие подзабыл), но подход от нее сразу дал доказательство этой.
Пусть есть изначально числа .. Ну, выше писали $r_1,r_2,...r_{13}$ Возьмем последовательность $a_1,a_2,...a_{13}$ где $a_i=\sum\limits_{k=1}^{i}r_k$ Тогда у каких-то двух равные остатки на 13, а следовательно их разность...

Я пока что только понял, что такие числа с одинаковой разностью точно должны быть, но вот что дают они - не ясно. Ну делится разность на 13, да, но ведь сумма-то не факт, что делится на 13 у этих же чисел.