Results 1 to 1 of 1

Math Help - Combinatorics problem

  1. #1
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976

    Combinatorics problem

    New to this forum, so sorry if this is in the wrong place!

    Anyway, this was in my Combinatorics final, but during the course we also introduced uses of Linear Algebra, Set Theory and Group theory in the field so it can be related to those as well. Question is attached below.

    It's easy to see that there can only be one intersection of size one between any two sets -- otherwise we get L = a^3 = b^3 but a != b.

    So would it be possible to show, maybe by induction, that for every k <= n there can only be one possible k-sized intersection? Because this would mean that there are m different intersections (including the empty set), but an intersection of subsets can only be as big as the original one, meaning m <= n as needed.

    Also tried approaching this with Dilworth theorem, which we did to some other stuff including the proof of Erdos-Szekeres, but that didn't really yield any result. Pigeonhole didn't work either, so I'm pretty much clueless...

    Thanks!
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. problem in combinatorics
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 21st 2011, 08:23 AM
  2. Help with combinatorics problem
    Posted in the Advanced Statistics Forum
    Replies: 5
    Last Post: December 7th 2010, 03:35 PM
  3. Combinatorics Problem
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: May 1st 2010, 05:22 PM
  4. Combinatorics problem
    Posted in the Statistics Forum
    Replies: 6
    Last Post: November 12th 2009, 07:05 AM
  5. Combinatorics Problem
    Posted in the Statistics Forum
    Replies: 1
    Last Post: March 30th 2008, 05:11 AM

Search Tags


/mathhelpforum @mathhelpforum