 |
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:
| \(\displaystyle \mathrm{gcd}\bigg( \prod \limits_{a \in A} {a}; \prod \limits_{b \in B} {b} \bigg) ~\Bigg|~ \bigg| \prod \limits_{a \in A} {a} - \prod \limits_{b \in B} b \bigg| = k. \) | (1) |
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:
| \(\displaystyle \prod \limits_{b \in B} {b} < n^{\frac{n}3+1+u+v}. \) | (2) |
Továbbá, az \(\displaystyle \prod \limits_{a \in A} a\) szorzat legalább \(\displaystyle 6k\), így
| \(\displaystyle \frac{\prod \limits_{b \in B} b}{\prod \limits_{a \in A} a} \ge \frac{\Big(\prod \limits_{a \in A} a\Big) -k}{\prod \limits_{a \in A} a} = 1 - \frac{k}{\prod \limits_{a \in A} a} \ge 1 - \frac16 = \frac56. \) | (3) |
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,
| \(\displaystyle \prod \limits_{a \in A} a \cdot \prod \limits_{b \in B} b > \left(\frac{n}{e}\right)^n. \) | (4) |
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