KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

ELTE

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

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 points)

Deadline expired on 11 February 2013.


Google Translation (Sorry, the solution is published in Hungarian only.)

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 on problem B. 4505.
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

  • Támogatóink:   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