Timeline for Mathematics of the 24 game
Current License: CC BY-SA 2.5
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 1, 2010 at 7:19 | comment | added | Jeremy H | @Kevin: I agree. That's what I meant by "barring obvious cases". @Tony: Thinking about the complexity is what lead to this question. I'm hoping that a polynomial-time algorithm could handle all but a sparse set, and then by Mahaney's Theorem we could argue that it is not NPC. | |
| Jul 31, 2010 at 1:34 | comment | added | JBL | 3, 3, 7, 7 is a good one along the lines of 3, 3, 8, 8; I'm partial to 1, 2, 7, 7, myself. | |
| Jul 31, 2010 at 0:45 | comment | added | Tony Huynh | @Noah: but 2(10-3)+10=24 | |
| Jul 30, 2010 at 23:19 | comment | added | Noah Snyder | I like 2,3,10,10 allowing exponents. | |
| Jul 30, 2010 at 23:14 | comment | added | Micah Milinovich | 5,5,5,1 is a similar example. | |
| Jul 30, 2010 at 22:54 | comment | added | Kevin Buzzard | @Tony: I like 1,3,4,6 (which I had not seen before) but I take your point :-) | |
| Jul 30, 2010 at 22:17 | answer | added | Steven Stadnicki | timeline score: 3 | |
| Jul 30, 2010 at 21:56 | comment | added | Tony Huynh | It also seems natural to ask if we can decide whether an instance is solvable in polynomial-time. I'd guess that the problem is NP-hard. | |
| Jul 30, 2010 at 21:41 | comment | added | Tony Huynh | @Kevin: I can't decide if I like 8,3,8,3 better than 1,3,4,6. There's more room to go wrong with 1,3,4,6 since the numbers are distinct. On the other hand, improper fractions are just downright diabolical. | |
| Jul 30, 2010 at 20:40 | comment | added | George Lowther | Do you have to use all the numbers? That makes it trickier | |
| Jul 30, 2010 at 20:37 | comment | added | George Lowther | Ah, Countdown, that brings back memories. Carol Vorderman could normally do this for n=6 and t < 1000, but not always. | |
| Jul 30, 2010 at 19:42 | comment | added | Kevin Buzzard | 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$. | |
| Jul 30, 2010 at 19:22 | comment | added | Eric Tressler | 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. | |
| Jul 30, 2010 at 19:17 | history | asked | Jeremy H | CC BY-SA 2.5 |