trigonometry
geometry
cyclic quadrilateral
geometry proposed

[u][b]The author of this posting is : darkmaster (edited by Darij Grinberg)[/b][/u]
____________________________________________________________________

Given a circle (O) with center O, a fixed diameter CD of this circle (O), and two points A and B which don't lie in (O).
Construct the point M on the circle (O) such that, if the lines AM and BM intersect the circle (O) at the points P and Q, respectively (apart from the points A and B), then the line PQ is perpendicular to the line CD.

Let's get rid of assumptions we won't need: At first, we rename the circle (O) into k (just because k is shorter and because we won't need the center O of the circle (O) anywhere). Then, we note that the line CD only plays the role of a fixed line. Demanding that the line PQ is perpendicular to the line CD means simply demanding the line PQ to have a given direction. In other words, if we call g an arbitrary line perpendicular to the line CD, then the line PQ is perpendicular to the line CD if and only if the line PQ is parallel to the line g. Hence, the problem comes down to finding the point M on the circle k such that the line PQ is parallel to the line g. Hence we get the following simplified version of the problem:

[i]Given a circle k, a fixed line g, and two points A and B which don't lie in k.
Construct the point M on the circle k such that, if the lines AM and BM intersect the circle k at the points P and Q, respectively (apart from the points A and B), then the line PQ is parallel to the line g.[/i]

In fact, generally, there are two points M on the circle k such that the line PQ is perpendicular to the line CD. In the following, I will construct all of these points, but still I will speak about "the point M" in order to simplify the argumentation.

We will work with directed angles modulo 180. First let's discuss some preliminaries about angles between circles and angles between a line and a circle:

If two circles k and k' intersect at two points U and V, then there is no "directed angle between the circles k and k' ". Instead, there is a [b]directed angle between the circles k and k' at the point U[/b], which is is defined as the directed angle < (u; u'), where u and u' are the tangents to the circles k and k' at the point U, and the [b]directed angle between the circles k and k' at the point V[/b], which is defined as the directed angle < (v; v'), where v and v' are the tangents to the circles k and k' at the point V. In general, the two directed angles between the circles k and k' at the points U and V are not equal, but they are oppositely equal (i. e., we have < (u; u') = - < (v; v')). Hence, we cannot say that the circles k and k' intersect at the angle < (u; u') or that they intersect at the angle < (v; v'); we must say that the circles k and k' intersect at the angles < (u; u') and < (v; v') (which are oppositely equal to each other). In other words, one has to be careful when speaking of the "angle between two circles": such an angle is well-defined only if it is non-directed; when speaking of directed angles between two circles, one must always specify at which of their points of intersection the angle is measured.

Similarly, we can define the angles between a circle and a line: If a circle k intersects a line l at two points U and V, then we define the [b]directed angle between the circle k and the line l at the point U[/b] as the angle < (u; l), where u is the tangent to the circle k at the point U, and the [b]directed angle between the circle k and the line l at the point V[/b] as the angle < (v; l), where v is the tangent to the circle k at the point V. Again, the angles at the points U and V are oppositely equal, and thus, in order to have a well-defined directed angle between a circle and a line, we have to specify which of the points of intersection we take.

Now let's come to the solution of the problem:

The angle t = < (AB; g) is a fixed angle (since the lines AB and g are fixed lines).

The points M, P, Q lie on the circle k. Let n be the circle through the points M, A, B. Then, the directed angle w between the circles k and n at the point M equals < (i; j), where i and j are the tangents to the circles k and n at the point M. Now, < (i; j) = < (AM; j) - < (AM; i). By the tangent-chord angle theorem, < (AM; j) = < ABM and < (PM; i) = < PQM; the latter equation can be rewritten as < (AM; i) = < PQM. Thus,

  w = < (i; j) = < (AM; j) - < (AM; i) = < ABM - < PQM
      = < (AB; BM) - < (PQ; BM) = < (AB; PQ).

Now, our goal is to construct the point M on the circle k satisfying PQ || g. But of course, PQ || g holds if and only if < (AB; PQ) = < (AB; g). Now, < (AB; PQ) = w, as we know, and < (AB; g) = t is a fixed angle. Hence, our problem is to construct the point M on the circle k for which the angle w (remember that this is the angle between the circles k and n at the point M) equals the fixed angle t. Now, this is the key to the solution - in fact, it is just enough to construct the circle n which passes through the points A and B and which intersects the circle k at the angles t and -t (as I have said before, the sign of the directed angle of two circles depends on the choice of their point of intersection), construct the two points of intersection of the circles k and n, pick the one of them at which the angle between the circles k and n is t (and not -t), and call this point M; then the problem will be solved.

Hence, we have reduced our problem to the following, more fundamental problem:

[i]Given a circle k, two points A and B and an angle t, construct the circle n which passes through the points A and B and which intersects the circle k at the angles t and -t.[/i]

This problem is again substantially simplified by an inversion; in fact, an inversion with inversion center B maps the circle n (which passes through the point B) to a line, and since inversions preserve angles (changing their orientation, but this is not important here since we have the angles t and -t which are oppositely equal to each other), it remains to solve the following problem:

[i]Given a circle k, a point A and an angle t, construct the line n which passes through the point A and which intersects the circle k at the angles t and -t.[/i]

But this is very easy. In fact, call X and Y the points of intersection of the line n with the circle k such that the angle between the circle k and the line n at the point X equals t and the angle between the circle k and the line n at the point Y equals -t. Then, by the definition of the angle between a circle and a line, we have < (x; n) = t, where x is the tangent to the circle k at the point X. If Z is the center and r is the radius of the circle k, then we have ZX = r on one hand, and $ZX\perp x$ on the other hand (since the line x is the tangent to k at X). Thus, < (ZX; x) = 90, and hence,

  < (ZX; n) = < (ZX; x) + < (x; n) = 90 + < (x; n) = 90 + t.

If V is the orthogonal projection of the point Z on the line n, then, in the right-angled triangle ZVX, we have

  $ZV = ZX\cdot \sin\angle VXZ = ZX\cdot \sin\left|\measuredangle\left(ZX;\;n\right)\right| = r\cdot \sin\left|90^{\circ}+t\right|$

(hereby, the angle $\angle VXZ$ is non-directed, while the angle < (ZX; n) is directed; this is why we use the modulus sign).

In other words, the distance from the point Z to the line n is $r\cdot \sin\left|90^{\circ}+t\right|$. This means that the line n touches the circle z with center Z and radius $r\cdot \sin\left|90^{\circ}+t\right|$; since the line n passes through the point A, it is thus a tangent from the point A to the circle z. Thus we have shown: Every line n which passes through the point A and which intersects the circle k at the angles t and -t is a tangent from the point A to the circle z. (Note that the circle z is a fixed circle that we can easily construct.)

Conversely, it may be shown that every of the two tangents from the point A to the circle z intersects the circle k at the angles t and -t (for the proof, just redo the above argumentation backwards). Hence, in order to construct the lines n which pass through the point A and which intersect the circle k at the angles t and -t, we just have to draw the tangents from the point A to the circle z. This solves our problem and explains why there are two solutions (namely this is because there are two tangents from the point A to the circle z; hereby, I leave out the degenerate cases when the two tangents coincide).

The problem is solved...

  Darij

Oh , your solution is very complicated !!  ;)  ;)
 I have one solution for the general problem :
  Given a circle (O) with center O and two points A and B which don't lie in (O).
Construct the point M on the circle (O) such that, if the lines AM and BM intersect the circle (O) at the points P and Q, respectively , then PQ is parallel with the fixed line d .

   Erect $ QN //  AB $ , $ N \in (O) $ . $ PN $  :cap:  $ AB $ at C . We will prove C is fixed .
  It's easy to show PMCB is a cyclic quadrilateral . So $ AC. AB = AM . AP = P(A/(O)) = const $
  So C is fixed .
  It's easy to show $ <PQN $ is invariable ==> PN is invariable
  From C , we have the invariable chord PN  ....
  The problem finish !!

Very nice! Now, I am just seeing that your solution has much in common with mine.

Let's look:

[quote="nttu"]  It's easy to show PMCB is a cyclic quadrilateral . So $ AC. AB = AM . AP = P(A/(O)) = const $[/quote]

Now, of course, this means that the inversion with respect to the circle centered at A and having radius $\sqrt{AC\cdot AB}=\sqrt{AM\cdot AP}$ maps the point B to the point C and leaves the circle k = (O) fixed. My solution inverts with respect to B, but this is actually quite the same thing :D . And the problem reduces to drawing a line through the point C which intercepts on the circle k a chord of given length. This is equivalent to drawing a line through the point C which intersects the circle k at a given angle. That's what I did!

But you actually did everything in a simpler and more beautiful way. Well done!

  Darij


limit
logarithms
integration
real analysis
real analysis unsolved

Let sequence $ a_n$ and
$ A_n\equal{}\frac{a_1\plus{}a_2\plus{}a_3\plus{}....\plus{}a_n}{n}$
Prove that if $ \lim_{n\to\infty}A_{n}\equal{}A$ then $ \lim\frac{1}{\ln{n}}\sum^n_{k\equal{}1}\frac{a_k}{k}\equal{}A$

[quote="Algadin"]Let sequence $ a_n$ and
$ A_n \equal{} \frac {a_1 \plus{} a_2 \plus{} a_3 \plus{} .... \plus{} a_n}{n}$
Prove that if $ \lim_{n\to\infty}A_{n} \equal{} A$ then $ \lim\frac {1}{\ln{n}}\sum^n_{k \equal{} 1}\frac {a_k}{k} \equal{} A$[/quote]

$ \forall n>1$ : $ a_n\equal{}nA_n\minus{}(n\minus{}1)A_{n\minus{}1}$ and so $ \frac{a_n}n\equal{}A_n\minus{}A_{n\minus{}1}\plus{}\frac{A_{n\minus{}1}}n$

So $ \frac 1{\ln(n)}\sum_{k\equal{}1}^n\frac{a_k}k$ $ \equal{}\frac 1{\ln(n)}(a_1\plus{}$ $ \sum_{k\equal{}2}^n(A_k\minus{}A_{k\minus{}1})\plus{}$ $ \sum_{k\equal{}2}^n\frac{A_{k\minus{}1}}k)$

$ \implies$ $ \frac 1{\ln(n)}\sum_{k\equal{}1}^n\frac{a_k}k$ $ \equal{}\frac 1{\ln(n)}(A_n\plus{}\sum_{k\equal{}2}^n\frac{A_{k\minus{}1}}k)$

And, since $ \lim_{n\to\plus{}\infty}A_n\equal{}A$ :

1) $ \exists M$ such that $ \minus{}M<A_n<M$ $ \forall n$
2) $ \forall \epsilon>0 \exists n_{\epsilon}$ such that $ n>n_{\epsilon}$ $ \implies$ $ A\minus{}\epsilon<A_n<A\plus{}\epsilon$ and so :

$ \minus{}\frac{n_{\epsilon}M}{\ln(n)}\plus{}$ $ \frac{A\minus{}\epsilon}{\ln(n)}\int_{n_{\epsilon}\plus{}1}^{n\plus{}1}\frac {dx}x<$ $ \frac 1{\ln(n)}\sum_{k\equal{}1}^n\frac{a_k}k$ $ <\frac{n_{\epsilon}M}{\ln(n)}\plus{}$ $ \frac{A\plus{}\epsilon}{\ln(n)}\int_{n_{\epsilon}}^{n}\frac {dx}x$

and so :
$ \minus{}\frac{n_{\epsilon}M}{\ln(n)}\plus{}$ $ (A\minus{}\epsilon)\frac{\ln(n\plus{}1)\minus{}\ln(n_{\epsilon}\plus{}1)}{\ln(n)}<$ $ \frac 1{\ln(n)}\sum_{k\equal{}1}^n\frac{a_k}k$ $ <\frac{n_{\epsilon}M}{\ln(n)}\plus{}$ $ (A\plus{}\epsilon)\frac{\ln(n)\minus{}\ln(n_{\epsilon})}{\ln(n)}$

And so $ A\minus{}\epsilon \le$ $ \lim_{n\to\plus{}\infty}\frac 1{\ln(n)}\sum_{k\equal{}1}^n\frac{a_k}k$ $ \le A\plus{}\epsilon$

Hence the result.


Find out x,y natural if sqrt(x+sqrt(x))=y.

spoiler:

[hide]clearly the solution (0,0) works, so lets assume x>0.  Then we have that x + :sqrt: x = y^2, and because y^2 is a positive integer, x must be a square, so let x = k^2 with k > 0, then we have k^2+k=y^2 or equivalently, k*(k+1)=y^2.  Now, k and k+1 are relatively prime, so if their product is a square, each must be a square, but there are no consecutive squares with k>0, so there is no solution for positive x,y and (0,0) is the only solution.

[/hide]


geometry
circumcircle
incenter
angle bisector
geometry unsolved

[quote="hattieu"][quote="plane geometry"]1.G is the centroid of △ABC , O1,O2,O3 are centroid of △GBC, △GAC,△GAB
O is the circumcenter of △ABC
Prove:O is the centroid of △ O1O2O3
2. i is the incenter of △ABC ,G1,G2,G3 are centroid of △IBC, △IAC,△IAB
G is the centroid of △ABC
Prove:G is the incenter of △ G1G2G3
3.G is the centroid of △ABC,H1,H2,H3 are orthocenter of △GBC, △GAC,△GAB
H is the orthocenter of △ABC
Prove:H is the centroid of △H1H2H3[/quote]
#1 O1,O2,O3 should be circumcenter of GBC, GAC and GAB[/quote]
yes,I am sorry
edited

[quote="plane geometry"]1.G is the centroid of △ABC , O1,O2,O3 are circumcenter of △GBC, △GAC,△GAB
O is the circumcenter of △ABC
Prove:O is the centroid of △ O1O2O3
2. i is the incenter of △ABC ,G1,G2,G3 are centroid of △IBC, △IAC,△IAB
G is the centroid of △ABC
Prove:G is the incenter of △ G1G2G3
3.G is the centroid of △ABC,H1,H2,H3 are orthocenter of △GBC, △GAC,△GAB
H is the orthocenter of △ABC
Prove:H is the centroid of △H1H2H3[/quote]

