Az A. 770. feladat (2020. február)

A. 770. Határozzuk meg azokat az $\displaystyle n$ pozitív egészeket, melyekre $\displaystyle n!$ két Fibonacci-szám szorzata.

(7 pont)

A beküldési határidő 2020. március 10-én LEJÁRT.

Megoldásvázlat. Jelölések:

$\displaystyle F_k$ a $\displaystyle k$-adik Fibonacci-szám ($\displaystyle F_0=0$, $\displaystyle F_1=F_2=1$)
$\displaystyle v_3(x)$ a $\displaystyle 3$ kitevője az $\displaystyle x$ prímtényezős felbontásában.

Mivel $\displaystyle F_1=F_2=1$, csak az $\displaystyle 1$-nél nagyobb indexet használjuk; bármely $\displaystyle F_k$ említése esetén a $\displaystyle k$ legalább $\displaystyle 2$.

1. lemma: ($\displaystyle k\ge2$ esetén) $\displaystyle F_k\ge1.6^{k-1}$.

Bizonyítás: Teljes indukció $\displaystyle k$ szerint. $\displaystyle k=2,3$-ra $\displaystyle F_2=1=1.6^0$, $\displaystyle F_3=2>1.6^1$.

Ha az állítás igaz valamely $\displaystyle k\ge3$-re, akkor $\displaystyle (k+1)$-re is igaz:

$\displaystyle F_{k+1}=F_k+F_{k-1}\ge 1.6^k+1.6^{k-1}=1.6^{k-1}\cdot(1.6+1)>1.6^{k-1}\cdot 1.6^2 = 1.6^{k+1}.$

2. lemma: $\displaystyle F_{3k}=5F_k^3+3(-1)^kF_k$.

Bizonyítás: A Fibonacci-számok explicit alakja szerint az $\displaystyle u=\dfrac{1+\sqrt5}2$, $\displaystyle v=\dfrac{1-\sqrt5}2$ számokkal $\displaystyle F_k=\dfrac{u^k-v^k}{\sqrt5}$. Ezt behelyettesítve,

$\displaystyle F_{3k} = \frac{u^{3k}-v^{3k}}{\sqrt5} = \frac{(u^k-v^k)^3+3(uv)^k(u^k-v^k)}{\sqrt5} = 5\left(\frac{u^k-v^k}{\sqrt5}\right)^3+3(-1)^k\frac{u^k-v^k}{\sqrt5} = 5F_k^3+3(-1)^kF_k. $

3. lemma: Ha $\displaystyle 3^t|F_k$, akkor $\displaystyle 4\cdot 3^{t-1}|k$. (Visszafelé is igaz, de erre most nem lesz szükségünk.)

Bizonyítás: Teljes indukció $\displaystyle t$ szerint. A Fibonacci-számok $\displaystyle 9$-es maradékai ($\displaystyle F_0=0$-val kezdve) $\displaystyle 24$ szerint periodikusak:

$\displaystyle \begin{matrix} 0 & 1 & 1 & 2 \\ 3 & 5 & 8 & 4 \\ 3 & 7 & 1 & 8 \\ 0 & 8 & 8 & 7 \\ 6 & 4 & 1 & 5 \\ 6 & 2 & 8 & 1 \\ 0 & 1 & 1 & \ldots \\ \end{matrix} $

Az állítás leolvasható $\displaystyle t=1$-re és $\displaystyle t=2$-re.

Az indukciós feltevés a 2. Lemmából következik. Tegyük fel, hogy a Lemma igaz valamilyen $\displaystyle t\ge2$-re, és vizsgáljuk $\displaystyle (t+1)$-et. Ha $\displaystyle 3^{t+1}|F_k$, akkor $\displaystyle 3^t|F_k$ is teljesül, és az indukciós feltevés szerint $\displaystyle 4\cdot3^{t-1}|k$. Legyen $\displaystyle m=k/3$; a 2. Lemma szerint $\displaystyle F_k=F_{3m}=5F_m^3+3F_m$. Mivel $\displaystyle 3|F_k$, látjuk, hogy $\displaystyle 3|F_m$, majd $\displaystyle v_3(5F_m^3)>v_3(3F_m)$, és így $\displaystyle v_3(F_k)=v_3(F_m)+1$. Végül $\displaystyle 3^t|F_m$, ami miatt $\displaystyle 4\cdot3^{t-1}|m$, tehát $\displaystyle 4\cdot3^t|k$.

