Optimal Countdown - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T05:40:20Z http://mathoverflow.net/feeds/question/61034 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/61034/optimal-countdown Optimal Countdown Denis Serre 2011-04-08T08:44:02Z 2011-05-08T10:27:07Z <p>Many know the TV game <em>Countdown</em>, whose French version <em>Des chiffres et des lettres</em> has lasted since 1965.</p> <p>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$.</p> <p>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$ ?</p> <p>Examples:</p> <ul> <li>$k=1$, nothing much interesting, $N_1=1$</li> <li>$k=2$, then $(1,3)$ yields $N_2=4$</li> <li>$k=3$, then $(2,3,10)$ yields $N_3=17$. Optimal ?</li> </ul> <p><em>Edit</em> 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.</p> http://mathoverflow.net/questions/61034/optimal-countdown/61095#61095 Answer by Jeremy Kahn for Optimal Countdown Jeremy Kahn 2011-04-08T20:13:02Z 2011-04-08T20:13:02Z <p>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 </p> <p>countdown 2 4 6 50</p> <p>and took 7 minutes to run on my MacBook Pro. </p> http://mathoverflow.net/questions/61034/optimal-countdown/61362#61362 Answer by Jeremy Kahn for Optimal Countdown Jeremy Kahn 2011-04-12T04:15:41Z 2011-04-12T04:15:41Z <p>We can prove that $\log N_k \sim k \log k$ as follows:</p> <p>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)$. </p> <p>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 &lt; 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}$. </p> <p>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$. </p> <p>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$.</p> <p>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$. </p> http://mathoverflow.net/questions/61034/optimal-countdown/61475#61475 Answer by François Brunault for Optimal Countdown François Brunault 2011-04-12T21:37:54Z 2011-04-12T21:43:17Z <p>Gilles Bannay informed me of the following results he has found :</p> <ol> <li>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)$.</li> <li>For $k=5$, the solution $(2,3,4,63,152)$ gives all numbers up to $450$.</li> <li>For $k=6$, the solution $(2,3,3,11,136,180)$ gives all numbers up to $2003$.</li> <li>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).</li> </ol> <p>He obtained these results using his program <em>CEB</em>, which can be downloaded <a href="http://gilles.bannay.free.fr/wordpress/jeux_us.html" rel="nofollow">here</a> (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 :</p> <pre><code>&gt; CEB -g -b1 -e10000 -a4 4 8 80 80 </code></pre> http://mathoverflow.net/questions/61034/optimal-countdown/63215#63215 Answer by Gilles Bannay for Optimal Countdown Gilles Bannay 2011-04-27T19:17:42Z 2011-05-08T10:27:07Z <p>The last results I got using my program <a href="http://gilles.bannay.free.fr/wordpress/jeux_us.html" rel="nofollow"><em>CEB</em></a> 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.</p>