Does in plane exist $22$ points and $22$ such circles that each circle contains at least $7$ points and each point is on at least $7$ circles.
Clash Royale CLAN TAG#URR8PPP
up vote
8
down vote
favorite
Does in plane exist $22$ points and $22$ such circles that each circle contains at least $7$ points and each point is on at least $7$ circles. (Moldova TST 2005)
I have solved this one but now I can't remember how I did it. I just remember that I used some linear algebra and double counting.
Suppose each point $P_iin P_1,P_2,...P_22$ is on $p_igeq 7$ circles among circles $C_1,C_2,...,C_22$. Since each pair $C_i,C_j$ share at most $2$ points and each point is on $displaystylep_ichoose 2$ pair of circles, we have:
$$ 2cdot 22choose 2 geq sum _i=1^22 p_ichoose 2 geq 22 7choose 2 $$
Since we must have all equalities we deduce that $p_i = 7$ for all $i$ and each pair of circles intersect in exactly two points. Now since $$ 22cdot 7 leq sum _i=1^22 |C_i| = sum _i=1^22p_i = 22cdot 7$$
so each circle contains exactly $7$ points.
linear-algebra combinatorics contest-math
asked Oct 26 '17 at 14:17
greedoid
28k93776
 |Â
show 1 more comment
up vote
8
down vote
favorite
Does in plane exist $22$ points and $22$ such circles that each circle contains at least $7$ points and each point is on at least $7$ circles. (Moldova TST 2005)
I have solved this one but now I can't remember how I did it. I just remember that I used some linear algebra and double counting.
Suppose each point $P_iin P_1,P_2,...P_22$ is on $p_igeq 7$ circles among circles $C_1,C_2,...,C_22$. Since each pair $C_i,C_j$ share at most $2$ points and each point is on $displaystylep_ichoose 2$ pair of circles, we have:
$$ 2cdot 22choose 2 geq sum _i=1^22 p_ichoose 2 geq 22 7choose 2 $$
Since we must have all equalities we deduce that $p_i = 7$ for all $i$ and each pair of circles intersect in exactly two points. Now since $$ 22cdot 7 leq sum _i=1^22 |C_i| = sum _i=1^22p_i = 22cdot 7$$
so each circle contains exactly $7$ points.
linear-algebra combinatorics contest-math
asked Oct 26 '17 at 14:17
greedoid
28k93776
1
@user247327: a circle is the perimeter. If the interior were wanted, the term should be a disk.
– Ross Millikan
Oct 26 '17 at 18:14
2
As there are $21$ pairs of points on each circle, each pair of circles must intersect in two points. Similarly each pair of points must be on one circle. This is sounding like a projective plane to me.
– Ross Millikan
Oct 26 '17 at 18:30
1
Your solution shows that, if there is such a configuration, then each of its circles must contain exactly $7$ points and each of its points must lie on exactly $7$ circles. I am not quite sure if I would consider this as actually showing that such a configuration does exist.
– Fimpellizieri
Oct 26 '17 at 19:12
1
Ok guys, I remember the solution now. You have to make an incidence matrix $A$ and show that the determinant of $M = Acdot A^T$ is not a square (which should be) and thus such a configuration does not exist. Funny, no one like this problem though.
– greedoid
Oct 26 '17 at 19:36
1
I like it. You can write an answer yourself, this is acceptable and even encouraged.
– Ivan Neretin
Oct 26 '17 at 20:20
 |Â
show 1 more comment
up vote
8
down vote
favorite
up vote
8
down vote
favorite
Does in plane exist $22$ points and $22$ such circles that each circle contains at least $7$ points and each point is on at least $7$ circles. (Moldova TST 2005)
I have solved this one but now I can't remember how I did it. I just remember that I used some linear algebra and double counting.
Suppose each point $P_iin P_1,P_2,...P_22$ is on $p_igeq 7$ circles among circles $C_1,C_2,...,C_22$. Since each pair $C_i,C_j$ share at most $2$ points and each point is on $displaystylep_ichoose 2$ pair of circles, we have:
$$ 2cdot 22choose 2 geq sum _i=1^22 p_ichoose 2 geq 22 7choose 2 $$
Since we must have all equalities we deduce that $p_i = 7$ for all $i$ and each pair of circles intersect in exactly two points. Now since $$ 22cdot 7 leq sum _i=1^22 |C_i| = sum _i=1^22p_i = 22cdot 7$$
so each circle contains exactly $7$ points.
linear-algebra combinatorics contest-math
asked Oct 26 '17 at 14:17
greedoid
28k93776
Does in plane exist $22$ points and $22$ such circles that each circle contains at least $7$ points and each point is on at least $7$ circles. (Moldova TST 2005)
I have solved this one but now I can't remember how I did it. I just remember that I used some linear algebra and double counting.
Suppose each point $P_iin P_1,P_2,...P_22$ is on $p_igeq 7$ circles among circles $C_1,C_2,...,C_22$. Since each pair $C_i,C_j$ share at most $2$ points and each point is on $displaystylep_ichoose 2$ pair of circles, we have:
$$ 2cdot 22choose 2 geq sum _i=1^22 p_ichoose 2 geq 22 7choose 2 $$
Since we must have all equalities we deduce that $p_i = 7$ for all $i$ and each pair of circles intersect in exactly two points. Now since $$ 22cdot 7 leq sum _i=1^22 |C_i| = sum _i=1^22p_i = 22cdot 7$$
so each circle contains exactly $7$ points.
linear-algebra combinatorics contest-math
asked Oct 26 '17 at 14:17
greedoid
28k93776
edited Oct 26 '17 at 19:03
asked Oct 26 '17 at 14:17
greedoid
28k93776
asked Oct 26 '17 at 14:17
greedoid
28k93776
asked Oct 26 '17 at 14:17
greedoid
28k93776
28k93776
1
@user247327: a circle is the perimeter. If the interior were wanted, the term should be a disk.
– Ross Millikan
Oct 26 '17 at 18:14
2
As there are $21$ pairs of points on each circle, each pair of circles must intersect in two points. Similarly each pair of points must be on one circle. This is sounding like a projective plane to me.
– Ross Millikan
Oct 26 '17 at 18:30
1
Your solution shows that, if there is such a configuration, then each of its circles must contain exactly $7$ points and each of its points must lie on exactly $7$ circles. I am not quite sure if I would consider this as actually showing that such a configuration does exist.
– Fimpellizieri
Oct 26 '17 at 19:12
1
Ok guys, I remember the solution now. You have to make an incidence matrix $A$ and show that the determinant of $M = Acdot A^T$ is not a square (which should be) and thus such a configuration does not exist. Funny, no one like this problem though.
– greedoid
Oct 26 '17 at 19:36
1
I like it. You can write an answer yourself, this is acceptable and even encouraged.
– Ivan Neretin
Oct 26 '17 at 20:20
 |Â
show 1 more comment
1
@user247327: a circle is the perimeter. If the interior were wanted, the term should be a disk.
– Ross Millikan
Oct 26 '17 at 18:14
2
As there are $21$ pairs of points on each circle, each pair of circles must intersect in two points. Similarly each pair of points must be on one circle. This is sounding like a projective plane to me.
– Ross Millikan
Oct 26 '17 at 18:30
1
Your solution shows that, if there is such a configuration, then each of its circles must contain exactly $7$ points and each of its points must lie on exactly $7$ circles. I am not quite sure if I would consider this as actually showing that such a configuration does exist.
– Fimpellizieri
Oct 26 '17 at 19:12
1
Ok guys, I remember the solution now. You have to make an incidence matrix $A$ and show that the determinant of $M = Acdot A^T$ is not a square (which should be) and thus such a configuration does not exist. Funny, no one like this problem though.
– greedoid
Oct 26 '17 at 19:36
1
I like it. You can write an answer yourself, this is acceptable and even encouraged.
– Ivan Neretin
Oct 26 '17 at 20:20
1
1
@user247327: a circle is the perimeter. If the interior were wanted, the term should be a disk.
– Ross Millikan
Oct 26 '17 at 18:14
@user247327: a circle is the perimeter. If the interior were wanted, the term should be a disk.
– Ross Millikan
Oct 26 '17 at 18:14
2
2
As there are $21$ pairs of points on each circle, each pair of circles must intersect in two points. Similarly each pair of points must be on one circle. This is sounding like a projective plane to me.
– Ross Millikan
Oct 26 '17 at 18:30
As there are $21$ pairs of points on each circle, each pair of circles must intersect in two points. Similarly each pair of points must be on one circle. This is sounding like a projective plane to me.
– Ross Millikan
Oct 26 '17 at 18:30
1
1
Your solution shows that, if there is such a configuration, then each of its circles must contain exactly $7$ points and each of its points must lie on exactly $7$ circles. I am not quite sure if I would consider this as actually showing that such a configuration does exist.
– Fimpellizieri
Oct 26 '17 at 19:12
Your solution shows that, if there is such a configuration, then each of its circles must contain exactly $7$ points and each of its points must lie on exactly $7$ circles. I am not quite sure if I would consider this as actually showing that such a configuration does exist.
– Fimpellizieri
Oct 26 '17 at 19:12
1
1
Ok guys, I remember the solution now. You have to make an incidence matrix $A$ and show that the determinant of $M = Acdot A^T$ is not a square (which should be) and thus such a configuration does not exist. Funny, no one like this problem though.
– greedoid
Oct 26 '17 at 19:36
Ok guys, I remember the solution now. You have to make an incidence matrix $A$ and show that the determinant of $M = Acdot A^T$ is not a square (which should be) and thus such a configuration does not exist. Funny, no one like this problem though.
– greedoid
Oct 26 '17 at 19:36
1
1
I like it. You can write an answer yourself, this is acceptable and even encouraged.
– Ivan Neretin
Oct 26 '17 at 20:20
I like it. You can write an answer yourself, this is acceptable and even encouraged.
– Ivan Neretin
Oct 26 '17 at 20:20
 |Â
show 1 more comment
1 Answer
1
active
oldest
votes
up vote
5
down vote
As we already see in the introduction each point is on $7$ circles and each circle contains $7$ points. Also every two circles meet at $2$ points.
Let $A$ be an incident matrix, so $a_ij = 1$ if $P_j in C_i$, else $a_ij =0$. Let $M:= Acdot A^T$, then determinant of
$M$ is a perfect square: $det (M) =det (Acdot A^T)
=det A cdot det A^T =(det A)^2$. But $$ M=
beginbmatrix
7 & 2 & 2 & cdots & 2 & 2 \
2 & 7 & 2 & cdots & 2 & 2 \
2 & 2 & 7 & cdots & 2 & 2 \
vdots & vdots & vdots & cdots & vdots & vdots \
2 & 2 & 2 & cdots& 7 & 2 \
2 & 2 & 2 & cdots & 2 & 7 \
endbmatrix sim
beginbmatrix
5 & 0 & 0 & cdots & 0 & -5 \
0 & 5 & 0 & cdots & 0 & -5 \
0 & 0 & 5 & cdots & 0 & -5 \
vdots & vdots & vdots & cdots & vdots & vdots \
0 & 0 & 0 & cdots& 5 & -5 \
2 & 2 & 2 & cdots & 2 & 7 \
endbmatrix sim
beginbmatrix
5 & 0 & 0 & cdots & 0 & 0 \
0 & 5 & 0 & cdots & 0 & 0 \
0 & 0 & 5 & cdots & 0 & 0 \
vdots & vdots & vdots & cdots & vdots & vdots \
0 & 0 & 0 & cdots& 5 & 0 \
2 & 2 & 2 & cdots & 2 & 49 \
endbmatrix
$$
so $det (M)= 5^21cdot 49$ which is not a perfect square. Thus such a configuration does not exist.
answered Oct 26 '17 at 20:38
greedoid
28k93776
What is the geometric meaning of the determinant of $A$?
– Legoman
Aug 29 at 8:58
I'm not aware of that.
– greedoid
Aug 29 at 9:01
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
As we already see in the introduction each point is on $7$ circles and each circle contains $7$ points. Also every two circles meet at $2$ points.
Let $A$ be an incident matrix, so $a_ij = 1$ if $P_j in C_i$, else $a_ij =0$. Let $M:= Acdot A^T$, then determinant of
$M$ is a perfect square: $det (M) =det (Acdot A^T)
=det A cdot det A^T =(det A)^2$. But $$ M=
beginbmatrix
7 & 2 & 2 & cdots & 2 & 2 \
2 & 7 & 2 & cdots & 2 & 2 \
2 & 2 & 7 & cdots & 2 & 2 \
vdots & vdots & vdots & cdots & vdots & vdots \
2 & 2 & 2 & cdots& 7 & 2 \
2 & 2 & 2 & cdots & 2 & 7 \
endbmatrix sim
beginbmatrix
5 & 0 & 0 & cdots & 0 & -5 \
0 & 5 & 0 & cdots & 0 & -5 \
0 & 0 & 5 & cdots & 0 & -5 \
vdots & vdots & vdots & cdots & vdots & vdots \
0 & 0 & 0 & cdots& 5 & -5 \
2 & 2 & 2 & cdots & 2 & 7 \
endbmatrix sim
beginbmatrix
5 & 0 & 0 & cdots & 0 & 0 \
0 & 5 & 0 & cdots & 0 & 0 \
0 & 0 & 5 & cdots & 0 & 0 \
vdots & vdots & vdots & cdots & vdots & vdots \
0 & 0 & 0 & cdots& 5 & 0 \
2 & 2 & 2 & cdots & 2 & 49 \
endbmatrix
$$
so $det (M)= 5^21cdot 49$ which is not a perfect square. Thus such a configuration does not exist.
answered Oct 26 '17 at 20:38
greedoid
28k93776
What is the geometric meaning of the determinant of $A$?
– Legoman
Aug 29 at 8:58
I'm not aware of that.
– greedoid
Aug 29 at 9:01
add a comment |Â
up vote
5
down vote
As we already see in the introduction each point is on $7$ circles and each circle contains $7$ points. Also every two circles meet at $2$ points.
Let $A$ be an incident matrix, so $a_ij = 1$ if $P_j in C_i$, else $a_ij =0$. Let $M:= Acdot A^T$, then determinant of
$M$ is a perfect square: $det (M) =det (Acdot A^T)
=det A cdot det A^T =(det A)^2$. But $$ M=
beginbmatrix
7 & 2 & 2 & cdots & 2 & 2 \
2 & 7 & 2 & cdots & 2 & 2 \
2 & 2 & 7 & cdots & 2 & 2 \
vdots & vdots & vdots & cdots & vdots & vdots \
2 & 2 & 2 & cdots& 7 & 2 \
2 & 2 & 2 & cdots & 2 & 7 \
endbmatrix sim
beginbmatrix
5 & 0 & 0 & cdots & 0 & -5 \
0 & 5 & 0 & cdots & 0 & -5 \
0 & 0 & 5 & cdots & 0 & -5 \
vdots & vdots & vdots & cdots & vdots & vdots \
0 & 0 & 0 & cdots& 5 & -5 \
2 & 2 & 2 & cdots & 2 & 7 \
endbmatrix sim
beginbmatrix
5 & 0 & 0 & cdots & 0 & 0 \
0 & 5 & 0 & cdots & 0 & 0 \
0 & 0 & 5 & cdots & 0 & 0 \
vdots & vdots & vdots & cdots & vdots & vdots \
0 & 0 & 0 & cdots& 5 & 0 \
2 & 2 & 2 & cdots & 2 & 49 \
endbmatrix
$$
so $det (M)= 5^21cdot 49$ which is not a perfect square. Thus such a configuration does not exist.
answered Oct 26 '17 at 20:38
greedoid
28k93776
What is the geometric meaning of the determinant of $A$?
– Legoman
Aug 29 at 8:58
I'm not aware of that.
– greedoid
Aug 29 at 9:01
add a comment |Â
up vote
5
down vote
up vote
5
down vote
As we already see in the introduction each point is on $7$ circles and each circle contains $7$ points. Also every two circles meet at $2$ points.
Let $A$ be an incident matrix, so $a_ij = 1$ if $P_j in C_i$, else $a_ij =0$. Let $M:= Acdot A^T$, then determinant of
$M$ is a perfect square: $det (M) =det (Acdot A^T)
=det A cdot det A^T =(det A)^2$. But $$ M=
beginbmatrix
7 & 2 & 2 & cdots & 2 & 2 \
2 & 7 & 2 & cdots & 2 & 2 \
2 & 2 & 7 & cdots & 2 & 2 \
vdots & vdots & vdots & cdots & vdots & vdots \
2 & 2 & 2 & cdots& 7 & 2 \
2 & 2 & 2 & cdots & 2 & 7 \
endbmatrix sim
beginbmatrix
5 & 0 & 0 & cdots & 0 & -5 \
0 & 5 & 0 & cdots & 0 & -5 \
0 & 0 & 5 & cdots & 0 & -5 \
vdots & vdots & vdots & cdots & vdots & vdots \
0 & 0 & 0 & cdots& 5 & -5 \
2 & 2 & 2 & cdots & 2 & 7 \
endbmatrix sim
beginbmatrix
5 & 0 & 0 & cdots & 0 & 0 \
0 & 5 & 0 & cdots & 0 & 0 \
0 & 0 & 5 & cdots & 0 & 0 \
vdots & vdots & vdots & cdots & vdots & vdots \
0 & 0 & 0 & cdots& 5 & 0 \
2 & 2 & 2 & cdots & 2 & 49 \
endbmatrix
$$
so $det (M)= 5^21cdot 49$ which is not a perfect square. Thus such a configuration does not exist.
answered Oct 26 '17 at 20:38
greedoid
28k93776
As we already see in the introduction each point is on $7$ circles and each circle contains $7$ points. Also every two circles meet at $2$ points.
Let $A$ be an incident matrix, so $a_ij = 1$ if $P_j in C_i$, else $a_ij =0$. Let $M:= Acdot A^T$, then determinant of
$M$ is a perfect square: $det (M) =det (Acdot A^T)
=det A cdot det A^T =(det A)^2$. But $$ M=
beginbmatrix
7 & 2 & 2 & cdots & 2 & 2 \
2 & 7 & 2 & cdots & 2 & 2 \
2 & 2 & 7 & cdots & 2 & 2 \
vdots & vdots & vdots & cdots & vdots & vdots \
2 & 2 & 2 & cdots& 7 & 2 \
2 & 2 & 2 & cdots & 2 & 7 \
endbmatrix sim
beginbmatrix
5 & 0 & 0 & cdots & 0 & -5 \
0 & 5 & 0 & cdots & 0 & -5 \
0 & 0 & 5 & cdots & 0 & -5 \
vdots & vdots & vdots & cdots & vdots & vdots \
0 & 0 & 0 & cdots& 5 & -5 \
2 & 2 & 2 & cdots & 2 & 7 \
endbmatrix sim
beginbmatrix
5 & 0 & 0 & cdots & 0 & 0 \
0 & 5 & 0 & cdots & 0 & 0 \
0 & 0 & 5 & cdots & 0 & 0 \
vdots & vdots & vdots & cdots & vdots & vdots \
0 & 0 & 0 & cdots& 5 & 0 \
2 & 2 & 2 & cdots & 2 & 49 \
endbmatrix
$$
so $det (M)= 5^21cdot 49$ which is not a perfect square. Thus such a configuration does not exist.
answered Oct 26 '17 at 20:38
greedoid
28k93776
edited Aug 29 at 8:56
answered Oct 26 '17 at 20:38
greedoid
28k93776
answered Oct 26 '17 at 20:38
greedoid
28k93776
answered Oct 26 '17 at 20:38
greedoid
28k93776
28k93776
What is the geometric meaning of the determinant of $A$?
– Legoman
Aug 29 at 8:58
I'm not aware of that.
– greedoid
Aug 29 at 9:01
add a comment |Â
What is the geometric meaning of the determinant of $A$?
– Legoman
Aug 29 at 8:58
I'm not aware of that.
– greedoid
Aug 29 at 9:01
What is the geometric meaning of the determinant of $A$?
– Legoman
Aug 29 at 8:58
What is the geometric meaning of the determinant of $A$?
– Legoman
Aug 29 at 8:58
I'm not aware of that.
– greedoid
Aug 29 at 9:01
I'm not aware of that.
– greedoid
Aug 29 at 9:01
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2490876%2fdoes-in-plane-exist-22-points-and-22-such-circles-that-each-circle-contains%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
@user247327: a circle is the perimeter. If the interior were wanted, the term should be a disk.
– Ross Millikan
Oct 26 '17 at 18:14
2
As there are $21$ pairs of points on each circle, each pair of circles must intersect in two points. Similarly each pair of points must be on one circle. This is sounding like a projective plane to me.
– Ross Millikan
Oct 26 '17 at 18:30
1
Your solution shows that, if there is such a configuration, then each of its circles must contain exactly $7$ points and each of its points must lie on exactly $7$ circles. I am not quite sure if I would consider this as actually showing that such a configuration does exist.
– Fimpellizieri
Oct 26 '17 at 19:12
1
Ok guys, I remember the solution now. You have to make an incidence matrix $A$ and show that the determinant of $M = Acdot A^T$ is not a square (which should be) and thus such a configuration does not exist. Funny, no one like this problem though.
– greedoid
Oct 26 '17 at 19:36
1
I like it. You can write an answer yourself, this is acceptable and even encouraged.
– Ivan Neretin
Oct 26 '17 at 20:20