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-




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}! \\ $$

Leave a Reply

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