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

2011 USAMO Problems真题及答案

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

2011 USAMO Problems真题及答案

完整版真题免费下载

+答案解析请参考文末

Day 1

Problem 1

Let? $a$ ,? $b$ ,? $c$ ?be positive real numbers such that? $a^2 + b^2 + c^2 + (a + b + c)^2 le 4$ . Prove that $[frac{ab + 1}{(a + b)^2} + frac{bc + 1}{(b + c)^2} + frac{ca + 1}{(c + a)^2} ge 3.]$

Problem 2

An integer is assigned to each vertex of a regular pentagon so that the sum of the five integers is 2011. A turn of a solitaire game consists of subtracting an integer? $m$ ?from each of the integers at two neighboring vertices and adding? $2m$ ?to the opposite vertex, which is not adjacent to either of the first two vertices. (The amount? $m$ ?and the vertices chosen can vary from turn to turn.) The game is won at a certain vertex if, after some number of turns, that vertex has the number 2011 and the other four vertices have the number 0. Prove that for any choice of the initial integers, there is exactly one vertex at which the game can be won.

Problem 3

In hexagon? $ABCDEF$ , which is nonconvex but not self-intersecting, no pair of opposite sides are parallel. The internal angles satisfy? $angle A = 3 angle D$ ,? $angle C = 3 angle F$ , and? $angle E = 3 angle B$ . Furthermore,? $AB = DE$ ,? $BC = EF$ , and? $CD = FA$ . Prove that diagonals? $overline{AD}$ ,? $overline{BE}$ , and? $overline{CF}$ ?are concurrent.

Day 2

Problem 4

Consider the assertion that for each positive integer? $n ge 2$ , the remainder upon dividing? $2^{2^n}$ ?by? $2^n - 1$ ?is a power of 4. Either prove the assertion or find (with proof) a counterexample.

Problem 5

Let? $P$ ?be a given point inside quadrilateral? $ABCD$ . Points? $Q_1$ ?and? $Q_2$ ?are located within? $ABCD$ ?such that? $angle Q_1 BC = angle ABP$ ,? $angle Q_1 CB = angle DCP$ ,? $angle Q_2 AD = angle BAP$ ,? $angle Q_2 DA = angle CDP$ . Prove that? $overline{Q_1 Q_2} parallel overline{BA}$ ?if and only if? $overline{Q_1 Q_2} parallel overline{CD}$ .

Problem 6

Let? $A$ ?be a set with? $|A| = 225$ , meaning that? $A$ ?has 225 elements. Suppose further that there are eleven subsets? $A_1$ ,? $dots$ ,? $A_{11}$ ?of? $A$ ?such that? $|A_i | = 45$ ?for? $1 le i le 11$ ?and? $|A_i cap A_j| = 9$ ?for? $1 le i < j le 11$ . Prove that? $|A_1 cup A_2 cup dots cup A_{11}| ge 165$ , and give an example for which equality holds.

Problem 1

Solution 1

Since $begin{align*} (a+b)^2 + (b+c)^2 + (c+a)^2 &= 2(a^2 + b^2 + c^2 + ab + bc + ca) \ &= a^2 + b^2 + c^2 + (a + b + c)^2, end{align*}$ it is natural to consider a change of variables: $begin{align*} alpha &= b + c \ beta &= c + a \ gamma &= a + b end{align*}$ with the inverse mapping given by: $begin{align*} a &= frac{beta + gamma - alpha}2 \ b &= frac{alpha + gamma - beta}2 \ c &= frac{alpha + beta - gamma}2 end{align*}$ With this change of variables, the constraint becomes $[alpha^2 + beta^2 + gamma^2 le 4,]$ while the left side of the inequality we need to prove is now $begin{align*} & frac{gamma^2 - (alpha - beta)^2 + 4}{4gamma^2} + frac{alpha^2 - (beta - gamma)^2 + 4}{4alpha^2} + frac{beta^2 - (gamma - alpha)^2 + 4}{4beta^2} ge \ & frac{gamma^2 - (alpha - beta)^2 + alpha^2 + beta^2 + gamma^2}{4gamma^2} + frac{alpha^2 - (beta - gamma)^2 + alpha^2 + beta^2 + gamma^2}{4alpha^2} + frac{beta^2 - (gamma - alpha)^2 + alpha^2 + beta^2 + gamma^2}{4beta^2} = \ & frac{2gamma^2 + 2alphabeta}{4gamma^2} + frac{2alpha^2 + 2betagamma}{4alpha^2} + frac{2beta^2 + 2gammaalpha}{4beta^2} = \ & frac32 + frac{alphabeta}{2gamma^2} + frac{betagamma}{2alpha^2} + frac{gammaalpha}{2beta^2}. end{align*}$

Therefore it remains to prove that $[frac{alphabeta}{2gamma^2} + frac{betagamma}{2alpha^2} + frac{gammaalpha}{2beta^2} ge frac32.]$

We note that the product of the three (positive) terms is 1/8, therefore by AM-GM their mean is at least 1/2, and thus their sum is at least 3/2 and we are done.

Solution 2

Rearranging the condition yields that $[a^2 + b^2 + c^2 +ab+bc+ac le 2]$

Now note that $[frac{2ab+2}{(a+b)^2} ge frac{2ab+a^2 + b^2 + c^2 +ab+bc+ac}{(a+b)^2}=frac{(a+b)^2 + (c+a)(c+b)}{(a+b)^2}]$

Summing this for all pairs of? ${ a,b,c }$ ?gives that $[sum_{cyc} frac{2ab+2}{(a+b)^2} ge 3+ sum_{cyc}frac{(c+a)(c+b)}{(a+b)^2} ge 6]$

By AM-GM. Dividing by? $2$ ?gives the desired inequality. The problems on this page are copyrighted by the?Mathematical Association of America's?American Mathematics Competitions.

Problem 2

Solution

Let? $mathbb{F}_5$ ?be the field of positive residues modulo 5. We label the vertices of the pentagon clockwise with the residues 0, 1, 2, 3 and 4. For each? $i in mathbb{F}_5$ ?let? $n_i$ ?be the integer at vertex? $i$ ?and let? $r_i in mathbb{F}_5$ ?be defined?as: $[r_i equiv 4n_{i+1} + 3n_{i+2} + 2n_{i+3} + n_{i+4} equiv sum_{kinmathbb{F}_5}(i-k)n_k pmod 5.]$ Let? $s = sum_{iinmathbb{F}_5} n_i$ . A move in the game consists of $[(n_i, n_{i+1}, n_{i+2}, n_{i+3}, n_{i+4}) mapsto (n_i + 2m, n_{i+1}, n_{i+2} - m, n_{i+3} - m, n_{i+4})]$ for some vertex? $i in mathbb{F}_5$ ?and integer? $m$ . We immediately see that? $s$ ?is an invariant of the game. After our move the new value of? $r_i$ ?is decreased by? $3m + 2m equiv 0 pmod 5$ ?as?a result of the change in the? $3n_{i+2}$ ?and? $2n_{i+3}$ ?terms. So? $r_i$ ?does not change after a move at vertex? $i$ .

For all? $i in mathbb{F}_5$ ?we have: $[r_{i+1} - r_i equiv sum_{kinmathbb{F}_5} ((i+1-k)n_k - (i-k)n_k) equiv sum_{kinmathbb{F}_5} n_k equiv s pmod 5.]$

Therefore, the? $r_i$ ?form an arithmetic progression in? $mathbb{F}_5$ ?with a difference of? $s$ . Since? $r_k$ ?is unchanged by a move at vertex? $k$ , so are all the remaining? $r_i$ ?as?the differences are constant.

Provided? $s notequiv 0 pmod 5$ , we see that the mapping? $i mapsto r_i$ ?is a bijection? $mathbb{F}_5 to mathbb{F}_5$ ?and exactly one vertex will have? $r_i equiv 0 pmod 5$ .?As? $r_i$ ?is an invariant, a winning vertex must have? $r_i equiv 0$ , since in the final state each? $n_k$ ?with? $k ne i$ ?is zero. So, for? $s notequiv 0 pmod 5$ , if a winning vertex exists, it is the unique vertex with? $r_i equiv 0$ .

