Verbal arithmetic

Last updated

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.

Contents

The equation is typically a basic operation of arithmetic, such as addition, multiplication, or division. The classic example, published in the July 1924 issue of Strand Magazine by Henry Dudeney, [1] is:

The solution to this puzzle is O = 0, M = 1, Y = 2, E = 5, N = 6, D = 7, R = 8, and S = 9.

Traditionally, each letter should represent a different digit, and (as an ordinary arithmetic notation) the leading digit of a multi-digit number must not be zero. A good puzzle should have one unique solution, and the letters should make up a phrase (as in the example above).

Verbal arithmetic can be useful as a motivation and source of exercises in the teaching of algebra.

History

Cryptarithmic puzzles are quite old and their inventor is unknown. An 1864 example in The American Agriculturist [2] disproves the popular notion that it was invented by Sam Loyd. The name "cryptarithm" was coined by puzzlist Minos (pseudonym of Simon Vatriquant) in the May 1931 issue of Sphinx, a Belgian magazine of recreational mathematics, and was translated as "cryptarithmetic" by Maurice Kraitchik in 1942. [3] In 1955, J. A. H. Hunter introduced the word "alphametic" to designate cryptarithms, such as Dudeney's, whose letters form meaningful words or phrases. [4]

Types of cryptarithms

Richard Feynman's skeletal division puzzle - each A represents the same digit, and each dot any digit not represented by A Feynman long division puzzle.svg
Richard Feynman's skeletal division puzzle – each A represents the same digit, and each dot any digit not represented by A

Types of cryptarithm include the alphametic, the digimetic, and the skeletal division.

Alphametic
A type of cryptarithm in which a set of words is written down in the form of a long addition sum or some other mathematical problem. The object is to replace the letters of the alphabet with decimal digits to make a valid arithmetic sum.
Digimetic
A cryptarithm in which digits are used to represent other digits.
Skeletal division
A long division in which most or all of the digits are replaced by symbols (usually asterisks) to form a cryptarithm.

Solving cryptarithms

Solving a cryptarithm by hand usually involves a mix of deductions and exhaustive tests of possibilities. For instance the following sequence of deductions solves Dudeney's SEND+MORE = MONEY puzzle above (columns are numbered from right to left):

  1. From column 5, M = 1 since it is the only carry-over possible from the sum of two single digit numbers in column 4.
  2. Since there is a carry in column 5, O must be less than or equal to M (from column 4). But O cannot be equal to M, so O is less than M. Therefore O = 0.
  3. Since O is 1 less than M, S is either 8 or 9 depending on whether there is a carry in column 4. But if there were a carry in column 4 (generated by the addition of column 3), N would be less than or equal to O. This is impossible since O = 0. Therefore there is no carry in column 4 and S = 9.
  4. If there were no carry in column 3 then E = N, which is impossible. Therefore there is a carry and N = E + 1.
  5. If there were no carry in column 2, then ( N + R ) mod 10 = E, and N = E + 1, so ( E + 1 + R ) mod 10 = E which means ( 1 + R ) mod 10 = 0, so R = 9. But S = 9, so there must be a carry in column 2 so R = 8.
  6. To produce a carry in column 2, we must have D + E = 10 + Y.
  7. Y is at least 2 so D + E is at least 12.
  8. The only two pairs of available numbers that sum to at least 12 are (5,7) and (6,7) so either E = 7 or D = 7.
  9. Since N = E + 1, E can't be 7 because then N = 8 = R so D = 7.
  10. E can't be 6 because then N = 7 = D so E = 5 and N = 6.
  11. D + E = 12 so Y = 2.

Another example of TO+GO=OUT (source is unknown):

  1. The sum of two biggest two-digit-numbers is 99+99=198. So O=1 and there is a carry in column 3.
  2. Since column 1 is on the right of all other columns, it is impossible for it to have a carry. Therefore 1+1=T, and T=2.
  3. As column 1 had been calculated in the last step, it is known that there isn't a carry in column 2. But, it is also known that there is a carry in column 3 in the first step. Therefore, 2+G≥10. If G is equal to 9, U would equal 1, but this is impossible as O also equals 1. So only G=8 is possible and with 2+8=10+U, U=0.

The use of modular arithmetic often helps. For example, use of mod-10 arithmetic allows the columns of an addition problem to be treated as simultaneous equations, while the use of mod-2 arithmetic allows inferences based on the parity of the variables.

