PRMO Model Question : "The least LCM of 20 natural numbers, not necessarily different, whose sum is 413, is _________"

Question

This is a question I saw on a PRMO model paper conducted by an institution where I study (I mean, not my school, but an entrance coaching center) on August 1, 2021 as per the calendar here. I was initially dumbstruck on seeing the question. I have never tried playing with LCM's, but I somehow managed to reach a sort-of solution, which I am adding below:

Let $a_1, a_2, a_3, \dots , a_{20}$ be the numbers. Given that their sum is odd, there are more odd numbers than even ones, or there are an odd number of odd numbers among the majority of even numbers among $a_1, a_2, a_3$, etc. Also, $413 = 21\times 19 + 14$, and since it is said that all of $a_1,a_2,a_3$, etc. aren't necessarily distinct and since one of $a_1,a_2,a_3, \dots$ is even as per the first possibility, we can say that $19\space a_i$'s are $21$ and the only even number among the $20$ integers is $14$. Also $lcm(21,21,21,... \text{(19 nos.)},14) = 42$, which is thus a possible candidate worth considering.

I stopped there. The answer key also told me that $42$ is the answer,(only in a few papers did they add the full solution, which I am in a sort of disagreement with (personally) except for those questions which I or anybody else finds helplessly hard. This time, they just gave away the key without steps and as I had found this problem a tough rock during the model exam, I longed to have a solution. I checked my copy of Justin Stevens' 'Olympiad Number Theory Through Challenging Problems' and 'Intermediate Number Theory' but in vain) but that still makes me think of the second possibility of the sum, which is quite more challenging than I thought. Also, I am not able to prove the minimality of $42$ in the solution set, which again disheartens me and makes me think that I arrived at the solution trivially.

I would like to know if there's a better way to the solution and also how I can prove or disprove that $42$ is the minimum possible value. Also, providing links to similar questions with different sums and numbers will also do me a great help in learning.

Answer 1

The correct answer is actually $24$, which is achieved with a list comprised of $17$ copies of $24$, two copies of $2$, and one $1$.

The largest of the numbers is at least $\frac{413}{20}=20.65$, so it's at least $21$. So, the LCM of the numbers must be at least $21$.

If it is $21$, and there are $n$ copies of $21$, the total sum $S$ satisfies $$413=S\geq 21n+7(20-n)=14n+140,$$ which solves to $n\geq 19.5$. This means that $n\geq 20$, which can't occur.

If it is $22$, since $11$ doesn't divide $413$, there must be a $1$ or a $2$. If there are $n$ copies of $22$, we have $$413=S\geq 22n+11(19-n)+2=11n+211,$$ which gives $n\geq 18.36\dots$ -- however, $19$ copies of $22$ sum to $418>413$, so this can't happen.

If it is $23$, and there are $n$ copies of $23$, all others are ones, which gives $$413=S=23n+(20-n)=20+22n,$$ which does not give an integer $n$.

So, the optimum is $24$.

Answer 2

The least LCM of twenty numbers summing to $413$ is $24$.

• The LCM cannot be odd. If it were, all twenty numbers would be odd and their sum would be even.

• The LCM cannot be smaller than $\frac{413}{20} = 20.65$. By the definition of divisibility, every element of a set is less than or equal to the LCM of the set. If the LCM were smaller than $20.65$, then the sum of the elements of the set would be smaller than $413$, a contradiction.

• The LCM cannot be $22$. A set with nineteen $22$s sums to more than $413$. A set with seventeen or fewer $22$s sums to less than $413$. Only two sets have exactly eighteen $22$s, LCMs of $22$, and one odd element: $$S_1 = \{\underbrace{22, 22, \dots, 22}_{18\text{ times}}, 2, 11\}$$ $$S_2 = \{\underbrace{22, 22, \dots, 22}_{18\text{ times}}, 2, 1\}$$ but the sum of the elements of $S_1$ is $409$ and the sum of the elements of $S_2$ is $399$.

The LCM can be $24$ and therefore $24$ is the least possible LCM. There are several different sets of numbers that work, made possible by the plentiful factors of $24$:

$$\{\underbrace{24, 24, \dots, 24}_{16\text{ times}}, 12, 8, 6, 3\}$$ $$\{\underbrace{24, 24, \dots, 24}_{16\text{ times}}, 12, 8, 8, 1\}$$ $$\{\underbrace{24, 24, \dots, 24}_{16\text{ times}}, 12, 12, 3, 2\}$$ $$\{\underbrace{24, 24, \dots, 24}_{16\text{ times}}, 12, 12, 4, 1\}$$ $$\{\underbrace{24, 24, \dots, 24}_{17\text{ times}}, 2,2,1\}$$ $$\{\underbrace{24, 24, \dots, 24}_{17\text{ times}}, 3,1,1\}$$

---

Edit: Now, your (common and underaddressed) meta question, "How?"

Ask meaningful questions.

Your problem solving technique is personal, it's up to you, and different approaches work better or worse in different contexts. Polya suggests four principles for all problem solving scenarios -

• Understand the problem
• Make a plan
• Do it
• Review / revise

When I'm initially dumbstruck, I try to ask meaningful questions to myself. I wondered why your answer focused on odd and even numbers. I wondered what was special about $42$ and $413$? Is it important that they're both divisible by $7$? What prevents a smaller multiple of $7$ from working? If $28$ does work, why can't an even smaller number work? What numbers definitely can't work? From the answers to my subquestions, I gained traction in understanding the main question.

What is definitely true is that to solve problems, you must ask meaningful (and possibly humbling) questions, and then survive the feedback loop to ask again.