I have seen these problems in a book about triangle geometry. But they are all be solved by vertorial method  :(
I hope that someone find out synthetic proofs for all these problems.  :)

[quote="plane geometry"][b][size=100]PROBLEM 1.[/size][/b] - $ G$ is the centroid of $ \bigtriangleup ABC$ and $ O_{1},\ O_{2},\ O_{3}$ are circumcenters of $ \bigtriangleup GBC,\ \bigtriangleup GAC,\ \bigtriangleup GAB.$ $ O,$ is the circumcenter of $ \bigtriangleup ABC.$ Prove that $ O$  is the centroid of $ \bigtriangleup O_{1}O_{2}O_{3}.$[/quote]
We can solve this problem, as a direct application of the follows Lemma:

[b][size=100][color=DarkBlue]LEMMA. - Let $ \bigtriangleup ABC,\ \bigtriangleup A'B'C'$ be, two triangles orthologic with respect to each other, such that the centroid $ G$ of $ \bigtriangleup ABC,$ is coincided with its orthologic center with respect to $ \bigtriangleup A'B'C'.$ Prove that the centroid $ G'$ of $ \bigtriangleup A'B'C',$ is coincided with its orthologic center with respect to $ \bigtriangleup ABC.$[/color][/size][/b]

So, because of the mid-perpendiculars of $ BC,\ AC,\ AB,$ pass through the points $ O_{1},\ O_{2}.\ O_{3}$ respectively, based on the above [b][size=100]Lemma[/size][/b], we conclude that their concurrency point $ O,$ as the circumcenter of $ \bigtriangleup ABC$ and also as the orthologic center of $ \bigtriangleup O_{1}O_{2}O_{3}$ with respect to $ \bigtriangleup ABC,$ is coincided with the centroid of $ \bigtriangleup O_{1}O_{2}O_{3}$ and we are done.

Kostas Vittas.

PS. I will check more carefully my notes about the [b][size=100]Lemma[/size][/b] and if I am not mistaken, I will post here later its proof I have in mind.

[quote="vittasko"][b][size=100][color=DarkBlue]LEMMA. - Let $ \bigtriangleup ABC,\ \bigtriangleup A'B'C'$ be, two triangles orthologic with respect to each other, such that the centroid $ G$ of $ \bigtriangleup ABC,$ is coincided with its orthologic center with respect to $ \bigtriangleup A'B'C'.$ Prove that the centroid $ G'$ of $ \bigtriangleup A'B'C',$ is coincided with its orthologic center with respect to $ \bigtriangleup ABC.$[/color][/size][/b][/quote]
We draw the lines through vertices $ A,\ B,\ C,$ of the triangle $ \bigtriangleup ABC$ and perpendicular to $ AG,\ BG,\ CG$ respectively, where $ G$ is the centroid of $ \bigtriangleup ABC$ and we denote the triangle $ \bigtriangleup A'B'C',$ formed by their intersection points, taken per two of them.

Let $ D,\ D'$ be, the orthogonal projections of $ G,\ A'$ respectively on $ BC$ and it is easy to show that $ MD \equal{} MD',$ where $ M$ is the midpoint of the side-segment $ BC,$ because of $ A'G$ is the diameter of the circumcircle $ (O_{1})$ of the triangle $ \bigtriangleup GBC.$

Let $ N,\ X$ be, the midpoints of the segments $ O_{2}O_{3},\ B'C'$ respectively and so, we have that the points $ G,\ N,\ X,$ are collinear and $ GN \equal{} NX.$

Because of now, $ GD\parallel O_{1}M\parallel A'D',$ as perpendicular to $ BC$ and $ MD \equal{} MD'$ we conclude that the line segments $ O_{1}M,\ A'D',$ pass through the points $ N,\ X,$ respectively.

So, the line segment $ O_{1}N\perp BC,$ is the $ O_{1}$-median of the triangle $ \bigtriangleup O_{1}O_{2}O_{3},$ which clearly is coincided with the mid-perpendicular of $ BC.$

Similarly, the mid-perpendiculars of $ AC,\ AB,$ are the $ B',\ C'$-medians of $ \bigtriangleup O_{1}O_{2}O_{3}$ respectively and  may be completed here, the solution of the proposed [b][size=100]Problem 1[/size][/b] $ ($ the circumcenter $ O$ of $ \bigtriangleup ABC,$ is the centroid of $ \bigtriangleup O_{1}O_{2}O_{3}$ $ ).$

$ \bullet$By the same way as the line segment $ A'D'\equiv A'X,$ is the $ A'$-median of the triangle $ \bigtriangleup A'B'C',$ we can also say that the lines through the points $ B',\ C'$ and perpendicular to $ AC,\ AB$ respectively, are the $ B',\ C'$-medians of $ \bigtriangleup A'B'C'$ too.

Hence, we conclude that the centroid $ G'$ of $ \bigtriangleup A'B'C',$ is coincided with its ortologic center, with respect to $ \bigtriangleup ABC.$

If we consider now, an arbitrary triangle $ \bigtriangleup A''B''C'',$ such that $ A''B''\parallel A'B'$ and $ B''C''\parallel B'C'$ and $ A''C''\parallel A'C',$ it is easy to show that the triangles $ \bigtriangleup ABC$ and $ \bigtriangleup A''B''C'',$ are orthologic with respect to each other.

We can say that the line through the point $ A''$ and parallel to $ A'X,$ is perpendicular to $ BC$ and also, passes through the midpoint $ X'$ of the side-segment $ B''C''$ of $ \bigtriangleup A''B''C'',$ as the homologous line segment of $ A'X$ of $ \bigtriangleup A'B'C'.$

Similarly, for the line segments through the points $ B'',\ C''$ and parallel to $ B'Y,\ C'Z,$ respectively.

Hence, we conclude that the centroid $ G''$ of $ \bigtriangleup A''B''C'',$ is coincided with its orthologic center with respect to $ \bigtriangleup ABC$ and the proof of the [b][size=100]Lemma[/size][/b] is completed.

Kostas Vittas.

[quote="plane geometry"][b][size=100]PROBLEM 2.[/size][/b] - $ I$ is the incenter of $ \bigtriangleup ABC$ and $ G_{1},\ G_{2},\ G_{3}$ are the centroids of the triangles $ \bigtriangleup IBC,\ \bigtriangleup IAC,\ \bigtriangleup IAB.$ $ G$ is the centroid of $ \bigtriangleup ABC.$ Prove that $ G$ is the incenter of $ \bigtriangleup G_{1}G_{2}G_{3}.$[/quote]
This problem is easy, because of the line segment $ GG_{1},$ where $ G_{1}$ is the centroid of $ \bigtriangleup IBC,$ is parallel to $ AI$ $ ($ from $ AG \equal{} 2\cdot GM$ and $ IG_{1} \equal{} 2\cdot G_{1}M,$ where $ M$ is the midpoint of the side-segment $ BC$ $ ).$

So, from $ G_{2}G_{3}\parallel BC$ and $ G_{1}G_{2}\parallel AB$ and $ G_{1}G_{3}\parallel AC$ $ ($ easy to prove $ ),$ where $ G_{2},\ G_{3}$ are the centroids of the triangles $ \bigtriangleup IAC,\ \bigtriangleup IAB$ respectively, we conclude that the line segment $ G_{1}G,$ is the angle bisector of $ \angle G_{2}G_{1}G_{3},$ as the homologous line segment of $ AI.$

Similarly, we can say that the line segments $ G_{2}G,\ G_{3}G$ are the angle bisectors of $ \angle G_{1}G_{2}G_{3},\ \angle G_{1}G_{3}G_{2},$ respectively.

Hence, the centroid $ G$ of the given triangle $ \bigtriangleup ABC,$ is the incenter of the triangle $ \bigtriangleup G_{1}G_{2}G_{3}$ and the proof is cpmpleted.

Kostas Vittas.


AMC AIME USA(J)MO USAMO geometry rotation probability

I finally made it to AIME :D

I got a 133.5.

Nice. I left the last six blank thinking i would get 1-19 right  :roll: but i went home and did them and they werent that hard, thoguh 21 was tricky.

Hmm, why do we have so many threads with the exact thing...

lol 126 shut up i thought i had a 132 then i mess like #4 up or something (kidding it wasn't #4 it was like 10 or something). lol i have never not made it to AIME through and AMC 10 i have ever taken.

I could've had a 139.5 so easily...I missed number 9 because I forgot to divide by 2a instead of a.

139.5
Didn't do number 25 because I ran out of time
and
I missed number 17 (I think i know why I did it wrong)

Eh, ended up having to take the 10(plus it couldn't have hurt my index...). Got 150. Eh. 21 wasn't that bad, there's a topic about it I think.

got a 144..

missed number 25 because i didnt consider when the truck meets up with Michael...

had like 10 mins for the problem but ended up not checking that but instead that whole string of As and Bs..

[quote="bluelobster"]has anyone here ever gone to USAMO?[/quote]
I think like a lot of people here have gone to USAMO, even IMO.

130.5, as I mentioned on another post.

By the way, can someone tell me how to quote?[/quote]

probably i'm guessing AMC 10B: 120 as usual, and 12B: 100, most likely.

[quote="xpmath"][quote="hadasah"]Yeah, the cutoff for the B is always the highest it can get: 120 for the 10 and 100 for the 12.

I did 22 problems, missed number 25, and skipped 3 problems: 21, 23 and 24. I just ran out of time to draw a diagram for 24. I had a protractor...which makes me very mad. I could've ignored 25 and gotten 24. Then I might have 136.5. Oh well. It's already a miracle that I got 130.5. :lol:[/quote]
The cutoff was 115.5 last year, but it's probably 120 this year.[/quote]

i highly doubt that the cutoff will be 120.

Maybe not 120, but it didn't seem to me the probalems were harder than the A. Probably because I'm better at counting and probability than geometry.

Lol im sooooo bad at the AMCs i almost didnt make it to the 10 i probably got like a 86 lol where can i check the scores thought they werent out for 3 weeks......

Got 135 or something like that. I should check w/ my teacher. In any case, 20+ points over my AMC 12A score, so I'll be putting that down for the AIME/USAMO index.

Methinks I got a perfect.  I don't remember my answers, but maybe...

Guys do you have any tips on preperation for amc contests.

Thanks.

bluelobster you can go to the mathcounts/amc official website and download practice brochures or just put them up on ur screen while you do the problems on paper I also recommend getting some AMC books to help u out.

My score was downright horrible.... 66.9 :rotfl:

Could have gotten a 150 if I wasn't next to the heater. I was literally sweating right after it started. I feel so stupid for sitting there.


Let $ ABC$ be a triangle inscribed in the circle of center $ O$ with the altitudes $ AH,BK$ and $ CL$. Denote by $ A_0,B_0$ and $ C_0$, respectively, the midpoints of $ AH,BK$ and $ CL$. The circle of center $ I$ inscribed in triangle $ ABC$, touches the sides $ BC,CA$ and $ AB$ at $ D,E$ and $ F$ respectively.
Prove that the four lines $ A_0D,B_0EC_0F$ and $ OI$ are concurrent (When $ O$ coincides $ I$, one considers the line $ OI$ which is a arbitrary line passing through $ O$). :roll:  :lol:


trigonometry
inequalities
geometry proposed
geometry

If $ a,b,c$ are distincts, then

$ \frac{\cos^2 \frac{A}{2}}{\sin^2 \frac{B\minus{}C}{2}}\plus{}\frac{\cos^2 \frac{B}{2}}{\sin^2 \frac{C\minus{}A}{2}}\plus{}\frac{\cos^2 \frac{C}{2}}{\sin^2 \frac{A\minus{}B}{2}}\geq 2$

.

We have : $ \frac {\cos^2\frac A2}{\sin^2\frac {B \minus{} C}{2}} \equal{} \frac {\cos^2\frac A2}{\left(\sin\frac B2\cos\frac C2 \minus{} \sin\frac C2\cos\frac B2\right)^2} \equal{}$ $ \frac {\cos^2\frac A2}{\left(\sqrt {\frac {(s \minus{} a)(s \minus{} c)}{ac}}\cdot\sqrt {\frac {s(s \minus{} c)}{ab}} \minus{} \sqrt {\frac {(s \minus{} a)(s \minus{} b)}{ab}}\cdot\sqrt {\frac {s(s \minus{} b)}{ac}}\right)^2} \equal{}$

$ \equal{} \frac {\cos^2\frac A2}{\left(\frac {s \minus{} c}{a}\sqrt {\frac {s(s \minus{} a)}{bc}} \minus{} \frac {s \minus{} b}{a}\sqrt {\frac {s(s \minus{} a)}{bc}}\right)^2} \equal{} \frac {\cos^2\frac A2}{\cos^2\frac A2\left(\frac {b \minus{} c}{a}\right)^2} \equal{} \frac {a^2}{(b \minus{} c)^2}$ a.s.o.

So the inequality reduces to : $ \boxed{\ \frac {a^2}{(b \minus{} c)^2} \plus{} \frac {b^2}{(c \minus{} a)^2} \plus{} \frac {c^2}{(a \minus{} b)^2}\ge 2\ }$ , with $ a,b,c$ distinct numbers .

Using the well-known identity $ \frac {bc}{(a \minus{} b)(a \minus{} c)} \plus{} \frac {ca}{(b \minus{} c)(b \minus{} a)} \plus{} \frac {ab}{(c \minus{} a)(c \minus{} b)} \equal{} 1$ we have :

$ \sum\frac {a^2}{(b \minus{} c)^2} \equal{} \left(\frac {a}{b \minus{} c} \plus{} \frac {b}{c \minus{} a} \plus{} \frac {c}{a \minus{} b}\right)^2 \plus{} 2\sum\frac {bc}{(a \minus{} b)(a \minus{} c)} \equal{}$ $ \left(\sum\frac {a}{b \minus{} c}\right)^2 \plus{} 2\ge 2$ .

[quote="Ligouras"]Prove that if $ a,b,c$ are distincts, then $ \frac {\cos^2 \frac {A}{2}}{\sin^2 \frac {B \minus{} C}{2}} \plus{} \frac {\cos^2 \frac {B}{2}}{\sin^2 \frac {C \minus{} A}{2}} \plus{} \frac {\cos^2 \frac {C}{2}}{\sin^2 \frac {A \minus{} B}{2}}> 2$ .[/quote]

Observe that $ \frac {\cos\frac A2}{\left|\sin\frac {B \minus{} C}{2}\right|}\equal{}\frac {a}{|b\minus{}c|}$ . Thus $ \sum \frac {\cos^2 \frac {A}{2}}{\sin^2 \frac {B \minus{} C}{2}}\equal{}\sum\frac {a^2}{(b\minus{}c)^2}\stackrel{C.B.S.}{\ \ge\ }\frac {4s^2}{\sum (b\minus{}c)^2}\equal{}\frac {2s^2}{s^2\minus{}3r(4R\plus{}r)}>2$ .

[b]Remark.[/b] The inequality $ s^2\ge 3r(4R\plus{}r)$ is well-known and in our case it is strictly. Sorry [b]Ligouras[/b], I don't like this inequality.

"[i][b][color=violet][b]Sorry Ligouras, I don't like this inequality.[/b][/color][/b][/i]"

My Friend [color=red][b]Virgil[/b][/color],
not all the inequalities can have a beauty and important depth.
They are mathematical objects to practice the brain.
They also have them a dignity.
I don't also like it very... I respect it as creation of the mind....

Regards

Another proof using a well known inequality and identity.

(1).$ \cos^2\frac{B\minus{}C}{2}$ $ \geq$ $ \frac{2r}{R}$, and  similar inequalities for $ \cos^2\frac{A\minus{}B}{2}$ and $ \cos^2\frac{C\minus{}A}{2}$.

(2).$ \sum\sin^2\frac{A}{2}$ =$ 1\minus{}$$ \frac{r}{2R}$

Denote the left side of the inequality by L
Using (1). we get $ \frac{1}{\sin^2\frac{B\minus{}C}{2}}$ $ \geq$ $ \frac{1}{1\minus{}\frac{2r}{R}}$ and two similar inequalities obtained by cyclic permutation of A, B and C,  and by (2) we have $ \sum\cos^2\frac{A}{2}$ =$ 2$+$ \frac{r}{2R}$

Therefore L $ \geq$ $ \frac{\sum\cos^2\frac{A}{2}}{1\minus{}\frac{2r}{R}}$ $ \equal{}$     $ \frac{2\plus{}\frac{r}{2R}}{1\minus{}\frac{2r}{R}}$ $ >$ $ 2$. Clearly L never reaches the value 2.


geometry
circumcircle
trigonometry
quadratics
rectangle
angle bisector
perpendicular bisector

Triangle $ABC$. Let $D\in BC$ such $\angle BAD = \angle CAD$

Construct triangle $ABC$ given $AD$, $BC$ and $\angle BAC$.

Thanks :)

