edited by
2,081 views
11 votes
11 votes

Suppose $(S_{1}, S_{2},\ldots,S_{m})$ is a finite collection of non-empty subsets of a universe $U.$ Note that the sets in this collection need not be distinct. Consider the following basic step to be performed on this sequence. While there exist sets $S_{i}$ and $S_{j}$ in the sequence, neither of which is a subset of the other, delete them from the sequence, and 

  1. If $S_{i}\cap S_{j}\neq \emptyset $, then add the sets $S_{i}\cup S_{j}$ and $S_{i}\cap S_{j}$ to the sequence;
  2. If $S_{i}\cap S_{j} = \emptyset$, then add only the set $S_{i}\cup S_{j}$ to the sequence.

In each step we delete two sets from the sequence and add at most two sets to the sequence. Also, note that empty sets are never added to the sequence. Which of the following statements is TRUE?

  1. The size of the smallest set in the sequence decreases in every step
  2. The size of the largest set in the sequence increases in every step
  3. The process always terminates
  4. The process terminates if $U$ is finite but might not if $U$ is infinite
  5. There is a finite collection of subsets of a finite universe $U$ and a choice of $S_{i}$ and $S_{j}$ in each step such that the process does not terminate
edited by

3 Answers

Best answer
3 votes
3 votes

There are $m$ sets in the initial sequence. If we pick two sets $S_i$ and $S_j$ NEITHER of which are subsets of each other we add

  1. $S_i \cup S_j$
  2. $S_i \cap S_j$ if it is not NULL.

So, the two added sets are not eligible to be picked as a pair as INTERSECTION is always a subset of UNION. So, in each step we are removing a pair of eligible sets. But the addition of set(s) can cause more eligible pairs to be created. 

With $m$ sets we can only have ${}^mC_2$ pairs possible. So, if we repeat the procedure for ${}^mC_2$ times, and number of times $S_i \cap S_j = \phi$ is $k,$

  • Number of sets reduces by $k$
  • Number of ineligible pairs will be $\geq {}^mC_2 -k$
  • Number of possible eligible pairs $ \leq {}^{m-k}C_2 - \left({}^mC_2 -k\right)$
    $ \implies \frac{(m-k) (m-k-1)} {2}- \frac{m(m-1)}{2} + k$
    $= \frac{m^2-mk-m-mk+k^2+k-m^2+m}{2}+k$
    $ = \frac{k^2-2mk+k}{2} + k $
    $= k\left[ \frac{k-2m+1}{2}+1\right]$
    Maximum value of $k$ is $m$. If we put $k = m$ we get
    $m\left[ \frac{m-2m+1}{2}+1\right] = \frac{-m^2}{2}+\frac{3m}{2} \leq 0$ for $m \geq 3$
  • i.e., for all $m \geq 3$ after some finite moves we are left with $0$ eligible pairs to choose. 
  • For $m=1$ since there are no eligible pairs, process cannot start. For $m=2$ there can be maximum one eligible pair and after one step this must reduce to no eligible pairs.
  • So, the process always terminates.
  • PS: Even if each of the sets is infinite it won't affect the termination of the process.

Option C.

selected by
0 votes
0 votes

The Answer should be $E$.

Let's say my Universe consist of only two elements $\{1,2\}$ and I define two subsets $s_1 = \{1\}, s_2 = \{1,2\}.$ And Sequence $S = s_1s_2 = \{1\}\{1,2\}$.

Initially - $\{1\}\{1,2\}$
$Step \ 1$ - $\{1,2\}\{1\}$

$S_1 \cap S_2$ is not null so we delete these two sets and add $S_1 \cup S_2$ which will be = $\{1,2\}$ and there intersection which will be = $\{1\}$. Now we got the same sets in the sequence again. If we again do the same procedure then again we get the same set. So only Option E matches.

$Step \ 2$ - $\{1\}\{1,2\}$
$Step \ 3$ - $\{1,2\}\{1\}$
$\vdots$

A is false likewise B because the size of smallest and largest set is constant in every step. Infact smallest set and largest set can change in any step.

Note that as soon as we find 2 consecutive sets in the sequence such that one is the subset of other, they will get repeated again and again and the process never terminates.
So C and D are false.

edited by
0 votes
0 votes

Option D

While there exist sets Si and Sj in the sequence, "neither of which is a subset of the other," delete them from the sequence

read the bold part again, we delete sets iff neither of two is a subset of the other.

Hence the process must terminate if U is finite.

Answer:

Related questions

21 votes
21 votes
3 answers
1
makhdoom ghaya asked Oct 17, 2015
1,979 views
Let $m$, $n$ denote two integers from the set $\{1, 2,\dots,10\}$. The number of ordered pairs $\left ( m, n \right )$ such that $2^{m}+2^{n}$ is divisible by $5$ is.$10$...