HSC 2015 MX2 Permutations & Combinations Marathon (archive) (3 Viewers)

[Drsoccerball]

Re: 2015 permutation X2 marathon

I really don't think it is a good idea to give out your name on this site.

For the sake of maths...

 

[braintic]

Re: 2015 permutation X2 marathon

[*]

(I just want to get this question out while it's still in my head, so don't forget the previous question)

In a 12 sided convex polygon, how many diagonal intersections lie inside the polygon? (ie. not counting the vertices themselves)
[Assume that no three diagonals happen to intersect at the same point.]

Answer: 495

 

[Zlatman]

Re: 2015 permutation X2 marathon

How many ways can the name '*******' be arranged so that no vowels are together?

I'm just gonna leave the name out, in case you decide to remove it.

First, we arrange the consonants, which there are 7 of:
Then, we place the 5 vowels in the gaps between the consonants, including at the beginning and end of the consonants. There are 8 gaps in which these vowels can be placed, so arrangements of vowels:
Finally, there are two I's and two E's which can't be differentiated, so we divide by:

Therefore, total arrangements = or 8,467,200 arrangements.

 

[kawaiipotato]

Re: 2015 permutation X2 marathon

I'm just gonna leave the name out, in case you decide to remove it.

First, we arrange the consonants, which there are 7 of:
Then, we place the 5 vowels in the gaps between the consonants, including at the beginning and end of the consonants. There are 8 gaps in which these vowels can be placed, so arrangements of vowels:
Finally, there are two I's and two E's which can't be differentiated, so we divide by:

Therefore, total arrangements = or 8,467,200 arrangements.

Why does doing total - vowels together not get the same answer?
total together = 12!/(2!2!)
vowels together = 5!/(2!2!) * 8!
not together =

 

[Zlatman]

Re: 2015 permutation X2 marathon

Why does doing total - vowels together not get the same answer?
total together = 12!/(2!2!)
vowels together = 5!/(2!2!) * 8!
not together =

Because that only provides the case where all 5 vowels are together, not when there are 2-4 vowels together.

 

[braintic]

Re: 2015 permutation X2 marathon

Why does doing total - vowels together not get the same answer?
total together = 12!/(2!2!)
vowels together = 5!/(2!2!) * 8!
not together =

You would have to get seriously stuck into Inclusion/Exclusion

 

[Drsoccerball]

Re: 2015 permutation X2 marathon

I'm just gonna leave the name out, in case you decide to remove it.

First, we arrange the consonants, which there are 7 of:
Then, we place the 5 vowels in the gaps between the consonants, including at the beginning and end of the consonants. There are 8 gaps in which these vowels can be placed, so arrangements of vowels:
Finally, there are two I's and two E's which can't be differentiated, so we divide by:

Therefore, total arrangements = or 8,467,200 arrangements.

Does this include the options which theres 2 constants in between two of the vowels?

 

[Zlatman]

Re: 2015 permutation X2 marathon

Does this include the options which theres 2 constants in between two of the vowels?

Yeah, only 5 of the 8 gaps between the consonants will be filled by vowels, leaving blank spaces in the other gaps. This means that consonants with a blank space between them will be together, so it includes the cases where 2-3 consonants are together (I hope, new to inclusion method).

 

[kawaiipotato]

Re: 2015 permutation X2 marathon

You would have to get seriously stuck into Inclusion/Exclusion

What do you mean?

 

[glittergal96]

Re: 2015 permutation X2 marathon

[*]

(I just want to get this question out while it's still in my head, so don't forget the previous question)

In a 12 sided convex polygon, how many diagonal intersections lie inside the polygon? (ie. not counting the vertices themselves)
[Assume that no three diagonals happen to intersect at the same point.]

Answer: 495

Given any four distinct points, there is exactly one way of dividing the four points into two pairs and joining each pair with a line such that the intersection is interior to the convex polygon defined by the initial four points. (The lines are just the diagonals of this convex polygon.)

Moreover, every point of diagonal intersection in an n-go arises from a unique pair of lines and hence a unique subset of four vertices.

So the answer is just

 

[glittergal96]

Re: 2015 permutation X2 marathon

How many ways can we paint the 4 faces of a tetrahedron using n colours? (colours can be repeated.)

Answer the same question for the cube.

 

[Drsoccerball]

Re: 2015 permutation X2 marathon

How many ways can we paint the 4 faces of a tetrahedron using n colours? (colours can be repeated.)

Answer the same question for the cube.

no repeats : (nc4)
2 repeats :
2 repeats x 2 :
3 repeats:
All same colour : n /4
whats the answer?

 

[braintic]

Re: 2015 permutation X2 marathon

How many ways can we paint the 4 faces of a tetrahedron using n colours? (colours can be repeated.)

Wouldn't the answer depend on whether or not n>3 ?

 

[braintic]

Re: 2015 permutation X2 marathon

