Asymptote
geometry
geometric transformation
geometry proposed

I recall failing to solve this problem in DC.  The key lies in finding
[hide]the cyclic quadrilateral, $ ABQX$[/hide]

$ \angle CXD \equal{} \angle CDB \minus{} \angle XCD$ and $ \angle AQB \equal{} \angle BQP \plus{} \angle AQP \equal{} (180 \minus{} \angle CDB)\plus{} \angle XCD$ so $ \angle CXD \plus{} \angle AQB \equal{} 180$ so $ AQBX$ is cyclic quadrilateral. $ \angle QYP \equal{} \angle QAP \equal{} \angle QXB$ and $ PY\parallel BX$ so $ Q,Y,X$ are collinear. Analogously $ Q,Z,X$ are collinear

[quote="K81o7"]the cyclic quadrilateral, $ ABQX$[/quote]

This follows directly from the fact that $ Q$ is the Miquel point  :wink:

I think I've got a slightly different solution.
$ \angle XCQ \equal{} \angle ACQ \equal{} \angle BPQ \equal{} \angle BDQ$, so $ DXCQ$ is a cyclic quad.
Then $ \angle QXD \equal{} \angle QCD \equal{} \angle QCP \equal{} \angle QYP$. Thus $ \angle QXD \equal{} \angle QYP$, and since $ XB$ and $ YP$ are parallel, it follows that $ Q,X,Y$ are collinear. Similarly, $ Q,X,Z$ are collinear.

$Q$ is the unique center of the spiral similarity sending $CD$ to $AB$, so it is also the unique center of the spiral similarity sending $CA$ to $DB$; hence $DXQC$ and $AXQB$ are concyclic.  Let $Z' = XQ \cap \omega_2$; then \[ \measuredangle CAB = \measuredangle XAB = \measuredangle XQB = \measuredangle Z'QB = \measuredangle Z'PB \implies PZ' \parallel AC \implies Z=Z' \] and $Y=Y'$ is similar.

[asy]/* DRAGON 0.0.9.6
Homemade Script by v_Enhance. */

import olympiad;
import cse5;
size(11cm);
real lsf=0.8000;
real lisf=2011.0;
defaultpen(fontsize(10pt));

/* Initialize Objects */
pair A = (-2.0, 2.0);
pair B = (4.031165686870916, 3.133944005249443);
pair C = (1.0, -2.0);
pair D = (1.0, 0.0);
pair P = IntersectionPoint(A--B,Line(C,D,0,lisf));
pair X = IntersectionPoint(A--C,Line(B,D,0,lisf));
pair O_1 = circumcenter(A,P,C);
pair O_2 = circumcenter(P,D,B);
pair Q = 2*foot(P,relpoint(O_1--O_2,0.5-10/lisf),relpoint(O_1--O_2,0.5+10/lisf))-P;
pair Y_prime = (2)*(foot(O_1,X,Q))-Q;
pair Z_prime = (2)*(foot(O_2,Q,X))-Q;

/* Draw objects */
draw(circumcircle(A,P,C), rgb(0.7,0.8,0.9) + linewidth(1.0));
draw(circumcircle(B,P,D), rgb(0.7,0.8,0.9) + linewidth(1.0));
draw(A--B, rgb(0.4,0.4,0.4));
draw(C--P, rgb(0.4,0.4,0.4));
draw(A--C, rgb(0.5,0.5,0.5) + linewidth(1.0) + linetype("4 4"));
draw(B--X, rgb(0.5,0.5,0.5) + linetype("4 4"));
draw(P--Y_prime, rgb(0.5,0.5,0.5) + linetype("4 4"));
draw(P--Z_prime, rgb(0.5,0.5,0.5) + linewidth(1.0) + linetype("4 4"));
draw(Y_prime--Z_prime, rgb(0.4,0.8,1.0));
draw(circumcircle(C,Q,D), rgb(0.7,0.8,0.9) + linewidth(1.0));
draw(circumcircle(Q,A,B), rgb(0.7,0.8,0.9) + linewidth(1.0));

/* Place dots on each point */
dot(A);
dot(B);
dot(C);
dot(D);
dot(P);
dot(X);
dot(Q);
dot(Y_prime);
dot(Z_prime);

/* Label points */
label("$A$", A, lsf * dir(150));
label("$B$", B, lsf * dir(45));
label("$C$", C, lsf * dir(-90));
label("$D$", D, lsf * dir(60) * 1.414);
label("$P$", P, lsf * dir(100));
label("$X$", X, lsf * dir(225));
label("$Q$", Q, lsf * dir(-45));
label("$Y'$", Y_prime, lsf * dir(225));
label("$Z'$", Z_prime, lsf * dir(-45));
[/asy]

[quote="v_Enhance"]...  Let $Z' = XQ \cap \omega_2$; then \[ \langle CAB = \langle XAB = \langle XQB = \langle Z'QB = \langle Z'PB \implies PZ' \parallel AC \implies Z=Z' \] ...

[/quote]
I've noticed that some people on the forum use Reim's theorem
in particular if we look at circles $AXBQ$ and $PBQZ'$ we have $PZ'||AX$.

