Вася выписал в ряд 2013 последовательных натуральных чисел в некотором порядке (не обязательно подряд в порядке возрастания). Между каждыми двумя соседними в этом ряду числами Петя вписал наибольший общий делитель этих двух чисел. Может ли оказаться, что числа, написанные Петей - это 2012 последовательных натуральных чисел, тоже написанные в некотором порядке?

задан 10 Янв '14 15:00

изменен 13 Янв '14 19:05

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

Пусть между какими-то числами Петя написал $%d$%. Оба этих числа делятся на $%d$%, и это же верно для разности большего и меньшего из этих чисел. Она не превосходит 2012, так как были взяты последовательные числа в количестве 2013. Значит, все выписанные Петей числа находятся в пределах от 1 до 2012, и последовательными они могут быть только тогда, когда представляют собой перестановку чисел от 1 до 2012.

Для небольшого количества чисел можно привести примеры, когда всё получается. Скажем, если бы Вася написал 9 12 8 10 7, то Петя вписал бы 3 4 2 1. Однако при большом количестве так уже не получается. Доказать это можно многими способами. Рассмотрим один из них.

Каждое чётное число, написанное Петей, расположено между двумя чётными числами Васи. Отсюда следует, что чётных чисел в списке Васи больше, чем у Пети, по крайней мере на 1. Действительно, каждому чётному числу Пети сопоставим число Васи, расположенное слева от него. Все эти числа разные. А для крайнего справа есть ещё одно число, расположенное правее, которое не было учтено. Заметим, что такое положение дел имеет место лишь тогда, когда у Пети все чётные числа расположены подряд.

То же самое соображение можно отнести к числам, которые делятся не на 2, а, скажем, на 3, на 4, на 5 и так далее. Легко понять, что в списке чисел от 1 до 2012 имеется ровно $%[2012/m]$% таких, которые кратны $%m$% (в частности, чётных ровно половина). Среди любых 2013 последовательных чисел количество тех, которые кратны $%m$%, может быть больше максимум на единицу. Это следует из того, что среди $%m$% последовательных натуральных чисел на $%m$% делится ровно одно.

Из того, что было сказано выше, вытекает такое следствие: если описанная конструкция возможна, то для любого $%m$% все числа Пети, делящиеся на $%m$%, должны идти подряд (ср. пример из пяти чисел). А это невозможно, так как если взять произведение трёх различных простых вида $%pqr$% в списке Пети (например, 30), то из трёх чисел $%p$%, $%q$%, $%r$%, которые там тоже должны быть, какие-то два встретятся по одну сторону от $%pqr$%. Пусть тогда $%p$% стоит между $%pqr$% и $%q$%. При этом нарушается расположение подряд чисел списка, кратных $%q$%, что завершает рассуждение.

Судя по всему, к противоречию здесь можно прийти очень многими путями.

ссылка

отвечен 13 Янв '14 20:15

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×191
×44
×10

задан
10 Янв '14 15:00

показан
1610 раз

обновлен
13 Янв '14 20:15

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

по почте:

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

по RSS:

Ответы

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

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