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

2011 USAJMO Problems真题及答案

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

2011 USAJMO Problems真题及答案

完整版真题免费下载

+答案解析请参考文末

Day 1

Problem 1

Find, with proof, all positive integers $n$ for which $2^n + 12^n + 2011^n$ is a perfect square.

Problem 2

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 3

For a point $P = (a,a^2)$ in the coordinate plane, let $ell(P)$ denote the line passing through $P$ with slope $2a$ . Consider the set of triangles with vertices of the form $P_1 = (a_1, a_1^2)$ , $P_2 = (a_2, a_2^2)$ , $P_3 = (a_3, a_3^2)$ , such that the intersections of the lines $ell(P_1)$ , $ell(P_2)$ , $ell(P_3)$ form an equilateral triangle $Delta$ . Find the locus of the center of $Delta$ as $P_1 P_2 P_3$ ranges over all such triangles.

Day 2

Problem 4

A word is defined as any finite string of letters. A word is a palindrome if it reads the same backwards as forwards. Let a sequence of words $W_0$ , $W_1$ , $W_2$ , $dots$ be defined as follows: $W_0 = a$ , $W_1 = b$ , and for $n ge 2$ , $W_n$ is the word formed by writing $W_{n - 2}$ followed by $W_{n - 1}$ . Prove that for any $n ge 1$ , the word formed by writing $W_1$ , $W_2$ , $dots$ , $W_n$ in succession is a palindrome.

Problem 5

Points $A$ , $B$ , $C$ , $D$ , $E$ lie on a circle $omega$ and point $P$ lies outside the circle. The given points are such that (i) lines $PB$ and $PD$ are tangent to $omega$ , (ii) $P$ , $A$ , $C$ are collinear, and (iii) $overline{DE} parallel overline{AC}$ . Prove that $overline{BE}$ bisects $overline{AC}$ .

Problem 6

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.

2011 USAJMO真题参考答案及详解

Problem 1

Solution 1

Let $2^n + 12^n + 2011^n = x^2$ . Then $(-1)^n + 1 equiv x^2 pmod {3}$ . Since all perfect squares are congruent to 0 or 1 modulo 3, this means that n must be odd. Proof by Contradiction: We wish to show that the only value of $n$ that satisfies is $n = 1$ . Assume that $n ge 2$ . Then consider the equation $2^n + 12^n = x^2 - 2011^n$ . From modulo 2, we easily know x is odd. Let $x = 2a + 1$ , where a is an integer. $2^n + 12^n = 4a^2 + 4a + 1 - 2011^n$ . Dividing by 4, $2^{n-2} + 3^n cdot 4^{n-1} = a^2 + a + dfrac {1}{4} (1 - 2011^n)$ . Since $n ge 2$ , $n-2 ge 0$ , so $2^{n-2}$ similarly, the entire LHS is an integer, and so are $a^2$ and $a$ . Thus, $dfrac {1}{4} (1 - 2011^n)$ must be an integer. Let $dfrac {1}{4} (1 - 2011^n) = k$ . Then we have $1- 2011^n = 4k$ . $1- 2011^n equiv 0 pmod {4}$ . $(-1)^n equiv 1 pmod {4}$ . Thus, n is even. However, it has already been shown that $n$ must be odd. This is a contradiction. Therefore, $n$ is not greater than or equal to 2, and must hence be less than 2. The only positive integer less than 2 is 1.

Solution 2

If $n = 1$ , then $2^n + 12^n + 2011^n = 2025 = 45^2$ , a perfect square.

If $n > 1$ is odd, then $2^n + 12^n + 2011^n equiv 0 + 0 + (-1)^n equiv 3 pmod{4}$ .

Since all perfect squares are congruent to $0,1 pmod{4}$ , we have that $2^n+12^n+2011^n$ is not a perfect square for odd $n > 1$ .

If $n = 2k$ is even, then $(2011^k)^2 < 2^{2k}+12^{2k}+2011^{2k}$ $= 4^k + 144^k + 2011^{2k} <$ $2011^k + 2011^k + 2011^{2k} < (2011^k+1)^2$ .

