## Le Monde puzzle [#937]

Posted in Books, R with tags , , , , on November 11, 2015 by xi'an

A combinatoric Le Monde mathematical puzzle that resembles many earlier ones:

Given a pool of 30 interns allocated to three person night-shifts, is it possible to see 31 consecutive nights such that (a) all the shifts differ and (b) there are no pair of shifts with a single common intern?

In fact, the constraint there is very strong: two pairs of shift can only share zero or two interns. For one given shift, there are 26 other shifts with which it can share two interns, but then any two of those 26 others must share zero or two, which makes the two common to all and exclude any additional shift. But this is not the only approach to allocate the interns over the shifts since, as pointed out by Jean-Louis and checking with the following R code, 28 and not 27 is the maximum possible number of shifts under those conditions.

poss=combn(30,3)
shft=matrix(NA,31,3)
shft[1,]=sample(1:30,3)

poss=poss[,sample(4060)]
prop=poss[,1];k=2
acpt=intersect(prop,shft[1,])
while (((length(acpt)==1)+(length(acpt==3)))>0){
prop=poss[,k];k=k+1
acpt=intersect(prop,shft[1,])}
shft[2,]=prop
for(i in 3:31){
poss=poss[,sample(4060)]
prop=poss[,1];k=2
acpt=(length(intersect(prop,shft[1,]))==1)+(length(intersect(prop,shft[1,]))==3)
for (j in 2:(i-1))
acpt=acpt+(length(intersect(prop,shft[j,]))==1)+(length(intersect(prop,shft[j,]))==3)
while ((acpt>0)&(k<4061)){
prop=poss[,k];k=k+1
acpt=(length(intersect(prop,shft[1,]))==1)+(length(intersect(prop,shft[1,]))==3)
for (j in 2:(i-1))
acpt=acpt+(length(intersect(prop,shft[j,]))==1)+(length(intersect(prop,shft[j,]))==3)}
if (k==4061) break()
shft[i,]=prop}


## Le Monde puzzle [#934]

Posted in Books, Kids, pictures, Statistics, Travel, University life with tags , , , , on October 25, 2015 by xi'an

Another Le Monde mathematical puzzle with no R code:

Given a collection of 2€ coins and 5€ bills that sum up to 120€, find the number of 5€ bills such that the collection cannot be divided into 5 even parts.

Indeed, as soon as one starts formalising the problem, it falls apart: if there are a 5€ bills and b 2€ coins, we have 5a+2b=120, hence 2b=120-5a=5(24-a), meaning that b must be a multiple of 5, b=5b’ and a must be even, a=2a’, with b’=12-a’.  Hence, 10 possible values for both pairs (a’,b’) and (a,b), since a>0 and b>0. If these 120 Euros can be evenly divided between 5 persons, each gets 24€. Now, 24€ can be decomposed in 5€ bills and 2€ coins in three ways:

24=2×2+4×5=7×2+2×5=12×2+0x5.

Each of the five persons using any of the 3 above decompositions means there exist integers α, β, and γ such that

α(2×2+4×5)+β(12×2)+γ(7×2+2×5)=(2α+12β+7γ)x2+(4α+2γ)x5=bx2+ax5

with α+β+γ=5; therefore a=4α+2γ and b=2α+12β+7γ, which implies 2α+γ=a’ and 2α+12β+87γ=5×12-5a’=2α+5×12-12α-12γ+7γ, or 5a’=10α+5γ. That is, 2α+γ=a’ again… If a’=11, there is no solution with α+γ≤5, and this is the only such case. For any other value of a’, there is a way to divide the 120€ in 5 even parts. As often, I wonder at the point of the puzzle if this is the answer or at its phrasing if I have misunderstood the question.

Just to check the above by R means, I still wrote a short R code

for (a in 1:11){
# find integer solutions to 2x+y=a
sum=0;z=-1
while ((z<a)&(z<6)&(sum<2)){
z=z+1;x=trunc((a-z)/2);y=5-x-z
sum=(2*a==4*x+2*z)+(5*(11-a)==x+11*y+6*z)}
print(c(2*a,5*(11-a),x,y,z))
}


which returned

[1]  2 50  0  4  1
[1]  4 45  1  4  0
[1]  6 40  1  3  1
[1]  8 35  2  3  0
[1] 10 30  2  2  1
[1] 12 25  3  2  0
[1] 14 20  3  1  1
[1] 16 15  4  1  0
[1] 18 10  4  0  1
[1] 20  5  5  0  0
[1] 22  0  5 -1  1


meaning that a’=11 does not produce a viable solution.

## Le Monde sans puzzle #933

Posted in Books, Kids, Statistics, University life with tags , , , , , on October 17, 2015 by xi'an

While Le Monde mathematical puzzle is purely geometric this week

If twelve points in a plane are such that, for any 5-uplet of those, at least 4 are on the same circle, and if M is the largest number of those points on the same circle, what is the minimal value of M?

and not straightforward to solve with an R code, there are several entries of interest in the Sciences and Medicine leaflet. One about capture-mark-recapture: making fun of a PLOS One paper on a capture-recapture study about the movements of bed bugs in New Jersey apartments. Another one on the resolution by Terry Tao of Erdös’ discrepancy conjecture. Which states that. for any (deterministic) sequence f:N{1,+1} taking values in {1,+1}, the discrepancy of f is infinite, when the discrepancy is defined as

