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

2017 USAJMO Problems真题及答案

Category: AMC美国数学竞赛, 国际竞赛 Date: 2019年8月13日上午11:25

2017 USAJMO Problems真题及答案

完整版真题免费下载

+答案解析请参考文末

Day 1

Note: For any geometry problem whose statement begins with an asterisk ( $*$ ), the first page of the solution must be a large, in-scale, clearly labeled diagram. Failure to meet this requirement will result in an automatic 1-point deduction.

Problem 1

Prove that there are infinitely many distinct pairs? $(a,b)$ ?of relatively prime positive integers? $a > 1$ ?and? $b > 1$ ?such that? $a^b + b^a$ ?is divisible by? $a + b.$

Problem 2

Consider the equation $\left(3x^3 + xy^2 \right) \left(x^2y + 3y^3 \right) = (x-y)^7.$

(a) Prove that there are infinitely many pairs? $(x,y)$ ?of positive integers satisfying the equation.

(b) Describe all pairs? $(x,y)$ ?of positive integers satisfying the equation.

Problem 3

( $*$ ) Let? $ABC$ ?be an equilateral triangle and let? $P$ ?be a point on its circumcircle. Let lines? $PA$ ?and? $BC$ ?intersect at? $D$ ; let lines? $PB$ ?and? $CA$ intersect at? $E$ ; and let lines? $PC$ ?and? $AB$ ?intersect at? $F$ . Prove that the area of triangle? $DEF$ ?is twice the area of triangle? $ABC$ .

Day 2

Problem 4

Are there any triples? $(a,b,c)$ ?of positive integers such that? $(a-2)(b-2)(c-2) + 12$ ?is a prime that properly divides the positive number? $a^2 + b^2 + c^2 + abc - 2017$ ?

Problem 5

( $*$ ) Let? $O$ ?and? $H$ ?be the circumcenter and the orthocenter of an acute triangle? $ABC$ . Points? $M$ ?and? $D$ ?lie on side? $BC$ ?such that? $BM = CM$ and? $\angle BAD = \angle CAD$ . Ray? $MO$ ?intersects the circumcircle of triangle? $BHC$ ?in point? $N$ . Prove that? $\angle ADO = \angle HAN$ .

Problem 6

Let? $P_1, \ldots, P_{2n}$ ?be? $2n$ ?distinct points on the unit circle? $x^2 + y^2 = 1$ ?other than? $(1,0)$ . Each point is colored either red or blue, with exactly? $n$ of them red and exactly? $n$ ?of them blue. Let? $R_1, \ldots, R_n$ ?be any ordering of the red points. Let? $B_1$ ?be the nearest blue point to? $R_1$ ?traveling counterclockwise around the circle starting from? $R_1$ . Then let? $B_2$ ?be the nearest of the remaining blue points to? $R_2$ ?traveling counterclockwise around the circle from? $R_2$ , and so on, until we have labeled all the blue points? $B_1, \ldots, B_n$ . Show that the number of counterclockwise arcs of the form? $R_i \rightarrow B_i$ ?that contain the point? $(1,0)$ ?is independent of the way we chose the ordering? $R_1, \ldots, R_n$ ?of the red points.

Problem 1

Solution 1

Let? $a = 2n-1$ ?and? $b = 2n+1$ . We see that? $(2n \pm 1)^2 = 4n^2\pm4n+1 \equiv 1 \pmod{4n}$ . Therefore, we have? $(2n+1)^{2n-1} + (2n-1)^{2n+1} \equiv 2n + 1 + 2n - 1 = 4n \equiv 0 \pmod{4n}$ , as desired.

Solution 2

Let? $x$ ?be odd where? $x>1$ . We have? $x^2-1=(x-1)(x+1),$ ?so? $x^2-1 \equiv 0 \pmod{2x+2}.$ ?This means that $x^{x+2}-x^x \equiv 0 \pmod{2x+2},$ ?and since x is odd,? $x^{x+2}+(-x)^x \equiv 0 \pmod{2x+2},$ ?or? $x^{x+2}+(x+2)^x \equiv 0 \pmod{2x+2},$ ?as desired.

Solution 3

