Feladat: F.2629 Korcsoport: 18- Nehézségi fok: átlagos
Megoldó(k):  Alpár A. ,  Beke T. ,  Benczúr A. ,  Bereczky Á. ,  Binder Zsuzsanna ,  Cynolter G. ,  Eckert B. ,  Gács A. ,  Hajdú G. ,  Hajnal Z. ,  Horváth 969 J. ,  Jalsovszky P. ,  Kelemen Eszter ,  Keleti T. ,  Kerey P. ,  Madas P. ,  Majoros L. ,  Pál G. ,  Rimányi R. ,  Szabó 484 P. ,  Szabó 668 T. ,  Szalay Gy. ,  Szegedi Nóra ,  Tasnádi T. ,  Tóth 178 G. 
Füzet: 1987/november, 370. oldal  PDF  |  MathML 
Témakör(ök): Számelrendezések, Indirekt bizonyítási mód, Feladat
Hivatkozás(ok):Feladatok: 1987/március: F.2629

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

I. megoldás. Az 1,2,...,120 számok mindegyikét ötször írhatjuk be, tehát e számok összesen 600 mezőt fednek le. Másrészt minden olyan mezőt e számokkal kell lefednünk, amelyekre soruk és oszlopuk sorszámát összeszorozva 120-nál nem nagyobb számot kapunk. Az első sorban 120 ilyen mező van, a másodikban 1202=60, a harmadikban 1203,..., az i-edik sorban [120i] olyan mező van, amely megfelel (ha az oszlop száma m, akkor im≦120-nak kell teljesülnie). Az összes ilyen mezők száma tehát ∑i=1120[120i]=602.
Ezek szerint több mezőt kell 120-nál nem nagyobb számokkal lefednünk, mint ahány szám a lefedésre rendelkezésünkre áll, így a táblázat nem tölthető ki a feladat kívánalmainak megfelelően. (Már egy 120×120-as táblázat sem tölthető ki az 1-től 2880-ig terjedő egészekkel.)

 

II. megoldás. Általánosabban azt mutatjuk meg, hogy ha n≧ek+1, akkor egy n×n-es táblázat nem tölthető ki az 1,2,...,n2k számokkal az előírt módon úgy, hogy minden számot k-szor használunk fel. (Feltesszük, hogy k osztója n-nek.)
Megint felhasználjuk, hogy az első n szám valamelyikével kell lefednünk minden olyan mezőt, amelyre sorának és oszlopának sorszámát összeszorozva n-nél nem nagyobb számot kapunk. Ilyen mező az első sorban n darab, a másodikban [n2],..., az i-edik sorban [ni] darab van. Összesen tehát ∑i=1n[ni] ilyen mezőt kell lefednünk az n-nél nem nagyobb számokkal.
Mivel [x]>x-1, tehát ∑i=1n[ni]>∑i=1n(ni-1)=n∑i=1n(1i)-n. Ismeretes, hogy ∑i=1n1i>lnn, vagyis azoknak a mezőknek a száma, amelyeket az 1, 2, ..., n számok valamelyikével kell lefednünk, nagyobb, mint n(lnn-1). Másrészt e számok mindegyikét pontosan k-szor használhatjuk, így k⋅n mezőt fedhetünk le velük. Ahhoz, hogy a kitöltés megvalósítható legyen, szükséges (de nem elégséges!) tehát, hogy kn>n(ln n-1), azaz k+1>ln n, n<ek+1 teljesüljön. n≧ek+1 esetén tehát a kitöltés nem valósítható meg. Feladatunkban k=5, ek+1=403,42...<1000=n, a kitöltés tehát nem létezik.