Permutations with pigeonhole principle quesion

59 Views Asked by At

I have set G of 101 functions from [10] to [10] ([10] is S10).

I need to prove that there are 2 functions (a,b) from the set G, and two numbers I,j that belongs to [10], that sustain a(i) = b(i) and a(j) = b(j). I understand that I need to use the pigeonhole principle, but I can't detect the items and the containers in order to use the pigeonhole principle.

1

There are 1 best solutions below

1
On BEST ANSWER

Take first any two numbers i and j in $[10]$, so between 1 and 10. Let $f$ be a map from $[10]$ to $[10]$. There is then 10 possibilities for the value of $f(i)$ and also 10 for the value of $f(j)$. There is then 100 possibilities for the values of $(f(i), f(j))$. Since you have 101 functions, you can use the pigeonhole principle and obtain the fact that there is another map $g$ such that $g(i)=f(i)$ and $g(j)=f(j)$.

Did I understood well what you wanted? I ask that because I proved here that your statement is true for any pair $(i,j)$, and not particularly for a special one.