Results 1 to 9 of 9

Math Help - Putnam proof

  1. #1
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599

    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?
    Last edited by Jameson; August 30th 2006 at 12:52 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    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).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Apr 2006
    Posts
    399
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    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
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599
    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}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Putnam Problem
    Posted in the Math Puzzles Forum
    Replies: 5
    Last Post: September 8th 2010, 12:01 PM
  2. Putnam 1990 A1
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: June 20th 2010, 11:23 AM
  3. Putnam Problem of the Day (3)
    Posted in the Math Challenge Problems Forum
    Replies: 6
    Last Post: June 11th 2010, 02:31 AM
  4. Putnam Problem of the Day (2)
    Posted in the Math Challenge Problems Forum
    Replies: 0
    Last Post: May 24th 2010, 06:21 PM
  5. Putnam question
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: December 11th 2009, 06:31 PM

Search Tags


/mathhelpforum @mathhelpforum