арифметические прогрессии по модулю 3

[rus4]

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

Comments

[anonymous]

Можно, пожалуйста, доказательство еще раз выложить?

[rus4]

Можно, я теперь проще даже умею.

Пусть K --- поле, A --- линейно упорядоченное множество из n элементов (например, A={1,...,n}). Для ненулевой функции f∈ KA из A в K назовём её лидером, соответственно аутсайдером, наименьший, соответственно наибольший, элемент x из A, для которого f(x) не равно 0.

Лемма 1. Пусть X --- линейное подпространство в пространстве KA функций на A размерности m. Тогда количество различных лидеров элементов X равно m. То же и количество аутсайдеров.

Доказательство. Метод Гаусса.

Лемма 2. Пусть в условиях леммы 1 выполняется равенство ∑ x ∈ A f(x)g(x)h(x)=0 для любых функций f,g,h из X. Тогда m ≤ |A|/2.

Доказательство. Пусть не так и 2m>|A|. Тогда по лемме 1 (и принципу Дирихле) найдутся функции f,g ∈ X такие что лидер f совпадает с аутсайдером g. Полагая h=g получаем, что в сумме ∑x ∈ A f(x)g(x)h(x) ровно одно ненулевое слагаемое --- противоречие.

Пусть теперь K=F3 --- поле остатков по модулю 3, A --- подмножество в K^n без 3-прогрессий, то есть a+b+c=0 при a,b,c ∈ A тогда и только когда a=b=c. Пусть X