A B. 5469. feladat (2025. május)

B. 5469. Bergengóciában három város van, $\displaystyle A$, $\displaystyle B$ és $\displaystyle C$, ezekben összesen $\displaystyle 2025$ ember lakik. Az idei évtől kezdve minden év végén $\displaystyle A$ lakosságának a fele átköltözik $\displaystyle B$-be, $\displaystyle B$-ének a harmada $\displaystyle C$-be, és $\displaystyle C$-ének a negyede $\displaystyle A$-ba (ha az átköltözők száma bármely esetben nem lenne egész, akkor felfelé van kerekítve). Igazoljuk, hogy néhány év eltelte után egyik város lélekszáma sem fog változni.

Javasolta: Váli Benedek (Budapest)

(6 pont)

A beküldési határidő 2025. június 10-én LEJÁRT.

Megoldás. Jelölje $\displaystyle A$, $\displaystyle B$, $\displaystyle C$ városok lakosságát az $\displaystyle i$-edik évben rendre $\displaystyle a_i$, $\displaystyle b_i$, $\displaystyle c_i$. A feltételek alapján

$$\begin{align*} a_{i+1} &= \left \lfloor \frac{a_i}{2}\right\rfloor+\left \lceil \frac{c_i}{4}\right\rceil, \\ b_{i+1} &= \left \lfloor \frac{2b_i}{3}\right\rfloor+\left \lceil \frac{a_i}{2}\right\rceil, \\ c_{i+1} &= \left \lfloor \frac{3c_i}{4}\right\rfloor+\left \lceil \frac{b_i}{3}\right\rceil, \end{align*}$$

ahol $\displaystyle \lfloor t\rfloor$, illetve $\displaystyle \lceil t\rceil$ a $\displaystyle t$ szám alsó, illetve felső egészrészét jelöli.

Nézzük meg, milyen $\displaystyle a,b,c$ hármasra kaphatunk egyensúlyi állapotot (ami alatt azt értjük, hogy már nem változik), ha az egészrészeket elhagyjuk, vagyis oldjuk meg az

$$\begin{align*} a &= \frac{a}{2}+\frac{c}{4}, \\ b &= \frac{2b}{3}+ \frac{a}{2}, \\ c &= \frac{3c}{4}+ \frac{b}{3} \end{align*}$$

egyenletrendszert. Ennek megoldása $\displaystyle a=2k,b=3k,c=4k$ valamely $\displaystyle k$ mellett. A feladatban $\displaystyle a+b+c=2025$, ami azt jelenti, hogy $\displaystyle k=2025/9=225$ mellett éppen egyensúlyi állapotot kapunk, ekkor ugyanis a rekurzióban szereplő törtek mind egészek. Azt fogjuk igazolni, hogy minden állapotból eljutunk az $\displaystyle a=2k=450,b=3k=675,c=4k=900$ állapotba.

Jelölje $\displaystyle x_i,y_i,z_i$ az ettől való eltérést az $\displaystyle i$-edik évben, vagyis legyen

$\displaystyle a_i=2k+x_i,\quad b_i=3k+y_i,\quad c_i=4k+z_i.$

Világos, hogy $\displaystyle x_i+y_i+z_i=0$. A rekurzió alapján az eltérésekre a következőket kapjuk:

$$\begin{align*} x_{i+1} &= \left \lfloor \frac{x_i}{2}\right\rfloor+\left \lceil \frac{z_i}{4}\right\rceil, \\ y_{i+1} &= \left \lfloor \frac{2y_i}{3}\right\rfloor+\left \lceil \frac{x_i}{2}\right\rceil, \\ z_{i+1} &= \left \lfloor \frac{3z_i}{4}\right\rfloor+\left \lceil \frac{y_i}{3}\right\rceil. \end{align*}$$

Ebből rögtön leolvasható, hogy $\displaystyle |x_i|+|y_i|+|z_i|$ értéke monoton csökken. A háromszög-egyenlőtlenség alapján ugyanis

$\displaystyle |x_{i+1}| \leq \left|\left \lfloor \frac{x_i}{2}\right\rfloor\right|+\left|\left \lceil \frac{z_i}{4}\right\rceil\right|, $

$\displaystyle (1)$

$\displaystyle |y_{i+1}| \leq \left|\left \lfloor \frac{2y_i}{3}\right\rfloor \right|+\left|\left \lceil \frac{x_i}{2}\right\rceil\right|, $

