Problem B. 4505. (January 2013)
B. 4505. We have two containers with volumes of p litres and of q litres. It is allowed to fill up completely or empty either container at a tap, to fill up either container completely from the other one, and to pour the entire content of one into the other. Prove that if p>q are relatively prime positive integers, and s is a positive integer such that sp, then it is possible to achieve that one container have exactly s litres of water in it.
Suggested by G. Holló, Budapest
(5 pont)
Deadline expired on February 11, 2013.
Sorry, the solution is available only in Hungarian. Google translation
Megoldási ötlet: Állítsuk elő q többszöröseit modulo p.
Megoldás. Jelöljük (x,y)-nal azt az állapotot, amikor a p literes edényben x, a q literesben y liter víz van. Egy tetszőleges x nemnegatív egészre jelölje xmod p az x osztási maradékát p-vel osztva.
A feladat megoldása a következő segédállításból következik:
Segédállítás. Ha valamilyen x egész számra az (x,0) állapot elérhető, akkor az ((x+q)mod p,0) állapot is elérhető.
Bizonyítás. Induljunk ki az (x,0) állapotból. Töltsük meg a q literes edényt, és tartalmát öntsük át a p literes edénybe. Ha közben a p literes edény megtelik (ami p-x liter áttöltése után következik be), akkor a p literes edényt ürítsük ki (azaz öntsünk ki belőle p litert). Ha x+q<p, akkor a következő állapotokat állítjuk elő:
Ha pedig x+qp, akkor a második edényből teletöltjük az első edényt, ezután az első edényt kiürítjük, és végül a második edényben levő maradékot öntjük át az első edénybe:
Ezzel a Segédállítást igazoltuk.
Ezek után a feladat megoldása:
- A (0,0) és a (p,0) állapot triviálisan elérhető.
- Ha 0<s<p, akkor a Segédállítást többször alkalmazva, a (0,0), (q,0), (2q mod p,0), (3q mod p,0), állapotok mind elérhetők. Mivel p és q relatív prímek, ezek között szerepel az (s,0) állapot is, mert a q többszörösei minden maradékot kiadnak p-vel osztva. Tehát, az (s,0) állapot elérhető.
Statistics:
82 students sent a solution. 5 points: 70 students. 4 points: 7 students. 2 points: 3 students. 1 point: 1 student. 0 point: 1 student.
Problems in Mathematics of KöMaL, January 2013