Re:The Mathematics of 2048: Counting States by Exhaustive En...
by maweki on Monday December 11, 2017 @02:51AM
(#15895706)
This is neat. I wonder whether there is a faster approach using binary decision diagrams or a variant thereof. If the state transition were represented by a binary function, BDDs could allow for counting states without actually enumerating. The question would be, how to actually find all the fixed points of that function.
Re:The Mathematics of 2048: Counting States by Exhaustive En...
by ballenf on Monday December 11, 2017 @09:49AM
(#15897271)
I'd also think that working backwards from all possible winning states would offer some insight and potential for speed. At the expense of being somewhat more difficult (at first glance anyway) to ascertain validity of the predecessor state.
Re:The Mathematics of 2048: Counting States by Exhaustive En...
by jdleesmiller on Monday December 11, 2017 @01:48PM
(#15899254)
(Author here.) That would indeed be interesting, thanks --- I don't think it's trivial to generate all of the possible predecessor states, but it seems like it should be possible. One to think about.
Re:The Mathematics of 2048: Counting States by Exhaustive En...
by Al-Khwarizmi on Monday December 11, 2017 @01:40AM
(#15895519)
Me too. I kind of expected a dystopian article where people in 2048 are so badly educated that the most advanced math they can do is count U.S. states one by one!
Kind of disappointed it's not that, to be honest :)
Re:The Mathematics of 2048: Counting States by Exhaustive En...
by tomahunt on Monday December 11, 2017 @01:49AM
(#15895552)
I was expecting a maths where quantum computation had taken over analytic number theory and theorems could be proved using brute force enumeration.Or something
Re:The Mathematics of 2048: Counting States by Exhaustive En...
by whatshisface on Monday December 11, 2017 @08:13AM
(#15896807)
If you take just one piece of information from this blog:
Quantum computers would not solve hard search problems
instantaneously by simply trying all the possible solutions at once
Re:The Mathematics of 2048: Counting States by Exhaustive En...
by jameshart on Monday December 11, 2017 @08:19AM
(#15896828)
First, capture, tag, and release a number of US senators. 15 or so should work. Then, reset your traps and capture some more. Count how many of the second capture set were tagged in the first group. This tells you what proportion of the population of Senators you captured the first time, and by dividing the number of senators you tagged by this proportion you can estimate the total population of senators. Divide that number by two to obtain the number of states.
Re:The Mathematics of 2048: Counting States by Exhaustive En...
by jameshart on Monday December 11, 2017 @08:45AM
(#15896964)
Knowing that a bijection exists between states and stars on the US flag, first obtain a US flag. Observe that the stars in the top left corner fall in a rectangular n x m grid with stars located at every node, and also in the rows and columns in between, forming a smaller (n-1) x (m-1) rectangle, so the number of stars is nm + (n-1)(m-1). Then you can just count n and m - 6 and 5 respectively - and substitute to obtain 30+20=50 stars.
I got this from here - https://puzzling.stackexchange.com/questions/48/what-is-the-...
https://www.cs.carleton.ca/sites/default/files/tr/TR-04-10.p...
Warning-free URL: https://service.scs.carleton.ca/sites/default/files/tr/TR-04...
Kind of disappointed it's not that, to be honest :)
(The subtitle of Aaronson's blog.)
https://www.scottaaronson.com/blog/