Problem 65: IMO Shortlist 2015, G3

by henderson, May 7, 2017, 5:21 PM

$\color{red}\bf{Problem \ 65}$ Let $ABC$ be a triangle with $\angle{C} = 90^{\circ}$ , and let $H$ be the foot of the altitude from $C$ . A point $D$ is chosen inside the triangle $CBH$ so that $CH$ bisects $AD$ . Let $P$ be the intersection point of the lines $BD$ and $CH$ . Let $\omega$ be the semicircle with diameter $BD$ that meets the segment $CB$ at an interior point. A line through $P$ is tangent to $\omega$ at $Q$ . Prove that the lines $CQ$ and $AD$ meet on $\omega$ .
$\color{red}\bf{Solution}$ $[asy] unitsize(3cm); pointfontpen=fontsize(10); pointpen=black; pathpen=rgb(0.4,0.6,0.8); pair B=dir(0), A=-B, C=dir(110), H=foot(C,A,B), N=WP(D(C--H),0.85), D=2*N-A, P=extension(B,D,C,H), Q=tangent(P,(B+D)/2,length(B-D)/2,2), K=extension(A,D,C,Q), M=(B+D)/2; D(CR((0,0),1,0,180),heavygreen); D(arc(M,length(K-M),degrees(B-M),degrees(D-M),CCW),red); D(A--B--C--cycle,linewidth(1)+pathpen); DPA(D--B--Q--cycle^^Q--P--D^^H--C); D(C--K--A,dashed+pathpen); /*Angle marks and pathticks*/ markscalefactor=0.01; DPA(rightanglemark(B,C,A)^^rightanglemark(B,H,C)^^rightanglemark(B,Q,D)); /* Dot and label points */ D("A",A,W); D("B",B,E); D("C",C,dir(C)); D("D",D,SSE); D("H",H); D("K",K,dir(K)); D("P",P,dir(P)); D("Q",Q,dir(Q)); [/asy]$
Let $K=AD\cap CQ$ . We claim that $\triangle ABC\sim\triangle DBQ$ . Indeed, $\angle BCA=\angle BQD=90^{\circ}$ and since $\triangle PDQ\sim\triangle PQB$ and $CH$ bisects $\overline{AD}$ , $\frac{DQ^2}{BQ^2}=\frac{PQ^2}{PB^2}=\frac{PD}{PB}=\frac{AH}{BH}=\tan^2B=\frac{AC^2}{BC^2},$ and our claim holds. Thus $B$ is the center of the spiral similarity $\overline{AD}\to\overline{CQ}$ , so $\angle KDB=\angle KQB$ , and $K$ lies on $\omega$ .

This post has been edited 1 time. Last edited by henderson, Jul 3, 2017, 7:41 PM

Spiral Similarity

geometry

Problem 64: Integer functional equation

by henderson, Mar 30, 2017, 4:44 PM

$\color{red}\bf{Problem \ 64}$ Determine all functions $f:\mathbb{Z}\rightarrow\mathbb{Z}$ with the property that $f(x-f(y))=f(f(x))-f(y)-1$ holds for all $x,y\in\mathbb{Z}.$
(IMO Shortlist 2015, A2)

This post has been edited 1 time. Last edited by henderson, Mar 30, 2017, 4:46 PM

functional equation

Functional Equations

IMO Shortlist

Problem 63: Concurrent lines

by henderson, Mar 26, 2017, 12:23 PM

$\color{red}\bf{Problem \ 63}$ Let $O$ be the circumcenter of an acute $\triangle ABC.$ The points $E$ and $F$ are chosen on the lines $AB$ and $AC,$ respectively, such that $O$ is the midpoint of $EF.$ Let $D$ be the intersection point of $AO$ $($ other than $A$ $)$ with the circumcircle of $\triangle ABC.$ Prove that the lines $EF, BC$ and the tangent to the circumcircle of $\triangle ABC$ at $D$ are concurrent.
$\color{red}\bf{My \ solution}$ Denote by $l$ the tangent to the circumcircle of $\triangle ABC$ at $D$ and let $\{ S \}=BC \cap l.$ Applying the butterfly theorem to the degenerated quadrilateral $BDCD,$ we obtain that, if $m$ is the line passing through the point $S$ such that $m \perp OS,$ then the intersection points of $BD$ and $CD$ with the line $m$ have equal distances from the point $S.$ In other words, if $\{ E_2 \}=BD\cap m$ and $\{ F_2 \}=CD\cap m,$ then $SE_2=SF_2.$

$\color{blue}\textbf{Claim.}$ $\quad$ $\triangle DE_2F_2 \sim \triangle AEF.$

