Author |
Topic: Transformations (Read 386 times) |
|
Mond
Guest
|
Consider the set {1,1/2,1/3,1/4...1/M}
Now take any two elements of the set, and replace them by the sum of their sum and product
For example, take 1/2 and 1/3. Replace them with
1/2+1/3+1/(2*3) =1
So the set now has M-1 elements {1,1,1/4,1/5...1/M}
If M-1 such transformations are applied , what is the last remaining element ?
|
|
 IP Logged |
|
|
|
Papa Homer
Guest
|
The remaining element is M.
The solution:
First, show that the order of transformations does not matter. Consider any three elements a, b, and c.
T(T(a,b),c) = T(a+b+ab,c) = a + b + c + ab + ac + bc + abc
T(a,T(b,c) = T(a,b+c+bc) = a + b + c + ab + ac + bc + abc
T(b,T(a,c) = T(b,a+c+ac) = a + b + c + ab + ac + bc + abc
Now that we have shown that the order of transformations does not matter we can prove the result by induction. For the base case let M = 2 (we could have started with 1 as well). The set is {1,1/2}. There is only one trasformation to do and the result is T(1,1/2) = 1 + 1/2 + 1/2 = 2. Now for the inductive step assume that the hypothesis holds for M and add an extra element 1/M+1. Becuase the order of the transformations does not matter, we will transform all but the last element of the set first. By the inductive hypothesis, we will end up with a set {M, 1/M+1}. Doing the final transformation results in T(M, 1/M+1) = M + 1/(M+1) + M/(M+1) = M + 1.
|
|
IP Logged |
|
|
|
Mond
Guest
|
Neat solution ... Can you think of a way of proving this without using induction ? Or to generalize, how would this work if the set you started off with was
{a[/sub]1, a[sub]2, .... a[sub][/sub]n}
ie. What would the value of the last element be, after n-1 transformations ?
|
|
IP Logged |
|
|
|
Mond
Guest
|
Sorry about that.. .the set should be :
{a[/sub]1[sub], a[/sub]2[sub], .... a[/sub]n[sub]}
|
|
IP Logged |
|
|
|
Papa Homer
Guest
|
How about:
The result is going to be a polynomial where each monomial has a coefficient 1 and at most n variables. We will designate each monomial with an n-bit number such that every bit designates a variable (a1 through an). If the bit is set the variable is present. For example, if n=4, then monomial a1a3a4 would be represented as 1011. The polynomial we are after is the sum of monomials represented by all possible non-zero n-bit numbers. Once again, for n=4, a1 + a2 + a3 + a4 + a1a2 + a1a3 + a1a4 + a2a3 + a2a4 + a3a4 + a1a2a3 + a1a2a4 + a1a3a4 + a2a3a4 + a1a2a3a4 ( 1000 + 0100 + 0010 + 0001 + 1100 + 1010 + 1001 + 0110 + 0101 + 0011 + 1101 + 1110 + 1011 + 0111 + 1111)
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 1948
|
 |
Re: Transformations
« Reply #5 on: Apr 26th, 2003, 12:19pm » |
 Quote  Modify
|
The general answer can be more simply stated as:
[Prodni=1 (1+ai)] -1
In the original problem, this is just the telescoping product:
[Prodni=1 (i+1)/i] - 1 = (M+1)/1 - 1 = M
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove