Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?
A régi honlapot akarom!!! :-)

A B. 3975. feladat (2007. február)

B. 3975. Adott N és k pozitív egészekre megszámoltuk, hogy az N számot hányféleképpen lehet felírni a+b+c alakban, ahol 1\lea,b,c\lek, és az összeadandók sorrendje is számít. Kaphattunk-e eredményül 2007-et?

(5 pont)

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


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.


Statisztika:

66 dolgozat érkezett.
5 pontot kapott: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 pontot kapott:Dinh Hoangthanh Attila, Kőkuti András, Mezei Márk, Sárkány Lőrinc, Varga 171 László.
3 pontot kapott:1 versenyző.
2 pontot kapott:4 versenyző.
1 pontot kapott:2 versenyző.
0 pontot kapott:17 versenyző.
Nem versenyszerű:5 dolgozat.

A KöMaL 2007. februári matematika feladatai