2019 Putnam Problem A1

On Saturday, December 7, 2019, I took the 2019 Putnam competition. The Putnam competition is the premier undergraduate math competition in the United States. It has two sessions of six problems each with 3 hours allotted for each session. The problems are all proof-based and are graded on a 0-10 scale, with 10 points being given only for complete proofs. This exam is infamous for having a median score of 0-1 points out of a total of 120. This was my first time taking the Putnam, so my goal was simply to get a positive score.

According to AoPS, discussion is now allowed on the 2019 Putnam.

Putnam Problem A1 concerns finding the possible values of an integer expression for arbitrary choices of the integers in the expression. The question reads:

2019 Putnam Problem A1:
Determine all possible values of
A^3 + B^3 + C^3 - 3ABC
where A, B, and C are nonnegative integers.

This was easily my favorite problem out of the questions I solved during the test. It took me much longer than it probably should have in reflection. Here’s my solution:

Solution #1: Mod 3 Bash

First, we can observe by AM-GM that (A^3+B^3+C^3)/3 >= (A^3*B^3*C^3)^(1/3) –> A^3+B^3+C^3 – 3ABC >= 0. Thus, the expression must take on a nonnegative integer for nonnegative choices of A, B, and C. To be concise, let f(A,B,C) = A^3+B^3+C^3 – 3ABC. We can observe that for all integers n, f(n+1,n,n-1) = 9n, f(n+1,n,n) = 3n+1, and f(n,n,n-1) = 3n-1. Finally, f(0,0,0) = 0. It follows that all nonnegative integers which are 0,1,2,4,5,7,8 mod 9 can be obtained with one of these generators. We claim these are the only possible values of f(A,B,C).

At this point, it suffices to show that f(A,B,C) cannot be 3 or 6 mod 9. We can observe that 0^3 = 3^3 = 6^3 = 0 mod 9, 1^3 = 4^3 = 7^3 = 1 mod 9, and 2^3 = 5^3 = 8^3 = 8 mod 9. It follows that A^3 mod 9 is uniquely determined by A mod 3. Similarly, 3ABC mod 9 = 3*(ABC mod 3) mod 9. Thus, the value of f(A,B,C) mod 9 is uniquely determined by A mod 3, B mod 3, and C mod 3. Thus, it suffices to check all triples A,B,C mod 3 and ensure that none are 3 mod 9 or 6 mod 9. We can simplify this task by noting that f is symmetric in A,B,C, so it is unnecessary to check rearrangements of A,B,C. Checking the triples (0,0,0), (0,0,1), (0,0,2), (0,1,1), (0,1,2), (0,2,2), (1,1,1), (1,1,2), (1,2,2), and (2,2,2), we can observe that none are 3 or 6 mod 9. Thus, we have shown that the only possible values of f(A,B,C) are all nonnegative integers which are not 3 or 6 mod 9.

I had a feeling there was a way to factor f(A,B,C), and indeed there is: f(A,B,C) = (A+B+C)(A^2+B^2+C^2-AB-AC-BC). Many solutions on AoPS used this factorization to greatly simplify the casework of the mod 3 bash.

This was probably my favorite question that I solved during the exam, because it took me nearly an hour to find a method that seemed promising. I initially failed to treat this problem as a Functional Equation and searched endlessly for potential factorizations. When I started trying to search for generators, I was very satisfied with the results.

Thanks for reading! See you tomorrow.