Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Math Solutions
Index -> Contests
Goto page Previous  1, 2, 3, 4, 5  Next
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
SilverSprite




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

short my ass.. its a corr. question Razz
Sponsor
Sponsor
Sponsor
sponsor
bugzpodder




PostPosted: 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




PostPosted: 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




PostPosted: 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 Razz
bugzpodder




PostPosted: 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




PostPosted: 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




PostPosted: 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




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

hahahahahahahahhaaha yeah ok bugz
Sponsor
Sponsor
Sponsor
sponsor
SilverSprite




PostPosted: 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




PostPosted: 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+1-i) = (k+1)/(k+1-i) * k_C_i.
Similarly for j.

Since gcd(k_C_i,k_C_j)>1,
therefore gcd((k+1)/(k+1-i) * k_C_i, (k+1)/(k+1-j) * k_C_j)>1.
bugzpodder




PostPosted: 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+1-i=m*p
k+1-j=m*q

then wouldn't your inductive step fail?
SilverSprite




PostPosted: 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+1-i) * k_C_i.
Similarly for j.

Since gcd(k_C_i,k_C_j)>1,
therefore gcd((k+1)/(k+1-i) * k_C_i, (k+1)/(k+1-j) * k_C_j)>1.


[edit] -->typo
SilverSprite




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

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




PostPosted: 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! / (n-i)!(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 n-1. if you expand the formula:

code:

nCi = (n)(n-1) ... (2)(1) / (n-i)(n-i-1) ... (2)(1) * (i)(i-1) ... (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 n-i, 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 (0-based) 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




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

kmd-10 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.
Display posts from previous:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 4 of 5  [ 71 Posts ]
Goto page Previous  1, 2, 3, 4, 5  Next
Jump to:   


Style:  
Search: