# System of Distinct Representatives

• Mar 30th 2010, 11:58 AM
coolhandluke
System of Distinct Representatives
Let $\Lambda = (A_1,A_2,...,A_n)$ be a family of sets with an SDR. Let x be an element of A_1. Prove that there is an SDR containing x, but show by example that it may not be possible to find an SDR in which x represents A_1.

SDR is a system of distinct representatives. More information here: Transversal - Wikipedia, the free encyclopedia

Supposed A_1={a,b,c}, A_2={a,b}, A_3={b,c}, a SDR could be (a,b,c).

So, with this problem, finding an example is easy.

Say, n = 4, A_1={x,a}, A_2={x}, A_3={x,a,b,c}, A_4={b,c}, then a SDR would be (a,x,c,b), or a few others, but it would not be possible to find one with x representing A_1.

I'm not sure how to prove that there is an SDR containing x. Any help?