$F$ is a set of $101$ functions from $\{1,2,\ldots,10\}$ to itself. Prove that $\exists f,g\in F$ and $\exists i,j\in\{1,2,\ldots,10\}=[10]$ so $f(i)=g(i)$ and $f(j)=g(j)$.
I didn’t manage to solve this problem. It looks like pigenhole principle but for some reason it didn’t work for me any idea? Thank you.
When $m$ and $n$ are positive integers, how many distinct functions are there from $\{1,2,...,n\}$ to $\{1,2,...,m\}$?
To define a function $f:\{1,...,n\}\to\{1,...,m\}$ means that for each element $i\in\{1,...,n\}$ we have specified its image $f(i)\in\{1,...,m\}$. Since the codomain has $m$ many elements, there are $m$ choices that we have for $f(i)$. Because there are $n$ many points to specify the image of, we see that there are $m^n$ total functions.
Now we can solve your problem. Take $i=1$ and $j=2$. Then each map $f:\{1,...,10\}\to \{1,...,10\}$ restricts to a map $\tilde{f}:\{1,2\}\to\{1,...,10\}$. From the argument above, we see that there are $10^2=100$ maps $\{1,2\}\to\{1,...,10\}$. Thus, if we have a collection of $101$ maps $f_1,...,f_{101}$ from $\{1,...,10\}$ to itself, then by restricting their common domains we get a collection of $101$ maps $\tilde{f}_1,...,\tilde{f}_{101}$ from $\{1,2\}$ to $\{1,...,10\}$. Since we have shown that there are only $100$ such maps, there must exist $k,l\in\{1,...,101\}$ where $\tilde{f}_k=\tilde{f}_l$. That is, $f_k(1)=f_l(1)$ and $f_k(2)=f_1(2)$ as desired.