Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?
A régi honlapot akarom!!! :-)

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


(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ő.


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