4. lemma: Ha $\displaystyle n\ge9$, akkor $\displaystyle v_3(n!)\ge\frac{n}{3}$.

Bizonyítás: A Legendre-formula szerint $\displaystyle v_3(n!)=\sum_{k=1}^\infty\left[\frac{n}{3^k}\right]$. Ha csak az első két tagot vesszük, $\displaystyle v_3(n!)\ge\left[\frac{n}{3}\right]+\left[\frac{n}{9}\right]\ge\frac{n}{3}$.

A megoldáshoz felülről becsüljük $\displaystyle n$-et. Tegyük fel, hogy $\displaystyle n\ge 9$, $\displaystyle n!=F_kF_\ell$, $\displaystyle k,\ell\ge2$, $\displaystyle x=v_3(F_k)\ge0$ és $\displaystyle y=v_3(F_\ell)\ge2$. Ekkor

$$\begin{gather*} \frac{n}{3}\le v_3(n!) = v_3(F_kF_\ell) = v_3(F_k)+v_3(F_\ell) = x+y \\ k\ge 3^x+1, \quad \ell\ge 4\cdot 3^{y-1} \ge 3^y+3, \\ 2^{n(n-1)} > n^{n-1} > n! = F_k F_\ell \ge 1.6^{3^x} \cdot 1.6^{3^y+2} = 1.6^{3^x+3^y+2} \ge 1.6^{2\cdot 3^{\frac{x+y}2+2}} > 2^{3^{\frac{n}6+2}} \\ n(n-1) \ge 3^{\frac{n}6+2} \\ n \le 20. \end{gather*}$$

Ellenőrizhető, hogy $\displaystyle F_{90}>20!$, ezért $\displaystyle k,\ell\le 89$.

Az első Fibonacci számok prímfelbontásából elleőrizhetjük, hogy az $\displaystyle F_{13},F_{14},\ldots,F_{89}$ számok mindegyikének van $\displaystyle 20$-nál nagyobb prímosztója, ezért csak $\displaystyle k,\ell\le 12$ lehet. Akkor pedig $\displaystyle n!\le F_{12}^2<8!$, tehát $\displaystyle n\le 7$.

Az $\displaystyle F_7=13$, $\displaystyle F_9=34$, $\displaystyle F_{10}=55$, $\displaystyle F_{11}=89$ számoknak van $\displaystyle 7$-nél nagyobb prímosztója. A megmaradt Fibonacci számok: $\displaystyle 1,2,3,5,8,21,144$. Az ezekből készítető 21 kéttényezős szorzatot megvizsgálva látjuk, hogy $\displaystyle 1!=1\cdot1$, $\displaystyle 2!=2\cdot1$, $\displaystyle 3!=3\cdot2$, $\displaystyle 4!=8\cdot3$ és $\displaystyle 6!=144\cdot5$ két-két Fibonacci-szám szorzata; az $\displaystyle 5!=120$ és $\displaystyle 7!=5040$ nem áll elő két Fibonacci-szám szorzataként.

Tehát, az $\displaystyle n!$ akkor írható fel két Fibonacci-szám szorzataként, ha $\displaystyle n=1,2,3,4$ vagy $\displaystyle 6$.

Statisztika:

8 dolgozat érkezett.

7 pontot kapott: Beke Csongor, Füredi Erik Benjámin.

6 pontot kapott: Hegedűs Dániel, Várkonyi Zsombor, Weisz Máté.

4 pontot kapott: 1 versenyző.

0 pontot kapott: 2 versenyző.

A KöMaL 2020. februári matematika feladatai

8 dolgozat érkezett.
7 pontot kapott:	Beke Csongor, Füredi Erik Benjámin.
6 pontot kapott:	Hegedűs Dániel, Várkonyi Zsombor, Weisz Máté.
4 pontot kapott:	1 versenyző.
0 pontot kapott:	2 versenyző.

Már regisztráltál?
Új vendég vagy?