Here is one that inspired a problem that ended up on the Maryland Math Olympiad, Part I (which is 25 multiple choices questions). (5 choices, 4 points for a correct answer, 2 points for a wrong answer. You really really do not want to guess.)
Here is what happened: I went to dinner with my darling, and my two sister-in-laws and their husbands. I sat across from my darling but the other couples sat next to each other. So here is the question: I immediately thought about the following question:
$n$ couples go to dinner. They sit at a rectangular table, but nobody sits at the ends. Each couple either sits ACROSS FROM or NEXT TO their darling. How many ways can they be seated?The problem on the exam was asked for 5 couples and gave choices.
Its not a hard problem for the readers of this blog, so I leave it to my commenters to solve it. (If nobody does I'll post the solution later.) Note that it would be hard for a high school student- very few got it correct. (We suspected this would be the case. We try to order the questions by difficulty and this was question 23.)
Is it f(n) = 2*n*f(n-1) + 4*n*(n-1)*f(n-2) ,where f(0) = 1 and f(1) = 2; and n being the number of couples?
ReplyDeleteAn even number of couples must be sitting across from each other, otherwise there would have to be a remaining couple unable to sit next to each other.
ReplyDeleteSuppose exactly k couples sit next to each other.
There are (n choose k) = n! / (k! * (n-k)!) ways to choose the "x-coordinates": how far from the end of the table each couple is.
Within those k couples sitting across from each other, there are k! possible orderings of the couples, and for each such ordering, 2^k different choices for which half of the couple is to the north.
Within those n - k couples sitting next to each other, there are (n-k)! possible orderings of the couples, and for each such ordering, 2^(n-k) different choices for which half of the couple is to the west.
Therefore, for exactly k couples, there are n! / (k! * (n-k)!) * k! * 2^k * (n-k)! * 2^(n-k) = 2^n * n! different orderings. Summing over all even k from 0 to n, the total number of orderings is n! * 2^n * (n/2).
# perfect matchings in the ladder graph (L_n = P_2 x P_n) * n! * 2^n
ReplyDelete= F(n+1) * n! * 2^n
where F(n) is the nth Fib. number
Maybe.
First we may decide from left to right for the chairs at the table how they are put together in pairs. The two leftmost chair
ReplyDeleteare reserved for a couple sitting across or the four leftmost chairs are reserved for two couples both sitting next to each other. Then it remains to decide on the pairing of 2(n-1) chairs or 2(n-2) chairs. This yields the recursion for the number of different pairings P(n) = P(n-1) + P(n-2), the recursion for Fibonacci numbers but with P(1) = 1 and P(2) = 2.
Next we decide how to put n couples to n pairs of chairs. There are n! possibilities.
Now there remain for each of the n couples 2 possible seating.
So we get
2^n x n! x F(n+1) (where F(n) stands for the nth Fibonacci number).
This is the same result as in comment #1 and #3.
I guess the problem is slightly ambiguous. We've all assumed it's a table with exactly $n$ chairs on each side (i.e, the seatings are maximally "compact"), but what if it's an infinitely long table and there can be solutions like "everyone sits on the same side of the table" (but still assume the seatings induce a conneted graph)?
ReplyDelete40
ReplyDeleteI do agree that the problem is a bit ambiguous.
ReplyDeleteSuppose there's only one couple, Alice and Bob. There are initially two choices: either they sit next to each other or across.
However, suppose the ordering of how they're sitting is taken into account. So now there are two choices if they're sitting across or if they're sitting next to each other.
Now suppose the location of where they're sitting on the table is taken into account. Assume the ends of the table point east and west and the table has four chairs, two chairs on the north side and two on the south. Now there are two choices if they're sitting across or next to each other.
The last assumption makes the problem complicated when trying to count the orderings of all the couples. The size of the table also comes into play here.
Ignoring this last assumption and assuming the table is big enough and that all the couples sit on the south side when they're next to each other, then there are n!*4^n possible seating arrangements. (n! orderings of the couples and 4 ways of sitting (2 for each of ACROSS and NEXT TO)).
For n couples, isn't it just the nth Fib number?
ReplyDeleteFib(n+1)* n! * 2^n is right.
ReplyDeletebut that's basically not a new problem.
There are Fib(n+1) ways in which the couples can be arranged. There are n! different ways to assign the couples to the seating positions. And there are 2^n different ways to assign the partners to their respective seats.
ReplyDeleteSo I agree w/ Martin (and others):
Fib(n+1) * n! * 2^n
Thus for five couples there are a mere 30,720 seating positions.
Now, let's say these couples are all swingers....
Eric
I believe the answer for 5 couples is 2*5!*8.
ReplyDeletethere are 8 ways of arranging the couple-slots around a 10-person table, and you multiply that by the permutation of couples, and the permutation of people within a couple.
so, 2*n!*(#ways to arrange the couples around a table)
oops, mistake in my analysis, but you guys are definitely right.
ReplyDeleteF(n+1)*n!*2^n
Isnt this a problem of combinatorics? assuming n to be even number,
ReplyDelete1. For case where no couples sitting next to each other (all across): 2n!
2. for k couples sitting next to each other and therefore n-2k couples sitting across from one another: (This can only be valid for k = 1 to (n/2 - 1) above which all must sit next to each other)
2(n/2 choose k) = # comb's of couples sitting next to each other;
2k! = # comb's of couples sitting next to each other on other side of the table
2(n-2k)!= # comb's of remaining couples sitting across from each other.
So, multiply the three together and sum them from k = 1 to (n/2 - 1)
3. For case where all couples sit next to each other: 2n!
Finally, add parts 1, 2 and 3 for answer.
2n! + 2n! + SUM(2(n/2 C k)(2k!)2(n-2k)!)
The final summation is over k=1 to n/2 - 1
1) I meant that the
ReplyDeletetwo diff sides of the
table have n seats each.
2) One of the Anon said
the problem was not new.
A good Olympaid problem
does not have to be new,
it just needs to be
not-well-known.
I'm not surprised or even
disappointed that it is
not new-- I'm not publishing it or anything
of the sort-- however,
could you please supply
a reference?
http://mathcircle.berkeley.edu/original/Combinatorics1.pdf
ReplyDeleteExercise 4
It's the same but the couples are indistinguishable and so are the the two persons within the couple.
The "fibonacci trick" is relatively well known among the upper tiers of math competitors. Recognizing that this is equivalent to it is slightly nontrivial, and I missed the 2^n factor.
ReplyDeleteStill, nice problem.
Sorry for the digression, did anybody notice this paper claiming that Graph Isomorphism is in P. I haven't read the paper yet. I don't know how reliable arxiv is (or) if this paper is reviewed !!
ReplyDeleteShiva,
ReplyDeleteI looked at the Graph Isomorphism paper. It's poorly written and hard to follow, and there seem to be some elementary math errors. I seriously doubt it's correct.
I missed 2^n too. (Must remember that it is noticeable when individuals switch positions in a couple.)
ReplyDeleteNice problem. I didn't know before that \sum_m {C-m \choose m} is F_{C+1}. (The sum is how I counted ways of writing C as a sum of 1 and 2.)
Since its multiple choice, the difficulty really lies in what choices you gave. For instance, you can immediately rule out any number less than 5!=120. You can also rule out any number greater than 10! A highschool student should at least be able to do this. What possible answers did you give?
ReplyDeleteI didn't know before that \sum_m {C-m \choose m} is F_{C+1}.
ReplyDeleteActually, that's exercise 1.2.8-16 in TAoCP, for which I found a solution in some old notes of mine. So I must have known that identity at some point.