Because problems such as this usually are related to expressions along the lines of? $x\pm1$ , it's tempting to try these. After a few cases, we see that? $\left(a,b\right)=\left(2x-1,2x+1\right)$ ?is convenient due to the repeated occurrence of? $4x$ ?when squared and added. We rewrite the given expressions as: $\left(2x-1\right)^{2x+1}+\left(2x+1\right)^{2x-1}, \left(2x-1\right)+\left(2x+1\right)=4x.$ After repeatedly factoring the initial equation,we can get: $\left(2x-1\right)^{2}\left(2x-1\right)^{2}...\left(2x-1\right)+\left(2x+1\right)^{2}\left(2x+1\right)^{2}\left(2x+1\right)^{2}...\left(2x+1\right).$ Expanding each of the squares, we can compute each product independently then sum them: $\left(4x^{2}-4x+1\right)\left(4x^{2}-4x+1\right)...\left(2x-1\right)\equiv\left(1\right)\left(1\right)...\left(2x-1\right)\equiv2x-1\mod{4x},$ $\left(4x^{2}+4x+1\right)\left(4x^{2}+4x+1\right)...\left(2x+1\right)\equiv\left(1\right)\left(1\right)...\left(2x+1\right)\equiv2x+1\mod{4x}.$ Now we place the values back into the expression: $\left(2x-1\right)^{2x+1}+\left(2x+1\right)^{2x-1}\equiv\left(2x-1\right)+\left(2x+1\right)\equiv0\mod{4x}.$ Plugging any positive integer value for? $x$ ?into? $\left(a,b\right)=\left(2x-1,2x+1\right)$ ?yields a valid solution, because there is an infinite number of positive integers, there is an infinite number of distinct pairs? $\left(a,b\right)$ .

Problem 2

Solution 1

We have? $(3x^3+xy^2)(yx^2+3y^3)=(x-y)^7$ , which can be expressed as? $xy(3x^2+y^2)(x^2+3y^2)=(x-y)^7$ . At this point, we

think of substitution. A substitution of form? $a=x+y, b=x-y$ ?is slightly derailed by the leftover x and y terms, so

instead, seeing the xy in front, we substitute? $x=a+b, y=a-b$ . This leaves us with? $(a^2-b^2)(4a^2+4ab+4b^2)(4a^2- 4ab+4b^2)=128b^7$ , so? $(a^2-b^2)(a^2+ab+b^2)(a^2-ab+b^2)=8b^7$ . Expanding yields? $a^6-b^6=8b^7$ . Rearranging, we have

$b^6(8b+1)=a^6$ . To satisfy this equation in integers,? $8b+1$ ?must obviously be a? $6th$ ?power, and further inspection shows

that it must also be odd. Also, since it is a square and all odd squares are 1 mod 8, every odd sixth power gives a

solution. Since the problem asks for positive integers, the pair? $(a,b)=(0,0)$ ?does not work. We go to the next highest odd

$6th$ ?power,? $3^6$ ?or? $729$ . In this case,? $b=91$ , so the LHS is? $91^6\cdot3^6=273^6$ , so? $a=273$ . Using the original

substitution yields? $(x,y)=(364,182)$ ?as the first solution. We have shown part a by showing that there are an infinite

number of positive integer solutions for? $(a,b)$ , which can then be manipulated into solutions for? $(x,y)$ . To solve part

b, we look back at the original method of generating solutions. Define? $a_n$ ?and? $b_n$ ?to be the pair representing the nth

solution. Since the nth odd number is? $2n+1$ ,? $b_n=\frac{(2n+1)^6-1}{8}$ . It follows that? $a_n=(2n+1)b_n=\frac{(2n+1)^7- (2n+1)}{8}$ . From our original substitution,? $(x,y)=\left(\frac{(2n+1)^7+(2n+1)^6-2n-2}{8}, \frac{(2n+1)^7-(2n+1)^6-2n} {8}\right)$ .

Solution 2 (and motivation)

First, we shall prove a lemma:

LEMMA:

$\left(3x^3 + xy^2 \right) \left(x^2y + 3y^3 \right) = \frac{(x+y)^6-(x-y)^6}{4}$ PROOF: Expanding and simplifying the right side, we find that $\frac{(x+y)^6-(x-y)^6}{4}=\frac{12x^5y+40x^3y^3+12xy^5}{4}$ $=3x^5y+10x^3y^3+3xy^5$ $=\left(3x^3 + xy^2 \right) \left(x^2y + 3y^3 \right)$ which proves our lemma.

