A B. 5502. feladat (2026. január)

B. 5502. Legyen $\displaystyle A$ egy valós számokból álló $\displaystyle n$ elemű halmaz. Mutassuk meg, hogy legalább $\displaystyle 4n-3$ szám felírható $\displaystyle a-2b+c$ alakban, ahol $\displaystyle a,b,c\in A$ nem feltétlenül különbözőek.

Javasolta: Pach Péter Pál (Budapest)

(3 pont)

A beküldési határidő 2026. február 10-én LEJÁRT.

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.

Statisztika:

A B. 5502. feladat értékelése még nem fejeződött be.

A KöMaL 2026. januári matematika feladatai

Már regisztráltál?
Új vendég vagy?