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.
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.
(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.
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 :)
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
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
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.
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.