USA Mathematical Talent Search Round 1 Solutions …

1 Create PDF with GO2 PDF for free, if you wish to remove this line, click here to buy Virtual PDF PrinterUSA Mathematical Talent SearchRound 1 SolutionsYear 23 Academic Year 2011 grid on the right has 12 boxes and 15 edges connect-ing boxes. In each box, place one of the six integers from 1 to 6such that the following conditions hold: For each possible pair of distinct numbers from 1 to6, there is exactly one edge connecting two boxeswith that pair of numbers. If an edge has an arrow, then it points from a boxwith a smaller number to a box with a larger do not need to prove that your configuration is the only one possible; you merely needto find a configuration that satisfies the constraints above.

2 (Note: In any other USAMTS problem, you need to provide a full proof. Only in this problem is an answer withoutjustification acceptable.)???1?First, we notice that each number 1 through 6 must be placedin exactly two boxes. For each number, one of the two boxes musthave 2 neighbors and the other must have 3. Of the boxes with 3neighbors, there is exactly one that does not have any incomingarrows. This box must contain the value 1. Likewise, only twoof the boxes with three neighbors have no outgoing arrows, andtwo of the boxes with two neighbors have no outgoing the two sixes must lie in these four boxes.

3 We label these as?in our first 6We note that wherever the two sixes land, they must have 5distinct neighbors. In particular, they cannot land in a pair ofboxes that share a neighbor. Among these four, the only 2- and3-valent boxes (boxes with 2 or 3 neighbors respectively) that donot share a neighbor are the two to the that we ve taken care of the simplest cases, we will needto be much more careful with the remaining boxes. Let s label them as in the first figure onthe next page, using letters early in the alphabet to represent the 2-valent boxes (containing1-5) and letters late in the alphabet for the 3-valent boxes (containing 2-5).

4 Create PDF with GO2 PDF for free, if you wish to remove this line, click here to buy Virtual PDF PrinterUSA Mathematical Talent SearchRound 1 SolutionsYear 23 Academic Year 2011 6 ZABXCThe values ofDandEmust be equal to two of the values fromX,Y,Z, andW. However, we know that two boxes with thesame value cannot be neighbors and also cannot share neighbors,so the valuesDandEmust equal the valuesXandYin someorder. By the symmetric argument, the valuesAandBmust beequal to the valuesZandWin some order.

5 The specific upshotof this is that we now know that we must haveC= 6 2A2D1 The remaining entries are all from 2 to 5. We know thatA,X, andYare distinct and all greater thanB, soB= 2. Recallalso thatBmust be equal to one ofZorW. SinceW > D,Wcannot be equal to 2, and soZmust be 2. Since{A, B}={W, Z}andB=Z, we must haveW=A. Along the same lines, sinceW=AandAneighborsY, we cannot haveY=D, so insteadwe must haveY=EandX=D. We compile this to the the grid is straightforward from here .

6 We know thatA,D, andEmust beequal to 3, 4, and 5 in some order. The bottom of the grid tells us thatDis the smallest ofthe three, soD= 3. The top of the grid tells us thatA < E, so we haveA= 4 andE= solution is given below, and a direct check shows that all conditions hold. Ourargument above shows that this solution is 4 3 55 1 6 24 2 3 1 Create PDF with GO2 PDF for free, if you wish to remove this line, click here to buy Virtual PDF PrinterUSA Mathematical Talent SearchRound 1 SolutionsYear 23 Academic Year 2011 all integersa,b,c,d, ande, such thata2=a+b 2c+ 2d+e 8,b2= a 2b c+ 2d+ 2e 6,c2= 3a+ 2b+c+ 2d+ 2e 31,d2= 2a+b+c+ 2d+ 2e 2,e2=a+ 2b+ 3c+ 2d+e begin by bringing all terms to the left sides.

7 A2 a b+ 2c 2d e+ 8 = 0,b2+a+ 2b+c 2d 2e+ 6 = 0,c2 3a 2b c 2d 2e+ 31 = 0,d2 2a b c 2d 2e+ 2 = 0,e2 a 2b 3c 2d e+ 8 = we add these five equations together we geta2 6a+b2 4b+c2 2c+d2 10d+e2 8e+ 55 = we can complete the squares,(a2 6a+ 9) + (b2 4b+ 4) + (c2 2c+ 1) + (d2 10d+ 25) + (e2 8e+ 16) = 0,or(a 3)2+ (b 2)2+ (c 1)2+ (d 5)2+ (e 4)2= here we see that any quintuple (a, b, c, d, e) satisfying the original equations mustnecessarily satisfy this final equation. However, since squares of integers are always nonneg-ative, this can only be solved when each of the squares is equal to zero.

8 Therefore the onlypossible solution is(a, b, c, d, e) = (3,2,1,5,4).We now need to check that these values satisfy all of the original check that these values give a solution we must substitute them all back into theoriginal equations. Indeed, all 5 equations are satisfied by these values,32= 3 + 2 2 1 + 2 5 + 4 8,22= 3 2 2 1 + 2 5 + 2 4 6,12= 3 3 + 2 2 + 1 + 2 5 + 2 4 31,52= 2 3 + 2 + 1 + 2 5 + 2 4 2,42= 3 + 2 2 + 3 1 + 2 5 + 4 PDF with GO2 PDF for free, if you wish to remove this line, click here to buy Virtual PDF PrinterUSA Mathematical Talent SearchRound 1 SolutionsYear 23 Academic Year 2011 there is a single, unique answer: (a, b, c, d, e) = (3,2,1,5,4).

9 Create PDF with GO2 PDF for free, if you wish to remove this line, click here to buy Virtual PDF PrinterUSA Mathematical Talent SearchRound 1 SolutionsYear 23 Academic Year 2011 (Corrected from an earlier release.)You have 14 coins, dated 1901 through of these coins are real and weigh ounce each. The other seven are counterfeitand weigh ounces each. You do not know which coins are real or counterfeit. You alsocannot tell which coins are real by look or for you, Zoltar the Fortune-Weighing Robot is capable of making very precisemeasurements.

10 You may place any number of coins in each of Zoltar s two hands and Zoltarwill do the following: If the weights in each hand are equal, Zoltar tells you so and returns all of the coins. If the weight in one hand is heavier than the weight in the other, then Zoltar takes onecoin, at random, from the heavier hand as tribute. Then Zoltar tells you which handwas heavier, and returns the remaining coins to objective is to identify a single real coin that Zoltar has not taken as tribute. Is therea strategy that guarantees this?