កំណែលំហាត់សិស្សពូកែទូទាំងប្រទេស២០០៩ (14)

អនុគមន៍ $f(x;y)$ មួយផ្ទៀងផ្ទាត់លក្ខខណ្ឌទាំងបីខាងក្រោមចំពោះគ្រប់ចំនួនគត់មិនអវិជ្ជមាន $x$ និង $y$ :

$f(0;y)=1+y$
$f(x+1;0)=f(x;1)$
$f(x+1;y+1) =f(x;f(x+1;y))$

ក. គណនា $f(1;n),f(2;n)$ និង $f(3;n)$ ជាអនុគមន៍នៃ $n$
ខ. គណនា $f(4;2009)$

សំនួរសិស្សពូកែអន្តរជាតិ 1981
សំនួរសិស្សពូកែកម្ពុជា 2009

ចម្លើយ

គណនា $f(1,n)$

តើ $f(1,n)$ ជាចំនួនគត់ឬទេ?
យើងមាន
$f(0;n)=1+n (*)$
$f(1;0)=f(0;1)=2$
$f(1;n+1)=f(0;f(1;n) ) (**)$

តាម (*) & (**) យើងទាញបាន $f(1;n+1)$ ជាចំនួនគត់ បើ $f(1;n)$ ជាចំនួនគត់។ ដោយ $f(1,1)=f(0;f(1;0) )=2$ ជាចំនួនគត់ នោះ $f(1;n)$ ជាចំនួនគត់។
តាម (*) & (**) យើងទាញបាន $f(1;n+1)=f(0;f(1;n) )=1+f(1;n)$ ។ ដូច្នេះ
$f(1;2)=1+f(1;1)=3;$
$f(1;3)=1+f(1;2)=4;$
$\dotsi$
$f(1;n)=n+1$

គណនា $f(2;n)$

$f(2;n+1)=f(1;f(2;n))$

យើងទាញបាន $f(2;n+1)$ គត់ បើ $f(2;n)$ គត់។ ដោយ $f(2;0)=f(1;1)=2;f(2;1)=f(1;f(2;0) )=f(1;2)=3$ ជាចំនួនគត់ នោះ $f(2;n)$ ជាចំនួនគត់។ ដូច្នេះ

$f(2;n+1)=f(1;f(2;n) )=1+f(2;n)$
$\implies f(2;1)=1+f(2;0)=3;$
$f(2;2)=1+f(2;1)=4;$
$\dotsi$
$f(2;n)=n+2$

គណនា $f(3;n)$

$f(3;n+1)=f(2;f(3;n) )=f(3;n)+2$
$f(3;0)=f(2;1)=3$
$f(3;1)=f(3;0)+2=3+2$
$f(3;2)=f(3;1)+2=3+2.2$
….
$f(3;n)=f(3;n-1)+2=3+2n$

គណនា $f(4;2009)$

$f(4;n+1)=f(3;f(4;n))=3+2f(4;n)$
$f(4;0)=f(3;1)=5$
—————————————————
$f(4;1)=3+2f(4;0)$ ……….. $\times 2^{2008}$
$f(4;2)=3+2f(4;1)$ ……….. $\times 2^{2007}$
$f(4;3)=3+2f(4;2)$ ……….. $\times 2^{2006}$
…
$f(4;2007)=3+2f(4;2006)$ ……….. $\times 2^2$
$f(4;2008)=3+2f(4;2007)$ ……….. $\times 2$
$f(4;2009)=3+2f(4;2008)$
—————————————————-
$\implies f(4;2009)=3+3.2+3.2^2+\dotsi+3.2^{2007}+3.2^{2008}+2^{2009} f(4;0)=3\frac{2^{2009}-1}{2-1}+2^{2009}.5=8.2^{2009}-3=2^{2012}-3$