Author Topic: TT's Maths Thread (Read 154347 times) Tweet Share

Ahmad · « **Reply #300 on:** December 05, 2009, 10:34:33 pm »

Oh that was directed at zzdfa. Also, they say the day you become a mathematician is the day after the night you spend awake scratching your head (or probably pulling your hair out, by then) over a problem

I might as well point out that a university friend of mine suffers deeply from that nerd snipe issue. If you give him an interesting problem he zones out completely to the point where if you call his name right to his face he can't hear you. Once I gave him a geometry problem and we didn't see him for a week at uni. After a week he came back and said that he was busy solving the problem.

TrueTears · « **Reply #301 on:** December 05, 2009, 10:35:30 pm »

Quote from: Ahmad on December 05, 2009, 10:34:33 pm

Oh that was directed at zzdfa. Also, they say the day you become a mathematician is the day after the night you spend awake scratching your head (or probably pulling your hair out, by then) over a problem

I've spent my entire afternoon until now on this problem lol and I still couldn't do it without your help =(

Ahmad · « **Reply #302 on:** December 05, 2009, 10:38:12 pm »

Frustrating over problems is one of the most important parts of the learning process, so don't despair. You've been getting better!

kamil9876 · « **Reply #303 on:** December 06, 2009, 12:04:58 am »

^ Yeah true, Ahmah. I've had a few of those moments though I ussually try to plan to postpone any possible nerd sniping of myself for the holidays or some unbusy time of the year.

By request, an algebraic argument for:

Quote

$\sum_{j=0}^k\binom{n}{j}\binom{m}{k-j} = \binom{n+m}{k}$

consider the $x^k$ term of $(x+1)^{n+m}$

this is simply $\binom{n+m}{k} x^k$ Hence the RHS.

Now another way to work this out is:

$(x+1)^{n+m}=(x+1)^n (x+1)^m$

$=(\binom{n}{0} x^n + \binom{n}{1}x^{n-1}...)(\binom{m}{0} x^m + \binom{m}{1}x^{m-1}...)$

But the only way to get a term that contributes to $x^k$ we get this by multiplying a $\binom{n}{j}x^j$ term from first factor by a $\binom{m}{k-j} x^{k-j}$ term from the second factor.

Then when we sum up and collect like terms etc, we get the LHS $\blacksquare$

TrueTears · « **Reply #304 on:** December 06, 2009, 02:00:43 am »

Wait so you have:

$(x+1)^{n+m} = \binom{n+m}{0}x^{n+m} + \binom{n+m}{1}x^{n+m-1} + \cdots + \binom{n+m}{n+m-1}x + 1$

$(x+1)^n(x+1)^m = \left[\binom{n}{0}x^n + \binom{n}{1}x^{n-1}+ \cdots + \binom{n}{n-1}x + 1\right]\left[\binom{m}{0}x^m + \binom{m}{1}x^{m-1}+ \cdots + \binom{m}{m-1}x + 1\right]$

Then what? How do you show that $\sum_{j=0}^k\binom{n}{j}\binom{m}{k-j} = \binom{n+m}{k}$ identity from what you have?

Is it like this?

Another way to write $(x+1)^{n+m} = \binom{n+m}{0}x^{n+m} + \binom{n+m}{1}x^{n+m-1} + \cdots + \binom{n+m}{n+m-1}x + 1 = \binom{n+m}{n+m}x^{n+m} + \binom{n+m}{n+m-1}x^{n+m-1} + \cdots + \binom{n+m}{1}x + 1$

Another way to write $(x+1)^n(x+1)^m = \left[\binom{n}{0}x^n + \binom{n}{1}x^{n-1}+ \cdots + \binom{n}{n-1}x + 1\right]\left[\binom{m}{0}x^m + \binom{m}{1}x^{m-1}+ \cdots + \binom{m}{m-1}x + 1\right] = \left[\binom{n}{n}x^n + \binom{n}{n-1}x^{n-1}+ \cdots + \binom{n}{1}x + 1\right]\left[\binom{m}{m}x^m + \binom{m}{m-1}x^{m-1}+ \cdots + \binom{m}{1}x + 1\right]$

$\therefore$ the coefficient of any term, namely, $x^k$ , where $k \le n+m$ , in the expansion of $(x+1)^{n+m}$ is $\binom{n+m}{k}$

Expanding $(x+1)^n(x+1)^m =\binom{n}{n}\binom{m}{m} x^{m+n} + \left(\binom{n}{n}\binom{m}{m-1}+\binom{n}{n-1}\binom{m}{m}\right) x^{m+n-1}+ \left(\binom{n}{n}\binom{m}{m-2}+ \binom{n}{n-1}\binom{m}{m-1} + \binom{n}{n-2}\binom{m}{m}\right)x^{n+m-2} + ... + 1$

Which means any coefficient of $x^k$ , where $k \le n+m$ , in the expansion of $(x+1)^n(x+1)^m$ can be written in the form of $x^k\left(\binom{n}{k}\binom{m}{0}+\binom{n}{k-1}\binom{m}{1}+ ... + \binom{n}{2}\binom{m}{k-2}+\binom{n}{1}\binom{m}{k-1} + \binom{n}{0}\binom{m}{k}\right)$

Equating $x^k$ coefficients yields: $\left(\binom{n}{k}\binom{m}{0}+\binom{n}{k-1}\binom{m}{1}+ ... + \binom{n}{2}\binom{m}{k-2}+\binom{n}{1}\binom{m}{k-1} + \binom{n}{0}\binom{m}{k}\right) = \binom{n+m}{k}$

$\mbox{LHS} = \sum_{j=0}^k\binom{n}{j}\binom{m}{k-j}$

$\therefore \sum_{j=0}^k\binom{n}{j}\binom{m}{k-j} = \binom{n+m}{k}$

kamil9876 · « **Reply #305 on:** December 06, 2009, 02:19:09 am »

yeah lol i shoulve used $\binom{n}{n} x^n$ instead of $\binom{n}{0} x^n$ to make the notation neater

and more clear

TrueTears · « **Reply #306 on:** December 06, 2009, 02:20:37 am »

Quote from: kamil9876 on December 06, 2009, 02:19:09 am

yeah lol i shoulve used $\binom{n}{n} x^n$ instead of $\binom{n}{0} x^n$ to make the notation neater and more clear

Haha, but that $(x+1)^{n+m}$ was the crux step, was that just from experience you knew that would lead to solving the problem?

kamil9876 · « **Reply #307 on:** December 06, 2009, 02:57:09 am »

Quote from: TrueTears on December 06, 2009, 02:20:37 am

Quote from: kamil9876 on December 06, 2009, 02:19:09 am
yeah lol i shoulve used $\binom{n}{n} x^n$ instead of $\binom{n}{0} x^n$ to make the notation neater and more clear
Haha, but that $(x+1)^{n+m}$ was the crux step, was that just from experience you knew that would lead to solving the problem?

i looked at RHS first because it looks simple. So I knew that i needed the power of the expansion to be n+m, and the x^k term. Also the fact that n and m are "broken up" in the LHS expression, i figured we need to break it up somehow.

TrueTears · « **Reply #308 on:** December 06, 2009, 04:02:15 am »

Quote from: TrueTears on December 05, 2009, 03:12:39 pm

1. In an office, at various times during the day, the boss gives the secretary a letter to type, each time putting the letter on top of the pile in the secretary's in-box. When there is time, the secretary takes the top letter off the pile and types it. There are nine letters to be typed during the day and the boss delivers them in the order 1,2,3,4,5,6,7,8,9. While leaving for lunch, the secretary tells a colleague that letter 8 has already been typed, but says nothing else about the morning's typing. The colleague wonders which of the nine letters remain to be typed after lunch and in what order they will be typed. Based upon the information given, how many such after-lunch typing orders are possible? (There are no letters left to typed is one of the possibilities.)

I think I've got this question after some thought.

The question can be split up into 2 scenarios. The letter 9 arrives before lunch break or it arrives after lunch break.

Let the case of it arriving before lunch break be $[A]$ .

Let the case of it arriving after lunch break be $[B]$ .

$[A]$

If letter 9 arrived before lunch then that means letter 8 have been typed and we are not sure whether letters of the set $\{1,2,3,4,5,6,7,9\}$ have been typed or not typed.

Some experimenting quickly leads to what we must count.

Say letter 1 arrives and the secretary immediately types it up, then letter 2 comes and the secretary does not have time to type it up, then letter 3,4,5,6,7 comes and she does not have the time to type them up until letter 8 comes which the secretary has time to type up and then finally letter 9 arrives which she does not type up.

This means after lunch she must type up the letter set $\{9,7,6,5,4,3,2\}$ (The letter numbers are placed from the top letter in the box down to the bottom letter in the box) which is a subset of $\{1,2,3,4,5,6,7,9\}$

Imagine another scenario, letter 1 comes and she types it up, letter 2 comes and she does not type it up. Letter 3, 4, 5 comes and she types all three up. Letter 6,7 come and she doesn't type up. 8 comes and she obviously types it up. 9 comes and she does not type it up.

This means after lunch she must type up the letter set $\{9,7,6,2\}$ (The letter numbers are placed from the top letter in the box down to the bottom letter in the box) which again is a subset of $\{1,2,3,4,5,6,7,9\}$

Now notice how the question also asks for the order of the typing, but the order of $\{9,7,6,5,4,3,2\}$ and $\{9,7,6,2\}$ is fixed as the secretary has no choice what to type since she types the letter on the top till the one on the very bottom.

The aim is clear: we need to find all possible subsets of $\{1,2,3,4,5,6,7,9\}$ which is found by $2^8$ .

$\therefore |[A]| = 2^8$

$[B]$

Now we ask what if the letter 9 comes after lunch?

Consider the set of letters that can be typed or not typed up before lunch in this case. It would be $\{1,2,3,4,5,6,7\}$

Now to be consistent with our experimentation in $[A]$ lets use the same example.

Letter 1 comes and she types it up, letter 2 comes and she does not type it up. Letter 3, 4, 5 comes and she types all three up. Letter 6,7 come and she doesn't type up. 8 comes and she obviously types it up. However this time letter 9 does not come, since it is still before lunch.

Now after the secretary comes back from lunch break she will have to type up $\{7,6,2\}$ (The letter numbers are placed from the top letter in the box down to the bottom letter in the box).

However this time the boss can give her the letter 9 at any time. Say she just returns from lunch break and her boss gives her letter 9, then she would have to type up $\{9,7,6,2\}$ .

If she already types up 7 and then her boss gives her letter 9, her typing order would now be $\{7,9,6,2\}$

There are 2 more possibilities of when her boss can give her letter 9 namely: $\{7,6,9,2\}$ and $\{7,6,2,9\}$

All of those orderings are from the very top letter in the box down to the bottom letter in the box.

Now we notice something, if she just returns from lunch break and her boss gives her letter 9, then she would have to type up $\{9,7,6,2\}$ , but the ordered group $\{9,7,6,2\}$ is already counted in $[A]$ which means we are only left with 3 ordered groups namely: $\{7,9,6,2\}$ , $\{7,6,9,2\}$ and $\{7,6,2,9\}$

Again we notice something, if the subset of $\{1,2,3,4,5,6,7\}$ contains 3 elements then there are 3 typing orders possible for that one set.

How many 3 element subsets are there for $\{1,2,3,4,5,6,7\}$ ? Well there are $\binom{7}{3}$ subsets which means there are a total of $\binom{7}{3}(3)$ typing orders for a subset with 3 elements.

Doing some more experimentation shows that for a 2 element subsets there are 2 typing orders for that set. Which means there are $\binom{7}{2}(2)$ typing orders for a subset with 2 elements.

Thus we require this summation:

$\sum_{j=1}^7 \left((j)\binom{7}{j}\right) = \sum_{j=1}^7 \frac{(j)(7!)}{(7-j)!j!} = \sum_{j=1}^7 \frac{(j)(7!)}{(7-j)!(j)(j-1)!} = \sum_{j=1}^7 \frac{(7!)}{(7-j)!(j-1)!} = \sum_{j=1}^7 \frac{(7)((6)!)}{(7-j)!(j-1)!} = 7 \sum_{j=1}^7 \binom{6}{7-j} = 7 \left(\binom{6}{6} + \binom{6}{5} + ... + \binom{6}{0}\right) = 7(2^6)$

(Notice we start from when $j = 1$ , ie when the subset of $\{1,2,3,4,5,6,7\}$ contains only 1 element, since if it contains 0 elements it is already counted in $[A]$ )

$\therefore |[B]| = 7(2^6)$

In total we have $|[A]| + |[B]| = 2^8 + 7(2^6) = 704$ typing orders!

TrueTears · « **Reply #309 on:** December 06, 2009, 04:06:53 am »

Another set of interesting questions:

~~1. In how many ways can four squares, not all in the same row or column be selected from an 8-by-8 chessboard to form a rectangle?~~

2. A gardener plants three maple trees, four oak trees and five birch trees in a row. He plants them in random order, each arrangement being equally likely. Find the probability that no two birch trees are next to one another.

~~3. 25 people sit around a circular table. Three of them are chosen randomly. What is the probability that at least two of the three are sitting next to one another?~~

/0 · « **Reply #310 on:** December 06, 2009, 05:28:06 am »

1.

Let an $m\times n$ be a rectangle with height m rows and width n columns.

The number of a particular rectangle can be easily counted by translating the original rectangle throughout the board.

For a 2x2 rectangle there are 7 possible horizontal and 7 possible vertical positions, in total 49.

2x2 rectangles: 7*7
2x3 rectangles: 6*7
2x4 rectangles: 5*7
...
2x8 rectangles: 1*7

3x2 rectangles: 7*6
3x3 rectangles: 6*6
...
3x8 rectangles: 1*6

So in total there are:

$7(7+6+5+4+3+2+1)+6(7+6+5+4+3+2+1)+...+1(7+6+5+4+3+2+1) = (7+6+5+4+3+2+1)^2=784$

(There must be exactly 2 squares in a row and 2 squares in a column. If there were 3 in the same row/column, then a rectangle would not be formed unless the 4th were in the same row/column, which is not allowed)

kamil9876 · « **Reply #311 on:** December 06, 2009, 12:11:31 pm »

alternative to 1:

If we select two points $(x,y)$ and $(x',y')$ such that $x\neq x'$ and $y\neq y'$ (ie two points that are not in same row nor in the same column) then we have defined the two opposite corners of a rectangle, which already defines the rectangle. The total number of ways of choosing such corners is: $\frac{1}{2}*64*(64-8-8+1)=32*49$ ways of doing this. However each rectangle has two different pair of opposite corners, hence we halve that number to get $16*49$ .

kamil9876 · « **Reply #312 on:** December 06, 2009, 12:21:35 pm »

3.) Sketch:

Let's try to find how many ways there are when none of them sit next to one another. If we choose one person, then we cannot choose the two people sitting next to him, hence we have 22 people left to choose. Then when we choose the next person, there are two possibilities that may occur:

1.)

**xCx****xCx**

C means chosen, * means unchosen and avaibalbe, x means unavaibable. In this case we have 19 people left for the third person to choose.

2.)

***xCxCx***

In this case, we have 20 people left to choose for the third person.

Now just work out how many different ways there are to choose the people, then subtract from the total number of ways of choosing people in this manner (23*24*25), and then divide by this total.

TrueTears · « **Reply #313 on:** December 06, 2009, 03:20:55 pm »

Thanks kamil, /0 =]

Ahmad · « **Reply #314 on:** December 06, 2009, 03:50:17 pm »

Cool way to do 1: $\binom{8}{2}^2 = 784$ (why?)

Search the forums now!

We have moved!

Author Topic: TT's Maths Thread (Read 154347 times) Tweet Share

Ahmad

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

Ahmad

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

/0

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

Ahmad

Re: TT's Maths Thread

Recent Posts

User:
Password: