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

porcupinetree · Aug 8, 2015

Re: 2015 permutation X2 marathon

sida1049 said:
There are 8 gates which 10 cars can pass through. How many ways can the cars pass through if every gate is used?

(Sorry my initial answer was incorrect. Working out another one.)

Here's what I have (assuming the order of cars through the gates matters):

Case 1 - 2 gates have 2 cars while the other 6 gates have 1 car
8C2 - choose 2 gates
10C2*2! - choose 2 cars for gate 1 & arrange
8C2*2! - choose 2 cars for gate 2 & arrange
6! - arrange other cars
Total for case 1 = 8C2.10C2.2!.8C2.2!.6! = 101606400

Case 2 - 1 gate has 3 cars, the rest have 1
8C1 - choose the gate to have 3 cars
10C3.3! - choose 3 cars for gate 1 and arrange
7! - arrange the other cars
Total for case 2: 29030400

Total = 101606400 + 29030400 = 1 306 636 800

Ekman · Aug 8, 2015

Re: 2015 permutation X2 marathon

sida1049 said:
There is another case where 3 cars go through a single gate and 7 gates with a single car.

But I already considered that in the 8^2 though. Since each car has 8 possible gates to go through

sida1049 · Aug 8, 2015

Re: 2015 permutation X2 marathon

