Az A. 804. feladat (2021. szeptember)

A. 804. Egy mesebeli városban $\displaystyle n$ ember él. A városban jogarvírus teszteket szeretnének vásárolni, melyekkel egyszerre több embertől vett mintát is meg lehet vizsgálni. A következő eredménye lehet egy tesztnek:

$\displaystyle \bullet$ Vírus pozitív: a tesztelt emberek között van beteg, és nincs olyan, aki már korábban átesett a jogarvírus betegségen.
$\displaystyle \bullet$ Antitest pozitív: a tesztelt emberek között van, aki átesett a betegségen, és nincs beteg.
$\displaystyle \bullet$ Semleges: vagy mindenki egészséges, vagy van közöttük beteg és olyan is, aki már átesett a betegségen (az antitestek és a vírusok semlegesítik egymást).

Legalább hány tesztet kell vásárolniuk, ha meg szeretnék tudni, hogy a jogarvírus jelen van-e a városban, azaz van-e olyan ember, aki átesett rajta vagy éppen beteg? (Az emberektől a mintát egyszerre veszik, és mindenki vagy egészséges, vagy beteg, vagy már átesett a betegségen.)

Javasolta: Beke Csongor (Cambridge)

(7 pont)

A beküldési határidő 2021. október 11-én LEJÁRT.

Megoldás. Ha mindenkit letesztelnek külön, akkor $\displaystyle n$ tesztből megállapítható, hogy a jogarvírus jelen van-e. Megmutatjuk, hogy ha $\displaystyle n-1$ tesztet végeztek el és mindegyik semleges lett, akkor lehetséges hogy nem mindenki egészséges, továbbá világos, hogy az is lehet, hogy mindenki egészséges, így ebben az esetben nem tudjuk eldönteni, hogy a jogarvírus jelen van-e a városban.

Számozzuk meg az embereket $\displaystyle 1$-től $\displaystyle n$-ig és legyen $\displaystyle S_i$ az $\displaystyle i$-edik tesztben résztvevő emberek sorszámainak halmaza. Tekintsük a következő egyenleteket $\displaystyle 1\le i\le n-1$-re:

$\displaystyle \sum_{j\in S_i}x_j=0$

Ez egy $\displaystyle n$-ismeretlenes, $\displaystyle n-1$ egyenletből álló homogén lineáris egyenletrendszer. Jól ismert, hogy az ilyen egyenletrendszereknek van nem csupa nullából álló $\displaystyle (y_1, \dots, y_n)$ megoldása. Ha $\displaystyle y_i=0$, akkor legyen az $\displaystyle i$-edik ember egészséges, ha $\displaystyle y_i>0$, akkor beteg, ha pedig $\displaystyle y_i<0$, akkor átesett. Ekkor mindegyik tesztben vagy csak egészséges emberek voltak, vagy beteg és átesett emberek is, hiszen $\displaystyle \sum_{j\in S_i}y_j=0$, így ha nem mindegyik $\displaystyle y_j$ értéke 0, akkor pozitív és negatív értékűnek is kell az egyenletben szerepelnie, hogy végül 0-t kapjunk. Így tehát mindegyik teszt semleges eredményt adott, és nem volt mindenki egészséges.

Így $\displaystyle n-1$ tesztet nem elég venni, de azt láttuk a megoldás elején, hogy $\displaystyle n$ tesztből megoldható a feladat.

Statisztika:

14 dolgozat érkezett.
7 pontot kapott:	Ben Gillott, Kovács 129 Tamás, Nádor Benedek, Németh Márton, Török Ágoston, Varga Boldizsár.
3 pontot kapott:	1 versenyző.
2 pontot kapott:	3 versenyző.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2021. szeptemberi matematika feladatai