KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem B. 4839. (December 2016)

B. 4839. Solve the following equation in the set of positive integers:

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

(Proposed by K. Williams, Szeged)

(6 pont)

Deadline expired on 10 January 2017.


Sorry, the solution is available only in Hungarian. Google translation

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)\).


Statistics:

34 students sent a solution.
6 points: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 points:Csahók Tímea, Daróczi Sándor, Németh 123 Balázs, Saár Patrik.
3 points:1 student.
1 point:16 students.
0 point:3 students.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley