HSC 2015 MX2 Permutations & Combinations Marathon (archive) (1 Viewer)

[lita1000]

Re: 2015 permutation X2 marathon

In how many ways can the letters of mathematics be arranged around a circle?

 

[Drsoccerball]

Re: 2015 permutation X2 marathon

In how many ways can the letters of mathematics be arranged around a circle?

10!/(2! 2! 2! 2!)

 

[lita1000]

Re: 2015 permutation X2 marathon

10!/(2! 2! 2! 2!)

Nope, this problem is actually reasonably difficult

 

[braintic]

Re: 2015 permutation X2 marathon

Nope, this problem is actually reasonably difficult

Are you referring to a non-invertible circle like a table, or an invertible circle like a necklace?

 

[lita1000]

Re: 2015 permutation X2 marathon

non invertible, but you still can't use the conventional method of arranging n distinct elements around a circle, then account for repetitions. For instance, consider the problem how many ways can you arrange AAABBB around a circle? Using the conventional method gets thou 5!/{3!3!} which isn't an integer.

 

[braintic]

Re: 2015 permutation X2 marathon

non invertible, but you still can't use the conventional method of arranging n distinct elements around a circle, then account for repetitions. For instance, consider the problem how many ways can you arrange AAABBB around a circle? Using the conventional method gets thou 5!/{3!3!} which isn't an integer.

But AAABBBC is 6!/3!3!, no?

 

[braintic]

Re: 2015 permutation X2 marathon

10!/(2! 2! 2! 2!)

I'm pretty sure your only mistake was in miscounting the number of doubles.

As long as there is at least one single letter, you just fix that letter, then arrange the others around it. That is arrange 10 letters containing 3 doubles, so 10! / (2!)^3.

But if there are no singles, it does become tricky.

 

[braintic]

Re: 2015 permutation X2 marathon

*
Andy, Ben. Charlie and Dick are to be allocated to 4 committees - Advertising, Finance, Planning, and Subterfuge.
Each committee is to contain exactly two people, and each person is to be on exactly two committees.
In how many ways can the committees be chosen?

I don't want to give the answer yet, but it is between: 75 and 100

(Note: This is NOT a typical textbook committee question)

 

[glittergal96]

Re: 2015 permutation X2 marathon

*
Andy, Ben. Charlie and Dick are to be allocated to 4 committees - Advertising, Finance, Planning, and Subterfuge.
Each committee is to contain exactly two people, and each person is to be on exactly two committees.
In how many ways can the committees be chosen?

I don't want to give the answer yet, but it is between: 75 and 100

(Note: This is NOT a typical textbook committee question)

Will double check this solution / look for a nicer way of computing it (ideally a computation generalised to n people/committees) when sober but:

If A has the same partner in both of his committees, then so must the other two people. So the number of such arrangements is:

