The M2S3 game is a simple arithmetic puzzle. Given two numbers, the task is how to get from one number to the next using only multiplication by two (M2) and subtraction of three (S3). The goal is to minimize the number of steps.
In the M2S3 game, a sequence consists of a list of zero, one, or more operations, each of which is either or . The sequence can be applied to any sufficiently large positive integer by performing the operations in the given order; we will write for the outcome, which is necessarily also a positive integer. If any of the steps in calculating yields a non-positive value, we will declare undefined.
A concrete M2S3 puzzle is as follows: given an initial value , find the sequence that leads to a given outcome in a minimum number of steps; that is, for which sequence of minimum length is ?
We will call the answer to this puzzle .
An example of a sequence is When applied to the initial value , the sequence generates the output . The detailed steps are as follows:
The sequence cannot be applied if is too small. What is the minimum value of for which is defined?
If , the first or second subtraction results in zero, which is not allowed. If , things go fine at first but break down toward the end: The smallest value for which is defined is :
- Prove that if is defined, then is defined for all , and that in fact .
- Find a general rule to determine the minimum value of for which is defined.
Find the M2S3 sequence of minimum length from 8 to 11.
The answer is ; the steps are
There are several strategies to find this answer:
Start with and apply both of the possible operators. Do the same for the results, and so on. As soon as the outcome is 11, the search is complete, and the solution is guaranteed to be minimal. This solution is illustrated below. The dashed boxes indicate numbers that occurred in an earlier stage of the process, and therefore need not to be explored because it would only lead to longer-than-minimal sequences.
Start with and work backward. The inverse operation can be applied to each number, but the inverse operation only applies to even numbers. This method is more efficient than the first, because fewer attempts are needed.
Instead of exhaustive searching as in 1 and 2 above, one can also calculate the solution. This will be discussed in the sections below.
Is there a way to determine whether a solution exists and what that solution is, without exhaustive search?
Arithmetic modulo 3 gives some interesting insights. The positive numbers can be sorted into three bins: multiples of three, one less than multiples of three, and one more than multiples of three. Thus we will write Now consider the effect of the operations on these bins:
- Subtracting three results in a number from the same bin. In other words, .
- Multiplication by two has the same effect as flipping the sign: .
Therefore, if we begin with a multiple of three the same will be true for every next number in the calculation. If we begin with any other number (), the same will remain true; only the multiplication by two will swap back and forth between the and bins. This leads to the following conclusions:
- If is a multiple of 3, but is not, then there is no solution to the M2S3 game. Likewise, if is a multiple of 3, but is not, there is no solution.
- If and are both multiples of 3, all intermediate values in the calculation are multiples of 3. We might as well divide everything by three, and play a reduced game M2S1, where we subtract one instead of three. For instance,
- If and are not multiples of 3, but belong to the same bin then any sequence must contain an even number of multiplications by two. Likewise, if and are not multiples of 3, but belong to opposite bins then any sequence must contain an odd number of multiplications by two.
As long as either both or neither of and are multiples of three, a solution is guaranteed to exist. We prove this by generating a sequence such that ; it is usually not the minimal sequence, but if one such sequence exists, there must be a minimal one as well.
The idea is first to multiply by two as much as necessary to make the number big enough, and then to subtract three until the desired value is reached.
Step A. Choose a number such that , and moreover,
if are not multiples of three, should be even if and odd if ;
if are multiples of three, no further conditions apply.
Step B. Generate the sequence where
Exercise: Prove that for this sequence.
We will call the smallest value of that satisfies the above conditions .
Let and . Since and modulo 3, we need an odd value of .
Since but , the minimum allowed value is . Then so we define and get the steps The number of steps in this sequence is , which is not minimal; but at least we have proven that a solution exists.
Exercise: Suppose we play the game M4S5, with the operations and . Under what conditions does a sequence exist?
In the previous section we ended up with many subtractions at the end of the sequence. The number of subtractions may be reduced by placing them earlier in the sequence. The idea is that any subsequent multiplication by two "amplifies" the subtraction:
More specifically, we can shorten a sequence by repeatedly replacing
We can repeat this process until no two successive subtractions remain, except possibly at the beginning of the sequence. Thus we find a sequence of the form Here the brackets indicate that this step is optional.
The sequence contains multiplications by two. Let us number them from right to left, from on the right to on the left. Define The numbers may be interpreted as bits--digits in a binary numeral . We have Here, is the "effective" number of subtractions of three, as defined above.
Challenge: Convince yourself that this formula for is correct.
We now have a sequence starting with subtractions, containing multiplications, and inserting subtractions after the multiplications. (I will write for the number of ones in the binary representation of .) Thus the sequence has length Since we have minimized the number of subtractions, this sequence is guaranteed to be the shortest for the chosen value of multiplications, . We will call the sequence generated this way .
Let and . Then , so that we need an even number of multiplications . Let us choose . Note that in this case; we do not pick the minimal value for
Then so that we could in principle start with 6 multiplications and then apply 294 subtractions. The number of subtractions can be minimized by noting that Writing in binary notation, we get . We now have a recipe for a sequence: start with subtractions, then multiplications, and insert one subtraction after multiplications 1, 2, and 5 (counting from the right and starting with zero). Thus, This corresponds to the calculation The length of this sequence is . It is obvious that this is not the shortest sequence; note that the calculation contains a cycle .
Exercise: Repeat this calculation with the minimal number of multiplications . How does the sequence you find compare to the one with ?
For a complete solution of the M2S3 puzzle, all that remains is to determine the value of for which is minimal. It is tempting to conclude immediately that this happens for the minimal possible value ; that is, . But this must be proven first.
Can you prove this?
Conjecture: If a sequence has multiplications, and , then it contains at least one cycle. Removing the longest cycle will remove precisely multiplications, and will result in the shortest possible sequence.
In the previous example, the cycle was , consisting of two multiplications. Indeed, we generated this sequence with while .