HSC 2015 MX2 Permutations & Combinations Marathon (archive) (2 Viewers)

Drsoccerball · Oct 2, 2015

Re: 2015 permutation X2 marathon

Braintic that new font you use is dope :O how do you use it

seanieg89 · Oct 2, 2015

Re: 2015 permutation X2 marathon

Nope, for this particular question we don't need calculus, although calculus will certainly generalise better.

The same method you proposed should work for the sphere should it not?

$Let $\phi$ be the angle of latitude measured from the north pole at $\phi=0$ down to the south pole at $\phi=\pi.$ Let t be the variable we are going to select at random in an interval (say $[0,1]$). \\ \\ Then \\ \\ $\frac{A_{\textsf{cap}}(\phi)}{4\pi}=t\Rightarrow 1-\cos(\phi)=2t \Rightarrow \phi(t)=\cos^{-1}(1-2t).$$

braintic · Oct 2, 2015

Re: 2015 permutation X2 marathon

seanieg89 said:
Nope, for this particular question we don't need calculus, although calculus will certainly generalise better.

The same method you proposed should work for the sphere should it not?

$Let $\phi$ be the angle of latitude measured from the north pole at $\phi=0$ down to the south pole at $\phi=\pi.$ Let t be the variable we are going to select at random in an interval (say $[0,1]$). \\ \\ Then \\ \\ $\frac{A_{\textsf{cap}}(\phi)}{4\pi}=t\Rightarrow 1-\cos(\phi)=2t \Rightarrow \phi(t)=\cos^{-1}(1-2t).$$

Are you trying to map [0,1] to [0,pi/2] ?
Because t=1 leads to arccos(-1).
Did you mean 2π (not 4π) ?

I shouldn't have said 'spherical cap'. I meant 'spherical segment'.
It seems that the area of the surface of a segment between the equator and a latitude phi is:

$2\pi R^2 \sin \phi$

