PART II,  2002

December 4, 2002, 1:00--3:00
2 hours

1. (30 points) 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.

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

3. (30 points) 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.

4. (30 points) 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.

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.

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.