$\color{blue}\textbf{Proof.}$ $\quad$ Since $l$ is tangent to the circumcircle of $\triangle ABC,$ $\angle EAO=\angle E_2DS$ and $\angle FAO=\angle F_2DS$ hold. On the other hand, sines' law imply
$\frac{E_2D}{\sin \angle E_2SD}=\frac{E_2S}{\sin \angle E_2DS} \ \text{and} \ \frac{F_2D}{\sin \angle F_2SD}=\frac{F_2S}{\sin \angle F_2DS}$ $\Longrightarrow$

$\frac{E_2D}{F_2D}=\frac{\sin \angle F_2DS}{\sin \angle E_2DS}=\frac{\sin \angle FAO}{\sin \angle EAO} .$ Moreover, $\frac{EA}{FA}=\frac{\sin \angle FAO}{\sin \angle EAO}$ in $\triangle AEF.$
Thus, we obtain $\frac{E_2D}{F_2D}=\frac{EA}{FA}.$ Taking into account the fact that
$\angle E_2DF_2=\angle E_2DS+\angle F_2DS= \angle EAO+\angle FAO=\angle EAF,$ we conclude
$\triangle DE_2F_2 \sim \triangle AEF ,$ as desired. $\quad$ $\square$

Let $\{ E_1 \}=OS\cap AB.$ Since $\angle E_2SE_1=\angle E_2BE_1,$ the quadrilateral $E_2SBE_1$ is cyclic $\Longrightarrow$ $\angle SE_2B=\angle SE_1B.$ As $\angle SE_2B=\angle F_2E_2D=\angle FEA=\angle OEA,$ we obtain $\angle SE_1B=\angle OEA,$ which means that $E$ and $E_1$ coincide.
Therefore, the lines $l, BC$ and $EO$ are concurrent at the point $S$ $\Longrightarrow$ $l, BC$ and $EF$ are concurrent at the point $S.$ $\quad$ $\square$

This post has been edited 4 times. Last edited by henderson, Mar 30, 2017, 4:49 PM

butterfly theorem

geometry

concurrent lines

Problem 62: Sum of fractions

by henderson, Feb 1, 2017, 7:00 PM

https://artofproblemsolving.com/community/c6h1161621
https://en.m.wikipedia.org/wiki/Bertrand's_postulate
https://en.m.wikipedia.org/wiki/Harmonic_number
http://math.uga.edu/~pete/4400intro.pdf

This post has been edited 3 times. Last edited by henderson, Feb 3, 2017, 7:35 PM

Problem 61: Poland MO Finals 2003, Problem 3

by henderson, Jan 30, 2017, 8:04 PM

$\color{red}\bf{Problem \ 61}$ Find all polynomials $W$ with integer coefficients satisfying the following condition: For every natural number $n, 2^n - 1$ is divisible by $W(n).$

This post has been edited 1 time. Last edited by henderson, Jan 30, 2017, 8:05 PM

number theory

Justin Stevens

Poland MO

Problem 60:

by henderson, Jan 25, 2017, 6:06 PM

ghghghhghg

geometry

angle bisector

parallelogram

Problem 59: ELMO Shortlist 2012, G3

by henderson, Jan 21, 2017, 2:33 PM

$\color{red}\bf{Problem \ 59}$ $ABC$ is a triangle with incenter $I.$ The foot of the perpendicular from $I$ to $BC$ is $D,$ and the foot of the perpendicular from $I$ to $AD$ is $P.$ Prove that $\angle BPD = \angle DPC.$

Proposed by Alex Zhu
$\color{red}\bf{Solution}$ Let the incircle touch the sides $AB,AC$ at $E,F,$ respectively and let $X=EF \cap BC.$ Then $X$ lies on the polar of $A$ with respect to the incircle, so $A$ lies on the polar of $X.$ Thus $AD$ is the polar of $X.$ In particular, $IX \perp AD,$ so $\angle XPD=90^{\circ}.$ Since $AD,BE,CF$ are concurrent, $(B;C;D;X)=-1,$ and it is a well-known fact that the last two equalities imply $\angle BPD=\angle DPC.$

This post has been edited 4 times. Last edited by henderson, Jan 21, 2017, 3:20 PM

geometry

ELMO Shortlist

poles and polars

Problem 58: Iran 1996 inequality

by henderson, Jan 6, 2017, 3:21 PM

