1998 SOLUTIONS, PART II

1. Four positive numbers are placed at the vertices of a rectangle. Each number is at least as large as the average of the two numbers at the adjacent vertices. Prove that all four numbers are equal.

Solution:
Look at the smallest number. It is at least as large as the average of its two neighbors, so it must equal each of them. Now consider one of these two neighbors. Since it is also smallest, it must equal its two neighbors, by the same argument. This implies that all four numbers are equal.

2. The sum 498+499+500+501=1998 is one way of expressing 1998 as a sum of consecutive positive integers. Find all ways of expressing 1998 as a sum of two or more consecutive positive integers. Prove your list is complete.

Solution: Suppose a+(a+1)+(a+2)+...+(a+b)=1998 with a,b>=1. This means 1998= (b+1)a+b(b+1)/2, which is the same as 3996=(b+1)(b+2a). Note that one of b+1 and b+2a is odd and the other is even, so 3996=(even)·(odd). Since b+2a>=b+2 > b+1, the larger factor is b+2a and the smaller is b+1. The factorizations of 3996=4·333·7 into an even times an odd (>1) are 1332·3, 444· 9, 148·27, 108·37, 36·111, 12·333, and 4·999. Solving for a and b yields the following sums:
665+666+667
218+219+...+226
61+62+...+87
36+37+...+72
38+39+...+73
161+162+...+ 172
498+499+500+501

3. An infinite strip (two parallel lines and the region between them) has a width of 1 inch. What is the largest value of A such that every triangle with area A square inches can be placed in this strip? Justify your answer.

Solution: We first show that if the area is <= 3-1/2 then the triangle can be placed in a strip of width 1. Let a be the length of the largest side of the triangle and h be that of the corresponding height. So each of the two angles adjacent to a is acute. The height h divides the triangle into two right triangles. Applying the Pythagorean theorem to a right triangle with base a/2 or larger (two bases add up to a), we have h2<=a2-(a/2)2, hence h<=a·31/2/2 and h2<= ha31/2/2<=1. The last equality uses the assumption that the area of the triangle is ha/2<=3-1/2. So h<=1. This means the triangle can be placed in a strip of width 1. We now show that an equilateral triangle of area larger than 3-1/2 cannot be placed in the strip. Such a triangle has altitude larger than 1. Suppose the triangle fits in the strip. We may expand the triangle so that at least one vertex is touching each edge. Suppose vertex A touches one side and vertex B touches the other. Suppose, by symmetry, that the vertex C is closer to the side touched by B. Then AB makes an acute (or right) angle with the side touched by B, and this angle must be at least 60 degrees since C is within the strip. Therefore the sine of this angle is between sin 60o=31/2/2 and sin 90o=1. Since the length of AB is greater than 2/31/2, the width of the strip, namely |AB| times the sine of the angle, is greater than 1.
The largest value of the area is therefore 3-1/2.

4. A plane divides space into two regions. Two planes that intersect in a line divide space into four regions. Now suppose that twelve planes are given in space so that a) every two of them intersect in a line, b) every three of them intersect in a point, and c) no four of them have a common point. Into how many regions is space divided? Justify your answer.

Solution: First note that n points divide a line into n+1 pieces. Now let Ln be the number of regions into which n lines divide the plane (assuming that no 3 lines intersect in a point and no two are parallel). If we add an (n+1) line, it is divided into n+1 pieces by its intersections with the other lines. Each piece divides an existing region in the plane into two, so the number of regions increases by n+1. This means that Ln+1-Ln=n+1. Since L1=2, an easy induction shows that Ln=1+n(n+1)/2. Now let Pn be the number of regions into which n planes divide 3-dimensional space. When we add an (n+1)st plane, this plane is divided into Ln pieces by the other n planes. Each piece divides an existing region of 3-dimensional space into 2 parts, so the number of regions increases by Ln. Therefore Pn+1-Pn=Ln. Use P1=2 and an easy induction to show that Pn=1+n+n(n-1)/2+n(n-1)(n-2)/6. When n=12, we have P12=299.

5. Five robbers have stolen 1998 identical gold coins. They agree to the following: The youngest robber proposes a division of the loot. All robbers, including the proposer, vote on the proposal. If at least half the robbers vote yes, then that proposal is accepted. If not, the proposer is sent away with no loot and the next youngest robber makes a new proposal to be voted on by the four remaining robbers, with the same rules as above. This continues until a proposed division is accepted by at least half the remaining robbers. Each robber guards his best interests: He will vote for a proposal if and only if it will give him more coins than he will acquire by rejecting it, and the proposer will keep as many coins for himself as he can. How will the coins be distributed? Explain your reasoning.

Solution: Observe that a robber who is offered no coins will vote against any suggested plan. If there were 2 robbers, the younger would propose that he get it all, vote for his proposal, and take the money. Now suppose that there were 3 robbers. The youngest must offer a coin to at least 1 robber since he needs at least 1 yes vote in addition to his own. If he offers a coin to the oldest robber, that robber will reason that he will get nothing if the plan is rejected (since then the number of robbers will be reduced to 2) so he will accept. Moreover, offering a coin to robber 2, instead of robber 1, would not buy his vote, so in the case of 3 robbers, the oldest robber gets 1 coin and the youngest gets the rest. If there were 4 robbers then the youngest still needs only 1 vote besides his own, and can obtain it by offering 1 coin to the one who would get nothing if the number of robbers would be reduced to 3. Again offering 1 coin to either of the other robbers would not buy any votes. Let us now number the robbers 1 (oldest), 2 (next oldest) and so on. We have just seen that with 4 robbers, robber 2 gets 1 coin and robber 4 gets the rest. Now we are prepared to deal with 5 robbers. The youngest robber must give out at least 2 coins since he needs 2 votes in addition to his own. He can secure 2 votes by giving 1 coin each to the robbers who would receive nothing if the number of robbers is reduced to 4. Namely robbers 3 and 1. Moreover, neither robber 2 nor 4 would vote for a plan if they were offered 1 coin (since they would also get at least 1 if the plan was rejected) so, with 5 robbers, robbers 1 and 3 will get 1 coin each and robber 5 will get the rest.