We will prove, and apply, the Pigeonhole Principle: For any function from a finite set 𝑋 with 𝑛 elements to a finite set

[answerhappygod]

We will prove, and apply, the Pigeonhole Principle: For anyfunction from a finite set 𝑋 with 𝑛 elements to a
finite set 𝑌 with 𝑚 elements, if 𝑛 > 𝑚, then 𝑓 is notone-to-one.
[2 pts] Denote the elements of 𝑌 by 𝑦1, 𝑦2, ..., 𝑦𝑚. For each 𝑥∈ 𝑋, the must be some integer 𝑘 such that 1 ≤ 𝑘 ≤ 𝑚 and 𝑥 ∈𝑓−1({𝑦𝑘}) – why?
[1 pt] Thus, what is the relationship between 𝑋 and ⋃𝑚 𝑓−1({𝑦})? 𝑖=1 𝑖
[1 pt] The sets 𝑓−1({𝑦𝑖}), for 1 ≤ 𝑖 ≤ 𝑚, are mutually disjoint– why?
[1 pt] Thus, what is the relationship between |𝑋| and|𝑓−1({𝑦𝑖})|, for 1 ≤ 𝑖 ≤ 𝑚?
[3 pts] Supposing that 𝑓 is one-to-one, we arrive at acontradiction – what is it?
[2 pts] Suppose 𝑎1, 𝑎2, ..., 𝑎𝑛 is a sequence of 𝑛 integers noneof which is divisible by 𝑛. Show that at least one of thedifferences 𝑎𝑖 − 𝑎𝑗 (for 𝑖 ≠ 𝑗) must be divisible by 𝑛.