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

Status
Not open for further replies.
B

braintic

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



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.
Click to expand...
Is this a question you are posing for others, or one you need help with?
 
B

braintic

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

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

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

He-Mann

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

pikachu975 said:
Pretty sure it's because Paradoxica didn't respond properly either but doesn't really matter
Click to expand...
That's the point, m8. Paradoxica mocking braintic's question made braintic mock how specific Paradoxica's comment was.
 
B

braintic

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

InteGrand

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



 
Last edited:
C

calamebe

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



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.
Click to expand...
I did it in my head so I may be wrong, is iv) (n+1)^n-n! or something?
 
C

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.
 
B

braintic

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

Drsoccerball said:
"HSC 2016 MX2 Combinatorics Marathon"
Click to expand...
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

dan964

what
Joined
Jun 3, 2014
Messages
3,479
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: 2)

Top