FELADATMEGOLDÓ SPECIÁLKOLLÉGIUM

9 . feladatsor

1) Egy vándor elalszik egy nagyon sűrű erdőben (ha az erdő belsejében vagyunk bármelyik irányba nézünk ugyanazt látjuk: rengeteg fát). Mikor felébred csak arra emlékszik, hogy az erdő alakja egy félsík és ő a félsíkot definiáló egyenestől L távolságra aludt el. Adjunk stratégiát a vándornak, amely alapján minél rövidebb út megtétele után kijut az erdőből.

2) Egy páncélszekrényen 3 kerék van, mindegyik 8–8 lehetséges állással. Hiba folytán a szekrény már akkor is kinyílik, ha legalább két kerék a helyes állásban van. Hány próbálkozásra van szükség ahhoz, hogy biztosan kinyissuk a szekrényt?

3) Egy n pontú teljes gráf élhalmazát teljes páros gráfokkal szeretnénk lefedni. Minimálisan hány fedő gráfra van szükségünk? Mi a helyzet, ha kikötjük, hogy a fedő (teljes páros) gráfok éldiszjunktak legyenek?

4) Az x_{1},…, x_{n}, n ≥ 4 természetes számok egy kör mentén helyezkednek el úgy, hogy bármely i-re az x_{i} szomszédainak az összege az x_{i} szám egy egész k_{i}-szerese. Igazoljuk, hogy ha S_{n} = ∑_{1≤i≤n} k_{i}, akkor 2n ≤ S_{n} < 3n.

5) Egy egységnyi oldalú négyzetben adott n pont. Bizonyítsuk be, hogy van olyan legfeljebb 2\sqrt{n} + o(\sqrt{n}) hosszú görbe, amely az összes adott ponton áthalad. Adjunk meg minél nagyobb olyan L számot is, amely hosszként nem garantálható, azaz alkalmas n elemű ponthalmazhoz nem létezik L hosszú görbe, amely az összes ponton áthalad.

6) Tervezzünk olyan, nem pontosan az 1–6 számokat tartalmazó kockát, amelyre a két kockával történő dobások összegének valószínűsége ugyanaz, mint a szabályos kockánál.

A feladatok megbeszélése: április 15-én , Farkas terem, 17:00 Minden érdeklődőt szeretettel várunk A feladatsort NE VIDD EL. A könyvtárban van másolható példány.

Hajnal Péter Totik Vilmos