Proving that order doesn't matter for elements in this sequence

R

rasen58

New member
Joined
Mar 4, 2021
Messages
5
I was doing a problem with the relevant problem statement being:
"
Consider a list of integers L. Initially, L contains the integers 1 through N, each of them exactly once (but it may contain multiple copies of some integers later). The order of elements in L is not important. You should perform the following operation N−1 times:
  • Choose two elements of the list, let's denote them by X and Y.
  • Erase the chosen elements from L.
  • Append the number X+Y+X⋅Y to L.
At the end, L contains exactly one integer. Find the maximum possible value of this integer.
"
I was able to write down some examples for N = 2 and 3 and saw that the order in which I chose the two elements didn't matter, and thus I can just iterate through the list and perform the operation (X + Y + XY) sequentially till I get the final total.

BUT, the part I don't understand is how would I have actually proven that the order doesn't matter here? I want to be able to do these kinds of problems without needing to write down examples first but where I can really see why something is the case.
 
This doesn't seem easy to prove at all (for me at least). I've tried to illustrate the problem with 4 starting variables instead of numbers. A single list element is shown between vertical lines. If there's more than one expression between the vertical lines then they are summed. A pattern is formed and it's obvious that the initial order doesn't matter, and that this would hold for any length of initial list. I wouldn't consider this a proper proof on its own, but it's a possible starting point for a general proof...

Rich (BB code): 
OPERATE ON THE FIRST TWO                     SUM          +        PRODUCT

|   |   |   |   |                       |       |         +        | a*b |
| a | b | c | d |                       | a   b |                  |     |


|       |   |   |                       |           |          |   a*b*c   | 
|  a*b  |   |   |                       |  a*b      |     +    | a*c   b*c |
| a   b | c | d |                       | a   b   c |          |           |


|                 |   |         |                     |       |        a*b*c*d        |
|      a*b*c      |   |         |      a*b*c          |   +   | a*b*d   a*c*d   b*c*d |
| a*b   a*c   b*c |   |         | a*b   a*c   b*c     |       |    a*d   b*d   c*d    |
|    a   b   c    | d |         |    a   b   c      d |       |                       |


|              a*b*c*d              |
|   a*b*c   a*b*d   a*c*d   b*c*d   |     ...all combinations of 3
| a*b   a*c   b*c   a*d   b*d   c*d |     ...all combinations of 2
|           a   b   c   d           |
 
rasen58 said:
I was doing a problem with the relevant problem statement being:
"
Consider a list of integers L. Initially, L contains the integers 1 through N, each of them exactly once (but it may contain multiple copies of some integers later). The order of elements in L is not important. You should perform the following operation N−1 times:
  • Choose two elements of the list, let's denote them by X and Y.
  • Erase the chosen elements from L.
  • Append the number X+Y+X⋅Y to L.
At the end, L contains exactly one integer. Find the maximum possible value of this integer.
"
I was able to write down some examples for N = 2 and 3 and saw that the order in which I chose the two elements didn't matter, and thus I can just iterate through the list and perform the operation (X + Y + XY) sequentially till I get the final total.

BUT, the part I don't understand is how would I have actually proven that the order doesn't matter here? I want to be able to do these kinds of problems without needing to write down examples first but where I can really see why something is the case.
Click to expand...
In effect, you just have to prove that the operation x*y=x+y+xy is commutative and associative. The former is obvious. The latter means:

(a*b)*c = a*(b*c)​

But

(a*b)*c = (a+b+ab)*c = (a+b+ab)+c+(a+b+ab)c = a+b+ab+c+ac+bc+abc = a+b+c+ab+bc+ca+abc​
a*(b*c) = a*(b+c+bc) = a+(b+c+bc)+a(b+c+bc) = a+b+c+bc+ab+ac+abc = a+b+c+ab+bc+ca+abc​

These are, of course, equal.

So given any list of numbers, a*b*c*...*z is unchanged if we rearrange the numbers at will.
 
Dr.Peterson said:
In effect, you just have to prove that the operation x*y=x+y+xy is commutative and associative. The former is obvious. The latter means:

(a*b)*c = a*(b*c)​

But

(a*b)*c = (a+b+ab)*c = (a+b+ab)+c+(a+b+ab)c = a+b+ab+c+ac+bc+abc = a+b+c+ab+bc+ca+abc​
a*(b*c) = a*(b+c+bc) = a+(b+c+bc)+a(b+c+bc) = a+b+c+bc+ab+ac+abc = a+b+c+ab+bc+ca+abc​