Denote the angle $\angle BAC = \alpha$. Since $\angle BAD = \angle CAD$, $AD$ is the bisector of the angle $\angle BAC = \alpha$ and $\angle BAD = \angle CAD = \frac{\alpha}{2}$. Construct an isosceles triangle $\triangle BCP$ with the base $BC$ and angles $\angle PBC = \angle PCB = \frac{\alpha}{2}$ and the circumcircle $(O)$ of this triangle. Since

$\angle BPC = 180^o - (\angle PBC + \angle PCB) = 180^o - \alpha$

the angles spanning the arc $BC$ of the circle $(O)$ opposite to the point $P$ are equal to $\alpha$. Hence, the circle $(O)$ is the circumcircle of the desired triangle $\triangle ABC$. Let the angle bisector $AD$ intersect the circle $(O)$ at the point $P'$ different from $A$. Since the angles $\angle P'AB = \angle P'AC = \frac{\alpha}{2}$ are equal, the chords $P'B = P'C$ are also equal and the points $P' \equiv P$ are identical. Let $M$ be the midpoint of the segment $BC$ and let the perpendicular bisector $OM \equiv PM$ of the segment $BC$ intersect the circle $(O)$ at a point $Q$ different from $P$. Let $R$ be the radius of the circle $(O)$ and denote the angle $\angle APQ = \phi$. Since $PQ = 2R$ is a diameter of the circle $(O)$, the angle $\angle PQA = 90^o$ is right and

$PA = PQ \cos{\widehat{APQ}} = 2R \cos \phi$

On the other hand, $\angle BOM = \angle COM = \alpha$,

$OM = OB \cos \alpha = R \cos \alpha,\ \ PM = OP - OM = R(1 - \cos \alpha)$

$PD = \frac{PM}{\cos \phi} = \frac{R(1 - \cos \alpha)}{\cos \phi}$

$AD = PA - PD = 2R \cos \phi - \frac{R(1 - \cos \alpha)}{\cos \phi}$

$2R \cos^2{\phi} - AD \cos \phi - R(1 - \cos \alpha) = 0$

$\cos^2{\phi} - \frac{AD}{2R} \cos \phi - \frac{1 - \cos \alpha}{2} = \cos^2{\phi} - \frac{AD}{2R} \cos \phi - \sin^2{\frac{\alpha}{2}} = 0$

Thus we obtained a quadratic equation for $\cos \phi$ or better yet, a quadratic equation for $x = PA = 2R \cos \phi$. The base $BP$ of the isosceles triangle $\triangle BOP$ with $OB = OP = R$ and $\angle BOP = \alpha$ is equal to $BP = 2R \sin{\frac{\alpha}{2}}$. Then

$4R^2\cos^2{\phi} - AD \cdot 2R \cos \phi - 4R^2 \sin^2{\frac{\alpha}{2}} = 0$

$x^2 - AD \cdot x - BP^2 = 0$

$x = PA = \frac{AD}{2} \pm \sqrt{\left(\frac{AD}{2}\right)^2 + BP^2}$

Since $PA > AD$, we have to use the root with the plus sign. To construct $PA$, erect a normal to the line $BP$ at the point $B$ (obviously, this normal is the line $BQ$). Draw a circle $(B)$ centered at the point $B$ and with radius $\frac{AD}{2}$, intersecting the line $BQ$ at a point $N$ opposite to the point $Q$. Using Pythagorean theorem for the right angle triangle $\triangle BPN$,

$PN = \sqrt{BN^2 + BP^2} = \sqrt{\left(\frac{AD}{2}\right)^2 + BP^2}$

Draw a circle $(N)$ centered at the point $N$ and with radius $PN$, intersecting the line $BQ$ at a point $F$ opposite to the point $B$.

$BF = BN + PN = \frac{AD}{2} + \sqrt{\left(\frac{AD}{2}\right)^2 + BP^2} = PA$

Complete the right angle triangle $\triangle BPF$ into a rectangle $BPEF$. Draw a circle $(P)$ centered at the point $P$ and with radius $PE = BF = PA$ intersecting the circle $(O)$ at points $A, A'$, thus completeing 2 oppositely congruent triangles $\triangle ABC \cong \triangle A'BC$.

Thanks yetti. It is O.K. :lol:

I have only one remark.

We can get formula $x^2-ADx -BP^2=0$  from similarty of triangles $BPD$ and $ABP$, so we don't need this:

[quote="yetti"]
 $\displaystyle PA = PQ \cos{\widehat{APQ}} = 2R \cos \phi $

On the other hand,$\displaystyle \angle BOM = \angle COM = \alpha $

$\displaystyle OM = OB \cos \alpha = R \cos \alpha,\ \ PM = OP - OM = R(1 - \cos \alpha) $

$\displaystyle PD = \frac{PM}{\cos \phi} = \frac{R(1 - \cos \alpha)}{\cos \phi} $

$\displaystyle AD = PA - PD = 2R \cos \phi - \frac{R(1 - \cos \alpha)}{\cos \phi} $

$\displaystyle 2R \cos^2{\phi} - AD \cos \phi - R(1 - \cos \alpha) = 0 $

$\displaystyle \cos^2{\phi} - \frac{AD}{2R} \cos \phi - \frac{1 - \cos \alpha}{2} = \cos^2{\phi} - \frac{AD}{2R} \cos \phi - \sin^2{\frac{\alpha}{2}} = 0 $

Thus we obtained a quadratic equation for  or better yet, a quadratic equation for
$ \displaystyle x = PA = 2R \cos \phi $. The base $BP$ of the isosceles triangle $\Delta BOP$ with $OB = OP = R$ and
$\displaystyle \angle BOP = \alpha $ is equal to $\displaystyle BP = 2R \sin{\frac{\alpha}{2}}$.  Then

$ \displaystyle 4R^2\cos^2{\phi} - AD \cdot 2R \cos \phi - 4R^2 \sin^2{\frac{\alpha}{2}} = 0 $

[/quote] ;)

[quote="Number1"]Thanks yetti. It is O.K. :lol:

I have only one remark.

We can get formula $x^2-ADx -BP^2=0$  from similarty of triangles $BPD$ and $ABP$, so we don't need this:...
[/quote]

It goes both ways. We can get the quadratic equation by trigonometry, hence, we don't need similarity of the triangles $\triangle BPD$ and $\triangle ABP$. :lol:

Yetti.


function
analytic geometry
number theory proposed
number theory

Arm yourself with AN ATOMIC bomb and kill this in a second ,but with out this Atomic bomb ,noway :) .Anyway here is a funny little big problem:

Draw the shap of this function in a coordinated plane. $y^n +x^n=1,n \in N-\{1,2\}$
Prove that there dont exist a point with rational coordinats on this shape  :D (Remember you of something?)

Put $x=a/b$, $y=c/d$, so it becomes $(ad)^n+(bc)^n=(bd)^n$, which is impossible by Fermat's last theorem.  Was that what you were looking for?

Exactly,pretty fast solution blahblah ,nice :lol:


let (C) be a circle and M be a point in the interior of it.A and B are two variable points on (C)inwich:

angle AMB=90.

N is the mid point of chord AB.find the locus of N.

That's http://www.mathlinks.ro/Forum/viewtopic.php?t=14246 problem 1.

  darij


geometry
incenter
circumcircle
geometry unsolved

[color=darkblue]Triangle $ ABC$ is inscribed in a circle $ \omega$. Let $ I$ be incenter of the triangle, $ A_1,B_1,C_1$ tangency points of incircle to the sides $ BC,CA,AB$ respectively. Lines $ AI,BI,CI$ intersect $ \omega$ again at points $ A_2,B_2,C_2$ respectively. Prove that lines $ A_1A_2,B_1B_2,C_1C_2$ are concurrent.[/color]

[hide="Image"][img]http://ipicture.ru/uploads/080610/EIZUcVITXo.png[/img][/hide]

$ A_1B_1 \perp CI$ and $ A_2B_2\perp CI$
 $ \Rightarrow A_1B_1\parallel{}A_2B_2$
Similar $ A_1C_1\parallel{}A_2C_2,B_1C_1\parallel{}B_2C_2$
Therefore
$ \triangle{A_1B_1C_1}\sim \triangle{A_2B_2C_2}$ so $ A_1A_2,B_1B_2,C_1C_2$ is concurrent .

It is clear, because the line segments $ A_{1}A_{2},\ B_{1}B_{2},\ C_{1}C_{2},$ intercect the line segment $ OI,$ where $ O$ is the circumcenter and $ I$ is the incenter of $ \bigtriangleup ABC,$ at the same point $ P,$ such that $ PI / PO \equal{} r / R.$

Kostas Vittas.


topology
advanced fields
advanced fields unsolved

I was suggesting to use coverings to determine the fundamental groups of the spaces below, but I am stuck because I do not know how to even start :blush:. The spaces are :

[b](1)[/b] The space formed by removing a circle (homeomorphic to $ S^1$) from $ R^3$;

[b](2)[/b] The space formed by removing two circles, which are interlaced, from $ R^3$.

Thank you in advance

[quote="randomgraph"]I wouldn't actually recommend doing these via coverings, if you can avoid it. Are you familiar with the Van Kampen theorem?[/quote]

yes, I am familiar, but I would like to know if the proof of my problems can be obtained without using this (not because I don't want to, but it is just because this theorem is not part of my notes yet).

thanks randomgraph

I agree with Randomgraph this would be much easier to do with Van Kampen (pass $ \mathbb{R}^3$ to its one-point compactification $ S^3$. Also notice that $ S^3$ is homeomorphic to the quotient space of two solid toruses $ S^1\times D$ identified by their surface. Then use Van Kampen's theorem). If I think of any good coverings though, I'll post again.

I don't see how to use coverings, so I think the best way is to use Van Kampen's Theorem.   I was reading Hatcher's book and I got the answer.   For instance, for the first one, he says that this space can be deformed to $ S^1 \vee S^2$.  If I assume this I can use Van Kampen to determine the fundamental group of $ S^1 \vee S^2$, but I don't see why $ S^1 \vee S^2$ deformation retracts to my desired space.   His explanation can be reduced to this:

$ R^3 \backslash A$ ($ A$ is a circle) deformation retracts onto the union of $ S^2$ with a diameter ($ A$ is inside $ S^2$ and the diameter goes through the interior of the disc induced by $ A$), where points outside $ S^2$ deformation retract onto $ S^2$ , and points inside $ S^2$ and not in $ A$ can be pushed away from $ A$ toward $ S^2$ or the diameter.

I am trying to imagine how the deformation retraction acts, but I can't  :(

Thank you in advance


IMO 2007
Clique number
algorithm
graph theory
IMO
combinatorics
IMO Shortlist

This is very hard problem because I heard that only one chinese solved this problem...

[quote]we suppose that competition contain:
$ (G_{i})_{i\in \{1,2,...,g\}}=groups \ not\ clique$
$ (C_{i})_{i\in \{1,2,...,c\}}=cliques$
$ A_{n}=\{C_{i}|\ |C_{i}|=n\}$ and $ G=\{G_{i}\}$
we have $ max\{|C_{i}|\}=2k$ for some $ k$.
$ R_{1}$ first room $ R_{2}$ second room[/quote]

$ I)$ if $ |A_{2k}|>1$
we put a clique of $ A_{2k}$ and $ G$ in $ R_{1}$ and the other cliques of $ A_{2k}$ in $ R_{2}$
[b]the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room[/b]$ =2k$

$ II)$ if $ |A_{2k}|=1,\ A_{2k}=\{C_{h}\}$

