Le Monde puzzle [#1013]

A purely arithmetic Le Monde mathematical puzzle:

An operation þ applies to all pairs of natural integers with the properties

0 þ (a+1) = (0 þ a)+1, (a+1) þ (b+1)=(a þ b)+1, 271 þ 287 = 77777, 2018 þ 39 = 2018×39

Find the smallest integer d>287 such that there exists c<d leading to c þ d = c x d, the smallest integer f>2017 such that 2017 þ f = 2017×40. Is there any know integer f such that f þ 2017 = 40×2017?

The major appeal in this puzzle (where no R programming seems to help!) is that the “data” does not completely defines the operation  þ ! Indeed, when a<b, it is straightforward to deduce that a þ b = (0 þ 0)+b, hence solving the first two questions by deriving (0 þ 0)=270×287 [with d=2×287 and f=2017×40-270×287], but the opposed quantity b þ a is not defined, apart from (2018-39) þ 0. This however brings a resolution since

(2018-39) þ 0 = 2017×39 and (2018-39+2017) þ 2017 = 2017×39+2017 = 2017×40

leading to f=2018-39+2017=3996.

Cédric Villani elected

Le Monde puzzle [#1012]

A basic geometric Le Monde mathematical puzzle:

Take a triangle ABC such that the side AB is c=42 long, each side has an integer length, and the area is 756. Given an inner point D, draw three lines parallel to the three sides of ABC through D in order to construct three triangles with common summit D and bases supported by these three sides.

1. How far is D from the base AB when all three triangles have perimeters equal to the sides that support their basis?
2. How far is D from the previous solution when the sum of the areas of the three triangles is minimal?

Since the puzzle is purely geometric, I was quite tempted to bypass it and to watch instead the British elections and the Comey audition! However, the sides a and b are easily found by an exhaustive search, a=39 and b=45 (or the reverse). From there, the problem resolution proceeds by a similar triangles argument, since all triangles constructed by the game rule have the same angles, hence proportional sides. For the first question, this leads to a straightforward determination of the basis of each triangle by the perimeter equation, meaning that D is then 12 units away from AB. The second question is not harder in that the surface of a triangle with basis a and opposite angles β and γ can be written as

a²sin(β)sin(γ)/2sin(β+γ)

meaning it suffices to minimise a²+a’²+a”² under the constraint that the sum of the three sides parallel to BC is the complete length of BC, a²+a’²+a”²=39. The solution is then that all triangles are identical, leading to a summit D’ at a distance 12 from AB, again!, but in the middle of the segment, hence distance to the earlier D equal to one.

Le Monde puzzle [#1011]

An combinatoric Le Monde mathematical puzzle (with two independent parts):

Given the following grid,

1. What is the longest path from A to B that does not use the same edge twice?
2.  What is the probability that two minimal length paths from A to B [of length 13] share the same middle [7th] edge?

The first question can be solved by brute force simulation. I ran a very simple minded self-avoiding random walk starting from A and restarting each time a dead-end was reached. (The details are not of capital interest: I entered the above grid as an 8×7 matrix for the nodes and associated with each node a four bit number indicating which edge had been visited. Picking at random among those not yet visited.) The longest path I found along 10⁷ simulations is 51 edges long, confirmed by an additional exploration of the paths on both square grids, separately. The associated path is as follows, the irregular shape being obtained by jittering the node locations towards a better visualisation of the order of the visits.

The second puzzle can be solved directly by looking at the number of paths sharing the seventh edge, which is ¼ (as checked by a further simulation of minimal length random walks).

Le Monde puzzle [#1010]

An arithmetic Le Monde mathematical puzzle (or two independent ones, again!):

1. Take the integers from 1 to 19, pick two of them with identical parity at random and replace the pair with their average. Repeat 17 times to obtain a single integer. What are the values between 1 and 19 that cannot be achieved?
2.  Take the integers from 1 to 19, pick four of them at random so that the average is an integer and replace the quadruplet with their average. Repeat 5 times to obtain a single integer. What are the values between 1 and 19 that can be achieved?

The first question seems pretty open to brute force simulation. Here is an R code I wrote

numbz=1:M
for (t in 2:M){
 numbz=sample(numbz);count=0
 while((count<100)&(sum(numbz[1:2])%%2>0)){
   numbz=sample(numbz);count=count+1}
if (count==100) break()
 numbz[1]=as.integer(mean(numbz[1:2]))
 numbz=numbz[-2]}

with the stopping rule resulting from the fact that the remaining two digits may sometimes be of opposite parity (a possibility omitted in the wording of the puzzle, along with a mistake in the number of repetitions). However, the outcome of this random exploration misses the extreme possible values. For instance, 10⁶ attempts produce the range

4 5 6 7 8 9 10 11 12 13 14 15 16 17

while the extremes should be 2 and 18 according to this scratch computation:

which appears to have too low a probability of occurring for being part of the 10⁶ instances. Running the code a mere (!) 10⁷ iterations managed to reach 3 as well. (Interestingly, the above sequence uses 2 the most and 19 the least, but weights 19 the most and 2 the least!)

The second puzzle is also open to random exploration with a very similar R code:

utcome=NULL
for (z in 1:1e6){
numbz=1:19
for (t in 1:6){
  numbz=sample(numbz);count=0
  while ((sum(numbz[1:4])%%4>0)&(count<100)){
    numbz=sample(numbz);count=count+1}
  if (count==100) break()
  numbz[1]=as.integer(mean(numbz[1:4]))
  numbz=numbz[-(2:4)]}
if (count<100) utcome=c(utcome,numbz)}

returning the values

4 7 10 13 16

Le Monde puzzle [#1009]

An incomprehensible (and again double) Le Monde mathematical puzzle (despite requests to the authors! The details in brackets are mine.):

1. A [non-circular] chain of 63 papers clips can be broken into sub-chains by freeing one clip [from both neighbours] at a time. At a given stage, considering the set of the lengths of these sub-chains, the collection of all possible sums of these lengths is a subset of {1,…,63}. What is the minimal number of steps to recover the entire set {1,…,63}?  And what is the maximal length L of a chain of paper clips that allows this recovery in 8 steps?
2.  A tri-colored chain of 200 paper clips starts with a red, a blue and a green clip. Removing one clip every four clips produces a chain of 50 removed clips identical to the chain of 50 first clips of the original chain and a chain of remaining 150 clips identical to the 150 first clips of the original chain. Deduce the number of green, red, and blue clips.

The first question can be easily tackled by random exploration. Pick one number at random between 1 and 63, and keep picking attached clips until the set of sums is {1,…,63}. For instance,

rebreak0]
 sumz=cumsum(sample(difz))
 for (t in 1:1e3)
  sumz=unique(c(sumz,cumsum(sample(difz))))
 if (length(sumz)<63)
    brkz=rebreak(sort(c(brkz,sample((1:63)[-brkz],1))))
 return(brkz)}

where I used sampling to find the set of all possible partial sums. Which leads to a solution with three steps, at positions 5, 22, and 31. This sounds impossibly small but the corresponding lengths are

1 1 1 4 8 16 32

from which one can indeed recover by summation all numbers till 63=2⁶-1. From there, a solution in 8 steps can be found by directly considering the lengths

1 1 1 1 1 1 1 1 9 18=9+8 36=18+17+1 72 144 288 576 1152 2303

whose total sum is 4607. And with breaks

10 29 66 139 284 573 1150 2303

The second puzzle is completely independent. Running another R code reproducing the constraints leads to

tromcol=function(N=200){
  vale=rep(0,N)
  vale[1:3]=1:3
  while (min(vale)==0){
    vale[4*(1:50)]=vale[1:50]
    vale[-(4*(1:50))]=vale[1:150]}
  return(c(sum(vale==1),sum(vale==2),sum(vale==3)))}

and to 120 red clips, 46 blue clips and 34 green clips.

Le Monde puzzle [#1008]

An arithmetic Le Monde mathematical puzzle (or two independent ones, rather):

1. The set of integers between 1 and 2341 is partitioned into sets such that a given set never contains both n and 3n. What is the largest possible size of one of these sets?
2.  Numbers between 1 and 2N are separated in two sets A and B of size N. Alice takes the largest element out of A and the smallest element out of B, records the absolute difference as S, and then repeats the sampling, adding the absolute difference to S at each draw. Bob does the same with numbers between 1 and 2P, with P<N, obtaining a total value of R. Alice points out that S-R=2341. What are the values of N and P?

The first question seems hard to solve by brute force simulation. My first idea is to take all prime numbers [except 3!] less than 2341, which is itself a prime number, and all combinations of these numbers less than 2341, since none of those is divisible by 3. Adding 3 as a final item keeps the constraint fine if 1 is not part of it (but 1 is not a prime number, so this is under control). Adding instead 1 to the set has the same impact but seems more natural. The number of prime numbers is 346, while the total size of the set thus constructed is 1561. Equal to 1+2×2340/3. However, the constraint in the puzzle does not exclude m and 9m. Or m and 9²m, or m and 9³m. Considering such multiples within {1,…,2341} leads to a set with 1765 integers.

The second puzzle is indeed independent and actually straightforward when one realises that the sums S and R are always equal to N² and P², respectively. (This is easily proven by invariance under a permutation turning the lowest entries to B and the largest ones to A. But there must be a rank statistic identity behind this result!) Hence it boils down to figuring out a pair (N,P) such that N²-P²=2341. Since 2341=(N-P)(N+P) is prime, this implies N=P+1. And N²-(N-1)²=N²-N²+2N-1=2341. Which leads to (N,P)=(1171,1170) as the only solution.