wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Sum of sum and product
        
(Message started by: Aryabhatta on Jul 19^th, 2004, 3:09pm)

Title: Sum of sum and product
Post by Aryabhatta on Jul 19^th, 2004, 3:09pm

You have the numbers 1, 1/2,1/3,....1/2004 written on a blackboard. You pick two numbers, say a and b at random and replace them with a+b+ab. You continue this till there is only one number, say X, remaining. What is the maximum possible value of X?

(Source: Mindsport, a weekly puzzle column from the newspaper Times of India)

Title: Re: Sum of sum and product
Post by Eigenray on Jul 20^th, 2004, 6:52am

Well, the minimum possible value of X is [hide]2004[/hide]...

Title: Re: Sum of sum and product
Post by towr on Jul 20^th, 2004, 10:02am

::[hide]
If we define an operator [oplus] as a[oplus]b = a+b+ab
then (a[oplus]b)[oplus]c = a[oplus](b[oplus]c)
So [oplus] is an associative operator which means the order of calculation doesn't matter.
[/hide]::

Title: Re: Sum of sum and product
Post by Aryabhatta on Jul 20^th, 2004, 10:32am

Right Eigenray and towr.

Eigenray, how did you arrive at that?

Generalization:
What if 2004 is replaced by n ?
i.e the numbers initially are 1,1/2,1/3,...1/n ?

Similar question:
What if the numbers were
1, [omega], [omega][sup2],...,[omega]^n-1
where [omega] is the n^th root of unity?

Title: Re: Sum of sum and product
Post by towr on Jul 20^th, 2004, 10:55am

for the generalization
::[hide]
(x-1) [oplus] 1/x = x
So inductively we very easily arive at
1 [oplus] 1/2 [oplus] ... [oplus] 1/(n-1) [oplus] 1/n = n
[/hide]::

Title: Re: Sum of sum and product
Post by Eigenray on Jul 20^th, 2004, 11:18am

It's easy to prove that in general,
x₁ [oplus] x₂ [oplus] . . . [oplus] x_n = [hide][prod]_i=1ⁿ (1+x_i) - 1[/hide].
For the case x_k = [omega]^k = e^2[pi]ik/n, [hide]we know
xⁿ - 1 = [prod](x - [omega]^k),
so taking x=-1 gives the answer as (-1)ⁿ⁺¹[/hide].

Title: Re: Sum of sum and product
Post by Aryabhatta on Jul 20^th, 2004, 12:10pm

on 07/20/04 at 11:18:35, Eigenray wrote:

answer as [hide] (-1)ⁿ⁺¹[/hide].

The identity you give is correct, but your final answer is not true when [omega] = 1. For another counter-example, take n=6 and i=2. But i guess that can be easily corrected.

Title: Re: Sum of sum and product
Post by towr on Jul 20^th, 2004, 12:24pm

When [omega] = 1, n = 1 so we only have [omega]⁰ = 1 = (-1)² So how is that not right?

Title: Re: Sum of sum and product
Post by Aryabhatta on Jul 20^th, 2004, 12:30pm

on 07/20/04 at 12:24:38, towr wrote:

When [omega] = 1, n = 1 so we only have [omega]⁰ = 1 = (-1)² So how is that not right?

What i was saying is that, for n=1000, [omega] can be 1 as 1 is an n^th root of unity.. i.e the numbers is just 1,1,1,..... I probably should have said that [omega] is one of the n^th roots of unity.

Title: Re: Sum of sum and product
Post by Eigenray on Jul 20^th, 2004, 3:25pm

on 07/20/04 at 12:10:57, Aryabhatta wrote:

The identity you give is correct, but your final answer is not true when [omega] = 1. For another counter-example, take n=6 and i=2. But i guess that can be easily corrected.

(I usually take i=[sqrt]-1, but that's just me :))
In general then, if [omega]=e^2[pi]ir/n, let d=gcd(r,n), m=n/d, so that [omega] is a primitive m-th root of unity.
Then the answer is 2^d-1 when m is odd, and -1 when m is even, or [1-(-1)^m]^d-1.

Title: Re: Sum of sum and product
Post by Aryabhatta on Jul 20^th, 2004, 4:03pm

on 07/20/04 at 15:25:08, Eigenray wrote:

(I usually take i=[sqrt]-1, but that's just me :))

;D

Quote:

In general then, if [omega]=e^2[pi]ir/n, let d=gcd(r,n), m=n/d, so that [omega] is a primitive m-th root of unity.
Then the answer is 2^d-1 when m is odd, and -1 when m is even, or [1-(-1)^m]^d-1.

Right. The value depends on the [omega] you choose, but there is one formula (the one you gave) which works for all...