Kezdőlap


Feladat:	Pontversenyen kívüli P.82	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Füredi Zoltán , Katona Endre , Less György , Martoni Viktor , Stachó Balázs
Füzet:	1971/október, 72 - 73. oldal		PDF \| MathML
Témakör(ök):	Kombinatorikus geometria síkban, Pontversenyen kívüli probléma
Hivatkozás(ok):	Feladatok: 1970/november: Pontversenyen kívüli P.82

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

a) Először az állítás második részét bizonyítjuk. Föltesszük, hogy $k$ háromszöget sikerült kijelölni az előírt módon, és megmutatjuk, hogy $k \leq \frac{1}{3} (\binom{n}{2})$ . Mivel háromszögeink közül semelyik kettőnek nincs közös oldala ‐ mondjuk ezúttal így: közös éle ‐, azért együttvéve $3 k$ élük van. Ez a szám nem lehet nagyobb, mint az $n$ pontból képezhető pontpárok, élek száma, ami $(\binom{n}{2})$ , így $3 k \leq (\binom{n}{2})$ , és ebből éppen az állításbeli felső korlát adódik $k$ -ra.
b) Induljunk ki ismét abból, hogy egy kiválasztási próbában $k$ db háromszög kijelölése után megakadtunk, vagyis bárhogy választunk ki egy ( $k + 1$ )-edik háromszöget, annak valamelyik éle már valamelyik kiválasztott háromszögnek is éle. Másképpen mondva azt jelenti ez, hogy végigmenve a még föl nem használt éleken ‐ amelyeknek száma az a) rész szerint $h = (\binom{n}{2}) - 3 k$ ‐, és mindegyik ilyenhez hozzápróbálva harmadik csúcsnak a végpontjaitól különböző ( $n - 2$ ) pont mindegyikét, e $p = h (n - 2)$ próba során mindig tiltott háromszöget kaptunk; vagyis olyat, melynek legalább egy éle a már kijelölt $3 k$ él közül való.
Tekintsük másrészt a ki nem jelölt háromszögek számát, ami $H = (\binom{n}{3}) - k$ (az első tag a pontjainkból kijelölhető ponthármasok száma, ha nincs korlátozás.) Fenti próbáink során mindig ilyen háromszöget kapunk, és ha egy ki nem jelölt háromszögnek 2 olyan oldala van, amely még ki nem jelölt él, azt 2-szer is megkaptuk, mindkét ilyen oldala révén. (3-szor azonban egyetlen ki nem jelölt háromszög sem adódhatott ki, hiszen ha egy gondolható háromszögnek egyik oldala sem szerepel a kijelölt háromszögek élei között, akkor az a háromszög kijelölhető, ilyen pedig nincs a föltevésünk szerint.)
Ezek szerint a végzett próbák száma nem nagyobb $2 H$ -nál, és ezt a felső korlátot mindjárt növelve

\begin{matrix} p = h (n - 2) = & {(\binom{n}{2}) - 3 k} (n - 2) \leq 2 H < 2 (\binom{n}{3}) = & (1) \\ = & \frac{n (n - 1) (n - 2)}{3} = (\binom{n}{2}) \cdot \frac{2 (n - 2)}{3} . \end{matrix}

Innen pedig (mivel nyilvánvalóan elég az

n - 2 > 0

eseteket tekinteni)

\begin{matrix} 3 k > (\binom{n}{2}) \cdot (1 - \frac{2}{3}), k > \frac{1}{9} (\binom{n}{2}), \end{matrix}

ezt kellett bizonyítanunk. Ezzel a feladatot megoldottuk.

Stachó Balázs, Katona Endre

Megjegyzések. 1. Nem kapunk lényegesen nagyobb alsó korlátot, ha (1)-ben megállunk

H

eredeti kifejezésénél:

\begin{matrix} {(\binom{n}{2}) - 3 k} (n - 2) \leq 2 (\binom{n}{3}) - 2 k -ból k \geq \frac{1}{3 n - 8} (\binom{n}{3}), \end{matrix}

ugyanis ennek és az állításbeli alsó korlátnak a hányadosa csupán

\begin{matrix} \frac{3 (n - 2)}{3 n - 8} = 1 + \frac{2}{3 n - 8} \leq 1 + \frac{1}{n}, mihelyt n \geq 8. | \end{matrix}

2. Nem lett volna helyes azt mondani, hogy a b) részben gondolt próbák során minden ki nem jelölt háromszöget megkaptunk (legalább egyszer), mert létezhet olyan háromszög, melynek mindhárom oldala szerepel kijelölt háromszög éleként, de mindegyik oldala más-más kijelölt háromszögben.

3. Az állításbeli felső korlát általában nem javítható, mert pl.

n = 7

esetén lehet kijelölni

\frac{1}{3} (\binom{7}{2}) = 7

háromszöget, a csúcsokat az

1,2, ...,7

számokkal jelölve ilyen kijelölés a következő:

\begin{matrix} 1,2,3; 1,4,5; 1,6,7; 2,4,6; 2,5,7; 3,4,7; 3,5,6. \end{matrix}

4. Megoldásunkban többet bizonyítottunk be a feladat állításánál. A feladat csak annyit állít, hogy a háromszögek alkalmas megválasztásával biztosítani lehet legalább

\frac{1}{9} (\binom{n}{2})

háromszöget, megoldásunkból pedig az derült ki, hogy ehhez semmi ügyeskedésre nincs szükség, lépésről lépésre tetszőlegesen választva a már kiválasztott háromszögekhez egy további ,,szabad'' háromszöget, mindig legalább

\frac{1}{9} (\binom{n}{2})

háromszöget kapunk. Ez azt mutatja, hogy az alsó korlátot lehetne tovább javítani.