$ 1)$ if $ m=max\{i\in N|\ A_{i}\neq\emptyset,i<2k \}>k$
here we put $ m$ competitors of $ C_{h}$ in $ R_{1}$ and the other elements ($ 2k-m<m$) of $ C_{h}$ in $ R_{2}$
we put $ G$ in $ R_{1}$ and the cliques of $ A_{m}$ in $ R_{2}$
we can put the rest of cliques in $ R_{2}$ for example.
[b]the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room[/b]$ =m$

$ 2)$ if $ m=max\{i\in N|\ A_{i}\neq\emptyset,i<2k \}\le k$
we put $ k$ competitors of $ C_{h}$ in $ R_{1}$ and $ k$ competitors of $ C_{h}$ in $ R_{2}$
and we put $ G$ in $ R_{1}$ and the other cliques in $ R_{2}$
[b]the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room[/b]$ =k$

[u]sorry for my bad english[/u]

[quote="aviateurpilot"][quote]we suppose that competition contain:
$ (G_{i})_{i\in \{1,2,...,g\}}=groups \ not\ clique$
$ (C_{i})_{i\in \{1,2,...,c\}}=cliques$
$ A_{n}=\{C_{i}|\ |C_{i}|=n\}$ and $ G=\{G_{i}\}$
we have $ max\{|C_{i}|\}=2k$ for some $ k$.
$ R_{1}$ first room $ R_{2}$ second room[/quote]
$ I)$ if $ |A_{2k}|>1$
we put a clique of $ A_{2k}$ and $ G$ in $ R_{1}$ and the other cliques of $ A_{2k}$ in $ R_{2}$
[b]the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room[/b]$ =2k$
[/quote]

I don't know if I misundertsand your idea or not, but you seems didn't consider if two cliques is overlap.

e.g. {1,2,3,4} is a clique and {1,5,6,7} is another clique, you can't put 1 in both room anyway

I solved the problem. Here is my idea.
For a subset $ A$ of graph $ G$, let $ f(A)$ be the size of largest clique in the induced graph by $ A$. For a partition of $ G$ to $ A,B$, define $ f(A,B)=f(A)-f(B)$. Suppose $ K_{n}$ is the largest clique of $ G$ and split it into two $ K_{n}$'s randomly and put one of the $ K_{n}$'s in set $ A$, and put the other $ K_{n}$ and other vertices in set $ B$. You see $ f(A,B)\geq0$, we can make some operations on the partition and to that at each step $ f$ reduces at most one, and $ f$ is non-positive at the end.

that is also my idea. I reduce it to the case when $ f(A,B)=1$ where each member is part of a $ f(A)$-clique an there exist no two members x,y and clique $ K$ so that the union of $ K$ with x and with y is a $ f(A)+1$ clique.

The following is an idea.  Let $ \mathbb{S}_{n}=\left\{ \bold x\in[0,1]^{n}|\left< \bold x,\bold{1}\right> =1\right\}$ and $ f(G)=\max_{\bold x\in\mathbb{S}_{n}}f_{G}(\bold x)=\max_{\bold x\in\mathbb{S}_{n}}\left<A\bold x,\bold x\right>$, where $ A$ is the adjacency matrix of any graph $ G$ with $ |G|=n$.  Clearly, $ f$ is an increasing function, so for $ H,G-H\subset G$, $ f(H)\leq f(G)$.  It can be proven that if $ \omega (G)$ is the maximum clique number of $ G$, then $ f(G)=\frac{\omega(G)-1}{\omega(G)}$ (How?). We want to prove that there exists a subset $ H\subset G$ such that $ f(H)=f(G-H)$, i.e. $ \max_{\bold x\in \mathbb{S}_{|H|}}f_{H}(\bold x)=\max_{\bold x\in\mathbb{S}_{|G-H|}}f_{G-H}(\bold x)$.  Hopefully, this is a correct [i]approach[/i].

actually Omid Hatami f can reduce also by 2 , and in my solution that's where I have to use that the maximum clique is of even size. Where do you use it?

I split a $ K_{2n}$ into two $ K_{n}$'s, and then I do the operations such that at each step $ f$ reduces by at most 1(you must prove that it is always possible, using the maximality of $ K_{2n}$). Obviously before the first step $ f\geq0$, and at the last step all of the the vertices in $ B$, which are not in $ K_{n}\subset B$ will be moved in $ A$, and at last step $ f\leq0$, and everything is proved.
If the size of the maximum clique was odd then maybe at the first step and at the last step we had $ f\geq0$, and we could not prove anything. But for odd $ n$, we can prove that it's possible to split vertices in two parts that the size of the maximum clique in each side differ by at most 1.

Yes!
that's also my proof (approximately)
actually in showing that it can decrease by at most 1
I suppose the contrary (that it can't) and get either a bigger size of the maximal clique or that it has odd size (thus contradiction in both)

I think Omid Hatami has  really good idea. But it is not clear (and no any proofs that it is possible) about operations that decreasing f.

----------------------------------------

No lame, no game.

We can prove that by an algorithm.
Note by [b]max(Room n)[/b] the largest clique size in Room n, where [b]n= 0 or 1[/b]

[b]Lema 1.[/b] If we move one person from Room 1 to Room 2 then the largest size of a clique in Room 1 will decrease by 0 or 1, and in Room2 it will increase by 0 or 1.
[b]Lema 2.[/b] If in Room 1 the largest size of a clique is [b]m[/b] and in Room 2 - [b]n[/b], then the maximum size of a clique of all persons is not greater than [b]n+m[/b].

[b]The algorithm:[/b]
All persons are in Room 1.
Move to Room 2 all except the largest clique.
Move persons by one from Room1 to Room2 until max( Room 1 ) - max(Room 2) = 0 or 1  (this is possible to achieve due to Lema 1). If it is 0 then its done. So consider  max( Room 1 ) = max(Room 2) + 1 .
Move any person from Room 1 to Room2. If max(Room 2) do not increase it is done (in max(Room1) will decrease by 1 as there is only one clique of persons).
So consider max(Room 2) + 1 = max(Room 1).
Find a person in the largest clique of Room2 which is not friend with all persons from Room 1 and move that person to Room 1, and we get max (Room 1) = max(Room 2) q.e.d. (there exist such a person otherwise all people in the largest clique of Room2 are friends with all persons from the only clique in Room 1 and by concatenating both cliques we get an odd size and it is the largest - from Lema 2).

I had a typo, now it is correct.

[quote="anonymous1173"][quote]Find a person in the largest clique of Room2 which is not friend with all persons in Room 2 and move that person to Room 1, and we get max (Room 1) = max(Room 2) q.e.d. [/quote]
in this step if we have more then one largest clique in Room2, max(Room2) and max(Room1) don't change.[/quote]

I can't finish this, but I pursued this approach a bit further -- here's a sketch.

If there is more than one largest clique in Room 2, take a person in Room 2 who belongs to at least one but not all of the largest cliques, and move him to Room 1.  If this increases the size of the largest clique in room 1, we're done, otherwise, repeat until we have a unique clique in Room 2, call it K.  If we move any of the persons in K to room 1, we'll decrease max(Room 2) -- if we can do this without increasing max(Room 1), we're good.  The problem is that everyone in K could be friends with all of a maximal clique in Room 1.

Suppose a person x in K is friends with everyone in a maximal clique L in room 1 -- if there is only one such L satisfying this description for a given person x, we can do the following..  Then not everyone in L is friends with everyone in K, or we would have a maximal clique in our big graph of odd size, so take $ y \in L$ such that y is not friends in everyone in K, switch x to room 1, switch y to room 2, so that max(room 1) is unaffected and max(room 2) decreases by 1.  The problem is that there might be more than one clique in room 1 containing only friends of x, and then we would have to move one person from each of those cliques to room 2 so as to keep from increasing max(room 1).  At this point I get stuck because I don't see how to assure that max(room 2) will actually decrease if we have to move a bunch of people to room 2.

I think this is enough to finish the most annoying case (when Room 2 has several cliques of maximal size).

Let $ A_{1}, A_{2}, ..., A_{n}$ be the distinct (but not disjoint) cliques of maximal size in Room 2. There must be a vertex in $ A_{1}$ which is not in all of the other cliques (proof: if each vertex of $ A_{1}$ were also in all of $ A_{2}, ..., A_{n}$ then, being of the same size, there would be no room in them for other vertices, so they would all be equal to $ A_{1}$, absurd because they are distinct). So we have a vertex $ V$ which is in $ A_{1}$ and possibly also in some other $ A_{i}$ but not in all cliques, so not in, for example, $ A_{l}$. Now, for each clique not containing $ V$ (in this case $ A_{l}$), take a vertex $ V_{l}$ in $ A_{l}$ not joined to $ V$ by an edge. Such a vertex exists because, if $ V$ were joined to all vertices of $ A_{l}$, $ V$ and $ A_{l}$ would form a larger-than-maximum clique. Possibly some of the vertices $ V_{l}, V_{m}$ chosen in this way will be the same; in that case, count it just once.

Now we will have a set of vertices of the form $ V, V_{l}, V_{m}$. Move these to Room 1. This will reduce the max clique size in Room 2, because all their maximal cliques have lost vertices, but it will decrease only by $ 1$ (because $ A_{1}$ has lost only one vertex; clearly $ V_{l}, V_{m}$ can't belong to $ A_{1}$ because they are not joined to $ V$, which is in $ A_{1}$). If the max clique size in Room 1 doesn't increase, we're done. If it does, a new larger clique has arisen, containing some of the new vertices. Now, since $ V$ is not joined to the other $ V_{l}$, if the new clique contains $ V$ it only contains $ V$, and all the other $ V_{l}$ can be sent back to Room 2, where all sets to which $ V$ didn't belong will be repaired, and we will be done (since the new clique in Room 1 only contains $ V$ the max clique size in R1 cannot increase by more than 1). If the new clique doesn't contain $ V$, it can contain several of the $ V_{l}, V_{m}$ and the max clique size in R1 can increase by more than one. First bring back $ V$ to Room 2; $ A_{1}$ will be repaired. Now, if m-c-s in R1 has increased by only 1, we're done; otherwise, send back vertices $ V_{l}$ one by one to Room 2. M-c-s in R1 will decrease at most 1 in each step, while m-c-s in Room 2 will not increase (because $ A_{1}$ is already a maximal clique), so at some point we will win.

Nice problem! Is next geneneralization true : $n$ divides size of maximal clique and we need to divide set in $n$ rooms?

Finally! :)
[quote=Valentin Vornicu]In a mathematical competition some competitors are friends. Friendship is always mutual. Call a group of competitors a [i]clique[/i] if each two of them are friends. (In particular, any group of fewer than two competitiors is a clique.) The number of members of a clique is called its [i]size[/i].

Given that, in this competition, the largest size of a clique is even, prove that the competitors can be arranged into two rooms such that the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room.

[i]Author: Vasily Astakhov, Russia[/i][/quote]

Call the rooms $A$ and $B$; suppose $A$ is initially empty while $B$ has all the competitors in it. Let $M$ be the maximum clique of the initial group. Suppose $|M|=2m$. Now, one-by-one pick elements from $M$ and put them in $A$. Let $\mathcal{C}(A), \mathcal{C}(B)$ denote the size of maximum cliques in these respective sets. Initially $\mathcal{C}(B)-\mathcal{C}(A)=2m$ and on each move this decreases by $1$ or $2$. Continue the process as long as it isn't negative; we either obtain $\mathcal{C}(A)+1=\mathcal{C}(B)$ or $\mathcal{C}(A)=\mathcal{C}(B)$.

The latter yields a desirable partition so assume we have the former case. Let $\mathcal{C}(A)=k$, then $\mathcal{C}(B)=k+1$. Now let $M'$ be the remnants of former maximum clique $M$ in $B$.

[b]Claim.[/b] All $k+1$ cliques in $B$ contain $M'$.

(Proof) If not; pick an element from $M'$ that doesn't destroy some $k+1$ clique in $B$ and put it in $A$ thus making $A$ a $k+1$ clique. $\blacksquare$

Let $S_1, \dots, S_j$ denote the set of $k+1$ cliques in $B$. Now onwards, we will not meddle with elements in $B$ aside from those in $S=\cup^{j}_{i=1} S_i$. Fix $S_1$ and one-by-one pick elements from $S$ not in $S_1$ and put them in $A$. If at any point $\mathcal{C}(A)$ becomes $k+1$ then we're done. So now we have deposited all elements of $S$ not in $S_1$ to $A$. The maximum clique in $A$ right now (say $T$) has size $k$. Note that all elements of $T$ share an edge with all elements of $M'$ and $|T|+|M'|=2m$ hence $T \cup M'$ is a maximum clique of the entire graph. Thus, if we pluck an element from $S_1$ and put it in $A$; it will not contribute to any maximum clique in $A$. By doing so, we've now made $\mathcal{C}(A)=\mathcal{C}(B)=k$ as desired. $\blacksquare$

After having read the solution in Pascal96's book a long time ago, I finally take the time to write it up now. Take the obvious graph interpretation $G$. We paint red any vertices in one of the maximal cliques $K$, which we assume has $2r$ vertices, and paint the remaining vertices green. We let $\alpha(\bullet)$ denote the clique number.
Initially, let the two rooms $A = K$, $B = G-K$.

[b][color=red]Claim:[/color][/b]  	We can move at most $r$ vertices of $A$ into $B$ 	to arrive at $\alpha(A) \le \alpha(B) \le \alpha(A)+1$.
[i]Proof.[/i]  	This is actually obvious by discrete continuity. 	We move one vertex at a time, 	noting $\alpha(A)$ decreases by one at each step, 	while $\alpha(B)$ increases by either zero or one at each step.
We stop once $\alpha(B) \ge \alpha(A)$, 	which happens before we have moved $r$ vertices 	(since then we have $\alpha(B) \ge r = \alpha(A)$). 	The conclusion follows. $\blacksquare$

So let's consider the situation \[ \alpha(A) = k \ge r \qquad\text{and}\qquad \alpha(B) = k+1. \]
At this point $A$ is a set of $k$ red vertices, while $B$ has the remaining $2r-k$ red vertices (and all the green ones). An example is shown below with $k=4$ and $2r = 6$.
[asy] size(10cm); pair K1 = 2*dir(45); pair K2 = 2*dir(135); pair K3 = 2*dir(225); pair K4 = 2*dir(315);
label("$A$", (0,2), dir(90), red); label("$\alpha(A) = k$", (0,-2.5), dir(90), red); label("$k$ red vertices", (0,-2.5), dir(-90), red);
pair K5 = (6,1); pair K6 = (6,-1);
draw(K1--K5, palered); draw(K2--K5, palered); draw(K3--K5, palered); draw(K4--K5, palered);
draw(K1--K6, palered); draw(K2--K6, palered); draw(K3--K6, palered); draw(K4--K6, palered);
pair B1 = (4.8,1.3); pair B2 = (3.7,0); pair B3 = (4.8,-1.3);
pair C1 = (7.2,1.3); pair C2 = (8.3,0); pair C3 = (7.2,-1.3);
draw(K5--B1--K6, paleblue); draw(K5--B2--K6, paleblue); draw(K5--B3--K6, paleblue); draw(B1--B2--B3--cycle, paleblue); draw(K5--C1--K6, paleblue); draw(K5--C2--K6, paleblue); draw(K5--C3--K6, paleblue); draw(C1--C2--C3--cycle, paleblue);
draw(K1--K2--K3--K4--cycle, red+1); draw(K1--K3, red+1); draw(K2--K4, red+1); draw(K5--K6, red+1);
dot(K1, red); dot(K2, red); dot(K3, red); dot(K4, red); dot(K5, red); dot(K6, red); dot(B1, deepgreen); dot(B2, deepgreen); dot(B3, blue); dot(C1, deepgreen); dot(C2, deepgreen); dot(C3, blue); draw(circle(B3, 0.15), blue); draw(circle(C3, 0.15), blue);
label("$B$", (6,2), dir(90), deepgreen); label("$\alpha(B) = k+1$", (6,-2.5), dir(90), deepgreen); label("$2r-k$ red vertices", (6,-2.5), dir(-90), deepgreen);
draw((3,2.8)--(3,-2.8), black+1.5); [/asy]
Now, if we can move any red vertex from $B$ back to $A$ without changing the clique number of $B$, we do so, and win.
Otherwise, it must be the case that [i]every[/i] $(k+1)$-clique in $B$ uses [i]every[/i] red vertex in $B$. For each $(k+1)$-clique in $B$ (in arbitrary order), we do the following procedure. [list] 	[*]If all $k+1$ vertices are still green, pick one and re-color it blue. 	This is possible since $k+1 > 2r-k$. 	[*]Otherwise, do nothing. [/list] Then we move all the blue vertices from $B$ to $A$, one at a time, in the same order we re-colored them. This forcibly decreases the clique number of $B$ to $k$, since the clique number is $k+1$ just before the last blue vertex is moved, and strictly less than $k+1$ (hence equal to $k$) immediately after that.

[b][color=red]Claim:[/color][/b]  	After this, $\alpha(A) = k$ still holds.
[i]Proof.[/i]  	Assume not, and we have a $(k+1)$-clique 	which uses $b$ blue vertices and $(k+1)-b$ red vertices in $A$. 	Together with the $2r-k$ red vertices already in $B$ 	we then get a clique of size 	\[ b + \left( (k+1-b) \right) 	+ \left( 2r-k \right) = 2r + 1 \] 	which is a contradiction. $\blacksquare$

[quote=v_Enhance]After having read the solution in Pascal96's book a long time ago, I finally take the time to write it up now. Take the obvious graph interpretation $G$. We paint red any vertices in one of the maximal cliques $K$, which we assume has $2r$ vertices, and paint the remaining vertices green. We let $\alpha(\bullet)$ denote the clique number.

Initially, let the two rooms $A = K$, $B = G-K$.

[b][color=red]Claim:[/color][/b]  	We can move at most $r$ vertices of $A$ into $B$ 	to arrive at $\alpha(A) \le \alpha(B) \le \alpha(A)+1$.

[i]Proof.[/i]  	This is actually obvious by discrete continuity. 	We move one vertex at a time, 	noting $\alpha(A)$ decreases by one at each step, 	while $\alpha(B)$ increases by either zero or one at each step.

We stop once $\alpha(B) \ge \alpha(A)$, 	which happens before we have moved $r$ vertices 	(since then we have $\alpha(B) \ge r = \alpha(A)$). 	The conclusion follows. $\blacksquare$

So let's consider the situation \[ \alpha(A) = k \ge r \qquad\text{and}\qquad \alpha(B) = k+1. \]

At this point $A$ is a set of $k$ red vertices, while $B$ has the remaining $2r-k$ red vertices (and all the green ones). An example is shown below with $k=4$ and $2r = 6$.

[asy] size(10cm); pair K1 = 2*dir(45); pair K2 = 2*dir(135); pair K3 = 2*dir(225); pair K4 = 2*dir(315);

label("$A$", (0,2), dir(90), red); label("$\alpha(A) = k$", (0,-2.5), dir(90), red); label("$k$ red vertices", (0,-2.5), dir(-90), red);

pair K5 = (6,1); pair K6 = (6,-1);

draw(K1--K5, palered); draw(K2--K5, palered); draw(K3--K5, palered); draw(K4--K5, palered);

draw(K1--K6, palered); draw(K2--K6, palered); draw(K3--K6, palered); draw(K4--K6, palered);

pair B1 = (4.8,1.3); pair B2 = (3.7,0); pair B3 = (4.8,-1.3);

pair C1 = (7.2,1.3); pair C2 = (8.3,0); pair C3 = (7.2,-1.3);

draw(K5--B1--K6, paleblue); draw(K5--B2--K6, paleblue); draw(K5--B3--K6, paleblue); draw(B1--B2--B3--cycle, paleblue); draw(K5--C1--K6, paleblue); draw(K5--C2--K6, paleblue); draw(K5--C3--K6, paleblue); draw(C1--C2--C3--cycle, paleblue);

draw(K1--K2--K3--K4--cycle, red+1); draw(K1--K3, red+1); draw(K2--K4, red+1); draw(K5--K6, red+1);

dot(K1, red); dot(K2, red); dot(K3, red); dot(K4, red); dot(K5, red); dot(K6, red); dot(B1, deepgreen); dot(B2, deepgreen); dot(B3, blue); dot(C1, deepgreen); dot(C2, deepgreen); dot(C3, blue); draw(circle(B3, 0.15), blue); draw(circle(C3, 0.15), blue);

label("$B$", (6,2), dir(90), deepgreen); label("$\alpha(B) = k+1$", (6,-2.5), dir(90), deepgreen); label("$2r-k$ red vertices", (6,-2.5), dir(-90), deepgreen);

draw((3,2.8)--(3,-2.8), black+1.5); [/asy]

Now, if we can move any red vertex from $B$ back to $A$ without changing the clique number of $B$, we do so, and win.

Otherwise, it must be the case that [i]every[/i] $(k+1)$-clique in $B$ uses [i]every[/i] red vertex in $B$. We pick a green vertex from each clique simultaneously (possibly with overlap), which is possible since $k+1 > 2r-k$, and re-color it blue. We move them all blue vertices to $A$, forcibly decreasing the clique number of $B$ to $k$.

[b][color=red]Claim:[/color][/b]  	After this, $\alpha(A) = k$ still holds.

[i]Proof.[/i]  	Assume not, and we have a $(k+1)$-clique 	which uses $b$ blue vertices and $(k+1)-b$ red vertices in $A$. 	Together with the $2k-r$ red vertices already in $B$ 	we then get a clique of size 	\[ b + \left( (k+1-b) \right) 		+ \left( 2k-r \right) = 3k+1 - r \ge 2r + 1 \] 	since $k \ge r$, contradiction. $\blacksquare$[/quote]

Everything is OK, but can you explain me, why moving all blue vertices from $B$ to $A$ decreases the size of the largest clique in $B$ [i]exactly[/i] by 1?

My mistake. I think I took too many blue vertices. I edited what I think should be a fix for it.

Let $ Q_{max}$ be a largest clique. At the beginning we deploy all students in the room $ R_1$ and then begin to move the competitors in $ Q_{max}$ one by one from $ R_1$ into the other room $ R_2$. Consider the last moment, the largest size of the cliques in $ R_1$ is greater than the size of the clique in $ R_2$. Denote by $ Q_1,Q_2$ the groups of students, $ Q_{max}$ is split into, and which currently are in $ R_1$ and $ R_2$  respectively. Clearly, $ Q_1\neq \emptyset$.
So, suppose at this moment the maximal clique size in $ R_1$ is $ m_1$ and the size of the clique in $ R_2$ is $ m_2=|Q_2|, m_2<m_1$. Taking any $ q_1\in Q_1$ and moving it to $ R_2$ changes the situation, i.e. after that move we have $ m_2\geq m_1 $. In case of equality, we are done , so we assume that after moving any $ q_1\in Q_1$ into room $ R_2$ the clique in $ R_2$ has greater size than any clique in $ R_1$. It means $ m_1=m_2+1$

Denote by $ \mathcal{Q}$ the family of all cliques of size $ m_1$ in $ R_1$. Taking into account that after removing any $ q_1\in Q_1$ the max clique size in $ R_1$ drops down, it follows $ Q_1\subset Q$ for any $ Q\in \mathcal{Q}$. We also conclude $ Q_1\not\in \mathcal{Q}$, since otherwise $ |Q_1|=|Q_2|+1$, which is impossible because $ |Q_{max}|$ is even.
Now, we start transferring students $ s_1,s_2,\dots,s_k$ not in  $ Q_1$ that take part in some clique of $ \mathcal{Q}$ from room $ R_1$ to $ R_2$ till the moment we destroy all cliques in $ \mathcal{Q}$. At that moment, the max clique size in $ R_1$ decreases with $ 1$ and equals $ m_1-1$. We claim the max clique size in $ R_2$ is still intact and equals $ m_2=m_1-1$.

Assume on the contrary, there exists a clique $ P_2$ in $ R_2$ with $ |P_2|>|Q_2|=m_2$. Note that all students of $ P_2\setminus Q_2$ are among $ s_1,s_2,\dots,s_k$ and thus they are friends with all students in $ Q_1$. Hence $ P_2\cup Q_1$ is a clique with size $ |P_2|+|Q_1|>|Q_2|+|Q_1|=|Q_{max}|$, a contradiction with the fact $ Q_{max}$ is a clique with maximal size.

Remark: Here are [url=https://dgrozev.wordpress.com/2019/12/05/splitting-the-cliques-of-a-graph-imo-2007-p3/]more detailed comments[/url] on the motivation and grading of this problem.

[quote=v_Enhance]
Claim: After this, $\alpha(A) = k$ still holds.

Proof. Assume not, and we have a $(k+1)$-clique which uses $b$ blue vertices and $(k+1)-b$ red vertices in $A$. Together with the $2k-r$ red vertices already in $B$ we then get a clique of size\[ b + \left( (k+1-b) \right) 		+ \left( 2k-r \right) = 3k+1 - r \ge 2r + 1 \]since $k \ge r$, contradiction. $\blacksquare$ [/quote]
There are $2r-k$ red vertices in $B$, not $2k-r$
Can be fixed easily, though.

[hide="Click here for solution"]

Define $f(A)$ as the size of maximum clique of $A$ where $A\subseteq G$.
Then, we are to devide $G$ into partition $(A,B)$ such that $f(A)=f(B)$.

Write $K_{2n}$ be the maximum clique of $G$.
Let $A=G$ and $B=\emptyset$.
Obviously, $f(A)>f(B)$.

At each step, put $x\in K_{2n}\cap A$ into $B$.
Each step makes $f(A)-f(B)$ decrease by $1$ or $2$.
So there exists a time when $f(A)-f(B)\in\{0,1\}$.
If $f(A)-f(B)=0$, then proof. So we assume that $f(A)-f(B)=1$.

As $B\subseteq K_{2n}$, we write $B=K_t$.
Then $K_{2n-t}\subseteq A$. We write it as $S$.
As $f(B)=t$, we have $f(A)=t+1$. So $t\ge n$.
So we have several $K_{t+1}\in A$.
We write them as $M_1,M_2,\cdots,M_s$.
If there is $S\backslash M_i\ne\emptyset$, move one of the elements to $B$.
After that, $f(A)=t+1$ and $f(B)=t+1$ ($B$ and the elements are all from $K_{2n}$).
Therefore, we can assume that $S\subseteq M_i$ for all $i=1,2,\cdots,s$.

As $|M_i|=t+1\ge|S|$, there is vertice set $T\subseteq \left(\cup M_i\right)\backslash S$ such that $|M_i\backslash T|=t$.
Now, we put $T$ into $B$. Then, $f(A)=t$. Now, we prove that $f(B)=t$.
Assume that $f(B)>t$. There must be $T_0\subseteq T$ and $X\subseteq B$ such that $T\cup X$ makes up a larger clique.
So, $f(B)=|T\cup X|=|T|+|X|\ge t+1$. However, $S\cup T\cup X$ is a clique from $G$ and $|S\cup T\cup X|=|S|+|T|+|X|\ge n+t+1\ge 2n+1$.
It contradicts $f(G)=2n$. So proof!

[/hide]

[u]Solution:[/u] We take the obvious graph interpretation, i.e., let a vertex denote competitor and let an edge denote friendship. Let the rooms be $A$ and $B$. Let $X$ denote a maximal clique and let it have $2x$ vertices. The idea here is to move competitors from one room to the other (pairwise). When we put the vertices of $X$ into $A$ and $B$ in that order, the size of the largest clique in $A$ would be $2x$ and in $B$ at most $2x$ (note the bound). Also let $A'$ denote a maximal clique of $A$. Assume that they don't have the same clique size (with $A$'s larger), as if they do than we would already have the desired result. As indicated above in this post, we'll move the vertices (competitors) from $A$ to $B$ one at a time. We continue this process whenever $A$ has the larger size of a maximal clique than $B$ (notice that the case when we don't continue the process is when $B$ has a larger size of a maximal clique than $A$, and from our "moving process," $B$ has a maximal clique of size $k$, $A$ has a maximal clique of size $k-1$). Consequently, we easily get that $k \geq x+1$ from $B$ and $k-1 \leq x-1$ from $A$, which is absurd, so thus $A$ has at least $x$ vertices of $X$. Denote by $B \cap X = X'$ (has at most $x$ vertices coming from $X$).  Note we get a ton of friendships from $A'$ w.r.t $X'$, so obviously the union would be a clique. Let $y \in X'$ s.t $y$ is not a maximal clique of $B$. Then if we reverse our process (i.e., move $B$ back to $A$), then that would obviously increase the size of the maximal clique, and hence $A$ and $B$ both have maximal clique size $k$. This tells us that $X'$ belongs in every maximal clique of $B$. Now consider the set formed by removing the elements of $X'$ from a maximal clique of $B$, and move every vertex to $A$. From this, we can get that the size of the maximal clique of $A$, $A'$ is at most $k-1 \implies$ the original rooms $A$ and $B$ have the same maximal clique size $k-1$, as desired. $\square$

[quote=Valentin Vornicu]In a mathematical competition some competitors are friends. Friendship is always mutual. Call a group of competitors a [i]clique[/i] if each two of them are friends. (In particular, any group of fewer than two competitiors is a clique.) The number of members of a clique is called its [i]size[/i].

Given that, in this competition, the largest size of a clique is even, prove that the competitors can be arranged into two rooms such that the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room.

[i]Author: Vasily Astakhov, Russia[/i][/quote]

Consider a graph $G$ with $n$ vertices and an edge between any two vertices(competitors) if they are friends.
Now consider two groups with one group having all the competitors and the other containing no competitors.
For convinence,denote both the rooms by $R_1$ and $R_2$ and define $C(R_n)$ as the largest size of a clique in a particular room.
By definition,at the starting we have $$\mathcal{C}(R_1)=2n \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \mathcal{C}(R_2)=0$$
Continue the process as long as it isn't negative; we either obtain $\mathcal{C}(A)+1=\mathcal{C}(B)$ or $\mathcal{C}(A)=\mathcal{C}(B)$
Now suppose that the first case holds i.e $\mathcal{C}(A)+1=\mathcal{C}(B)=k+1$ and by default the largest clique is of $2m$
Move 1 person for the second room to the first.Then we have two cases:-
$\;\;\;  \bullet$ All people in the clique in room 2 know everyone in room 1:-Then move everyone to rome 1.There's a clique of size $2k+1$ in room 1 and this is the largest clique among the competitors since otherwise if someone knows all the people in the clique in room 1,then his count increases one of that in room 1 or 2,contradiction.
$\;\;\; \bullet$ No one in the clique from room 2 know anyone in room 1:-Then simply transfer one of them;there is a clique of $k$ in both of them.$\blacksquare$

We will prove this statement by constructing such a division of the competitors into two rooms.

Let the largest size of a clique be $k$. Since $k$ is even, we can divide the clique into two groups of $k/2$ competitors each. Let these two groups be called $A$ and $B$.

Now consider any other clique in the competition. It must have a size less than or equal to $k$, since we have assumed that $k$ is the largest size of a clique. If the size of this clique is less than $k/2$, then it can be fully contained in either group $A$ or group $B$. If the size of this clique is $k/2$, then it must contain exactly one competitor from each group $A$ and $B$.

Therefore, we can divide the competitors into two rooms such that the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room by putting group $A$ in one room and group $B$ in the other room.

Notice that in the construction above we made use of the fact that the largest clique is even. This is important because if the largest clique were odd, we could not divide it into two groups of the same size, which would make the construction above impossible.

Call the rooms $A$ and $B$. Start with $A$ having one of the largest cliques, and $B$ having everyone else. Let the largest size of a clique of any set $S$ of competitors $m(S)$. Let the maximum in general be $2m$. Here, we see $A$ and $B$ as sets. Evidently, $m(A)\ge m(B)$. As long as $m(A)>m(B)$, take one member of $A$ and move them to $B$. This increases $m(B)$ by at most one and decreases $m(A)$ by exactly one. Thus, $m(A)-m(B)$ decreases by one or two at a time. Since we do this process until it is non-positive, at the end of the process it will be $0$ or $-1$.

If it is $0$ we are done. Suppose it is $-1$. Let $X$ be the subset of $A$ that is part of one of the largest cliques of $A$, and $Y$ be the subset of $B$ that is part of one of the largest cliques of $B$. If for some $p\in Y$, $p$ is not friends with $x$ for some $x\in X$, then moving $p$ to $A$ will not change $m(A)$ but will decrease $m(B)$ by one. If for some $q\in B\setminus Y$, $q$ is friends with each of the competitors in $X$, then moving $q$ to $A$ will not change $m(B)$ but will increase $m(A)$ by one. Thus, if either of these conditions are true, we are done. Assume
[list = "i"]
[*] For each $p\in Y$, $p$ is friends with each $x\in X$.
[*] For each $q\in B\setminus Y$, $q$ is not friends for some $x\in X$.
[/list]
By the first condition, for any pair $(x,y)$ in $(X,Y)$, $x$ and $y$ are friends. Since $X$ and $Y$ are both cliques, $X\cup Y$ is also a clique. Since \[2m(X)<m(X)+m(Y)=m(X+Y) \le m\] so $m(X)\le m-1$. However, this means that we moved at least $m+1$ from $A$ to $B$ in our first process. Thus, $m(A)-m(B)\le -2$, contradiction.

I see that there's a lot of solutions posted! Here's my only hard combo problem solved lol
in fact I think it might be unique, but my heuristic was really simple so probably not.
Call the rooms A and B, with splitting them s.t. A has the largest clique and B has everyone else, with the maximum 2x size clique and y and z representing the size of their respective largest cliques. We move an arbitrary person from A to be continuously, meaning y decreases by 1 every time and z increases by at most 1, stopping when z-y=0 or 1. Now if it's 0 we're done, so suppose it's 1. Call a person who did not come from room A $different$ and someone who did but now in B $friendzoned.$ If there is a friendzoned person not in z, just move it, which increases y by 1 and we're done. If there are multiple largest cliques in B, we can just take any friendzoned person who would join the clique in A from B, and we would be done (since there'd be at least one clique that stays the same size, yet y would +1). If not, then every friendzoned person must be both in the unique largest clique z, with at least one different person (since if otherwise, both A and that largest clique only contain members that come from A, and because y was originally even we can evenly split), and we can take them and move them to A, which will subtract one from z but not add one to y since they were not a person from A, meaning they would not fit in/add to y as a clique member. $\blacksquare$

Solved with [b]AdventuringHobbit[/b] and others.

Have a left side and a right side; an LHS and RHS respectively, for short. Start with everything on the LHS. Let $C$ be a maximally sized clique. Move elements of $C$ one by one from the LHS to RHS, until all of them are on the RHS. Now, at each step of this process, the largest clique size on the LHS stays the same or decreases by one and that of the RHS increases by one. Thus, either eventually they must cross, and if they do then at that point we are done, or at some point the LHS has maximal clique size $k+1$ and the RHS has $k$ elements of $C$ and then after one step the maximal clique size for the LHS goes down to $k$ where the RHS goes up to $k+1$ elements of $C$. Now, observe that every maximally sized clique on the LHS before this step should contain $C\cap$LHS; otherwise we could take the element in $C$ on the LHS not in a maximally sized clique and move it to the RHS, thus increasing the maximal clique size of the RHS to $k+1$ but leaving that of the LHS at $k+1$ and finishing the problem. Now, every maximally sized clique on the LHS cannot only be $C\cap$LHS because then its size would add to $k+1$ to make the size of $C$, which would make that size $2k+1$, but that is odd, contradicting problem condition. Hence, moving all elements outside of $C$ that connect to every element of $C\cap$LHS to the RHS ensures that no more $k+1$-sized clique on the LHS can remain as it would have to contain all of $C\cap$LHS and then at least one of the elements which we just moved. This leaves the LHS with maximal clique size $k$, and we claim that the RHS remains at maximal clique size $k$ as well: we know that it was at $k$ before so now the maximal clique size will be at least $k$, and every element of the RHS connects to every element of $C\cap$LHS, meaning any clique on the RHS combined with $C\cap$LHS can have at most the size of $C$, which is the same as the size of the original $C\cap$RHS clique combined with $C\cap$LHS, so any new clique cannot have a larger size and thus has size at most $k$. This proves that the largest clique size on the RHS is at least $k$ and at most $k$, hence equal to $k$ and in particular equal to the largest clique size on the LHS, as desired.


[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=35832]mathleague results[/url]

in my opinion, one who does well on the AMC does not necessarily do well on the USAMO.
besides the fact that the USAMO is much harder, they require a little different skills.
simlilarly for math league; it was fun finding the USAMO qualifiers among the people who did well on the math league  :)

Congrats everybody!

well... mathleague is sorta "fun test" to do for people advanced enough to be qualified for AIME. I dont think anyone who is USAMO qual should have difficult time doing any of the ML problems.


Let $a_{1},a_{2},...,a_{n}$ be non-negative real numbers. Find the greatest constant $k$ such that
\[\sum_{i<j}\frac1{a_{i}^{2}+a_{j}^{2}}\geq \frac k{(a_{1}+a_{2}+\cdots+a_{n})^{2}}.\]

The case n=4 is posted here by me. The case n=3 is of VASC and my friend Nguyen Viet Anh.


[quote="eminem"]a,b,c,d are all real and positive and $a^4 + b^4 + c^4 + d^4 = 4abcd$

prove $a=b=c=d$[/quote]

[hide]
AM-GM , $a^4+b^4+c^4+d^4\geq 2a^2b^2+2c^2d^2$

$4abcd\geq 2a^2b^2+2c^2d^2$  :arrow:  $(ab-cd)^2\leq 0$  :arrow: $ab=cd$

The equality holds when $a=b$ , $c=d$ . So we have $a^2=c^2$ :arrow: $a=c$

Hence $a=b=c=d$
 :)
[/hide]

[quote="Labiliau"]Yes, or just AM-GM :

$\frac{a^4+b^4+c^4+d^4}{4} \geq \sqrt[4]{a^4b^4c^4d^4} = abcd$ with equality iff $a=b=c=d$[/quote]

Oh.  Aha.  Good point  :D

[quote="K81o7"]I believe this is called the power mean, that
$\sqrt{\frac{a_1^n+a_2^n+...+a_n^n}{n}}\ge\frac{a_1+a_2+...+a_n}{n}$
Then one just uses AM-GM.  The Power Mean follows from a special case of Cauchy, i think...
$n(a_1^n+a_2^n+...+a_n^n)\ge(a_1+a_2+...+a_n^n)^n$
that is, if i'm not mistaken...[/quote]
This is just a special case of power mean. The power mean is indeed:
Let $a_1,a_2,\cdots,a_n$ be positive reals and $p>q$ be two real numbers. Then
$M^p(a_1,a_2,\cdots,a_n)\geq M^q(a_1,a_2,\cdots,a_n)$ , or,
$(\frac{a_1^p+a_2^p+\cdots+a_n^p}{n})^\frac{1}{p} \geq (\frac{a_1^q+a_2^q+\cdots+a_n^q}{n})^\frac{1}{q}$
Equality holds iff $a_1=a_2=\cdots=a_n$
By convention, $M^0(a_1,a_2,\cdots,a_n)$ is defined to be $\sqrt[n]{a_1a_2\cdots a_n}$

FWIW - If you want to show-off as knowing nothing about AM-GM  and want to show it with simple algebra
[hide]$0=a^4+b^4+c^4+d^4-4abcd = (a^2-b^2)^2 + (c^2-d^2)^2 + 2(ab-cd)^2$
is possible only if each squared quantity is zero: so $a^2=b^2;c^2=d^2;$ last one gives $a^2=c^2$  [/hide]

My method......
Write $a^4 +b^4$ as $(a^2+b^2)^2-2(a^2b^2 )$ and the same with the c and thing.send the $2(a^2b^2)$ stuuffs over to the r.h.s,write 4abcd as 2abcd+2abcd and take out common n stuff...u'll finally get....

$(a^2+b^2)^2+(c^2+d^2)^2+2(ab-cd)^2=0$

so then equate each of them to 0.


We call $A_{1},A_{2},A_{3}$ [i]mangool[/i] iff there is a permutation $\pi$ that $A_{\pi(2)}\not\subset A_{\pi(1)},A_{\pi(3)}\not\subset A_{\pi(1)}\cup A_{\pi(2)}$. A good family is a family of finite subsets of $\mathbb N$ like $X,A_{1},A_{2},\dots,A_{n}$. To each goo family we correspond a graph with vertices $\{A_{1},A_{2},\dots,A_{n}\}$. Connect $A_{i},A_{j}$ iff $X,A_{i},A_{j}$ are mangool sets. Find all graphs that we can find a good family corresponding to it.

I suppose it's all the complementary gragh of a gragh consisting of several non-intersecting complete paragraphs

The answer is that all graphs correspond to some good family.

We will only use the following two results about mangool sets:

[b][color=#f00]Claim 1: [/color][/b] If $X \not\subset A_i \cup A_j$ and $A_i \not\equiv A_j$, then $\{X,A_i,A_j\}$ is mangool.

[i]Proof: [/i] Note at least one of $A_i \not\subset A_j$ or $A_j \not\subset A_i$ is true, and our Claim follows. $\square$

[b][color=#f00]Claim 2: [/color][/b]If $A_i,A_j \subset X$ and $X \subset A_i \cup A_j$, then $\{X,A_i,A_j\}$ is mongool.

[i]Proof: [/i]Just note that
$$ A_i \subset X \cup A_j ~~,~~ A_j \subset X \cup A_i ~~,~~ X \subset A_i \cup A_j $$
so our Claim follows. $\square$

We return to our main problem now. Fix any graph $G$ on $n$ veritces. We look at $\overline{G}$ (complement of $G$). We construct a good family satisfying the following:
[list]
[*] $ A_1,A_2,\ldots,A_n \subset X $
[*] $A_1,A_2,\ldots,A_n$ are pairwise distinct.
[*] For any $A_i,A_j$, they are connected in $\overline{G}$ iff there is a element of $X$ which is in neither of $A_i,A_j$.
[/list]
then we are done. We do this now!
Originally start with any set $X$ containing a lot of elements and take
$$ A_1 \equiv A_2 \equiv \cdots \equiv A_n \equiv X $$
To any edge of $A_iA_j$ of $\overline{G}$, we correspond a unique element $\alpha \in X$. Then we remove element $\alpha$ from sets $A_i,A_j$ only (and not any other $A_k$). This way, note the first and third condition are satisfied. Lastly we require all $A_1,\ldots,A_n$ to be distinct. To do this, pick a set $Y$ disjoint from $X$. Add $Y$ to each of the sets $X,A_1,A_2,\ldots,A_n$. Then from each $A_i$, remove some unique element of $Y$. This completes the proof. $\blacksquare$

[b][color=#00f]Remark: [/color][/b] In the above proof, we are assuming $X \subset X$. Even if $X \not\subset X$ was meant, then that is easy to fix. Basically after constructing as above, to each edge $A_iA_j$ of $G$, we correspond a unique element $\beta$ which is not in either of $X,Y$. Then we add $\beta$ to both of $A_i,A_j$ only (and not any other $A_k$).


[quote="HUY VAN"]Prove that
$a+b+c\geq\frac{2}{3}(\sqrt{a^{2}+bc}+\sqrt{b^{2}+ca}+\sqrt{c^{2}+ab})$
for all non-negative real numbers $a, b, c$[/quote]
See here:
http://www.artofproblemsolving.com/Forum/viewtopic.php?t=63645


number theory
greatest common divisor
least common multiple

1-If (b,c)=1, then (a,bc) = (a,b)(a,c)

2-If a=ga and b=gb where g=(a,b), then [a,b]=g * a * b where a and b are positive integers.

3-abc=(ab,bc,ac)*[a,b,c]

4-abc≥(a,b,c)*[a,b,c]

5-(a,[b,c])=[(a,b),(a,c)]

well, if no one comes out to explain them, i dont think i can believe that :)

I know this may sound not very good but please try to solve these 5 problems.
I really need their solns today.

P.S: I'm sorry and ashamed for being like telling the others to solve my problems, but there's no way out. :blush:  :maybe:

OK, here's #1 I think:

Let (a, b) = f and (a, c) = g.
Let b and c satisfy b = f*b and c = g*c.
(b, c) = 1 --> (f*b, g*c) = 1 --> (f, g) = 1.
f | a and g | a --> a = f*g*a.
a = f*g*a, b = f*b, and c = g*c -->
(b, g*a) = 1 and (c, f*a) = 1 -->
(b, a) = 1 and (c, a) = 1 -->
(b*c, a) = 1.

Thus, (a, bc) = (a, f*b*g*c) = (f*g*a, f*g*b*c).
(b*c, a) = 1 --> (f*g*a, f*g*b*c) = f*g = (a, b) * (a, c).

If something is unclear or wrong, I can fix  :) .

This smacks of a request for homework solutions.  If that is the case I think it would be more appropriate to discuss the concepts behind the class so that you can build up your ability to solve the homework problems on your own.

It might be wise to train yourself to understand the ways in which GCDs and LCMs relate to the prime factorizations of integers.

Oh no its not a school-home work stuff (BTW school has no yet begun here in Albania, it begins after two weeks)
Im working on my own with some olympiad training books but the exercises there (except for the example ones) have no solutions.
so the ones Ive recently posted here are a few of them.

BTW I already have a soln for 3

[a, b, c]=[[a, b], c]=[ab/(a, b) ,c]=abc/(a,b) / (ab/(a, b) ,c)=abc/(a,b)*(ab/(a, b) ,c) =abc/(ab,(ca,cb)=abc/(ab,bc,ac)

If (b,c)=1, then (a,bc) = (a,b)(a,c)

Let

Using the fundamental theorem of algebra:

a = Prod(pi^xi)
b = Prod(pi^yi)
c = Prod(pi^zi)

Clearly, because (b,c) = 1, at least one of each yi and zi = 0

Hence:

(a,bc) = Prod(pi^(min(xi,yi+zi))
(a,b) = Prod(pi^(min(xi,yi))
(a,c) = Prod(pi^(min(xi,zi))

However, for all i, either yi or zi = 0.

It then follows that if yi = 0, then the corresponding ith prime power in (a,b) is equal to 1.

The corresponding term in (a,bc) is then pi^(min(xi,zi)) but this is exactly equal to the corresponding term from (a,c).

Hence (b,c)=1, then (a,bc) = (a,b)(a,c) as desired.

[quote="Peter VDD"]these questions have no real problem-solving value, that's why no one solves them :)

If you understand what lcm and gcd is, just go ahead and switch to the next page.[/quote]

I agree, although these might have some value in number theory questions.


Hello,

 I am wondering if the following problem can be solved. I need to find the Angles A or B or C or D or Distance x.

Problem is as stated in the figure below:
http://data.at.preempted.net/posts/angle.jpg

Thank you,
Sarad.

The problem doesn't seem to be well defined. The value of x looks to be arbitrary.

[color=darkred]Hint[/color]

[hide]Pythagorean theorem  and cosines low :wink: [/hide]


Prove that at least one of the numbers $ a(a\minus{}c)\ ,\ a(a\minus{}2b)\ ,\ b(b\minus{}1)\ ,\ c(c\minus{}b)\plus{}1\ ,\ 2b^2\minus{}c\ ,\ 2c^2\minus{}a$ is positive .

[quote="alex2008"]Prove that at least one of the numbers $ a(a \minus{} c)\ ,\ a(a \minus{} 2b)\ ,\ b(b \minus{} 1)\ ,\ c(c \minus{} b) \plus{} 1\ ,\ 2b^2 \minus{} c\ ,\ 2c^2 \minus{} a$ is positive .[/quote]

Add them all we get $ 2a^2\plus{}3b^2\plus{}3c^2\minus{}ac\minus{}2ab\minus{}bc\minus{}a\minus{}b\minus{}c\plus{}1$

which is equal to $ (a^2\minus{}a\plus{}\frac{1}{4})\plus{}(b^2\minus{}b\plus{}\frac{1}{4})\plus{}(c^2\minus{}c\plus{}\frac{1}{4})\plus{}(a^2\plus{}2b^2\plus{}2c^2\minus{}ac\minus{}2ab\minus{}bc)\plus{}\frac{1}{4}$
$ \ge (a^2\plus{}2b^2\plus{}2c^2\minus{}ac\minus{}2ab\minus{}bc)\plus{}\frac{1}{4}$ (because $ x^2\minus{}x\plus{}\frac{1}{4}\equal{}(x\minus{}\frac{1}{2})^2 \ge 0$ for all real $ x$)

$ \equal{} \frac{(a\minus{}2c)^2\plus{}(b\minus{}2c)^2\plus{}3a^2\minus{}8ab\plus{}7b^2}{4}\plus{}\frac{1}{4}$
$ \ge \frac{3a^2\minus{}8ab\plus{}7b^2}{4}\plus{}\frac{1}{4}$
$ \equal{}\frac{(\sqrt{3}a\minus{}\frac{4}{\sqrt{3}}b)^2\plus{}\frac{5}{3}b^2}{4}\plus{}\frac{1}{4}$
$ \ge \frac{1}{4}$

As sum of the numbers is positive, at least one of the numbers must be positive.


Wanda weighed her four pet pot-bellied piglets in pairs. Together Oinker and Squeaker weighed 110 pounds. Squeaker and Curly weighed 103 pounds and Curly and Porker totalled 108 pounds. How many pounds would Oinker and Porker weigh together?

We are given that
\begin{align}
O+S &= 110 \\
S+C &= 103 \\
C+P &= 108
\end{align}
Subtracting $ (2)$ from $ (1)$ gives us $ O-C=7$.  Adding this to $ (3)$ gives us $ O+P=\boxed{115}$.

for this problem we need to assign some variable but all we need to know is just O AND P we DO NOT need to know the individidual but JUST THE 0+P

so it looks like this

O+S=110-----1
S+C=103-----2
C+P=108-----3

subtract 1-2 and get O-C=7 and subtract this by 3 and get O+P=115

[color=#0080FF][b][i][u]PLEASE RATE MY POST THANK YOU SO MUCH!!!!!![/u][/i][/b][/color]

:ddr: :ddr: :ddr: :ddr:


inequalities
Cauchy Inequality
inequalities unsolved

I have a solution but i want to find another solution!!!!
Let x,y,z positive numbers that satisfy:

        (1/ :sqrt: 1+3x^2)+(1/ :sqrt: 1+3y^2)+(1/ :sqrt: 1+3z^2)>=3/2
Prove:
               a)x+y+z>=3xyz.
               b)27xyz<=3+5(x+y+z)+3(xy+yz+xz).

Let $ x,y,z $ be 3 positive numbers satisfied
$ \frac{1}{\sqrt{3x^2+1}}+ \frac{1}{\sqrt{3y^2+1}}+ \frac{1}{\sqrt{3z^2+1}} \geq\ \frac{3}{2} $
Prove
         $  a)  x+y+z \geq\ 3xyz $
         $  b)  27xyz \leq\ 3+5(x+y+z)+3(xy+yz+xz) $

I only have solution for a).

a) $ x+y \geq\ z(3xy-1) $
If $ xy \leq\ 1/3 $ then a) obviously true.
If $ xy > 1/3 $  then
Assume $ x \geq\ y \geq\ z. $ We easily prove that $ z \leq\ 1 $
If $ x \leq\ 1 $ then $ xyz \leq\ 1 $ and use Cauchy inequality we have $ x+y+z \geq\ 3(xyz)^\frac{1}{3}\geq\ 3xyz $
If $ x>1 $ then
Let $ x= \frac{tanA}{\sqrt{3}} $ and $ y=\frac{tanB}{\sqrt{3}} $$ (0<A,B<90)  $
Because $ x \geq\ 1 $ so $ A \geq\ 60 $
If $ B \leq\ 30 => y \leq\frac{1}{3} => z \leq\frac{1}{3} $ we only have to prove $ x+y \geq\frac{1}{3}(3xy-1) $
$<=> 3x(1-y)+3y+1 \geq\ 0 $

If $ B>30 => $ triangle ABC is an acute triangle.

Replace $x=\frac{tanA}{\sqrt{3}}$ ,$y=\frac{tanB}{\sqrt{3}} $ in the condition. We have $ z \leq\frac{tanC}{\sqrt{3}}$ because $ cosA+cosB+cosC \leq\frac{3}{2} \leq\ cosA+cosB+\frac{1}{\sqrt{3z^2+1}} $
So all we have to do is replace z by $\frac{tanC}{\sqrt{3}} $ and prove the new inequality with the acute triangle ABC which is
$ tanA+tanB+tanC \geq\ tanAtanBtanC $ (this is an equality)

I think that b) can do in the same way but I haven't finished yet.


modular arithmetic
number theory unsolved
number theory

Prove that if an integer is divisible by two distinct odd primes, then it does not have a primitive root.

Here is where I stand: For any numbers not 1 or 2, $ \gcd(\phi(m),\phi(n))>1$ and if $ \gcd(m,n)\equal{}1$, $ a^{h}\equiv 1\pmod{m}$, $ a^{k}\equiv 1\pmod{n}$, then $ a^{j}\equiv 1\pmod{mn}$ where $ j\equal{}\frac{hk}{\gcd(h,k)}$.  I know I am supposed to use these two facts.

Also, prove that the only numbers with primitive roots are $ 2$, $ 4$, $ p^{r}$, and $ 2p^{r}$ where $ p$ is prime.  I've already proved that $ 2^{n}$ can't have a primitive root for $ n\geq 3$, and the above result should get rid of a lot more.  How do I complete it?

I'm bad at NT, but...
Let $ n\equal{}p^r q^s m$, where $ p,q$ are distinct odd primes, and $ m$ is the rest of the number we don't care about ($ (p,m)\equal{}(q,m)\equal{}1$).
By Euler's totient theorem, we have $ a^{\phi(p^r)}\equiv1 \pmod {p^r}$ and $ a^{\phi(q^s)}\equiv1 \pmod {q^s}$. Letting $ j\equal{}\frac{\phi(p^rq^s)}{(\phi(p^r),\phi(q^s))}$, we have $ a^j\equiv 1 \pmod{p^rq^s}$. But clearly, $ (\phi(p^r),\phi(q^s))\neq 1$, as both $ \phi(p^r)$ and $ \phi(q^s)$ must be even.
From here, we see that the number $ n$ has a multiplicative order no more than $ \frac{\phi(n)}{2}$, which implies that it cannot have primitive roots.

Thanks.  That certainly seems to make sense.  Along the lines of what I was thinking, just not including the multiplicative order part.


3. What value of Delta T should be used for the calorimetry experiment that gives these graphed results?

(A) 10 °C
(B) 12 °C
(C) 15 °C
(D) 19 °C

The website keeps saying it's B, but how is it not A?

oh yea, this is a USNCO question that i still never got...

My interpretation of the graph is that u are adding something hot to a substance and the temp of the system obviously goes up. After some time it will then regress as seen during t=10 min and after. Therefore, for thermodynamic calculations, we would assume that the change in temperature would be T(10) - T(6) or 34-24 = 10 A.... But alas this is wrong...

Ahh...This question is a tricksy one indeed.

In a coffee cup calorimeter (which this "experiment" was most likely run in), there is a good loss of heat from inside the calorimeter. Thus, there is no possible way to examine the maximum temperature solely from this curve. To obtain a good estimate of the value, one should extrapolate from the down sloping cooling curve and the upward heating curve. The intersection of the two corresponds to the maximum temperature, which is 36 deg C. Thus, the temperature difference is 12 deg C.

Thats the most retarded question ive ever seen on the usnco...

you don't need a perfect 60 on the MC to go to the camp ya know...

actually i know of people who got like 50/60 and still made it

But the question doesnt even specify coffee cup calorimetry. Thus assuming that heat is lost in some coffee cup is  quite a bold assumption.

Well, a bomb calorimeter is very insulated, and probably wouldn't have such drops in temperature. So, it is fine to assume it was done in a coffee cup. Besides, it's never a good idea to select an answer that is easily determined on the USNCO.

Okay, if you have a 50/60 on the MC, then you would need a near-perfect score on the FR?

is it that hard to do?
hehe
well it just matters on your overall performance.

I don't know too many people who get perfect scores on the MC. Plus, it's not important either. The national exam has nothing to do with the study camp or the selection of the traveling team.

@elite: This was like problem 3...

I still find this problem retarded...


I'm studying some problems, for the compass exam. If I need help is it okay to post them here? I will post what I did so far and why I am stuck.

I think it's ok for you to post them here.

Could someone help me to understand how to start this problem.

please :blush:


special factorizations
number theory solved
number theory

Let $x$ and $y$ be two integers not equal to $0$ such that $x+y$ is a divisor of $x^2+y^2$. And let $\frac{x^2+y^2}{x+y}$ be a divisor of $1978$. Prove that $x = y$.

[i]German IMO Selection Test 1979, problem 2[/i]

suppose we have (x^2+y^2)/(x+y) =  \pm A, with A a positive integer divisor of 1978, then (x^2+y^2) = A*(x+y) so A|(x^2+y^2); x^2+y^2 = 0 mod A, and if p is a prime divisor of A, x^2 + y^2 = 0 mod p

now 1978 = 2*23*43 is a square-free integer, so A must also be a square-free integer.  Then A cannot have any prime divisors q congruent to 3 mod 4,  since x^2+y^2 = 0 mod q is impossible for q = 3 mod 4.  23 = 43 = 3 mod 4, 23 and 43 do not divide A, so A must be either 1 or 2.

If A = 2, then our original equation (x^2+y^2)/(x+y) =  \pm A becomes x^2+y^2 =  \pm 2*x  \pm 2*y, subtracting and completing the square, (x  \pm 1)^2 + (y \pm 1)^2 = 2, so (x  \pm 1)^2 = (y \pm 1)^2 = 1, so either x = y = \pm 2 or one of x or y = 0

If A = 1, then we have x^2+y^2 = \pm (x+y), and the only soltion with x nor y equal to 0 is when x = y =  \pm 1

so in all cases, x = y.


calculus
integration
algebra
polynomial
partial fractions
calculus computations

Evaluate $\ds{\sum_{n=1}^\infty{\frac{9n+4}{n(3n+1)(3n+2)}}}.$
(A. Kukush)

hint
[hide]partial fraction[/hide]

I'm not looking at whatever Moubinool has hidden.

Step 1: use partial fractions to turn the sum into

$3\sum_{n=1}^{\infty}\left[\frac2{3n}-\frac1{3n+1}-\frac 1{3n+2}\right]$

Step 2: Introduce a variable. Define

$f(x)=3\sum_{n=1}^{\infty}\left[\frac{2x^{3n}}{3n}-\frac{x^{3n+1}}{3n+1}-\frac{x^{3n+2}}{3n+2}\right]$

Step 3: Differentiate:

$f'(x)=3\sum_{n=1}^{\infty}\left(2x^{3n-1}-x^{3n}-x^{3n+1}\right)$

This is a geometric sum:

$f'(x)=3\cdot\frac{2x^{2}-x^{3}-x^{4}}{1-x^{3}}= 3\cdot\frac{2x^{2}+x^{3}}{1+x+x^{2}}$

We have now represented the sum as the following integral:

$3\int_{0}^{1}\frac{2x^{2}+x^{3}}{1+x+x^{2}}\,dx$

Step 4: Do the integral. (Can be done with sufficient patience.)

Can you explain why we have to specify the interval of the integral in $(0,1)$ ? Cant it be in other region ? Thanks

It is since we want to know $f(1)$ and it is clear $f(0) = 0$. Integrating that gives us $f(1)-f(0) = f(1)$. Integrating with other bounds surely doesn't give us anything useful...

Interesting solution with power serie Kent, here another one.

 use partial fractions in the partial sum

$3\sum_{n=1}^{N}\left[\frac2{3n}-\frac1{3n+1}-\frac 1{3n+2}\right]=3(H(N)-H(3N+2))+\frac{3}{2}+3$  where

$H(N)=\sum_{k=1}^{N}\frac{1}{k}=\gamma+ln(N)+o(1)$ when N tends to infty

The sum is $-3ln3+\frac{9}{2}$

I posted my previous answer before I even attempted to do the integral. At the time I assumed that the integral computation would be tedious. It turns out to be much quicker than I had assumed.

By long division,

$\frac{x^{3}+2x^{2}}{x^{2}+x+1}=x+1-\frac{2x+1}{x^{2}+x+1}.$

Given that, $3\int_{0}^{1}x+1-\frac{2x+1}{x^{2}+x+1}\,dx$

$=\left.3\left[\frac12x^{2}+x-\ln(x^{2}+x+1)\right]\right|_{0}^{1}= \frac92-3\ln3$

A note to the calculus beginners here: why should this series even be convergent?

If we were to multiply out the polynomials (which we won't actually do because we don't need to), the highest degree term in the numerator of the fraction would have an $n$ and the highest degree term in the denominator an $n^{3}.$ Therefore for large $n,$ the terms of the series would closely resemble a constant times $\frac1{n^{2}}.$ Hence the series converges by limit comparison to $\sum\frac1{n^{2}}.$

We needed to do this argument before we performed the partial fractions expansion. The expanded form obscures the estimate for the size of the terms.

Seeing this much - that the series converges (absolutely) - is very quick. Computing the value is something else.

However, in my calculation, I did need a separate argument that the series coverges. I need that because it's a hypothesis of Abel's Theorem on power series, and I am using Abel.


Math’s will be my downfall..

66 = 2 * 1 000 000 log2  y.

That is log to the base 2.. know how would I go about find y.
thax

[hide]Therefore 33/1000000=log2(y) -> y=2^(33/1000000). Is that what you mean (the equation is kind of confusing)?[/hide]

yes u've got what i meant

r u saying that y =  2 to the power of 33 devided by 1000000

Yes, that is what jb05 meant

y=2^(33/1000000)

Hence the parenthesis

thankyou guys, but can u duble check for me is this what u get for y?

[url=http://img115.echo.cx/my.php?image=hhm8hw.gif][img]http://img115.echo.cx/img115/8690/hhm8hw.th.gif[/img][/url]

whered u get that skin of Firefox anyways....??

https://addons.update.mozilla.org/themes/moreinfo.php?id=72

if u use FlashGot, u must install skin before flashGot or ull get a bug


function
integration
calculus
real analysis
real analysis unsolved

Prove that
\begin{eqnarray*} \sum_{n = 1}^{\infty} \frac{F_n}{2^n \cdot n} & \mbox{is} & \mbox{irrational} \end{eqnarray*}
Or, prove more (and this is actually the [b]real[/b] problem)
\begin{eqnarray*} \sum_{n = 1}^{\infty} \frac{F_n}{2^n \cdot n} & = & \frac{i \cdot 2 \sqrt{5}}{5} \cdot \left( \arctan \left( \frac{i \cdot \sqrt{5}}{5} \right) - \arctan \left( \frac{i 2 \sqrt{5}}{5} \right) \right) \end{eqnarray*}
Implying something more that irrationality :)

The second strikes me as easier than the first; we use the generating function $\frac1{1-x-x^2}=\sum_{n=0}^\infty F_nx^n$ for $|x|<\frac{\sqrt{5}-1}2$.
$\sum_{n=1}^\infty \frac1n F_nx^n=\sum_{n=1}^\infty F_n\int_0^x t^{n-1}\,dt=\int_0^x\left(\sum_{n=1}^\infty F_nt^{n-1}\right)\,dt= \int_0^x \frac{1+t}{1-t-t^2}\,dt$, and the rest is a calculus exercise.

Yes, exactly. The problem relays on the fact that people often forget about generating functions ;)


