Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

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 s\lep, 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ő:


(x,0) \longrightarrow (x,q) \longrightarrow (x+q,0) = \big((x+q)\mod
p,0\big);

Ha pedig x+q\gep, 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:


(x,0) \longrightarrow (x,q) \longrightarrow (p,x+q-p)
\longrightarrow (0,x+q-p)
\longrightarrow (x+q-p,0) = \big((x+q)\mod p,0\big).

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), \ldots á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