Not 24

Suppose \(P(D) \leq 3\). Then each digit contributes at most \(\left\lfloor \frac{c_d}{2}\right\rfloor\) pairs, so \begin{equation} c_d \leq 2 \left\lfloor \frac{c_d}{2}\right\rfloor + 1 \end{equation} for each \(d\). Summing over \(d = 1, \dots, 9\), \begin{equation} k = \sum_{i=1}^9 c_d \leq \sum_{i=1}^9 \left(2\left\lfloor \frac{c_d}{2}\right\rfloor + 1 \right) = 2P(D) + 9 \leq 2\cdot 3 + 9 = 15. \end{equation} Thus, if \(k \geq 16\), it is impossible to have \(P(D) \leq 3\); hence \(P(D) \geq 4\).

By the above lemma, for \(k \geq 16\) we may choose four disjoint pairs \((a,a), (b,b), (c,c), (d,d)\) (not necessarily unique digits) and form \begin{equation} \frac{a}{a} = \frac bb = \frac cc = \frac dd = 1, \end{equation} thus we can reach 10. To guarantee we can use all remaining digits without affecting the value 10, it suffices to have an additional equal pair \((e,e)\) disjoint from the 8 digits already used, because then we can form \(e-e=0\) and multiply the entire leftover expression by 0.

So we want \(P(D) \geq 5\). From the same inequality as used in the lemma, \begin{equation} k \leq 2 P(D)+9. \end{equation} Plugging in our desired \(P(D)-1\) (same logic as lemma), we have that \(k \leq 2 \cdot 4 + 9 = 17\), so to ensure \(P(D) \geq 5\), we require \(k \geq 18\), as claimed.

Intuition. The only way to use exactly 4 leaves is via a full binary tree with 4 leaves. There are only 2 root shapes: \((2,2)\) and \((1,3)\). The delicate point is that unary operations \(\sqrt{\cdot}\) and \((\cdot)^2\) may be applied at internal nodes without consuming digits, so we must account for them completely. We reduce the problem to a finite target-exclusion check.

Unary closure

Define the unary-closure operator on a set \(S\) by \begin{equation} cl(S) \doteq S \cup \{x^2 : x \in S\} \cup \{\sqrt{x} : x \in S \text{ and } x \text{ is a perfect square integer}\}. \end{equation} Since unary operations act only on the value already produced at a node, the set of values attainable by any fixed subtree is closed under \(cl(\cdot)\).

Classify all 2-leaf values from \(\{7,7\}\)

Let \(S_2\) denote the set of all values obtainable from exactly two leaves \(\{7,7\}\) using operations in \(M\). We claim \begin{equation} S_2 \supseteq \{0,\ 1,\ 14,\ 49,\ 98,\ 196,\ 2401,\ 1/7,\ 1/49\}. \end{equation}

Justification:

• Using only the binary operations on raw leaves gives \(7-7=0\), \(7/7=1\), \(7+7=14\), \(7\times 7=49\).
• Applying \((\cdot)^2\) to \(14\) and \(49\) yields \(196\) and \(2401\). Applying \(\sqrt{\cdot}\) to \(196\) and \(2401\) returns \(14\) and \(49\); no other square roots are defined from two 7s.
• By allowing a unary operation on a single leaf before the binary root, we may use \(49\) as a leaf value and form \(7/49 = 1/7\). Squaring yields \((1/7)^2 = 1/49\).

(We will only need the displayed subset of small values in the later finite checks.)

Reduce the 4-leaf problem to two root shapes

Every full 4-leaf binary tree has root of type \((2,2)\) or \((1,3)\). Concretely, any 4-leaf expression is of one of the following forms (up to swapping left/right): \begin{equation} E = U(A \circ B) \quad \text{with } A,B \text{ 2-leaf subexpressions}, \end{equation} or \begin{equation} E = U(7 \circ T) \ \text{or}\ U(T \circ 7) \quad \text{with } T \text{ a 3-leaf subexpression}, \end{equation} where \(\circ \in \{+,-,\times,\cdot/\cdot\}\) and \(U(\cdot)\) denotes an (optional) finite composition of unary operations applied at the root (each application must be defined).

Unary operations at the root force a finite set of binary targets

The only unary operations are \(x \mapsto x^2\) and \(x \mapsto \sqrt{x}\) (when defined). Since \(10\) is neither a perfect square nor the square root of a perfect square integer other than 100, the only way a root unary chain can produce 10 is if the binary root value lies in \begin{equation} \{10,\ -10,\ 100\}. \end{equation} (\(x^2=10\) has no rational solution; \(\sqrt{x}=10\) forces \(x=100\); and \(\sqrt{x^2}\) can introduce an absolute value, hence \(-10\).)

Thus, to show impossibility, it suffices to show that in either root shape, the binary root can never evaluate to any of \(10,-10,100\).

Exclude root shape \((2,2)\)

In this shape, \(A,B \in S_2\). Therefore the binary root lies in the finite set \begin{equation} \{a\circ b : a,b \in S_2,\ \circ \in \{+,-,\times,\cdot/\cdot\}\}. \end{equation} A direct check shows this set does not contain \(10\), \(-10\), or \(100\). Hence the \((2,2)\) shape cannot yield 10.

Exclude root shape \((1,3)\)

In this shape, the binary root is \(7 \circ T\) or \(T \circ 7\). To have the binary root in \(\{10,-10,100\}\), \(T\) must satisfy one of finitely many equations, giving the forced target set \begin{equation} \begin{aligned} \mathcal{T} \doteq \{&3,\ -3,\ 17,\ -17,\ 93,\ -93,\ 107,\ 10/7,\ -10/7,\ 100/7,\\ &-100/7,\ 7/10,\ -7/10,\ 7/100,\ -7/100,\ 70,\ -70,\ 700,\ -700\}. \end{aligned} \end{equation} (These come from solving \(7 \circ T = y\) and \(T \circ 7 = y\) for \(y \in \{10,-10,100\}\) and \(\circ \in \{+,-,\times,\cdot/\cdot\}\).)

Now, any 3-leaf expression necessarily contains a 2-leaf subtree; evaluating that subtree first yields some \(x \in S_2\), and then \(T\) is obtained by combining \(x\) with the remaining leaf \(7\) using one binary operation, followed by unary closure: \begin{equation} T \in cl(\{x \circ 7,\ 7 \circ x : x \in S_2,\ \circ \in \{+,-,\times,\cdot/\cdot\}\}). \end{equation} Therefore, it suffices to check the finite set on the right-hand side and verify it is disjoint from \(\mathcal{T}\). This direct check succeeds: no element of \(\mathcal{T}\) appears.

Hence the \((1,3)\) shape cannot yield a binary root in \(\{10,-10,100\}\), and therefore cannot yield 10 after any root-level unary operations.

Neither root shape \((2,2)\) nor \((1,3)\) can yield a binary root value in \(\{10,-10,100\}\), hence no valid expression using exactly four 7s can evaluate to 10. This proves the claim.

Write \begin{equation} c_d = 2\left\lfloor \frac{c_d}{2}\right\rfloor + r_d, \quad r_d \in \{0,1\}. \end{equation} Summing over \(d=1,\dots,9\), \begin{equation} 16 = \sum_{d=1}^9 c_d = 2P(D) + \sum_{d=1}^9 r_d = 8 + \sum_{d=1}^9 r_d, \end{equation} so \(\sum_{d=1}^9 r_d = 8\). Since \(r_d=1\) implies \(c_d\) is odd (hence \(\geq 1\)), this means that at least 8 distinct digits appear in \(D\), i.e. at most one digit is missing from \(\{1,\dots,9\}\).

Now consider the set \(\{2,3,4,9\}\). If 2 is missing then 3,4,9 are present, so in particular \(\{3,9\} \subset D\). If digit 3 is missing then \(\{2,4\} \subset D\). Similarly, if 4 is missing then \(\{3,9\} \subset D\), and if 9 is missing then \(\{2,4\} \subset D\). If none are missing, then both \(\{2,4\}\) and \(\{3,9\}\) are present. Thus at least one of \(\{2,4\}\) or \(\{3,9\}\) occurs, and we can form \(4-2^2=0\) or \(9-3^2=0\) using each digit exactly once.

Since \(P(D)=4\) and \(k=16\), write \begin{equation} c_d = 2\left\lfloor \frac{c_d}{2}\right\rfloor + r_d,\quad r_d\in\{0,1\}. \end{equation} As in Lemma 5, summing gives \(\sum_{d=1}^9 r_d = 8\). Hence exactly one digit has even multiplicity; call it \(e\). (All other digits have odd multiplicity, hence at least 1.)

Now note the following fact: if \(c_d\) is odd, then reserving a single copy of \(d\) does not decrease the number of available pairs contributed by \(d\), since \begin{equation} \left\lfloor \frac{c_d-1}{2}\right\rfloor = \left\lfloor \frac{c_d}{2}\right\rfloor \quad \text{when } c_d \text{ is odd}. \end{equation} The only way reserving digits can decrease \(P(D)\) is if we reserve a copy of the unique even-multiplicity digit \(e\).

By Lemma 5, at least one of the gadgets is available; choose \(Z \in \{4-2^2, 9-3^2\}\) so that reserving its digits leaves four disjoint equal pairs. Choose the zero gadget \(Z\) so that it does not use the digit \(e\):

• If \(e \in \{2,4\}\), choose \(Z = 9-3^2\).
• If \(e \in \{3,9\}\), choose \(Z = 4-2^2\).
• If \(e \notin \{2,3,4,9\}\), choose whichever of the two gadgets is available.

Because at most one digit is missing from \(\{1,\dots,9\}\), in the first two bullets the "other" gadget is guaranteed to be available: if (say) \(e=2\) then digit 2 is present (even multiplicity) and so the only possible missing digit is not both 3 and 9, hence \(\{3,9\}\subset D\); similarly for the other cases.

With this choice, the digits reserved for \(Z\) come only from odd-multiplicity digits, so reserving them does not reduce \(P(D)\). Therefore there remain at least four disjoint equal pairs available to build \(T=10\).

Fix \(k \geq 16\). If \(P(D) \geq 5\), then we revert to the \(k \leq 18\) proof: use 4 pairs to build \(T=10\) and use the 5th pair to build \(e-e=0\), absorbing all remaining digits.

So assume \(k=16\) and \(P(D)=4\). By Lemma 6, we can form a duplicate-free zero gadget \(Z \in \{4-2^2,\ 9-3^2\}\) with \(Z=0\) (choose whichever is available in \(D\)).

Independently, since \(P(D)=4\), we can select 4 disjoint equal pairs and construct \begin{equation} T = \left(\frac{a}{a}+\frac{b}{b}+\frac{c}{c}\right)^2+\frac{d}{d} = 10. \end{equation} Let \(R\) be any expression using every remaining unused digit exactly once (e.g. their product in any parenthesization). Then \begin{equation} T + Z\cdot R = 10 \end{equation} uses every digit exactly once and evaluates to 10.

Since \begin{equation} 12 = \sum_{i=1}^9 c_i = 2P(D) + R(D), \end{equation} we have \begin{equation} R(D) = 12 - 2P(D). \end{equation}

We argue by cases.

Case 1: \(P(D) \ge 4\). Then \(U(D) \ge P(D) \ge 4\).

Case 2: \(P(D) = 3\). Then \(R(D) = 6\). So six vertices of the path carry an odd token.

But the path on nine vertices has independence number \(5\); hence any subset of six vertices must contain at least one adjacent pair. Therefore \(A(D) \ge 1\), and \begin{equation} U(D) \ge 3 + 1 = 4. \end{equation}

Case 3: \(P(D) \le 2\). Then \(R(D) \ge 8\).

Now we claim any induced subgraph of the 9-vertex path on at least 7 vertices has matching number at least 2.

Indeed, if a subset \(S\) of vertices satisfies \(\nu(P_9[S]) \le 1\), then the induced subgraph consists of isolated vertices together with at most one component containing an edge. In a path, such a component has size at most 3. The remaining vertices must be isolated and therefore pairwise nonadjacent; there can be at most 4 of these. Hence \(\abs{S} \le 3 + 4 = 6\). Contrapositively, \(\abs{S} \ge 7\) implies \(\nu(P_9[S]) \ge 2\).

Applying this with \(\abs{S} = R(D) \ge 8\), we obtain \(A(D) \ge 2\), and therefore \begin{equation} U(D) \ge P(D) + A(D) \ge 2 + 2 = 4. \end{equation}

All cases give \(U(D) \ge 4\).

Let \(k \ge 14\). Since there are only 9 digit types, some digit \(e\) appears at least twice. Reserve two copies and form \begin{equation} Z \doteq e - e = 0. \end{equation}

Remove these two digits; the remaining multiset \(D'\) has size \begin{equation} \abs{D'} = k - 2 \ge 12. \end{equation}

