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  |  MathML 
Témakör(ök): Prímszámok, Maradékos osztás, kongruenciák, Nehéz feladat
Hivatkozás(ok):Feladatok: 1995/december: N.86

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 0≤k≤q-1 egész szám, amelyre kp≡n(modq). Ha k≤np 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 x≡mp(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+x≡kp≡n(modq), és mp+x≤mp+q≤q-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 x≡mp(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+x≡kp≡n(modq) és (m+1)p+x<q2p+q≤n+q, ezúttal is kész vagyunk.
 Több dolgozat alapján 

 
II. megoldás. Legyen -q2<k≤q2 az az egész szám, amelyre kp≡1(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.)