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
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
bugzpodder




PostPosted: Fri Aug 08, 2003 9:16 pm   Post subject: (No subject)

observations that are false are even worse Very Happy no offense or anything, but
Quote:
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.


guess what gcd(12C3,12C4) is?
now do it
Sponsor
Sponsor
Sponsor
sponsor
kmd-10




PostPosted: Fri Aug 08, 2003 10:42 pm   Post subject: (No subject)

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.

sorry, i hope i'm not making a moron of myself here. but what i did say, is at least the smallest factor of n that isn't 1.

C(12,3) = 220, and C(12,4) = 495, if i did them right.

the smallest non-1 factor of 12 is 2. the gcd of 220 and 495 is at least 5, as i'm too lazy to actually figure it out. and 5 is definitely greater than 2.

also, the information above the pascal's triangle bit is actually a proof. as messy and informal as it is, i don't see a flaw in it. of course, there may be one, but i don't see it. and it really shouldn't be counted out because of its disorganization. if you like, i can try and clean it up.

sorry to create the confusion i have. please don't treat me like a novice, even if my post count gives me that title. i may have made a mistake, i may not have -- i'm just trying to participate in the conversations and stuff.

anyway, let's keep going!
AsianSensation




PostPosted: Sat Aug 09, 2003 9:16 am   Post subject: (No subject)

kmd-10 wrote:
also, the information above the pascal's triangle bit is actually a proof. as messy and informal as it is, i don't see a flaw in it.


a proof is something like this:

take question #2:

You have to either give an algebraic proof why this is the case, or you have to show, by induction (which uses algebra) or comparison (which is the solution posted up) why that is the case.

You cannot just keep on adding and adding, since the n could be any number.

Much like the Pascal's Triangle, it extend itself infinitely, you cannot test every single case. The observation made cannot be validated unless you give a reason why it works like that.

And of course, we do not think of you as a novice, the fact you tried to give solution to this tough problem is one of the reasons. I am merely pointing out why your solution was not valid.
AsianSensation




PostPosted: Sat Aug 09, 2003 9:18 am   Post subject: (No subject)

Bugz, if your not too busy, can you give a question in which if you merely observe, it seems like it follows a certain pattern, except it actually doesn't?

I can't find a question like that, so if you don't mind, can you post up a question that helps to explain the "observation is not a valid proof" statement?
bugzpodder




PostPosted: Sat Aug 09, 2003 11:49 am   Post subject: (No subject)

Quote:
also, the information above the pascal's triangle bit is actually a proof.

I suppose you are talking about this "proof":
Quote:
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.


first of all, "see" isnt an actual proof, "see" is just an observation. and unfortunately, this observation is wrong. I have already showed you a case where it fails, C(12,3) = 220, and C(12,4) = 495
according to your observation, every number in row 12 is divisible by the lowest factor of 12 greater than 1. so according to your statement C(12,3) must be divisible by 3. but it is not, hence your observation is false.

Mr. White is right, a lot of ppl indeed have does not know how to do proofs. kmd, personally I think you are one of them. I am not saying this to offend you, but rather, i am trying to help you. there is nothing wrong being a novice, at long as we learn in the process. we are all novice at something, and of course, even if we are good at something, we were just a 'novice' at it once upon a time.
bugzpodder




PostPosted: Sat Aug 09, 2003 11:51 am   Post subject: (No subject)

AsianSensation wrote:
Bugz, if your not too busy, can you give a question in which if you merely observe, it seems like it follows a certain pattern, except it actually doesn't?

I can't find a question like that, so if you don't mind, can you post up a question that helps to explain the "observation is not a valid proof" statement?


goldbach's conjecture. make your observation, and prove it
AsianSensation




PostPosted: Sat Aug 09, 2003 1:18 pm   Post subject: (No subject)

um....Bugz? You want ME to PROVE Goldbach's conjecture?

Evil or Very Mad Evil or Very Mad Evil or Very Mad Evil or Very Mad Evil or Very Mad Evil or Very Mad

How the hell am I suppose to do that? Crazy old bastard....

(j/k)

but still, I can't possibly prove Goldbach's conjecture, there is like no way in hell. If you threaten my life with it, I still can't prove it....
kmd-10




PostPosted: Sat Aug 09, 2003 1:34 pm   Post subject: (No subject)

haha, i think this is kind of funny.

you need to read my statements carefully. i didn't say that every number in a row is divisible by the lowest non-1 factor of n. i said at least that.

i didn't make this by observation.

i proved it by use of logic. there isn't much formality in it, i admit. but it's an acceptable proof, as it shows, for all cases, what i am saying.

the bit about pascal's triangle was only to show what i had proven.

everything before "ok, the easiest way of looking at it is this" is a proof of what i display using pascal's triangle. and what i had proven is that in any row of pascal's triangle (or, for every set of nCr), each term is divisible by at least the smallest factor of n that isn't 1.

there is a proof. please don't look at the pascal's triangle section until you understand that there is a proof above it. later on i think i will formalize my proof, since that seems to be what everyone wants.

i do know how to construct a formal proof. i just chose to show what i found in order of how i logically thought of it.
Sponsor
Sponsor
Sponsor
sponsor
kmd-10




PostPosted: Sat Aug 09, 2003 1:36 pm   Post subject: (No subject)

"also, the information above the pascal's triangle bit is actually a proof."

yes, above the pascal's triangle bit. the part that doesn't mention pascal's triangle at all.

and you know what .. i made a mistake in one part. i didn't mean that every number was divisible by the smallest non-1 factor, but at least that number.
kmd-10




PostPosted: Sat Aug 09, 2003 2:48 pm   Post subject: (No subject)

nCi = n! / (n-i)! * (i)!
nCj = n! / (n-j)! * (j)!

it is easiest to follow this proof if you focus on this method of calculating nCr.

if you write out nCr in the way shown above, and expand factorials, then cancel out the numbers from top and bottom.

example:

code:

7C3
= (7!) / (7-3)! * (3)!
= 7! / 4! * 3!
= (7)(6)(5)(4)(3)(2)(1) / (4)(3)(2)(1) * (3)(2)(1)
= (7)(6)(5) / (3)(2)(1)
= (7)(2)(5) / (2)(1)
= (7)(1)(5) / (1)
= (7)(5)
= 35



there are four cases.
case 1: n is prime. in this case, you will have all numbers in the form nCr divisible by n, since you will never be able to divide n from the numerator.
case 2: n is not prime, and both max(i, n-i) and max(j, n-j) are less than the greatest prime less than n. in this case, the greatest prime less than n will divide all the numbers in this form, since it will not be cancelled out from the numerator.
case 3: n is not prime, and one or both of max(i, n-i) and max(j, n-j) are greater than or equal to the greatest prime less than n. in this case, the greatest prime less than n will be cancelled out from the top of one or both. in this case, one of the prime factors of n will divide both numbers. this is because the denominator will never contain all the factors of n. there will always be one (at least) left over, since the greatest remaining number in the denominator is n-max(i,n-i), and in the numerator, the smallest number is max(i,n-i)+1. the numbers in the numerator will take care of all but at least one of the prime factors of n in the denominator, leaving at least one to be a common divisor. it will not be 1, therefore, and if there is one divisor greater than 1, the greatest divisor must also be greater than one.

i think there might be a flaw in case 3, since i rushed it and have to go, but if there is, i'm sure it can be easily corrected.
bugzpodder




PostPosted: Sat Aug 09, 2003 8:02 pm   Post subject: (No subject)

i agree with your case #1,and #2.
Quote:

n is not prime, and one or both of max(i, n-i) and max(j, n-j) are greater than or equal to the greatest prime less than n. in this case, the greatest prime less than n will be cancelled out from the top of one or both.


true
Quote:

this case, one of the prime factors of n will divide both numbers.
this is because the denominator will never contain all the factors of n.

i suppose the few sentences below is a proof fo these statements.

Quote:

since the greatest remaining number in the denominator is n-max(i,n-i), and in the numerator, the smallest number is max(i,n-i)+1

remaining number? what are you talking about?

correct me if i am wrong, but as i understand you are trying to show in case 3 that there is at least one prime factor of n in the number nCi -- since you never refered to nCi and nCj together. but what if nCi have factor of p and nCj have only factor of q and n=p*q?
Display posts from previous:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

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


Style:  
Search: