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:
.jpeg/220px-Bernoulli_Nicolaus(II).jpeg)
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?
I should know the answer to this one...or to be able to figure it out.
ReplyDeleteBut I can't think of it right now.
Letters: A B C D E F G
ReplyDeleteEnvelopes 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
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.
ReplyDeleteFor 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.
I tried this, and maybe the sequence is instructive:
ReplyDelete6 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
A program to count the permutations also gives 1854.
ReplyDeleteAnd the prize goes to James!
ReplyDeleteIn case you're curious, the equation for this is
n!((1/(2!)-1/(3!)+1/(4!)-1/(5!)+1/(6!)-1/(7!))
Well, sometime after I admitted inability to think my way through it (at that moment), I hit a search engine.
DeleteAnd 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...
I would never have gotten there.
ReplyDelete