These are, of course, equal.

So given any list of numbers, a*b*c*...*z is unchanged if we rearrange the numbers at will.
Click to expand...

Brilliant! I'm kicking myself for missing that!
 
Dr.Peterson said:
In effect, you just have to prove that the operation x*y=x+y+xy is commutative and associative. The former is obvious. The latter means:

(a*b)*c = a*(b*c)​

But

(a*b)*c = (a+b+ab)*c = (a+b+ab)+c+(a+b+ab)c = a+b+ab+c+ac+bc+abc = a+b+c+ab+bc+ca+abc​
a*(b*c) = a*(b+c+bc) = a+(b+c+bc)+a(b+c+bc) = a+b+c+bc+ab+ac+abc = a+b+c+ab+bc+ca+abc​

These are, of course, equal.

So given any list of numbers, a*b*c*...*z is unchanged if we rearrange the numbers at will.
Click to expand...
Perfect thank you!

Also just wondering but is there a way in which you would have intuitively known yourself upon reading the original problem that the order in which we choose two elements didn't matter?
I only realized this by doing a few small examples with n=3 and 4 on paper and finding that the order didn't matter.
But do you have an alternate way or a different kind of intuition with which you could've saved time in knowing that the order didn't matter?
 
rasen58 said:
Perfect thank you!

Also just wondering but is there a way in which you would have intuitively known yourself upon reading the original problem that the order in which we choose two elements didn't matter?
I only realized this by doing a few small examples with n=3 and 4 on paper and finding that the order didn't matter.
But do you have an alternate way or a different kind of intuition with which you could've saved time in knowing that the order didn't matter?
Click to expand...
I think I would immediately see that the operation is commutative, and its symmetry would strongly suggest associativity.

If I didn't see that immediately, I would probably do as you did, trying some small numbers to get a feel for how it worked, and make that discovery. Then I would continue, looking for a pattern in the answers to see if I could develop a formula, either by guessing and then proving, or by extending what I did for associativity.

Or, skipping all that, I might do as I did just now in my head, seeing the final answer almost directly by rewriting the formula for the operation in a way that extends very easily. I hadn't bothered to solve the entire problem until now.

This approach also bypasses the need to separately prove that order doesn't matter; that is built into the formula for the final answer.

You haven't said what sort of final answer you found. Is it the simple formula I just discovered?
 
Dr.Peterson said:
Is it the simple formula I just discovered?
Click to expand...

Which simple formula? I don't see any formula you mentioned.

Dr.Peterson said:
You haven't said what sort of final answer you found.
Click to expand...

The final answer in this case was just a computer program that would output the calculated result for a give input N. So to do that, I just iterate sequentially through the list [1, N] and performed the operation X+Y+X⋅Y as I went through.
 
rasen58 said:
The final answer in this case was just a computer program that would output the calculated result for a give input N. So to do that, I just iterate sequentially through the list [1, N] and performed the operation X+Y+X⋅Y as I went through.
Click to expand...

Then try noting down the output for N=2,3,4,5 and see if you notice something! I noticed a similarity to a function that's probably on your calculator. Using this I came up with a simple expression for the answer (this is doing what @Dr.Peterson first suggests in post #6). But I'm looking forward to (hopefully) seeing more hints about the following method too...

Dr.Peterson said:
Or, skipping all that, I might do as I did just now in my head, seeing the final answer almost directly by rewriting the formula for the operation in a way that extends very easily. I hadn't bothered to solve the entire problem until now.
Click to expand...
 
Cubist said:
But I'm looking forward to (hopefully) seeing more hints about the following method too...
Click to expand...
I noticed how similar x+y+xy is to (x+1)(y+1) = xy+x+y+1.

How about writing the operation x*y = x+y+xy as x*y = (x+1)(y+1)-1? Then what is (x*y)*z? What happens as you include more numbers?
 
Dr.Peterson said:
How about writing the operation x*y = x+y+xy as x*y = (x+1)(y+1)-1? Then what is (x*y)*z? What happens as you include more numbers?
Click to expand...
The formula seems to be that it is always in the form x*y*...*z = (x+1)(y+1)....(z+1) - 1
so I guess that means it's equal to (n+1)! - 1?
 
You must log in or register to reply here.
Top