Számítástudomány elemei gyakorlat
1. feladatsor (2002. szept. 12.)

1. 1. A hét törpe minden este más sorrendben szeretne sorba állni, amikor Hófehérke a vacsorát osztja. Hány egymás utáni napon tehetik ezt meg?

   2. Egy 25 fős klubban hányféleképpen lehet egy elnököt és két alelnököt választani?

   3. Nyolc gyerek hányféleképpen állíható úgy sorba, hogy Jancsi és Juliska egymás mellett álljanak?

2. Hányféleképp lehet az 52 lapos franciakártya paklit négy ember között kiosztani ($4\times13$ lap), hogy mind a négy ászt ugyanaz az ember kapja? (ZH, 2000. márc.)

3. Hányféleképpen lehet kitölteni egy TOTÓ szelvényt, ha tudjuk, hogy legfeljebb két mérkőzés fog döntetlenül végződni? (ZH, 2000. máj.)

4. Egy Forma 1-es csapatról az a hír járja, hogy első számú versenyzőjüket, X-et a másik (Y) nem előzheti meg, ha X az első helyen van; sőt, ha ő vezet és X felzárkózik mögé, köteles előre engedni. Más helyezésekért - ha nem ők vannak az élen - szabad egymással csatázniuk. Hányféle lehet a sorrend a dobogón egy olyan futamon, ahol huszonketten indulnak?

5. A Schönherz QPA sörváltó versenyén 32 csapat indult. A verseny egyenes kieséses rendszerben folyt, a szervezők a nevezés után az egész verseny sorsolását előre elkészítették. (Az első körben 16 páros mérkőzést rendeztek, majd az első és második nyertes csapat, a harmadik és negyedik nyertes, stb. mérkőzött meg egymással, stb.) Hányféle lehetett az első két helyezett csapat? (ZH, 2000. okt.)

6. Tíz ember hányféleképpen helyezhető el egy négy- és két háromágyas szobában, ha a háromágyas szobákat nem különböztetjük meg? (Vizsga, 1999. jún.)

7. Benő kilukasztott BKV-jegyeket gyűjt újbóli felhasználás céljából. Egy már meglevő kombináció hossztengelyre való tükörképe nem érdekli, hiszen a jegyet fordítva is kezelhette. Hány jegyet kell Benőnek összegyűjtenie, hogy bármely kombinációval (vagy annak tükörképével) rendelkezzen?

8. Van-e olyan (legalább kétpontú) egyszerű gráf, melyben minden pont foka különböző?

9. Az $1,2,3,...,60$ pontokon hány 1768 élű egyszerű gráfot rajzolhatunk? (ZH, 2000. márc.)

10. Van-e olyan egyszerű gráf, melyben a pontok foka rendre
    1. $1,2,2,2,3,3$
    2. $1,1,2,2,3,4,4$
    3. $2,3,3,4,5,6,7$
    4. $1,3,3,4,5,6,6$

11. Egy $n$ pontú egyszerű gráfban minden pont foka legalább $$\frac n2$$. Bizonyítsd be, hogy a gráf összefüggő!