A B. 4839. feladat (2016. december)

B. 4839. Oldjuk meg a pozitív egész számok körében a következő egyenletet:

\(\displaystyle n!= 2^a - 2^b. \)

Javasolta: Williams Kada (Szeged, Radnóti M. Gimn.)

(6 pont)

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

Megoldás. Mivel \(\displaystyle 0<n!\), ezért \(\displaystyle a> b\), legyen \(\displaystyle d=a-b> 0\). Ekkor az egyenlet \(\displaystyle n!=2^b(2^d-1)\) alakban írható. Jelölje \(\displaystyle \nu_3(m)\) azt, hogy az \(\displaystyle m\) szám prímtényezős alakjában mi a 3 kitevője. Ha \(\displaystyle 9\leq n\), akkor \(\displaystyle \nu_3(n!)\geq \frac{n}{3}\), hiszen az \(\displaystyle 1\cdot 2\cdot \dots \cdot n\) szorzatban a 3-mal osztható tényezők száma \(\displaystyle \lceil n/3\rceil\) és \(\displaystyle n\geq 9\) esetén szerepel a 9 is, ami már \(\displaystyle 3^2\)-nel is osztható. Ezért \(\displaystyle \nu_3(2^b(2^d-1))=\nu_3(2^d-1)\) értéke is legalább \(\displaystyle n/3\). Megmutatjuk, hogy \(\displaystyle 2^d-1\) pontosan akkor osztható 3-mal, ha \(\displaystyle d\) páros, és ekkor \(\displaystyle \nu_3(2^d-1)=\nu_3(d)+1\). Az állítást \(\displaystyle \nu_3(d)=\alpha\) szerinti teljes indukcióval bizonyítjuk. Vizsgáljuk meg a 2-hatványok 9-es maradékát:

\(\displaystyle 2^0\equiv 1, 2^1\equiv 2, 2^2\equiv 4, 2^3\equiv 8, 2^4\equiv 7, 2^5\equiv 5, 2^6\equiv 1,\dots\)

és innen ciklikusan ismétlődik az \(\displaystyle 1,2,4,8,7,5\). Ebből egyrészt következik, hogy \(\displaystyle 2^d-1\) pontosan akkor osztható 3-mal, ha \(\displaystyle d\) páros, másrészt az is, hogy \(\displaystyle 2^d-1\) pontosan akkor osztható \(\displaystyle 3^2\)-tel is, ha a páros \(\displaystyle d\) kitevő 3-mal is osztható. Legyen tehát \(\displaystyle d=2\cdot 3^\alpha\cdot D\), ahol \(\displaystyle 3\nmid D\). Azt kell megmutatnunk, hogy \(\displaystyle \nu_3(2^d-1)=\alpha+1\), és már láttuk, hogy \(\displaystyle \alpha=0\) esetén ez teljesül. Most megmutatjuk indukcióval, hogy ha az állítás teljesül \(\displaystyle \alpha-1\)-re, akkor \(\displaystyle \alpha\)-ra is. Tekintsük a következő szorzattá alakítást:

\(\displaystyle 2^d-1=2^{2\cdot 3^\alpha\cdot D}-1=(2^{2\cdot 3^{\alpha-1}\cdot D}-1)(2^{4\cdot 3^{\alpha-1}\cdot D}+2^{2\cdot 3^{\alpha-1}\cdot D}+1).\)

Legyen \(\displaystyle c=2^{2\cdot 3^{\alpha-1}\cdot D}\). Megmutatjuk, hogy \(\displaystyle \nu_3(c^2+c+1)=1\). Ehhez azt kell belátnunk, hogy \(\displaystyle 3|c^2+c+1\), de \(\displaystyle 9\nmid c^2+c+1\). Mivel \(\displaystyle c=2^{2\cdot 3^{\alpha-1}\cdot D}\)-ben a kitevő páros, ezért a korábbiak szerint \(\displaystyle 3|(c-1)\), vagyis \(\displaystyle c=3k+1\) alakú (ahol \(\displaystyle k\) nemnegatív egész szám). Ekkor \(\displaystyle c^2+c+1=(3k+1)^2+(3k+1)+1=9(k^2+k)+3\), vagyis valóban \(\displaystyle \nu_3(c^2+c+1)=1\). így az indukciós feltevést is használva:

\(\displaystyle \nu_3(2^d-1)=\nu_3(2^{2\cdot 3^{\alpha-1}\cdot D}-1)+\nu_3(2^{4\cdot 3^{\alpha-1}\cdot D}+2^{2\cdot 3^{\alpha-1}\cdot D}+1)=\alpha+\nu_3(c^2+c+1)=\alpha+1,\)

vagyis az állítás \(\displaystyle \alpha\)-ra is igaz. Tehát \(\displaystyle \nu_3(2^d-1)=\nu_3(d)+1\), ha \(\displaystyle d\) páros. Tegyük fel, hogy \(\displaystyle 9\leq n\). Az eddigiek szerint \(\displaystyle \nu_3(2^d-1)\geq \frac{n}{3}\), vagyis \(\displaystyle \nu_3(d)\geq \frac{n}{3}-1\). Mivel \(\displaystyle 3|2^d-1\) miatt \(\displaystyle d\)-nek párosnak is kell lennie, ezért \(\displaystyle d\geq 2\cdot 3^{\frac{n}{3}-1}\). Mivel \(\displaystyle 2^d-1\leq 2^b(2^d-1)=n!\) és \(\displaystyle n!\) páros, ezért \(\displaystyle 2^d\leq n!\) is teljesül, és ezért

