Author |
Topic: Sum of sum and product (Read 811 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Sum of sum and product
« on: Jul 19th, 2004, 3:09pm » |
 Quote  Modify
|
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)
|
|
 IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Sum of sum and product
« Reply #1 on: Jul 20th, 2004, 6:52am » |
Quote Modify
|
Well, the minimum possible value of X is 2004...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Sum of sum and product
« Reply #2 on: Jul 20th, 2004, 10:02am » |
Quote Modify
|
::
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.
::
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Sum of sum and product
« Reply #3 on: Jul 20th, 2004, 10:32am » |
Quote Modify
|
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 nth root of unity?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Sum of sum and product
« Reply #4 on: Jul 20th, 2004, 10:55am » |
Quote Modify
|
for the generalization
::
(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
::
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Sum of sum and product
« Reply #5 on: Jul 20th, 2004, 11:18am » |
Quote Modify
|
It's easy to prove that in general,
x1 [oplus] x2 [oplus] . . . [oplus] xn = [prod]i=1n (1+xi) - 1.
For the case xk = [omega]k = e2[pi]ik/n, we know
xn - 1 = [prod](x - [omega]k),
so taking x=-1 gives the answer as (-1)n+1.
|
| « Last Edit: Jul 20th, 2004, 11:19am by Eigenray » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Sum of sum and product
« Reply #6 on: Jul 20th, 2004, 12:10pm » |
Quote Modify
|
on Jul 20th, 2004, 11:18am, Eigenray 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.
|
| « Last Edit: Jul 20th, 2004, 12:11pm by Aryabhatta » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Sum of sum and product
« Reply #7 on: Jul 20th, 2004, 12:24pm » |
Quote Modify
|
When [omega] = 1, n = 1 so we only have [omega]0 = 1 = (-1)2 So how is that not right?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Sum of sum and product
« Reply #8 on: Jul 20th, 2004, 12:30pm » |
Quote Modify
|
on Jul 20th, 2004, 12:24pm, towr wrote:When [omega] = 1, n = 1 so we only have [omega]0 = 1 = (-1)2 So how is that not right?
|
|
What i was saying is that, for n=1000, [omega] can be 1 as 1 is an nth root of unity.. i.e the numbers is just 1,1,1,..... I probably should have said that [omega] is one of the nth roots of unity.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Sum of sum and product
« Reply #9 on: Jul 20th, 2004, 3:25pm » |
Quote Modify
|
on Jul 20th, 2004, 12:10pm, 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]=e2[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 2d-1 when m is odd, and -1 when m is even, or [1-(-1)m]d-1.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Sum of sum and product
« Reply #10 on: Jul 20th, 2004, 4:03pm » |
Quote Modify
|
on Jul 20th, 2004, 3:25pm, Eigenray wrote:
(I usually take i=[sqrt]-1, but that's just me )
|
|
Quote:
In general then, if [omega]=e2[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 2d-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...
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print