A B. 4052. feladat (2008. január)

B. 4052. Egy egyszerű gráfban ugróiskolának nevezünk egy olyan P₁,P₂,...,P_k utat, amelyben minden i-re a P_i csúcs fokszáma i. Legfeljebb hány csúcsa lehet egy ugróiskolának egy n csúcsú gráfban?

Javasolta: Mészáros Gábor

(4 pont)

A beküldési határidő 2008. február 15-én LEJÁRT.

Megoldás: Jelölje a kérdéses számot f(n). Könnyen ellenőrizhető, hogy f(1)=0, f(2)=1, f(3)=f(4)=2 és f(5)=3. Tegyük fel, hogy a gráfban van egy P₁,P₂,...,P_k ugróiskola, ahol k $\ge$ 4. P_k az út csúcsai közül P₁-gyel, P₂-vel és saját magával nem lehet összekötve, vagyis a gráfnak kell legyen még legalább 3 további csúcsa. Ez azt mutatja, hogy n $\ge$ 6 esetén f(n) $\le$ n-3. A továbbiakban megmutatjuk, hogy n $\ge$ 6 esetén f(n) $\ge$ n-3 is fennáll, vagyis k $\ge$ 3 esetén van olyan k+3 szögpontú egyszerű G_k gráf, amely tartalmaz k csúcsú ugróiskolát.

Vegyünk fel ehhez egy $P_1P_2\ldots P_k$ utat, és 3 $\le$ i,j $\le$ k, i $\ne$ j, k+3 $\le$ i+j esetén kössük össze a P_i és a P_j csúcsokat (amennyiben eddig még nem voltak összekötve) egy éllel. Az így kapott H_k egyszerű gráfban jelölje d(i) a P_i csúcs fokát. Nyilván d(1)=1 és d(2)=2. Ha i $\ge$ 3, akkor k+3-i $\le$ j $\le$ k, i $\ne$ j esetén P_i össze van kötve P_j-vel, vagyis d(i) $\ge$ (i-2)-1=i-3. Másrészt azon az i-2 darab P_j csúcson kívül, amelyre k+3-i $\le$ j $\le$ k teljesül, P_i legfeljebb két további csúccsal lehet összekötve a $P_1P_2\ldots P_k$ út mentén, vagyis d(i) $\le$ (i-2)+2=i. összefoglalva, i $\ge$ 3 esetén 0 $\le$ i-d(i) $\le$ 3. Ha felveszünk három további csúcsot, és 3 $\le$ i $\le$ k esetén a P_i csúcsot ezek közül i-d(i) darabbal összekötjük, olyan k+3 csúcsot tartalmazó G_k egyszerű gráfot kapunk, amelyben P₁,P₂,...,P_k ugróiskola.

Megállapíthatjuk tehát, hogy n $\ge$ 6 esetén f(n)=n-3.

Statisztika:

82 dolgozat érkezett.

4 pontot kapott: Aczél Gergely, Ágoston Tamás, Bálint Dániel, Balla Attila, Bencs 111 Ferenc, Bodor Bertalan, Börcsök Bence, Cséke Balázs, Csere Kálmán, Czeller Ildikó, Dudás 002 Zsolt, Éles András, Farkas Márton, Fonyó Dávid, Frankl Nóra, Gele Viktória, Gévay Gábor, Gőgös Balázs, Grósz Dániel, Kalina Kende, Kiss 243 Réka, Kiss 902 Melinda Flóra, Kiss 991 Mátyás, Konkoly 001 Csaba, Kovács 729 Gergely, Kovács Kristóf, Kristóf Panna, Marák Károly, Mészáros András, Mihálykó Ágnes, Nagy 648 Donát, Palincza Richárd, Peregi Tamás, Perjési Gábor, Réti Dávid, Salát Zsófia, Szabó 124 Zsolt, Szabó 895 Dávid, Szalkai Balázs, Szőke Nóra, Tóth 369 László Márton, Véges Márton, Zelena Réka.

3 pontot kapott: 12 versenyző.

2 pontot kapott: 4 versenyző.

1 pontot kapott: 9 versenyző.

0 pontot kapott: 11 versenyző.

Nem versenyszerű: 3 dolgozat.

A KöMaL 2008. januári matematika feladatai

82 dolgozat érkezett.
4 pontot kapott:	Aczél Gergely, Ágoston Tamás, Bálint Dániel, Balla Attila, Bencs 111 Ferenc, Bodor Bertalan, Börcsök Bence, Cséke Balázs, Csere Kálmán, Czeller Ildikó, Dudás 002 Zsolt, Éles András, Farkas Márton, Fonyó Dávid, Frankl Nóra, Gele Viktória, Gévay Gábor, Gőgös Balázs, Grósz Dániel, Kalina Kende, Kiss 243 Réka, Kiss 902 Melinda Flóra, Kiss 991 Mátyás, Konkoly 001 Csaba, Kovács 729 Gergely, Kovács Kristóf, Kristóf Panna, Marák Károly, Mészáros András, Mihálykó Ágnes, Nagy 648 Donát, Palincza Richárd, Peregi Tamás, Perjési Gábor, Réti Dávid, Salát Zsófia, Szabó 124 Zsolt, Szabó 895 Dávid, Szalkai Balázs, Szőke Nóra, Tóth 369 László Márton, Véges Márton, Zelena Réka.
3 pontot kapott:	12 versenyző.
2 pontot kapott:	4 versenyző.
1 pontot kapott:	9 versenyző.
0 pontot kapott:	11 versenyző.
Nem versenyszerű:	3 dolgozat.

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