Le Monde puzzle [#857]

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.

5 Responses to “Le Monde puzzle [#857]”

  1. I don’t understand. When p is not a prime, s=p+1 doesn’t have to be true. So x+y-1 could actually be prime. Why can’t x = 5 and y = 9 when Primrose has got a 45?

    • 1. Sarah observed x+y. She deduced from s = x+y-1 (= 45) not being a prime that Primrose could not infer (x,y) from x*y=p, since the only case when Primrose can deduce the pair from the product is when the product p is a prime number (or p=1). After solving the puzzle we know Sarah is correct since she observed s=46 and Primrose observed 45 = 5*9 = 15*3 = 45*1.
      2. Now, Primrose knows that the decomposition of 45 = x*y is such that x+y-1 is not a prime number. This eliminates (5,9) since 5+9-1=13 is prime. And this eliminates (15,3) since 15+3-1=17 is prime. The only possibility is (45,1), hence Primrose infers that s=46.
      3. We know from the puzzle text that s=46, so we have to look at other possible products producing a sum of 46. However those other products p always include (p,1) as a possible decomposition, so there cannot be unicity in the derivation of (x,y). QED

      • Tkanks, I ‘ve got it now. However I think that there are certain products in your code that are not being checked. For example when x=4 and the factors are 1 2 2 2 3 7, do you check (2*2*3) * (2*7) ?
        I have tried the following code:

        library(schoolmath)

        for (x in 1:23) {
        fact = c(1, prime.factor(x * (46 – x)))
        print(fact)

        ve <- vector()
        for (i in 1:(length(fact) – 1)) {

        total = fact
        first <- combn(total, i, MARGIN=2)
        second <- apply(first, 2, function(z) total[is.na(pmatch(total, z))])

        if (is.null(dim(second)))
        second <- matrix(second, ncol = length(second))

        for (j in 1:ncol(first)) {

        u = 0
        u = u + 1 – is.prim(prod(first[, j]) + prod(second[, j]) – 1)

        if (u == 1 & !(prod(first[, j]) %in% ve)) {
        cat('x=',x," y=",46-x," first=",prod(first[, j])," second=",prod(second[, j]),"\n")}

        ve <- c(ve,prod(first[, j]),prod(second[, j]))
        }
        }
        }

      • Right: I should have considered all permutations, rather than only those following the natural ordering of the prime factors…

  2. […] article was first published on Xi'an's Og » R, and kindly contributed to […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 634 other followers