There are arbitrary 7 points in the plane. Circles are drawn through every 4 possible concyclic points. Find the maximum number of circles that can be drawn.
Problem
Source: China TST 1990, problem 8
Tags: set theory, combinatorics unsolved, combinatorics
05.10.2009 15:59
I think that the maximum number of circles is $ 5$(just guess) Let $ ABCD$ is a cyclic quadrilateral.$ AB\cap CD=F,AD \cap BC=E$. The circle $ (ABE)$ cuts the circle $ (ADF)$ at $ M$.We have that $ MEAB,MDAF,ABCD,MCDE,MACF$ are cyclic quadrilaterals. Is that right?
05.10.2009 19:12
thats simply 7c4
05.10.2009 19:16
The maximum number is $ \boxed{6}$ . Consider an equilateral triangle, the midpoint of its edges and its center. (see below). Image not found We'll will prove that the required number of circles is at most $ 7$. Let transpose our problem into set theory terms. Choose $ A = \{[7]\} = \{1,2,3,4,5,6,7\},$ and let $ M_{1}, M_{2}, \dots, M_{k} \subset A,$ with \[ |M_i| = 4 \ \wedge\ |M_i\cap M_j|\leq 2, \ \forall\ i,j\in A, \ i\neq j\] Then $ k\leq 7.$ Proof. Define $ C_i: = \{j\in \{[k]\} \ : \ i\in M_j \}, \ \forall\ i\in A$. By counting in two ways we get that: \[ 2\cdot\dbinom{k}{2}\geq \displaystyle\sum_{i < j}|M_i\cap M_j| = \displaystyle\sum_{i = 1}^7 \dbinom{|C_i|}{2} = \frac {1}{2}\left (\displaystyle\sum_{i = 1}^7|C_i|^2 - \displaystyle\sum_{i = 1}^7|C_i|\right )\stackrel{\mathrm{CBS}}{\geq}\frac {1}{2}\left [\frac {1}{7}\left (\displaystyle\sum_{i = 1}^7 |C_i|\right )^2 - \displaystyle\sum_{i = 1}^7|C_i|\right] = \frac {8}{7}k^2 - 2k\] So $ \frac {8}{7}k^2 - 2k\leq k^2 - k\ \Longrightarrow\ \frac {1}{7}k^2\leq k\ \Longrightarrow\ \boxed{k\leq 7}$ We used above that $ 4k = \displaystyle\sum_{i = 1}^k |M_i| = \displaystyle\sum_{i = 1}^7 |C_i|$. As an afferent observation, I found that $ k=7$ is reachable.
\[ M_1=\{1,2,3,4\}, \ M_2=\{1,2,5,6\}, \ M_3=\{1,3,5,7\}, \ M_4=\{1,4,6,7\}, \ M_5=\{2,3,6,7\}, \ M_6=\{2,4,5,7\}, \ M_7=\{3,4,5,6\}\]
04.09.2010 20:17
Suppose that we can draw $7$ circles through our points. Then (using what i wrote above) through any point pass exactly $4$ circles. Consider a point $P$ and the $4$ circles passing through it. Note that these circles intersect each other in $6$ points. Making an inversion with pole $P$ and random power our figure maps into a complete quadrangle. It's easy to check that we cannot draw more than $2$ circles using these points. (or else there will be a circle that contains $3$ collinear points, absurd). Hence the contradiction...
15.10.2016 11:01
yeah,the answer is surely 6
05.05.2021 18:31
This is similar to Mathcamp Admissions this year lol. The answer is 6. For construction, consider the 7 points $A(0,0), B(1,1), C(1, 2), D(0,3), E(2, 1), F(2,2), G(3,0)$. Then invert about the circle with center $(-5,0)$ and radius $1$. Then the 6 circles are $A'B'C'D', A'E'F'D', A'B'E'G', A'C'F'G', B'C'E'F', D'C'E'G'$, which can be verified by noticing the original points are either cyclic are collinear. Now to prove that 6 is the maximum. I claim that each point has at most 4 circles going through it. Assume 5 circles are going through a point $P$. Inverting about $P$, we have 6 points and 5 lines with 3 points on each line, which is impossible. Hence each point has at most 4 circles going through it. Note that if all points had at most 3 circles going through it, we would have less than 6 circles, so assume there exists a point $Q$ with 4 circles going through it. Invert about $Q$. The 4 circles form a complete quadrilateral. In the 6 points that form the complete quadrilateral, there are at most 2 cyclic quadrilaterals. Hence at most 6 circles can be drawn.