10 Twos and Random Operators

E(2 □ 2 □ 2 □ 2 □ 2 □ 2 □ 2 □ 2 □ 2 □ 2)

Problem

Alice writes a horizontal line of 10 twos on a blackboard:

2 □ 2 □ 2 □ 2 □ 2 □ 2 □ 2 □ 2 □ 2 □ 2 = ?

Bob then randomly places one of the four operators (+,-,x,÷) in each of the 9 gaps in between. What’s the expected value of the final computation?

Note that the order of operations is considered during the final computation, i.e. 2+2x2 is evaluated as 2+(2x2).

Source: ABMC Online Contest, December 2024

Hint 1

Consider the symmetry.

Hint 2

What if only x and ÷ are allowed.

Solution

Note that the expression can be divided into blocks separated by + and -, with each block being evaluated independently. For example, the expression 2 - 2 + 2x2÷2 + 2÷2 - 2÷2÷2 can be split into the blocks 2, -2, 2x2÷2, 2÷2, and -2÷2÷2. The results of evaluating these individual blocks can then be summed to obtain the final result.

Additionally, each expression with two or more blocks has a corresponding paired expression where every + is replaced with -, and every - is replaced with +. For example, 2 - 2 + 2x2÷2 + 2÷2 - 2÷2÷2 and 2 + 2 - 2x2÷2 - 2÷2 + 2÷2÷2 form such a pair. When summing each pair, all blocks except the first, which is always positive, cancel out with their corresponding counterparts. Therefore, the sum of the pair is simply twice the value of the first block. This observation allows us to perform case analysis based on the first block, determined by the position of the first + or -.

In the case where the first +/- appears in the \(i\)-th position (\(i\) ranging from 1 to 9). (We will consider the case where there is no +/- in the end). Let’s count how many such expressiosn are there in this case. Since the gaps before the \(i\)-th position can only be filled with x or ÷, there are only two choices for each of the first i positions. For the remaining gaps, there are 4 choices each, resulting in a total of \(2^{i} \times 4^{9-i}\) different expressions (out of \(4^9\) possible expressions).

Keep in mind that these \(2^{i} \times 4^{9-i}\) different expressions form \(2^{i-1} \times 4^{9-i}\) pairs with \(2^{i-1}\) distinct leading blocks. Thus we only need to compute the sum of these \(2^{i-1}\) different leading blocks and multiply by \(2\cdot 4^{9-i}\) to get the total sum of expressions where the first +/- appears in the \(i\)-th position.

Each leading block consists of \(i\) twos without any + or - operators, where the \(i−1\) operators include only x and ÷. Since the number of x and ÷ in the leading block adds up to \(i−1\), and an invisible \(1 \times\) precedes the very first 2, the total sum of distinct leading blocks can be calculated using the binomial theorem: \[ 2 \cdot (2+1/2) ^ {i-1} = 2 \cdot (\frac{5}{2})^{i-1}.\] We then multiply this result by \(2\cdot 4^{9-i}\) to obtain the total sum of expressions in this case. Dividing by \(4^9\), the total number of possible expressions, gives the contribution to the final expected value from this case the case where the first + or - appears in the \(i\)-th position: \[ \frac{2 \cdot (5/2) ^ {i-1} \cdot (2\cdot 4^{9-i})}{4^9} = (\frac{5}{8})^{i-1}. \]

Lastly, we consider the case where there is no +/- at all. In this scenario, the entire expression consists only of x and ÷ operators. Similarly, the total sum of distinct leading blocks of \(10\) two’s without any \(+/-\) operators can be calculated using the binomial theorem: \[ 2 \cdot (2+1/2) ^ 9 = 2 \cdot (\frac{5}{2})^{9}.\]

Since there are no blocks after this case, we simply divide by \(4^9\) to obtain the contribution to the final expected value from this case, which is \[ \frac{2 \cdot (5/2) ^ 9}{4^9} = 2(\frac{5}{8})^{9}. \] Therefore the final expected value is \[ 1 + \frac{5}{8} + \cdots + (\frac{5}{8})^{i-1} + \cdots + (\frac{5}{8})^{8} + 2(\frac{5}{8})^{9} = \frac{8}{3} - \frac{2}{3} (\frac{5}{8})^{9}. \]

Finally, the discussion and results above can be readily generalized and the formula for computing the expected value of expressions involving \(n\) twos is \[ 1 + \frac{5}{8} + \cdots + (\frac{5}{8})^{i-1} + \cdots + (\frac{5}{8})^{n-2} + 2(\frac{5}{8})^{n-1} = \frac{8}{3} - \frac{2}{3} (\frac{5}{8})^{n-1}. \] It is worth noting that when \(n\) goes to \(\inf\), this expected value converges to \(\frac{8}{3}\).

Code

To confirm the correctness of the solution above, one can write a program to enumerate all possible expressions and evaluate them using a brute-force approach. Below is an example of such a Python program (courtesy of ChatGPT).

```{python}
# P15 from https://abmathcompetitions.org/wp-content/uploads/2024/12/2025_december_online_contest.pdf
from itertools import product

# Define the operators
operators = ['+', '-', '*', '/']

def evaluate_expression(expression):
    """Evaluate the expression respecting operator precedence."""
    tokens = expression.split()

    # First handle * and /
    i = 0
    while i < len(tokens):
        if tokens[i] in ('*', '/'):  # Handle higher precedence operators
            left = float(tokens[i - 1])
            operator = tokens[i]
            right = float(tokens[i + 1])

            if operator == '*':
                result = left * right
            elif operator == '/':
                # Avoid division by zero
                if right == 0:
                    return None
                result = left / right

            # Replace the operation with its result
            tokens = tokens[:i - 1] + [str(result)] + tokens[i + 2:]
            i -= 1  # Step back to reprocess
        else:
            i += 1

    # Then handle + and -
    i = 0
    while i < len(tokens):
        if tokens[i] in ('+', '-'):  # Handle lower precedence operators
            left = float(tokens[i - 1])
            operator = tokens[i]
            right = float(tokens[i + 1])

            if operator == '+':
                result = left + right
            elif operator == '-':
                result = left - right

            # Replace the operation with its result
            tokens = tokens[:i - 1] + [str(result)] + tokens[i + 2:]
            i -= 1  # Step back to reprocess
        else:
            i += 1

    return float(tokens[0])

def generate_expressions(n, operators):
    """Generate all valid expressions using n numbers and operators."""
    numbers = [2] * n
    for ops in product(operators, repeat=n - 1):
        # Create an expression by interleaving numbers and operators
        expression = "".join(f"{numbers[i]} {ops[i]} " if i < len(ops) else f"{numbers[i]}" for i in range(len(numbers)))
        yield expression.strip()

def f(n):
    # 1 + 5/8 + (5/8)^2 + ... + (5/8)^{n-2} + 2*(5/8)^{n-1}
    return 8/3 - 2/3*(5/8)**(n-1)

def main(n):
    unique_results = {}

    for expr in generate_expressions(n, operators):
        result = evaluate_expression(expr)
        if result is not None:
            unique_results[expr] = result

    # Compute the total sum of all unique results
    total_sum = sum(unique_results.values())

    print("Total Number of Expressions:", len(unique_results))
    print("Total Sum of Results:", total_sum)
    print("Expected value (brute-force):", total_sum / len(unique_results))

    print("Expected value (using formula):", f(n))

if __name__ == "__main__":
    n = 10  # Number of twos
    main(n)
```

Total Number of Expressions: 262144
Total Sum of Results: 696507.53515625
Expected value (brute-force): 2.6569653898477554
Expected value (using formula): 2.6569653898477554