Натуральные числа от 1 до 2014 выписаны по кругу в некотором порядке. Отличница Маша (Ира, Катя, Марго, Сардаана - нужное подчеркнуть) вычислила наибольшие общие делители у всех пар стоящих рядом чисел и заявила, что среди полученных НОДов ровно 1007 чётных. Докажите, что она ошиблась. (К. Сухов, Д. Максимов; Ленинградская Олимпиада)

Поскольку чётный НОД может стоять только между двумя чётными числами, мне кажется, что число чётных НОДов будет равно 1007 минус число "кусков" чётных чисел. То есть, если все они идут одним "куском" (2, 4, 6, ..., 2014), то будет ровно 1006 чётных НОДов, а если, например, чётные числа чередуются с нечётными, то "кусков" получается ровно 1007, а чётных НОДов - нуль.

Вот теперь как бы мне всё это ещё и доказать?

задан 10 Май '14 1:36

Мне кажется, все правильно. Вы уже доказали.

(10 Май '14 1:55) Doctrina

Формализовать рассуждения, то можно так. Пусть $%k>0$% - число цепочек, состоящих из подряд идущих четных чисел, причем следующее и предыдущее число за/перед цепочкой - нечетное. Пусть $%s_1,\ldots, s_k$% - число дуг в каждой цепочке (может быть нулевым). Числа или дуги не могут состоять в двух цепочках одновременно, и каждое четное число лежит в какой-то одной цепочке. Названо число всех дуг: $%s_1+\ldots+s_k$%. Число чисел в каждой цепочке равно $%s_i+1$%. Итого всего четных чисел $%(s_1+1)+\ldots+(s_k+1)=s_1+\ldots+s_k+k=1007+k>1007$%. Но четных чисел $%1007$%. Следовательно, Маша ошиблась.

(10 Май '14 22:01) cartesius
10|600 символов нужно символов осталось
0

Тут проще сразу отказаться от понятия НОД, так как это усложнение, и лучше говорить о количестве пар рядом стоящих чётных чисел. Их не могло получиться так много по той причине, что чётных чисел всего 1007, и не может за каждым из них стоять чётное, так как есть ещё и нечётные числа. (Слово "за" подразумевает фиксированное направление обхода -- скажем, по часовой стрелке.) А любое число от 0 до 1006 включительно получиться могло.

ссылка

отвечен 10 Май '14 1:58

Спасибо!!!

(10 Май '14 2:11) Сардаана
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,131
×259
×64

задан
10 Май '14 1:36

показан
1056 раз

обновлен
10 Май '14 22:01

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

по почте:

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

по RSS:

Ответы

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

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