Without loss of generality, it remains to show that if? $r_0 equiv 0 pmod 5$ , then 0 must be a winning vertex. To prove this, we perform the following moves: $begin{align*} (n_0, n_1, n_2, n_3, n_4) &mapsto (n_0-n_1, 0, n_2, n_3 + 2n_1, n_4), & (i, m) &= (3, n_1) \ &mapsto (n_0-n_1-n_4, 0, n_2+2n_4, n_3 +2n_1, 0) & (i, m) &= (2, n_4) end{align*}$ We designate the new state? $(n'_0, 0, n'_2, n'_3, 0)$ . Since? $r_0 equiv 0$ ?is an invariant, and? $n'_1 = n'_4 = 0$ , we now have? $r_0 equiv n'_3 - n'_2 = 5p$ , for some integer? $p$ . Our final set of moves is: $begin{align*} (n'_0, 0, n'_2, n'_3, 0) &mapsto (n'_0+p, p, n'_2, n'_3 - 2p, 0), & (i, m) &= (3, -p)\ &mapsto (n'_0+p, 0, n'_2-p, n'_3 - 2p, 2p), & (i, m) &= (4, p) \ &mapsto (n'_0-p, 0, n'_2+3p, n'_3 - 2p, 0), & (i, m) &= (2, 2p)\ &mapsto (n'_0+2n'_2 + 5p, 0, 0, n'_3-n'_2 - 5p = 0, 0) & (i, m) &= (0, n'_2 + 3p) end{align*}$ Now our chosen vertex 0 is the only vertex with a non-zero value, and since? $s$ ?is invariant, that value is? $s$ ?as?required. Since a vertex? $i$ ?with? $r_i equiv 0 pmod 5$ ?is winnable, and with? $s = 2011 notequiv 0 pmod 5$ ?we always have a unique such vertex, we are done.

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

Problem 3

Solution 1

Let? $angle D = alpha$ ,? $angle F = gamma$ , and? $angle B = epsilon$ ,? $AB=DE=p$ ,? $BC=EF=q$ ,? $CD=FA=r$ ,? $AB$ ?intersect? $DE$ ?at? $X$ ,? $BC$ ?intersect? $EF$ ?at? $Y$ , and? $CD$ ?intersect? $FA$ ?at? $Z$ . Define the vectors: $[vec{u} = vec{AB} + vec{DE}]$ $[vec{v} = vec{BC} + vec{EF}]$ $[vec{w} = vec{CD} + vec{FA}]$ Clearly,? $vec{u}+vec{v}+vec{w}=textbf{0}$ .

Note that? $angle X = 360^circ - angle D - angle C - angle B = 360^circ - alpha - 3gamma - beta = 180^circ - 2gamma$ . By sliding the vectors? $vec{AB}$ ?and? $vec{DE}$ ?to the vectors? $vec{MX}$ and? $vec{XN}$ ?respectively, then? $vec{u} = vec{MN}$ .?As? $XMN$ ?is isosceles with? $XM = XN$ , the base angles are both? $gamma$ . Thus,? $|vec{u}|=2p cos gamma$ . Similarly,? $|vec{v}|=2q cos alpha$ ?and? $|vec{w}| = 2r cos epsilon$ .

Next we will find the angles between? $vec{u}$ ,? $vec{v}$ , and? $vec{w}$ .?As? $angle MNX = gamma$ , the angle between the vectors? $vec{u}$ ?and? $vec{NE}$ ?is? $gamma$ . Similarly, the angle between? $vec{NE}$ ?and? $vec{EF}$ ?is? $180^circ-beta$ , and the angle between? $vec{EF}$ ?and? $vec{v}$ ?is? $alpha$ . Thus, the angle between? $vec{u}$ ?and? $vec{v}$ ?is? $gamma + 180^circ-beta+alpha = 360^circ - 2beta$ , or just? $2beta$ ?in the other direction if we take it modulo? $360^circ$ . Similarly, the angle between? $vec{v}$ ?and? $vec{w}$ ?is? $2 gamma$ , and the angle between? $vec{w}$ ?and? $vec{u}$ ?is? $2 alpha$ .

And since? $vec{u}+vec{v}+vec{w}=vec{0}$ , we can arrange the three vectors to form a triangle, so the triangle with sides of lengths? $2p cos gamma$ ,? $2q cos alpha$ , and? $2r cos epsilon$ ?has opposite angles of? $180^circ - 2gamma$ ,? $180^circ - 2alpha$ , and? $180^circ - 2epsilon$ , respectively. So by the law of sines (double sine formula): $[frac{2p cos gamma}{sin 2gamma} = frac{2q cos alpha}{sin 2alpha} = frac{2r cos epsilon}{sin 2epsilon}]$ $[frac{p}{sin gamma} = frac{q}{sin alpha} = frac{r}{sin epsilon},]$ and the triangle with sides of length? $p$ ,? $q$ , and? $r$ ?has corrosponding angles of? $gamma$ ,? $alpha$ , and? $epsilon$ ?(but then triangles? $FAB$ ,? $CDB$ , and? $FDE$ ?). So? $FD=p$ ,? $BF=q$ , and? $BD=r$ , and? $D$ ,? $F$ , and? $B$ ?are the reflections of the vertices of triangle? $ACE$ ?about the sides. So? $AD$ ,? $BE$ , and? $CF$ concur at the orthocenter of triangle? $ACE$ , with? $ACE$ ?being the smaller triangle: $[asy] pair A,B,C,D,E,F; B=(0,0); D=(200,0); F=(100,173.2); A=(B+F)/2; C=(B+D)/2; E=(D+F)/2; draw(B--D--F--B); draw(A--C--E--A,red); label("$textcolor{red}{A}$",A,dir(150)); label("$B$",B,dir(210)); label("$textcolor{red}{C}$",C,S); label("$D$",D,dir(330)); label("$textcolor{red}{E}$",E,dir(30)); label("$F$",F,N); [/asy]$

Solution 2

We work in the complex plane, where lowercase letters denote point affixes. Let? $P$ ?denote hexagon? $ABCDEF$ . Since? $AB=DE$ , the condition? $ABnotparallel DE$ ?is equivalent to? $a-b+d-ene 0$ .

Construct a "phantom hexagon"? $P'=A'B'C'D'E'F'$ ?as?follows: let? $A'C'E'$ ?be a triangle with? $angle{A'C'E'}=angle{F}$ ,? $angle{C'E'A'}=angle{B}$ , and? $angle{E'A'C'}=angle{F}$ ?(this is possible since? $angle{B}+angle{D}+angle{F}=180^circ$ ?by the angle conditions), and reflect? $A',C',E'$ ?over its sides to get points? $D',F',B'$ , respectively. By rotation and reflection if necessary, we assume? $A'B'parallel AB$ ?and? $P',P$ ?have the same orientation (clockwise or counterclockwise), i.e.? $frac{b-a}{b'-a'}inmathbb{R}^+$ . It's easy to verify that? $angle{X'}=angle{X}$ ?for? $Xin{A,B,C,D,E,F}$ ?and opposite sides of? $P'$ ?have equal lengths.?As?the corresponding sides of? $P$ ?and? $P'$ ?must then be parallel, there exist positive reals? $r,s,t$ ?such that? $r=frac{a-b}{a'-b'}=frac{d-e}{d'-e'}$ ,? $s=frac{b-c}{b'-c'}=frac{e-f}{e'-f'}$ , and? $t=frac{c-d}{c'-d'}=frac{f-a}{f'-a'}$ . But then? $0ne a-b+d-e=r(a'-b'+d'-e')$ , etc., so the non-parallel condition "transfers" directly from? $P$ ?to? $P'$ ?and $begin{align*} 0 &=(a-b+d-e)+(b-c+e-f)+(c-d+f-a) \ &=r(a'-b'+d'-e')+s(b'-c'+e'-f')+t(c'-d'+f'-a') \ &=(r-t)(a'-b'+d'-e')+(s-t)(b'-c'+e'-f'). end{align*}$ If? $r-t=s-t=0$ , then? $P$ ?must be similar to? $P'$ ?and the conclusion is obvious.

