Not 24

Suppose $P(D) \leq 3$. Then each digit contributes at most $\left\lfloor \frac{c_d}{2}\right\rfloor$ pairs, so $$c_d \leq 2 \left\lfloor \frac{c_d}{2}\right\rfloor + 1$$ for each $d$. Summing over $d = 1, \dots, 9$, $$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.$$ 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 $$\frac{a}{a} = \frac bb = \frac cc = \frac dd = 1,$$ 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, $$k \leq 2 P(D)+9.$$ 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 $$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}\}.$$ 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 $$S_2 \supseteq \{0,\ 1,\ 14,\ 49,\ 98,\ 196,\ 2401,\ 1/7,\ 1/49\}.$$

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): $$E = U(A \circ B) \quad \text{with } A,B \text{ 2-leaf subexpressions},$$ or $$E = U(7 \circ T) \ \text{or}\ U(T \circ 7) \quad \text{with } T \text{ a 3-leaf subexpression},$$ 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 $$\{10,\ -10,\ 100\}.$$ ($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 $$\{a\circ b : a,b \in S_2,\ \circ \in \{+,-,\times,\cdot/\cdot\}\}.$$ 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{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}$$ (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: $$T \in cl(\{x \circ 7,\ 7 \circ x : x \in S_2,\ \circ \in \{+,-,\times,\cdot/\cdot\}\}).$$ 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 $$c_d = 2\left\lfloor \frac{c_d}{2}\right\rfloor + r_d, \quad r_d \in \{0,1\}.$$ Summing over $d=1,\dots,9$, $$16 = \sum_{d=1}^9 c_d = 2P(D) + \sum_{d=1}^9 r_d = 8 + \sum_{d=1}^9 r_d,$$ 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 $$c_d = 2\left\lfloor \frac{c_d}{2}\right\rfloor + r_d,\quad r_d\in\{0,1\}.$$ 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 $$\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}.$$ 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 $$T = \left(\frac{a}{a}+\frac{b}{b}+\frac{c}{c}\right)^2+\frac{d}{d} = 10.$$ Let $R$ be any expression using every remaining unused digit exactly once (e.g. their product in any parenthesization). Then $$T + Z\cdot R = 10$$ uses every digit exactly once and evaluates to 10.

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

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 $$U(D) \ge 3 + 1 = 4.$$

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 $\left| S \right| \le 3 + 4 = 6$. Contrapositively, $\left| S \right| \ge 7$ implies $\nu(P_9[S]) \ge 2$.

Applying this with $\left| S \right| = R(D) \ge 8$, we obtain $A(D) \ge 2$, and therefore $$U(D) \ge P(D) + A(D) \ge 2 + 2 = 4.$$

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 $$Z \doteq e - e = 0.$$

Remove these two digits; the remaining multiset $D'$ has size $$\left| D' \right| = k - 2 \ge 12.$$

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 $$T \doteq (1+1+1)^2 + 1 = 10.$$

Let $R$ be any expression using all remaining unused digits exactly once (for instance, their product in any parenthesization). Then $$T + Z \cdot R = 10$$ 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 $$D = \{x^{c_x}, y^{c_y}\}, \qquad c_x + c_y = 9.$$ Then the number of disjoint equal pairs is $$P(D) = \left\lfloor \frac{c_x}{2} \right\rfloor + \left\lfloor \frac{c_y}{2} \right\rfloor.$$ 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: $$\frac aa = \frac bb = \frac cc = \frac dd = 1.$$ Then $$(1+1+1)^2 + 1 = 10$$ 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: $$3 \notin D \quad \text{and} \quad 9 \notin D.$$

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: $$1-4-7, \qquad 2-5-8, \qquad 3-6-9.$$ 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: $$\{1\},\ \{2\},\ \{4\},\ \{5\},\ \{6\},\ \{7\},\ \{8\},$$
• two-value supports: $$\{1,2\},\ \{1,5\},\ \{1,6\},\ \{1,7\},\ \{2,4\},\ \{2,6\},\ \{4,8\},\ \{5,6\},\ \{5,7\},\ \{6,7\},\ \{6,8\},\ \{7,8\},$$
• multi-value supports: $$\{1,2,6\},\ \{1,5,6\},\ \{1,5,7\},\ \{1,6,7\},\ \{5,6,7\},\ \{6,7,8\},\ \{1,5,6,7\}.$$

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 $$10 = (1+1+1)^2 + 1.$$
• Else if $b \ge 4$, use $$10 = 2\cdot2\cdot2+2.$$
• Else if $b \ge 2$ and $c \ge 1$, use $$10 = 6+2^2.$$
• Else if $b=1$ and $a \ge 2$, use $$10 = (2+1)^2+1.$$
• Else if $a \ge 1$ and $c \ge 4$, use $$10 = 1+\left(\frac{6+6+6}{6}\right)^2.$$
• Otherwise $c \ge 6$, so use $$10 = \left(\frac{6+6}{6}\right)^2+6.$$

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 $$10 = 1 + 3^2.$$

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 $$10 = \left(\frac{7+7+7}{7}\right)^2 + 1.$$

Support $\{1,6,7\}$

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

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 $$10 = 6 + (7-5)^2.$$

Support $\{6,7,8\}$

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

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 $$10 = 6 + (7-5)^2.$$

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 $$Z \doteq e - e = 0.$$ Remove these two digits; the remaining multiset $D'$ has size $\left| D' \right| = 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 $$T + Z \cdot R = 10$$ 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 $$1-2-\cdots-9.$$ But the unique independent 5-set in this path is $$\{1,3,5,7,9\}.$$ 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$.