Archive for mathematical puzzle

Le Monde puzzle [#1112]

Posted in Books, Kids, R with tags , , , on October 3, 2019 by xi'an

Another low-key arithmetic problem as Le Monde current mathematical puzzle:

Find the 16 integers x¹,x²,x³,x⁴,y¹,y²,y³,y⁴,z¹,z²,z³,z⁴,w¹,w²,w³,w⁴ such that the groups x¹,y¹,z¹,w¹, &tc., are made of distinct positive integers, the sum of the x’s is 24, of the y’s 20, of the z’s 19 and of the w’s 17. Furthermore, x¹<max(y¹,z¹,w¹), x²<max(y²,z²,w²), x³<max(y³,z³,w³)=z³, and x⁴<max(y⁴,z⁴,w⁴), while x¹<x².

There are thus 4 x 3 unknowns, all bounded by either 20-3=17 or 19-3=16 for x³,y³,z³. It is then a case for brute force resolution since drawing all quadruplets by rmultinom until all conditions are satisfied

valid=function(x,y,z,w){
 (z[3]>max(y[3],w[3]))&(x[1]<x[2])&(sum(x)==24)&
 (sum(y)==20)&(sum(z)==19)&(sum(w)==17)}

returns quickly several solutions. Meaning I misread the question and missed the constraint that the four values at each step were the same up to a permutation, decreasing the number of unknowns to four, a,b,c,d (ordered). And then three because the sum of the four is 20, average of the four sums. It seems to me that the first sum of x’s being 24 and involving only a,b, and c implies that 4c is larger than 24, ie c>6, hence d>7, while a>0 and b>1, leaving only two degrees of freedom for choosing the four values, meaning that only

  1 2 7 10
1 2 8 9
1 3 7 9
1 4 7 8
2 3 7 8

are possible. Sampling at random across these possible choices and allocating the numbers at random to x,y,z, and w leads rather quickly to the solution

     [,1] [,2] [,3] [,4]
[1,]    3    7    7    7
[2,]    2    8    2    8
[3,]    7    2    8    2
[4,]    8    3    3    3

Le Monde puzzle [#1111]

Posted in R, Statistics with tags , , , , , , on September 18, 2019 by xi'an

Another low-key arithmetic problem as Le Monde current mathematical puzzle:

Notice that there are 10 numbers less than, and prime with 11, 100 less than and prime with 101, 1000 less than, and prime with 1111? What is the smallest integer N such that the cardinal of the set of M<N prime with N is 10⁴? What is the smallest multiple of 1111 using only different digits? And what is the largest?

As it is indeed a case for brute force resolution as in the following R code

library(numbers)
homanycoprim=function(n){
  many=1
  for (i in 2:(n-1)) many=many+coprime(i,n)
  return(many)}

smallest=function(){
  n=1e4
  many=homanycoprim(n)
  while (many!=1e4) many=homanycoprim(n<-n+1)
  return(n)}

which returns n=10291 as the smallest value of N.  For the other two questions, the usual integer2digit function is necessary

smalldiff=function(){
  n=1111;mul=1
  while (mul<1e6) {
    x=as.numeric(strsplit(as.character(n*mul), "")[[1]])
    while (sum(duplicated(x))!=0){
     mul=mul+1
     x=as.numeric(strsplit(as.character(n*mul), "")[[1]])}
  print(n*mul);mul=mul+1}}

leading to 241,087 as the smallest and 9,875,612,340 as the largest (with 10 digits).

Le Monde puzzle [#1110]

Posted in Books, Kids, R, Travel with tags , , , , , , , , , on September 16, 2019 by xi'an

A low-key sorting problem as Le Monde current mathematical puzzle:

If the numbers from 1 to 67 are randomly permuted and if the sorting algorithm consists in picking a number i with a position higher than its rank i and moving it at the correct i-th position, what is the maximal number of steps to sort this set of integers when the selected integer is chosen optimaly?

As the question does not clearly state what happens to the number j that stood in the i-th position, I made the assumption that the entire sequence from position i to position n is moved one position upwards (rather than having i and j exchanged). In which case my intuition was that moving the smallest moveable number was optimal, resulting in the following R code

sorite<-function(permu){ n=length(permu) p=0 while(max(abs(permu-(1:n)))>0){
    j=min(permu[permu<(1:n)])
    p=p+1
    permu=unique(c(permu[(1:n)<j],j,permu[j:n]))} 
  return(p)}

which takes at most n-1 steps to reorder the sequence. I however checked this insertion sort was indeed the case through a recursive function

resorite<-function(permu){ n=length(permu);p=0 while(max(abs(permu-(1:n)))>0){
    j=cand=permu[permu<(1:n)]
    if (length(cand)==1){
      p=p+1
      permu=unique(c(permu[(1:n)<j],j,permu[j:n]))
    }else{
      sol=n^3
      for (i in cand){
        qermu=unique(c(permu[(1:n)<i],i,permu[i:n]))
        rol=resorite(qermu)
        if (rol<sol)sol=rol}
      p=p+1+sol;break()}} 
  return(p)}

which did confirm my intuition.

Le Monde puzzle [#1109]

Posted in Kids, R with tags , , , , , on September 4, 2019 by xi'an

A digital problem as Le Monde current mathematical puzzle:

Noble numbers are such that they only involve different digits and are multiple of all their digits. What is the largest noble number?

Hmmmm…. Brute force? Since the maximal number of digits is 10, one may as well try:

k=soz=9
for (t in 1:1e3){
sol=1
while (sol<10^(k-1)){ 
 u=sample(0:8,k);i=digit2int(u) 
 if (max(i%%u[u>0])==0) soz=max(soz,sol<-i)}}

which returns 9875643120… (I made the conscious choice to exclude zero from the dividers. Which was not a choice spelled out in the original question.)

Le Monde puzzle [#1107]

Posted in Kids with tags , , , on July 8, 2019 by xi'an

A light birthday problem as Le Monde mathematical puzzle:

Each member of a group of 35 persons writes down the number of those who share the same birth-month and the number of those who share the same birth-date [with them]. It happens that these 70 numbers include all integers from 0 to 10. Show that at least two people share a birth-day. What is the maximal number of people for this property to hold?

Which needs no R code since the result follows from the remark that the number of individuals sharing a birth-month with just one other, n¹, is a multiple of 2, the number of individuals sharing a birth-month with just two others, n², a multiple of 3, and so on. Hence, if no people share a birth-day, n¹,n²,…,n¹⁰>0 and

n¹+n²+…+n¹⁰ ≥ 2+3+…+11 = 6·11-1=65

which means that it is impossible that the 10 digits n¹,…,n¹⁰ are all positive. All the way up to 65 people. As an aside, no correction of the wrong solution to puzzle #1105 was published in the subsequent editions.

Le Monde puzzle [#1105]

Posted in Kids, R with tags , , , , , , on July 8, 2019 by xi'an

Another token game as Le Monde mathematical puzzle:

Archibald and Beatrix play with a pile of n>100 tokens, sequentially picking m tokens from the pile with m being a prime number [including m=1] or a multiple of 6, the winner taking the last tokens. If Beatrix knows n and proposes to Archibald to start, what is the value of n?

Which cannot be solved in a few lines of R code:

k<-function(n)n<4||all(n%%2:ceiling(sqrt(n))!=0)||!n%%6
g=(1:3)
n=c(4,i<-4)
while(max(n)<101){
  if(k(i)) g=c(g,i) else{
  while(i%in%g)i=i+1;j=4;o=!j
  while(!o&(j<i)){ 
    o=(j%in%n)&k(i-j);j=j+1}
  if(o) g=c(g,i) else n=c(n,i)}
  i=i+1}

since it returned no unsuccessful value above 100! With 4, 8, 85, 95, and 99 as predecessors. A rather surprising outcome and a big gap that most certainly has a straightforward explanation! Or a lack of understanding from yours truly: this post appears after the solution was published in Le Monde and I am more bemused than ever since the losing numbers in the journal are given as 4, 8, 85, … 89, and 129. With the slight hiccup that 89 is a prime number…. The other argument in the solution that there can only be five such losers is well-taken since there are only five possible non-zero remainders in the division by 6.

Le Monde puzzle [#1106]

Posted in Books, Kids with tags , on July 5, 2019 by xi'an

After a translation of the original puzzle,a straight linear equation as Le Monde mathematical puzzle:

Find the ten integers x¹,x²,…. such that Ax=3x-1 where

A=\left[\begin{matrix}  0& 1& 1& 1& 0& 0& 0& 0& 0& 0\\ 1& 0& 0& 0& 1& 1& 0& 0& 0& 0\\ 1& 0& 0& 1& 0& 0& 1& 0& 0& 0\\ 1& 0& 1& 0& 1& 0& 0& 0& 0& 0\\ 0& 1& 0& 1& 0& 1& 0& 0& 0& 0\\ 0& 1& 0& 0& 1& 0& 0& 0& 1& 1\\ 0& 0& 1& 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 0& 1& 0\\ 0& 0& 0& 0& 0& 1& 0& 1& 0& 1\\ 0& 0& 0& 0& 0& 1& 0& 0& 1& 0\\  \end{matrix}\right]

Which returns 38 44 31 38 44 49 16 16 31 27 as its solution and is definitely of limited appeal…