AIME 2026 II · 第 14 题

Solution 1

Let $A$ be the sum of all terms added when evaluating the operation, and $S$ be the sum of all terms subtracted. Every term in the sequence is either added or subtracted, so the total sequence sum is:

$$A + S = 12$$ The final operation result equals the sum of added terms minus the sum of subtracted terms:

$$A - S = 0$$ We have the system:

$$\begin{cases} A + S = 12 \\ A - S = 0 \end{cases}$$ Adding the two equations gives: $2A = 12 \implies A = 6$. We substitute back to get $S = 6$. Thus, the sum of all subtracted terms in the operation must be exactly $6$. Our problem reduces to counting sequences where the total of subtracted terms equals $6$. We know for any integers $x$ and $y$, $x - y \equiv x + y \pmod{2}$. Subtraction does not change the parity of the result. By induction on the number of terms, the parity of the running operation result before term $a_k$ is exactly equal to the parity of the sum of all terms before $a_k$. This gives a simplified subtraction rule, a term $a_k$ is subtracted if and only if:

1. The sum of all terms before $a_k$ is odd;
2. $a_k$ itself is even.

Even terms do not change the parity of the cumulative sum, only odd terms do. This allows us to partition the sequence into "gaps" of even terms between (and before/after) the odd terms, eliminating the need to track running parity for every term. Suppose a sequence has $m$ odd terms, in order: $o_1, o_2, \dots, o_m$. We split the sequence into $m+1$ gaps of even terms: $G_0$: Even terms before the first odd term $o_1$; $G_k$: Even terms between $o_k$ and $o_{k+1}$ for $1 \leq k \leq m-1$; $G_m$: Even terms after the last odd term $o_m$. All even terms in the sequence fall into exactly one of these gaps. For example, in the sequence $[2, 1, 4, 3, 6]$: Odd terms: $1, 3$, so $m=2$, Gaps: $G_0 = [2]$, $G_1 = [4]$, $G_2 = [6]$. The parity of the cumulative sum before gap $G_k$ depends only on the number of odd terms we have already passed: Before $G_0$: $0$ odd terms $\implies$ sum parity is even; Before $G_1$: $1$ odd term $\implies$ sum parity is odd; Before $G_2$: $2$ odd terms $\implies$ sum parity is even; In general: Before $G_k$, sum parity is $k \pmod{2}$. Combined with our subtraction rule, this gives: All even terms in odd-indexed gaps ($G_1, G_3, G_5, \dots$) are subtracted. All even terms in even-indexed gaps ($G_0, G_2, G_4, \dots$) are added. Now our counting goal is to count sequences where the sum of even terms in odd-indexed gaps equals $6$. We split the total sequence sum into three non-negative parts:

1. $O$: Sum of the odd terms in the sequence
2. $E_{\text{add}}$: Sum of even terms in even-indexed gaps (added terms)
3. $E_{\text{sub}}$: Sum of even terms in odd-indexed gaps (subtracted terms, which equals $6$)

From the total sequence sum:

$$O + E_{\text{add}} + E_{\text{sub}} = 12 \implies O + E_{\text{add}} = 6$$ We now find all valid values of $O$:

1. $O$ is the sum of positive odd terms. Recall that the sum of odd numbers is even if and only if there is an even number of terms, since odd + odd = even, and pairs of odd terms preserve evenness.
2. $E_{\text{add}}$ is a sum of even terms, so it is even.
3. $O + E_{\text{add}} = 6$, so $O$ must be even.
4. $O = 0$ is impossible: no odd terms means no odd-indexed gaps, so $E_{\text{sub}} = 0 \neq 6$.
5. $O > 6$ is impossible: $E_{\text{add}}$ cannot be negative.

Thus, the only valid values for $O$ are $\boldsymbol{2, 4, 6}$. We now count valid sequences for each value of $O$, breaking our work into subcases for clarity. We will use two main counting rules for our analysis:

