Last weekend we biked to the Festival du Monde, which holds a series of events and interactions with the journal team, if not at the level of The New Yorker Festival. In and around the modern building of Le Monde, near Gare d’Austerlitz. As most sessions were already booked, with only one entry left for my wife (on the incoming US Presidential Elections), I stayed outside on the small plaza and listened to (blah) bands, tasted yummy olive oils from Brazil and Uruguay that were part of a Southern Hemisphere oil competition (Brazil won!), a tepid empanada, a comfort plantain banana bowl and Bordeaux red wine aged in clay amphoras! While speaking with the winemaker was very nice, from the mix of Petit Verdot and Merlot (even though the vineyard page mentions Malbec!), to the local making of the amphoras, the outcome (of this recent experiment) was not that great. (Still hoping for a Georgian orange wine experiment!)
Archive for Gare d’Austerlitz
Le Monde [festival]
Posted in Books, pictures, Travel, Wines with tags amphora, Bordeaux, Brazil, Carmenere, festival, France, Gare d'Austerlitz, Georgia, Le Monde, Malbec, Merlot, olive oil, orange wine, Paris, Petit Verdot, Seine, The New Yorker, Uruguay, US elections 2024, wine making on October 6, 2024 by xi'anLe Monde puzzle [#1164]
Posted in Books, Kids, R with tags Diophanti Alexandrini Arithmeticorum, Diophantine equations, Euclidean algorithm, Frobenius number, Gare d'Austerlitz, james Joseph Sylvester, Le Monde, Mathematica, mathematical puzzle, Paris, partition, prime numbers, R, Wolfram Research on November 16, 2020 by xi'an
The weekly puzzle from Le Monde is quite similar to older Diophantine episodes (I find myself impossible to point out):
Give the maximum integer that cannot be written as 105x+30y+14z. Same question for 105x+70y+42z+30w.
These are indeed Diophantine equations and the existence of a solution is linked with Bézout’s Lemma. Take the first equation. Since 105 and 30 have a greatest common divisor equal to 3×5=15, there exists a pair (x⁰,y⁰) such that
105 x⁰ + 30 y⁰ = 15
hence a solution to every equation of the form
105 x + 30 y = 15 a
for any relative integer a. Similarly, since 14 and 15 are co-prime,
there exists a pair (a⁰,b⁰) such that
15 a⁰ + 14 b⁰ = 1
hence a solution to every equation of the form
15 a⁰ + 14 b⁰ = c
for every relative integer c. Meaning 105x+30y+14z=c can be solved in all cases. The same result applies to the second equation. Since algorithms for Bézout’s decomposition are readily available, there is little point in writing an R code..! However, the original question must impose the coefficients to be positive, which of course kills the Bézout’s identity argument. Stack Exchange provides the answer as the linear Diophantine problem of Frobenius! While there is no universal solution for three and more base integers, Mathematica enjoys a FrobeniusNumber solver. Producing 271 and 383 as the largest non-representable integers. Also found by my R code
o=function(i,e,x){
if((a<-sum(!!i))==sum(!!e))sol=(sum(i*e)==x) else{sol=0
for(j in 0:(x/e[a+1]))sol=max(sol,o(c(i,j),e,x))}
sol}
a=(min(e)-1)*(max(e)-1)#upper bound
M=b=((l<-length(e)-1)*prod(e))^(1/l)-sum(e)#lower bound
for(x in a:b){sol=0
for(i in 0:(x/e[1]))sol=max(sol,o(i,e,x))
M=max(M,x*!sol)}
(And this led me to recover the earlier ‘Og entry on the coin problem! As of last November.) The published solution does not bring any useful light as to why 383 is the solution, except for demonstrating that 383 is non-representable and any larger integer is representable.
Le Monde puzzle [#1158]
Posted in Books, Kids, R with tags brute-force solution, Gare d'Austerlitz, Le Monde, mathematical puzzle, Paris, R on November 10, 2020 by xi'anA weekly puzzle from Le Monde on umbrella sharing:
Four friends, Antsa, Cyprien, Domoina and Fy, are leaving school to return to their common housing. It is raining and they only have one umbrella with only room for two. Given walking times, x¹, x², x³ and x⁴, find the fastest time by which all of the four will be home, assuming they all agree to come back with the umbrella if need be.
A recursive R function produces the solution
bez=function(starz=rexp(4),finiz=rep(0,4),rtrn=F){
if((!rtrn)&(sum(starz>0)==2)){return(max(starz))
}else{
tim=1e6
if(rtrn){
for(i in (1:4)[finiz>0]){
nstart=starz;nstart[i]=finiz[i]
nfini=finiz;nfini[i]=0
targ=finiz[i]+bez(nstart,nfini,FALSE)
if(targ<tim){tim=targ}}
}else{
for(i in (1:4)[starz>0])
for(j in (1:4)[starz>0]){
if(i!=j){
nstar=starz;nstar[i]=nstar[j]=0
nfini=finiz;nfini[i]=starz[i];nfini[j]=starz[j]
targ=max(starz[i],starz[j])+bez(nstar,nfini,TRUE)
if (targ<tim){tim=targ}
}}}
return(tim)}
which gives for instance
> bez() [1] 3.297975 > bez(1:4) [1] 11 > bez(rep(3,4)) [1] 15
Le Monde puzzle [#1159]
Posted in Books, Kids, R with tags brute-force solution, Gare d'Austerlitz, Le Monde, mathematical puzzle, Paris, partition, R on October 6, 2020 by xi'anThe weekly puzzle from Le Monde is quite similar to #1157:
Is it possible to break the ten first integers, 1,…,10, into two groups such that the sum over the first group is equal to the product over the second? Is it possible that the second group is of cardinal 4? of cardinal 3?
An exhaustive R search returns 3 solutions by
library(R.utils) bitz<-function(i) c(rev(as.binary(i)),rep(0,10))[d<-1:10] for (i in 1:2^10) if (sum(d[!!bitz(i)])==prod(b<-d[!bitz(i)])) print(b)
[1] 1 4 10 #40
[1] 6 7 #42
[1] 1 2 3 7 #42
which brings a positive reply to the question. Moving from N=10 to N=19 produces similar results
[1] 1 9 18 #162 [1] 2 6 14 #168 [1] 1 3 4 14 #168 [1] 1 2 7 12 #168
with this interesting pattern of only two acceptable products, but I am obviously unable to run the same code for N=49, which is the subsidiary question to the puzzle. Turning to a more conceptual (!) approach, over a long insomnia bout (!!) and a subsequent run, I realised that if there are three terms, x¹,x² and x³, in the second group, they need satisfy
x¹x²x³+x¹+x²+x³=½N(N+1)
and if in addition one of them is equal to 1, x¹ say, this equation simplifies into
(x²+1)(x³+1)=½N(N+1)
which always leads to a solution, as e.g. for N=49,
x¹=1, x²=24 and x³=48.
A brute-force search also led to a four term solution in that case
x¹=1, x²=7, x³=10 and x⁴=17.
Le Monde puzzle [#1157]
Posted in Books, Kids, R with tags brute-force solution, Gare d'Austerlitz, Le Monde, mathematical puzzle, Paris, R, tournament on October 1, 2020 by xi'anThe weekly puzzle from Le Monde is an empty (?) challenge:
Kimmernaq and Aputsiaq play a game where Kimmernaq picks ten different integers between 1 and 100, and Aputsiaq must find a partition of these integers into two groups with identical sums. Who is winning?
Indeed, if the sums are equal, then the sum of their sums is even, meaning the sum of the ten integers is even. Any choice of these integers such that the sum is odd is a sure win for Kimmernaq. End of the lame game (if I understood its wording correctly!). If some integers can be left out of the groups, then both solutions seem possible: calling the R code
P=1;M=1e3
while (P<M){
a=sample(1:M,10);P=Q=0
while((P<M)&(!Q)){
t=sample(1:7,1) #size of subset
o=1 #total sum must be even
while(!!(s<-sum(o))%%2)o=sample(a,10-t)
Q=max(2*cumsum(b<-sample(o))==s)
P=P+1}}
I found no solution (i.e. exiting the outer while loop) for M not too large… So Aputsiaq is apparently winning. Le Monde solution considers the 2¹⁰-1=1023 possible sums made out of 10 integers, which cannot exceed 955, hence some of these sums must be equal (and the same applies when removing the common terms from both sums!). When considering the second half of the question
What if Kimmernaq picks 6 distinct integers between 1 and 40, and Aputsiaq must find a partition of these integers into two groups with identical sums. Who is winning?
recycling the above R code produced subsets systematically hitting the upper bound M, for much larger values. So Kimmernaq should have a mean to pick 6 integers such that any subgroup cannot be broken into two parts with identical sums. One of the outcomes being
> a [1] 36 38 30 18 1 22
one can check that all the possible sums differ:
aa=a
for(i in 2:5){
bb=NULL
while(length(bb)<choose(6,i))bb=unique(c(bb,sum(sample(a,i))))
aa=c(aa,bb)}
unique(aa)
and the outcome is indeed of length 2⁶-2=62!
As an aside, a strange [to me at least] R “mistake” was that when recycling the variable F in a code-golfing spirit, since it is equal to zero by default, rather than defining a new Q:
while((P<M)&(!F)){
...
F=max(2*cumsum(b<-sample(o))==s)
P=P+1}
the counter P was not getting updated!
