Maths Olympiad Prep

Library / /4 of 37

Combinatorics Difficulty 6.2 National olympiad Find the answer

There are 1010 birds on the ground. For any 55 of them, there are at least 44 birds on a circle. Determine the least possible number of birds on the circle with the most birds.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Given that there are 10 birds on the ground and for any 5 of them, there are at least 4 birds on a circle, we need to determine the least possible number of birds on the circle with the most birds.

To solve this, consider the following steps:

1. Initial Assumption: Let n n be the number of birds on the circle with the most birds. We need to find the minimum value of n n .

2. Case Analysis:
- **Case n=10 n = 10 : All 10 birds are on the same circle. This trivially satisfies the condition.
-
Case n=9 n = 9 : Suppose 9 birds are on one circle and 1 bird is outside. For any 5 birds chosen, at least 4 must be on the circle. This condition is satisfied because any set of 5 birds will include at least 4 from the circle of 9.
-
Case n<9 n < 9 : If fewer than 9 birds are on the circle, then there are at least 2 birds outside the circle. Consider any 5 birds chosen. If 3 or more of these birds are outside the circle, then fewer than 4 birds will be on the circle, violating the given condition.

3. Conclusion**: The minimum number of birds on the circle with the most birds is 9. This ensures that for any 5 birds chosen, at least 4 will be on the circle, satisfying the condition.

Thus, the least possible number of birds on the circle with the most birds is:
9 \boxed{9}

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.