Since $(2011^k)^2 < 2^n+12^n+2011^n < (2011^k+1)^2$ , we have that $2^n+12^n+2011^n$ is not a perfect square for even $n$ .

Thus, $n = 1$ is the only positive integer for which $2^n + 12^n + 2011^n$ is a perfect square.

Solution 3

Looking at residues mod 3, we see that $n$ must be odd, since even values of $n$ leads to $2^n + 12^n + 2011^n = 2 pmod{3}$ . Also as shown in solution 2, for $n>1$ , $n$ must be even. Hence, for $n>1$ , $n$ can neither be odd nor even. The only possible solution is then $n=1$ , which indeed works.

Solution 4

Take the whole expression mod 12. Note that the perfect squares can only be of the form 0, 1, 4 or 9 (mod 12). Note that since the problem is asking for positive integers, $12^n$ is always divisible by 12, so this will be disregarded in this process. If $n$ is even, then $2^n equiv 4 pmod{12}$ and $2011^n equiv 7^n equiv 1 pmod {12}$ . Therefore, the sum in the problem is congruent to $5 pmod {12}$ , which cannot be a perfect square. Now we check the case for which $n$ is an odd number greater than 1. Then $2^n equiv 8 pmod{12}$ and $2011^n equiv 7^n equiv 7 pmod {12}$ . Therefore, this sum would be congruent to $3 pmod {12}$ , which cannot be a perfect square. The only case we have not checked is $n=1$ . If $n=1$ , then the sum in the problem is equal to $2+12+2011=2025=45^2$ . Therefore the only possible value of $n$ such that $2^n+12^n+2011^n$ is a perfect square is $n=1$ .

Problem 2

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]$

Problem 3

Solution 1

Note that all the points $P=(a,a^2)$ belong to the parabola $y=x^2$ which we will denote $p$ . This parabola has a focus $F=left(0,frac{1}{4}right)$ and directrix $y=-frac{1}{4}$ which we will denote $d$ . We will prove that the desired locus is $d$ .

First note that for any point $P$ on $p$ , the line $ell(P)$ is the tangent line to $p$ at $P$ . This is because $ell(P)$ contains $P$ and because $[frac{d}{dx}] x^2=2x$ . If you don't like calculus, you can also verify that $ell(P)$ has equation $y=2a(x-a)+a^2$ and does not intersect $y=x^2$ at any point besides $P$ . Now for any point $P$ on $p$ let $P'$ be the foot of the perpendicular from $P$ onto $d$ . Then by the definition of parabolas, $PP'=PF$ . Let $q$ be the perpendicular bisector of $overline{P'F}$ . Since $PP'=PF$ , $q$ passes through $P$ . Suppose $K$ is any other point on $q$ and let $K'$ be the foot of the perpendicular from $K$ to $d$ . Then in right $Delta KK'P'$ , $KK'$ is a leg and so $KK'<KP'=KF$ . Therefore $K$ cannot be on $p$ . This implies that $q$ is exactly the tangent line to $p$ at $P$ , that is $q=ell(P)$ . So we have proved Lemma 1: If $P$ is a point on $p$ then $ell(P)$ is the perpendicular bisector of $overline{P'F}$ .

We need another lemma before we proceed. Lemma 2: If $F$ is on the circumcircle of $Delta XYZ$ with orthocenter $H$ , then the reflections of $F$ across $overleftrightarrow{XY}$ , $overleftrightarrow{XZ}$ , and $overleftrightarrow{YZ}$ are collinear with $H$ .

Proof of Lemma 2: Say the reflections of $F$ and $H$ across $overleftrightarrow{YZ}$ are $C'$ and $J$ , and the reflections of $F$ and $H$ across $overleftrightarrow{XY}$ are $A'$ and $I$ . Then we angle chase $angle JYZ=angle HYZ=angle HXZ=angle JXZ=m(JZ)/2$ where $m(JZ)$ is the measure of minor arc $JZ$ on the circumcircle of $Delta XYZ$ . This implies that $J$ is on the circumcircle of $Delta XYZ$ , and similarly $I$ is on the circumcircle of $Delta XYZ$ . Therefore $angle C'HJ=angle FJH=m(XF)/2$ , and $angle A'HX=angle FIX=m(FX)/2$ . So $angle C'HJ = angle A'HX$ . Since $J$ , $H$ , and $X$ are collinear it follows that $C'$ , $H$ and $A'$ are collinear. Similarly, the reflection of $F$ over $overleftrightarrow{XZ}$ also lies on this line, and so the claim is proved.

Now suppose $A$ , $B$ , and $C$ are three points of $p$ and let $ell(A)capell(B)=X$ , $ell(A)capell(C)=Y$ , and $ell(B)capell(C)=Z$ . Also let $A''$ , $B''$ , and $C''$ be the midpoints of $overline{A'F}$ , $overline{B'F}$ , and $overline{C'F}$ respectively. Then since $overleftrightarrow{A''B''}parallel overline{A'B'}=d$ and $overleftrightarrow{B''C''}parallel overline{B'C'}=d$ , it follows that $A''$ , $B''$ , and $C''$ are collinear. By Lemma 1, we know that $A''$ , $B''$ , and $C''$ are the feet of the altitudes from $F$ to $overline{XY}$ , $overline{XZ}$ , and $overline{YZ}$ . Therefore by the Simson Line Theorem, $F$ is on the circumcircle of $Delta XYZ$ . If $H$ is the orthocenter of $Delta XYZ$ , then by Lemma 2, it follows that $H$ is on $overleftrightarrow{A'C'}=d$ . It follows that the locus described in the problem is a subset of $d$ .

Since we claim that the locus described in the problem is $d$ , we still need to show that for any choice of $H$ on $d$ there exists an equilateral triangle with center $H$ such that the lines containing the sides of the triangle are tangent to $p$ . So suppose $H$ is any point on $d$ and let the circle centered at $H$ through $F$ be $O$ . Then suppose $A$ is one of the intersections of $d$ with $O$ . Let $angle HFA=3theta$ , and construct the ray through $F$ on the same halfplane of $overleftrightarrow{HF}$ as $A$ that makes an angle of $2theta$ with $overleftrightarrow{HF}$ . Say this ray intersects $O$ in a point $B$ besides $F$ , and let $q$ be the perpendicular bisector of $overline{HB}$ . Since $angle HFB=2theta$ and $angle HFA=3theta$ , we have $angle BFA=theta$ . By the inscribed angles theorem, it follows that $angle AHB=2theta$ . Also since $HF$ and $HB$ are both radii, $Delta HFB$ is isosceles and $angle HBF=angle HFB=2theta$ . Let $P_1'$ be the reflection of $F$ across $q$ . Then $2theta=angle FBH=angle C'HB$ , and so $angle C'HB=angle AHB$ . It follows that $P_1'$ is on $overleftrightarrow{AH}=d$ , which means $q$ is the perpendicular bisector of $overline{FP_1'}$ .

Let $q$ intersect $O$ in points $Y$ and $Z$ and let $X$ be the point diametrically opposite to $B$ on $O$ . Also let $overline{HB}$ intersect $q$ at $M$ . Then $HM=HB/2=HZ/2$ . Therefore $Delta HMZ$ is a $30-60-90$ right triangle and so $angle ZHB=60^{circ}$ . So $angle ZHY=120^{circ}$ and by the inscribed angles theorem, $angle ZXY=60^{circ}$ . Since $ZX=ZY$ it follows that $Delta ZXY$ is and equilateral triangle with center $H$ .

By Lemma 2, it follows that the reflections of $F$ across $overleftrightarrow{XY}$ and $overleftrightarrow{XZ}$ , call them $P_2'$ and $P_3'$ , lie on $d$ . Let the intersection of $overleftrightarrow{YZ}$ and the perpendicular to $d$ through $P_1'$ be $P_1$ , the intersection of $overleftrightarrow{XY}$ and the perpendicular to $d$ through $P_2'$ be $P_2$ , and the intersection of $overleftrightarrow{XZ}$ and the perpendicular to $d$ through $P_3'$ be $P_3$ . Then by the definitions of $P_1'$ , $P_2'$ , and $P_3'$ it follows that $FP_i=P_iP_i'$ for $i=1,2,3$ and so $P_1$ , $P_2$ , and $P_3$ are on $p$ . By lemma 1, $ell(P_1)=overleftrightarrow{YZ}$ , $ell(P_2)=overleftrightarrow{XY}$ , and $ell(P_3)=overleftrightarrow{XZ}$ . Therefore the intersections of $ell(P_1)$ , $ell(P_2)$ , and $ell(P_3)$ form an equilateral triangle with center $H$ , which finishes the proof. --Killbilledtoucan

Solution 2

Note that the lines $l(P_1), l(P_2), l(P_3)$ are $[y=2a_1x-a_1^2, y=2a_2x-a_2^2, y=2a_3x-a_3^2,]$ respectively. It is easy to deduce that the three points of intersection are $[left(frac{a_1+a_2}{2},a_1a_2right),left(frac{a_2+a_3}{2},a_2a_3right), left(frac{a_3+a_1}{2},a_3a_1right).]$ The slopes of each side of this equilateral triangle are $[2a_1,2a_2,2a_3,]$ and we want to find the locus of $[left(frac{a_1+a_2+a_3}{3},frac{a_1a_2+a_2a_3+a_3a_1}{3}right).]$ We know that $[2a_1=tan(theta), 2a_2=tan (theta + 120), 2a_3=tan (theta-120)]$ for some $theta.$ Therefore, we can use the tangent addition formula to deduce $[frac{a_1+a_2+a_3}{3}=frac{tan(theta)+tan (theta + 120)+tan (theta-120)}{6}=frac{3tantheta-tan^3theta}{2-6tan^2theta}]$ and $begin{align*} frac{a_1a_2+a_2a_3+a_3a_1}{3}&=frac{tantheta (tan(theta-120)+tan(theta+120))+tan(theta-120)tan(theta+120)}{12} &=frac{9tan^2theta-3}{12(1-3tan^2theta)} &=-frac{1}{4}.end{align*}$ Now we show that $frac{a_1+a_2+a_3}{3}$ can be any real number. Let's say $[frac{3tantheta-tan^3theta}{2-6tan^2theta}=k]$ for some real number $k.$ Multiplying both sides by $2-tan^2theta$ and rearranging yields a cubic in $tantheta.$ Clearly this cubic has at least one real solution. As $tan theta$ can take on any real number, all values of $k$ are possible, and our answer is the line $[boxed{y=-frac{1}{4}.}]$ Of course, as the denominator could equal 0, we must check $tan theta=pm frac{1}{sqrt{3}}.$ $[3tan theta-tan^3theta=k(2-6tan^2theta).]$ The left side is nonzero, while the right side is zero, so these values of $theta$ do not contribute to any values of $k.$ So, our answer remains the same.

Problem 4

Solution

Let $r$ be the reflection function on the set of words, namely $r(a_1dots a_n) = a_n dots a_1$ for all words $a_1 dots a_n$ , $nge 1$ . Then the following property is evident (e.g. by mathematical induction):

$r(w_1 dots w_k) = r(w_k) dots r(w_1)$ , for any words $w_1, dots, w_k$ , $k ge 1$ .

a, b, ab, bab, We use mathematical induction to prove the statement of the problem. First, $W_1 = b$ , $W_1W_2 = bab$ , $W_1W_2W_3 = babbab$ are palindromes. Second, suppose $nge 3$ , and that the words $W_1 W_2 dots W_k$ ( $k = 1$ , $2$ , $dots$ , $n$ ) are all palindromes, i.e. $r(W_1W_2dots W_k) = W_1W_2dots W_k$ . Now, consider the word $W_1 W_2 dots W_{n+1}$ :

$[r(W_1 W_2 dots W_{n+1}) = r(W_{n+1}) r(W_1 W_2 dots W_{n-2}W_{n-1}W_n)]$

$[= r(W_{n-1}W_n) W_1 W_2 dots W_{n-2} W_{n-1} W_n]$

$[= r(W_{n-1}W_n) r(W_1 W_2 dots W_{n-2}) W_{n+1}]$

$[= r(W_1 W_2 dots W_{n-2} W_{n-1}W_n) W_{n+1}]$

$[= W_1W_2dots W_n W_{n+1}.]$

By the principle of mathematical induction, the statement of the problem is proved.

Problem 5

Solution 1

Let $O$ be the center of the circle, and let $X$ be the intersection of $AC$ and $BE$ . Let $angle OPA$ be $x$ and $angle OPD$ be $y$ .

$angle OPB = angle OPD = y$ , $angle BED = frac{angle DOB}{2} = 90-y$ , $angle ODE = angle PDE - 90 = 90-x-y$ $angle OBE = angle PBE - 90 = x = angle OPA$

Thus $PBXO$ is a cyclic quadrilateral and $angle OXP = angle OBP = 90$ and so $X$ is the midpoint of chord $AC$ .

~pandadude

Solution 2

Let $O$ be the center of the circle, and let $M$ be the midpoint of $AC$ . Let $theta$ denote the circle with diameter $OP$ . Since $angle OBP = angle OMP = angle ODP = 90^circ$ , $B$ , $D$ , and $M$ all lie on $theta$ .

$[asy] import graph; unitsize(2 cm); pair A, B, C, D, E, M, O, P; path circ; O = (0,0); circ = Circle(O,1); B = dir(100); D = dir(240); P = extension(B, B + rotate(90)*(B), D, D + rotate(90)*(D)); C = dir(-40); A = intersectionpoint((P--(P + 0.9*(C - P))),circ); E = intersectionpoint((D + 0.1*(C - A))--(D + C - A),circ); M = (A + C)/2; draw(circ); draw(P--B); draw(P--D); draw(P--C); draw(B--E); draw(D--E); draw(O--B); draw(O--D); draw(O--M); draw(O--P); draw(Circle((O + P)/2, abs(O - P)/2),dashed); draw(D--M); dot("$A$", A, NE); dot("$B$", B, NE); dot("$C$", C, SE); dot("$D$", D, S); dot("$E$", E, S); dot("$M$", M, NE); dot("$O$", O, dir(0)); dot("$P$", P, W); label("$theta$", (O + P)/2 + abs(O - P)/2*dir(120), NW); [/asy]$

Since quadrilateral $BOMP$ is cyclic, $angle BMP = angle BOP$ . Triangles $BOP$ and $DOP$ are congruent, so $angle BOP = angle BOD/2 = angle BED$ , so $angle BMP = angle BED$ . Because $AC$ and $DE$ are parallel, $M$ lies on $BE$ (using Euclid's Parallel Postulate).

Solution 3

Note that by Lemma 9.9 of EGMO, $(A,C;B,D)$ is a harmonic bundle. We project through $E$ onto $overline{AC}$ , $[-1=(A,C;B,D)stackrel{E}{=}(A,C;M,P_{infty})]$ Where $P_{infty}$ is the point at infinity for parallel lines $overline{DE}$ and $overline{AC}$ . Thus, we get $frac{MA}{MC}=-1$ , and $M$ is the midpoint of $AC$ .

Solution 4

Connet segment PO, and name the interaction of PO and the circle as point M.

Since PB and PD are tangent to the circle, it's easy to see that M is the midpoint of arc BD.

∠ BOA = 1/2 arc AB + 1/2 arc CE

Since AC // DE, arc AD = arc CE,

thus, ∠ BOA = 1/2 arc AB + 1/2 arc AD = 1/2 arc BD = arc BM = ∠ BOM

Therefore, PBOM is cyclic, ∠ PFO = ∠ OBP = 90°, AF = AC (F is the interaction of BE and AC)

BE bisects AC, proof completed!

Problem 6

Solution

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.