$\sup_{n,d} \left|\sum_{j=1}^n f(jd)\right|$

The entry in Le Monde tells the story of the derivation of the result and in particular the role of the Polymath5 project launched by Tao. It is interesting it is such a hard problem when considering the equivalent for a random sequence, which is more or less the gambler’s ruin result of Huygens. And a third entry on the explosion of the predatory journals, which publish essentially every submission in open access provided the authors accept to pay “charges”. And borrow titles and formats from existing reviews to a point where they can fool authors…

## Le Monde puzzle [#932]

Posted in Books, Kids, Statistics, University life with tags , , , , on October 15, 2015 by xi'an

A 12×8 grid contains the first 96 integers, as in R matrix(1:96,ncol=12). If one picks 24 of those integers including 3 for each row and 2 for each column, what are the extreme values of the sum of the selected integers?

I obviously rephrased quite strongly the question (and possibly changed it!). Before rushing to the R simulation of a random collection of 24 such integers, I pondered how this sum could vary among random samples since there were the same terms in all samples. More clearly, using the 10×10 grid instead as a basis for reasoning, picking e.g. 20 integers with 2 per row and 2 per colum for all rows and columns, we end up with 2 copies of every integer between 0 and 9 and 2 copies of every decimal between 0 and 90. Random simulation confirms this reasoning:

grid=matrix(1:96,ncol=12)
#pick a subset at random
coleft=sample(rep(1:12,2))
sub7=grid[1,coleft[1:3]]
coleft=coleft[-(1:3)]
for (i in 2:8){
sub7=c(sub7,grid[i,coleft[1:3]])
coleft=coleft[-(1:3)]}
resl=sum(sub7)


since repeated call to the above keeps returning the same value, 1164, which is also

> sum(3*(0:7))*12+2*sum(1:12)
[1] 1164


## Le Monde on the “dangers” of mathematics

Posted in Books, Statistics, Travel, University life with tags , , , , on October 12, 2015 by xi'an

“La responsabilité des mathématiciens semble engagée.”

This post is presumably aiming at a very small (French speaking) audience, but Le Monde published a central Science leaflet this week on the dangers of using uncontrolled mathematical modelling. Resulting in a mismatch of platitudes and absurdities. Blaming mathematicians for about every misappropriate use of mathematics and even more statistics, from the lack of reproducibility in published psychology studies and the poor predictions of flu epidemics by Google to the sub-prime crisis and the prosecutor fallacy. Quoting judicial miscarriages like the case of Lucy de Berk when the statistical arguments were administrated by a psychologist, while a statistician, Richard Gill, was instrumental in reopening the case by demonstrating those arguments were wrong. Objecting to the use of logistic regression for profiling inmates on the probability of recidivism. &tc., &tc… The only item of interest in this really poor article is the announcement of a semester workshop at the Isaac Newton Institute on the use of mathematics in criminal sciences. Which after verification is a workshop on probability and statistics in forensic sciences. With Richard Gill as one of the organisers.

## Le Monde puzzle [#930]

Posted in Books, Kids, Statistics, University life with tags , , , on October 9, 2015 by xi'an

On a linear board of length 17, Alice and Bob set alternatively red and blue tokens. Two tokens of the same colour cannot sit next to one another. Devise a winning strategy for the first player.

In the ‘Og tradition, this calls for a recurrent R code:

game=function(n=17,col=1,tak=rep(0,n)){
frei=rew=0*tak
# stopping rule
if (sum(tak==col)==0){
frei=(tak==0)}else{
for (i in (1:n)[tak!=-col])
frei[i]=(min(abs((1:n)[tak==col]-i))>1)}
# left positions
if (sum(frei)>0){
for (i in (1:n)[frei==1]){
prop=tak;prop[i]=col
rew[i]=1-game(n=n,col=-col,tak=prop)}}
# outcome of best choice
return(max(rew))}


While I did not run the rudimentary recursive function for n=17, I got a zero return from n=2 till n=12, meaning that the starting player is always going to lose if the other player plays optimally.

## Le Monde puzzle [#929]

Posted in Books, Kids, R with tags , on September 29, 2015 by xi'an

A combinatorics Le Monde mathematical puzzle:

In the set {1,…,12}, numbers adjacent to i are called friends of i. How many distinct subsets of size 5 can be chosen under the constraint that each number in the subset has at least a friend with him?

In a brute force approach, I tried a quintuple loop to check all possible cases:

case=0
for (a in 1:(12-4))
for (b in (a+1):(12-3))
for (c in (b+1):(12-2))
for (d in (c+1):(12-1))
for (e in (d+1):12)
case=case+((b-a<2)&(min(c-b,d-c)<2)
&(min(d-c,e-d)<2)&(e-d<2))


which returns 64 possible cases. Note that the second and last loop are useless since b=a+1 and e=d+1, necessarily. And c is either (b+1) or (d-1), which means 2 choices for c, except when e=a+4. This all adds up to

$8 + 2\sum_{a=1}^7\sum_{e=a+5}^{12} = 8+2.7.8-2.7.8/2=8.8=64$

A related R question: is there a generic way of programming a sequence of embedded loops like the one above without listing all of the loops one by one?