${\color{red}\bf{Problem \ 58}}$ Prove that, for all positive real numbers $a,b,c$
$(ab+bc+ca)\left(\frac{1}{(b+c)^2}+\frac{1}{(c+a)^2}+\frac{1}{(a+b)^2} \right)\geq \frac{9}{4}$ holds.
(Iran 1996)
${\color{red}\bf{Solution}}$ We may assume that $a\geq b \geq c.$ Firstly, let's show that
$\frac{1}{(b+c)^2}+\frac{1}{(c+a)^2}+\frac{1}{(a+b)^2}\geq \frac{1}{4ab}+\frac{2}{(a+c)(b+c)}.$ This can be rewritten as
$\left(\frac{1}{a+c}-\frac{1}{b+c}\right)^2\geq \frac{(a-b)^2}{4ab(a+b)^2},$ or equivalently $4ab(a+b)^2\geq (a+c)^2(b+c)^2.$ This is obvious, since $4ab\geq (b+c)^2$ and $(a+b)^2\geq (a+c)^2.$
Thus, it remains to prove that
$(ab+bc+ca)\left(\frac{1}{4ab}+\frac{2}{(a+c)(b+c)} \right)\geq \frac{9}{4}.$ Using the identities
$\frac{ab+bc+ca}{4ab}=\frac{1}{4}+\frac{c(a+b)}{4ab}, \quad \frac{2(ab+bc+ca)}{(a+c)(b+c)}=2 -\frac{2c^2}{(a+c)(b+c)},$ this becomes
$\frac{c(a+b)}{4ab}\geq \frac{2c^2}{(a+c)(b+c)}.$ But this is equivalent to
$(a+b)(b+c)(c+a)\geq 8abc,$ which is a simple consequence of $AM-GM.$ $\quad$ $\square$

This post has been edited 3 times. Last edited by henderson, Jan 6, 2017, 6:07 PM

Inequality

Iran 1996 inequality

Problem 57: Prime factorization

by henderson, Jan 4, 2017, 2:32 PM

${\color{red}\bf{Problem \ 57}}$ Prove that for every nonnegative integer $n,$ the number $7^{7^{n}}+1$ is the product of at least $2n+3$ (not necessarily distinct) primes.
(USAMO 2007)
${\color{red}\bf{Solution}}$ Let's apply induction.

$\boxed{\color{blue}{1}}$ The base case is $n=0,$ which is $8=2^3,$ so it has $2n+3$ prime factors.

$\boxed{\color{blue}{2}}$ Now, assume that $7^{7^{n}}+1$ is the product of $2n+3$ primes.

$\boxed{\color{blue}{3}}$ We wish to prove that $7^{7^{n+1}}+1$ is the product of $2(n+1)+3=2n+5$ primes.
Let $x = 7^{7^{n}}.$ $\quad$ $x+1$ is the product of $2n+3$ primes, so we want to show that $x^7+1$ is the product of $2n+5$ primes.

Note that $x^7+1 = (x+1)(x^6-x^5+x^4-x^3+x^2-x+1).$ By the inductive hypothesis, we know that $x+1$ is the product of $2n+3$ primes, so it suffices to show that $x^6-x^5+x^4-x^3+x^2-x+1$ is composite.

Since $x^6-x^5+x^4-x^3+x^2-x+1=(x+1)^6 - 7x(x^2+x+1)^2$ and $x=7^{7^{n}}$ , $x^6-x^5+x^4-x^3+x^2-x+1$ is the difference of two squares, therefore is composite.

Thus, $7^{7^{n+1}}+1$ is the product of at least $(2n+3)+2=2n+5$ primes, and we are done. $\square$

This post has been edited 4 times. Last edited by henderson, Jan 12, 2017, 11:11 AM

number theory

prime numbers

USAMO

Problem 56: Brazil MO 2013, Day 1, Problem 2

by henderson, Dec 16, 2016, 3:48 PM

${\color{red}\bf{Problem \ 56}}$ Arnaldo and Bernaldo play the following game: given a fixed finite set of positive integers $A$ known by both players, Arnaldo picks a number $a \in A$ but doesn't tell it to anyone. Bernaldo thens pick an arbitrary positive integer $b$ (not necessarily in $A$ ). Then Arnaldo tells the number of divisors of $ab$ . Show that Bernaldo can choose $b$ in a way that he can find out the number $a$ chosen by Arnaldo.
(Brazil MO 2013)
${\color{red}\bf{Solution}}$ Let us say the primes that divide at least one element from $A$ are $p_0,p_1,\ldots,p_k$ . An element $a\in A$ can be represented then as $a=\prod_{j=0}^k p_j^{\alpha_j}$ , with $\alpha_j \geq 0$ . When $b=\prod_{j=0}^k p_j^{\beta_j}$ , the number of divisors of $ab$ is $\tau(ab) = \prod_{j=0}^k (1+ \alpha_j + \beta_j)$ . Let us plug in $\beta_j = x^{2^j}$ ; then $P(x) = \prod_{j=0}^k (1+\alpha_j + x^{2^j})$ is a polynomial in $x$ of degree $2^{k+1} - 1$ , where the coefficient of $x^{2^{k+1} - 2^j - 1}$ is precisely $1+\alpha_j$ . In fact, if we take $n > \prod_{j=0}^k (1+\alpha_j)$ , then $P(n)$ is the writing in basis $n$ of some (huge) integer, and all "digits" can be determined, namely also the values $\alpha_j$ . So all is left to do is to take $n > \prod_{j=0}^k (1+a_j)$ , where $a_j = \max_{A} \alpha_j$ , and $\beta_j = n^{2^j}$ .