Inspired by jd2718′s Thanksgiving Puzzles, here’s a Thanksgiving puzzle created by yours truly (though inspired by one I heard a while back):
It’s Thanksgiving Day and you’re hosting dinner for your large extended family of 30 people. In the interest of organization, you’ve created nametags for each person and placed them around the table. But when everybody goes to sit down at the table, there’s a problem: Great Aunt Ermintrude, who is 104, has already sat down. However, being a bit senile, she has forgotten her own name and just picked a seat at random! Not wanting to disturb her, everybody decides to just let her stay there. Each person, as he comes to the table, will sit at his own seat if it is available, but if it is not, he’ll just pick a seat at random from the ones that are left. You, being the host, are the last one to sit down. What is the probability that you’ll sit at your correct place?
[Note that there is a small possibility Great Aunt Ermintrude has sat at her own place after all.]
Well, I didn’t know what to do, so I pretended I was one of my students. I solved a series of smaller problems, for Gertrude and me, and then the two of us with one more person, than 4 in total, then 5 in total…. Even these simple problems were nice exercises in conditional probability.
But you know what was strange? I wonder why that happens. I can’t see how to induce it.
Jonathan
That’s what I always recommend, solving a simpler problem. But there is a nice general solution that’s not hard to prove with the right insight.
I have to post lessons or an outline from my high school combinatorics class… they learn a little bit of counting, but they learn an awful lot about how to attack strange looking problems…
(so much so, in fact, that I find kids forgetting algorithms and shortcuts, but happily attacking what should be routine questions with perfectly reasonable (if unreasonably long) problem solving approaches)
(eg, last test, I threw up front a couple of old, easy questions, just to start them off with some gimmes. One was, “how many 3 digit numbers do not include the digit 3?” and a few kids slogged through to 900 – 100 – 8*(19) …)
You can think of this problem while 100 people board a plane.
Oh, I didn’t realize you’d posted this! (Though the airplane version is the way I first heard the problem; I just thought I’d rephrase it with a Thanksgiving theme.)
No problem. And that one has a link in the comments to a solution.
Many years ago, I solved this problem using products, induction, and the whole shebang. But I can’t for the life of me remember how it went. Anyways, I’ve just realized that you can use a symmetry argument, and all that extra math is unnecessary.
Ouch! At least you used induction–I told this problem to someone yesterday and he started trying to solve it without even that. Of course the trick with these problems is to realize that if the only way to do it was some horribly long and inelegant process, I wouldn’t be asking the question in the first place.
In this case, the real trick (but an easy one) is in proving why the symmetry argument works.
Car Talk? This was Click and Clack???
[...] thing as how we solved the airplane seat problem almost two years ago, and Susan’s related Thanksgiving seating problem. Then each permutation in one collection is paired with one in the other collection, and the two in [...]
1- [1/30 + (29/30 x 1/29) + (28/29 x 1/28)... + (2/3 x 1/2)]