Miklos Schweitzer 2013 problem 1

[drago]

Нека [tex]q[/tex] е положително цяло число. Докажете, че съществува константа [tex]C_q[/tex] (зависеща само от [tex]q[/tex]), такава че за всяко крайно множество от цели числа е в сила:

[tex]|A+qA|\ge (q+1)|A|-C_q[/tex].

където [tex]A+qA=\{a_1+q a_2 \,\mid \, a_1,a_2 \in A\}[/tex], а [tex]|B|[/tex] е броя на елементите на множеството [tex]B[/tex].

Коментар: Не мога да я реша и не знам решението, но ми е страшно интересна!

[ptj]

Aко опиташ с индукция по броя на елементите на [tex]A[/tex] (съществено е че са различни) ,

ще се наложи да докажеш, че новите елементи в [tex]\{a_{n+1}+qa_i\|i=1,2,...,n\}\cup\{a_i+qa_{n+1}|i=1,2,...,n\}[/tex] са поне q+1.

Това е вярно когато [tex]n>q[/tex], тогава за останалите случаи просто ще трябва да избереш подходящо [tex]C_q[/tex], така че при [tex]n\le q[/tex] да е изпълнено например

[tex](q+1)|A|-C_q\le (q+1)q-C_q\le 0 \Leftrightarrow C_q\ge q^2-q[/tex]

[drago]

...ще се наложи да докажеш, че новите елементи в [tex]\{a_{n+1}+qa_i\|i=1,2,...,n\}\cup\{a_i+qa_{n+1}|i=1,2,...,n\}[/tex] са поне q+1.

Това е вярно когато [tex]n>q[/tex]...

Защо ?

[ptj]

Без загуба на общност може да се избере [tex]a_{n+1}>a_i|i=1,2,...,n[/tex] , т.е. елементите да са подредени в нарастващ ред.
Не съм се изразил правилно - за да възможно доказателство с индукция, ще е необходимо да се докаже, че новите двойки в които участва [tex]a_n+1[/tex] са поне [tex]n+1>q+1[/tex].

[drago]

Достатъчно е да са поне q+1, но ме съмнява, че този подход може да стане. Пробвал съм го в различни варианти, което не значи, че ти няма да успееш!
Състезанието Miklos Schweitzer не е online. Дават се около 10 задачи, като участниците имат срок от 10 дни за предоставяне на решенията. Според мен,това е най-трудното от всички студентски състезания. Задачите понякога са непубликувани резултати на авторите, известни унгарски математици.
Конкретно, този проблем е на Antol Balog, тук може да се види решението, но за съжаление е на унгарски:
http://www.bolyai.hu/Schweitzer_jelentes_2013-1.pdf
(първият проблем)
П.П. Понеже съм го прекарвал през google translate, тази задача е решена само от един състезател.