A B. 4505. feladat (2013. január) |
B. 4505. Van egy p és egy q literes edényünk. A vízcsapnál bármelyik edényt színültig megtölthetjük vagy kiüríthetjük, bármelyik edényből a másik edényt teletölthetjük, illetve bármelyik edény teljes tartalmát átönthetjük a másik edénybe. Bizonyítsuk be, hogy ha p>q egymáshoz relatív prím pozitív egészek, s pedig olyan pozitív egész, amelyre sp, akkor elérhetjük azt, hogy az egyik edényben pontosan s liter víz legyen.
Javasolta: Holló Gábor
(5 pont)
A beküldési határidő 2013. február 11-én LEJÁRT.
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ő.
Statisztika:
82 dolgozat érkezett. 5 pontot kapott: 70 versenyző. 4 pontot kapott: 7 versenyző. 2 pontot kapott: 3 versenyző. 1 pontot kapott: 1 versenyző. 0 pontot kapott: 1 versenyző.
A KöMaL 2013. januári matematika feladatai