Inference-What are You Thinking?


Number Clues

A certain number theorist has recently disappeared. His safe may contain papers that would lead police to his whereabouts. The trouble is that his safe will self-destruct if it is forced open. So we must infer the combination.

He has left a few hints. They involve pairs of numbers. Each pair, p and q, has a product (p × q), a greatest common divisor [gcd(p,q)], and a least common multiple [lcm(p,q)].

Consider, for example, p = 10 and q = 25. The greatest common divisor gcd(p,q) = 5, because both 10 and 25 are divisible by 5, but not by any number greater than 5. (“Divisible by” always implies a zero remainder.) The least common multiple lcm(p,q) = 50, because 50 is divisible by 10 and by 25, but no positive number less than 50 is divisible by both 10 and 25. So the greatest common divisor has all prime factors in common to p and q, in this case 5 alone. The least common multiple has the prime factors contained by either, in this case 2, 5, and 5.

The number theorist has left hints obeying the following rules:

  1. These hints concern pairs of positive whole numbers p and q. For every pair, p q.

  2. Each of p and q has two digits (i.e., between 10 and 99 inclusive).

Warm-Up

Suppose I tell you that q = 18, p is unknown, but gcd(p,q) = 6 and lcm(p,q) = 36. What is p?

Solution to Warm-Up

The factors of 36 are 2, 2, 3, and 3. The factors of 18 are 2, 3, and 3. The factors of 6 are 2, 3. So, we know that p has at least 2 and 3, because gcd(p,q) = 6 so 6 must divide p. Further, since lcm(p,q) = 36, either p or q has to have two 2s. Because q doesn’t, p must, so p has factors 2, 2, and 3. Therefore p = 12.

Here are the first three hints, given stipulations (i) and (ii) above.

  1. For the first p, q pair, lcm(p,q) = 60, p × q = 240. What are p and q?

  2. The product of p and q is 140. gcd(p,q) = 2. What are p and q?

  3. There is a pair p and q whose lcm(p,q) = 35. What are p and q?

The number theorist left another hint that the police have just decrypted: “If you’ve gotten this far, then you are doing well. Here now is one last hint.”

  1. The sequence of numbers that opens the safe is a sequence of five numbers from the hints. The sequence enjoys the following property: The greatest common divisors between neighbors of the sequence strictly increase as one proceeds from left to right in the sequence, but all greatest common divisors are single digits. What is the sequence that opens the safe?




Puzzles for Programmers and Pros
Puzzles for Programmers and Pros
ISBN: 0470121688
EAN: 2147483647
Year: 2007
Pages: 81
Authors: Dennis Shasha

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net