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?

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.

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.

Íme ismét egy válogatópélda, méghozzá 2006-ból. Akkor és abban a mezőnyben olyan nehéznek számított, hogy senki nem oldotta meg, pedig két teljesen különböző megoldása is van. Remélem, ez már a múlt, és ti mind a két módon meg tudjátok oldani. (És ezt komolyan mondom, mind a kettő megoldás fontos, úgyhogy akkor is érdemes továbbgondolkozni rajta, ha egyféleképp már megy.)

Van néhány magyar versenyről származó feladat is, amely érdekes, nem triviális, sőt fontos. Ugyanakkor ezekkel nagyobb eséllyel is találkozhattatok, úgyhogy igyekszem mellettük máshonnan származó, és talán valamivel nehezebb feladatokat is kitűzni, hogy ne unatkozzatok. Ez az intervallumos is egy ilyen példa: a 2007-es válogatóversenyen szerepelt, és ahhoz képest viszonylag nehéznek mondható (nemzetközi szinten inkább könnyű), viszont hallatlanul fontos módszert gyakoroltat.

Még azt itt megjegyezném, hogy példabemenetet és ábrákat a legritkább esetben fogok a posztba beleírni, viszont mindig linkelem az eredeti feladatleírást, ahol ezek megtalálhatóak.