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.
As Tristan says correctly, this works if (M,N) = (K,K+1)
where K is an integer >= 2
(it also works if K = 1, but the problem statement has ruled this out).
In addition, it works if (M,N) = (GK,G*(K+1))
where K is an integer >= 2 and G is an integer >= 1
e.g., (2,3) (M=2, G= 1)
or (4,6) (M=2, G=2)
or (400,600) (M = 2, G = 200)
or (25,30) (M= 5, G = 5)
To test if two numbers M and N satisfy the condition, divide by
their greatest common divisor G. If the difference between the
resulting integers = 1, then 50% of integers divisible by one or both
of them is divisible by the greater of them, over any large random set.
If we allow negatives, it also works for
(-GK,G*(K+1)) and (GK,-G*(K+1)) and (-GK,-G*(K+1)).
/******************/
Proof:
Let
G = the greatest common divisor of M and N. Then M and N can be
expressed as GK and GJ, where K and J are relatively prime.
Consider the set of all integers between 1 and their least common
multiple, JKG, which are divisible by either M or N prime.
J of these are divisible by M.
And K of them are divisible by N.
But this double counts JKG, which is divisible by both.
Altogether, K out of J+K-1 are divisible by N.
(1/2) = K/(J+K-1), so 2K = J + K - 1 and J = K+1.
So any numbers of the form (GK,G*(K+1)) will satisfy the problem condition.
Edited on June 17, 2006, 2:49 pm
Edited on June 17, 2006, 6:55 pm
Edited on June 17, 2006, 7:18 pm
More values and a proof
