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

To leave a comment for the author, please follow the link and comment on his blog: Xi'an's Og » R.

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



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Tags: , , ,

Comments are closed.