\(\displaystyle 2^{2\cdot 3^{\frac{n}{3}-1}}\leq n!\leq n^n.\)

Ebből 2-es alapú logaritmust véve:

\(\displaystyle 2\cdot 3^{\frac{n}{3}-1} \leq n\log_2 n. \)

Ha \(\displaystyle n=12\), akkor ez már nem teljesül, mert a bal oldal értéke 54, a jobb oldal pedig 44-nél is kisebb. Megmutatjuk, hogy más \(\displaystyle n\geq 12\) esetén sem teljesül. Ehhez elég megmutatnunk, hogy ha valamely \(\displaystyle n\geq 12\)-re \(\displaystyle 2\cdot 3^{\frac{n}{3}-1} > n\log_2 n\), akkor \(\displaystyle 2\cdot 3^{\frac{n+1}{3}-1} > (n+1)\log_2 (n+1)\). Ezt a következő becslések segítségével bizonyíthatjuk:

\(\displaystyle (n+1)\log_2 (n+1)= n(\log_2 n)(1+1/n)\frac{\log_2 n+\log_2(1+1/n)}{\log_2 n}\leq\)

\(\displaystyle \leq n(\log_2 n) (1+1/12)\frac{\log_2 n+\log_2(1+1/12)}{\log_2 n}\leq \)

\(\displaystyle \leq n(\log_2 n) (1+1/12)\frac{\log_2 12+\log_2(1+1/12)}{\log_2 12}<1,2\cdot n(\log_2 n)<\)

\(\displaystyle <3^{1/3}\cdot 2\cdot 3^{\frac{n}{3}-1}= 2\cdot 3^{\frac{n+1}{3}-1}. \)

Tehát azt kaptuk, hogy \(\displaystyle n\geq 12\) esetén az \(\displaystyle n!=2^b(2^d-1)\) egyenletnek nincs megoldása. Ha \(\displaystyle n!=2^b(2^d-1)\), akkor \(\displaystyle 2^b\) az \(\displaystyle n!\) szám legnagyobb 2-hatvány osztója, \(\displaystyle 2^d-1\) pedig az \(\displaystyle n!\) szám páratlan része. így \(\displaystyle 1\leq n\leq 11\) esetén azt kell megvizsgálnunk, hogy \(\displaystyle n!\) páratlan részéhez 1-et adva mikor kapunk 2-hatványt. Az \(\displaystyle n=1,2,\dots,11\) esetekben az \(\displaystyle n!\) szám páratlan része rendre:

\(\displaystyle 1,1,3,3,15,45, 315,315,2835,14175,155925.\)

A páratlan résznél 1-gyel nagyobb szám pontosan az első 5 esetben 2-hatvány, így az egyenletnek pontosan akkor van nemnegatív egész megoldása, ha \(\displaystyle 1\leq n\leq 5\). Vizsgáljuk meg mind az öt esetet:

– Ha \(\displaystyle n=1\), akkor \(\displaystyle n!=1\), ezért \(\displaystyle 2^b=1\) és \(\displaystyle 2^d-1=1\), amiből \(\displaystyle a=1,b=0\) (\(\displaystyle d=1\)), vagyis itt nem kapunk megoldást, mert \(\displaystyle b\) nem pozitív.

–Ha \(\displaystyle n=2\), akkor \(\displaystyle n!=2\), ezért \(\displaystyle 2^b=2\) és \(\displaystyle 2^d-1=1\), amiből \(\displaystyle a=2,b=1\) (\(\displaystyle d=1\)).

–Ha \(\displaystyle n=3\), akkor \(\displaystyle n!=6\), ezért \(\displaystyle 2^b=2\) és \(\displaystyle 2^d-1=3\), amiből \(\displaystyle a=3,b=1\) (\(\displaystyle d=2\)).

–Ha \(\displaystyle n=4\), akkor \(\displaystyle n!=24\), ezért \(\displaystyle 2^b=8\) és \(\displaystyle 2^d-1=3\), amiből \(\displaystyle a=5,b=3\) (\(\displaystyle d=2\)).

–Ha \(\displaystyle n=5\), akkor \(\displaystyle n!=120\), ezért \(\displaystyle 2^b=8\) és \(\displaystyle 2^d-1=15\), amiből \(\displaystyle a=7,b=3\) (\(\displaystyle d=4\)).

Az egyenlet megoldásai tehát: \(\displaystyle (n=2;a=2,b=1),(n=3;a=3,b=1),(n=4;a=5,b=3),(n=5;a=7,b=3)\).

Statisztika:

34 dolgozat érkezett.
6 pontot kapott:	Borbényi Márton, Döbröntei Dávid Bence, Gáspár Attila, Győrffy Ágoston, Kerekes Anna, Kovács 246 Benedek, Matolcsi Dávid, Sokvári Olivér, Tóth Viktor, Weisz Máté.
5 pontot kapott:	Csahók Tímea, Daróczi Sándor, Németh 123 Balázs, Saár Patrik.
3 pontot kapott:	1 versenyző.
1 pontot kapott:	16 versenyző.
0 pontot kapott:	3 versenyző.

A KöMaL 2016. decemberi matematika feladatai