Archive for puzzle

Newer Entries »

New Le Monde puzzle

Posted in Kids, R with tags , on March 4, 2010 by xi'an

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 Comments »

Le Monde puzzle

Posted in Statistics with tags , on February 21, 2010 by xi'an

The puzzle in Le Monde is quite straightforward (!) this weekend: it can be rewritten as to figure out the values of the sums

10! \displaystyle{\left.\left\{1 - \sum_{j_1=1}^{10} \frac{1}{j_1}\left\{1-\sum_{\stackrel{j_2=1}{j_2\ne j_1}}^{10}\frac{1}{j_2}\right\{1-\ldots\right.\right.}

\displaystyle{\qquad\ldots\left.\left.\left.\left\{1-\sum_{\stackrel{j_9=1}{j_9\ne j_1,\ldots,j_8}}^{10} \frac{1}{j_9}\right\}\ldots\right\}\right\}\right\}}

and

\displaystyle{\left.(49!)^2 \left\{1 - \sum_{j_1=1}^{49} \frac{1}{j_1^2}\left\{1-\sum_{\stackrel{j_2=1}{j_2\ne j_1}}^{49}\frac{1}{j_2^2}\right\{1-\ldots\qquad\right.\right.}

\displaystyle{\qquad\ldots\left.\left.\left.\left\{1-\sum_{\stackrel{j_{48}=1}{j_{48}\ne j_1,\ldots,j_{47}}}^{49} \frac{1}{j_{48}^2}\right\}\ldots\right\}\right\}\right\}}

which are easily displayed and as easily solved.

The first sum can indeed be written as

\displaystyle{\sum_{i=1}^k (-1)^{k-i} \sum_{\stackrel{j_1\ne\cdots\ne j_i}{\in\{1,\ldots,k\}}} \prod_{u=1}^i j_u}

for k=10. This is simply

\displaystyle{\sum_{i=0}^k (-1)^{k-i} \sum_{\stackrel{j_1\ne\cdots\ne j_i}{\in\{1,\ldots,k\}}} \prod_{u=1}^i j_u}- (-1)^k = \prod_{i=1}^k (i-1) - (-1)^k

and the solution is thus (-1)^{k+1}, equal to -1 for k=10. Once we realise the fact this is a product with one missing term, the second sum is similar: it can be written as

\displaystyle{\sum_{i=0}^k (-1)^{k-i} \sum_{\stackrel{j_1\ne\cdots\ne j_i}{\in\{1,\ldots,k\}}} \prod_{u=1}^i j_u^2}- (-1)^k

\qquad = \prod_{i=1}^k (i^2-1) - (-1)^k = - (-1)^k

This is equal to 1 for k=49. A bit disappointing because it amounts to reformulate the question with the proper algebraic formula…

4 Comments »

Newer Entries »