2019 Putnam Problem A1 Exploration in Python

Problem A1 of the 2019 Putnam Competition states:

Determine all possible values of the expression \(A^3 + B^3 + C^3 − 3ABC\) where \(A\), \(B\), and \(C\) are nonnegative integers.

In the real test, you can’t use a computer. Nevertheless, let’s generate some examples in Python. We’ll generate all \(A\), \(B\), \(C\) with \(10 \geq A \geq B \geq C \geq 0\) and look at all unique values of the expression less than 30.

from collections import defaultdict

values = defaultdict(list)

for A in range(11):
    for B in range(A+1):
        for C in range(B+1):
            value = A**3 + B**3 + C**3 - 3*A*B*C
            if value < 30:
                values[value].append((A, B, C))

for key in sorted(values.keys()):
    print("%s: %s" % (key, values[key]))
## 0: [(0, 0, 0), (1, 1, 1), (2, 2, 2), (3, 3, 3), (4, 4, 4), (5, 5, 5), (6, 6, 6), (7, 7, 7), (8, 8, 8), (9, 9, 9), (10, 10, 10)]
## 1: [(1, 0, 0)]
## 2: [(1, 1, 0)]
## 4: [(2, 1, 1)]
## 5: [(2, 2, 1)]
## 7: [(3, 2, 2)]
## 8: [(2, 0, 0), (3, 3, 2)]
## 9: [(2, 1, 0)]
## 10: [(4, 3, 3)]
## 11: [(4, 4, 3)]
## 13: [(5, 4, 4)]
## 14: [(5, 5, 4)]
## 16: [(2, 2, 0), (6, 5, 5)]
## 17: [(6, 6, 5)]
## 18: [(3, 2, 1)]
## 19: [(7, 6, 6)]
## 20: [(3, 1, 1), (7, 7, 6)]
## 22: [(8, 7, 7)]
## 23: [(8, 8, 7)]
## 25: [(9, 8, 8)]
## 26: [(9, 9, 8)]
## 27: [(3, 0, 0), (4, 3, 2)]
## 28: [(3, 1, 0), (3, 3, 1), (10, 9, 9)]
## 29: [(10, 10, 9)]

The values which don’t appear are 3, 6, 12, 15, 21, and 24. So the solution is probably all nonnegative integers not congruent to 3 or 6 (mod 9). The examples also tell us how to generate solutions. For example if \(n = 3k+1\) then \((k+1, k, k)\) is a solution. If \(n = 3k + 2\) then \((k + 1, k + 1, k)\) is a solution. If \(n = 9k\), then \((k + 1, k, k - 1)\) is a solution. I’ll leave it to the reader to show that \(9k + 3\) and \(9k+6\) are impossible to generate.

Avatar
Will Dearden
Quantitative Researcher

Quantitative Researcher at Allston Trading

Related