Otherwise, since? $a'-b'+d'-e'ne0$ ?and? $b'-c'+e'-f'ne0$ , we must have? $r-tne0$ ?and? $s-tne0$ . Now let? $x=frac{a'+d'}{2}$ ,? $y=frac{c'+f'}{2}$ ,? $z=frac{e'+b'}{2}$ ?be the feet of the altitudes in? $triangle{A'C'E'}$ ; by the non-parallel condition in? $P'$ ,? $x,y,z$ ?are pairwise distinct. But? $frac{z-x}{z-y}=frac{s-t}{r-t}inmathbb{R}$ , whence? $x,y,z$ ?are three distinct collinear points, which is clearly impossible. (The points can only be collinear when? $triangle{A'C'E'}$ ?is a right triangle, but in this case two of? $x,y,z$ ?must coincide.)

Alternatively (for the previous paragraph), WLOG assume that? $(A'C'E')$ ?is the unit circle, and use the fact that? $b'=a'+c'-frac{a'c'}{e'}$ , etc. to get simple expressions for? $a'-b'+d'-e'$ ?and? $b'-c'+e'-f'$ .

Solution 3

We work in the complex plane to give (essentially) a complete characterization when the parallel condition is relaxed.

WLOG assume? $a,b,c$ ?are on the unit circle. It suffices to show that? $a,b,c$ ?uniquely determine? $d,e,f$ , since we know that if we let? $E$ ?be the reflection of? $B$ ?over? $AC$ ,? $D$ ?be the reflection of? $A$ ?over? $CE$ , and? $F$ ?be the reflection of? $C$ ?over? $AE$ , then? $ABCDEF$ ?satisfies the problem conditions. (*)

It's easy to see with the given conditions that $begin{align*} (a-b)(c-d)(e-f) &= (b-c)(d-e)(f-a) Longleftrightarrow f=frac{(a-b)(c-d)e+(c-b)(e-d)a}{(a-b)(c-d)+(c-b)(e-d)} \ frac{(e-a)(c-b)}{(a-b)(c-d)+(c-b)(e-d)} = frac{f-e}{d-e} &= left(frac{c-b}{a-b}right)^2 overline{left(frac{a-b}{c-b}right)} = frac{c-b}{a-b}cdotfrac{c}{a} Longleftrightarrow d=frac{c[(a-b)c+(c-b)e]+a(a-e)(a-b)}{c[(a-b)+(c-b)]} \ frac{(a-b)(c-d)+(c-b)(e-d)}{(a-e)(c-d)} = frac{b-a}{f-a} &= left(frac{e-d}{c-d}right)^2 overline{left(frac{c-d}{e-d}right)}. end{align*}$ Note that $[frac{e-d}{c-d}=frac{(a-b)[c(e-c)+a(e-a)]}{c(c-e)(c-b)-a(a-e)(a-b)},]$ so plugging into the third equation we have $begin{align*} frac{a(a-b)(2b-a-c)}{c(c-e)(c-b)-a(a-e)(a-b)} &=frac{(a-b)+(c-b)frac{(a-b)[c(e-c)+a(e-a)]}{c(c-e)(c-b)-a(a-e)(a-b)}}{(a-e)}\ &=left(frac{(a-b)[c(e-c)+a(e-a)]}{c(c-e)(c-b)-a(a-e)(a-b)}right)^2overline{left(frac{c(c-e)(c-b)-a(a-e)(a-b)}{(a-b)[c(e-c)+a(e-a)]}right)}\ &=left(frac{(a-b)[c(e-c)+a(e-a)]}{c(c-e)(c-b)-a(a-e)(a-b)}right)^2frac{frac{1}{c}left(overline{e}-frac{1}{c}right)frac{b-c}{bc}-frac{1}{a}left(overline{e}-frac{1}{a}right)frac{b-a}{ba}}{frac{b-a}{ab}left(frac{1}{c}left(frac{1}{c}-overline{e}right)+frac{1}{a}left(frac{1}{a}-overline{e}right)right)}\ &=left(frac{(a-b)[c(e-c)+a(e-a)]}{c(c-e)(c-b)-a(a-e)(a-b)}right)^2frac{c^3(aoverline{e}-1)(a-b)-a^3(coverline{e}-1)(c-b)}{c(a-b)[a^2(coverline{e}-1)+c^2(aoverline{e}-1)]}\ &=frac{(a-b)[c(e-c)+a(e-a)]^2}{[c(c-e)(c-b)-a(a-e)(a-b)]^2}frac{c^3(aoverline{e}-1)(a-b)-a^3(coverline{e}-1)(c-b)}{c[a^2(coverline{e}-1)+c^2(aoverline{e}-1)]}. end{align*}$ Simplifying, this becomes $begin{align*} &ac(2b-a-c)[c(c-e)(c-b)-a(a-e)(a-b)][a^2(coverline{e}-1)+c^2(aoverline{e}-1)]\ &=[c(e-c)+a(e-a)]^2[c^3(aoverline{e}-1)(a-b)-a^3(coverline{e}-1)(c-b)]. end{align*}$ Of course, we can also "conjugate" this equation -- a nice way to do this is to note that if $[x=frac{(a-b)[c(e-c)+a(e-a)]}{c(c-e)(c-b)-a(a-e)(a-b)},]$ then $[frac{a(2b-a-c)}{c(e-c)+a(e-a)}=frac{x}{overline{x}}=overline{left(frac{c(e-c)+a(e-a)}{a(2b-a-c)}right)}=frac{frac{1}{c}left(overline{e}-frac{1}{c}right)+frac{1}{a}left(overline{e}-frac{1}{a}right)}{frac{1}{a}left(frac{2}-frac{1}{a}-frac{1}{c}right)},]$ whence $[ac(2b-a-c)[2ac-b(a+c)]=b[c(e-c)+a(e-a)][a^2(coverline{e}-1)+c^2(aoverline{e}-1)].]$ If? $a+cne 0$ , then eliminating? $overline{e}$ , we get $[einleft{a+c-frac{ac},a+frac{2c(c-b)}{a+c},c+frac{2a(a-b)}{a+c}right}.]$ The first case corresponds to (*) (since? $a,b,c,e$ ?uniquely determine? $d$ ?and? $f$ ), the second corresponds to? $ABparallel DE$ ?(or equivalently, since? $AB=DE$ ,? $a-b=e-d$ ), and by symmetry, the third corresponds to? $CBparallel FE$ .

Otherwise, if? $c=-a$ , then we easily find? $b^2e=a^4overline{e}$ ?from the first of the two equations in? $e,overline{e}$ ?(we actually don't need this, but it tells us that the locus of working? $e$ ?is a line through the origin). It's easy to compute? $d=e+frac{a(a-b)}$ ?and? $f=e+frac{a(a+b)}$ , so? $a-c=2a=f-dimplies c-d=a-fimplies CDparallel AF$ , and we're done.

Comment.?It appears that taking? $(ABC)$ ?the unit circle is nicer than, say? $e=0$ ?or? $(ACE)$ ?the unit circle (which may not even be reasonably tractable).

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

Problem 4

Solution 1

We will show that? $n = 25$ ?is a counter-example.

Since? $textstyle 2^n equiv 1 pmod{2^n - 1}$ , we see that for any integer? $k$ ,? $textstyle 2^{2^n} equiv 2^{(2^n - kn)} pmod{2^n-1}$ . Let? $0 le m < n$ ?be the residue of? $2^n pmod n$ . Note that since? $textstyle m < n$ ?and? $textstyle n ge 2$ , necessarily? $textstyle 2^m < 2^n -1$ , and thus the remainder in question is? $textstyle 2^m$ . We want to show that? $textstyle 2^m pmod {2^n-1}$ ?is an odd power of 2 for some? $textstyle n$ , and thus not a power of 4.

Let? $textstyle n=p^2$ ?for some odd prime? $textstyle p$ . Then? $textstyle varphi(p^2) = p^2 - p$ . Since 2 is co-prime to? $textstyle p^2$ , we have $[{2^{varphi(p^2)} equiv 1 pmod{p^2}}]$ and thus $[textstyle 2^{p^2} equiv 2^{(p^2 - p) + p} equiv 2^p pmod{p^2}.]$

Therefore, for a counter-example, it suffices that? $textstyle 2^p pmod{p^2}$ ?be odd. Choosing? $textstyle p=5$ , we have? $textstyle 2^5 = 32 equiv 7 pmod{25}$ . Therefore,? $textstyle 2^{25} equiv 7 pmod{25}$ ?and thus $[textstyle 2^{2^{25}} equiv 2^7 pmod {2^{25} - 1}.]$ Since? $textstyle 2^7$ ?is not a power of 4, we are done.

Solution 2

Lemma (useful for all situations): If? $x$ ?and? $y$ ?are positive integers such that? $2^x - 1$ ?divides? $2^y - 1$ , then? $x$ ?divides? $y$ . Proof:? $2^y equiv 1 pmod{2^x - 1}$ . Replacing the? $1$ ?with a? $2^x$ ?and dividing out the powers of two should create an easy induction proof which will be left to the reader as an Exercise.

Consider? $n = 25$ . We will prove that this case is a counterexample via contradiction.

Because? $4 = 2^2$ , we will assume there exists a positive integer? $k$ ?such that? $2^{2^n} - 2^{2k}$ ?divides? $2^n - 1$ ?and? $2^{2k} < 2^n - 1$ . Dividing the powers of? $2$ ?from LHS gives? $2^{2^n - 2k} - 1$ ?divides? $2^n - 1$ . Hence,? $2^n - 2k$ ?divides? $n$ . Because? $n = 25$ ?is odd,? $2^{24} - k$ ?divides? $25$ . Euler's theorem gives? $2^{24} equiv 2^4 equiv 16 pmod{25}$ ?and so? $k ge 16$ . However,? $2^{2k} geq 2^{32} > 2^{25} - 1$ , a contradiction. Thus,? $n = 25$ ?is a valid counterexample.

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

Problem 5

Solution 1

First note that? $overline{Q_1 Q_2} parallel overline{AB}$ ?if and only if the altitudes from? $Q_1$ ?and? $Q_2$ ?to? $overline{AB}$ ?are the same, or? $|Q_1B|sin angle ABQ_1 =|Q_2A|sin angle BAQ_2$ . Similarly? $overline{Q_1 Q_2} parallel overline{CD}$ ?iff? $|Q_1C|sin angle DCQ_1 =|Q_2D|sin angle CDQ_2$ .

If we define? $S =frac{|Q_1B|sin angle ABQ_1}{|Q_2A|sin angle BAQ_2} times frac{|Q_2D|sin angle CDQ_2}{|Q_1C|sin angle DCQ_1}$ , then we are done if we can show that S=1.

By the law of sines,? $frac{|Q_1B|}{|Q_1C|}=frac{sinangle Q_1CB}{sinangle Q_1BC}$ ?and? $frac{|Q_2D|}{|Q_2A|}=frac{sinangle Q_2AD}{sinangle Q_2DA}$ .

So,? $S=frac{sin angle ABQ_1}{sin angle BAQ_2}cdotfrac{sin angle CDQ_2}{sin angle DCQ_1}cdotfrac{sin angle BCQ_1}{sin angle CBQ_1}cdotfrac{sin angle DAQ_2}{sin angle ADQ_2}$

By the terms of the problem,? $S=frac{sin angle PBC}{sin angle PAD}cdotfrac{sin angle PDA}{sin angle PCB}cdotfrac{sin angle PCD}{sin angle PBA}cdotfrac{sin angle PAB}{sin angle PDC}$ . (If two subangles of an angle of the quadrilateral are equal, then their complements at that quadrilateral angle are equal?as?well.)

Rearranging yields? $S= frac{sin angle PBC}{sin angle PCB}cdotfrac{sin angle PDA}{sin angle PAD}cdotfrac{sin angle PCD}{sin angle PDC}cdotfrac{sin angle PAB}{sin angle PBA}$ .

Applying the law of sines to the triangles with vertices at P yields? $S=frac{|PC|}{|PB|}frac{|PA|}{|PD|}frac{|PD|}{|PC|}frac{|PB|}{|PA|}=1$ .

Solution 2

Lemma. If? $AB$ ?and? $CD$ ?are not parallel, then? $AB, CD, Q_1 Q_2$ ?are concurrent.

Proof. Let? $AB$ ?and? $CD$ ?meet at? $R$ . Notice that with respect to triangle? $ADR$ ,? $P$ ?and? $Q_2$ ?are isogonal conjugates. With respect to triangle? $BCR$ ,? $P$ ?and? $Q_1$ ?are isogonal conjugates. Therefore,? $Q_1$ ?and? $Q_2$ ?lie on the reflection of? $RP$ ?in the angle bisector of? $angle{DRA}$ , so? $R, Q_1, Q_2$ ?are collinear. Hence,? $AB, CD, Q_1 Q_2$ ?are concurrent at? $R$ .

Now suppose? $Q_1 Q_2 parallel AB$ ?but? $Q_1 Q_2$ ?is not parallel to? $CD$ . Then? $AB$ ?and? $CD$ ?are not parallel and thus intersect at a point? $R$ . But then? $Q_1 Q_2$ also passes through? $R$ , contradicting? $Q_1 Q_2 parallel AB$ . A similar contradiction occurs if? $Q_1 Q_2 parallel CD$ ?but? $Q_1 Q_2$ ?is not parallel to? $CD$ , so we can conclude that? $Q_1 Q_2 parallel AB$ ?if and only if? $Q_1 Q_2 parallel CD$ .

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

Problem 6

Solution 1

Existence

Note that? $textstyle binom{11}3 = 165,$ ?and so it is natural to consider placing one element in each intersection of three of the 11 sets. Since each pair of sets is in 9 3-way intersections—one with each of the 9 remaining sets—any two sets will have 9 elements in common. Since? $textstyle binom{10}2 = 45,$ ?each set is in 45 triples and thus will have 45 elements. We can now throw in 60 more elements outside the union of the? $A_i$ ?and we are done.

Minimality

As?in the proof of PIE, let? $I$ ?be a finite set. Let? $textstyle U = bigcup_{iin I} A_i$ . For? $iin I$ , let? $chi_i$ ?be the?characteristic function?of? $A_i$ , that is, for? $alpha in U,$ $[chi_i(alpha) = begin{cases} 1 & alpha in A_i \ 0 & alpha notin A_i end{cases}]$

For each? $alpha in U$ ?let? $textstyle n_alpha = sum_{i in I} chi_i(alpha)$ , that is the number of subsets? $A_i$ ?of which? $alpha$ ?is an element.

If? $S subset I$ , let? $textstyle A_S = bigcap_{i in S}A_i$ . Then the characteristic function of? $A_S$ ?is? $textstyle prod_{i in S} chi_i$ . The number of elements of? $A_S$ ?is simply the sum of its characteristic function over all the elements of? $U$ : $[|A_S| = sum_{alpha in U} prod_{i in S} chi_i(alpha).]$ For? $0 le k le |I|$ , consider the sum? $N_k$ ?of? $|A_S|$ ?over all? $Ssubset I$ ?with? $|S|= k$ . This is: $[N_k = sum_{substack{Ssubset I\|S| = k}} sum_{alpha in U} prod_{i in S} chi_i(alpha) = sum_{substack{Ssubset I\|S| = k}} |A_S|]$ reversing the order summation,?as?an element? $alpha$ ?that appears in? $n_alpha$ ?of the? $A_i$ , will appear in exactly? $textstyle binom{n_alpha}{k}$ ?intersections of? $k$ ?subsets, we get: $[sum_{substack{Ssubset I\|S| = k}} |A_S| = sum_{alpha in U} sum_{substack{Ssubset I\|S| = k}} prod_{i in S} chi_i(alpha) = sum_{alpha in U} binom{n_alpha}k.]$

Applying the above with? $I = {1, 2, ldots, 11},$ ?and? $k=1$ , since each of the 11? $A_i$ ?has 45 elements, we get: $[N_1 = sum_{alpha in U} n_alpha = 11 cdot 45,]$ and for? $k = 2$ , since each of the 55 pairs? $A_i cap A_j$ ?has 9 elements, we get: $[N_2 = sum_{alpha in U} binom{n_alpha}2 = 9 cdot 55 = 11 cdot 45.]$

Therefore $begin{align*} s_1 &= sum_{alpha in U} n_alpha = N_1 = 11cdot45 \ s_2 &= sum_{alpha in U} n_alpha^2 = 2N_2 + N_1 = 3cdot11cdot45. end{align*}$ Let? $n = |U|$ ?be the number of elements of? $U$ . Since for any set of real numbers the mean value of the squares is greater than or equal to the square of the mean value, we have: $[frac{s_2}n ge left(frac{s_1}nright)^2 implies n ge frac{s_1^2}{s_2} = frac{11^2cdot 45^2}{3cdot11cdot45} = frac{11cdot45}3 = 165.]$

Thus? $|U| ge 165$ ?as?required.

Solution 2

We will count the number of ordered triples,? $(A_i,A_j,x)$ , where? $1le i,jle11$ ?and? $xin A_i cap A_j$ . We know this is equal to? $990=11cdot10cdot9$ -. We can also find that this is? $sum_{k=1}^{225}b_k^2-b_k$ , where? $b_k$ ?is the number of the? $11$ ?subsets the? $k^{text{th}}$ ?element of? $A$ ?is in. Since? $sum_{k=1}^{225}b_k=45cdot11=495$ , we know? $sum_{k=1}^{225}b_k^2=990+495=1485$ . Let? $n=|A_1 cup A_2 cup dots cup A_{11}|$ .? $n$ ?is equal to the number of? $b_k>0$ , where? $1le kle225$ . By the QM-AM inequality, we know? $frac{sum_{k=1}^{225}b_k^2}ngeBigg(frac{sum_{k=1}^{225}b_k}nBigg)^2impliesfrac{1485}ngeBig(frac{495}nBig)^2implies nge165$ ?and that equality occurs when? $b_1=b_2=b_3=cdots=b_{165}=3,b_{166}=b_{167}=cdots=b_{225}=0$ .? $square$