Verbal arithmetic
Encyclopedia
Verbal arithmetic, also known as alphametics, cryptarithmetic, crypt-arithmetic, cryptarithm or word addition, is a type of mathematical game
consisting of a mathematical equation
among unknown number
s, whose digit
s are represented by letter
s. 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
, 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 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).
Verbal arithmetic can be useful as a motivation and source of exercises in the teaching
of algebra
.
. 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 word
s or phrases.’’”
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 permutation
s 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 provide also good examples for backtracking
paradigm of algorithm
design.
. (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.
Mathematical game
A mathematical game is a multiplayer game whose rules, strategies, and outcomes can be studied and explained by mathematics. Examples of such games are Tic-tac-toe and Dots and Boxes, to name a couple. On the surface, a game need not seem mathematical or complicated to still be a mathematical game...
consisting of a mathematical equation
Equation
An equation is a mathematical statement that asserts the equality of two expressions. In modern notation, this is written by placing the expressions on either side of an equals sign , for examplex + 3 = 5\,asserts that x+3 is equal to 5...
among unknown number
Number
A number is a mathematical object used to count and measure. In mathematics, the definition of number has been extended over the years to include such numbers as zero, negative numbers, rational numbers, irrational numbers, and complex numbers....
s, whose digit
Numerical digit
A digit is a symbol used in combinations to represent numbers in positional numeral systems. The name "digit" comes from the fact that the 10 digits of the hands correspond to the 10 symbols of the common base 10 number system, i.e...
s are represented by letter
Letter (alphabet)
A letter is a grapheme in an alphabetic system of writing, such as the Greek alphabet and its descendants. Letters compose phonemes and each phoneme represents a phone in the spoken form of the language....
s. 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
Arithmetic
Arithmetic or arithmetics is the oldest and most elementary branch of mathematics, used by almost everyone, for tasks ranging from simple day-to-day counting to advanced science and business calculations. It involves the study of quantity, especially as the result of combining numbers...
, such as addition
Addition
Addition is a mathematical operation that represents combining collections of objects together into a larger collection. It is signified by the plus sign . For example, in the picture on the right, there are 3 + 2 apples—meaning three apples and two other apples—which is the same as five apples....
, multiplication
Multiplication
Multiplication is the mathematical operation of scaling one number by another. It is one of the four basic operations in elementary arithmetic ....
, or division
Division (mathematics)
right|thumb|200px|20 \div 4=5In mathematics, especially in elementary arithmetic, division is an arithmetic operation.Specifically, if c times b equals a, written:c \times b = a\,...
. The classic example, published in the July 1924 issue of Strand Magazine by Henry Dudeney
Henry Dudeney
Henry Ernest Dudeney was an English author and mathematician who specialised in logic puzzles and mathematical games. He is known as one of the country's foremost creators of puzzles...
, 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 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).
Verbal arithmetic can be useful as a motivation and source of exercises in the teaching
Education
Education in its broadest, general sense is the means through which the aims and habits of a group of people lives on from one generation to the next. Generally, it occurs through any experience that has a formative effect on the way one thinks, feels, or acts...
of algebra
Algebra
Algebra is the branch of mathematics concerning the study of the rules of operations and relations, and the constructions and concepts arising from them, including terms, polynomials, equations and algebraic structures...
.
History
Verbal arithmetic puzzles are quite old and their inventor is not known. An example in The American Agriculturist of 1864 disproves the popular notion that it was invented by Sam LoydSam Loyd
Samuel Loyd , born in Philadelphia and raised in New York, was an American chess player, chess composer, puzzle author, and recreational mathematician....
. 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 word
Word
In language, a word is the smallest free form that may be uttered in isolation with semantic or pragmatic content . This contrasts with a morpheme, which is the smallest unit of meaning but will not necessarily stand on its own...
s or phrases.’’”
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):- From column 5, M = 1 since it is the only carry-over possible from the sum of two single digit numbers in column 4.
- To produce a carry from column 4 to column 5, S + M is at least 9, so S is 8 or 9, so S + M is 9 or 10, and so O is 0 or 1. But M = 1, so O = 0.
- If there were a carry from column 3 to column 4 then E = 9 and so N = 0. But O = 0, so there is no carry, and S = 9.
- If there were no carry from column 2 to column 3 then E = N, which is impossible. Therefore there is a carry and N = E + 1.
- If there were no carry from column 1 to column 2, then ( N + R ) mod 10 = E, and N = E + 1, so E + 1 + R = E mod 10, so R = 9. But S = 9, so there must be a carry from column 1 to column 2 and R = 8.
- To produce a carry from column 1 to column 2, we must have D + E = 10 + Y. As Y cannot be 0 or 1, D + E is at least 12. As D is at most 7, then E is at least 5. Also, N is at most 7, and N = E + 1. So E is 5 or 6.
- If E were 6 then to make D + E at least 12, D would have to be 7. But N = E + 1, so N would also be 7, which is impossible. Therefore E = 5 and N = 6.
- To make D + E at least 12 we must have D = 7, and so Y = 2.
The use of modular arithmetic
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
often helps. For example, use of mod-10 arithmetic allows the columns of an addition problem to be treated as simultaneous equations
Simultaneous equations
In mathematics, simultaneous equations are a set of equations containing multiple variables. This set is often referred to as a system of equations. A solution to a system of equations is a particular specification of the values of all variables that simultaneously satisfies all of the equations...
, while the use of mod-2 arithmetic allows inferences based on the parity of the variables.
In computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, cryptarithms provide good examples to illustrate the brute force method, and algorithms that generate all permutation
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
s 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 provide also good examples for backtracking
Backtracking
Backtracking is a general algorithm for finding all solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c as soon as it determines that c cannot possibly be completed to a valid solution.The classic textbook example...
paradigm of algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
design.
Other information
When generalized to arbitrary bases, the problem of determining if a cryptarithm has a solution is NP-completeNP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
. (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
Sudoku
is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid contains all of the digits from 1 to 9...
and Kakuro.
External links
- Alphametic Solver written in Python
- Cryptarithms at cut-the-knotCut-the-knotCut-the-knot is a free, advertisement-funded educational website maintained by Alexander Bogomolny and devoted to popular exposition of many topics in mathematics. The site has won more than 20 awards from scientific and educational publications, including a Scientific American Web Award in 2003,...
- Alphametics and Cryptarithms
- An on-line tool to create Alphametics and Cryptarithms