4
1

Среди 2 последовательных чисел первое всегда взаимно простое со вторым. Среди набора из 3 чисел среднее взаимно простое с 1 и 3. В наборе из 4 последовательных чисел так же всегда найдётся число взаимно простое с остальными. Собственно задача:

Найдите максимальное число $%k \in \mathbb{N}$% такое, что для любого $%n \in \mathbb{N}$% в каждом наборе из $%1, 2, ..., k$% последовательных чисел начиная с $%n$% всегда найдётся хотя бы одно число взаимно простое со всеми остальными.

задан 22 Ноя '13 22:04

изменен 22 Ноя '13 22:05

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

Для 17 последовательных чисел можно привести пример, когда ни одно из них не подходит, то есть каждое из чисел не взаимно просто с каким-то другим числом из списка. Рассмотрим числа 27830, ..., 27846. Среди них 9 чётных. Рассмотрим оставшиеся 8 нечётных; из них 27831, 27837, 27843 делятся на 3, а 27835, 27845 делятся на 5. Число 27833 делится на 13 вместе с ещё одним числом списка, 27839 делится на 7, а 27841 делится на 11. Ясно, что можно взять больше 17 чисел, и то же самое будет верно.

Докажем теперь, что если чисел 16, то среди них обязательно найдётся взаимно простое с остальными. Из этого будет следовать, что максимальное значение $%k$% равно $%16$%. Предположим противное. Тогда любое из чисел должно иметь некоторый общий простой делитель $%p$% вместе с каким-то ещё числом. Понятно, что $%p\le13$%. Нечётных чисел здесь имеется всего 8, и среди них кратны 3 не более трёх, кратны 5 не более двух, кратны 7 не более двух, и не более чем одно число может быть кратно каждому из чисел 11 и 13. Пока что это даёт оценку сверху, равную 9, и её нужно улучшить, показав, что одновременно все эти условия выполнены быть не могут.

Будем для удобства считать, что первое число чётно -- это не нарушает общности. Рассмотрим для начала случай, когда число $%p=13$% не оказывается задействовано. В этом случае оценка уменьшается на единицу, и каждое из восьми нечётных чисел оказывается отнесённым ровно к одному из значений $%p=3,5,7,11$%. Чтобы число 11 оказалось задействовано, необходима делимость на 11 одного из чисел $%n+1$%, $%n+3$%, $%n+13$%, $%n+15$%. При этом два числа, кратных 7, возникают только в случае, если $%n+1$% и $%n+15$% делятся на $%7$%. Эти числа уже не могут входить в состав трёх нечётных чисел, кратных 5, для которых остаётся один вариант делимости на 5 чисел $%n+3$% и $%n+13$%, но тогда ни одно из них не будет задействовано для делимости на 11.

Теперь пусть число 13 задействовано, то есть $%n+1$% или $%n+15$% на него делится. Тогда нечётное число, кратное 7, из оставшихся может быть лишь одно, и это второе число из двух только что рассмотренных. То есть верхняя оценка снова снижается на единицу, и на 11 могут делиться лишь $%n+3$% или $%n+13$%. В этом случае на 5 уже не могут делиться два оставшихся нечётных числа, так как в противном случае в их состав входило бы одно из уже использованных чисел.

Добавление. Я сейчас вспомнил, что уже излагал однажды решение этой задачи. Если бы обнаружил это раньше, то не стал бы вспоминать решение и излагать его заново. На всякий случай, вот ссылка. Кое-какие детали рассуждения, там, возможно, изложены более "прозрачно".

ссылка

отвечен 23 Ноя '13 1:55

изменен 23 Ноя '13 2:37

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

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

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

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

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

отмечен:

×334

задан
22 Ноя '13 22:04

показан
1456 раз

обновлен
23 Ноя '13 2:37

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

по почте:

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

по RSS:

Ответы

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

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