The Putnam exam is one of the hardest and most prestigious mathematical exams. Every year, more than 4,000 students, including math olympiad medalists from various countries, attempt the exam. The median score, almost every year, is 0. Each correctly answered question is worth 10 points
I often find myself trying to solve old Putnam problems, mainly because it serves as a way of “mathematical” procrastination- something that detracts me from my actual job of trying to solve my research problem. Yesterday, I ended up solving most questions from the 2010 Putnam paper. This is probably due to the fact that 2010 was one of the easiest papers in the recent past. When I compared my solutions with the solutions online, they turned out to be pretty different. Hence, I am recording them here.
The problems can be found here
A1: We need to find the largest number of boxes. Clearly, we need to place as few elements as possible in each box. If is odd, then assume that we can place the largest element in a box by itself. All the other boxes contain elements of the form . Hence, we can have boxes. Why can we not have an even larger number of boxes? Let be the lowest number of elements in a box. If , then the configuration above is the only possibility. If , then there are at most boxes, which is lower than the number of boxes we have obtained above ).
If is even, then one such configuration is . Using an argument similar to that given above, we can conclude that the highest number of boxes possible is .
A2: First we prove that the derivative of the function above is periodic with period . For some , we know that
.
Hence, . This way, we have proven that the derivative of is periodic with period .
What this shows is it that the function repeats the same “shape” every time we move to the right or left by . If is not a straight line, then there will be two points in with different derivatives. Let us also assume without loss of generality that . Hence, is positive. Let be the point with a derivative that is different from . However, will be the same as because . This is because the function repeats its shape with a period of . Hence,
.
This contradicts the fact that .
Therefore, as the derivative at all points is the same, straight lines are the only solutions.
A3: Consider the curve . Clearly, . Now as , clearly is exponential, at least along . That contradicts the fact that is bounded.
A4: Let , where is not a power of . Then we claim that is divisible by .
Proof: .
Now . Hence, it is .
Similarly, . Adding the residues up, we see that
B1: Let us assume that this is true. Then we have . If any of these elements, say , is greater than , then will be much greater than for large enough . Hence, this contradicts the fact that . Therefore, all the ‘s are less than . The ‘s that are exactly equal to , we can remove by subtracting them from the left hand side. Now for these numbers that are less than , as we increase , is a decreasing sequence. However, the right hand side, which is , is an increasing sequence. This is a contradiction. Therefore, no such sequence exists.
B2: The smallest such length is . Let . If the smallest length is , then without loss of generality let . Note that if , then both and need to be integers. This is impossible. Similarly, if the smallest length is , then without loss of generality, we can assume that . Then if , then both and need to be integers. This can also be seen to be impossible, by a simple case by case analysis. Note that . Hence, the difference between and must be at least twice the smaller number plus 1. Without loss of generality, we can assume that ( as the three points are not collinear). This leaves only a couple of possibilities for which can be checked by hand to not be possible. Hence the minimum length is , which gives us the regular pythagorean triangle with sides . The coordinate of the points will be and .
B3: This is indeed a fantastic problem, with a simple solution: first transfer all the balls to , and then transfer them one by one to the other baskets. As we can only draw balls from the th basket, we need to ensure that at least one basket is such that it has balls. Otherwise, no balls can be moved from the initial configuration. Hence, the minimal number of balls is . Hence, the minimal value of is the upper floor value of this number divided by , which is .
B5: This is a pretty tricky problem. The way that I finally thought through is is to visualize what would look like for an increasing function . If is always positive, then for would be within an distance of a fixed positive number, which is a contradiction as gets arbitrarily close to for . Now we shall allow to be negative. If is not bounded below, then there will exist negative such that will be negative. This contradicts the fact that is always non-negative. Now consider which is bounded below, but can still be negative. Clearly has to become positive at some point, as must be positive. If it becomes positive only when , then for will still be negative, which is a contradiction as must be non-negative. Let ( is assumed to be positive here) be . If becomes positive when , then for will be negative, which is again a contradiction. Hence, has to become positive for . Now if , then for will be arbitrarily close to a fixed positive number, which is a contradiction as for approaches . Hence, must be .
Hence, the only remaining possibility is a function such that and . Let us analyze this function. We know that . Also, for , . Hence, . This implies that . I haven’t yet determined how to eliminate this case.