Now, we have that $\frac{(x+y)^6-(x-y)^6}{4}=(x-y)^7$ Rearranging and getting rid of the denominator, we have that $(x+y)^6=4(x-y)^7+(x-y)^6$ Factoring, we have $(x+y)^6=(x-y)^6(4(x-y)+1)$ Dividing both sides, we have $\left(\frac{x+y}{x-y}\right)^6=4x-4y+1$ Now, since the LHS is the 6th power of a rational number, and the RHS is an integer, the RHS must be a perfect 6th power. Define? $a=\frac{x+y}{x-y}$ . By inspection,? $a$ ?must be a positive odd integer satistisfying? $a \geq 3$ . We also have $a^6=4x-4y+1$ Now, we can solve for? $x$ ?and? $y$ ?in terms of? $a$ :? $x-y=\frac{a^6-1}{4}$ ?and? $x+y=a(x-y)=\frac{a(a^6-1)}{4}$ . Now we have: $(x,y)=\left(\frac{(a+1)(a^6-1)}{8},\frac{(a-1)(a^6-1)}{8}\right)$ and it is trivial to check that this parameterization works for all such? $a$ ?(to keep? $x$ ?and? $y$ ?integral), which implies part (a).

MOTIVATION FOR LEMMA: I expanded the LHS, noticed the coefficients were? $(3,10,3)$ , and immediately thought of binomial coefficients. Looking at Pascal's triangle, it was then easy to find and prove the lemma.

-sunfishho

Solution? $(1.5, x)$ ?where? $|x|>0$

So named because it is a mix of solutions 1 and 2 but differs in other aspects. After fruitless searching, let? $x+y=a$ ,? $x-y=b$ . Clearly? $a, b > 0$ . Then? $x=\frac{a+b}{2}, y=\frac{a-b}{2}, x^2+y^2=\frac{a^2+b^2}{2}, x^2=\frac{a^2+2ab+b^2}{4}, y^2=\frac{a^2-2ab+b^2}{4}, xy=\frac{a^2-b^2}{4}$ .

Change the LHS to? $xy(3x^2+y^2)(x^2+3y^2)=(a-b)(a+b)(a^2+ab+b^2)(a^2-ab+b^2)*\frac{1}{4}=(a^3-b^3)(a^3+b^3)*\frac{1}{4}=(a^6-b^6)*\frac{1}{4}$ . Change the RHS to? $b^7$ . Therefore? $(\frac{a})^6=4b+1$ . Let? $n=\frac{a}$ , and note that? $n$ ?is an integer. Therefore? $a=n(\frac{n^6-1}{4}), b=\frac{n^6-1}{4}$ . Because? $n^6 \equiv 1 (\mod{4})$ ,? $n$ ?is odd and? $>1$ ?because? $b>0$ . Therefore, substituting for? $x$ ?and? $y$ ?we get:? $x=\frac{(n^4+n^2+1)(n-1)(n+1)^2}{8}, y=\frac{(n+1)(n-1)^2(n^4+n^2+1)}{8}$ .

Problem 3

WLOG, let? $AB = 1$ . Let? $[ABD] = X, [ACD] = Y$ , and? $\angle BAD = \theta$ . After some angle chasing, we find that? $\angle BCF \cong \angle BEC \cong \theta$ ?and? $\angle FBC \cong \angle BCE \cong 120^{\circ}$ . Therefore,? $\triangle FBC$ ?~? $\triangle BCE$ .

Lemma 1: If $BF = k$ , then? $CE = \frac 1k$ . This lemma results directly from the fact that? $\triangle FBC$ ?~? $\triangle BCE$ ;? $\frac{BF}{BC} = \frac{BF}{1} = \frac{BC}{CE} = \frac{1}{CE}$ , or? $CE = \frac{1}{BF}$ .

Lemma 2: $[AEF] = (k+\frac 1k + 2)(X+Y)$ . We see that? $[AEF] = (X+Y) \frac{[AEF]}{[ABC]} = (k+1)(1+\frac 1k)(X+Y) = (k + \frac 1k + 2)(X+Y)$ , as desired.

