Feladat: F.2303 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Alberti G. ,  Breiner L. ,  Böröczky K. ,  Böröczky Lilla ,  Csere K. ,  Danyi P. ,  Ditrich P. ,  Dósa Gy. ,  Erdős L. ,  Feledi Gy. ,  Genczler Judit ,  Gyöngyösi P. ,  Halász P. ,  Hetyei G. ,  Holbok I. ,  Kapos L. ,  Károlyi Gy. ,  Kató G. ,  Katona Gy. ,  Megyesi G. ,  Mikó Teréz ,  Pöltl J. T. ,  Simonyi G. ,  Steiner M. ,  Szabó E. ,  Szabó T. ,  Szalai J. ,  Szállási Z. ,  Törőcsik J. 
Füzet: 1981/november, 130 - 131. oldal  PDF file
Témakör(ök): Részhalmazok, Oszthatóság, Feladat
Hivatkozás(ok):Feladatok: 1981/március: F.2303

Adott tetszés szerinti 10 pozitív egész szám úgy, hogy egyiknek sincs 20-nál nagyobb prímosztója. Mutassuk meg, hogy kiválasztható a számok közül néhány, melyek szorzata teljes négyzet.

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.

Ha a megadott számok között van két négyzetszám, akkor persze ezek szorzata is teljes négyzet. Így feltehetjük, hogy nem ez a helyzet, vagyis számaink közül kiválasztható kilenc, melyek egyike sem négyzetszám, jelöljük ezek halmazát H-val.
H-nak minden nem üres A részhalmazára tekintsük az A-beli számok szorzatát. Mivel H kilenc elemű, azért a kapott szorzatok száma 29-1=511. Egy ilyen szorzat akkor és csak akkor teljes négyzet, ha a prímtényezős felbontásában minden prím páros kitevőn szerepel. Elegendő tehát prímtényezős felbontásaikban a kitevők paritását vizsgálni.
A feladatban szereplő számoknak ‐ és így szorzataiknak is ‐ mindössze 8 különböző prímtényezője lehet: 2, 3, 5, 7, 11, 13, 17 és 19. Így a szorzatok a kitevők paritása szempontjából 28=256 különböző osztályba eshetnek attól függően, hogy a 2, a 3 stb., a 19 kitevője páros-e vagy páratlan. Feladatunk éppen az, hogy megmutassuk: az előbbi szorzatok valamelyike abba az osztályba esik, melyben minden kitevő páros.
Első pillanatban nem látszik, hogy ennek miért kellene így lennie. Annyit tudunk, hogy a szorzatok száma 511, és ez nagyobb a lehetséges osztályok számánál, 256-nál. Tehát van két szorzat, mondjuk az A és a B részhalmazok elemeinek szorzata, melyek ugyanabba az osztályba esnek. Ám e két szorzat szorzata, vagyis A elemeinek és B elemeinek szorzata négyzetszám, hiszen itt minden prím kitevője vagy két páratlan, vagy két páros szám összege, tehát biztosan páros. Ha A-nak és B-nek nincs közös eleme, azaz AB=, akkor készen vagyunk: AB elemeinek szorzata négyzetszám.
Ha viszont AB nem üres, akkor a "szorzatok szorzatában'' ennek a közös résznek minden eleme pontosan kétszer szerepel. Hagyjuk el ezeket a kétszer szereplő számokat! A megmaradó számok szorzata továbbra is négyzetszám marad, hiszen minden prímtényező kitevőjét páros számmal csökkentettük (ha csökkentettük egyáltalán), s így az páros maradt. A "szorzatok szorzatából'' nem hagyhattuk el az összes tényezőt, hiszen A és B különböző részhalmazai voltak H-nak, így, van olyan elem, amely vagy csak A-ban vagy csak B-ben van. Végül nem maradhatott egyetlen tényező, mert akkor annak négyzetszámnak kellene lennie, márpedig H elemei között nincs négyzetszám.
Ezzel igazoltuk, hogy számaink közül mindig kiválasztható néhány, de legalább kettő, melyek szorzata teljes négyzet.