Maths Olympiad Prep

Library / /2 of 3

Combinatorics Difficulty 6.2 National olympiad Find the answer

There is a city with nn 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:

- 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.

- Antibody positive: there is at least one person who was healed from an earlier infection among the people whose samples were analyzed, and none of them are infected now.

- 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.)

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

To determine the smallest number of tests required to ascertain if the sceptervirus is currently present or has been present in the city, let's analyze the given conditions for the test results:

1. Virus positive: Indicates there is at least one currently infected individual among the tested samples, and none of them have antibodies from previous infections.

2. Antibody positive: Indicates there is at least one individual healed from a previous infection among the samples, with no currently infected individuals.

3. Neutral: This result implies that either all individuals tested are not infected, or there is a mix of currently infected persons and previously infected (and now healed) individuals, thus neutralizing each other's presence.

### Objective

We need to strategically design the testing process to determine if there is a current infection or if there has been a previous infection, using the smallest number of tests.

### Solution Approach

To achieve this, consider the following:

- Each citizen falls into one of three categories: currently infected, previously infected (healed), or naive (neither infected nor healed).

- A single test can give us sufficient information about the presence of a virus or antibodies among the selected group.

- By testing each citizen individually, we can directly determine the category to which each citizen belongs—specifically, whether they are currently infected or have antibodies from a previous infection.

### Testing Strategy

Given that we have n n citizens, the simplest strategy to achieve our objective is:

- Test each citizen individually.

This approach ensures that:
- If any test comes back virus-positive, we know that the virus is currently present.
- If any test comes back antibody-positive, we know that the virus was present previously.

By applying a separate test to each individual, we guarantee the detection of any current or past virus presence without ambiguity. Therefore, the minimum number of tests required is:

n \boxed{n}

This solution is both straightforward and optimal as each individual test provides definitive information about each citizen's current or past infection status, collectively revealing the city's overall virus presence.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.