2002 PART II Solutions

1. One chilly morning, 10 penguins ate a total of 50 fish. No fish was shared by two or more penguins. Assuming that each penguin ate at least one fish, prove that at least two penguins ate the same number of fish.

Answer: By way of contradiction, assume that all 10 penguins eat a different number of fish. We will argue that at least 55 fish must have been consumed, which is contrary to the statement of the problem. Order the penguins in increasing order of the number of fish they ate. The first penguin ate at least one fish. The second penguin ate at least two fish, and arguing inductively, the tenth penguin ate at least 10 fish. Hence at least 1+2+...+10=55 fish were consumed, contradiction.

2. A triangle of area 1 has sides of lengths a > b > c. Prove that b > 21/2.

Answer: Let A,B,C denote the vertices of the triangle with vertex B opposite the side of length b. Let h be the length of the altitude drawn from B to the line containing AC. Since the shortest distance from a point to a line is given by a segment perpendicular to the line, h < = c, hence h < b. But the area of the triangle is 1=(1/2)bh, so bh=2. Since h < b, b 2 > 2, hence b > 21/2.

3. Imagine ducks as points in a plane. Three ducks are said to be in a row if a straight line passes through all three ducks. Three ducks, Huey, Dewey, and Louie, each waddle along a different straight line in the plane, each at his own constant speed. Although their paths may cross, the ducks never bump into each other. Prove: If at three separate times the ducks are in a row, then they are always in a row.

Answer: Given two points (x1,y1) and (x2,y2) the equation (y-y1)(x2-x1)=(x-x1)((y2-y1) represents the line passing through these two points (it is a linear equation satisfied by the coordinares of the two points). It follows that three points (x1,y1), (x2,y2) and (x3,y3) lie on the same line if and only if the condition
C:   (y3-y1)(x2-x1)= (x3-x1)(y2-y1)
holds. Now suppose that (x1,y1), (x2,y2) and (x3,y3) represent the (changing) coordinates of the three ducks as they waddle along their paths. Each coordinate is a linear function of time t, so the equation C is an equation in t of degree at most 2 (i.e., is a quadratic). If such an equation has more than 2 solutions then it must reduce to an identity and thus hold true for all values of t. That is, if the ducks are in a row at more than two times, then they are always in a row.

4. Two computers and a number of humans participated in a large round-robin chess tournament (i.e., every participant played every other participant exactly once). In every game, the winner of the game received one point, the loser zero. If a game ended in a draw, each player received half a point. At the end of the tournament, the sum of the two computers' scores was 38 points, and all of the human participants finished with the same total score. Describe (with proof) ALL POSSIBLE numbers of humans that could have participated in such a tournament.

Answer: Let n denote the number of humans and let s be equal to the human's common score. As there are n+2 participants, there are (n+2)(n+1)/2 games played in the tournament and each game produces a total of one point to the common score. Thus,
which simplifies to 2sn=n2+3n-74. Since n and 2s are integers and n clearly divides n2+3n, n must divide 74. The only integers which divide 74 are n=1,2,37,74. It is easy to see that n=1 and n=2 are impossible (since there would not be enough games to get the computer's score high enough). It remains to see that the other two possibilities are both viable: If n=37 and every game is a draw, then the conditions of the problem are satisfied. As well, if n=74 and one computer loses every game and the other computer beats the first computer but draws every human then again the conditions are satisfied. Thus, n=37 and 74 is the complete set of solutions.

5. One thousand cows labeled 000, 001,..., 998, 999 are requested to enter 100 empty barns labeled 00, 01,...,98, 99. One hundred Dalmatians -- one at the door of each barn -- enforce the following rule: In order for a cow to enter a barn, the label of the barn must be obtainable from the label of the cow by deleting one of the digits. For example, the cow labeled 357 would be admitted into any of the barns labeled 35, 37 or 57, but would not admitted into any other barns.

a) (15 points) Demonstrate that there is a way for all 1000 cows to enter the barns so that at least 50 of the barns remain empty.

Answer: Let S be the set of 50 barns in which EITHER both digits are even OR both digits are odd. Clearly, every three digit number has (at least) two digits that are even or else two digits that are odd, so every cow can enter at least one of the barns in S.

b) (15 points) Prove that no matter how they distribute themselves, after all 1000 cows enter the barns, at most 50 of the barns will remain empty.

Answer: Call a cow optimistic if the digits of its number are increasing, i.e., a < b < c, pessimistic if its digits are decreasing, and constant if all 3 of its digits are the same. Suppose the cows are all put into appropriate barns. Clearly, the 10 constant cows must go into barns 00,11,...,99, so these 10 barns are nonempty. We will show that at least 20 barns are needed to accommodate the optimistic barns. This suffices as a symmetric argument shows that 20 barns are needed to accommodate the pessimistic cows, hence at least 10+20+20=50 barns are nonempty. For any subset S of {0,1,...,9}, call a cow an S-cow if all three of its digits are elements of S.
Claim: If S has 2n elements (for 1 < = n < = 5) then at least n(n-1) barns are needed to accommodate all of the optimistic S-cows.
Note that the claim suffices since it implies that at least 5· 4=20 barns are needed to accommodate all of the optimistic cows. The claim is proved by induction on n. When n=1 this is trivial as there are no optimistic S cows when S has size 2. So assume that the claim holds for sets of size 2n-2 and fix a set S of size 2n. Let a be the smallest element of S. First, if Barn ac is nonempty for every c in S - {a}, and we take S' to be any subset of S - {a} of size 2n-2, then (n-1)(n-2) barns are needed to accommodate the optimistic S'-cows. Hence at least (n-1)(n-2)+2n-1 barns are nonempty, which is greater than n(n-1). So assume that Barn ac is empty for at least one c in S - {a}. Let c be the largest element of S so that Barn ac is empty and let S'=S-{a,c}. Now, we have assumed that each of the Barns ad are nonempty where d > c and d in S. Furthermore, for all b in S satisfying a < b < c, Cow abc is put into either Barn ab or bc, so at least one of those two barns is nonempty. Thus, in addition to the (n-1)(n-2) barns that are needed to accommodate the optimistic S'-cows, at least 2n-2 additional barns are nonempty, which establishes the claim.