USAJMO/USAMO 2026 (Problem 5/4)

A positive integer

n

is called solitary if, for any nonnegative integers

a

and

b

such that

a+b=n

, either

a

b

contains the digit

1

when written in base

10

. Determine, with proof, the number of solitary integers less than

10^{2026}

We guess there are

2^m-1

solitary integers less than

10^m

.

Let's prove it by induction.

Suppose

r_1,r_2,\ldots,r_{2^{m-1}-1}

are the solitary integers less than

10^{m-1}

.Our claim is that the only solitary integers less than

10^m

are

\left\{r_1,r_2,\ldots,r_{2^{m-1}-1},\underbrace{199\ldots9}_{m-1\text{ nines}},2\times10^{m-1}+r_1,2\times10^{m-1}+r_2,\ldots,2\times10^{m-1}+r_{2^{m-1}-1}\right\}.

\underbrace{199\ldots9}_{m-1\text{ nines}}=a+b,

without loss of generality, assume

a\le b

\underbrace{199\ldots9}_{m-1\text{ nines}}\ge b\ge\underbrace{100\ldots0}_{m-1\text{ zeros}}.

Therefore,

b

contains the digit

1

\Rightarrow\underbrace{199\ldots9}_{m-1\text{ nines}}\text{ is solitary}.

Now consider

2\times10^{m-1}+r_i=a+b.

Without loss of generality, assume

a\le b

b\ge10^{m-1}.

2\times10^{m-1}+r_i

is not solitary, then

b\ge2\times10^{m-1}.

r_i=(b-2\times10^{m-1})+a.

Since

r_i

is solitary, either

b-2\times10^{m-1}

a

contains the digit

1

. Hence either

b

a

contains the digit

1

, which gives a contradiction.Now the only thing left to prove is that all the other numbers, except the solitary integers we have identified, are not solitary.

Assume

s\notin\left\{r_1,r_2,\ldots,r_{2^{m-1}-1},\underbrace{199\ldots9}_{m-1\text{ nines}},2\times10^{m-1}+r_1,\ldots,2\times10^{m-1}+r_{2^{m-1}-1}\right\}.

10^{m-1}\le s\le2\times10^{m-1}-2,

s=\underbrace{999\ldots9}_{m-1\text{ nines}}+\overline{c_{m-2}c_{m-3}\ldots c_1c_0}.

c_i=1

, add

1

c_i

and subtract

1

from the corresponding

9

, so

s

is not solitary.

If

2\times10^{m-1}<s<3\times10^{m-1}

and

s\ne2\times10^{m-1}+r_i

, then

s=2\times10^{m-1}+t,\qquad t\ne r_i.

Since

t

is not solitary, we can write

t=a+b

, where neither

a

nor

b

contains the digit

1

. Therefore,

s=(2\times10^{m-1}+a)+b,

and neither summand contains the digit

1

, so

s

is not solitary.

If

3\times10^{m-1}\le s<10^m,

Then

s=\overline{a\underbrace{99\ldots9}_{m-1}}+\overline{c_{m-2}c_{m-3}\ldots c_0},

where

2\le a\le8

.If

c_i=1

, add

1

c_i

and subtract

1

from the corresponding

9

, so

s

is not solitary.Therefore, the solitary integers less than

10^m

are exactly the numbers in our claimed set.Their number is

(2^{m-1}-1)+1+(2^{m-1}-1)=2^m-1.

By induction, the result holds for every positive integer

m

.Taking

m=2026

, the answer is

\boxed{2^{2026}-1}.\quad\checkmark