inequalities
geometry
inequalities proposed

[color=purple]Let ABC and XYZ are two triangle ưith the side length a,b,c ;x,y,z and the area S,S' respectively.Prove that with all m,n,p>0 we have
 $ma[x-(\sqrt{y}-\sqrt{z})^{2}]+nb[y-(\sqrt{z}-\sqrt{x})^{2}]+pc[z-(\sqrt{x}-\sqrt{y})^{2}]\geq 4\sqrt{3m^{2}n^{2}p^{2}SS'}$
        Have fun :D [/color]

[color=purple]Thanks GacKiem ! But have you got a proof for this problem ?
     [/color]


Let a,b,c be positive real numbers.Prove that:
    SUM [a^2(1+a^3)^2/bc(b+c)^3] >=3/2

An ugly and boring inequal:Using Tchebycheff we have:
$\sum\frac{a^2(1+a^3)^2}{bc(b+c)^3}\geq \frac13.\sum a^2(1+a^3)^2\sum\frac{1}{bc(b+c)^3}\geq \frac13.\sum ab(1+a^3)(1+b^3)\sum\frac{1}{ab(a+b)^3}$
By Holder:$(1+1)(1+a^3)(b^3+1)\geq (a+b)^3\to (1+a^3)(b^3+1)\geq \frac12.(a+b)^3$
And by C.B.S we have the result immediately.


complex numbers
geometry
geometric transformation
geometry unsolved

ABCDEF is a convex hexagon, with <B + <D + <F = 360, and AB.CD.FE = BC.DE.FA. Prove that BC.AE.FD = CA.EF.DB :spidy:

It's on the '98 shortlist: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=3488#p3488

You can solve it pretty easily by complex numbers or spiral similarity, and it seems that you can do it by inversion too. A bit contrived in my opinion, but apparently not too hard.


If $ a$ and $ b$ are real numbers, $ a^2b^3\equal{}\frac{32}{27}$, and $ \frac{a}{b^3}\equal{}\frac{27}{4}$, what is $ a\plus{}b$?

We know that $ a^2b^3=\frac{32}{27}$ and $ \frac{a}{b^3}=\frac{27}{4}$, and we can multiply them:

$ a^2 b^3 \cdot \frac{a}{b^3} = a^2 \cdot a \cdot b^3 \cdot \frac{1}{b^3} = a^3$

multiply them, you get $ a^2 b^3 \cdot \frac{a}{b^3} = a^2 \cdot a \cdot b^3 \cdot \frac{1}{b^3} = a^3$ a^3 is equal to 8. Therefore a is 2. Plug into second equation, you get that b is 3/2. 2+3/2 is 7/2


$ S$ majmoooeii shamele $ 2000$ adaade tabieii kochektar az $ 10^{100}$ ,mibashad.asbet konid $ 2$ zir majmoooe natohi va mojjaza az $ S$ manande $ A$ va $ B$ vojod darand betoike $ |A| \equal{} |B|$ va $ \sum_{x\in A}x \equal{}\sum_{y\in B}y$ va $ \sum_{x\in A}x^{2}\equal{}\sum_{y\in B}y^{2}$.

fek konam manzooret $ 10^{100}$ boode...

idash lane kabootarie:
tedade zir majmooehaye $ 1000$ ozvie $ S$ barabar ast ba:

$ \binom{2000}{1000}\equal{}\frac{2000!}{1000!1000!}\equal{}\frac{(2000*1998*1996*...*2)*(1999*1997*...*3)}{1000!1000!}$

amma tavajoh dashte bashid ke $ 1999 > 1998,1997 > 1996,...,3 > 2$ pas darim:

$ \binom{2000}{1000}>\frac{\prod_{i \equal{} 1}^{1000}2i\prod_{i \equal{} 1}^{999}2i}{1000!1000!}$

pas haddeaghal $ \frac{2^{1999}1000!999!}{1000!1000!}\equal{}\frac{2^{1999}}{1000}$ ta zir majmooe $ 1000$ ozvie motafavet darim...

hala tavajoh dashte bashid ke age $ A$ yek zirmajmooe $ 1000$ ozvi az $ S$ bashe oon moghe majmooe morabate aazash
kamtar az $ 1000*10^{200}$e (har ozvi haddeaksar barabare $ 10^{100}$e)...

hala ma haddeaghal $ \frac{2^{1999}}{1000}$ ta zirmajmooe dashtim,ke majmooe morabateshoon maximum barabare
$ 1000*10^{200}\equal{} 10^{203}$e pas tebghe asle lane kabootari haddeaghal $ \frac{2^{1999}}{10^{206}}$ ta zirmajmooe
$ 1000$ ozvi peida mishan ke majmooe morabate aazashoon barabar bashe...

khob hamchenin midoonim majmooe aazae ye zirmajmooe $ 1000$ ozvi kamtar az $ 1000*10^{100}\equal{} 10^{103}$ hast (har
ozvi haddeaksar barabare $ 10^{100}$e...)

pas az beine $ \frac{2^{1999}}{10^{206}}$ ta zirmajmooei ke dashtim,tebghe asle lane kabootari,haddeaghal $ \frac{2^{1999}}{10^{206}*10^{103}}\equal{}\frac{2^{1999}}{10^{309}}$ ta zirmajmooe motamayeze $ 1000$ ozvi peida mishe ke
ham majmooe aaza va ham majmooe morabate aazashoon barabar bashe...

hala dota azin majmooeharo entekhab mikonimo aazaye moshtarakeshoono mirizim dooro baghiashoono negah midarim...

pas kafie sabet konim $ \frac{2^{1999}}{10^{309}}> 1$...  :wink:

rahe rahat tar az inam dare:
ye setai tashkil bedim baraye har zir majmoooe (tedad aaza, majmoe azaa , majmooe tavane dovome azaaa) tedade in $ 3$ taei haa az $ 2^{2000}$ yani tedad zirmajmooehaye $ S$ kamtare pas tebghe kaftari masale hallee