Solution to Find a system of distinct representatives for the following sets: {a, c, f}, {b, g}, … - Sikademy
Author Image

Archangel Macsika

Find a system of distinct representatives for the following sets: {a, c, f}, {b, g}, {c, d, h}, {a, d, j}, {e, i, k}, {f, j, l}, {b, i, k}, {e, g}, {a, c, f, h, l}, {g, k}, {b, e, i}, {d, h, j}.

The Answer to the Question
is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

By Hall's Theorem,

An SDR (System of distinct representatives) is a collection of distinct elements a_{1}, a_{2}, \ldots a_{m}\ \text{such that}\ a_{i} \in A_{i}\ \text{for}\ i=1,2, \ldots m

Let A_{1}, A_{2}, \ldots, A_m be subsets of A

A_{1}, A_{2}, \ldots, A_{m} has an SDR if

\left|\bigcup_{i \in I} A_{i}\right| \geqslant |I|

In our case

Total no. of distinct elements =12 [a, c, f, b, g, d, h, j, e, i, k, l]

Total no. of sub sets =12

Hence,

System of distinct representatives,

=\left\{a, c, f, b, g, d, h, j, e, i, k, l\right\}

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-1308-qpid-1046