Pigeonhole principle and counting

[TalonStriker]

Homework Statement

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.

Homework Equations

Pigeonhole principle.

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 $$\infty X \infty$$ array, they could be counted by the diagonals. No such rule exists for functions over N.

 

[piercas]

it is important to understand and apply mathematical principles to solve problems and make predictions. In this case, the pigeonhole principle can be applied to both problems.

For the first problem, we are given that there are 100 subsets with the same sum. This means that there must be at least 100 subsets in total. To minimize the value of Y, we can assume that there are exactly 100 subsets with the same sum, and each subset has a sum of 5. This means that Y = 500, as there are 100 subsets of 5 elements each, giving a total of 500 elements in the set. However, it is not necessary to prove that this is the smallest possible value of Y, as the question only asks for the smallest value we can come up with.

For the second problem, we are asked to show that the set of all functions from natural numbers to natural numbers (FUNC) is not countable. This may seem counterintuitive, as the set of natural numbers is countable. However, the set of functions from natural numbers to natural numbers is uncountably infinite, meaning that there are more functions than there are natural numbers. This can be shown using a proof by contradiction, assuming that FUNC is countable and arriving at a contradiction. This is a well-known result in mathematics, known as Cantor's diagonal argument.