Putnam 1995 A1

Let $S$ be a set of real numbers which is closed under multiplication (that is, if $a$ and $b$ are in $S$, then so is $ab$). Let $T$ and $U$ be disjoint subsets of $S$ whose union is $S$. Given that the product of any three (not necessarily distinct) elements of $T$ is in $T$ and that the product of any three elements of $U$ is in $U$, show that at least one of the two subsets $T$, $U$ is closed under multiplication.


Closure under multiplication is a property that most math majors are pretty familiar with, as it comes up in abstract algebra courses as a property of groups. The only real pitfall to avoid here is assuming something implicitly/unconsciously. So let's see: we'd like to show that one of the two subsets is closed under multiplication. Here, proof by contradiction seems like a good idea, because it lets us get our hands on actual elements.

That is, if we assume that $T$ and $U$ are not closed under multiplication, we get elements $t_1, t_2 \in T$ such that $t_1t_2$ is not in $T$. Since $T$ and $U$ are disjoint and their union is $S$, that means $t_1t_2 \in U$. Similarly we can get elements $u_1, u_2 \in U$ such that $u_1u_2$ is not in $U$, which means that it must be in $T$.

It's a good sign that we've used some of the properties of $T$ and $U$ already. So now we have these four elements--what should we do with them? Well, we haven't used the "triple product" property yet, so we need to multiply some combination of these elements so we can use it.

The obvious choice is the product (call it $p$) of all four:
\[ p = (t_1 t_2)(u_1 u_2). \] So notice that since $(u_1 u_2) \in T$, $p$ is the product of three elements of $T$, so it has to be in $T$. But since $(t_1 t_2) \in U$, $p$ is also the product of three elements of $U$, so it has to be in $U$. But $T$ and $U$ are disjoint. Contradiction!

This was the first Putnam problem I ever solved, so it's reasonable for it to be the first problem on the blog.

I'll finish each Putnam problem discussion with a measure of how others did on the problem, which comes from the official Putnam website. The numbers below represent the number of the top 200 participants (plus ties) who got the scores 10, 9, 8, and 2, 1, 0, respectively. It is a quirk of the Putnam exam that scores of 3, 4, 5, 6, or 7 are not given at all! So for instance 64 of the top 204 participants got a score of 9 out of 10 for this problem.

Top 204 by score:
(115,64,20), (1,0,4)