Chomp

Chomp is a 2 -player game that can be played with paper and pencil.

Name and usually

The playing field is a rectangle divided into a grid of equal-sized fields. The resemblance to a bar of chocolate has given the game its name, because the English verb to chomp say bite off. You can play well on paper with computer box Chomp. Players remove alternating fields (eg by marking the box ) according to the following rule: The player on the train are choosing one of the remaining fields (anchor field) and removes any remaining fields in the one rectangle that has the anchor field as the upper left corner and that's enough down and right up to the edge of the pitch. The player must take the upper left field, loses the game.

History

Fred shoe is considered the inventor of Chomp. He published in 1952 the Spel van Delers ( "play the part" ). This is the multi-dimensional number theoretic variant of Chomp (see generalizations ). In 1974, by David Gale is the standard version, by Martin Gardner was named Chomp. Since then, several publications have appeared with analyzes of Chomp; but so far a winning strategy could not be developed.

In the German translation of the standard work of mathematical games Winning Ways of ER Berlekamp et al. was chosen as the name for the Chomp game " chucks ". This name seems to but have not enforced.

Example

The following figure shows a typical sequence at Chomp game. Since the output rectangle has 3 rows and 6 columns, this game is called (3,6) - Chomp. Legal game situations have at the bottom of the remaining fields a " staircase " from bottom left to top right (white fields ).

Player B must be ( ticked ) take and lose the last field. The anchor fields are each marked by a dot.

Theory of play

On theoretical grounds, one does without the removal of the upper left box, so that is not the loser, but the winner of the last train makes; In particular, the rectangle may have more than one field. With this agreement, Chomp can be classified as neutral (or objective ) 2 -person game in combinatorial game theory. Such games always have a winning strategy for either the attractive players ( 1 train ) or join their players ( second train ). The same is true for every conceivable playing situation between the first and the last train.

In Chomp there is a winning strategy for attracting players. This one has a so-called strategy theft by: If there were a winning strategy for the second player, it would have a profitable reply move on the removal of the lower right box enter. The armature field this Antwortzugs but could choose the first player in the very first train; that would give him a winning strategy. So the adoption of a winning strategy for the second player is wrong.

The strategy theft is not a constructive winning strategy for Chomp. This means that only the existence of a winning strategy is proven, but the winning strategy itself is not to be derived. For any (n, m) - Chomp (ie for n rows, m columns ) is not a winning strategy known, but probably small number of pairs (n, m), and also for all pairs of numbers (n, n ), ( n, 2) and (2, m).

The winning strategy is not unique in general. The smallest known example in which there is more than one winning strategy, is (8.10) - Chomp.

Generalizations of the game idea

Chomp is through the rectangular, gridded field simple to prepare and playable. However, it can also number theoretically instead formulate geometrically. For this purpose, one starts with a natural number N, which is the product of two prime powers: N = pn × qm (p, q are distinct primes ). The players alternately choose an anchor numbers factors of N; this may not be selected which the 1 and not already selected factor or a multiple thereof. The player for whom only one is left, loses. This game is identical to game theory ( n 1, m 1) - Chomp, as the following figure shows that you can arrange all the factors of N in an (n 1, m 1) rectangle; the anchor numbers then correspond to the anchor fields. After removal of the anchor box remain only factors which are not multiples of the armature speed. In the picture is the anchor field in the (i 1) - th row and the (k 1) -th column; all green fields edged omitted. Then fields are only left that are not multiples of pi × qk.

The number-theoretic definition of Chomp game allows two generalizations. If r primes may occur instead of two primes in the product N, follow the same rules for r-dimensional Chomp. Furthermore, you can pick up many fields, the restriction to finite; then as the anchor numbers all products of r given prime numbers with arbitrarily high powers allowed, provided they are not already selected anchor numbers or multiples thereof.