A subset S of {1,2,…,n} is said to be packed if whenever i,j∈S the number ⌊i+j2⌋ is also in S?
A subset S of {1,2,…,n} is said to be packed if whenever i,j∈S the number ⌊(i+j)/2⌋ is also in S. Determine how many subsets of {1,2,…,25} are packed.
Thing to be noted:
i and j need not be distinct. If i=j is in the set, then clearly so is ⌊(i+j)/2⌋.
The sets S and the empty set clearly satisfy the conditions of the question, and should be included in your count.
More Questions From This User See All
Answers & Comments
Verified answer
You can show that the following sets are packed:
{5}
{6,7,8,9,10,11}
{1,2}
In fact, the packed sets are exactly the ones that look like
{x | x is an integer and a <= x <= b}
for some integers a,b in the set S.
-------
To count these, consider a few cases:
(1) The empty set: 1 packed set
(2) The singletons: 25 packed sets
(3) All the others: (25 choose 2) = 300 packed sets
Therefore there are 326 total packed subsets of S.
=====
Note: ⌊x⌋ is the floor of x, which is the greatest integer <= x. Therefore, we have
⌊(1+2)/2⌋ = ⌊1.5⌋ = 1
is still an integer. In fact, it will always be an integer.
One thing to note is that your set cannot have both odd and even integers, since this would preclude (i+j)/2 from necessarily being an integer. Thus we're looking at subsets of the even integers: {2,4,...,24} and subsets of {1,3,...,25}.
As you noted, every single value subset will be packed. For two elements, however we run into problems. Let {a,b} be a set (even or odd doesn't matter). Then (a+b)/2 is, by definition, less than b and greater than a. Thus it can't be in the set {a,b}. In fact, we will run into this problem no matter what size our subset is.
{a,b, ..., z} arbitrary length (using letters since subscripts are atrocious on yahoo answers) ordered from least to greatest. If it were packed, then (a+b)/2 would by necessity be inside the set. But (a+b)/2 is greater than a, and less than b, and by the ordering no other value will be in that range.
Thus the only packed sets we have are single element sets and the empty set giving us a total of 26 of them.