In computer science, cryptarithms provide good examples to illustrate the brute force method, and algorithms that generate all permutations of m choices from n possibilities. For example, the Dudeney puzzle above can be solved by testing all assignments of eight values among the digits 0 to 9 to the eight letters S,E,N,D,M,O,R,Y, giving 1,814,400 possibilities. They also provide good examples for backtracking paradigm of algorithm design.

Other information

When generalized to arbitrary bases, the problem of determining if a cryptarithm has a solution is NP-complete. [6] (The generalization is necessary for the hardness result because in base 10, there are only 10! possible assignments of digits to letters, and these can be checked against the puzzle in linear time.)

Alphametics can be combined with other number puzzles such as Sudoku and Kakuro to create cryptic Sudoku and Kakuro.

Longest alphametics

Anton Pavlis constructed an alphametic in 1983 with 41 addends:

SO+MANY+MORE+MEN+SEEM+TO+SAY+THAT+
THEY+MAY+SOON+TRY+TO+STAY+AT+HOME+
SO+AS+TO+SEE+OR+HEAR+THE+SAME+ONE+
MAN+TRY+TO+MEET+THE+TEAM+ON+THE+
MOON+AS+HE+HAS+AT+THE+OTHER+TEN
=TESTS

(The answer is that MANYOTHERS=2764195083.) [7]

See also

Related Research Articles

<span class="mw-page-title-main">Diophantine equation</span> Polynomial equation whose integer solutions are sought

In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, for which only integer solutions are of interest. A linear Diophantine equation equates to a constant the sum of two or more monomials, each of degree one. An exponential Diophantine equation is one in which unknowns can appear in exponents.

<span class="mw-page-title-main">Euclidean algorithm</span> Algorithm for computing greatest common divisors

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements . It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.

In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers x, y, the greatest common divisor of x and y is denoted . For example, the GCD of 8 and 12 is 4, that is, gcd(8, 12) = 4.

<span class="mw-page-title-main">Geometric series</span> Sum of an (infinite) geometric progression

In mathematics, a geometric series is the sum of an infinite number of terms that have a constant ratio between successive terms. For example, the series

<span class="mw-page-title-main">Gaussian elimination</span> Algorithm for solving systems of linear equations

In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of row-wise operations performed on the corresponding matrix of coefficients. This method can also be used to compute the rank of a matrix, the determinant of a square matrix, and the inverse of an invertible matrix. The method is named after Carl Friedrich Gauss (1777–1855). To perform row reduction on a matrix, one uses a sequence of elementary row operations to modify the matrix until the lower left-hand corner of the matrix is filled with zeros, as much as possible. There are three types of elementary row operations:

<span class="mw-page-title-main">Modular arithmetic</span> Computation modulo a fixed integer

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.

<span class="mw-page-title-main">Multiplication</span> Arithmetical operation

Multiplication is one of the four elementary mathematical operations of arithmetic, with the other ones being addition, subtraction, and division. The result of a multiplication operation is called a product.

In mathematics, Pascal's triangle is a triangular array of the binomial coefficients which play a crucial role in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, although other mathematicians studied it centuries before him in Persia, India, China, Germany, and Italy.

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">Addition</span> Arithmetic operation

Addition is one of the four basic operations of arithmetic, the other three being subtraction, multiplication and division. The addition of two whole numbers results in the total amount or sum of those values combined. The example in the adjacent image shows two columns of three apples and two apples each, totaling at five apples. This observation is equivalent to the mathematical expression "3 + 2 = 5".

<span class="mw-page-title-main">Subtraction</span> One of the four basic arithmetic operations

Subtraction is one of the four arithmetic operations along with addition, multiplication and division. Subtraction is an operation that represents removal of objects from a collection. For example, in the adjacent picture, there are 5 − 2 peaches—meaning 5 peaches with 2 taken away, resulting in a total of 3 peaches. Therefore, the difference of 5 and 2 is 3; that is, 5 − 2 = 3. While primarily associated with natural numbers in arithmetic, subtraction can also represent removing or decreasing physical and abstract quantities using different kinds of objects including negative numbers, fractions, irrational numbers, vectors, decimals, functions, and matrices.

<span class="mw-page-title-main">Cube (algebra)</span> Number raised to the third power

In arithmetic and algebra, the cube of a number n is its third power, that is, the result of multiplying three instances of n together. The cube of a number or any other mathematical expression is denoted by a superscript 3, for example 23 = 8 or (x + 1)3.

