06/06/2020 (2011: National Team Round, Problem 8)

Q: A subset of the integers {1, 2, 3, ..., 499, 500} has the property that none of its members is 5 times another. What is the maximum number of members in such a subset?

A: 416

We know that all the integers that aren't multiples of 5 can be in this subset, so 4/5 of the 500 numbers = 400 numbers are in the subset.

Because, so far, no multiple of 5 has been included in the subset, that means multiples of 5 * 5 can be included (as long as they aren't multiples of 5 * 5 * 5). 5 * 5 = 25, and there are 20 multiples of 25 less than or equal to 500. 5 * 5 * 5 = 125, and there are 4 multiples of 125 less than or equal to 500. That means there are 20 - 4 = 16 multiples of 5 * 5 that can be included in this subset.

400 numbers + 16 numbers = 416 numbers.