Small Numbers With A Large LCM

We claim that the answer is 67. Indeed, let us first show that 67 is a viable solution. Construct the sequence of integers:

$67, 101, 102, 103, \ldots, \hat{134}, \ldots, 200$

where the 'hat' symbol means 134 is missing. This sequence works since if we pick any two integers $101\le m < n\le 200$ , then $n$ is not a multiple of $m$ so their LCM is at least $2n > 200$ . Also, if we pick 67 and another integer $m$ , then their LCM must be $67m$ since $m$ is not a multiple of 67.

On the other hand, let us show that the smallest integer must be at least 67. Indeed, we partition the set of integers $1, 2, \ldots, 200$ as a disjoint union of sets

$A_k := \{ n : n=(2k-1)2^j \text{ and } 1 \le n \le 200\},$

so that:

$\begin{aligned} A_1 &= \{1, 2, 4, 8, \ldots, 128\}, \\ A_2 &= \{3, 6, 12, 24, \ldots, 192\}, \\ &\ldots \\ A_{100} &= \{199\}\end{aligned}$

Since the LCM of any two $a_i$ 's exceeds 200, no $a_i$ is a multiple of another $a_j$ . This means, in particular, that we can only have at most one element of the sequence from each $A_k$ . But there are exactly 100 elements! So we have to pick one from each $A_k$ , i.e. the sequence comprises of $a_k = (2k-1)2^{j_k}$ , albeit in a non-sorted order. Now, consider the two elements:

$a_k = (2k-1)2^{j_k}, \quad a_{3k-1} = 3(2k-1) 2^{j_{3k-1}}.$

If $j_k \le j_{3k-1}$ then $a_{3k-1}$ is a multiple of $a_k$ , which is a contradiction. Hence $j_k > j_{3k-1}$ , and the LCM of $a_k$ and $a_{3k-1}$ is $3(2k-1) 2^{j_k}$ . Since this must be at least 201, we have:

$a_k = (2k-1)2^{j_k} \ge \frac{201}3 = 67.$

First, I included all the numbers from 101 to 200. No two of these numbers will have an LCM less than or equal to 200.

Now, we already have 100 numbers. But, we are looking for the smallest possible number. If, we include a number less than 101, we have to exclude the multiples of that number from our existing set, to keep the constraint under check.

Also, we have to take 100 numbers. So, if we include a number, we must take that number such that there is just one multiple of it in the existing set.

Let us say, we take 'a'.

'a' is the 1st multiple of 'a'

'2a' is the 2nd multiple of 'a'

So, we must include an 'a' such that only $2 \times a$ gets excluded, not $3 \times a$

In, other words, $3 \times a$ > 200 or, a > 66.66

The minimum value satisfying = $\boxed{67}$

I just assumed that the possible least common multiple above 200 is 201 and I thought that smaller divisors produces larger quotients. Then I came up with 3, so i divide 201 with 3 and I got 67.

(just guessed)