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).

Advertisements

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 ith 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 ith 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.