# HSC 2016 MX2 Combinatorics Marathon (archive) (1 Viewer)

Status
Not open for further replies.

#### braintic

##### Well-Known Member
Re: HSC 2016 MX2 Combinatorics Marathon

Consider an alphabet with n different available letters.

Let P(k) be the number of ways you can use exactly k different letters in an n letter word.

i) Explain why

$\bg_white \noindent \sum_{k=1}^n P(k) \binom{n}{k} = n^n$

ii) Show that

$\bg_white \binom{n+1}{k} = \frac{n+1}{n+1-k} \binom{n}{k}$

Let the Score of a word, X, be defined as 1/(1+#(X)), where #(X) is the number of letters that were not used by the word X.

iii) Show that the sum of all the Scores, S, over all possible n letter words, is given by:

$\bg_white S = \sum_{k=1}^n \frac{P(k)}{n+1-k} \binom{n}{k}$

iv) Hence, evaluate S in closed form.
Is this a question you are posing for others, or one you need help with?

##### -insert title here-
HSC 2016 MX2 Combinatorics Marathon

Is this a question you are posing for others, or one you need help with?
I don't believe this thread is the appropriate place to ask for help.

PP

#### braintic

##### Well-Known Member
Re: HSC 2016 MX2 Combinatorics Marathon

I don't believe this thread is the appropriate place to ask for help.

PP
I'm having a heart attack. Can you call 000, or should I ask you in another thread?

##### -insert title here-
Re: HSC 2016 MX2 Combinatorics Marathon

I'm having a heart attack. Can you call 000, or should I ask you in another thread?
What?

Anyway this was co-written with the help of a friend.

#### He-Mann

##### Vexed?
Re: HSC 2016 MX2 Combinatorics Marathon

I'm having a heart attack. Can you call 000, or should I ask you in another thread?
This smart-ass......

#### pikachu975

Re: HSC 2016 MX2 Combinatorics Marathon

This smart-ass......
Pretty sure it's because Paradoxica didn't respond properly either but doesn't really matter

#### Drsoccerball

##### Well-Known Member
Re: HSC 2016 MX2 Combinatorics Marathon

This smart-ass......
What if he actually had a heart attack and we all thought it was a joke ?

#### He-Mann

##### Vexed?
Re: HSC 2016 MX2 Combinatorics Marathon

Pretty sure it's because Paradoxica didn't respond properly either but doesn't really matter

#### braintic

##### Well-Known Member
Re: HSC 2016 MX2 Combinatorics Marathon

Hmmmm ...... I actually wasn't mocking anyone. I was just being flippant .... because I felt like it at the time. I didn't consider Paradoxica's question to be mocking me.

#### Drsoccerball

##### Well-Known Member
Re: HSC 2016 MX2 Combinatorics Marathon

HSC 2016 MX2 Argument Marathon

#### InteGrand

##### Well-Known Member
Re: HSC 2016 MX2 Combinatorics Marathon

$\bg_white \noindent A group of n boys numbered 1,2,\ldots, n (n\geq 3) sit at a round table in that order. Person 1 starts with a counter and passes the counter at random (with 50-50 chance) to one of the two people sitting directly next to him. The person who gets the counter then passes it to one of the two people directly him, again with equal probabilities for each. This process continues indefinitely.$

$\bg_white \noindent For a given x \in \left\{2,\ldots ,n\right\}, find the probability p_{n}\left(x\right) that person x is the last person to receive the counter for the first time.$

Last edited:

#### calamebe

##### Active Member
Re: HSC 2016 MX2 Combinatorics Marathon

Consider an alphabet with n different available letters.

Let P(k) be the number of ways you can use exactly k different letters in an n letter word.

i) Explain why

$\bg_white \noindent \sum_{k=1}^n P(k) \binom{n}{k} = n^n$

ii) Show that

$\bg_white \binom{n+1}{k} = \frac{n+1}{n+1-k} \binom{n}{k}$

Let the Score of a word, X, be defined as 1/(1+#(X)), where #(X) is the number of letters that were not used by the word X.

iii) Show that the sum of all the Scores, S, over all possible n letter words, is given by:

