Out of a quite large set of random integer numbers, I selected only those that were multiples of M or N, and rejected the rest. In the resulting (obviously smaller) subset, 50% of the numbers were multiples of N. Curiously, M wasn't 50% of N.

What is the minimum possible pair of values for M and N? The next such pair? Are there infinite possible such pairs?

PS. If you don't know the reason for the "Cherry picking" title, check this reference or this other one.

PPS. And if "a quite large set" of numbers doesn't satisfy you, imagine an infinite set, with every possible integer.

Try M=2, N=3


In general, it seems that this is true if N-1 = M > 1 (not including possible negative pairs).

The reason for this is that M and N are coprime, so the LCM is NM. From 1 to NM, there are M-1 integers that are multiples of N, N-1 integers that are multiples of M, and one multiple of both N and M.  Therefore, there are M integers that are multiples of N, and N-1=M integers that are not multiples of N.  Of course, this same pattern repeats every NM integers, so as the set of integers approaches infinite size, the percentage of N-multiples will approach 50%.

I leave the proof/disproof of uniqueness to someone else.

Posted by Tristan on 2006-06-17 10:51:16