2005.március 20.

Babai László 2004. májusi előadása

Lejegyezte: Maga Péter.

Az elhangzott feladatokból:

Van n kövünk, különböző nehézségűek, a sorrendjüket szeretnénk minél kevesebb méréssel megállapítani, ahol egy mérés két kő nehézségének összehasonlítását jelenti. Bármely kettő összemérése nyílván jó, de ez n(n– 1)/2 mérés. Ennél jóval kevesebbel is meg lehet állapítani a sorrendet. Képzeljük el, hogy már néhány kő sorba van rakva, és egy újabbat szeretnénk a láncba beilleszteni. Ekkor felesleges minden eddigi kővel összemérni, hiszen a nehézség (mint reláció) tranzitív tulajdonsággal rendelkezik. Ha tehát például az új követ a középsővel (vagy „majdnem” középsővel) összemérjük, és annál nehezebbnek / könnyebbnek találjuk, akkor már a kövek felénél biztosan nehezebb / könnyebb...

	Megtekintés	Letöltés
Feladatok versenyeken