An interesting AMC 10 probability problem

Problem 20 from the 2006 AMC 10 gave my son some trouble last night:

Problem #20 from the 2006 AMC 10 A

Here’s the problem:

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.