Student World

Před několika měsíci mi můj švagr Carl Wittwer, patolog, položil zajímavou matematickou otázku. Vyvinul krevní zkoušku na odhalení určité drobné dětské vady. Její výskyt se kryje s přítomností jisté látky v krvi. Zkouška je dostatečně citlivá, aby dokázala odhalit jednoho postiženého ve stočlenné skupině prověřením směsi malých krevních vzorků členů skupiny.

(Ve skutečnosti každý biologický test, jakkoliv citlivý, někdy selže. Taková možnost poroste s počtem příspěvků do směsi. S pravděpodobností mylného výsledku by se proto mělo v návrhu způsobu provádění počítat.)

Samozřejmě, odběrem krevních vzorků sta dětí se takto postižené dají přesně určit provedením sta jednotlivých zkoušek. Carlova otázka zněla: dá se výrazně snížit počet zkoušek smícháním vzorků a prověřením směsí s cílem vyloučit velké skupiny dětí najednou? Jestli ano, jak to dělat nejúsporněji?

Představa je velmi přirozená — vyskytuje-li se vada vzácně, očekávali bychom, že i v dost velké skupině dětí pravděpodobně žádné postižené nebude. Prověříme-li je tedy všechny najednou, je vyhlídka, že uklidníme najednou všechny jejich rodiče, aniž by bylo třeba provádět nějaké dodatečné zkoušky. (A ušetřené prostředky můžeme použít k zajištění lepší léčby skutečně postižených.)

Tato otázka je velmi podobná známému druhu zábavných matematických hádanek, takzvaným úlohám o vážení mincí, a tak tuto kapitolu zahájíme zkoumáním obvyklého příkladu toho druhu.

ÚLOHA O VÁŽENÍ MINCÍ

Úloha 7.1. Máte devět mincí, osm pravých a jednu falešnou. Víte, že pravé váží stejně, falešná je nepatrně těžší. Máte též váhy podobné těm, které jsou na obrázku 7.1, na nichž můžete srovnávat váhy dvou hromádek mincí. Jakým nejmenším počtem vážení lze určit tu falešnou?

Dopřejte si náskok a zkuste úlohu vyřešit před tím, než budete pokračovat.

Jistě lze falešnou minci odhalit nejvýš čtyřmi váženími. Rozdělte mince do čtyř dvojic a jedna zbude. V každé dvojici srovnejte váhu obou mincí. Je-li jedna těžší, nalezli jste tu padělanou. Jestli se váhy nevychýlí u žádné dvojice, je padělaná ta lichá. Toto zaručuje úspěch při nejvýš čtyřech váženích, ale v průměru uspějete s méně pokusy. S pravděpodobností 2/9 je padělek

v první dvojici. S pravděpodobností 2/9 se vyskytne v každém z druhého a třetího vážení. A nakonec s pravděpodobností 3/9 = 1/3 se padělek neprozradí až do čtvrtého vážení. Pravděpodobný počet vážení, která provedete, tedy je

1 × 2/9 + 2 × 2/9 + 3 × 2/9 + 4 × 3/9 = 8/3

.

Takže v průměru budete potřebovat pouze 2 a 2/3 vážení.

To však není nejobratnější způsob jak najít nepravou minci. Lze ji zaručeně odhalit pouhými dvěma váženími takto: Udělejte dvě hromádky po třech mincích a zvažte je navzájem. Je-li jedna těžší, je padělek v ní. Jestli ne, je ve zbylé trojici. V obou případech jste našli kupku, v níž je. Teď oddělte dvě mince z té podezřelé a zvažte je spolu. Je-li jedna těžší, je to padělek. Jestli ne, je to ta třetí. Postup uspěje přesně se dvěma váženími, ať je nepravá mince kterákoliv.

Právě popsaný postup se velmi podobá navrhovanému přístupu ke krevním vzorkům. U mincí některé ke zkoušce „sdružíme“, abychom urychlili postupné zužování možností. Pokusíme se to pochopit trochu hlouběji. Za prvé, není moc těžké si všimnout, že máme-li mincí 27 místo devíti, dal by se padělek týmž sdružovacím postupem objevit na tři vážení. Nejprve je rozdělíme do tří skupin po devíti a dvě spolu zvážíme. Tak poznáme, do které padělek patří, a na ni uplatníme týž postup, jako s devíti mincemi. Při 3 × 27 = 81 mincích obdobně vystačíme se čtyřmi váženími. Obecně, pro 3 na m mincí se obejdeme s m váženími (máme-li dost pevné váhy, aby unesly tolik mincí).

