Sum and Product Puzzle

Last updated

The Sum and Product Puzzle, also known as the Impossible Puzzle because it seems to lack sufficient information for a solution, is a logic puzzle. It was first published in 1969 by Hans Freudenthal, [1] [2] and the name Impossible Puzzle was coined by Martin Gardner. [3] The puzzle is solvable, though not easily. There exist many similar puzzles.

Contents

Puzzle

X and Y are two whole numbers greater than 1, and Y > X. Their sum is not greater than 100. S and P are two mathematicians (and consequently perfect logicians); S knows the sum X + Y and P knows the product X × Y. Both S and P know all the information in this paragraph.

In the following conversation, both participants are always telling the truth:

What are X and Y?

Explanation

The problem is rather easily solved once the concepts and perspectives are made clear. There are three parties involved, S, P, and O. S knows the sum X+Y, P knows the product X·Y, and the observer O knows nothing more than the original problem statement. All three parties keep the same information but interpret it differently. Then it becomes a game of information.

Let us call the split of a number A into two terms A=B+C a 2-split. There is no need for any advanced knowledge like Goldbach's conjecture or the fact that for the product B·C of such a 2-split to be unique (i.e. there are no other two numbers that also when multiplied yield the same result). But with Goldbach's conjecture, along with the fact that P would immediately know X and Y if their product were a semiprime, it can be deduced that the sum x+y cannot be even, since every even number can be written as the sum of two prime numbers. The product of those two numbers would then be a semiprime.

The following steps give the solution:

  1. S (Sue), P (Pete), and O (Otto) make tables of all products that can be formed from 2-splits of the sums in the range, i.e. from 5 to 100 (X > 1 and Y > X requires us to start at 5). For example, 11 can be 2-split into 2+9, 3+8, 4+7, and 5+6. The respective products are 18, 24, 28, and 30 and the players put a tick mark beside each of these products in their tables (Table 1). When they are done, some numbers have no tick marks, some have one, and some have more than one.
  2. Sue now looks at her sum and all its 2-splits. She sees that all 2-splits have products that are not unique, i.e. there exists a different factorization that is a 2-split of some other possible sum. She sees this from the table in Step 1 where all her products have more than one tick mark. She realises that because of this fact, Pete will be unable to uniquely determine the factors X and Y by looking at the product (that would have required at least one of the candidate products to have only one tick mark). Thus she exclaims "P cannot know X and Y". When Pete and Otto hear this, they get the information that none of the products associated with Sue's sum are unique. By going through the possible sums, one by one, Sue, Pete, and Otto can now, each one by themselves, make a list of all eligible sums (Table 2). The table contains those sums all of whose 2-splits have products that are non-unique, i.e. have more than one tick mark in Table 1. Sue, Pete, and Otto have created the table of candidate sums (Sue of course already knows her sum but needs to trace Pete's thinking).
  3. Considering the new information in Table 2, Pete once again looks at his product. The sums of all of the possible 2-splits of his product except one have disappeared from Table 2 compared to all numbers between 5 and 100 that were considered as sums from the outset. The only one that remains must be the sum of the two hidden numbers X and Y whose product X·Y he knows. From the sum and the product, it is easy to know the individual numbers and thus he tells Sue that "Now I know X and Y". Pete is now done and exits the game.
  4. Sue and Otto recalculate Table 1, this time only counting products of 2-splits from sums that are in Table 2 instead of from all numbers in the range 5 to 100 as in the original Table 1. This updated table is called Table 1B. Sue looks at all the products of the 2-splits of her sum and finds that only one of them appears exactly once in Table 1B. This must then be the product Pete has, and she can infer the two numbers from their sum and product as easily as Pete did. Thus, she tells Otto (Pete is already gone) that "Now I also know X and Y". Sue is now also done and exits the game, only Otto remains.
  5. From the information in Step 4, Otto scans all sums in Table 2 in search for one of which only a single 2-split has a single tick mark in Table 1B. The desired one can only have one tick mark, or Sue would not have been able to know X and Y with certainty. Finally, Otto arrives at the desired sum which also happens to be the only one with these properties, making the original problem solvable with a unique solution. Otto's task is now done as well.

Solution

The solution has X and Y as 4 and 13, with P initially knowing the product is 52 and S knowing the sum is 17.

Initially P does not know the solution, since

52 = 4 × 13 = 2 × 26

and S knows that P does not know the solution since all the possible sums to 17 within the constraints produce similarly ambiguous products. However once P knows that S believes there are multiple possible solutions given the product, P can rule out 2 x 26, as in that case the sum is 28. If S had been told 28, she couldn't state with certainty that P didn't know the values, as a possible pair would be 5 and 23, and if P had been told the total of 5 x 23, then those two numbers are the only possible solution. So P now knows the numbers are 4 and 13 and tells S that he knows the numbers. From this, S now knows that of the possible pairs based on the sum (viz. 2+15, 3+14, 4+13, 5+12, 6+11, 7+10, 8+9) only one has a product that would allow P to deduce the answer, that being 4 + 13. The reader can then deduce the only possible solution based on the fact that S was able to determine it. Note that for instance, if S had been told 97 (48 + 49) and P was told 2352 (48 * 49), P would be able to deduce the only possible solution, but S would not, as 44 & 53 would still be a logically possible alternative.