3.C(4,2)=18 (Choose A's only partner and choose the two committees this pair is in).

If A has differing partners, so must the person that does not partner A.

The number of such arrangements is then

C(3,2).4.3.2=72 (Choose A's two partners, choose the committee the alphabetically earlier partner shares with A, choose the committee the alphabetically later partner shares with A, choose the committee the alphabetically earlier partner of A shares with the non-partner of A.)

This results in an answer of 90.


(The order of "choose" statements in a term's justification corresponds to the order of factors in that term.)

 

[braintic]

Re: 2015 permutation X2 marathon

Will double check this solution / look for a nicer way of computing it (ideally a computation generalised to n people/committees) when sober but:

If A has the same partner in both of his committees, then so must the other two people. So the number of such arrangements is:

3.C(4,2)=18 (Choose A's only partner and choose the two committees this pair is in).

If A has differing partners, so must the person that does not partner A.

The number of such arrangements is then

C(3,2).4.3.2=72 (Choose A's two partners, choose the committee the alphabetically earlier partner shares with A, choose the committee the alphabetically later partner shares with A, choose the committee the alphabetically earlier partner of A shares with the non-partner of A.)

This results in an answer of 90.


(The order of "choose" statements in a term's justification corresponds to the order of factors in that term.)

I'll check your answer tomorrow, but I was getting 87.

 

[dan964]

Re: 2015 permutation X2 marathon

one thing, if you reply with quote, the answer in white is visible kind of.

 

[Drsoccerball]

Re: 2015 permutation X2 marathon

*
Andy, Ben. Charlie and Dick are to be allocated to 4 committees - Advertising, Finance, Planning, and Subterfuge.
Each committee is to contain exactly two people, and each person is to be on exactly two committees.
In how many ways can the committees be chosen?

I don't want to give the answer yet, but it is between: 75 and 100

(Note: This is NOT a typical textbook committee question)

the wording screwed me up i dont understand the question

 

[InteGrand]

Re: 2015 permutation X2 marathon

I'll check your answer tomorrow, but I was getting 87.

Lol I had 90 too, used basically the same method as glittergal96.

 

[InteGrand]

Re: 2015 permutation X2 marathon

the wording screwed me up i dont understand the question

What's wrong with the wording? Each committee must have exactly two people, and each person must be in exactly two committees.

 

[Drsoccerball]

Re: 2015 permutation X2 marathon

What's wrong with the wording? Each committee must have exactly two people, and each person must be in exactly two committees.

Oh so one person could be in more than 1 committee or is there a limit on how many committees they can join?

 

[InteGrand]

Re: 2015 permutation X2 marathon

Oh so one person could be in more than 1 committee or is there a limit on how many committees they can join?

 

[braintic]

Re: 2015 permutation X2 marathon

Lol I had 90 too, used basically the same method as glittergal96.

I was doing it a different way, and I finally got 90.

The reason for my other method was that I then wanted to up the numbers.

So ... how would you do it if there are 6 people to be placed in 6 committees, with each person on exactly 3 committees and each committee having exactly 3 people?

And the number of people and committees need not be equal.

So 4 people placed in 6 committees, with each person on exactly 3 committees, and each committee having exactly 2 people.

I'm trying to find a general way of doing this. It is the same as drawing points in two parallel rows and trying to join the points in each row with points in the other row with lines so that all the points in a row have an equal number of lines coming into them. I've tried to find something online, but I don't really know what to search for.

 

[InteGrand]

Re: 2015 permutation X2 marathon

I was doing it a different way, and I finally got 90.

The reason for my other method was that I then wanted to up the numbers.

So ... how would you do it if there are 6 people to be placed in 6 committees, with each person on exactly 3 committees and each committee having exactly 3 people?

And the number of people and committees need not be equal.

So 4 people placed in 6 committees, with each person on exactly 3 committees, and each committee having exactly 2 people.

I'm trying to find a general way of doing this. It is the same as drawing points in two parallel rows and trying to join the points in each row with points in the other row with lines so that all the points in a row have an equal number of lines coming into them. I've tried to find something online, but I don't really know what to search for.

So there are four parameters in your general problem?

 

[braintic]

Re: 2015 permutation X2 marathon

So there are four parameters in your general problem?

That can be reduced to 3:

(1) The number of people, m
(2) The number of committees, n
(3) The number of connections (which must be a multiple of m and n - not necessarily the LCM)

 

[braintic]

Re: 2015 permutation X2 marathon

I have been considering the simplified case of placing n people into n committees with 2 people in each committee and each person in 2 committees.


I have noticed a pattern - but it is a pattern of TWO only, so there is a good chance it means nothing.


For 3 people & 3 committees, call the people A, B, C. Since each person has to be allocated twice, we need to arrange the letters A, A, B, B, C, C to form a "word" of the form

_ _ / _ _ / _ _

where the same letter does not appear twice in each group.

If you form a word without that restriction, the number of words is (6!)/(2^3), yet the final answer (6) turns out to be (4!)/(2^2).



If the same thing is done with 4 people and 4 committees, the number of unrestricted words is (8!)/(2^4), yet the final answer (90) turns out to be (6!)/2^3.



Can anyone see a logical reason for that pattern, or is it just a fluke?




Another pattern:

For 2 people, 2 committees, the answer is 2C2.
For 3 people, 3 committees, it is 4C2 times 2C2.
For 4 people, 4 committees, it is 6C2 times 4C2 times 2C2.

This suggests that there should be a recursive way to get the solution, but I can't see the logic.