1
$\begingroup$

Suppose you have a list of integers from 1 to N

And say you remove any two numbers, X and Y, from the list of numbers, and add (X + Y + X.Y) to the list

If you keep doing this until you have only one number remaining (which means I performed the above operation N-1 times), the answer turns out to be (N+1)! - 1

For example, let N = 4 Which means my list is: {1, 2, 3, 4}

If I choose X = 1 and Y = 2, then (1 + 2 + 1.2) is 5, so my list now becomes {5, 3, 4}

Now let X = 5 and Y = 4, then (5 + 4 + 5.4) is 29, so my list now becomes {29, 3}

And when X = 29 and Y = 3, we get (29 + 3 + 29.3) which is {119}

And 119 turns out to be 5! - 1 So for N = 4, my answer is 5!-1

Similarly for any N, my result ends up being (N+1)! - 1

Can someone provide some proof or explanation for this?

For reference, my question is based on this problem- https://www.codechef.com/MAY19B/problems/REDONE

$\endgroup$
2
3
$\begingroup$

Suppose your list is $L$. Then consider $I=\prod\limits_{i\in L}(i+1)$. $I$ is invariant, since when you do one of your operations, $x,y\to x+y+xy$, $(x+1)(y+1)=x+y+xy+1$ so $L$ remains constant. Thus $L_{\text{start}}=L_{\text{end}}$, so since $L_{\text{start}}=(n+1)!$, we must have $L_{\text{end}}=(n+1)!$ But there's just one number left so this number must be $(n+1)!-1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.