HSC 2015 MX2 Permutations & Combinations Marathon (archive) (1 Viewer)

[pororo]

Re: 2015 permutation X2 marathon

nvm

 

[braintic]

Re: 2015 permutation X2 marathon

A man has $1 to his name.
Every day he either gains $1 (with probability p) or loses $1 (with probability 1-p).
This stops if and when he goes broke.

Find, as a function of p, the probability P that the man will eventually go broke.

Let P_n be the probability that the man goes broke, given that he currently has $n.

To go broke starting from $1, he must either:
(1) lose $1 with probability (1-p);
OR
(2) gain $1 with probability p AND then go broke from a new starting point of $2.

That is:
P₁ = (1-p) + p.P₂

To go broke from a starting point of $2, regardless of how much money he accumulates from there, he must first pass through $1.
The probability of going from $2 to $1 must be the same as going from $1 to nothing, ie. P₁
So P₂ = P₁.P₁ (two steps of -$1 are needed)

So:
P₁ = (1-p) + p.P₁²

p.P₁² - P₁ + (1-p) = 0

Solving the quadratic gives:
P₁ = 1
OR
P₁ = (1-p)/p

The second equation doesn't give valid probabilities for p ≤ 1/2.
So the value of P₁ for p ≤ 1/2 must be 1.

It should be clear that if p = 1, then P₁ = 0. The second solution gives this value.
The second solution also gives P₁ = 1 when p = 1/2.

So the only way of getting a continuity of P₁ values as p changes is if:

P₁ = 1 for p ≤ 1/2
P₁ = (1-p)/p for p > 1/2

 

[InteGrand]

Re: 2015 permutation X2 marathon

Let P_n be the probability that the man goes broke, given that he currently has $n.

To go broke starting from $1, he must either:
(1) lose $1 with probability (1-p);
OR
(2) gain $1 with probability p AND then go broke from a new starting point of $2.

That is:
P₁ = (1-p) + p.P₂

To go broke from a starting point of $2, regardless of how much money he accumulates from there, he must first pass through $1.
The probability of going from $2 to $1 must be the same as going from $1 to nothing, ie. P₁
So P₂ = P₁.P₁ (two steps of -$1 are needed)

So:
P₁ = (1-p) + p.P₁²

p.P₁² - P₁ + (1-p) = 0

Solving the quadratic gives:
P₁ = 1
OR
P₁ = (1-p)/p

The second equation doesn't give valid probabilities for p ≤ 1/2.
So the value of P₁ for p ≤ 1/2 must be 1.

It should be clear that if p = 1, then P₁ = 0. The second solution gives this value.
The second solution also gives P₁ = 1 when p = 1/2.

So the only way of getting a continuity of P₁ values as p changes is if:

P₁ = 1 for p ≤ 1/2
P₁ = (1-p)/p for p > 1/2

How can we actually justify / be sure though that P(p) needs to be continuous? Is it just something 'obvious'?

 

[braintic]

Re: 2015 permutation X2 marathon

How can we actually justify / be sure though that P(p) needs to be continuous? Is it just something 'obvious'?

That was my worry too. I know the answer is correct, but I'm not sure how to justify that, other than it seems to be common sense (and yes, I know a lot of things that seem to be common sense turn out not to be true).

 

[braintic]

Re: 2015 permutation X2 marathon


p and q are real numbers.
p is randomly chosen on the interval -a ≤ p ≤ a
q is randomly chosen on the interval 0 ≤ q ≤ b

What is the probability that the equation x² + px + q = 0 has real roots ?


[Note: This is technically a 2 unit question]

 

[awesome-0_4000]

Re: 2015 permutation X2 marathon

In how many ways can a coin be tossed n times such that no two consecutive tosses are heads?

 

[kawaiipotato]

Re: 2015 permutation X2 marathon

The amount of heads (H) and the amount of tails (T) must fall under the condition H =< T for no consecutive heads to occur.
Consider the case when n T's are thrown (n = even)
= 1 way

