## Le Monde puzzle [#872]

Posted in Books, Kids, Statistics, University life with tags , , , , , on June 28, 2014 by xi'an

An “mildly interesting” Le Monde mathematical puzzle that eventually had me running R code on a cluster:

Within the set {1,…,56}, take 12 values at random, x1,…,x12. Is it always possible to pick two pairs from those 12 balls such that their sums are equal?

Indeed, while exhaustive search cannot reach the size of the set,

fowler=function(i=1,pred=NULL){
pred=c(pred,i)
for (j in (1:N)[-pred]){
a=outer(c(pred,j),c(pred,j),"+")
if ((sum(duplicated(a[lower.tri(a)]))>0)){
val=FALSE
}else{
if (length(pred)==n-1){
print(c(pred,j))
val=TRUE
}else{
val=fowler(j,pred)}}
if (val) break()
}
return(val)
}
fowler(i=N,pred=1)


with N=35 being my upper limit (and n=9 the largest value inducing double sums), the (second) easiest verification goes by sampling as indicated and checking for duplicates.

mindup=66
for (t in 1:10^7){
#arguing that extremes should be included
x=c(1,56,sample(2:55,10))
A=outer(x,x,"+")
mindup=min(mindup,sum(duplicated(A[lower.tri(A)])))
if (mindup==0) break()}


The values of mindup obtained by running this code a few times are around 5, which means a certain likelihood of a positive answer to the above question…

This problem raises a much more interesting question, namely how to force simulations of those 12-uplets towards the most extreme values of the target function, from simulated annealing to cross-entropy to you-name-it… Here is my simulated annealing attempt:

target=function(x){
a=outer(x,x,"+")
return(sum(duplicated(a[lower.tri(a)])))}
beta=100
Nmo=N-1
nmt=n-2
nmo=n-1
x=sort(sample(2:Nmo,nmt))
cur=c(1,x,N)
tarcur=target(cur)
for (t in 1:10^6){
dex=sample(2:nmo,2)
prop=sort(c(cur[-dex],sample((2:Nmo)[-(cur-1)],2)))
tarprop=target(prop)
if (beta*log(runif(1))<tarprop -tarcur){
cur=prop;tarcur=tarprop}
beta=beta*.9999
if (tarcur==0) break()}


Apart from this integer programming exercise, a few items of relevance in this Le Monde Science & Medicine leaflet.  A portrait of Leslie Lamport for his Turing Prize (yes, the very same Leslie Lamport who created LaTeX!, and wrote this book which stood on most mathematicians’ bookshelves for decades, with the marginally annoying lion comics at the head of each chapter!). A tribune on an interesting book, The Beginning and the End, by Clément Vidal, discussing how to prepare for the end of the Universe by creating a collective mind. And the rise of biobanks…

## Le Monde puzzle [#849]

Posted in Books, Kids, R, Statistics with tags , , , , , on January 19, 2014 by xi'an

A straightforward Le Monde mathematical puzzle:

Find a pair (a,b) of integers such that a has an odd number d of digits larger than 2 and ab is written as 10d+1+10a+1. Find the smallest possible values of a and of b.

I ran the following R code

d=3
for (a in 10^(d-1):(10^d-1)){
c=10^(d+1)+10*a+1
if (a*trunc(c/a)==c)
print(c(a,c))}


which produced a=137 (and b=83) as the unique case. For d=4, I obtained a=9091 and b=21, for d=6, a=909091, and b=21, for d=7, a=5882353 and b=27, while for d=5, my code did not return any solution. While d=8 took too long to run, a prime factor decomposition of 10⁹+1 leads to (with the schoolmath R library)

> for (d in 3:10) print(c(d,prime.factor(10^(d+1)+1)))
[1]   3  73 137
[1]    4   11 9091
[1]    5  101 9901
[1]      6     11 909091
[1]       7      17 5882353
[1]     8     7    11    13    19 52579
[1]     9   101  3541 27961
[1]   10   11   11   23 4093 8779


which gives a=52631579 and b=29 for d=8 and also explains why there is no solution for d=5. The corresponding a has too many digits!

This issue of Le Monde Science&Médecine leaflet had more interesting entries, from one on “LaTeX as the lingua franca of mathematicians”—which presumably made little sense to any reader unfamiliar with LaTeX—to the use of “big data” tools (like news rover) to analyse data produce by the medias, to  yet another tribune of Marco Zito about the “five sigma” rule used in particle physics (and for the Higgs boson analysis)—with the reasonable comment that a large number of repetitions of an experiment is likely to exhibit unlikely events, and an also reasonable recommendation to support “reproduction experiments” that aim at repeating exceptional phenomena—, to a solution to puzzle #848—where the resolution is the same as mine’s, but mentions the principle of Dirichlet’s drawers to exclude the fact that all prices are different, a principle I had never heard off…

