Problem:
Consider a string of 's, , into which signs are inserted to produce an arithmetic expression. For example, could be obtained from eight 's in this way. For how many values of is it possible to insert signs so that the resulting expression has value ?
Solution:
To simplify, replace all the 's with 's, that is, divide all the numbers in the sum by . The desired values of are the same as the values of for which + signs can be inserted in a string of 's to obtain a sum of . The result will be a sum of 's, 's, and 's, where , and are nonnegative integers, , and . Subtract to find that , so . There cannot be more than 's in a string whose sum is , and the least number of 's occurs when the string consists of nine 's and one . Therefore , and so . Thus the number of values of is the number of possible integer values of between and , inclusive, subject to the condition that
Note that is equivalent to , and therefore to . Then use the fact that to conclude that is equivalent to , and therefore to . The fact that is nonnegative means that . Thus an ordered pair of integers satisfies
if and only if it satisfies and . Hence when can have any integer value between and , inclusive; when can have any integer value between and , inclusive; and when can have any integer value between and , inclusive. But only if , that is, when ; and when , implies that . Thus for nonnegative integers and can have any integer value between and except for , so there are possible values for .
To simplify, replace all the 's with 's, that is, divide all the numbers in the sum by . The desired values of are the same as the values of for which + signs can be inserted in a string of 's to obtain a sum of . Because the sum is congruent to modulo and , it follows that . Also, . There are positive integers that satisfy both conditions, namely, . For , or , the greatest sum that is less than or equal to is . Thus , so there are at most possible values of , and these values are contained in . It will be shown that all elements of except are possible.
First note that is possible because , while is not possible because when , the greatest sum that is at most is . All other elements of are possible because if any element of between and is possible, then must be too. To see this, consider two cases, the case where the sum has no 11's and the case where the sum has at least one .
If the sum has no 's, it must have at least one . If it has exactly one , there must be nine 's and . Thus, for , the sum has more than one , so it must have at least 's, and, for , at least one . To show that if is possible, then is possible, replace a with , replace eleven 's with eleven 's, and include nine new 's as +'s. The sum remains .
If the sum has at least one , replace an with , and include nine new 's as +'s.
Now note that is possible because , and so all elements of except are possible. Thus there are possible values for .
The problems on this page are the property of the MAA's American Mathematics Competitions