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

braintic · Oct 5, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

Paradoxica said:
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

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

ii) Show that

$\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:

$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?

Paradoxica · Oct 5, 2016

HSC 2016 MX2 Combinatorics Marathon

braintic said:
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 · Oct 5, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

Paradoxica said:
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?

Paradoxica · Oct 5, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

braintic said:
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 · Oct 6, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

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

This smart-ass......

pikachu975 · Oct 6, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

He-Mann said:
This smart-ass......

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

Drsoccerball · Oct 6, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

He-Mann said:
This smart-ass......

What if he actually had a heart attack and we all thought it was a joke ?

He-Mann · Oct 6, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

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

That's the point, m8. Paradoxica mocking braintic's question made braintic mock how specific Paradoxica's comment was.

braintic · Oct 9, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

He-Mann said:
That's the point, m8. Paradoxica mocking braintic's question made braintic mock how specific Paradoxica's comment was.

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 · Oct 9, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

HSC 2016 MX2 Argument Marathon

InteGrand · Oct 21, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

$\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.$

$\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.$

calamebe · Oct 21, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

Paradoxica said:
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

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

ii) Show that

$\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:

$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 · Oct 21, 2016

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 · Nov 27, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

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

$\\\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 · Nov 27, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

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

$\\\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"

Paradoxica · Nov 27, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

Drsoccerball said:
"HSC 2016 MX2 Combinatorics Marathon"

And he didn't even define the game.

InteGrand · Nov 28, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

Here's a link to the game for anyone who wants to play it and/or do the above problem: https://www.mathsisfun.com/games/towerofhanoi.html .

braintic · Nov 30, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

Drsoccerball said:
"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 · Feb 6, 2017

Re: HSC 2016 MX2 Combinatorics Marathon

Thread closed. Consider starting a 2017 marathon.

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

braintic

Well-Known Member

Paradoxica

-insert title here-

braintic

Well-Known Member

Paradoxica

-insert title here-

He-Mann

Vexed?

pikachu975

Premium Member

Drsoccerball

Well-Known Member

He-Mann

Vexed?

braintic

Well-Known Member

Drsoccerball

Well-Known Member

InteGrand

Well-Known Member

calamebe

Active Member

calamebe

Active Member

leehuan

Well-Known Member

Drsoccerball

Well-Known Member

Paradoxica

-insert title here-

InteGrand

Well-Known Member

braintic

Well-Known Member

dan964

what

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