Menu Close

Given-the-7-element-set-A-a-b-c-d-e-f-g-find-a-collection-T-of-3-element-subsets-of-A-such-that-each-pair-of-elements-from-A-occurs-exactly-in-one-of-the-subsets-of-T-

Tinku Tara 0 Comments
Pin




Question Number 24366 by Tinkutara last updated on 16/Nov/17
Given the 7-element set A = {a, b, c, d, e, f, g}, find a collection T of 3- element subsets of A such that each pair of elements from A occurs exactly in one of the subsets of T.
$$\mathrm{Given}\:\mathrm{the}\:\mathrm{7}-\mathrm{element}\:\mathrm{set}\:{A}\:=\:\left\{{a},\:{b},\:{c},\right. \\ $$$$\left.{d},\:{e},\:{f},\:{g}\right\},\:\mathrm{find}\:\mathrm{a}\:\mathrm{collection}\:{T}\:\mathrm{of}\:\mathrm{3}- \\ $$$$\mathrm{element}\:\mathrm{subsets}\:\mathrm{of}\:{A}\:\mathrm{such}\:\mathrm{that}\:\mathrm{each} \\ $$$$\mathrm{pair}\:\mathrm{of}\:\mathrm{elements}\:\mathrm{from}\:{A}\:\mathrm{occurs}\:\mathrm{exactly} \\ $$$$\mathrm{in}\:\mathrm{one}\:\mathrm{of}\:\mathrm{the}\:\mathrm{subsets}\:\mathrm{of}\:{T}. \\ $$
Commented by Rasheed.Sindhi last updated on 18/Nov/17
Questions imposed_(−) (i)How many such collections can be produced? (ii)How many 3-membered sets are necessary in order to determine a particular collection acquiring above property?
$$\underset{−} {\mathrm{Questions}\:\mathrm{imposed}} \\ $$$$\left(\mathrm{i}\right)\mathrm{How}\:\mathrm{many}\:\mathrm{such}\:\mathrm{collections} \\ $$$$\:\:\:\:\:\mathrm{can}\:\mathrm{be}\:\mathrm{produced}? \\ $$$$\left(\mathrm{ii}\right)\mathrm{How}\:\mathrm{many}\:\mathrm{3}-\mathrm{membered} \\ $$$$\:\:\:\:\:\:\:\:\mathrm{sets}\:\mathrm{are}\:\mathrm{necessary}\:\mathrm{in}\:\mathrm{order} \\ $$$$\:\:\:\:\:\:\:\:\mathrm{to}\:\mathrm{determine}\:\mathrm{a}\:\mathrm{particular} \\ $$$$\:\:\:\:\:\:\:\:\:\mathrm{collection}\:\mathrm{acquiring}\:\mathrm{above} \\ $$$$\:\:\:\:\:\:\:\:\:\mathrm{property}? \\ $$
Answered by Rasheed.Sindhi last updated on 17/Nov/17
.Strategy._(−) Possible pairs: (((ab),(ac),(ad),(ae),(af),(ag)),(,(bc),(bd),(be),(bf),(bg)),(,,(cd),(ce),(cf),(cg)),(,,,de,df,dg),(,,,,(ef),(eg)),(,,,,,(fg)) ) Take a pair from above and include any member of A(other than members of the pair) in order to make a set of 3 elements For example in pair a,b we can include c,d,e,f or g.Say we′ve made {a,b,c}. From a,b,c three pairs can be made ab,bc and ac. So cross out these from the above table of pairs.Next take another pair which is not crossed out and include an element in it in such a way that all the three pairs produced (from the set of three elements) are new i-e not crossed out. Go on till all the pairs of above table cross out. T={{a,b,c},{a,d,e},{a,f,g},{b,d,f}, {b,e,g},{c,d,g},{c,e,f}}
$$\:\:.\underset{−} {\mathrm{Strategy}.} \\ $$$$\mathrm{Possible}\:\mathrm{pairs}: \\ $$$$\:\begin{pmatrix}{\mathrm{ab}}&{\mathrm{ac}}&{\mathrm{ad}}&{\mathrm{ae}}&{\mathrm{af}}&{\mathrm{ag}}\\{}&{\mathrm{bc}}&{\mathrm{bd}}&{\mathrm{be}}&{\mathrm{bf}}&{\mathrm{bg}}\\{}&{}&{\mathrm{cd}}&{\mathrm{ce}}&{\mathrm{cf}}&{\mathrm{cg}}\\{}&{}&{}&{\mathrm{de}}&{\mathrm{df}}&{\mathrm{dg}}\\{}&{}&{}&{}&{\mathrm{ef}}&{\mathrm{eg}}\\{}&{}&{}&{}&{}&{\mathrm{fg}}\end{pmatrix} \\ $$$$\mathrm{Take}\:\mathrm{a}\:\mathrm{pair}\:\mathrm{from}\:\mathrm{above}\:\mathrm{and} \\ $$$$\mathrm{include}\:\mathrm{any}\:\mathrm{member}\:\mathrm{of}\:\mathrm{A}\left(\mathrm{other}\right. \\ $$$$\left.\mathrm{than}\:\mathrm{members}\:\mathrm{of}\:\mathrm{the}\:\mathrm{pair}\right)\:\mathrm{in} \\ $$$$\mathrm{order}\:\mathrm{to}\:\mathrm{make}\:\mathrm{a}\:\mathrm{set}\:\mathrm{of}\:\mathrm{3}\:\mathrm{elements} \\ $$$$\mathrm{For}\:\mathrm{example}\:\mathrm{in}\:\mathrm{pair}\:\mathrm{a},\mathrm{b}\:\mathrm{we}\:\mathrm{can} \\ $$$$\mathrm{include}\:\mathrm{c},\mathrm{d},\mathrm{e},\mathrm{f}\:\:\mathrm{or}\:\:\mathrm{g}.\mathrm{Say}\:\mathrm{we}'\mathrm{ve} \\ $$$$\mathrm{made}\:\left\{\mathrm{a},\mathrm{b},\mathrm{c}\right\}.\:\mathrm{From}\:\mathrm{a},\mathrm{b},\mathrm{c}\:\mathrm{three} \\ $$$$\mathrm{pairs}\:\mathrm{can}\:\mathrm{be}\:\mathrm{made}\:\mathrm{ab},\mathrm{bc}\:\mathrm{and}\:\mathrm{ac}. \\ $$$$\mathrm{So}\:\mathrm{cross}\:\mathrm{out}\:\mathrm{these}\:\mathrm{from}\:\mathrm{the}\:\mathrm{above} \\ $$$$\mathrm{table}\:\mathrm{of}\:\mathrm{pairs}.\mathrm{Next}\:\mathrm{take}\:\mathrm{another} \\ $$$$\mathrm{pair}\:\mathrm{which}\:\mathrm{is}\:\mathrm{not}\:\mathrm{crossed}\:\mathrm{out}\:\mathrm{and} \\ $$$$\mathrm{include}\:\mathrm{an}\:\mathrm{element}\:\mathrm{in}\:\mathrm{it}\:\mathrm{in}\:\mathrm{such} \\ $$$$\mathrm{a}\:\mathrm{way}\:\mathrm{that}\:\mathrm{all}\:\mathrm{the}\:\mathrm{three}\:\mathrm{pairs} \\ $$$$\mathrm{produced}\:\left(\mathrm{from}\:\mathrm{the}\:\mathrm{set}\:\mathrm{of}\:\mathrm{three}\right. \\ $$$$\left.\mathrm{elements}\right)\:\mathrm{are}\:\mathrm{new}\:\mathrm{i}-\mathrm{e}\:\mathrm{not}\: \\ $$$$\mathrm{crossed}\:\mathrm{out}.\:\mathrm{Go}\:\mathrm{on}\:\mathrm{till}\:\mathrm{all}\:\mathrm{the} \\ $$$$\mathrm{pairs}\:\mathrm{of}\:\mathrm{above}\:\mathrm{table}\:\mathrm{cross}\:\mathrm{out}. \\ $$$$ \\ $$$$\mathrm{T}=\left\{\left\{\mathrm{a},\mathrm{b},\mathrm{c}\right\},\left\{\mathrm{a},\mathrm{d},\mathrm{e}\right\},\left\{\mathrm{a},\mathrm{f},\mathrm{g}\right\},\left\{\mathrm{b},\mathrm{d},\mathrm{f}\right\},\right. \\ $$$$\left.\:\:\:\:\:\:\:\:\:\:\:\left\{\mathrm{b},\mathrm{e},\mathrm{g}\right\},\left\{\mathrm{c},\mathrm{d},\mathrm{g}\right\},\left\{\mathrm{c},\mathrm{e},\mathrm{f}\right\}\right\} \\ $$
Commented by Tinkutara last updated on 17/Nov/17
Thank you very much Sir!
$$\mathrm{Thank}\:\mathrm{you}\:\mathrm{very}\:\mathrm{much}\:\mathrm{Sir}! \\ $$

Pin

Leave a Reply

Your email address will not be published. Required fields are marked *