 |
Az A. 815. feladat (2022. január) |
A. 815. Legyen \(\displaystyle q\) egy 1 főegyütthatós, egész együtthatós polinom. Bizonyítandó, hogy létezik olyan, csak a \(\displaystyle q\) polinomtól függő \(\displaystyle C\) konstans, melyre tetszőleges \(\displaystyle p\) prímszám és tetszőleges \(\displaystyle N\le p\) pozitív egész esetén az \(\displaystyle n! \equiv q(n) \pmod{p}\) kongruenciának legfeljebb \(\displaystyle CN^{2/3}\) megoldása van bármely \(\displaystyle N\) darab egymást követő egész között.
Javasolta: Navid Safaei (Irán)
(7 pont)
A beküldési határidő 2022. február 10-én LEJÁRT.
Megoldás. Először belátjuk a következő lemmát:
Lemma: Álljon a \(\displaystyle H\) halmaz \(\displaystyle N\) egymást követő egész számból: \(\displaystyle H=\{k,k+1,...,k+N-1\}\). Legyen \(\displaystyle S\) a \(\displaystyle H\) tetszőleges részhalmaza és legyen \(\displaystyle \alpha=(|S|-1)/N\). Ekkor létezik egy olyan \(\displaystyle 1\le d \le 2/\alpha\) egész szám, melyre legalább \(\displaystyle N\alpha^2/4\) megoldása van az \(\displaystyle y-x=d\) egyenletnek az \(\displaystyle S\) halmazon.
Bizonyítás: Tekintsük \(\displaystyle S\) egymást követő elemei között a különbséget (és rendeljük hozzá a kisebb elemhez). Legfeljebb \(\displaystyle N\alpha/2\) esetben lehet a különbség nagyobb, mint \(\displaystyle 2/\alpha\). Tehát legalább \(\displaystyle N\alpha/2\) olyan eleme van \(\displaystyle |S|\)-nek, amikor a különbség kisebb, mint \(\displaystyle 2/\alpha\). A skatulya-elv miatt tehát lesz egy különbség, amely legalább \(\displaystyle N\alpha/2\cdot \alpha/2=N\alpha^2/4\) esetben fellép.
Legyen most \(\displaystyle S\) az \(\displaystyle n! \equiv q(n) \pmod{p}\) megoldásainak halmaza a \(\displaystyle H=\{k,k+1,...,k+N-1\}\) halmazon. A fenti lemma miatt van olyan \(\displaystyle 1\le d \le 2/\alpha\), hogy az \(\displaystyle S\) legalább \(\displaystyle N\alpha^2/4\) darab \(\displaystyle a\) elemére \(\displaystyle a+d\) is \(\displaystyle S\)-beli. Ez viszont azt jelenti, hogy
\(\displaystyle q(a)(a+1)(a+2)...(a+d)\equiv q(a+d)\pmod{p}. \)
Vegyük észre, hogy itt a \(\displaystyle q(x)(x+1)...(x+d)-q(x+d)\) polinom gyökeiről van szó. A polinom nem azonosan 0 mod \(\displaystyle p\). Jól ismert tétel, hogy mod \(\displaystyle p\) tekintve a polinomokat is igaz az, hogy legfeljebb annyi gyöke lehet mod \(\displaystyle p\), mint amennyi a foka, ami pedig \(\displaystyle \deg q+d\le \deg q+2/\alpha\). Tehát
\(\displaystyle \deg q+2/\alpha\ge N\alpha^2/4. \)
Innen pedig egyszerű átrendezéssel (és alkalmas, csak \(\displaystyle q\) fokától függő \(\displaystyle C\)-vel)
\(\displaystyle N\alpha^3\le 4\alpha \deg q + 8\le 4\deg q+ 8=C^3. \)
Ezzel pedig (ha S legalább két elemből áll) \(\displaystyle |S|=1+\alpha N\le 2CN^{-1/3}\cdot N=2CN^{2/3}\), és ez volt a bizonyítandó.
Statisztika:
1 dolgozat érkezett. 1 pontot kapott: 1 versenyző.
A KöMaL 2022. januári matematika feladatai