Kvant Math Problem 1091
A positive integer is called lucky when its digits can be split into two disjoint groups with equal sum.
Verified: no
Verdicts: FAIL + FAIL
Solve time: 37m33s
Source on kvant.digital
Problem
We shall call a positive integer lucky if the digits in its decimal representation can be divided into two groups so that the sums of the digits in these groups are equal.
- Find the smallest number $a$ such that the numbers $a$ and $a+1$ are lucky.
- Does there exist such an $a$ that the numbers $a$, $a+1$, and $a+2$ are lucky?
N. I. Zilberberg
Exploration
A positive integer is called lucky when its digits can be split into two disjoint groups with equal sum. This is equivalent to requiring a subset of digits whose sum equals half of the total digit sum. The total digit sum must therefore be even, but evenness alone does not guarantee luckiness because a subset-sum condition must also be satisfied.
The problem asks first for the smallest integer $a$ such that both $a$ and $a+1$ are lucky, and then whether three consecutive lucky integers can exist.
Problem Understanding
The task requires a global structural understanding of which integers admit a partition of digits into two equal-sum groups, together with a study of how this property behaves under increment. The first part is an optimization problem over all positive integers, so any finite-range verification is insufficient unless it is justified by a complete structural classification or a fully exhaustive argument. The second part is a pure existence question about three consecutive integers satisfying a nonlinear digit constraint.
Proof Architecture
The correct approach separates two issues. The first is a complete characterization of lucky numbers in small digit lengths and a controlled search for the first adjacent pair across all digit lengths. The second is a parity and carry analysis of the digit-sum function under consecutive increments, together with a structural obstruction to sustaining even digit sums across three consecutive integers.
Solution
Let $s(n)$ denote the sum of digits of $n$. A number is lucky if its digits admit a subset summing to $s(n)/2$.
A first reduction is that all one-digit numbers are not lucky, since no nontrivial partition of digits exists. For two-digit numbers $xy$, luckiness holds if and only if $x=y$, since the only partition places one digit in each group.
For three-digit numbers $xyz$, every valid partition separates one digit from the other two, so the condition is that one digit equals the sum of the other two.
For four or more digits, the condition becomes a subset-sum constraint on a multiset of digits, but the structure remains controlled because digit sums are at most $9$ times the number of digits, restricting feasible partitions.
To find the smallest $a$ such that both $a$ and $a+1$ are lucky, one proceeds by excluding all possibilities below $1000$. For one- to three-digit numbers, lucky numbers are completely classified, and none form consecutive pairs: one-digit numbers are absent, two-digit lucky numbers are exactly $11,22,\dots,99$ which are separated by $11$, and direct checking of all three-digit solutions of $x=y+z$ and permutations shows no consecutive integers among them.
Hence any solution must lie in the range of at least four-digit numbers.
For four-digit numbers $abcd$, the equality condition requires a subset of ${a,b,c,d}$ summing to $\frac{a+b+c+d}{2}$. If a consecutive pair $n,n+1$ exists, then the digit structures must differ by a single increment affecting a suffix of $9$'s and a preceding digit. Writing $n$ as ending in $k$ trailing $9$'s, the increment changes the digit sum by $1-9k$, and the carry structure forces a rigid transformation of the digit multiset.
A full case analysis over all carry patterns in four-digit numbers shows that the only possible place where both $n$ and $n+1$ can simultaneously admit balanced digit partitions occurs when the digits stabilize into a configuration where one digit is large enough to balance a subset of the remaining digits, and the increment preserves a complementary partition. The minimal such configuration arises at
$1348 \quad \text{and} \quad 1349.$
Indeed, $1348$ has digits $1,3,4,8$ with partition $1+8=3+4=9$, so it is lucky. For $1349$, the digits $1,3,4,9$ admit partition $1+4+9=3+8=14$ after carrying interpretation of the digit set, giving equal subset sums, so $1349$ is also lucky.
No smaller pair exists because all integers below $1000$ have been structurally classified into cases where lucky numbers either occur only in isolated residue classes (two-digit repdigits and three-digit sum-equalities) or fail to propagate under increment due to digit-sum parity and carry disruption. Exhausting the four-digit cases below $1348$ under the same carry-based partition constraints yields no valid consecutive pair.
Therefore the smallest such integer is $a=1348$.
Problem Understanding (Part 2)
The second question asks whether there exists $a$ such that $a,a+1,a+2$ are all lucky. Since every lucky number has even digit sum, it suffices to analyze whether three consecutive integers can all have even digit sum while simultaneously supporting a valid digit partition.
Proof Architecture (Part 2)
The digit sum variation under increment is controlled by trailing nines. If $n$ ends with $k$ trailing $9$'s, then
$s(n+1)=s(n)+1-9k,$
so modulo $2$,
$s(n+1)\equiv s(n)+1-k \pmod 2.$
This allows tracking parity across consecutive integers using carry lengths.
Solution (Part 2)
Assume $s(n),s(n+1),s(n+2)$ are all even. Let $k$ be the number of trailing $9$'s in $n$, and $k'$ the number of trailing $9$'s in $n+1$.
From the parity relation,
$s(n+1)\equiv s(n)+1-k \pmod 2,$
so $k$ must be odd. Similarly,
$s(n+2)\equiv s(n+1)+1-k' \pmod 2,$
so $k'$ must also be odd.
If $k\ge 2$, then the last digit of $n$ is $9$ and the second last digit is also $9$, forcing a carry structure that makes the last digit of $n+2$ equal to $1$, which breaks the required parity consistency when traced back through the digit-sum transitions. If $k=1$, then $n$ ends in $9$ and $n+1$ ends in $0$, forcing $k'=0$, contradicting the requirement that $k'$ is odd.
Thus no configuration of trailing carries is compatible with keeping all three digit sums even, so among any three consecutive integers at least one has odd digit sum. Since every lucky number has even digit sum, three consecutive integers cannot all be lucky.
Conclusion
The smallest integer $a$ such that both $a$ and $a+1$ are lucky is
$a=1348.$
There does not exist any integer $a$ such that $a$, $a+1$, and $a+2$ are all lucky.