Let 
be positive reals such that 
.
be an acute triangle. Denote by 
the foot of the perpendicular line drawn from the point 
to the side 
,
the midpoint of 
the orthocenter of 
be the point of intersection of the circumcircle 
of the triangle 
,
be the point of intersection (other than 
)
and the circle 
must hold.
the length of the line segment 
,
for 
,
form a geometric progression in some order.
such that![$$\left(a+b+c+d-K\right)^2+2\left[1-\left(3\sqrt2-4\right)K\right]abcd\geq\left(3\sqrt2-K\right)^2$$](http://latex.artofproblemsolving.com/3/5/3/35382fd52c29efa5185d1b9fbeef944a0fd2fee3.png)
for all 
satisfying
Y by Purple_Planet, Adventure10, Mango247
Define a 
-clique to be a set of people such that every pair of them are acquainted with each other. At a certain party, every pair of 3-cliques has at least one person in common, and there are no 5-cliques. Prove that there are two or fewer people at the party whose departure leaves no 3-clique remaining.
-clique to be a set of people such that every pair of them are acquainted with each other. At a certain party, every pair of 3-cliques has at least one person in common, and there are no 5-cliques. Prove that there are two or fewer people at the party whose departure leaves no 3-clique remaining.Attachments:
This post has been edited 2 times. Last edited by orl, Dec 22, 2008, 1:12 AM
s.t. 
.
as a vertex have their vertices among 
.
as a vertex, and the same holds for 
,
is a 
,
(for example) s.t. 
.
or 
as vertices. After noticing that 
can't be edges, we can see that the only way this can happen is to have another vertex 
and triangles 
.
,
and 
sharing edge 
.
and 
,
,
and 
.
,
,
are connected.
,
,
,
is a 5-clique, which is a contradiction. Therefore, no two triangles can share an edge.
;
and 
,
and 
.
and 
will share edge 
,
belonging in this 3-clique. This 3-clique cannot be disjoint with 
,
,
and 
sharing edge 
,
denote the assertion that there must exist a triangle not containing either of 
and 
for a triangle 
denote the assertion that each triangle in 
must contain at least one of 
.
force the existence of triangle 
.
,
is an edge, and from 
,
must be an edge. Finally, 
together imply that 
must be a triangle, so 
such that 
and 
are both 3-cliques. Remove persons 
and 
Then, there exists a person 
such that 
forms a 3-clique (if there are no 3-cliques remaining, we are done; furthermore, this 3-clique must share some person with the 3-cliques 
and 
(add 
again). A similar argument shows that this forces 
to be a 3-clique. Hence, 
forms a 5-clique, contradiction. We hereby assume any two 3-cliques share exactly one person.
such that 
we easily see that there exists a person 
such that 
and 
are both 3-cliques, where 
This contradicts our first paragraph, so we're done. 
.
,
,
be the triangles that are jointed to 
,
,
.
,
connected by a hinge because the hinge would have to be common.
,
.
or they would all have a common hinge, so WLOG 
and 
.
and 
that are disjoint, a contradiction.
,
,
.
are disjoint, a contradiction.
,
.
,
as a vertex must be of the form 
,
,
,
.
since that would be disjoint from 
then it's disjoint from 
,
then 
is a 
and 
(here all lettered vertices are assumed to be distinct). Since 
can't be a 
is not an edge. WLOG, assume 
is not an edge.
such that 
and 
are triangles.
that doesn't contain 
and 
,
is an edge of 
as an edge, then we could simply delete 
as an edge. Now those two triangles must intersect at one vertex, call it 
was a vertex such that 
and 
were triangles. But then 
.
from becoming 
is not an edge. We claim that every other triangle must have either 
.
.
t
and 
t
t
,
and 
t
,
,
.
are not all the same vertex; wlog 
.
.
is a triangle. Now, assume neither of 
is 
;
,
.
.
.
,
,
are triangles. Assume wlog an 
.
;
.
is adyacent to 
,
is a 5-clique, a contradiction.
-
.
share a common neighbour. Suppose 
is that pair, with the common neighbour 
.
and 
(even if they don't share a common neighbour). We claim that now no triangles exist. Suppose a triangle still remains; then it must contain 
or 
.
be a triangle, where 
.
and 
(before the removal) don't share any common vertex, contradiction.
and 
.
was a triangle. But then the triangles 
didn't share a common vertex before the removal - contradiction.
which share the common vertex 
or 
as sides. But it must have one of 
as sides. However, then 
,
is a 4-clique for some vertices 
.
.
.
cannot be a triangle, since otherwise 
would be a 5-clique. Hence, any new triangle must have one vertex be 
,
leaves us with no triangles, contradiction. 
and 
existed for some vertices 
.
is not an edge, else 
would be a 4-clique. Now, any other triangle must have one vertex be 
and 
are triangles and share vertex 
of possible edges. Suppose one of these is an edge, WLOG 
.
,
,
to win. So 
.
and 
,
-
-
We must have some triangle that does not have 
- we want to show that ![[asy]
size(4cm);
pair A=(0,5);
pair B=(-2,2);
pair C=(2,2);
pair D=(-1,1);
pair E=(1,1);
dot("$A$",A,N);
dot("$B$",B,W);
dot("$C$",C,E);
dot("$D$",D,SW);
dot("$E$",E,SE);
draw (A--B--C--A);
draw (A--D--E--A,blue);
[/asy]](http://latex.artofproblemsolving.com/e/5/1/e5147351a18a5e5ead24377c7e79fb9b1b7de636.png)
so we need some triangle without 
and 
because all triangles have a common vertex. Without loss of generality, say that it touches 
and we have a triangle 
for some random (and irrelevant) point 
Since 
is an edge, this means that 
is a triangle too.![[asy]
size(4cm);
pair A=(0,5);
pair B=(-2,2);
pair C=(2,2);
pair D=(-1,1);
pair E=(1,1);
dot("$A$",A,N);
dot("$B$",B,W);
dot("$C$",C,E);
dot("$D$",D,SW);
dot("$E$",E,SE);
draw (A--B--C--A);
draw (A--D--E--A);
draw (C--E,blue);
[/asy]](http://latex.artofproblemsolving.com/f/f/3/ff3402abce727eee3df38060957db92d569ba3c1.png)
so we must construct some triangle that does not have 
.
are not common vertices.![[asy]
size(4cm);
pair A=(0,5);
pair B=(-2,2);
pair C=(2,2);
pair D=(-1,1);
pair E=(1,1);
dot("$A$",A,N);
dot("$B$",B,W);
dot("$C$",C,E);
dot("$D$",D,SW);
dot("$E$",E,SE);
draw (A--B--C--A);
draw (A--D--E--A);
draw (C--E);
draw (E--B--D,blue);
[/asy]](http://latex.artofproblemsolving.com/d/f/1/df10a0558ca8d40ea6746f1e27189289c27020b5.png)
So we must have a triangle without those vertices. Also note that our final triangle must have 
it must have 
and it must have 
So ![[asy]
size(4cm);
pair A=(0,5);
pair B=(-2,2);
pair C=(2,2);
pair D=(-1,1);
pair E=(1,1);
dot("$A$",A,N);
dot("$B$",B,W);
dot("$C$",C,E);
dot("$D$",D,SW);
dot("$E$",E,SE);
draw (A--B--C--A);
draw (A--D--E--A);
draw (C--E);
draw (E--B--D);
draw (C--D,blue);
[/asy]](http://latex.artofproblemsolving.com/4/4/0/440b91296d8ca1e51802ac692963969c4ef32e58.png)
,
is connected.
,
is connected.
is connected.
.
and 
doesn't work, there must exist a triangle not containing either; then the triangle must contain 
.
or 
.
or 
.
must be 
must be 
,
,
,
and because we find that each of 
points. Then, the graph will have a 
vertex. Let 
and 
be the non-shared vertex besides 
and it doesn't have 
,
,
cannot be edges since otherwise there would be a 
.
.
and the one with 
must also include a vertex besides 
and 
must share a vertex with 
,
If there is only one clique the problem is trivial.
and 
Now, removing 
would break every 3-clique unless there is 3-clique that contains neither 
nor 
Then this clique must contain both 
and 
Let this clique be 
Now, we claim that removing 
does the job. If any 3-clique remains, it must contain 
which creates a 5-clique, a contradiction.
We claim: removing 
or 
or 
WLOG, let it have 
is a 3-clique. However, that creates two 3-cliques that share two people, so we're done by the previous part.
two people when upon departing leaves behind a 
.
arrive once more, we have the following subsequent 
,
-
.
,
,
,
such that 
,
,
,
,
,
that don't have a common vertex. Then consider 
,
,
.
and 
,
is a 
,
,
,
.
,
,
and 
are two disjoint triangles, contradiction.
.
.
are two disjoint triangles, contradiction.
has one point, apply the previous claim to 
,
,
.
,
or 
.
is a 
for which 
,
,
.
for which 
,
or 
.
for which 
and 
,
,
,
intersects one of 
,
for which 
for which 
.
.
for some 
.
are all pairwise distinct. Now, note that there exists a triangle 
for which 
,
,
is thus a 
.
for some vertex 
.
for which 
,
since 
is a 
be a 
.
for which 
.
is a triangle, 
.
are not in 
for some vertex 
not equal to 
,
.
is a triangle, we have that 
.
and 
ia a triangle, we have that 
,
,
and 
is a 
.
.
or 
However, since 
we can say that every 3 clique contains either 
so the deletion of those vertices result in no 3-cliques remaining.
There exists a point that forms the 3-clique with 
Note that 
By similar logic to case 1, every 3-clique contains 
so our induction is complete.
.
cannot exist (or else there is a 
and 
we know 
,
can't be a 
.
,
,
,
for some 
.
and 
exists, notice that all remaining triangles include one of the vertices 
or 
.
due to the problem condition. We now also remove 
,
,
must be a side in the triangle. In the former case, 
is a 
is a 
-
,
,
,
,
and 
such that 
,
and 
are all 
also is a 
,
or 
are acquainted, which creates a 
,
still, it must be 
,
and 
.
and we obviously want to remove B. Now assume that there still exist some triangles after removing B. Then they must be some of 
,
,
,
for a vertex P. Now if at most one from the pairs of 
and 
exists, we have that all remaining triangles have one of A, C, N, M as their vertex. If not, WLOG assume that there still exist 
and it is obvious that 
.
there are no triangles left and we are ready.
be the assertion that there exists a 3-clique not using 
similarly.
.
we can define a second 3-clique 
,
.
exists.
is missing all but one edge (WLOG 
)
and the 3-cliques 
and 
we find there exists a 3-clique using 
,
to obtain that 
is a 5-clique, a contradiction. 
.
If we add any other triangle, it must pass through 
First assume the triangle doesn't pass through any of those points. Then we must have the triangle be 
,
)
because that creates a 
to be removed.
.
because this violates the claim that no two triangles share an edge. Thus, we must have all triangles intersect at 
be the vertices.
Any additional triangle must have exactly 
there must be some triangle with 
But picking 
we must have a triangle 
Thus as these triangles must share a vertex 
But then 
is a 
and 
Remove 
then there must be another triangle not containing 
Then all other triangle have a vertice among 
and among 
Since there is no 
is a triangle, then we cannot connect 
and 
Thus if we have a triangle involving 
for it to share a vertex with 
yields a contradiction. But if it does not exist, all other triangles involve only 
works.
are triangles. Removing 
If any two of the vertices are connected, e.g. 
then all other vertices are connected to those two. By removing those, our claim is true. Thus, each triangle is connected through a single vertex. This clearly works.
