Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**careless25****Real Member**- Registered: 2008-07-24
- Posts: 560

Here is the question: http://pastebin.com/8yrJxMKE

I am sure this has to be proved by induction.

I am guessing my basis step would be, for n rocks where n = 2, then k*m = 1 = (n(n-1))/2 = 1.

induction hypothesis: basis step holds true for n >= 2

Now I am stuck, because k*m could break apart easily into many different possibilities and if i try to keep it such that k decreases and m is always 1, this doesnt take into account all the possibilities.

Can someone give me a little push in the right direction?

Thanks!

*Last edited by careless25 (2012-05-21 14:21:31)*

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 16,048

Hi careless25

Well if the su mof the first n numbers is.n(n+1)/2 then the sum of the.first n+1 elements is n(n+1)/2 + n+1 =(n^2+n+2n-2)/2=(n^2+3n+2)/2=(n+1)(n+2)/2

Qed

Oh and your formula is.not correct. It is n(n+1)/2 like I wrote up there.

Stefy

*Last edited by anonimnystefy (2012-05-22 04:08:56)*

Here lies the reader who will never open this book. He is forever dead.

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

The knowledge of some things as a function of age is a delta function.

Offline

**careless25****Real Member**- Registered: 2008-07-24
- Posts: 560

Thanks a lot, though the formula is n(n-1)/2 but i can account for that in my proof.

I need help with one more proof.

Prove that GCD(ab,c) = GCD(a,c) * GCD(b,c)

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 16,048

Am I imagining,or did you change your original question?

Here lies the reader who will never open this book. He is forever dead.

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

The knowledge of some things as a function of age is a delta function.

Offline

**careless25****Real Member**- Registered: 2008-07-24
- Posts: 560

No I need help with another question and its easier to continue in this thread than create another.

Prove GCD(ab,c) = GCD(a,c) * GCD(b,c)

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 16,048

Do you know the Fundamental Theorem of Arithmetics? It can be used here.

Here lies the reader who will never open this book. He is forever dead.

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

The knowledge of some things as a function of age is a delta function.

Offline

**careless25****Real Member**- Registered: 2008-07-24
- Posts: 560

I just looked it up, I am not sure how to apply it though.

i am guessing we show, a,b,c have some prime factors since all of them have the same prime factor, the statement should be true.

EDIT:

This is what i have so far:

Let a = p1 * p2 where pN is an integer and a prime.

Let b = p3 * p4 " " " """

Let c = p5* p6 " " " " "

Now i am not sure how to show that a,b,c have the same unique prime factor.

*Last edited by careless25 (2012-05-22 05:35:39)*

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 16,048

No,Wait a sec,it isn't true for a=2,b=1024,c=4!!!

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

The knowledge of some things as a function of age is a delta function.

Offline

**careless25****Real Member**- Registered: 2008-07-24
- Posts: 560

Yes it does

GCD(8,1024) = 8

GCD(2,1024) = 2

GCd(4,1024) = 4

hence 8 = 4*2

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 16,048

No,you didn't substitute correctly.

GCD(1024,4)=4

GCD(512,4)=4

GCD(2,4)=2

2*4<>4

Sorry,I took b=512. You can see that we have a counterexample so the claim is false.

*Last edited by anonimnystefy (2012-05-22 05:56:06)*

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

The knowledge of some things as a function of age is a delta function.

Offline

**careless25****Real Member**- Registered: 2008-07-24
- Posts: 560

Wow that was that easy! thanks!

C25

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 16,048

Where did you get that question?

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

The knowledge of some things as a function of age is a delta function.

Offline

**careless25****Real Member**- Registered: 2008-07-24
- Posts: 560

It was a homework question on one of my assignments.

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 16,048

What was the wording of the question?

Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

The knowledge of some things as a function of age is a delta function.

Offline

**careless25****Real Member**- Registered: 2008-07-24
- Posts: 560

it said for all a,b,c in intergers prove the following:

GCD(ab,c) = GCD(a,c) * GCD(b,c)

so a counterexample proves it false since it is for all a,b,c.

Offline

Pages: **1**