Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem B. 3975. (February 2007)

B. 3975. N and k are positive integers. We have counted the different ways of expressing N in the form a+b+c, where 1\lea,b,c\lek, and the order of the terms also matters. Is it possible that we got 2007?

(5 pont)

Deadline expired on March 19, 2007.


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

Megoldás: Jelölje a szóban forgó előállítások számát S(N,k), keressünk erre képletet N és k függvényében. Előbb azonban oldjunk meg egy egyszerűbb problémát. Pozitív egész M,k esetén jelölje T(M,k) azon M=b+c felírások számát, ahol b és c is 1 és k közé eső egész számok. Ha M=1 vagy M\ge2k+1, akkor T(M,k)=0, egyébként pedig két esetet érdemes megkülönböztetni. Ha 2\leM\lek+1, akkor tetszőleges 1\leb\leM-1 választás mellett 1\leM-b\lek teljesül, vagyis T(M,k)=M-1. Ha viszont k+2\leM\le2k, akkor az M-k\leb\lek feltétel szükséges és elegendő ahhoz, hogy M-b értéke is 1 és k közé essen, ekkor tehát T(M,k)=k-(M-k)+1=2k+1-M. Az eredeti kérdésre visszatérve, ha N\le2 vagy N\ge3k+1, akkor S(N,k)=0. Most tehát 3 esetet érdemes megkülönböztetnünk N és k viszonyától függően.

Az első esetben 3\leN\lek+2, ekkor a értéke tetszőleges 1 és N-2 közötti szám lehet. Ha a értékét így rögzítjük, akkor az M=N-a számra 2\leM\leN-1\lek+1 teljesül, a b,c számokat tehát T(N-a,k)=N-a-1 féleképpen választhatjuk a-hoz a feltételeknek megfelelően. Ezért ebben az esetben

S(N,k)=\sum_{a=1}^{N-2}(N-a-1)=\frac{(N-2)(N-1)}{2}.

Vizsgáljuk másodiknak azt az esetet, amikor 2k+2\leN\le3k, ekkor szükségképpen a\geN-2k. Ha a értékére N-2k\lea\lek teljesül, akkor k+2\leN-k\leN-a\le2k, ezért ezen a mellé b és c értékét T(N-a,k)=2k+1+a-N féleképpen választhatjuk meg, vagyis

S(N,k)=\sum_{a=N-2k}^k(2k+1+a-N)=\frac{(3k+1-N)(3k+2-N)}{2}.

A harmadik eset, amikor is k+3\leN\le2k+1, valamivel bonyolultabb. Ha a értékét 1 és N-k-2 között választjuk, akkor k+2\leN-a\le2k, ha pedig N-k+1 és (az annál nem kisebb) k között, akkor 3\leN-k\leN-a\lek+1 lesz a helyzet. Így ebben az esetben

S(N,k)=\sum_{a=1}^{N-k-2}(2k+1+a-N)+\sum_{a=N-k-1}^{k}(N-a-1)=

=\frac{(N-k-2)(3k+1-N)}{2}+\frac{(2k+2-N)(N-1)}{2}=
\frac{3k^2+1-\ell^2}{4},

ahol az \ell=2N-(3k+3) számra -k+3\le\ell\lek-1 teljesül, vagyis \ell2<k2.

Ezek után a kérdést már viszonylag könnyen megválaszolhatjuk. Mivel a 2007 prímtényezős felbontása 2007=32.223, az első két esetben a 2.32.223 számot kellene felírnunk két szomszédos szám szorzataként, ami nyilván lehetetlen, hiszen valamelyiknek oszthatónak kellene lennie 223-mal, akkor viszont mindkét tényező legalább 222 lenne, a szorzatuk túl nagy lenne. A harmadik esetben a 4.2007=3k2+1-\ell2 feltételnek kell teljesülni, ahol \ell2<k2. Innen 2k2<8028\le3k2+1 adódik, vagyis k értéke 52 és 63 közé kell, hogy essen. A k=52 esetet könnyen kizárhatjuk: k nem lehet 4-gyel osztható, mert akkor \ell-nek páratlan számnak kellene lennie, akkor viszont 3k2+1-\ell2 osztható lenne 8-cal. Az első szóba jövő érték tehát k=53, ekkor \ell2-re 400 adódik, vagyis 2N-(3.53+3)=\pm20. Ha az ebből kapott N=71 és N=91 értékeket megviszgáljuk, akkor látjuk, hogy azok k+3 és 2k+1 közé esnek, vagyis a megfelelő képlet szerint S(71,53)=S(91,53)=2007. A feladat kérdésére tehát igenlő a válasz.


Statistics:

66 students sent a solution.
5 points:Almási 270 Gábor András, Bálint Dániel, Balogh 147 Ádám, Blázsik Zoltán, Bodor Bertalan, Cseh Ágnes, Cséke Balázs, Dékány Tamás, Fonyó Dávid, Honner Balázs, Horváth 385 Vanda, Konkoly Csaba, Korom-Vellás Judit, Kunovszki Péter, Mester Anita, Mészáros András, Peregi Tamás, Róka Péter, Somogyi Ákos, Sümegi Károly, Szabó 124 Zsolt, Szalai Zsófia, Szalóki Dávid, Szigetvári Áron, Szőke Nóra, Szűcs Gergely, Tossenberger Anna, Tóth 666 László Márton, Tóth 796 Balázs, Török Lajos, Véges Márton, Wolosz János.
4 points:Dinh Hoangthanh Attila, Kőkuti András, Mezei Márk, Sárkány Lőrinc, Varga 171 László.
3 points:1 student.
2 points:4 students.
1 point:2 students.
0 point:17 students.
Unfair, not evaluated:5 solutionss.

Problems in Mathematics of KöMaL, February 2007