Прогрессия

DarkMel · Сообщение **DarkMel** » 05 фев 2015, 19:52

Набор чисел $\{1,2,...,3n \}$ раскрашен в 3 цвета. Чисел каждого цвета поровну. Доказать, что существует трёхцветная арифметическая прогрессия длины 3.

Бьюсь уже второй день. Задача действительно не лёгкая. Может у кого-то получится.

Ian · Сообщение **Ian** » 06 фев 2015, 16:32

Вот такая безнадежная выкладка неожиданно сошлась, надо проверять.
А сколько всего есть трехчленных прогрессий среди 3n чисел? Ограничимся случаем n=2k+1. С разностью 1 3n-2 шт, с разностью 2 3n-4 шт, и т.д.,пока эти количества положительны.Всего $$(6k+1)+(6k-1)+...=(3k+1)^2$$

А сколько максимум среди них одноцветных? Каждого цвета (n-2)+(n-4)+...= $$(2k-1)+(2k-3)+...=k^2$$

, итого 3k^2
А двухцветных, с преобладанием данного цвета, не больше чем число пар этого цвета $\frac{n(n-1)}{2}=2k^2+k$ , и всего не трехцветных $$9k^2+3k<(3k+1)^2$$

, значит, небольшое количество трехцветных гарантировано. Случай четного n не должен сильно отличаться)

DarkMel · Сообщение **DarkMel** » 09 мар 2015, 20:05

Ссылки на докозательства. Довольно нетривиальные!
http://www.kurims.kyoto-u.ac.jp/EMIS/journ...ers/d18/d18.pdf
http://www.combinatorics.org/ojs/index.php...oad/v11i1r1/pdf

yourdomain.com