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

Status
Not open for further replies.

seanieg89

Well-Known Member
Joined
Aug 8, 2006
Messages
2,662
Gender
Male
HSC
2007
Re: HSC 2016 MX2 Combinatorics Marathon

It is the Combinatorics marathon. So this is what I was hoping for.
Of course, such solutions are often far nicer.

The splitting into 4 subsets/teams was actually the first solution I spotted, I just wrote the other one as I figured it would take less writing to justify :).
 

braintic

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

(1) The faces, edges and vertices of a cube are indistinguishable. In how many unique ways can the vertices be labelled 1 to 8 ?

(2) (I have no answer for this) In how many unique ways can the 20 vertices of a dodecahedron be labelled 1 to 20 ?

(3) (Ditto) Repeat for the 12 vertices of an icosahedron.
 

Paradoxica

-insert title here-
Joined
Jun 19, 2014
Messages
2,556
Location
Outside reality
Gender
Male
HSC
2016
Re: HSC 2016 MX2 Combinatorics Marathon

(1) The faces, edges and vertices of a cube are indistinguishable. In how many unique ways can the vertices be labelled 1 to 8 ?

(2) (I have no answer for this) In how many unique ways can the 20 vertices of a dodecahedron be labelled 1 to 20 ?

(3) (Ditto) Repeat for the 12 vertices of an icosahedron.
I'm thinking we fix one face and consider the opposite face and the central remaining ring of alternating vertices all individually. This applies to both solids.

Alternatively we could fix the central alternating ring and consider the faces separately.
 

seanieg89

Well-Known Member
Joined
Aug 8, 2006
Messages
2,662
Gender
Male
HSC
2007
Re: HSC 2016 MX2 Combinatorics Marathon

I will not spoil (1), because it is the closest to MX2 level. (The same method works there though).

Remark:
The standard way of dealing with counting problems involving symmetry is Burnside's lemma. Unfortunately this is far enough out of syllabus to not be close to usable in MX2 exams. Highly recommend anyone into combinatorics that doesn't have this up their sleeve tries to learn it though.

Anyway, if we were to apply Burnside's lemma in this problem we would find the equation rather degenerate. This is essentially because the numbers we are putting on the vertices are distinct (if instead we colour the vertices of polyhedra with a smaller number of colours, things get a little more interesting).

Consider the set X of ways of numbering vertices of a fixed dodecahedron/icosahedron. This set just has cardinality V!.

Now we can apply rotations to our fixed dodecahedron/icosahedron to obtain equivalent numberings. The number of ways of rotating a given colouring x in X is just the size |G| of the symmetry group of our polyhedron (the number of distinct rotations). In other words, rotational equivalence partitions the set |X| into subsets of size |G|, where all x in any single subset are rotationally equivalent numberings.

The number were alre looking for then is just |X|/|G|=V!/|G|, the number of equivalence classes.

Now we note that a rotation of regular 3d polyhedron is completely determined by the ending position of a single pre-selected vertex p (unimportant which), as well as orientation. We can move this vertex p to any of the V orginal vertex locations, and then we can choose m orientations, where m is the number of faces that meet at each vertex. So the symmetry group has order mV.

For an icosahedron/dodecahedron we have (V,m)=(12,5) and (20,3) and so we get |G|=60 regardless. (This is actually obvious because they are duals.)

This leads to the answers:

b) 20!/60, c)12!/60.
 

braintic

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

I have a question which I am having difficulty analysing.

n balls are numbered 1, 2, 3, ..., n.
The balls are placed randomly in a straight line, each ball sitting in a position 1, ..., n.
Let P(n, k) be the probability that there are exactly k balls whose number corresponds to its position in the line.

For example if n=3, the possible arrangements are:
1 2 3 [3]
1 3 2 [1]
2 1 3 [1]
2 3 1 [0]
3 1 2 [0]
3 2 1 [1]

The number in square brackets indicates the number of balls sitting in the correct position.
(Those balls are bolded.)

So:
P(3,0) = 2/6
P(3,1) = 3/6
P(3,2) = 0/6
P(3,3) = 1/6

I am wondering if there is a general formula for the distribution P(n,k)?
All I can see at the moment is that:
(1) P(n,n) = 1/(n!)
(2) P(n, n-1) = 0
(3) The expected value of the distribution is equal to 1 (independent of n).

Any suggestions?
 
Last edited:

Paradoxica

-insert title here-
Joined
Jun 19, 2014
Messages
2,556
Location
Outside reality
Gender
Male
HSC
2016
Re: HSC 2016 MX2 Combinatorics Marathon

I have a question which I am having difficulty analysing.

n balls are numbered 1, 2, 3, ..., n.
The balls are placed randomly in a straight line, each ball sitting in a position 1, ..., n.
Let P(n, k) be the probability that there are exactly k balls whose number corresponds to its position in the line.

For example if n=3, the possible arrangements are:
1 2 3 [3]
1 3 2 [1]
2 1 3 [1]
2 3 1 [0]
3 1 2 [0]
3 2 1 [1]

The number in square brackets indicates the number of balls sitting in the correct position.
(Those balls are bolded.)

So:
P(3,0) = 2/6
P(3,1) = 3/6
P(3,2) = 0/6
P(3,3) = 1/6

I am wondering if there is a general formula for the distribution P(n,k)?
All I can see at the moment is that P(n,n) = 1/(n!), and that P(n, n-1) = 0.

Any suggestions?
This is a derangement.
 

InteGrand

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

I have a question which I am having difficulty analysing.

n balls are numbered 1, 2, 3, ..., n.
The balls are placed randomly in a straight line, each ball sitting in a position 1, ..., n.
Let P(n, k) be the probability that there are exactly k balls whose number corresponds to its position in the line.

For example if n=3, the possible arrangements are:
1 2 3 [3]
1 3 2 [1]
2 1 3 [1]
2 3 1 [0]
3 1 2 [0]
3 2 1 [1]

The number in square brackets indicates the number of balls sitting in the correct position.
(Those balls are bolded.)

So:
P(3,0) = 2/6
P(3,1) = 3/6
P(3,2) = 0/6
P(3,3) = 1/6

I am wondering if there is a general formula for the distribution P(n,k)?
All I can see at the moment is that:
(1) P(n,n) = 1/(n!)
(2) P(n, n-1) = 0
(3) The expected value of the distribution is equal to 1 (independent of n).