Lemma 3: $\frac{X}{Y} = k$ . We see that $\frac XY = \frac{\frac 12 (AB)(AD) \sin(\theta)}{\frac 12 (AC)(AD) \sin (60^{\circ} - \theta)} = \frac{\sin(\theta)}{\sin (60^{\circ} - \theta)}.$ However, after some angle chasing and by the Law of Sines in? $\triangle BCF$ , we have? $\frac{k}{\sin(\theta)} = \frac{1}{\sin(60^{\circ} - \theta)}$ , or? $k = \frac{\sin(\theta)}{\sin (60^{\circ} - \theta)}$ , which implies the result.

By the area lemma, we have $[BDF] = kX$ ?and? $[CDF] = \frac{Y}{k}$ .

We see that? $[DEF] = [AEF] - [ABC] - [BDF] - [DCE] = Xk + Yk + \frac Xk + \frac Yk + 2X + 2Y - X - Y - Xk - \frac Yk = X + Y + \frac Xk + yk$ . Thus, it suffices to show that? $X + Y + \frac Xk + Yk = 2X + 2Y$ , or? $\frac Xk + Yk = X + Y$ . Rearranging, we find this to be equivalent to? $\frac XY = k$ , which is Lemma 3, so the result has been proven.

Solution 2

We will use barycentric coordinates and vectors. Let? $\vec{X}$ ?be the position vector of a point? $X.$ ?The point? $(x, y, z)$ ?in barycentric coordinates denotes the point? $x\vec{A} + y\vec{B} + z\vec{C}.$ ?For all points in the plane of? $\triangle{ABC},$ ?we have? $x + y + z = 1.$ ?It is clear that? $A = (1, 0, 0)$ ;? $B = (0, 1, 0)$ ; and? $C = (0, 0, 1).$

Define the point? $P$ ?as? $P = \left(x_P, y_P, z_P\right).$ ?The fact that? $P$ ?lies on the circumcircle of? $\triangle{ABC}$ ?gives us? $x^2_P + y^2_P + z^2_P = 1.$ ?This, along with the condition? $x_P + y_P + z_P = 1$ ?inherent to barycentric coordinates, gives us? $x_Py_P + y_Pz_P + z_Px_P = 0.$

We can write the equations of the following lines: $BC: x = 0$ $CA: y = 0$ $AB: z = 0$ $PA: \frac{y}{y_P} = \frac{z}{z_P}$ $PB: \frac{x}{x_P} = \frac{z}{z_P}$ $PC: \frac{x}{x_P} = \frac{y}{y_P}.$

We can then solve for the points? $D, E, F$ : $D = \left(0, \frac{y_P}{y_P + z_P}, \frac{z_P}{y_P + z_P}\right)$ $E = \left(\frac{x_P}{x_P + z_P}, 0, \frac{z_P}{x_P + z_P}\right)$ $F = \left(\frac{x_P}{x_P + y_P}, \frac{y_P}{x_P + y_P}, 0\right).$

The area of an arbitrary triangle? $XYZ$ ?is: $[XYZ] = \frac{1}{2}|\vec{XY}\times\vec{XZ}|$ $[XYZ] = \frac{1}{2}|(\vec{X}\times\vec{Y}) + (\vec{Y}\times\vec{Z}) + (\vec{Z}\times\vec{X})|.$

To calculate? $[DEF],$ ?we wish to compute? $(\vec{D}\times\vec{E}) + (\vec{E}\times\vec{F}) + (\vec{F}\times\vec{D}).$ ?After a lot of computation, we obtain the following: $(\vec{D}\times\vec{E}) + (\vec{E}\times\vec{F}) + (\vec{F}\times\vec{D}) = \frac{2x_Py_Pz_P}{(x_P + y_P)(y_P + z_P)(z_P + x_P)}[(\vec{A}\times\vec{B}) + (\vec{B}\times\vec{C}) + (\vec{C}\times\vec{A})].$

Evaluating the denominator, $(x_P + y_P)(y_P + z_P)(z_P + x_P) = (1 - z_P)(1 - y_P)(1 - x_P)$ $(x_P + y_P)(y_P + z_P)(z_P + x_P) = 1 - (x_P + y_P + z_P) + (x_Py_P + y_Pz_P + z_Px_P) - x_Py_Pz_P.$

