41st Putnam 1980

Problem A2

Find f(m, n), the number of 4-tuples (a, b, c, d) of positive integers such that the lowest common multiple of any three integers in the 4-tuple is 3m7n.



Answer: (6m2 + 3m + 1)(6n2 + 3n + 1).

Each of a, b, c, d must be of the form 3h7k with h ≤ m, k ≤ n. We can consider h and k separately. At least two of a, b, c, d must have h = m. So there are three cases: (1) all of a, b, c, d have h = m (1 possibility); (2) three of a, b, c, d have h = m and the other has 0 ≤ h < m (3m possibilities); (3) two of a, b, c, d have h = m and the other two have 0 ≤ h < m (6m2 possibilities). So, in all, there are 6m2 + 3m + 1 possibilities for h. Similarly, there are 6n2 + 3n + 1 possibilities for k. Each of the possibilities for h can be combined with each of the possibilities for k, so in all there are (6m2 + 3m + 1)(6n2 + 3n + 1) possible 4-tuples.



41st Putnam 1980

© John Scholes
10 Dec 1999
Last corrected/updated 21 Nov 02