General Question

LostInParadise's avatar

Brain Teaser - How does this work?

Asked by LostInParadise (27708points) March 27th, 2009

This may be a bad time of year for this, but I am hoping there is enough tease in this to catch someone’s attention.

Given a list of numbers, for example, 3, 4, 6, 8 and 9, remove two of the numbers a and b from the list and replace them with a*b + a + b. Keep doing this until one number remains. No matter what order you do this in the answer will be the same, in this case 12,599.

Hint: a*b + a + b can almost be factored.

I will provide the short answer and also use this problem as an introduction to the concept of isomorphism, which tells when two operations are structually identical.

Observing members: 0 Composing members: 0

3 Answers

BonusQuestion's avatar

Starting with n numbers a(1), a(2), ..., a(n) we will always end up with (a(1)+1) ( a(2)+1)...(a(n)+1) -1.

The reason is that ab+a+b = (a+1)(b+1) – 1

One way to prove the above statement is by induction on n: Lets say in the step right before the last step we are left with two numbers a and b. We know a and b are results of this operation on k and n-k numbers for some k < n. So by induction hypothesis a = (a(1)+1)...(a(k)+1) -1 and b =(a(k+1)+1)...(a(n)+1) -1

Calculating (a+1)(b+1)-1 proves the statement for n, which shows the statement is true by induction on n.

BonusQuestion's avatar

Another way of proving that statement is to show in each step the product of (a(i)+1) does not change. Meaning that if we do the operation on a(1),...,a(n) and we get b(1),...,b(n-1) then

(a(1)+1) .... (a(n)+1) = (b(1)+1) .... (b(n-1)+1)

Again the reason is that we replace a , b by (a+1)(b+1)-1.

Therefore if we finally get to a single number x , then we should have: x+1 is the same as the product of (a(i)+1) which means x = ( product of (a(i)+1) ) -1

LostInParadise's avatar

@BonusQuestion , you got it right. I would like to show another way of looking at it that is not quite so easy to explain as I had hoped, but I can give a rough idea of how it works.

Suppose we define an operation & as
a & b = a * b + a + b. Then what we want to show is that the order in which & is applied does not matter and to do that it is sufficient to show & is commutative and associative.

We have a & b + 1 = (a+1)*(b+1). If we let T(x) = x + 1 then we get T(a & b) = T(a)*T(b). This is an isomorphic relationship, meaning that the internal structure of & is the same as *. You can think of T as a kind of reflection. On one side you get a & b = c and on the other you get T(a) * T(b) = T©. What happens on one side matches up to what happens on the other if you replace x with T(x) and & with *. For example T(a & b) = T(a) * T(b) and T(b & a) = T(b) * T(a), so & is commutative because * is. Similarly for associativity.

Answer this question

Login

or

Join

to answer.

This question is in the General Section. Responses must be helpful and on-topic.

Your answer will be saved while you login or join.

Have a question? Ask Fluther!

What do you know more about?
or
Knowledge Networking @ Fluther