Archive for arithmetics

Le Monde puzzle [#945]

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

A rather different Le Monde mathematical puzzle:

A two-person game is played on an nxn grid filled with zero. Each player pick an entry, which is increased by one as well as all adjacent entries. The game stops when all entries are equal. For n=3,4,5, what are the possible grids with identical values all over?

If I define an R neighbourhood function

 nighbo=function(i,n){
   neigh=i
   if (i%%n!=1) neigh=c(i-1,neigh)
   if (i%%n>0) neigh=c(i+1,neigh)
   if (i+n<=n*n) neigh=c(i+n,neigh)
   if (i-n>0) neigh=c(i-n,neigh) 
   return(neigh)}

and try a brute force filling of the grid

while ((min(grid)==0)||(length(unique(grid))>1)){
  ent=sample(1:(n*n),1,prob=1/as.vector(grid+1)^10)
  grid[nighbo(ent,n)]=grid[nighbo(ent,n)]+1}

the loop never stops. When thinking of the case n=3 [while running in the early morning], I wondered whether or not reaching an equal value on all entries was at all possible. Indeed, it is impossible to update one of the four corners without updating at least one of the neighbours, while the converse is false. Experimenting further with simulated annealing to optimise the probabilities of picking different entries in the table when n=4,5 seems to indicate this is also the case for larger values of n, in that all attempts lead to larger values of neighbours to the four corners :

outer=c(1,n,n*n,n*n-n+1)
border=sort(unique(c(2:(n-1),(n*n-n+2):(n*n-1),1+n*(1:(n-2)),n+n*(1:(n-2)))))
inner=(1:(n*n))[-c(outer,border)]
#
target=function(weit){
 grid=matrix(0,n,n)
 for (t in 1:1e4){
   cas=sample(1:3,1,prob=weit)
   if (cas==1) ent=sample(outer,1,prob=max(grid[outer])-grid[outer]+1)
   if (cas==2) ent=sample(border,1,prob=max(grid[border])-grid[border]+1)
   if (cas==3) ent=sample(inner,1,prob=max(grid[inner])-grid[inner]+1)
   ent=nighbo(ent,n)
   grid[ent]=grid[ent]+1}
 ave=c(mean(grid[outer]),mean(grid[border]),mean(grid[inner]))
 return(list(dive=max(diff(sort(ave))),ave=ave,ava=mean(grid)))
 }
#
weit=rep(1,3)
cur=target(weit)
T=100
while (cur$dive>0){
 ind=sample(1:3,1,prob=1/cur$ave)
 peit=weit
 peit[ind]=weit[ind]-(cur$ave[ind]-cur$ava)*runif(1)/(cur$ava)
 while(peit[ind]<0)
 peit[ind]=weit[ind]-(cur$ave[ind]-cur$ava)*runif(1)/(cur$ava)
 prop=target(peit)
 if (log(runif(1))*1e4/T<prop$dive-cur$dive){
 weit=peit;cur=prop}
 T=T*1.00001
 print(cur$ave)}

Le Monde puzzle [#944]

Posted in Books, Kids, pictures, Statistics, Travel, University life with tags , , , , on January 20, 2016 by xi'an

A completely dull Le Monde mathematical puzzle:

Find all integer pairs (a,b) less than 10⁶ such that a-b=2015 and ab is a perfect square.

If  I write the only condition as the function

perfect=function(c){
  return(c==trunc(sqrt(c))^2)}

and brute-force checked for all possible solutions

for (A in 2015:1e6)
 if (perfect(A*(A-2015))) print(A)
trunc(y/10)*11+(y-10*trunc(y/10))-(y==10*trunc(y/10))}

which produced

[1] 2015
[1] 2304
[1] 2420
[1] 2511
[1] 3627
[1] 4212
[1] 7056
[1] 7595
[1] 16640
[1] 33759
[1] 41616
[1] 79092
[1] 204020

as the 13 possible answers. If one checks between 10⁶ and 5 10⁶, the only remaining solution is 1,016,064. Which is the highest possible one according to Le Monde.

Le Monde puzzle [#940]

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

A rather different Le Monde mathematical puzzle with no simulation:

A student has x days to train before an exam and decides to take one day off after every nine consecutive days of training. She makes her planning and manages to fit one chapter of her textbook per day of training. She then realises she has forgotten one extra chapter, but cannot keep the pattern, even when taking one day off after 10 consecutive days of training. What is the maximum value of x?

If y denotes the number of chapters, this means that

10⌊(y-1)/9⌋+(y-1-9⌊(y-1)/9⌋)⁻ ≤ x < 11⌊y/10⌋+(y-10⌊y/10⌋)⁻

with  ⌊y/10⌋ denoting the integer part and with (z)⁻ equal to z when z>0 and to -1 when z=0. Defining both functions of y as

curv1 <- function(y){
  10*trunc((y-1)/9)+(y-1-9*trunc((y-1)/9))-(y-1==9*trunc((y-1)/9))}
curv2 <- function(y){
  trunc(y/10)*11+(y-10*trunc(y/10))-(y==10*trunc(y/10))}

I get the following graph:

lemonde941which sees both curves meeting at y=20 or x=21, which could be the answer to the puzzle. However, larger values of x see the above inequality satisfied as well. It is only after y=73 or x=80 that the above inequality is forever impossible since the lower bound is then larger than or equal to the upper bound [when removing the -1 from (z)⁻] or for y=81 or x=88 [when keeping the initial definition of (z)⁻].

Le Monde puzzle [#939bis]

Posted in Books, Kids, R with tags , , , , , , , on December 18, 2015 by xi'an

If you remember the previous post, I had two interpretations about Le Monde mathematical puzzle #639:

Find all integers with less than 11 digits that are perfect squares and can be written as a(a+6), a being an integer.

and:

Find all integers with less than 11 digits that are perfect squares and can be written as x concatenated with (x+6), x being an integer.

I got a nice email from Jamie Owen, from Newcastle, Britain, about an R resolution with a clever code, as opposed to mine!

About the second version of the puzzle, Jamie first creates the vector of concatenations:

 
x = 1:1e5
cats = x * (10^floor(log10(x+6) + 1) +1)+ 6

He then made the function perfect more… perfect:

perfect=function(b){
  a=trunc(sqrt(b))
  any((a:(a+1))^2 == b)
  }

(using a function any() I had not seen before, and then got the collection of solutions as

x = 1:1e5
x[sapply(x * (10^floor(log10(x+6) + 1) +1)+ 6,perfect)]
[1] 15 38

which runs about 25 times faster than my R solution! (And he further designed a 100 times faster version…)

Jamie also proposed an R code for solving the first version of that puzzle:

max = 1e10
squares = (1:floor(sqrt(max)))^2
# possible answers to a(a+6)
a = -1e6:1e6
# which squares have solutions
sols = intersect(a*(a + 6), squares)
# what are they?
f = function(x){
power = floor(floor(log10(x))/2)+1
a = -10^power:10^power
sols = c(x,a[a*(a+6) - x == 0])
names(sols) = c("square", "a1", "a2")
sols
}
sapply(sols,f)
## [,1]
## square 16
## a1 -8
## a2 2

which returns again 2 as the unique positive solution (equivalent to -8, if considering relative integers). A great lesson in efficient R programming, thanks Jamie!

Le Monde puzzle [#939]

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

A Le Monde mathematical puzzle about special integers:

Find all integers with less than 11 digits that are perfect squares and can be written as a(a+6), a being an integer.

Eleven digits being too much for a brute force exploration of the form `for (t in 1:1e11)`…, some preliminary  analysis is needed, but I could not figure out a reason why there is no solution apart from 2… (I checked up to 1e8!)

Since I had “guessed” the above puzzle from the solution published one week later (!), I checked the quality of my guesswork with my friend Jean-Louis Fouley, who gave me the genuine question, based on a different interpretation of a(a+6):

Find all integers with less than 11 digits that are perfect squares and can be written as x concatenated with (x+6), x being an integer.

This is more open to brute-force R exploration (with some help from stack overflow) since x only has five digits at most!

 
perfect=function(b){
  x=FALSE
  a=trunc(sqrt(b))
  for (i in a:(a+1))
    if (i^2==b) x=TRUE
  return(x)}

for (x in 1:(1e6-1))
  if (perfect(
    as.numeric(paste(c(as.numeric(strsplit(as.character(x), "")[[1]]),
    as.numeric(strsplit(as.character(x+6), "")[[1]])),collapse="")))) 
      print(x)

Which returns

[1] 15
[1] 38

and then crashes for x=99994, because

strsplit(as.character(1e+05), "") 

does not return the six digits of 1e+05 but

[[1]]
[1] "1" "e" "+" "0" "5"

instead. Except for this value of x, no other solution is found using this R code. And for x=99994, y=99994100000 is not a perfect square.

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}

Continue reading

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.

Follow

Get every new post delivered to your Inbox.

Join 1,032 other followers