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

Drsoccerball · Aug 16, 2015

Re: 2015 permutation X2 marathon

Kaido said:
Dont know if this question is hard enough to be X2, but anyways...

A classic b-day problem:
30 people in a room, what is the probability that at least 2 people have the same b-day

First of all make sure you give the answer with the question
1-(0 people)
1-( $\frac{30}{365} \cdot \frac{29}{364}...\frac{1}{336}$ )

Kaido · Aug 16, 2015

Re: 2015 permutation X2 marathon

Drsoccerball said:
First of all make sure you give the answer with the question
1-(0 people)
1-( $\frac{30}{365} \cdot \frac{29}{364}...\frac{1}{336}$ )

Yeah m8 soz, gimme yo answer in actual percentage

I didnt simplify in exam, lost a mark rofl, calc bs on me

kawaiipotato · Aug 16, 2015

Re: 2015 permutation X2 marathon

dunno if this is MX2 and I don't have the answer lol, just saw this somewhere
https://i.imgur.com/0YFCJhC.jpg

braintic · Aug 16, 2015

Re: 2015 permutation X2 marathon

Drsoccerball said:
First of all make sure you give the answer with the question
1-(0 people)
1-( $\frac{30}{365} \cdot \frac{29}{364}...\frac{1}{336}$ )

Nup.

1 - 364/365 . 363/365 . 362/365 . ... . 336/365

InteGrand · Aug 16, 2015

Re: 2015 permutation X2 marathon

kawaiipotato said:
dunno if this is MX2 and I don't have the answer lol, just saw this somewhere
https://i.imgur.com/0YFCJhC.jpg

$Total of 30 to pick from initially.$
$Pick the first item (30 ways to do it). This eliminates 5 from its row from its column and 5 from its column (counting itself only once). So for the next one, there's now a choice of $30-5-5=20$.$

$Pick the next one (20 ways to do it). This now eliminates $10-2=8$ new ones (including itself), since the second object was from a different row and column to the first one, but two of the ones it would eliminate are already eliminated from before. So there are now $20-8=12$ options to pick the third from.$

$Pick the final one (12 ways). We have the total no. of ways being (to account for over-counting) $\frac{30\times 20 \times 12}{3!}=1200$ (since the order of a set does not matter).$

braintic · Aug 16, 2015

Re: 2015 permutation X2 marathon

kawaiipotato said:
dunno if this is MX2 and I don't have the answer lol, just saw this somewhere
https://i.imgur.com/0YFCJhC.jpg

(6×5)×(5×4)×(4×3)

Edit: Yes - forgot the multiple counting.

braintic · Aug 16, 2015

Re: 2015 permutation X2 marathon

[*]

Give a combinatorics reason (NOT a binomial theorem reason) why

n.2^(n-1) = nC1 + 2.nC2 + 3.nC3 + ... + n.nCn

[I actually don't recall the reason and am trying to remind myself. So a prompt would be useful rather than the entire answer.]

InteGrand · Aug 16, 2015

Re: 2015 permutation X2 marathon

braintic said:
[*]

Give a combinatorics reason (NOT a binomial theorem reason) why

n.2^(n-1) = nC1 + 2.nC2 + 3.nC3 + ... + n.nCn

[I actually don't recall the reason and am trying to remind myself. So a prompt would be useful rather than the entire answer.]

Does this work?:

Consider a group of n people. Count the no. of ways to: form a subcommittee from those people (with at least 1 person and at most n people in the subcommittee) and then elect a leader out of those chosen for the subcommittee. The RHS is one way to count this. The LHS counts this because we can pick the leader first in n ways, and for the remaining (n – 1) people, we decide whether they're in the subcommittee or not.

braintic · Aug 16, 2015

Re: 2015 permutation X2 marathon

Yep, that's it. One of my students came up with that a couple of years ago, but I couldn't remember it.

braintic · Aug 17, 2015

Re: 2015 permutation X2 marathon

[*]

Let T_n be the number of ORDERED subsets of n distinct objects.

Show that as n approaches infinity, T_n approaches e.n!

InteGrand · Aug 17, 2015

Re: 2015 permutation X2 marathon

braintic said:
[*]

Let T_n be the number of ORDERED subsets of n distinct objects.

Show that as n approaches infinity, T_n approaches e.n!

$The number of $k$-subsets is $\binom{n}{k}=\frac{n!}{k!(n-k)!}$ ($k=0,1,2,...,n$), and each can be ordered in $k!$ ways. Therefore,$

$T_n = \sum _{k=0}^n k!\cdot \frac{n!}{k!(n-k)!}$

$=\sum _{k=0}^n \frac{n!}{(n-k)!}$

$=\sum _{k=0}^n \frac{n!}{k!}$

$\Rightarrow T_n=n!\sum _{k=0}^n \frac{1}{k!}$

$\Rightarrow \frac{T_n}{n!}=\sum _{k=0}^n \frac{1}{k!}\to e$ as $n\to \infty$

$that is, $\frac{T_n}{e\cdot n!}\to 1$ as $n\to \infty$.$

(Most Year 12's probably wouldn't know about the infinite series for e I'm guessing...did you have some other method in mind?)

Drsoccerball · Aug 17, 2015

Re: 2015 permutation X2 marathon

InteGrand said:
$The number of $k$-subsets is $\binom{n}{k}=\frac{n!}{k!(n-k)!}$ ($k=0,1,2,...,n$), and each can be ordered in $k!$ ways. Therefore,$

$T_n = \sum _{k=0}^n k!\cdot \frac{n!}{k!(n-k)!}$

$=\sum _{k=0}^n \frac{n!}{(n-k)!}$

$=\sum _{k=0}^n \frac{n!}{k!}$

$\Rightarrow T_n=n!\sum _{k=0}^n \frac{1}{k!}$

$\Rightarrow \frac{T_n}{n!}=\sum _{k=0}^n \frac{1}{k!}\to e$ as $n\to \infty$

$that is, $\frac{T_n}{e\cdot n!}\to 1$ as $n\to \infty$.$

(Most Year 12's probably wouldn't know about the infinite series for e I'm guessing...did you have some other method in mind?)

There was a similar question to this in our exam today :
prove probability of winning: p^n(2-p^n) where he has to answer n questions in a row and can get 1 wrong but has to start again

Kaido · Aug 18, 2015

Re: 2015 permutation X2 marathon

InteGrand said:
$The number of $k$-subsets is $\binom{n}{k}=\frac{n!}{k!(n-k)!}$ ($k=0,1,2,...,n$), and each can be ordered in $k!$ ways. Therefore,$

$T_n = \sum _{k=0}^n k!\cdot \frac{n!}{k!(n-k)!}$

$=\sum _{k=0}^n \frac{n!}{(n-k)!}$

$=\sum _{k=0}^n \frac{n!}{k!}$

$\Rightarrow T_n=n!\sum _{k=0}^n \frac{1}{k!}$

$\Rightarrow \frac{T_n}{n!}=\sum _{k=0}^n \frac{1}{k!}\to e$ as $n\to \infty$

$that is, $\frac{T_n}{e\cdot n!}\to 1$ as $n\to \infty$.$

(Most Year 12's probably wouldn't know about the infinite series for e I'm guessing...did you have some other method in mind?)

How'd you get from 2nd step to 3rd lol

InteGrand · Aug 18, 2015

Re: 2015 permutation X2 marathon

Kaido said:
How'd you get from 2nd step to 3rd lol

$Both sums contain exactly the same terms (write them out to see, the terms are just reversed). It's analogous to the integration identity $\int _0 ^ a f(x) \text{ d}x = \int _0^a f(a-x)\text{ d}x$.$

Ekman · Aug 18, 2015

Re: 2015 permutation X2 marathon

InteGrand said:
$The number of $k$-subsets is $\binom{n}{k}=\frac{n!}{k!(n-k)!}$ ($k=0,1,2,...,n$), and each can be ordered in $k!$ ways. Therefore,$

$T_n = \sum _{k=0}^n k!\cdot \frac{n!}{k!(n-k)!}$

$=\sum _{k=0}^n \frac{n!}{(n-k)!}$

$=\sum _{k=0}^n \frac{n!}{k!}$

$\Rightarrow T_n=n!\sum _{k=0}^n \frac{1}{k!}$

$\Rightarrow \frac{T_n}{n!}=\sum _{k=0}^n \frac{1}{k!}\to e$ as $n\to \infty$

$that is, $\frac{T_n}{e\cdot n!}\to 1$ as $n\to \infty$.$

(Most Year 12's probably wouldn't know about the infinite series for e I'm guessing...did you have some other method in mind?)

Its quite a common question for inequalities to ask the infinite series for e, so I guess year 12's should be able to recognise it.

braintic · Aug 18, 2015

Re: 2015 permutation X2 marathon

Ekman said:
Its quite a common question for inequalities to ask the infinite series for e, so I guess year 12's should be able to recognise it.

Actually, it is not something HSC students need to know. I asked the question on the basis that this result would have been derived in an earlier part.

braintic · Aug 19, 2015

Re: 2015 permutation X2 marathon

[*]

A special chessboard has 25 squares by 25 squares.
In how many ways can a knight move from the top left corner to the bottom right corner if it only moves down and to the right?

Answer: 12870

simpleetal · Aug 19, 2015

Re: 2015 permutation X2 marathon

braintic said:
[*]

A special chessboard has 25 squares by 25 squares.
In how many ways can a knight move from the top left corner to the bottom right corner if it only moves down and to the right?

Answer: 12870

I'll assume that everyone knows how a knight moves in a chess board. Since the piece starts at the top left corner and has to travel to the bottom right in a 25 x 25 board, it must move right 24 squares, and down 24 squares. As there is a condition that the knight can only move down and to the right, the only moves possible are the ones where:

a) The knight moves two spaces to the right, and one space down
b) The knight moves two spaces down, and one space to the right

Suppose that the journey involves m moves of a), and n moves of b). So, the total number of spaces the knight moves to the right is 2m+n, which equals 24. Similarly, the total number of times the knight moves down is equal to 2n+m, which equals 24. Simultaneously solving for these equations gives us that m=n=8. Hence, there are 8 moves each of a) and b), in some order. So basically, all we need to do is find the number of ways in which 8As, and 8Bs can be arranged in a row, which is 16C8= 12870

Chlee1998 · Aug 19, 2015

Re: 2015 permutation X2 marathon

How many ways can the name 'CHRISTIAN LEE' (yay my name!!) be arranged so that no vowels are together?

braintic · Aug 19, 2015

Re: 2015 permutation X2 marathon

Chlee1998 said:
How many ways can the name 'CHRISTIAN LEE' (yay my name!!) be arranged so that no vowels are together?

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

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

Well-Known Member

be.

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

be.

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Member

Member

Well-Known Member

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