A Welcome Problem for the Year 2018

Problem

A Welcome Problem for the Year 2018

Solution 1

Assume at some point there are numbers $a_1,a_2,\ldots,a_n.$ Consider the expression $\displaystyle P=\prod_{k=1}^{n}(a_k+1)-1.$

WLOG, Alice picked numbers $a_1$ and $a_2$ and replaced them with $a_1a_2+a_1+a_2.$ This operation left $P$ invariant - unchanged - because $(a_1a_2+a_1+a_2)+1=(a_1+1)(a_2+1).$

It follows that at the end if the day, Alice will be left with the number

$\displaystyle\prod_{k=1}^{2018}\left(\frac{1}{k}+1\right)-1=\prod_{k=1}^{2018}\frac{k+1}{k}-1=2019-1=2018,$

as the product telescopes into a simple expression.

Solution 2

Let $I=\{1,2,...,n\}$ be indexing set for the initial numbers. Let the set of initial numbers be $\{x_i|i\in I\}$. We claim that any number on the board is of the form

$\displaystyle\left[\prod_{i|i\in~\text{Some subset of I}}(1+x_i)\right]-1.$

The initial "primitive" numbers can be written as $(1+x_i)-1$ and when two primitive numbers $x_i$ and $x_j$ are combined, we replace $(1+x_i)-1$ and $(1+x_j)-1$ with $x_i+x_j+x_ix_j=(1+x_i)(1+x_j)-1$.

Now, consider two disjoint subsets of $I$ - $P$ and $Q$. The combination of

$\displaystyle\left[\prod_{i|i\in P}(1+x_i)\right]-1$

and

$\displaystyle\left[\prod_{i|i\in Q}(1+x_i)\right]-1$

replaces these two numbers with

$\displaystyle\left[\prod_{i|i\in P\cup Q}(1+x_i)\right]-1.$

Thus, in essence, the effect of replacing two numbers on the board by a new number is equivalent to taking the union of disjoint subsets of the indexing set. The primitive numbers are just those subsets that have single elements.

When the procedure is successively repeated, we keep taking the unions until we are left with the entire set $I$. Thus, the final number is

$\displaystyle\begin{align}\left[\prod_{i|i\in I}(1+x_i)\right]-1 &=\left[\prod_{i=1}^n\left(1+\frac{1}{i}\right)\right]-1 \\ &=\frac{2}{1}\cdot \frac{3}{2}\cdot \frac{4}{3}\cdot \ldots \cdot \frac{n+1}{n}-1=n. \end{align}$

In our case, $n=2018.$

Solution 3

I guess one way to see this is to note that the binary operation

$x*y :=\,x+y+xy$

is both assosciative and commutative. So if

$x_1*x_2*x_3*\ldots *x_{2018} = 2018$

then changing the order of the elements and/or the order of operations would have no effect on the final result.

Acknowledgment

The problem with $2012$ instead of $2018$ was offered at the 2012 Pan African Mathematics Olympiad. It was published at the Crux Methematicorum as problem CC154 (2016). In a more general setting the problem was discussed in a 1997 page where it was also illustrated by a now defunct Java applet.

Solution 2 is by Amit Itagi; Solution 3 is by Emad Thomaie.

 

[an error occurred while processing this directive]

|Contact| |Up| |Front page| |Contents| |Arithmetic|

Copyright © 1996-2018 Alexander Bogomolny
[an error occurred while processing this directive]
[an error occurred while processing this directive]