HSC 2016 MX2 Combinatorics Marathon (archive) (2 Viewers)

glittergal96 · Nov 14, 2015

Re: HSC 2016 MX2 Combinatorics Marathon

A potentially biased coin produces a H when flipped with probability p.

If you flip this coin repeatedly until you get k H's in a row (k being an arbitrary positive integer), what is the average number of flips you will have to do in total?
Your answer should depend on both p and k.

(If you find this question too difficult, try just solving the k=1 and/or k=2 case, which may be easier for you to think about.)

glittergal96 · Nov 14, 2015

Re: HSC 2016 MX2 Combinatorics Marathon

Also note that we are taking the average of a quantity that can take infinitely many positive values (the process might take an arbitrarily large number of flips to terminate). This is done exactly the same way as averaging something that only takes finitely many values, the sum just contains infinitely many terms.

$X_\textrm{ave}=\sum_{n=1}^\infty n\cdot\mathcal{P}(X=n).$

InteGrand · Nov 14, 2015

Re: HSC 2016 MX2 Combinatorics Marathon

glittergal96 said:
A potentially biased coin produces a H when flipped with probability p.

If you flip this coin repeatedly until you get k H's in a row (k being an arbitrary positive integer), what is the average number of flips you will have to do in total?
Your answer should depend on both p and k.

(If you find this question too difficult, try just solving the k=1 and/or k=2 case, which may be easier for you to think about.)

$Is the answer just $\frac{K}{p}$?$

$Let the expected number of tosses be $X_K$, noting $X_0 = 0$, $X_1 = \frac{1}{p}$ (expectation of geometric distribution) if one is uncomfortable with $X_0$. Then note that $X_K = \frac{1}{p}+X_{K-1}$ for $K\geq 1$ (or $K\geq 2$, doesn't matter much) (expected no. of tosses to get the first Head, plus expected no. of tosses to get next $K-1$). So this is an arithmetic progression formula with common difference $\frac{1}{p}$, so $X_K = X_0 + K\cdot \frac{1}{p}\Rightarrow X_K = \frac{K}{p}$, as $X_0 = 0$ (same result occurs if we use $X_K = X_1 + (K-1)\cdot \frac{1}{p}$).$

glittergal96 · Nov 14, 2015

Re: HSC 2016 MX2 Combinatorics Marathon

Not quite.

1/p is indeed correct for k=1.

However I think you have misinterpreted the problem judging by your induction.
A sequence terminates after k consecutive heads, rather than just k heads in total.

InteGrand · Nov 14, 2015

Re: HSC 2016 MX2 Combinatorics Marathon

glittergal96 said:
Not quite.

1/p is indeed correct for k=1.

However I think you have misinterpreted the problem judging by your induction.
A sequence terminates after k consecutive heads, rather than just k heads in total.

Right, misread it, didn't see the "in a row".

InteGrand · Nov 14, 2015

Re: HSC 2016 MX2 Combinatorics Marathon

$Well letting $X_K$ be the expected no. of tosses to get $K$ H's in a row \Big{(}with $X_1 = \frac{1}{p}$\Big{)}, we can set up the following recurrence:$

$$X_K = \left(X_{K-1}+1 \right)\cdot p + \left(X_{K-1}+1 + X_K \right)\cdot \left(1-p\right),K\geq 2$.$

$(I.e., get to $\left(K-1\right)$ H's in $X_{K-1}$ tosses on average, and then you need 1 more toss with probability $p$ (corresponding to getting H on the next toss), or you need $1+X_K$ more with probability $1-p$, corresponding to failing to get H on the next toss.)$

$\begin{align*}\therefore X_K &= pX_{K-1}+p+X_{K-1}-pX_{K-1}+1-p+X_K -pX_K \\ \Rightarrow pX_K &= 1 + X_{K-1} \quad (\text{cancelling out some terms and rearranging}) \\ \Rightarrow X_K &= \frac{1}{p}+\frac{1}{p}X_{K-1},K\geq 2,X_1 = \frac{1}{p}.\end{align*}$

$It is easy to show by repeatedly plugging in to the recurrence that this recurrence and initial condition implies that $X_K = \frac{1}{p}+\frac{1}{p^2}+\frac{1}{p^3}+\cdots +\frac{1}{p^K}$.$

$Using G.P. sum formula for $p\neq 1$ and simplifying a bit, we have that $X_K = \frac{\left(\frac{1}{p} \right)^K -1}{1-p}$ for $p\in (0,1)$, and $X_K = K$ if $p=1$ (as expected; if we're guaranteed H each time, we expect $K$ tosses to get $K$ H's in a row). If $p$ is 0, we'd have an undefined expected value.$

glittergal96 · Nov 14, 2015

Re: HSC 2016 MX2 Combinatorics Marathon

Exactly, well done

.

braintic · Nov 14, 2015

Re: HSC 2016 MX2 Combinatorics Marathon

So this has now become a thread for ex-students?

InteGrand · Nov 14, 2015

Re: HSC 2016 MX2 Combinatorics Marathon

$Here's a question:$

$Let $n,m,r$ be positive integers with $n,m\geq r$.$

$Show that $C(m,r)\cdot P(n,r)=P(m,r)\cdot C(n,r)$, where $C(n,r)$ is ``$n$ choose $r$'' ($^n C_r$) and $P(n,r)$ is $^nP_r$.$

$Bonus: provide a combinatorial interpretation.$

porcupinetree · Nov 23, 2015

Re: HSC 2016 MX2 Combinatorics Marathon

A question for the actual 2016'ers:

4 letters of the word METRONOME are chosen and arranged to form a word. How many possible different words are there?

InteGrand · Nov 23, 2015

Re: HSC 2016 MX2 Combinatorics Marathon

porcupinetree said:
A question for the actual 2016'ers:

My Q was also directed at current HSC students.

porcupinetree · Nov 23, 2015

Re: HSC 2016 MX2 Combinatorics Marathon

InteGrand said:
My Q was also directed at current HSC students.

Haha soz, glanced over it and it appeared like it was one of the university level questions that commonly arise among the 2016 threads

Paradoxica · Nov 26, 2015

Re: HSC 2016 MX2 Combinatorics Marathon

Prove the binomial theorem using calculus and induction.

Drsoccerball · Nov 26, 2015

Re: HSC 2016 MX2 Combinatorics Marathon

Paradoxica said:
Prove the binomial theorem using calculus and induction.

Should this really be in this thread?

calamebe · Nov 29, 2015

Re: HSC 2016 MX2 Combinatorics Marathon

InteGrand said:
$Here's a question:$

$Let $n,m,r$ be positive integers with $n,m\geq r$.$

$Show that $C(m,r)\cdot P(n,r)=P(m,r)\cdot C(n,r)$, where $C(n,r)$ is ``$n$ choose $r$'' ($^n C_r$) and $P(n,r)$ is $^nP_r$.$

$Bonus: provide a combinatorial interpretation.$

http://m.imgur.com/NBOOw6E

calamebe · Nov 29, 2015

Re: HSC 2016 MX2 Combinatorics Marathon

porcupinetree said:
A question for the actual 2016'ers:

4 letters of the word METRONOME are chosen and arranged to form a word. How many possible different words are there?

http://m.imgur.com/BUMOEKp

braintic · Dec 1, 2015

Re: HSC 2016 MX2 Combinatorics Marathon

calamebe said:
http://m.imgur.com/BUMOEKp

Not correct. Interestingly, I get an anagram of that answer: 738

Drsoccerball · Dec 1, 2015

Re: HSC 2016 MX2 Combinatorics Marathon

$$ No repeats $ = ^6P_4$

$$ 1 repeat $ \frac{\binom{3}{1}\binom{5}{2}4!}{2!}$

$$ 2 repeats $ \frac{\binom{3}{2}4!}{2!2!}$

$$ All cases $ = 738$

InteGrand · Dec 2, 2015

Re: HSC 2016 MX2 Combinatorics Marathon

$\noindent \textbf{NEW QUESTION}$

$\noindent Alice and Bob play a game where they each toss a coin repeatedly. Alice tosses a coin that has a probability of coming up heads of $p_1 \in (0,1)$. Bob tosses a coin that comes up heads with probability $p_2 \in (0,1)$. On each turn of the game, each player tosses his or her coin and records the result (and each player can see both coins), keeping a running total of the number of heads each player has tossed. The game can end in one of two ways:$

$\noindent (1) after some turn, Alice reaches a total of $m$ heads, where $m$ is some fixed predetermined positive integer; or$

$\noindent (2) after a certain turn, Bob's running total of heads exceeds Alice's by $k$, where $k$ is some fixed predetermined positive integer (known to both).$

$(Note that it is impossible for both of these to occur simultaneously after a turn.) If (1) happens before (2) has happened, the game ends and Alice wins. If (2) happens before (1) happens, Bob wins.$

$\noindent Find an expression in terms of $m,k,p_1,$ and $p_2$ of Alice winning the game (if possible!).$

$\noindent As an example, the game could pan out as follows. Say $m$ (the total Alice needs to win) is 2 and $k$ (the amount Bob needs to overtake Alice by to win) is 3. The results by turn are listed below:$

$\noindent $\bullet$ Alice: $\mathcal{T}$, $\mathcal{T}$, $\mathcal{H}$ (Alice on 1 head), $\mathcal{H}$ (\textbf{Alice on 2 heads})$

$\noindent $\bullet$ Bob: $\mathcal{H}$ (so Bob ahead by 1), $\mathcal{T}$ (Bob ahead by 1), $\mathcal{H}$ (Bob ahead by 1), $\mathcal{H}$ (Bob ahead by 1)$

$\noindent In this game, Alice wins after Turn 4 because she reaches $m=2$ heads here. The game did not end before this because Bob did not get to a lead of $k=3$ before this, and Alice did not reach $2$ heads before this.$

davidgoes4wce · Feb 10, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

If all the letters of the word REARRANGE are arranged at random, what is the probability that the R's are together?

Ans: 1/12

HSC 2016 MX2 Combinatorics Marathon (archive) (2 Viewers)

Active Member

Active Member

Well-Known Member

Active Member

Well-Known Member

Well-Known Member

Active Member

Well-Known Member

Well-Known Member

not actually a porcupine

Well-Known Member

not actually a porcupine

-insert title here-

Well-Known Member

Active Member

Active Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

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