Ismerősök – megoldás

2013.04.03. 05:53

Az eredeti feladat itt.

Társasjáték – megoldás

2013.04.03. 05:47

Az eredeti feladat itt.

Fa – megoldás

2013.04.03. 05:46

Az eredeti feladat itt.

Ismerősök

2013.04.03. 05:38

Feladat

Adott egy N csúcsú gráf, ahol legfeljebb 5 kivétellel minden csúcs foka legfeljebb 2. Adjuk meg a maximális független csúcshalmaz méretét. Avagy mesével: N ember közül – legfeljebb 5 kivétellel – mindenki legfeljebb 2 másikat ismer. Legfeljebb hány ember tudunk kiválasztani, hogy közülük senki ne ismerjen senkit?

Társasjáték

2013.04.03. 05:38

Feladat

Egy társasjáték mezőit megszámoztuk 1-től N-ig, a bábunk az 1-es mezőn áll. Dobókockát dobálunk, és mindig annyit lépünk előre, amennyit dobtunk. A cél az N-edik mező, de csak pontos dobással érhetünk be: ha többet dobnánk, a maradékot hátrafelé kell lelépni. Ha a lépések után az N-edik mezőn áll a bábu, akkor a játék véget ér. A kérdés az, hogy hányféle játéklefolyás eredményeként juthatunk a célba, ha legfeljebb K-szor dobhatunk.

Fa

2013.04.03. 05:37

Megpróbálom sorra venni a 2013-as válogatóverseny feladatait.

Feladat

Adott egy bináris fa (van egy gyökérpont, az 1-es csúcs, és minden csúcsnak lehet egy bal és egy jobb oldali gyereke – és persze a gyökér kivételével pontosan egy szülője van). Keressük meg a gyökérhez legközelebbi olyan csúcsot, hogy az abból „leszármazó” részfa szimmetrikus, azaz a jobb és bal oldali részfák egymás tükörképei.