User kakia - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T19:07:07Z http://mathoverflow.net/feeds/user/30484 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/129209/number-of-configurations-in-the-optimal-hanoi-tower Number of Configurations in the optimal Hanoi tower kakia 2013-04-30T11:54:49Z 2013-05-02T21:25:16Z <p>There is a unique strategy how to move \$n\$ disks from the first rod to the second optimally and it takes \$2^n-1\$ steps, solution is obtained by simple recursion. I am interested into the following question, how many times during this strategy we have \$a\$ disks on the first rod, \$b\$ disks on the second and \$c\$ disks on the third. We can solve this question using dynamic programming and recursive relation for the optimal strategy, the recurrent formula is the following: </p> <p>\$dp[a][b][c][n]=dp[a-1][c][b][n-1]+dp[c][b-1][a][n-1]\$. </p> <p>If we consider \$n=3k\$ and \$a=b=c=k\$, \$dp[k][k][k][3k]\$ matches the following sequence (\$a_k\$ is number of ways to arrange \$k\$ blue, \$k\$ red and \$k\$ green balls so that the first one is fixed and no pair of adjacent balls are of the same color, first and last are also considered adjacent):</p> <p><a href="http://oeis.org/search?q=2%2c8%2c44%2c268%2c1732" rel="nofollow">http://oeis.org/search?q=2%2c8%2c44%2c268%2c1732</a></p> <p>on the first 20 numbers, which makes me believe they are the same, though up to now I was unable to prove equivalence of these two sequences. Note that if we take different number of different color balls, the number of arranging them with the same conditions does not match with the number of respective configurations. </p> <p><a href="http://oeis.org/A197657" rel="nofollow">http://oeis.org/A197657</a></p> <p>this sequence was suggested in the comments, each number \$a_k\$ is half of the number in our sequence. </p> <p>Is it just a coincidence or is there any nice way to show the equivalence? Reduction of the original question on any of these two would give a linear time algorithm to find the number of configurations. </p> http://mathoverflow.net/questions/118357/computational-complexity computational complexity kakia 2013-01-08T13:13:53Z 2013-01-11T14:17:11Z <p>I am interested into computational complexity of decision problem: Does a given 2-dimensional simplicial complex contain (any)triangulation of 2-sphere? This problem trivially lies into NP, because certificate is the subset of triangles. I think that it is NP-complete. </p> http://mathoverflow.net/questions/129209/number-of-configurations-in-the-optimal-hanoi-tower Comment by kakia kakia 2013-05-02T13:42:56Z 2013-05-02T13:42:56Z Well, I see these connections can be arbitrary and there might be no nice way to show the equivalence. I just wanted to have a closed formula for Hanoi tower configurations, from the computational perspective, formulas I see with the equal sequences can be calculated in linear time with respect to \$n\$, whilst recurrent formula for Hanoi configurations takes cubic time. http://mathoverflow.net/questions/118357/computational-complexity Comment by kakia kakia 2013-01-08T22:34:36Z 2013-01-08T22:34:36Z I agree with connected components and retraction of boundary, but after these operations we are still dealing with quite arbitrary structure. We can even make things &quot;easier&quot; and assume that every edge is incident with at most 3 triangles by simple topological transformation. If we consider dual problem, take 1 vertex in each triangle and connect two vertices if their respective triangles share edges, we get: in somewhat special graph we need to find cubic planar 3-connected subgraph(corresponding to triangulation). Finding cubic subgraph in planar graph is NP-complete. I see some connection. http://mathoverflow.net/questions/118357/computational-complexity Comment by kakia kakia 2013-01-08T15:32:41Z 2013-01-08T15:32:41Z If we are given set of triangles as a certificate, first we will check connectivity, afterwards we check that the link of each vertex is a cycle. If these conditions are satisfied, we know for sure that we have a closed surface. Then calculate Euler characteristic, we are dealing with sphere if and only if Euler characteristic is 2. <a href="http://en.wikipedia.org/wiki/Surface#Classification_of_closed_surfaces" rel="nofollow">en.wikipedia.org/wiki/&hellip;</a> here you can check what are the Euler characteristics of closed surfaces.