Problem B. 4130. (November 2008)

B. 4130. Consider a finite number of line segments on a line. Prove that if they are rearranged so that the midpoints of any two line segments are moved closer to each other then the total length of the union of the line segments will not increase.

(5 pont)

Deadline expired on December 15, 2008.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás: Az egyenest azonosítsuk a valós számegyenessel, az s szakasz átrendezés utáni képét jelölje s', a véges sok szakaszból álló S szakaszrendszer képe ennek megfelelően legyen S', t(S) pedig jelölje az S-beli szakaszok U(S) uniójának összhosszát. Elegendő az állítást olyan S szakaszrendszerek esetén bizonyítani, melyekre U(S) összefüggő. Valóban, ha $S=S_1\cup S_2\cup\ldots\cup S_k$ , ahol $U(S_1),U(S_2),\ldots,U(S_k)$ páronként diszjunkt szakaszok, akkor ennek alapján

$t(S)=t(S_1)+t(S_2)+\ldots+t(S_k)\ge t(S_1')+t(S_2')+\ldots+t(S_k')\ge t(S')$

már következik.

Legyen tehát U(S)=[a,b]. Azt kell igazolnunk, hogy t(S') $\le$ t([a,b])=b-a. U(S') legkisebb és legnagyobb elemét jelölje a', illetve b'. Mivel t(S') $\le$ t([a',b'])=b'-a', elegendő azt megmutatni, hogy b'-a' $\le$ b-a. Legyen s $\in$ S egy olyan szakasz, amelyre s' baloldali végpontja a', u $\in$ S pedig egy olyan szakasz, amelyre u' jobboldali végpontja b'. Ha s=u, akkor U(S')=s', $s\subseteq U(S)$ miatt az állítás nyilvánvaló. Feltesszük tehát, hogy s $\ne$ u, és legyen [c,d] a legrövidebb intervallum, amely tartaltalmazza az s és u szakaszok egyesítését. Ekkor a $\le$ c $\le$ d $\le$ b, vagyis elegendő azt megmutatni, hogy b'-a' $\le$ d-c. Jelölje s és u hosszát $\alpha$ , illetve $\beta$ , középpontjaik távolságát pedig $\varrho$ . Ekkor | $\alpha$ - $\beta$ | $\ge$ 2 $\varrho$ esetén d-c=max { $\alpha$ , $\beta$ }, | $\alpha$ - $\beta$ | $\le$ 2 $\varrho$ esetén pedig $d-c=\frac{\alpha+\beta}{2}+\varrho$ , vagyis f( $\varrho$ )=d-c a $\varrho$ mennyiség monoton növő függvénye. Ha tehát az s' és u' szakaszok középpontjának távolsága $\varrho$ '< $\varrho$ , akkor b'-a'=f( $\varrho$ ')<f( $\varrho$ )=d-c.

Statistics:

29 students sent a solution.

5 points: Blázsik Zoltán, Bodor Bertalan, Éles András, Frankl Nóra, Kispéter Tamás, Nagy 648 Donát, Weisz Ágoston.

4 points: Fonyó Dávid, Keresztfalvi Tibor, Strenner Péter, Varga 171 László.

3 points: 2 students.

2 points: 1 student.

1 point: 5 students.

0 point: 10 students.

Problems in Mathematics of KöMaL, November 2008

29 students sent a solution.
5 points:	Blázsik Zoltán, Bodor Bertalan, Éles András, Frankl Nóra, Kispéter Tamás, Nagy 648 Donát, Weisz Ágoston.
4 points:	Fonyó Dávid, Keresztfalvi Tibor, Strenner Péter, Varga 171 László.
3 points:	2 students.
2 points:	1 student.
1 point:	5 students.
0 point:	10 students.

Already signed up?
New to KöMaL?