1. Compositions: A composition of a number is an ordered sum of positive integers. For example, $1+5$ and $5+1$ are distinct compositions of $6$, since sequence order matters.
2. Splitting Even Sums Across Gaps: To split an even sum $S = 2K$ across $t$ gaps, we allow empty gaps: Let the sum in gap $i$ be $2k_i$, so $k_1 + k_2 + \dots + k_t = K$, which can be counted using the stars and bars method. For a gap with $k_i = 0$: exactly $1$ way (no terms). For a gap with $k_i \geq 1$: the number of compositions of $2k_i$ into positive even terms is $2^{k_i - 1}$, since we double each part of a composition of $k_i$ to get an even composition.

Case 1: Sum of Odd Terms $O = 6$ Here, $E_{\text{add}} = 6 - 6 = 0$: no even terms in even-indexed gaps. We count:

1. Number of compositions of $6$ into an even number of positive odd terms
2. Number of ways to split the subtracted sum $6$ into the odd-indexed gaps

Subcase 1a: 2 odd terms Compositions of $6$ into 2 odd terms: $1+5, 3+3, 5+1$ $\implies$ $3$ ways Number of odd-indexed gaps: $1$ ($G_1$) Ways to split $6$ into 1 gap: $4$ ways. To see this, note the even compositions of 6 are $[6]$, $[2+4]$, $[4+2]$, and $[2+2+2]$, giving exactly 4 ways.

Total: $3 \times 4 = 12$

Subcase 1b: 4 odd terms Compositions of $6$ into 4 odd terms: $1+1+1+3, 1+1+3+1, 1+3+1+1, 3+1+1+1$ $\implies$ $4$ ways Number of odd-indexed gaps: $2$ ($G_1, G_3$) Ways to split $6$ into 2 gaps: $12$ ways

Total: $4 \times 12 = 48$

Subcase 1c: 6 odd terms Compositions of $6$ into 6 odd terms: $1+1+1+1+1+1$ $\implies$ $1$ way Number of odd-indexed gaps: $3$ ($G_1, G_3, G_5$) Ways to split $6$ into 3 gaps: $25$ ways

Total: $1 \times 25 = 25$

Total for Case $1$: $12 + 48 + 25 = 85$

Case 2: Sum of Odd Terms $O = 4$ Here, $E_{\text{add}} = 6 - 4 = 2$: we split $2$ extra even terms across even-indexed gaps. We count:

1. Number of compositions of $4$ into an even number of positive odd terms
2. Number of ways to split the subtracted sum $6$ into odd-indexed gaps
3. Number of ways to split the added sum $2$ into even-indexed gaps

Subcase 2a: 2 odd terms Compositions of $4$ into 2 odd terms: $1+3, 3+1$ $\implies$ $2$ ways Odd-indexed gaps: $1$ $\implies$ $4$ ways to split $6$ Even-indexed gaps: $2$ ($G_0, G_2$) $\implies$ $2$ ways to split $2$

Total: $2 \times 4 \times 2 = 16$

Subcase 2b: 4 odd terms Compositions of $4$ into 4 odd terms: $1+1+1+1$ $\implies$ $1$ way Odd-indexed gaps: $2$ $\implies$ $12$ ways to split $6$ Even-indexed gaps: $3$ ($G_0, G_2, G_4$) $\implies$ $3$ ways to split $2$

Total: $1 \times 12 \times 3 = 36$

Total for Case $2$: $16 + 36 = 52$

Case 3: Sum of Odd Terms $O = 2$ Here, $E_{\text{add}} = 6 - 2 = 4$: we split $4$ extra even terms across even-indexed gaps. It is only possible to have 2 odd terms. Compositions of $2$ into 2 odd terms: $1+1$ $\implies$ $1$ way Odd-indexed gaps: $1$ $\implies$ $4$ ways to split $6$ Even-indexed gaps: $2$ $\implies$ $5$ ways to split $4$ More than $2$ odd terms is impossible, as the smallest sum of 4 positive odd terms is $1+1+1+1=4$, which is greater than $2$.

Total for Case $3$: $1 \times 4 \times 5 = 20$

We add the totals from all valid cases:

