y a plus de mouchoirs au bureau des pleurs

Once the French government started giving up to some requests of the unstructured “gilets jaunes” protesters, it was like a flood or flush gate had opened and every category was soon asking for a rise (in benefits) and a decrease (in taxes) or the abolition of a recent measure (like the new procedure for entering university after high school). As an illustration, I read a rather bemusing tribune in Le Monde from a collective of PhD students against asking non-EU students (including PhD students) to pay fees to study in French universities. This may sound a bit of a surrealistic debate from abroad, but the most curious point in the tribune [besides the seemingly paradoxical title of students against Bienvenue En France!] is to argue that asking these students to pay the intended amount would bring their net stipends below the legal minimum wage, considering that they are regular workers… (Which is not completely untrue when remembering that in France the stipends are taxed for income tax and retirement benefits and unemployment benefits, meaning that a new PhD graduate with no position can apply for these benefits.) It seems to me that the solution adopted in most countries, namely that the registration fees are incorporated within the PhD grants, could apply here as well… The other argument that raising these fees from essentially zero to 3000 euros is going to stop bright foreign students to do their PhD in France is not particularly strong when considering that the proportion of foreign students among PhD students here is slightly inferior to the proportion in the UK and the US, where the fees are anything but negligible, especially for foreign students.

Le Monde puzzle [#1076]

A cheezy Le Monde mathematical puzzle : (which took me much longer to find [in the sense of locating] than to solve, as Warwick U does not get a daily delivery of the newspaper [and this is pre-Brexit!]):

Take a round pizza (or a wheel of Gruyère) cut into seven identical slices and turn one slice upside down. If the only possibly moves are to turn three connected slices to their reverse side, how many moves at least are needed to recover the original configuration? What is the starting configuration that requires the largest number of moves?

Since there are ony N=2⁷ possible configurations, a brute force exploration is achievable, starting from the perfect configuration requiring zero move and adding all configurations found by one additional move at a time… Until all configurations have been visited and all associated numbers of steps are stable. Here is my R implementation

nztr=lengz=rep(-1,N) #length & ancestor
nztr[0+1]=lengz[0+1]=0 
fundz=matrix(0,Z,Z) #Z=7
for (i in 1:Z){ #only possible moves
  fundz[i,c(i,(i+1)%%Z+Z*(i==(Z-1)),(i+2)%%Z+Z*(i==(Z-2)))]=1
  lengz[bit2int(fundz[i,])+1]=1
  nztr[bit2int(fundz[i,])+1]=0}
while (min(lengz)==-1){ #second loop omitted
  for (j in (1:N)[lengz>-1])
  for (k in 1:Z){
    m=bit2int((int2bit(j-1)+fundz[k,])%%2)+1
    if ((lengz[m]==-1)|(lengz[m]>lengz[j]+1)){
      lengz[m]=lengz[j]+1;nztr[m]=j}
      }}

Which produces a path of length five returning (1,0,0,0,0,0,0) to the original state:

> nztry(2)
[1] 1 0 0 0 0 0 0
[1] 0 1 1 0 0 0 0
[1] 0 1 0 1 1 0 0
[1] 0 1 0 0 0 1 0
[1] 1 1 0 0 0 0 1
[1] 0 0 0 0 0 0 0

and a path of length seven in the worst case:

> nztry(2^7)
[1] 1 1 1 1 1 1 1
[1] 1 1 1 1 0 0 0
[1] 1 0 0 0 0 0 0
[1] 0 1 1 0 0 0 0
[1] 0 1 0 1 1 0 0
[1] 0 1 0 0 0 1 0
[1] 1 1 0 0 0 0 1
[1] 0 0 0 0 0 0 0

Since the R code was written for an arbitrary number Z of slices, I checked that there is no solution for Z being a multiple of 3.

about French inequalities [graphs]

A first graph in Le Monde about the impact of the recent tax changes on French households as a percentage of net income with negative values at both ends, except for a small spike at about 10% and another one for the upper 1%, presumably linked with the end of the fortune tax (ISF).

A second one showing incompressible expenses by income category, with poorest households facing a large constraint on lodging, missing the fraction due to taxes. Unless the percentage is computed after tax.

A last and amazing one detailing the median monthly income per socio-professional category, not because of the obvious typo on the blue collar median 1994!, but more fundamentally because retirees have a median income in the upper part of the range. (This may be true in most developed countries, I was just unaware of this imbalance.)

Le Monde puzzle [#1075]

A new Le Monde mathematical puzzle in the digit category:

Find the largest number such that each of its internal digits is strictly less than the average of its two neighbours. Same question when all digits differ.

For instance, n=96433469 is such a number. When trying pure brute force (with the usual integer2digits function!)

le=solz=3
while (length(solz)>0){
 solz=NULL
 for (i in (10^(le+1)-1):(9*10^le+9)){
  x=as.numeric(strsplit(as.character(i), "")[[1]])
 if (min(x[-c(1,le+1)]<(x[-c(1,2)]+x[-c(le,le+1)])/2)==1){ print(i);solz=c(solz,i); break()}}
 le=le+1}

this is actually the largest number returned by the R code. There is no solution with 9 digits. Adding an extra condition

le=solz=3
while (length(solz)>0){
 solz=NULL
 for (i in (10^(le+1)-1):(9*10^le+9)){
  x=as.numeric(strsplit(as.character(i), "")[[1]])
 if ((min(x[-c(1,le+1)]<(x[-c(1,2)]+x[-c(le,le+1)])/2)==1)&
    (length(unique(x))==le+1)){ print(i);solz=c(solz,i); break()}}
 le=le+1}

produces n=9520148 (seven digits) as the largest possible integer.

Le Monde puzzle [#1078]

Recalling Le Monde mathematical puzzle  first competition problem

Given yay/nay answers to the three following questions about the integer 13≤n≤1300 (i) is the integer n less than 500? (ii) is n a perfect square? (iii) is n a perfect cube?  n cannot be determined, but it is certain that any answer to the fourth question (iv) are all digits of n distinct? allows to identify n. What is n if the answer provided for (ii) was false.

When looking at perfect squares less than 1300 (33) and perfect cubes less than 1300 (8), there exists one single common integer less than 500 (64) and one single above (729). Hence, it is not possible that answers to (ii) and (iii) are both positive, since the final (iv) would then be unnecessary. If the answer to (ii) is negative and the answer to (iii) is positive, it would mean that the value of n is either 512 or 10³ depending on the answer to (i), excluding numbers below 500 since there is no unicity even after (iv). When switching to a positive answer to (ii), this produces 729 as the puzzle solution.

Incidentally, while Amic, Robin, and I finished among the 25 ex-aequos of the competition, none of us reached the subsidiary maximal number of points to become the overall winner. It may be that I will attend the reward ceremony at Musée des Arts et Métiers next Sunday.

Le Monde puzzle [#1075]

A Le Monde mathematical puzzle from after the competition:

A sequence of five integers can only be modified by subtracting an integer N from two neighbours of an entry and adding 2N to the entry.  Given the configuration below, what is the minimal number of steps to reach non-negative entries everywhere? Is this feasible for any configuration?

As I quickly found a solution by hand in four steps, but missed the mathematical principle behind!, I was not very enthusiastic in trying a simulated annealing version by selecting the place to change inversely proportional to its value, but I eventually tried and also obtained the same solution:

      [,1] [,2] [,3] [,4] [,5]
   -3    1    1    1    1
    1   -1    1    1   -1
    0    1    0    1   -1
   -1    1    0    0    1
    1    0    0    0    0

But (update!) Jean-Louis Fouley came up with one step less!

      [,1] [,2] [,3] [,4] [,5]
   -3    1    1    1    1
    3   -2    1    1   -2
    2    0    0    1   -2
    1    0    0    0    0

The second part of the question is more interesting, but again without a clear mathematical lead, I could only attempt a large number of configurations and check whether all admitted “solutions”. So far none failed.

Le Monde puzzle [#1073]

And here is Le Monde mathematical puzzle  last competition problem

Find the number of integers such that their 15 digits are all between 1,2,3,4, and the absolute difference between two consecutive digits is 1. Among these numbers how many have 1 as their three-before-last digit and how many have 2?

Combinatorics!!! While it seems like a Gordian knot because the number of choices depends on whether or not a digit is an endpoint (1 or 4), there is a nice recurrence relation between the numbers of such integers with n digits and leftmost digit i, namely that

n⁴=(n-1)³, n³=(n-1)²+(n-1)⁴, n²=(n-1)²+(n-1)¹, n¹=(n-1)²

with starting values 1¹=1²=1³=1⁴=1 (and hopefully obvious notations). Hence it is sufficient to iterate the corresponding transition matrix

on this starting vector 14 times (with R, which does not enjoy a built-in matrix power) to end up with

15¹=610, 15²= 987, 15³= 987, 15⁴= 610

which leads to 3194 different numbers as the solution to the first question. As pointed out later by Amic and Robin in Dauphine, this happens to be twice Fibonacci’s sequence.

For the second question, the same matrix applies, with a different initial vector. Out of the 3+5+5+3=16 different integers with 4 digits, 3 start with 1 and 5 with 2. Then multiplying (3,0,0,0) by M¹⁰ leads to 267+165=432 different values for the 15 digit integers and multiplying (0,5,0,0) by M¹⁰ to. 445+720=1165 integers. (With the reassuring property that 432+1165 is half of 3194!) This is yet another puzzle in the competition that is of no special difficulty and with no further challenge going from the first to the second question…