kawaiipotato said:
how come we don['t account for when it's like _C_C_C_C_C_CC_ ?

It's taken into account like this:

VCVCVCVC_CV

Librah · Aug 8, 2015

Re: 2015 permutation X2 marathon

Twenty-one girls and twenty-one boys took part in a mathematical competition. It turned out that each contestant solved at most six problems, and for each pair of a girl and a boy, there was at least one problem that was solved by both the girl and the boy. Show that there is a problem that was solved by at least three girls and at least three boys.

According to thread rules, must answer question before moving on.

InteGrand · Aug 8, 2015

Re: 2015 permutation X2 marathon

porcupinetree said:
Here's what I have (assuming the order of cars through the gates matters):

Case 1 - 2 gates have 2 cars while the other 6 gates have 1 car
8C2 - choose 2 gates
10C2*2! - choose 2 cars for gate 1 & arrange
8C2*2! - choose 2 cars for gate 2 & arrange
6! - arrange other cars
Total for case 1 = 8C2.10C2.2!.8C2.2!.6! = 101606400

Case 2 - 1 gate has 3 cars, the rest have 1
8C1 - choose the gate to have 3 cars
10C3.3! - choose 3 cars for gate 1 and arrange
7! - arrange the other cars
Total for case 2: 29030400

Total = 101606400 + 29030400 = 1 306 636 800

sida1049 said the order through each gate does not matter.

sida1049 said:
Consider the consonants as "fixed" positions:
_C_C_C_C_C_C_
Where the underscores highlight the positions the vowels can situate.

Hence the number of possible positions of vowels follows: 7C5

Vowels can only be in one arrangement.

There are 6 consonants but 2 are of the same, hence number of arrangement of vowels = 6!/2

Answer: 7C5.6!/2 = 7560.

Next question:

There are 8 gates which 10 cars can pass through. How many ways can the cars pass through if every gate is used?(Order of cars passing through a particular gate does not matter, but order of cars passing through different gates, e.g. car A through gate 1 or gate 2, matters.)

(Sorry my initial answer was incorrect. Working out another one.)

Oh my god I've just realised the difficulty of this question. Still working on it. Apologies for the edits.

So is the question equivalent to: 'Consider 10 (distinct) balls labelled 1-10. Consider (distinct) 8 boxes labelled 1-8. How many ways can the balls be placed in the boxes so that each box has at least one ball?'

sida1049 · Aug 8, 2015

Re: 2015 permutation X2 marathon

Alright wow my question is a massive pain. I'll offer my explanation and let's poke holes in each other's rationalities:

Case #1: one gate has 3 cars
10C3.8!
First part because we need to select the cars. Second part because we need to figure out which car goes through which gate (also considering that order of cars passing through does not matter).

Case #2: two gates with 2 cars
[(10C2.8C2)/2].8!
First part because we have to find the groups of cars, and ordering of the cars through the same gates does not matter. Second part because, you know, which goes into what.

Answer: 10C3.8! + [(10C2.8C2)/2].8! = 30,240,000

InteGrand · Aug 8, 2015

Re: 2015 permutation X2 marathon

Librah said:
Twenty-one girls and twenty-one boys took part in a mathematical competition. It turned out that each contestant solved at most six problems, and for each pair of a girl and a boy, there was at least one problem that was solved by both the girl and the boy. Show that there is a problem that was solved by at least three girls and at least three boys.

According to thread rules, must answer question before moving on.

Lol the IMO Q again.

http://www.artofproblemsolving.com/wiki/index.php/2001_IMO_Problems/Problem_3

sida1049 · Aug 8, 2015

Re: 2015 permutation X2 marathon

InteGrand said:
sida1049 said the order through each gate does not matter.

So is the question equivalent to: 'Consider 10 (distinct) balls labelled 1-10. Consider (distinct) 8 boxes labelled 1-8. How many ways can the balls be placed in the boxes so that each box has at least one ball?'

Yep.

Soulful · Aug 8, 2015

Re: 2015 permutation X2 marathon

ok what ive got is

consider case 1 - 2 gates with 2 cars, 6 gates with 1

choosing the first gate - 8C1
choosing two cars for this gate - 10C2
choosing the 2nd gate - 7C1
choosing two cars for this gate - 8C2
the rest of the cars - 6!
EDIT - HAVE TO DIVIDE BY 2 CAUSE OF THE TWO GATES

case 2 - 1 gate with 3 cars, 7 gates with 1

choosing the gate - 8C1
choosing three cars - 10C3
the other cars - 7!

total ways = 1/2(8C1 x 10C2 x 7C1 x 8C2 x 6!) + 8C1 x 10C3 x 7! = 30240000

InteGrand · Aug 8, 2015

Re: 2015 permutation X2 marathon

sida1049 said:
Alright wow my question is a massive pain. I'll offer my explanation and let's poke holes in each other's rationalities:

Case #1: one gate has 3 cars
10C3.8!
First part because we need to select the cars. Second part because we need to figure out which car goes through which gate (also considering that order of cars passing through does not matter).

Case #2: two gates with 2 cars
[(10C2.8C2)/2].8!
First part because we have to find the groups of cars, and ordering of the cars through the same gates does not matter. Second part because, you know, which goes into what.

Answer: 10C3.8! + [(10C2.8C2)/2].8! = 30,240,000

I think this is correct.

$What you were actually asking was how many ways to partition 10 distinct objects into 8 non-empty subsets, and then arrange them. The number of ways to partition $n$ distinct objects into $k$ non-empty subsets (order of them unimportant) is called a \emph{Stirling number of the second kind}, and is denoted $S(n,k)$ or $\begin{Bmatrix}n\\k\end{Bmatrix}$. See the Wikipedia page for information, including a table of some values, as well as a formula for $\begin{Bmatrix}n\\k\end{Bmatrix}$ as a series:$

https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind

$For your question, we could form the 8 non-empty subsets of 10 balls in $\begin{Bmatrix}10\\8\end{Bmatrix}=750$ ways (see the table of values on the Wikipedia page). Then, we can arrange each of these in $8!=40320$ ways. This makes the answer $8!\times \begin{Bmatrix}10\\8\end{Bmatrix} = 40320\times 750 = 30240000$.$

(An inductive proof of the series expression for S(n, k) may be found here: http://www.emis.de/journals/HOA/ADS/Volume1_2/157.pdf)

Here is a Q from the HSC 2015 4U Marathon about setting up a recursive formula for Stirling numbers of the second kind:

Sy123 said:
$\\ $Let$ \ S(n,k) \ $be the number of ways to divide the collection of numbers$ \ \{1,2,3,\dots,n \} \ $into$ \ k \ $non-empty groups$$

$\\ $e.g.$ \ S(3,2) = 3 \ $since one can divide$ \ (A,B,C) \ $into groups$ \ (AB, C) , (AC, B) \ $and$ \ (BC, A)$

$\\ $By considering whether the number$ \ n \ $is in its own group or not, show that$ \\ S(n,k) = S(n-1,k-1) + k\cdot S(n-1,k)$

sida1049 · Aug 8, 2015

Re: 2015 permutation X2 marathon

Ekman said:
For the gates question, my plan of attack was:

10C8 different cars to go through every single gate
8! for each gate to be accessed
8^2 for the remaining two cars, since we don't care which gate they access

10C8 * 8! * 8^2 = 116121600

I'm having a huge problem trying to poke a hole through your argument! I'm suspecting that by simply multiplying 8 twice for the cars which have to go through used gates, you are not taking into account the ways in which specific cars can overlap. E.g. car A and car B through gate 1, or car B and car A through gate 1. Although I'm only postulating at this point.

sida1049 · Aug 8, 2015

Re: 2015 permutation X2 marathon

InteGrand said:
I think this is correct.

$What you were actually asking was how many ways to partition 10 distinct objects into 8 non-empty subsets, and then arrange them. The number of ways to partition $n$ distinct objects into $k$ non-empty subsets (order of them unimportant) is called a \emph{Stirling number of the second kind}, and is denoted $S(n,k)$ or $\begin{Bmatrix}n\\k\end{Bmatrix}$. See the Wikipedia page for information, including a table of some values, as well as a formula for $\begin{Bmatrix}n\\k\end{Bmatrix}$ as a series:$

https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind

$For your question, we could form the 8 non-empty subsets of 10 balls in $\begin{Bmatrix}10\\8\end{Bmatrix}=750$ ways (see the table of values on the Wikipedia page). Then, we can arrange each of these in $8!=40320$ ways. This makes the answer $8!\times \begin{Bmatrix}10\\8\end{Bmatrix} = 40320\times 750 = 30240000$.$

(An inductive proof of the series expression for S(n, k) may be found here: http://www.emis.de/journals/HOA/ADS/Volume1_2/157.pdf)

Finally... it's over.

(And thank you for your insightful answer!)

Drsoccerball · Aug 8, 2015

Re: 2015 permutation X2 marathon

If there is a rectangular table with 2 seats on one side symmetrically and 3 seats on the other side of the table find the probability that Ekman and Integrand would sit on the same side next to each other
Answer : \frac{2}{45}

Drsoccerball · Aug 8, 2015

Re: 2015 permutation X2 marathon

InteGrand said:
I think this is correct.

$What you were actually asking was how many ways to partition 10 distinct objects into 8 non-empty subsets, and then arrange them. The number of ways to partition $n$ distinct objects into $k$ non-empty subsets (order of them unimportant) is called a \emph{Stirling number of the second kind}, and is denoted $S(n,k)$ or $\begin{Bmatrix}n\\k\end{Bmatrix}$. See the Wikipedia page for information, including a table of some values, as well as a formula for $\begin{Bmatrix}n\\k\end{Bmatrix}$ as a series:$

https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind

$For your question, we could form the 8 non-empty subsets of 10 balls in $\begin{Bmatrix}10\\8\end{Bmatrix}=750$ ways (see the table of values on the Wikipedia page). Then, we can arrange each of these in $8!=40320$ ways. This makes the answer $8!\times \begin{Bmatrix}10\\8\end{Bmatrix} = 40320\times 750 = 30240000$.$

(An inductive proof of the series expression for S(n, k) may be found here: http://www.emis.de/journals/HOA/ADS/Volume1_2/157.pdf)

Here is a Q from the HSC 2015 4U Marathon about setting up a recursive formula for Stirling numbers of the second kind:

How is that =750

InteGrand · Aug 8, 2015

Re: 2015 permutation X2 marathon

Drsoccerball said:
How is that =750

It's not a binomial coefficient (notation was with curly brackets), if that's what you were wondering.

And it's 750 as seen from the table of values on the Wikipedia, or using the explicit formula for S(n, k) given there (a proof of that is given in another link in that post) (or look at sida1049's working, and you'll see it's 10C3 + ((10C2)•8C2)/2, which is 750).

braintic · Aug 9, 2015

Re: 2015 permutation X2 marathon

Drsoccerball said:
If there is a rectangular table with 2 seats on one side symmetrically and 3 seats on the other side of the table find the probability that Ekman and Integrand would sit on the same side next to each other
Answer : \frac{2}{45}

I'm not sure of the meaning of "symmetrically" in your question.
Your question is saying there are 5 seats altogether, right?

If so, I get 3/10, not your answer.

Edit: Assuming you meant 10 seats, spread 3,2,3,2 around the four sides of the table, I get 1/15, not 2/45.

Ekman · Aug 9, 2015

Re: 2015 permutation X2 marathon

braintic said:
I'm not sure of the meaning of "symmetrically" in your question.

And I get 3/10, not your answer.

Yeah I got that as well, but after I PM'ed him, he said that he meant to say 2 sides have 2 seats and the other 2 sides have 3 seats, so a total of 10 seats, rather than 5.

Also by saying symmetrically, im assuming he meant to say that the sides are identical.

Drsoccerball · Aug 9, 2015

Re: 2015 permutation X2 marathon

Each side has a different colour

Ekman · Aug 9, 2015

Re: 2015 permutation X2 marathon

Drsoccerball said:
Each side has a different colour

If im not mistaken, it should be 2/15

braintic · Aug 9, 2015

Re: 2015 permutation X2 marathon

Drsoccerball said:
Each side has a different colour

Makes no difference to the answer.

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

not actually a porcupine

Well-Known Member

Well-Known Member

Not_the_pad

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

HSC Hipster

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

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