$$85 + 52 + 20 = 157$$ Hence, the number of valid sequences is $\boxed{157}$.

~Steven Zheng

Solution 2

Since the sum is even, the count of odd numbers is even, let it be $2k$. We can rewrite the sequence as:

$$e_{0, 1}, e_{0, 2}, \dots, e_{0, c_0}, o_1, e_{1, 1}, e_{1, 2}, \dots, e_{1, c_1}, o_2, \dots, o_{2k}, e_{2k, 1}, \dots, e_{2k, c_{2k}}$$ where o stands for odd and e stands for even. Denote

$$S_i= \sum_{j= 1}^{c_i} e_{i, j}$$ and we can notice that:

$$0= a_1 \circ a_2 \circ a_3 \circ \dots \circ a_n = \sum_{i= 1}^{2k} o_i+ \sum_{i= 0}^{2k} ((-1)^i S_i)$$ From which we can deduce:

$$\sum_{i= 1}^{k} S_{2i- 1}= 6 \text{ and }\sum_{i= 1}^{2k} o_i \leq 6$$ which we see $1 \leq k \leq 3$, so let's starting counting.

$\textbf{Claim}$: The number of even sequences summing up to $k$ is $2^{\frac{k}{2}- 1}$, this can be proven easily using stars and bars.

We denote $A_k$ as under a fixed $k$, the count of possible sequences $e_{1, .}, e_{3, .}, \dots, e_{2k- 1, .}$ summing up to $6$.

$B_{k, s}$ as the count of possible sequence $o_{.}$ summing up to $s$.

$C_{k, s}$ as the count of possible sequences $e_{0, .}, e_{2, .}, …, e_{2k, .}$ summing up to $6- s$.

Then the sought answer can be expressed as:

$$\sum_{k= 1}^{3} A_k \sum_{\frac{s}{2}= k}^{3} B_{k, s}C_{k, s}$$ And we can find each component individually.

First, by stars and bars, $B_{k, s}$ is just $\binom{\frac{s}{2}+ k- 1}{2k- 1}$.

Finding $C_{k, s}$ is also simple. When $s= 6$, $C_{k, s}$ is clearly $1$. and when $s= 4$, $C_{k, s}$ is always $2k$, which leaves us with $C_{1, 2}$, possible sequences are $[[], [2, 2]]\ / \ [[], [4]]\ / \ [[2, 2], []]\ / \ [[4], []]$ and $[[2], [2]]$, so $C_{1, 2}= 5$.

Lastly, we calculate $A_k$. $A_1$ is simply $2^{3- 1}= 4$.

There are 2 cases for $A_2$: $[S_1, S_3]= [0, 6]$ or $[2, 4]$ with their permutations.

For the first case, we have $2$ permutations, along with $2^{3- 1}$ sequences. For the second case, we also have $2$ permutations along with $2^{2- 1} \cdot 2^{1- 1}$ sequences. Summing up:

$$A_2= 2 \cdot 4+ 2 \cdot 2= 12$$ There are 3 cases for $A_3$: $[S_1, S_3, S_5]= [0, 0, 6], [0, 2, 4]$ or $[2, 2, 2]$ with their permutations.

For the first case, we have $3$ permutations, along with $2^{3- 1}$ sequences. For the second case, we have $6$ permutations along with $2^{2- 1} \cdot 2^{1- 1}$ sequences. For the third case, we have $1$ permutations and $1$ sequence. Summing up:

$$A_3= 3 \cdot 4+ 6 \cdot 2+ 1 \cdot 1= 25$$ Substituting back and we can finally get our answer:

$$4 \cdot (1 \cdot 5+ 2 \cdot 2+ 3 \cdot 1)+ 12 \cdot (1 \cdot 4+ 3 \cdot 1)+ 25 \cdot (1 \cdot 1)= \boxed{157}$$ ~PikaBlaze (feel free to edit)

Solution 3

