Let $ A_1A_2...A_n$ be a convex polygon. Show that there exists an index $ j$ such that the circum-circle of the triangle $ A_j A_{j + 1} A_{j + 2}$ covers the polygon (here indices are read modulo n).
Problem
Source: Indian postal coaching 2008
Tags: geometry, circumcircle, induction, extremal principle, combinatorics unsolved, combinatorics
feliz
22.12.2008 05:36
Take a circle that covers the polygon and try to make it get smaller until it becomes a circumcircle of some triangle.
aakansh92
22.12.2008 12:37
I don't think that hint will work for me. I mean.... how will you show that that circle will always become some triangle's circumcircle?
gauravpatil
23.12.2008 14:07
i would say try to find a triangle (general) whose circumcircle covers the n gon and then try to create more triangles
ith_power
24.12.2008 11:53
aakansh92 wrote: Let $ A_1A_2...A_n$ be a convex polygon. Show that there exists an index $ j$ such that the circum-circle of the triangle $ A_j A_{j + 1} A_{j + 2}$ covers the polygon (here indices are read modulo n).
Prove that the biggest circle possible through any 3 vertices is
i) covering the polygon
ii) passing through three consequtive points.
both can be proved by contradiction method.
aakansh92
24.12.2008 13:59
Please be more clear and give full solution. Gaurav, could you do that problem during the postals? If yes, I am eager to look at the solution.
Agr_94_Math
24.12.2008 14:02
Aaknash, were u at the IMOTC last year?
Akashnil
24.12.2008 17:55
Here's my (not well-written ) solution. Hope you understand the idea.
I don't know if the following requires proof.
Lemma 1:
Suppose $ S$ is a circle which contains $ Y,Z$ but doesn't contain $ X$.
Then the portion of the circumference of $ S$ that lies opposite $ X$ wrt $ YZ$ lies outside the circumcircle of $ XYZ$
[geogebra]8311777ddf6748db7b929f40c8136d68ab2b9775[/geogebra]
Suppose the problem statement is true for all convex $ n$-gon for some $ n\ge 4$
(Base case $ 4$ is easy to prove)
Assume there exists a convex $ n + 1$-gon $ A_1,A_2,\cdots A_{n + 1}$ such that the statement isn't true.
By induction hypothesis on the polygon $ A_1A_2\cdots A_n$, there exists $ A_j,A_{j + 1},A_{j + 2}$ such that exactly one vertex of the polygon, $ A_{n + 1}$ lies outside their circumcircle.
By induction hypothesis on the polygon $ A_1A_2\cdots A_jA_{j + 2}\cdots A_{n + 1}$, exactly one vertex of the polygon, $ A_{j + 1}$ lies outside a circle $ S$ that has on it's circumference 3 consecutive points from the polygon.
[geogebra]a1b4053b21d62e5195188b71d634b48bdaf91f91[/geogebra]
But none of these three points lie on the same side as $ A_{j + 1}$ wrt $ A_jA_{j + 2}$. But since $ A_{j + 1}$ lies outside $ S$, by lemma 1 such three points can't lie inside the circumcircle of $ A_jA_{j + 1}A_{j + 2}$. So these 3 points must be $ A_j,A_{j + 2},A_{n + 1}$. But these are consecutive only if $ n = 3$. Which isn't true because $ n\ge 4$
Do reply if you understand or not.
feliz
24.12.2008 21:30
Ah... Sorry... When I replied, I was thinking in another problem. Akashnil, I think you should replace three of your $ A_{j + 1}$'s by $ A_{j + 2}$'s. Anyway, what is wrt?
ffao
24.12.2008 21:50
wrt = with relation to, or something similar.
Akashnil
25.12.2008 07:28
wrt=with respect to. $ A$ is opposite $ B$ wrt $ CD$ means the points $ A$ and $ B$ lie on oposite sides of the line $ CD$. Yes I messed up some of $ A_{j+1}$ and $ A_{j+2}$s . Sorry. I've edited now. Thanks. And once again do reply if you understand it now or not.
ith_power
25.12.2008 08:28
aakansh92 wrote: Please be more clear and give full solution.
Among the finitely many circles through any 3 vertices, there is a maximal one, denote it by $ \tau$.
as said earlier we prove:
1. $ \tau$ covers n-gon.
2. $ \tau$ passes through 3 consequtive vertices.
$ 1.$ Suppose point A' lies outside the maximal circle about $ \triangle ABC$ where $ A,B,C,A'$
are vertices of polygon so that they form a convex quadrilateral. Then circumcircle of $ \triangle A'BC$ has larger radius than $ \triangle ABC$. CONTRADICTION.
$ 2.$ Let $ A_i,A_j,A_k$ be vertices on the MAXIMAL circle. Let $ A_l$ lie between $ A_j \& A_k$, not on $ \tau$. Because of (1), it lies inside $ \tau$, but then circle about $ \triangle A_jA_lA_k$ is larger than maximal circumcircle. CONTRADICTION.
. please verify the solution.
ith_power
25.12.2008 08:44
Akashnil wrote: I don't know if the following requires proof. Lemma 1: Suppose $ S$ is a circle which contains $ Y,Z$ but doesn't contain $ X$. Then the portion of the circumference of $ S$ that lies opposite $ X$ wrt $ YZ$ lies outside the circumcircle of $ XYZ$ P.S.- above lemma can be easily proved since two circles(not identical) can intersect at only two points. P.P.S.- AKashnil, your proof is really very good.
Akashnil
25.12.2008 10:02
Yours too
gauravpatil
25.12.2008 18:36
those two solutions are god damn BEAUTIFUL hats off to you both ith_power and Akashnil my solution amounted to atleast 5 whole written pages in Ideas but yours(both) is just beauty
aakansh92
27.12.2008 07:28
That's really wonderfull.Thanks!
Agr_94_Math
31.12.2008 20:46
It is very unfortunate that this problem was taken from the very well known Arthur Engel book's Extremal principle chapter. Infact it is an example problem. Too bad of the problem setters in India. Anyway, akashnil's solution is superb as it is a different one . ith_power ur solution is superb as u have used the extremal principle well. I also solved it by that way and even in the book they solved it in the same way. Moderators if this is an unnecessary post sorry but just wanted to say that it was copied thats all.
gauravpatil
01.01.2009 09:47
engel does not state consecative
Agr_94_Math
01.01.2009 13:01
Enegel does state consecutive.