Since? $x_P + y_P + z_P = 1$ ?and? $x_Py_P + y_Pz_P + z_Px_P = 0,$ ?it follows that: $(x_P + y_P)(y_P + z_P)(z_P + x_P) = -x_Py_Pz_P.$

We thus conclude that: $(\vec{D}\times\vec{E}) + (\vec{E}\times\vec{F}) + (\vec{F}\times\vec{D}) = -2[(\vec{A}\times\vec{B}) + (\vec{B}\times\vec{C}) + (\vec{C}\times\vec{A})].$

From this, it follows that? $[DEF] = 2[ABC],$ ?and we are done.

Solution 3

$[asy] import cse5; import graph; import olympiad; size(3inch); pair A = (0, 3sqrt(3)), B = (-3,0), C = (3,0), O = (0, sqrt(3)); pair P = (-1, -sqrt(11)+sqrt(3)); path circle = Circle(O, 2sqrt(3)); pair D = extension(A,P,B,C); pair E1 = extension(A,C,B,P); pair F=extension(A,B,C,P); draw(circle, black); draw(A--B--C--cycle); draw(B--E1--C); draw(C--F--B); draw(A--P); draw(D--E1--F--cycle, dashed); pair G = extension(O,D,F,E1); draw(O--G,dashed); label("A", A, N); label("B", B, W); label("C", C, E); label("P", P, S); label("D", D, NW); label("E", E1, SE); label("F", F, SW); dot("O", O, SE); [/asy]$ We'll use coordinates and shoelace. Let the origin be the midpoint of? $BC$ . Let? $AB=2$ , and? $BF = 2x$ , then? $F=(-x-1,-x\sqrt{3})$ . Using the facts? $\triangle{CBP} \sim \triangle{CFB}$ ?and? $\triangle{BCP} \sim \triangle{BEC}$ , we have? $BF * CE = BC^2$ , so? $CE = \frac{1}{2x}$ , and? $E = (\frac{1}{x}+1,-\frac{\sqrt{3}}{x})$ .

The slope of? $FE$ ?is $k = \frac{-\frac{\sqrt{3}}{x} + x\sqrt{3}}{2+\frac{1}{x}+x}$ It is well-known that? $\triangle{DFE}$ ?is self-polar, so? $FE$ ?is the polar of? $D$ , i.e.,? $OD$ ?is perpendicular to? $FE$ . Therefore, the slope of? $OD$ ?is? $-\frac{1}{k}$ . Since? $O=(0,\frac{1}{\sqrt{3}})$ , we get the x-coordinate of? $D$ ,? $x_D = \frac{k}{\sqrt{3}}$ , i.e.,? $D = (\frac{k}{\sqrt{3}},0)$ . Using shoelace, $2[\triangle{FDE}] = \frac{k}{\sqrt{3}}(-x\sqrt{3})+(-x-1)(-\frac{\sqrt{3}}{x})- (-x\sqrt{3})(\frac{1}{x}+1) - (-\frac{\sqrt{3}}{x})\frac{k}{\sqrt{3}}$ $= 2\sqrt{3} + \sqrt{3}(\frac{1}{x}+x) + k(\frac{1}{x} - x)$ $= 2\sqrt{3} + \sqrt{3}(\frac{2(\frac{1}{x}+x)+(\frac{1}{x}+x)^2-(\frac{1}{x}-x)^2} {2+\frac{1}{x}+x})$ $= 2\sqrt{3} + \sqrt{3}(\frac{2(\frac{1}{x}+x)+4}{2+\frac{1}{x}+x})$ $= 4\sqrt{3}$ So? $[\triangle{FDE}] = 2\sqrt{3} = 2[\triangle{ABC}]$ . Q.E.D

Problem 4

Solution

