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.

 

Related material
Read more...

Telescoping situations

  • Leibniz and Pascal Triangles
  • Infinite Sums and Products
  • Sum of an infinite series
  • Harmonic Series And Its Parts
  • A Telescoping Series
  • An Inequality With an Infinite Series
  • That Divergent Harmonic Series
  • An Elementary Proof for Euler's Series
  • $\sin 1^{\circ}+\sin {2^\circ}+\sin 3^{\circ}+\cdots+\sin 180^{\circ}=\tan 89.5^{\circ}$
  • Problem 3824 from Crux Mathematicorum
  • $x_n=\sin 1+\sin 3+\sin 5+\cdots+\sin (2n-1)$
  • |Contact| |Up| |Front page| |Contents| |Arithmetic|

    Copyright © 1996-2018 Alexander Bogomolny

     63699349

    Search by google: