1995 Cssa 4u Q8 (1 Viewer)

[adzy]

Found this in my brother's stack of old trial papers. I found this test a higher standard than anything else I've ever done (consistent high standard throughout)

Just a note, the examiners are Graham Arnold and Denise Arnold. Heh.

Q8
n letters L1, L2, L3, ..., Ln are to be placed at random into n addressed envelopes E1, E2, E3,...,En, each bearing a different address, where Ei bears the correct address for letter Li, i= 1,2,3,...n

Let Un be the number of arrangements where no letter is placed in the correct envelope, for n a positive integer, n>= 2

i) Show U2 = 1 and U3= 2
ii) Deduce that U_k+1 = k(U_k + U_(k-1)), k=4,5,6...
iii) Use results from i) and ii) to calculate U_4 and U_5
iv) Show by mathematical induction that

U_n = n![ 1/2! - 1/3! + 1/4! - ...+(-1)^n * 1/n! ], n=2,3,4...

v) If there are 5 letters and envelopes:
a) Explain why probability no letter is placed in the correct envelope is U_5/120 and calculate this probability as a fraction
b) Show probability that exactly one letter is placed in the correct envelope is 5U_4 / 120 and calculate this probaiblity as a fraction
c) Find the probability exactly 2 letters are placed in the correct envelopes

vi) Deduce that summation k = 2 to n of [N choose K] * U_k = n!-1

 

[Stefano]

This is one of those that are meant to be skipped. It's a trap! RUN!!

 

[KFunk]

i) Show U2 = 1 and U3= 2
ii) Deduce that U_k+1 = k(U_k + U_(k-1)), k=4,5,6...
iii) Use results from i) and ii) to calculate U_4 and U_5
iv) Show by mathematical induction that

U_n = n![ 1/2! - 1/3! + 1/4! - ...+(-1)^n * 1/n! ], n=2,3,4...

i) This is pretty simple. If you have two letters and two envelopes there is only one way to get them messed up.

If you have three letters and three envelopes lined up (for the sake of visualization) then 2 letters can go in the first envelope, 1 in the next and 1 in the next.

ii) Let me think on this.

iii) You can do this pretty easily since you already have U2 and U3 given to you.

iv)

U_n = n![ 1/2! - 1/3! + 1/4! - ...+(-1)^n * 1/n! ]

n(U_n +U_n-1) = U_n+1 so,

U_n+1
= n![ n/2! - n/3! + n/4! - ...+(-1)ⁿ * n/n! ] + n![ 1/2! - 1/3! + 1/4! - ...+(-1)^n-1 * 1/(n-1)!]

= n![ (n+1)/2! - (n+1)/3! + ... + (-1)^n-1*(n+1)/(n-1)! + (-1)ⁿ * n/n!)

{note: n/n! = (n+1)/n! - 1/n! = (n+1)/n! - (n+1)/(n+1)! }

= (n+1)![ 1/2! - 1/3! + 1/4! - ...+(-1)ⁿ⁺¹*1/(n+1)! ]

U_n ==> U_n+1 yada yada...

 

[KFunk]

v) If there are 5 letters and envelopes:
a) Explain why probability no letter is placed in the correct envelope is U_5/120 and calculate this probability as a fraction
b) Show probability that exactly one letter is placed in the correct envelope is 5U_4 / 120 and calculate this probaiblity as a fraction
c) Find the probability exactly 2 letters are placed in the correct envelopes

a) The total number of ways to arrange 5 distinct letters into 5 distinct envelopes is 5! = 120

# ways to put all letters in incorrect envelopes = U₅

P(all incorrect) = (ways to arrange them incorrect)/(total # ways to arrange them)

∴ P(all incorrect) = U₅/120


b) Consider the group of 5 letters. There are 5 ways in which we can pick a single letter from this group. This letter is then put in the correct envelope. The # ways that the remaining four letters can be placed in the incorrect evelopes = U₄.

∴ P(1 correct) = 5U₄/120 = 1/4 (or something like that)


