Из чисел от 1 до 2n выбрано n+1 число

[Edward_Tur]

Из чисел от 1 до $2n$ выбрано $n+1$ число. Докажите, что среди выбранных чисел найдется пара взаимно простых, если
1) $2n+1$ - простое число;
2) $n$ - произвольное число.

[Хорхе]

Так два последовательных числа найдутся, или я ошибаюсь?

[Sasha2]

Каждое натуральное число, большее единицы, является взаимно простым с предыдущим (легко получить из основной теоремы арифметики).
Следовательно, если мы хотим набрать n+1 чисел, чтобы среди них не было взаимно простых, мы должны брать их, как минимум через одно. Но невозможно набрать n+1 чисел из чисел от 1 до 2n через одно.
Следовательно одна пара взаимно простых чисел найдется.

[Cave]

А при $n\geqslant 5$ найдутся два не взаимно простых. Правда, вряд ли это поможет.

[worm2]

Можно усилить до "из чисел от 1 до 2n+1..."

[Sasha2]

Наверно можно уще боьше усилить.
Найдется не только 2 взаимно простых, но и одно простое. А следовательно и два взаимно простых.

[Хорхе]

Sasha2 в сообщении #238445 писал(а):

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

Это вранье, конечно. Асимптотическая плотность простых равна нулю. Уже начиная с $n=16$ их (вместе с единицей, которая тоже подходит) меньше половины.

Цитата:

А следовательно и два взаимно простых.

И это вранье! Если число простое, это не значит, что любое другое с ним взаимно просто.

[Sasha2]

Ну я просто опустил тривиальный случай, когда из n+1 числа выбирается не более 1 четного.
Не любое да, но то, которое меньше его на 1, точно взаимно просто с ним.

[Хорхе]

Sasha2 в сообщении #238460 писал(а):

Ну я просто опустил тривиальный случай, когда из n+1 числа выбирается не более 1 четного.
Не любое да, но то, которое меньше его на 1, точно взаимно просто с ним.

Видимо, частица "не" тут лишняя. И именно этот случай Вы имели в виду! Молодец. Я Вам больше скажу: в этом случае не только одно простое среди них будет, а почти все! Ну кроме, может быть, двойки.

Все же, если без шуток: а сколько все же надо взять чисел, чтобы среди них гарантированно нашлось два взаимно простых? Пусть даже не наименьшее количество. Но понятно, что достаточно намного меньше половины.

-- Чт авг 27, 2009 23:42:11 --

Впрочем, чего это я? Как раз половина. Все четные.

-- Чт авг 27, 2009 23:46:33 --

Задача про два не взаимно простые тоже простенькая. Там ответ $\pi(n)+2$.

Так, чтобы одно делилось на другое, тоже все ответ знают: $n+1$.

Так, чтобы какое-то не делилось на какое-то другое, тоже просто: $[\log_2 n] + 1$.

-- Чт авг 27, 2009 23:47:25 --

Тогда предлагаю вот такую задачу на эту тему: сделать из этой задачи задачу.

[Sasha2]

А Вы учитываете еще, что числа берутся не где попало, а в промежутке от 1 до 2n?
А вообще, как Вы думаете, одно и тоже набирать простые числа (или взаимно простые) в каком угодно промежутке от k до k+2n или есть какие то отличия, когда этот промежуток от 1 до n?
А насчет Вашей задачи. Вот наверно случай от 1 до 6 можно и вручную перебрать.
А далее, есть одна такая схожая задача и мне почему то кажется, что к ней Ваша может быть сведена.
А именно:
Доказать, что среди любых 7 человек всегда найдутся либо 3 попрано знакомых, либо трое попарно незнакомых.

[Kid Kool]

Sasha2

достаточно 6-и.

[Sasha2]

А чтобы из задачи сделать задачу, наверно прежде всего надо откинуть все четные числа.
Мне так кажется, а дальше уже смотреть, скоолько их взять, откуда и докуда и какой вопрос трудней.

[VAL]

Sasha2 в сообщении #238588 писал(а):

Доказать, что среди любых 7 человек всегда найдутся либо 3 попрано знакомых, либо трое попарно незнакомых.

Элементарно! выгоняем одного взашей и получаем известное утверждение

[ИСН]

Sasha2 в сообщении #238610 писал(а):

прежде всего надо откинуть все четные числа.

И чо? На то место выкатится делимость на 3 и всё по новой.
Нет, пока что не пахнет задачей...

[Хорхе]

ИСН в сообщении #238690 писал(а):

Sasha2 в сообщении #238610 писал(а):

прежде всего надо откинуть все четные числа.

И чо? На то место выкатится делимость на 3 и всё по новой.
Нет, пока что не пахнет задачей...

А вот с этого места поподробней. Потому что мне показалось, что это таки-да задача.