## Le Monde puzzle [#905]

Posted in Books, Kids, R, Statistics, University life with tags , , , on April 1, 2015 by xi'an

A recursive programming  Le Monde mathematical puzzle:

Given n tokens with 10≤n≤25, Alice and Bob play the following game: the first player draws an integer1≤m≤6 at random. This player can then take 1≤r≤min(2m,n) tokens. The next player is then free to take 1≤s≤min(2r,n-r) tokens. The player taking the last tokens is the winner. There is a winning strategy for Alice if she starts with m=3 and if Bob starts with m=2. Deduce the value of n.

Although I first wrote a brute force version of the following code, a moderate amount of thinking leads to conclude that the person given n remaining token and an adversary choice of m tokens such that 2m≥n always win by taking the n remaining tokens:

optim=function(n,m){

outcome=(n<2*m+1)
if (n>2*m){
for (i in 1:(2*m))
outcome=max(outcome,1-optim(n-i,i))
}
return(outcome)
}


eliminating solutions which dividers are not solutions themselves:

sol=lowa=plura[plura&lt;100]
for (i in 3:6){
sli=plura[(plura&gt;10^(i-1))&amp;(plura&lt;10^i)]
ace=sli-10^(i-1)*(sli%/%10^(i-1))
lowa=sli[apply(outer(ace,lowa,FUN=&quot;==&quot;),
1,max)==1]
lowa=sort(unique(lowa))
sol=c(sol,lowa)}


> subs=rep(0,16)
> for (n in 10:25) subs[n-9]=optim(n,3)
> for (n in 10:25) if (subs[n-9]==1) subs[n-9]=1-optim(n,2)
> subs
[1] 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
> (10:25)[subs==1]
[1] 18


Ergo, the number of tokens is 18!

## Le Monde puzzle [#904.5]

Posted in Books, Kids, R, Statistics, University life with tags , , , on March 25, 2015 by xi'an

Find all plural integers, namely positive integers such that (a) none of their digits is zero and (b) removing their leftmost digit produces a dividing plural integer (with the convention that one digit integers are all plural).

a slight modification in the R code allows for a faster exploration, based on the fact that solutions add one extra digit to solutions with one less digit:

First, I found this function on Stack Overflow to turn an integer into its digits:

pluri=plura=NULL
#solutions with two digits
for (i in 11:99){

dive=rev(digin(i)[-1])
if (min(dive)&gt;0){
dive=sum(dive*10^(0:(length(dive)-1)))
if (i==((i%/%dive)*dive))
pluri=c(pluri,i)}}

for (n in 2:6){ #number of digits
plura=c(plura,pluri)
pluro=NULL
for (j in pluri){

for (k in (1:9)*10^n){
x=k+j
if (x==(x%/%j)*j)
pluro=c(pluro,x)}
}
pluri=pluro}


which leads to the same output

&gt; sort(plura)
[1] 11 12 15 21 22 24 25 31 32 33 35 36
[13] 41 42 44 45 48 51 52 55 61 62 63 64
[25] 65 66 71 72 75 77 81 82 84 85 88 91
[37] 92 93 95 96 99 125 225 312 315 325 375 425
[49] 525 612 615 624 625 675 725 735 825 832 912
[61] 915 925 936 945 975 1125 2125 3125 3375 4125
[70] 5125 5625
[72] 6125 6375 7125 8125 9125 9225 9375 53125
[80] 91125 95625


## Le Monde puzzle [#904]

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

An arithmetics Le Monde mathematical puzzle:

Find all plural integers, namely positive integers such that (a) none of their digits is zero and (b) removing their leftmost digit produces a dividing plural integer (with the convention that one digit integers are all plural).

An easy arithmetic puzzle, with no real need for an R code since it is straightforward to deduce the solutions. Still, to keep up with tradition, here it is!

First, I found this function on Stack Overflow to turn an integer into its digits:

digin=function(n){
as.numeric(strsplit(as.character(n),"")[[1]])}


then I simply checked all integers up to 10⁶:

plura=NULL
for (i in 11:10^6){
dive=rev(digin(i)[-1])
if (min(dive)>0){
dive=sum(dive*10^(0:(length(dive)-1)))
if (i==((i%/%dive)*dive))
plura=c(plura,i)}}


eliminating solutions which dividers are not solutions themselves:

sol=lowa=plura[plura<100]
for (i in 3:6){
sli=plura[(plura>10^(i-1))&(plura<10^i)]
ace=sli-10^(i-1)*(sli%/%10^(i-1))
lowa=sli[apply(outer(ace,lowa,FUN="=="),
1,max)==1]
lowa=sort(unique(lowa))
sol=c(sol,lowa)}


> sol
[1] 11 12 15 21 22 24 25 31 32 33 35 36
[13] 41 42 44 45 48 51 52 55 61 62 63 64
[25] 65 66 71 72 75 77 81 82 84 85 88 91
[37] 92 93 95 96 99 125 225 312 315 325 375 425
[49] 525 612 615 624 625 675 725 735 825 832 912
[61] 915 925 936 945 975 1125 2125 3125 3375 4125
[70] 5125 5625
[72] 6125 6375 7125 8125 9125 9225 9375 53125
[80] 91125 95625


leading to the conclusion there is no solution beyond 95625.

## Le Monde puzzle [#902]

Posted in Books, Kids, Statistics, University life with tags , , , , , , on March 8, 2015 by xi'an

Another arithmetics Le Monde mathematical puzzle:

From the set of the integers between 1 and 15, is it possible to partition it in such a way that the product of the terms in the first set is equal to the sum of the members of the second set? can this be generalised to an arbitrary set {1,2,..,n}? What happens if instead we only consider the odd integers in those sets?.

I used brute force by looking at random for a solution,

pb <- txtProgressBar(min = 0, max = 100, style = 3)
for (N in 5:100){
sol=FALSE
while (!sol){
k=sample(1:N,1,prob=(1:N)*(N-(1:N)))
pro=sample(1:N,k)
sol=(prod(pro)==sum((1:N)[-pro]))
}
setTxtProgressBar(pb, N)}
close(pb)


and while it took a while to run the R code, it eventually got out of the loop, meaning there was at least one solution for all n’s between 5 and 100. (It does not work for n=1,2,3,4, for obvious reasons.) For instance, when n=15, the integers in the product part are either 3,5,7, 1,7,14, or 1,9,11. Jean-Louis Fouley sent me an explanation:  when n is odd, n=2p+1, one solution is (1,p,2p), while when n is even, n=2p, one solution is (1,p-1,2p).

A side remark on the R code: thanks to a Cross Validated question by Paulo Marques, on which I thought I had commented on this blog, I learned about the progress bar function in R, setTxtProgressBar(), which makes running R code with loops much nicer!

For the second question, I just adapted the R code to exclude even integers:

while (!sol){
k=1+trunc(sample(1:N,1)/2)
pro=sample(seq(1,N,by=2),k)
cum=(1:N)[-pro]
sol=(prod(pro)==sum(cum[cum%%2==1]))
}


and found a solution for n=15, namely 1,3,15 versus 5,7,9,11,13. However, there does not seem to be a solution for all n’s: I found solutions for n=15,21,23,31,39,41,47,49,55,59,63,71,75,79,87,95…

## Le Monde puzzle [#899]

Posted in Books, Kids, Statistics, University life with tags , , , , , on February 8, 2015 by xi'an

An arithmetics Le Monde mathematical puzzle:

For which n’s are the averages of the first n squared integers integers? Among those, which ones are perfect squares?

An easy R code, for instance

n=10^3
car=as.integer(as.integer(1:n)^2)
sumcar=as.integer((cumsum(car)%/%as.integer(1:n)))
diff=as.integer(as.integer(cumsum(car))-as.integer(1:n)*sumcar)
print((1:n)[diff==00])


which produces 333 values

  [1]   1   5   7  11  13  17  19  23  25  29  31  35  37  41  43  47  49  53
[19]  55  59  61  65  67  71  73  77  79  83  85  89  91  95  97 101 103 107
[37] 109 113 115 119 121 125 127 131 133 137 139 143 145 149 151 155 157 161
[55] 163 167 169 173 175 179 181 185 187 191 193 197 199 203 205 209 211 215
[73] 217 221 223 227 229 233 235 239 241 245 247 251 253 257 259 263 265 269
[91] 271 275 277 281 283 287 289 293 295 299 301 305 307 311 313 317 319 323
[109] 325 329 331 335 337 341 343 347 349 353 355 359 361 365 367 371 373 377
[127] 379 383 385 389 391 395 397 401 403 407 409 413 415 419 421 425 427 431
[145] 433 437 439 443 445 449 451 455 457 461 463 467 469 473 475 479 481 485
[163] 487 491 493 497 499 503 505 509 511 515 517 521 523 527 529 533 535 539
[181] 541 545 547 551 553 557 559 563 565 569 571 575 577 581 583 587 589 593
[199] 595 599 601 605 607 611 613 617 619 623 625 629 631 635 637 641 643 647
[217] 649 653 655 659 661 665 667 671 673 677 679 683 685 689 691 695 697 701
[235] 703 707 709 713 715 719 721 725 727 731 733 737 739 743 745 749 751 755
[253] 757 761 763 767 769 773 775 779 781 785 787 791 793 797 799 803 805 809
[271] 811 815 817 821 823 827 829 833 835 839 841 845 847 851 853 857 859 863
[289] 865 869 871 875 877 881 883 887 889 893 895 899 901 905 907 911 913 917
[307] 919 923 925 929 931 935 937 941 943 947 949 953 955 959 961 965 967 971
[325] 973 977 979 983 985 989 991 995 997


