WordGPT

Pigeonhole: six integers, two differ by a multiple of 5

Exercise · Level 2 (Easy)

Prove that among any 6 integers, two have a difference divisible by 5.

a1,…,a6 ⇒ 5∣ai−aja_1,\dots,a_6\ \Rightarrow\ 5\mid a_i-a_j

wordgptpro.com

Solution

  1. On division by 5 there are only five possible remainders: 0, 1, 2, 3, 4 (the pigeonholes). Six integers (the pigeons) cannot all go into different holes.

  2. So two integers ai,aja_i,a_j leave the same remainder, and their difference is a multiple of 5:

    ai=5q+r, aj=5q′+r⇒ ai−aj=5(q−q′)\begin{aligned}a_i&=5q+r,\ a_j\\&=5q'+r\\&\Rightarrow\ a_i-a_j\\&=5(q-q')\end{aligned}
    (1)
Answer5∣ai−aj for some i≠j5\mid a_i-a_j\ \text{for some } i\ne j

wordgptpro.com

Need a hint?

How many different remainders are possible when you divide by 5?

Six integers fill only five possible remainders mod 5, so two share a remainder and their difference is divisible by 5.

How to work it out

  1. On division by 5 there are only five possible remainders: 0, 1, 2, 3, 4 (the pigeonholes). Six integers (the pigeons) cannot all go into different holes.

  2. So two integers ai,aja_i,a_j leave the same remainder, and their difference is a multiple of 5:

    ai=5q+r, aj=5q′+r⇒ ai−aj=5(q−q′)\begin{aligned}a_i&=5q+r,\ a_j\\&=5q'+r\\&\Rightarrow\ a_i-a_j\\&=5(q-q')\end{aligned}
    (1)
LaTeX source of the formulas on this page
\[ 5\mid a_i-a_j\ \text{for some } i\ne j \]
\[ a_i=5q+r,\ a_j=5q'+r\ \Rightarrow\ a_i-a_j=5(q-q') \]

Questions

What is the answer to: Pigeonhole: six integers, two differ by a multiple of 5?

Six integers fill only five possible remainders mod 5, so two share a remainder and their difference is divisible by 5.

What is the key idea?

More objects than boxes means some box holds two (the pigeonhole principle).

Is there a hint?

How many different remainders are possible when you divide by 5?

Related problems

More number theory problems

    Pigeonhole: six integers, two differ by a multiple of 5: answer and solution | WordGPT