$\bg_white S = \sum_{k=1}^n \frac{P(k)}{n+1-k} \binom{n}{k}$

iv) Hence, evaluate S in closed form.
I did it in my head so I may be wrong, is iv) (n+1)^n-n! or something?

#### calamebe

##### Active Member
Re: HSC 2016 MX2 Combinatorics Marathon

Ok, I'm certain my above answer is wrong. Anyway, I have time now so I might as well write a larger response to the whole question:

i) P(k)(nCk) is saying choose k letters, then arrange them in all the ways that they can form a word. So summing this from k =1 to k =n will give all the possible n lettered words, which can be expressed as n^n. And so they are equal.

ii) Simple algebra, just splitting the (n+1)! into (n+1)n! and (n+1-k)! into (n+1-k)(n-k)!.

iii) 1/(1+#(X)) will just be equal to 1/(n+1-k), as n-k words will not be used in word X with k distinct letters. And so summing the scores from k=1 to n is just 1/(n+1-k) multiplied by the words there are for a word with k distinct letters, or P(k)(nCk), and that will give the sum.

iv) Using part ii), this sum can be expressed as (1/(n+1))ΣP(k)(n+1)Ck from 1 to n. P(k)(n+1)Ck is essentially how many n-lettered words can be created from a (n+1)-lettered alphabet, and so it is (n+1)^n. Thus, the answer is (n+1)^(n-1)

I'm not really all that confident with my answer for iv) honestly, I feel like I'm wrong but meh.

#### leehuan

##### Well-Known Member
Re: HSC 2016 MX2 Combinatorics Marathon

$\bg_white \text{Let }\mathcal{H}_n\text{ be the minimum number of moves}\\ \text{required to finish a game of Towers of Hanoi}$

$\bg_white \\\text{1. By playing the game or using your memory, evaluate }\mathcal{H}_1,\mathcal{H}_2,\mathcal{H}_3\text{ and }\mathcal{H}_4\\ \text{2. Use the above results to guess an explicit formula for }\mathcal{H}_n\\ \text{3. By playing the game again and observing a pattern, explain why}\\ \text{for }n\ge 2, \, \mathcal{H}_n=2\mathcal{H}_{n-1}+1\\ \text{4. Using the recursive formula in part 3}\\ \text{Prove by mathematical induction that your formula in part 2 holds for all }n\ge 1$

#### Drsoccerball

##### Well-Known Member
Re: HSC 2016 MX2 Combinatorics Marathon

$\bg_white \text{Let }\mathcal{H}_n\text{ be the minimum number of moves}\\ \text{required to finish a game of Towers of Hanoi}$

$\bg_white \\\text{1. By playing the game or using your memory, evaluate }\mathcal{H}_1,\mathcal{H}_2,\mathcal{H}_3\text{ and }\mathcal{H}_4\\ \text{2. Use the above results to guess an explicit formula for }\mathcal{H}_n\\ \text{3. By playing the game again and observing a pattern, explain why}\\ \text{for }n\ge 2, \, \mathcal{H}_n=2\mathcal{H}_{n-1}+1\\ \text{4. Using the recursive formula in part 3}\\ \text{Prove by mathematical induction that your formula in part 2 holds for all }n\ge 1$
"HSC 2016 MX2 Combinatorics Marathon"

##### -insert title here-
Re: HSC 2016 MX2 Combinatorics Marathon

"HSC 2016 MX2 Combinatorics Marathon"
And he didn't even define the game.

#### braintic

##### Well-Known Member
Re: HSC 2016 MX2 Combinatorics Marathon

"HSC 2016 MX2 Combinatorics Marathon"
As an aside, this question won't prove that you have found the minimal solution, merely that the formula works for your method.
There is an interesting graph which shows that the method is the optimal solution by noting that the shortest path between two points (states of the system) is a straight line.

#### dan964

##### what
Re: HSC 2016 MX2 Combinatorics Marathon

Thread closed. Consider starting a 2017 marathon.

Status
Not open for further replies.