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.

Feladat

Volt nekünk egy szabályos zárójelsorozatunk, gömbölyű és szögletes zárójelekből: (,),[,]. Precízen most nem definiálom, hogy mi az a szabályos (ha valakinek kell, ott van az eredeti feladatleírásban), de pont az, amire gondolunk. Igen ám, csak valami elromlott a kódolásban, és az összes szögletes zárójel kicserélődött gömbölyű nyitóra: (. Tehát megkapjuk ezt a módosult sztringet, a kérdés pedig az, hogy hányféle lehetett az eredeti zárójelsorozat.

Í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.)

Feladat

Adott egy város a négyzetrácson. Az utcák a tengelypárhuzamos, rácspontokon keresztül húzott egyenesek, közülük a főút az x-tengely. A polgármester tűzijátékot szeretne rendezni a főút valamelyik rácspontjában, azonban azt csak a rácsponton keresztül haladó utcákról lehet látni. Tehát ha a (p,0) pontban rendezi, akkor azt a főútról, valamint az x=p egyenesről látni. A helyszínt úgy akarja kiválasztani, hogy a (fontosabb) városlakóknak minél kevesebbet kelljen sétálni ahhoz, hogy megnézhessék a tűzijátékot. A sétatáv Manhattan-távolságban értendő, azaz csak utcákon sétálhatnak, és szomszédos utcák közt egy egységnyi utat kell megtenni.

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.

Feladat

Adott egy n tagú egész számokból álló sorozat: a₀, a₁, ..., a_n-1. Hívjuk az a_k, a_k+1,...,a_n-1, a₀, a₁,..., a_k-1 sorozatot ennek a k-adik elforgatottjának (0<=k<n). Úgy szeretnénk elforgatni a sorozatot, hogy az első i elem összege nemnegatív legyen minden i=1,2,...,n-re. Határozzuk meg, hogy hányféle k-ra lesz a k-adik elforgatott ilyen sorozat.

Feladat

Adjuk meg, hogy a C_n gráfban, vagyis az n hosszú körben hány párosítás található. A csúcsokat megkülönböztetjük. Párosítás alatt az élek egy csúcsdiszjunkt részhalmazát értjük, azaz néhány élt úgy, hogy semelyik kettőnek nincs közös végpontja.