Yes. Let? $p = (a-2)(b-2)(c-2)+12 = abc - 2(ab+ac+bc)+4(a+b+c)+4$ . Also define? $\alpha=a+b+c$ . We want? $p$ ?to divide the positive number? $a^2+b^2+c^2+abc-2017=(\alpha-47)(\alpha+43)+p$ . This equality can be verified by expanding the righthand side. Because? $a^2+b^2+c^2+abc-2017$ ?will be trivially positive if? $(\alpha-47)(\alpha+43)$ ?is non-negative, we can just assume that? $\alpha=47$ . Analyzing the structure of? $p$ , we see that? $a-2$ , $b-2$ , and? $c-2$ ?must be? $1$ ?or? $5$ ?mod? $6$ , or? $p$ ?will not be prime (divisibility by? $2$ ?and? $3$ ). Thus, we can guess any? $a$ , $b$ , and? $c$ ?which satisfies those constraints. For example,? $a = 21$ , $b=13$ , and? $c=13$ ?works.? $p=2311$ ?is prime, and it divides the positive number? $a^2+b^2+c^2+abc-2017=2311$ .

This solution is wrong. No? $p$ ?actually exist.

Problem 5

Solution

$[asy] size(9cm); pair A = dir(130); pair B = dir(220); pair C = dir(320); draw(unitcircle, lightblue); pair P = dir(-90); pair Q = dir(90); pair D = extension(A, P, B, C); pair O = origin; pair M = extension(B, C, O, P); pair N = 2*M-P; draw(A--B--C--cycle, lightblue); draw(A--P--Q, lightblue); draw(A--N--D--O--A, lightblue); draw(A--D--N--O--cycle, red); dot("$A$", A, dir(A)); dot("$B$", B, dir(B)); dot("$C$", C, dir(C)); dot("$P$", P, dir(P)); dot("$Q$", Q, dir(Q)); dot("$D$", D, dir(225)); dot("$O$", O, dir(315)); dot("$M$", M, dir(315)); dot("$N$", N, dir(315)); [/asy]$

Suppose ray? $OM$ ?intersects the circumcircle of? $BHC$ ?at? $N'$ , and let the foot of the A-altitude of? $ABC$ ?be? $E$ . Note that? $\angle BHE=90-\angle HBE=90-90+\angle C=\angle C$ . Likewise,? $\angle CHE=\angle B$ . So,? $\angle BHC=\angle BHE+\angle CHE=\angle B+\angle C$ .? $BHCN'$ ?is cyclic, so? $\angle BN'C=180-\angle BHC=180-\angle B-\angle C=\angle A$ . Also,? $\angle BAC=\angle A$ . These two angles are on different circles and have the same measure, but they point to the same line? $BC$ ! Hence, the two circles must be congruent. (This is also a well-known result)

We know, since? $M$ ?is the midpoint of? $BC$ , that? $OM$ ?is perpendicular to? $BC$ .? $AH$ ?is also perpendicular to? $BC$ , so the two lines are parallel.? $AN$ ?is a transversal, so? $\angle HAN=\angle ANO$ . We wish to prove that? $\angle ANO=\angle ADO$ , which is equivalent to? $AOND$ ?being cyclic.

Now, assume that ray? $OM$ ?intersects the circumcircle of? $ABC$ ?at a point? $P$ . Point? $P$ ?must be the midpoint of? $\stackrel{\frown}{BC}$ . Also, since? $AD$ ?is an angle bisector, it must also hit the circle at the point? $P$ . The two circles are congruent, which implies? $MN=MP\implies ND=DP\implies$ NDP is isosceles. Angle ADN is an exterior angle, so? $\angle ADN=\angle DNP+\angle DPO=2\angle DPO$ . Assume WLOG that? $\angle B>\angle C$ . So,? $\angle DPO=\angle APO=\frac{\angle B+\angle C}{2}-\angle C=\frac{\angle B-\angle C}{2}$ . In addition,? $\angle AON=\angle AOP=\angle AOB+\angle BOP=2\angle C+\angle A$ . Combining these two equations,? $\angle AON+\angle ADN=\angle B-\angle C+2\angle C+\angle A=\angle A+\angle B+\angle C=180$ .

Opposite angles sum to? $180$ , so quadrilateral? $AOND$ ?is cyclic, and the condition is proved.

Problem 6

Solution