Other solutions

The problem can be generalized. [2] The bound X + Y ≤ 100 is chosen rather deliberately. If the limit of X + Y is altered, the number of solutions may change. For X + Y < 62, there is no solution. This might seem counter-intuitive at first since the solution X = 4, Y = 13 fits within the boundary. But by the exclusion of products with factors that sum to numbers between these boundaries, there are no longer multiple ways of factoring all non-solutions, leading to the information yielding no solution at all to the problem. For example, if X = 2, Y = 62, X + Y = 64, X·Y=124 is not considered, then there remains only one product of 124, viz. 4·31, yielding a sum of 35. Then 35 is eliminated when S declares that P cannot know the factors of the product, which it would not have been if the sum of 64 was allowed.

On the other hand, when the limit is X + Y ≤ 1685 or higher, there appears a second solution X = 4, Y = 61. Thus, from then on, the problem is not solvable in the sense that there is no longer a unique solution. Similarly, if X + Y ≤ 1970 or higher a third solution appears (X = 16, Y = 73). All of these three solutions contain one prime number. The first solution with no prime number is the fourth which appears at X + Y ≤ 2522 or higher with values X = 16 = 2·2·2·2 and Y = 111 = 3·37.

If the condition Y > X > 1 is changed to Y > X > 2, there is a unique solution for thresholds X + Y ≤ t for 124 < t < 5045, after which there are multiple solutions. At 124 and below, there are no solutions. It is not surprising that the threshold for a solution has gone up. Intuitively, the problem space got "sparser" when the prime number 2 is no longer available as the factor X, creating fewer possible products X·Y from a given sum A. When there are many solutions, that is, for higher t, some solutions coincide with those for the original problem with Y > X > 1, for example X = 16, Y = 163.

If the condition X + Y ≤ t for some threshold t is exchanged for X·Y ≤ u instead, the problem changes appearance. It becomes easier to solve with less calculations required. A reasonable value for u could be u = t·t/4 for the corresponding t based on the largest product of two factors whose sum are t being (t/2)·(t/2). Now the problem has a unique solution in the ranges 47 < t < 60, 71 < t < 80, 107 < t < 128, and 131 < t < 144 and no solution below that threshold. The results for the alternative formulation do not coincide with those of the original formulation, neither in number of solutions, nor in content.

See also

Related Research Articles

<span class="mw-page-title-main">Chinese remainder theorem</span> Theorem for solving simultaneous congruences

In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.

In mathematics, a polynomial is a mathematical expression consisting of indeterminates and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example of a polynomial of a single indeterminate x is x2 − 4x + 7. An example with three indeterminates is x3 + 2xyz2 − yz + 1.

<span class="mw-page-title-main">Prime number</span> Number divisible only by 1 or itself

A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order.

The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset of integers and a target-sum , and the question is to decide whether any subset of the integers sum to precisely . The problem is known to be NP-hard. Moreover, some restricted variants of it are NP-complete too, for example:

A multiplication algorithm is an algorithm to multiply two numbers. Depending on the size of the numbers, different algorithms are more efficient than others. Efficient multiplication algorithms have existed since the advent of the decimal numeral system.

<span class="mw-page-title-main">Factorization</span> (Mathematical) decomposition into a product

In mathematics, factorization (or factorisation, see English spelling differences) or factoring consists of writing a number or another mathematical object as a product of several factors, usually smaller or simpler objects of the same kind. For example, 3 × 5 is an integer factorization of 15, and (x – 2)(x + 2) is a polynomial factorization of x2 – 4.

Hilbert's tenth problem is the tenth on the list of mathematical problems that the German mathematician David Hilbert posed in 1900. It is the challenge to provide a general algorithm that, for any given Diophantine equation, can decide whether the equation has a solution with all unknowns taking integer values.

<span class="mw-page-title-main">Dynamic programming</span> Problem optimization method

Dynamic programming is both a mathematical optimization method and an algorithmic paradigm. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.

<span class="mw-page-title-main">Wave function</span> Mathematical description of the quantum state of a system

In quantum physics, a wave function is a mathematical description of the quantum state of an isolated quantum system. The most common symbols for a wave function are the Greek letters ψ and Ψ. Wave functions are complex-valued. For example, a wave function might assign a complex number to each point in a region of space. The Born rule provides the means to turn these complex probability amplitudes into actual probabilities. In one common form, it says that the squared modulus of a wave function that depends upon position is the probability density of measuring a particle as being at a given place. The integral of a wavefunction's squared modulus over all the system's degrees of freedom must be equal to 1, a condition called normalization. Since the wave function is complex-valued, only its relative phase and relative magnitude can be measured; its value does not, in isolation, tell anything about the magnitudes or directions of measurable observables. One has to apply quantum operators, whose eigenvalues correspond to sets of possible results of measurements, to the wave function ψ and calculate the statistical distributions for measurable quantities.

