# Putnam proof

Printable View

• Aug 29th 2006, 01:42 PM
Jameson
Putnam proof
I am studying for the Putnam competition in December and I want just a hint at how to do this problem, not a full solution please. I'm trying to develop a good methodology to approaching proofs.

A1. Determine, with proof, the number of ordered triples $(A_1,A_2,A_3)$ of sets which have the property that

(i) $A_1 \cup A_2 \cup A_3 = \{1,2,3,4,5,6,7,8,9,10\}$, and
(ii) $A_1 \cap A_2 \cap A_3 = \emptyset$. Express the answer in the form of $2^a3^b5^c7^d$, where a,b,c, and d are non-negative integers.

What's the best way to approach this?
• Aug 29th 2006, 02:45 PM
ThePerfectHacker
Quote:

Originally Posted by Jameson
I am studying for the Putnam competition in December and I want just a hint at how to do this problem, not a full solution please. I'm trying to develop a good methodology to approaching proofs.

A1. Determine, with proof, the number of ordered triples $(A_1,A_2,A_3)$ of sets which have the property that

(i) $A_1 \cup A_2 \cup A_3 = {1,2,3,4,5,6,7,8,9,10}$, and
(ii) $A_1 \cap A_2 \cap A_3 \ne \emptyset$. Express the answer in the form of $2^a3^b5^c7^d$, where a,b,c, and d are non-negative integers.

What's the best way to approach this?

The way I like to is to procede the opposite.
Meaning do the problem:
$A_1\cup A_2\cup A_3 = \{\}$
Then from the full total subtract this number.

I do not understand why you chose to place this Algebra section.
• Aug 29th 2006, 03:38 PM
Jameson
Quote:

Originally Posted by ThePerfectHacker
I do not understand why you chose to place this Algebra section.

Ooops! I didn't really think about where to put it. I'll move it.

Thanks for your help guys. I'll think about it and post back what I have.
• Aug 29th 2006, 04:05 PM
Jameson
Quote:

Originally Posted by ThePerfectHacker
The way I like to is to procede the opposite.
Meaning do the problem:
$A_1\cup A_2\cup A_3 = \{\}$
Then from the full total subtract this number.

Ok. I'll try to start this way. My problem is that I have trouble going from specific cases and setting up a pattern/generalizing behavior that's needed for a proof.

So if $A_1\cup A_2\cup A_3 = \{\}$, then obviously the sets can not have any items in common. So I need to find the number of ways to split up the numbers 1-10 into 3 groups.

I see this as having $A_1={_{10} C _ i}$, $A_2={_{10} C _j}$, and $A_3={_{10} C _k}$ , where i+j+k=10. On the right track or should I stop and consider another method? If I'm going in the right direction, any suggestions after the step I gave?

Thanks guys.

PH - Are you going to take the Putnam exam?
• Aug 29th 2006, 05:12 PM
ThePerfectHacker
Sorry, I meant to write.
$A_1\cap A_2 \cap A_3$

(Still number theory is not appropriate. I would place it in the High School Probabily question. Yes I know this is very complicated but as far as level is concerned it deserves to be there. I guess I am the only one of the forum who is careful where everything goes).
• Aug 30th 2006, 09:22 AM
ThePerfectHacker
Quote:

Originally Posted by Jameson

I see this as having $A_1={_{10} C _ i}$, $A_2={_{10} C _j}$, and $A_3={_{10} C _k}$ , where i+j+k=10. On the right track or should I stop and consider another method? If I'm going in the right direction, any suggestions after the step I gave?

Not true.
The first set you can select.
${{10}\choose n}$ for $1\leq n\leq 8$
The second set you can select.
${{10-n}\choose m}$ for $1\leq m \leq 9-n$
And the third set you can only take the remaining which is one.
Thus,
$\frac{10!}{n!(10-n!)}\cdot \frac{(10-n)!}{(10-n-m)!m!}$
Which simplifies to,
$\frac{10!}{n!m!(10-n-m)!}$
Now you add each one.
• Aug 30th 2006, 12:30 PM
JakeD
Quote:

Originally Posted by Jameson
I am studying for the Putnam competition in December and I want just a hint at how to do this problem, not a full solution please. I'm trying to develop a good methodology to approaching proofs.

A1. Determine, with proof, the number of ordered triples $(A_1,A_2,A_3)$ of sets which have the property that

(i) $A_1 \cup A_2 \cup A_3 = \{1,2,3,4,5,6,7,8,9,10\}$, and
(ii) $A_1 \cap A_2 \cap A_3 \ne \emptyset$. Express the answer in the form of $2^a3^b5^c7^d$, where a,b,c, and d are non-negative integers.

What's the best way to approach this?

I solved this problem and got the answer $7^{10} - 6^{10},$ which does not have the required form. I found the reason for this is that the problem is not stated correctly: there is an equal sign in the second condition.

Your methodology so far is off track. Look carefully at what conditions (i) and the correct (ii) mean. This is not a problem of how to place 10 objects in 3 containers. Up to 30 objects could be used.
• Aug 30th 2006, 12:47 PM
CaptainBlack
Quote:

Originally Posted by CaptainBlack
Consider the sets $A_1,\ A_2,\ A_3$ to be containers into which
counters labled $1,\ 2,\ 3,\ \dots \,\ 10$ are to be placed.

RonL

Of course after reading JakeD's response I realise that I was solving the
problem with:

$A_i \cap A_j = \emptyset,\ \ i\ne j$ :(

RonL
• Aug 31st 2006, 02:46 PM
Jameson
Ok, I finally got it.

Drawing a Venn Diagram with three circles there are seven distinct regions. From condition 1 all of these regions may be used, but because of condition 2 the center region is excluded.

So there are 6 regions which we can place 10 elements in. Thus the answer is $10^6$ ways, but in the form they requested $2^{10}3^{10}$