aime26-01

Proposed solution

I need to find the number of positive integer palindromes with no zero digits where the sum of digits equals 13.

Let me think about the structure of palindromes. A palindrome reads the same forwards and backwards, so I only need to determine the first half of the digits (or the first half plus the middle digit for odd-length palindromes).

Let me consider palindromes of different lengths:

**Case 1: 1-digit palindromes**
These are just single digits. Since we need no zeros and sum = 13, this is impossible since the maximum single digit is 9.

**Case 2: 2-digit palindromes**
A 2-digit palindrome has the form $aa$ where $a$ is a non-zero digit.
Sum of digits = $a + a = 2a = 13$
This gives $a = 6.5$, which is not an integer. So no solutions.

**Case 3: 3-digit palindromes**
A 3-digit palindrome has the form $aba$ where $a, b$ are non-zero digits.
Sum of digits = $a + b + a = 2a + b = 13$
Since $a \geq 1$ and $b \geq 1$, we have $2a + b = 13$.
Also, $a \leq 9$ and $b \leq 9$.

From $b = 13 - 2a$:
- $b \geq 1$ means $13 - 2a \geq 1$, so $2a \leq 12$, so $a \leq 6$
- $b \leq 9$ means $13 - 2a \leq 9$, so $2a \geq 4$, so $a \geq 2$

Therefore: $2 \leq a \leq 6$
The valid pairs $(a,b)$ are:
- $a = 2, b = 9$: palindrome 292
- $a = 3, b = 7$: palindrome 373
- $a = 4, b = 5$: palindrome 454
- $a = 5, b = 3$: palindrome 535
- $a = 6, b = 1$: palindrome 616

That's 5 palindromes.

**Case 4: 4-digit palindromes**
A 4-digit palindrome has the form $abba$ where $a, b$ are non-zero digits.
Sum of digits = $a + b + b + a = 2a + 2b = 13$
This gives $a + b = 6.5$, which is impossible since $a, b$ are integers.

**Case 5: 5-digit palindromes**
A 5-digit palindrome has the form $abcba$ where $a, b, c$ are non-zero digits.
Sum of digits = $a + b + c + b + a = 2a + 2b + c = 13$
We need $a \geq 1, b \geq 1, c \geq 1$ and $a \leq 9, b \leq 9, c \leq 9$.

So $2a + 2b + c = 13$, which means $c = 13 - 2a - 2b$.
We need $1 \leq c \leq 9$, so $1 \leq 13 - 2a - 2b \leq 9$.

This gives us: $4 \leq 2a + 2b \leq 12$, or $2 \leq a + b \leq 6$.

Let's count the valid combinations:
- $a + b = 2$: $(a,b) = (1,1)$, so $c = 9$. Palindrome: 11911
- $a + b = 3$: $(a,b) = (1,2), (2,1)$, so $c = 7$. Palindromes: 12721, 21712
- $a + b = 4$: $(a,b) = (1,3), (2,2), (3,1)$, so $c = 5$. Palindromes: 13531, 22522, 31513
- $a + b = 5$: $(a,b) = (1,4), (2,3), (3,2), (4,1)$, so $c = 3$. Palindromes: 14341, 23332, 32323, 41314
- $a + b = 6$: $(a,b) = (1,5), (2,4), (3,3), (4,2), (5,1)$, so $c = 1$. Palindromes: 15151, 24142, 33133, 42124, 51115

That's $1 + 2 + 3 + 4 + 5 = 15$ palindromes.

**Case 6: 6-digit palindromes**
A 6-digit palindrome has the form $abccba$ where $a, b, c$ are non-zero digits.
Sum of digits = $a + b + c + c + b + a = 2a + 2b + 2c = 13$
This gives $a + b + c = 6.5$, which is impossible.

**Case 7: 7-digit palindromes**
A 7-digit palindrome has the form $abcdecba$ where $a, b, c, d$ are non-zero digits.
Sum of digits = $a + b + c + d + c + b + a = 2a + 2b + 2c + d = 13$
We need $2a + 2b + 2c + d = 13$ where each variable is between 1 and 9.

Let's consider this systematically. Since we want $2a + 2b + 2c + d = 13$ with $a, b, c, d \geq 1$, we have:
$2(a + b + c) + d = 13$

Since $d \geq 1$, we have $2(a + b + c) \leq 12$, so $a + b + c \leq 6$.
Since $a, b, c \geq 1$, we have $a + b + c \geq 3$.

So $3 \leq a + b + c \leq 6$.

For each value of $s = a + b + c$:
- $s = 3$: $d = 7$, and we need to count ways to write $a + b + c = 3$ with $a, b, c \geq 1$. This is $\binom{2}{2} = 1$ way.
- $s = 4$: $d = 5$, and we need to count ways to write $a + b + c = 4$ with $a, b, c \geq 1$. This is $\binom{3}{2} = 3$ ways.
- $s = 5$: $d = 3$, and we need to count ways to write $a + b + c = 5$ with $a, b, c \geq 1$. This is $\binom{4}{2} = 6$ ways.
- $s = 6$: $d = 1$, and we need to count ways to write $a + b + c = 6$ with $a, b, c \geq 1$. This is $\binom{5}{2} = 10$ ways.

Total for 7-digit palindromes: $1 + 3 + 6 + 10 = 20$

**Case 8: 8-digit palindromes**
A palindrome o