We begin by analyzing the parity of the partial sums resulting from the operation $\circ$. Let $S_k$ denote the result of the operations on the prefix $a_1, \dots, a_k$. That is, $S_1 = a_1$ and $S_k = S_{k-1} \circ a_k$ for $k > 1$. The operation is defined as:

$$x \circ y = \begin{cases} x - y & \text{if } x \text{ is odd and } y \text{ is even}, \\ x + y & \text{otherwise}. \end{cases}$$ Observe that in both cases, $x \circ y \equiv x \pm y \equiv x + y \pmod 2$. By induction, the parity of the partial result $S_k$ is equal to the parity of the sum of the terms:

$$S_k \equiv \sum_{i=1}^k a_i \pmod 2.$$ This observation is crucial because the condition for subtraction depends on the parity of the previous result.

Specifically, the term $a_k$ (for $k > 1$) is subtracted if and only if $S_{k-1}$ is odd and $a_k$ is even. In all other cases, $a_k$ is added.

Since $S_{k-1} \equiv\sum_{i=1}^{k-1} a_i \pmod 2$, we can state the rule solely in terms of the sum of the preceding terms: $a_k$ is subtracted if and only if the sum of the previous terms is odd and $a_k$ itself is even.

Let $P$ be the set of indices $i$ such that $a_i$ is added, and $M$ be the set of indices $j$ such that $a_j$ is subtracted. The value of the expression is given by:

$$S_n = \sum_{i \in P} a_i - \sum_{j \in M} a_j.$$ We are given two conditions: the total sum of the integers is $\sum_{i=1}^n a_i = 12$, and the result of the operations is $S_n = 0$. Substituting the total sum into the expression for $S_n$:

$$S_n = \left(\sum_{i \in P} a_i + \sum_{j \in M} a_j\right) - 2\sum_{j \in M} a_j = 12 - 2\sum_{j \in M} a_j.$$ Setting $S_n = 0$ yields $12 - 2\sum_{j \in M} a_j = 0$, which implies:

$$\sum_{j \in M} a_j = 6.$$ Thus, the problem is equivalent to finding the number of sequences of positive integers with a total sum of 12 such that the sum of the $\textbf{subtracted}$ terms is exactly 6.

We can solve this using dynamic programming. Let $N(s, m)$ be the number of sequences of positive integers with total sum $s$ where the sum of the subtracted terms is $m$. We are interested in finding $N(12, 6)$.

The state transitions depend on whether the current accumulated sum $s$ is even or odd, as this determines whether the next term will be subtracted.

\begin{array}{|c|c|c|c|} \hline \text{Current Sum } s & \text{Last Term } v & \text{Prev Sum } s-v & \text{Action on } v \\ \hline \text{Even} & \text{Even} & \text{Even} & \text{Add} \\ \text{Even} & \text{Odd} & \text{Odd} & \text{Add} \\ \hline \text{Odd} & \text{Odd} & \text{Even} & \text{Add} \\ \textbf{Odd} & \textbf{Even} & \textbf{Odd} & \textbf{Subtract} \\ \hline \end{array}

Let's derive the recurrence relations for $N(s, m)$ by considering the last term added, say $v$. The previous sum was $s-v$.

$1.$ If the current sum $s$ is even:

The previous sum $s-v$ must have the same parity as $v$.

$\bullet$ If $v$ is even, $s-v$ is even. The previous sum was even, so $v$ was added (not subtracted).

$\bullet$ If $v$ is odd, $s-v$ is odd. An odd term is never subtracted.

In both cases, no subtraction occurred for the last term. Thus:

$$N(s, m) = \sum_{v \text{ even}} N(s-v, m) + \sum_{v \text{ odd}} N(s-v, m).$$ $2$. If the current sum $s$ is odd:

The previous sum $s-v$ must have the opposite parity to $v$.

$\bullet$ If $v$ is odd, $s-v$ is even. The previous sum was even, so $v$ was added.

$\bullet$ If $v$ is even, $s-v$ is odd. The previous sum was odd and $v$ is even, so $v$ was \textbf{subtracted}. The previous subtracted sum must have been $m-v$.

Thus:

