5. The organizers of a mathematics olympiad decided to photograph 60 participants. It is known that no more than 30 participants can fit in a single photograph, however, any two students must appear together in at least one photograph. What is the minimum number of photographs needed to achieve this?
Solution
# Answer: 6.
## Solution:
Example with 6 photos: divide 60 participants into 4 groups of 15 people (groups , Г). Take 6 photos of all possible pairs of groups: - in each photo, there will be 30 people, and it is easy to see that in this way any two people will be photographed together.
We will prove that fewer photos are not sufficient. Suppose no more than 5 photos were taken. After each photo, give each photographed person a candy. Then, in total, the participants received no more than candies (since no more than 30 people are in each photo, and there are no more than 5 photos). Since there are 60 participants, there will be a participant who received no more than 2 candies (otherwise, a total of at least candies would have been given). Then he was photographed with no more than 29 other participants in one photo and with no more than 29 other participants in another photo (if there is such a photo) - that is, with no more than other participants of the olympiad, while he should have been photographed with all 59 participants (i.e., with everyone except himself). This is a contradiction, so five or fewer photos are insufficient to meet the condition of the problem.
## Criteria:
A correct answer without a correct example is not scored.
Example for 6 photos - 2 points.
Correct estimation (justification why 5 or fewer photos are insufficient) - another 5 points.
Examples or estimates for 7 or more photos are not scored.
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.