Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Math Problems on vacation

Expand Messages
  • GASARCH
    SO, as mentioned in my last post, there were two other math-folks on the bus tour I was taking. So what did we do? Exchange problems to solve on the bus. We
    Message 1 of 1 , Aug 12, 2008
    • 0 Attachment
      SO, as mentioned in my last post, there were two other math-folks on the bus tour I was taking. So what did we do? Exchange problems to solve on the bus. We alternated.
      1. I asked them: if there are n couples in a resturant, and everyone sits either across from or next to their darling at a rectangular table (nobody sits at the ends) then how many ways can they be seated?
      2. They asked me: A marathon is 26.2 miles. A runner runs in such a way that during EVERY 1-mile interval he averages exactly 10 miles an hour. But his overall time is better than 10 miles an hour. How can this be?
      3. I asked them: Show that if no matter how your 3-color the numbers {1,...,2006} there will be two points, a square apart, the same color.
      4. They asked me: There is a bus where n people have assigned seats. The first person sits randomly instead of in his assigned seat. Henceforth, every person looks for his assigned seat, and if he does not find it, sits in a random seat. What is the prob that the last person sits in his assigned seat?
      How did we do on these problems? They got my problems correctly. I basically got theirs (missed some points).

      It was interesting coming up with problems that had not well known. I couldn't ask them truth-teller-and-liar problems or hats problems, since these are well known. Some of the problems above have appeared on this blog before. Not sure if that makes them well-known. At least they didn't know them. I tried asking the following problem that I thought was not so well known (I read it in American Math Monthly and told it to Peter Winkler two years ago-- he had not heard of it), but they had already heard it:
      Here is a game: There are initially two piles of stones with a in one pile and b in the other. Every move a player removes a multiple of the smaller pile from the larger. If either pile has 0 in it then you cannot move. THe first player who can't move loses. For which (a,b) does player I have a winning stradegy.

      Readers- I am not going to post solution. But you can in the comments!

      --
      Posted By GASARCH to Computational Complexity at 8/12/2008 12:14:00 PM
    Your message has been successfully submitted and would be delivered to recipients shortly.