Problem for 3/25

This is the very first problem of the very first Putnam exam. (All Putnam problems are taken from the book The William Lowell Putnam Mathematical Competition 1985–2000: Problems, Solutions, and Commentary, published by the Mathematical Association of America. )

Problem:
 Determine, with proof, the number of ordered triples (A1,A2,A3) of sets which
have the property that
(i) A1 ∪ A2 ∪ A3 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, and
(ii) A1 ∩ A2 ∩ A3 = ∅,
where ∅ denotes the empty set. Express the answer in the form 2^a * 3^b * 5^c *7^d, where a, b,
c, and d are nonnegative integers. ∪ means  union, ∩ means intersection.

This is a very good problem for me to begin with, because it's pretty simple to state, and requires no complicated ideas to prove. Hopefully anyone reading this blog can understand it.

I solved the problem in like 5-10 minutes, but I forgot what an "ordered triple" was, so I thought I made a mistake, and continued for 1 hour, and had to use the book's hint, and arrived at the same solution as I had the first time, and then realized that an ordered triple means that (a,b,c) and (c,b,a) are different, and banged my head loudly against the desk.

Please please comment about how clear these solutions are, as I am pretty bad at explaining things.

So, I have two solutions to share:

Solution #1: (solution I found with a hint from the book):
This is basically saying, how many ways can you split {1,..10} into 3 sets, where elements can be in two sets at once, but not 3.

We can make a Venn diagram to represent this actually. Draw a Venn Diagram with 3 circles (like this), and cross out the section where all 3 circles intersect. (This is the section in white on the picture) If we fill this diagram, excluding the crossed-out part, with the numbers from 1 to 10, we can take the numbers in our 3 circles as A1, A2, A3. There are 6 different spaces in the Venn Diagram in which we can put numbers. So each number from 1 to 10 can go into any of the 6 spaces, so there are 6^10=2^10 * 3^10 ways of doing this.



Solution #2: (my solution)
Replace {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} with {1,2,3,4,....n}.
And call the number of sets f(n). I'm just going to find out how to compute f(n) in general, and then compute f(10). We do this by recursion. If we have a triple (A1, A2, A3) for some n, and then we replace n with n+1. That same triple satisfies the second property, but not the first. We can fix this by inserting n+1 into at least one of our sets.
(If we take a triple for n+1, we can remove all instances of n+1 and get a triple for n, so we don't "miss" any).

So how many ways can we do this?  Well, we can add n+1 into A1, A2, or A3, which is 3 ways. But we can also add n+1 into 2 sets, as there is only a problem if it's in all 3. There are also 3 ways of doing that (adding it to A1, A2, or A2,A3, or A1,A3). So for each triple in n, there are 6 triples in  n+1, so f(n+1)=6f(n).


f(1)=6, (Our choices are ({1},∅,∅), ({1},{1},∅) and all reorderings thereof).
So f(n)=6^n, f(10)=6^10=2^10 * 3^10.


I think the first solution is very nice, and that this is a pretty good problem, if a bit easy.

What I can take away from this is that early Putnam problems are not that hard(in general most contests get more difficult from year to year), and that I should really know what an ordered triple is.