All same colour : n /4

Why are you dividing by 4 ?

 

[InteGrand]

Re: 2015 permutation X2 marathon

Wouldn't the answer depend on whether or not n>3 ?

Well there's nothing wrong with that, we could just answer in cases.

 

[braintic]

Re: 2015 permutation X2 marathon

I don't want to give my calculation because it is supposed to be for HSC students.

But for the tetrahedron, and only for n>3, I get an expression which simplifies algebraically to:


I can't see a logical way to go straight to that answer.

 

[glittergal96]

Re: 2015 permutation X2 marathon

I haven't done the calculation yet myself, but the answer will look something like braintics.

I won't completely give away the method yet, because I think it is a fantastic exercise in counting things with symmetry (although a decent bit harder than syllabus for sure).

The key though is to consider a more general class of problems: Suppose we have a finite set X (in our example, the collection of ways of colouring 4 distinct faces using n colours, without worrying about rotational equivalence) and a collection S of "symmetries" of X, (like the rotations of our tetrahedron/cube/bracelet/whatever our problem involves.)

If we group together the elements of X that are equivalent under symmetries in S, how many "classes" of equivalent elements of X are there?

In this more abstract setting, try to prove that the answer is the average (over S) of the number of fixed points in X of an arbitrary symmetry in S. (*) (Note that the action of leaving X unchanged is itself trivially a symmetry.)

(An x is said to be a fixed point of the symmetry s if it is unchanged by s. Eg. the string (ABAB) is not a fixed point of rotation left by one unit (which gives (BABA)), but it IS a fixed point of the rotation left by two units.)


(If proving (*) is too hard, try just to use it to solve the problems originally posted.)

 

[shervos]

Re: 2015 permutation X2 marathon

I haven't done the calculation yet myself, but the answer will look something like braintics.

I won't completely give away the method yet, because I think it is a fantastic exercise in counting things with symmetry (although a decent bit harder than syllabus for sure).

The key though is to consider a more general class of problems: Suppose we have a finite set X (in our example, the collection of ways of colouring 4 distinct faces using n colours, without worrying about rotational equivalence) and a collection S of "symmetries" of X, (like the rotations of our tetrahedron/cube/bracelet/whatever our problem involves.)

If we group together the elements of X that are equivalent under symmetries in S, how many "classes" of equivalent elements of X are there?

In this more abstract setting, try to prove that the answer is the average (over S) of the number of fixed points in X of an arbitrary symmetry in S. (*) (Note that the action of leaving X unchanged is itself trivially a symmetry.)

(An x is said to be a fixed point of the symmetry s if it is unchanged by s. Eg. the string (ABAB) is not a fixed point of rotation left by one unit (which gives (BABA)), but it IS a fixed point of the rotation left by two units.)


(If proving (*) is too hard, try just to use it to solve the problems originally posted.)

Judging by the lack of responses to this question, I'd say that most people are confused by the wording. Can you provide an example as to what you mean by average (over S) of the number of fixed points in X of an arbitrary symmetry in S for instance?

 

[glittergal96]

Re: 2015 permutation X2 marathon

Okay, I will illustrate the idea for a simpler problem.

Q/ How many ways are there to colour the 4 sides of a square using n colours?

A/ Consider strings of the form (ABCD). In this problem we have 4 symmetries (that correspond to rotating the square anticlockwise by 0,1,2,3 quarter turns respectively).

(ABCD)->(ABCD)
(ABCD)->(BCDA)
(ABCD)->(CDAB)
(ABCD)->(DABC)

So there are obviously n^4 ways of choosing 4 character strings with n characters available to us, but to treat rotational equivalence of strings, we need to use the approach discussed in the previous question.

In particular, if we assume the abstract result:

"In this more abstract setting, try to prove that the answer is the average (over S) of the number of fixed points in X of an arbitrary symmetry in S. (*) (Note that the action of leaving X unchanged is itself trivially a symmetry.)"

we need to sum the number of fixed points of the 4 symmetries and divide by 4 to obtain our final answer.

How many strings are preserved by the 0 unit rotation? All of them! So that is n^4.

How many strings are preserved by the 1 unit rotation? Only n of them! Since (ABCD)->(BCDA), if a string is preserved by this rotation we must have A=B, B=C, C=D...ie our string must consist of the same letter repeated 4 times.

The same holds true for the 3 unit rotation.

The 2 unit rotation is slightly less straightforward. As (ABCD)->(CDAB) we must have A=C and B=D. So the number of fixed points here is the number of ways of making an ordered selection of 2 out of the n characters. This is just n^2.

So the answer for this example problem is:




The tetrahedron problem (if you assume the result in quotes) is more difficult only because it is harder to visualise the symmetries of a 3d object.

 

[glittergal96]

Re: 2015 permutation X2 marathon

And for comparison to your solutions, I believe braintic's answer for the tetrahedron problem is correct (for all n).