# New Le Monde puzzle

March 3, 2010
By

(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.

Filed under: Kids, R Tagged: Le Monde, puzzle

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...

Tags: , , ,