$\displaystyle (2) $

$\displaystyle |z_{i+1}| \leq \left|\left \lfloor \frac{3z_i}{4}\right\rfloor\right|+\left|\left \lceil \frac{y_i}{3}\right\rceil\right|, $

$\displaystyle (3)$

ezeket összeadva éppen az $\displaystyle |x_{i+1}|+|y_{i+1}|+|z_{i+1}|\leq |x_i|+|y_i|+|z_i|$ egyenlőtlenséget kapjuk, hiszen

$$\begin{align*} |x_{i}| &= \left|\left \lfloor \frac{x_i}{2}\right\rfloor\right|+\left|\left \lceil \frac{x_i}{2}\right\rceil\right|, \\ |y_{i}| &= \left|\left \lfloor \frac{2y_i}{3}\right\rfloor \right|+\left|\left \lceil \frac{y_i}{3}\right\rceil\right|, \\ |z_{i}| &= \left|\left \lfloor \frac{3z_i}{4}\right\rfloor\right|+\left|\left \lceil \frac{z_i}{4}\right\rceil\right|. \end{align*}$$

Mivel $\displaystyle |x_i|+|y_i|+|z_i|$ nemnegatív egész szám, ezért véges sok év után az értéke már nem változik tovább. A továbbiakban tegyük fel, hogy már elértük ezt az állapotot, és az eltérések abszolút értékes összege tovább már nem csökken.

Ekkor $\displaystyle x_i<0<z_i$ nem lehetséges, hiszen akkor az (1) háromszög-egyenlőtlenség szigorúan teljesülne, és így az eltérések összege csökkenne. Ugyanígy, (2) és (3) alapján sem $\displaystyle y_i<0<x_i$, sem $\displaystyle z_i<0<y_i$ nem lehetséges.

De ez azt is jelenti, hogy $\displaystyle x_i,y_i,z_i$ valamelyike biztosan 0, hiszen különben az $\displaystyle x_i,z_i,y_i(,x_i)$ ciklikus sorrendben negatív értéket pozitív követne valahol (ugyanis $\displaystyle x_i+y_i+z_i=0$).

Tegyük fel indirekten, hogy mire $\displaystyle |x_i|+|y_i|+|z_i|$ állandóvá vált, nem értük el az $\displaystyle x_i=y_i=z_i=0$ egyensúlyi állapotot. Ekkor innentől kezdve $\displaystyle x_i,y_i,z_i$ között mindig egy pozitív, egy negatív és egy 0 lesz. Korábbi észrevételeink alapján három eset lehetséges, de mindhárom esetben ellentmondást kapunk az alábbiak szerint, a rekurziót alkalmazva:

$\displaystyle x_i<0=z_i<y_i \implies x_{i+1}<0<z_{i+1}, $

$\displaystyle y_i<0=x_i<z_i \implies y_{i+1}<0<x_{i+1}, $

$\displaystyle z_i<0=y_i<x_i \implies z_{i+1}<0<y_{i+1}, $

vagyis a következő évben olyan hármast kapnánk, ami nem lehetséges.

Ellentmondásra jutottunk, így csak az lehet, hogy biztosan elérjük az $\displaystyle x_i=y_i=z_i=0$ állapotot, vagyis egy idő után $\displaystyle A$-nak mindig 450, B-nek mindig 675, $\displaystyle C$-nek pedig 900 lakosa lesz.

Statisztika:

19 dolgozat érkezett.

6 pontot kapott: Ali Richárd, Holló Martin, Sárdinecz Dóra, Wágner Márton.

4 pontot kapott: 3 versenyző.

3 pontot kapott: 2 versenyző.

2 pontot kapott: 3 versenyző.

1 pontot kapott: 2 versenyző.

0 pontot kapott: 1 versenyző.

Nem versenyszerű: 3 dolgozat.

A KöMaL 2025. májusi matematika feladatai

19 dolgozat érkezett.
6 pontot kapott:	Ali Richárd, Holló Martin, Sárdinecz Dóra, Wágner Márton.
4 pontot kapott:	3 versenyző.
3 pontot kapott:	2 versenyző.
2 pontot kapott:	3 versenyző.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	1 versenyző.
Nem versenyszerű:	3 dolgozat.

Már regisztráltál?
Új vendég vagy?