Konhauser Problem Set 2001

Konhauser Problemfest

Problems by David Savitt and Russel Mann (Harvard University)

1. Last season, the Minnesota Timberwolves won 5 times as many games as they lost, in games in which they scored 100 or more points. On the other hand, in games in which their opponents scored 100 or more points, the Timberwolves lost 50% more games than they won. Given that there were exactly 34 games in which either the Timberwolves or their opponents scored 100 or more points, what was the Timberwolves’ win-loss record in games in which BOTH they and their opponents scored 100 or more points?

2. Three circles are drawn in chalk on the ground. To begin with, there is a heap of n pebbles inside one of the circles, and there are “empty heaps” (containing no pebbles) in the other two circles. Your goal is to move the entire heap of n pebbles to a different circle, using a series of moves of the following type. For any nonnegative integer k, you may move exactly 2^k pebbles from one heap (call it heap A) to another (heap B), provided that heap B begins with fewer than 2^k pebbles, and that after the move, heap A ends up with fewer than 2^k pebbles. Naturally, you want to reach your goal in as few moves as possible. For what values of n <= 100 would you need the largest number of moves?

3.(a) Begin with a string of 10 A’s, B’s, and C’s, for example A B C C B A B C B A and underneath, form a new row, of length 1 shorter, as follows: between two consecutive letters that are different, you write the third letter, and between two letters that are the same, you write that same letter again. Repeat this process until you have only one letter in the newrow. For example:
A B C C B A B C B A
C A C A C C A A C
B B B B C B A B
B B B A A C C
B B C A B C
B A B C A
C C A B
C B C
A A
A
Prove that the letters at the corners of the resulting triangle are either all the same or all different. (b) Besides 10, for which positive integers n is the result from part (a) true for all strings of n A’s, B’s, and C’s?

4. When Mark climbs a staircase, he ascends either 1, 2, or 3 stairsteps with each stride, but in no particular pattern from one foot to the next.In how many ways can Mark climb a staircase of 10 steps? (Note that he must finish on the top step. Two ways are considered the same if the number of steps for each stride are the same; that is, it doesn’t matter whether he puts his best or his worst foot forward first.) Suppose that a spill has occurred on the 6th step and Mark wants to avoid it. How many ways can he climb the staircase without stepping on the 6th step?

5. Number the vertices of a cube from 1 to 8, and let A be the 8×8 matrix whose (i, j) entry is 1 if the cube has an edge between vertices i and j, and is 0 otherwise. Find the eigenvalues of A, and describe the corresponding eigenspaces.

6. Let f(x) be a twice-differentiable function on the open interval (0, 1)such that lim f(x) = – Infinity x->0+ lim f(x) = + Infinity x->1- Show that f”(x) takes on both negative and positive values.

7. Three stationary sentries are guarding an important public square which is, in fact, square, with each side measuring 8 rods (recall, a rod is 5.5 yards). If any of the sentries see trouble brewing at any location on the square, the sentry closest to the trouble spot will immediately cease to be stationary and dispatch to that location. And like all good sentries, these three are continually looking in all directions for trouble to occur. Find the maximum value of D, so that no matter how the sentries are placed, there is always some spot in the square that is at least D rods from the closest sentry.

8. The Union Atlantic Railway is planning a massive project: a railroad track joining Cambridge, Massachusetts and Northfield, Minnesota. However, the funding for the project comes from the will of Orson Randolph Kane, the eccentric founder of the U.A.R., who has specified some strange conditions on the railway; thus the skeptical builders are unsure whether or not it is possible to build a railway subject to his unusual requirements. Kane’s will insists that there must be exactly 100 stops (each named after one of his great-grandchildren) between the termini, and he even dictates precisely what the distance along the track between each of these stops must be. (Unfortunately, the tables in the will DON’T list the order in which the stops are to appear along the railway.) Luckily, it is clear that Kane has put some thought into these distances; for any three distinct stops, the largest of the three distances among them is equal to the sum of the smaller two, which is an obvious necessary condition for the railway to be possible. (Also, all the given distances are shorter than the distance along a practical route from Cambridge to Northfield! U.A.R.’s engineers have pored over the numbers and noticed that for any four of Kane’s stops, it would be possible to build a railway with these four stops and the distances between them as Kane specifies. Prove that, in fact, it is possible to complete the entire project to Kane’s specifications.

9. Gail was giving a class on triangles, and she was planning to demonstrate on the blackboard that the three medians, the three angle bisectors, and the three altitudes of a triangle each meet at a point (the centroid, incenter, and orthocenter of the triangle, respectively). Unfortunately, she got a little careless in her example, and drew a certain triangle ABC with the median from vertex A, the altitude from vertex B, and the angle bisector from vertex C. Amazingly, just as she discovered her mistake, she saw that the three segments met at a point anyway! Luckily it was the end of the period, so no one had a chance to comment on her mistake. In recalling her good fortune later that day, she could only remember that the side across from vertex C was 13 inches in length, that the other two sides also measured an integral number of inches, and that none of the lengths were the same. What were the other two lengths?

10. An infinite sequence of digits “1” and “2” is determined uniquely by the following properties: (i) The sequence is built up by stringing together pieces of the form “12” and “112”. (ii) If we replace each “12” piece with a “1” and each “112” piece with a “2”, then we get the original sequence back. (a) Write down the first dozen digits in the sequence. At which place will the 100th “1” occur? What is the 1000th digit? (b) Let A_n be the number of “1”s among the first n digits of the sequence. Assume that the ratio A_n/n approaches a limit. What limit must it approach? (c) Show that the ratio A_n/n does approach a limit.