Bevezetés a számításelméletbe I.

1. gyakorlat, 2005. szeptember 12.

                            Koblinger Egmont <egmont@cs.bme.hu>

Vegyes feladatok

1. Helyezzünk el minél több azonos tisztet a sakktáblán úgy, hogy semelyik kettő se üsse egymást. (Ez figuránként külön feladat.)

2. 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?

3. 13 pénzérme közül az egyik hamis, súlya eltér a többi súlyától. Válasszuk ki a hamisat egy súlykészlet nélküli kétkarú mérleg segítségével három méréssel.

4. Legalább hány embert kell kiválasztani ahhoz, hogy biztosan legyen közöttük kettő, akinek ugyanannyi foga van? És ahhoz, hogy biztosan legyen közöttük kettő, akinek ugyanolyan a fogazata?

5. A végtelen négyzethálós papíron kijelöltünk száz mezőt. Igazoljuk, hogy ezek közül ki lehet választani 25-öt, melyeknek páronként nincs közös pontjuk.

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

7. A tér egy pontját rácspontnak nevezzük, ha mindhárom koordinátája egész szám. Mutassuk meg, hogy bármely 9 rácspont közül van kettő, amelyek által meghatározott szakasz felezőpontja is rácspont.

8. Egy dobozban 51 piros, 62 zöld és 30 sárga golyó van. Hányat kell (csukott szemmel) kihúzni ahhoz, hogy biztosan legyen köztük

a) legalább két különböző?

b) legalább három piros?

c) legalább két azonos?

9. Egy sakktábla két átellenes sarkát lecsippentettük. Lefedhető-e az így maradt tábla 31 darab 2 × 1-es dominóval?

10. Fogalmazzuk meg a következő állítás tagadását úgy, hogy ne szerepeljen benne tagadószó: „Minden asszony életében van egy pillanat, hogy (=amikor) szeretne olyat tenni, amit nem szabad.”

Számítástudományi és Információelméleti Tanszék: I.B.132

 http://www.cs.bme.hu/

Feladatsoraim:

 http://www.cs.bme.hu/˜ egmont/bsz/

BSz Fan Club:

 http://www.cs.bme.hu/˜ zoli/bszfc/