## Posts Tagged ‘Le Monde’

### Le Monde problem on PIN number

30/09/2010

Now that the new school year has started, Christian Robert has picked up solving the Le Monde mathematical puzzles using R again, which leads me to solving them without R… Last week-end’s puzzle is:

Alice’s PIN number is made of four different non-zero digits. She remembers it by noting that when she sums all two-digit numbers that can be made out of those four digits, and multiplies this sum by 7, she gets her PIN number back.

If the PIN number is written $\overline{abcd}$, it is easy to check that the sum computed by Alice is equal to $33*(a+b+c+d)$. Thus $\overline{abcd}=231*(a+b+c+d)$.

The sum $(a+b+c+d)$ can take values between 10 and 30. Since 231 is divisible by 3, so is $\overline{abcd}$. Hence (by the rule used to check for divisibility by 3), $(a+b+c+d)$ is divisible by 3. This makes $\overline{abcd}$ divisible by 9, and so (by the rule used to check for divisibility by 9) $(a+b+c+d)$ is also divisible by 9.

The only possible values for $(a+b+c+d)$ are 18 and 27. It turns out that the only value which works is 18. Hence the PIN number is $18 \times 231 = 4158$ (and the sum of those four digits is indeed equal to 18).

### Candy branching process

07/05/2010

Christian Robert has basically forced me to post my solution to last week’s Le Monde problem:

Two kids are given three boxes of chocolates with a total of 32 pieces. Rather than sharing evenly, they play the following game: Each in turn, they pick one of the three boxes, empty its contents in a jar and pick some chocolates from one of the remaining boxes so that no box stays empty. The game ends with the current player’s loss when this is no longer possible. What is the optimal strategy?

Although we don’t know the number of chocolates in each box, the kids do. A kid loses when at his turn, he is faced with the configuration (1,1,1): he has to leave one empty, thus losing. Note that the total number of chocolates decreases at each turn.

Because the initial number of chocolates is a power of 2, the first kid (A) is guaranteed to win. Let us look at the parity of the number of chocolates in each box. The strategy of player A is to give to the other kid (B) a configuration of the form (odd, odd, odd). Then B will necessarily return (odd, odd, even) to A. Kid A can empty a box with an odd number of chocolates, split the even number into two odd numbers, and B is faced again with (odd,odd,odd). Eventually, B will end up with (1,1,1) and lose.

Note also that any (odd, even, even) configuration wins: empty one of the even boxes, and split the other even number into two odd numbers.

The only remaining question is what to do with a configuration (even, even, even). Per the above, the first player to introduce a box with an odd number of chocolates loses. Kid A’s strategy is now to give B a configuration of the form (4a+2, 4b+2, 4c+2). To avoid odd numbers, B must give A a configuration of the form (4a+2, 4d+2, 4e), where the number of chocolates in box 3 is a multiple of 4. Kid A can then empty one of the first two boxes, giving B (4a+2, 4f+2, 4g+2) again, and so on until B is faced with (2, 2, 2), at which point he has lost.

This can be easily generalized: let a configuration be of the form $\left(2^n a, 2^n b, 2^n c\right)$, with n as large as possible (so at least one of a, b, c is odd). If a, b and c are all odd, the configuration loses; otherwise, it can be transformed into a configuration where a, b and c are all odd, and the other player loses.

Because the initial total number of chocolates is a power of 2, the initial configuration is necessarily a winning configuration.

### Le Monde problem: “Nationale 7”

23/03/2010

It seems that solving mathematical puzzles from Le Monde is becoming the main focus of this blog. This week’s problem is about a road with 100 trees: 50 elms and 50 plane trees, in a random order. We are asked to show that whatever the order of the trees, there exists a sequence of 50 consecutive trees with exactly 25 elms and 25 plane trees.

Let $v_k (k=1,\ldots 51)$ be the number of elms between positions $k$ and $k+49$; we are asked to prove that there exists a $k$ such that $v_k=25$. Note that $v_1+v_{51}=50$, since that includes all the trees exactly once. By symmetry, we can assume that $v_1\leq 25$ and $v_{51}\geq 25$. Note also that the sets considered for $v_k$ and $v_{k+1}$ differ by only one tree, hence $| v_k - v_{k+1} | \leq 1$. Looking at the sequence $(v_k)$ we need to go from an integer below $25$ to an integer above $25$ by taking steps of size $0$ or $1$. At some point, we will necessarily go through $25$.

The exact same proof holds with only 98 trees (49 of each species). However, going down to 96 trees (48 of each), the following arrangement has no set of 50 consecutive trees with half of each: 24 elms, then 48 plane trees, then 24 elms.

### Le Monde problem: “The prediction”

04/03/2010

This week’s Le Monde mathematical problem is:

