My Most Memorable Math Mistake
I have forgotten all the problems from the math Olympiads I participated in, except for one. That problem cost me one point, and as result I didn’t get a perfect score. Here is Problem Number 4 from the 1976 IMO:
Determine the greatest number that is the product of some positive integers, and the sum of these integers is 1976.
The solution goes like this. Consider a partition of 1976. If there is an integer x in the partition greater than 5, then replacing it with two integers x-2 and 2 gives a bigger product. Replacing 4 in the partition by 2 and 2 doesn’t change the product. On the other hand, if there is 1 in the partition, it is profitable to attach it to any other number: to replace 1 and x by x+1.
That means the maximum-product partition of a number greater than one has to consist only of twos and threes. If we have three twos in the partition, we can replace them by two threes, thus increasing the product. That means that our partition should consist of twos and threes, and the number of twos shouldn’t be greater than three.
I lost my point when I made an elementary arithmetic mistake while calculating the remainder of 1976 modulo 3.
Let’s generalize this problem for any number n. If we define the maximum product of partitions a(n) as a function of the number n, we get the sequence A000792 in the Encyclopedia of Integer Sequences. This sequence has other interesting definitions, which appear if we add some structure to partitions of n.
For example, we can suppose that our n is not just a number, but it also represents n objects that are being permuted by the symmetric group Sn. In this case, we can associate some Abelian subgroups of the symmetric group with every partition. Namely, we can divide the set of n elements into disjoint subsets of sizes corresponding to our partition and cycle the elements in every subset. The product of these cycles is an Abelian subgroup, the order of which doesn’t depend on how exactly we partition or how we cycle. This order is the product of the partition numbers. It appears that we can get all maximal Abelian subgroups of the symmetric group in this manner. Thus the sequence a(n) is the maximum size of the maximal Abelian subgroup in a symmetric group Sn.
We can do something else with our n objects. Suppose they are represented by vertices of a graph. We take any partition of n and divide our graph into groups of vertices according to this partition. Next we connect vertices of the graph that belong to different groups. If we take a vertex from every group, then the corresponding subgraph is a clique. We can see that it is a maximal clique as two vertices from the same group are never connected and we can’t add any more vertices. The number of different cliques of this size is the product of the number of elements in every group. We can prove that a(n) is the maximum possible number of maximal cliques in a graph with n vertices.
Even though I can’t return to 1976 to correct my stupid mistake, I love this problem and the corresponding sequence.
Share:
Leave a comment