Answer to Question #140324 in Discrete Mathematics for Promise Omiponle

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