# pigeonhole principle homework 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.

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 ... ?
• @KjTada: You want your pigeonholes to be disjoint: otherwise, you’re trying to stuff some pigeons into two holes at once, which doesn’t actually help you. You could use the sets $\{1\},\{2,3\},\{4,5\},\ldots,\{170,171\}$, though. Jul 5 '13 at 8:16
• @KjTada: You’re welcome. You might want to look at what happens to the last digit if you start with $0,1,2,\ldots,8$, or $9$ and keep raising it to higher and higher powers, e.g., $3,9,81,24\underline{3}$. Jul 5 '13 at 8:19
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.