Q.7.16 - A First Course in Probability

Question

Suppose that each of the elements of $S=\{1,2,\dots ,n\}$ is to be colored either red or blue. Show that if $A_1,\dots ,A_r$ are subsets of $S$, there is a way of doing the coloring so that at most $\sum _{i=1}^r(1/2{)}^{\left|A_i\right|-1}$ of these subsets have all their elements the same color (where $\left|A\right|$ denotes the number of elements in the set $A$).

Step-by-Step Solution

Answer

It has been shown that at most $\sum _{i=1}^r{\left(\frac{1}{2}\right)}^{\left[A_i\right]-1}$of the subsets $A_1,A_2,\dots ,A_r.$

Step 1: Given Information

Elements $S=\{1,2,..,n\}$is to be colored either red or blue.

$A_1,\dots ,A_r$are subsets of$S$,

Show that at most $\sum _{i=1}^r(1/2{)}^{\left|A_i\right|-1}$of the given subsets.

Step 2: Explanation

Each of the element of $S=\{1,2,\dots ,n\}$ is to be colored red or blue suppose that each element is independently, equally likely to be colored Red or Blue.

Each elements is Red or Blue with probability $\frac{1}{2}$

Let ${\mathrm{E}}_{\mathrm{i}}=\left\{\text{ All the elements of ith subject }{\mathrm{A}}_{\mathrm{i}}\text{ are of the same colour }\right\}$

$\therefore \mathrm{P}\left[{\mathrm{E}}_{\mathrm{i}}\right]=2.{\left(\frac{1}{2}\right)}^{\left[{\mathrm{A}}_{\mathrm{i}}\right]}={\left(\frac{1}{2}\right)}^{\left[{\mathrm{A}}_{\mathrm{i}}\right]-1} \forall i=1,2,..,n$

Where $\left[{\mathrm{A}}_{\mathrm{i}}\right]=$Number of elements in ${\mathrm{A}}_{\mathrm{i}} \forall i=1,2,..,n$

$\therefore \sum _{i=1}^r\mathrm{P}\left[{\mathrm{E}}_{\mathrm{i}}\right]=\sum _{i=1}^r{\left(\frac{1}{2}\right)}^{\left[{\mathrm{A}}_i\right]-1}$

Step 3: Explanation

As from Boole's inequality

$\mathrm{P}\left[\underset{i}{\cup }{E}_i\right]\le \sum _i\mathrm{P}\left[{\mathrm{E}}_{\mathrm{i}}\right]$

$\Rightarrow$ At most $\sum _{\mathrm{i}=1}^{\mathrm{r}}{\left(\frac{1}{2}\right)}^{\left[\lambda {\lambda }_i\right]-1}$of the subsets of $A_1,A_2,\dots ,A_r$

Step 4: Final Answer

Hence, it has been shown that at most $\sum _{i=1}^r(1/2{)}^{\left|A_i\right|-1}$of the subset $A_1,A_2,\dots ,A_r.$

And have all their elements the same color.