Az A. 647. feladat (2015. szeptember)

A. 647. Legyen $\displaystyle k$ nemnegatív egész szám. Bizonyítsuk be, hogy csak véges sok $\displaystyle n$ pozitív egész esetén léteznek olyan diszjunkt $\displaystyle A$ és $\displaystyle B$ halmazok, amelyekre $\displaystyle A \cup B = \{1; 2; \ldots; n\}$ és $\displaystyle \displaystyle\left|\prod \limits_{a \in A} {a} - \prod\limits _{b \in B} {b}\right|=k$ teljesül.

Javasolta: Maga Balázs, Budapest

(5 pont)

A beküldési határidő 2015. október 12-én LEJÁRT.

Megoldás. A $\displaystyle k=0$ esetet külön kezeljük. Ha $\displaystyle n\ge2$, akkor a Csebisev-tétel miatt van olyan $\displaystyle p$ prímszám, amelyre $\displaystyle \frac{n}2<p\le n$; a $\displaystyle p$ szerepel az $\displaystyle 1,2,\ldots,n$ számok között, de a $\displaystyle p$ minden más többszöröse nagyobb $\displaystyle n$-nél. Ezért a $\displaystyle \prod_{a \in A} a$ és $\displaystyle \prod_{b\in B} b$ szorzatok közül az egyik osztható $\displaystyle p$-vel, a másik szorzat pedig nem; a két szorzat nem lehet egyenlő.

* * *

A továbbiakban feltételezzük, hogy $\displaystyle k\ge1$ és $\displaystyle n\ge 6k$. Az $\displaystyle 1,2,\ldots,n$ számok között tehát szerepel a $\displaystyle 6k$ is; a szimmetria miatt feltehetjük, hogy $\displaystyle 6k\in A$. Legyen a $\displaystyle k$ prímténytezős felbontásában a $\displaystyle 2$ és a $\displaystyle 3$ kitevője $\displaystyle u$, illetve $\displaystyle v$.

Vegyük észre, hogy a $\displaystyle \prod \limits_{a \in A} {a}$ és $\displaystyle \prod \limits_{b \in B} {b}$ szorzatok legnagyob közös osztója a $\displaystyle k$-nak osztója:

Mivel $\displaystyle 6k\in A$, $\displaystyle 2^{u+1} ~\bigg|~ 6k ~\bigg|~ \prod \limits_{a \in A} {a}$. Ha a $\displaystyle B$ halmazban $\displaystyle u$-nál több páros szám lenne, akkor a $\displaystyle \prod \limits_{b \in B} {b}$ szorzat is osztható lenne $\displaystyle 2^{u+1}$-gyel, de ez ellentmondana (1)-nek. A $\displaystyle B$ halmazban tehát legfeljebb $\displaystyle u$ páros szám lehet. Hasonlóan látjuk, hogy a $\displaystyle B$ halmazban legfejlebb $\displaystyle v$ darab $\displaystyle 3$-mal osztható szám van.

Összességében a $\displaystyle B$ halmazban legfeljebb $\displaystyle u+v$ kivétellel mindegyik szám relatív prím a $\displaystyle 6$-hoz, vagyis $\displaystyle 6$-tal osztva $\displaystyle 1$ vagy $\displaystyle 5$ maradékot ad; az $\displaystyle 1,2,\ldots, n$ számok között legfeljebb $\displaystyle \left\lceil\frac{n}{3}\right\rceil< \frac{n}3+1$ ilyen lehet. A kivételekkel együtt a $\displaystyle B$ halmaznak kevesebb, mint $\displaystyle \frac{n}{3}+1+u+v$ eleme van. Ezek mindegyikét becsüljük felülről $\displaystyle n$-nel:

Továbbá, az $\displaystyle \prod \limits_{a \in A} a$ szorzat legalább $\displaystyle 6k$, így

Végül, mivel az $\displaystyle 1,2,\ldots, n$ számok mindegyike pontosan az egyik halmazban szerepel,

$\displaystyle \prod \limits_{a \in A} a \cdot \prod \limits_{b \in B} b = n!.$

A jól ismert $\displaystyle n!>\left(\frac{n}{e}\right)^n$ egyenlőtlenséggel kombinálva,

A (3) és (4) szorzatát (2)-vel összevetve,

$\displaystyle \frac56 \cdot \left(\frac{n}{e}\right)^n < \left( \prod \limits_{b \in B} b \right)^2 < \left( n^{\frac{n}{3}+1+u+v}\right)^2$

$\displaystyle n^{\frac{n}{3}} < \frac65 e^n n^{2+2u+2v}$

$\displaystyle n < \left(\frac65\right)^{\frac3n} \cdot e^3 \cdot \left(n^{\frac1n}\right)^{6+6u+6v} < \left(\frac65\right)^3 \cdot e^3 \cdot 2^{6+6u+6v}.$

Ebből láthatjuk, hogy $\displaystyle n$ nem lehet akármilyen nagy.

Statisztika:

10 dolgozat érkezett.
5 pontot kapott:	Baran Zsuzsanna, Gáspár Attila, Imolay András, Szabó 789 Barnabás, Williams Kada.
1 pontot kapott:	3 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2015. szeptemberi matematika feladatai