Problem A. 804. (September 2021)

A. 804. There is a city with \(\displaystyle n\) citizens. The city wants to buy sceptervirus tests with which it is possible to analyze the samples of several people at the same time. The result of a test can be the following:

\(\displaystyle \bullet\) Virus positive: there is at least one currently infected person among the people whose samples were analyzed, and none of them were healed from an earlier infection.
\(\displaystyle \bullet\) Antibody positive: there is at least one person who was healed from an earlier infection among the people whose samples were analyzed, and non of them are infected now.
\(\displaystyle \bullet\) Neutral: either all of the people whose samples were analyzed are not infected, or there is at least one currently infected person and one person who was healed from an earlier infection. (Viruses and antibodies in samples completely neutralize each other.)

What is the smallest number of tests to buy if we would like to know if the sceptervirus is present now or it has been present earlier? (The samples are taken from the people at the same time. The people are either infected now, have been infected earlier, or haven't contacted the virus yet.)

Submitted by Csongor Beke, Cambridge

(7 pont)

Deadline expired on October 11, 2021.

Official solution translated to English by Tashi Diaconescu

If everyone is tested separately, \(\displaystyle n\) tests can be used to determine if a sceptervirus is present.

We show that if we buy \(\displaystyle n - 1\) tests, and all of them gave neutral result, then it is possible that not everyone is negative, and it is clear that everyone may be negative, so in this case we cannot decide whether the sceptervirus is present in the in city (a negative person is a person, who is not infected and was not infected earlier).

Number the people from 1 to \(\displaystyle n\), and let \(\displaystyle S_i\) be the set of the numbers of the people who are tested with the \(\displaystyle i^{\mathrm{th}}\) test, for \(\displaystyle 1\le i\le n-1\). Consider the following homogeneous system of linear equations:

\(\displaystyle \sum_{j\in S_i} x_j=0\text{ for } 1\le i \le n-1. \)

This system has \(\displaystyle n-1\) equations and \(\displaystyle n\) variables. It is known that a such system has a solution \(\displaystyle (y_1,y_2,\ldots, y_n)\) different from the trivial solution \(\displaystyle (0,0,\ldots,0)\).

Because for each \(\displaystyle 1\le i\le n-1\): \(\displaystyle \sum\limits_{j\in S_i}y_j=0\), it follows that \(\displaystyle A_i=\{y_j\mid j\in S_i\}\) is \(\displaystyle \{0\}\) has at least one positive number and at least one negative number. Hence if \(\displaystyle y_i=0\), let \(\displaystyle i\) be healthy, if \(\displaystyle y_i>0\), let \(\displaystyle i\) be infected, and if \(\displaystyle y_i<0\), let \(\displaystyle i\) be healed. It follows now that all the tests are neutral and not everyone is negative (because \(\displaystyle (y_1,\ldots,y_n)\ne(0,\ldots,0)\)).

Thus, we have solved the problem.

Statistics:

14 students sent a solution.
7 points:	Ben Gillott, Kovács 129 Tamás, Nádor Benedek, Németh Márton, Török Ágoston, Varga Boldizsár.
3 points:	1 student.
2 points:	3 students.
1 point:	2 students.
0 point:	2 students.

Problems in Mathematics of KöMaL, September 2021