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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 717 other followers