New Le Monde puzzle

March 3, 2010

By xi'an

(This article was first published on Xi'an's Og » R, and kindly contributed to R-bloggers)

When I first read Le Monde puzzle this weekend, I though it was even less exciting than the previous one: find

$Y>2010$ and $N<(Y-N)$ ,

such that

$N(Y-N)$ is a multiple of $Y$ .

The solution is obtained by brute-force checking through an R program:

$Y=2012, N=1006$

and then the a next solution is $Y=2016, N=504$ (with several values for N).

However, while waiting in the plane to Edinburgh, I thought more about it and found that the problem can be solved with paper and pencil. It goes like this. There exists an integer

$c$ such that $N(Y-N)=cY.$

Hence, solving the second degree equation,

$N = left(Ypmsqrt{Y^2-4cY}right)/2 = Y left(1pmsqrt{1-4c/Y}right)/2$

which implies that

$2 / left(1pmsqrt{1-4c/Y}right)$

is one of the integral factors of $Y$ . If we write

$Y=qk$ with $1pmsqrt{1-4c/Y}= dfrac{2}{k},$

we get

$dfrac{4c}{Y} = dfrac{4c}{qk} = 1 - left( 1 - dfrac{2}{k}right)^2 = frac{4}{k}left(1-dfrac{1}{k}right)$

and thus

$c=q-dfrac{q}{k} = q,dfrac{k-1}{k}$ .

We thus deduce that $q/k$ is an integer, meaning that $q=pk$ and thus that $k^2$ is an integer factor of $Y$ . This obviously restricts the choice of $Y$ , especially when considering that $4cle Y$ implies $kge 4$ . Furthermore, the solutions to the second degree equations are then given by

$dfrac{Y}{2} left( 1 pm dfrac{k-2}{k}right) = left{ begin{matrix} pk\ pk(k-1)end{matrix}right.$ .

The conclusion is thus that any $Y$ which can be divided by a squared integer larger than or equal to $4^2$ provides a solution. Now, if we look at the decomposition of

$2010=2times 3times 5times 67$ ,

$2011=2011times 1$ ,

$2012=2^4times 503$ ,

$2013=3times 11times 61$ ,

$2014=2times 19times 53$ ,

$2015=5times 13times 31$ ,

$2016=2^5times 3^2times 7$ ,

we see (without any R programming) that $(Y,N)=(2016,504)$ is the smallest solution (in $Y$ ). $Y=2016$ is the smallest solution with $N=504$ a possible solution in $N$ ( $N=168$ being another one). Which makes (at least) for a more bearable diversion in the plane…

An approach avoiding the second degree equation is to notice that $N(Y-N)=cY$ implies that $N$ and $Y$ share a largest common divider $h>1$ , i.e.

$Y=hY^prime,,quad N=hN^prime$

which implies

$N^prime(Y^prime-N^prime)h=cY^prime$ ,

thus that $Y^prime$ divides $k$ (because both other terms are prime with $Y^prime$ ). Eliminating dividers common to $c$ and $N^prime$ actually leads to $Y^prime=k$ , hence to the same conclusion as before.