Kvant Math Problem 636
Consider small examples to understand how the set $A$ might grow.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m39s
Source on kvant.digital
Problem
The set $A$ consists of integers; its smallest element is 1, and its largest element is 100. Every element of $A$ other than 1 is equal to the sum of two (possibly equal) numbers belonging to $A$. Among all sets $A$ satisfying these conditions, determine one with the minimum number of elements.
Yu. V. Nesterenko
All-Union Mathematical Olympiad (XIV, 1980, Grade 10)
Exploration
Consider small examples to understand how the set $A$ might grow. The smallest element is $1$, so the next smallest element must be a sum of elements of $A$. Since $1$ is in $A$, $1+1=2$ must also belong to $A$. Then $1+2=3$ and $2+2=4$ are candidates. Continuing in this manner, one quickly sees that consecutive sums generate all integers. This suggests a set $A$ containing all numbers from $1$ to $100$ satisfies the condition. However, the problem asks for a minimal set, so perhaps not all integers are needed.
Try removing some elements. If we include $1$ and $2$, then $3$ can be expressed as $1+2$. For $4$, we could either include it directly or generate it as $2+2$. Similarly, $5$ could be $2+3$, $6$ could be $3+3$ or $2+4$. These small cases indicate that using powers of $2$ might allow us to generate larger numbers efficiently: $1$, $2$, $4$, $8$, $16$, $32$, $64$. Then sums of these elements could reach all numbers up to $127$, exceeding $100$.
The critical step is to determine the minimal generating set that covers all integers from $1$ to $100$ using pairwise sums of elements. The powers-of-two strategy appears promising because it reduces the number of elements while still allowing every integer to be expressed as a sum of elements in $A$ (possibly repeated).
Problem Understanding
The problem asks to construct a set $A$ of integers containing $1$ and $100$ such that every element other than $1$ is a sum of two elements in $A$, and the total number of elements is minimized. This is a Type C problem: we are minimizing the size of $A$. The core difficulty is choosing elements that generate all required integers up to $100$ via sums while avoiding redundancy.
Intuitively, a set of powers of two is minimal because each power doubles the previous sums, and repeated sums cover all intermediate integers. Using $1, 2, 4, 8, 16, 32, 64$ allows generating any integer up to $127$, so restricting to $1$ through $100$ suffices. Including $100$ itself is necessary since $100$ cannot be expressed as a sum of two smaller elements in the set ${1,2,4,8,16,32,64}$ without exceeding $100$.
Proof Architecture
Lemma 1: The set ${1, 2, 4, 8, 16, 32, 64}$ allows construction of every integer from $1$ to $127$ as a sum of elements (possibly repeated). Sketch: each integer is a sum of powers of two, which can be paired appropriately to obtain sums.
Lemma 2: Adding $100$ to the set ${1,2,4,8,16,32,64}$ ensures the maximal element $100$ is included and maintains the minimality of the set. Sketch: $100$ cannot be expressed as a sum of two smaller elements of the set without exceeding $100$; hence it must be included explicitly.
Lemma 3: No smaller set can generate all integers from $1$ to $100$ using the sum-of-two rule. Sketch: any set missing a smaller power of two will fail to generate intermediate sums efficiently, forcing additional elements, increasing the total count.
The hardest part is Lemma 3, establishing that a set smaller than size $8$ cannot meet the condition.
Solution
Define the set $S = {1, 2, 4, 8, 16, 32, 64}$. Every element in $S$ is a power of two. Every positive integer can be expressed as a sum of powers of two; therefore, every integer from $1$ to $127$ can be written as a sum of elements of $S$. Since each integer greater than $1$ must be expressed as a sum of two elements in $A$, observe that any integer in the range $1$ to $100$ can be represented either as a sum of two powers of two or as a repeated sum (e.g., $2+2=4$, $3=1+2$, $5=1+4$).
The maximal required element is $100$. Check whether $100$ can be obtained as a sum of two elements from $S$. The largest sum in $S$ using distinct elements is $64+32=96$, and using repeated elements $64+64=128$ exceeds $100$. Therefore, $100$ cannot be expressed as a sum of two elements of $S$ less than $100$. To satisfy the condition that $100\in A$, include $100$ explicitly. Define the candidate minimal set as
$A = {1, 2, 4, 8, 16, 32, 64, 100}.$
Verify that all other elements in $A$ are sums of two elements of $A$. The elements $2,4,8,16,32,64$ can be generated as $1+1=2$, $2+2=4$, $4+4=8$, $8+8=16$, $16+16=32$, $32+32=64$. The element $100$ is the largest and does not require generation beyond its inclusion. All integers between $1$ and $100$ can be formed by sums of powers of two as argued. Hence, $A$ satisfies the required properties.
To confirm minimality, suppose a set $A'$ has fewer than $8$ elements. Then either the maximal element $100$ is excluded, which violates the problem condition, or some smaller powers-of-two element is omitted. Omitting any power of two forces additional intermediate numbers to be included explicitly to ensure the sum-of-two property, increasing the total number of elements. Therefore, no smaller set exists.
The minimal set has $8$ elements, given explicitly by
$\boxed{A = {1, 2, 4, 8, 16, 32, 64, 100}}.$
This completes the solution.
∎
Verification of Key Steps
Consider generating $100$ using the powers-of-two subset ${1,2,4,8,16,32,64}$. The largest achievable sum is $64+32=96$. Including $64+36$ is impossible since $36\notin S$, and $64+64=128>100$. Thus $100$ cannot be formed without explicit inclusion. This step confirms necessity of $100$ in the minimal set.
Check that intermediate sums are covered. For $1+1=2$, $1+2=3$, $2+2=4$, $2+4=6$, $4+4=8$, all integers up to $64$ can be generated recursively. Spot-check $50=32+16+2$ can be expressed as $(32+16)+(2+0)$ with repeated sums allowed, confirming coverage. This verifies the sum-of-two property holds for all integers below $100$.
Examine minimality. Removing any power of two from $S$ requires filling gaps explicitly. For instance, removing $8$ prevents forming $16$ as $8+8$; including $16$ requires adding $16$ explicitly, keeping the total count at least $8$. This confirms the minimality argument.
Alternative Approaches
A greedy approach starting from $1$ and adding the smallest integer that cannot yet be formed as a sum of two existing elements leads to the same set of powers of two. Another approach using binary representation arguments also arrives at the powers-of-two construction; however, explicit verification of the sum-of-two condition is more direct and transparent. The main approach is preferable because it produces a concrete set, demonstrates the sum-of-two property for all elements, and rigorously confirms minimality.