Pigeon hole principle Cartesian product?

Question

Let $A = \{0, 1, 2\}^{10}$. Show that every subset of $A$ with more than $1200$ elements contain two elements in which the $0’s$ appear in exactly the same positions.

Ok. so A is just a subset of ordered pairs. Of which there are $9$ possibilities. I guess I could group them by which have the same locations of $0's$? But from there I'm lost

do you mean $A={0,1,2}^{10}$? – Angina Seng Apr 17 '19 at 02:55 — Angina Seng, Apr 17 '19 at 02:55
Do two sets having no $0$'s count as the same position? – Jason Kim Apr 17 '19 at 03:12 — Jason Kim, Apr 17 '19 at 03:12

score 0 · Accepted Answer · answered Apr 17 '19 at 03:22

We count how many different ways a subset can contain $0$'s, where the placement of $0$ matters.

Every spot in the ordered pair either does not have a $0$ or has a $0$ (it does not matter whether the spot has a $1$ or $2$ in it). Therefore, the number of ways to arrange where the $0$'s are in an ordered pair is $2^{10}=1024$.

By Pigeonhole, we get that there must be at least $\left\lceil\frac{1200}{1024}\right\rceil=2$ ordered pairs with the $0$'s in the same places.

Pigeon hole principle Cartesian product?

1 Answers1