Problem Link:
Difficulty:
SIMPLE
Pre-requisites:
Ad-hoc
Problem:
Given integers N and K, pick K integers in 1…N, such that no two chosen integers are relatively prime.
Explanation:
Let us try to construct a set of K integers such that no two are coprime. If we choose a number x (>1), and pick all multiples of x, then clearly no two of them will be coprime (all the numbers are divisible by x)! Thus, we can pick a set of size floor(N/x) having such a property. Thus, it is in our interest to have x small.
Indeed, if we pick x = 2, then for any K <= floor(N/2), we can just output the set 2, 4, 6, …, 2K. Hence, we have the sufficient condition when K <= floor(N/2).
It turns out that this sufficient condition is also necessary (almost). The fact is, when K > N/2, any set of size K will have some 2 consecutive elements. These consecutive elements will then be coprime.
The only special case is where (N, K) = (1, 1). In this case, since K = 1, we can output plate 1 and we’re done.
Formally, we can prove the necessity as follows:
If K = 1, we output 1 and we are done.
If K > 1, then we can can never have 1 in our set.
Then, from (2i, 2i+1), we can pick only one of the two. That is, we can pick only one from (2, 3), (4, 5), …, which gives us the bound of floor(N/2).
Setter’s Solution:
Can be found here
Tester’s Solution:
Can be found here
(y)