(a) Suppose F is a family of subsets of {1, 2, . . . , 60}, and that |x| = 3 for
ID: 3148570 • Letter: #
Question
(a) Suppose F is a family of subsets of {1, 2, . . . , 60}, and that |x| = 3 for all x F. Assume further that x y = for every x, y F. What is the largest possible value of |F|?
(b) For any integer k 1, a discrete interval of length k is defined as a set of k consecutive integers. [For example, {4, 5, 6, 7} and {-8, -7, -6, -5} are discrete intervals of length four, and {101, 102, 103} is a discrete interval of length three.] A family F of discrete intervals of length k is called intersecting if x y = for all x, y F. Describe a largest possible intersecting family F of discrete intervals of length 240, say how large it is, and prove that it is largest possible.
Explanation / Answer
as i get the question:
a) largest |F|= 20
as we are suppose to define:
disjoint subsets of length of 3,
so divide all elements from {1,2,...........60} into groups of size 3 each, and find how many
such disjoint subsets exists for {1,2,...........60}.
so there are 2 cases:
case1:
if it is a discrete interval of length 3, then we will clearly get 20 subsets each of size 3.
as F = ({1,2,3}, {4,5,6}, {7,8,9},.............{58,59,60} )
so largest possible value of |F| = 20.
but surprisingly this also holds true for
case 2:
imagine we want to put any 3 numbers in any subset, so although there will be many such arrangements possible but ultimately only 20 total disjoint subsets will exist at a single time.
so our concern is about | F | value which is always 20 maximum.
b)
consider any x= { k, k+1, k+2,............(k+239)), where k= largest possible integer
and consider y= { (k+240), (k+241),..................(k+479)}
then we see that x y = , , like wise we can construct infinite x,y and club them together,
so largest possible is not defined as F may contain infinite subsets of length of 240.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.