Разбиение множества простых чисел на два подмножества

[Ktina]

Все простые числа произвольным образом разбиты на две группы (на два непустых непересекающихся подмножества -- прим. ред.).
Доказать, что хотя бы в одной из групп найдутся три числа, одно из которых есть среднее арифметическое двух других.

[Ms-dos4]

Теорема Грина-Тао немедленно решает задачу. Пользуясь её мы устанавливаем возможность существования арифм. прогрессии(в данной задаче достаточно 3 членов). И далее один из членов есть среднее арифметическое соседних.

[Ktina]

Ms-dos4 в сообщении #715753 писал(а):

Теорема Грина-Тао немедленно решает задачу

Можно и без неё обойтись. Тем паче, что Теорема Грина — Тао была доказана только в 2004г, а наша задача на порядок древнее.

-- 26.04.2013, 14:44 --

Ms-dos4 в сообщении #715753 писал(а):

Пользуясь её мы устанавливаем возможность существования арифм. прогрессии(в данной задаче достаточно 3 членов). И далее один из членов есть среднее арифметическое соседних.

А кто сказал, что эти три члена одного цвета будут? В смысле, в одном подмножестве?

[Sender]

Да, трёх маловато. Даже восемь можно распихать по двум множествам.
$\{a_1,a_1+2d,a_1+4d,a_1+5d\}$,
$\{a_1+d,a_1+3d,a_1+6d,a_1+7d\}$.

[Ktina]

Sender в сообщении #715765 писал(а):

Да, трёх маловато. Даже восемь можно распихать по двум множествам.
$\{a_1,a_1+2d,a_1+4d,a_1+5d\}$,
$\{a_1+d,a_1+3d,a_1+6d,a_1+7d\}$.

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

[Ms-dos4]

Цитата:

А кто сказал, что эти три члена одного цвета будут? В смысле, в одном подмножестве?

Теорема устанавливает существование прогрессий с любым числом членов

[Ktina]

Ms-dos4 в сообщении #715768 писал(а):

Теорема устанавливает существование прогрессий с любым числом членов

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

[vorvalm]

Если объединять членов прогрессии по одному и по два в произвольном порядке
, то через каждые 5 шагов мы встретим нужные нам 3 числа.

[Ms-dos4]

Цитата:

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

Теорема Ван-Дер-Вардена в помощь. При n>8 разбить на 2 подмножества без создания прогрессии не удастся.

[Cash]

Кидаетесь ядерными бомбами направо и налево . Только теорема Ван-дер-Вардена тут не к месту. В ней красят натуральный ряд, а здесь только его подмножество.

[Ktina]

Cash в сообщении #716224 писал(а):

Кидаетесь ядерными бомбами направо и налево . Только теорема Ван-дер-Вардена тут не к месту. В ней красят натуральный ряд, а здесь только его подмножество.

Нудным перебором (может, Вы без перебора сумеете доказать?) убеждаемся, что любая арифметическая прогрессия из 9 членов не может быть разбита на 2 подмножества так, чтобы ни в одном из них не нашлось трёх чисел, образующих арифметическую прогрессию.

А арифметическая прогрессия из 9 простых чисел существует:
199, 409, 619, 829, 1039, 1249, 1459, 1669, 1879.

[hurtsy]

Cash в сообщении #716224 писал(а):

Кидаетесь ядерными бомбами направо и налево

Действительно, больше знаний - больше печали. Лучше взять маленький отрезок {2,3,5,7,11,13,17,19,23} и попробовать разбить его на два подмножества свободных от среднего арифметического. С уважением.

[mihailm]

hurtsy в сообщении #716256 писал(а):

...Лучше взять маленький отрезок {2,3,5,7,11,13,17,19,23} и попробовать разбить его на два подмножества свободных от среднего арифметического. С уважением.

Его можно - $\{2, 3, 7, 17\}, \{5, 11, 13, 19, 23\}$

[Cash]

Ktina в сообщении #716236 писал(а):

Нудным перебором (может, Вы без перебора сумеете доказать?) убеждаемся, что любая арифметическая прогрессия из 9 членов не может быть разбита на 2 подмножества так, чтобы ни в одном из них не нашлось трёх чисел, образующих арифметическую прогрессию.

Так это очевидное следствие из теоремы Ван-дер-Вардена. Сгодилась, всё-таки, родная...

[Ms-dos4]

О чём я и говорил