Zatím jsme ověřili, že při počtu 3 na m mincí lze zaručit úspěch na m pokusů; co jsme ale neudělali — neověřili jsme, že to je nejmenší možný počet, ačkoliv je intuitivně jasné, že to m bude asi to nejlepší, co lze zaručit. A tuto představu lze postavit na pevnější základ následovně. Každé vážení je otázka, která má tři možné odpovědi:

(L) levá sada je těžší;

(V) sady jsou vyvážené; nebo

(P) pravá sada je těžší.

Začněme tím, že je 3 na m možností umístění padělané mince. (Bývá je zvykem chápat jako možné „stavy“ naší sady zkoumaných mincí.) Kterékoliv dvě menší sady vážíme v prvním kole, všech 3 na m možných stavů se rozpadne do tří skupin:

• všechny ty, u nichž bude při vážení odpověď (L);

• všechny s odpovědí (V);

• všechny s odpovědí (P).

Ježto je 3 na m možností rozděleno do tří skupin, aspoň jedna musí obsahovat přinejmenším třetinu možností, tj. aspoň 3 na (m−1). Ať tedy zvážíme jako první kterékoliv dvě sady, zbývá přinejmenším 3 na (m−1) možných stavů ke zkoumání dalším vážením. V takovém případě druhé vážení těchto 3 na (m−1) stavů rozdělí do tří skupin a nejméně v jedné bude aspoň 3 na (m−2) stavů. Tak pokračujeme a zjišťujeme, že nemůžeme zaručit zúžení počtu možností na 1 = 3 na 0 méně než m váženími.

Právě provedené odůvodnění lze shrnout takto: „jestli má položená otázka tři možné odpovědi, nelze zaručit rozlišení mezi 3 na m možnými stavy méně než m otázkami“. A stejně tak, klademe-li otázky, na něž jsou dvě možné odpovědi (ano či ne), pak největší počet možností, jež lze rozlišit položením m otázek je 2 na m. V obou případech (3 odpovědi nebo 2 odpovědi) je počet možností, které lze rozlišit, exponenciální funkcí (3 na m nebo 2 na m) počtu otázek.

Ve zbytku této kapitoly nás budou zajímat otázky ano/ne. Počet možných stavů, které dokážeme m otázkami rozlišit, tedy bude 2 na m. Bývá obvykle výhodnější vyjadřovat počet potřebných otázek pomocí počtu stavů, jež máte rozlišit, než naopak. Je-li počet stavů n = 2 na m, je potřebný počet otázek dvojkový logaritmus

m = log₂ n.

Zde obsažené lze zhruba přepsat do tvaru počet otázek ano/ne ≈ log₂ (počet stavů).

Nejdůležitější tu je, že počet potřebných otázek je mnohem menší, než počet možností, které potřebujeme rozlišit. To je dobré znamení pro věc krevních vzorků. Podívejme se, zda nám ji zamyšlení nad záležitostí s mincemi pomůže vyřešit.

Připomeňme otázku, jíž tato kapitola začala. Odebrali jsme krevní vzorky od jistého množství dětí a chceme zjistit, zda a případně které vykazuje jisté chorobné příznaky. Můžeme prověřovat jednotlivé vzorky, nebo smíchat malá množství z více vzorků a prověřit vzniklou směs. V obou případech jsou dva možné výsledky zkoušky

(P) aspoň jeden přispěvatel vykazuje chorobné známky;

(N) všichni přispěvatelé jsou chorobných příznaků prosti.

Úkolem je vyvinout účinný postup jak přesně určit, které děti mají příznaky.

Tento text je úryvkem z knihy

Keith Ball: Podivuhodné křivky, počítání králíků a jiná matematická dobrodružství

Argo a Dokořán 2011

O knize na stránkách vydavatele

autor