There are $10$ birds on the ground. For any $5$ of them, there are at least $4$ birds on a circle. Determine the least possible number of birds on the circle with the most birds.
Problem
Source: China Mathematical Olympiad 1991 problem3
Tags: combinatorics unsolved, combinatorics
10.10.2013 00:11
I don't understand what the problem is asking for. If it asks for the least number of birds in the circle, the answer is 9: suppose its 8 or less, so there are 2 outside the circle. Take those 2 and 3 arbitrary birds to obtain a contradiction.
10.10.2013 04:34
Actually, 9 is the right answer. As the problem 3 which usually means the hardest problem in the contest, this problem seems too easy...
10.10.2013 12:21
tuvie wrote: I don't understand what the problem is asking for. If it asks for the least number of birds in the circle, the answer is 9: suppose its 8 or less, so there are 2 outside the circle. Take those 2 and 3 arbitrary birds to obtain a contradiction. What contradiction? Out of these $2 + 3$ points, why cannot $2 + 2$ be on a same circle? It has not to be the circle of the $8$ points, eh?
04.07.2022 19:39
Replace $10$ with $n\ge 9$. I claim that the answer is $n-1$. First get rid of the flavortext, the birds are points and bird $i$ represents point $A_i$. We begin with a lemma: Lemma: The answer is greater than $4$. Proof: Obviously the answer cannot be less than $4$, so suppose the answer is $4$. Then there are $\frac{\binom{n}{5}}{n-4}$ 4-point groups that lie on a circle. The total number of three point groups is $\binom{n}{3}$. On the other hand, because distinct circles have at most 2 intersections, this number is $\ge \frac{\binom{n}{5}}{n-4}\binom{4}{3}$, which is impossible. The rest just becomes a puzzle. Now suppose WLOG that $(A_1, A_2, A_3, A_4, A_5)$ are concyclic. Such a tuple must exist by our lemma. Suppose that two other points $A_i$ and $A_j$ do not lie on this circle. Consider the $5$-element group of points $A_i, A_j, A_1, A_2, A_3$. Since $A_i, A_j$ do not lie on $(A_1A_2A_3)$, $A_i$ and $A_j$ must lie on a circle with exactly two of the other points, say $A_1$ and $A_2$ but not $A_3$. Consdering $A_i, A_j, A_3, A_4, A_5$, we get that $A_i, A_j, A_4, A_5$ lie on a circle. Consider $A_i, A_j, A_1, A_3, A_4$. We know that $A_i, A_j, A_1, A_3$ and $A_i, A_j, A_3, A_4$ are not concyclic. Thus $A_i, A_j, A_1, A_4$ must be concyclic. This implies that $A_i, A_j, A_1, A_2, A_4, A_5$ lie on a circle, and $A_3$ does not lie on this circle. However, this circle is the same as $A_1, A_2, A_3, A_4, A_5$ since distinct circles have at most $2$ intersections, which is a contradiction. Thus at most one point is not on the circle with the rest of the points, making the answer $n-1$. This can simply be achieved by placing $A_1,A_2,\cdots,A_{n-1}$ on a circle and $A_{n}$ not on said circle.
05.07.2022 05:11
Good job figuring it out
11.01.2024 06:10
This solution is so incredibly ugly but here we go. The answer is $9$; we can see this by drawing a circle with $9$ points on it and then any other arbitrary point. To show this is optimal, draw all circles between the $10$ points that contain at least $4$ of the points; we will call these circles nontrivial. Let $(ABCD)$ be any nontrivial circle. Claim. There exist at most $3$ points not on $(ABCD)$. Proof. Suppose there existed $4$, say $A_1, A_2, A_3, A_4$. Then, fix some $A_i$ and $A_j$ and consider picking all $5$-tuples consisting of $A_i, A_j$, and $3$ points from $A, B, C$. Because $A_i$ and $A_j$ do not lie on $(ABCD)$, both $A_i$ and $A_j$ must be concyclic with some two points from $A, B, C, D$. Say these two points are $A$ and $B$. This condition itself is not enough because picking the set $\{A_i, A_j, B, C, D\}$ yields that $A_i$ and $A_j$ must also be concyclic with $C$ and $D$. (If $A_i$ and $A_j$ are concyclic with $B$ and $D$ or $B$ and $C$, then $(A_iA_jBCA)$ or the analog is concyclic which is impossible.) So for each of the $6$ sets $\{i, j\}$, there exist one of the three groupings $(\{A, B\}, \{C, D\})$ and symmetric analogs that must be both concyclic with $A_i$ and $A_j$. In particular, looking at two of these sets $\{i, j\}$ that correspond to the same grouping, there must exist $i, j, k$ such that $A_i, A_j, A_k$ is concyclic with both say $A, B$ and $C, D$ without loss of generality. But $(A_iA_jA_k)$ is fixed, so this implies $(A_iA_jA_k)=(ABCD)$, which is a contradiction. $\blacksquare$ So now we resolve edge cases. The first edge case occurs when there are $3$ points not on $(ABCD)$, which necessitates that $\omega=(ABCD)$ has $7$ points on it. Let the three points be $B_1, B_2, B_3$ and $A_1, A_2, \dots, A_7$ be the points on the circle. There exists at most two points $A_1$ and $A_2$ that lie on $(B_1B_2B_3)$; then, we look at sets $\{B_1, B_2, B_3, A_i, A_j\}$ with $i, j \geq 3$. Again, for each of these ${5 \choose 2} = 10$ sets $\{i, j\}$, one of $\{B_1, B_2\}$, $\{B_2, B_3\}$, $\{B_3, B_1\}$ is concyclic with $\{A_i, A_j\}$; in particular, there exists one of the three, say $\{B_1, B_2\}$, that is concyclic with $4$ such $\{A_i, A_j\}$ by Pigeonhole. Two of these $4$ sets must share a common element $A_i$; if they are $\{A_i, A_j\}$ and $\{A_i, A_k\}$, then $B_1, B_2, A_i, A_j, A_k$ are concyclic, which is a clear contradiction. The second edge case occurs when there are $2$ points on $(ABCD)$, which necessitates that $\omega$ has $8$ points on it; we label similarly. By a similar argument, for any set $\{i, j, k\}$, one of $\{A_i, A_j\}$, $\{A_i, A_k\}$, $\{A_j, A_k\}$ is concyclic with $B_1$ and $B_2$. Fix $i = 1$ and vary $j, k$. If there exists two $j_1, j_2$ such that $B_1, B_2$ are concyclic with $\{A_1, A_{j_1}\}$ and $\{A_1, A_{j_2}\}$, then we have a clear contradiction; so there exists at most one value, say $j_1 = 2$. In varying $\{j, k\} \subset \{3, 4, 5, 6, 7, 8\}$, every subset of the form $\{A_j, A_k\}$ is concyclic with $B_1$ and $B_2$. In particular, $B_1$ and $B_2$ must be concyclic with all of $A_3, A_4, \dots, A_8$, which is again a contradiction. We have resolved all cases, so the proof is complete.