n-1 T's and 1 H is thrown
= n!/(n-1)! = n ways

n-2 T's and 2 H is thrown
= (n-1)C(2)

n-3 T's and 3H is thrown
= (n-2)C(3)

.
.
.

n/2 H's and n/2 T's
= (n/2 + 1)C(n/2)

Summing, the total ways = 1 + n + (n-2)C(3) + (n-3)C4 + ... + (n/2 + 1)C(n/2)

= summation from k=0 to k=n/2 of (n+1 -k)C(k)
... which I don't know how to evaluate lol
not even sure if this is right can someone check?

 

[InteGrand]

Re: 2015 permutation X2 marathon

 

[InteGrand]

Re: 2015 permutation X2 marathon

The amount of heads (H) and the amount of tails (T) must fall under the condition H =< T for no consecutive heads to occur.
Consider the case when n T's are thrown (n = even)
= 1 way

n-1 T's and 1 H is thrown
= n!/(n-1)! = n ways

n-2 T's and 2 H is thrown
= (n-1)C(2)

n-3 T's and 3H is thrown
= (n-2)C(3)

.
.
.

n/2 H's and n/2 T's
= (n/2 + 1)C(n/2)

Summing, the total ways = 1 + n + (n-2)C(3) + (n-3)C4 + ... + (n/2 + 1)C(n/2)

= summation from k=0 to k=n/2 of (n+1 -k)C(k)
... which I don't know how to evaluate lol
not even sure if this is right can someone check?

Fewer heads than tails does not guarantee no consecutive heads, e.g. we could have H,H,T,T,T,T,T.

 

[kawaiipotato]

Re: 2015 permutation X2 marathon

Fewer heads than tails does not guarantee no consecutive heads, e.g. we could have H,H,T,T,T,T,T.

For those cases I used the insertion method
which would mean it's 6C2 for that example

 

[InteGrand]

Re: 2015 permutation X2 marathon

For those cases I used the insertion method
which would mean it's 6C2 for that example

Oh right, I think I misunderstood your method before.

 

[kawaiipotato]

Re: 2015 permutation X2 marathon

Oh right, I think I misunderstood your method before.

Is my method valid for n= even?

 

[awesome-0_4000]

Re: 2015 permutation X2 marathon

This is the approach I was looking for, although I wasn't sure if suggesting recursion made it too easy.

 

[InteGrand]

Re: 2015 permutation X2 marathon

Is my method valid for n= even?

Yes haha.

 

[kawaiipotato]

Re: 2015 permutation X2 marathon

Yes haha.

Is there a way to simplify the summation? Like starting off with a binomial expansion and then substituting some value in

 

[braintic]

Re: 2015 permutation X2 marathon

Fibonacci (n+2)

 

[braintic]

Re: 2015 permutation X2 marathon


Now my question again:

p and q are real numbers.
p is randomly chosen on the interval -a ≤ p ≤ a
q is randomly chosen on the interval 0 ≤ q ≤ b

What is the probability that the equation x² + px + q = 0 has real roots ?


At its core, this is not hard. It involves discriminant and area under a curve.
There is just one hitch.

 

[rand_althor]

Re: 2015 permutation X2 marathon

Question I saw: In a chess tournament, n women and 2n men participated, and each one of them played only one game with everybody else. The ratio of the number of games won by women to the number of games won by men is 7:5. Find the number of men that participated in the tournament if no game was over in a tie.
Answer: 6 men

 

[braintic]

Re: 2015 permutation X2 marathon

Question I saw: In a chess tournament, n women and 2n men participated, and each one of them played only one game with everybody else. The ratio of the number of games won by women to the number of games won by men is 7:5. Find the number of men that participated in the tournament if no game was over in a tie.
Answer: 6 men

Is the aim here to block out my questions?

 

[Drsoccerball]

Re: 2015 permutation X2 marathon

Is the aim here to block out my questions?

Are we assuming theres n is even otherwise one person doesnt play another ?