Archive for prime.factor

Le Monde puzzle [#857]

Posted in Books, Kids, R with tags , , , , , , , on March 22, 2014 by xi'an

A rather bland case of Le Monde mathematical puzzle :

Two positive integers x and y are turned into s=x+y and p=xy. If Sarah and Primrose are given S and P, respectively, how can the following dialogue happen?

  • I am sure you cannot find my number
  • Now you told me that, I can, it is 46.

and what are the values of x and y?

In the original version, it was unclear whether or not each person knew she had the sum or the product. Anyway, the first person in the dialogue has to be Sarah, since a product p equal to a prime integer would lead Primrose to figure out x=1 and hence s=p+1. (Conversely, having observed the sum s cannot lead to deduce x and y.) This means x+y-1 is not a prime integer. Now the deduction of Primrose that the sum is 46 implies p can be decomposed only once in a product such that x+y-1 is not a prime integer. If p=45, this is the case since 45=15×3 and 45=5×9 lead to 15+3-1=17 and 5+9-1=13, while 45=45×1 leads to 45+1-1=45.  Other solutions fail, as demonstrated by the R code:

 > for (x in 1:23){
 + fact=c(1,prime.factor(x*(46-x)))
 + u=0;
 + for (i in 1:(length(fact)-1))
 + u=u+1-is.prim(prod(fact[1:i])+prod(fact[-(1:i)])-1)
 + if (u==1) print(x)}
 [1] 1

Busser and Cohen argue much more wisely in their solution that any non-prime product p other than 45 would lead to p+1 as an acceptable sum s, hence would prevent Primrose from guessing s.