<span class="mw-page-title-main">Unit fraction</span> One over a whole number

A unit fraction is a positive fraction with one as its numerator, 1/n. It is the multiplicative inverse (reciprocal) of the denominator of the fraction, which must be a positive natural number. Examples are 1/1, 1/2, 1/3, 1/4, 1/5, etc. When an object is divided into equal parts, each part is a unit fraction of the whole.

<span class="mw-page-title-main">Doomsday rule</span> Way of calculating the day of the week of a given date

The Doomsday rule, Doomsday algorithm or Doomsday method is an algorithm of determination of the day of the week for a given date. It provides a perpetual calendar because the Gregorian calendar moves in cycles of 400 years. The algorithm for mental calculation was devised by John Conway in 1973, drawing inspiration from Lewis Carroll's perpetual calendar algorithm. It takes advantage of each year having a certain day of the week upon which certain easy-to-remember dates, called the doomsdays, fall; for example, the last day of February, 4/4, 6/6, 8/8, 10/10, and 12/12 all occur on the same day of the week in any year.

In mathematics, the Kronecker product, sometimes denoted by ⊗, is an operation on two matrices of arbitrary size resulting in a block matrix. It is a specialization of the tensor product from vectors to matrices and gives the matrix of the tensor product linear map with respect to a standard choice of basis. The Kronecker product is to be distinguished from the usual matrix multiplication, which is an entirely different operation. The Kronecker product is also sometimes called matrix direct product.

Modular exponentiation is exponentiation performed over a modulus. It is useful in computer science, especially in the field of public-key cryptography, where it is used in both Diffie–Hellman key exchange and RSA public/private keys.

In mathematics, the kernel of a linear map, also known as the null space or nullspace, is the part of the domain which the map maps to the zero vector. That is, given a linear map L : V → W between two vector spaces V and W, the kernel of L is the vector space of all elements v of V such that L(v) = 0, where 0 denotes the zero vector in W, or more symbolically:

In number theory, a Dudeney number in a given number base is a natural number equal to the perfect cube of another natural number such that the digit sum of the first natural number is equal to the second. The name derives from Henry Dudeney, who noted the existence of these numbers in one of his puzzles, Root Extraction, where a professor in retirement at Colney Hatch postulates this as a general method for root extraction.

A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1)-matrix is a matrix with entries from the Boolean domain B = {0, 1}. Such a matrix can be used to represent a binary relation between a pair of finite sets. It is an important tool in combinatorial mathematics and theoretical computer science.

In numerical analysis and linear algebra, lower–upper (LU) decomposition or factorization factors a matrix as the product of a lower triangular matrix and an upper triangular matrix. The product sometimes includes a permutation matrix as well. LU decomposition can be viewed as the matrix form of Gaussian elimination. Computers usually solve square systems of linear equations using LU decomposition, and it is also a key step when inverting a matrix or computing the determinant of a matrix. The LU decomposition was introduced by the Polish astronomer Tadeusz Banachiewicz in 1938. To quote: "It appears that Gauss and Doolittle applied the method [of elimination] only to symmetric equations. More recent authors, for example, Aitken, Banachiewicz, Dwyer, and Crout … have emphasized the use of the method, or variations of it, in connection with non-symmetric problems … Banachiewicz … saw the point … that the basic problem is really one of matrix factorization, or “decomposition” as he called it." It is also sometimes referred to as LR decomposition.

References

  1. ↑ H. E. Dudeney, in Strand Magazine vol. 68 (July 1924), pp. 97 and 214.
  2. ↑ "No. 109 Mathematical puzzle". American Agriculturist. Vol. 23, no. 12. December 1864. p. 349.
  3. ↑ Maurice Kraitchik, Mathematical Recreations (1953), pp. 79-80.
  4. ↑ J. A. H. Hunter, in the Toronto Globe and Mail (27 October 1955), p. 27.
  5. ↑ Feynman, Richard P. (August 2008). Perfectly Reasonable Deviations from the Beaten Track: The Letters of Richard P. Feynman. ISBN   9780786722426.
  6. ↑ David Eppstein (1987). "On the NP-completeness of cryptarithms" (PDF). SIGACT News. 18 (3): 38–40. doi:10.1145/24658.24662. S2CID   2814715.
  7. ↑ Pavlis, Anton. "Crux Mathematicorum" (PDF). Canadian Mathematical Society. Canadian Mathematical Society. p. 115. Retrieved 14 December 2016.

Alphametics solvers

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.