Bevezetés a számításelméletbe
1. gyakorlat 2002. szeptember 9.
 
 
Vegyes feladatok

 

1. Fogalmazzuk meg a következő állítas tagadását úgy, hogy ne szerepeljen benne (a tagadásban) tagadószó: Minden asszony életében van egy pillanat, amikor szeretne olyat tenni, amit nem szabad.
2. Egy dobozban 51 piros, 62 zöld és 30 sárga golyó van. Minimálisan hányat kell (csukott szemmel) kihúzni ahhoz, hogy biztosan legyen köztük
   1. legalább két különböző?
   2. legalább három piros?
   3. legalább két azonos?
3. Két pohár közül az egyikben víz, a másikban ugyanannyi bor van. áttöltünk valamennyi vizet a boros pohárba, majd az abban lévő folyadékból visszatöltünk ugyanennyit a vizet tartalmazóba. Miből lesz több: vízből az eredetileg boros pohárban, vagy borból az eredetileg vizesben?
4. Kieséses pingpongversenyt rendeznek 2002 játékos között. Párokba sorsolják őket, majd továbbjutnak a győztesek és az, akinek esetleg nem jutott pár. A továbbjutottakat ismét párokba sorsolják, és így tovább, míg végül meg nem születik az abszolút győztes. Hány mérkőzés zajlott le az egész verseny során?
5. Adott a síkon végtelen sok pont. Bizonyítsuk be, hogy végtelen sok különböző távolság lép fel köztük!
6. Kör alakú mély tóban úszkál egy hittérítő. A tó partján megjelenik egy úszni nem tudó kannibál, aki a parton négyszer olyan gyorsan tud futni, mint ahogy a hittérítő úszik. Viszont a szárazföldön a hittérítő sokkal jobb futó, mint a kannibál. El tud-e menekülni a hittérítő az őt üldöző kannibál elől? (Ha igen, hogyan; ha nem, miért nem?)
7. Egy sakktábla két átellenes sarkát lecsippentettük. Lefedhető-e az így maradt tábla 31 darab 2x1-es dominóval?
8. A mesebeli Csalafalván 100 házaspár él. Mindegyik férj tudja az összes asszonyról, hogy hűtlen-e, kivéve a saját feleségéről. Egy nap kiderül, hogy van hűtlen asszony a faluban. A férjek elhatározzák, hogy nem beszélnek egymással erről a kínos dologról, de az, aki saját felesége hűtlenségére rájön, másnap reggel 6-kor megkondítja a templom harangját, egyben jelezve, hogy megbüntette hűtlen asszonyát. Az első 99 reggelen a harangok nem szólaltak meg. Mi történt a századik reggelen?
9. Bizonyítsuk be, hogy egy hatfős társaságban van három ember, akik vagy mind ismerik egymást, vagy pedig egyikük sem ismeri a másik kettő egyikét sem! (Az ismeretség kölcsönös.)