Le Monde puzzle [#1021]

Posted in Books, Kids, R with tags , , , , , on September 17, 2017 by xi'an

A puzzling Le Monde mathematical puzzle for which I could find no answer in the allotted time!:

A most democratic electoral system allows every voter to have at least one representative by having each of the N voters picking exactly m candidates among the M running candidates and setting the size n of the representative council towards this goal, prior to the votes. If there are M=25 candidates, m=10 choices made by the voters, and n=10 representatives, what is the maximal possible value of N? And if N=55,555 and M=33, what is the minimum value of n for which m=n is always possible?

I tried a brute force approach by simulating votes from N voters at random and attempting to find the minimal number of councillors for this vote, which only provides an upper bound of the minimum [for one vote], and a lower bound in the end [over all votes]. Something like

for (i in 1:N) votz[i,]=sample(1:M,n)
#exploration by majority
remz=1:N;conz=NULL
while (length(remz)>0){
seatz=order(-hist(votz[remz,],
breaks=(0:M)+0.5,plot=FALSE)\$density)[1]
conz=c(conz,seatz);nuremz=NULL
for (v in remz)
if (!(seatz%in%votz[v,])) nuremz=c(nuremz,v)
remz=nuremz}
solz=length(conz)
#exploration at random
kandz=matrix(0,N,M)
for (i in 1:N) kandz[i,votz[i,]]=1
for (t in 1:1e3){
#random choice of councillors
zz=sample(c(0,1),M,rep=TRUE)
while (min(kandz%*%zz)!=1)
zz=sample(c(0,1),M,rep=TRUE)
solz=min(solz,sum(zz))
#random choice of remaining councillor per voter
remz=1:N;conz=NULL
while (length(remz)>0){
seatz=sample(votz[remz[1],],1)
conz=c(conz,seatz);nuremz=NULL
for (i in remz)
if (!(seatz%in%votz[i,])) nuremz=c(nuremz,i)
remz=nuremz}
solz=min(solz,length(conz))}
maxz=max(solz,maxz)}


which leads to a value near N=4050 for the first question, with 0% confidence… Obviously, the problem can be rephrased as a binary integer linear programming problem of the form

$n= \max_A \min_{c;\,\min Ac=1}\mathbf{1}^\text{T}c$

where A is the NxM matrix of votes and c is the vector of selected councillors. But I do not see a quick way to fix it!