## spot the LaTeX mistake

Posted in Books, Linux with tags , on April 22, 2013 by xi'an

It took me forever to spot the (obvious) mistake in the following LaTeX formula


\int \exp$-\{ (n+\sigma^{-2})\mu^2 -2n\mu{\bar x_n} + n ({\bar x_n})^2 \}/2$



Can you find it?!

## one of those weird LaTeX incidents…

Posted in Books, University life with tags , , , on February 26, 2013 by xi'an

This afternoon, I had to recompile a LαTεX file written two years ago (in French) and it returned the error:

 Missing \endcsname inserted.
\unskip
l.182 \citeyear{berger:robert:1990}
avec James Berger dans un article aux {\...


and I couldn’t figure out what had changed into the compiler to produce this strange message… Except that removing the line

\usepackage[french]{babel}


was removing the error message (but producing garbage French!).

I thus checked on forums and found some solution on a French LαTεX users forum called MathemaTeX. The issue had to do with using :’ in my reference codes… However, after fiddling with this solution, I ended up with

\usepackage[french,english]{babel}


as enough to remove the error message and produce the same output as earlier. Weird! (As I always use the same bibTeX file and do use babel-french from time to time… Maybe not that often with citations, actually!)

## \verbatim [beamer package]

Posted in R, Statistics, University life with tags , , , , , , on June 12, 2012 by xi'an

Once again working on my slides for the AMSI Lecture 2012 tour, it took me a while to get the following LaTeX code (about the family reunion puzzle) to work:

\begin{frame}[fragile,label=notleM2]
\slidetitle{A family meeting}
\begin{block}{Random switch of couples}
\only<1>{
\begin{itemize}
\item Pick two couples [among the 20 couples] at random with probabilities proportional
to the number of other couples they have not seen\\
{\verb+prob=apply(meet(T)==0,1,sum)+}
\item switch their respective position during one of the 6 courses
\item accept the switch with Metropolis--Hsatings probability\\
{\verb#log(runif(1))<(penalty(old)-penalty(new))/gamma#}
\end{itemize}
}
\only<2>{
\begin{verbatim}
for (t in 1:N){
prop=sample(1:20,2,prob=apply(meet(T)==0,1,sum))
cour=sample(1:6,1)
Tp=T
Tp[prop[1],cour]=T[prop[2],cour]
Tp[prop[2],cour]=T[prop[1],cour]
penatp=penalty(meet(Tp))
if (log(runif(1))<(penat-penatp)/gamma){
T=Tp
penat=penatp}
}
\end{verbatim}
}
\end{block}
\end{frame}

since I was getting error messages of the form

[86] (./simulation.38.vrb) [87] (./simulation.39.vrb
!Illegal parameter number in definition of \beamer@doifinframe.
l
l.12 }
?


Using two frames in a row instead of the “only<2>” version  did not help…

## \STATE [algorithmic package]

Posted in Books, Kids, pictures, R, Statistics, Travel, University life with tags , , , , , , , , , on June 8, 2012 by xi'an

I fought with my LαTεX compiler this morning as it did not want to deal with my code:

 \begin{algorithmic}[1]
\STATE N=1000
\STATE $\hat\pi=0$
\FOR {I=1,N}
\STATE X=RDN(1), Y=RDN(1)
\IF {$\text{X}^2+\text{Y}^2<1$}
$\hat\pi$ = $\hat\pi +1$
\ENDIF
\ENDFOR
\RETURN 4*$\hat\pi/$N
\end{algorithmic}


looking on forums for incompatibilities between beamer and algorithmic, and adding all kinds of packages, to no avail. Until I realised one \STATE was missing:

 \begin{algorithmic}[1]
\STATE N=1000
\STATE $\hat\pi=0$
\FOR {I=1,N}
\STATE X=RDN(1), Y=RDN(1)
\IF {$\text{X}^2+\text{Y}^2<1$}
\STATE $\hat\pi$ = $\hat\pi +1$
\ENDIF
\ENDFOR
\RETURN 4*$\hat\pi/$N
\end{algorithmic}
`

(This is connected with my AMSI public lecture on simulation, obviously!)

## the universe in zero words

Posted in Books, Kids, Statistics, University life with tags , , , , , , , , , , , , , , , , on May 30, 2012 by xi'an

The universe in zero words: The story of mathematics as told through equations is a book with a very nice cover: in case you cannot see the details on the picture, what looks like stars on a bright night sky are actually equations discussed in the book (plus actual stars!)…