Thursday, March 07, 2013

NPR Sunday Puzzle (Mar 3, 2013): Dinner Party Musical Chairs

NPR Sunday Puzzle (Mar 3, 2013): Dinner Party Musical Chairs:
Q: Eight people are seated at a circular table. Each person gets up and sits down again — either in the same chair or in the chair immediately to the left or right of the one they were in. How many different ways can the eight people be reseated?
For this puzzle, I think we have to assume each seat position and person is unique. Also, I assume Will wants seating arrangements where each person has their own chair (no sharing). What I don't see, is why the table has to be circular. Couldn't it be square and we could still figure out how to move left or right?

Edit: The first case that might get overlooked is everyone returning to their original seat. The next two cases are where all 8 people move clockwise or counter-clockwise one seat. There can't be any other cycles involving more than two people because that would require someone to move more than one seat, so the remaining cases involve neighboring "couples" swapping seats while others stay still. All that is required is to enumerate the ways to swap couples.
A: There are 49 ways that 8 people could stand up and be reseated (link to PDF containing diagrams). Incidentally, the Online Encyclopedia of Integer Sequences has the answers for various table sizes (A0048162 = 1, 2, 6, 9, 13, 20, 31, 49...) which confirms the answer for 8 people is 49 ways.

157 comments:

  1. Here's my standard reminder... don't post the answer or any hints that could lead directly to the answer (e.g. via Google or Bing) before the deadline of Thursday at 3pm ET. If you know the answer, click the link and submit it to NPR, but don't give it away here.

    You may provide indirect hints to the answer to show you know it, but make sure they don't give the answer away. You can openly discuss your hints and the answer after the Thursday deadline. Thank you.

    ReplyDelete
  2. In my mind, this is an equivalent stating of the problem: Try to imagine a poker table. We have the dealer position and 7 other positions, each with their own cards and chips. Then Will walks into the room and asks everyone to shift around using the "move left, right or stay" rule. How many ways could the 8 people be reseated?

    ReplyDelete
    Replies
    1. Actually Blaine, I think your restatement of the puzzle changes it slightly. I also think this may be the trick to solving it correctly.

      Delete
    2. The trick is to look when they stand up and see whose bottoms are threadbare and need to be reseated.

      Delete
    3. I can see the round table gets rid of any ambiguity in moving left or right. If you move strictly to the right from the number 1 position or strictly to the left from the number 2 position, you could move to a spot without a chair. (And you thought you'd never need that musical chairs strategy again).

      Delete
    4. I'm getting a very large number, but maybe I'm off base; that happens often.

      Delete
    5. Can we have as many rounds as we like, or is there just one?

      Delete
    6. Uncle John, one round, no squares, golden spirals . . .March fo(u)rth on this most assertive day of the year!

      Delete
    7. I love your clues and cues, WW. You're very generous. ;]

      Delete
    8. My pleasure, Uncle John.

      Last week the kindergartners & I did week two on Fibonacci and golden spirals. Four hours of Fibonacci & they are loving the 'F' numbers now. ;-)

      Maybe I'll bring this puzzle to them Friday. ;-)

      Delete
  3. I'm not sure. There's a whole class of "round table" combinatorics problems. For example, how many ways can 8 people be seated around a round table. The answer is 7!, since there are 8! ways to arrange 8 people in a line, but 8 of these are the same after rotation. So, the key me is what happens, for example, if everyone moves to his/her left? Is this another seating arrangment or not?

    ReplyDelete
    Replies
    1. No. I agree with Blaine. I think we need to assume that we have 8 people (label them a-h) and 8 chairs (label them 1-8). So we start off with 8 people/chair pairings (a1, b2, c3, etc). Any reseating arrangement which changes these pairings counts.

      Delete
  4. Well Blaine, how much have they been drinking? And can we even see with all that cigar smoke?

    ReplyDelete
  5. I have an answer, but with the math puzzles you can't be quite sure, so I'm going to think about it for the whole day.

    ReplyDelete
  6. To tell you the truth, I’m not even sure I fully and correctly understand what is being asked. I may just have to pass this one up. Oh well, I was one in only 150 solvers nationally last week :)

    One thing I figured out is that player 3 moving clockwise is exactly the same as player 4 moving counterclockwise.

    Chuck

    ReplyDelete
    Replies
    1. I wasn't....just for the record.

      Delete
    2. I was also one of 150, which made me sit up in bed this morning and scream when I heard that. Math like this makes my brain hurt. It is either simple as h***, or complicated as h***.

      Delete
  7. If we start out with person A in seat 1, B in seat 2, etc, it's easy to see that each person can end up in one of only 3 seats: A in 8, 1, or 2, B in 1, 2, or 3, etc. If we allowed lap-sitting, it's easy to see that there are 3^8, or 6561 possible arrangements. But we don't, so we know the answer has to be less than that. That narrows it down a bit...

    ReplyDelete
  8. Continuing, and not really giving anything away, after everyone stands up, only one of 4 things can happen:
    1. Everyone stays in her original seat.
    2. Everyone shifts one seat to the left.
    3. Everyone shifts one sear to the right.
    4. One or more (specifically, 1, 2, 3, or 4) pairs of adjacent people switch seats.
    So, all you need to do is figure out how many ways you can arrange pairs of adjacent people, add 3, and you're done!

    ReplyDelete
    Replies
    1. Hey Jan,

      You're thinking the same way that I was thinking and I'm sure you've arrived at the same total at which I arrived.

      Also, two words, one in each of Blaine's two clues at the top, tell me that Blaine arrived at the same total we did!

      Delete
    2. Do you think Will would accept 3 < x < 6561 as close enough?

      Glad I got outside to enjoy the spring-like day!

      Delete
  9. The Veterinary puzzle only had 150 entries. Considering the nature of math puzzles, I'm guessing this one will be a low turnout as well, especially they only report on correct answers. I submitted my best guess, but I'm never sure when it comes to the math ones.

    ReplyDelete
  10. OK, I lied before. Despite my earlier remark I decided to think about the puzzle anyway. And I have an answer.

    BTW I don’t think we need to designate chairs – just people. All places at a circular table are equal and which chair they’re in is irrelevant. It’s the order they’re seated in – i.e. who’s sitting next to whom, etc. – that defines a different seating arrangement. For example, if everyone moved one chair clockwise, that’s not a different seating arrangement – everybody’s still sitting next to the people they were before. But if Person 1 switched chairs with Person 2 that does constitute a different seating arrangement because now Person 8 is sitting next to Person 2 not Person 1.

    Anyway, your mileage may vary but that’s how it looks from here.

    Chuck

    ReplyDelete
    Replies
    1. I think you are changing the puzzle. I think you should read it again.

      Delete
    2. I don't agree. To me, if everybody moved one seat to the right (or left) that would count as a "re-seating". I even think that everybody sitting back down in the same seat would count, but this goes to show how hard it is to precisely understand the statement of a problem, let alone the solution.

      Delete
  11. You might be right SDB – I’ll have to ponder some more.

    And here’s another interesting question that Charles brings up. Look at the last sentence of the puzzle, particularly the last word. Does anyone think that if they sat in the same spot one wouldn’t count that as being reseated since they were already sitting there in the first place and thus were not reseated? Or do you think the word means that since they literally sat down again one would count the way they were originally seated as being reseated, too?

    Dictionary.com defines reseat as to provide with a new seat or seats or to show a person to a new seat. The Free Dictionary also defines it to mean to provide with a new or different seat. Vocabulary.com defines it to mean provide a new seat or show to a different seat.

    The answer to this question would affect one’s answer...

    Chuck

    ReplyDelete
  12. This one rang some bells. I'm going for the big number by assuming one of the chairs gets battered by the kitchen door. I came up with my answer by starting with two groups of four.

    ReplyDelete
  13. Also, do we assume only one "move" per reseating? If not, the number of solutions become so large that Will could not easily explain in 30 seconds, e.g everyone shifts one to the right, then they switch pairs 1/2 3/4 etc, then they rotate one more to the right again. Does that count as a single seating combination ? The possibilities are huge !

    ReplyDelete
    Replies
    1. Please, PLEASE, let us assume one move per reseating. With sugar on top?

      Delete
  14. Will said not to write a computer program to solve this, but I couldn't resist. The program showed that my manual answer was off by 1 (I think I double counted somewhere). As a bonus, the program solved the problem for any number of seats. Looking at the number of re-seatings as a function of the number of seats, produces a number sequence that appears various places online from the math literature.

    ReplyDelete
    Replies
    1. Thank you for subsidizing my laziness.

      Delete
  15. Replies
    1. Several weeks late; but I appreciated you baring your soul in your post. What's so hard to believe that the God Who created all things can and will speak to hungry and open people?

      Delete
    2. zeke,
      Thanks for the post, but I am wondering if you caught that my "charity begins at home." post is a play on words. Anyway I'm glad to see you keep an open mind. I feel I must clarify that I do not believe the voice I heard, while more perfect than possible, was what people would call God. My concept of God is much different than most people in the Western Hemisphere.

      Delete
    3. I caught the gist of the post, but I was just butting in. My roots are Asian. Encoupled with the mountain thang I'm a strange mutt at that.

      Delete
  16. Kin I bring mah own fude to dis shabang? I'm bringin' the combo meal without the mutated chicken breast, lite on the ketchup.
    Zeke the hongry

    ReplyDelete
  17. …What’s that? Mathematics? Oh, hello again, everyone.

    Some fun with the answer: If the solution is k, then the sum of the digits of k² equals one of k’s divisors, call this m; and the decimal expansion of 1⁄k has a period of m(m — 1).

    I will provide a formula for the general case of n persons come Thursday.

    ReplyDelete
    Replies
    1. Looking forward to the tutoring.

      Delete
    2. Hey pi man,
      With the 'fude' post am I in the ballpark?
      Zeke the party crasher

      Delete
    3. @PlannedChaos,

      Apart from the degenerative cases of 1 and 2 chairs, I'm seeing a nice relationship to the Fibonacci sequence. You too?

      Delete
    4. @Blaine,

      Indeed; that's sort of the key to the whole thing. Not sure you should be pointing this out, though.

      Delete
    5. Planned Chaos, what are your thoughts on the pi vs tau controversy? Given your "photo," I take it you are a pi lover?

      Delete
    6. @Word Woman,

      Despite my recent change in avatar, I actually have no preference since they’re functionally equivalent. Most of the debate seems to come down to which one is easiest to grok in the majority of situations, and there are a number of convincing arguments on both sides. And of course, even if Tau was preferable, it’d have to be significantly better in order to overcome pi’s establishment in the literature. So it remains an open question.

      Numberphile has a fun video debating their merits.

      Delete
  18. It was my mother's day to call me and while talking to her, the solution came to me. At least I hope it is the solution. Never can tell with these math problems.

    Here's my math question: what is the percentage of all Blaine's bloggers that were among the 150 correct answers last week? Count me in that number!

    ReplyDelete
    Replies
    1. I was one of the spurned 149. :-(

      Delete
    2. I do not believe there were 150, but somewhat fewer. They seem to always say "there were more than" or "there were about" X number" when it is a lessor amount than the figure they present. I was among that number, but will not be this week as I am not even working this puzzle. I am not all that math inclined. I think it is a good puzzle, but for those who are good at math.

      Delete
    3. I was amongst the about 150 as well. I'm not math inclined either. But, if I were inclined, I guess that would make me more geometrical than algebraic.

      Delete
    4. I was in the unpicked 149 too!

      Delete
    5. I too was among the 150, as were my two doppelgangers.

      Delete
    6. Another member of the 150 club here!

      Delete
    7. @skydiveboy,
      Ironic that you professed not knowing how to calculate the answer in the 49th post to this blog!

      (P.S.: Obligatory “I was also in the unchosen 150.”)

      Delete
    8. Blaine, was the unpicked 149 a nod at the table answer?

      I now looked at the OEIS as I thought it would ne unfair to look before. What a cool tool. I also learned about the rise of tau and fall of pi. All in all, a most satisfying puzzle.

      Dare I say to U: "Taut me alot."

      Btw, next to Colorado, Utau is my favorite state. I am a fan of Fisher Tower, Arches, Escalante, Capitol Reef, Bryce and Zion. Maybe Utau could adopt Tau as the Official State Number. ;-)

      Delete
    9. Although, all these years and Mississippi hasn't adopted pi. . .

      Delete
  19. I was among the 150 as well. I have an answer to this week's puzzle and it fits with the Fibonacci references.

    ReplyDelete
    Replies
    1. Will should have mentioned there was a vase with a sunflower in the middle of the table. I'm just sayin'...

      Delete
    2. How are you, AbqGuerrilla? We've missed you and your doppelgangers.

      Back to the sunflower. . .Have you gotten caught up in determining bract-kets for March madness?

      Delete
    3. Hola WW ~ I enjoy the college basketball classic almost as much as your botanical humor. As for my absence this week, the math puzzles just don't do it for me. I am quite good at solving them, but the fact that you never really know for sure if you have the correct answer always leaves me feeling like it's an exercise in futility. I thought about purchasing a math puzzle book on Amazon last month and when I clicked on it, a pop-up window surfaced with the message: "People who bought this book also bought a rope and a stool." That kind of sums it up for me. "See" you manana, no doubt.

      Delete
    4. You can fool all of the people some of the time, and some of the people all of the time, but you can't fool all of the people all of the time.

      Delete
    5. @AbqGuerrilla, glad you enjoy botanical humor ;-). As to the rope and stool, it makes me think of Whodunnit books...Although in Utah maybe they are Hoodoo it books?
      As to the uncertainty of the answers for the math puzzles, that's part of their charm for me. That, and all the good stuff I learn along the way.
      We talked about phi yesterday with Kg crowd.Several kids thought I was saying feet!
      Another weekend snowstorm here so plenty of time for puzzle solving.

      Delete
    6. And I thought you were playing Fibonacci chairs yesterday. Just goes to show!
      Uh...the 'charm' of mathematics is it's 'certainty' ???????????

      Delete
    7. Paul, we did both. Measured the height & width of the kids' faces and averaged the ratios to 1.61. Had us jumping out of our chairs and onto our phi-t.

      Journey...not the destination ;-). That's what I wrote on my SATs.
      All this OEIS talk has me wondering if mathematicians, like prisoners and jokes, walk around saying A82031 and A3424 to each other at math conferences. . .

      Delete
  20. I was also among the 150. Not expecting to be among the chosen this week, though.

    ReplyDelete
  21. I have an answer for this which I'm pretty happy with, but as a check I'll tell you the answers I got for the cases where there are 4 people, and where there are 6 people: 9 and 20 respectively.

    ReplyDelete
  22. Regarding the question of the 150, I am in a subset of folk who are (somewhat) active on here, got the answer before the deadline, but didn't actually enter, as I'm outside the US.

    ReplyDelete
  23. Elliott, is it possible your answer for 6 people is off by 1?

    And, NPR won't call outside the U.S.?

    ReplyDelete
    Replies
    1. Only if you're not including the situation where everyone stays where they were. The wording of the question is a little ambiguous, but I have included that eventuality.

      I'd assumed NPR wouldn't call the UK, but maybe I'm wrong. When you go to enter, it asks for your local station, and of course I don't have one.

      Delete
  24. I have manually calculated the answer for 2,3,4,5,6,7 and 8 and found the relevant listing on the OEIS, so now I'm certain they're correct.

    ReplyDelete
  25. Yes, Elliott's off by one. Also, after a careful re-listening to the podcast I'm still not clear if "reseated" is meant to include the trivial case of everyone back in their original seat.

    It's only a difference of one in the answer, but I'm qualifying my answer to make it clear which interpretation I used! I also have a generalized formula and analysis for n seats, n >= 4 (you can probably work out 1, 2, and 3 for yourself, no matter how "math challenged" you think you are!).

    And for me, it's nice to get a math problem from Will Shortz now and again amongst the many word problems!

    ReplyDelete
    Replies
    1. It does come down to the interpretation of the question as to whether the 'identity' is included in the count. If it's not to be included then I'd just have to subtract 1 from each of my answers.
      The fact that Blaine uses the word 'square' in his hint suggests to me that he at least thinks the identity possibly should be included.

      Delete
    2. Ned, I agree. It is great to get a math problem...This is not that difficult if you work your way up the food chair (sic). Some are saying they can't or won't. You can!

      Delete
  26. I finally decided that drawing a tree was the way to go. Suprisingly easy after getting into the swing of things.

    Of the three people that can occupy a seat, the original owner is in it 1.5 times more than either of the others.

    Let's see if I draw trees better than I count triangles.

    ReplyDelete
  27. I did some fairly simple casework, but the answer i got makes me feel like there's some way to quickly knock out this problem.

    ReplyDelete
  28. Hey Blaine,

    I see you altered this week’s artwork (from this to this). What inspired the change?

    ReplyDelete
    Replies
    1. As part of my submission to NPR (and for posting after the deadline on Thursday), I've created a chart of the various reseatings and I used the new version as the basis. Aesthetically, I liked circles and the extra 11.25° rotation.

      Delete
    2. It seems we’re always duplicating effort. :) I’ve also put together a little video tutorial for Thursday.

      (Side note: you mean the extra 22.5° rotation.)

      Delete
    3. Oops, cut 90° in half too many times. :)

      Delete
    4. So can I just say π/8 radians? ;)

      Delete
    5. I hate it when they cut the pi into too many slices.

      Delete
    6. Me, too, Jan. And with pi day coming up on 3/14 and all. . .such a fruitful time.

      Delete
    7. Nah, fruit just wastes pie crusts that could be filled with pecans.

      My niece is waiting to hear from MIT at 6:28 (Tau Time) on that date.

      Delete
    8. That's exciting! I wish her well.

      How was your windy bike ride? Gotta love the changing of the seasons.

      Delete
    9. 25 miles of misery. But I got a rare midweek afternoon ride in today, when it was much nicer. Saw a turkey, a coyote, and heard what I learned on NPR this week is the true harbinger of spring, a redwing blackbird, so things are looking up.

      Delete
    10. Nice! Violets are up here.

      Back to that crust thing, do you thing you could have your pi and eat it tau?

      Delete
    11. Hey! who stole the leading role from Robin of being harbinger of spring? Those blackbirds make their entrances too early and try to steal the scene like some Ali Baba.

      Delete
    12. RobinRobin, nice to see you bobbing along again. Apparently the redwing blackbird is a better harbinger of spring...Though the ultimate is a harbinger-of-spring!

      Delete
  29. Well, I finally rolled up my sleeves and ground out an answer which (wonder of wonders!) is divisible by the sum of the digits of it's square, and whose reciprocal's decimal expansion repeats every x digits, where x is a number alluding to a legendary ballplayer.
    I'm exhausted.
    When I regain my strength, I may go looking for Fibonacci numbers, or I may ask God why I ever thought this might have anything to do with balanced ternary arithmetic.
    Still looking forward to the tutorials.

    ReplyDelete
    Replies
    1. You must have been thinking of the GeekDad puzzle this week.

      Delete
    2. No, but thanks for thew tip.

      Delete
  30. I came up with an answer. Dont ask Lucie how I got there.

    Perhaps my greatest skill was missing the Veterinary puzzle entirely, by accident.

    - Other Ben

    ReplyDelete
  31. This comment has been removed by a blog administrator.

    ReplyDelete
    Replies
    1. This comment has been removed by a blog administrator.

      Delete
    2. @Elliott,

      I think that clue (now deleted twice), combined with your prior comments could be considered as something that could lead to the answer. Do you agree? Yes, you have the same answer I do. You can elaborate after the deadline.

      Delete
    3. Thank you, Blaine. Sometimes I wish there was a way to privately message you directly whenever I see a giveaway like that. Something I often see other people do, and the worst thing one can do IMO, is to add a reply stating the clue should be removed. In the meantime, it only serves as a red flag for other visitors that the indicated clue can lead to the answer with some cursory Googling.

      Delete
    4. And your avatar as twice as good now!

      Delete
    5. Wow, change! Can Massachusetts Institute of Tau be far behind?

      Delete
    6. Twice as good, with half the legs! (I always found Pi fattening.)

      Delete
    7. My son was born on Tau day, June 28th 2011. I wanted to call him Tau but we called him Austin instead, which does at least have the letters of Tau in it!

      Sorry for the deleted comments, I didn't think it was that much of a giveaway - I've seen much more obvious clues to other puzzles left in place - but I suppose when combined with my previous comments could lead to the answer. I though it would be allowed as just Googling the five digit number wouldn't lead anywhere, but I bow to your greater judgement.

      Delete
  32. Looking forward, indeed, to the sprezzatura from both Blaine and Planned Chaos...and being able to finally give all those clues that would make it too easy.

    AbqG, wondered if you could take a field trip to SLC to interview Dr. Palais about why he thinks tau is really better than pi. Is he really just trying to promote Utau? :-)

    ReplyDelete
    Replies
    1. Ouch! That pun was tau-rible.

      Delete
    2. Thanks, Blaine. Are you hopping on the Tau Train, too?

      Delete
  33. Next time I venture down to the capitol, WW, I'll see if Dr. Palais is available for lunch. We used to be fraternity brothers at Bringham Young (I Felta Thigh). Pretty sure he'll remember me.

    ReplyDelete
  34. There are 49 unique arrangements.

    For those who had difficulty figuring out how one might go about counting, I’ve put together a handy solution video. Also available are the 49 still frames, and a single composite image showing all 49 positions at once.

    If the initial seating is ABCDEFGH, then the permutations (sorted alphabetically) are as follows:

    ABCDEFGH, ABCDEFHG, ABCDEGFH, ABCDFEGH, ABCDFEHG, ABCEDFGH, ABCEDFHG, ABCEDGFH, ABDCEFGH, ABDCEFHG, ABDCEGFH, ABDCFEGH, ABDCFEHG, ACBDEFGH, ACBDEFHG, ACBDEGFH, ACBDFEGH, ACBDFEHG, ACBEDFGH, ACBEDFHG, ACBEDGFH, BACDEFGH, BACDEFHG, BACDEGFH, BACDFEGH, BACDFEHG, BACEDFGH, BACEDFHG, BACEDGFH, BADCEFGH, BADCEFHG, BADCEGFH, BADCFEGH, BADCFEHG, BCDEFGHA, HABCDEFG, HBCDEFGA, HBCDEGFA, HBCDFEGA, HBCEDFGA, HBCEDGFA, HBDCEFGA, HBDCEGFA, HBDCFEGA, HCBDEFGA, HCBDEGFA, HCBDFEGA, HCBEDFGA, HCBEDGFA.

    By taking the sum of the (n–1)st and (n+1)st Fibonacci numbers, plus the two cases where everyone moves one place to the left or right, we can generalize to n persons and define a function σ (sigma) that returns the number of reseatings:

    For n > 2, σ(n) ≡ φ + ψ + 2
    (image of this equation),

    where φ (phi) and ψ (psi) are real numbers representing, respectively, the golden ratio and its conjugate; namely, φ = (1 + √5)/2 and ψ = (1 – √5)/2 (image of these values substituted into σ). Note that it is a direct result of the Fibonacci sequence being recursively defined by the sum of its previous two entries that our function’s domain is restricted to n > 2.

    The first few outputs are listed below.

    σ(0) ≝ 1, σ(1) ≝ 1, σ(2) ≝ 2, σ(3) = 6, σ(4) = 9, σ(5) = 13, σ(6) = 20, σ(7) = 31, σ(8) = 49, σ(9) = 78, σ(10) = 125, σ(11) = 201, σ(12) = 324, σ(13) = 523, σ(14) = 845, σ(15) = 1366.

    For more information, see the entry at The Online Encyclopedia of Integer Sequences.

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

      Delete
    2. This comment has been removed by the author.

      Delete
    3. @actonbell,

      If one substitutes the closed-form expressions for the (n-1)st and (n+1)st Fibonacci numbers into the equation F(n-1) + F(n+1) + 2, it simplifies to σ(n) ≡ φ + ψ + 2, as given above.

      Delete
    4. Right you are. Sorry for failing to simplify!

      Delete
    5. No need to apologize (or delete your original comments, for that matter)! I welcome error checking.

      Delete
    6. So, does anyone care to explain why for all k σ(4k) is always a perfect square?

      k 4k σ(4k)
      0 0 1 = 1²
      1 4 9 = 3²
      2 8 49 = 7²
      3 12 324 = 18²
      4 16 2209 = 47²
      5 20 15129 = 123²
      6 24 103684 = 322²
      7 28 710649 = 843²
      8 32 4870849 = 2207²
      9 36 33385284 = 5778²

      Delete
    7. @Enya_and_Weird_Al_fan,

      Very good observation!

      Proof that for all n = 4i, σ(n) is a perfect square:

      Using the substitution ψ = -1/φ, we can rewrite sigma as σ(n) = φ + (-1/φ) + 2.

      Substituting 4i for n and simplifying, we can get

      σ(4i) = ((φ⁴ + 1)/φ²

      which is what we wanted to show.

      Delete
    8. The right-hand side can be further simplified to the square of

      (φ+1) + (ψ+1),

      which perhaps makes it a bit easier to see, based on the unique properties of the golden ratio, how (φ+1) + (ψ+1) ∈ ℕ for all i ∈ ℕ, implying ((φ+1) + (ψ+1))² is indeed a perfect square for all i ∈ ℕ.

      Delete
  35. Four pairs of neighbors swap two ways.
    Three pairs of neighbors swap sixteen ways.
    Two pairs of neighbors swap twenty ways.
    One pair of neighbors swaps eight ways (because there are eight pairs of neighbors).
    I was disinclined to include 'everybody moves one chair clockwise' and 'everybody moves one chair anticlockwise' because I was reading something into the shape of the table.
    I was inclined to include the original seating arrangement because I glossed over 'reseating' with my own interpretation.
    A number of the 'pairs of neighbors' 'ways' may be excludable consistent with one or the other or both of my 'inclinations'. If that number turns out to be between three and six, I might consider putting MrScience on trial for witchcraft.
    1/k = 0.0204081632653061224489795918367346938775510204081632653061224489795918367346938775510204081632653061 ...
    Mariano Rivera rules.
    Sprezzatura....yes, I do think Blaine and PC wil 'make it look easy'.

    ReplyDelete
    Replies
    1. After glancing at PC's post...I'm not so sure.

      Delete
    2. Thanks, Blaine and Tau Man.

      I stopped at 42...Wanted the Hitchhiker's Guide to the Galaxy and MrScience (almost) to be the answer. It was fun anyway!

      My "some are" (summer) comment was meant to point toward Summer of '42. I will save that for the next puzzle MrScience chimes in on. ;-)

      Delete
  36. Next week's challenge: Eight people are seated at a circular table. Each person gets up
    and sits down again — either in the same chair or in the chair immediately to the left or
    right of the one they were in. How many different ways can the eight people be reseated?

    First 3 counted possibilities:

    1. All 8 people sit down in their original seat.
    2. All 8 people sit down in the chair immediately to their left
    3. All 8 people sit down in the chair immediately to their right

    All other possibilities involve at least one swap between adjacent seats; all people not
    involved in an adjacent swap sit down in their original seat.

    1. Only one swap: 8 possibilities.

    2. Two swaps: 8*5/2 (If we put 8 marks on the table, each mark half-way between two
    adjacent seats, then if we represent a swap by drawing an X through a half-way mark,
    then each X drawn puts its neighboring marks off limits. So the first X removes not
    only itself, but its two neighbors from consideration for the second X. 20 possibles.

    3. 4 swaps: (Easier to consider than 3, so I'll do this next and save the case of 3 for
    last.) 2 possibilities.

    4. 3 swaps: This leaves two people unswapped. The unswapped people are either neighbors
    or there is one X between them on one side, two X's on the other side. In both cases
    the left-most of the two unswapped people (with fewest others between them) could have
    been at any of the 8 positions. So 16 total possibilities here.

    So total possible ways are: 3 + 8 + 20 + 2 + 16 = 49 possible ways.

    ReplyDelete
  37. Ah, the OEIS! Such a wonderful resource - Dr Sloane is a hero.
    I once worked on a problem (namely 'how many quadrilaterals in a triangular matchstick array') for which the sequence didn't yet exist. So I wrote it up and it got accepted (A204185). One of my proudest moments.

    ReplyDelete
    Replies
    1. Right beside 6-28-11 and the birth of Austin, yes? Congrats on both fronts.

      Never ran into the OEIS before. I did go to geologic field camp with a group of engineers who lumped all our elegantly detailed stratigraphic sequences as "rock." But not one word about OEIS!

      Delete
    2. This comment has been removed by the author.

      Delete
  38. This comment has been removed by the author.

    ReplyDelete
  39. "Of the three people that can occupy a seat, the original owner is in it 1.5 times more than either of the others."

    In other words, the answer is a multiple of 7.

    ReplyDelete
  40. Enjoyed the video about Pi vs Tau Smackdown, Planned Chaos. For me, the most compelling reason to introduce pi is the easily measurable circumferences and diameters of circles. It makes it more tangible and touchable and therefore stays in the brains of young kids more readily.

    Of course, both are correct.

    Ok, I'm going to throw in the tau-el on this one. Off to tead my copy of The Pi of Pooh, er The Tao(u) of Pooh.

    ReplyDelete
  41. I figured 48. I’m still not convinced that standing up and sitting down in the same place constitutes being reseated...

    Chuck

    ReplyDelete
  42. Just a note here. I did not solve the puzzle. I read it online shortly after it was posted and went back to bed thinking I would solve it when I got up much later. I immediately realized the legit first three seatings where everyone sits down in their original chairs and then all rotating one seat to the left and then to the right, but I thought after those easy ones it would just get unbearably tedius and so decided I would not do more than simply think about it.
    I posted to Blaine that I thought his restatement was missing the counting of them all sitting back down in the same seats, but I just went back and re-read Blaine's post and I now think I was in error, and that he did allow for that. Sorry Blaine.
    Later on I did draw a circle and number the chairs and set Scrabble chips beside each chair and began listing the obvious, easy seatings of about 30, but then I figured, incorrectly it now seems, that it would get entirely out of hand, and I was not interested in this tedium any longer, and so I stopped. Now I see I should have pushed on as I was not as far as I thought from the solution, but I really was not enjoying it.
    I am not at all into math and I thought there would be a very simple solution, which I still don't think there is, but I don't understand math language. All that being said I want to say that I compliment Will Shortz on providing us with a REAL puzzle this time. Thanks Will, and sorry I was not up to it.

    ReplyDelete
    Replies
    1. Sky Dive Boy, thanks for writing so forthrightly.

      Enya and Weird Al's description of the answer was the clearest to me. What do you think?

      When you said you weren't even going to try it made me mad. And I don't think you were the only one. When I volunteered in my son and daughter's classrooms I heard "Oh, I can't do math!" from teachers, parents, and kids. No one ever said "I can't read."

      It's the reason I keep working with kindergartners so they are encouraged to fall in love with numbers...because it is a beautiful language. They smile and laugh when they say Fibonacci and draw golden spirals.

      Anyway, SDB, I thought you might try...and you were close (so was I). Please take away the soapbox now.

      Delete
    2. I really cannot comment on Enya's description as I am not proficient at math, but at least his is the most understandable to me. I was a terrible student in school and learned mostly by osmosis and the fact that I read adult books instead of paying attention or studying. I have to say that I loved geometry, much to my surprise, as it is puzzles. I have never been fully able to understand why I was a lousy student, but I have a high IQ and love to learn when it is intelligently provided. I have little good to say of my school teachers.
      I never doubted that I was able to solve this puzzle, but I had things to do and was not excited about the tedium of listing the possibilities, which I believed were more than they actually are. Therefor I took a pass on this one and perhaps now regret it. You can just chalk it up to my being lazy this time.

      Delete
    3. I think it may just be partly the way math was generally taught when we were learning. It was so esoteric and theoretical. Lots of workbooks.

      My kids had lots of manipulatives (beans or m and m's work just fine) so numbers had a tangible kinesthetic meaning to them. Once they could feel numbers it made sense in their developing brains.

      It makes sense to me that you liked geometry most because it has that tangible (and tangential;-)) feel.

      I wish you could experience these kindergarteners. There are 8 in the class. I placed several piles of beans on the table and asked them how many beans in the next pile? I gave them the clue of "Look what happens when we push together this pile of 1 and 1, now 1 and 2." Every kid placed the piles in sequence 1,1,2,3,5,8,13, and 21. One kid went up to 89!

      At the end of class, Isobel said "And we're even a Fibonacci number class!"

      Tomorrow can't come soon enough...

      Delete
  43. Can anyone explain to me the meaning of the formula in the title of the OEIS entry? The formula is
    (1-x+3*x^3-2*x^4-3*x^5)/(1-2*x+x^3)
    (image of this equation), but I can’t figure out how it’s related to the sequence they’re describing.

    ReplyDelete
  44. Planned Chaos, If you do the power series expansion of the indicated quotient in powers of x, the coefficients of the successive powers of x
    are the successive terms in the sequence. If the sequence you were trying to represent were all ones, you would write 1/(1 - x). The power series
    expansion would be 1 + x + x^2 + x^3 + ..., and
    all the coefficients are 1.

    ReplyDelete
    Replies
    1. My answer was 56. I didn't account for the overlap. Using my superficial knowledge of algebra I went with a combination equation.
      @ ww halfway between mine and yours was the right answer. 1/2 point apiece.
      Remember your towel and don't panic.
      Zeekphod

      Delete
    2. Zeke Creek, I'm surprised you weren't tutored by Blaine. ;-)

      Delete
    3. Ouch! Snipper and Blaine, one and the same?

      Delete
    4. Did anyone from Blaine's Blog get the call?

      Delete
  45. In a slightly different question, where everybody had to move one to the left or the right, there would be only four possible re-seatings.

    ReplyDelete
  46. All week I've wanted a mathematical/logical explanation from basic principles for why the Fibonacci series can be used to find the general answer to this problem (i.e., not just looking at the OEIS and finding a series that seems to fit this case). I think I have found such an explanation. It's fair long, so I'll give it in 2 posts.

    First I want to show that

    sigma(n) = sigma(n-2) + sigma(n-1) - 2

    where sigma(n) is the answer to this problem for a table size of n. Define a function swap(n) that is the number of 2-seat swaps for a table of n, INCLUDING 0 swaps. Then,

    sigma(n) = swap(n) + 2

    where the 2 accounts for the cases where everyone moves right or left.

    Now, for a table size of n, focus on any pair of adjacent seats. There are exactly 5 all-inclusive cases:

    1. Both seats do not swap.
    2. The leftmost seat swaps with the seat to the left and the rightmost does not swap;
    3. The rightmost seat swaps with the seat to the right and the leftmost does not swap.
    4. The seats swap with each other.
    5. The leftmost seat swaps with the seat to the left and the rightmost seat swaps with the seat to the right.

    Now, consider a table size of (n-1), and focus on any seat. There exactly 3 cases:

    A. The seat does not swap.
    B. The seat swaps with the seat to the left.
    C. The seat swaps with the seat to the right.

    Case A maps exactly to Case 1 for the table size of n. By "maps" I mean that the remaining (n-2) seats have exactly the same possible arrangements. Case B maps to Case 2, and Case C maps to case 3.

    Now, consider a table size of (n-2) and focus on the space between any pair of seats. There are exactly 2 case:

    a. The seats on either side do not swap.
    b. The seats on either side do swap.

    Case a maps to case 4 for a table size of n, and case b maps to case b maps to case 5.

    Therefore,

    swaps(n) = swaps(n-2) + swaps(n-1)

    but

    sigma(n) = swaps(n) + 2 or swaps(n) = sigma(n) - 2)

    So, substituting,

    sigma(n) = (sigma(n-2) - 2) + (sigma(n-1) - 2) + 2
    = sigma(n-2) + siga(n-1) - 2

    ReplyDelete
  47. Continuing from my last post, I now want to show why

    sigma(n) = Fib(n-1) + Fib(n+1) + 2

    where Fib(n) is the nth term of the Fibonacci series (i.e., 1,1,2,3,5,8, ...). The proof is by induction on m, m > 2.

    As others have show above, sigma(3)=6, and Fib(2)=1 and Fib(4) = 3, so

    sigma(3) = Fib(2) + Fib(4) + 2 = 1 + 3 + 2 = 6.

    Now, assume

    sigma(m) = Fib(m-1) + Fib(m+1) + 2

    We must show that

    sigma(m+1) = Fib(m) + Fib(m+2) + 2

    From my previous post

    sigma(m) = sigma(m-2) + sigma(m-1) - 2

    So,

    sigma(m+1) = sigma(m-1) + sigma(m) - 2

    Substituting the induction hypothesis,

    sigma(m+1) = Fib(m-2) + Fib(m) + 2 + Fib(m-1) + Fib(m+1) + 2 - 2

    or

    sigma(m+1) = Fib(m-2) + Fib(m-1) + Fib(m) + Fib(m+1) + 2


    By the definition of the Fibonacci series,

    Fib(m) = Fib(m-2) + Fib(m-1), and
    Fib(m+2) = Fib(m) + Fib(m+1)

    Substituting this gives

    sigma(m+1) = Fib(m) + Fib(m+2) + 2

    which is the desired result, and we have proved

    sigma(n) = Fib(n-1) + Fib(n+1) + 2

    by induction.

    We can now apply the closed form solution based on the Fibonacci series explained previously.

    ReplyDelete
  48. Congratulations, Laura Leonard.

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

      Delete
  49. Enter man in a bejeweled dinner jacket. The math symposium director looks at him and says "Sequence, sequence...not sequins."

    Ok, on to the next puzzle, please.

    ReplyDelete
  50. The new puzzle came up a bit ago.

    Next week's challenge: Think of two familiar three-word sayings in which all three words are the same length. The middle word in both sayings is the same. In each saying, the first and last words rhyme with each other. What two sayings are these?

    I already have an answer and am wondering if it the same as expected. Who thought it would be up so soon? Sorry I have not come up with a hint yet that is not too revealing, so you are just going to have to wait

    ReplyDelete
  51. New puzzle is up. The key here is to take your time. If that doesn!t work, then just force it.

    ReplyDelete
  52. I've made my submission. I'm I happy with it?

    I happen to know a certain king would be unhappy with one of the three-word sayings I submitted. He even proposed an improved three-word phrase to replace it, but unfortunately his improvement fails the criteria of the puzzle.

    ReplyDelete