Colorings with constraints

#IE#coloring#constraints

Statement

How many $3\times3$ $0$ - $1$ matrices have at least one all- $1$ column?

Hint

IE on "column $j$ is all ones".

Show solutionHide solution

Sets. $A_j$ = column $j$ all ones. $|A_j|=2^6=64$ .

Pairs. $|A_i\cap A_j|=2^3=8$ .

Triple. $|A_1\cap A_2\cap A_3|=1$ .

IE. $3\cdot64-3\cdot8+1=169$ .

Conclusion. $169$ matrices.