Question

This question concerns bit strings of length six. These bit strings can be divided up into four types depending on their initial and terminal bit. Thus the types are: 0XXXX0, 0XXXX1, 1XXXX0, 1XXXX1.
How many bit strings of length six must you select before you are sure to have at least 6 that are of the same type? (Assume that when you select bit strings you always select different ones from ones you have already selected.)

Answer 1

$\text {Let }\newline X_1=\{0xxxx0\}\newline X_2=\{0xxxx1\}\newline X_3=\{1xxxx0\}\newline X_4=\{1xxxx1\}\text{ corresponding to string set types}$

$X=\{xxxxxx\}\text{ set bit strings of length 6}$

$\text{where }x\isin\{0,1\}$

$X_1\cup{X_2}\cup{X_3}\cup{X_4}=X$

$X_i\cap{X_j}=\emptyset\text{ if }i\not=j\text{ and }i,j\isin\{1,2,3,4\}$

$\text{That is, any element from the set }X\text{ is an element of one and only one of the sets }X_i$

$\text{where } i\isin\{1,2,3,4\}$

$\text{For an unambiguous selection of 6 elements of the same type, you must choose}$

$4*5+1=21\text{ elements}$

Answer: 21