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?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?

**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, theOnline Encyclopedia of Integer Sequenceshas 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.

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.

ReplyDeleteYou 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.

Beautiful, tangible diagram, Blaine!

DeleteIn 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?

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

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

DeleteI can see the

Deleteroundtable 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).I'm getting a very large number, but maybe I'm off base; that happens often.

DeleteCan we have as many rounds as we like, or is there just one?

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

DeleteI love your clues and cues, WW. You're very generous. ;]

DeleteMy pleasure, Uncle John.

DeleteLast 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. ;-)

I guessed 52.

DeleteI'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?

ReplyDeleteNo. 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.

DeleteWell Blaine, how much have they been drinking? And can we even see with all that cigar smoke?

ReplyDeleteI 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.

ReplyDeleteA 2 step multiplication?

ReplyDeleteOne step combo.

DeleteTo 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 :)

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

Chuck

I too was one of the 150!

DeleteI wasn't....just for the record.

DeleteI 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***.

DeleteIf 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...

ReplyDeleteContinuing, and not really giving anything away, after everyone stands up, only one of 4 things can happen:

ReplyDelete1. 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!

Hey Jan,

DeleteYou'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!

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

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

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.

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

ReplyDeleteBTW 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

I agree!

DeleteI think you are changing the puzzle. I think you should read it again.

DeleteI 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.

DeleteYou might be right SDB – I’ll have to ponder some more.

ReplyDeleteAnd 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

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.

ReplyDeleteAlso, 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 !

ReplyDeletePlease, PLEASE, let us assume one move per reseating. With sugar on top?

DeleteWill 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.

ReplyDeleteThank you for subsidizing my laziness.

DeleteCharity begins at home.

ReplyDeleteSeveral 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?

Deletezeke,

DeleteThanks 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.

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.

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

ReplyDeleteZeke the hongry

Ball, bone, bell or boot?

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

ReplyDeleteSome fun with the answer: If the solution is

k, then the sum of the digits ofk² equals one ofk’s divisors, call thism; and the decimal expansion of 1⁄khas a period ofm(m— 1).I will provide a formula for the general case of

npersons come Thursday.Looking forward to the tutoring.

DeleteHey pi man,

DeleteWith the 'fude' post am I in the ballpark?

Zeke the party crasher

Paul, down Biff ! ;-)

Delete@PlannedChaos,

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

@

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

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

Delete@

DeleteWord 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

waspreferable, it’d have to besignificantlybetter in order to overcome pi’s establishment in the literature. So it remains an open question.Numberphile has a fun video debating their merits.

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.

ReplyDeleteHere'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!

I was one of the spurned 149. :-(

DeleteMe too.

DeleteI 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.

DeleteMe, too

DeleteI 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.

DeleteI was in the unpicked 149 too!

DeleteI too was among the 150, as were my two doppelgangers.

DeleteAnother member of the 150 club here!

Delete@

Deleteskydiveboy,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.”)

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

DeleteI 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. ;-)

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

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

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

DeleteHow are you, AbqGuerrilla? We've missed you and your doppelgangers.

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

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.

DeleteYou 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@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?

DeleteAs 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.

And I thought you were playing Fibonacci chairs yesterday. Just goes to show!

DeleteUh...the 'charm' of mathematics is it's 'certainty' ???????????

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.

DeleteJourney...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. . .

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

ReplyDeleteI 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.

ReplyDeleteRegarding 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.

ReplyDeleteElliott, is it possible your answer for 6 people is off by 1?

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

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.

DeleteI'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.

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.

ReplyDeleteYes, 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.

ReplyDeleteIt'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!

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.

DeleteThe fact that Blaine uses the word 'square' in his hint suggests to me that he at least thinks the identity possibly should be included.

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!

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

ReplyDeleteOf 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.

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.

ReplyDeleteHey Blaine,

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

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.

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

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

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

DeleteSo can I just say π/8 radians? ;)

DeleteYes, or τ/16 radians. :D

DeleteI hate it when they cut the pi into too many slices.

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

