Integermania - Number of Solutions

How many solutions can an Integermania problem have?

Theorem: In an Integermania problem with $n$ values and $k$ available binary operations, where each value is used exactly once, and values are combined by using only the available binary operations, there are at most $\dfrac{k^{n-1} (2n-2)!}{(n-1)!}$ positive integers which can be created.

Outline of Proof: Let a set of $n$ values $m_i$ be fixed, and let $p_j$ denote the $k$ available binary operations. A solution $s$ can be uniquely described by the sequence of operations $p$ used on the $n$ values to obtain $s$, and will take the form $m_1 p_1 m_2 p_2 \cdots p_{n-1} m_n$, with parentheses to determine the order of operations. Since the $n$ values are assumed to be distinct and not repeated, there are $n!$ ways to order the values in the above solution form. The operations can be repeated, and are chosen from a set of $k$ possible operations. There are $k^{n-1}$ ways to select those operations. The number of ways to insert sets of parentheses is $C(n-1)$, a term of the sequence of Catalan numbers given by $C(n) = \frac{1}{n+1} \binom{2n}{n}$. Multiplying these three factors gives the result. See proof for more details.

A Worst Case Example: Define the set of values $a, b \in \{1,2,3,4\}$, and define the four operations:

\begin{equation} a \oplus_k b = k \times 10^{2 + [\log_{10} a] + [\log_{10} b]} + a \times 10^{1 + [\log_{10} b]} + b \end{equation}

for $k \in \{5,6,7,8\}$. It can be shown that the result of each of these four operations is equivalent to writing the juxtaposed result $kab$, both of which are equivalent to the original operation written in prefix notation. In other words, each result retains all of the information about the operations, value, and order of operations used to produce it, and therefore any combination of the operations is one-to-one. There are 7680 ways in which all four values can be used exactly once each, using three of the four available binary operations, as stated by the theorem. Each of those ways gives a different 15-digit positive integer solution.

Comments: The worst case example provides evidence that the formula given by the theorem is the best possible bound on the number of solutions without additional information about the values or the operations. But for a particular Integermania problem, the number of possible positive integer solutions may be much smaller, due to repeated values in the set of values, operations which are commutative, solutions which are not positive integers, or solutions which can be produced in more than one way.

Back to Theorems and Conjectures.