Archive for arithmetics

Le Monde puzzle [#1000…1025]

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

Le Monde mathematical puzzle launched a competition to celebrate its 1000th puzzle! A fairly long-term competition as it runs over the 25 coming puzzles (and hence weeks). Starting with puzzle #1001. Here is the 1000th puzzle, not part of the competition:

Alice & Bob spend five (identical) vouchers in five different shops, each time buying the maximum number of items to get close to the voucher value. In these five shops, they buy sofas at 421 euros each, beds at 347 euros each, kitchen appliances at 289 euros each, tables at 251 euros each and bikes at 211 euros each, respectively. Once the buying frenzy is over, they realise that within a single shop, they would have spent exactly four vouchers for the same products. What is the value of a voucher?

Le Monde puzzle [#967]

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

A Sudoku-like Le Monde mathematical puzzle for a come-back (now that it competes with The Riddler!):

Does there exist a 3×3 grid with different and positive integer entries such that the sum of rows, columns, and both diagonals is a prime number? If there exist such grids, find the grid with the minimal sum?

I first downloaded the R package primes. Then I checked if by any chance a small bound on the entries was sufficient:

cale<-function(seqe){ 
 ros=apply(seqe,1,sum)
 cole=apply(seqe,2,sum)
 dyag=sum(diag(seqe))
 dayg=sum(diag(seqe[3:1,1:3]))
 return(min(is_prime(c(ros,cole,dyag,dayg)))>0)}

Running the blind experiment

for (t in 1:1e6){
  n=sample(9:1e2,1)
  if (cale(matrix(sample(n,9),3))) print(n)}

I got 10 as the minimal value of n. Trying with n=9 did not give any positive case. Running another blind experiment checking for the minimal sum led to the result

> A
 [,1] [,2] [,3]
[1,] 8 3 6
[2,] 1 5 7
[3,] 2 11 4

with sum 47.

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.