1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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 ... ?

$\endgroup$
4
  • $\begingroup$ thanks brian, a quick question that pops in my head is why cant the sets be {1,2},{2,3},{3,4} as i was thinking maybe thats how they should be $\endgroup$ – Kj Tada Jul 5 '13 at 7:57
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Jul 5 '13 at 8:16
  • $\begingroup$ thanks Brian. I think that was where I was stuck for the first one, still working out the second one using your hint. $\endgroup$ – Kj Tada Jul 5 '13 at 8:17
  • $\begingroup$ @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}$. $\endgroup$ – Brian M. Scott Jul 5 '13 at 8:19
2
$\begingroup$
  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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.