I define a sequence to be, starting at? $(1,0)$ ?and tracing the circle counterclockwise, and writing the color of the points in that order - either R or B. For example, possible sequences include? $RB$ ,? $RBBR$ ,? $BBRRRB$ ,? $BRBRRBBR$ , etc. Note that choosing an? $R_1$ ?is equivalent to choosing an? $R$ ?in a sequence, and? $B_1$ ?is defined as the? $B$ ?closest to? $R_1$ ?when moving rightwards. If no? $B$ s exist to the right of? $R_1$ , start from the far left. For example, if I have the above example? $RBBR$ , and I define the 2nd? $R$ ?to be? $R_1$ , then the first? $B$ ?will be? $B_1$ . Because no? $R$ ?or? $B$ can be named twice, I can simply remove? $R_1$ ?and? $B_1$ ?from my sequence when I choose them. I define this to be a move. Hence, a possible move sequence of? $BBRRRB$ ?is:? $BBR_1RRB_1\implies B_2BRR_2\implies B_3R_3$

Note that, if, in a move, $B_n$ ?appears to the left of? $R_n$ , then? $\stackrel{\frown}{R_nB_n}$ ?intersects? $(1,0)$

Now, I define a commencing? $B$ ?to be a? $B$ ?which appears to the left of all? $R$ s, and a terminating? $R$ ?to be a? $R$ ?which appears to the right of all? $B$ s. Let the amount of commencing? $B$ s be? $j$ , and the amount of terminating? $R$ s be? $k$ , I claim that the number of arcs which cross? $(1,0)$ ?is constant, and it is equal to? $\text{max}(j,k)$ . I will show this with induction.

Base case is when? $n=1$ . In this case, there are only two possible sequences -? $RB$ ?and? $BR$ . In the first case,? $\stackrel{\frown}{R_1B_1}$ ?does not cross? $(1, 0)$ , but both? $j$ ?and? $k$ ?are? $0$ , so? $\text{max}(j,k)=0$ . In the second example,? $j=1$ ,? $k=1$ , so? $\text{max}(j,k)=1$ .? $\stackrel{\frown}{R_1B_1}$ ?crosses? $(1,0)$ ?since? $B_1$ ?appears to the left of? $R_1$ , so there is one arc which intersects. Hence, the base case is proved.

For the inductive step, suppose that for a positive number? $n$ , the number of arcs which cross? $(1,0)$ ?is constant, and given by? $\text{max}(j, k)$ ?for any configuration. Now, I will show it for? $n+1$ .

Suppose I first choose? $R_1$ ?such that? $B_1$ ?is to the right of? $R_1$ ?in the sequence. This implies that? $\stackrel{\frown}{R_1B_1}$ ?does not cross? $(1,0)$ . But, neither? $R_1$ ?nor? $B_1$ ?is a commencing? $B$ ?or terminating? $R$ . These numbers remain constant, and now after this move we have a sequence of length? $2n$ . Hence, by assumption, the total amount of arcs is? $0+\text{max}(j,k)=\text{max}(j,k)$ .

Now suppose that? $R_1$ ?appears to the right of? $B_1$ , but? $B_1$ ?is not a commencing? $B$ . This implies that there are no commencing? $B$ s in the series, because there are no? $B$ s to the left of? $B_1$ , so? $j=0$ . Note that this arc does intersect? $(1,0)$ , and? $R_1$ ?must be a terminating? $R$ .? $R_1$ ?must be a terminating? $R$ ?because there are no? $B$ s to the right of? $R_1$ , or else that? $B$ ?would be? $B_1$ . The? $2n$ ?length sequence that remains has? $0$ commencing? $B$ s and? $k-1$ ?terminating? $R$ s. Hence, by assumption, the total amount of arcs is? $1+\text{max}(0,k-1)=1+k-1=k=\text{max}(j,k)$ .

Finally, suppose that? $R_1$ ?appears to the right of? $B_1$ , and? $B_1$ ?is a commencing? $B$ . We know that this arc will cross? $(1,0)$ . Analogous to the previous case,? $R_1$ ?is a terminating? $R$ , so the? $2n$ ?length sequence which remains has? $j-1$ ?commencing? $B$ s and? $k-1$ ?terminating? $R$ s. Hence, by assumption, the total amount of arcs is? $1+\text{max}(j-1,k-1)=1+\text{max}(j,k)-1=\text{max}(j,k)$ .

There are no more possible cases, hence the induction is complete, and the number of arcs which intersect? $(1,0)$ ?is indeed a constant which is given by? $\text{max}(j,k)$ .

完整版真题资料可以底部二维码免费领取↓↓↓