Computer Science Canada

Math Solutions

Author:  AsianSensation [ Sat Jun 28, 2003 6:15 pm ]
Post subject:  Math Solutions

ok, time to post some solvable math problems, I'll give bits to the person that comes up with these solutions. They don't have to be correct, but if there is something interesting that you did, I will also award bits. I just want to learn something new out of this.

*note: I haven't done any of these problems myself, so I will be participating at the same time as everyone else. Therefore, to prevent me from getting a head start, I will not do the problem until a day after.

Question #1:

show that there are no integers a, b, c for which a^2 + b^2 - 8c = 6

Author:  krishon [ Sat Jun 28, 2003 6:21 pm ]
Post subject: 

welll, all i do is just substitute numbers in

i'd put c=1 and test that...and theres no solutions for that one
then i'd do c=2 and so on...but those dun't work either..so there's no solution.

Author:  AsianSensation [ Sat Jun 28, 2003 6:27 pm ]
Post subject: 

haha...funny....

I doubt that is a solution, because you cannot check for an infinite number of a, b and c.

anyways, to prevent spamming, or people fooling around, I will propose a negative bit system. The idea is I keep track of the participant, and if someone spams, then they receive minus something bits, and even if they send solutions later and receive bits, it will be added on to that negative value.

example:

-dodge_tomahawk spams
-dodge_tomahawk now have -20 bits(in this thread)
-dodge_tomahawk sends in a solution
-I award 15 bits
-now he has -5 bits(in this thread)

so as you can see, you will not receive bits if you continuously post stupid stuff.

Author:  krishon [ Sat Jun 28, 2003 6:31 pm ]
Post subject: 

well that's wuzn't really my solution...i wuz tellin u my method...

Author:  SilverSprite [ Sat Jun 28, 2003 7:20 pm ]
Post subject: 

where are you getting these from btw?

Author:  Crono [ Sat Jun 28, 2003 7:28 pm ]
Post subject: 

clearly i'll b cheatin if i did these problems, lol, it's just not fair fo the rest of u guyz...haha, nah, just j/k...anywho, want hints? ask me...

Author:  SilverSprite [ Sat Jun 28, 2003 7:45 pm ]
Post subject: 

yeee crono is your main math man... lol anyways i have the solution.. another 10 second one meng you gimp.. get harder ones than these or do you WANT to give free bits away.. well here it goes

when ever i do a2 or b2 it means a^2 or b^2

assume that there exists integer values for a,b,c such that
a2 + b2 - 8c = 6

a2 + b2 = 6+8c
look at this in mod4.. where a perfect square is either 1 or 0.. therefore three are two cases
CASE 1:a2=1 mod 4 and b2=1 mod 4 from this it follows that 6-8c = 2 mod 4 and c=0 mod 4
CASE 2: a2=0 mod 4 and b2=0 mod 4 from this it folllows that 4c=3 mod 4 and so this case is also extraneous since c is integral

we are left with CASE 1.. both a and b are odd and c is a multiple of 4..
from this it follows that m(m+1) + n(n+1) = 2c+1.. the RHS is obviously even and the LHS is obviously odd. Hence contradiction.. therefore no integer values of a,b,c satisfy the above condition

Author:  SilverSprite [ Sat Jun 28, 2003 7:46 pm ]
Post subject: 

and i'll need more than 15 bits for YOUR sorry excuse of a question making me do math this summer!!Razz

Author:  SilverSprite [ Sat Jun 28, 2003 7:55 pm ]
Post subject: 

i used 6-8c instead of 6+8c.. however this does not change anything.. the result is the same.. my bad:S

Author:  SilverSprite [ Sat Jun 28, 2003 7:58 pm ]
Post subject: 

i also forgot to mention that i let a=2n+1 and b=2m+1... haha i'm wayy out of it today

Author:  AsianSensation [ Sun Jun 29, 2003 10:04 am ]
Post subject: 

yeah, it wouldn't be fair if Crono or Bugz start to do these questions, but there are still good solutions to some of the problems.

SilverSprite gave the correct solution, and that's the way I did it too. But I found a better solution, much cooler:

Alternate Solution:

every integer in the world is the forms: 4n, 4n+1, 4n+2, or 4n+3.

the modulus equivalent of each of the above cases squared is either 0, 1, or 4 (mod 8 ).

8c+6 is equivalent to 6(mod 8 ), and therefore, it is not possible to form something equal to 6(mod 8 ) from the sum of two perfect squares.

Author:  AsianSensation [ Sun Jun 29, 2003 10:06 am ]
Post subject: 

Score Board

I will tally up the scores for each participant in here.

So far...

SilverSprite: 0 bits
Bugzpodder: 0 bits
Crono(if he ever wish to participate): 0 bits

*Note, I will only pay out the bits at the end of each week, so it would be easier for me to "take away" bits. (I can't actually give you minus bits, Im not a mod, though I wish I could be, for this thread anyways Confused )

Author:  AsianSensation [ Sun Jun 29, 2003 10:14 am ]
Post subject: 

Btw, I haven't done these problems myself, so I don't know how hard or ho easy it is, so if I post up a really hard question that looks easy, then it's not my fault.

The first question was easy, next few would get increasingly harder.

anyways, on to the next one

Question #2:

prove that for n = 1, 2, 3...

1 + 1/1! + 1/2! + 1/3! + ... + 1/n! < 3

Author:  krishon [ Sun Jun 29, 2003 10:25 am ]
Post subject: 

well here's how i did it

since 1 + 1/1! is already equal to two

1/2! + 1/3! ... 1/n! > 1

and then worked out the rest. when u add the other ones...the sum increases by a continually smaller amount so that it can never reach one. am i right?

Author:  SilverSprite [ Sun Jun 29, 2003 11:59 am ]
Post subject: 

asian. your way cooler solution is the same solution as mine..just presented differently:P.. so dont go saying its way cooler geek.. and 4 in modulus 4 is the same as 0 LOSER

Author:  AsianSensation [ Sun Jun 29, 2003 4:46 pm ]
Post subject: 

SilverSprite wrote:
asian. your way cooler solution is the same solution as mine..just presented differently:P


um..have you read the entire thing completely? Yours compare parity, and the other solution compares answers in modulus form. You used a bit of modulus math, in fact, that modulus math you used wasn't even needed, you could have simplified and got the same result, and it comes down to parity.

SilverSprite wrote:
and 4 in modulus 4 is the same as 0


um.....what? I know that's true, but what does that have to do with the other solution?

Author:  AsianSensation [ Sun Jun 29, 2003 5:31 pm ]
Post subject: 

Solutions to Question #2:

1 + 1/1! = 2

now we have to prove
1/2! + 1/3! + ... + 1/n! < 1

First we look at the sum of a geometric series, with r term 1/2.
1/2 + 1/(2^2) + 1/(2^3) + ... + 1/(2^n)

compare each one of these terms with the series
1/2! + 1/3! + ... + 1/n!

1) 1/2, 1/4, 1/8, ... 1/(2^n)
2) 1/2, 1/6, 1/24, ...1/n!

it is clearly seen that 1) > 2)

the sum of 1) is (1/2(1 - (1/2)^n))/(1/2)
and that is always less than 1.

therefore, 2 + something less than 1 is obviously less than 3.

therefore, 1 + 1/1! + 1/2! + 1/3! + ... + 1/n! < 3

*note: post any other alternate solutions, even if it is not correct, but if you think have a good approach, then I will still award bits.

Author:  SilverSprite [ Sun Jun 29, 2003 5:58 pm ]
Post subject: 

okkk that solution is wrong.. i think you remembered something else and tried to copy it but you did it wrong..
Quote:
1/2! + 1/3! + ... + 1/n!

