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