6
$\begingroup$

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.

$\endgroup$
11
  • 1
    $\begingroup$ $28\cdot 13 + 7\cdot 7 = 413$ and $lcm(28,7) = 28$ $\endgroup$
    – David Diaz
    Aug 9, 2021 at 4:05
  • $\begingroup$ @DavidDiaz so was that supposed to be the answer? $\endgroup$
    – Spectre
    Aug 9, 2021 at 4:06
  • $\begingroup$ And so basically, I need to find a linear combination for the sum and take the LCM of the coefficients? $\endgroup$
    – Spectre
    Aug 9, 2021 at 4:07
  • 3
    $\begingroup$ $24\cdot 16 + 12\cdot 2 + 3 + 2 = 413$ and $lcm(24,12,3,2) = 24$. This seems to be the minimal answer as the lcm cannot be less than $413/20$ and $21,22,$ and $23$ don't appear to work. $\endgroup$
    – David Diaz
    Aug 9, 2021 at 4:31
  • 1
    $\begingroup$ Or @DavidDiaz is it that the least bound for the possible LCM's of $n$ natural numbers whose sum is $S$ is $\lfloor\frac{S}{n}\rfloor$? I am asking so because I have never heard of such a result. $\endgroup$
    – Spectre
    Aug 9, 2021 at 4:36

2 Answers 2

4
$\begingroup$

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$.

$\endgroup$
6
  • 3
    $\begingroup$ The $x_{i}$s consists of $x_{max}$ and its factors or else $LCM\left(x_{1},…,x_{20}\right)\geq 2x_{max}\geq 42$. No wonder they put $42$ as the example, it was a hint! $\endgroup$ Aug 9, 2021 at 5:04
  • $\begingroup$ @CalSchildkraut I think it was a typo then. The fact that I arrived at the answer with the typo was what had baffled me .. also, I am not getting why the least bound for such a problem (sum $S$, $n$ numbers) is $\lfloor\frac{S}{n}\rfloor$, so would you mind adding how I can arrive at that result? Anyway, Vielen danke! $\endgroup$
    – Spectre
    Aug 9, 2021 at 5:10
  • 2
    $\begingroup$ @Spectre the LCM of several numbers cannot be smaller than any of the numbers including the maximum and the maximum cannot be smaller than the average. $\endgroup$ Aug 9, 2021 at 5:15
  • $\begingroup$ @RezhaAdrianTanuharja oh yeah, seems like I had forgotten that the LCM of two numbers is always greater than or equal to either of the numbers (or both of them) . Thanks for reminding me! $\endgroup$
    – Spectre
    Aug 9, 2021 at 5:18
  • 2
    $\begingroup$ @Spectre Bitte! In fact, you can achieve a lower bound of $\lceil S/n\rceil$ using the same logic. $\endgroup$ Aug 9, 2021 at 5:20
3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ thanks, but I am not so acquainted with roundness (I read it just now and understood it, so thanks). Also, I am not looking for exhaustive search, but yes, nice answer and thanks again. $\endgroup$
    – Spectre
    Aug 9, 2021 at 8:20
  • $\begingroup$ @CarlSchildkraut's sort of algebra and number theory combo type answer is something that works out well for me, as exhaustive search can consume my time during the test. $\endgroup$
    – Spectre
    Aug 9, 2021 at 8:21
  • $\begingroup$ Oh my God, I had forgotten to read the whole answer by Carl... and I mistook yours for the only one with exhaustive search.. so I'd like to say a sorry. Yeah, thanks for your answer too. $\endgroup$
    – Spectre
    Aug 9, 2021 at 8:26
  • 2
    $\begingroup$ (+1) for your 'ask meaningful questions' part. Really liked this part. $\endgroup$
    – Oshawott
    Aug 12, 2021 at 17:40
  • $\begingroup$ @DavidDiaz yeah, I must have been too subtle. Sorry for the trouble and thanks for contributing the extra part in your question. It will be of great help to me as well as to many others. $\endgroup$
    – Spectre
    Aug 13, 2021 at 1:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.