[Computational Complexity] Math Problems from everyday life
- Often I see something in real life that inspires a math problem. Could be a math problem for an exam or a student project or (more rarely) serious research. (e.g., I give my 9 year old great nephew seven crayons and he colors the numbers 1,...,2000 without any monochromatic 3-AP's so I get a new VDW number out of it.)
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.)
Posted By GASARCH to Computational Complexity at 11/14/2007 08:49:00 AM