Verbal arithmetic
From Wikipedia, the free encyclopedia
Verbal arithmetic, also known as alphametics, cryptarithmetic, crypt-arithmetic, or cryptarithm, is a type of mathematical game consisting of a mathematical equation among unknown numbers, whose digits are represented by letters. 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.
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:
S E N D
+ M O R E
= M O N E Y
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 in ordinary arithmetic notation) the leading digit of a multi-digit number must not be zero. A good puzzle should have a unique solution, and the letters should make up a cute phrase (as in the example above).
Contents |
[edit] History
Verbal arithmetic puzzles are quite old and their inventor is not known. An example in The American Agriculturalist of 1864 largely disproves the popular notion that it was invented by Sam Loyd. The name crypt-arithmetic was coined by puzzlist Minos (pseudonym of Maurice Vatriquant) in the May 1931 issue of Sphinx, a Belgian magazine of recreational mathematics. In the 1955, J. A. H. Hunter introduced the word "alphametic" to designate cryptarithms, such as Dudeney's, whose letters form meaningful words or phrases.[2]
[edit] Solving cryptarithms
Solving a cryptarithm by hand usually involves a mix of clever deductions and exhaustive tests of possibilities. For instance, in Dudeney's example, one can immediately conclude that the leading M of the result is 1, since it is the only carry-over possible in the sum of two numbers. It follows that S=8 or S=9, because those are the only values that can produce a carry when added to M=1 (and possibly a carry). And so on.
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 for the backtracking paradigm of algorithm design. They also provide a pedagogical application for algorithms that generate all permutations (reorderings) of n given things.
When generalized to arbitrary bases, the problem of determining if a cryptarithm has a solution is NP-complete.[3] (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.
[edit] See also
[edit] References
- ^ H. E. Dudeney, in Strand Magazine vol. 68 (July 1924), pp. 97 and 214.
- ^ J. A. H. Hunter, in the Toronto Globe and Mail (27 October 1955), p. 27.
- ^ David Eppstein (1987). "On the NP-completeness of cryptarithms". SIGACT News 18 (3): 38–40.
- Martin Gardner, Mathematics, Magic, and Mystery. Dover (1956)
- Journal of Recreational Mathematics, has a regular alphametics column.
