Archive for brute-force solution

Le Monde puzzle [#1119]

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

A digit puzzle as Le weekly Monde current mathematical puzzle that sounds close to some earlier versions:

Perfect squares are pairs (a²,b²) with the same number of digits such that a²b² is itself a square. What is the pair providing a²b² less than 10⁶? Is there a solution with both integers enjoying ten digits?

The run of a brute force R code like

cek<-function(a,b){
  u<-trunc
  if ((n<-u(log(a^2,ba=10)))==u(log(b^2,ba=10))&
      (u(sqrt(a^2*10^(n+1)+b^2))^2==(a^2*10^(n+1)+b^2))) print(c(a,b))}

provides solutions to the first question.

[1] 2 3
[1] 4 9
[1] 12 20
[1] 15 25
[1] 18 30
[1] 49 99
[1] 126 155
[1] 154 300
[1] 159 281
[1] 177 277
[1] 228 100
[1] 252 310
[1] 285 125

with the (demonstrable) conclusion that the only pairs with an even number of digits are of the form (49…9²,9…9²), as for instance (49999²,99999²) with ten digits each.

Le Monde puzzle [#1115]

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

A two-person game as Le weekly Monde current mathematical puzzle:

Two players Amaruq and Atiqtalik are in a game with n tokens where Amaruq chooses a number 1<A<10 and then Atiqtalik chooses a different 1<B<10, and then each in her turn takes either 1, A or B tokens out of the pile.The player taking the last token wins. If n=150, who between Amaruq and Atiqtalik win if both are acting in an optimal manner? Same question for n=210.

The run of a brute force R code like

B=rep(-1,200);B[1:9]=1
for (i in 10:200){
    v=matrix(-2,9,9)
    for (b in 2:9){
       for (a in (2:9)[-b+1])
       for (d in c(1,a,b)){
        e=i-d-c(1,a,b)
        if (max(!e)){v[a,b]=max(-1,v[a,b])}else{
         if (max(e)>0) v[a,b]=max(v[a,b],min(B[e[which(e>0)]]))}}
     B[i]=max(B[i],min(v[v[,b]>-2,b]))}

always produces 1’s in B, which means the first player wins no matter… I thus found out (from the published solution) that my interpretation of the game rules were wrong. The values A and B are fixed once for all and each player only has the choice between withdrawing 1, A, and B on her turn. With the following code showing that Amaruq looses both times.

B=rep(1,210)
for(b in(2:9))
 for(a in(2:9)[-b+1])
  for(i in(2:210)){
   be=-2
   for(d in c(1,a,b)){
    if (d==i){best=1}else{
      e=i-d-c(1,a,b)
      if (max(!e)){be=max(-1,be)}else{
       if (max(e)>0)be=max(be,min(B[e[which(e>0)]]))}}}
   B[i]=be}

Le Monde puzzle [#1114]

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

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

32761 is 181² and the difference of two cubes, which ones? And 181=9²+10², the sum of two consecutive integers. Is this a general rule, i.e. the root z of a perfect square that is the difference of two cubes is always the sum of two consecutive integers squared?

The solution proceeds by a very dumb R search of cubes, leading to

34761=105³-104³

The general rule can be failed by a single counter-example. Running

sol=0;while(!sol){
  x=sample(2:1e3,1)
  y=sample(1:x,1)-1
  sol=is.sqr(z<-x^3-y^3)
  z=round(sqrt(z))
  if (sol) 
   sol=(trunc(sqrt(z/2))^2+ceiling(sqrt(z/2))^2!=z)}

which is based on the fact that, if z is the sum of two consecutive integers squared, a² and (a+1)² then

2 a²<z<2 (a+1)²

Running the R code produces

x=14, y=7

as a counter-example. (Note that, however, if the difference of cubes of two consecutive integers is a square, then this square can be written as the sum of the squares of two different integers.) Reading the solution in the following issue led me to realise I had missed the consecutive in the statement of the 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.)