12
$\begingroup$

Happy New Year 2024! I got to know that $$(10 + (9 + 8 \times 7) \times 6) \times 5 + 4 \times 3 \times 2 \times 1 = 2024.$$ I am wondering how many numbers can be represented by similar arithmetic operations ($+$ and $\times$) on the numbers from 10 to 1.

We can definitely write code to enumerate all the possible cases, but can we have better ways to find the numbers?

More specifically, I mean $$10 \operatorname{op}_1 9 \operatorname{op}_2 8 \operatorname{op}_3 7 \operatorname{op}_4 6 \operatorname{op}_5 5 \operatorname{op}_6 4 \operatorname{op}_7 3 \operatorname{op}_8 2 \operatorname{op}_9 1$$ with legal parentheses, where each $\operatorname{op}_i \in \{+, \times\}$ (we can consider "$-$" and "$/$" too! but less us stay with $\{+, \times\}$ first).


Naive idea: If I am correct, we have at most $9! \times 2^9 = 185794560$ possible situations, where $9!$ is the number of different orders of operators that might be changed by parentheses, and $2^9$ is the number of combinations of operators.


Reduce the cases: Ideas and techniques for improving the efficiency of enumeration are also appreciated! For example, we can find all the full binary trees with $10$ leaves and use reserve Polish to compute the numbers. Each case can be represented by a full binary tree, where the $10$ leaves are numbers and the $9$ non-leaves are operators. Hence, the number of cases can be further bounded by $$C_9 \times 2^9 = 2489344,$$ where $C_9 = 4862$ is the $9$-th Catalan number.


Moreover, even finding the maximum possible number seems interesting and nontrivial.


Related question: When considering all four arithmetic operations, the question would be equivalent to an existing question on the site (Construct numbers using digits $123456789$ and the operations $+,-,×,÷$). When only considering two operations ($+$ and $\times$), the question accepts unique techniques mentioned in the answer by @Misha Lavrov, which is also mentioned by @Benjamin Wang.

$\endgroup$
3
  • $\begingroup$ @bumblebee Thanks! The question is very related! But they didn't discuss any way to find such numbers other than using DP $\endgroup$
    – Vezen BU
    Commented Jan 1 at 23:31
  • $\begingroup$ I believe this question is not a duplicate since the linked question doesn't really have a full answer. This question is also slightly different, amenable to a different strategy as shown in the top answer. $\endgroup$ Commented Jan 3 at 10:15
  • $\begingroup$ @Benjamin I agree with you that with only two associative operators, the top answer provides essentially different insights. But I also admit that if we consider all for arithmetic operators, two questions are equivalent $\endgroup$
    – Vezen BU
    Commented Jan 3 at 10:24

2 Answers 2

7
$\begingroup$

We can think of the associative operations $+$ and $\times$ as operations which can take any number of arguments, representing the example in the question as $${+}\Bigg({\times}\bigg({+}\Big(10, {\times}\big({+}(9,{\times}(8,7)),6\big)\Big), 5\bigg), {\times}\bigg(4,3,2,1\bigg)\Bigg).$$ Now our expression tree is no longer a binary tree: each non-leaf node can have degree $2$ or higher. There are more such trees. But the advantage of this representation is that the operations no longer need to be chosen independently: they must alternate at each level, or else we'd combine the levels together. So there is only a $2$-way choice for the operations: is the top level $+$ or $\times$?

The number of trees we can build is given by OEIS sequence A001003, and for $10$ elements there are $103049$ trees. Multiplying by $2$, we get an upper bound of $206098$ possible numbers we can obtain.

This is actually the exact answer for how many possible expressions we can get with variable inputs $x_1, x_2, \dots, x_{10}$ instead of numerical inputs $10, 9, \dots, 1$. Past this point, the only improvement we can make to the count comes from identifying the places where fundamentally different operations give us the same answer. (For three inputs rather than ten, an example of this is $3+2+1 = 3\times 2\times 1$.)

It goes against the spirit of the question, but a brute-force search of these trees finds that there are

$35869$ different numbers that can be obtained in this way; the smallest is $$54 = 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 \times 1$$ and the largest is $$5443200 = 10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times (2 + 1).$$ When it comes to years, we'll be able to find an expression for every year until the end of the century except for $2048$.

$\endgroup$
0
-4
$\begingroup$

What about if I say ...

10_9_8_7_6_5_4_3_2_1 (assuming they have to be in descending order)

9 slots with 2 possibilities (× or +).

Total number of possibilities = $2^9 = 512$

The smallest number = $10 + 9 + \dots + 2 + 1 = 55$

The largest number = $10! = 3628800$

The maximum number of such numbers = $3628746$ (assuming we include parentheses to increase the range e.g. $4 + ( 3 \times 2) = 10$ and $(4 + 3) \times 2 = 14$)

Signing off ...

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .