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

[braintic]

Re: HSC 2016 MX2 Combinatorics Marathon

It is the Combinatorics marathon. So this is what I was hoping for.

 

[seanieg89]

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]

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]

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]

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]

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?

 

[Paradoxica]

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]

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.

 

[braintic]

Re: HSC 2016 MX2 Combinatorics Marathon

This is a derangement.

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]

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.

 

[InteGrand]

Re: HSC 2016 MX2 Combinatorics Marathon

Thanks for that. Looks like I have another series of YouTube lectures to view.

Yes, it is a good series. The full playlist is here: https://youtube.com/playlist?list=PL2SOU6wwxB0uwwH80KTQ6ht66KWxbzTIo .

I think that lecture series is available on iTunes too.

 

[braintic]

Re: HSC 2016 MX2 Combinatorics Marathon

Yes, it is a good series. The full playlist is here: https://youtube.com/playlist?list=PL2SOU6wwxB0uwwH80KTQ6ht66KWxbzTIo .

I think that lecture series is available on iTunes too.

Of course these lectures are not free. 35 lectures = 35 cans of bourbon.

 

[InteGrand]

Re: HSC 2016 MX2 Combinatorics Marathon

Of course these lectures are not free. 35 lectures = 35 cans of bourbon.

Actually, had a look on iTunes, and they're all free: https://itunes.apple.com/us/course/statistics-110-probability/id502492375 .

 

[RealiseNothing]

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]

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]

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]

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]

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]

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]

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?