Functions, Pigeonhole Principle Help

Question

Questions On Here

I understand the basis of functional composition and powersets, however I'm really not sure how to go about answering these questions...

Would I use an example set? Eg {1,2} and then derive the power set?

Answer 1

Hint: For each question it suffices to write the problem in terms of $f$, $A$, $B$, and verify $|A| > |B|$.

Hint: Let $f$ map each of your $12$ integers to its remainder after division by $11$.

Hint: For the fourth question, maybe consider $A$ being the five integers you pick, and $B$ being the list of possible [unordered] pairs of integer that each sum to $9$, and $f$ mapping an integer to the unique pair in $B$ that contains it. For example, $f$ maps $3$ to the pair $(3,6)$.

Answer 2

Just state $|X| > |Y|$ so no fuction is injective so there are two $a,b\in X; a\ne b$ where $f(a)=f(b)$.

1) $|P(A)| = 2^{|A|} > |A|$ so no $f:P(A)\to A$ is injective.

2) People have tens of thousands of hairs but no-one has more than.... say 50 thousand. I have no idea what the population of Sheffield is but I imaging it must be more than 100,000. 100,000 > 50,000 so any $f(a) = $ number of hairs $a$ has is not injective. So there are $a,b$ in Sheifield so that $f(a)=f(b)$ and they have the same number of hairs. etc.

3) $12$ elements of your set and $11$ posible remainders when you divide by $11$. $12 > 11$ so.... there are two numbers $a\ne b$ with the same remainder when divided by $11$.

4) There are $4$ pairs of numbers that add to nine: $(1,8)(2,7),(3,6)(4,5)$. You have $5$ numbers. $5 > 4$ so.... there are two numbers $a$ and $b$ that belong to the same pair.

====

If you didn't know the pigeon hole principal you would do number $4$ like this.

Let's try to get a set where no two numbers add to $9$. Suppose the first number in the set is $a$. All things being equal, I might as well assume $a =1$. Let the second number be $b$. $b$ is and not $8$ (we'd have $1+8 =9$) so assuming we don't we might as well assume $b = 6$. $c \ne 1,6$ and can not be $8,3$ ($3+6=9$) so without loss of generality, we can assume $c =4$. So $d\ne 1,6,4$ and can not be $8,3$ or $5$ might as well assume $d=2$. So $e \ne 1,2,4,6$ and can not be $8,7,5,$ or $3$ so it can be.... wait, there's nothing left.

And THAT is the pigeon hole principal. The moment we realize "wait, there is nothing left".

And we can predict that that moment is inevetable. There are $5$ numbers in our set and there are only $4$ possible pairs that add to $9$. We will have to run out of possible pairs.

We might as well point that out at the very beginning and not go through the wasted effort of trying to find $5$ numbers from only $4$ different pairs.