How many integers from 100 through 999 must you pick in order to be sure that at least two of them have a digit in common? (For example, 256 and 530 have the common digit 5.)
In the worst case I can pick 111, 222, 333, 444, 555, 666, 777, 888, 999. Whatever next integer I choose will have a common digit with one of those above, therefore the answer is 10. But how to apply The Pigeonhole Principle?
let $S=[100, 999]$
let $S'\subseteq S, |S'|>9$ (because I know that the answer is 10). $S'$ is the integers I pick from $S$ at least two of which have a digit in common.
let $f: S' \rightarrow T$ where $T$ is some set, $|T|=9$ (again, because I know that the answer is 10).
If I knew the definition of $f$ and $T$ I would proceed as follows:
Let $k\in Z^+$, by the generalised Pigeonhole Principle $k<\frac{|S'|}{|T|} \rightarrow \exists t\in T(|f^{-1}(t)|=k+1)$, $f^{-1}(t)$ is the inverse image of $t$
The exercise says at least two numbers picked from $S$ to have a digit in common, therefore I want $k=1$:
$1<\frac{|S'|}{9}, 9<|S'|$
$\therefore |S'|\geq 10$ in order to guarantee that at least 2 integers in $S'$ have a digit in common.
I'm struggling to find the set $T$ and the function $f$. What could they be?