MATHEMATICAL WORLD + VOLUME 17 KVANT SELECTA: Combinatorics, I Serge Tabachnikov, EditorSelected Titles in This Series 17 Serge Tabachnikov, Editor, Kvant Selecta: Combinatorics, 1, 2001 16 V. V. Prasolov, Essays on number and figures, 2000 15 Serge Tabachnikov, Editor, Kvant Selecta: Algebra and analysis. Il, 1999 14 Serge Tabachnikov, Editor, Kvant Selecta: Algebra and analysis. 1, 1999 13 Saul Stahl, A gentle introduction to game theory, 1999 12 V.S. Varadarajan, Algebra in ancient and modern times, 1998 11 Kunihiko Kodaira, Editor, Basic analysis: Japanese grade 11, 1996 10 Kunihiko Kodaira, Editor, Algebra and geometry: Japanese grade 11, 1996 9 Kunihiko Kodaira, Editor, Mathematics 2: Japanese grade 11, 1997 8 Kunihiko Kodaira, Editor, Mathematics 1: Japanese grade 10, 1996 7 Dmitry Fomin, Sergey Genkin, and Ilia Itenberg, Mathematical circles (Russian experience), 1996 David W. Farmer and Theodore B. Stanford, Knots and surfaces: A guide to discovering mathematics, 1996 David W. Farmer, Groups and symmetry: A guide to discovering mathematics, 1996 V. V. Prasolov, Intuitive topology, 1995 L. E. Sadovskit and A. L. Sadovskif, Mathematics and sports, 1993 ‘Yu. A. Shashkin, Fixed points, 1991 1 V.M. Tikhomirov, Stories about maxima and minima, 1990 woeKVANT SELECTA: Combinatorics, IMATHEMATICAL WORLD + VOLUME 17 KVANT SELECTA: Combinatorics, I Serge Tabachnikov, Editor American Mathematical Society‘This volume is a collection of articles translated from Russian Editions of the journal “Kvant”. ‘Translated by Hal McFaden Cover art created by Sergei Ivanov 2000 Mathematics Subject Classification. Primary 00-01, 00A08; Secondary 97A20. AssTRacr. This volume is the third in a series of translations of selected mathematical articles published in the Russian magazine “Kvant™ (meaning “Quantur”) since 1970. The papers in this ‘volume are devoted to various problems of combinatorics and its applications. ‘The book is intended for students and teachers who love mathematics and want to learn it beyond the standard school curriculum. ISBN 0-8218-2171-7 ISSN 1055-9426 Copying and reprinting. Individual readers of this publication, and nonprofit libraries acting for them, are permitted to make fair use of the material, such as to copy an article for use {in teaching or research. Permission is granted to quote brief passages from this publication in reviews, provided the customary acknowledgment of the source is given. ‘Republication, systematic copying, or multiple reproduction of any material in this is permitted only under license from the American Mathematical Society. Requests for such permission should be addressed to the Assistant to the Publisher, American Mathematical Society, P.O, Box 6248, Providence, Rhode Island 02940-6248. Requests can also be made by e-mail to roprint-pornissicndans.org. © 2001 by the American Mathematical Society. All rights reserved. ‘The American Mathematical Society retains all rights ‘except those granted to the United States Government. Printed in the United States of America. @ The paper used in this book is acid-free and falls within the guidelines ‘established to ensure permanence and durability. Visit the AMS home page at URL: http://vw.ans.org/ 10987654321 060504030201Contents Preface ‘Two Games with Matchsticks 1. M. Yactom Economics and Linear Inequalities A. B. Katok Economics and Linear Inequalities (Continuation) A. B. KaTox Switching Networks R. V. FREIVALD Who Will Go to Rio? G. M. ADEL‘son-VEL'ski, I. N. BERNSHTEIN, AND M. L. GERVER From the Life of Units A. L. Toom Nonrepeating Sequences G. A. GurevicH Words with Restrictions A. M. STePIN AND A. T. TAGI-ZADE Planar Switching Circuits S. OVCHINNIKOV Classification Algorithms P. BLEHER AND M. KELBERT How to Detect a Counterfeit Coin G. SHESTOPAL ‘The Generalized Problem of Counterfeit Coins M. MAMIKON ‘Truthtellers, Liars, and Deceivers P. BLEHER 47 6 103 107vit CONTENTS Solvable and Unsolvable Algorithmic Problems V. A. Uspenskil AND A. L. SEMENOV Best Bet for Simpletons P. A. PEVZNER 3 123Preface This volume is the third in a sories of translations of selected mathematical articles published in the Russian magazine “Kvant™ (meaning “Quantum”) since 1970 (the first two volumes were published by the AMS in 1999; see Mathematical World, volumes 14, 15). The reader interested in the history of “Kvant” is referred to the Preface in the first volume. The articles in the present volume are devoted mainly to combinatorics and discrete mathematics. They are written for motivated high schoo! students, and no substantial background knowledge of mathematics is needed to understand them. However, this is not “an easy reading”: the articles contain nontrivial material, and one should be prepared to work with pencil and paper at hand and to return to difficult places more than once. The industrious reader will be generously rewarded by the elegance and beauty of the subject. Serge TabachnikovTwo Games with Matchsticks 1M. Yactom In this article we tell you about the games “Nim” and “Tsyan-shizi”. Both are Chinese folk games; the translation of “Tsyan-shizi” is “picking up stones” (of course, replacing the stones in the games by matchsticks is an inessential change). ‘These games later penetrated into Europe; at one time the game Nim was popular in Western Europe. Let us describe the rules of these games. ‘The game Nim There are three piles of matchsticks on a table. Two players in turn take match- sticks from these piles, and during his turn each player can take any number of matchsticks from one (and only one!) of the piles. The winner is the one who takes the last matchstick. ‘The game Tsyan-shizi There are two piles of matchsticks on a table. Two players in turn take match- sticks from these piles, and during his turn each player can either take any numbers of matchsticks from one pile or the same (but also arbitrary!) number of matchsticks from both piles. The winner is the one who takes the last matchstick. ‘The problem is to determine the initial positions (that is, the numbers of match- sticks in each pile) such that the first player can win and the initial positions such that he cannot win, and to determine a method of correct (winning) play. Practically, it is very convenient to play Nim or Tsyan-shizi at the blackboard— without any matchsticks but with chalk and eraser in hand. On the blackboard one can sketch, say, three rows of boxes ending at the right-hand side of the board, and three circles, one in each row of boxes (Figure 1). Each player in his turn erases one of the circles and “shifts” it across an arbitrary number of boxes to the right (here we are playing Nim); the winner is the one who makes the last move. Tsyan-shizi can be played in the same way, except that now the blackboard has two rows of boxes, and each player in his turn either moves one circle or moves both circles across the same number of boxes. ‘The Russian original is published in Keant 1971, no. 2, pp. 4-10. 12 1. M. YAGLOM Ficure 2 Let us start playing Nim Assume that the three piles contain a, 6, and c matchsticks, respectively. where a 2 are winning positions for the first player: in his tun he takes ¢ — 1 matchsticks from the third pile, leaving the certain losing position (0.1.1) for his opponent. The next losing position for the first player is the triple (0,2,2): for if he takes one matchstick, then his opponent will leave iti move, and if he takes two, then his opponent will end the game (that is, win) in the next move. All the remaining positions (0,2,¢) with ¢ > 3 are winning positions for the first player, because he can take ¢ — 2 matchsticks in his turn and leave his opponent the (losing!) position (0,2,2). ‘The next positions that are losing for the first playcr have the form (1,2,3) and (0,3,3): here after each tum of the first player his opponent cither «ins immediately or reduces the game to one of the positions (0,1,1) or (0.2.2) considered! above (sce Figure 2, where the boldface numbers denote losing positions for the first player and the arrows denote moves). Continuing to reasou in this way, we can compose a table of initial positions that are losing positions for the first player: a player who has to make a move starting from such a position must inevitably pass to a position that is winning for his opponent (that is, to a position not in our table); conversely, if a position is not a losing position, then the player in his turn can either win at once or pass to 4 losing position, thereby “exposing” his opponent to it. The first fifteen of these