Le Monde puzzle [#1020]

Posted in Books, Kids, R with tags , , , on September 15, 2017 by xi'an

A collection of liars in this Le Monde mathematical puzzle:

1. A circle of 16 liars and truth-tellers is such that everyone states that their immediate neighbours are both liars. How many liars can there be?
2. A circle of 12 liars and truth-tellers is such that everyone state that their immediate neighbours are one liar plus one truth-teller. How many liars can there be?
3.  A circle of 8 liars and truth-tellers is such that four state that their immediate neighbours are one liar plus one truth-teller and four state that their immediate neighbours are both liars . How many liars can there be?

These questions can easily be solved by brute force simulation. For the first setting, using 1 to code truth-tellers and -1 liars, I simulate acceptable configurations as

tabz=rep(0,16)
tabz[1]=1 #at least one
tabz[2]=tabz[16]=-1
for (i in 3:15){
if (tabz[i-1]==1){
tabz[i]=-1}else{
if (tabz[i+1]==-1){
tabz[i]=1}else{
if (tabz[i+1]==1){
tabz[i]=-1}else{
if (tabz[i-2]==-1){
tabz[i]=1}else{
tabz[i]=sample(c(-1,1),1)
}}}}}


which produces 8, 9, and 10 as possible (and obvious) values.

The second puzzle is associated with the similar R code

tabz=sample(c(-1,1),12,rep=TRUE)
rong=FALSE
while (!rong){
for (i in sample(12)){
if (tabz[i-1+12*(i==1)]*tabz[i%%12+1]==-1){
tabz[i]=1}else{
tabz[i]=sample(c(-1,1),1)}
}
rong=TRUE
for (i in (1:12)[tabz==1])
rong=rong&(tabz[i-1+12*(i==1)]*tabz[i%%12+1]==-1)
if (rong){
for (i in (1:12)[tabz==-1])
rong=rong&(tabz[i-1+12*(i==1)]*tabz[i%%12+1]!=-1)
}}


with numbers of liars (-1) either 12 (obvious) or 4.

The final puzzle is more puzzling in that figuring out the validating function (is an allocation correct?) took me a while, the ride back home plus some. I ended up with the following code that samples liars (-1) and thruth-seekers (1) at random, plus forces wrong and right answers (in 0,1,2) on these, and check for the number of answers of both types:

rong=FALSE
while (!rong){
tabz=sample(c(-1,1),8,rep=TRUE) #truth
tabz[1]=1;tabz[sample(2:8,1)]=-1
tt=(1:8)[tabz==1];lr=(1:8)[tabz==-1]
statz=rep(0,8) #stmt
statz[tt]=(tabz[tt-1+8*(tt==1)]*tabz[tt%%8+1]==-1)+
2*(tabz[tt-1+8*(tt==1)]+tabz[tt%%8+1]==-2)
statz[lr]=2*(tabz[lr-1+8*(lr==1)]*tabz[lr%%8+1]==-1)+
(tabz[lr-1+8*(lr==1)]+tabz[lr%%8+1]==-1)+
sample(c(1,2),8,rep=TRUE)[lr]*
(tabz[lr-1+8*(lr==1)]+tabz[lr%%8+1]==1)
rong=(sum(statz==1)==4)&(sum(statz==2)==4)}


with solutions 3, 4, 5 and 6.

Le Monde puzzle [#1019]

Posted in Books, Kids with tags , , , , , , on September 7, 2017 by xi'an

A gamey (and verbose) Le Monde mathematical puzzle:

A two-player game involves n+2 cards in a row, blue on one side and red on the other. Each player can pick any blue card among the n first ones and flip it plus both following ones. The game stops when no blue card is left to turn. The gain for the last player turning cards is 20-t, where t is the number of times cards were flipped, with gain t for its opponent. Both players aim at maximising their gain.

1. When n=4 and all cards are blue, can the first player win? If not, what is the best score for this player?

2. Among all 16 configurations at start, how many lead to the first player to win?

3. When n=10 and all cards are blue, how many cards are flipped an odd number of times for the winning configuration?

The first two questions can easily be processed by an R code like the following recursive function:

liplop <- function(x,n,i){
if (max(x[1:n])==0){
return(i)
}else{
sol=NULL
for (j in (1:n)[x[1:n]==1]){
y=x;y[j:(j+2)]=1-y[j:(j+2)]
sol=c(sol,20-liplop(y,n,i+1))}
return(max(sol))}}


Returning

> liplop(rep(1,6),4,0)
[1] 6


Meaning the first player cannot win, by running at most six rounds. Calling the same function for all 4⁴=16 possible configurations leads to 8 winning ones:

[1] 0 0 0 1
[1] 0 0 1 1
[1] 0 1 0 1
[1] 0 1 1 1
[1] 1 0 0 0
[1] 1 0 1 0
[1] 1 1 0 0
[1] 1 1 1 0


Solving the same problem with n=10 is not feasible with this function. (Even n=6 seems out of reach!)

Le Monde puzzle [#1018]

Posted in Books, Kids, R with tags , , , , , on August 29, 2017 by xi'an

An arithmetic Le Monde mathematical puzzle (that first did not seem to involve R programming because of the large number of digits in the quantity involved):

An integer x with less than 100 digits is such that adding the digit 1 on both sides of x produces the integer 99x.  What are the last nine digits of x? And what are the possible numbers of digits of x?

The integer x satisfies the identity

$10^{\omega+2}+10x+1=99x$

where ω is the number of digits of x. This amounts to

10….01 = 89 x,

where there are ω zeros. Working with long integers in R could bring an immediate solution, but I went for a pedestrian version, handling each digit at a time and starting from the final one which is necessarily 9:

#multiply by 9
rap=0;row=NULL
for (i in length(x):1){
prud=rap+x[i]*9
row=c(prud%%10,row)
rap=prud%/%10}
row=c(rap,row)
#multiply by 80
rep=raw=0
for (i in length(x):1){
prud=rep+x[i]*8
raw=c(prud%%10,raw)
rep=prud%/%10}
#find next digit
y=(row[1]+raw[1]+(length(x)>1))%%10


returning

7 9 7 7 5 2 8 0 9


as the (only) last digits of x. The same code can be exploited to check that the complete multiplication produces a number of the form 10….01, hence to deduce that the length of x is either 21 or 65, with solutions

[1] 1 1 2 3 5 9 5 5 0 5 6 1 7 9 7 7 5 2 8 0 9
[1] 1 1 2 3 5 9 5 5 0 5 6 1 7 9 7 7 5 2 8 0 8 9 8 8 7 6 4 0 4 4 9 4 3 8 2 0 2 2
[39] 4 7 1 9 1 0 1 1 2 3 5 9 5 5 0 5 6 1 7 9 7 7 5 2 8 0 9


The maths question behind is to figure out the powers k of 10 such that

$10^k\equiv -1 \text{ mod } (89)$

For instance, 10²≡11 mod (89) and 11¹¹≡88 mod (89) leads to the first solution ω=21. And then, since 10⁴⁴≡1 mod (89), ω=21+44=65 is another solution…

sequence riddle

Posted in Kids, R with tags , , , , , on August 10, 2017 by xi'an

The riddle this week on The Riddler was about finding the largest sequence of integers between 1 and 100 such that each integer is only used once and always followed by a multiple or a factor. A basic R code searching at random [and programmed during a massive downpour on Skye] led to a solution of 69:

although there is no certainty this is the best p… And the solutions posted the next week showed sequences with length 77! [Interestingly, both posted solutions have a sequence starting with 87. And they seem to exploit the graph of connections between integers in a much more subtle way that my random exploration of subsequences.]

Le Monde puzzle [#1707]

Posted in Books, Kids, R with tags , , , , , on July 28, 2017 by xi'an

A geometric Le Monde mathematical puzzle:

1. Given a pizza of diameter 20cm, what is the way to cut it by two perpendicular lines through a point distant 5cm from the centre towards maximising the surface of two opposite slices?
2.  Using the same point as the tip of the four slices, what is the way to make four slices with equal arcs in four cuts from the tip again towards maximising the surface of two opposite slices?

For both questions, I did not bother with the maths but went itself to a discretisation of the disk, counting the proportion of points within two opposite slices and letting the inclination of these slices move from zero to π/2. Unsurprisingly, for the first question, the answer is π/4, given that there is no difference between both surfaces at angles 0 and π/2. My R code is as follows, using (5,0) as the tip:

M=100
surfaz=function(alpha){
surfz=0
cosal=cos(alpha);sinal=sin(alpha)
X=Y=seq(-10,10,le=M)
Xcosal=(X-5)*cosal
Xsinal=(X-5)*sinal
for (i in 1:M){
norm=sqrt(X[i]^2+Y^2)
scal1=Xsinal[i]+Y*cosal
scal2=-Xcosal[i]+Y*sinal
surfz=surfz+sum((norm<=10)*(scal1*scal2>0))}
return(4*surfz/M/M/pi)}


The second puzzle can be solved by a similar code, except that the slice area between two lines has to be determined by a cross product:

surfoz=function(alpha,ploz=FALSE){
sinal=sin(alpha);cosal=cos(alpha)
X=Y=seq(-10,10,le=M)
frsterm=cosal*(10*cosal-5)+sinal*(10*sinal-5)
trdterm=cosal*(10*cosal+5)+sinal*(10*sinal+5)
surfz=0
for (i in 1:M){
norm=sqrt(X[i]^2+Y^2)
scal1=(10*(Y[i]-5)*cosal-(10*sinal-5)*X)*frsterm
scal2=-(-10*(Y[i]-5)*sinal-(10*cosal-5)*X)*frsterm
scal3=(-10*(Y[i]-5)*cosal+(10*sinal+5)*X)*trdterm
scal4=-(10*(Y[i]-5)*sinal+(10*cosal+5)*X)*trdterm
surfz=surfz+sum((norm<=10)*
((scal1>0)*(scal2>0)+
(scal3>0)*(scal4>0)))}
return(4*surfz/M/M/pi)}


a code that shows that all cuts lead to identical surfaces for bot sets of slices. A fairly surprising result!

Le Monde puzzle [#1016]

Posted in Books, Kids with tags , , , on July 16, 2017 by xi'an

An even more straightforward Le Monde mathematical puzzle that took a few minutes to code in the train to Cambridge:

1. Breaking {1,…,8} into two sets of four integrals, what is (or are) the division into two groups of equal size such that the sums of the squared terms from each are equal? Same question for the set {21,…,28}.
2.  Considering the integers from 1 to 12, how many divisions into two groups of size six satisfy the above property? Same question when the two groups are of different sizes.

The first code is

nop=TRUE
while (nop){
s=sample(1:8)
nop=(sum(s[1:4]^2)!=sum(s[5:8]^2))}


with result

1 6 4 7

while the second set leads to the unique [drifted] solution (up to symmetries)

21 24 26 27


and the divisions for the larger set {1,…,12} is unique in the equal case, and are four in the unequal case.