Problem B. 5502. (January 2026)

B. 5502. Let $\displaystyle A$ be a set of real numbers with $\displaystyle n$ elements. Prove that at least $\displaystyle 4n-3$ numbers can be written in the form $\displaystyle a-2b+c$ such that $\displaystyle a$, $\displaystyle b$, $\displaystyle c\in A$ not necessarily distinct.

Proposed by Péter Pál Pach, Budapest

(3 pont)

Deadline expired on February 10, 2026.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. Legyenek az $\displaystyle A$ halmaz elemei nagyság szerinti sorrendben:

$\displaystyle a_1<a_2<\dots<a_n.$

Az alábbiakban megadunk $\displaystyle 4n-3$ számot, melyek mind $\displaystyle a-2b+c$ ($\displaystyle a,b,c\in A$) alakúak és különbözők:

$$\begin{gather*} a_1-2a_n+a_1 ~~<~~ a_1-2a_n+a_2 ~~<~~ \dots ~~<~~ a_1-2a_n+a_n ~~<~~ a_2-2a_n+a_n ~~<~~ \dots ~~<~~ a_n-2a_n+a_n ~~=\\=~~ a_1-2a_1+a_1 ~~<~~ a_1-2a_1+a_2 ~~<~~ \dots ~~<~~ a_1-2a_1+a_n ~~<~~ a_2-2a_1+a_n ~~<~~ \dots ~~<~~ a_n-2a_1+a_n. \end{gather*}$$

Megjegyzések. A $\displaystyle (4n-3)$-as korlát éles. Valóban, ha például $\displaystyle A=\{1,2,\dots,n\}$, akkor az $\displaystyle a-2b+c$ alakban előálló számok $\displaystyle -(2n-2),-(2n-1),\dots,2n-1,2n-2$, vagyis számuk éppen $\displaystyle 4n-3$. (Akkor is ennyi számot kapunk, ha $\displaystyle A$ egy tetszőleges $\displaystyle n$ hosszú számtani sorozat.)

Boris Bukh eredménye, hogy hasonló becslés igazolható, ha az $\displaystyle 1,-2,1$ helyett olyan együtthatókat veszünk (akárhányat), melyek legnagyobb közös osztója 1, ekkor a becslésben $\displaystyle n$ együtthatója az együtthatók abszolút értékének összege lesz.

Az analóg kérdést modulo $\displaystyle p$ vizsgálva (ahol $\displaystyle p$ prímszám) azonban nehezebb problémát kapunk. Itt természetesen nem hivatkozhatunk rendezésre, és a fent felsorolt $\displaystyle 4n-3$ elem között egybeesések is lehetnek. Noah Kravitz azt kérdezte, hogy mi az a legkisebb $\displaystyle n$ érték, hogy ha $\displaystyle A\subseteq \{0,1,\dots,p-1\}$ mérete $\displaystyle n$, akkor $\displaystyle a-2b+c$ ($\displaystyle a,b,c\in A$) alakban előálló számok modulo $\displaystyle p$ maradékaként biztosan mind a $\displaystyle p$ féle maradék előáll. Kis $\displaystyle p$ értékek esetén a válasz $\displaystyle n=\left\lceil \frac{p-1}{4}\right\rceil +1$, azonban általánosan ez nem ismert. Vsevolod Lev, Matolcsi Máté, Pach Péter Pál és Varga Dániel azt bizonyították, hogy $\displaystyle n>2p/7$ esetén már minden maradék előáll, ha $\displaystyle p>3$. Továbbra is nyitott kérdés, hogy a $\displaystyle 2/7$ konstans javítható-e $\displaystyle 1/4$-re.

Statistics:

69 students sent a solution.

3 points: 56 students.

2 points: 6 students.

1 point: 3 students.

0 point: 4 students.

Problems in Mathematics of KöMaL, January 2026

69 students sent a solution.
3 points:	56 students.
2 points:	6 students.
1 point:	3 students.
0 point:	4 students.

Already signed up?
New to KöMaL?