A számítástudomány alapjai - Régi ZH feladatok vegyesen
Ez az oldal régi ZH kérdéseket tartalmaz vegyesen. A többségük emlékezetből lett leírva. Érdemes először a főoldali ZH sorokat átnézni, majd utána ezekből is szemezgetni.
Tartalomjegyzék
Kombinatorika
- Hány különböző rendszám adható ki, amely három betűből és azt követő három számból áll?
A rendszámtábla a következőképpen kell, hogy kinézzen a feladat szövege alapján (b-betű, sz-szám): b,b,b,sz,sz,sz. Vegyük azt, hogy az ábécében n darab betű van. Az első helyre n darab betű közül választhatunk, a másodikra szintén, ugyanígy a harmadikra is, tehát ez ismétléses variáció. A számok esetében ugyanígy járunk el, itt mind a három helyre 10 számjegy közül választhatunk.
Tehát: [math]n*n*n*10*10*10[/math]- Hányféleképpen állítható sorba n (különböző) gyerek?
- Hányféleképpen ültethető egy kör alakú asztal köré n lovag?
- Hányféleképpen fűzhető fel n különböző színű gyöngy egy láncra?
- Válaszoljuk meg az előző kérdéseket akkor is, ha Jancsi és Juliska, Sir Lancelot és King Arthur, illetve a kék és a fehér gyöngy egymás mellé kell, hogy kerüljenek!
- A gyerekek sorba állítása - ismétlés nélküli permutáció: [math]n![/math]
- A kör alakú asztal köré leültetett lovagok közül az első lovag leültetése nem számít, mert ő lesz a viszonyítási alap: [math](n-1)![/math]
Másképp: Az asztalhoz elsőként leültetett lovaghoz képest a pozíciók n esetben megegyeznek: [math]{n! \over n} = (n-1)![/math] - Gyöngysor ugyan ilyen, feltéve, hogy nincs rajta kapocs.
- Jancsi és Juliska egymás mellé ül - vegyük őket "egy személynek" --> A sorba állításban együtt szerepelnek: [math](n-1)![/math]
De köztük is kétféle sorrend lehet: [math](n-1)!*2[/math] - Sir Lancelot-ék esetében ugyanígy eljárva: [math](n-2)!*2[/math]
- Hány olyan hatjegyű szám létezik, amelyben van két azonos számjegy? Hány ilyen 15 jegyű szám létezik?
Hatjegyű számok összesen: [math]9*10^5[/math] (0 nem lehet az első számjegy) és ebből le kell vonnunk azokat, amelyekben mindegyik számjegy különböző: [math]9*9*8*7*6*5[/math]
Tehát: [math]9*10^5-9*9*8*7*6*5[/math]
15 jegyű számok esetén: Mivel csak 10 fajta számjegy van, így mindegyikben van legalább két azonos --> Az összes megfelel a feltételnek: [math]9*10^{14}[/math]- Hányféleképpen olvasható ki az alábbi ábrából a "SzA Rulez"?
- S Z A R U
- Z A R U L
- A R U L E
- R U L E Z
Az összes lehetőség egy út, ahol a bal fölső sarokból indulunk ki, és a jobb alsóba érkezünk. Írjunk le egy lehetőséget, ahol Jobbra és Le lépegetünk:
- J,J,J,J,L,L,L (4 darab J és 3 darab L)
- J,J,L,L,L,J,J (4 darab J és 3 darab L)
Vegyük észre, hogy J,J,J,J,L,L,L lehetséges út ismétléses permutációi felölelik az összes kiolvasási lehetőséget, hiszen az út végigjárásához négyszer kell jobbra és háromszor kell le mennünk, a lépések minden egyes permutációjával egy lehetséges "kiolvasási-úthoz" jutunk: [math]\frac{7!}{4!*3!}[/math]
Másképpen: Vegyük észre, hogy a 7 választásból ki kell választanunk, hogy melyik "lefele lépés" vagy kiválaszthatjuk, hogy melyik "jobbra lépés" /indifferens/.
Ismétlés nélküli kombináció: [math]{7 \choose 3} ={7 \choose 4}= \frac{7!}{4!*3!} [/math]- Hány 6-ra végződő hatjegyű szám van?
- Hányféleképpen lehet 8 bástyát felrakni a sakktáblára úgy, hogy azok ne üssék egymást?
- Hányféleképpen lehet a 32 magyar kártyából 10-et kivenni úgy, hogy a 4 ász köztük legyen?
- Hányféleképpen tölthető ki egy lottószelvény? Hány 5, 4 és 3 találatos kitöltés van?
- Tizenöt vívóból hányféleképpen alkothatunk három (nem feltétlenül diszjunkt) négyfős csapatot?
- Hányféleképp osztható ki 100 hallgatónak 57 különböző könyv és 69 egyforma alma, ha egy hallgató akárhány (esetleg 0) könyvet és akárhány (esetleg 0) almát is kaphat?
- Ugyan annyi van, mint öt jegyű szám: [math]9*10^4[/math]
- Mindegyik elfoglal egy sávot a táblából, tehát: [math]8![/math]
- Ha a négy ászt kivettük, még maradt 28 lapunk, amiből már csak 6-ot kell kiválasztani: [math]{28 \choose 6}[/math]
- Lehetséges szelvény kitöltések: [math]90 \choose 5[/math]
5 találatos kitöltés - pont azt az 5 számot jelölöd, amit kihúztak: [math]1[/math]
4 találatos kitöltés - 4 számot a kihúzottak közül jelölsz, 1 számot pedig a maradék 85-ből: [math]{5 \choose 4}*{85 \choose 1}[/math] - Ha akár ugyanaz a négy fő is lehet mind a 3 csapat: [math]\frac{{15 \choose 4}^3}{3!}[/math]
- Az almák egyformák, így ez egy ismétléses kombináció. A könyvek viszont különbözőek, tehát számít, hogy ki melyiket kapja - Az 1. könyv 100 hallgatóé lehet, a 2. könyv szintén 100 hallgatóé, a 3. könyv ugyancsak 100 hallgatóé... Mivel a könyvek és almák kiosztása egymástól független így a kettőt össze kell szorozni: [math]{100+69-1 \choose 69}*100^{57}[/math]
- Hányféleképpen választhatunk ki három 1 és 30 közötti természetes számot úgy, hogy ezek összege páros legyen?
Két eset van: 2 páratlan + 1 páros vagy 3 páros
- eset: (15 db páratlanból 2 db) * (15 db párosból 1 db) = [math]{15 \choose 2}*{15 \choose 1}[/math]
- eset: 15 db párosból 3 db = [math]{15 \choose 3}[/math]
- Hányféleképpen lehet eljutni az origóból a (2,3,5) pontba úgy, hogy csak egységnyi hosszú JOBBRA, ELŐRE illetve FEL lépések lehetségesek?
A megoldás hasonló az "SZA RULEZ" feladathoz (feljebb), csak 3D -ben: JJFFFHHHHH
J = jobbra(x)
F = fel(y)
H = hátra(z)
- Hány olyan sorrendje van az 1, 2, … n számoknak, amelyekben a páros és páratlan számok felváltva követik egymást?
Ha n páros, akkor a páros és páratlan felét [math]\left( {n \over 2 } \right) ![/math] féleképpen lehet sorba rakni külön-külön, tehát: [math]\left( {\frac{n}{2}!} \right) ^2[/math]
Ha n páratlan, akkor a páros számokból eggyel kevesebb van, mint páratlanokból: [math]\left( \frac{n-1}{2}! \right) \left( \frac{n+1}{2}! \right) [/math]- Egy 12 fős társaságot egy szálloda két háromágyas és három kétágyas szobájában kell elszállásolni. Hány különböző szobabeosztás lehetséges, ha az azonos számú ágyat tartalmazó szobákat nem különböztetjük meg egymástól?
A 12 főt sorba állítjuk, az első három főt az első háromágyasba küldjük, a második hármat a második háromágyasba tehetjük, stb...
Így 12! szobabeosztást találtunk, de ezek közül nagyon sok azonos megoldásnak számít: Érdektelen a két db háromágyas sorrendje (2!), a három darab kétágyas sorrendje (3!), és a szobákon belül az emberek sorrendje ( 3! * 3! * 2! * 2! * 2! -- itt a faktoriálisok egy-egy szobának felelnek meg). Tehát a 12!-t el kell osztani ezekkel a számokkal. A végeredmény: [math]\frac{12!}{(3!)^3*(2!)^4}[/math]- Az {1,2,…100} számokat hányféleképpen lehet három 20-elemű, két 15 elemű és egy 10-elemű halmazra szétosztani? (Mindegyik pontosan 1-be kerül bele)
- Hány olyan 10 betűből álló (nem feltétlenül értelmes) szó van, amelyben 4 különböző magánhangzó van? A mássalhangzók lehetnek egyformák is. A magyar ABC-ben 14 magánhangzó és 21 mássalhangzó van.
- Egy vállalat szeretné megjutalmazni 20 dolgozóját. Van 8 jegye egy világkörüli hajóútra, 7 jegye a foci VB-re és 5 jegye az állatkertbe. Hányféleképpen oszthatja ki ezeket?
Gráfok alapfogalmai, Fák
- Van-e olyan (legalább kétpontú) gráf, melyben minden pont foka különböző?
- Egyszerű gráfban nincs mivel ott minden él két pont fokszámát növeli. Összetett gráfban lehet, mivel abban lehet hurokél, illeltve párhuzamos él.
- Hány különböző minimális súlyú feszítőfája van az alábbi, számozott pontú fának? Gráf
- Hány különböző olyan fa adható meg a 1,2,..n pontokon úgy, hogy az 1-es pont foka pontosan 2 legyen?
A fákat legegyszerűbben a Prüfer-kódjukkal tudjuk leírni, így a feladat megoldásánál is tegyük ezt. Tudjuk, hogy a Prüfer-kód (n-2) hosszú, valamint hogy minden csúcs egyel kevesebbszer szerepel a kódban, mint amennyi a fokszáma. Emiatt az 1-es pont egyszer szerepel a Prüfer kódban.
Tehát a kérdés, hogy hány olyan n-2 hosszú számsor létezik, amiben pontosan 1 db 1-es fordul elő. Cayley miatt n ponton [math]n^{n+2}[/math] különböző fa adható meg, de a miénkben az 1-es csak 1x fordul elő, ezért ez [math](n-1)^{n-3}[/math]-ra redukálódik (n-1, mert az 1-est már nem választhatjuk, és n-3, mert már csak n-3 hosszú helyre kell számokat választani).
Most döntsük el hova legyen az 1-es beszúrva. Lehet a számsor elején és végén, valamint bármely két szám között (n-3 szám van, így köztük n-4 hely van), tehát összesen n-4+2 = n-2 helyre lehet beszúrni az 1-est.
Tehát a végeredmény: [math](n-2)*(n-1)^{n-3}[/math]- Van-e olyan egyszerű gráf, amelyben a pontok foka rendre:
- 1, 2, 2, 3, 3, 3
- 1, 1, 2, 2, 3, 4, 4
- 5, 5, 5, 6, 6, 6, 7, 7, 7
- 1, 2, 2, 3, 4, 4, 5, 6, 6
- 1, 1, 3, 3, 3, 3, 5, 6, 8, 9
- 2, 3, 3, 4, 5, 6, 7
- Igazoljuk, hogy egy tetszőleges gráfban a páratlan fokú pontok száma páros.
- Milyen komponensekből állhat egy gráf, ha minden pontjának a foka legfeljebb 2?
- Bizonyítsuk be, hogy minden fában van olyan pont, amit az összes leghosszabb út tartalmaz.
- Tartalmazhat-e egy Kn (n ≥ 4) feszített részgráfként 4 hosszú kört?
- Egy negyedfokú reguláris összefüggő gráfból töröljük egy fa éleit. Bizonyítsuk be, hogy a maradék legalább két kört tartalmaz.
- Legyen v egy egyszerű G gráfban egy olyan pont, melyre d(v)≥2. Bizonyítsd be, hogy ha a G-v gráf 2-szeresen összefüggő, akkor G is 2-szeresen összefüggő. (A G-v gráf a G gráfból a v pont és az összes v-re illeszkedő él elhagyásával keletkezik.)
- Melyik az a legnagyobb k szám, melyre az alábbi gráf k-szorosan összefüggő? Gráf
- Rajzolja fel az összes olyan páronként nem izomorf egyszerű, összefüggő 5 pontú gráfot, amelyben pontosan egy kör van és a maximális fokszáma legfeljebb 3.
- Bizonyítsd be, hogy ha egy egyszerű G gráfban minden olyan X (része V(G)-nek) ponthalmazra, melyre |X| ≥ 2 teljesül igaz, hogy az X által feszített részgráfnak legalább |X|/2 éle van, akkor a gráf teljes!
Euler-kör, Hamilton-kör és hasonlók
- Milyen n esetén tartalmaz a teljes n-pontú gráf Euler körsétát illetve sétát?
Teljes gráf: Olyan egyszerű gráf, melynek tetszőleges két pontja szomszédos.
Tétel: Egy összefüggő G gráfban akkor és csak akkor van Euler-kör, ha G minden pontjának foka páros.
Tétel: Egy összefüggő G gráfban akkor és csak akkor van Euler-út, ha G páratlan fokú pontjainak száma 0 vagy 2.
Tehát a körhöz minden fokszámnak párosnak kell lenni, vagyis a csúcsok száma páratlan.
Az út esetében nem lehet páratlan fokú csúcs, csak páros, mert páratlanból max. 2 lehetne, de mivel ez egy teljes gráf, ezért az összes csúcs vagy páros, vagy páratlan fokszámú. Így az Euler-útra is ugyan azt a feltételt adhatjuk: n legyen páratlan.- Legyen G=(V,E) az a gráf, melyre V={1,2,…,100}, és a és b pont között pontosan akkor fut él, ha a-b osztható 4-gyel. Van-e G gráfnak Euler körsétája?
Megjegyzés: Fleiner Tamás hivatalos megoldását másoltam be ide, nekem első körben kijött, hogy van benne Euler körséta, és ezt ő a megoldásban is feltüntette, helytelen következtetésként, tehát vigyázni kell.
"Vegyük észre, hogy két pontot akkor köt össze él, ha 4-gyel osztva azonos maradékot adnak, azaz a G gráf 4db 25 méretű teljes gráfból áll: Az egyik teljes gráf csúcsai az 1,5,9,...97, a másiké 2,6,10,...98, a harmadiké 3,7,11,...99, a negyediké 4,8,12,...100 számok lesznek. Mivel G nem összefüggő, és minden komponensének van éle, ezért G-nek bizonyosan nincs Euler-köre.
Rossz megoldás: Ha valaki kiszámolja, hogy minden pont foka 24, ami páros, és ebből helytelenül arra következtet, hogy van Euler-kör, kapjon 4 pontot."- 10 házaspár mindegyik tagjára igaz, hogy a maradék 9 házaspár mindegyikének legalább egyik tagját ismeri. (Az ismeretség kölcsönös.) Bizonyítsuk be, hogy az említett 20 személy leültethető egy 20 személyes, kör alakú asztalhoz úgy, hogy mindenki ismerje a két mellette ülő személy mindegyikét!
- Az alábbi három gráf mindegyikéről döntse el, hogy van-e benne Hamilton-kör? Teljesül-e rá Ore feltétele? Gráfok
Először nézzük Ore tételét: Ha az n pontú G gráfban minden olyan x,y V(G) pontpárra, amelyre {x,y} E(G) teljesül az is, hogy d(x) + d(y) n, akkor a gráfban van Hamilton-kör.
Első gráf: Nem lehet benne Hamilton-kör, mert ha elhagyjuk a középső pontot, 2 komponensre esik szét, márpedig van egy tételünk, ami kimondja, hogy ha a G gráfban létezik k olyan pont, amelyeket elhagyva a gráf több, mint k komponensre esik, akkor nem létezik a gráfban Hamilton-kör. Ore feltétele nem teljesül, mert ha teljesülne, lenne benne Hamilton-kör, az előbb pedig bebizonyítottuk, hogy nincs.
Második gráf: Van benne Hamilton-kör. Bizonyításképp mutatunk egyet. Elindulunk a legbaloldalibb csúcsból és lépünk fel,le,fel,fel,le,fel majd vissza a kiinduló pontba. Ore feltétel nem teljesül, mert bár tudunk mutatni két olyan nem szomszédos csúcsot, amire igaz, hogy d(x) + d(y) n (pl. középső és valamelyik szélső), de nagyon fontos, hogy a feltételnek az összes nem szomszédos pontpárra teljesülnie kell, ez pedig pl. a két felső csúcs esetén már nem igaz, mert fokszámösszegük 6, ami kisebb 7-nél.
Harmadik gráf: A második gráf ennek a feszítő részgráfja, E' E, és a másodikban volt Hamilton-kör, akkor ebben is van(mivel a másodikban volt, és ez annyiban különbözik a másodiktól, hogy több él van benne, így még könnyebb találni). Ore feltétel teljesül, mert az összes nem szomszédos csúcsra igaz, hogy fokszámösszegük a csúcsok számánál.- Legalább hány éle van egy olyan 6 pontú gráfnak, melynek van Hamilton-köre?
- Milyen x és y értékekre tartalmaz Euler körsétát illetve sétát az x × y méretű „kockás” papír, aminek (x + 1) × (y + 1) pontja van?
- Bizonyítsuk be, hogy a Petersen gráfban nincsen Hamilton-kör!
- Bizonyítsuk be, hogy tetszőleges összefüggő gráf élei bejárhatók úgy, hogy minden élen pontosan kétszer megyünk át!
- Képzeljünk el egy képzőművészeti kiállítást. A látogatók szeretik a saját lelkiviláguk szerint élvezni a tárlat anyagát, azaz annyira elmerülnek az esztétikai élmények kavalkádjában, hogy útjelző táblák figyelemmel követésére már nem képesek. Annyi azért persze még tőlük is elvárható, hogy mindig olyan folyosón haladnak tovább, amerre addig még nem jártak és ha egy adott pillanatban látnak ilyen folyosót, akkor azok egyikén tovább is haladnak. Feladat: határozzuk meg, milyen lehet egy ilyen kiállítócsarnok, ha azt szeretnénk, hogy az összes látogató a saját korlátoltsága ellenére végignézhesse a kiállítást!
- Keressünk olyan 8 pontú gráfot, hogy se ő, se a komplementere ne legyen síkba rajzolható!
- Keressük meg az összes 6 csúcsú nem síkgráfot!
- Legfeljebb hány élt húzhatunk be az ábrán látható gráf irányítatlan változatába az egyszerűség megtartásával úgy, hogy a keletkező gráf síkbarajzolható legyen? Gráf
- Legyen G egy összefüggő gráf, amiben minden pont foka páros. Igaz-e, hogy ha elhagyjuk G-ből egy körének éleit, akkor a maradékban biztosan van Euler körséta?
- Bizonyítsd be, hogy ha egy legalább két komponensből álló egyszerű n pontú gráfban minden pont foka legalább n/3, akkor a gráfban van egy legalább n/3 hosszú kör!
Dualitás és Pert módszer
- Döntsük el, hogy az alábbi gráf síkbarajzolható-e! Ha igen, rajzoljuk le egyenes szakaszokkal, élkereszteződés nélkül, és adjuk meg a duálisát is! Ha nem, bizonyítsuk! Gráf
- Határozzuk meg az összes olyan egyszerű, összefüggő 3-reguláris gráfot, mely izomorf a duálisával!
- Egy irányított, (az irányítástól eltekintve) összefüggő, n pontú gráf körmátrixának két sora van. Hány éle van?
- Hány csúcsa lehet annak a fának, amelyben csak kétféle fokszám szerepel, ezek közül az egyik a 4, és a pontoknak pontosan a negyedrésze negyedfokú?
- Legyen G a következő 2n pontú gráf: {v1,…,vn} és {vn+1,…v2n} is egy-egy n hosszú kört alkot. Ezen kívül pedig minden i-re {vi,vi+n} E(G). Igaz-e, hogy G bármely élét elhagyva a maradék gráfban van Hamilton-kör?
- Az alábbi PERT feladatokban határozzuk meg a feladatok elvégzéséhez szükséges összes időt! Mik a kritikus tevékenységek? (x és p paraméterek!)
- Tegyük fel, hogy egy egyszerű G gráf előáll k db egyszerű, síkba rajzolható gráf éldiszjunkt uniójaként. Azaz az éleit k csoportra lehet osztani úgy, hogy az egy csoportban lévő élek síkba rajzolható gráfot alkossanak. Bizonyítsd be, hogy ha n a pontok száma, e az élek száma, akkor [math]k\ge\frac{e}{3n-6}[/math]
- Síkbarajzolható-e az alábbi gráf? Gráf
- Egy egyszerű, hat pontból álló, összefüggő gráfban van 1, 2, 3, 4 és 5 fokú pont is. Mennyi lehet a hatodik pont foka?
- Rajzoltam egy 10 csúcsú fát, de elveszítettem. Rajzold le a duálisát!
Bejárások, Útkeresés
- Egy 15 pontú gráf mélységi bejárása során számozzuk a csúcsokat a bejárási sorrend, azaz mélységi számuk alapján. Közben felírjuk a bejárás befejezési számait is és az alábbi sorrendet kapjuk: 4, 6, 5, 7, 3, 2, 8, 1, 11, 12, 14, 13, 10, 15, 9 Rajzold fel a mélységi gráfot!
- Az egyszeri Qpázó meg szeretné látogatni a Szimpatikus Egyetemet (hogy üdvözölhesse őket), ám útja során csak szénsavmentes üdítőital beszerzésére alkalmas helyeken keresztül mehet. Keressük meg a leggyorsabb utat, hogy időben visszaindulhasson a SKEBU-ra: Ábra
Hogyan oldanád meg a feladatot, ha plusz kitétel, hogy minden vendéglátó-ipari egységben 5 percet tölt a delikvens? Hogyan oldanád meg a feladatot, ha az plusz kitétel, hogy a Qpázónak egy vendéglátó-ipari egység meglátogatása (ami tegyük fel 0 percet vesz igénybe) megér annyit, hogy 3 percet késsen a SKEBU-ról? És ha 5 percet is megér? - Egy n pontú fában jelölje B azon pontok halmazát, amelyek foka legalább 2 (nem levelek). Bizonyítsuk be, hogy: [math]\sum_{v\in B} d(v) = n - 2 + |B|[/math]
- Legalább hány élet kell elhagyni a K6 gráfból ahhoz, hogy síkba rajzolható gráfot kapjunk?
- Egy 20 tagú társaságban mindenki ugyanannyi embert ismer a többiek közül. Bizonyítsd be, hogy le tudnak ülni egy kör-alakú asztal mellé vagy úgy, hogy mindenki mindkét szomszédját ismeri, vagy úgy, hogy senki se ismeri egyik szomszédját sem!
- Egy egyszerű, síkba-rajzolható gráfban a minimális fokszám 5. Mutasd meg, hogy ekkor legalább 12 darab ötödfokú pont van!
- Bizonyítsd be, hogy tetszőleges két n csúcsú fa gyengén izomorf!
- Hány olyan fa van az 1-től 15-ig címkézett pontokon, melyben az 1-es számú csúcs foka 7?
