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.
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.
ReplyDeleteOne 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 Theorem
On "new" problems:
ReplyDeleteHaving 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.
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.
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?
ReplyDeleteI'd say two problems are equivalent if, given a solution to one, it becomes trivial to find the answer to the other.
ReplyDeleteSounds like a need for some form of reducibility...can you be more specific?
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/).
ReplyDeleteIn the indistinguishable domino case, taking one side of the table completely determines the problem.
Then by introducing some distinguishing characteristic to the dominoes (color for instance) the problem may be solved relatively quickly.
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.
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?
ReplyDeleteDon'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.
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 whippersnapper
ReplyDeleteThe 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.
ReplyDeleteYet 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?
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?
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.
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).
ReplyDeleteBut 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.
(the extra 'no one sitting on the ends' in the first post removes my perfectly allowable but silly intepretation).
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.
And what is easier: couples can be 'next to' each other at the corners or not?