14
$\begingroup$

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.

$\endgroup$
14
  • $\begingroup$ 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. $\endgroup$ Apr 8, 2011 at 10:33
  • $\begingroup$ 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] $\endgroup$
    – user9072
    Apr 8, 2011 at 11:24
  • 1
    $\begingroup$ 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$ ? $\endgroup$ Apr 8, 2011 at 19:15
  • 2
    $\begingroup$ 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. $\endgroup$ Apr 8, 2011 at 20:29
  • 1
    $\begingroup$ 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). $\endgroup$ Apr 9, 2011 at 0:49

4 Answers 4

9
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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.) $\endgroup$ Apr 12, 2011 at 17:36
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 14, 2011 at 0:31
  • $\begingroup$ @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. $\endgroup$ Apr 14, 2011 at 11:20
7
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – user11235
    Apr 8, 2011 at 20:39
  • $\begingroup$ (2,3,15,37) gives 84 $\endgroup$
    – user11235
    Apr 9, 2011 at 11:05
  • 1
    $\begingroup$ (2, 3, 14, 60) gives 86. This is optimal for $(n_1, n_2, n_3, n_4) \le (5, 10, 20, 100)$. $\endgroup$ Apr 9, 2011 at 23:20
  • 4
    $\begingroup$ Up to $k=4$ the best known solutions seem to form a chain : (2,3), (2,3,14) and (2,3,14,60)... $\endgroup$ Apr 11, 2011 at 16:54
5
$\begingroup$

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.

$\endgroup$
0
2
$\begingroup$

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
$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$ Apr 13, 2011 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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