The scene is set in 2010. Young $N$, an integer looking for his soul-mate, consults a fortune-teller, who says: “Yes, you shall encounter the beloved number [call it $X$], a number strictly greater than you, but later! That year [call it $Y$], you will be the only [my emphasis]  two positive integers whose sum is equal to the year, and whose product is a multiple of the year.” When (at the earliest) will $N$ meet his soul -mate?

This is the kind of question which could be asked at the FFJM semi-finals in a couple of weeks (which my schedule doesn’t allow me to attend, unfortunately). The word only is key. (Christian solves the problem without that word.)

We have, for some integer $k$,

$X>N\\Y>2010\\X+N=Y\\XN=kY$

and we want to minimize $Y$.

Write $Y=ab^2$, with $a$ and $b$ integers and $b$ as large as possible. Then it is clear that both $X$ and $N$ are multiples of $ab$. Write $X=xab$ and $N=nab$. Suppose that we have a solution to the problem, with $(x,n)\neq (1,2)$; then the couple $(x+1,n-1)$ would give another solution. Hence $X=ab$, $N=2ab$ and $ab^2=Y=X+N=3ab$, so $b=3$.

The problem is now to find the smallest $Y=9a>2010$ such that no perfect square divides $a$ (otherwise $b$ would not be as large as possible). $2016=9\times 4^2 \times 14$ and $2025=9\times 15^2$ don’t work, so we move to $2034=9\times 2\times 113$, which does work.

The solution is then that in year $Y=2034$, young $N=678$ will meet $X=1356$ and they will live happily ever after.

### Le Monde puzzle on sums of products

25/02/2010

Christian Robert is disappointed by last week-end’s Le Monde’s mathematical problem :

Take the integers 1 to 10. Group them together; the product of these numbers is 3,628,800. This is the first term of your sum. Now group these numbers in 9s. There are 10 different ways of doing this. For each group, take the product of the 9 numbers and substract the results of each of these 10 products from your sum. Repeat the process by grouping the numbers in 8s (add the product), in 7s (substract them), …, in pairs (add them) and in singletons (substract them). What is the final total? What happens if, instead of 1 to 10, you apply the same (even more interminable) procedure to the first 49 squares (1, 4, 9, 16, … 2401)?

Christian solves this the brutal way, which gives the answer but isn’t very satisfying. Here are a couple of alternative ways of getting the product  (call it $P$).

1. Consider the following 11×11 matrix:

$\begin{tabular}{*{11}{c}} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0& 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0& 0 & 3 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0& 0 & 0 & 4 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0& 0 & 0 & 0 & 5 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0& 0 & 0 & 0 & 0 & 6 & 1 & 1 & 1 & 1 & 1 \\ 0& 0 & 0 & 0 & 0 & 0 & 7 & 1 & 1 & 1 & 1 \\ 0& 0 & 0 & 0 & 0 & 0 & 0 & 8 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 9 & 1 & 1 \\ 0& 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 10 & 1 \\1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\end{tabular}$

The determinant is obviously 0 (the first and last row are identical). On the other hand, using the Leibniz formula to calculate the determinant would yield all the terms in the product calculated above, plus one term given by the bottom-leftmost 1 and the 1s on the diagonal above the main diagonal. Hence $0=P+1$.

2. This solution is more obvious, and  I expect Le Monde will give a solution similar to this. Let $P_n$ be the product given when using the numbers 1 to $n$. Then

$P_n=nP_{n-1} -P_{n-1} +(-1)^{n-1} \times n$

whence $P_n=(-1)^{n-1}$.

3. I was hoping to find a counting argument to solve this problem, because the alternating signs reminded me of the formula for the cardinal of a union of sets. Here’s the best I have come up with, but I’m sure there’s a better way of seeing this.

Consider the set of all sequences of 10 integers where the $i$th entry is an integer between 1 and $i$; this corresponds to the sequences which lie in the lexicographic order between $(1,1,1,\ldots , 1)$ and $(1, 2, 3, \ldots , 10)$. There are clearly $10!$ such sequences, but let’s count them in a more stupid way, noting that each sequence contains at least one $1$..

Let $A_i$ be the number of such sequences with the additional constraint that the $i$th entry is equal to $1$. Then, using $\vert \cdot \vert$ to denote the cardinal function, we have

$10! = | \cup A_{i} | = | A_1 | + | A_2 | + \ldots + | A_{10} | - |A_1 \cap A_2 | - |A_1 \cap A_3| \ldots + |A_1 \cap A_2 \cap A_3| \ldots$

Each of these terms corresponds to a term in $P$, with the exception of the last term $|A_1\cap A_2 \cap \ldots \cap A_{10}|$, which is worth $1$ and comes with the sign of $(-1)^{n-1}$.

A very similar reasoning holds if we take numbers other than 1, 2, … 10, as long as the first number is a $1$.