which are made of all odd integers that are not multiple of 3. (I could have guessed the exclusion of even numbers since the numerator is always odd. Why are the triplets excluded, now?! Jean-Louis Fouley gave me the answer: the sum of squares is such that

$\frac{1+2^2+\cdots+m^2}{m}=\frac{m(m+1)(2m+1)}{6m}=\frac{(m+1)(2m+1)}{6}$

and hence m must be odd and 2m+1 a multiple of 3, which excludes multiples of 3.)

The second part is as simple:

sole=sumcar[(1:n)[diff==0]]
scar=as.integer(as.integer(sqrt(sole))^2)-sole
sum(scar==0)


with the final result

> sum(scar==0)
[1] 2
> ((1:n)[diff==0])[scar==0]
[1] 1 337


since  38025=195² is a perfect square. (I wonder if there is a plain explanation for that result!)

## Le Monde puzzle [#887quater]

Posted in Books, Kids, R, Statistics, University life with tags , , on November 28, 2014 by xi'an

And yet another resolution of this combinatorics Le Monde mathematical puzzle: that puzzle puzzled many more people than usual! This solution is by Marco F, using a travelling salesman representation and existing TSP software.

N is a golden number if the sequence {1,2,…,N} can be reordered so that the sum of any consecutive pair is a perfect square. What are the golden numbers between 1 and 25?

For instance, take n=199, you should first calculate the “friends”. Save them on a symmetric square matrix:

m1 <- matrix(Inf, nrow=199, ncol=199)
diag(m1) <- 0
for (i in 1:199) m1[i,friends[i]] <- 1


Export the distance matrix to a file (in TSPlib format):

library(TSP)
tsp <- TSP(m1)
tsp
image(tsp)
write_TSPLIB(tsp, "f199.TSPLIB")


And use a solver to obtain the results. The best solver for TSP is Concorde. There are online versions where you can submit jobs:

0 2 1000000
2 96 1000000
96 191 1000000
191 168 1000000
...


The numbers of the solution are in the second column (2, 96, 191, 168…). And they are 0-indexed, so you have to add 1 to them:

3  97 192 169 155 101 188 136 120  49 176 148 108 181 143 113 112  84  37  63 18  31  33  88168 193  96 160 129 127 162 199  90  79 177 147  78  22 122 167 194 130  39 157  99 190 13491 198  58  23  41 128 196  60  21 100 189 172 152 73 183 106  38 131 125 164 197  59 110 146178 111 145  80  20  61 135 121  75  6  94 195166 123 133 156  69  52 144  81  40   9  72 184  12  24  57  87  82 62  19  45  76 180 109 116 173 151  74  26  95 161 163 126  43 153 17154  27 117 139  30  70  11  89 107 118 138 186103  66 159 165 124 132  93  28   8  17  32  45  44  77 179 182 142  83  86  14  50 175 114 55 141 115  29  92 104 185  71  10  15  34   27  42 154 170 191  98 158  67 102 187 137 119 25  56 65  35  46 150 174  51  13  68  53  47 149 140  85  36  64 105  16  48


## Le Monde puzzle [#887ter]

Posted in Books, Kids, Statistics, University life with tags , , , , on November 27, 2014 by xi'an

Here is a graph solution to the recent combinatorics Le Monde mathematical puzzle, proposed by John Shonder:

N is a golden number if the sequence {1,2,…,N} can be reordered so that the sum of any consecutive pair is a perfect square. What are the golden numbers between 1 and 25?

Consider an undirected graph GN with N vertices labelled 1 through N. Draw an edge between vertices i and j if and only if i + j is a perfect square. Then N is golden if GN contains a Hamiltonian path — that is, if there is a connected path that visits all of the vertices exactly once.I wrote a program (using Mathematica, though I’m sure there must be an R library with similar functionality) that builds up G sequentially and checks at each step whether the graph contains a Hamiltonian path. The program starts with G1 — a single vertex and no edges. Then it adds vertex 2. G2 has no edges, so 2 isn’t golden.

Adding vertex 3, there is an edge between 1 and 3. But vertex 2 is unconnected, so we’re still not golden.

The results are identical to yours, but I imagine my program runs a bit faster. Mathematica contains a built-in function to test for the existence of a Hamiltonian path.

Some of the graphs are interesting. I include representations of G25 and G36. Note that G36 contains a Hamiltonian cycle, so you could arrange the integers 1 … 36 on a roulette wheel such that each consecutive pair adds to a perfect square.

A somewhat similar problem:

Call N a “leaden” number if the sequence {1,2, …, N} can be reordered so that the sum of any consecutive pair is a prime number. What are the leaden numbers between 1 and 100? What about an arrangement such that the absolute value of the difference between any two consecutive numbers is prime?

[The determination of the leaden numbers was discussed in a previous Le Monde puzzle post.]