Home » 国际竞赛 » 数学国际竞赛 » AMC美国数学竞赛 » Details

2013 USAMO Problems真题及答案

Category: AMC美国数学竞赛, 国际竞赛 Date: 2019年8月13日下午12:09

2013 USAMO Problems真题及答案

完整版真题免费下载

+答案解析请参考文末

Day 1

Problem 1

In triangle $ABC$ , points $P,Q,R$ lie on sides $BC,CA,AB$ respectively. Let $omega_A$ , $omega_B$ , $omega_C$ denote the circumcircles of triangles $AQR$ , $BRP$ , $CPQ$ , respectively. Given the fact that segment $AP$ intersects $omega_A$ , $omega_B$ , $omega_C$ again at $X,Y,Z$ respectively, prove that $YX/XZ=BP/PC$ .

Problem 2

For a positive integer $ngeq 3$ plot $n$ equally spaced points around a circle. Label one of them $A$ , and place a marker at $A$ . One may move the marker forward in a clockwise direction to either the next point or the point after that. Hence there are a total of $2n$ distinct moves available; two from each point. Let $a_n$ count the number of ways to advance around the circle exactly twice, beginning and ending at $A$ , without repeating a move. Prove that $a_{n-1}+a_n=2^n$ for all $ngeq 4$ .

Problem 3

Let $n$ be a positive integer. There are $tfrac{n(n+1)}{2}$ marks, each with a black side and a white side, arranged into an equilateral triangle, with the biggest row containing $n$ marks. Initially, each mark has the black side up. An operation is to choose a line parallel to the sides of the triangle, and flipping all the marks on that line. A configuration is called admissible if it can be obtained from the initial configuration by performing a finite number of operations. For each admissible configuration $C$ , let $f(C)$ denote the smallest number of operations required to obtain $C$ from the initial configuration. Find the maximum value of $f(C)$ , where $C$ varies over all admissible configurations.

Day 2

Problem 4

Find all real numbers $x,y,zgeq 1$ satisfying $[min(sqrt{x+xyz},sqrt{y+xyz},sqrt{z+xyz})=sqrt{x-1}+sqrt{y-1}+sqrt{z-1}.]$

Problem 5

Given positive integers $m$ and $n$ , prove that there is a positive integer $c$ such that the numbers $cm$ and $cn$ have the same number of occurrences of each non-zero digit when written in base ten.

Problem 6

Let $ABC$ be a triangle. Find all points $P$ on segment $BC$ satisfying the following property: If $X$ and $Y$ are the intersections of line $PA$ with the common external tangent lines of the circumcircles of triangles $PAB$ and $PAC$ , then $[left(frac{PA}{XY}right)^2+frac{PBcdot PC}{ABcdot AC}=1.]$

2013USAMO真题参考答案及详解

Problem 1

Solution 1