DeleteNah, fruit just wastes pie crusts that could be filled with pecans.

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

That's exciting! I wish her well.

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

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.

DeleteNice! Violets are up here.

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

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.

DeleteRobinRobin, 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!

DeleteWell, 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.

ReplyDeleteI'm exhausted.

When I regain my strength, I may go looking for Fibonacci numbers, or I may ask God why I

everthought this might have anything to do with balanced ternary arithmetic.Still looking forward to the tutorials.

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

DeleteNo, but thanks for thew tip.

DeleteThew.....what is THAT?

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

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

- Other Ben

This comment has been removed by a blog administrator.

ReplyDeleteThis comment has been removed by a blog administrator.

Delete@Elliott,

DeleteI 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.

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

Deletecando 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.And your avatar as twice as good now!

DeleteWow, change! Can Massachusetts Institute of Tau be far behind?

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

DeleteMy 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!

DeleteSorry 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.

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.

ReplyDeleteAbqG, 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? :-)

Ouch! That pun was tau-rible.

Delete

DeleteThanks, Blaine. Are you hopping on the Tau Train, too?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.

ReplyDeleteThere are

ReplyDelete49 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 tonpersons 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 ton> 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.

This comment has been removed by the author.

DeleteThis comment has been removed by the author.

Delete@

Deleteactonbell,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.Right you are. Sorry for failing to simplify!

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

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

Deletek 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²

@

DeleteEnya_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 4

ifornand simplifying, we can getσ(4i) = ((φ⁴ⁱ+ 1)/φ²ⁱ)²which is what we wanted to show.

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

Delete(φ+1)

ⁱ+ (ψ+1)ⁱ,which perhaps makes it a bit easier to see, based on the unique properties of the golden ratio, how (φ+1)

ⁱ+ (ψ+1)ⁱ∈ ℕ for alli∈ ℕ, implying ((φ+1)ⁱ+ (ψ+1)ⁱ)² is indeed a perfect square for alli∈ ℕ.Four pairs of neighbors swap two ways.

ReplyDeleteThree 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'.

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

DeleteThanks, Blaine and Tau Man.

DeleteI stopped at 42...Wanted the

Hitchhiker's Guide to the Galaxyand MrScience (almost) to bethe 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. ;-)

Next week's challenge: Eight people are seated at a circular table. Each person gets up

ReplyDeleteand 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.

Ah, the OEIS! Such a wonderful resource - Dr Sloane is a hero.

ReplyDeleteI 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.

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

DeleteNever 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!

This comment has been removed by the author.

DeleteThis comment has been removed by the author.

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

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

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.

ReplyDeleteOf 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.*read*

ReplyDeleteMy answer: 8x3x8=192.

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

ReplyDeleteChuck

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.

ReplyDeleteI 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.

Sky Dive Boy, thanks for writing so forthrightly.

DeleteEnya 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.

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.

DeleteI 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.

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.

DeleteMy 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...

Domani never comes.

DeleteCan anyone explain to me the meaning of the formula in the title of the OEIS entry? The formula is

ReplyDelete(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.

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

ReplyDeleteare 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.

Excellent. Thank you.

DeleteMy answer was 56. I didn't account for the overlap. Using my superficial knowledge of algebra I went with a combination equation.

Delete@ ww halfway between mine and yours was the right answer. 1/2 point apiece.

Remember your towel and don't panic.

Zeekphod

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

DeleteOuch! Snipper and Blaine, one and the same?

DeleteDid anyone from Blaine's Blog get the call?

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

ReplyDeleteAll 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.

ReplyDeleteFirst 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

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

ReplyDeletesigma(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.

Congratulations, Laura Leonard.

ReplyDeleteJust for the record.

DeleteThis comment has been removed by the author.

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

ReplyDeleteOk, on to the next puzzle, please.

The new puzzle came up a bit ago.

ReplyDeleteNext 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

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

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

ReplyDeleteI happen to know a certain king would be

withunhappyof the three-word sayings I submitted. He even proposed anonethree-word phrase to replace it, but unfortunately his improvement fails the criteria of the puzzle.improved