<span class="mw-page-title-main">Egyptian fraction</span> Finite sum of distinct unit fractions

An Egyptian fraction is a finite sum of distinct unit fractions, such as

Verbal arithmetic, also known as alphametics, cryptarithmetic, cryptarithm or word addition, is a type of mathematical game consisting of a mathematical equation among unknown numbers, whose digits are represented by letters of the alphabet. The goal is to identify the value of each letter. The name can be extended to puzzles that use non-alphabetic symbols instead of letters.

In computational complexity theory, the 3SUM problem asks if a given set of real numbers contains three elements that sum to zero. A generalized version, k-SUM, asks the same question on k elements, rather than simply 3. 3SUM can be easily solved in time, and matching lower bounds are known in some specialized models of computation.

<span class="mw-page-title-main">Kakuro</span> Type of logic puzzle

Kakuro or Kakkuro or Kakoro is a kind of logic puzzle that is often referred to as a mathematical transliteration of the crossword. Kakuro puzzles are regular features in many math-and-logic puzzle publications across the world. In 1966, Canadian Jacob E. Funk, an employee of Dell Magazines, came up with the original English name Cross Sums and other names such as Cross Addition have also been used, but the Japanese name Kakuro, abbreviation of Japanese kasan kurosu, seems to have gained general acceptance and the puzzles appear to be titled this way now in most publications. The popularity of Kakuro in Japan is immense, second only to Sudoku among Nikoli's famed logic-puzzle offerings.

<span class="mw-page-title-main">Znám's problem</span> On divisibility among sets of integers

In number theory, Znám's problem asks which sets of integers have the property that each integer in the set is a proper divisor of the product of the other integers in the set, plus 1. Znám's problem is named after the Slovak mathematician Štefan Znám, who suggested it in 1972, although other mathematicians had considered similar problems around the same time.

<span class="mw-page-title-main">Secretary problem</span> Mathematical problem involving optimal stopping theory

The secretary problem demonstrates a scenario involving optimal stopping theory that is studied extensively in the fields of applied probability, statistics, and decision theory. It is also known as the marriage problem, the sultan's dowry problem, the fussy suitor problem, the googol game, and the best choice problem. Its solution is also known as the 37% rule.

<span class="mw-page-title-main">Mathematics of Sudoku</span> Mathematical investigation of Sudoku

Mathematics can be used to study Sudoku puzzles to answer questions such as "How many filled Sudoku grids are there?", "What is the minimal number of clues in a valid puzzle?" and "In what ways can Sudoku grids be symmetric?" through the use of combinatorics and group theory.

A Survo puzzle is a kind of logic puzzle presented and studied by Seppo Mustonen. The name of the puzzle is associated with Mustonen's Survo system, which is a general environment for statistical computing and related areas.

<span class="mw-page-title-main">Hilbert space</span> Type of topological vector space

In mathematics, Hilbert spaces allow the methods of linear algebra and calculus to be generalized from (finite-dimensional) Euclidean vector spaces to spaces that may be infinite-dimensional. Hilbert spaces arise naturally and frequently in mathematics and physics, typically as function spaces. Formally, a Hilbert space is a vector space equipped with an inner product that induces a distance function for which the space is a complete metric space.

"Cheryl's Birthday" is a logic puzzle, specifically a knowledge puzzle. The objective is to determine the birthday of a girl named Cheryl using a handful of clues given to her friends Albert and Bernard. Written by Dr Joseph Yeo Boon Wooi of Singapore's National Institute of Education, the question was posed as part of the Singapore and Asian Schools Math Olympiad (SASMO) in 2015, and was first posted online by Singapore television presenter Kenneth Kong. It went viral in a matter of days and also hit national television in all major cities globally. Henry Ong, the Founder of SASMO was interviewed by Singapore's Mediacorp program FIVE hosts Chua En Lai and Yasmine Yonkers.

<span class="mw-page-title-main">Rope-burning puzzle</span> Mathematical puzzle

In recreational mathematics, rope-burning puzzles are a class of mathematical puzzle in which one is given lengths of rope, fuse cord, or shoelace that each burn for a given amount of time, and matches to set them on fire, and must use them to measure a non-unit amount of time. The fusible numbers are defined as the amounts of time that can be measured in this way.

References

  1. ↑ Hans Freudenthal, Nieuw Archief Voor Wiskunde, Series 3, Volume 17, 1969, page 152
  2. 1 2 Born, A.; Hurkens, C. A. J.; Woeginger, G. J. (2006). "The Freudenthal problem and its ramifications (Part I)" (PDF). Bulletin of the European Association for Theoretical Computer Science, EATCS. 90: 175–191.
  3. ↑ Gardner, Martin (December 1979), "Mathematical Games: A Pride of Problems, Including One That Is Virtually Impossible", Scientific American , 241: 22–30, doi:10.1038/scientificamerican0979-22 .
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.