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

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 ?

$$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.

• @Semiclassical Thank you for your feedback, in particular about my error. I made a calculation mistake with my $(6)$ as the RHS should be $\ge 3$, not $\ge 4$. Also, I removed my second set of inequalities since I had mixed up $\ge$ with $\le$, so it wasn't valid. Thus, I added to my answer the solution for $k=3$, and showed that $k=4$ has no solution, to conclude there are $108$ possible solutions (for a digits sum of $9$) rather than my earlier conclusion of $107$. Commented Aug 6 at 23:49
• Glad it was helpful. (I had stumbled myself over the fact that $k=4$ is an exceptional case.) Commented Aug 6 at 23:51

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$$.