1

I have been given the problem

"Let P={S_1,S_2,...,S_r} be a family of distinct nonempty subsets of the set {1,2,...,n}. If the S_i are all of the same cardinality (|S_i|=k), then prove that there exists an System of Distinct Representatives (SDR) of P."

I don't understand how this can be true. Take, for example, n=10 and k=6. There are (n!)/(k!(n-k)!) distinct subsets of cardinality k, so for the example, there are 10!/(6!*4!) = 210 possible distinct subsets of size 6. Suppose that P contained all of these subsets. Then the SDR would require 210 distinct values, but we only have 10. Obviously I'm missing something, but I just don't see how this is possible. Thanks.

Update: I have checked over the textbook and i have quoted the problem correctly. This isn't the first time that I have found a typo in the textbook so it is more than likely that the question is simply wrong. I have reached out to my instructor and I will post an update when I have an answer. Thank you.

Update: The question is taken from Combinatorics and Graph Theory 2nd edition (J.M Harris, J.L Hirst, M.J Mossinghoff). The question is exercise 4 from section 1.7.2. I have spoken with my instructor and apparently we are supposed to prove this is true for certain values of r, not all values.

user2912093
  • 11
  • You are absolutely right. If you quoted the problem accurately, then the problem is wrong. It's hard to guess what the problem was intended to be. Ask your instructor. – bof Mar 25 '20 at 03:55
  • Here's the only thing I can think of that's vaguely reminiscent of your "problem": If $P={S_1,S_2,\dots,S_r}$ and $Q={T_1,T_2,\dots,T_r}$ are TWO PARTITIONS of the set ${1,2,\dots,n}$ into $k$-element sets, then there is a System of COMMON Representatives. But that's not very close at all, so it's hard to see how it could be a typo. – bof Mar 25 '20 at 04:04
  • 1
    Your question might be more useful to the rest of us if you could identify the textbook and the problem. Also, the immediate context of the problem might provide some clues as to what was meant. – bof Mar 25 '20 at 08:15

1 Answers1

1

The condition for the existence of SDR would basically be that $r\le n$. Because, just suppose that $r>n$. Now we have $n$ elements that can represent and more than $n$ members to be represented. So basically by pigeon hole principle atleast one element was used more than once for representing the members.

reyna
  • 2,101
CodeonMars
  • 11