pigeonhole principle homework question

Question

These are Homework question. They are pigeon hole principle questions and I have a very hard time with these unless I have worked on a similar problem before.

Q.1. Prove that if we select 87 numbers from the set $S = {1,2,3,....,171}$ then there are at least two consecutive numbers in our selection.

Q.2. Let $n\ \epsilon \ Z^+$. Show that there exists $a,b \ \epsilon \ Z^+$ with $a \neq b$ such that $n^a-n^b $is divisible by $10$

Any help, hints would be great.

Answer 1

HINTS:

1. Divide $S$ into the sets $\{1,2\},\{3,4\},\{5,6\},\ldots,\{169,170\},\{171\}$. How many sets is that? How many numbers are you choosing from $S$?

2. $n^a-n^b$ is divisible by $10$ if and only if its ordinary base-ten representation ends in $0$. This happens exactly when $n^a$ and $n^b$ end in the same digit. There are only $10$ possible last digits, and there are infinitely many possible exponents, so there must be two powers of $n$ with ... ?

Answer 2

1. The worst case is $2n+1$, $n \geq 0$ ie. you choose $\{1,3,5,...171\}$. 171 is when $n$ is 85. For the left two number , any number you choose will form three consecutive number, in form of $2n, 2n+1, 2n+2$.
2. As Brian said, $10 \hspace{2pt}|\hspace{2 pt} n^{a} -n^{b}$ if and only if it's remaining when divided by ten is same . i.e same class in modulo 10. Notice that for any $x^{y}$ it's last digit will repeat after maximum 5 times. So you got infinite number of same last digit pair.