$[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 = (-1.0, 3.0); pair B = (-3.0, -3.0); pair C = (4.0, -3.0); pair P = (-0.6698198198198195, -3.0); pair Q = (1.1406465288818244, 0.43122416534181074); pair R = (-1.6269590345062048, 1.119122896481385); path w_A = circumcircle(A,Q,R); path w_B = circumcircle(B,P,R); path w_C = circumcircle(P,Q,C); pair O_A = midpoint(relpoint(w_A, 0)--relpoint(w_A, 0.5)); pair O_B = midpoint(relpoint(w_B, 0)--relpoint(w_B, 0.5)); pair O_C = midpoint(relpoint(w_C, 0)--relpoint(w_C, 0.5)); pair X = (2)*(foot(O_A,A,P))-A; pair Y = (2)*(foot(O_B,A,P))-P; pair Z = (2)*(foot(O_C,A,P))-P; pair M = 2*foot(P,relpoint(O_B--O_C,0.5-10/lisf),relpoint(O_B--O_C,0.5+10/lisf))-P; pair D = (2)*(foot(O_B,X,M))-M; pair E = (2)*(foot(O_C,X,M))-M; /* Draw objects */ draw(A--B, rgb(0.6,0.6,0.0)); draw(B--C, rgb(0.6,0.6,0.0)); draw(C--A, rgb(0.6,0.6,0.0)); draw(w_A, rgb(0.4,0.4,0.0)); draw(w_B, rgb(0.4,0.4,0.0)); draw(w_C, rgb(0.4,0.4,0.0)); draw(A--P, rgb(0.0,0.2,0.4)); draw(D--E, rgb(0.0,0.2,0.4)); draw(P--D, rgb(0.0,0.2,0.4)); draw(P--E, rgb(0.0,0.2,0.4)); draw(P--M, rgb(0.4,0.2,0.0)); draw(R--M, rgb(0.4,0.2,0.0)); draw(Q--M, rgb(0.4,0.2,0.0)); draw(B--M, rgb(0.0,0.2,0.4)); draw(C--M, rgb(0.0,0.2,0.4)); draw((abs(dot(unit(M-P),unit(B-P))) < 1/2011) ? rightanglemark(M,P,B) : anglemark(M,P,B), rgb(0.0,0.8,0.8)); draw((abs(dot(unit(M-R),unit(A-R))) < 1/2011) ? rightanglemark(M,R,A) : anglemark(M,R,A), rgb(0.0,0.8,0.8)); draw((abs(dot(unit(M-X),unit(A-X))) < 1/2011) ? rightanglemark(M,X,A) : anglemark(M,X,A), rgb(0.0,0.8,0.8)); draw((abs(dot(unit(D-X),unit(P-X))) < 1/2011) ? rightanglemark(D,X,P) : anglemark(D,X,P), rgb(0.0,0.8,0.8)); /* Place dots on each point */ dot(A); dot(B); dot(C); dot(P); dot(Q); dot(R); dot(X); dot(Y); dot(Z); dot(M); dot(D); dot(E); /* Label points */ label("$A$", A, lsf * dir(110)); label("$B$", B, lsf * unit(B-M)); label("$C$", C, lsf * unit(C-M)); label("$P$", P, lsf * unit(P-M) * 1.8); label("$Q$", Q, lsf * dir(90) * 1.6); label("$R$", R, lsf * unit(R-M) * 2); label("$X$", X, lsf * dir(-60) * 2); label("$Y$", Y, lsf * dir(45)); label("$Z$", Z, lsf * dir(5)); label("$M$", M, lsf * dir(M-P)*2); label("$D$", D, lsf * dir(150)); label("$E$", E, lsf * dir(5));[/asy]$

In this solution, all lengths and angles are directed.

Firstly, it is easy to see by that $omega_A, omega_B, omega_C$ concur at a point $M$ . Let $XM$ meet $omega_B, omega_C$ again at $D$ and $E$ , respectively. Then by Power of a Point, we have $[XM cdot XE = XZ cdot XP quadtext{and}quad XM cdot XD = XY cdot XP]$ Thusly $[frac{XY}{XZ} = frac{XD}{XE}]$ But we claim that $triangle XDP sim triangle PBM$ . Indeed, $[measuredangle XDP = measuredangle MDP = measuredangle MBP = - measuredangle PBM]$ and $[measuredangle DXP = measuredangle MXY = measuredangle MXA = measuredangle MRA = 180^circ - measuredangle MRB = measuredangle MPB = -measuredangle BPM]$ Therefore, $frac{XD}{XP} = frac{PB}{PM}$ . Analogously we find that $frac{XE}{XP} = frac{PC}{PM}$ and we are done.

courtesy v_enhance

Solution 2

Diagram Refer to the Diagram link.

By Miquel's Theorem, there exists a point at which $omega_A, omega_B, omega_C$ intersect. We denote this point by $M.$ Now, we angle chase: $[angle YMX = 180^{circ} - angle YXM - angle XYM]$ $[= 180^{circ} - angle AXM - angle PYM]$ $[= left(180^{circ} - angle ARMright) - angle PRM]$ $[= angle BRM - angle PRM]$ $[= angle BRP = angle BMP.]$ In addition, we have $[angle ZMX = 180^{circ} - angle MZY - angle ZYM - angle YMX]$ $[= 180^{circ} - angle MZP - angle PYM - angle BMP]$ $[= 180^{circ} - angle MCP - angle PBM - angle BMP]$ $[= left(180^{circ} - angle PBM - angle BMPright) - angle MCP]$ $[= angle BPM - angle MCP]$ $[= 180^{circ} - angle MPC - angle MCP]$ $[= angle CMP.]$ Now, by the Ratio Lemma, we have $[frac{XY}{XZ} = frac{MY}{MZ} cdot frac{sin angle YMX}{sin angle ZMX}]$ $[= frac{sin angle YZM}{sin angle ZYM} cdot frac{sin angle BMP}{sin angle CMP}]$ (by the Law of Sines in $triangle MZY$ ) $[= frac{sin angle PZM}{sin angle PYM} cdot frac{sin angle BMP}{sin angle CMP}]$ $[= frac{sin angle PCM}{sin angle PBM} cdot frac{sin angle BMP}{sin angle CMP}]$ $[= frac{MB}{MC} cdot frac{sin angle BMP}{sin angle CMP}]$ (by the Law of Sines in $triangle MBC$ ) $[= frac{PB}{PC}]$ by the Ratio Lemma. The proof is complete.

Solution 3

Use directed angles modulo $pi$ .

Lemma. $angle{XRY} equiv angle{XQZ}.$

Proof. $[angle{XRY} equiv angle{XRA} - angle{YRA} equiv angle{XQA} + angle{YRB} equiv angle{XQA} + angle{CPY} = angle{XQA} + angle{AQZ} = angle{XQZ}.]$

Now, it follows that (now not using directed angles) $[frac{XY}{YZ} = frac{frac{XY}{sin angle{XRY}}}{frac{YZ}{sin angle{XQZ}}} = frac{frac{RY}{sin angle{RXY}}}{frac{QZ}{sin angle{QXZ}}} = frac{BP}{PC}]$ using the facts that $ARY$ and $APB$ , $AQZ$ and $APC$ are similar triangles, and that $frac{RA}{sin angle{RXA}} = frac{QA}{sin angle{QXA}}$ equals twice the circumradius of the circumcircle of $AQR$ .

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.

Problem 2

Solution 1

We label the points in clockwise order as $1$ , $2$ , $3$ , dots, $n$ , where point $A$ is the same as point $1$ . We start and end at point $1$ , and we must cross over it, either by visiting it again, or else by making the move from point $n$ to point $2$ . We interpret each of these cases in terms of tiling. In each move, we either move one or two points clockwise, so we can think of each move as a $1times 1$ or $1times 2$ tile. If the point $1$ is visited in the middle, then the first cycle around the circle can be thought of as a tiling of a $1times n$ board, and the second cycle around the circle can also be thought of as a $1times n$ board. We place this second board directly below the first board. Therefore, in this first case, we wish to find the number of tilings of two $1times n$ boards, and to guarantee that no move is repeated, we cannot have two tiles of the same type lying directly atop each other in the $2times n$ board. Suppose there are $u_n$ such tilings. It can easily be computed that $u_3=2$ and $u_4=6$ as shown below. $[asy] unitsize(10); draw((0,0)--(3,0)--(3,2)--(0,2)--cycle^^(0,1)--(3,1),linewidth(2)); draw((1,0)--(1,1)^^(2,1)--(2,2)); draw(shift((0,-2.5))*((0,0)--(3,0)--(3,2)--(0,2)--cycle^^(0,1)--(3,1)),linewidth(2)); draw(shift((0,-2.5))*((1,0)--(1,1)^^(2,1)--(2,2))); draw(shift((7,0))*((0,0)--(4,0)--(4,2)--(0,2)--cycle^^(0,1)--(4,1)),linewidth(2)); draw(shift((7,0))*((1,1)--(1,2)^^(2,0)--(2,2)^^(3,1)--(3,2))); draw(shift((7,-2.5))*((0,0)--(4,0)--(4,2)--(0,2)--cycle^^(0,1)--(4,1)),linewidth(2)); draw(shift((7,-2.5))*((1,0)--(1,1)^^(2,0)--(2,2)^^(3,1)--(3,2))); draw(shift((12,0))*((0,0)--(4,0)--(4,2)--(0,2)--cycle^^(0,1)--(4,1)),linewidth(2)); draw(shift((12,0))*((1,1)--(1,2)^^(2,0)--(2,1)^^(3,1)--(3,2))); draw(shift((12,-2.5))*((0,0)--(4,0)--(4,2)--(0,2)--cycle^^(0,1)--(4,1)),linewidth(2)); draw(shift((12,-2.5))*((1,1)--(1,2)^^(2,0)--(2,2)^^(3,0)--(3,1))); draw(shift((17,0))*((0,0)--(4,0)--(4,2)--(0,2)--cycle^^(0,1)--(4,1)),linewidth(2)); draw(shift((17,0))*((1,0)--(1,1)^^(2,1)--(2,2)^^(3,0)--(3,1))); draw(shift((17,-2.5))*((0,0)--(4,0)--(4,2)--(0,2)--cycle^^(0,1)--(4,1)),linewidth(2)); draw(shift((17,-2.5))*((1,0)--(1,1)^^(2,0)--(2,2)^^(3,0)--(3,1))); [/asy]$ In the second case, where we pass by point $1$ by moving from point $n$ to point $2$ , we can similarly think about it in terms of tiling two rows of $1times n$ boards, but we remove the last square in the first row and the first square in the second row to make sure that we jump from point $n$ to point $2$ . Suppose that we can tile such boards in $s_n$ ways. It can be easily computed that $s_3=3$ and $s_4=5$ as shown below. $[asy] unitsize(10); draw((1,0)--(3,0)--(3,1)--(2,1)--(2,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(2,1),linewidth(2)); draw(shift((0,-2.5))*((1,0)--(3,0)--(3,1)--(2,1)--(2,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(2,1)),linewidth(2)); draw(shift((0,-2.5))*((2,0)--(2,1))); draw(shift((4,0))*((1,0)--(3,0)--(3,1)--(2,1)--(2,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(2,1)),linewidth(2)); draw(shift((4,0))*((1,1)--(1,2))); draw(shift((11,0))*((1,0)--(4,0)--(4,1)--(3,1)--(3,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(3,1)),linewidth(2)); draw(shift((11,0))*((1,1)--(1,2)^^(2,1)--(2,2)^^(3,0)--(3,1))); draw(shift((11,-2.5))*((1,0)--(4,0)--(4,1)--(3,1)--(3,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(3,1)),linewidth(2)); draw(shift((11,-2.5))*((2,0)--(2,2))); draw(shift((16,0))*((1,0)--(4,0)--(4,1)--(3,1)--(3,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(3,1)),linewidth(2)); draw(shift((16,0))*((2,1)--(2,2)^^(3,0)--(3,1))); draw(shift((16,-2.5))*((1,0)--(4,0)--(4,1)--(3,1)--(3,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(3,1)),linewidth(2)); draw(shift((16,-2.5))*((1,1)--(1,2)^^(2,0)--(2,1)^^(3,0)--(3,1))); draw(shift((21,0))*((1,0)--(4,0)--(4,1)--(3,1)--(3,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(3,1)),linewidth(2)); draw(shift((21,0))*((1,1)--(1,2)^^(2,0)--(2,1))); [/asy]$ Since these are the only two possible cases, we see that $[a_n=u_n+s_ntag{1}.]$

For the sake of convenience in determining recurrence relations, we define another type of board with two $1times n$ boards where a specific corner is removed (without loss of generality, we place this in the lower left hand corner). Let $t_n$ be the number of ways to tile such a board without placeing two of the same type of tile atop each other. Once again, we compute that $t_3=3$ and $t_4=5$ as shown below. $[asy] unitsize(10); draw((1,0)--(3,0)--(3,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(3,1),linewidth(2)); draw((1,1)--(1,2)^^(2,0)--(2,1)); draw(shift((0,-2.5))*((1,0)--(3,0)--(3,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(3,1)),linewidth(2)); draw(shift((0,-2.5))*((1,1)--(1,2)^^(2,1)--(2,2))); draw(shift((4,0))*((1,0)--(3,0)--(3,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(3,1)),linewidth(2)); draw(shift((4,0))*((2,1)--(2,2))); draw(shift((11,0))*((1,0)--(4,0)--(4,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(4,1)),linewidth(2)); draw(shift((11,0))*((1,1)--(1,2)^^(2,1)--(2,2)^^(3,0)--(3,1))); draw(shift((11,-2.5))*((1,0)--(4,0)--(4,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(4,1)),linewidth(2)); draw(shift((11,-2.5))*((1,1)--(1,2)^^(2,0)--(2,1)^^(3,1)--(3,2))); draw(shift((16,0))*((1,0)--(4,0)--(4,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(4,1)),linewidth(2)); draw(shift((16,0))*((2,0)--(2,2)^^(3,1)--(3,2))); draw(shift((16,-2.5))*((1,0)--(4,0)--(4,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(4,1)),linewidth(2)); draw(shift((16,-2.5))*((2,1)--(2,2)^^(3,0)--(3,1))); draw(shift((21,0))*((1,0)--(4,0)--(4,2)--(0,2)--(0,1)--(1,1)--cycle^^(1,1)--(4,1)),linewidth(2)); draw(shift((21,0))*((2,0)--(2,2)^^(3,0)--(3,1))); [/asy]$ We can determine reccurence relations for $s_n$ , $t_n$ , and $u_n$ in terms of each other. For $s_n$ , note that a tiling can end in one of the three following ways such that the rest of the board can be tiled without restriction (the placed tiles are shaded). $[asy] path unitrect=(0,0)--(2,0)--(2,1)--(0,1)--cycle; unitsize(10); fill(shift((3,0))*unitsquare,mediumgray); draw(shift((0,0))*((0,0)--(4,0)--(4,1)--(0,1)^^(3,1)--(3,2)--(0,2)),linewidth(2)); draw(shift((0,0))*((3,0)--(3,1))); label("$dots$",(-1,1)); fill(shift((10,1))*unitsquare,mediumgray); fill(shift((10,0))*unitrect,mediumgray); draw(shift((8,0))*((0,0)--(4,0)--(4,1)--(0,1)^^(3,1)--(3,2)--(0,2)),linewidth(2)); draw(shift((8,0))*((2,0)--(2,2))); label("$dots$",(8-1,1)); fill(shift((18,0))*unitrect,mediumgray); fill(shift((17,1))*unitrect,mediumgray); draw(shift((16,0))*((0,0)--(4,0)--(4,1)--(0,1)^^(3,1)--(3,2)--(0,2)),linewidth(2)); draw(shift((16,0))*((2,0)--(2,1)^^(1,1)--(1,2))); label("$dots$",(16-1,1)); [/asy]$ In the first, second, and third cases, we see that we can tile the rest of the board in $t_{n-1}$ , $t_{n-2}$ , and $s_{n-2}$ ways, respectively. Hence for $nge 5$ , we see that $[s_n=t_{n-1}+t_{n-2}+s_{n-2}tag{2}.]$ For $t_n$ , note that a tiling can end in one of the three following ways such that the rest of the board can be tiled without restriction. $[asy] path unitrect=(0,0)--(2,0)--(2,1)--(0,1)--cycle; unitsize(10); filldraw(shift((3,0))*unitsquare,mediumgray); filldraw(shift((2,1))*unitrect,mediumgray); draw(shift((0,0))*((0,0)--(4,0)--(4,1)--(0,1)^^(4,1)--(4,2)--(0,2)),linewidth(2)); label("$dots$",(-1,1)); filldraw(shift((11,1))*unitsquare,mediumgray); filldraw(shift((10,0))*unitrect,mediumgray); filldraw(shift((9,1))*unitrect,mediumgray); draw(shift((8,0))*((0,0)--(4,0)--(4,1)--(0,1)^^(4,1)--(4,2)--(0,2)),linewidth(2)); label("$dots$",(8-1,1)); filldraw(shift((19,1))*unitsquare,mediumgray); filldraw(shift((18,1))*unitsquare,mediumgray); filldraw(shift((18,0))*unitrect,mediumgray); draw(shift((16,0))*((0,0)--(4,0)--(4,1)--(0,1)^^(4,1)--(4,2)--(0,2)),linewidth(2)); label("$dots$",(16-1,1)); [/asy]$ In the first, second, and third cases, we see that we can tile the rest of the board in $s_{n-1}$ , $s_{n-2}$ , and $t_{n-2}$ ways, respectively. Hence for $nge 5$ , we see that $[t_n=s_{n-1}+s_{n-2}+t_{n-2}tag{3}.]$ For $u_n$ , note that a tiling can end in one of the two following ways such that the rest of the board can be tiled without restriction. $[asy] path unitrect=(0,0)--(2,0)--(2,1)--(0,1)--cycle; unitsize(10); filldraw(shift((3,1))*unitsquare,mediumgray); filldraw(shift((2,0))*unitrect,mediumgray); draw(shift((0,0))*((0,0)--(4,0)--(4,1)--(0,1)^^(4,1)--(4,2)--(0,2)),linewidth(2)); label("$dots$",(-1,1)); filldraw(shift((11,0))*unitsquare,mediumgray); filldraw(shift((10,1))*unitrect,mediumgray); draw(shift((8,0))*((0,0)--(4,0)--(4,1)--(0,1)^^(4,1)--(4,2)--(0,2)),linewidth(2)); label("$dots$",(8-1,1)); [/asy]$

In either case, we are left with a board with a corner removed, hence we can tile the rest of the board in $t_{n-1}$ ways in each case. Hence for $nge 4$ , we see that $[u_n=2t_{n-1}tag{4}.]$ Subtracting (3) from (2), we find that $[s_n-t_n=s_{n-1}-t_{n-1}.]$ Therefore, if $s_{n-1}=t_{n-1}$ , then $s_n=t_n$ . Since $s_3=t_3$ and $s_4=t_4$ , we see that $s_n=t_n$ for all $nge 3$ . Therefore, (2) can be rewritten as $[s_n=s_{n-1}+2s_{n-2}tag{5},]$ and (4) can be rewritten as $[u_n=2s_{n-1}tag{6}.]$ Now by (1), we know that $[a_{n}+a_{n-1}=u_n+s_n+u_{n-1}+s_{n-1}.tag{7}]$ In particular, $a_4+a_3=6+5+2+3=2^4$ , so the statement is true for $n=4$ . Then by (7), and then substituting (5) and (6) (where these are valid for $nge 5$ ), we find $begin{align*} a_n+a_{n-1}&=u_n+s_n+u_{n-1}+s_{n-1}\ &=2s_{n-1}+(s_{n-1}+2s_{n-2})+u_{n-1}+s_{n-1}\ &=4s_{n-1}+2s_{n-2}+u_{n-1}.tag{8} end{align*}$ But then by (5), and then substituting $4s_{n-3}=2u_{n-2}$ and $2s_{n-2}=u_{n-1}$ (by (6), and these are valid for $nge 6$ ), we find $begin{align*} 2s_{n-1}&=2s_{n-2}+4s_{n-3}\ &=u_{n-1}+2u_{n-2}. end{align*}$ We substitute this into (8), finding that for $nge 6$ , $begin{align*} a_{n}+a_{n-1}&=2s_{n-1}+2s_{n-2}+u_{n-1}+(u_{n-1}+2u_{n-2})\ &=2(s_{n-1}+s_{n-2}+u_{n-1}+u_{n-2})\ &=2(a_{n-1}+a_{n-2}).tag{9} end{align*}$ Therefore, if $a_{n-1}+a_{n-2}=2^{n-1}$ , then $a_{n}+a_{n-1}=2^n$ . We already know that $a_4+a_3=2^4$ . Also, we can compute that $begin{align*} s_5&=s_4+2s_3=5+2cdot 3=11\ u_5&=2s_4=2cdot 5=10. end{align*}$ Hence $a_5=s_5+u_5=21$ . So as $a_4=s_4+u_4=11$ , we find that $a_5+a_4=2^5$ . Then we can use (9) for $nge 6$ to find by induction that $a_{n}+a_{n-1}=2^n$ for all $nge 4$ .

Solution 2

We choose the tilings for the first and second pass around the circle simultaneously. As we tile both passes, our state is defined by whether or not we are in a continuation of a length 2 block on the first and second pass. We can't be in a continuation of a length 2 block on both passes, since that would mean we used the same move on the same block on both passes. Thus we have three states: (non-continuation, non-continuation), (non-continuation, continuation), and (continuation, non-continuation), where the elements of each tuple refer to the first and second pass respectively. Listing out the state transitions (while following the rule that we can't use the same move on both passes, and that a continuation must become a non-continuation), we get the transition matrix $T = begin{bmatrix} 0 & 1 & 1 \ 1 & 0 & 1 \ 1 & 1 & 0 end{bmatrix} = J-I$ , where $J$ is the ones matrix, and $I$ is the identity. We have that $a_n = left(T^nright)_{11} + left(T^nright)_{23}$ . The first term represents the case where we end the first pass at point $A$ , and the second term represents the case where we jump over point $A$ when finishing the first pass. Thus it simply remains to compute $T^n$ . We have $T^n = (J-I)^n = sum_{k=0}^n J^k (-1)^{n-k} {n choose k} = J sum_{k=1}^n 3^{k-1} (-1)^{n-k} {n choose k} + (-1)^n I = frac{1}{3}Jleft(2^n-(-1)^nright) + (-1)^n I$ . Thus $a_n = left(T^nright)_{11} + left(T^nright)_{23} = frac{2}{3}left(2^n-(-1)^nright) + (-1)^n$ . Thus, $a_{n-1}+a_n = 2^n$ , as desired.

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.

Problem 3

暂无官方Solutions，可联系翰林导师进行详解。欢迎点击联系我们资讯翰林顾问！

Problem 4

Solution (Cauchy or AM-GM)

The key Lemma is: $[sqrt{a-1}+sqrt{b-1} le sqrt{ab}]$ for all $a,b ge 1$ . Equality holds when $(a-1)(b-1)=1$ .

This is proven easily. $[sqrt{a-1}+sqrt{b-1} = sqrt{a-1}sqrt{1}+sqrt{1}sqrt{b-1} le sqrt{(a-1+1)(b-1+1)} = sqrt{ab}]$ by Cauchy. Equality then holds when $a-1 =frac{1}{b-1} implies (a-1)(b-1) = 1$ .

Now assume that $x = min(x,y,z)$ . Now note that, by the Lemma,

$[sqrt{x-1}+sqrt{y-1}+sqrt{z-1} le sqrt{x-1} + sqrt{yz} le sqrt{x(yz+1)} = sqrt{xyz+x}]$ . So equality must hold. So $(y-1)(z-1) = 1$ and $(x-1)(yz) = 1$ . If we let $z = c$ , then we can easily compute that $y = frac{c}{c-1}, x = frac{c^2+c-1}{c^2}$ . Now it remains to check that $x le y, z$ .

But by easy computations, $x = frac{c^2+c-1}{c^2} le c = z Longleftrightarrow (c^2-1)(c-1) ge 0$ , which is obvious. Also $x = frac{c^2+c-1}{c^2} le frac{c}{c-1} = y Longleftrightarrow 2c ge 1$ , which is obvious, since $c ge 1$ .

So all solutions are of the form $boxed{left(frac{c^2+c-1}{c^2}, frac{c}{c-1}, cright)}$ , and all permutations for $c > 1$ .

Remark: An alternative proof of the key Lemma is the following: By AM-GM, $[(ab-a-b+1)+1 = (a-1)(b-1) + 1 ge 2sqrt{(a-1)(b-1)}]$ $[abge (a-1)+(b-1)+2sqrt{(a-1)(b-1)}]$ . Now taking the square root of both sides gives the desired. Equality holds when $(a-1)(b-1) = 1$ .

Solution with Thought Process

Without loss of generality, let $1 le x le y le z$ . Then $sqrt{x + xyz} = sqrt{x - 1} + sqrt{y - 1} + sqrt{z - 1}$ .

Suppose x = y = z. Then $sqrt{x + x^3} = 3sqrt{x-1}$ , so $x + x^3 = 9x - 9$ . It is easily verified that $x^3 - 8x + 9 = 0$ has no solution in positive numbers greater than 1. Thus, $sqrt{x + xyz} ge sqrt{x - 1} + sqrt{y - 1} + sqrt{z - 1}$ for x = y = z. We suspect if the inequality always holds.

Let x = 1. Then we have $sqrt{1 + yz} ge sqrt{y-1} + sqrt{z-1}$ , which simplifies to $[1 + yz ge y + z - 2 + 2sqrt{(y-1)(z-1)}]$ and hence $[yz - y - z + 3 ge 2sqrt{(y-1)(z-1)}]$ Let us try a few examples: if y = z = 2, we have $3 > 2$ ; if y = z, we have $y^2 - 2y + 3 ge 2(y-1)$ , which reduces to $y^2 - 4y + 5 ge 0$ . The discriminant (16 - 20) is negative, so in fact the inequality is strict. Now notice that yz - y - z + 3 = (y-1)(z-1) + 2. Now we see we can let $u = sqrt{(y-1)(z-1)}$ ! Thus, $[u^2 - 2u + 2 = (u-1)^2 + 1 > 0]$ and the claim holds for x = 1.

If x > 1, we see the $sqrt{x - 1}$ will provide a huge obstacle when squaring. But, using the identity $(x+y+z)^2 = x^2 + y^2 + z^2 + xy + yz + xz$ : $[x + xyz ge x - 1 + y - 1 + z - 1 + 2sqrt{(x-1)(y-1)} + 2sqrt{(y-1)(z-1)} + 2sqrt{(x-1)(y-1)}]$ which leads to $[xyz ge y + z - 3 + 2sqrt{(x-1)(y-1)} + 2sqrt{(y-1)(z-1)} + 2sqrt{(x-1)(z-1)}]$ Again, we experiment. If x = 2, y = 3, and z = 3, then $18 > 7 + 4sqrt{6}$ .

Now, we see the finish: setting $u = sqrt{x-1}$ gives $x = u^2 + 1$ . We can solve a quadratic in u! Because this problem is a #6, the crown jewel of USAJMO problems, we do not hesitate in computing the messy computations: $[u^2(yz) - u(2sqrt{y-1} + 2sqrt{z-1}) + (3 + yz - y - z - 2sqrt{(y-1)(z-1)}) ge 0]$

Because the coefficient of $u^2$ is positive, all we need to do is to verify that the discriminant is nonpositive: $[b^2 - 4ac = 4(y-1) + 4(z-1) - 8sqrt{(y-1)(z-1)} - yz(12 + 4yz - 4y - 4z - 8sqrt{(y-1)(z-1)})]$

Let us try a few examples. If y = z, then the discriminant D = $8(y-1) - 8(y-1) - yz(12 + 4y^2 - 8y - 8(y-1)) = -yz(4y^2 - 16y + 20) = -4yz(y^2 - 4y + 5) < 0$ .

We are almost done, but we need to find the correct argument. (How frustrating!) Success! The discriminant is negative. Thus, we can replace our claim with a strict one, and there are no real solutions to the original equation in the hypothesis.

--Thinking Process by suli

Solution 2

WLOG, assume that $x = min(x,y,z)$ . Let $a=sqrt{x-1},$ $b=sqrt{y-1}$ and $c=sqrt{z-1}$ . Then $x=a^2+1$ , $y=b^2+1$ and $z=c^2+1$ . The equation becomes $[(a^2+1)+(a^2+1)(b^2+1)(c^2+1)=(a+b+c)^2.]$ Rearranging the terms, we have $[(1+a^2)(bc-1)^2+[a(b+c)-1]^2=0.]$ Therefore $bc=1$ and $a(b+c)=1.$ Express $a$ and $b$ in terms of $c$ , we have $a=frac{c}{c^2+1}$ and $b=frac{1}{c}.$ Easy to check that $a$ is the smallest among $a$ , $b$ and $c.$ Then $x=frac{c^4+3c^2+1}{(c^2+1)^2}$ , $y=frac{c^2+1}{c^2}$ and $z=c^2+1.$ Let $c^2=t$ , we have the solutions for $(x,y,z)$ as follows: $(frac{t^2+3t+1}{(t+1)^2}, frac{t+1}{t}, t+1)$ and permutations for all $t>0.$

--J.Z.

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.

Problem 5

Solution

This solution is adopted from the official solution. Both the problem and the solution were suggested by Richard Stong.

WLOG, suppose $m geq n geq 1$ . By prime factorization of $n$ , we can find a positive integer $c_1$ such that $c_1n=10^s n_1$ where $n_1$ is relatively prime to $10$ . If a positive $k$ is larger than $s$ , then $(10^k c_1 m - c_1 n)= 10^s t$ , where $t=10^{k-s} c_1m-n_1>0$ is always relatively prime to $10$ . Choose a $k$ large enough so that $t$ is larger than $c_1m$ . We can find an integer $bgeq 1$ such that $10^b-1$ is divisible by $t$ , and also larger than $10c_1m$ . For example, let $b=phi(t)$ and use Euler's theorem. Now, let $c_2=(10^b-1)/t$ , and $c=c_1c_2$ . We claim that $c$ is the desired number.

Indeed, since both $c_1m$ and $n_1$ are less than $t$ , we see that the decimal expansion of both the fraction $(c_1m)/t = (cm)/(c_2t) = (cm)/(10^b-1)$ and $n_1/t=(c_2n_1)/(10^b-1)$ are repeated in $b$ -digit. And we also see that $10^k (c_1m)/t = (t+c_1n)/t= 1+10^s (n_1/t)$ , therefore the two repeated $b$ -digit expansions are cyclic shift of one another. This proves that $cm$ and $c_2n_1$ have the same number of occurrences of non-zero digits. Furthermore, $cn = c_2c_1n=10^s c_2n_1$ also have the same number of occurrences of non-zero digits with $c_2n_1$ .

Problem 6

Solution

Let circle $PAB$ (i.e. the circumcircle of $PAB$ ), $PAC$ be $omega_1, omega_2$ with radii $r_1$ , $r_2$ and centers $O_1, O_2$ , respectively, and $d$ be the distance between their centers.

Lemma. $XY = frac{r_1 + r_2}{d} sqrt{d^2 - (r_1 - r_2)^2}.$

Proof. Let the external tangent containing $X$ meet $omega_1$ at $X_1$ and $omega_2$ at $X_2$ , and let the external tangent containing $Y$ meet $omega_1$ at $Y_1$ and $omega_2$ at $Y_2$ . Then clearly $X_1 Y_1$ and $X_2 Y_2$ are parallel (for they are both perpendicular $O_1 O_2$ ), and so $X_1 Y_1 Y_2 X_2$ is a trapezoid.

Now, $X_1 X^2 = XA cdot XP = X_2 X^2$ by Power of a Point, and so $X$ is the midpoint of $X_1 X_2$ . Similarly, $Y$ is the midpoint of $Y_1 Y_2$ . Hence, $XY = frac{1}{2} (X_1 Y_1 + X_2 Y_2).$ Let $X_1 Y_1$ , $X_2 Y_2$ meet $O_1 O_2$ s at $Z_1, Z_2$ , respectively. Then by similar triangles and the Pythagorean Theorem we deduce that $X_1 Z_1 = frac{r_1 sqrt{d^2 - (r_1 - r_2)^2}}{d}$ and $frac{r_2 sqrt{d^2 - (r_1 - r_2)^2}}{d}$ . But it is clear that $Z_1$ , $Z_2$ is the midpoint of $X_1 Y_1$ , $X_2 Y_2$ , respectively, so $XY = frac{(r_1 + r_2)}{d} sqrt{d^2 - (r_1 - r_2)^2},$ as desired.

Lemma 2. Triangles $O_1 A O_2$ and $BAC$ are similar.

Proof. $angle{AO_1 O_2} = frac{angle{PO_1 A}}{2} = angle{ABC}$ and similarly $angle{AO_2 O_1} = angle{ACB}$ , so the triangles are similar by AA Similarity.

Also, let $O_1 O_2$ intersect $AP$ at $Z$ . Then obviously $Z$ is the midpoint of $AP$ and $AZ$ is an altitude of triangle $A O_1 O_2$ .Thus, we can simplify our expression of $XY$ : $[XY = frac{AB + AC}{BC} cdot frac{AP}{2 h_a} sqrt{BC^2 - (AB - AC)^2},]$ where $h_a$ is the length of the altitude from $A$ in triangle $ABC$ . Hence, substituting into our condition and using $AB = c, BC = a, CA = b$ gives $[left( frac{2a h_a}{(b+c) sqrt{a^2 - (b-c)^2}} right)^2 + frac{PB cdot PC}{bc} = 1.]$ Using $2 a h_a = 4[ABC] = sqrt{(a + b + c)(a + b - c)(a - b + c)(-a + b + c)}$ by Heron's Formula (where $[ABC]$ is the area of triangle $ABC$ , our condition becomes $[frac{(a + b + c)(-a + b + c)}{(b + c)^2} + frac{PB cdot PC}{bc} = 1,]$ which by $(a + b + c)(-a + b + c) = (b + c)^2 - a^2$ becomes $[frac{PB cdot PC}{bc} = frac{a^2 bc}{(b+c)^2}.]$ Let $PB = x$ ; then $PC = a - x$ . The quadratic in $x$ is $[x^2 - ax + frac{a^2 bc}{(b+c)^2} = 0,]$ which factors as $[(x - frac{ab}{b+c})(x - frac{ac}{b+c}) = 0.]$ Hence, $PB = frac{ab}{b+c}$ or $frac{ac}{b+c}$ , and so the $P$ corresponding to these lengths are our answer. The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.