c) Using a similar method to above: there are ⁵C₂ (i.e. 10) ways to seperate the 5 letters into a group of two and a group of three. The two letters are then placed in their correct envelopes. The # of ways that the remaining three letters can be placed in the incorrect envelopes = U₃/

∴ P(2 correct) = 10U₃/120 = 1/6

 

[KFunk]

vi) Deduce that ∑ (k = 2 to n) ⁿC_k U_k = n! - 1

What this is doing is summing up all the individual cases:

When k=2, ⁿC₂ U₂ = the number of ways in which the letters can be arranged where two letters are out of place.

When k=3, ⁿC₃ U₃ = the number of ways in which the letters can be arranged where three letters are out of place.

...

When k=n, ⁿC_n U_n = the number of ways in which the letters can be arranged where all 'n' letters are out of place.


Logically it is impossible for only one letter to be out of place which is why they skip the k=1 case. However, it is possible for all the letters to be in the right place (there is only one way this can happen) and this is not included in the sum .

Knowing that the total number of arrangements = n! and that the above sum acounts for all arrangements except for the case where all letters are in the right place (hence 1 must be subtracted from n!) then it is safe to say that:

∑ (k = 2 to n) ⁿC_k U_k = n! - 1

 

[adzy]

Thanks dude. Haha, if I see that q8 I think i just panic and not even try it.

ii) Deduce that U_k+1 = k(U_k + U_(k-1)), k=4,5,6...

Any headway on this?

 

[adzy]

Thanks dude.

ii) Deduce that U_k+1 = k(U_k + U_(k-1)), k=4,5,6...

Still any headway on this?

 

[KFunk]

Thanks dude.

ii) Deduce that U_k+1 = k(U_k + U_(k-1)), k=4,5,6...

Still any headway on this?

I've come to that answer a couple times using shaky-common sense but not much of it had strong mathematical grounding. This is the best I could come up with but it's still a little shonky:

Consider the case with (k+1) letters and (k+1) envelopes... there are 'k' letters which can go into E₁. Let the one which goes into E₁ be L_q [q = 2,3...(k+1)]. From here we can subdivide into two cases.

Case 1 - L₁ is put into E_q. This leaves (k-1) letters each of which have a corresponding envelopes (i.e. for every L_i there is an E_i). There are U_k-1 ways to arrange these remaining (k-1) letters into the (k-1) envelopes.

Case 2 - L₁ is *not* put into E_q. Once more we have (k-1) letters/envelopes other than (L₁ / E_q). For all intents and purposes we can treat E_q as if it were E₁ in this situation since we cannot place L₁ in it. Hence we can treat this like the arrangment of 'k' envelopes (for L_i we have E_i). This yields U_k arrangments in this situation.

Combining case 1 and case 2 we get (kU_k-1 + kU_k) since each case begins with k possible selections.

= k(U_k + U_k-1)

 

[KFunk]

Anyhow, that one bugged me for a bit. I'd like to see someone come up with a more elegant solution for it. Btw, I think when I calculated the values of a couple of the U₄/U₅ terms I may have been unco and stuffed them up (after saying that part was easy ).

 

[SeDaTeD]

U_n = n![ 1/2! - 1/3! + 1/4! - ...+(-1)^n * 1/n! ] tends to n!/e as n gets large. You can see this as the term in the bracket are the first n terms of a power series expansion of e^-1 (missing the 1/0! - 1/1! terms, but these are zero), if you have come across this before. Just something you may be interested in.

 

[Stefano]

Good work guys.

 

[KFunk]

U_n = n![ 1/2! - 1/3! + 1/4! - ...+(-1)^n * 1/n! ] tends to n!/e as n gets large. You can see this as the term in the bracket are the first n terms of a power series expansion of e^-1 (missing the 1/0! - 1/1! terms, but these are zero), if you have come across this before. Just something you may be interested in.

Hmm, that's pretty cool. I've seen the e^x power series before (I have a pretty rough understanding of how it comes from the taylor series) but I didn't notice it here. Thanks for pointing it out.

 

[acmilan]

That series in question is actually e^-x, which is basically the same thing as e^x except you replace x by -x in the taylor/maclaurin series

edit: now that i think of it, it doesnt really make a difference in the example above