Chomp
Chomp is a 2-person game that can be played with a pencil and paper.
Name and rule
The playing field is a rectangle, divided into a grid of equally sized fields. The similarity with a chocolate bar gave the game its name, because the English verb to chomp means to bite off . One can play Chomp well on paper with arithmetic boxes. The players take turns removing fields (e.g. by marking the boxes) according to the following rule: The player in turn chooses one of the remaining fields (anchor field) and removes all remaining fields in the rectangle that has the anchor field on the left top corner and that extends down and right to the edge of the field. The player who has to take the top left square loses the game.
history
Fred Schuh is considered to be the inventor of Chomp. In 1952 he published the Spel van delers (" Game of Dividers "). This is the multidimensional number theoretic variant of Chomp (see generalizations ). In 1974 the standard version followed by David Gale , which was named Chomp by Martin Gardner . Since then, several publications with analyzes by Chomp have appeared; a winning strategy has not yet been developed.
In the German translation of the standard work of mathematical games Winning Ways by ER Berlekamp et al. was chosen as the name for the chomp game "Feeding" . However, this name does not seem to have caught on.
example
The following picture shows a typical chomp game sequence. Since the starting rectangle has 3 rows and 6 columns, this game is called (3,6) -Chomp. Legal game situations have a "staircase" from the bottom left to the top right at the bottom of the remaining fields (white fields).
Player B has to take the last square (checked) and loses. The anchor fields are each marked with a point.
Theory of the game
For theoretical reasons, the removal of the top left field is dispensed with, so that it is not the loser but the winner who makes the last move; in particular, the rectangle should have more than one field. With this agreement, Chomp can be classified as a neutral (or objective ) 2-player game within combinatorial game theory . Such games always have a winning strategy for either the attracting player (1st move) or the following player (2nd move). The same applies to every conceivable game situation between the first and the last move.
At Chomp there is a winning strategy for the attractive player. This can be proven with a so-called strategy theft: If there were a winning strategy for those who followed, there would have to be a profitable answer to the removal of the lower right field. But the attracting person could have chosen the anchor field of this reply move on the first move; that would give him a winning strategy. So the assumption of a winning strategy for the newcomer is wrong.
Strategy theft is not a constructive winning strategy at Chomp. This means that only the existence of a winning strategy is proven, but the winning strategy itself cannot be derived from it. No winning strategy is known for any (n, m) -Chomp (that is, for n rows, m columns), but for small pairs of numbers (n, m), and also for all pairs of numbers (n, n), (n, 2) and (2, m).
The winning strategy is generally ambiguous. The smallest known example where there is more than one winning strategy is (8,10) -Chomp.
Generalizations of the game idea
Chomp is easy to display and play thanks to the rectangular, grid-patterned playing field. However, it can also be formulated in number theory instead of geometrically. To do this, one begins with a natural number N, which is the product of two prime powers: N = p n × q m (p, q different prime numbers ). The players take turns choosing factors of N as anchor numbers ; 1 and no factor that has already been chosen or a multiple thereof may be chosen. The player with only 1 left loses. In game theory, this game is identical to (n + 1, m + 1) -Chomp, because the following picture shows that all factors of N can be arranged in a (n + 1, m + 1) rectangle; the anchor numbers then correspond to the anchor fields. After removing an anchor field, only factors remain that are not multiples of the number of anchors. In the picture the anchor field is in the (i + 1) -th row and the (k + 1) -th column; all fields outlined in green are omitted. Then there are only fields left that are not multiples of p i × q k .
The number-theoretical definition of the chomp game allows two generalizations. If r primes instead of two prime numbers are allowed to appear in the product for N, the same rules of the game lead to the r-dimensional chomp . Furthermore, one can remove the restriction to a finite number of fields; then all products of the r given prime numbers with arbitrarily high powers are allowed as anchor numbers, provided they are not already chosen anchor numbers or multiples thereof.
See also
Individual evidence
- ↑ Fred Schuh: Spel van delers . Nieuw Tijdschrift voor Wiskunde 39 (1952), pp. 299-304
- ^ David Gale: A curious Nim-type game . Amer. Math. Monthly 81 (1974), pp. 876-879
- ↑ a b c Elwyn R. Berlekamp et al .: Winning - Strategies for Mathematical Games , Volume 3. Vieweg, Braunschweig / Wiesbaden 1986, ISBN 3-528-08533-9 , pp. 172f
