tag:blogger.com,1999:blog-3722233.post7474713628728312297..comments2023-11-28T22:15:32.433-06:00Comments on Computational Complexity: Math Problems from everyday lifeLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger21125tag:blogger.com,1999:blog-3722233.post-45856413859826123972010-03-17T05:07:37.783-05:002010-03-17T05:07:37.783-05:00I didn't know before that \sum_m {C-m \choose ...<i>I didn't know before that \sum_m {C-m \choose m} is F_{C+1}.</i><br /><br />Actually, 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.rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88342739927432583972007-11-15T08:59:00.000-06:002007-11-15T08:59:00.000-06:00Since its multiple choice, the difficulty really l...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?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53685072651407951372007-11-15T05:07:00.000-06:002007-11-15T05:07:00.000-06:00I missed 2^n too. (Must remember that it is notice...I missed 2^n too. (Must remember that it is noticeable when individuals switch positions in a couple.)<BR/><BR/>Nice 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.)rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38836256188068632832007-11-14T23:56:00.000-06:002007-11-14T23:56:00.000-06:00Shiva,I looked at the Graph Isomorphism paper. It...Shiva,<BR/><BR/>I 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-815439051134314032007-11-14T22:47:00.000-06:002007-11-14T22:47:00.000-06:00Sorry for the digression, did anybody notice this ...Sorry for the digression, did anybody notice this <A HREF="http://arxiv.org/abs/0711.2010" REL="nofollow">paper</A> 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 !!Shiva Kintalihttps://www.blogger.com/profile/07853545928906483737noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39856964739622900772007-11-14T20:38:00.000-06:002007-11-14T20:38:00.000-06:00The "fibonacci trick" is relatively well known amo...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.<BR/><BR/>Still, nice problem.Johnhttps://www.blogger.com/profile/18079824074256670713noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65531487834461685702007-11-14T17:18:00.000-06:002007-11-14T17:18:00.000-06:00http://mathcircle.berkeley.edu/original/Combinator...http://mathcircle.berkeley.edu/original/Combinatorics1.pdf<BR/><BR/>Exercise 4<BR/><BR/>It's the same but the couples are indistinguishable and so are the the two persons within the couple.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76717903183379121542007-11-14T16:18:00.000-06:002007-11-14T16:18:00.000-06:001) I meant that thetwo diff sides of thetable have...1) I meant that the<BR/>two diff sides of the<BR/>table have n seats each.<BR/><BR/>2) One of the Anon said<BR/>the problem was not new.<BR/>A good Olympaid problem<BR/>does not have to be new,<BR/>it just needs to be <BR/>not-well-known.<BR/><BR/><BR/><BR/><BR/>I'm not surprised or even<BR/>disappointed that it is<BR/>not new-- I'm not publishing it or anything<BR/>of the sort-- however,<BR/>could you please supply<BR/>a reference?GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9301106628229529232007-11-14T15:32:00.000-06:002007-11-14T15:32:00.000-06:00Isnt this a problem of combinatorics? assuming n t...Isnt this a problem of combinatorics? assuming n to be even number,<BR/><BR/>1. For case where no couples sitting next to each other (all across): 2n!<BR/><BR/>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)<BR/><BR/>2(n/2 choose k) = # comb's of couples sitting next to each other;<BR/>2k! = # comb's of couples sitting next to each other on other side of the table<BR/>2(n-2k)!= # comb's of remaining couples sitting across from each other.<BR/>So, multiply the three together and sum them from k = 1 to (n/2 - 1)<BR/><BR/>3. For case where all couples sit next to each other: 2n!<BR/><BR/>Finally, add parts 1, 2 and 3 for answer.<BR/>2n! + 2n! + SUM(2(n/2 C k)(2k!)2(n-2k)!)<BR/><BR/>The final summation is over k=1 to n/2 - 1Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47828281927245726552007-11-14T15:13:00.000-06:002007-11-14T15:13:00.000-06:00oops, mistake in my analysis, but you guys are def...oops, mistake in my analysis, but you guys are definitely right.<BR/><BR/>F(n+1)*n!*2^nAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16141875198360264452007-11-14T15:09:00.000-06:002007-11-14T15:09:00.000-06:00I believe the answer for 5 couples is 2*5!*8.there...I believe the answer for 5 couples is 2*5!*8.<BR/><BR/>there 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.<BR/><BR/>so, 2*n!*(#ways to arrange the couples around a table)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55547356783794400462007-11-14T14:08:00.000-06:002007-11-14T14:08:00.000-06:00There are Fib(n+1) ways in which the couples can b...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.<BR/><BR/>So I agree w/ Martin (and others):<BR/><BR/>Fib(n+1) * n! * 2^n<BR/><BR/>Thus for five couples there are a mere 30,720 seating positions.<BR/><BR/>Now, let's say these couples are all swingers....<BR/><BR/>EricAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66870863955355773802007-11-14T13:27:00.000-06:002007-11-14T13:27:00.000-06:00Fib(n+1)* n! * 2^n is right.but that's basically ...Fib(n+1)* n! * 2^n is right.<BR/><BR/>but that's basically not a new problem.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27467926411167876502007-11-14T12:21:00.000-06:002007-11-14T12:21:00.000-06:00For n couples, isn't it just the nth Fib number?For n couples, isn't it just the nth Fib number?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70775945588357896042007-11-14T12:11:00.000-06:002007-11-14T12:11:00.000-06:00I do agree that the problem is a bit ambiguous. Su...I do agree that the problem is a bit ambiguous. <BR/><BR/>Suppose there's only one couple, Alice and Bob. There are initially two choices: either they sit next to each other or across.<BR/><BR/>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.<BR/><BR/>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.<BR/><BR/>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.<BR/><BR/>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)).Unknownhttps://www.blogger.com/profile/16888729787755023147noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23973485422052790952007-11-14T11:53:00.000-06:002007-11-14T11:53:00.000-06:004040breckhttps://www.blogger.com/profile/09068597042303572115noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75518784957213385432007-11-14T10:42:00.000-06:002007-11-14T10:42:00.000-06:00I guess the problem is slightly ambiguous. We've a...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)?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6105939276115206392007-11-14T10:13:00.000-06:002007-11-14T10:13:00.000-06:00First we may decide from left to right for the ch...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<BR/>are 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.<BR/>Next we decide how to put n couples to n pairs of chairs. There are n! possibilities.<BR/>Now there remain for each of the n couples 2 possible seating.<BR/>So we get <BR/>2^n x n! x F(n+1) (where F(n) stands for the nth Fibonacci number).<BR/>This is the same result as in comment #1 and #3.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39132791470497478622007-11-14T10:02:00.000-06:002007-11-14T10:02:00.000-06:00# perfect matchings in the ladder graph (L_n = P_2...# perfect matchings in the ladder graph (L_n = P_2 x P_n) * n! * 2^n<BR/><BR/>= F(n+1) * n! * 2^n<BR/><BR/>where F(n) is the nth Fib. number<BR/><BR/>Maybe.Martin Harriganhttps://www.blogger.com/profile/01610696350600503266noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41921704539125768792007-11-14T09:20:00.000-06:002007-11-14T09:20:00.000-06:00An even number of couples must be sitting across f...An 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. <BR/><BR/>Suppose exactly k couples sit next to each other.<BR/><BR/>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.<BR/><BR/>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.<BR/><BR/>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.<BR/><BR/>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).Davehttps://www.blogger.com/profile/00243750470577898974noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90167283759569105532007-11-14T09:15:00.000-06:002007-11-14T09:15:00.000-06:00Is it f(n) = 2*n*f(n-1) + 4*n*(n-1)*f(n-2) ,where ...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?Anonymousnoreply@blogger.com