Na, kigyötörtem. És amilyen egyszerű, olyan sokáig tartott. Az a (teljes indukciós) állítás, hogy n ember esetén mindig ki lehet megfelelően n-1 kérdést választani, hogy ezen a részhalmazon mindenki különböző választ adjon.
Kezdőlépés: n=1: nem kell kiválasztani egyik kérdést sem
n=2: Ilyenkor nyilván van olyan kérdés, aminél eltér a válasz, válasszuk azt.
Indukciós lépés (nn+1): válasszunk egy olyan kérdést, amire nem adta mindenki ugyanazt a választ (ilyen van, különben mindenkinek minden kérdésre azonos választ kellett adnia, ami lehetetlen). A válaszok szerint bontsuk csoportokra az embereket - az azonos választ adók kerülnek egy csoportba. Nem kell feltenni, hogy csak kétféle (pl. igen-nem) válasz adható. Az előző megjegyzés szerint legalább két csoport lesz. Álljanak a csoportok a1,a2,...,ak emberből. A csoportokra alkalmazzuk az indukciós feltevést, és ilyenkor (létszám-1) tesztkérdés kiválasztható az adott csoporthoz, ezeket összeadva kijön, hogy összességében elég 1+(a1-1)+...+(ak-1) tesztkérdés, ami k2 miatt legfeljebb n-1. Ha legalább 3 csoport van, akkor ennél kevesebb is elég.
----
Van olyan elrendezés, amihez kell is ennyi kérdés, pl. ha a k. ember csak a k. kérdést rontja el. Ilyenkor az első 20 kérdésből muszáj 19-et kiválasztanunk, hogy azok alapján különbözzenek a tanulók.
(Bocs, ha nem teljesen érthető minden, kicsit gyorsan írtam.)
|