The whole numbers from 1 to 2k are split into two equal-sized groups in such a way that any two numbers from the same group share no more than two distinct primefactors.
What is the largest possible value of k?
44 is the largest possible value of k.
Numbers 30, 60 and 90 all share three distinct prime factors (2, 3 and 5). If k ≥45, each of these three numbers must be assigned to one of the two groups, so one of these groups must contain at least two of these numbers. Hence k < 45.
We need to check that there is a way of splitting the numbers into two groups when k = 44. If k = 44, we can split the numbers into A = {1, 2, 3, . . . , 44} and B = {45, 46, . . . , 87, 88}. We need to show that using this way of splitting the numbers there are not two numbers, x and y, which share three prime factors and are in the same group.
Let x < y ≤ 88 sharethree prime factors(p, q, r).Then both x, y are multiples of pqr. As 3pqr ≥ 3 × (2 × 3 × 5) = 90 > 88, we have x = pqr and y = 2pqr.
As y ≤ 88 and x = y/2, we have x ≤ 44, so x is in group A.
As y = 2pqr≥ 2× (2 × 3 × 5)> 44, we have y is in group B. Hence 44 is the largest possible value of k.
Be up-to-date with our recent updates, new problems and answers!
Ask about our courses and offerings, and we will help you choose what works best for you.
