Optimal Countdown - MathOverflow

Optimal Countdown

2011-04-08T08:44:02Z

Many know the TV game Countdown, whose French version Des chiffres et des lettres has lasted since 1965.

The rules of the count are as follows: you are given natural integers $n_1,\ldots,n_6$ and a target $N$. You are free to employ the four operations $+,\times,-,\div$. You may employ each $n_j$ at most once. You must end with the result $N$.

For mathematicians, a colleague of mine suggests to modify the rule that way: you are given $k\ge1$. You are free to choose $n_1,\ldots,n_k$. Then you must realize the targets $1,2\ldots,N$. How do you choose $n_1,\ldots,n_k$. What is the largest possible $N_k$ ?

Examples:

$k=1$, nothing much interesting, $N_1=1$
$k=2$, then $(1,3)$ yields $N_2=4$
$k=3$, then $(2,3,10)$ yields $N_3=17$. Optimal ?

Edit about the rules. Parentheses are allowed (and useful). Division $a/b$ is possible only when $b$ divides $a$ in the usual sense of integers. You may have negative integers, but it does not help.

Answer by Jeremy Kahn for Optimal Countdown

2011-04-08T20:13:02Z

For convenience, we write $(a_1, \ldots, a_k) \le (b_1, \ldots, b_k)$ when $a_i \le b_i$ for each $i$. When $k = 3$, the solution $(2, 3, 10)$ is optimal among $(n_1, n_2, n_3) \le (10, 20, 100)$. For $k = 4$, you can make $1 \ldots 79$ with $(2, 3, 5, 33)$. This is optimal for $(n_1, n_2, n_3, n_4) \le (2, 4, 6, 50)$. These results were obtained with a perl script I wrote that you can find at www.math.sunysb.edu/~kahn/countdown. The last result, for example, was obtained by running

countdown 2 4 6 50

and took 7 minutes to run on my MacBook Pro.

Answer by Jeremy Kahn for Optimal Countdown

2011-04-12T04:15:41Z

We can prove that $\log N_k \sim k \log k$ as follows:

If we want to combine a set of $k$ numbers using the four arithmetic operations, we can think of inputting the numbers (in any order) along with the operations into an RPN calculator. There are $k!$ ways of ordering the numbers, $C_{k-1} = \frac1{k}{2k-2 \choose k-1}$ ways of choosing places to insert the arithmetic operations (without running out of numbers on the stack) and $4^{k-1}$ ways of choosing which of the four operations we will insert at each place, for a grand total of $4^{k-1}\frac{(2k-2)!}{(k-1)!}$ ways of combining $k$ numbers with the four operations. If we are given $k$ numbers and we can work with any subset of them (as in the original formulation of $N_k$), then there are $$ \sum_{i=1}^k {k \choose i} 4^{i-1}\frac{(2i-2)!}{(i-1)!} = \sum_{i=1}^k 4^{i-1} C_{i-1} \frac{k!}{(k-i)!} \le 16^k k! \le (16k)^k $$ ways of choosing a subset and then arranging and combining the elements of the subset with the arithmetic operations. Hence $\log N_k \le k(\log k + \log 16)$.

The lower bound is a little bit more interesting. Just by using addition and multiplication, we can prove that $N_{b+r-2} \ge b^r - 1$: We take as our $b + r - 2$ numbers $2, 3, \ldots b-1, 1, b, \ldots b^{r-1}$ (of course we are assuming that $b \ge 2$). Then we can write any positive integer $n < b^r$ as $\sum_{i=0}^{r-1} a_i b^i$, with $0 \le a_i \le b-1$, and then, by collecting the terms with a given "digit" $a_i$, we can write $n$ as a sum of terms of the form $a(b^{i_{a1}} + \ldots + b^{i_{aj_a}})$, where each $a$, $0 \le a \le b-1$, appears at most once. Of course, we can throw out the term with $a=0$, and not write the 1 when $a=1$, so we can write our number with $2, 3, \ldots, b-1, 1, b, \ldots, b^{r-1}$.

If we allow subtraction as well we can use Francois's idea (and the same set of numbers) to show that $N_{b+r-2} \ge ((2b - 1) ^ r - 1)/2$ when $b \ge 2, r \ge 1$.

Even with only addition and multiplication, we obtain (roughly) $N_k \ge (\epsilon k)^{(1-\epsilon) k}$ for $k$ large given $\epsilon > 0$, and hence $\log N_k \ge (1-\epsilon) k \log k$ when $k$ is large given $\epsilon$. So $\log N_k \sim k \log k$.

The next question to ask is whether $N_k^{1/k}/k$ has a limit, and if so, what is is. We have proven that $\limsup N_k^{1/k}/k \le 16$, but we have not even proven that $\liminf N_k^{1/k}/k > -\infty$.

Answer by François Brunault for Optimal Countdown

2011-04-12T21:37:54Z

Gilles Bannay informed me of the following results he has found :

For $k=4$, the solution $(2,3,14,60)$ is optimal for $(n_1,n_2,n_3,n_4) \leq (4,8,80,80)$.
For $k=5$, the solution $(2,3,4,63,152)$ gives all numbers up to $450$.
For $k=6$, the solution $(2,3,3,11,136,180)$ gives all numbers up to $2003$.
Using the original rules from the French TV game, the $6$-tuple $(1,2,3,4,10,100)$ gives all numbers up to $1281$ (which answers my question in a comment).

He obtained these results using his program CEB, which can be downloaded here (the page is in English and contains a detailed explanation of all the options). He has added an option in order to search for the best $k$-tuples. For example, the result 1. above was found by typing :

> CEB -g -b1 -e10000 -a4 4 8 80 80

Answer by Gilles Bannay for Optimal Countdown

2011-04-27T19:17:42Z

The last results I got using my program CEB are: - For k=5, the best solution $(n_1,n_2,n_3,n_4,n_5)$ ≤ (200,200,200,200,200) is (2,3,4,63,152) and we can get all numbers up to $N_5$=450. - For k=6, the best solution $(n_1,n_2,n_3,n_4,n_5,n_6)$ ≤ (10,20,30,40,50,80) is (2,3,24,37,47,66) and we can get all numbers up to $N_6$ = 3398.