New Le Monde puzzle

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(Y\pm\sqrt{Y^2-4cY}\right)/2 = Y \left(1\pm\sqrt{1-4c/Y}\right)/2$

which implies that

$2 / \left(1\pm\sqrt{1-4c/Y}\right)$

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

$Y=qk$ with $1\pm\sqrt{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 $4c\le Y$ implies $k\ge 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=2\times 3\times 5\times 67$,

$2011=2011\times 1$,

$2012=2^4\times 503$,

$2013=3\times 11\times 61$,

$2014=2\times 19\times 53$,

$2015=5\times 13\times 31$,

$2016=2^5\times 3^2\times 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.

8 Responses to “New Le Monde puzzle”

1. […] Monde puzzle [41] The current puzzle in Le Monde this week is again about prime […]

2. […] current puzzle in Le Monde this week is again about prime […]

3. […] Monde rank test In the puzzle found in Le Monde of this weekend, the mathematical object behind the silly story is defined as a pseudo-Spearman […]

4. […] In connection with the Le Monde puzzle of last week, I was looking for an R function that would give me the prime factor decomposition of […]

5. Robin has posted his solution, which is much cleaner and terser. Plus, he account for the additional constraint of having a single decomposition.

6. […] allow me to attend, unfortunately). The most important word is only; without that word, brute force would be the best way to […]

7. Mark Fisher Says:

First, there appears to be a bug in your R program since (Y, N) = (2012, 1006) is not a solution. (The problem requires N < Y/2.)

Second, since there are 5 solutions with Y = 2016 (N = 168, 336, 504, 672, 840), why do you refer to (Y, N) = (2016, 504) as the smallest?

(I wrote a Mathematica program for brute-force checking.)

• Mark: thanks for the points. I first looked at solutions and ran my R program without imposing the constraint. The “smallest” in my answer is referring to $Y$, as this was the original question. It is true there are several solutions in $N$. Actually, Le Monde asked for the smallest solution in $Y$ with a unique solution in $N$.