Feladat: 1.10.
Egy mindkét irányban végtelen hosszú folyosó
egyik oldalán végtelen sok szoba helyezkedik el. A
szobák egymást követő egész számokkal
vannak megszámozva, és minden szobában van egy
zongora. A szobákban véges sok zongorista él. (Egy
szobában akár több is.) Minden nap két
szomszédos szobában lakó zongorista (pl. a
k-adik
és a
k+1-edik) megelégeli a másik
gyakorlását, és a
k-1-edik illetve
k+2-edik
szobába költöznek át. Igazoljuk, hogy véges
számú nap elteltével abbahagyják a
költözködèst.
Megoldás: 1.10
Legyen a zongoristák száma
m, ekkor
m=2 esetén egy
nap után vége a költözködésnek. Ezután
nézzük a feladatot
m szerinti teljes indukcióval:
megmutatom, hogy akárhogy is van elrendezve az
m zongorista,
létezik olyan
f(m) szám, hogy
f(m) napon belül
vége a költözködésnek.
m=2-re igaz
(
f(2)=1), s tegyük fel, hogy
m=1,2,...,n-re is igaz, ekkor
megmutatom,
hogy
n+1-re is:
Legyen egy
A állapotban a zongoristák számai
a1
≤
a2
≤...≤
an+1
és rendeljük minden
állapothoz a
G állapotfüggvényt úgy, hogy
G(A)=(
a2
-
a1
)2
+(
a3
-
a1
)2
+...+(
an+1
-
a1
)2
Ha az
A-ból következik a
B állapot, ahol
ai
+1=
aj
számokból lesznek az
ai
-1 és
aj
+1 (
i≠1) számok,
akkor
G(B)=(
a2
-
a1
)2
+(
a3
-
a1
)2
+...+(
ai
-
a1
-1
)2
+...+(
aj
-
a1
+1
)2
+...+(
an+1
-
a1
)2
=G(A)+2-2(
ai
-
a1
)+2(
aj
-
a1
)=G(A)+2+2(
aj
-
ai
)≥G(A)+2
ha
i=1 akkor
G(B)=(
a2
-
a1
+1
)2
+(
a3
-
a1
+1
)2
+...+(
aj
-
a1
+2
)2
+...+(
an+1
-
a1
+1
)2
>G(A)+n
vagyis
G szigorúan monoton nő és a végtelenbe
tart. S ekkor a két legszélső zongorista
távolsága akármekkora lehet, ugyanis tegyük fel
indirekt módon, hogy akárhány nap is telik el, a
távolság legfeljebb
k, ám ez azt jelentené, hogy
G(A) tetszőleges
A állapot esetèn legfeljebb
nk2
, de ez ellentmond annak, hogy
G a végtelenbe tart.
Tehát ezek alapján, mivel G minden nap 1-gyel nő,
így
C=(2fn(n)+2n
)2
n
napon belül a két legszélső zongorista
távolsága legalább
2nf(n)+2n, s ekkor lesz olyan
l
pozitív egész szám, hogy
al+1
-
al
≥2f(n)+2.
S ekkor nézzük külön az
a1
,
a2
,...
al
és
al+1
,
al+2
,...,
an+1
zongoristákat, ekkor
f(l),f(n+1-l)≤f(n) miatt mindkét csoportban
f(n) nap
alatt vége a költözködésnek, s
f(n) nap
alatt
al
legfeljebb
f(n)-et nőhetett, míg
al+1
legfeljebb
f(n)-et csökkenhetett, tehát
al+1
-
al
≥2f(n)+2 miatt nem kerülhettek egymás
mellé. Tehát a költözésnek
C+2f(n) napon
belül vége,
így
f(n+1)≤C+2f(n)=(f(n)+2
)2
n2
+2f(n)
Tehát létezik az
f(n+1) szám is, s ezzel a feladat
állítása be van bizonyítva.