Math Solutions
Author 
Message 
SilverSprite

Posted: Mon Jul 21, 2003 9:26 am Post subject: (No subject) 


short my ass.. its a corr. question 





Sponsor Sponsor



bugzpodder

Posted: Mon Jul 21, 2003 3:48 pm Post subject: (No subject) 


i never said its going to be easy or its solution is gonna be short (just the question is short). besdies some corr problems are easy. 





Crono

Posted: Mon Jul 21, 2003 8:20 pm Post subject: (No subject) 


tat aint so fair, usin other kidz 2 do ur corr. questions, lol... 





AsianSensation

Posted: Mon Jul 21, 2003 8:56 pm Post subject: (No subject) 


Crono wrote: tat aint so fair, usin other kidz 2 do ur corr. questions, lol...
Bugz is using us for math now eh? lol, I can't ever imagine the day that would happen...
anyways, if no one answer to the question, bugz will eventually have to give out a solution, right? So that's like having him doing correspondence for us 





bugzpodder

Posted: Mon Jul 21, 2003 10:44 pm Post subject: (No subject) 


go check the due date, it was already due one month ago!
i'll post the solution eventually 





bugzpodder

Posted: Mon Jul 21, 2003 10:45 pm Post subject: (No subject) 


and mr silversprite who thinks he knows EVERYTHING, has to screw things up for me!! 





bugzpodder

Posted: Mon Jul 21, 2003 10:45 pm Post subject: (No subject) 


who got the big mouth now? who keep on telling everyone stuff? now everyone's like: I give up. you think this one is hard? wait till you find out where the other question came from in the "Proof" Thread (after all, i dont want to insult anyone's intelligence by given them something they could do easily!) 





SilverSprite

Posted: Tue Jul 22, 2003 1:41 pm Post subject: (No subject) 


hahahahahahahahhaaha yeah ok bugz 





Sponsor Sponsor



SilverSprite

Posted: Wed Jul 23, 2003 3:20 am Post subject: (No subject) 


bugzpodder wrote: short little problem: Prove gcd(nCi,nCj)>1, given 0<i,j<n
Hmm... what if i=j? Then gcd(nCi,nCj) = nCi. And we know n is at least 2 because of the restrictions on i and j. 





SilverSprite

Posted: Wed Jul 23, 2003 3:30 am Post subject: (No subject) 


Now a formal proof assuming Bugz forgot to put i cannot equal j.
This one seemed harder last time i checked it out?? I think i made a mistake somewhere here or there. Anyways check it out Bugz/Crono.
I will prove the given assertion through induction on n.
The base case where n=3 is obvious.
Assume the inductive hypothesis (the condition is true for n=k).
Now:
(k+1)_C_(k+1i) = (k+1)/(k+1i) * k_C_i.
Similarly for j.
Since gcd(k_C_i,k_C_j)>1,
therefore gcd((k+1)/(k+1i) * k_C_i, (k+1)/(k+1j) * k_C_j)>1. 





bugzpodder

Posted: Wed Jul 23, 2003 12:10 pm Post subject: (No subject) 


doesnt follow thru at all, suppose i want 18C3 and 18C9, what are you going to induct on?
suppose gcd(nCi,nCj)=m,
k+1=p*q, gcd(p,q)=1
k+1i=m*p
k+1j=m*q
then wouldn't your inductive step fail? 





SilverSprite

Posted: Wed Jul 23, 2003 12:47 pm Post subject: (No subject) 


SilverSprite wrote: Now a formal proof assuming Bugz forgot to put i cannot equal j.
This one seemed harder last time i checked it out?? I think i made a mistake somewhere here or there. Anyways check it out Bugz/Crono.
I will prove the given assertion through induction on n.
The base case where n=3 is obvious.
Assume the inductive hypothesis (the condition is true for n=k).
Now:
(k+1)_C_(i) = (k+1)/(k+1i) * k_C_i.
Similarly for j.
Since gcd(k_C_i,k_C_j)>1,
therefore gcd((k+1)/(k+1i) * k_C_i, (k+1)/(k+1j) * k_C_j)>1.
[edit] >typo 





SilverSprite

Posted: Wed Jul 23, 2003 12:55 pm Post subject: (No subject) 


I knew it was too good to be true hehe.. Oh well worth a shot. 





kmd10

Posted: Fri Aug 08, 2003 3:13 pm Post subject: (No subject) 


sure, old topic, but i'm in the mood.
if you are proving that gcd(nCi,nCj) > 1, you are proving that there is a number that divides both nCi and nCj, that isn't 1.
if there is a number that divides nCi and nCj, that isn't 1, then you've proved that the greatest common divisor is greater than 1, whether it's the number you found or not.
now:
code: 
nCi = n! / (ni)!(i)!

by saying that i and j are always less than n, and greater than 0, we are never dividing n! by n. therefore, we will only ever be dividing n! by numbers between 1 and n1. if you expand the formula:
code: 
nCi = (n)(n1) ... (2)(1) / (ni)(ni1) ... (2)(1) * (i)(i1) ... (2)(1)

you can see that the n in the numerator will never be reduced to 1, since you are never dividing by n; you are always dividing by numbers smaller than n (like ni, and i, which are always less than n). as a result, in both nCi and nCj, the numerator will always have at least the lowest factor of n, and so nCi and nCj have a common divisor of this lowest factor, which will always be greater than 1.
i'm having a bit of trouble explaining what i mean, but i hope you can understand.
what i'm essentially saying is that nCi and nCj will always have a common divisor of at least the smallest factor of n that isn't 1.
example:
code: 
8C3 = 28
8C4 = 56
28 and 56 are both divisible by 2, which is the lowest factor of 8.

ok, the easiest way of looking at it is this.
if you don't understand my proof above, i can show you what i proved.
in pascal's triangle, the nth (0based) row corresponds to nC0, nC1, etc.
the question is asking to prove that every row of pascal's triangle has a common divisor greater than 1. if you look at the triangle, you can see that if you take the second number in each row (which is actually the row number) and find its lowest factor greater than 1, every term in that row is divisible by it. this proves the question.
code: 
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 25 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1







AsianSensation

Posted: Fri Aug 08, 2003 5:22 pm Post subject: (No subject) 


kmd10 wrote:
if you look at the triangle, you can see that if you take the second number in each row (which is actually the row number) and find its lowest factor greater than 1, every term in that row is divisible by it. this proves the question.
a proof cannot be based on observation, unless you use induction. You can't just "see" that it is like this, you have to "prove", through mathematical means that it works.
so far, you just showed an observation, not a proof. 






