Pigeonhole principle and counting

TalonStriker

1. The problem statement, all variables and given/known data
1) 100 of the 5-element subsets of {1, . . . , Y } have the same SUM. (Fill in Y . Make Y as small as you can, however you need NOT prove that it is smallest possible. You might
need a calculator.)

2) Let FUNC be the set of all FUNCTIONS from N to N. Show that FUNC is NOT countable.

2. Relevant equations
Pigeonhole principle.


3. The attempt at a solution
1) The only thing I know is that I need to apply pigeonhole principle... Can someone give me a nudge?
2) Definitely confused here. Since the integers are countable, the naturals must be countable too right? THen how the heck are I supposed to show that FUNC isn't countable when it is?

kataya

a) Can you venture a guess as to what the pigeons and holes are?


b)
Natural numbers are countable, but that does not mean that all functions on N are countable. There are definitely an infinite number of functions mapping N to N, and there is no way to write them such that they could be counted.

The set of all rational numbers is countable, even though there is an infinite gap between any two rational numbers. If the all the rational numbers were written in an [tex]\infty X \infty[/tex] array, they could be counted by the diagonals. No such rule exists for functions over N.