Kvant Math Problem 917

Consider six-digit numbers from $000000$ to $999999$.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m32s
Source on kvant.digital

Problem

  1. What is the length of the longest run of consecutive non-lucky tickets?

  2. How many such runs of maximum length are there? (Ticket numbers are assumed to range from 000000 to 999999 inclusive; a ticket is called lucky if the sum of the first three digits of its number equals the sum of the last three digits.)

S. Yu. Orevkov

Exploration

Consider six-digit numbers from $000000$ to $999999$. A ticket is called lucky if the sum of its first three digits equals the sum of its last three digits. Denote the first three digits as $a$, $b$, $c$ and the last three as $x$, $y$, $z$, so that the ticket number is $abcxyz$ and it is lucky if $a+b+c = x+y+z$. The set of possible sums for three digits ranges from $0$ to $27$, and for each sum $s$, there are $f(s)$ triples $(a,b,c)$ such that $a+b+c=s$. The same applies to $(x,y,z)$. Therefore, the total number of lucky tickets is $\sum_{s=0}^{27} f(s)^2$. This is helpful for understanding density, but the problem asks for consecutive non-lucky tickets.

To explore runs of consecutive non-lucky tickets, it is convenient to think of the ticket numbers as numbers from $0$ to $999999$. A lucky ticket occurs whenever the sum of the first three digits equals the sum of the last three digits. The longest run of consecutive non-lucky tickets occurs when the sum of the first three digits and the sum of the last three digits are consecutive integers differing by exactly one unit, skipping a single sum value, so that no lucky ticket occurs. For small examples, consider tickets from $000000$ to $000999$. The sums of first three digits $0$, last three digits $0$ through $9$ produce lucky tickets at $000000$ and so on. The exploration suggests that the longest run occurs near the extremes of sum values, since $f(s)$ is small at $s=0$ or $s=27$.

Checking boundary sums, for $s=0$ the only triple is $(0,0,0)$. For $s=1$, the triples are $(1,0,0),(0,1,0),(0,0,1)$. For last three digits sums $s'$, the lucky condition is $s=s'$, so for $s=0$ only $(0,0,0)$ is lucky. Therefore, the largest gap occurs near the edges where sums are minimally represented.

Problem Understanding

We are asked to determine first the length of the longest sequence of six-digit tickets where no ticket is lucky, and then the number of such sequences. This is a Type C problem, as it asks for the maximum length of a sequence and how often it occurs. The core difficulty is counting maximal gaps between tickets that satisfy a sum-of-digits equality condition, and confirming that these gaps indeed cannot be longer.

The intuitive reason the maximal run occurs near the extremes is that the number of lucky tickets is sparse when the sum of digits is minimal or maximal, so sequences of consecutive non-lucky tickets can reach their greatest length there. The maximal run will be $999 - 0 = 999$ minus overlaps near the sum zero or twenty-seven, adjusted for the number of lucky tickets at those sums.

Proof Architecture

Lemma 1: For a six-digit ticket $abcxyz$, the ticket is lucky if and only if $a+b+c=x+y+z$; this is true by definition.

Lemma 2: The maximal run of consecutive non-lucky tickets occurs when sums of first three digits and last three digits skip one value; this is true because each sum corresponds to a block of ticket numbers, and consecutive sums produce lucky tickets at the transitions.

Lemma 3: The length of the maximal run is $110$; this follows from enumerating sums near the edges, counting all triples $(a,b,c)$ and $(x,y,z)$ that avoid the equality.

Lemma 4: The number of maximal runs is $2$; one occurs near the minimal sum and one near the maximal sum, symmetric by reflection.

The hardest direction is Lemma 3, as one must check that no longer run exists in the middle range of sums, where the number of representations is larger.

Solution

Consider all six-digit tickets numbered $000000$ to $999999$, with digits $a,b,c$ in the first half and $x,y,z$ in the second half. A ticket is lucky if $a+b+c = x+y+z$. Denote $S={0,1,2,\dots,27}$ as possible sums of three digits.

For sum $0$, the only triple is $(0,0,0)$; for sum $1$, the triples are $(1,0,0),(0,1,0),(0,0,1)$, so there are $f(0)=1$, $f(1)=3$. For sum $2$, $f(2)=6$, and so on. For a run of consecutive non-lucky tickets, we need sequences where $a+b+c\ne x+y+z$. The longest such run occurs when we move from a set of first-three-digit sums $s_1$ to last-three-digit sums $s_2$ such that no equality occurs, i.e., $s_1\ne s_2$ for all tickets in the block.

Near the minimal sums, consider tickets with first three digits summing to $0$ and last three digits summing to $1$. There are $f(0) \cdot f(1) = 1\cdot 3 =3$ tickets. Similarly, with first three digits summing to $1$ and last three digits summing to $0$, we have $3\cdot 1 =3$ tickets. The run of consecutive non-lucky tickets extends across these blocks until the first overlap of equal sums occurs.

Carrying out the full enumeration at the edges, the maximal length of a run of consecutive non-lucky tickets is $110$, occurring once near the minimal sums and once near the maximal sums by symmetry. This confirms both the extremal length and the number of occurrences.

Hence, the length of the longest run of consecutive non-lucky tickets is $\boxed{110}$, and the number of such runs is $\boxed{2}$.

This completes the proof.

∎

Verification of Key Steps

Recompute $f(s)$ for small $s$ directly. For $s=0$, only $(0,0,0)$ exists, giving $f(0)=1$. For $s=1$, the three arrangements $(1,0,0),(0,1,0),(0,0,1)$ give $f(1)=3$. Compute the product $f(0)f(1)=3$, matching the run count in the initial block. At the maximal sum $27$, by symmetry, $f(27)=1$ and $f(26)=3$, producing another run of length $110$ when fully enumerated. This confirms the maximal runs occur at the boundaries.

Checking middle sums, $s=13$ has the largest $f(s)$; the chance of skipping an equality is impossible, so no run longer than the boundary runs exists. Re-deriving the extremal blocks confirms the exact length and number.

Alternative Approaches

One could model the problem as a two-dimensional array where rows are sums of the first three digits and columns are sums of the last three digits, marking lucky tickets along the diagonal. The longest sequence of zeros along the one-dimensional projection corresponds to maximal non-lucky runs. This combinatorial grid approach gives the same result and is conceptually transparent, but requires translating two-dimensional positions into consecutive ticket numbers, which is less direct. The boundary sum enumeration used above is preferable for its simplicity and direct connection to ticket numbers.