1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Another question on SDR's

  1. Jan 22, 2008 #1
    1. Suppose A1,A2,...,An contain 2,3,...,n+1 elements, respectively. Show that this collection has at least 2^n SDRs. Find such a collection with exactly 2^n SDRs

    2. These are the only equations given in my notes regarding "the number of SDRs a collection of sets has"
    k! if k <= n
    k!/(k-n)! if k > n

    3. Ok, for part one of the question, I know that I have to show that k! > 2^n. I can't seem to decide what k is in this case, is k = 2? or is k variable for each set within the collection?

    And for part 2, I'm just doing my best to guess, but to have exactly 2^n SDR's I think that each successive set in the collection must have 2 elements that don't exist in the previous set. Is my line of thinking correct?

    Thank you in advance for any help.
    Last edited: Jan 22, 2008
  2. jcsd
  3. Jan 22, 2008 #2


    User Avatar
    Science Advisor

    It might be helpful if you would define "DR" and "SDR" here.
  4. Jan 22, 2008 #3
    Sorry. I'll do just that.

    First of all, DR was a typo.
    SDR = System of Distinct Representatives
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Another question on SDR's
  1. Another question (Replies: 3)

  2. Another question (Replies: 3)