after taking out a factor of 1/2 does not become
Quote:
1/2(1/1! + 1/2! + 1/3! + ... + 1/(n - 1)!)

or am i missing something here?
i am completely lost with your solution.. you dont have any equations just expressions.. dont be too quick to award yourself bits Razz

Author:  AsianSensation [ Sun Jun 29, 2003 6:21 pm ]
Post subject: 

lol, I don't actually award myself bits, but anyways, I see what I did wrong, so I am going to edit that post and put the correct solutions up instead.

btw, is it only us two that's participating in this? come on peoples, put in all your solutions.

anyways, +5 bits to SilverSprite for pointing out my mistake.

Author:  SilverSprite [ Sun Jun 29, 2003 6:33 pm ]
Post subject: 

that is bugz's solution...

Author:  SilverSprite [ Sun Jun 29, 2003 6:33 pm ]
Post subject: 

erase your first solution eh:P save your own skin

Author:  SilverSprite [ Sun Jun 29, 2003 6:36 pm ]
Post subject: 

btw.. your equation 1 is not greater than equation 2 for n=1 lol

Author:  AsianSensation [ Sun Jun 29, 2003 6:38 pm ]
Post subject: 

what is, the one I edited?

well, I didn't ask him or anyone else, I came up with that by myself, there is another solution to that, one kinda similar, it uses the same ideas, so I'm not going to post it up here.

Anyways...

Question #3:

let Sn = 1 + 1/sqrt(2) + 1/sqrt(3) + ... + 1/sqrt(n)

show that 2*sqrt(n + 1) - 2 < Sn < 2*sqrt(n) - 1

for n > 1

Author:  bugzpodder [ Wed Jul 02, 2003 10:18 pm ]
Post subject: 

i solved Q#3 so i get bits Very HappyVery HappyVery Happy

Author:  bugzpodder [ Wed Jul 02, 2003 11:34 pm ]
Post subject: 

here is my question (i am too cheap to offer any bits so dont ask for them)

prove if p+2 and p^2+2 are prime,then p^3+2 is also prime, with p being a prime itself. SilverSprite isnt allowed to answer. he should know why.

Author:  AsianSensation [ Thu Jul 03, 2003 9:04 am ]
Post subject: 

yeah, bugz gets the bits for #3, but you still have to post the solutions up, I want to see a "real" solution, instead of my solution (if you call random pen scratches on scrap paper solutions)

Author:  bugzpodder [ Thu Jul 03, 2003 10:56 am ]
Post subject: 

proof is located here: http://www.sosmath.com/CBB/viewtopic.php?p=3296#3296

Author:  bugzpodder [ Thu Jul 03, 2003 10:59 am ]
Post subject: 

My proof for question #2:
since lim (k-> inf) 1/1!+1/2!+1/3!+...+1/k! = e ~ 2.71828...
therefore 1/1!+1/2!+1/3!+...+1/n! < e < 3
another 30 bits? Very Happy

Author:  AsianSensation [ Thu Jul 03, 2003 1:21 pm ]
Post subject: 

that's cool, yeah, I'll give you another 30 bits, just keep pumping out those good solutions.

and since bugz already gave a question, let that question be question #4 then.

Author:  bugzpodder [ Thu Jul 03, 2003 1:25 pm ]
Post subject: 

i changed my mind if anyone solves 4, i'll give the 30 bits AS gave me to give you (Excluding SS of course)

Author:  AsianSensation [ Mon Jul 07, 2003 1:36 pm ]
Post subject: 

crap, I forgot to give the bits to bugz....oh well, here is the 60 bits that i promised, and your counter starts up new

I haven't been working on that problem, too much critical reading....

anyways, I'll get started soon(but it's not other people are trying for these questions anyways Confused )

+60 bits to Bugz

Author:  AsianSensation [ Fri Jul 18, 2003 4:48 pm ]
Post subject: 

um........how do you tell if a number is prime?

I know one method, and I've been using it, but it's not giving me results....

