Let $S$ be a set containg $n$ elements, say $S=\{x_1,x_2,\dots,x_n\}$. Suppose that $\{y_1,y_2,\dots, y_n\}$ are distinct elements from $S$. How to prove that $\{y_1,y_2,\dots,y_n\}=S$ via the pigeonhole principle?
I was thinking about it for a while but I do not understand how to use the pigeonhole principle.
On
I'm not sure how would you do this by pigeonhole principle. I would do like this:
Suppose $\{y_1,y_2,\dots,y_n\}\varsubsetneq S$ then we have a subset in $S$ which has the same number of elements as does $S$ and it is not $S$. A contradiction since $S$ is finite.
On
In mathematics, the pigeonhole principle states that if n items are put into m container, the n items must be more than m container. In your case, suppose that, elements of n contained between x and y in the set of Y. Then,
If n elements > set of S, where n elements > 1, and n elements € aka contained of x and y, Then, it agrees the principle of pigeonhole where, n elements > set of S, containing the sub-element of X and Y.
One idea would be to consider the $x_i$ as boxes (or pigeon holes or whatever), and then some $y_j$ is put in the box $x_i$ precisely if $y_j = x_i$. By the pigeon hole principle, the $n$ $y$'s can either be placed in $n$ separate boxes, or one box will have to contain at least two $y$'s. But this last possibility means that two $y$'s are equal to the same $x$, contradicting distinctness of the $y$'s.