(I wasn't using this formula before - I only just discovered it)

So I'm now getting:

$\frac{2\pi\sin\phi}{2\pi}=t$

$\phi=\sin^{-1} t$

braintic · Oct 2, 2015

Re: 2015 permutation X2 marathon

Drsoccerball said:
Braintic that new font you use is dope :O how do you use it

I'm not sure whether "dope" is a good or bad thing. It doesn't sound good.

All I'm doing is changing the font and font size using the menu at the top of the reply box.

InteGrand · Oct 2, 2015

Re: 2015 permutation X2 marathon

braintic said:
I'm not sure whether "dope" is a good or bad thing. It doesn't sound good.

All I'm doing is changing the font and font size using the menu at the top of the reply box.

I didn't think it sounded good either on first hearing, but I realised it probably was from the ":O how do you use it" part.

seanieg89 · Oct 2, 2015

Re: 2015 permutation X2 marathon

braintic said:
Are you trying to map [0,1] to [0,pi/2] ?
Because t=1 leads to arccos(-1).
Did you mean 2π (not 4π) ?

I shouldn't have said 'spherical cap'. I meant 'spherical segment'.
It seems that the area of the surface of a segment between the equator and a latitude phi is:

$2\pi R^2 \sin \phi$

(I wasn't using this formula before - I only just discovered it)

So I'm now getting:

$\frac{2\pi\sin\phi}{2\pi}=t$

$\phi=\sin^{-1} t$

No, I am mapping [0,1] to [0,pi], the full sphere (hence the normalisation by 4pi rather than 2pi).

Your new formula is equivalent to mine, (as one might guess from their similar forms), you are just basing yours at the origin as opposed to mine which was based at the north pole.

There are lots of ways to map a rectangle to a sphere in a way that does not distort area.

(Also note that it makes no difference to consider spherical caps vs spherical segments, as passing between the formulae for these guys is straightforward.)

braintic · Oct 2, 2015

Re: 2015 permutation X2 marathon

seanieg89 said:
No, I am mapping [0,1] to [0,pi], the full sphere (hence the normalisation by 4pi rather than 2pi).

Your new formula is equivalent to mine, (as one might guess from their similar forms), you are just basing yours at the origin as opposed to mine which was based at the north pole.

There are lots of ways to map a rectangle to a sphere in a way that does not distort area.

(Also note that it makes no difference to consider spherical caps vs spherical segments, as passing between the formulae for these guys is straightforward.)

Thanks for that. I hope you don't mind if I stick with my version - it seems a little more intuitive - I can practically "see" it. In fact, I am wondering if there is a geometric connection to Archimedes' result.

seanieg89 · Oct 2, 2015

Re: 2015 permutation X2 marathon

braintic said:
Thanks for that. I hope you don't mind if I stick with my version - it seems a little more intuitive - I can practically "see" it. In fact, I am wondering if there is a geometric connection to Archimedes' result.

Of course I don't mind

, everyone has their own ways of seeing things and it is a quite trivial matter to pass between the two in this case.

There are several differing conventions for spherical coordinates even without the modification to preserve area.

If you are referring to http://mathworld.wolfram.com/ArchimedesHat-BoxTheorem.html this theorem is just equivalent to the fact that specifying a longtitudinal coordinate $\theta$ and a perpendicular height above the equator z is another way of mapping a rectangle to the sphere in a way that does not distort area.

braintic · Oct 3, 2015

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.

Drsoccerball · Oct 3, 2015

Re: 2015 permutation X2 marathon

braintic said:
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.

$P = \frac{1-p}{p^2-p+1}$

braintic · Oct 3, 2015

Re: 2015 permutation X2 marathon

Drsoccerball said:
$P = \frac{1-p}{p^2-p+1}$

Not correct ... but at least it is a sensible answer - it gives you what you would expect for p=0 and p=1.

I can't comment further without working or some idea of what you were thinking.
But ... it's bed time for me.

Paradoxica · Oct 3, 2015

Re: 2015 permutation X2 marathon

braintic said:
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.

I got $\sum_{\mathbb{Z}^+}{\dbinom{2n+1}{n}p^n(1-p)^{n+1}}$

(Sum goes over the set of positive integers, if you were confused)

I don't know how to prove this, and I don't know how to clean this up into a nice closed expression.

InteGrand · Oct 3, 2015

Re: 2015 permutation X2 marathon

braintic said:
Not correct ... but at least it is a sensible answer - it gives you what you would expect for p=0 and p=1.

I can't comment further without working or some idea of what you were thinking.
But ... it's bed time for me.

$I haven't studied random walks or martingales much, but from something I think I read/heard about them before, if $p\leq \frac{1}{2}$, then $P=1$, right (i.e. he will almost surely go broke) (makes intuitive sense)?$

Drsoccerball · Oct 3, 2015

Re: 2015 permutation X2 marathon

Paradoxica said:
I got $\sum_{\mathbb{Z}^+}{\dbinom{2n+1}{n}p^n(1-p)^{n+1}}$

(Sum goes over the set of positive integers, if you were confused)

I don't know how to prove this, and I don't know how to clean this up into a nice closed expression.

What I did was him being bankrupt on the :

First day : (1-p)

third day: p(1-p)^2

fifth day: p^2(1-p)^3
...

And i summed the series and got my answer ?

Paradoxica · Oct 3, 2015

Re: 2015 permutation X2 marathon

Drsoccerball said:
What I did was him being bankrupt on the :

First day : (1-p)

third day: p(1-p)^2

fifth day: p^2(1-p)^3
...

And i summed the series and got my answer ?

That's not correct. There is more than one way to lose after the first 3 days. He could gain a bit more, like say 3 and then drop back down to zero. All these possible paths must be taken into account. Draw an arbitrarily long checkerboard, cut it at the main diagonal, and construct your infinite tree diagram on that. You will see what I mean, as the further out you go from the beginning, the more ways there are to lose. Your approach is naive, and would most likely score 0 marks. I considered your approach until I drew my own tree diagram.

InteGrand · Oct 3, 2015

Re: 2015 permutation X2 marathon

Drsoccerball said:
What I did was him being bankrupt on the :

First day : (1-p)

third day: p(1-p)^2

fifth day: p^2(1-p)^3
...

And i summed the series and got my answer ?

$I thought it was something like this:$

$Clearly he can only go broke after an odd number of days. Imagine him starting on the $y$-axis at the point $y=1$. Let $L$ denote a loss (moves down 1 position), which happens on a turn with probability $q\equiv 1-p$, and $W$ denote a win (moves up 1 unit, with probability $p\in [0,1]$).$

$To go broke after $N=2k+1$ days $(k=0,1,2,...)$, he must have exactly 1 more $L$ than $W$ as he is starting 1 higher than the ``broke zone'' ($y=0$). I.e. he must have exactly $k+1$ $L's$ and $k$ $W$'s. If $N=1$, he must have an $L$ to go broke, and this happens with probability $q$. Also, for $N=2k+1\geq 3$, the last two results must be $L$'s to go broke, and the first one a $W$. This is because if the first is an $L$, then he goes broke in fewer than 3 days, which we don't want, and also, the last two must be $L$, because since the first was a $W$, he must have gone to position $y=2$, and then to come back down to 0, he must have two consecutive $L$'s to finish.$

$So for $N\geq 3$ ($k\geq 1$), his sequence of results in order is something like: $W.....LL$, where the ``.....'' contains $k-1$ $W$'s and $k-1$ $L$'s in any order (so that before the second last $L$, he is at position $y=2$. The probability of this sequence occurring is $\binom{2k-2}{k-1}p^k q^{k+1}$ using simple perms and combs. So his overall probability of going broke would be $P =q + \sum_{k =1} ^{\infty} \binom{2(k-1)}{k-1} p^{k}q^{k+1} =q + \sum _{j=0} ^{\infty} \binom{2j}{j} p^{j+1}q^{j+2}$. But I realised now I think we could do this problem by just deriving the probability of ruin if the gambler finishes the game if he reaches a finite $\$D$ (consider this that he wins if he reaches $D$) using recurrence relations, and then take limits as $D\to \infty$ (this problem is called Gambler's Ruin). I was trying doing recurrence without a finite $D$ before, which is why it wasn't working.$

$And I think the above series approach is wrong, because $P$ should be 0 if $p\leq \frac{1}{2}$, and $P>0$ if $p>\frac{1}{2}$. This can be seen from deriving the formula using recurrences with finite $D$ and then taking limit as $D\to \infty$, but I don't want to type it up now.$

Zlatman · Oct 3, 2015

Re: 2015 permutation X2 marathon

InteGrand said:
$I thought it was something like this:$

$Clearly he can only go broke after an odd number of days. Imagine him starting on the $y$-axis at the point $y=1$. Let $L$ denote a loss (moves down 1 position), which happens on a turn with probability $q\equiv 1-p$, and $W$ denote a win (moves up 1 unit, with probability $p\in [0,1]$).$

$To go broke after $N=2k+1$ days $(k=0,1,2,...)$, he must have exactly 1 more $L$ than $W$ as he is starting 1 higher than the ``broke zone'' ($y=0$). I.e. he must have exactly $k+1$ $L's$ and $k$ $W$'s. If $N=1$, he must have an $L$ to go broke, and this happens with probability $q$. Also, for $N=2k+1\geq 3$, the last two results must be $L$'s to go broke, and the first one a $W$. This is because if the first is an $L$, then he goes broke in fewer than 3 days, which we don't want, and also, the last two must be $L$, because since the first was a $W$, he must have gone to position $y=2$, and then to come back down to 0, he must have two consecutive $L$'s to finish.$

$So for $N\geq 3$ ($k\geq 1$), his sequence of results in order is something like: $W.....LL$, where the ``.....'' contains $k-1$ $W$'s and $k-1$ $L$'s in any order (so that before the second last $L$, he is at position $y=2$. The probability of this sequence occurring is $\binom{2k-2}{k-1}p^k q^{k+1}$ using simple perms and combs. So his overall probability of going broke would be $P =q + \sum_{k =1} ^{\infty} \binom{2(k-1)}{k-1} p^{k}q^{k+1} =q + \sum _{j=0} ^{\infty} \binom{2j}{j} p^{j+1}q^{j+2}$. But I realised now I think we could do this problem by just deriving the probability of ruin if the gambler finishes the game if he reaches a finite $\$D$ (consider this that he wins) using recurrence relations, and then take limits as $D\to \infty$ (this problem is called Gambler's Ruin). I was trying doing recurrence without a finite $D$ before, which is why it wasn't working.$

I had something similar to this, except I think that

$\binom{2(k-1)}{k-1}$

assumes that you can be broke or have negative dollars, and the game will continue. Instead, I had:

$[\binom{2(k-1)}{k-1} - \binom{2(k-2)}{k-2} + \binom{2(k-3)}{k-3} - ... ] + 1$

for each term.

I'll post a picture of the tree diagram and the working out I had, and hopefully it makes some sense.

http://imgur.com/a/ZOeCv

InteGrand · Oct 3, 2015

Re: 2015 permutation X2 marathon

Zlatman said:
I had something similar to this, except I think that

$\binom{2(k-1)}{k-1}$

assumes that you can be broke or have negative dollars, and the game will continue.

Oh right, that's why my series method wasn't working.

braintic · Oct 3, 2015

Re: 2015 permutation X2 marathon

Although this is related to series, you don't need to sum an unspecified or infinite number of terms.

No solution yet, but I'll give the answer:

For p ≤ 1/2, the answer is 1 (as Integrand already suggested)

For p > 1/2, the answer is $\frac{1-p}{p}$

The only thing I will say at the moment is that they are the solutions to a quadratic equation.

pororo · Oct 3, 2015

Re: 2015 permutation X2 marathon

Catalan?

HSC 2015 MX2 Permutations & Combinations Marathon (archive) (2 Viewers)

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

-insert title here-

Well-Known Member

Well-Known Member

-insert title here-

Well-Known Member

Member

Well-Known Member

Well-Known Member

New Member

Users Who Are Viewing This Thread (Users: 0, Guests: 2)