[asy]
/* Borrowed then adapted from v_enhance, thanks */
import olympiad;
import cse5;
size(8cm);
real lsf=0.8000;
real lisf=2011.0;
defaultpen(fontsize(11pt));
/* Initialize Objects */
pair A = (-2.0, 2.0);
pair B = (4.031165686870916, 3.133944005249443);
pair C = (1.0, -2.0);
pair D = (1.0, 0.0);
pair P = IntersectionPoint(A--B,Line(C,D,0,lisf));
pair X = IntersectionPoint(A--C,Line(B,D,0,lisf));
pair O_1 = circumcenter(A,P,C);
pair O_2 = circumcenter(P,D,B);
pair Q = 2*foot(P,relpoint(O_1--O_2,0.5-10/lisf),relpoint(O_1--O_2,0.5+10/lisf))-P;
pair Y= (2)*(foot(O_1,X,Q))-Q;
pair Z = (2)*(foot(O_2,Q,X))-Q;
/* Draw objects */
draw(circumcircle(A,P,C), green);
draw(circumcircle(B,P,D), blue);
draw(A--B);
draw(X--D--Q--C--cycle);
draw(Y--P--Z);
draw(X--A);
draw(C--P);
draw(D--B);
draw(Y--Z, dashed);
draw(circumcircle(X,D,C), red);
/* Place dots on and label each point */
dot(A); label("$A$", A, lsf * dir(150));
dot(B); label("$B$", B, lsf * dir(45));
dot(C); label("$C$", C, lsf * dir(-90));
dot(D); label("$D$", D, lsf * dir(160) * 1.414);
dot(P); label("$P$", P, lsf * dir(100));
dot(X); label("$X$", X, lsf * dir(225));
dot(Q); label("$Q$", Q, lsf * dir(-45));
dot(Y); label("$Y$", Y, lsf * dir(225));
dot(Z); label("$Z$", Z, lsf * dir(-45));[/asy]
$Q$ is the [url=http://www.cut-the-knot.org/Curriculum/Geometry/Miquel.shtml]Miquel point[/url] of $CXA, CDP, XDB, APB$, so $CXDQ$ is cyclic. By Reim's theorem on $\omega_1$ and $(CXDQ)$, $Q,X,Y$ are collinear; by Reim's theorem on $\omega_2$ and $(CXDQ)$, $Z,Q,X$ are collinear, and the result follows.

[hide="Note"]Equally well, $ABQX$ is cyclic from Miquel, so we may proceed with Reim's theorem on $(ABQX), \omega_1$ and $(ABQX), \omega_2$ to obtain the result.[/hide]

Let $ J= YP \cap \omega_2$.
Let $ L= YP \cap \omega_1$.
Now, \[ \measuredangle ZQB = \measuredangle ZPB = -  \measuredangle BPZ = \measuredangle ZPA = \measuredangle LPA =\measuredangle PAC =\measuredangle XAP \]
Now,  \[ \measuredangle YQB = \measuredangle YQP + \measuredangle PQB =  \measuredangle YCP +  \measuredangle PJB =  \measuredangle YCP +  \measuredangle DPJ =  \measuredangle YCP +  \measuredangle CPY = - \measuredangle PYC = - \measuredangle PAC = \measuredangle XAP \]
Finally observe that $Q$ is the $Miquel$ $Point$ of the complete quadrilateral formed by the vertices $X,D,P,A$.
\[ \implies XAQB  concyclic.  \] .
So,  \[ \measuredangle XQB = \measuredangle XAB = \measuredangle XAP \].
So , \[ \measuredangle ZQB = \measuredangle YQB = \measuredangle XQB \]
This leads us to the desired conclusion.

By spiral similarity $Q$ maps $DB$ to $CA$ so $QCXD$ is cyclic. If $QX$ intersects $\omega_1$ at $Y'$, $PY'$ and $DX$ are both antiparallel to $QC$ so $PY'\parallel DX$, $Y'=Y$, and $Y,Z$ lie on $QX$.

$Q$ is the Miquel point of complete quadrilateral $PBXC$, so $QDXC$ and $ADBX$ are cyclic.

Let $QX \cap w_1 \equiv Y'$. Angle chasing, we have $\angle Y'QC = \angle Y'AC = \angle Y'PD$. By the above and $QDXC$ cyclic, we have that $\angle Y'QC = \angle CDX = \angle Y'PD$ so $Y'P \parallel DX$, and similarly for $Z'$. The conclusion follows.

My proof is literally the exact same as everyone else's, but here goes.

Let $QX\cap w_1=Y'$. It suffices to show that $PY' \parallel BD$. We have $$\measuredangle{APY'}=\measuredangle{APC}-\measuredangle{Y'PC}=\measuredangle{BPC}-\measuredangle{Y'QC}=\measuredangle{BPD}-\measuredangle{XQC}$$
Now observe that $Q$ is the Miquel Point of complete quadrilateral $AXDP$, since $Q=w_1 \cap w_2$, so $DXCQ$ is cyclic. We now have
$$\measuredangle{BPD}-\measuredangle{XQC}=\measuredangle{BPD}-\measuredangle{XDC}=\measuredangle{BPD}-\measuredangle{BDP}=-\measuredangle{DPB}-\measuredangle{BDP}=\measuredangle{PBD}$$
Hence $PY' \parallel BD$. An identical argument shows that $PZ' \parallel AC$, where $Z'$ is defined analogously to $Y'$. It follows that $Q,X,Y$ and $Z$ are collinear, as desired. $\square$

Note that $\ Q$ is the Miquel Point of the quadrilateral $\ PDXA$, therefore $\ Q$ is the center of the unique spiral similarity sending $\ PD$ to$\ AX$, hence $\angle{AQX}=\angle{PQD}=\angle{PBD}=\angle{ABX}=\angle{APY}=\angle{AQY}$, implying that $\ Q,X$ and$\ Y$ are collinear.
In addition, $\angle{BQZ}=\angle{BPZ}=\angle{PAZ}=\angle{PAQ}+\angle{QAC}=\angle{QCP}+\angle{QPC}=\angle{QXD}+\angle{QBD}=180\ -\angle{BQX} $, thus $\ X,Z,Q$ are collinear.
Finally, the points $\ X,Y,Z$ and$\ Q$ are collinear.

Since $Q$ is the miquel point of complete quadrilateral $PDXA,$ quadrilateral $ABQX$ is cyclic.
But since $\measuredangle AQY=\measuredangle APY=\measuredangle ABX=\measuredangle AQX;$  we get that $Q,X$ and $Y$ are collinear. Similarly $Q,X$ and $Z$ are collinear, and the result follows. $\square$

[hide=Solution][quote=USA TST 2007 P1]Circles $ \omega_1$ and $ \omega_2$ meet at $ P$ and $ Q$. Segments $ AC$ and $ BD$ are chords of $ \omega_1$ and $ \omega_2$ respectively, such that segment $ AB$ and ray $ CD$ meet at $ P$. Ray $ BD$ and segment $ AC$ meet at $ X$. Point $ Y$ lies on $ \omega_1$ such that $ PY \parallel BD$. Point $ Z$ lies on $ \omega_2$ such that $ PZ \parallel AC$. Prove that points $ Q,X,Y,Z$ are collinear.[/quote]
[b][color=#000]Solution:[/color][/b] Notice $Q$ is the miquel point of $APDX$. Hence,
\begin{align*} \angle DXQ=\angle DCQ=\angle DYQ \implies Y \in XQ \end{align*}
\begin{align*} \angle XQD=\angle XCD=\angle DPZ = 180^{\circ}-\angle DQZ \implies Q \in XZ \qquad \blacksquare \end{align*}
[/hide]

Note that $Q$ is the miquel point of $APDX$, so $AXQB$ and $CXDQ$ are cyclic.

$$\angle DQZ = \angle DPZ = \angle CPZ = \angle ACP = \angle XCD = \angle DQX,$$ so $X,Z,Q$ are collinear.

$$\angle AQX = \angle ABX = \angle BPX = \angle APY = \angle AQY,$$ so $Y,X,Q$ are collinear.

Identify $Q$ as the Miquel point of $ACDB$. Let $Y'$ denote the second intersection of $\omega_1$ and $XQ$, note that by the spiral similarity circles,
\[\measuredangle Y'PC=\measuredangle Y'QC=\measuredangle XQC=\measuredangle XDC,\]
hence $Y'=Y$. Then, $Q,X,Y$ are collinear, so we are done by symmetry.

[quote=N.T.TUAN]Circles $ \omega_1$ and $ \omega_2$ meet at $ P$ and $ Q$. Segments $ AC$ and $ BD$ are chords of $ \omega_1$ and $ \omega_2$ respectively, such that segment $ AB$ and ray $ CD$ meet at $ P$. Ray $ BD$ and segment $ AC$ meet at $ X$. Point $ Y$ lies on $ \omega_1$ such that $ PY \parallel BD$. Point $ Z$ lies on $ \omega_2$ such that $ PZ \parallel AC$. Prove that points $ Q,X,Y,Z$ are collinear.[/quote]

Invert the problem about $P$. Let $T'$ denote the image of point $T$ under the given inversion. Then our problem is [quote=Inverted form of given problem]$A',B',C',D',P$ are points in a plane such that $P=C'D' \cap A'B'$. Let the lines $A'C'$ and $B'D'$ intersect at $Q'$. Let $X'=(A'C'P) \cap (B'D'P)$. Let the tangents from $P$ to $(A'C'P), (B'D'P)$ intersect $B'D',A'C'$ at $Z',Y'$ respectively. Prove that $Y'X'PZ'Q'$ is cyclic[/quote]

Observe that $$\angle X'C'Y' =\angle X'P'B' =\angle X'D'B'$$ Hence $X'C'Q'D'$ is cyclic.
Note that \begin{align*} \angle PZ'D' =\angle  Z'PC' -\angle Z'D'P &=\angle  PX'C' -\angle  Z'D'P \\ &= \angle PX'C' -\angle Q'X'C' \\&= \angle PX'Q' \end{align*} Hence $PX'Q'Z'$ is cyclic. Similarly we can conclude that $PX'Y'Q'$ is cyclic. Hence we are done.

Obviously $Q$ is the Miquel Point, which means that $BAXQ$ and $CXDQ$ are cyclic. I will first show that $Q, Z, X$ are collinear. Note that
\[\measuredangle QZP=\measuredangle QDP=\measuredangle QDC=\measuredangle QXC=\measuredangle QXA.\]
Since $PZ$ and $AC$ are parallel, $Q, Z, X$ must be collinear.

Now I will show that $Q, X, Y$ are collinear. We have
\[\measuredangle QXB=\measuredangle QAB=\measuredangle QAP=\measuredangle QYP.\]
Since $PY$ and $BD$ are parallel, $Q, X, Y$ must be collinear.

Combining the facts that $Q, Z, X$ are collinear and $Q, X, Y$ are collinear, we have that $Q,X,Y,Z$ are collinear.

[img]https://i.ibb.co/gtS2NjD/aops5.png[/img]

[b]Solution.[/b]

[b]Claim 1.[/b] $XCQD$ is cyclic.
[b]Proof.[/b]
We show that $\angle XCQ + \angle XDQ = \pi \iff \angle XCQ = \pi - \angle XDQ$.
$$\angle XCQ = \angle ACQ = \pi-\angle APQ = \angle BPQ = \angle BDQ = \pi -\angle XDQ$$

[b]Claim 2.[/b] $Y,X,Q$ collinear.
[b]Proof.[/b]
We show that $\angle XQP = \angle YQP$.
$$\angle XQP = \angle XQD + \angle DQP = \angle XCD + \angle DBP$$
$$=\angle ACP + \angle YPA  = \angle YQP$$

[b]Claim 3.[/b] $X,Q,Z$ collinear.
[b]Proof.[/b]
We show that $\angle XQP+\angle PQZ = \pi\iff \angle PQZ = \pi - \angle XQP$.
$$\angle PQZ = \pi - (\angle PBD + \angle DBZ)=\pi -( \angle APY + \angle DPZ)$$
$$=\pi -( \angle APY + \angle DCA)=\pi -( \angle APY + \angle PCA)=\pi -\angle XQP$$

Consider complete quadrilateral $APDX$ with $AP \cap DX = B$ and $AX \cap DP = C$. Since $Q = (CAP) \cap (BDP)$, we know it's the Miquel Point of $APDX$. Thus, $CXDQ$ and $BAXQ$ are cyclic.

[b][color=#f00]Claim:[/color][/b] $X, Q, Z$ are collinear.

[i]Proof.[/i] Notice $$\measuredangle XQD = \measuredangle XCD = \measuredangle ACP = \measuredangle ZPC = \measuredangle ZPD = \measuredangle ZQD$$ which obviously suffices. $\square$

[b][color=#f00]Claim:[/color][/b] $AY \parallel BZ$.

[i]Proof.[/i] Let $BX \cap AY = E$. Then, $$\measuredangle AEB = \measuredangle AYP = \measuredangle ACP = \measuredangle ZPC = \measuredangle ZPD = \measuredangle ZBD = \measuredangle ZBE$$ as desired. $\square$

Thus, $$\measuredangle PQY = \measuredangle PAY = \measuredangle BAY = \measuredangle ABZ = \measuredangle PBZ = \measuredangle PQZ$$ implying $Q, Y, Z$ are collinear. Combining the two collinearities yields the desired result. $\blacksquare$

Notice that $Q$ is the Miquel point of complete quadrilateral $BPCAXD.$ Let $Y'=\overline{PQ}\cap\overline{ACP}.$ Since $CAPQ$ and $BXAQ$ are cyclic, $$\measuredangle BPY'=\measuredangle APY'=\measuredangle AQY'=\measuredangle ABX,$$ so $\overline{PY'}\parallel\overline{BD}.$ Thus, $Y'=Y$ and $Y$ is on $\overline{PQ}.$ Similarly, $X$ is also on $\overline{PQ}.$ $\square$

[hide=solution]Let $\measuredangle{ABC}$ denote the directed angle of $\angle{ABC}.$

We note that $Q$ is the center of the spiral similarity taking $AC$ to $BD.$ This spiral similarity also takes $AB$ to $CD.$ Since $AC\cap BD=X$ and $Q$ is the center of the spiral similarity taking $AB$ to $CD,$ $Q$ is the second intersection of the circles $(ABX)$ and $(CDX).$ In other words, $A,B,Q,$ and $X$ are concyclic and $C,D,Q,$ and $X$ are concyclic. Now, $$\measuredangle{AQX}=\measuredangle{ABX}=\measuredangle{APY}=\measuredangle{AQY},$$ so $Q,X,$ and $Y$ are collinear. Similarly, $$\measuredangle{BQX}=\measuredangle{BAX}=\measuredangle{BPZ}=\measuredangle{BQZ},$$ so $Q,X,$ and $Z$ are collinear. We are done.[/hide]

We have $XCQD$ cyclic because $\angle XCQ=\angle ACQ=\angle QPB=\angle QDB.$

We have $\angle DXQ=\angle DCQ=\angle PCQ=\angle PYQ$ and $PY \parallel BD$ implies $Y,X,Q$ collinear.

Similarly, $\angle QXC=\angle QDC=\angle PZQ$ and $XC\parallel PZ$ implies $X,Q,Z.$ The result follows.

[asy]/* DRAGON 0.0.9.6
Homemade Script by v_Enhance. */

import olympiad;
import cse5;
size(11cm);
real lsf=0.8000;
real lisf=2011.0;
defaultpen(fontsize(10pt));

/* Initialize Objects */
pair A = (-2.0, 2.0);
pair B = (4.031165686870916, 3.133944005249443);
pair C = (1.0, -2.0);
pair D = (1.0, 0.0);
pair P = IntersectionPoint(A--B,Line(C,D,0,lisf));
pair X = IntersectionPoint(A--C,Line(B,D,0,lisf));
pair O_1 = circumcenter(A,P,C);
pair O_2 = circumcenter(P,D,B);
pair Q = 2*foot(P,relpoint(O_1--O_2,0.5-10/lisf),relpoint(O_1--O_2,0.5+10/lisf))-P;
pair Y_prime = (2)*(foot(O_1,X,Q))-Q;
pair Z_prime = (2)*(foot(O_2,Q,X))-Q;

/* Draw objects */
draw(circumcircle(A,P,C), rgb(0.7,0.8,0.9) + linewidth(1.0));
draw(circumcircle(B,P,D), rgb(0.7,0.8,0.9) + linewidth(1.0));
draw(A--B, rgb(0.4,0.4,0.4));
draw(C--P, rgb(0.4,0.4,0.4));
draw(A--C, rgb(0.5,0.5,0.5) + linewidth(1.0) + linetype("4 4"));
draw(B--X, rgb(0.5,0.5,0.5) + linetype("4 4"));
draw(P--Y_prime, rgb(0.5,0.5,0.5) + linetype("4 4"));
draw(P--Z_prime, rgb(0.5,0.5,0.5) + linewidth(1.0) + linetype("4 4"));
draw(Y_prime--Z_prime, rgb(0.4,0.8,1.0));
draw(circumcircle(C,Q,D), rgb(0.7,0.8,0.9) + linewidth(1.0));
draw(circumcircle(Q,A,B), rgb(0.7,0.8,0.9) + linewidth(1.0));

/* Place dots on each point */
dot(A);
dot(B);
dot(C);
dot(D);
dot(P);
dot(X);
dot(Q);
dot(Y_prime);
dot(Z_prime);

/* Label points */
label("$A$", A, lsf * dir(150));
label("$B$", B, lsf * dir(45));
label("$C$", C, lsf * dir(-90));
label("$D$", D, lsf * dir(60) * 1.414);
label("$P$", P, lsf * dir(100));
label("$X$", X, lsf * dir(225));
label("$Q$", Q, lsf * dir(-45));
label("$Y'$", Y_prime, lsf * dir(225));
label("$Z'$", Z_prime, lsf * dir(-45));
[/asy]
(diagram stolen from @vEnhance)

I tried removing the point $X$ first to show that $\overline{Y-Q-Z}$ were collinear and my goodness, how badly stuck was I back then... :stretcher: But fortunately, spiral sim gotchme! :)

Firstly note that $\measuredangle QCA=\measuredangle QPA=\measuredangle QPB=\measuredangle QDB$ and $\measuredangle CAQ=\measuredangle CPQ=\measuredangle DPQ=\measuredangle DBQ$, and so, $Q$ is the center of the spiral similarity taking $CA\mapsto DB$.

So we thus get that $QCXD$ and $QXAB$ are cyclic. Now we have $\measuredangle AQX=\measuredangle ABX=\measuredangle PBD=\measuredangle ABD=\measuredangle APY=\measuredangle AQY$ which gives that $\overline{Q-X-Y}$ are collinear and similarly $\overline{Q-X-Z}$ are also collinear and we are done.

first, by spiral similarity $CQD$ and $AQB$ are similar
from that, we also get that $AQC$ and $BQD$ are similar, and angles $QAX$ and $QBX$, so $ABQX$ is a cyclic quadrilateral.
then, if $BQZ=BAX$ then $XQZ$ are collinear, but $BQZ=BPZ=BAX$ because $PZ||AC$, so $XQZ$ are collinear
lastly, we need $PYQ=BXQ$ to prove $Y$ is collinear with $XQZ$, but because we have $PYQ=PAQ=BXQ$, $Y$ is collinear with $XQZ$
therefore, $Q,X,Y$, and $Z$ are collinear


[quote="ashrafmod"]....-1..........-1............  -1 [/quote]

Sorry, but I don't understand that

[quote="ashrafmod"]tan(1\2) +tan( 1\3) +tan ( 1\4)..........[/quote]

It is a well known fact that $\sum_{k=2}^{\infty}\frac{1}{k}= \infty$. So $\forall x \in (0;\frac{\pi}{2}): \tan x > x$ implies $\sum_{k=2}^{\infty}\tan \frac{1}{k}= \infty$.

$\tg x<2x$ for $x<1$, therefore $arctg x>\frac{x}{2}$ for $x<1$

Same thing;  $arctan x ~ x$ for $x$ small, so the sum will still diverge.


25 people form some committees, with each committee having 5 members and each pair of committees having at most one common member. Determine the maximum number of committees.

Geez AWholeNewWorld, I either really suck at math or those problems are really hard. I mean, I've only gotten 10 so far since three days after ARML :-(


modular arithmetic
number theory unsolved
number theory

Find all integers $ n$ such that $ (x,n)\equal{}1$ implies that $ x^{2}\equiv 1\pmod n$.
(I think the answer is $ {1,2,3,4,6,8,12,24}$ , but I couldn`t prove that there is no another solution .)

[quote="shoki"]it is PEN D16 :blush:[/quote]
sorry  :blush: . Thanks


topology
function
vector
real analysis
Functional Analysis

Hi!

I am wondering if there are any prominant uses of the Smirnov metrization theorem in say, functional analysis? Is this theorem used frequently within analysis? That is,  we have a topological space $ X$ defined in some way, such as by seminorms (or any other way where the metric isn't given), and we would like to demonstrate that there [i]is [/i] a metric for $ X$, even if it's difficult to find. If there are examples of this scenerio I would appreciate some examples!

Thanks in advance!

Los

(Theorem statement: A space $ X$ is metrizable iff it is a paracompact Hausdorff space that is locally metrizable).

Here's an example: Let $ \mathcal{S}$ be the Schwartz space on $ \mathbb{R}.$ We have that $ f\in \mathcal{S}$ iff for all nonnegative integers $ j$ and $ k,$ we have $ x^j\left(\frac {d}{dx}\right)^kf(x)$ bounded. (Informally, $ \mathcal{S}$ consists of all $ C^{\infty}$ functions that decay at infinity faster than any power of $ x,$ along with every derivative.)

This description includes a description of the topology, which is given by the family of seminorms $ \|f\|_{j,k} \equal{} \sup_{x\in\mathbb{R}}\left|x^j\left(\frac {d}{dx}\right)^kf(x)\right|.$ That is, $ f_n\to f$ iff $ \|f_n \minus{} f\|_{j,k}\to 0$ for all $ j$ and $ k.$

As you've noted, this is a metrizable topology. What good is that to us? It implies that if we want to describe anything that depends on the topology, notably including whether any function defined on $ \mathcal{S}$ (for instance, a linear functional) is continuous, then we may safely rely on descriptions and definitions that use sequences.

In practice, we'll have no use for the metric itself. That's too clumsy. Instead, all of our specific arguments will directly use the seminorms.

Side note: the space $ \mathcal{D}$ of compactly supported $ C^{\infty}$ functions, with its conventional topology, is [i]not[/i] metrizable. Which means that we won't be on entirely safe ground talking about sequences.

Interesting! I wonder if there are any other situations in functional analysis and/or PDE where this is used?

Thanks!

Los

[quote="Los"]we have a topological space $ X$ defined in some way, such as by seminorms (or any other way where the metric isn't given), and we would like to demonstrate that there [i]is [/i] a metric for $ X$, even if it's difficult to find. If there are examples of this scenerio I would appreciate some examples!
[/quote]

If you look at topological Hausdorff vector spaces (and that's usually the only thing you look at in functional analysis and PDE) the question of metrizability is really very simple:

A topological Hausdorff vector space $ X$ is metrizable if and only if it is first-countable.

In the case $ X$ is locally convex, you can say even more: $ X$ is metrizable if and only if it's topology can be defined by a [i]countable[/i] family of seminorms $ \{p_n | n\in\mathbb{N}\}$, in which case the metric can explicitly be defined by $ d(x,y) \equal{} \sum_{n\in\mathbb{N}} 2^{ \minus{} n} \frac {p_n(x \minus{} y)}{1 \plus{} p_n(x \minus{} y)}$, for example (this also covers the example Kent Merryfield was referring to).

So in functional analysis there is really no need for Smirnov's theorem.

[i]Edit:[/i] A nice proof can be found in Rudin, Functional Analysis, Chap. 1.

When [i]is[/i] smirnov's theorem used?

Los

maybe you need smirnov's metrization theorem when working with manifolds? (a manifold $ \mathbb{M}$ is metrizable iff it is paracompact)


[quote="quykhtn-qa1"]Let a,b,c,d be real numbers such that:a+b+c+d+abcd=1.
Find the smallest the value of the expression:
Q=$ a^4 \plus{} b^4 \plus{} c^4 \plus{} d^4$[/quote]
No one interested in this problem? :(

[quote="Kyoshiro"]Let $ \alpha$ be a positive root of the equation : $ x^4 \plus{} 4x \minus{} 1 \equal{} 0$
By AM-GM inequality, we have:
$ a^4 \plus{} \alpha^4 \plus{} \alpha^4 \plus{} \alpha^4\ge 4|a|\alpha^3 \ge 4a\alpha^3$
$ b^4 \plus{} \alpha^4 \plus{} \alpha^4 \plus{} \alpha^4\ge 4|b|\alpha^3 \ge 4b\alpha^3$
$ c^4 \plus{} \alpha^4 \plus{} \alpha^4 \plus{} \alpha^4\ge 4|c|\alpha^3\ge 4c\alpha^3$
$ d^4 \plus{} \alpha^4 \plus{} \alpha^4 \plus{} \alpha^4\ge 4|d|\alpha^3\ge 4d\alpha^3$
$ \alpha^3(a^4 \plus{} b^4 \plus{} c^4 \plus{} d^4)\ge 4|abcd|\alpha^3\ge 4abcd\alpha^3$
Summing up these inequalities, we obtain:
$ a^4 \plus{} b^4 \plus{} c^4 \plus{} d^4\ge \boxed{\frac {4\alpha^3 \minus{} 12\alpha^4}{\alpha^3 \plus{} 1}}$
The equality occurs when $ a \equal{} b \equal{} c \equal{} d  \equal{} \alpha$[/quote]
you can't solve equation:$ x^4\plus{}4x\minus{}1\equal{}0$ :P  :P  :P

[quote="quykhtn-qa1"][quote="Kyoshiro"]Let $ \alpha$ be a positive root of the equation : $ x^4 \plus{} 4x \minus{} 1 \equal{} 0$
By AM-GM inequality, we have:
$ a^4 \plus{} \alpha^4 \plus{} \alpha^4 \plus{} \alpha^4\ge 4|a|\alpha^3 \ge 4a\alpha^3$
$ b^4 \plus{} \alpha^4 \plus{} \alpha^4 \plus{} \alpha^4\ge 4|b|\alpha^3 \ge 4b\alpha^3$
$ c^4 \plus{} \alpha^4 \plus{} \alpha^4 \plus{} \alpha^4\ge 4|c|\alpha^3\ge 4c\alpha^3$
$ d^4 \plus{} \alpha^4 \plus{} \alpha^4 \plus{} \alpha^4\ge 4|d|\alpha^3\ge 4d\alpha^3$
$ \alpha^3(a^4 \plus{} b^4 \plus{} c^4 \plus{} d^4)\ge 4|abcd|\alpha^3\ge 4abcd\alpha^3$
Summing up these inequalities, we obtain:
$ a^4 \plus{} b^4 \plus{} c^4 \plus{} d^4\ge \boxed{\frac {4\alpha^3 \minus{} 12\alpha^4}{\alpha^3 \plus{} 1}}$
The equality occurs when $ a \equal{} b \equal{} c \equal{} d \equal{} \alpha$[/quote]
you can't solve equation:$ x^4 \plus{} 4x \minus{} 1 \equal{} 0$ :P  :P  :P[/quote]
Of course I can! It's very easy :).
$ x^4 \plus{} 4x \minus{} 1 \equal{} 0 \leftrightarrow (x^2\plus{}1)^2\equal{}2(x\minus{}1)^2$

[quote="Kyoshiro"][quote="quykhtn-qa1"][quote="Kyoshiro"]Let $ \alpha$ be a positive root of the equation : $ x^4 \plus{} 4x \minus{} 1 \equal{} 0$
By AM-GM inequality, we have:
$ a^4 \plus{} \alpha^4 \plus{} \alpha^4 \plus{} \alpha^4\ge 4|a|\alpha^3 \ge 4a\alpha^3$
$ b^4 \plus{} \alpha^4 \plus{} \alpha^4 \plus{} \alpha^4\ge 4|b|\alpha^3 \ge 4b\alpha^3$
$ c^4 \plus{} \alpha^4 \plus{} \alpha^4 \plus{} \alpha^4\ge 4|c|\alpha^3\ge 4c\alpha^3$
$ d^4 \plus{} \alpha^4 \plus{} \alpha^4 \plus{} \alpha^4\ge 4|d|\alpha^3\ge 4d\alpha^3$
$ \alpha^3(a^4 \plus{} b^4 \plus{} c^4 \plus{} d^4)\ge 4|abcd|\alpha^3\ge 4abcd\alpha^3$
Summing up these inequalities, we obtain:
$ a^4 \plus{} b^4 \plus{} c^4 \plus{} d^4\ge \boxed{\frac {4\alpha^3 \minus{} 12\alpha^4}{\alpha^3 \plus{} 1}}$
The equality occurs when $ a \equal{} b \equal{} c \equal{} d \equal{} \alpha$[/quote]
you can't solve equation:$ x^4 \plus{} 4x \minus{} 1 \equal{} 0$ :P  :P  :P[/quote]
Of course I can! It's very easy :).
$ x^4 \plus{} 4x \minus{} 1 \equal{} 0 \leftrightarrow (x^2 \plus{} 1)^2 \equal{} 2(x \minus{} 1)^2$[/quote]
OK  :oops:  :roll:  :oops:

[quote="Kyoshiro"]Let $ \alpha$ be a positive root of the equation : $ x^4 \plus{} 4x \minus{} 1 \equal{} 0$
By AM-GM inequality, we have:
$ a^4 \plus{} \alpha^4 \plus{} \alpha^4 \plus{} \alpha^4\ge 4|a|\alpha^3 \ge 4a\alpha^3$
$ b^4 \plus{} \alpha^4 \plus{} \alpha^4 \plus{} \alpha^4\ge 4|b|\alpha^3 \ge 4b\alpha^3$
$ c^4 \plus{} \alpha^4 \plus{} \alpha^4 \plus{} \alpha^4\ge 4|c|\alpha^3\ge 4c\alpha^3$
$ d^4 \plus{} \alpha^4 \plus{} \alpha^4 \plus{} \alpha^4\ge 4|d|\alpha^3\ge 4d\alpha^3$
$ \alpha^3(a^4 \plus{} b^4 \plus{} c^4 \plus{} d^4)\ge 4|abcd|\alpha^3\ge 4abcd\alpha^3$
Summing up these inequalities, we obtain:
$ a^4 \plus{} b^4 \plus{} c^4 \plus{} d^4\ge \boxed{\frac {4\alpha^3 \minus{} 12\alpha^4}{\alpha^3 \plus{} 1}}$
The equality occurs when $ a \equal{} b \equal{} c \equal{} d \equal{} \alpha$[/quote]
NICE solution, Kyoshiro! :lol:

I am eager to see yours quykthn-qa1! :oops:  :rotfl:

Let m be a positive root of the f(x)= $ x^4\plus{}4x\minus{}1\equal{}0$ for x>0
$ f'(x)\equal{}4x^3\plus{}4>0$
Now,if $ abcd>m^4$
And by AM-GM we have$ a\plus{}b\plus{}c\plus{}d \ge 4m$
And now $ abcd\plus{}a\plus{}b\plus{}c\plus{}d>m^4\plus{}4m\equal{}1$
So $ abcd \le m^4$
And since a+b+c+d+abcd=1.We have $ a\plus{}b\plus{}c\plus{}d \ge 1\minus{}m^4$
And now if k>1.We have
$ a^k\plus{}b^k\plus{}c^k\plus{}d^k \ge \frac{(a\plus{}b\plus{}c\plus{}d)^k}{4^{k\minus{}1}} \ge \frac{(1\minus{}m^4)^k}{4^{k\minus{}1}}$


geometry
trapezoid
analytic geometry
geometry unsolved

M and N are the midpoints of the sides AB and CD of a trapezium ABCD respectively. AN and DM intersects each other at X. Similarly, BN and CM intersects each other at Y. Prove that, XY || AB || CD.

It is easy with coordinates, let N=(0,0), C=(1,0), D=(-1,0), A=(r,q), B=(p,q), $ M = (\frac {p + r}{2})$, then ${ AN = (y = \frac {q}{r} \cdot x})$, $ MD = (y = \frac {q}{\frac {p + r}{2} + 1} \cdot (x + 1))$, hence $ \frac {r}{q} \cdot y = \frac {\frac {p + r}{2} + 1}{q} \cdot y - 1$.
Similarly, we have $ \frac {p}{q} \cdot y = \frac {\frac {p + r}{2} - 1}{q} \cdot y + 1$.
They give the same solution for y.
I will try to find an easy way without coordinates.

Just use the fact that $ AXM$ and $ DXN$ are similar and $ BMY$ and $ NYC$ are similar..the conclusion then follows easily using that $ AM\equal{}MB$ and $ DN\equal{}NC$

Daniel

Yes, I just realized that, $ \frac {YN}{BY} \equal{} \frac {CN}{BM} \equal{} \frac {ND}{AM} \equal{} \frac {DX}{XM}$ because of similarity.


ratio
trigonometry
geometry proposed
geometry

Project the perspectrix of $\triangle ABC,\triangle DEF$ to infinity and label projected points with primes. Thus, $D,E,F$ go to the midpoints $D',E',F'$ of $B'C',$ $C'A',$ $A'B'$ and $X,Y,Z$ go to $X',Y'Z'$ on $E'F',F'D',D'E'.$ Now, get rid of the primes. Since the lines $AX,$ $BY$ and $CZ$ obviously divide the pairs of sides $(FE,BC),$ $(DF,CA)$ and $(ED,AB)$ into the same ratios, then it follows by the converse of Ceva's theorem that $AX,BY,CZ$ concur $\Longleftrightarrow$ $DX,EY,FZ$ concur.

Dear Virgil, Luis and Mathlinkers,
this is a nice formulation of the cevian nests theorem.
A synthetic proof of this result can be seen on my site :
http://perso.orange.fr/jl.ayme     vol. 3
Sincerely
Jean-Louis

Dear Virgil and Mathlinkers,
some interesting applications can also be seen on my site :
http://perso.orange.fr/jl.ayme
vol. 3 The cross-cevian point
Produit et quotient cévien de deux points
Sincerely
Jean-Louis

One can use the following [b]Lemma[/b]:

[i]Let D be a point on BC; a straight line l intersects AB, AC and AD at M, N and P respectively. The following relation occurs:
(AB/AC).(AN/AM) = (BD/CD).(NP/MP)[/i]

The lemma can easily be proven: draw parallels to BC through M and N; they will intersect AD at M' and N', etc.
As it can be seen, it's not restrictive [i.e. D on (BC), etc.].

It appeared in Romanian [b]Gazeta Matematica[/b] well before 1980. Is it called now "Transversal Theorem"?

Best regards,
sunken rock

[size=117][color=darkblue][b]Thank you[/b] for your commentaries of this nice problem. I agree the elementary proof of [b]Sunkenrock[/b]. Here is his proof.[/color][/size]

[color=darkred][b][u]Lemma[/u].[/b] Let $ ABC$ be a triangle. Then $ D\in (BC)$ , $ E\in (CA)$ , $ F\in (AB)$ and $ X\in AD\cap EF$ $ \implies$  $ \frac {XF}{XE}\equal{}\frac {DB}{DC}\cdot \frac {AF}{AE}\cdot \frac {AC}{AB}$ .[/color]

[hide="Proof."]
[color=darkblue]Apply an well-known relation in the triangles $ ABC$ and $ AEF$ for the common cevian $ \overline {AXD}$ :

$ \left\|\begin{array}{c}
\frac {DB}{DC}\equal{}\frac {AB}{AC}\cdot\frac {\sin\widehat {DAB}}{\sin\widehat{DAC}}\\\\
\frac {XF}{XE}\equal{}\frac {AF}{AE}\cdot\frac {\sin\widehat {XAF}}{\sin\widehat {XAE}}\end{array}\right\|\ : \ \uparrow\ \implies\ \boxed {\ \frac {XF}{XE}\equal{}\frac {DB}{DC}\cdot\frac {AF}{AE}\cdot\frac {AC}{AB}\ }$ because $ \widehat {DAB}\equiv\widehat {XAF}$ and $ \widehat{DAC}\equiv\widehat {XAE}\ .$[/color][/hide]

[quote="Virgil Nicula"] [color=darkred]Given are $ \triangle ABC$ and $ D\in (BC)$ , $ E\in (CA)$ , $ F\in (AB)$ so that $ AD\cap BE\cap CF\ne\emptyset$ . Consider

$ X\in (EF)$ , $ Y\in (FD)$ , $ Z\in (DE)$ . Prove that $ AX\cap BY\cap CZ\ne \emptyset\ \Longleftrightarrow\ DX\cap EY\cap FZ\ne\emptyset\ .$[/color] [/quote]

[color=darkblue][b][u]Proof[/u].[/b] Apply the [u][b]Ceva[/b]'s theorem[/u] to the point $ S\in AD\cap BE\cap CF$ and $ \triangle ABC\ \implies\ \frac {DB}{DC}\cdot\frac {EC}{EA}\cdot\frac {FA}{FB}\equal{}1\ .$

Denote $ \left\|\begin{array}{c}
M\in AX\cap BC\\\\
N\in BY\cap CA\\\\
P\in CZ\cap AB\end{array}\right\|\ .$ Using the upper lemma obtain $ \left\|\begin{array}{c}
\frac {XF}{XE}\equal{}\frac {MB}{MC}\cdot\frac {AF}{AE}\cdot\frac {AC}{AB}\\\\
\frac {YD}{YF}\equal{}\frac {NC}{NA}\cdot\frac {BD}{BF}\cdot\frac {BA}{BC}\\\\
\frac {ZE}{ZD}\equal{}\frac {PA}{PB}\cdot\frac {CE}{CD}\cdot\frac {CB}{CA}\end{array}\right\|\ \bigodot\implies$

$ \frac {XF}{XE}\cdot\frac {YD}{YF}\cdot\frac {ZE}{ZD}\equal{}\frac {MB}{MC}\cdot\frac {NC}{NA}\cdot\frac {PA}{PB}\ .$ In conclusion, $ AX\cap BY\cap CZ\ne \emptyset\ \Longleftrightarrow$

$ \frac {MB}{MC}\cdot\frac {NC}{NA}\cdot\frac {PA}{PB}\equal{}1\Longleftrightarrow \frac {XF}{XE}\cdot\frac {YD}{YF}\cdot\frac {ZE}{ZD}\equal{}1$ $ \Longleftrightarrow DX\cap EY\cap FZ\ne\emptyset\ .$[/color]

[quote="Virgil Nicula"]Given are $ \triangle ABC$ and $ D\in (BC)$ , $ E\in (CA)$ , $ F\in (AB)$ so that $ AD\cap BE\cap CF\ne\emptyset$ . Consider

$ X\in (EF)$ , $ Y\in (FD)$ , $ Z\in (DE)$ . Prove that $ AX\cap BY\cap CZ\ne \emptyset\ \Longleftrightarrow\ DX\cap EY\cap FZ\ne\emptyset\ .$[/quote]
See here http://www.artofproblemsolving.com/Forum/blog.php?u=50172&b=33721


algebra
polynomial
linear algebra
matrix
geometry
3D geometry
sphere

$ \varphi(x)=x^{T}Sx$, where: $ x=\left(\begin{array}{c}x_{1}&x_{2}&...&x_{n}\end{array}\right)$

and $ S \in M_{n}(\mathbb{R})$, $ S^{T}=S$

if we restrict  $ x^{T}x=1$

How to find the extremum of $ \varphi(x)$  :D

This extremum equals to the maximal eigenvalue of $ S$ (or what is the same -- to the maximal root of the characteristic polynomial of $ S$). One cannot express this extremum explicitely through the entries of the matrix.

Start by noting that if $ Q \in \mathbb{R} ^{n \times n}$ is an orthogonal matrix and $ x \in \mathbb{R} ^n$ is such that $ x^Tx \equal{} 1$, then $ (Qx)^T(Qx) \equal{} x^TQ^TQx \equal{} x^T I_n x \equal{} x^Tx \equal{} 1$. Observe also that, since $ Q$ is orthogonal, then it is also non-singular, and as $ x$ varies over the unit sphere the same happens with $ Qx$. Now, as $ S$ is a symmetrical matrix, there is an orthogonal matrix $ Q$ such that $ S \equal{} Q^TDQ$, where D is the diagonal matrix of the eigenvalues of S. Therefore, for $ x^Tx \equal{} 1$,

$ x^TSx \equal{} x^T Q^TDQx \equal{} (Qx)^TD(Qx) \equal{} y^TDy \equal{} \sum_{i \equal{} 1}^n \lambda_i y_i^2 \leq \sum_{i \equal{} 1}^n \lambda_1 y_i^2$

$ \equal{} \lambda_1 \sum_{i \equal{} 1}^n y_i^2 \equal{} \lambda_1 \cdot y^Ty \equal{} \lambda_1 \cdot 1 \equal{} \lambda_1$,

where $ \lambda_1$ is the maximal eigenvalue of $ S$. So,

$ max \,\,(x^TSx) \equal{} \lambda_1$. $ \Diamond$


induction
number theory
relatively prime

Given a natural number n>=2, consider all of the fractions of the form 1/ab , where a and b are relatively prime natural numbers such that a < b<= n and a + b > n. Show that the sum of these fractions is 1/2.

[hide]
We proceed by induction on $ n$.

Base case: n=2
$ \frac{1}{1*2}=\frac{1}{2}$ is clearly true.

Inductive Step:
Call the sum in question $ S(n)$. Suppose $ S(1)=S(2)=...=S(n-1)=\frac{1}{2}$.  We have that

\[ S(n)-S(n-1)=\frac{1}{n}\left(\sum_{(k, n)=1, 1 \le k < n}\frac{1}{k}\right)-\sum_{a+b=n, (a, b)=1, a<b}\frac{1}{ab}\]
But $ \sum_{a+b=n, (a, b)=1, a<b}\frac{1}{ab}=\sum_{(a, n)=1, 1 \le a < \frac{n}{2}}\frac{1}{a(n-a)}$, because $ (a, n-a)=1 \iff (a, n)=1$.  We finally finish with the fact that
\[ \frac{1}{n}\left(\frac{1}{k}+\frac{1}{n-k}\right)=\frac{1}{k(n-k)}\] to show that $ S(n)=S(n-1)$.[/hide]


I'm not a number sense person but I would think round it and then add a like 1 at the end.

wow, i acutally got within .5!!  took a little bit longer than 10 seconds because my mental arithmetic capabilities are quiet low.  i calculated 9*4=36 then 36*4.5=162 then i added 8 for something nice to get 170

[quote="Rep123max"]within 5%
9.34*3.81*4.77?[/quote]

Since I know that 5% is a criteria of the problem, think 1/20th of each number:  .46+, .19+, .23+.

The last two are very convenient!  If I round 3.81 up by the 5% limit, I get 4.  If I round 4.77 up by the 5% limit, I get 5.

To compensate, I must round 9.34 down by at least 5% but not more than 15%.  Rounding to 9 would be too big.  Rounding to 8 is near the low end of the range.

8*4*5=160.  Near low end of range
9*4*5=180.  A little too high.

I'd feel safe averaging them to 170.

Well, this took a little more than 10 seconds, but it works pretty well.

First, I found fractions that were about equal to the given numbers; 28/3 for 9.34, 19/5 for 3.81, and 43/9 for 4.77. 28/3 * 19/5 * 43/9 = 28/9 * 43/3 * 19/5  :approx: 3 * 14 * 4 = 168, which is close to the actual answer. It took me 17 seconds, though.


combinatorics proposed
combinatorics
knights and knaves

Five men, $ A$, $ B$, $ C$, $ D$, $ E$ are wearing caps of black or white colour without each knowing the colour of his cap. It is known that a man wearing black cap always speaks the truth while the ones wearing white always tell lies. If they make the following statements, find the colour worn by each of them:
$ A$ : I see three black caps and one white cap.
$ B$ : I see four white caps
$ C$ : I see one black cap and three white caps
$ D$ : I see your four black caps.

Lovely  :lol:
Observation 1: One of (A,C) has a white hat (i.e. is lying), also one of (B,D) has a white hat.
Observation 2: because of the above we see that the claim of D can never be true therefore D has a white hat.
Observation 3: If A were telling the truth then both C and D would have white hats making A's claim wrong and therefore A has a white hat.
Finally we see that B can not be telling the truth because otherwise C would be lying and saying the truth at the same time!
we are left with determining the color of the hat of C and E. Since B is lying then at least one of C,E has a black hat. If C has a black hat then E also has a black hat. If E has a black hat then C is telling the truth thus has a black hat.
Either way we have (A,B,C,D,E)=(W,W,B,W,B)

If D tells truth, there are 5 black, contradiction with C

[b]D lies[/b]

If B tells truth, then also C tells truth, contradiction with C liar

[b]B lies[/b]

A obviously lies, because there are at least 2 white (B,D)

[b]A lies[/b]

If C lies, then all are liars, but B would tell truth then. Contradiction

[b]C tells truth, E tells truth[/b]

We shall start from the colour of the cap E is wearing.

Let us prove by contradiction that E wears a black cap.

Suppose E waers white cap, D is obviously lying and so D also wears white cap. Now since there are atleast two white caps, we see A must be lying and so A also wears white cap.
Now, if C is indeed telling the truth, then C wears a black cap while A,D and E wear white. This implies that B is obviously lying and so B also wears white cap. But now there are 4 people with white caps, which contradicts C's statement. Thus, C should be lying.
Now if C lies, then C wears white. So, with A, C, D and E with white caps, then what B says is true making him wear a black cap. But B wears balc, C tells the turth-contradiction.

So, we see that E must have black cap. This clearly implies B is lying and so B wears white.  So, there can maximum be 3 black caps. This implies D is also lying. So D wears white cap. Then, we clearly see that since B and D wear white, there are 2 white caps. So A must be lying and so A ears white too. FInally, it is easily verified that C tellls the truth and C wears black.

So the colours of the caps are : (A,B,C,D,E)= (W,W,B,W,B).
(W-WHITE, B-BLACK).


I'll upload this to the MAML website later; for now, here it is.

From the printed version on Tuesday, two changes:  1. two answer choices were changed for Q21, so the question is solvable; and 2. I tweaked the list of calculators to make it more consistent.

Full solutions will be posted next Friday.

Enjoy.

Thanks so much!

Is there any way we could get the 2005-06 exam as well?


If we're a bit new to LaTeX, will we be docked points if our solution is a little hard to read?

If you mean it's hard to understand mathematically, yes they may take off points.  But if you mean there's some error in your Latex code that comes out wrong, then you might not lose points if the grader can still understand it.

I'm also new to it and have just learnt some basic commands for writing solutions of USAMTS problems. My suggestion is to feel free to explain in detail and don't worry about if it's too long. I hope this might help. :)

[quote="le00327146"]I'm not sure how specific I can get, but basically there's a lot of steps in my solution, and I think it may look a little questionable to some people.[/quote]

I don't know if I'm misinterpreting this, but that sounds more like an issue with the proof itself than with LaTeX.

However, I think simply having too many steps should be fine -- it's just important not to skip steps.


geometry
geometric transformation
combinatorics solved
combinatorics

We are given some S subset of the set $ \{1,2, \ldots,M\}$ which contain $ a_1, a_2, \ldots, a_s$ elements, respectively. It is known that none of these subsets contains another one. Prove that: $ \sum^s_{i\equal{}1} \frac{1}{\binom{M}{a_i}} \leq 1.$

Note: LMO1987 grade 10 elimination round

reference Leningrad olympiad books:

Dmitri Fomin, who now works in software in the USA played a key role in the Leningrad olympiad (one of my favourites) for many years. He apparently made huge efforts whilst he acted as secretary to collect all the problems, but the first 8 years (1934-41) defeated him because (apparently) the only (paper) records were destroyed. He says that in any case the early years had problems of low quality by modern standards (much closer to ordinary textbook exercises), but, of course, he still wants them. I think there is still a chance even for 1934-41. Some people may still be alive with personal papers. (Dmitri thinks not.)

For further information I can send you a nice description via e-mail. Anybody who has the desire to get further information may contact me.

Leningrad Mathematical Olympiads 1987-1991 (Contests in Mathematics Series ; Vol. 1) by Dmitry Fomin, Dmitry Fomin, Alexey Kirichenko

http://www.amazon.com/exec/obidos/ASIN/096264014X/absolutsearch05/102-5793095-6620961

partitial automatic translation by systran of http://www.pdmi.ras.ru/~olymp/general.html#biblio

Books about the St. Petersburg Olympiads D.V.Fomin, St. Petersburg mathematical competitions in schools, St. Petersburg: Polytechnics, 1994.
The book contains the tasks of the urban and elimination stages of Leningrad and St. Petersburg Olympiads from 1961 through 1993. To the majority of tasks the answers are given, the indications or the solutions. There is a large introductory article about the Olympiad and an historical description.

S.L.Berlov, S.V.Ivanov, K.P.Kokhas', Petersburg mathematical competitions in schools, St. Petersburg: Publishing house "doe", 1998.
The tasks (with the complete solutions) of all three stages of the olympiads from 1994 through 1998 are given, and also Olympiads FML-И9 during the same period. In the addition it contains reference information even two research tasks.

S.L.Berlov, S.V.Ivanov, K.P.Kokhas', Petersburg mathematical competitions in schools (second edition), St. Petersburg: Publishing house "doe", 2003. In the second edition the tasks of the Olympiad of 1999 are added, several new research tasks, and another additional information. You can study the index of the second edition.

Yearly the organization committee of  the olympiad and the state university publishes the collectiom of the tasks of the past Olympiad. Compilers (beginning from the middle of the 80th annually): O.A.Ivanov, A.S.Merkur'ev, N.Yu.Netsvetayev, D.V.Fomin, V.V.Makeyev, K.P.Kokhas', S.L.Berlov, S.V.Ivanov, R.A.Semizarov, D.V.Karpov, A.I.Khrabrov.

Materials about the Petersburg Olympiads periodically are published in the journals "quantum" and "mathematics in the school".

reference Sperner theory: http://mathworld.wolfram.com/SpernersTheorem.html

This result is due to Yamamoto and was proved particularly in order to provide another proof of the Sperner theorem, which says that the maximum number of subsets of the set {1,2,...,M}, none of which contains another, is equal to:

Cn(M,li(M/2)) = M! / (li(M/2)!(M-li(M/2))!) where li(x) and x \in R denotes the greatest integer \leq x.

Note that quite a few IMO shortlist/longlist problems were rejected at the IMO since they were known from Russian competitions as the All-Russianolympiad and Leningrad, Moscow, Kiev and other towns. Leningrad problems are directly taken from current research materials and they are mostly original meaning new problems in contrast to many other olympiads. The Leningrad olympiad includes four stages: school level,
regional level, All-city level (main round) and final level (elimination round). The last two final rounds are special as they are not written but oral rounds. The elimination rounds is intended to determine which contestants would represent the city team at the All-Russian round. The elimination round of the LMO is rather difficult. Often, at this level, some problems are not solved at all. There are several other interesting facts concerning LMO but I don't want to post them all at the forum. You know you may get the sent the information via e-mail.
The problems of the two final rounds (main round and elimination round) during the 80s might be found in the Canadian problem-solving journal Crux Mathematoricum at: http://journals.cms.math.ca/CRUX/ . Later since 1996 selected LMO problems are provided in the annual published books Mathematical Olympiads: Problems and Solutions from Around the World by Titu Andreescu, e.g the volume 2000/01 : http://www.amazon.com/exec/obidos/tg/detail/-/088385810X/qid=1065631676/sr=1-6/ref=sr_1_6/102-5793095-6620961?v=glance&s=books

My supervisor solved this problem.

His proof is following.

Let M=n.

Let sequence of sets A1 \in A2 \in ... \in An, where |Ak|=k, be chain.
It is clear there are n! diffrent chains.

MAIN IDEA
Two sets A and B are not contain each other <==> any chain which contains A is diffrent to any chain which contains B.

Let M1, M2, ..., Ms be sets from condition with a1,a2,...,as elements respectively. There exists ak!(n-ak)! chains which contains Mk and all these chains for all k=1...s are diffrent ==> \sum ak!(n-ak)! \leq n!

That's all.

Orl wrote here:
"...but the first 8 years (1934-41) defeated him because (apparently) the only (paper) records were destroyed. He says that in any case the early years had problems of low quality by modern standards (much closer to ordinary textbook exercises)..."

   Wrong. I myself have (somewhere) a sheet with 1934 problems (not
that I'm a grey-bearded elder - I received this sheet on LMO's 50th
anniversary celebration). The problems were quite nice. In fact, there is
a booklet with these problems published in 1934. It is extremely rare,
but can be found in major public libraries of Russia.
   By the way, Fomin apparently does not know about the olympiad of 1943 held in the besieged city.

"Some people may still be alive with personal papers. (Dmitri thinks not.)"

  As to the last statement, he himself should know well that V.A.Zalgaller
who was involved in olympiad activities in the late 30s, is alive, well
and doing mathematics in Israel.

[quote="guas"]Orl wrote here:
"...but the first 8 years (1934-41) defeated him because (apparently) the only (paper) records were destroyed. He says that in any case the early years had problems of low quality by modern standards (much closer to ordinary textbook exercises)..."

   Wrong. I myself have (somewhere) a sheet with 1934 problems (not
that I'm a grey-bearded elder - I received this sheet on LMO's 50th
anniversary celebration). The problems were quite nice. In fact, there is
a booklet with these problems published in 1934. It is extremely rare,
but can be found in major public libraries of Russia.
   [/quote]

Hi Alexander,

could you please post the problems of the SPbMO of 1934 and any other problems you have before 1961 on the forum, please ? Thanks.  :)

I just want to comment on the discussion on the availability of LMO 1934-1941 etc.

Indeed some of the materials were accessible and I have the copies. The problem is that since I only had some of the years and some of the grades I could not publish them as such in my book - that would naturally require having full versions for at least several contiguous years. That's why I only start the book with 1961 - for each year before that there were considerable omissions in my materials (also the overall size of the book was a consideration as well).

Secondly, there is no doubt in my mind that Golovanov knows perfectly well that I knew Prof.Zalgaller and of course talked to him at length about those years. More than that, he is specifically mentioned in the foreword to my book. The purpose of his comment therefore is pretty unclear to me. Unfortunately Viktor Abramovich did not have anything saved from the years before the WW II. Nor did any of the participants of the pre-war years I was able to contact.

As for the olympiad held in 1943 when the city was still under German blockade - at the time I wrote the book I could not be absolutely sure about this. More than that some of the afterwar olympiads bore the numbers which suggested that two years (not one) were skipped. Only later I was made aware of the existence of materials that proved that the olympiad was indeed organized in 1943. At the time of publication I decided not to mention that and simply (just in case) skipped 1943 when listing the olympiad years in the author's foreword.

Hope that helps to clears up this issue.

It still seems that there is not a lot of hope to fully restore 1934-1960. Out of all the years/grades before 1961 I probably have about half of the materials but they are scattered all over. Some years are absent in their entirety and for some only one or two grades' versions were found. Especially strange was absence of materials from 1950s - but then again the jury of the olympiad has almost completely changed around 1960 and I wasn't able to find more than just a couple of people from that older jury. Too bad... perhaps these materials still exist somewhere and will be found by some future olympiad historian, younger and more tenacious than yours truly.

Dmitri Fomin

[quote="dvf"]
Dmitri Fomin[/quote]

Wow, a new valuable guest  :)

Pierre.


analytic geometry
geometry
geometric transformation
dilation
rotation
trigonometry
geometric sequence

A sequence $ (a_1,b_1)$, $ (a_2,b_2)$, $ (a_3,b_3)$, $ \ldots$ of points in the coordinate plane satisfies \[ (a_{n \plus{} 1}, b_{n \plus{} 1}) \equal{} (\sqrt {3}a_n \minus{} b_n, \sqrt {3}b_n \plus{} a_n)\hspace{3ex}\text{for}\hspace{3ex}  n \equal{} 1,2,3,\ldots.\] Suppose that $ (a_{100},b_{100}) \equal{} (2,4)$.  What is $ a_1 \plus{} b_1$?

$ \textbf{(A)}\\minus{} \frac {1}{2^{97}}  \qquad
\textbf{(B)}\\minus{} \frac {1}{2^{99}} \qquad
\textbf{(C)}\ 0 \qquad
\textbf{(D)}\ \frac {1}{2^{98}}  \qquad
\textbf{(E)}\ \frac {1}{2^{96}}$

Hint:

[hide]Transform the points onto the complex plane (or cartesian) and notice the dilations and rotations that occur.[/hide]

[hide]Let $ z_n \equal{} a_n \plus{} i\cdot b_n$. Then
\[ (\sqrt {3} \plus{} i)\cdot z_n \equal{} (\sqrt {3}\cdot a_n \minus{} b_n) \plus{} i\cdot (\sqrt {3}b_n \plus{} a_n) \equal{} z_{n \plus{} 1}
\]
By the geometric sequence formula,
\[ z_n \equal{} z_1\cdot (\sqrt {3} \plus{} i)^{n \minus{} 1}
\]
Easily by definition, we have $ z_{100} \equal{} 2 \plus{} 4i$. Use demoivre's theorem to get:
\[ (\sqrt {3} \plus{} i)^{99} \equal{} 2^{99}\cdot \text{cis}\, 30\cdot 99 \equal{} 2^{99}i
\]
So $ z_1 \equal{} \frac {2 \plus{} 4i}{2^{99}i} \equal{} 2^{ \minus{} 97} \minus{} 2^{ \minus{} 98}i$. Now $ 2^{ \minus{} 97} \minus{} 2^{ \minus{} 98} \equal{} 2^{ \minus{} 98}$ so the answer is $ \boxed{D}$.[/hide]

Along with my comment that this problem seemed very familiar  :lol:

[quote="E^(pi*i)=-1"]A sequence $ (a_1,b_1)$, $ (a_2,b_2)$, $ (a_3,b_3)$, $ \ldots$ of points in the coordinate plane satisfies

$ (a_{n \plus{} 1}, b_{n \plus{} 1}) \equal{} (\sqrt {3}a_n \minus{} b_n, \sqrt {3}b_n \plus{} a_n)$  for $ n \equal{} 1,2,3,\ldots$.

Suppose that $ (a_{100},b_{100}) \equal{} (2,4)$.  What is $ a_1 \plus{} b_1$?

[b]A[/b]: $ \minus{} \frac {1}{2^{97}}$  [b]B[/b]: $ \minus{} \frac {1}{2^{99}}$  [b]C[/b]: $ 0$ [b]D[/b]: $ \frac {1}{2^{98}}$  [b]E[/b]: $ \frac {1}{2^{96}}$[/quote]

Can you put the answers in the following form? It'll make putting it into the resources section much nicer.

[code]$\textbf{(A)}\ AnswerA \qquad
\textbf{(B)}\ AnswerB \qquad
\textbf{(C)}\ AnswerC \qquad
\textbf{(D)}\ AnswerD \qquad
\textbf{(E)}\ AnswerE$[/code]

Done.  It does look a lot nicer that way.

Actually, after evaluating consecutive $ n$-values of $ a_n$ and $ b_n$ for 3 times using the definition, we will get $ a_{n\plus{}3}$ = $ \minus{}8b_n$ and $ b_{n\plus{}3} \equal{} 8a_n$. More substitions lead to $ a_{n\plus{}6} \equal{} \minus{}64a_n$ and $ b_{n\plus{}6} \equal{} \minus{}64b_n$. Finally we establish $ a_{n\plus{}12} \equal{} 2^{12} \cdot a_n$ and $ b_{n\plus{}12} \equal{} 2^{12} \cdot b_n$.

So we obtain $ a_{97} \equal{} 2^{96} \cdot a_1$ and $ b_{97} \equal{} 2^{96} \cdot b_1$.

Then, $ \minus{}a_{100} \equal{} \minus{}2 \equal{} 8 \cdot 2^{96} \cdot b_1$ and $ b_{100} \equal{} 4 \equal{} 8 \cdot 2^{96} \cdot a_1$.

Adding, $ 2 \equal{} 2^{99}(a_1 \plus{} b_1)$, so $ a_1 \plus{} b_1 \equal{} \frac {1}{2^{98}}$, hence $ (D)$.

But I guess the earlier solutions were more elegant and can be used in more contexts.

[quote="MellowMelon"]You know you suck when you looked at the topic referenced above a day before the test, see this problem and think "aha that technique will work", and manage to convince yourself a few minutes later that it won't.

This was the only problem I omitted...[/quote]

At least you didn't post on that topic explaining the exponents :oops:

Your answers are messed up. Can you fix them please?

No, I can't edit the post anymore.  Could a mod please fix it?

Each successive point in the sequence can be thought of as the image under a transformation mapping:

$ \left[\begin{array}{c}a_{n+1}\\ b_{n+1}\end{array}\right] =\left[\begin{array}{cc}\sqrt{3}&-1\\ 1 &\sqrt{3}\end{array}\right]\left[\begin{array}{c}a_{n}\\ b_{n}\end{array}\right] = 2\left[\begin{array}{cc}\cos 30^\circ &-\sin 30^\circ\\ \sin 30^\circ &\ \cos 30^\circ\end{array}\right]\left[\begin{array}{c}a_{n}\\ b_{n}\end{array}\right] $

So we now see that $(a_{1} , b_{1})$ is found by taking $(a_{100} , b_{100})$ and rotating it $30^\circ\times99$ times clockwise and dilating by a factor of $\frac{1}{2^{99}}$.  The point then becomes $(a_{1} , b_{1})=\left(\frac{4}{2^{99}},\frac{-2}{2^{99}}\right)$, and our correct answer is $D$.

Ummm.... unless I'm not reading it right that is no extension.

Then let's call it an Add-on problem.

EDIT: @Brut3: I know, it's just that I thought that this problem was worth posing for the people that haven't been exposed to this type of problem.

The "add-on" problem is much easier than the original problem.

Especially since above users have found the point exactly :P

[quote=t0rajir0u]See [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=187900]Turkey TST 1997[/url] and my comments.  :)[/quote]
He offers deeper insight here, but in the rush of the AMC 12, we could say the idea is rather to be reminded—purely by memory—of component-wise complex multiplication, that is $$(ac-bd)+(ad+bc)i=(a+bi)(c+di).$$ From there, we assign $a,b,c,d$ so it all works out and we're on our way.

The same idea also appears in [url=https://artofproblemsolving.com/community/c6h522371p2944660]2013 University of Tokyo Entrance Examination[/url].


I recently read the chapter about Limits about AoPS 2. I am completely befuddled...

Can someone help me?

That's a really vauge question... can you be more specific?

Well surely there's something in there you can do.

Why don't you post a few representative examples of what you [b]do[/b] get and a few representative examples of what you [b]don't[/b] get... and then we can try to help  :)

Because limits is a very broad subject


integration
function
limit
calculus
calculus computations

[quote="AYMANE"]lets $ a\in\mathbb{C}$ and $ \gamma(a) \equal{} \int_{0}^{ \plus{} \infty}e^{ \minus{} t}t^{a \minus{} 1}dt$
Prove that the equinalent of $ a_n \equal{} a(a \plus{} 1)(a \plus{} 2).....(a \plus{} n)$ when $ n$ goes to $ \plus{} \infty$ is $ \frac {n^{a}n!}{\gamma(a)}$[/quote]
hmm, I can prove , but it's well known :
I only show you idea:
at first : We need to find function $ \Gamma$ on the set $ G \in C$
such as if $ z\in C$ then $ z \plus{} 1 \in C$
and also $ \frac {\Gamma (z \plus{} 1)}{\Gamma (z)} \equal{} z$
and was analytic function.
by this condition we conclude that :
$ \frac {1}{\Gamma (z)} \equal{} ze^{h(z)}\prod_{k \equal{} 1}^{\infty}(1 \plus{} \frac {z}{k})e^{ \minus{} \frac {z}{k}}$
after calculating We have that : $ h(z) \equal{} \gamma z$
then you mast say that function $ \Gamma (z)$ and $ \int_{0}^{\infty}e^{ \minus{} z}t^{z \minus{} 1}dz$ is same .
and by direct calculation you can show that :
$ \Gamma (z) \equal{} \lim_{n \minus{} > \infty}\frac {n^{z}n!}{z(z \plus{} 1)...(z \plus{} n)}$ you are done


geometry
inradius
geometric transformation
reflection
perpendicular bisector
angle bisector
geometry unsolved

The Feuerbach point is the point of tangency between the incircle and the nine-point circle. Then, $ IF$ is an inradius, so the tangent line drawn to the incircle, centered at $ I$ with radius $ IF$, from $ H_a$ contains side $ BC$.
Furthermore, the nine-point center is the intersection $ N$ of line $ IF$ and the perpendicular bisector of $ FH_a$, since $ H_a$ lies on the nine-point circle. Then the nine-point circle has center $ N$ and radius $ NH_a$. It intersects $ BC$ at $ H_a$ and another point $ M_a$, the midpoint of $ BC$.
If we can construct $ I_a$, the $ A$-excenter, we can draw $ II_a$, the angle bisector of $ \angle A$. If the incircle is tangent to $ BC$ at $ X_a$, then the $ A$-excircle is tangent to $ BC$ at the image $ X_a'$ of $ X_a$ through the reflection across $ M_a$. Note that the $ A$-excircle is also tangent to the nine-point circle. So $ I_aN \minus{} I_aX_a'$ is the nine-point circle radius. Construct the point $ P$ on the perpendicular to $ BC$ through $ X_a'$ so that $ X_a'P \equal{} NF$ and $ P$ is on the same side of $ BC$ as $ I$. Then $ N$ and $ P$ are both points on the circle centered at $ I_a$ with radius $ NI_a$. Thus $ I_a$ is the intersection of $ PX_a'$ and the perpendicular bisector of $ NP$.
$ A$ is the intersection of the perpendicular to $ BC$ through $ H_a$ and $ II_a$. $ B$ and $ C$ are the intersections of the tangents from $ A$ to the incircle and $ BC$.


How many positive integers are factors of $ 21^{75}$?

The formula for factors is when a number's prime factorization is a^x*b^y, the number of factors is (x+1)(y+1). This is because there are x+1 different number of a's you can choose to use in the factor (up to x and including 0), and likewise for b. Since 21^75 can be broken up into 3^75 times 7^75, the answer is 76*76=5776


The number $ 1987$ can be written as a three digit number $ xyz$ in some base $ b$ such that $ x\plus{}y\plus{}z\equal{}1\plus{}9\plus{}8\plus{}7$. Find all possible values of $ x,y,z,b$.

Obviosly $ b^3>1987\ge b^2$. Therefore $ 13\le b\le 44$. Sum of number digits must be $ s(n)\equal{}25\equal{}n\mod b\minus{}1.$
Therefore $ b|1987\minus{}25\equal{}1962\equal{}2*3^2*109$. Therefore if exist suth b, then $ b\equal{}18\plus{}1$, and $ 1987\equal{}5*19^2\plus{}9*19\plus{}11,s_{19}(1987)\equal{}s_{10}(1987)\equal{}25.$


Is this more of a number theory problem? I can't see how it can be like a classical inequality but I'll try


induction
function
modular arithmetic
Divisibility Theory

Find all positive integers $n$ such that $9^{n}-1$ is divisible by $7^n$.

[quote="nicetry007"]$ 9^{n}-1 = (3^{n}+1)(3^{n}-1)$.

This implies that $ 7$ either divides $ 3^{n}+1$ or $ 3^{n}-1$ and not both. Hence, $ 7^{n}$ either divides $ 3^{n}+1$ or $ 3^{n}-1$ and not both.

But $ 0 \;< \;3^{n}-1 \;<\;3^{n}+1 \;< \; 7^{n}$.

Hence, $ 7^{n}$ does not divide $ 3^{n}+1$ or $ 3^{n}-1$, which implies that $ 7^{n}$ does not divide $ 9^{n}-1$.[/quote]

An other lemma :
Let $ p$ is a odd prime.
Call order of  a  mod p is d where $ a\not\in\{ \minus{} 1,1\}$
Suppose $ a^d\equiv 1(\mod p^{k_0})$
Then the order of a $ \mod p^k$ is d for $ k \equal{} 1,...,k_0$ and $ d{p^{k \minus{} k_0}}$ if $ k > d$
It is an useful lemma and prove by induction on k by Newton express.
Now consider our problem:
$ ord_{9}(\mod 7) \equal{} 3$ and $ 9^3\equiv 1 (\mod 7 )$
Imply that $ ord_{9}(\mod 7^n) \equal{} {3}.{7^{n \minus{} 1}}$
Imply that $ 3.{7^{n \minus{} 1}}|n$ so has no positive integer satisfy the condition.
Consider the equation:
$ a^n\equiv 1 (\mod p^n)$ where $ a\not \in \{ \minus{} 1,1\}$
Prove that the equation has only solution.
Here is some example :
[b]1.[/b] Consider the function :$ f: N\to N$
Satisfy : $ \frac {n}{f(n)}$ is bound for all $ n\in N$
Consider the equation:
$ a^n\equiv 1 (\mod p^{f(n)})$
Prove that the equation has finite solution.

Very nice solution by nicetry007 which is likely the intended solution.  Again, like A87, [url=http://www.artofproblemsolving.com/Resources/Papers/LTE.pdf]lifting the exponent[/url] kills this problem.

Since $9^n-1\equiv 0\pmod{7}$ we notice $\text{ord}_{7}9=3$ therefore $n\equiv 0\pmod{3}$.  Therefore substitute $n=3k$ to give us $729^k-1$ is divisible by $7^{3k}$.  By lifting the exponent $v_7(729^k-1)=v_7(729-1)+v_7(k)=1+v_7(k)\ge 3k$.  However $v_7(k)\le k$ so therefore $k+1\ge 1+v_7(k)\ge 3k$ contradiction.  There are no such $n$.

I apologize to everyone for my solution being very similar to that of [b]Binomial-theorem[/b].

First take care of $9^n\equiv 2^n$ is periodical in $(mod{7})$, $2,4,1,2,4,1,\dots$.Thus $n=3m(m\in \mathbb N),and 7^{3m}|9^{3m}-1=729^m-1$.$7\nmid 729, 7\nmid 1, 7|729-1$.By Lifting the Exponent Lemma,$v_7(729^m-1)=v_7(729-1)+v_7(m)=1+v_7(m)$.Let $m=7^kt(k\in \mathbb N_{0},7\nmid t)$.Then $3\cdot 7^k\le 3\cdot 7^kt\le 1+k$ which is absurd$(k\in \mathbb N_{0})$.Therefore there is no such $f$.$\blacksquare$ :coolspeak:


trigonometry
analytic geometry
graphing lines
slope

The graphs of y = cos x and y == tan x appear to cross at right-angles. Is this correct?

Yes, this can be proven with a bit of calculus.

First, recall that:
\[ \frac{d}{dx} \cos x \equal{} \minus{}\sin x\]
and:
\[ \frac{d}{dx} \tan x \equal{} \sec^2 x \equal{} \frac{1}{\cos^2 x}
\]

At any point $ \cos x$ crosses $ \tan x$, we have $ \cos x \equal{} \tan x$, or equivalently, $ \cos x \equal{} \frac{\sin x}{\cos x} \implies \cos^2 x \equal{} \sin x$.

Thus, substituting $ \sin x$ for $ \cos^2 x$ in $ \frac{d}{dx}\tan x$, we obtain $ \frac{d}{dx}\tan x \equal{} \frac 1{\sin x}$ whenever $ \cos x \equal{} \tan x$, and since $ \minus{}\sin x$ and $ \frac 1{\sin x}$ have perpendicular slopes, we can conclude that they intersect at right angles.


Sally works at a grocery store. In one week she earned $ \$390$ for working 47 hours, of which 7 hours were overtime. The next week she earned $ \$416$ for working 50 hours, of which 8 hours were overtime. What is Sally's overtime rate in dollars per hour?

[quote="Bugi"]390=40x+7y
416=42x+8y
x=8,y=10
Answer: 10[/quote]
  Thanks for this,
 this is willistowers.


inequalities
logarithms
inequalities unsolved

Let 0<a;b<1.Prove that:
$ ln\frac{a}{1\minus{}a}\minus{}ln\frac{b}{1\minus{}b}>4(a\minus{}b)$

First, note that equality can occur, say if $ a \equal{} b$.

WOLOG, let $ a \le b$.  If $ a \equal{} b$, then the inequality is trivial, so assume that $ a < b$.  Let
\[ f(x) \equal{} \log \frac{x}{1 \minus{} x} \equal{} \log x \minus{} \log (1 \minus{} x).\]
By the Mean Value Theorem,
\[ \frac{\log \frac{b}{1 \minus{} b} \minus{} \log \frac{a}{1 \minus{} a}}{b \minus{} a} \equal{} f'(c)\]
for some $ c \in (a,b)$.  But
\[ f'(c) \equal{} \frac{1}{c} \plus{} \frac{1}{1 \minus{} c} \equal{} \frac{1}{c(1 \minus{} c)} \ge 4,\]
by AM-GM.  The result follows.


[color=brown]Two circles $ (O_1)$, $ (O_2)$ are tangent at $ A$. A common tangent to both circles touches them at $ B_1,B_2$ respectively. $ C$ is the foot of the perpendicular from $ A$ to $ B_1B_2$. Prove that lines $ O_1B_2,O_2B_1,AC$ are concurent.[/color]

Call $ P: B_1O_2 \cap B_2O_1$, draw a line through P perpendicular to $ B_1B_2$ that meet $ O_1O_2$ at Q. $ \triangle B_1PO_1 \sim \triangle B_2PO_2$, then $ \frac{QO_1}{QO_2}\equal{} \frac{r_1}{r_2}$ so $ Q \equiv A$


superior algebra
superior algebra unsolved

Can we determine the order of $ PGL(n,q)$ in terms of $ n$ and $ q$?

Yes, look at http://www.artofproblemsolving.com/Forum/viewtopic.php?t=106542, then the conclusion follows.


Hi every body  :)
Find all applications f:IR--->IR such that:

(fofofof)(x)=(fofof)(x)+2x

enjoy :lol:

Gjeni f(x) n.q.s  (fofofof)(x)=(fofof)(x)+2x
Zgjidhje: E kerkojme funksionin te formes f:y=kx kemi
(fofofof)(x)=k^4*x   (fofof)(x)=k^3*x pra k^4*x=k^3*x+2x
k^4-k^3-2=0  (k+1)(k^3-2k^2+2k-2)=0
k+1=0,  k=-1   k^3-2k^2+2k-2=0
Pra f:y=-x ose f:y=ix ku i eshte rrenje e ekuacionit tjeter.


Is there a way to put more than one line of text to the side of an image?

Like on AoPS documents, they've got the logo thingy in the upper left, and then 4 lines of text to the right of it.  How do I do?

We use \parbox's.  \parbox (or it's analog the minipage) is good to use when you want a block of stuff next to another block of stuff.

Here's a sample of our code (it's ugly, but it works):

[code]
\chead{\parbox{1in}{\includegraphics[height=77pt,width=0.866in]{CalBaseBW.pdf}}
\parbox{5in}{\begin{center}\large {\em The Art of Problem Solving Online Classes}
\\  {\bf MATHCOUNTS/AMC Counting} \\MidTerm Challenge
\\ {\normalsize www.artofproblemsolving.com}\end{center}}}[/code]
(\chead is part of the [b]fancyhdr[/b] package)

Another solution is to use the [b]picins[/b] package.  Go to [url]http://www.ctan.org[/url] and search for it.

ahhh, thanks!!   Except.. I didn't have fancyhdr, so I went to download it the way described in the LaTeX guide and ended up with the following:

[quote]Starting package installation...
Installation folder: "C:\texmf"
 Package repository: "ftp://ctan.math.utah.edu/tex-archive/systems/win32/miktex/tm/packages/"
DBlight signature: 277775b8be4dc6432a8cb7c0b68c5f6a
Estimating expenditure...
  downloading: 285544 bytes
   installing: 6 files (1 packages)
downloading "ftp://ctan.math.utah.edu/tex-archive/systems/win32/miktex/tm/packages/fancyhdr.cab"...

Error: The file

  ftp://ctan.math.utah.edu/tex-archive/systems/win32/miktex/tm/packages/fancyhdr.cab

cannot be downloaded for the following reason:

The system cannot find the file specified.

Package installation failed.[/quote]

Know what's up?  :huh:

EDIT:::: nevermind, I just changed the site it downloaded from.   I worked fine and now it's lookin great!  Thanks a much


function
logarithms
algebra
functional equation
algebra proposed

Solve in real nubers the equation $f(f(x))=-x$ for $x\in R$

Sounds familiar  ;)
[url=http://www.mathlinks.ro/Forum/topic-56637.html]www.mathlinks.ro/Forum/topic-56637.html[/url]

[quote="silouan"]It looks familiar but the question is different. This is an EQUATION.[/quote]
You mean "find all such $f$"?

For the function $f(f(x))=-x$ for each real number I have the above results.

$f(x)$ take all the real prices.

the $f$ and $f^{-1}$ are odd.

and $f^{-1}(x)=-f(x)$

So I say that the $C_{-f}$ and the $C_{f^{-1}}$  are the same.

I am wrong ?

[quote="silouan"]
$f(x)$ take all the real prices.
[/quote]
Not "prices" but "values". ;)
Plus, isn't there a mistake when calculating f^(-1)?

EDIT: Sorry, I hadn't seen your post enescu  :blush:

[quote="enescu"]You probably meant $f^{-1}(x)=-f(x)$.[/quote]

Yes typo

By the way, here's an interesting problem: give an example of such a function which is continuous at $x=0$.
Hint: watch the graph referred in post #2

I wasn't able to conveniently modify that graph... :oops: .
Fortunately, I found another solution of the functional equation which is continuous at x=0 :
$f(x)=\left\{\begin{array}{cc}\frac{x}{10},&\mbox{ if x } \neq \mbox{ 0 and } [\log_{10}\mid x\mid ]\mbox{ is odd}\\o,&\mbox{ if x=0}\\-10x,&\mbox{ if x } \neq \mbox{ 0 and } [\log_{10}\mid x\mid ] \mbox{ is even}\end{array}\right.$
 :)

[quote="enescu"][quote="silouan"]Which graf you mean enescu ?[/quote]
[url=http://http://www.mathlinks.ro/Forum/viewtopic.php?t=49191]see post #4 here[/url][/quote]

the page cannot be displayed

Silouan, the graph is here: http://www.artofproblemsolving.com/Forum/viewtopic.php?t=49191


function
summer program
PROMYS
number theory unsolved
number theory

Let $ p$ be an arbitrary prime, $ a,b$ be two positive integers such that :
            $ a\equal{}a_k.p^k\plus{}a_{k\minus{}1}.p^{k\minus{}1}\plus{}...\plus{}a_1.p\plus{}a_0$
and       $ b\equal{}b_k.p^k\plus{}b_{k\minus{}1}.p^{k\minus{}1}\plus{}...\plus{}b_1.p\plus{}b_0$
here $ \large 0 \leq a_i,b_i < p$ are integer for $ i\equal{}0,1,2,...,k$. Prove that :
     $ (^a_b) \equal{} (^{a_k}_{b_k}).(^{a_{k\minus{}1}}_{b_{k\minus{}1}})...(^{a_1}_{b_1}).(^{a_0}_{b_0}) (mod p)$

I need a clear solution for this problem!! Help me please!!

First prove that $ \binom{n}{k}\equal{}\binom{n_{1}}{k_{1}}\binom{n_{0}}{k_{0}}(mod p)1$ if $ n\equal{}pn_{1}\plus{}n_{0}$ $ k\equal{}pk_{1}\plus{}k_{0}$.
If this is true then the Lucas's theorem follows by simple induction.
I will give the sketch of combinatorial proof of this.
Consider a hotel consisting of two buildings. THe first building has $ n_{1}$ floors each floor has p rooms. The second building is single floor with $ n_{0}$ rooms. The hotel has n rooms total. Now we want to put k people in the hotel. Let S be set of all such configurations.  If we do that than we must put
$ k_{1}p$ people in the first building and $ k_{0}$ in the second. Now let f be a function from S to S which moves each person in the first building to the floor above(the person in the last floor is moved to the first floor room which is below him). People in the second building are not moved by f. It is easy to see that f is correctly defined function and $ f^{p}(x)\equal{}x$ for each configuration x. From here it is not difficult to provet that number of fixed points of f is congruent to number of all ellemnts of S(because p is prime all ellements of S are either fixed points or they belong to some orbit with length p). And from here
 $ \binom{n}{k}\equal{}\binom{n_{1}}{k_{1}}\binom{n_{0}}{k_{0}}(mod p)1$ . Since the first number is the number of ellements of S and the second is the number of fixed points of f.

Thank you for this solution!
[quote="Baronov"] If we do that than we must put
$ k_{1}p$ people in the first building and $ k_{0}$ in the second. Now let f be a function from S to S which moves each person in the first building to the floor above(the person in the last floor is moved to the first floor room which is below him). People in the second building are not moved by f. It is easy to see that f is correctly defined function and $ f^{p}(x) \equal{} x$ for each configuration x. [/quote]
Sorry, but I think $ f^{n_1}(x)\equal{}x$.
[quote="Baronov"]From here it is not difficult to provet that number of fixed points of f is congruent to number of all ellemnts of S(because p is prime all ellements of S are either fixed points or they belong to some orbit with length p). And from here
 $ \binom{n}{k} \equal{} \binom{n_{1}}{k_{1}}\binom{n_{0}}{k_{0}}(mod p)1$ . Since the first number is the number of ellements of S and the second is the number of fixed points of f.[/quote]
Can you write it in details!!

Personally, I like the proof by generating functions.  First, let's be really clear:  the result we're trying to prove is

$ {pn_1 \plus{} n_0 \choose pk_1 \plus{} k_0} \equiv {n_1 \choose k_1} {n_0 \choose k_0} \bmod p$.

where $ 0 \le n_0, k_0 < p$.  First prove that $ p | {p \choose k}$ for $ p$ a prime, $ 1 \le k \le p\minus{}1$.  Conclude that

$ (x \plus{} 1)^p \equiv x^p \plus{} 1 \bmod p$

Finally, deduce that

$ (x \plus{} 1)^{pn_1 \plus{} n_0} \equiv (x^p \plus{} 1)^{n_1} (x \plus{} 1)^{n_0} \bmod p$

and consider the coefficient of $ x^{pk_1 \plus{} k_0}$.  ;)  This is the proof I used at PROMYS on our problem sets.


Find the units digit of 7 raised to the power of 2007.

[hide]Powers of 7 repeat in cycles of 4, so it's 3.[/hide].

Uh, is it me, or am I starting to divide wrong, because
[hide]Powers of 7 do repeat in cycles of 4, 2007 has a remainder of 3 when divided by 4, so it's 3...[/hide]

Seven's repetitive exponent sequence is 7,9,3,1 and since 2007/4 has a remainder of 3 so the third digit in the series is 3 :P

Euler's phi/totient function, which we apparently can't discuss in Mathcounts forum.

YEah, I remember the last time we did;it got moved to Intermediate.


[hide]Denote the position of a hand at a certain time to be the measure of the angle it makes with a ray from the center fo the 12. This degree measure can be reflex, because we measure it by starting on this ray and moving clockwise until we hit the hand.

We have $120+\frac{x}{2}$ for the position of the hour hand after $x$ minutes, for the minute hand it is $6x$. Since $120>90$, the first time this will happen, the minute hand will not have overtaken the hour hand. Hence

$120+\frac{x}{2}=6x\Rightarrow x=240/11$, which is approximately $4: 21: 49$.[/hide]

Time
1992 National Target # 2
To the nearest second, what is the first time between 4:00 and 5:00 that the minute and hour hands of a clock are perpendicular to each other? Express your answer in the form hr:min:sec
[hide]
i first got the ratio between the hour and the minute hands as in every time the hour hand moved 1 degree the minute hand moved 12. For the first time the two hands could be perpendicular I knew that the minute hand must be "before" (as in before 5) the hour hand. So I made an equation stating that every time x ( the minute hands degree of movement) occurs, it must be subtracted from 120 degrees ( the initial degrees btw the hour and minute hand) then x/12 (the hour hands degree of movement) must be added to it to get 90 degrees. Now that I had the equation (which looked like x/12 +120 -x = 90), I simply solved it out to get 32 and 8/11 degrees, which translated to about 5 minutes and 27 seconds. So the first time is 4:05:27[/hide]

EDIT: i hid my answer

[quote="pascal_1623"]That seems like they would be close to on top of each other... :huh:[/quote]

It is.

He should've made an absolute value equation, but you get the idea.

so...who has the right answer, 1337 or Insanely Bored?  :huh:


linear algebra
matrix
linear algebra solved

This question is from a test in my linear algebra class, which I believe was faultily graded. How would you answer?

[b]Show your work for full credit on each problem.[/b]

1. Indicate whether the statement is [b]always true[/b] or [b]sometimes false[/b].

(a) If both matrices A and B are symmetric, then
(i) AB is symmetric. (ii) AB+BA is symmetric.

(b) If both matrices A and B are invertible, then
(i) AB is invertible. (ii) A+B is invertible.

Off the top of my head,

1)
a) no
b) yes (this is the only one I'm not 100% sure about)

2)
a) yes
b) no

(a) (i) FALSE

$\begin{bmatrix}2&0\\ 0&1\end{bmatrix} \begin{bmatrix}1&1\\ 1&1\end{bmatrix}= \begin{bmatrix}2&2\\ 1&1\end{bmatrix}$

(a) (ii) TRUE

$A$ symmetric iff $A^T=A.$

$(AB+BA)^T=(AB)^T+(BA)^T=B^TA^T+A^TB^T=BA+AB=AB+BA.$

(b) (i) TRUE

By construction. $(AB)^{-1}=B^{-1}A^{-1}.$

(b) (ii) FALSE

Many silly examples. Try $A=I,\,B=-I.$

[quote="Valentin Vornicu"][quote="Ravi B"]If $A$ and $B$ have different sizes, does each statement become false?  Or are we supposed to assume that $A$ and $B$ have the same size?[/quote]I think that it was also given that they have equal sizes (square matrices) otherwise the questions would not make any sense, really :)[/quote]
Bingo! It was not given that A and B were the same size. This the error that I found, also. However, my instructor won't admit that he should have included this statement; he says that since he asked a question about the product of A and B, AB and BA must exist.

He claims, therefore, that 1(a)(ii) and 1(b)(i) are both always true, which they would be if A and B were the same size.

But since A and B might be different sizes, the products AB and BA may not exist, and therefore all of the statements are sometimes false. He won't admit that he's wrong, though, and I can't get him to correct his mistake and change my grade! :mad:

Any ideas what I should do?

Well if $A$ and $B$ are not square matrices of the same size, almost all problems we discuss about don't really make sense. I think he's being slightly biased in his decision. He knows very well he made a mistake, but he's probably punishing you for other reasons (which is bad, however it's not something you can stop him do - strictly mathematically speaking, he is right if the statement is just the one you presented).


probability
expected value
probability and stats

Hi all, I very much appreciate if someone can help me with this exercise:

A typist get work according to a process poisson, with an average of four jobs per hour. The works are typed according to the order of arrival, and the average job requires 12 minutes of time of worker; apparently the actual work time is exponentially distributed around this average. Determine:
a)	The probability that a job will be completed in less than 45 minutes after arrival.
b)	The probability that the typist complete all work by the end of the day.
c) The probability that the job would lead to the typist least 12 minutes.

Solution: 0528; 0.2; 0632 respectively.

I have not so far addressed.

greetings

do you know how to compute the probability that at the instant $ t$ the typist is typing and $ (k\minus{}1)$ files are waiting to be typed (call this event $ A_k$)?  Then if you denote the time for the job arriving at the instant $ t$ to be completed by $ T$, $ E[T] \equal{} \sum_k E[T|A_k] P[A_k] \equal{} \sum_k (k\plus{}1) \tau P[A_k]$, where $ \tau$ is equal to $ 12$ minutes (why?) Does this help ?

Alekko Hello, thank you very much for your help.

I'm not sure I follow all your counterquestion, but try to understand what you do despite my limited English.

Honestly, the formula for the expected value on queuing theory did not see in my course, So thank you to help me a little more.

If anything serves, I've been thinking about using the following formulas for some of the calculations. 	We can unite with that? Were they right?:

$ \lambda \equal{} 4 work/hours$. $ \mu \equal{} 5 jobs/hours$.

$ \rho \equal{} \lambda/\mu \equal{} 4/5 \equal{} 0.8$ While the system remains busy.

$ P_0 \equal{} 1 \minus{} \rho$, = 0.2 While the system remains idle.

$ P^n \equal{} (1 \minus{} \rho)\rho^n$ The probability of n jobs in the system at any given time.

$ L \equal{} \displaystyle\frac {\rho}{1 \minus{} \rho} \equal{} \displaystyle\frac {0.8}{0.2} \equal{} 4$ The average number of jobs in the system.

$ L_q \equal{} \displaystyle\frac {\rho^2}{1 \minus{} \rho} \equal{} \displaystyle\frac {0.8^2}{0.2} \equal{} 3.2$Average number of jobs in the queue.

$ W \equal{} \displaystyle\frac {1}{\mu(1 \minus{} \rho)} \equal{} \displaystyle\frac {1}{5(0.2)} \equal{} 1$ Average waiting time in the system.

$ W_q \equal{} \displaystyle\frac {\rho}{\mu \minus{} \lambda} \equal{} \displaystyle\frac {0.8}{5 \minus{} 4} \equal{} 0.8$ Average waiting time in the queue.

$ W_s \equal{} W \minus{} W_q \equal{} 0.2$ The average time it takes for a service.

$ Pr(n > k) \equal{} \rho^{k \plus{} 1} \equal{}$ 	The probability that in the system at any given time more than n jobs.

These formulas and conclusions are fine for this case?
For otr hand, do not know why I could not get the questions.

I appreciate if you help me with the first, a little more, and tell me how to draw the other.

Thank you very much and greetings

so (with your notations) $ P[A_k]\equal{} P^k\equal{} (1\minus{}\rho)\rho^k$

I passed one ....
see that they are asking for a chance ....

[b]b) The probability that the typist complete all work by the end of the day.[/b]

This might be?: $ P_{0}\equal{} 1\minus{}\rho$ = 0.2 While the system remains idle

Greetings

Got it! There will be that, as the distribution of services, with $ \mu \equal{} 5$
is a Poisson distribution, plays find with this distribution?

Greetings


group theory
abstract algebra
vector
function
linear algebra
matrix
superior algebra

Fix $m$ natural. For any $n$ we can ask how many subgroups of index $n$ have $\mathbb{Z}^{m}$?.... for example for $\mathbb{Z}^{2}$ we have 3 subgroups of index 2.... what can you say in the general case?

You can reduce to a finite problem by considering $(\mathbb{Z}/m\mathbb{Z})^{n}$; the multiples of $m$ are in any subgroup of index $m$. If $m$ is prime, the number we're looking for is the number of subspaces with codimension 1 in the vector space $(\mathbb{Z}/m\mathbb{Z})^{n}$. This number is $\frac{m^{n}-1}{m-1}$.
If $n$ is fixed, the number we're looking for is a multiplicative function of $m$. We've calculated it for primes- we need prime powers to get everything, and that's quite a bit more complicated.

This is a nice point of view, i'll try to work on it....  I was working with matrices, since theese subgroups are free of $n$ generators  for each one I can associate a matrix $\alpha=(\alpha_{1},...,\alpha_{n})\in \mathbb{Z}^{n\times n}$, $det(\alpha)\neq 0$ st the subgroup is $S_\alpha=\alpha_{1}\mathbb{Z}\oplus\cdots\alpha_{n}\mathbb{Z}$

the index $(\mathbb{Z}: S_\alpha)=|det \alpha|$ and $S_\alpha=S_\beta$ when there exists a matrix $U$ of determinant $1$ st $\alpha=\beta U$ so it's also a problem of clasification of matrices with given determinant...  well I couldn't go further... I hope theese obs can be usefull  :roll: .


algebra polynomial integration symmetry trigonometry function calculus

Try to find: The asymptotics for the number of real roots of the Bernoulli
polynomials. $B_{n}(x)$ :lol:

A definition of the [url=http://en.wikipedia.org/wiki/Bernoulli_polynomials]Bernoulli polynomials[/url]: $B_{n}$ is the unique polynomial (of degree $n$) such that $\int_{x}^{x+1}B_{n}(t)\,dt=x^{n}$ for all $x$.

We also have $\sum_{k=1}^{m}k^{n}=\frac1{n+1}B_{n}(m+1)+c$ (This constant $c$ is zero about half the time). The coefficients of these polynomials are essentially Bernoulli numbers.

Since $B_{n+1}'(x)=B_{n}(x)$, $B_{n+1}$ has at most one more real root than $B_{n}$, and the complex roots of $B_{n}$ are contained in the convex hull of the roots of $B_{n+1}$

The first five Bernoulli polynomials each have a number of real roots equal to their degree, but the sixth only has two; it has positive local minima at zero and 1. By the symmetry of the polynomials around $\frac12$, we lose roots in batches of 4.

Is the answer $\frac 2{\pi e}n$? :? The way I'm thinking of it is the following: $B_{n}(x)$ is (up to an irrelevant factor $n!$) the same as the $n$-th Taylor coefficient of $\frac z{e^{z}-1}e^{xz}$ with respect to $z$ at $0$. Now, this coefficient may be determined either by the nearest poles of the first factor or by the $n$-th coefficient of the second factor, so we basically have $\frac 1{(2\pi)^{n}}(\sin\text{ or }\cos) 2\pi x$ and $\frac{(ex)^{n}}{n^{n}}$ competing with each other. If $|x|< \frac{n}{2\pi e}$, the oscillating term wins; otherwise the victory goes to the positive term. The oscillating term has 2 zeroes per unit length, hence the answer above. This argument is full of gaps, of course, but I think I can fill most of them. If the answer is correct, I'll try to post a full formal proof.

Hi fedja. Yes you are right. You are really good in math. Full naswer is $\frac{2n}{e\pi}+\frac{\ln(n)}{e\pi}+o(1)$ your idea is really good. if you want I can represent proof.

Let's see if I can get that more precise result as well. Due to symmetry, we can count only the roots greater than $1/2$. The key is the residue theorem applied to the function $\frac{ze^{xz}}{e^{z}-1}$ in the left half-plane $\text{Re\,z}\le r$ with some $r>0$. It gives (for $n$ divisible by $4$, say, which is enough for our purposes because of jmerry's observation).
\[\frac 1{n!}B_{n}(x)+2\cdot(2\pi)^{-n}\cos 2\pi x+\Sigma(x)=\frac 1{2\pi}I(x) \]
where $\Sigma(x)=2\sum_{k\ge 2}(2\pi k)^{-n}\cos 2\pi kx$ and
\[I(x)=\int_{\mathbb R}\frac{e^{x}(r+iy)}{(e^{r+iy}-1)(r+iy)^{n}}=\frac{e^{xr}}{r^{n}}\int_{\mathbb R}\frac 1{e^{r+iy}-1}\left(\frac{e^{iyx/n}}{1+iy/r}\right)^{n}\,. \]
It is not hard to see that $\Sigma(x)$ and $\frac d{dx}\Sigma(x)$ are negligible compared to $(2\pi)^{-n}$, so we can safely drop this term in the considerations below.

$I(x)$ does not depend on $r$ but we can choose the most convenient $r$ to evaluate this integral. It is not hard to see that $B_{n}$ has no root greater than $An$ in absolute value where $A$ is some really big constant (we could prove it too but the explicit formula also yields this result fairly easily). Now, if $x<an$ and $a>0$ is small, then we can choose $r=10$, say, and get the estimate of order $10^{-n}e^{10an}<\!<(2\pi)^{-n}$ for both $I(x)$ and $\frac d{dx}I(x)$, so on the interval $[0,an]$ the zeroes of $B_{n}$ are really determined by the $\cos$ part. Thus, we need to investigate the case when $an<x<An$.

The integral in the last representation of $I(x)$ is oscillatory unless we kill the linear term in the Taylor decomposition of $\frac{e^{iyx/n}}{1+iy/r}$ at $y=0$. This can be achieved by choosing $r$ such that $xr=n$. Then $I(x)$ can be immediately found using the classical Laplace asymptotic formula and the answer is about $C(r)\frac{(ex)^{n}}{n^{n}\sqrt n}$ where $C(r)>0$ is bounded away from $0$ and $\infty$ as long as $r$ stays bounded from $0$ and $\infty$. The same estimate holds for the derivative $\frac d{dx}I(x)$. Thus, if this estimate is less than, say, $0.1\cdot(2\pi)^{-n}$, the zeroes are determined by $\cos$ and if it is greater than $100\cdot(2\pi)^{-n}$, there are no zeroes. Solving the corresponding inequalities, we see that in the interval $\left[0, \frac{2n+\log n}{4\pi e}-C\right]$ the zeroes are governed by the $\cos$ term and beyond $\frac{2n+\log n}{4\pi e}+C$ there are no zeroes. ($C$ is some large constant here).

It remains to observe that the interval $\left[\frac{2n+\log n}{4\pi e}-C,\frac{2n+\log n}{4\pi e}+C\right]$ can contain only $O(1)$ zeroes. Indeed, if there were too many zeroes here, then $B_{n-m}=B_{n}^{(m)}$ would have at least one zero in that interval where $m$ is a large fixed positive integer. But it is impossible because the same reasoning applied to $n-m$ instead of $n$ shows that there are no zeroes of $B_{n-m}$ beyond $\frac{2(n-m)+\log (n-m)}{4\pi e}+C<\frac{2n+\log n}{4\pi e}-C$.

That's it. Is your proof simpler, Extremal?

this is not my proof. It's Efimov proofs.

Some references about the zeros of Bernoulli polynomials:

[1]  D.H.Lehmer, [i]On the Maxima and Minima of Bernoulli Polynomials,[/i] Amer.Math.Monthly 47(1940)533-539.
[2]  N.E.Norlund, [i]Memoire sur les Polynomes de Bernoulli,[/i] Acta Math., 43(1920)121-196.
[3] A.M.Ostrowski, [i]On the zeros of Bernoulli Polynomials of even order,[/i] L'Enseignement Mathematique 6(1960)27-46.


category theory
superior algebra
superior algebra unsolved

Prove that a covariant functor transforms an isomorphism into a isomorphism.

If $ f\circ g \equal{} 1$ and $ g\circ f\equal{}1$, what can we say about $ F(f)$ and $ F(g)$?


inequalities
geometry
inequalities proposed

[i]Author of the problem is Adrian Satja Kurdija (although, of course, it may be possible that there already exists a very similar or same problem author didn't know about). This was Problem 1 (Algebra) for 10th grade on 1st Balkan Student Mathematical Competition 2008 - a competition 11 schools from Balkan area took part of during November 2008. All information about the competition can be found on http://www.mathlinks.ro/viewtopic.php?t=243614.[/i]

If $ x$, $ y$ and $ z$ are positive real numbers for which $ x \plus{} y \plus{} z \equal{} 1$, prove the inequality $ \frac {1}{\sqrt {x \plus{} y}} \plus{} \frac {1}{\sqrt {y \plus{} z}} \plus{} \frac {1}{\sqrt {z \plus{} x}} \leq \frac {1}{\sqrt {2xyz}}$.

[quote="mornik"]
If $ x$, $ y$ and $ z$ are positive real numbers for which $ x \plus{} y \plus{} z \equal{} 1$, prove the inequality $ \frac {1}{\sqrt {x \plus{} y}} \plus{} \frac {1}{\sqrt {y \plus{} z}} \plus{} \frac {1}{\sqrt {z \plus{} x}} \leq \frac {1}{\sqrt {2xyz}}$.[/quote]
The following inequality is true too.
Let $ x,$ $ y,$ $ z$ and $ k$ are positive numbers such that $ x\plus{}y\plus{}z\equal{}1.$ Prove that
\[ \frac {1}{\sqrt {x \plus{} ky}} \plus{} \frac {1}{\sqrt {y \plus{} kz}} \plus{} \frac {1}{\sqrt {z \plus{} kx}} \leq \frac {1}{\sqrt {(1\plus{}k)xyz}}\]

We can easily prove the tighter inequality"
$ \frac{1}{{x \plus{} ky}} \plus{} \frac {1}{ {y \plus{} kz}} \plus{} \frac {1}{ {z \plus{} kx}} \leq \frac {1}{3 {(1\plus{}k)xyz}}$
It is indeed killed by Cauchy Chwartz from these following inequalities:
1) $ (x\plus{}ky)(y\plus{}kx) \geq xy(k\plus{}1)^2$
2) $ (x\plus{}y\plus{}z)^2 \ge 3(xy\plus{}yz\plus{}zx)$

[quote="mornik"]
If $ x$, $ y$ and $ z$ are positive real numbers for which $ x \plus{} y \plus{} z \equal{} 1$, prove the inequality $ \frac {1}{\sqrt {x \plus{} y}} \plus{} \frac {1}{\sqrt {y \plus{} z}} \plus{} \frac {1}{\sqrt {z \plus{} x}} \leq \frac {1}{\sqrt {2xyz}}$.[/quote]
The following stronger inequality is true too.
Let $ x,$ $ y$ and $ z$ are positive numbers such that $ x\plus{}y\plus{}z\equal{}1.$ Prove that
\[ \frac {1}{\sqrt {x \plus{}y}} \plus{} \frac {1}{\sqrt {y \plus{} z}} \plus{} \frac {1}{\sqrt {z \plus{} x}} \leq\sqrt {\frac{4.5}{xy\plus{}xz\plus{}yz}}\]

[quote="matex (L)(L)(L)"]Is there any nice way to prove Your last inequality Arqady?[/quote]
I proved it by AM-GM only.

[quote="arqady"][quote="mornik"]
If $ x$, $ y$ and $ z$ are positive real numbers for which $ x \plus{} y \plus{} z \equal{} 1$, prove the inequality $ \frac {1}{\sqrt {x \plus{} y}} \plus{} \frac {1}{\sqrt {y \plus{} z}} \plus{} \frac {1}{\sqrt {z \plus{} x}} \leq \frac {1}{\sqrt {2xyz}}$.[/quote]
The following stronger inequality is true too.
Let $ x,$ $ y$ and $ z$ are positive numbers such that $ x \plus{} y \plus{} z \equal{} 1.$ Prove that
\[ \frac {1}{\sqrt {x \plus{} y}} \plus{} \frac {1}{\sqrt {y \plus{} z}} \plus{} \frac {1}{\sqrt {z \plus{} x}} \leq\sqrt {\frac {4.5}{xy \plus{} xz \plus{} yz}}
\]
[/quote]

We have
\[ \left( {\sum {\frac{1}{{\sqrt {x \plus{} y} }}} } \right)^2  \le \left( {\sum {\left( {x \plus{} z} \right)} } \right)\left( {\sum {\frac{1}{{\left( {x \plus{} y} \right)\left( {x \plus{} z} \right)}}} } \right) \equal{} \frac{{4\left( {x \plus{} y \plus{} z} \right)^2 }}{{\left( {x \plus{} y} \right)\left( {y \plus{} z} \right)\left( {z \plus{} x} \right)}}
\]
Hence it suffices to prove that
\[ \frac{{4\left( {x \plus{} y \plus{} z} \right)^2 }}{{\left( {x \plus{} y} \right)\left( {y \plus{} z} \right)\left( {z \plus{} x} \right)}} \le \frac{9}{{2\left( {xy \plus{} yz \plus{} zx} \right)}}
\]
\[ \Leftrightarrow 9\left( {x \plus{} y} \right)\left( {y \plus{} z} \right)\left( {z \plus{} x} \right) \ge 8\left( {xy \plus{} yz \plus{} zx} \right)
\]
which is true since
\[ \left( {x \plus{} y} \right)\left( {y \plus{} z} \right)\left( {z \plus{} x} \right) \ge \frac{8}{9}\left( {x \plus{} y \plus{} z} \right)\left( {xy \plus{} yz \plus{} zx} \right)
\]
:)

[quote="djuro"]Next time I create an inequality, I will ask arquady is there a stronger one :D

author[/quote]

When you read Arqady's posts, there always seems to be a stronger one, doesn't there?  :D

For the original inequality:

Let $ a\equal{}y\plus{}z,b\equal{}x\plus{}z,c\equal{}x\plus{}y$

AM-GM gives us $ abc\ge 8xyz$, so the RHS is always greater than or equal to $ \frac{2}{\sqrt{abc}}$

Now let's reduce the inequality to a common denominator, we have to prove: $ \sum_{cyclic} \sqrt{ab}\le 2$

Let $ p\equal{}\sqrt a,q\equal{}\sqrt b,r\equal{}\sqrt c$

$ \sum_{cyclic} pq\le 2$, but the condition is $ p^2\plus{}q^2\plus{}r^2\equal{}2$ so the inequality is obvious...


function
calculus
integration
calculus computations

let f(x) be a continuous function on [a,b] where a<c<b. If f(x)>0 when c<x<b and f(x)<0 when a<x<c
 :?:
then the integral from a to b of |f(x)| dx=?


trigonometry
algebra
polynomial
complex numbers

uhh the sum of the cosines doesn't equal $0$ but here we go:

[hide]

seeing this sum reminds us of the roots of unity

so given polynomial $x^n - 1 = (x-1)(x^{n-1} + x^{n-2} + \ldots + x + 1) = 0$, we first off know the sum of the roots of this are equal to $0$

hence, we have:

$1 + \sum_{i=1}^{n-1} \cos \frac{2\pi i}{n} + i \sum_{i=0}^{n-1} \sin \frac{2\pi i}{n} = 0$

since there is no imaginary part on the RHS, we know that $\sum_{i=0}^{n-1} \sin\frac{2\pi i}{n}$ (hence what we're trying to prove) must equal $0$

then we can also show the sum for the cosines, and since our whole sum is equal to $0$, we know that

$1 + \sum_{i=1}^{n-1} \cos \frac{2\pi i}{n} = 0$ and so the sum of the cosines equals $-1$

[/hide]

[quote="bthings_2000"]How can you show that for any positive integer $n$, where $n>1$,

$sin{\frac{2\pi}{n}}+sin{\frac{(2)2\pi}{n}}+sin{\frac{(3)2\pi}{n}}+...+sin{\frac{(n-1)2\pi}{n}}=0$?

And the same for cosine. Intuitively it seems obvious, but how to prove...[/quote]

gotztanhbeazn is right for cosine it's $-1$.

Another way of proving this is using the 'formula' for

$\sin a+\sin (2a)+...+\sin (na)$ and $\cos a+\cos(2a)+...+\cos(na)$.

For the sum of sine, the formula is
$\frac{\sin(\frac{na}{2})\sin(\frac{(n+1)a}{2})}{\sin(\frac{a}{2})}$.
For the sum of cosine, the formula is
$\frac{\sin(\frac{na}{2})\cos(\frac{(n+1)a}{2})}{\sin(\frac{a}{2})}$.

hmm ive nvr seen those formulas... do u think u can derive them for us?

I have a longer version of derivation which uses de Moivre's formula....

If u guys want to see it, I can type it...

You're all making this rather too complicated, I think.

Recall that $\sin \theta = - \sin (2\pi - \theta)$.  Gaussian pairing of the terms of the summation cancel them out.  :)  (Edit:  Incidentally, Gaussian pairing provides a decent proof of the general formula, although the proof by complex numbers is probably the best.)

[quote="kunny"]Use $\sin \alpha\cos \beta=\frac{1}{2}\{\sin (\alpha+\beta)+\sin (\alpha-\beta)\}$,

$\sum_{k=0}^n \sin \frac{\theta}{2}\cos k\theta=\frac{1}{2}\sum_{k=0}^n \left\{\sin \left(k+\frac{1}{2}\right)\theta -\sin \left(k-\frac{1}{2}\right)\theta \right\}$

$=\frac{1}{2} \left\{\sin \frac{\theta}{2}+\sin \left(n+\frac{1}{2}\right)\theta\right\}$

Use $\sin A+\sin B=2\sin \frac{A+B}{2}\cos \frac{A-B}{2}$

$=\sin \frac{n+1}{2}\theta \cos \frac{n}{2}\theta$

Divided by $\sin \frac{\theta}{2}\neq 0$ both sides,yielding the result.[/quote]
I didn't under stand the last sentence "Divided by $\sin \frac{\theta}{2}\neq 0$ both sides,yielding the result"
and how do I prove that $\sin\frac{k\cdot360}{n}+\sin\frac{(n-k+1)\cdot360(n-1)}{n}=0$? (Gaussian pairing) tnx  :)

$\sum_{k=0}^{n} \sin{\frac{\theta}{2}} \cos{k\theta} =\sin{\frac{\theta}{2}} \sum_{k=0}^{n} \cos{k\theta} =\sin{\frac{n+1}{2}\theta} \cos\frac{n}{2}\theta$, so dividing by $\sin\frac{\theta}{2}$ (constant) gives $\sum_{k=0}^n \cos{k\theta} =\frac{\sin{\frac{n+1}{2}\theta} \cos\frac{n}{2}\theta}{\sin\frac{\theta}{2}}$.

The problem with t0rajir0u's method is that it accounts for all cases with even $n$, but it does not work for cosine when $n$ is odd. Any remedies on the geometric tack?

[quote="bthings_2000"]but it does not work for cosine when $n$ is odd. [/quote]

It's not supposed to.  Cosine doesn't have the right symmetry.  I was only answering the sine case.  :)


A)Given that pi/12 is the first positive solution of (sqrt(3)-1)/sin(x) + (sqrt(3)+1)/cos(x) = 4 sqrt(2),
use the exact values of sin(pi/12) and cos(pi/12) to find the second.

B)What is the smallest positive angle which satisfies
8 sin(x) cos^5(x) - 8 sin^5(x) cos(x) = 1.

[quote="iamhe"]A)Given that $ \frac\pi{12}$ is the first positive solution of $ \frac {\sqrt3 \minus{} 1}{\sin x} \plus{} \frac {\sqrt3 \plus{} 1}{\cos x} \equal{} 4\sqrt2$,
use the exact values of $ \sin\left(\frac\pi{12}\right)$ and $ \cos\left(\frac\pi{12}\right)$ to find the second.

B)What is the smallest positive angle which satisfies
$ 8\sin x\cos^5 x \minus{} 8 \sin^5 x\cos x \equal{} 1$.[/quote]

Made prettier, and...
[hide="1"]
Multiply both sides by $ \sin x\cos x$ to get

$ (\sqrt3\plus{}1)\sin x\plus{}(\sqrt3\minus{}1)\cos x\equal{}2\sqrt2(2\sin x\cos x)\equal{}2\sqrt2\sin(2x)$.

The LHS can be expressed as $ K\sin(x\plus{}y)\equal{}K\sin x\cos y\plus{}K\sin y\cos x$, where

$ K\cos y\equal{}\sqrt3\plus{}1$ and $ K\sin y\equal{}\sqrt3\minus{}1$.

Squaring both equations and adding, we get

$ K^2(\sin^2 y\plus{}\cos^2 y)\equal{}K^2\equal{}4\plus{}2\sqrt3\plus{}4\minus{}2\sqrt3\equal{}8\implies K\equal{}2\sqrt2$.

Dividing both sides by $ K$ gives

$ \cos y\equal{}\frac{\sqrt6\plus{}\sqrt2}4\equal{}\cos\left(\frac\pi{12}\right)$ and

$ \sin y\equal{}\frac{\sqrt6\minus{}\sqrt2}4\equal{}\sin\left(\frac\pi{12}\right)$, so we can assume that

$ y\equal{}\frac\pi{12}$ ($ y\pm2n\pi$ would work as well, but this is the simplest way.)

Since we know that $ 2\sqrt2\sin(2x)\equal{}K\sin(x\plus{}y)\equal{}2\sqrt2\sin\left(x\plus{}\frac\pi{12}\right)\implies\sin(2x)\equal{}\sin\left(x\plus{}\frac\pi{12}\right)$, we can see that (if $ x\in[0,2\pi)$)

$ 2x\equal{}x\plus{}\frac\pi{12}\implies x\equal{}\frac\pi{12}$

$ \pi\minus{}2x\equal{}x\plus{}\frac\pi{12}\implies x\equal{}\boxed{\frac{11\pi}{12}}$

$ 3\pi\minus{}2x\equal{}x\plus{}\frac\pi{12}\implies x\equal{}\frac{35\pi}{36}$

$ 5\pi\minus{}2x\equal{}x\plus{}\frac\pi{12}\implies x\equal{}\frac{59\pi}{36}$

all provide unique solutions.
[/hide]
[hide="2"]
$ 8\sin x\cos x(\cos^2x \minus{} \sin^2x)(\sin^2x \plus{} \cos^2x) \equal{} 4\sin(2x)\cos(2x) \equal{} 2\sin(4x) \equal{} 1$

$ \implies\sin(4x) \equal{} \frac12\implies4x \equal{} \frac\pi6\implies x \equal{} \boxed{\frac\pi{24}}$.
[/hide]