Any suggestions?
I think this is called the de Montmort Problem or Matching Problem. It can be solved using inclusion-exclusion (which then can be used to prove the derangement formula in Paradoxica's link). It is worked through in this Stat110 Lecture from Harvard:

.

(The video first goes through the Birthday Problem if I recall correctly; it then goes on to the Matching Problem I think.)

(I haven't thought about this problem too recently so I can't remember if it's exactly the same as your problem. But I think it was from memory.)

Edit: OK had another look at that video, and the problem there was the probability that at least one of the n balls are correctly placed. This ends up being related to the derangement formula of course. Then, as RealiseNothing explained below, to do your problem of 'exactly k' correctly placed balls (a partial derangement), the number of ways will just be (n choose k)*D(n-k), where the D(n-k) formula can be derived via inclusion-exclusion similarly to in the video.

This de Montmort problem is treated in the last 10-ish minutes of that video, and the next lecture in that series also does that problem for a bit at the start if I recall correctly.
 
Last edited:

braintic

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

Thanks for the link. Apparently they are not derangements per se, but "partial derangements". It looks somewhat more complicated than a standard derangement (where ALL objects must be in the wrong position).
 

braintic

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

I think this is called the de Montmort Problem or Matching Problem. It can be solved using inclusion-exclusion (which then can be used to prove the derangement formula in Paradoxica's link). It is worked through in this Stat110 Lecture from Harvard:

(The video first goes through the Birthday Problem if I recall correctly; it then goes on to the Matching Problem I think.)
Thanks for that. Looks like I have another series of YouTube lectures to view.
 

RealiseNothing

what is that?It is Cowpea
Joined
Jul 10, 2011
Messages
4,591
Location
Sydney
Gender
Male
HSC
2013
Re: HSC 2016 MX2 Combinatorics Marathon

I have a question which I am having difficulty analysing.

n balls are numbered 1, 2, 3, ..., n.
The balls are placed randomly in a straight line, each ball sitting in a position 1, ..., n.
Let P(n, k) be the probability that there are exactly k balls whose number corresponds to its position in the line.

For example if n=3, the possible arrangements are:
1 2 3 [3]
1 3 2 [1]
2 1 3 [1]
2 3 1 [0]
3 1 2 [0]
3 2 1 [1]

The number in square brackets indicates the number of balls sitting in the correct position.
(Those balls are bolded.)

So:
P(3,0) = 2/6
P(3,1) = 3/6
P(3,2) = 0/6
P(3,3) = 1/6

I am wondering if there is a general formula for the distribution P(n,k)?
All I can see at the moment is that:
(1) P(n,n) = 1/(n!)
(2) P(n, n-1) = 0
(3) The expected value of the distribution is equal to 1 (independent of n).

Any suggestions?
Choose the k balls to be in their right position .

Now the remaining n-k balls have to all be in the wrong position, which is just a derangement of n-k balls. Let's call this .

So we would have:

where m is the amount of balls we want to be in the wrong position.

Working out the derangement is a bit harder as you can probably see from paradoxica's link.
 

seanieg89

Well-Known Member
Joined
Aug 8, 2006
Messages
2,662
Gender
Male
HSC
2007
Re: HSC 2016 MX2 Combinatorics Marathon

You are offered (at a price!) to flip a fair coin repeatedly until you flip n tails in a row. (n some positive integer).
At the end, you are given $k where k is the number of total flips you had (including the n tails).

Up to what price are you willing to pay in order to play this game?
 

Paradoxica

-insert title here-
Joined
Jun 19, 2014
Messages
2,556
Location
Outside reality
Gender
Male
HSC
2016
Re: HSC 2016 MX2 Combinatorics Marathon

You are offered (at a price!) to flip a fair coin repeatedly until you flip n tails in a row. (n some positive integer).
At the end, you are given $k where k is the number of total flips you had (including the n tails).

Up to what price are you willing to pay in order to play this game?
Given the asymptotic distribution of fair coin outcomes, I would pay
 

seanieg89

Well-Known Member
Joined
Aug 8, 2006
Messages
2,662
Gender
Male
HSC
2007
Re: HSC 2016 MX2 Combinatorics Marathon

Given the asymptotic distribution of fair coin outcomes, I would pay
Care to justify this more if you stand by it? I think you can afford to pay a lot more than that.

Eg in the simple n=1 case we are flipping coins till we get a tails. The probability of a coinflipping sequence terminating precisely after k flips is 1/2^k, and so the expected profit from playing this game is:

 

Paradoxica

-insert title here-
Joined
Jun 19, 2014
Messages
2,556
Location
Outside reality
Gender
Male
HSC
2016
Re: HSC 2016 MX2 Combinatorics Marathon

Care to justify this more if you stand by it? I think you can afford to pay a lot more than that.

Eg in the simple n=1 case we are flipping coins till we get a tails. The probability of a coinflipping sequence terminating precisely after k flips is 1/2^k, and so the expected profit from playing this game is:

Honestly, I have no clue, all I know is that the maximum betting that will yield profit is significantly larger than n....

My other idea was 3n/2
 

seanieg89

Well-Known Member
Joined
Aug 8, 2006
Messages
2,662
Gender
Male
HSC
2007
Re: HSC 2016 MX2 Combinatorics Marathon

Honestly, I have no clue, all I know is that the maximum betting that will yield profit is significantly larger than n....

My other idea was 3n/2
Yep, the profit grows much faster than n. Will provide more hints if it goes unsolved for a while.
 

RealiseNothing

what is that?It is Cowpea
Joined
Jul 10, 2011
Messages
4,591
Location
Sydney
Gender
Male
HSC
2013
Re: HSC 2016 MX2 Combinatorics Marathon

You are offered (at a price!) to flip a fair coin repeatedly until you flip n tails in a row. (n some positive integer).
At the end, you are given $k where k is the number of total flips you had (including the n tails).

Up to what price are you willing to pay in order to play this game?
 
Last edited:
Status
Not open for further replies.

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

Top