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

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.

share|improve this question
    
I don't think the description is right. How do you realize 1,2,3,4 from (1,3)? Since you can employ each number only once, you cannot realize more than two targets. –  Emil Jeřábek Apr 8 '11 at 10:33
    
Regarding the preceeding comment: why not more than two? 3-1=2, 3+1=4, 3*1=3; and also just 3 and 1 (if I understand correctly) But, I have to agree, I do not quite understand the question either: a. does one have parenthesis avalailable, e.g., is (a+b)c admissible (as I saw this game once very briefly I believe so). b. are intermediate results allowed to be negative and/or rational. c. related to b. how is division to be interpreted, say is 7/3 , just the rational, or inadmissible, or maybe 2. [I deleted an earlier comment, almost identical, as I asked something that is actually specified] –  quid Apr 8 '11 at 11:24
1  
Here is a related (maybe easier) question : fix an integer $k$ and assume $n_1=\ldots=n_k=1$. What is the smallest natural integer $N'_k$ which cannot be obtained from the $n_i$ using the above rules ? Obviously one has $N'_k - 1 \leq N_k$, but of course $N_k$ is likely to grow much faster than $N'_k$. Are there interesting lower/upper bounds on $N'_k$ ? –  François Brunault Apr 8 '11 at 19:15
2  
Francois: the example I know is making 24 out of 3,8,3,8 (and you have to use all four numbers). For this one you provably need to leave the world of integers. –  Kevin Buzzard Apr 8 '11 at 20:29
1  
Taking $n_i=3^{i-1}$ for $1 \leq i \leq k$ yields the lower bound $N_k \geq (3^k-1)/2$ (since every integer $N \leq (3^k-1)/2$ is a weighted sum of powers of 3). However, I have the impression that the actual growth rate of $N_k$ is much faster (and I don't know how to find an upper bound). –  François Brunault Apr 9 '11 at 0:49
show 9 more comments

4 Answers

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$.

share|improve this answer
    
Very nice lower bound ! Could you explain in more detail the argument with the Catalan number for the upper bound ? (I had found the crude upper bound $N_k = O(2^k (k!)^2)$, but maybe I wasn't careful enough.) –  François Brunault Apr 12 '11 at 17:36
1  
For example, with the numbers 1, 2, 3, and 4, in order, and the operation *, there are five ways that we can enter them into an RPN calculator: 1 2 * 3 * 4 *, 1 2 3 * * 4 *, 1 2 * 3 4 * *, 1 2 3 * 4 * *, and 1 2 3 4 * * *. In general, there must always be more numbers inputted into the calculator than there are operations applied: this condition is what gives us the Catalan numbers. –  Jeremy Kahn Apr 14 '11 at 0:31
    
@Jeremy Kahn: Thanks for the detailed explanation. In fact I used a different argument, but now I realize that your method gives a better upper bound. –  François Brunault Apr 14 '11 at 11:20
add comment

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.

share|improve this answer
1  
It may be worth noting that these numbers are not unique. For example, (2,3,10), (2,3,14), (2,6,11) and (2,6,13) all give 17. –  user11235 Apr 8 '11 at 20:39
    
(2,3,15,37) gives 84 –  user11235 Apr 9 '11 at 11:05
1  
(2, 3, 14, 60) gives 86. This is optimal for $(n_1, n_2, n_3, n_4) \le (5, 10, 20, 100)$. –  Jeremy Kahn Apr 9 '11 at 23:20
3  
Up to $k=4$ the best known solutions seem to form a chain : (2,3), (2,3,14) and (2,3,14,60)... –  François Brunault Apr 11 '11 at 16:54
add comment

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.

share|improve this answer
add comment

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

  1. 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)$.
  2. For $k=5$, the solution $(2,3,4,63,152)$ gives all numbers up to $450$.
  3. For $k=6$, the solution $(2,3,3,11,136,180)$ gives all numbers up to $2003$.
  4. 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
share|improve this answer
    
Using Gilles Bannay's program, it took only approximately 3 minutes (!) to test all $6$-tuples $(n_1,\ldots,n_6)$ with $n_i \in \{1,2,3,4,5,6,7,8,9,10,25,50,75,100\}$. The best $6$-tuple is $(2,3,5,8,9,100)$, for which $N_6=1912$. –  François Brunault Apr 13 '11 at 14:37
add comment

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.