Im using Wilson's Thereom, which state that the positive integer n is prime if and only if (n-1)! = -1 (mod n)

otherwise, how else could you check to see if it's prime or not? I have to divide all the previous integer before n/2?

Author:  SilverSprite [ Fri Jul 18, 2003 4:58 pm ]
Post subject: 

.........Wilsons theorem?? Thats actually a theorem? isnt that a bit obvious?

Author:  SilverSprite [ Fri Jul 18, 2003 4:58 pm ]
Post subject: 

And there is no easy way...why do you think ppl use encryptions with prime numbers... they arent easy to find.

Author:  AsianSensation [ Fri Jul 18, 2003 6:00 pm ]
Post subject: 

i was surprised too that it was a thereom, but hey, if it says so it's a thereom, then it is.

so i have to prove all cases involving p^3 + 2 divide by all integers before (p^3 + 2)/2? And show that they cannot be a integer?

btw, if p is prime, and p + 2 is prime, what is that called? twin primes?

Author:  bugzpodder [ Sat Jul 19, 2003 10:19 am ]
Post subject: 

Quote:

so i have to prove all cases involving p^3 + 2 divide by all integers before (p^3 + 2)/2? And show that they cannot be a integer?


no actually, if p is 1 or 2 mod 3, then p^2+2 = 1+2 (mod 3) or p^2+2=4+2 (mod 3) which is always divisble by 3 (for all p>1). so p^2+2 is prime iff p=3, and we can easily verify that 3^3+2=29 is prime

Author:  AsianSensation [ Sat Jul 19, 2003 12:23 pm ]
Post subject: 

ah.....nice, so p=3 is the only case?

anyways...since bugz posted up the solutions, and no one got it, then bugz keep his bits.

I'll load up another question in a minute.

I'll load up a geometry one, it will be the first one I do, so bare with the picture if it's not that good.

Author:  AsianSensation [ Sat Jul 19, 2003 12:29 pm ]
Post subject: 

Question #5:

Let P be the center of the square constructed on the hypotenuse AC of the right-angled triangle ABC. Prove that BP bisects angle ABC.


Edit:
And since I'm working on a different computer that doesn't have any image editing things other than paint, I'll give you the code in turing, just run it and it should show you the picture.

code:

var fontID := Font.New ("Ariel:12:Bold")
drawbox (50, 50, 150, 150, 7)
drawline (50, 150, 15, 70, 7)
drawline (50, 50, 15, 70, 7)
drawline (100, 100, 15, 70, 7)
Font.Draw ("A", 45, 160, fontID, 7)
Font.Draw ("B", 10, 50, fontID, 7)
Font.Draw ("C", 45, 35, fontID, 7)
Font.Draw ("P", 100, 80, fontID, 7)

Author:  Catalyst [ Sat Jul 19, 2003 1:17 pm ]
Post subject: 

doesnt sound like C should be where it is

Author:  bugzpodder [ Sat Jul 19, 2003 2:19 pm ]
Post subject: 

obviously ABCP is a cyclic quadrilateral (opposite angles add up to 180) and furthermore since ABP=ACP=45 (common chord in the circle). since ABC is 90 then PBC is also 45 and hence BP is the angle bisector

Author:  SilverSprite [ Sat Jul 19, 2003 6:04 pm ]
Post subject: 

AsianSensation wrote:
Let P be the center of the square constructed on the hypotenuse AC of the right-angled triangle ABC. Prove that BP bisects angle ABC.


Bugz likes to shorten his solutions as much as he can. Anyways this is an add-on to the beginning of bugz's solution since he seems to have flew by it. Or maybe I am wasting my time because this is common knowledge and is unnecessary to state but here it is anyways:

Since P is the centre of the square, PA=PC, and angleAPC=90degrees. Hence P lies on the circle. And this is where bugz comes in.

Author:  AsianSensation [ Sun Jul 20, 2003 11:21 am ]
Post subject: 

Yeah, the labeling was wrong, I fixed that.

anyways, here is my solution, would have posted it up yesterday, if I didn't go to that party.

Anyways, Since ABCP is a cyclic quadrilateral, draw a circle that circumscribe ABCP. Since angle PAC = angle PCA = 45, therefore, arc AP = arc PC, therefore, the angle subtended by AP and PC are equal, therefore, angle ABP = angle PBC = 45, therefore, PB bisect angle ABC.

btw, I added an attachment of the picture, it works for both bugz and mine solution.

Author:  AsianSensation [ Sun Jul 20, 2003 11:23 am ]
Post subject: 

ok, for those solutions, since it wasn't a hard problem, I give bugz 10 bits for solution 1, and SilverSprite 5 bits for clarification, additionally, for solution to problem 4, I give bugz 30 bits, check scoreboard for your total amount.

Author:  bugzpodder [ Sun Jul 20, 2003 12:54 pm ]
Post subject: 

short little problem: Prove gcd(nCi,nCj)>1, given 0<i,j<n

Author:  bugzpodder [ Sun Jul 20, 2003 12:55 pm ]
Post subject: 

nCi is obviously n Choose i

Author:  SilverSprite [ Mon Jul 21, 2003 9:26 am ]
Post subject: 

short my ass.. its a corr. question Razz

Author:  bugzpodder [ Mon Jul 21, 2003 3:48 pm ]
Post 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.

Author:  Crono [ Mon Jul 21, 2003 8:20 pm ]
Post subject: 

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

Author:  AsianSensation [ Mon Jul 21, 2003 8:56 pm ]
Post 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

Author:  bugzpodder [ Mon Jul 21, 2003 10:44 pm ]
Post subject: 

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

Author:  bugzpodder [ Mon Jul 21, 2003 10:45 pm ]
Post subject: 

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

Author:  bugzpodder [ Mon Jul 21, 2003 10:45 pm ]
Post 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!)

Author:  SilverSprite [ Tue Jul 22, 2003 1:41 pm ]
Post subject: 

hahahahahahahahhaaha yeah ok bugz

Author:  SilverSprite [ Wed Jul 23, 2003 3:20 am ]
Post 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.

Author:  SilverSprite [ Wed Jul 23, 2003 3:30 am ]
Post 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.

Author:  bugzpodder [ Wed Jul 23, 2003 12:10 pm ]
Post 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?

Author:  SilverSprite [ Wed Jul 23, 2003 12:47 pm ]
Post 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

Author:  SilverSprite [ Wed Jul 23, 2003 12:55 pm ]
Post subject: 

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

Author:  kmd-10 [ Fri Aug 08, 2003 3:13 pm ]
Post 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

Author:  AsianSensation [ Fri Aug 08, 2003 5:22 pm ]
Post 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.

Author:  bugzpodder [ Fri Aug 08, 2003 9:16 pm ]
Post 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

Author:  kmd-10 [ Fri Aug 08, 2003 10:42 pm ]
Post 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!

Author:  AsianSensation [ Sat Aug 09, 2003 9:16 am ]
Post 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.

Author:  AsianSensation [ Sat Aug 09, 2003 9:18 am ]
Post 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?

Author:  bugzpodder [ Sat Aug 09, 2003 11:49 am ]
Post 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.

Author:  bugzpodder [ Sat Aug 09, 2003 11:51 am ]
Post 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

Author:  AsianSensation [ Sat Aug 09, 2003 1:18 pm ]
Post 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....

Author:  kmd-10 [ Sat Aug 09, 2003 1:34 pm ]
Post 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.

Author:  kmd-10 [ Sat Aug 09, 2003 1:36 pm ]
Post 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.

Author:  kmd-10 [ Sat Aug 09, 2003 2:48 pm ]
Post 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.

Author:  bugzpodder [ Sat Aug 09, 2003 8:02 pm ]
Post 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?


: