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

2016 USAMO Problems真题及答案

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

2016 USAMO Problems真题及答案

完整版真题免费下载

+答案解析请参考文末

Day 1

Problem 1

Let $X_1, X_2, ldots, X_{100}$ be a sequence of mutually distinct nonempty subsets of a set $S$ . Any two sets $X_i$ and $X_{i+1}$ are disjoint and their union is not the whole set $S$ , that is, $X_icap X_{i+1}=emptyset$ and $X_icup X_{i+1}neq S$ , for all $iin{1, ldots, 99}$ . Find the smallest possible number of elements in $S$ .

Problem 2

Prove that for any positive integer $k,$ $[left(k^2right)!cdotprod_{j=0}^{k-1}frac{j!}{left(j+kright)!}]$ is an integer.

Problem 3

Let $triangle ABC$ be an acute triangle, and let $I_B, I_C,$ and $O$ denote its $B$ -excenter, $C$ -excenter, and circumcenter, respectively. Points $E$ and $Y$ are selected on $overline{AC}$ such that $angle ABY = angle CBY$ and $overline{BE}perpoverline{AC}.$ Similarly, points $F$ and $Z$ are selected on $overline{AB}$ such that $angle ACZ = angle BCZ$ and $overline{CF}perpoverline{AB}.$

Lines $overleftrightarrow{I_B F}$ and $overleftrightarrow{I_C E}$ meet at $P.$ Prove that $overline{PO}$ and $overline{YZ}$ are perpendicular.

Day 2

Problem 4

Find all functions $f:mathbb{R}rightarrow mathbb{R}$ such that for all real numbers $x$ and $y$ , $[(f(x)+xy)cdot f(x-3y)+(f(y)+xy)cdot f(3x-y)=(f(x+y))^2.]$

Problem 5

An equilateral pentagon $AMNPQ$ is inscribed in triangle $ABC$ such that $Minoverline{AB},$ $Qinoverline{AC},$ and $N, Pinoverline{BC}.$ Let $S$ be the intersection of $overleftrightarrow{MN}$ and $overleftrightarrow{PQ}.$ Denote by $ell$ the angle bisector of $angle MSQ.$

Prove that $overline{OI}$ is parallel to $ell,$ where $O$ is the circumcenter of triangle $ABC,$ and $I$ is the incenter of triangle $ABC.$

Problem 6

Integers $n$ and $k$ are given, with $nge kge 2.$ You play the following game against an evil wizard.

The wizard has $2n$ cards; for each $i = 1, ..., n,$ there are two cards labeled $i.$ Initially, the wizard places all cards face down in a row, in unknown order.

You may repeatedly make moves of the following form: you point to any $k$ of the cards. The wizard then turns those cards face up. If any two of the cards match, the game is over and you win. Otherwise, you must look away, while the wizard arbitrarily permutes the $k$ chosen cards and turns them back face-down. Then, it is your turn again.

We say this game is $textit{winnable}$ if there exist some positive integer $m$ and some strategy that is guaranteed to win in at most $m$ moves, no matter how the wizard responds.

For which values of $n$ and $k$ is the game winnable?

2016USAMO真题参考答案及详解

Problem 1

Solution 1

The answer is that $|S| ge 8$ .

First, we provide a inductive construction for $S = left{ 1, dots, 8 right}$ . Actually, for $n ge 4$ we will provide a construction for $S = left{ 1, dots, n right}$ which has $2^{n-1} + 1$ elements in a line. (This is sufficient, since we then get $129$ for $n = 8$ .) The idea is to start with the following construction for $|S| = 4$ : $[begin{array}{ccccccccc} 34 & 1 & 23 & 4 & 12 & 3 & 14 & 2 & 13 end{array}.]$ Then inductively, we do the following procedure to move from $n$ to $n+1$ : take the chain for $n$ elements, delete an element, and make two copies of the chain (which now has even length). Glue the two copies together, joined by $varnothing$ in between. Then place the element $n+1$ in alternating positions starting with the first (in particular, this hits $n+1$ ). For example, the first iteration of this construction gives: $[begin{array}{ccccccccc} 345 & 1 & 235 & 4 & 125 & 3 & 145 & 2 & 5 \ 34 & 15 & 23 & 45 & 12 & 35 & 14 & 25 & end{array}]$ Now let's check $|S| ge 8$ is sufficient. Consider a chain on a set of size $|S| = 7$ . (We need $|S| ge 7$ else $2^{|S|} < 100$ .) Observe that there are sets of size $ge 4$ can only be neighbored by sets of size $le 2$ , of which there are $binom 71 + binom 72 = 28$ . So there are $le 30$ sets of size $ge 4$ . Also, there are $binom 73 = 35$ sets of size $3$ . So the total number of sets in a chain can be at most $30 + 28 + 35 = 93 < 100$ .

Solution 2

My proof that $|S|ge 8$ is basically the same as the one above. Here is another construction for $|S| = 8$ that I like because it works with remainders and it's pretty intuitive. The basic idea is to assign different subsets to different remainders when divided by particular numbers, and then to use the Chinese Remainder Theorem to show that all of the subsets are distinct. The motivation for this comes from the fact that we want $X_i$ and $X_{i+1}$ to always be disjoint, so remainders are a great way to systematically make that happen, since $i$ and $i+1$ do not have the same remainder modulo any positive integer greater than $1.$ Anyway, here is the construction:

Let $S = left{ {1, 2, ..., 8} right}.$ For $i = 1, 2, ..., 98,$ we will choose which elements of the set $left{ {1, 2, 3, 4} right}$ belong to $X_i$ based on the remainder of $i$ modulo $9,$ and we will choose which elements of the set $left{ {5, 6, 7, 8} right}$ belong to $X_i$ based on the remainder of $i$ modulo $11.$ We do this asfollows: $[X_icapleft{ {1, 2, 3, 4} right} = begin{array}{ll} emptyset & iequiv 0 text{ (mod } 9text{)} \ left{ {1, 2} right} & iequiv 1 text{ (mod } 9text{)} \ left{ {3} right} & iequiv 2 text{ (mod } 9text{)} \ left{ {1, 4} right} & iequiv 3 text{ (mod } 9text{)} \ left{ {2} right} & iequiv 4 text{ (mod } 9text{)} \ left{ {3, 4} right} & iequiv 5 text{ (mod } 9text{)} \ left{ {1} right} & iequiv 6 text{ (mod } 9text{)} \ left{ {2, 3} right} & iequiv 7 text{ (mod } 9text{)} \ left{ {4} right} & iequiv 8 text{ (mod } 9text{)} \ end{array}]$ $[X_icapleft{ {5, 6, 7, 8} right} = begin{array}{ll} emptyset & iequiv 0 text{ (mod } 11text{)} \ left{ {5, 6} right} & iequiv 1 text{ (mod } 11text{)} \ left{ {7, 8} right} & iequiv 2 text{ (mod } 11text{)} \ left{ {5} right} & iequiv 3 text{ (mod } 11text{)} \ left{ {6, 8} right} & iequiv 4 text{ (mod } 11text{)} \ left{ {5, 7} right} & iequiv 5 text{ (mod } 11text{)} \ left{ {6} right} & iequiv 6 text{ (mod } 11text{)} \ left{ {5, 8} right} & iequiv 7 text{ (mod } 11text{)} \ left{ {6, 7} right} & iequiv 8 text{ (mod } 11text{)} \ left{ {8} right} & iequiv 9 text{ (mod } 11text{)} \ left{ {7} right} & iequiv 10 text{ (mod } 11text{)} \ end{array}]$ Finally, we specially define $X_{99} = left{ {1, 2, 3} right}$ and $X_{100} = left{ {5, 6, 7} right}.$

It is relatively easy to see that this configuration satisfies all of the desired conditions. We see that $X_{98} = left{ {4, 7} right},$ so $X_{98}$ and $X_{99}$ are disjoint, as are $X_{99}$ and $X_{100}.$ The remainder configuration above takes care of the rest, so any two consecutive sets are disjoint. Then, by the Chinese Remainder Theorem, no two integers from $1$ to $98$ have the same combination of residues modulo $9$ and modulo $11,$ so all of the sets $X_i$ are distinct for $i = 1, 2, ..., 98.$ It is also easy to verify that none of these match $X_{99}$ or $X_{100},$ since they all have at most two elements of $left{ {1, 2, 3, 4} right}$ and at most two elements of $left{ {5, 6, 7, 8} right},$ whereas $X_{99}$ and $X_{100}$ do not satisfy this; hence all of the sets are distinct. Finally, notice that, for any pair of consecutive sets, at least one of them has at most $3$ elements, while the other has at most $4.$ Thus, their union always has at most $7$ elements, so $X_icup X_{i+1}neq S$ for all $i = 1, 2, ..., 99.$

All of the conditions are satisfied, so this configuration works. We thus conclude that $text{min}left(left|Sright|right) = 8.$

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

Problem 2

Solution 1

Define $v_p(N)$ for all rational numbers $N$ and primes $p$ , where if $N=frac{x}{y}$ , then $v_p(N)=v_p(x)-v_p(y)$ , and $v_p(x)$ is the greatest power of $p$ that divides $x$ for integer $x$ . Note that the expression(that we're trying to prove is an integer) is clearly rational, call it $N$ .

$v_p(N)=sum_{i=1}^infty leftlfloor frac{k^{2}}{p^{i}} rightrfloor+sum_{j=0}^{k-1} sum_{i=1}^infty leftlfloor frac{j}{p^{i}}rightrfloor-sum_{j=k}^{2k-1} sum_{i=1}^infty leftlfloor frac{j}{p^{i}} rightrfloor$ , by Legendre. Clearly, $leftlfloor{frac{x}{p}}rightrfloor={frac{x-r(x,p)}{p}}$ , and $sum_{i=0}^{k-1} r(i,m)leq sum_{i=k}^{2k-1} r(i,m)$ , where $r(i,m)$ is the remainder function(we take out groups of $m$ which are just permutations of numbers $1$ to $m$ until there are less than $m$ left, then we have $m$ distinct values, which the minimum sum is attained at $0$ to $k-1$ ). Thus, $v_p(N)=sum_{m=p^{i}, iin mathbb{N}_{+}}-frac{k^{2}}{m}+leftlfloor{frac{k^{2}}{m}}rightrfloor-frac{sum_{i=0}^{k-1} r(i,m)-sum_{i=k}^{2k-1} r(i,m)}{m} geq sum_{m=p^{i}, iin mathbb{N}} leftlceil -frac{k^{2}}{m}+lfloor{frac{k^{2}}{m}}rfloorrightrceil geq 0$ , as the term in each summand is a sum of floors also and is clearly an integer.

Solution 2 (Controversial)

Consider an $ktimes k$ grid, which is to be filled with the integers $1$ through $k^2$ such that the numbers in each row are in increasing order from left to right, and such that the numbers in each column are in increasing order from bottom to top. In other words, we are creating an $ktimes k$ standard Young tableaux.

The Hook Length Formula is the source of the controversy, as it is very powerful and trivializes this problem. The Hook Length Formula states that the number of ways to create this standard Young tableaux (call this $N$ for convenience) is: $[N = frac{left(k^2right)!}{prod_{1le i, jle k}(i+j-1)}.]$ Now, we do some simple rearrangement: $[N = left(k^2right)!cdotprod_{j=1}^{k}prod_{i=1}^{k}frac{1}{i+j-1} = left(k^2right)!cdotprod_{j=1}^{k}frac{left(j-1right)!}{left(j+k-1right)!}]$ $[= left(k^2right)!cdotprod_{j=0}^{k-1}frac{j!}{left(j+kright)!}.]$ This is exactly the expression given in the problem! Since the expression given in the problem equals the number of distinct $ktimes k$ standard Young tableaux, it must be an integer, so we are done.

Problem 3

Solution

This problem can be proved in the following two steps.

1. Let $I_A$ be the $A$ -excenter, then $I_A,O,$ and $P$ are colinear. This can be proved by the Trigonometric Form of Ceva's Theorem for $triangle I_AI_BI_C.$

2. Show that $I_AY^2-I_AZ^2=OY^2-OZ^2,$ which implies $overline{OI_A}perpoverline{YZ}.$ This can be proved by multiple applications of the Pythagorean Thm.

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

Problem 4

Solution 1

Step 1: Set $x = y = 0$ to obtain $f(0) = 0.$

Step 2: Set $x = 0$ to obtain $f(y)f(-y) = f(y)^2.$

$indent$ In particular, if $f(y) ne 0$ then $f(y) = f(-y).$

$indent$ In addition, replacing $y to -t$ , it follows that $f(t) = 0 implies f(-t) = 0$ for all $t in mathbb{R}.$

Step 3: Set $x = 3y$ to obtain $left[f(y) + 3y^2right]f(8y) = f(4y)^2.$

$indent$ In particular, replacing $y to t/8$ , it follows that $f(t) = 0 implies f(t/2) = 0$ for all $t in mathbb{R}.$

Step 4: Set $y = -x$ to obtain $f(4x)left[f(x) + f(-x) - 2x^2right] = 0.$

$indent$ In particular, if $f(x) ne 0$ , then $f(4x) ne 0$ by the observation from Step 3, because $f(4x) = 0 implies f(2x) = 0 implies f(x) = 0.$ Hence, the above equation implies that $2x^2 = f(x) + f(-x) = 2f(x)$ , where the last step follows from the first observation from Step 2.

$indent$ Therefore, either $f(x) = 0$ or $f(x) = x^2$ for each $x.$

$indent$ Looking back on the equation from Step 3, it follows that $f(y) + 3y^2 ne 0$ for any nonzero $y.$ Therefore, replacing $y to t/4$ in this equation, it follows that $f(t) = 0 implies f(2t) = 0.$

Step 5: If $f(a) = f(b) = 0$ , then $f(b - a) = 0.$

$indent$ This follows by choosing $x, y$ such that $x - 3y = a$ and $3x - y = b.$ Then $x + y = tfrac{b - a}{2}$ , so plugging $x, y$ into the given equation, we deduce that $fleft(tfrac{b - a}{2}right) = 0.$ Therefore, by the third observation from Step 4, we obtain $f(b - a) = 0$ , as desired.

Step 6: If $f notequiv 0$ , then $f(t) = 0 implies t = 0.$

$indent$ Suppose by way of contradiction that there exists an nonzero $t$ with $f(t) = 0.$ Choose $x, y$ such that $f(x) ne 0$ and $x + y = t.$ The following three facts are crucial:

$indent$ 1. $f(y) ne 0.$ This is because $(x + y) - y = x$ , so by Step 5, $f(y) = 0 implies f(x) = 0$ , impossible.

$indent$ 2. $f(x - 3y) ne 0.$ This is because $(x + y) - (x - 3y) = 4y$ , so by Step 5 and the observation from Step 3, $f(x - 3y) = 0 implies f(4y) = 0 implies f(2y) = 0 implies f(y) = 0$ , impossible.

$indent$ 3. $f(3x - y) ne 0.$ This is because by the second observation from Step 2, $f(3x - y) = 0 implies f(y - 3x) = 0.$ Then because $(x + y) - (y - 3x) = 4x$ , Step 5 together with the observation from Step 3 yield $f(3x - y) = 0 implies f(4x) = 0 implies f(2x) = 0 implies f(x) = 0$ , impossible.

$indent$ By the second observation from Step 4, these three facts imply that $f(y) = y^2$ and $f(x - 3y) = left(x - 3yright)^2$ and $f(3x - y) = left(3x - yright)^2.$ By plugging into the given equation, it follows that $begin{align*} left(x^2 + xyright)left(x - 3yright)^2 + left(y^2 + xyright)left(3x - yright)^2 = 0. end{align*}$ But the above expression miraculously factors into $left(x + yright)^4$ ! This is clearly a contradiction, since $t = x + y ne 0$ by assumption. This completes Step 6.

Step 7: By Step 6 and the second observation from Step 4, the only possible solutions are $f equiv 0$ and $f(x) = x^2$ for all $x in mathbb{R}.$ It's easy to check that both of these work, so we're done.

Alternative Solution 1

From steps 1 and 2 of Solution 1 we have that $f(0)=0$ , and $f(-y) cdot f(y)=(f(y))^2$ . Therefore, if $f(y) ne 0$ , then $f(y)=f(-y)$ . Furthermore, setting $y=-x$ gives us $(f(x)-x^2) cdot f(4x) + (f(-x)-x^2) cdot f(4x) = f(0) = 0$ . The LHS can be factored as $(f(x)+f(-x)-2x^2) cdot f(4x) = 0$ . In particular, if $f(4x) ne 0$ , then we have $f(x)+f(-x)=2x^2$ . However, since we have from step 2 that $f(x)=f(-x)$ , assuming $f(x) ne 0$ , the equation becomes $2f(x)=2x^2$ , so for every $x$ , $f(x)$ is equivalent to either $0$ or $x^2$ . From step 6 of Solution 1, we can prove that $f(x)=0$ , and $f(x)=x^2$ are the only possible solutions.

Solution 2

Step 1: $x=y=0 implies f(0)=0$

Step 2: $x=0 implies f(y)f(-y)=f(y)^{2}$ . Now, assume $y not = 0$ . Then, if $f(y)=0$ , we substitute in $-y$ to get $f(y)f(-y)=f(-y)^{2}$ , or $f(y)=f(-y)=0$ . Otherwise, we divide both sides by $f(y)$ to get $f(y)=f(-y)$ . If $y=0$ , we obviously have $f(0)=f(0)$ . Thus, the function is even. . Step 3: $y=-x implies 2f(4x)(f(x)-x^{2})=0$ . Thus, $forall x$ , we have $f(4x)=0$ or $f(x)=x^{2}$ .

Step 4: We now assume $f(x) not = 0$ , $xnot = 0$ . We have $f(frac{x}{4})=frac{x^{2}}{16}$ . Now, setting $x=y=frac{x}{4}$ , we have $f(frac{x}{2}=frac{x^{2}}{4}$ or $f(frac{x}{2})=0$ . The former implies that $f(x)=0$ or $x^{2}$ . The latter implies that $f(x)=0$ or $f(x)=frac{x^{2}}{2}$ . Assume the latter. $y=-2x implies -frac{3y^{2}}{2}f(7y)-{2y^{2}}f(5y)=frac{x^{2}}{2}$ . Clearly, this implies that $f(x)$ is negative for some $m$ . Now, we have $f(frac{m}{4})=frac{m^{2}}{16} implies f(frac{m}{2})=0,frac{m^{2}}{4} implies f(m) geq 0$ , which is a contradiction. Thus, $forall x$ $f(x)=0$ or $f(x)=x^{2}$ .

Step 5: We now assume $f(x)=0$ , $f(y)=y^{2}$ for some $x,y not = 0$ . Let $m$ be sufficiently large integer, let $z=|4^{m}x|$ and take the absolute value of $y$ (since the function is even). Choose $c$ such that $3z-c=y$ . Note that we have $frac{c}{z}$ ~ $3$ and $frac{y}{z}$ ~ $0$ . Note that $f(z)=0$ . Now, $x=z, y=c implies$ LHS is positive, as the second term is positive and the first term is nonnegative and thus the right term is equal to $(z+c)^{4}$ ~ $256z^{4}$ . Now if $f(z-3c)=0$ , the second term of the LHS/RHS clearly ~0 as $m to infty$ . if $f(z-3c)=0$ , then we have LHS/RHS ~ $0$ , otherwise, we have LHS/RHS~ $frac{8^{2}cdot 3z^{4}}{256z^{4}}$ ~ $frac{3}{4}$ , a contradiction, as we're clearly not dividing by $0$ , and we should have LHS/RHS=1.

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

Problem 5

Solution 1

Let $D$ be the intersection of line $AI$ and the circumcircle of $Delta ABC$ (other than $A$ ), then $ODperp BC$ . Let $R$ be the point such that $NPQR$ is a rhombus. It follows that $ODperp QR$ .

Since $AM=AQ$ , $AIperp MQ$ , or $DIperp MQ$ . It follows that $angle ODI=angle RQM$ .

Since $BO=OD$ , $MA=AQ$ , $angle BOD=angle MAQ$ , it follows that $Delta BODsimDelta MAQ$ , so $AQ/MQ=OD/BD$ .

It is given that $AQ=NP=RQ$ , and by basic properties of the incenter, $ID=BD$ . Therefore, $RQ/MQ=OD/ID$ , so $Delta RQMsimDelta ODI$ . Since the rotation between the two triangles in 90 degrees, $OIperp MR$ . However, $l$ is parallel to the bisector of $MNR$ , which is perpendicular to $MR$ , so we are done.

Solution 2

Write $angle{JKL} = K$ for all $J,K,L$ chosen as distinct vertices of triangle $ABC$ . Define $a, b, c$ as sides opposite to angles $A, B$ , and $C$ , respectively. Place the triangle in the Euclidean plane with $A$ at the origin and $C$ on the positive x-axis. Assume without loss of generality that C is acute.

Consider the sides of the pentagon as vectors and note that $[overrightarrow{AM} + overrightarrow{MN} + overrightarrow{NP} = overrightarrow{AQ} + overrightarrow{QP} qquad (1)]$

Define $delta$ and $gamma$ as the angles made between the positive x-axis and $overrightarrow{MN}$ and $overrightarrow{QP}$ , respectively. Considering the x and y coordinates of the vectors in $(1)$ , it follows that $[cos delta - cos gamma = 1 - cos A - cos C qquad (2)]$ $[sin delta - sin gamma = sin C - sin A qquad (3)]$

Suppose $sin C - sin A = 0$ . Then $A = C$ , and the triangle is isosceles. In this case, it is clear by symmetry that $overline{OI}$ is vertical. Further, since point $S$ exists, $delta neq gamma$ , so $delta + gamma = 180$ and $overrightarrow{MN} + overrightarrow{QP}$ must be vertical as well.

For the remainder of the proof, assume $sin C neq sin A$ . Note that $[frac{cos y – cos x}{sin x - sin y} = frac{ (cos y - cos x)(sin x + sin y)}{ (sin x - sin y)(sin x + sin y)} = frac {sin x + sin y}{cos x + cos y}]$ whenever $x, y in mathbb{R}$ and $sin x neq sin y$ . Note further that the slope of the line defined by the vector formed by summing vectors $(cos x, sin x)$ and $(cos y, sin y)$ is this expression. Since $ell$ is parallel to $overrightarrow{MN} + overrightarrow{QP}$ , the slope of $ell$ can be formed by dividing expressions in $(2)$ and $(3)$ and inverting the sign: $[frac{cos A + cos C – 1}{sin C - sin A} qquad (4)]$

Determine the coordinates of $I$ by drawing perpendiculars from $I$ to the sides and vertices of the triangle. By exploiting congruence between pairs of right triangles that share a vertex, one can partition $a,b,c$ into $p+q, p+r, q+r$ where $p,q,r$ are bases of these triangles that lie on the sides of triangle $ABC$ . From here it is clear that $I = left(frac{b + c – a}{2} , frac{b + c – a}{2}tan(A / 2)right)$ .

To find the coordinates of $O$ , note that $angle{OJK} + angle{OJL} = angle{J}$ and that $angle {OJK} = angle{OKJ}$ in any acute triangle $JKL$ . It easily follows that $angle{OJK} = 90 – L$ . Note also that the perpendicular from $O$ to $overline{JK}$ bisects $overline{JK}$ . Hence, $[O = left(frac{b}{2},frac{b}{2} cot Bright) qquad (5)]$ if triangle $ABC$ is acute.

If triangle $JKL$ is obtuse at $angle J$ , then it can be similarly shown that $angle{OKL} = angle{OLK} = J – 90$ but that the remaining angles of this form are still $90-L$ and $90-K$ . It easily follows that $(5)$ holds if $angle A$ is obtuse. If $angle B$ is obtuse then $angle OAC = B – 90$ and the $y$ coordinate of $O$ is $-frac{b}{2} tan{B-90}$ . From this, $(5)$ follows in this case as well.

We can conclude the slope of $overline {OI}$ is $[left(frac{b cot {B} – (b + c – a) tan(A/2)}{a – c}right) = left( frac {cos B – tan{(A/2)}sin B}{sin A - sin C}right) + tan(A/2) quad (6)]$ by the Law of Sines and rearrangement.

Setting $(6) = (4)$ is equivalent to $[1 - cos A - cos C = cos B + tan(A/2)(sin A - sin B - sin C)]$

Since $tan(A/2) = frac{sin A}{1 + cos A}$ , this equation is equivalent to $[(1 + cos A)(cos A + cos B + cos C – 1) = (sin A)(sin B + sin C - sin A)]$

This equation is equivalent to $[cos(A + B) + cos(A + C) + cos B + cos C = 0]$ which is evident.

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

Problem 6

Solution 1

We first prove that the game is winnable whenever $n > k$ by demonstrating a winning strategy in this case.

On the $i$ th move, choose the $k$ cards in positions $i$ through $i+k-1.$ Assuming that you do not win on any earlier move, repeat this for $1le i le 2n-k+1.$

Assume that you did not win on any of the first $2n-k+1$ moves, as described above. Let $j$ be an integer such that $1le jle 2n-k.$ On the $j$ th move, the wizard revealed the cards in positions $j$ through $j+k-1,$ so you know the labels of all of these cards (just not necessarily in the right order). Then, on the $(j+1)$ th move, the wizard revealed the cards in positions $j+1$ through $j+k,$ which means that you get to see all of the cards that were moved to positions $j+1$ through $j+k.$ This means that you can uniquely determine the label on card $j,$ since you knew all of the labels from $j$ through $j+k-1,$ and the card in position $j$ could not have moved anywhere else since your last move.

It follows that, after the sequence of $2n-k+1$ moves described above, you know the labels on the first $2n-k$ cards. Since $n > k,$ we have $2n-k ge n+1,$ so there must be a pair of cards with matching labels in this group of $2n-k$ cards, by the Pigeonhole Principle. On your next move, you can pick a group of $k$ cards that includes that pair of matching cards, and you win.

We have created a strategy that is guaranteed to win in at most $m = 2n-k+2$ moves. Thus, the game is winnable for all $n > k.$

We now prove that the game is not winnable if $n=k.$ We will say that the game is in a state $S$ if your knowledge about the card labels is of the following form:

There exists a group of $n$ cards for which you know that those $n$ cards have all of the labels $1, 2, ..., n$ (i.e. you know that they have all distinct labels) in some order, but you know nothing about which of those $n$ cards have which labels. (Call this group of cards Group $A.$ )

Suppose that the game is in such a state $S.$ We will now show that, regardless of your next move, you cannot guarantee victory or an escape from state $S.$

Clearly, the $n$ cards that are not in Group $A$ must also have all of the labels $1, 2, ..., n.$ (You might know something about which cards have which labels, or you might not.) Call this other collection of cards Group $B.$

If, on the next move, you pick all of the cards from Group $A$ or all of the cards from Group $B,$ then you clearly will not get a matching pair. The wizard will then arbitrarily permute those cards. Thus, for those $n$ chosen cards, you know their labels are all distinct, but you know nothing about which cards have which labels. Thus, you are back in state $S.$

Now, suppose you pick $x$ cards from Group $A$ and $n-x$ cards from Group $B,$ where $x$ is an integer and $1le xle n-1.$ Then, the cards chosen from Group $B$ will form a set of labels $Psubset Z_n,$ where $Z_n = left{ {1, 2, ..., n} right}$ and $|P| = n-x.$ However, you know nothing about which cards in Group $A$ have which labels. Thus, there is no way for you to prevent the $x$ cards from Group $A$ to form the exact set of labels $Q = Z_nsetminus P.$ In such a case, there will be no matching cards, so you will not win. Furthermore, the wizard will then arbitrarily permute these $n$ cards, so you will know that they have all $n$ distinct labels, but you will know nothing about which cards have which labels. Therefore, you are again in state $S.$

We have covered all cases, so it follows that, once you enter state $S,$ you cannot guarantee escape from state $S$ or victory.

Now, look at the very first move you make. Obviously, you cannot guarantee victory on the first move, as you know nothing about which cards have which labels. Assuming that you do not win on the first move, the $n$ cards you chose have all distinct labels. The wizard then permutes the $n$ cards you chose, so you now know that those $n$ cards have all distinct labels but know nothing about which cards have which labels. Therefore, if you do not win on your first move, then the game enters state $S,$ and we have already proven that you cannot guarantee victory from this point.

We therefore conclude that the game is not winnable if $n=k.$ We proved earlier that the game is winnable if $n>k,$ so the game is winnable if and only if $n>kge 2.$

Solution 2

We claim that the game is winnable if and only if $n>k$ . Suppose after the first step, the cards $1$ to $n$ are shuffled around. Notice that we have $n$ cards that we don't know the position of (which are all cards from $1$ to $n$ ). Now, suppose we pick $p$ known cards. Note that the $p$ cards are all different(since the known cards are the cards from $1$ to $n$ ), and there is still a possibility that the other cards from the unknown cards complement and cause $1$ to $n$ . Therefore, we are in the same state as before, and the game is unwinnable.

Now, suppose $n>k$ . Denote the ith card counting from the left. We pick cards $1$ to $k$ , keeping track of the set of values of the cards. Then, we pick cards $2$ to $k+1$ , adding the value of the $k+1$ th card into the set of value of cards. We keep doing this, until we pick cards $2n-k$ to $2n-1$ , at which point we know the exact number on the $2n$ th card. Now, we go back to $1$ through $k$ , and repeat this process, until we reveal the $2n-1$ th card(unless we win during the process). This process terminates only when there are less or equal to $k$ cards that we don't know the exact numbers on or if we somehow win, clearly, as otherwise we're still revealing new information by picking cards from $1$ through $k$ . Note that we now know the exact values on $2n-k$ of the cards. By the Pigeonhole Principle, since $k<n$ , $2$ of them are the same, and we pick those $2$ cards and $k-2$ other random cards and we win.