Problem J - Game of Nines — Solution¶

1. Story-style intuition¶

Picture your digits \(0\)–\(8\) as tokens on a 10-hour clock (positions \(0\) through \(9\)). When you “add digit \(a\) to digit \(b\)”, you move token \(b\) forward by \(a\) ticks around the clock. If you land exactly on \(9\), that token disappears.

Two important facts drive everything:

Helpers don’t get used up.

A digit you use as an adder stays on the table. You can reuse it indefinitely.
Only the total step size matters.

Adders are reusable and order doesn’t matter, so what matters is the set of step sizes you can produce in total modulo \(10\).

We call this set of reusable digits the helper set \(H\).

2. What is \(d\)?¶

Given a helper set \(H\), the achievable total steps (mod \(10\)) are exactly the multiples of:

\[d := \gcd\bigl(10,\; \text{all digits in } H\bigr).\]

This is because the sums of helpers form a subgroup of \(\mathbb{Z}_{10}\), and every subgroup is \(\{0,d,2d,\ldots,10-d\}\) for some \(d\in\{1,2,5,10\}\).

Interpretation: :math:`d` is your tick size around the circle.

\(d=1\) → can move any number of steps
\(d=2\) → even steps only
\(d=5\) → only multiples of 5
\(d=10\) → no movement possible

A token \(b\) is eliminable iff:

\[b \text{ is eliminable using } H \iff d \mid (9-b).\]

3. Everything reduces to one gcd¶

Take \(H\) to be all digits you have. Define:

\[g = \gcd(10, a_1, a_2, \dots, a_n).\]

If \(g=1\), you can produce every step size → you can eliminate tokens until only one remains.
If \(g\in\{2,5,10\}\), no \(9-b\) is divisible by \(g\), so nothing can be eliminated.

Thus:

\[\begin{split}\text{Answer} = \begin{cases} 1 & \text{if } \gcd(10, a_1,\dots,a_n)=1,\\[4pt] n & \text{otherwise.} \end{cases}\end{split}\]

4. Constructive play when \(g=1\)¶

Case 1: You have a digit in \(\{1,3,7\}\) (coprime with 10). Keep one; repeatedly add it to any other digit until that digit becomes \(9\) and disappears.

Case 2: Otherwise, \(g=1\) implies you have a \(5\) and a nonzero even \(e\in\{2,4,6,8\}\). Keep \(\{e,5\}\) as helpers.

For a target \(b\):

If \(b\) is odd → eliminate using repeated \(e\) moves.
If \(b\) is even → apply \(5\) once to make it odd, then finish with \(e\).

You can also eliminate the \(5\) using \(e\) because \(5 + ke \equiv 9 \pmod{10}\) always has a solution.

5. Short proof¶

Achievable totals form a subgroup of \(\mathbb{Z}_{10}\) → equal to multiples of \(d\).
\(b\) is eliminable ⇔ \(b+t\equiv9\pmod{10}\) for some achievable \(t\) ⇔ \(d\mid(9-b)\).
If \(g=1\), all digits are eliminable; if \(g\in\{2,5,10\}\), none are.
A move consumes two digits but removes at most one, so one token remaining is optimal.

6. Algorithm¶

Read \(n\) and digits \(a_i\).
Compute \(g=\gcd(10,a_1,\ldots,a_n)\).
Output 1 if \(g=1\), else \(n\).

Time: \(\Theta(n)\)
Memory: \(\Theta(1)\)

7. Reference implementations¶

Python¶

import sys
import math

def solve():
    data = sys.stdin.read().strip().split()
    n = int(data[0])
    g = 10
    for i in range(1, n + 1):
        x = int(data[i])
        g = math.gcd(g, x)
    print(1 if g == 1 else n)

if __name__ == "__main__":
    solve()

8. Quick sanity checks¶

\(2 3 6\) ⇒ \(\gcd(10,2,3,6)=1\) ⇒ output 1
\(4 4\) ⇒ \(\gcd(10,4,4)=2\) ⇒ output 2
\(0 5 5\) ⇒ \(\gcd(10,0,5,5)=5\) ⇒ output 3
\(2 5\) ⇒ \(\gcd(10,2,5)=1\) ⇒ output 1