# Problem Of The Week #452 January 25th 2021

Status
Not open for further replies.

#### anemone

##### MHB POTW Director
Staff member
Here is this week's POTW:

-----

Determine all positive integers $a,\,b$ and $c$ that satisfy the following equation:

$(a+b)!=4(b+c)!+18(a+c)!$

-----

• Greg, lfdahl and topsquark

#### anemone

##### MHB POTW Director
Staff member
Hello all again!

I was told that the current POTW is a duplicate problem/challenge that have been posted in MHB before. For that, I am truly sorry. I have been posted many problems recently at MHB in the form of POTW or challenge that I will, sometimes, repost a same problem twice. I am writing to seek for your understanding and please know that I do not intentionally make the duplicate post.

Having said all those, please disregard the above post and I will now present to you this week's POTW:

Find the maximum value of the expression $|\cdots||x_1-x_2|-x_3|-\cdots -x_{1990}|$, where $x_1,\,x_2,\,\cdots,\,x_{1990}$ are distinct natural numbers between 1 and 1990.

#### anemone

##### MHB POTW Director
Staff member
No one replied to last week's POTW. However, I have decided to give the community another week's time to attempt at last week's POTW. And I am looking forward to receiving submissions from the members!

• topsquark

#### anemone

##### MHB POTW Director
Staff member
Congratulations to Opalg for his correct solution, which you can find below:

For a given permutation $(x_1,x_2,\ldots,x_n)$ of $(1,2,\ldots,n)$, let $S = \Bigl|\bigl|\ldots \bigl||x_1-x_2|-x_3\bigr|-\ldots - x_{n-1}\bigr| -x_n\Bigr|$.

For $2\leqslant r\leqslant n$, let $S(r) = \Bigl|\bigl|\ldots\bigl||x_1-x_2|-x_3\bigr|-\ldots - x_{r-1}\bigr| -x_r\Bigr|$. Then $S(r) = |S(r-1) - x_r|$, and $S = S(n)$.

An easy proof by induction shows that, for each $r$, $S(r)$ is an integer between $0$ and $n$. In particular, $S$ cannot be greater than $n$.

If $x_r$ is even then $S(r)$ has the same parity as $S(r-1)$, and if $x_r$ is odd then $S(r)$ has the opposite parity to $S(r-1)$. If $n$ is of the form $4k$ or $4k+3$ then the set $\{1,2,3,\ldots,n\}$ contains an even number of odd integers, so $S$ will be even. But if $n$ is of the form $4k+1$ or $4k+2$ then the set $\{1,2,3,\ldots,n\}$ contains an odd number of odd integers, so $S$ will be even. In particular, $1990$ is of the form $4k+2$. It follows that in that case $S$ cannot be greater than $1989$.

With $S$ as above, consider the permutation $\{x_1,x_2,\ldots, x_n,n+2,n+1\}$ of the numbers $(1,2,\ldots,n+2)$, and let $S^{++}$ be the corresponding sum $S^{++} = \Bigl|\bigl|\ldots\bigl||x_1-x_2|-x_3\bigl|-\ldots - (n+2)\bigl| -(n+1)\Bigl|$. Then $$S^{++} = \bigl||S - (n+2)| - (n+1)\bigr| = |n+2-S - (n+1)| = |S - 1|.$$ In particular, if $S=0$ then $S^{++} = 1$; and if $S=1$ then $S^{++} = 0$. Another easy induction proof then shows that if $n$ is of the form $4k+1$ or $4k+2$ then (by choosing the permutation $(x_1,x_2,\ldots,x_n)$ appropriately) it is possible to get $S=1$. (And if $n$ is of the form $4k$ or $4k+3$ then it is possible to get $S=0$.)

In particular, there is a permutation $(x_1,x_2,\ldots,x_{1989})$ of the numbers $(1,2,\ldots,1989)$ giving $S=1$. The permutation $(x_1,x_2,\ldots,x_{1989},1990)$ of the numbers $(1,2,\ldots,1990)$ then has a corresponding sum $S^+$ satisfying $S^+ = |S - 1990| = |1-1990| = 1989$. Therefore the maximum value of the expression $\Bigl|\bigl|\ldots\bigl||x_1-x_2|-x_3\bigr|-\ldots - x_{1989}\bigr| -x_{1990}\Bigr|$, where $x_1,x_2,\ldots,x_{1990}$ are distinct natural numbers between $1$ and $1990$, is $1989$.

• lfdahl and topsquark
Status
Not open for further replies.