Набор чисел раскрашен в 3 цвета. Чисел каждого цвета поровну. Доказать, что существует трёхцветная арифметическая прогрессия длины 3.
Бьюсь уже второй день. Задача действительно не лёгкая. Может у кого-то получится.
Прогрессия
Прогрессия
Последний раз редактировалось DarkMel 27 ноя 2019, 20:06, всего редактировалось 1 раз.
Причина: test
Причина: test
Прогрессия
Вот такая безнадежная выкладка неожиданно сошлась, надо проверять.
А сколько всего есть трехчленных прогрессий среди 3n чисел? Ограничимся случаем n=2k+1. С разностью 1 3n-2 шт, с разностью 2 3n-4 шт, и т.д.,пока эти количества положительны.Всего
А сколько максимум среди них одноцветных? Каждого цвета (n-2)+(n-4)+...=, итого 3k^2
А двухцветных, с преобладанием данного цвета, не больше чем число пар этого цвета , и всего не трехцветных , значит, небольшое количество трехцветных гарантировано. Случай четного n не должен сильно отличаться)
А сколько всего есть трехчленных прогрессий среди 3n чисел? Ограничимся случаем n=2k+1. С разностью 1 3n-2 шт, с разностью 2 3n-4 шт, и т.д.,пока эти количества положительны.Всего
А сколько максимум среди них одноцветных? Каждого цвета (n-2)+(n-4)+...=, итого 3k^2
А двухцветных, с преобладанием данного цвета, не больше чем число пар этого цвета , и всего не трехцветных , значит, небольшое количество трехцветных гарантировано. Случай четного n не должен сильно отличаться)
Последний раз редактировалось Ian 27 ноя 2019, 20:06, всего редактировалось 1 раз.
Причина: test
Причина: test
Прогрессия
Ссылки на докозательства. Довольно нетривиальные!
http://www.kurims.kyoto-u.ac.jp/EMIS/journ...ers/d18/d18.pdf
http://www.combinatorics.org/ojs/index.php...oad/v11i1r1/pdf
http://www.kurims.kyoto-u.ac.jp/EMIS/journ...ers/d18/d18.pdf
http://www.combinatorics.org/ojs/index.php...oad/v11i1r1/pdf
Последний раз редактировалось DarkMel 27 ноя 2019, 20:06, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Олимпиадные задачи»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 1 гость