На доске написано число $%2015$% и ещё несколько (не менее двух) натуральных чисел, не превосходящих $%5000$%. Все написанные на доске числа различны. Сумма любых двух из написанных чисел делится на какое-нибудь из остальных.

а) Может ли на доске быть записано ровно $%1009$% чисел?

б) Может ли на доске быть ровно пять чисел?

в) Какое наименьшее количество чисел может быть записано на доске?

задан 29 Апр '15 21:09

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

а) Может. Например, числа 1, 2, 3, ... , 1007, 2014, 2015. Если среди двух чисел отсутствует 1, то их сумма делится на неё. Если 1 присутствует в паре вместе с $%k$%, и число $%k+1$% тоже присутствует, то сумма на него делится. Оставшиеся случаи: $%1+1007$% и $%1+2015$% делятся на $%2$%.

б) Может: $%a$%, $%2a$%, $%3a$%, $%4a$%, $%5a$%, где $%a=403$%. Ясно, что сумма любых двух чисел делится на $%a$%; $%a+ka$% делится на $%(k+1)a$%; $%a+5a$% делится на $%2a$%.

в) Рассмотрим случай трёх чисел. Опишем все такие возможности. Про наличие числа 2015 временно забудем. Пусть имеются три числа $%a$%, $%b$%, $%c$%, где сумма любых двух делится на третье. Если они все вместе имеют нетривиальный общий делитель, то на него можно сократить, и свойство сохранится. Поэтому будем считать, что НОД$%(a,b,c)=1$%. Из этого следует, что числа взаимно просты попарно: если, скажем, $%a$% и $%b$% делятся на $%p$%, то $%b+c$% делится на $%a$%, и потому на $%p$%, то есть $%c$% также кратно $%p$%.

Поскольку сумма двух чисел делится на третье, то сумма всех чисел делится на каждое. Числа попарно взаимно просты, поэтому сумма должна делиться на произведение. В частности, $%a+b+c\ge abc$%. Полагая $%a < b < c$%, имеем $%a+b+c < 3c$%, откуда $%ab < 3$%. Следовательно, $%a=1$%, $%b=2$%. При этом $%c+3$% делится на $%2c$%, поэтому $%c=3$%.

Таким образом, тройка чисел из условия должна иметь вид $%d$%, $%2d$%, $%3d$%. Поскольку $%2015$% нечётно и не делится на $%3$%, оно равно $%d$%, но тогда $%3d > 5000$%.

Таким образом, набора из трёх чисел быть не может, а пример из четырёх чисел такой: $%a$%, $%2a$%, $%3a$%, $%5a$%, где $%a=403$%.

ссылка

отвечен 30 Апр '15 5:25

изменен 30 Апр '15 14:48

@falcao: Извините, пожалуйста за беспокойство, я пытался разобраться, но так до конца и не понял, почему если сумма всех чисел делится на каждое и числа попарно взаимно просты, то сумма должна делиться на произведение. Заранее благодарен.

(30 Апр '15 18:08) serg55

Я могу ответить.

Вот смотрите сумма это какое-то число. И теперь мы знаем, что это число делится на два взаимно простых числа, скажем, 3 и 4. То мы ведь можем утверждать что наше число делится на 12? А дальше по индукции легко доказать, что делится на произведение, если множителя не два, а больше.

(30 Апр '15 18:12) Роман83
1

@serg55: это общий факт. Если число делится на, скажем, 4, 7 и 33 (попарно взаимно простые), но оно делится на $%4\cdot7\cdot33$%. Это следует из основной теоремы арифметики (в каноническом разложении присутствуют $%2^2$%, $%3$%, $%7$% и $%11$%; у сомножителей нет общих простых чисел в разложении, поэтому произведение тоже входит).

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

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

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

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

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

отмечен:

×4,127

задан
29 Апр '15 21:09

показан
4788 раз

обновлен
30 Апр '15 18:18

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

по почте:

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

по RSS:

Ответы

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

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