tag:blogger.com,1999:blog-3722233.post1803801999677267283..comments2024-02-27T04:34:15.078-06:00Comments on Computational Complexity: More on the Tables ProblemLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3722233.post-63578673994825141152007-11-19T20:52:00.000-06:002007-11-19T20:52:00.000-06:00When I read the problem statement, I immediately s...When I read the problem statement, I immediately stopped reading the rest, not to be spoiled by seeing the answer (after all this I've looked of course).<BR/><BR/>But my first reading didn't give the same problem as that expected to give the usual Fibonacci recurrence. I read it as 'n couples sit at a rectangular table, n on a side' where I visualized the rectangle as a -square-, n on a side. <BR/><BR/>(the extra 'no one sitting on the ends' in the first post removes my perfectly allowable but silly intepretation).<BR/><BR/>But now what is this new sequence? number of ways for n couples to sit next or across at a square table n on a side...I can't come up with an obvious recurrence.<BR/><BR/>And what is easier: couples can be 'next to' each other at the corners or not?Mitchhttps://www.blogger.com/profile/06352106235527027461noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89548707454455625442007-11-19T02:54:00.000-06:002007-11-19T02:54:00.000-06:00The reason that your problem and the domino proble...The reason that your problem and the domino problem have different answers is that the answerer of the domino question treated the dominos like they were symmetric and interchangeable. If you assume they are all unique and asymmetric the answers become the same.<BR/><BR/>Yet another statement of the problem (the interchangeable symmetric version) is: given a graph with 2n nodes, where the nodes are comprised of pairs that have edges between them, pairs are connected in series with a single edge from each node in a pair going to different nodes in the next pair. How many ways can the graph be partitioned into n graphs each consisting of 2 nodes and 1 edge?<BR/><BR/>With the asymmetric non-interchangeable version being given those partitions how many ways can you add 2n-2 edges to get a graph the the 'shape' of the original graph?<BR/><BR/>I wonder if your question had asked about how many ways can the couples be seated, instead of how many ways the people can be seated if the answer would still be considered by most to be the same. I also wonder how many people when faced with the domino question said there wasn't enough information because there could be duplicates, or symmetric dominos, or otherwise stated some assumption about the distribution of the symbols of the n dominos.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2754866722596311782007-11-18T21:10:00.000-06:002007-11-18T21:10:00.000-06:00Guys, I defer to your superior wisdom, I'm just an...Guys, I defer to your superior wisdom, I'm just an amateur, but after maniacally scrutinizing my work to make sure I avoided duplication I still get 49,920 different arrangements. I divided the problem into three categories.1)When all couples are seated opposite their partners. 5!x2^5=3840 arrangements. 2)When three couples are seated opposite, and one couple on each side is seated next to their partner. 3!x2^3x2^3x4x10=15,360 arrangements. 3)When 2 couples on each side are seated next to their partner, and one couple is seated opposite. 2^7x2^4x3x5=30,720. 3840+15,360+30,720=49,920. Who has to utter the "oops"? Me or you guys? roger the whippersnapperAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19197565373361539562007-11-15T20:07:00.000-06:002007-11-15T20:07:00.000-06:00Can you guys help me understand how you get from T...<I>Can you guys help me understand how you get from T(n) = 2nT(n-1) + 4n(n-1)T(n-2) to the closed form expression?</I><BR/><BR/>Don't use that recurrence. First solve the 2x1 domino layout problem and then notice that there are 2^n n! solutions for every domino layout.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38487479958472324802007-11-15T15:46:00.000-06:002007-11-15T15:46:00.000-06:00The domino analogy makes a lot of sense. The probl...The domino analogy makes a lot of sense. The problem is greatly simplified by thinking about problem in this way, and the domino connection to Fibonacci numbers is discussed in detail by Arthur Benjamin (http://www.math.hmc.edu/~benjamin/).<BR/><BR/>In the indistinguishable domino case, taking one side of the table completely determines the problem.<BR/><BR/>Then by introducing some distinguishing characteristic to the dominoes (color for instance) the problem may be solved relatively quickly.<BR/><BR/>As to harrison brown's definition of equivalence (and he may have meant it this way), the reduction should be able to go in both directions in order to preserve symmetry in the relation.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53037837201640838602007-11-15T14:18:00.000-06:002007-11-15T14:18:00.000-06:00I'd say two problems are equivalent if, given a so...<I>I'd say two problems are equivalent if, given a solution to one, it becomes trivial to find the answer to the other.</I><BR/><BR/>Sounds like a need for some form of reducibility...can you be more specific?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60958544345464965402007-11-15T14:17:00.000-06:002007-11-15T14:17:00.000-06:00Can you guys help me understand how you get from T...Can you guys help me understand how you get from T(n) = 2nT(n-1) + 4n(n-1)T(n-2) to the closed form expression? This is just standard recurrence relation solution knowledge that I'm missing?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75934907962279741292007-11-15T13:42:00.000-06:002007-11-15T13:42:00.000-06:00On "new" problems:Having written mathematical comp...On "new" problems:<BR/><BR/>Having written mathematical competitions before, very rarely are problems for those "new" in almost any sense. Even when you're trying as hard as possible to make them new, chances are someone's thought of them already.<BR/><BR/>My $0.02 on that subject: I'd say two problems are equivalent if, given a solution to one, it becomes trivial to find the answer to the other.Johnhttps://www.blogger.com/profile/18079824074256670713noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70883532369408442262007-11-15T13:18:00.000-06:002007-11-15T13:18:00.000-06:00Not sure about "new", but in some sense if 2 probl...Not sure about "new", but in some sense if 2 problems have the same answer, and a similar logical path to a solution, then they are equivalent.<BR/><BR/>One interpretation of "new" could mean, "I took a known problem and obsfucated it so at casual glance, one can't see they have the same answer." I would apply this to puzzle type problems, as opposed to things like Fermats TheoremAnonymousnoreply@blogger.com