2005.március 20.
Babai László 2004. májusi előadása
Lejegyezte: Maga Péter.
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 | ![]() |
![]() |