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

Status
Not open for further replies.

braintic

Well-Known Member
Joined
Jan 20, 2011
Messages
2,137
Gender
Undisclosed
HSC
N/A
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




ii) Show that



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:




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

braintic

Well-Known Member
Joined
Jan 20, 2011
Messages
2,137
Gender
Undisclosed
HSC
N/A
Re: HSC 2016 MX2 Combinatorics Marathon

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

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

He-Mann

Vexed?
Joined
Sep 18, 2016
Messages
279
Location
Antartica
Gender
Male
HSC
N/A
Re: HSC 2016 MX2 Combinatorics Marathon

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

Well-Known Member
Joined
Jan 20, 2011
Messages
2,137
Gender
Undisclosed
HSC
N/A
Re: HSC 2016 MX2 Combinatorics Marathon

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.
 

InteGrand

Well-Known Member
Joined
Dec 11, 2014
Messages
6,109
Gender
Male
HSC
N/A
Re: HSC 2016 MX2 Combinatorics Marathon



 
Last edited:

calamebe

Active Member
Joined
Mar 19, 2015
Messages
462
Gender
Male
HSC
2017
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




ii) Show that



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:




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
Joined
Mar 19, 2015
Messages
462
Gender
Male
HSC
2017
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.
 

braintic

Well-Known Member
Joined
Jan 20, 2011
Messages
2,137
Gender
Undisclosed
HSC
N/A
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
Joined
Jun 3, 2014
Messages
3,473
Location
South of here
Gender
Male
HSC
2014
Uni Grad
2019
Re: HSC 2016 MX2 Combinatorics Marathon

Thread closed. Consider starting a 2017 marathon.
 
Status
Not open for further replies.

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

Top