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 $\le$ a,b,c $\le$ k, é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 $\ge$ 2k+1, akkor T(M,k)=0, egyébként pedig két esetet érdemes megkülönböztetni. Ha 2 $\le$ M $\le$ k+1, akkor tetszőleges 1 $\le$ b $\le$ M-1 választás mellett 1 $\le$ M-b $\le$ k teljesül, vagyis T(M,k)=M-1. Ha viszont k+2 $\le$ M $\le$ 2k, akkor az M-k $\le$ b $\le$ k 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 $\le$ 2 vagy N $\ge$ 3k+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 $\le$ N $\le$ k+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 $\le$ M $\le$ N-1 $\le$ k+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 $\le$ N $\le$ 3k, ekkor szükségképpen a $\ge$ N-2k. Ha a értékére N-2k $\le$ a $\le$ k teljesül, akkor k+2 $\le$ N-k $\le$ N-a $\le$ 2k, 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 $\le$ N $\le$ 2k+1, valamivel bonyolultabb. Ha a értékét 1 és N-k-2 között választjuk, akkor k+2 $\le$ N-a $\le$ 2k, ha pedig N-k+1 és (az annál nem kisebb) k között, akkor 3 $\le$ N-k $\le$ N-a $\le$ k+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$ $\le$ k-1 teljesül, vagyis $\ell$ ²<k².

Ezek után a kérdést már viszonylag könnyen megválaszolhatjuk. Mivel a 2007 prímtényezős felbontása 2007=3²^.223, az első két esetben a 2^.3²^.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=3k²+1- $\ell$ ² feltételnek kell teljesülni, ahol $\ell$ ²<k². Innen 2k²<8028 $\le$ 3k²+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 3k²+1- $\ell$ ² osztható lenne 8-cal. Az első szóba jövő érték tehát k=53, ekkor $\ell$ ²-re 400 adódik, vagyis 2N-(3^.53+3)= $\pm$ 20. 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

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.

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