$$N(s, m) = \sum_{v \text{ odd}} N(s-v, m) + \sum_{v \text{ even}} N(s-v, m-v).$$ We compute $N(s, m)$ for $s$ from 1 to 12. The base case is $N(0, 0) = 1$ (the empty sequence). We require $N(12, 6)$.

Performing the calculation step-by-step:

$\bullet$ $\mathbf{s=1}$ (Odd): $N(1,0) = N(0,0) = 1$.

$\bullet$ $\mathbf{s=2}$ (Even): $N(2,0) = N(1,0) (\text{add } 1) + N(0,0) (\text{add } 2) = 1 + 1 = 2$.

$\bullet$ $\mathbf{s=3}$ (Odd):

- $m=0$: Add 1 to $N(2,0)$, add 3 to $N(0,0)$. $2+1=3$.

- $m=2$: Add 2 (sub) to $N(1,0)$. $1$.

$N(3,0)=3, N(3,2)=1$.

$\bullet$ $\mathbf{s=4}$ (Even):

- $m=0$: Sum all $N(s', 0)$ for $s'<4$. $3+2+1+1 = 7$.

- $m=2$: Sum all $N(s', 2)$ for $s'<4$. $1+0+0+0 = 1$.

$N(4,0)=7, N(4,2)=1$.

$\bullet$ $\mathbf{s=5}$ (Odd):

- $m=2$: Add odd to $N(4,2)$ and $N(2,2)$; add even (sub) to $N(3,0)$.

- $v$ odd: $1$ (from $s=4$) + $0$ (from $s=2$) = $1$.

- $v$ even: Add 2 (sub) to $N(3,0)=3$. Add 4 (sub) to $N(1, -)$.

- Total for $m=2$: $1 + 3 = 4$.

- $m=4$: Add 2 (sub) to $N(3,2)=1$. Total 1.

$N(5,2)=4, N(5,4)=1$. (Other $m=0$ values omitted for brevity).

Continuing this process systematically up to $s=12$ and $m=6$:

$\bullet$ At $s=12$, we sum the contributions to reach a subtracted sum of $m=6$.

$\bullet$ The total count is found to be exactly $\boxed{157}$.

~ By Jesse Zhang (FUNKCCP)

List of Valid Sequences

The all 157 possible sequences:

111112221, 11111241, 11111421, 1111161, 111211221, 11121141, 111221121, 111222111, 11122212, 1112223, 11124111, 1112412, 111243, 11141121, 11142111, 1114212, 111423, 1116111, 111612, 11163, 11212221, 1121241, 1121421, 112161, 1132221, 113241, 113421, 11361, 121111221, 12111141, 121121121, 121122111, 12112212, 1211223, 12114111, 1211412, 121143, 12121221, 1212141, 1213221, 121341, 122111121, 122112111, 12211212, 1221123, 12212121, 1221321, 122211111, 12221112, 1222113, 12221211, 1222122, 1222131, 122214, 1222311, 122232, 12225, 1223121, 1231221, 123141, 12411111, 1241112, 124113, 1241211, 124122, 124131, 12414, 124311, 12432, 1245, 1312221, 131241, 131421, 13161, 14111121, 14112111, 1411212, 141123, 1412121, 141321, 14211111, 1421112, 142113, 1421211, 142122, 142131, 14214, 142311, 14232, 1425, 143121, 1611111, 161112, 16113, 161211, 16122, 16131, 1614, 16311, 1632, 165, 21112221, 2111241, 2111421, 211161, 21211221, 2121141, 21221121, 21222111, 2122212, 212223, 2124111, 212412, 21243, 2141121, 2142111, 214212, 21423, 216111, 21612, 2163, 2212221, 221241, 221421, 22161, 232221, 23241, 23421, 2361, 3112221, 311241, 311421, 31161, 3211221, 321141, 3221121, 3222111, 322212, 32223, 324111, 32412, 3243, 341121, 342111, 34212, 3423, 36111, 3612, 363, 412221, 41241, 41421, 4161, 52221, 5241, 5421, 561