Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I assume everyone here knows the 24-game -- given 4 numbers, combine them using +,-,x,/ and parentheses to form 24. An obvious generalization is to give $n$ integers ${a_,...,a_n}$ as input and specify the target value $t$.

Barring obvious cases, such as when $a_1a_2...a_n<t$, it seems that most instances are solvable. Does anyone know of a proof of such a result?

One potential formalizaiton: If the $a_i$ and $t$ are all chosen i.i.d. from ${1,...,N}$, what is the probability that the instance is solvable?

share|improve this question
    
Your formalization sounds very, very difficult, and probably subject to parity issues. It is well-defined, but I would like to see a graph for small N. –  Eric Tressler Jul 30 '10 at 19:22
5  
Here's an interesting one: 8,3,8,3 (my favourite). Your goal is to make 24. And yes, you have to use all the numbers, and only +-*/ and brackets. But for the general question it's surely not going to be true that "most instances are solvable". For example if $a_n$ is much much bigger than all the rest of the numbers, what are you going to do with it? e.g. if I give you $1,2,3,4,5,10^10$ then you're going to have a huge job making any small $t$, right? In fact if $n$ is fixed and $N$ goes to infinity, then the probability will tend to zero as $N\to\infty$. –  Kevin Buzzard Jul 30 '10 at 19:42
2  
Ah, Countdown, that brings back memories. Carol Vorderman could normally do this for n=6 and t < 1000, but not always. –  George Lowther Jul 30 '10 at 20:37
    
Do you have to use all the numbers? That makes it trickier –  George Lowther Jul 30 '10 at 20:40
1  
@Noah: but 2(10-3)+10=24 –  Tony Huynh Jul 31 '10 at 0:45

1 Answer 1

To expand on Kevin's comment (and using an answer since a comment doesn't have enough characters!) : one other obvious-but-relevant constraint that's going to be an issue for large values of $N$ is that the number of possible answers that can be acheived is a function strictly of $n$ and not of the $a_i$ (modulo a few minor issues like repetition of values etc): there are only $C_{n-1}$ 'operation' trees with $n$ leaves, where $C_n$ are the Catalan numbers, approximately $4^n$ plus some polynomial factors; since each of the $(n-1)$ internal nodes can be filled with one of 4 binary operators that adds another factor of $4^{n-1}$ to the total; and of course the $a_n$ can be permuted in $n!$ ways, so the overall bound is something like $n^n\alpha^n$ for $\alpha \approx 16/e \approx 5.9$; concretely, there are a maximum of $C_3 * 4^3 * 4!$ = 5 * 64 * 24 = 7680 possibilities for the $n=4$ case, so if $N$ is larger than this, you're guaranteed to have gaps regardless of the values for $a_i$ (and as $N$ goes to infinity, the number of possible solutions won't change, so the probability will be approximately $c/N$ for some constant $c$ - one interesting question would be what $c$ is likely to be, or more specifically, how many 'collisions' will reduce the number below the hard bound? There are a lot of obvious cases (e.g., swapping the terms of a summand won't make any difference) so the number of possible values is well below the explicit upper bound, but other than wildly speculating that it's still superexponential in $n$ I'm not even sure how to begin calculating it.

One conjecture that seems both plausible and accessible to me is that any 'numeric' bound is likely to hew closely to the 'algebraic' upper bound (where you treat the $a_i$ as independent variables rather than numbers and consider only the equivalence of the resulting functions and not the values they evaluate to); more specifically, if $F_n$ is the aforementioned number of algebraically distinct functions for a given $n$, then $\Sigma_{a_0=0}^{N}\Sigma_{a_1=0}^{N}\dots\Sigma_{a_n=0}^{N}(\sharp values)= F_nN^n(1-o(1))$, where $(\sharp values)$ is the number of distinct values acheivable for that set of $a_i$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.