## Wednesday, February 6, 2013

### Wednesday Brain Teaser 2-6-12

All of my engineer readers are probably quite familiar with the Bernoulli family, or at least their principle and equation.  For those of you who aren't, they were a Swiss family of mathematicians who sat around and came up with all sorts of interesting stuff, including a large part of fluid dynamics.

Anyway, I knew a lot of things carried the name Bernoulli (Bernoulli principle, Bernoulli numbers, Bernoulli's equation, Bernoulli distribution...they ran a damn franchise), but I didn't know until researching today's problem that it wasn't just one really prolific guy, but rather a family affair.  That made me feel a bit better about things.

This all relates because today's problem apparently was a favorite of Nicolaus Bernoulli (1695-1720), who I take it was the looker of the family:

So this lovely family invented a lot of tricky math stuff that helped us understand the world better, but made my sophomore year GPA suffer a bit more than was strictly necessary.  So now dear reader, I will let them loose on you:

A correspondent writes seven letter and addresses seven envelopes, one for each letter.  In how many ways can all of the letters be placed in wrong envelopes?

1. I should know the answer to this one...or to be able to figure it out.

But I can't think of it right now.

2. Letters: A B C D E F G
Envelopes 1 2 3 4 5 6 7

A can be put incorrectly in 2-7, so there's 6 options there.

B can be put in 1, 3-7 (i.e. 6 options), if A was put in 2, Otherwise, there are 5 options

If A or B was put in 3, C can go in 5 places. Otherwise, 4 places

If A, B or C was put in 4, D can go in 4 places, otherwise 3

If A,B,C or D were put in 5, E can go in 3 places, otherwise 2

If any of A-E were put in 6, F can go in 2 places, otherwise 1

G can go in 1 place

I am running short on time, but I would guess 6x5x4x3x2 + 6+5+4+3+2 -> 740 different combinations

3. I don't think it's that clean. I'm figuring 7! minus a whole bunch of werd stuff is going to show up somewhere, and that will be much larger.

For one letter there are 0 wrong arrangements. For 2 letters, one wrong arrangement. For 3 letters, 2 wrongs. For 4 letters, 9 possible wrong arrangements. I started working 5 by hand, and the number is over 40, but my head hurts and I may have missed something.

So what's got 5!(120) minus stuff, or 4! (24) plus stuff, and comes out to something around 45? Dunno. It must be a series, so I can't intuit it in from there. I'm letting this spin for qwhile.

4. I tried this, and maybe the sequence is instructive:
6 cases for the first, 5 for the second, 4 .. Wait a bit--suppose the first and second just swapped? Start from the beginning.

1 letter, always right, =0
2 letters, one way to goober it up
3 letters, 2 ways
4 letters: ah. 3*2=6 ways of cycling the 4 around, but then 3 ways of doing 2+2. (=9)

So partitioning is the way to go. A partition of 1 always maps the letter into the right envelope, so there's no answers with partition 1.

7 can be
a "cycle" of 7: with 1 case, which has 6*5*4*3*2 permutations
a "cycle" of 5 plus a "cycle" of 2: with 7*6/2 cases and 4*3*2 permutations
a "cycle" of 4 plus a "cycle" of 3: where I'm going to cheat and include the 2+2 in the 4, with 7*6*5/6 cases and (2 {for the 3} * 9 {for the 4}) permutations

That gives me 720+504+630=1854

5. A program to count the permutations also gives 1854.

6. And the prize goes to James!

In case you're curious, the equation for this is
n!((1/(2!)-1/(3!)+1/(4!)-1/(5!)+1/(6!)-1/(7!))

1. Well, sometime after I admitted inability to think my way through it (at that moment), I hit a search engine.

And found that formula. Plus a recursive one that I like better.

But I figured I would wait, and see if anyone else got close.

This was definitely a challenging puzzle, but now I think that I should have been able to solve it without a search engine...

7. I would never have gotten there.