By Lemma 8, we have \(U(D') \ge 4\). Hence we may extract 4 disjoint unit pairs from \(D'\) and convert them into 4 1s.

Using these four 1s, construct \begin{equation} T \doteq (1+1+1)^2 + 1 = 10. \end{equation}

Let \(R\) be any expression using all remaining unused digits exactly once (for instance, their product in any parenthesization). Then \begin{equation} T + Z \cdot R = 10 \end{equation} uses every digit exactly once and evaluates to \(10\).

If some digit repeats, we have an equal pair \((i,i)\) and hence \(1=i/i\). Otherwise all digits are distinct. But the independence number of the 9-vertex path is \(5\), so any set of \(6\) distinct vertices contains an adjacent pair \((i,i+1)\). Then \(1=(i-(i+1))^2\).

If \(D\) is supported on at most two values, write \begin{equation} D = \{x^{c_x}, y^{c_y}\}, \qquad c_x + c_y = 9. \end{equation} Then the number of disjoint equal pairs is \begin{equation} P(D) = \left\lfloor \frac{c_x}{2} \right\rfloor + \left\lfloor \frac{c_y}{2} \right\rfloor. \end{equation} For any integers \(c_x,c_y \ge 0\) with \(c_x+c_y=9\), we have \(P(D) \ge 4\); the minimum occurs at \(1+8\) or \(2+7\), giving \(0+4=4\) or \(1+3=4\).

Thus we can always select four disjoint equal pairs and form four \(1\)s: \begin{equation} \frac aa = \frac bb = \frac cc = \frac dd = 1. \end{equation} Then \begin{equation} (1+1+1)^2 + 1 = 10 \end{equation} gives a \(10\)-kernel.

We proceed by successive reductions. Throughout, we shall ignore unused digits.

Immediate 2-leaf kernels. If \(D\) contains any of \((1,9),(2,8),(3,7),(4,6)\) or contains two \(5\)s, then we can form \(10\) by addition and are done. Hence assume:

• no complement-to-10 pair occurs in \(D\), and
• \(c_5 \le 1\).

Singleton nine gadgets. If \(9 \in D\), we have \(9\). If \(3 \in D\), we have \(9=3^2\). In either case, removing that one digit leaves 8 digits. By Lemma 10, the remaining digits contain a disjoint unit pair producing \(1\). Hence \(10=9+1\). So assume: \begin{equation} 3 \notin D \quad \text{and} \quad 9 \notin D. \end{equation}

2-leaf nine gadgets. If \(D\) contains any sum-to-9 pair among \((1,8),(2,7),(4,5)\), then \(9=x+y\) uses two digits, leaving 7 digits; by Lemma 10, these yield a disjoint \(1\), hence \(10=9+1\). Similarly, if \(D\) contains a distance-3 pair \((i,i+3)\), then \(9=(i-(i+3))^2\) and again the remaining 7 digits yield a disjoint \(1\). Hence we may assume:

• none of \((1,8),(2,7),(4,5)\) occurs in \(D\), and
• no distance-3 pair \((i,i+3)\) occurs in \(D\).

mod-3 chain collapse. The distance-3 edges partition the digits into chains: \begin{equation} 1-4-7, \qquad 2-5-8, \qquad 3-6-9. \end{equation} The absence of any distance-3 pair implies that the support of \(D\) restricts on each chain to an independent set of that 3-vertex path. Thus:

• on \(1-4-7\), the allowed occupied subsets are \(\emptyset, \{1\}, \{4\}, \{7\}, \{1,7\}\),
• on \(2-5-8\), the allowed occupied subsets are \(\emptyset, \{2\}, \{5\}, \{8\}, \{2,8\}\),
• on \(3-6-9\), since \(3,9 \notin D\), the only possibilities are \(\emptyset\) and \(\{6\}\).

Now use the earlier exclusions:

• \(\{2,8\}\) is forbidden because it is a complement-to-10 pair,
• \(\{1,8\}\) and \(\{7,2\}\) are forbidden because they are complement-to-10 pairs,
• \(\{4,5\}\) is forbidden because it is a sum-to-9 pair.

Therefore the support of \(D\) must be one of the following:

• one-value supports: \begin{equation} \{1\},\ \{2\},\ \{4\},\ \{5\},\ \{6\},\ \{7\},\ \{8\}, \end{equation}
• two-value supports: \begin{equation} \{1,2\},\ \{1,5\},\ \{1,6\},\ \{1,7\},\ \{2,4\},\ \{2,6\},\ \{4,8\},\ \{5,6\},\ \{5,7\},\ \{6,7\},\ \{6,8\},\ \{7,8\}, \end{equation}
• multi-value supports: \begin{equation} \{1,2,6\},\ \{1,5,6\},\ \{1,5,7\},\ \{1,6,7\},\ \{5,6,7\},\ \{6,7,8\},\ \{1,5,6,7\}. \end{equation}

If \(D\) is supported on at most two values, then Lemma 11 applies and we are done. So it remains only to handle the seven explicit multi-value supports.

Support \(\{1,2,6\}\) Let \((a,b,c)\) denote multiplicities of \((1,2,6)\), so \(a+b+c=9\).

• If \(a \ge 4\), use \begin{equation} 10 = (1+1+1)^2 + 1. \end{equation}
• Else if \(b \ge 4\), use \begin{equation} 10 = 2\cdot2\cdot2+2. \end{equation}
• Else if \(b \ge 2\) and \(c \ge 1\), use \begin{equation} 10 = 6+2^2. \end{equation}
• Else if \(b=1\) and \(a \ge 2\), use \begin{equation} 10 = (2+1)^2+1. \end{equation}
• Else if \(a \ge 1\) and \(c \ge 4\), use \begin{equation} 10 = 1+\left(\frac{6+6+6}{6}\right)^2. \end{equation}
• Otherwise \(c \ge 6\), so use \begin{equation} 10 = \left(\frac{6+6}{6}\right)^2+6. \end{equation}

Support \(\{1,5,6\}\)

• If \(c_5 \ge 2\), then \(10=5+5\).
• Otherwise \(c_5=1\), so \(c_1+c_6=8\).
• If \(c_1 \ge 4\), use \(10=(1+1+1)^2+1\).
• If \(c_1 \le 3\), then \(c_6 \ge 5\); form \(3=(6+6+6)/6\) and then \begin{equation} 10 = 1 + 3^2. \end{equation}

Support \(\{1,5,7\}\)

• If \(c_5 \ge 2\), then \(10=5+5\).
• Otherwise \(c_5=1\), so \(c_1+c_7=8\).
• If \(c_1 \ge 4\), use \(10=(1+1+1)^2+1\).
• If \(c_1 \le 3\), then \(c_7 \ge 5\); use \begin{equation} 10 = \left(\frac{7+7+7}{7}\right)^2 + 1. \end{equation}

Support \(\{1,6,7\}\)

• If \(c_1 \ge 4\), use \(10=(1+1+1)^2+1\).
• If \(c_6 \ge 3\), use \begin{equation} 10 = 7 + \frac{6+6+6}{6}. \end{equation}
• Otherwise \(c_6 \le 2\), so \(c_7 \ge 4\); use \begin{equation} 10 = \left(\frac{7+7+7}{7}\right)^2 + 1. \end{equation}

Support \(\{5,6,7\}\)

• If \(c_5 \ge 2\), then \(10=5+5\).
• Otherwise \(c_5=1\), and since the support is exactly \(\{5,6,7\}\) we may use \begin{equation} 10 = 6 + (7-5)^2. \end{equation}

Support \(\{6,7,8\}\)

• If \(c_7 \ge 2\), use \begin{equation} 10 = 8 + \frac{7+7}{7}. \end{equation}
• Otherwise \(c_7=1\).
• If \(c_6 \ge 3\), use \begin{equation} 10 = 7 + \frac{6+6+6}{6}. \end{equation}
• If \(c_6 \le 2\), then \(c_8 \ge 6\); use \begin{equation} 10 = \left(\frac{8+8+8}{8}\right)^2 + \frac 88. \end{equation}

Support \(\{1,5,6,7\}\)

• If \(c_5 \ge 2\), then \(10=5+5\).
• Otherwise \(c_5=1\), and since 6 and 7 are present we may use \begin{equation} 10 = 6 + (7-5)^2. \end{equation}

Thus in all cases, \(D\) admits a \(10\)-kernel.

Let \(k \ge 11\) and \(D \subset [9]^k\). By pigeonhole, some digit \(e\) appears at least twice. Reserve two copies and form \begin{equation} Z \doteq e - e = 0. \end{equation} Remove these two digits; the remaining multiset \(D'\) has size \(\abs{D'} = k-2 \ge 9\). By Lemma 12, \(D'\) contains a \(10\)-kernel \(T\).

Let \(R\) be any expression using all remaining unused digits of \(D\) exactly once (for example, their product in any parenthesization). Then \begin{equation} T + Z \cdot R = 10 \end{equation} uses every digit exactly once and evaluates to \(10\).

If some digit repeats, we have an equal pair \((i,i)\) and therefore a unit pair.

So assume all five digits are distinct. If two are adjacent, we are done. Hence assume no two are adjacent. Then the support is an independent 5-set in the path \begin{equation} 1-2-\cdots-9. \end{equation} But the unique independent 5-set in this path is \begin{equation} \{1,3,5,7,9\}. \end{equation} Since \(3,9 \notin E\), this is impossible. Therefore \(E\) must contain a unit pair.

Let \((c_2,c_4)\) be multiplicities with \(c_2+c_4=7\).

• If \(c_2\ge 4\), use \(K_2\).
• Else \(c_2\le 3\), so \(c_4\ge 4\).
• If \(c_2=0\), then \(c_4=7\); use \(K_4\).
• If \(c_2\ge 1\), then \(c_4\ge 2\); use \(4+4+2=10\).

Let \((c_4,c_8)\) be multiplicities with \(c_4+c_8=7\).

• If \(c_8\ge 2\) and \(c_4\ge 1\), use \(8+\frac84=10\).
• Else if \(c_8\le 1\), then \(c_4\ge 6\); use \(K_4\).
• Else \(c_8\ge 2\) and \(c_4=0\), hence \(c_8=7\); use \(K_8\).

Let \((a,b,c)\) be multiplicities of \((1,2,6)\) with \(a+b+c=7\).

• If \(a\ge 4\), use \(K_1\).
• Else if \(b\ge 4\), use \(K_2\).
• Else if \(b\ge 2\) and \(c\ge 1\), use \(6+2^2=10\).
• Else if \(b=1\) and \(a\ge 2\), use \((2+1)^2+1=10\).
• Else if \(a\ge 1\) and \(c\ge 4\), use \(1+\left(\frac{6+6+6}{6}\right)^2=10\).
• Otherwise \(c\ge 6\), so use \(K_6\).

Let \((c_6,c_7,c_8)\) be multiplicities with \(c_6+c_7+c_8=7\).

If \(c_8\ge 1\):

• If \(c_8\ge 4\), use \(K_8\).
• Else if \(c_7\ge 3\), use \(8+\frac{7+7}{7}=10\).
• Else \(c_7\le 2\), so \(c_6\ge 2\); use \((8-6)^2+6=10\).

If \(c_8=0\), then \(c_6+c_7=7\):

• If \(c_7\ge 6\), use \(K_7\).
• Else if \(c_7\ge 3\), then \(c_6\ge 2\); use \(6+6-\frac{7+7}{7}=10\).
• Else if \(c_7\ge 1\), then \(c_6\ge 4\); use \(7+\frac{6+6+6}{6}=10\).
• Else \(c_6=7\); use \(K_6\).

Let \((a,b,c,d)\) be multiplicities of \((1,5,6,7)\) with \begin{equation} a+b+c+d=7. \end{equation}

If \(b\ge 2\), use \(5+5=10\). So assume \(b\le 1\).

Case 1: \(b=1\).

• If \(d\ge 5\), use \(K_7\).
• Else if \(a\ge 1\) and \(c\ge 1\), use \(6+(5-1)=10\).
• Else if \(c\ge 1\) and \(d\ge 1\), use \(6+(7-5)^2=10\).
• Else if \(a\ge 2\) and \(d\ge 1\), use \(7+5-(1+1)=10\).
• The only remaining possibilities are pure supports \(\{1,5\}\) or \(\{5,6\}\), so use \(K_1\) or \(K_6\).

Case 2: \(b=0\). Then \(a+c+d=7\).

• If \(a\ge 4\), use \(K_1\).
• Else if \(d\ge 6\), use \(K_7\).
• Else if \(a\ge 3\) and \(d\ge 1\), use \(7+1+1+1=10\).
• Else if \(a\ge 1\) and \(c\ge 4\), use \(1+\left(\frac{6+6+6}{6}\right)^2=10\).
• Else if \(a\ge 1\) and \(d\ge 4\), use \(1+\left(\frac{7+7+7}{7}\right)^2=10\).
• Else if \(c\ge 4\) and \(d\ge 1\), use \(7+\frac{6+6+6}{6}=10\).
• Else if \(c\ge 2\) and \(d\ge 3\), use \(6+6-\frac{7+7}{7}=10\).
• Else if \(a\ge 2\), \(c\ge 1\), and \(d\ge 2\), use \(7+(7-6)^2+(1+1)=10\).
• Otherwise \(c=7\), so use \(K_6\).

As in the \(k \le 11\) section, we use the identity \(10=9+1\) and seek a disjoint nine-gadget and unit pair.

First remove immediate 2-leaf kernels:

• no complement-to-10 pair in \((1,9),(2,8),(3,7),(4,6)\) occurs,
• and \(c_5 \le 1\) (so no \(5+5=10\) kernel).

If \(3 \in D\) or \(9 \in D\), we get a 1-leaf nine-gadget. Removing that one digit leaves 6 digits, and Lemma 10 yields a disjoint unit pair. So in the reduced case: \begin{equation} 3 \notin D \quad \text{and} \quad 9 \notin D. \end{equation}

Now consider 2-leaf nine-gadgets. If \(D\) contains any of \begin{equation} (1,8),(2,7),(4,5),(1,4),(4,7),(2,5),(5,8), \end{equation} then removing that gadget leaves 5 digits. By \(3,9 \notin D\) and Lemma 14, those 5 digits contain a disjoint unit pair. Hence \(10=9+1\).

Therefore, in the hard case we may assume all those pairs are absent. Equivalently, the support is an independent set in the forbidden graph \(H\) on vertices \begin{equation} \{1,2,4,5,6,7,8\} \end{equation} with forbidden edges \begin{equation} 14,47,25,58,18,27,45,28,46. \end{equation} The maximal independent sets of \(H\) are: \begin{equation} \{2,4\},\ \{4,8\},\ \{1,2,6\},\ \{6,7,8\},\ \{1,5,6,7\}. \end{equation} Define \begin{equation} M_1=\{2,4\},\quad M_2=\{4,8\},\quad M_3=\{1,2,6\},\quad M_4=\{6,7,8\},\quad M_5=\{1,5,6,7\}. \end{equation} Every reduced support \(S\) is an independent set of \(H\), hence \(S\subseteq M_i\) for some \(i\in\{1,\dots,5\}\). Therefore it is enough to prove, for each \(i\), the stronger family statement: \begin{equation} (\star_i):\quad \text{every 7-digit multiset } D \text{ with } \operatorname{supp}(D)\subseteq M_i \text{ contains a 10-kernel.} \end{equation} These are exactly lemmas Lemma 16 through Lemma 20. Hence the hard case is solved, and every 7-digit multiset admits a \(10\)-kernel.

Let \(k \ge 9\) and \(D \subset [9]^k\).

If some digit repeats, reserve two copies \((e,e)\) and set \begin{equation} Z \doteq e-e=0. \end{equation} Removing those two digits leaves \(k-2 \ge 7\) digits; pick any 7 of them and apply Lemma 15 to obtain a \(10\)-kernel \(T\). Let \(R\) be any expression using all remaining unused digits exactly once. Then \begin{equation} T + Z\cdot R = 10 \end{equation} uses every digit exactly once.

If no digit repeats and \(\abs{D}=9\), then necessarily \begin{equation} D=\{1,2,3,4,5,6,7,8,9\}, \end{equation} and we have an explicit full-use expression: \begin{equation} 1+2+3+4+5\bigl(9-8-(7-6)^2\bigr)=10. \end{equation}

Hence every 9-digit multiset is solvable, so \(k \le 9\).

We split by support size.

Case 1: one-value support

For \(T=\{d,d,d\}\), the following witnesses work: \begin{equation} \begin{aligned} \{1,1,1\}&:\ (1+1)^2+1=5,\\ \{2,2,2\}&:\ 2^2+\frac22=5,\\ \{3,3,3\}&:\ 3^2-\frac33=8,\\ \{4,4,4\}&:\ 4+\frac44=5,\\ \{5,5,5\}&:\ 5\cdot\frac55=5,\\ \{6,6,6\}&:\ 6-\frac66=5,\\ \{7,7,7\}&:\ 7+\frac77=8,\\ \{8,8,8\}&:\ 8\cdot\frac88=8,\\ \{9,9,9\}&:\ 9-\frac99=8. \end{aligned} \end{equation}

Case 2: two-value support

Write \(T=\{x,x,y\}\) with \(x\ne y\). Since \(\frac xx=1\), we can form \(y-1\), \(y\), and \(y+1\). Hence if \(y\in\{4,5,6,7,8,9\}\), one of these is \(5\) or \(8\).

So only \(y\in\{1,2,3\}\) remains. Exhaustive witnesses: \begin{equation} \begin{aligned} \{1,1,1\}&:\ (1+1)^2+1=5, & \{2,2,1\}&:\ 2+2+1=5, & \{3,3,1\}&:\ 3^2-1=8,\\ \{4,4,1\}&:\ 1+\sqrt{4\cdot4}=5, & \{5,5,1\}&:\ \sqrt{\frac{5\cdot5}{1}}=5, & \{6,6,1\}&:\ \sqrt{6\cdot6}-1=5,\\ \{7,7,1\}&:\ 1+\sqrt{7\cdot7}=8, & \{8,8,1\}&:\ 1+\sqrt{8+8}=5, & \{9,9,1\}&:\ 9-\sqrt9-1=5,\\ \{1,1,2\}&:\ 1+\left(\frac21\right)^2=5, & \{2,2,2\}&:\ 2^2+\frac22=5, & \{3,3,2\}&:\ 2+\sqrt{3\cdot3}=5,\\ \{4,4,2\}&:\ 2^2+\frac44=5, & \{5,5,2\}&:\ \frac{5+5}{2}=5, & \{6,6,2\}&:\ 2^2+\frac66=5,\\ \{7,7,2\}&:\ \sqrt{7\cdot7}-2=5, & \{8,8,2\}&:\ 2^2+\frac88=5, & \{9,9,2\}&:\ 2^2+\frac99=5,\\ \{1,1,3\}&:\ 1+1+3=5, & \{2,2,3\}&:\ 3^2-2-2=5, & \{3,3,3\}&:\ 3^2-\frac33=8,\\ \{4,4,3\}&:\ 4+4-3=5, & \{5,5,3\}&:\ 3+\sqrt{5\cdot5}=8, & \{6,6,3\}&:\ 3^2-\frac66=8,\\ \{7,7,3\}&:\ 7+7-3^2=5, & \{8,8,3\}&:\ \sqrt{8\cdot8}-3=5, & \{9,9,3\}&:\ 3^2-\frac99=8. \end{aligned} \end{equation}

Case 3: three-value support with a consecutive pair

Let \(a\lt b\lt c\) be distinct. If \(b=a+1\), then \(b-a=1\), so we can make \(c-1,c,c+1\); if \(c=b+1\), then \(c-b=1\), so we can make \(a-1,a,a+1\). Thus only finitely many edge cases remain; witnesses: \begin{equation} \begin{aligned} \{1,2,3\}&:\ \frac{2+3}{1}=5, & \{1,3,4\}&:\ \frac{3+\sqrt4}{1}=5, & \{1,4,5\}&:\ \sqrt{(1+4)\cdot5}=5,\\ \{1,5,6\}&:\ \sqrt{(6-1)\cdot5}=5, & \{1,6,7\}&:\ \frac{6^2-1}{7}=5, & \{1,7,8\}&:\ \sqrt{(1+7)\cdot8}=8,\\ \{1,8,9\}&:\ \frac{8-\sqrt9}{1}=5, & \{2,4,5\}&:\ 2+\sqrt{4+5}=5, & \{2,5,6\}&:\ 2^2-(5-6)=5,\\ \{2,6,7\}&:\ 2^2-(6-7)=5, & \{2,7,8\}&:\ 2^2-(7-8)=5, & \{2,8,9\}&:\ 2^2-(8-9)=5,\\ \{3,5,6\}&:\ 5+6-3=8, & \{3,6,7\}&:\ \sqrt{3\cdot6+7}=5, & \{3,7,8\}&:\ \frac{7+8}{3}=5,\\ \{3,8,9\}&:\ 8-\frac93=5. \end{aligned} \end{equation}

Case 4: three-value support with no consecutive pair

The sparse triples (\(35\) total) are exhausted by the following witnesses: \begin{equation} \begin{aligned} \{1,3,5\}&:\ 1+(5-3)^2=5, & \{1,3,6\}&:\ 1+\left(\frac63\right)^2=5, & \{1,3,7\}&:\ 1-(3-7)=5,\\ \{1,3,8\}&:\ \frac{8-3}{1}=5, & \{1,3,9\}&:\ 9-3-1=5, & \{1,4,6\}&:\ \sqrt{1+4\cdot6}=5,\\ \{1,4,7\}&:\ \frac{7-\sqrt4}{1}=5, & \{1,4,8\}&:\ 1-(4-8)=5, & \{1,4,9\}&:\ \frac{9-4}{1}=5,\\ \{1,5,7\}&:\ 1+(5-7)^2=5, & \{1,5,8\}&:\ (5-8)^2-1=8, & \{1,5,9\}&:\ 1-(5-9)=5,\\ \{1,6,8\}&:\ 1+(6-8)^2=5, & \{1,6,9\}&:\ 1+\left(\frac6{\sqrt9}\right)^2=5, & \{1,7,9\}&:\ 1+\sqrt{7+9}=5,\\ \{2,4,6\}&:\ \frac{4+6}{2}=5, & \{2,4,7\}&:\ 2-(4-7)=5, & \{2,4,8\}&:\ \frac{\sqrt4+8}{2}=5,\\ \{2,4,9\}&:\ 4+\sqrt9-2=5, & \{2,5,7\}&:\ \sqrt{(7-2)\cdot5}=5, & \{2,5,8\}&:\ 2-(5-8)=5,\\ \{2,5,9\}&:\ \sqrt{(2+\sqrt9)\cdot5}=5, & \{2,6,8\}&:\ \frac{\sqrt{6^2+8^2}}{2}=5, & \{2,6,9\}&:\ 2-(6-9)=5,\\ \{2,7,9\}&:\ \frac{7+\sqrt9}{2}=5, & \{3,5,7\}&:\ 3-(5-7)=5, & \{3,5,8\}&:\ \sqrt{(8-3)\cdot5}=5,\\ \{3,5,9\}&:\ 3+\sqrt{9-5}=5, & \{3,6,8\}&:\ 3-(6-8)=5, & \{3,6,9\}&:\ \frac{6+9}{3}=5,\\ \{3,7,9\}&:\ 3-(7-9)=5, & \{4,6,8\}&:\ \sqrt{\frac{6^2+8^2}{4}}=5, & \{4,6,9\}&:\ (6-9)^2-4=5,\\ \{4,7,9\}&:\ \sqrt{4+7\sqrt9}=5, & \{5,7,9\}&:\ 7+\sqrt9-5=5. \end{aligned} \end{equation}

All 3-digit multisets are covered, proving the lemma.

Witnesses: \begin{equation} \begin{aligned} 11&:\ 1+1,\quad 22:\ \sqrt{2+2},\quad 44:\ \frac4{\sqrt4},\quad 88:\ \sqrt{\sqrt{8+8}},\\ 12&:\ 1\cdot2,\quad 13:\ 3-1,\quad 14:\ \sqrt4,\quad 15:\ \sqrt{5-1},\quad 19:\ \sqrt9-1,\\ 24&:\ 4/2,\quad 26:\ 6-2^2,\quad 28:\ 8/2^2,\quad 35:\ 5-3,\quad 36:\ 6/3,\quad 37:\ 3^2-7,\\ 46&:\ 6-4,\quad 48:\ 8/4,\quad 57:\ 7-5,\quad 59:\ 5-\sqrt9,\quad 68:\ 8-6,\quad 69:\ 6/\sqrt9,\quad 79:\ 9-7. \end{aligned} \end{equation}

Let \(D\in[9]^5\). If \(D\) contains a \(G_2\)-pair, use that pair to build \(2\). The complementary triple builds \(5\) or \(8\) by Lemma 22, so we get \begin{equation} 2\cdot 5=10 \quad \text{or} \quad 2+8=10. \end{equation} Therefore any counterexample must contain no \(G_2\)-pair at all.

So we only need to solve 5-multisets independent in \(G_2\). The maximal independent supports are: \begin{equation} \{2,5\},\ \{2,7\},\ \{4,5\},\ \{4,7\},\ \{5,6\},\ \{5,8\}, \end{equation} \begin{equation} \{1,6,7\},\ \{1,7,8\},\ \{2,3,9\},\ \{3,4,9\},\ \{3,8,9\}. \end{equation} These are obtained by exhaustive verification over all supports in \(\{1,\dots,9\}\). Because \(1,2,4,8\) have loops, each can appear at most once inside these candidates.

It remains to list one witness per admissible 5-multiset family:

Family \(\{2,5\}\)

Family \(\{2,7\}\)

Family \(\{4,5\}\)

Family \(\{4,7\}\)

Family \(\{5,6\}\)

Family \(\{5,8\}\)

Family \(\{1,6,7\}\)

Family \(\{1,7,8\}\)

Family \(\{2,3,9\}\)

Family \(\{3,4,9\}\)

Family \(\{3,8,9\}\)

Thus every \(G_2\)-independent 5-multiset is solvable, and every non-independent one is solvable by the pair-plus-triple reduction above. Hence every 5-digit multiset is solvable. Together with Claim 3, this gives \(k=5\).