Six distinct positive integers are randomly chosen between 1 and 2006, inclusive. What is the probability that some pair of these integers has a difference that is a multiple of 5?

I like this problem because it seems overwhelming at first, but a little exploration reveals the hidden structure. The lessons learned working through this problem seemed important enough to revisit again this morning.

Here’s the introduction to the problem and a few test cases:

At the end of the last video we started talking about the Pigeon Hole principle – a simple sounding, but really powerful idea in math.

In the last part of our talk today I introduced the idea of looking at the remainder when you divide by 5. This idea uses “pigeon holes” that are slightly easier to see (but only slightly), but it gave a chance to look at the problem one more time through a different lens:

So, a fun and really instructive problem. As I think about it, I’d love to see how other people would approach this problem with younger math students.

## Comments

Going in the opposite direction, what if you just choose 2 numbers (or 3, 4, 5)? Then what is the probability that two will differ by a multiple of 5?