A(111) + B(11) + C = 1000. Find no. of distinct values of C + 2B+ 3A

Question

IOQM 2022 Problem 19:

Consider a string of n 1’s. We wish to place some + signs in between so that the sum is 1000. For instance, if n = 190 , one may put + signs so as to get 11 ninety times and 1 ten times, and get the sum 1000. If a is the number of positive integers n for which it is possible to place + signs so as to get the sum 1000, then find the sum of the digits of a.

This is the real problem. I've written the simplified version ( what we actually need to find ) in the title.

I used the following method to solve this question :

Since the sum should be thousand we won't take strings greater than 111. So, we basically have to solve

$ 111A + 11B + C = 1000 $

We can easily solve this by counting the cases -

$A = 0$     $B = 0$    $C$ has $1$ value

$A = 9$    $B= 0$    $C$ has $1$ value

$A = 8$    $B = 0,1,2,..,10$    $C$ has $11$ values

$A = 7$    $B = 0,1,2,...,20$    $C$ has $21$ values

$A = 6$    $B = 0,1,2,...,30$    $C$ has $31$ values

$A = 5$    $B = 0,1,2,...,40$    $C$ has $41$ values

$A = 4$    $B = 0,1,2,...,50$    $C$ has $51$ values

$A = 3$    $B = 0,1,2,...,60$    $C$ has $61$ values

$A = 2$    $B = 0,1,2,...,70$    $C$ has $71$ values

$A = 1$    $B = 0,1,2,...,80$    $C$ has $81$ values

So, there are $460$ cases in total. But the problem is, that for all of these $460$ cases

$3A$ + $2B$ + $C$ is not unique. So, how should I proceed ?

Answer 1

You've already determined that

$$111A + 11B + C = 1000 \tag{1}\label{eq1A}$$

$$3A + 2B + C = n \tag{2}\label{eq2A}$$

Next, \eqref{eq1A} minus \eqref{eq2A} gives

$$108A + 9B = 1000 - n \;\to\; 9(12A + B) = 1000 - n \;\to\; 12A + B = \frac{1000 - n}{9} \tag{3}\label{eq3A}$$

This shows $1000 - n$ is an integral multiple of $9$, i.e.,

$$n = 9k + 1 \tag{4}\label{eq4A}$$

for some integer $0\le k \le 111$ (the upper bound due to $n \le 1000$ as $12A + B \ge 0$). Substituting this into \eqref{eq2A} and \eqref{eq3A}, as well as multiplying both sides of \eqref{eq2A} by $4$ and using that $B, C \ge 0$, we get

$$36k + 4 = 4n \ge 12A + 8B \ge 12A + B = \frac{1000 - n}{9} = 111 - k \tag{5}\label{eq5A}$$

Using the LHS and RHS parts from above gives that

$$36k + 4 \ge 111 - k \;\to\; 37k \ge 107 \;\to\; k \ge 3 \tag{6}\label{eq6A}$$

The upper bound of $111$ for $k$ mentioned earlier means the range of possible values for $k$ are

$$3 \le k \le 111 \tag{7}\label{eq7A}$$

All these $109$ values need to be checked as some may not result in integer solutions. For $k = 3$, we have $A = 9$, $B = 0$ and $C = 1$ as a solution. For $k = 4$, however, we have from \eqref{eq2A} that $3A + 2B + C = 37$, and the RHS of \eqref{eq5A} that $12A + B = 107$. Considering using the solutions of the second equation in the first one, then $A = 8$ and $B = 11$ gives $3A + 2B = 24 + 20 = 46 \gt 37$. For each next possible $A$ and $B$, since $A$ decreases by $1$ while $B$ increases by $12$, then $3A + 2B$ changes by $3(-1) + 2(12) = 21$. Thus, the LHS of the first equation will always be $\gt 37$, so there's no solution for $k = 4$.

For $k \ge 5$, choosing the smallest non-negative integer value of $B$ which satisfies $12A + B = 111 - k$, then using this and the corresponding $A$ in \eqref{eq2A}, always results in a positive value of $C$. For $k = 5$, we get $A = 8$, $B = 10$ and $C = 2$. For each increase in $k$ by $1$ up to $15$, we have $A = 8$, $B$ decreases by $1$ and $C$ increases by $11$, to end up with $k = 15$, $A = 8$, $B = 0$ and $C = 112$.

Next, for $k = 16$, we have $A = 7$, $B = 11$ and $C = 102$. Note that using this procedure means that $A \le 7$ and $B \le 11$ for $k \ge 16$. Thus, $3A + 2B \le 3(7) + 2(11) = 43$ and $n = 9k + 1 \ge 9(16) + 1 = 145$, so $C \gt 0$. This continues until we get for $k = 111$ that $A = B = 0$ and $C = 1000$.

This shows there are $108$ distinct values of $n$, so $a = 108$ which has a sum of digits of $9$. Note this matches the result in Semiclassical's answer, as well as the answer at the end of the OP's linked PDF.

Answer 2

Here is a partial analysis, though carrying it through to a final solution exceeds my patience. Suppose we have two solutions $(A_1,B_1,C_1),(A_2,B_2,C_2)$ to $111A+11B+C=1000$ with the same value of $3A+2B+C$. This requires$$\begin{align}3A_1+2B_1+C_1&=3A_2+2B_2+C_2,\tag{1} \\ 111A_1+11B_1+C_1&=111A_2+11B_2+C_2\tag{2}\end{align}$$

Subtracting Eq. (1) from Eq. (2) yields

$$108A_1+9B_1=108A_2+9B_2\implies B_2-B_1=-12(A_2-A_1)$$

Rearranging Eq. (1) for $C_2-C_1$ now yields

$$C_2-C_1=-3(A_2-A_1)-2(B_2-B_1)=21(A_2-A_1)$$

Thus if $(A,B,C)$ is a solution to $111A+11B+C=1000$, then any other solution which yields the same value of $3A+2B+C$ is of the form $(A-k,B+12k,C-21k)$. So for instance the following six solutions all yield $3A+2B+C=136$:

$$(A,B,C)=(8,0,112),(7,12,91),(6,24,70),(5,36,49),(4,48,28),(3,60,7)$$

The challenge remaining is to work out how many distinct "chains" of such equivalent solutions exist.

---

Since John Omielan has provided a more satisfactory version of the above approach, I'll instead give a computational approach to validate the result. First, the set of nonnegative integer solutions to $111A+11B+C=1000$ can be generated in Mathematica using Solve over the NonNegativeIntegers domain. Since (as noted in John Omielan's answer) the only possible values of $3A+2B+C$ are of the form $9k+1$, we use these solutions to compute $(3A+2B+C-1)/9$. We then delete duplicates and sort the resulting list:

DeleteDuplicates[Sort[(3a+2b+c-1)/9/.Solve[111a+11b+c==1000,{a,b,c},NonNegativeIntegers]]]

This yields the following set of possible values for $k$: {3,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111}.

Apart from the first element $k=3$, this amounts to $5\leq k\leq 111$. So this yields 108 distinct values and thus the sum of digits is 9 (which agrees with the answer in the OP's linked PDF).

As a final point, if we don't delete duplicates in the list of $k$ values then we can Tally how many solutions correspond to a given $k$ value. This corresponds to the code

ListPlot[Sort[Tally[(3a+2b+c-1)/9/.Solve[111a+11b+c==1000,{a,b,c},NonNegativeIntegers]]],Filling->Axis]

with graph shown below:

Note the visible gap at $k=4$.