An integer $n$ will be called good if we can write \[n=a_1+a_2+\cdots+a_k,\] where $a_1,a_2, \ldots, a_k$ are positive integers (not necessarily distinct) satisfying \[\frac{1}{a_1}+\frac{1}{a_2}+\cdots+\frac{1}{a_n}=1.\] Given the information that the integers 33 through 73 are good, prove that every integer $\ge 33$ is good.
Problem
Source:
Tags: AMC, USAMO, induction, algebra, equation, Additive Number Theory
GlassBead
16.08.2011 22:24
Let $a_1, a_2, ..., a_m$ be integers that add up to some number $ n \in [33, 73]$. Consider $2n+8 = 2a_1+2a_2+\cdots+2a_m+4+4$. The sum of these reciprocals is still one (as $\frac{1}{2a_1}+\frac{1}{2a_2}+ \cdots \frac{1}{2a_m}=\frac{1}{2}$).
Similarly, we can achieve $2n+9$ by using $3, 6$ instead of $4, 4$.
So let each number in the range $[33, 73]$ under the two transformations $n \mapsto 2n+8, n \mapsto 2n+9$ gives the new range $[74, 155]$. By induction, it is easily shown that any range of the form $[n, 2n+7]$ maps to $[2n+8, 4n+23]$, so each of these ranges do not miss any of the integers greater than $73$, and we are done.
quangminhltv99
28.08.2016 12:05
Classic induction problem
We prove that if $n$ is good, then $2n+8$ and $2n+9$ are good either. Let consider a good $n$, the it satisfies \[ \begin{cases} n=a_1+a_2+\cdots+a_k\\ \frac{1}{a_1}+\frac{1}{a_2}+\cdots+\frac{1}{a_k}=1. \end{cases} \]Now, let consider $2n+8$. We have $2n+8=2(a_1+a_2+...+a_k)+4+4$ and \[ \frac{1}{2a_1}+\frac{1}{2a_2}+\cdots+\frac{1}{2a_k}+\frac{1}{4}+\frac{1}{4}=\frac{1}{2}+\frac{1}{2}=1. \]For $2n+9$, we can rewite it as $2n+9=2(a_1+a_2+\cdots+a_k)+3+6$ and we can easily prove it is also good. Now, let $n=33$, then every number in the range $[n,2n+7]$ is good. By induction, we can show that under the transformation $n\to 2n+8$ and $n\to 2n+9$, we will miss no number greater than $73$. QED.
DottedCaculator
03.09.2022 04:08
We see that the only bad numbers are $2$, $3$, $5$, $6$, $7$, $8$, $12$, $13$, $14$, $15$, $19$, $21$, and $23$. All of these are less than $33$.
huashiliao2020
15.04.2023 06:52
Base case is given. We can take n to 2n+8 by 2a_1+...+2a_k+4+4, since by inductive hypothesis the sum of reciprocals is equal to 1/2+1/4+1/4=1. Similarly, take n to 2n+9 by 2a_1+...+2a_k+3+6. Now, [33, 73] is the range [n, 2n+7], which gives the next interval [2n+8, 2(2n+7)+9]=[2n+8, 2(2n+8)+7]. So we have shown that this occurs for the next interval, covering n to 2n+7 to 2n+8 to 4n+23, etc.
peelybonehead
22.07.2023 06:44
We first prove that for a good integer $n,$ $2n+8$ and $2n+9$ are also good. $$2n+8 = 2(a_1 + a_2 + \cdot + a_k) + 4 + 4 \implies \frac{1}{2a_1}+\frac{1}{2a_2}+\cdots+\frac{1}{2a_n} + \frac14 + \frac14=1.$$$$2n+9 = 2(a_1 + a_2 + \cdot + a_k) + 3 + 6 \implies \frac{1}{2a_1}+\frac{1}{2a_2}+\cdots+\frac{1}{2a_n} + \frac13 + \frac16=1.$$We now proceed by strong induciton. It is given to us that integers $33$ throught $73$ are good. For the inductive hypothesis, assume that the integers $n, n+1, n+2, \cdot , 2n+7$ are good. Since $2n+8$ and $2n+9$ are good, for any $n,$ $n+1$ is also good. So we are done. $\blacksquare$
Saucepan_man02
06.11.2024 11:27
Notice that, if $n$ is a good number then: $$ \sum \tfrac{1}{a_i} = n \implies \left( \sum \tfrac{1}{2a_i} \right) + \tfrac{1}{2} = 1, \left( \sum \tfrac{1}{2a_i} \right) + \tfrac{1}{3} + \tfrac{1}{6} = 1$$Therefore: $2n+2, 2n+9$ are also good numbers. Now, this works in reverse also. If $n$ is good, then $\tfrac{n-1}{2}$ or $\tfrac{n-9}{2}$ is good (depends on parity of $n$). Thus, if $33, 34, \cdots, 73, \cdots, n-1$ are good for some $n$, then this implies $n$ is also good (strong induction) and we are done.