Question 162
Let $A_{1}, A_{2}, \ldots, A_{n}, B_{1}, B_{2}, \ldots, B_{n}$ be sets with $k$ elements each. Show that if $n \lt 2^{k-1}$ then there exist elements $a_{1}, a_{2}, \ldots, a_{n}, b_{1}, b_{2}, \ldots, b_{n}$ such that:
$$
a_{i} \in A_{i},\ b_{j} \in B_{j},\ a_{i} \neq b_{j}
$$
for all $1 \leqslant i, j \leqslant n$.
$$
a_{i} \in A_{i},\ b_{j} \in B_{j},\ a_{i} \neq b_{j}
$$
for all $1 \leqslant i, j \leqslant n$.