[Computational Complexity] More on the Tables Problem
- Recall the tables problem, which I now state more clearly than I did in my last post:
n couples go to a resturant. They will sit at a rectangular table that has room for n on each side. Each person sits either next to across from their darling. How many ways can they sit?Most people got the correct answer in the comments on my last blog. But some other interesting points were raised that I will address.
- I had commented that this was asked on the 2007 Maryland High School Math Olympiad, Part I,, problem 23, which is with Multiple Choice, for the case of n=5. Some commenter wanted to know what the choices were: 360, 768, 5040, 19200, 30720.
Someone commented that the problem `was not new'
and gave this, problem 4,
as a pointer to where it had been asked before.
Here is the problem they were referring to:
Define a domino to be a 1x2 rectangle. In how many ways can a nx2 rectangle be tiled by dominos?This raises an interesting question: When are two problems equivalent? Does phrasing matter (I had people, they have dominos)? Does making certain things distinguiable or not matter (Dominos are not distinguiable, couples are)? Does having different answers matter (his is Fib(n+1) mine is a Fib(n+1) x 2^n x n!)? More generally, its not clear when a problem is new.
- Just to reiterate- there is math all around you if you know where to look.
Posted By GASARCH to Computational Complexity at 11/15/2007 11:27:00 AM