Putnam proof

**Jameson** · August 29th 2006, 12:42 PM

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?

**ThePerfectHacker** · August 29th 2006, 01:45 PM

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.

**Jameson** · August 29th 2006, 02:38 PM

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.

**Jameson** · August 29th 2006, 03:05 PM

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?

**ThePerfectHacker** · August 29th 2006, 04:12 PM

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).

**ThePerfectHacker** · August 30th 2006, 08:22 AM

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.

**JakeD** · August 30th 2006, 11:30 AM

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.

**CaptainBlack** · August 30th 2006, 11:47 AM

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

**Jameson** · August 31st 2006, 01:46 PM

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}$

Thread: Putnam proof

LinkBack

Thread Tools

Display

Putnam proof

Similar Math Help Forum Discussions

Putnam Problem

Putnam 1990 A1

Putnam Problem of the Day (3)

Putnam Problem of the Day (2)

Putnam question

Search Tags