KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

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 11 February 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.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley