Feladat: A.257 Korcsoport: 18- Nehézségi fok: nehéz
Kitűző(k):  Surányi László ,  Virág Bálint 
Füzet: 2001/február, 103. oldal  PDF  |  MathML 
Témakör(ök): Algoritmikus eljárások, Nehéz feladat

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Van n golyó, mindegyiknek szeretnénk megtudni a súlyát. Ehhez rendelkezésünkre áll egy olyan egykarú mérleg, amellyel egyszerre egy vagy két golyó súlyának összegét lehet meghatározni. Arra is fel kell készülnünk, hogy esetleg az egyik mérés pontatlan lesz. Jelöljük f(n)-nel azt a minimális mérésszámot, amellyel az összes golyó súlya minden esetben biztosan meghatározható. Igazoljuk, hogy

f(n)>n+log3n-3.