Feladat: N.86 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Braun Gábor ,  Frenkel Péter ,  Gyarmati Katalin ,  Pap Gyula ,  Terék Zsolt 
Füzet: 1996/október, 421 - 422. oldal  PDF file
Témakör(ök): Prímszámok, Maradékos osztás, kongruenciák, Nehéz feladat
Hivatkozás(ok):Feladatok: 1995/december: N.86

Van egy p és egy q perces homokóránk (p és q relatív prím pozitív egészek), ezekkel egy n perces időtartamot szeretnénk kimérni. Kezdetben mindkét óra alapállapotban van, vagyis az összes homok az alsó tégelyekben található. A mérés kezdetekor, illetve amikor valamelyik óra lejár, megfordíthatjuk bármelyik vagy mindkét homokórát. Bizonyítsuk be, hogy ha npq2, akkor a mérés lehetséges.

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. Mivel p és q relatív prímek, a 0, p, 2p, ..., (q-1)p számok teljes maradékrendszert alkotnak modulo q, ezért létezik pontosan egy olyan 0kq-1 egész szám, amelyre kpn(modq). Ha knp is teljesül, akkor már készen is vagyunk; a p perces homokórával lemérünk k-szor p percet, majd a másik órával a hiányzó néhányszor q percet. Ellenkező esetben ez a módszer nem működik, ezért egy másik módszert is mutatunk.
Tegyük fel először, hogy k páros, k=2m. Mérjünk le a p perces órával mp percet, de közben indítsuk el a q perces órát is, és amikor lejár, mindig fordítsuk meg. Az mp perc letével a q perces óra x perce jár, ahol persze xmp(modq). Fordítsuk most meg a q perces órát. Feltételezve, hogy a lepergett homok a fordítás után ugyanannyi, tehát x perc alatt pereg vissza, a q perces óra az (mp+x)-edik perc végén jár le. Mivel mp+xkpn(modq), és mp+xmp+qq-12p+q<n+q, így vagy éppen n percet mértünk le, vagy még néhányszor q perc hiányzik, amit lemérhetünk az éppen lejárt q perces órával.
Vizsgáljuk most azt az esetet, amikor k páratlan, k=2m+1. A p perces órával mérjünk le (m+1)p percet. A q perces órát a p-edik perc végén indítsuk el, amikor lejár, mindig fordítsuk meg. Az (m+1)p perc elteltével a q perces órában x percnyi homok pergett le, ahol xmp(modq). Most fordítsuk meg a q perces órát, amely így az (m+1)p+x-edik perc végén jár le. Mivel (m+1)p+xkpn(modq) és (m+1)p+x<q2p+qn+q, ezúttal is kész vagyunk.
 Több dolgozat alapján 

 
II. megoldás. Legyen -q2<kq2 az az egész szám, amelyre kp1(modq). (Ilyen egyértelműen létezik, mert (p,q)=1.) Indítsuk el mindkét homokórát, és amikor valamelyik lejár, fordítsuk meg. Vizsgáljuk meg, mi történik |k|p perc elteltével. Mivel |k|p±1(modq), a p perces óra éppen lejárt, a q perces pedig vagy 1 perce jár, vagy 1 perce van még hátra. Az előbbi esetben fordítsuk meg mindkét, az utóbbi esetben csak a p perces órát. Ilyen módon elértük, hogy legfeljebb pq2 perc után a p perces órában az összes homok a felső tégelyben van, a q perces óra pedig 1 perc múlva jár le.
Ettől kezdve minden egyes perc leteltét mérhetjük: amikor a q perces óra lejár, addigra a p percesből éppen 1 percnyi homok pereg le. Mindkét órát megfordítva, az előbbi állapot fordítottja áll elő: a q perces órában minden homok a felső tégelyben van, a p perces pedig 1 perc múlva jár le.
 Frenkel Péter (Fazekas M. Főv. Gyak. Gimn., III. o.t.)