MATHEMATICAL WORLD · VOLUME 17


KVANT SELECTA:
Combinatorics, I


AI
''-.\ l J °t\
I


I
.J
I, .J'
;
)
4,
\
0 ),
/\
"
)
i" ,
,.



\
£ Q
 -
.,-
Serge Tabachnikov, Editor


A




ot



\

--



"'




Selected Titles in This Series


17 Serge Tahachnikov, Editor, Kvant Selecta: Combinatorics, I, 2001
16 V. V. Prasolov, Essays on number and figures, 2000
15 Serge Tabachnikov, Editor, Kvant Selecta: Algebra and analysis. II, 1999
14 Serge Tabachnikov, Editor, Kvant Selecta: Algebra and analysis. I, 1999
13 Saul Stahl, A gentle introduction to game theory, 1999
12 V. S. Varadarajan, Algebra in ancient and modern times, 199H
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
6 David W. Farmer and Theodore B. Stanford, Knots and surfaces: A guide to
discovering mathematics, 1996
5 David W. Farmer, Groups and symmetry: A guide to discovering mathematics, 1996
4 V. V. Prasolov, Intuitive topology, 1995
3 L. E. Sadovski'i' and A. L. Sadovski'1', Mathematics and sports, 1993
2 Yu. A. Shashkin, Fixed points, 1991
1 V. M. Tikhomirov, Stories about maxima and minima, 1990





KVANT SELECTA:
Combinatorics, I


MATHEMATICAL WORLD · VOLUME 17
KVANT SELECT A:
Combinatorics, I
Serge Tabachnikov, Editor
American Mathematical Society

This volume is a collection of articles translated from Russian Editions
of the journal UK vant" .
Translated by Hal McFaden
Cover art created by Sergei Ivanov
2000 Mathematics Subject Classification. Primary 00-01, 00A08; Secondary 97A20.
ABSTRACT. This volume is the third in a series of translations of selected mathematical articles
published in the Russian magazine "Kvant" (meaning "Quantum") 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 publication
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 bye-mail to
reprint-permissioneams.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://w'W . ams. orgl
10 9 8 7 6 5 4 3 2 1 06 05 04 03 02 01

Contents
Prefe 
Two Games with Matchsticks
I. M. Y AGLOM 1
Economics and Linear Inequalities
A. B. KATOK 9
Economics and Linear Inequalities (Continuation)
A. B. KATOK 21
Switching Networks
R. V. FREIVALD 29
Who Will Go to Rio?
G. M. ADEL'SON-VEL'SKII, I. N. BERNSHTEIN, AND M. L. GERVER 37
From the Life of Units
A. L. TOOM 47
Nonrepeating Sequences
G. A. GUREVICH 61
Words with Restrictions
A. M. STEPIN AND A. T. TAGI-ZADE 67
Planar Switching Circuits
S. OVCHINNIKOV 75
Classification Algorithms
P. BLEHER AND M. KELBERT 87
How to Detect a Counterfeit Coin
G. SHESTOPAL 97
The Generalized Problem of Counterfeit Coins
M. MAMIKON 103
Truthtellers, Liars, and Deceivers
P. BLEHER 107
vii

viii
CONTENTS
Solvable and Unsolvable Algorithmic Problems
V. A. USPENSKII AND A. L. SEMENOV
Best Bet for Simpletons
P. A. PEVZNER
113
123

Preface
This volume is the third in a series of translations of selected mathematical
articles published in the Russian magazine "Kvant" (meaning "Quantum") since
1970 (the first two volumes were published by the Al\1S in 1999; see l\1Iathematical
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 wlitten for motivated high school 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
IJ\.


Two Games with Matchsticks
I. M. YAGLOM
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 Kvant 1971t no. 2t pp. 4-10.

2
I. M. YAGLOM
11 10
9
8
7
6
5
4
3
2
1
o
0

, 0
J 0
FIGURE 1

FIGURE 2
Let us start playing Nim
Assume that the three piles contain a, b, and c matchsticks. respectively. where
a < b < c; the triple (a, b, c) is the state or position of the game at the moment.
It is clear that (0.1.1) is a losing position for the first player: he has to use his
turn to take one of the two matchsticks, and then his opponent takes the second
matchstick and wins. All the other initial positions of the form (0.1. c) with c > 2
are winning positions for the first player: in his turn he takes c - 1 matchsticks
from the third pile, leaving the certain losing position {O. 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 him thc position (0.1.1) in the next
move, and if he takes two. then his opponent will ('nd the game (that is. win) in the
next movc. All thc remaining positions (0.2. c) with (' > 3 are 'Winning positions
for the first player, hecause he can take (' - 2 lllat.dlRtick..c; in his turn and leave
his opponent the (losing!) position (0.2.2). Thc n('xt positions that are losing
for the first player have t11<' form (1,2,3) and (0,3.3): her(' after each turn of the
first player his oppol1('nt. ('ith('r win... immediatcly or reduces the game to one of
the positions (0,1,1) or (0.2.2) (.onsid('r('(l above (C(' Figurc 2, where the boldface
numbers dcnof,c- losing positions for the first player and the arrows denote moves).
Continuing to r('ason in this wa.y, we can compose a table of initial positions
that are losing positions for t.ll<' first pla'c-r: a player who has to make a move
starting fmm such a position mw;t inet l itably 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 pos.ition. then the player in his turn can either win .at once or pass to
a losing position. thereby ,oexpm;ing" his opponent to it. The first fifteen of these

TWO GAMES WITH MATCHSTICKS
3
positions are collected in Table I.
TABLE I. Losing positions in Nim.
# 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
a 0 0 1 0 0 1 0 2 0 3 2 1 0 0 1
b 1 2 2 3 4 4 5 4 6 4 5 6 7 8 8
c 1 2 3 3 4 5 5 6 6 7 7 7 7 8 9
We try to see a general regularity in the makeup of the table, a rule for compos-
ing it. However, at first glance there does not seem to be any definite law dictating
such a rule.
The game Tsyan-shizi
Suppose that our two piles contain a and b matchsticks, respectively, where
a < b; the pair ( a, b) of numbers is called the state or position at the given moment
of the game. Here again we look for the positions that are losing positions for the
first player. The first such position is (1.2). There are four possible moves in all:
he can take 1 matchstick from the first pile. or 1 matchstick from t.he second pile,
or 2 matchstickes from the second pile, or, finally, 1 from each pile. It is clear that
for any possible move of the first player his opponent ends the game in his next
move. that is, he wins. All the remaining positions where one of the two numbers
a and b is equal to 1 or 2 or where the difference b - a is equal to 1 are winning
positions for the first player: if in this position it is impossible to finish the game
in one move (that is, to win at once), then the game can be reduced to the position
(1,2), which is winning for the first player. The next losing position is the position
(3,5): here after each move of the first player his opponent either wins at once or
reduces the game to the position (1.2). All the remaining positions (a, b) where
one of a and b is equal to 3 or 5 or where b - a = 2, are winning for the first player;
the next losing position for the first player is (4,7). Continuing in this way, we can
compose a table of positions that are losing for the first player.
TABLE II. Losing positions in Tsyan-shizi.
# 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
a 1 3 4 6 8 9 11 12 14 16 17 19 21 22 24
b 2 5 7 10 13 15 18 20 23 26 28 31 34 36 39
Unfortunately, here also 110 definite law is obvious for the formation of the
table.

4
I. M. YAGLOM
But is it not possible to write Tables I and II in a different way?
We have not been able to see any patterns in Tables I and II, made up of three
rows of numbers in the first case and two rows in the second. Let us now speculate
about possible reasons for our lack of success.
We have already mentioned that Tables I and II are numerical tables; they are
formed by rows of numbers. Of course, we wrote the numbers in these tables in the
usual way, using the universally accepted decimal number system. For example,
the numbers 24 and 39 in the last column of Table II mean: "2 tens and 4 units",
and "3 tens and 9 units". However, the decimal number system in itself, whose
origin has to do with the chance circumstance that people have 10 fingers on their
hands, is not in any way connected with the games we are considering; therefore,
it does not seem out of place to try to express our tables in a different way.
The rest of this paper is connected with the paper "Number systems" (Kvant
1971, no. 6). We need the following facts from this paper.
There are many systems for writing positive integers by means of a small num-
ber of symbols (digits). Positional number systems (it would be more precise to
say positional systems for writing numbers) are constructed as follows. A basis or
system of key numbers is specified that is an infinite increasing sequence of integers:
(*)
1 =qo <ql <q2 <q3 < ....
Then each number N is represented as a sum of the numbers in our base. taken
with various integer coefficients:
N = amqm + am-lqm-l +... + a2q2 + alql + aoqo.
This expression can be written as N = amam-l... a2alaO, where am, am-It... are
the "digits" in the expression for N.
For example, if the system of base numbers is
1.2,3,5,7,11,13,17.19.23....,
then the number 27 is written as
27 = 1.23+0.19+0.17+0.13+0.11+0.7+0.5+1.3+0.2+1.1 = "1000000101".
FUrthermore, the kth digit ak in the expression for an arbitrary number N in
the number system with base (*) is always smaller than the ratio qk+l/ qk.
If the base of the number system has the form
1 = qO, q = ql. q2. q3, q-1. . . . ,
where q is some integer, thl'n the number system is called the q-ary system; in it all
numbers can be represented as sums of powers of q, and all digits in the expression
for a number N are less than q (less than 10 in the case of the universally used
decimal number system).
The simplest of all systems for expressing integers is the binary number system,
in which all numbers are represented by sums of powers of the number 2. If we use
this number system, then our Tables I and II take a very different form (numbers

TWO GAMES WITH MATCHSTICKS
5
in lines band c in Tables Ia and IIa are written in binary number system):
TABLE IA
# 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
a 0 0 1 0 0 1 0 10 0 11 10 1 0 0 1
b 1 10 10 11 100 100 101 100 110 100 101 110 111 1000 1000
c 1 10 11 11 100 101 101 110 110 111 111 111 111 1000 1001
TABLE IIA
# 1 2 3 4 5 6 7 8 9
a 1 11 100 110 1000 1001 1011 1100 1110
b 10 101 111 1010 1101 1111 10010 10100 10111
10 11 12 13 14 15
10000 10001 10011 10101 10110 11000
11010 11100 11111 100010 100100 100111
A careful study of Table Ia enables us to see in it a quite definite pattern:
indeed, the losing positions (a, b, c) in the game Nim are those such that the sum of
the digits at each place in the binary representations of the numbers a, b, and c is
even (that is, equal to 0 or 2)! However, Table IIa turns out to be more insidious.
Nothing seems to make it better than Table II, and it is impossible to see in it any
definite regularity in the makeup of the losing pairs (a, b).
But why should the binary number system give us the key to finding a system
of winning play in Tsyan-shizi? True, we have seen that this system seems to help
in analyzing the theory of the game Nim, but Tsyan-shizi is a quite different game,
and a key that opens one door certainly does not have to work with another door.
Perhaps it is possible to rewrite Table IT in a different way: maybe a different
system for expressing the numbers forming this system sheds greater light on its
structure.
A detailed study of Table II reveals that Fibonacci numbers appear often in
it (for example, see the 1st, 2nd, 5th, and 13th columns of the table).! And this
in turn might suggest to us the expediency of writing Table II in the "Fibonacci
number system" , in which all numbers are represented by sums of numbers of the
Fibonacci sequence (the numbers in line b in Table lIb are written in the Fibonacci
number system). For example, the number 100 is 1000010100 in the Fibonacci
number system, that is, 100 = 1 . 89 + 1 . 8 + 1 . 3.
lThe Fibonacci numbers are the sequence of numbers beginning with 1 and 2 and then con-
structed according to the following rule: each number oj the Fibonacci sequence is equal to the sum
oj the two preceding numbers. The first terms are 1,2,3.5.8.13.21.34.55.89.144.233.377.....
The Fibonacci numbers are the subject ofN. N. Vorob'ev's well-known pamphlet of that title (3rd
ed.. "Nauka tt , Moscow, 1969).

6
I. M. YAGLOM
Let us now rewrite Table II in the Fibonacci number system:
TABLE lIB
# 1 2 3 4 5 6 7 8 9
a 1 100 101 1001 10000 10001 10100 10101 100001
b 10 1000 1010 10010 100000 100010 101000 101010 1000010
10 11 12 13 14 15
00100 100101 101001 1000000 1000001 1000100
1001000 1001010 1010010 10000000 10000010 10001000
Here there is 110 doubt about the rule for forming losing pairs: a pair (a, b) of
numbers with 1I < b represented in the Fibonacci system determines a losing position
in the game Tsyan-shizi if a ends with an even number of zeros. 2 and b is obtained
from a by adjoining one zero at the end.
Guess? No, theorem!
We have now almost reached our goal: it seems that we know what positions
in the games Nim and Tsyall-shizi are losing positions for the first player, and
what positions are winning positions. However, mathematics does not recognize
the expression "seems"; to solve a problem in mathematics means not only (and
not so much!) to guess what the solution of the problem will be, but also to prove
that your guess is correct.
The proof of correctness of the pattern we have observed in the composition of
the losing positions goes as follows: show that in each of the two games there is a
system of positions (they can be called distinguished or losing positions) such that:
(a) for each position that is not a losing position there exists a move after which
the position is a losing position;
(b) each losing position ceases to be a losing position after any move of a player.
These properties of losing positions determine a "method for winning the game"
(which can be used, of course, only when the initial position is not a losing position):
a player must make each move so that the position becomes a losing position. 3
We now formulate the two theorems that must be proved.
THEOREM I. The lo,c;ing positions (that. is, those satisfying the conditions (a)
and (h) above) in the gmne Nim are precisely those positions (a, b, c) for which the
sum.f) of all the digits at the same places in the binary representations of a, b, care
e'l.1en.
2The number a can end in "zero zeros". that is, it can fail to contain any zeros at the end,
but zero is an even number.
3We include the position (0,0,0) (respectively, (0,0» among the losing positions, because if
a. player can bring the game to this position, then he has already won.

TWO GAMES WITH MATCHSTICKS
7
THEOREM II. The losing positions in the game Tsyan-shizi are precisely those
positions (a, b) such that the number a, represented in the Fibonacci number system,
ends in an even number of zeros, while the number b is obtained from the number
a by adjoining a zero at the end.
REMARK. It follows from Theorems I and II that both Nim and Tsyan-shizi are
in a certain sense advantageous for the first player: there are fairly few positions that
arc losing for the first player (see the tables), that is. such positions are encountered
much more rarely than all the other positions (which are winning positions for the
first player).
The proofs of these theorems are in the exercises given below. '\Yt' advise you
to begin with Exercises 1-4, since Exercises 5-7 are much more involved.
EXERCISES.
1. Prove that if the position (a, b, c) in Nim is not a losing position, that is,
does not satisfy the conditions in the statement of Theorem I. then the next player
can use his turn to make it losing.
2. Prove that if the position (a, b, c) in Nim is a losing position, then after any
next nlove it ceases to be losing.
3. Indicate the rules for winning play in Nim when the number of piles is an
arbitrary specified integer 11 > 2 (the other rules of play remain as before). To what
does the winning strategy reduce in the case n = 2?
4. Describe the losing positions (a, b, c) in Nim when the ntID1bers a, b, care
written not in the binary number system but in the quaterl1ar' number system
(that is, with, say, a represented in the form
a = anctn-l ... a2alaO = a n 471 + a n _ 1 4 n - 1 +... + a242 + a 1 4 + ao,
where 0 < Oi < 3 for i = n, n - 1,.. .,2,1,0).4
5. Prove that for any positive integer p there is one and only one losing position
( a, b) in Tsyan-shizi (that is, a position satisfying the conditions of Theorem II) such
that b - a = p. Verify this for the first 15 losing positions in Table II.
6. Prove that if the position (a. b) in Tsyan-shizi does not satisfy the conditions
in Theorem II, then the next player can either win at once with his move or change
the position to a losing position.
7. Prove that if the position (a, b) in Tsyan-shizi is losing, then after any next
move it ceases to be losing.
8. Indicate the rules for winning plar in Tsyan-shizi if the number of piles b
odd (each player has the right. to take any number of matchsticks from any single
pile or an equal (and also arbitrary!) number from all piles.
PROBLEM. Indicate the rules for winning play in Tsyan-shizi if the number of
piles is equal to four.
I want to forewarn the reader that I do not know the solution to this problem.
4The overline means that this is a representation of a number by digits anan-l ... a2 Q lao.
and not a product of numbers.


Economics and Linear Inequalities
A. B. KATOK
At present mathematics is finding more and more applications in
economics. There are a number of mathematical methods that help
in solving economics problems. In this article we tell you about one
such method: the method of linear programming.
It is hard to find anyone who has not heard that in recent times mathematical
methods have been widely and successfully used to solve economics problems.
Less known is the fact that mathematical economics has a fairly respectable age.
It originated about one and a half centuries ago but for a long time did not attract
any special attention. By the end of the last century only a few dozen papers
on mathematical economics had been published. At present thousands of books
and papers on this topic are published yearly in various countries. What is the
reason for such sharp growth in the popularity of mathematical economics? Ver)'
much simplified, the reason is that previously people tried to use mathematics only
for describing phenomena in economics (and only a narrow circle of specialists are
interested in such questions), but now mathematics is used also for clarifying how
better to organize this or that production process. The first problem of this kind was
considered in 1939 by the Soviet mathematician Academician L. V. Kantorovich in
connection with the following practical question, posed by workers at the Leningrad
Plywood Trust.
One of the factories of this trust turned out five types of products. The pro-
duction plan specified the percentages of total output corresponding to products of
each type. The factory had eight machine stations, each capable of manufacturing
anyone of the five types of products with a known productivity. It was required to
distribute the work among the machine stations in such a way that the production
output would be as great as possible.
In solving this problem Kalltorovich worked out a method called the method of
linear programming. This method has proved to be useful. because many seeming!)'
unrelated economics problems turn out to be similar to t.he above problem and to
be solvable by analogous methods after they are reformulated in the language of
mathematics.
The Plywood Trust problem was fairly involved, so we present somewhat sim-
pler problems to clarify the ideas on which the method of linear programming is
based.
The Russian original is published in Kvant 1971, no. 3. pp. 1-9.
'J

10
A.B. KATOK
1. The bicycle problem. A bicycle factory produces both racing and touring
hik(':-;. Tlu.' production is organized so that one racing bike can be produced for each
two t.ouring hik('s: morcover. a racing bike brings in 1.5 times as 111uch profit. TIU'
fad.ory ('an product 700 touring hikes per day. but their warehouse can receive at
mod. 500 hik('s p('r clay. How nlC\ny racin and touring bikes should be produced
per clay in orcl('r to maximize profits'!
2. The probleln of the sandpits. Brick factories are locatcd at points A
and B. and sundpits supplying them are locatcd at points C and D. The sand
l"('quirenU'nt of the factori('s is not greater than the productivity of the sandpits.
Th(' amount of sand ll<.'ed('d by ('ach of the two factories is known, and the amount
eHdl sand}>it cun produce is kuown. :Iorcover, the cost of transporting a ton of
sand from eaeh sandpit to the factorics is known. It is necessary to organize the
sUI>plring of sand to the factories in such a way that expenditures are as small as
possible. (Such problems are called transport problems.)
3. The problem of feed for chickens. A poultry farm is in the business
of fattening chickens. Assume for simplicity that two products can serve as feed:
wh('at and chickpeas. For a chick to grow normally: its daily ration must contain
110 less t hem a ccrtain number of calories, and also certain amounts of protein, fat.
and carbohydrates. These amounts have been established by experts on poultry
bn'C'cling. and we must regard them as specified. Suppose that it is known how
many calories and how much protein. fat. and carbohydrates are contained in a
gram of wheat and how much in a gram of chickpeas. and that the price of each
type of f('ed is also known. How should the ration be composed in order to be of
fulll1utrit'ional value hut as ('heap as possible?
In cach of thesC' problems it is n('('essC\ry to make an optimal choice. although
thc choic(' is underst.ood differ('ntly in each problem. To see what mathematical
qu('stions arise in the solution of such problems. we analyze the problem of feed for
chickens in detail.
To analyz(' this probl('m. tll<.' standard high school curriculum suffices, and all
th(' calculations can easily be done with pcncil and paper.
Suppose that onto gram of wheat contains (11 calories. one gram of chickpeas
contains b l calories, and t.he minimal llmu))('r of calOl'i('s llc('ded in the daily ration
is ('I. \V(, select a menu containing .,. grams of wheat and y grams of chickpeas
(n'])l'('s('nted by th(' point (,", y) on t.he plant'). Let us tr' to distinguish those
points on the plant' that correspond to ratiuus cuntaining at. k'ast Cl calories. Since
n n1<'nl1 ("ousist.ing of .,. grams of wh('at and !I grams of dlickp('as contains al,1" + b1y
calories, such points must. satist:\"
(II'" + bl!1 > ('I.
From an (')c'uU'ut.ary algdml com's(' WP knuw t.hat. tIt(' points such that al' +
bIll = ('1 lic' Oll t.ll(' st.raight line It passing through the points (0, cl/bd and
(cdllb 0). This lim' divid('s t.hc' pIaU(' into t.wo parts. Thc in('quality al,,'+b 1 y > Cl
holds for points (,".!I) on oUt' side of It. and t h(' inequality a 1.1' + b 1 Y < cIon th('
oth('1' side. Em'h of t h('s(' parts, togetht'l' wit.h It itself, is called a half-plane. Thus,
om' half-plan<, consists of all tht' points (,I'..l/) with
alJ' + b1y > c},

ECONOMICS AND LINEAR INEQUALITIES
11
L 1
4; ..
." .l>
. ; ..:. ... ..
. ...,-..
,'"
-.6 h .
........'\ .
.,.
, ..... :.
..c.
 J"
....-.::..
. '! . .
'/..,
Q
'/'2' '
""'6
./

,...
/
ow '...
x:
}
},
FIGURE 1
II
Y
-- LJ. ....
. .
- "'i i . .
'. t' ....: . ':.
 $.
. ,
!' ,
"d .).- .!.
. <err.....
... . ...
'I YO"!"'"
....-"t ..... .
J.--.. 01'. "II
"" . -,-,.,4 '" .
"J;,'_!l ,'"
(-t. . 1;; kif' ·
...<., v..;..;  11' ...
... '-
A
:r
FIGURE 2
and the other of the points with
aId + b1y < ('t.
In our case at and b l are positive numbers, and t.hus the first half-plane is the
half-plane Ll shown in Figure 1.
tvloreover, it is clear from the conditions of our problem that 3.' and yare non-
negative numbers (it is impossible to give chickens a negative amount of feed). The
condition x > 0 is satisfied by the points of the right half-plane, the condition y > 0
is satisfied by the points of the upper half-plane, and the points (.r, y) correspond-
ing to rations containing at least Ct calories are those satisfying simultaneously the
three inequalities
{ X > 0, Y > O.
(1) all' + bty > C"b
that is, the points lying in the intersection of the right half-plane. the upper half-
plane, and the half-plane L}. Figure 2 shows the set of points corresponding to

12
A.B.KATOK
-11 1 "l. .. A
. . :/.,  .' .
:,'i .. .
,.,.... ,.  -.11I. ._
, iii. ...... 
 :1 . .
i,"'. ,-,...
...... . - . .
I r
. .
 .";!'"
'"
<10 ;-_._
- :....... .
. It. '\
....:1 -I,,: i
,
II.
X
FIGURE 3
solutions of the system of inequalities (1). Let us pass to other constraints. If one
gram of wheat contains a2 grams of protein, one gram of chickpeas contains b2
grams of protein, and the daily ration of a chick must contain at least C2 grams of
protein, then a sufficient amount of protein is obviously contained in those rations
made up of x grams of wheat and y grams of chickpeas when
a2' + b 2 y > C2.
The points cOl'responding to these rations lie in the half-plane L 2 bounded by the
line 1 2 given by the equation a2.1' + b 2 y = C2. In precisely the same way. the ration
must satisfy the inequalities
{ a3X + b 3 y > C3,
a4.1' + b 4 y > C4,
where a3 and a.. are the amounts of fat and carbohydrates in one gram of wheat. b3
and b 4 are those in one gram of chickpeas, and C3 and c.. are the minimal amounts of
fat and carbohydrates in the daily rations of a chick. (All quantities are measured
in grams.) The points (x. y) satisfying the first of these two inequalities lie in the
half-plane L3, and those satis(ving the second inequality lie ill the half-plane L... A
ration containing a sufficient anl0unt of all the components (calories. protein, fat,
and carbohydrates) will be called admissible. Thus. the admissible rations are those
consisting of x grams of wheat and y grams of chickpeas such that the following
system of six linear inequalities is satisfied:
.1' > 0, y > 0,
alJ' + b1y > Clo
(12,1' + b 2 y > C2,
a3 X + b 3 y > C3,
a..,l' + b4Y > Col.
(2)
The points of the plane corresponding to admissible rations lie in the intersection of
the right half-plane, the upper half-plane, and the half-planes Lit L 2 , L3, and L...
that is, interior to or on the boundary of the figure (infinite polygon) A in Figure 3.

ECONOMICS AND LINEAR INEQUALITIES
13
FIGURE 4
I
I
I
I
.--- .
-, ::;.....
-- -
>i "'..
;'J .:
'l.
.
.S.: f r ; - . .
"' J . ::.4"7-
. . .
..... --
. r,
FIGURE 5A
This figure represents the case when each inequality in the system (2) is essen-
tial, that is, for each of the six inequalities there is a solution of the system of the
remaining five inequalities that does not satisfy this inequality. Another possible
case is shown in Figure 4.
This means geometrically that one of the lines (the line l4 in Figure 4) lies
outside the set A, and algebraically that the system (2) is equivalent to the system
with one of the inequalities excluded (in our case the last inequality). In order
not to have to make special reservations, we shall assume everywhere that we are
dealing with the case pictured in Figure 3.
A set of points in the plane is said to be convex if together with any two of its
points it contains the segment joining these points. Figure 5a shows some convex
sets, and Figure 5b shows some nonconvex sets.
A half-plane is a convex set, and the set A is convex because the intersection
of any number of convex sets is also a convex set.
Let us now try to choose the cheapest of all the admissible rations. Suppose
that 1 gram of wheat costs p cents, and 1 gram of chickpeas costs q cents. Then a

14
A.B.KATOK
FIGURE 5a
 y

,
,
,
...
.  '?,. .
. · '''''' A
: ;1M
". O. l.
"<:.? -..
\. : .
..."t" ...
-.I!. :
. f.......
. . J ..
., .
.
".III .
&;II; 1}
, ,". .'II!' .
.
..:.;....,,-.-   ,.
x
FIGURE 6
ration of x grams of wheat and y grams of chickpeas costs p.t" + qy cents. Thus. the
price is a linear function of x and y, and the problem of finding the cheapest ration
amounts to finding, alnong all pairs (x, y) satisfying the s'ste1l1 of inequalities (2),
the pairs for which the value of this linear function attains a minimum. In other
words, we must find those points of A at which the function p.1' + qy attains the
smallest value it takes on the set A.
The set of points (x, y) for which the expression p.,. + qy is equal to some
number  is a straight line. For different . such lines are parallel. For negative
and suffidently small positive values of k this line docs not intersect A, and hence
th('rc is 110 admissible ration of pI'ice k ccnts. If we increase k. beginning say at
k = 0, t.hc>n Uw lin(' given hy t.he ('quat-ion p." + qy = . is displaced to the right (see
Figurc 6). Finally, for SOllle value k = k n the line p.l' + qy = ko intersects A for the
first time, "hitting" one of its vertices (the point ItI in Fig1ne 6) or a whole side of
it at once (this can happen if the lines p.t + qy = k are pal'allel to one of the lines
lit l2, l3, l.1 or, what is the samc, if the rat.io p/q is equal to one of the ratios
alIbi, a2/ b 2, a3/b- J , (I..db..;
see Figur(' 8 below).

ECONOMICS AND LINEAR INEQUALITIES
15
A line is called a support line of a convex set in the plane if the sc>t li('s entirely
in one of the half-plancs into which this line divides the plane, and at least one
point of the set lies on the line. Tlms, the equation px + qy = ko gives a support
line of the set A.
We now analyze separately the two possible cases mentioned. Let us assume
first that the ratio p / q is not equal to one of the ratios
al/bl, a2/ b 2, a3/b3, a4/ b 4.
Then the point AJ = (.1.0, Yo) is the unique solution of the problem of the cheapest
admissible ration. Indeed, any other point of A lies in the half-plane K given by
the inequality px + qy > ko, and hence corresponds to a more expensive ration.
The sides of the infinite polygon A are rays of the coordinate axes and segments of
the lines h, I2, I3, l... Therefore, on each of these sides one of the six inequalities
of the system (2) becomes an equality, and at each vertex of A two inequalities in
(2) become equalities. In the case in Figure 6 the point Allies at the intersection
of II and I3 (see Figure 3); consequently,
{ alxo + blyo = c},
a3 X O + b3Yo = C3,
from which
blC3 - b 3 cI c}a3 - alC3
Xo = , Yo = .
a3bl - a I b3 a3 b I - a 1 b 3
On the other hand, the remaining four inequalities hold in the strict sense at this
point, that is, with "greater than" and not "or equar'. This means that the ration
consisting of Xo grams of wheat and Yo grams of chickpeas contains the minimal
necessary amount of calories and fat but an excessive amount of protein and carbo-
hydrates (if }.[ were at the intersection of different lines, then the conclusion would
change correspondingly).
However, if our experts on poultry breeding were to decide that the chickens
required a little Inore than C2 grams of protein or a little more than c.. grams of
carbohydrates per day, then the cheapest ration we just found would correspond to
these new requirements (indeed, this would mean that 1 2 or 14 would move a little to
the right, but if this shift is sufficiently small, then Al is nevertheless still a vertex
of the diminished polygon A). However, if it is required to give the chickens a little
more caloric intake or a little nlore than C3 grams of fat per day, then the problem
of the cheapest ration Inust be solved anew, because the ration corresponding to the
point }'l ceases to be admissible, and the cheapest ration becomes more expensive
(see FiglU'e 7, where under the strengthened requirement (13. r + b 3 y > C3 +0 a point
A/' lying interior to the half-plane I( corresponds to the cheapest ration).
Now let us consider the case when p/q is equal to one of the four ratios, say
al/bl (see Figure 8). In this case the line px + qy = ko coincides with the line h.
All the points of A except for the points on the segment }./I Al 2 lie interior to I{,
and hence the ration corresponding to any point of }./lA[2 is a cheapest admissible
ration. Thus, there are always vertices of A among the points corresponding to
solutions of the problem of the cheapest l.ation.

16
A.B.KATOK
'$
)l& y \.
U fJ?
"/. 
n
.... cP

/vI'
\
3'c?> \

cP \
\\
(')
cP ,
'3
l;
FIGURE 7
, 
Q"" x
"/.6 ....
U .... ,.
 4
'4
.,Q Y
'1 Xs&

l)
. '.
, ..... .J
A
,
': .!r.!l-.
 :,. 't!:
,:):  .
....-1 :
r'
. ....(",
.. '-.
.-:;..
....
.... .- 
. .J
Q X
./
x&
./
()
./
FIGURE 8
A little theory
To find a solution it suffices to compare the values of the function px + qy at
all the vertices. If among these values there is one that is less than all the others,
then the corresponding vertex is the unique solution of the problem; if the values at
two vertices are equal and are less than the values at the remaining vertices, then
these vertices must be neighboring, and all the points of the side joining them are
solutions of the problem.
Denote by a the acute angle formed by a line with the x-axis. Call it the slope
angle. The tangent tan a of this angle is called the slope of the line. If we move
along the boundary of the set of admissible points, beginning from the ray of the
x-axis in the direction of the y-axis, then each successive side lies on a line with a
greater slope than the preceding one. The slope of the line ax+by = c (a > 0, b > 0)
is equal to a/b. (If b = 0, then a = 1r /2, and tan a is taken equal to infinity.)
Suppose that a support line passes through the vertex :AI of the set of admissible
points, and the slope angle of this line is {3, while the slope angles of the lines

ECONOMICS AND LINEAR INEQUALITIES
17
"Y I!
. 
.  .
", J'
. f .
A
l '
.
tt1l
..'t.. '..
.;:'
.'
:.,. I. .
-. 1:.
.'OJ. . I

. 1\1
.. .
. ..
;,r . .;
..,. ".".
. :. tf
 1...
,.. .
_.'
i......
.,", .,..,. ..
I '.
x
FIGURE 9
containing the sides adjacent to AI are equal to al and 0:2' Then the angle {3 is
greater than one of these angles and less than the other (see Figure 9).
Thus, to find a vertex lying on a support line with a given direction we must
compare the slope angle of the lines in the given direction with the slope angle of
the lines containing sides of the set of admissible points, and choose two neighboring
sides such that the angle {3 lies between their slope angles. Then the intersection
of these sides will be the desired vertex. If {3 coincides with the slope angle of one
of the sides, then the desired support line coincides with the line on which this
side lies. Instead of comparing slope angles, we could compare their tangents, Le.
slopes; this is considerably more convenient since the tangent of the slope angle can
be simply expressed in terms of the coefficients of the equation of the line.
Numerical examples
1. Among the solutions of the system of linear inequaJities 2x + y > 10, x > 0,
Y > 0, x + y > 8, 3x + 7y > 42, x + 5y > 20 find those for which the linear function
4x + 3y attains a minimum. l
The set of admissible points is shown in Figure 10, from which it is clear that
the sides of this set are rays of the coordinate axes and segments of all four lines
x + 5y = 20, 3x + 7y = 42, x + y = 8, 2x + Y = 10.
The support line with the slope equal to 4/3 must pass through the vertex at
the intersection of a pair of neighboring sides, one with the slope less than 4/3 and
the other with the slope greater than 4/3. Such a pair is formed by the sides on the
lines x + y = 8 and 2x + y = 10, which have slopes equal to 1 and 2, respectively.
Thus, the coordinates of the desired vertex can be determined from the system
{ X + y = 8,
2x + y = 10,
from which x = 2, y = 6. The value of the function 4x + 3y at this point is
4 . 2 + 3 . 6 = 26, and the support line is determined by the equation 4x + 3y = 26.
IThe numerical data of this example is not in any way connected with the quantities in the
problem of feed for chickens.

ll:l
A.B. KATOK
. . .- .
: ::.' '-L
 ....J....
.,......;..... .
..... ...
.. :C'. .
to.. .
; 0(:' .
--
A
(2,6)
,.
. ...
.
.......
,.
<,
,:II, t
! .
FIGURE 10
TABLE 1
Equation of the line Points on the coordinate The slope of the line
axes through which the
line passes
y=O 0
,,,'+5y = 20 (0,4), (20,0) 1/5
3.r + 7y = 42 (0,6). (14, 0) 3/7
x+y=8 (0,8), (8,0) 1
2x + y = 10 (0,10). (5.0) 2
x=O x
4x + 3y = r (0, c/3). (c/4. 0) --113
For comparison we compute the values of -1..,. + 3y at all the remaining vel'tices
of the set of admissible point.s (see Table 2).
TABLE 2
Equations of liues int('r- Coordinates (.1". JJ) Values of -1..,' + 3y at the
sectiug at a vert('x of t.he V(,l't.('x vertex
x = 0,2,,' + y = 10 (0.10) 4 . 0 + 3 . 10 = 30
2x+y = 10,.,'+Y = 8 (2.6) 4 . 2 + 3 . 6 = 26
.r + Y = 8,3.r + 7y = 42 (3.5.4.5) 4 . 3.5 + 3 . 4.5 = 27.5
3." + 7y = 42,:1= + 5y = 20 (8.75,2.25) -1.8.75 + 3.2.25 = 41.75
.r + 5y = 20. y = 0 (20,0) 4.20+3.0=80

ECONOMICS AND LINEAR INEQUALITIES
19
y
."i .

A
.
.. -;.
 .
 ,. 'II ..
... ....
. I. :.
c' .
  -.
-" ..':.:..

,... ,--
C"
1\-1')=(10,15) . ..:.
-- kf 1 =(16,O)
r.
FIGURE 11
2. Among th(' solutions of the system of linear inequalities x > 0, y > 0,
3x + Y > 15, 3x + 4y > 36, :r + 2y > 12, 2:1' + 8y > 32 find those for which the
function 3x + 12y attains a minimum.
The set of admissible points is shown in Figure 11. from which it is clear that
the line .1" + 2y = 12 lies entirely outside thf:\ set. Thus, the sides of the set are
I'ays of the coordinate axes and segments of the three remaining lines. Since the
tangent of the slope angle of the line 3x + 12y = c coincides with the tangcnt of the
slope angle of one of the lines containing the sides of the set of admissible points
(the line 2x + 8y = 32). the support line coincides with this line. The solutions of
the problem are all the points of the side lying on this line. The endpoints of this
side are vertices lying at the points of intersection of the line 2;1' + 8y = 32 with the
neighboring lines y = 0 and 3x + 4.y = 36 (recall that we are not considering the
line x + 2y = 12).
TABLE 3
Equation of the line Points on the coordinate Tangent of the slope
axes through which the angle of the line
line passes
y=O 0
2x + 8y = 32 (0,4), (16,0) 1/4
x + 2y = 12 (0.6), (12.0) 1/2
3.1. +4y = 36 (0,9),(12,0) 3/4
3x + y = 15 (0, 15), (5,0) 3
x=O .x
3.1" + 12y = c (0, c/12), (c/3. 0) 1/4

20
A. B. KATOK
A
B
40
50
D
c
'.
. .,
I .
:.
". 30
70
FIGURE 12
Thus, the coordinates (Xl, YI) of the first vertex AfI are determined from the
system of equations
{ 2XI +8YI = 32,
YI = 0,
from which Xl = 16, YI = 0, and the coordinates (X2' Y2) of the second vertex M2
are determined from the system of equations
{ 2X2 +8Y2 = 32,
3X2 + 4Y2 = 36,
from which X2 = 10 and Y2 = 1.5.
All the points of the segment l\fIl\I2 are solutions of the problem, in other
words, the points of the form (16A + 10(1 - A), 1.5(1 - A» = (10 + 6A. 1.5 - 1.5A),
where A is any number between 0 and 1. The value of the function 3x + 12y is 48
at all points of AI I Af2.
EXERCISES.
1. Solve the bicycle problem.
2. Solve the problem of the sandpits with t.he data given in Figure 12.
3. How is the set of adlnissible points in the problem of the cheapest ration
changed if it is required in addition that the weight of the ration not exceed s
grams? Can such a restriction have an effect 011 t.he solution?
4. Prove that any convex polrgOll in the plane can be represented as the set of
solutions of a system of linear inequalities.
5. Let p/q = al/bl (see Figures 3 and 8). Determine how the solutions of
the problem of the cheapest ration are changed ill this situation if the following
replacements are made in the sy:.;t.em (2):
{ a) CI br CI + 8,
b) C2 by C2 +8,
c) C'n by C n +8,
where 8 is a positive but very small number.

Economics and Linear
Inequalities (Continuation)
A. B. KATOR
In the first part of this article we treated a problem on the cheapest ration
for chickens. I There we confined ourselves to a very simplified situation. First, we
considered only four components of the ration: calorie intake and the presence of
protein, fat, and carbohydrates. But in fact it is necessary to take into account
also a number of other components: the presence of vitamins, minerals, and so on.
Second, we assumed that the ration can consist of only two types of food. From a
practical point of view this assumption can lead to meaningless results, since it is
very difficult to ensure a sufficient amount of, say, vitamin A in a ration consisting
of wheat and chickpeas, and the cost of the cheapest ration rises sharply. But if we
allow the ration to contain also a foodstuff rich in vitamin A, say cod-liver oil, then
we can get an admissible ration not much more expensive than a ration consisting
of wheat and chickpeas. Let us formulate this problem in a more general form.
We assume that as feed we can use n types of foodstuffs, where the cost of
a unit of the ith foodstuff is equal to Pi. Suppose also that we must take into
consideration m components of the ration, where a unit of the ith foodstuff contains
aji units of the jth component, and that the minimal admissible amount of the jth
component in the ration is equal to Cj. Then the cost of the ration consisting of Xl
units of the first foodstuff, X2 units of the second foodstuff, and so on, is equal to
PI Xl + . . . + pnxn.
The problem of the cheapest ration consists now in finding among all n-tuples
(Xl,.'.' X n ) satisfying the system of inequalities
Xl > 0, . . . ,x n > 0,
an Xl +... + alnX n > CI.
.. .... .... ....... .........
amlXI + . . . + amnX n > C m
those n-tuples for which the function
I(x) = PIXI + ... + Pnxn
attains a minimum.
We consider one more class of economics problems reducing to a similar math-
ematical formulation.
The Russian original is published in Kvant 1971, no. 4, pp. 1-7.
1 EDITORIAL NOTE. See the previous article of this collection.
:?l

22
A,B,KATOK
The problem of the choice of technology
Suppose that we are dealing with an enterprise or group of enterprises producing
some kind of uniform product. The manufacture of the product uses various forms
of resources: llUman labor, electrical energy. diverse raw materials, fuel, equipment,
a plot of land, and so on. Each of these resources is limited in amount. The
production can take placc in different ways, distinguished by the amounts and
ratios of the resources used ill them. For example, it is possible to obtain coal from
mines or from opell pits, to process some component at a machine ll1anufacturing
factory by means of various sequences of technical operations, to fatten cattle in
natural pastures or by specially sowing fodder crops, to construct a building of
bricks, natural stones, solid reinforced concrete, or prefabricated structures lnade
in factories. and so on.
Our problem is to detennine the amount of product that must be made using
each t.echnology in order that the total production output be as large as possible.
Let us now formulate this problem in mathematical language.
Suppose that Pj units of the jth resource (j = 1".., n) are available. and
aji units of the jth resource are needed to produce a unit of product using the ith
procedure. If Xi units of prod'uct are made using the ith procedure. then ajlXI +
,.. +ajmXm units of the jth resource are used, and these quantities must not exceed
Pj. The total production is obviously equal to Xl + . . . + Xm.
Thus. among the nt-tuples (.t'}. . , , . x m ) satisfying the system of linear inequal-
ities
(1)
Xl > 0, . . . ,X m > 0,
allXl + . ,. + alm.l'm < PI,
anI Xl + ... + anmx m < Pn
find those for which the linear function f(.}') = .1'1 +... + .r" attains a ma,timum,
In the first part of this article we showed how the problem on the cheapest ration
reduces in the case of two food types to the geometric problem of constructing a
support line with given direction to the set of admissible points. Of course, all
linear programming problems with two unknowns in the inequalities admit the
samc interpretation. This includes the bicyc1t' problem and the problcm of the
sandpits in the first part, along with the problem of the choice of technology when
there arC' two po.')sible technologies. We show how to get an analogous geometric
int('rprctation for linear programming problems containing three unknowns.
Let us consider the problelll of t h(' choiC'(' of h'chnolog)'. We assume that we
havC' a choice' among t.hr('(' diff('rC'nt technologies. Our problem is to find the triples
(.rb ,"2. ,"3) satis(ving the systC'll1 of linC'u1' ine<!ualitiC'S
,1'1 > 0, ,1'2 > 0, .1'3 > 0,
Uu. I '} + (112,1'2 + (113,"3 < Ph
(2)
(1,,,1.1'1 + C1 n 2 X 2 + a n 3 X 3 < Pn
and such that. th(' linear fUllction f(.I') = .rl +.r2+x3 attains a ma.ximum. Wc assume
all the numbers PI, , . . . Pn, au, . . . , ani, a12, , . . , a n 2, a13, . . . , a n 3 to be positive.

ECONOMICS AND LINEAR INEQUALITIES (CONTINUATION)
23
FIGURE 1
Each triple (.t'I,X2,X3) of real numbers can be pictured as a point in three-
dimensional space. The points (XI, X2, X3) with Xl = 0 lie in the plane of the
axes OX2 and OX3' This plane divides the whole space into two parts. Each part
together with the plane itself is called a half-space. One of the half-spaces (the one
lying to the right of the plane X20X3 in Figure 1) consists of points with Xl > 0,
and the other of points with .r} < O. The points with X2 > 0 fOl'l11 the half-space
"behind" the plane .1' I OX3, and the points with .r3 > 0 form the half-space above
the plane X l OX2' Thus, the points (XI, X2, X3) with a'l > 0, .1'2 > 0, and X3 > 0
lie in the intersection of the above three half-spaces, that is, in the positive oct.ant
(eighth part) of the space (see Figure 1).
The points (Xit .t'2, X3) for which
allXl + a12 X 2 + al3 X 3 = p}
form a plane passing through the points PI = (PI/au. 0, 0) 011 the axis OXI, Ql =
(O,PI/a12,0) on the axis OX2, and 8 1 = (0, 0,PI/aI3) on the axis Oa'3. The points
with
(3)
allXI + al2 x 2 + a13.l'3 < PI
lie in one of the half-spaces into which this plane divides the space. Since PI > 0,
the coordinates of the point 0 = (0,0,0) satisfy the inequality (3). Therefore, we
must choose the half-space LI containing this point. The points (Xit X2, X3) with
coordinates satisfying the system of inequalities
{ Xl > 0, X2 > 0, .1'3 > 0,
allXI + al2 X 2 + a13 X 3 < PI
lie in the intersection of LI and the positive octant, This intersection is the non-
regular tetrahedron OPIQ I 8 1 (Figure 2).
The points with coordinates satisfying the inequality a2l X I +a22 x 2+ a 23.l'3 < P2
lie in the half-space L2 containing 0 and bounded by the plane through the points
P2 = (p2/a2lt 0, 0), Q2 = (0, P2/ a 22 , 0), 8 2 = (0,0,P2/a23)'

24
A.B.KATOK
X 3
8 1
t ",. .,  QI
;,)" , ,,..
. f.. "-"e.' :1:2
. -.:oft,. . . 
'.1.. ., ... . " ,.. -.,
 :.t..-:. . .. ":. ..
. .. _:">;. . .. ' ... .. ':. . 
.. ....."  ... ..,.. . .... Ie .
:. .. ' ....... .", " 7.(G r.........
';' \}1: 'I:,1"'7. .' 
f... ..I._"'w' .. .. .. 
. ..' ......" ..\.'.;.11;...:.
,.....   ,I ..,.-,;.:.-: !i., :i., '..
.'" I .,. ....4..: ..,
. -. 
o
PI
XI
FIGURE 2
The solutions of the system
{ Xl > 0, X2 > 0, X3 > 0,
all Xl + a12 x 2 + al3 x 3 < PI
a21 Xl + a22 X 2 + a23 x 3 < P2
(4)
are given by the intersection of the tetrahedron OP l Q 1 8 l with the half-space L2,
or, what is the same, the intersection of the tetrahedra OP l Q 1 8 1 and OP2Q282.
The following cases are possible.
a) All three points P 2 , Q2, 82 lie outside the tetrahedron OP l Q l 8 h which
means that
PI/aU < P2/ a 21, Pl/al2 < P2/ a 22, Pl/al3 < P2/ a 23'
Then the intersection of OP I Q l 8 l and OP2Q282 coincides with OP I Q l 8 1 (Fig-
ure 3a).
b) Some of the points P 2 , Q2, 82 lie inside and some outside of 0 PI Q 1 8 l , which
means that among the numbers
PI/au - P2/a2h PI/aI2 - p2/ a 22, PI/aI3 - P2/a23
at least one is positive and at least one negative. Then the plane of P2, Q2, 82 "cuts
a corner off" the tetrahedron OP I Q 1 8 l ; the intersection of OP l Q l 8 1 and OP2Q282
is a polyhedron with six vertices (the polyhedron OP2Q2DID281 in Figure 3b).
c) All three points P2, Q2, 82 lie inside OP l Q l 8 h that is,
PI/au > P2/ a 2h PI/aI2 > P2/a22, Pl/a13 > P2/ a 23.
In this case the intersection of OP 1 Q 1 8 1 and OP2Q282 coincides with OP2Q282.
Adjoining successive inequalities in (2) to the system (4), we see that either
each successive inequality does not change the solution set of the preceding in-
equalities (as in case a», or the plane constructed "cuts off" part of the polyhedron
corresponding to the solutions of the previous system (as in cases b) and c».

ECONOMICS AND LINEAR INEQUALITIES (CONTINUATION)
25
FIGURE 3A
Xl
FIGURE 38
Just as for the plane, a set of points in space is said to be convex if together
with each two of its points it contains the entire segment joining them. Since a
half-space is a convex set and the common part of any number of convex sets is
clearly also convex, it follows that the set of points corresponding to the solutions
of the system (2) is a convex polyhedron A. One of the vertices of this polyhedron
is certainly the point 0, and the edges going out from this vertex will be segments
of the coordinate axes. We note that, in contrast to the case for the solutions of
the problem of feed for chickens, the set of admissible solutions in this case turned
out to be bounded.
A plane is called a support plane of a convex set in space if it is entirely
contained in one of the half-spaces into which this plane divides the space, while at
least one point of the set lies on the plane.

26
A.B.KATOK
Let us consider the family of parallel planes
.r1 + .r2 + X3 = ](.
(5)
For I{ < ° these planes are disjoint from the positive octant, and hence fronl the
polyhedron A. The plane
.1"1 + X2 + X3 = °
is a support plane of A and intersects it at the single point (0,0,0). The whole
polyhedron A lies in t.he half-space XI +X2+X3 > 0, and (O,O,O) corresponds to the
minimum. of the lincar function I{x) = Xl + X2 + X3 on A. When K is increased,
the plane Xl + .r:"! + .1'3 = I( intersects A in a polygon.
There is a value K = Ko such that tbe plane .1"1 + X2 + X3 = ](0 is again a
support plane of A but A lies in the half-space XI + X2 + X3 < Ko.
The linear function f(x) = ;1'1 + X2 + X3 attains a ma.ximum on A at all the
points of intersection of A with the plan£' .1'1 + X2 +.r3 = Ko. We see that the
family of parallel planes given hy the equations (5) contains two support planes of
A. one corresponding to the minimum and the other to the desired maximum of the
function a.1 + J'2 + .1"3 on A. The intersection of a convex polyhedron with a support
plane can consist of a single vertex of the polyhedron, or of one of its edges, or of
one of its faces. Each of these three cases can be realized in our situation.
The faces of A lie in the planes
X, = ° (i = 1,2,3),
aj1.1"1 + a J :"!.T2 + aj3X3 = Pj (j = 1,..., n)
(6)
(not necessarily in all of them). Each edge lies in the intersection of two of these
planes, and each vertex lies in the interscction of scveral (three or more) of the
planes. Even if lUore than three planes meet at a vertex. it is still possible to
choose some three of thcm with intersection consisting of this vertex alone. The
coordinates of the intersection point of three planes can be found by solving the
system of equations giving these planes.
Thus, the vertices of A can be found as follows. Form all possible triples of
equations among the 71 + 3 equations (6). (There are (n + 3)(n + 2){n + 1)/6 such
t.liples.) Each triple can be regarded as a systenl of three linear equat.ions in three
unknowns. If the solution (XI, X2. X3) of this system exists and is unique, then it
is necessary to check to se whether the re'maining 11 inequalities of the system (2)
hold for the numbers J'I. .1'2, .I':J' If they do. th(\n tbe' point (.t'b .1'2. .to3) is a vertex
of t.he polyhedron A. After all t.his. the linear programming problem can be solved
by comparing t.he values of the funct.ion f(J') = .1'1 + .t'2 + ...3 at all the vertices
obtained and choosing th<' vertices at which this value is greatest. This procedure
entails quite a large amount of computations. especially if II is fairly large.
In fact. t.he solutions of most of the' syst.e'nlS will not be vertices of A, and
moreover, to :-;olve' the' linear programming problem it. is not necessary to know all
the vert.icC's of the' polyhedron. Therefore, people do not usc such a direct exhaustive
search to solve lincar programming problems.
Th(, most widespread method for solving linear programming problems is the
very economical method deviscd by the American mathematicians von Neumann
and Dantzig in 1947 (they did not then know of Kalltorovich's work and alTived at
the method of linear programming independently of hhn). They called their method
the simplex 1nethod. We now describe the geometric idea of the simplex method

ECONOMICS AND LINEAR INEQUALITIES (CONTINUATION)
27
in connection with our three-dimensional problem. In using t.he simplex method
one actually transforms the problem by introducing some addit.ional inequalities
that enable one to simplify the solution procedure from an algebraic point of view.
However, to preserve geometric clarity we shallllot do this.
Thus, let us begin fro111 the point
0=(0,0,0),
which we know is a vertex, and consider the edges of A going out from it. Let P
be the other endpoint of one of these edges. Th(\ value of the function
f(x) = Xl +X2 +X3
at P is greater than at o. Let us now consider all the edges going out fro111 P.
When we 1110ve away from P along some of thes edges, the value of .1'1 + .1'2 + .r3
call decrease or remain the srone. We discard these edges at. once and choose one of
the edges along which Xl + X2 + X3 increases. Let pI be the other end of this edge.
The value of a=l + X2 + X3 at P' is greater than at P. Let us consider all the ('dges
going out from P' and choose an edge P' pit along which Xl + X2 + .1:3 increases,
and so on.
At. each step we obtain a vertex of A at which the value of Xl + X2 + .1"3 is
greater than at the preceding vertices. We arrive finally at a vertex
1\1 = (x, xg, xg)
such that the value of the function Xl + X2 + Xa does not increase upon moving
along each edge going out from it. This means that the plane
Xl +X2 +xa = X +xg +xg
is a support plane of A, and 1\1 is one of the solutions of the linear programming
problem. To find any other solutions we must find edges going out from 1\1 along
which the value of the fWIction Xl + X2 + .1;a remains constant..
If there are no such edges, then Jl.l is the only solution of the problem. If there
is one such edge, then the solutions of the problem are all the points of this edge.
If there are two such edges, then all the points of the face containing these edges
are the solutions.
1tlost often three edges of the polyhedron A go out from each vert.ex. In this
case we have to check at most two edges at each step of the process (since the
edge on which the preceding vertex lies can be discarded at once). If Xl + 2'2 + Xa
increases along both these edges, then it makes sense to find the endpoints of both
edges, compare the values of the function at the two vertices obtained. and chose
the one at which this value is greater. If going out from a vertex there are a gTeater
number of edges along which .1'1 + X2 + .1;a increases, then we can choose the one
forming the greatest acute angle with the plane Xl + X2 + .l'a = K, that is, the edge
along which the function Xl + X2 + Xa "increases most. rapidly". This method can
turn out to be more economical from a computational point of view, since it does
not require a preliminary determination of the endpoints of all the edges going out
from a given vertex.
All the geometric concepts t.hat have tunled out to be useful in treating linear
programming problems with two and three valiables (line, plane, the property of
being parallel, convex set, support line, support plane, and so on) can be formulated
purely algebraically in the language of equations and inequalities. In the use of this

28
A.B.KATOK
language, in contrast to the geometric language, as a rule, there is no essential
differences between the cases of two, three, and a greater number of variables, and
the corresponding definitions carryover to the general case by analogy.
On the other hand, the value of the geometric language is that intuition can
suggest certain constructions and devices for solving problems which are difficult
to see how to handle if only the algebraic language is used. The simplex method
represents a nice example of such a device. For this reason it has turned out to be
useful to introduce the geometric language also in the case of an arbitrary number
of variables.
EXERCISES.
1. Prove that if the planes Xl + X2 + Xs = K are parallel to some face of the
polyhedron A, then the plane Xl + X2 + Xs = Ko coincides with the plane of this
face.
2. Is it true that if the planes Xl + X2 + Xs = K are parallel to some edge of
A, then the plane Xl + X2 + Xs = [(0 passes through this edge?
3. a) Suppose that in the problem of choosing a technology under the previous
constraints on resources it is required to maximize not the production output but
the profit, that is, the difference between the price of the final product and the
expenditures on resources used in production, and it is known that the unit price
of the final product is equal to q dollars while the expenditure per unit of the jth
resource used is qj dollars (j = 1,. . . , m).
b) Assume that in the problem of choosing a technology it is required that the
production output be at least S units and that expenditures be minimal.
Formulate each of these problems as a linear programming problem. Prove that
there is exactly one value of S for which the solutions of the problem b) coincide
with those of a).

Switching Networks
R. V. FREIVALD
The following was a problem at the Fifth All-Union Mathematical Olympiad.
A switch (Figure 1) with two inputs and two outputs can be in two different
states.
'.
"
FIGURE 1
1 .2.,.3
1 2 3
FIGURE 2
Pictured in Figure 2 is the network for a telephone connection, with three
inputs and three outputs, that has the property of being "universal" in the sense
The Russian original is published in K'lJant 1972, no. 2, pp. 16-19.27.
29

30
R. V. FREIvALD
123
FIGURE 3
that by manipulating the states of the switches it is possible to realize any of t.he
six combinations of three inputs and three outputs, that is,
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
1 1 ! , 1 1 1 , 1 1 1 , 1 1 1 , 1 1 1 . 1 1 1
1 2 3 3 1 2 2 3 1 2 1 3 3 2 1 1 3 2
(Verify this. Note that the total number of different states of this network is 2 3 = 8,
since each switch can be in two states.)
a) Construct a network with four inputs and four out.puts that is universal,
t.hat is, any of the 24 possible combinations of inputs and outputs can be realized.
b) What is the minimum number of switches needed for such a network?
c) We say that a network with 1l inputs and n outputs is n-universal if it can
realize any of the n! = 1 . 2 . . . n possible combinations of n inputs and II different
outputs. Figure 3 shows a network with eight inputs and eight outputs. where A
and Bare 4-univcrsallletworks. Prove that it is 8-universal.
Find upper and lower bounds for the number of switches in a minimal n-
universal network.
We consider the network in Figure --I. It can easily be shown t.o be 4-universal by
finding the neccssary stat of the switchcs for all the...t! = 24 required combinations.
Note that it is more convenient in practice." to procccd in the opposite direction: to
considc'r all 2 5 = 32 diffcrcnt. states of till' nctworl\ and write out what combination
is l"C'alized by c'ach st.ate of the network (try this!).
If SOlllC llC't.work comist.s of a.t most. 4 switches, t.hen it can have only at most
2,1 = 16 diff('rC'llt st.at.('s. Therefore'. such a net.work cannot realize 24 different
combinat.ions, and hence cannot be --I-universal. We have tlms solved problems a)
and b).
Thc last a.rgument can bC' generalizcd. Suppose that an n-universal network
consists of rn switches. It has 2 m different stat.es and must realize n! different
combinations. Therefore, 2 m > u!. so 711, > log2(n!). Since n! > (n/2)n/2 for
n > 2, it follow:.; that 711 > log2 (n/2)n/2) = (n/2)(log2n -1). Using the sharper
inequality n! > (n + l)ne- n (see Problem 3 in M. I. Bashmakov's article "On the

SWITCHING NETWORKS
31
12 34
12 34
FIGURE 4
Bertrand postulate" in the previous volume of K vant Selecta. 1 one can improve the
bound obtained by a factor of roughly two: 11 > (log2(n + 1) -log2 e).
We now prove the 8-universality of the network in Figure 3. Generally speaking,
this proof too can be carried out by going through the states of the network. but
here such an exhaustive examination is not practically feasible (at least not in the
time allowed on the Olympiad). Therefore, we nlust argue more rationally.
Suppose that it is required to realize the combination
1 2 345 6 7 8
! ! ! ! ! ! ! !
II 1 2 13 14 15 16 ,; Is
We say that this combination consists of 8 connections: the first connects input
1 with output 'it the second connects input 2 with output 1 2 , and so on.
Note that any connection (for example, input 3 with output 5) in our network
can be implemented in precisely two ways: through block A and through block B
(Figures 5 and 6). Each of these blocks has 4 inputs and 4 outputs. To realize
our combination we ITIust distribute all 8 connections over blocks A and B in such
a way that 4 connections go through A and 4 through B. Furthermore, we nlust
ensure that two different connections do not go through the same input nor the
same output of A and B.
Let us consider the first and fifth inputs of our network. Each of them can be
switched either to the first input of A or to the first input of B. Consequently, one of
these inputs must be connected to block A and the other to block B. otherwise two
connections will be made to the same input of some block. The following pairs of
inputs must also be connected to different blocks: 2 and 6, 3 and 7, and 4 and 8. It
is easy to see that this condition for distributing the connections between the blocks
is not only necessary but also sufficient for different connections in the network not
to go through the same input of A and B. To formulate the same condition for the
outputs of A and B it is useful to look at the symmetric arrangement of inputs and
outputs of the network. We conclude that the following pairs of outputs must be
connected to different blocks: 1 and 5. 2 and 6, 3 and 7, and 4 and 8.
1 Kvant Selecta: Algebra and Analysis. I. Mathematical World. vol. 1-1. Amer. Math. Soe..
Providence. RI, 1999, pp. 21-26.

32
R. V. FREivALD
8
1 2 3 4
5 6 7 8
FIGURE 5
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
FIGURE 6
We shall represent in a figure these relations between different connections
of the same combination. Each separate connection is represented as a rectangle
inside which it is indicated what input the connection joins to what output. If two
connections must go through different blocks, then the corresponding rectangles are
joined by a line. We draw a double line if tbe inputs differ by -1 and a solid line if
the outputs differ by 4.
For example, the combination
1 234 5 678
! ! ! ! ! ! ! !
3 8 1 6 2 754
is represented in this way in Figure 7.
Whatever the combination, exactly one solid line and exactly one double line
go out from each rectangle. Therefore, the figure always consists of one or more
"rings". Further, in each ring the double and solid lines alternate, otherwise two
lines of the same kind would go out from some rectangle. Consequently, each ring
contains an even number of rectangles.
By using this figure it is easy to distribute the connections between the blocks
in such a way that all the constraints indicated above are satisfied. For this we must

SWITCHING NETWORKS
FIGURE 7
33
3

1
7

5
12345678
FIGURE 8
ensure that the connections corresponding to rectangles joined by a line go through
different blocks. Therefore, in each ring in the figure we must arbitrarily choose
one rectangle and realize the connection corresponding to this rectangle through
block A, then realize the connection corresponding to the next rectangle through
block B, then the connection corresponding to the next rectangle through A, and
so on until the ring is closed. The connections corresponding to the first and last
rectangles will be realized through different blocks, since the number of rectangles
in a ring is even. It is now proved that the network is 8-universal (see Figure 3).
We note only that the distribution of connections between the blocks can always
be carried out in such a way that one of the switches (say the lower left-hand one)
is in some previously specified state. (In other words, this switch can be removed
from the network without the network ceasing to be universal.) Then in the ring
containing the connection going through the distinguished switch the distribution
of connections between the blocks must begin with this connection.
To get an upper bound for the number of switches in a minimal n-universal
network we try to construct an n-universal network with fewer switches. The
above proof of the 8-universality of a network (see Figure 3) is easily generalized
to the case of any even number of inputs. This method makes it possible, given an
8-universal network, to construct a fairly economical 16-universal network, then a
32-universal network, and so on. It can be calculated that if n = 2 k and the network

34
R. V. FRElvALD
1 2 3 4 5 6
2k-l 2k
FIGURE 9
1
1
1 2 3 4 5 6
2k-l 2k 2k+l
FIGURE 10
in Figure 4 is used as the blocks of a 4-universalnetwork, then the network has
2k . 2 k - I} . 2 k = 2n . log2 n - l.l . n switches. If 11 is not a power of 2, then we
can use a network that is universal for a greater number of inputs tbat is a power
of 2. Since the nearest power of 2 greater than n exceeds the latter by at most a
factor of 2, we get that for any n there is an n-universal network containing at most
4n . log2 n switches.
This bound can be I'educed h' roughly a factor of -I. To this end it should be
noted that the network in Figure 3 can be further simplified (Figure 8) without
essential changes in the proof of its 8-universality.
Tllis network can also be generalized to an arbitrary even number of inputs
(Figure 9). In the case of an odd number of inputs we can use a similar network
(Figure 10). These two networks make it possible to construct n-universal networks
for any n (and not just for powers of 2) by passing step-by-step to networks with
fewer inputs. The network thus constructed contains
n([log 2 n] + 1) - 2 1 + [log 2 n] + 1  n. log2 n
switches.

SWITCHING NETWORKS
35
Thus, we have obtained the following bounds for t.he number 1 (n) of switches
in a minimal n-universal network:
n(log2(n + 1) -log2 e) < log2(n!) < 1(n) < n. ([log2 n) + 1) - 2 1 +(log:z n] + 1.
For n = 2,3,4 the lower bound log2(n!) coincides with the upper bound, and for
n > 5 they differ. It turns out that the true value 1\1(5) = 8 for n = 5 coincides
with the upper bound. Therefore, it might be supposed that the upper bound
estimates 1\1 (n) more accurately; however, this question has not been cleared up,
and is apparently very difficult.
Results of the Soviet mathematicians Yu. P. Of man, JM. I. Kratko, and
E. Ya. Grinberg were used in the formulation of the problem and the writing of this
article.


Who Will Go to Rio?
G. M. ADEL'SON-VEL'SKII, I. N. BERNSHTEIN, AND l\tI. L. GERVER
The problem addressed in this article does not have anything essential to do
with chess, nor even with competitive sports in general. It could, for example, be
formulated as follows: from n stones not of the same weight choose the k heaviest
and arrange them in decreasing order, using only balance scales without measuring
weights, and with a minimal number of weighings. And here is a formulation with
a quite real mathematical meaning: write a computer program that will select the
k largest of n distinct numbers and put them in decreasing order, with a minimal
number of comparisons. l
The condition that the numbers be distinct automatically ensures that if a > b
and b > c, then a > c. One does not have to be a seasoned fan to know that
there is nothing like this in sports and that, say, Fisher's loss to Petrosyan at the
qualification tournament in Curaao and Spasskil's win in the deciding game of the
world championship match with Petrosyan in no way predetermined the outcome
of the Spasskir-Fisher match.
We note rather that the Olympic system (the loser is eliminated) is based on
precisely the assumptions at the beginning of this article. To the point, the "usual"
Olympic scheme, in which the loser in the final is at once awarded second prize
(and the winner of the match between those who lost in the semifinals is awarded
third prize), is only an inferior variant of the "VBJ\iII Rules"!
The problem of which the authors speak, as already noted, is of a completely
serious nature. (Incidentally, despite its apparent "elementary" character, it was
solved only quite recently, a fact certainly of special interest for our journal.) But
the authors thought it would be more pleasant and fun to present the problem in
the language of chess.
Chapter I. The VBMI Rules
It has actually happened! The chess players of the town of Vasyuki have finally
been allowed to compete at the World Olympiad in Rio de Janeiro. As usual, this
was announced at the last moment, and now it is necessary in a matter of days to
hold an elimination tournament and choose the three strongest players from among
128 chess amateurs. Two of them (the champion and the second-prize winner) will
play for the Vasyuki team at the first and second boards; the third-prize winner
goes to Rio as an alternate.
The Russian original is published in Kvant 1972, no. 8. pp. 2-8.
lOnly the case k = 3 is treated in this article (the general case is discussed in Problem 3).
:r;"

38 G. M. ADEL'SON-VEL'SKIi. I. N. BERNSHTEIN. AND M. L. GERVER
There were long and difficult arguments about how best to organize the tour-
nament. and when there was almost no time left they finally adopted the following
propositions.
1°. Hold the elimination games consecutively, onp after the other. 2 Name the
participants of each game based on the results of preceding games.
2°. Do not count drawn games (determine the winner by lot in the case of a
draw).
3°. If A defeats B. then regard A as stronger than B.
4 0 . If A is stronger than Band B is stronger than C, then regard A as stronger
than C"
5°. If it has already been established which one of two players is stronger, then
they do not play each other.
6° . Commission the VBIvII3 to quickly work out exact. rules for determining
thl' winners of the first, second, and third prizes in a minimal number of games.
Here are the rules set by the VBIvII.
 1. Determination of the champion. The games take place according to
the Olympic system. In the first round all 128 participants are divided into 64
pairs, and in each pair a winner is determined (64 games). In the second round
the 64 winners of the first round are divided into 32 pairs. and in each of them a
winner is determined (32 more games), and so on: in the third round there are 16
games, in the fourth round 8 games. in the fifth round -l games. in the sixth round
2 games, and in the seventh round 1 gmne. In all, 127 games.
The winner of the final game takes the title of "champion'. and is given the
right to play at the first board.
 2. Determination of the second-prize winner. It is clem. that onl)' those
players who have lost only to the champion have a right to this prize. There are
seven of them. We assign them numbers from 1 to 7 (no. 1 lost. to the champion in
the first round. no. 2 in the sccond round, and so on).
The second-prize winner is determined as follows: no. 1 plays no. 2. the winner
plays no. 3. the winner of this game plays no. 4, and so on (6 games in all).
The winner of the last game is declared the second-prize winner and plays for
the temn at the second board.
 3. Deterlnination of the alternate (the third-prize winner). The
chess players that have not lost to anyone other than the champion and the second-
prize winner have a claim to this prize. They ha\"( certainb" lost to the second-prize
winner. ...
The s('cond-priz(' winner won at most ('v('n games. Indeed, suppose that he
becaul<' no. i (i is a number from 1 to 7: s('('  2). Therefore. in play according
to t11<' Olympic syst('m (see  1) h(' won i-I games (in the 1st, 2nd,..., i-1st
rounds). Then (('('  2) 11(' dC'C('nt.l'd at most one chess player with a number less
2 After the famous performance of t.he Grandmaster o. Bender, the Vasyuki chess amateurs
sink into a gloomy stupor at the mention of "simultaneous games". (Translator's Note. This all
relates to a chapter in a 1928 comic novel, The twelve chairs by I. lI'f and E. Petrov, which has
long been widely known in Russia; English transl.. Random House, 1963.)
3Vasyuki Branch of the Mathematical Institute.
.J For otherwise they would have remained candidates for the second board.

WHO WILL GO TO RIO?
39
than i,5 and 7 - i players with numbers greater then i, that is. he played 8 - i or
7 - i more games. Adding this number to i-I, we get that in all the second-prize
winner won 7 or 6 games.
Thus, at most seven players compete for third prize. The strongest of them
can be determined in 6 games. This player will be the team's alternate.
 4. Conclusions. To find among 128 players the champion, second-prize
winner, and third-prize winner it suffices that
127 + 6 + 6 = 139
games be played.
Chapter II. Can the tournament be shorter?
How good are the VBfvlI rules? Can the first-, second-, and third-prize winners
be determined in fewer games?
 1. The opinion of the leadership, chance, and fate. Suppose that even
before the competitions the leadership of the Four Knights Club has formed the
opinion that A is the strongest player, B the second strongest, and C the third
strongest. And suppose that the goal of the competitions is to verify that thi:i is
indeed so.
Such verification cannot be accomplished in fewer than 127 games, since all the
players except the champion must lose at least one game. And in 127 games it is
possible that the 125 "outsiders" (all except A, B, and C) play 124 games with
the loser eliminated after each game, then the winner plays C and loses, 6 Closes
to B, 6 and B loses to A. 6 Properly speaking, it is not even necessary to know the
prize whmers in advance: they can be guessed in a random way, so that sometimes
("with luck") the three prize winners are determined in 127 games.
However, we assume that nothing is known in advance about the relative
strengths of the players and that we are not "lucky". fvloreover, we imagine that
III Fortune (or an agent of rivals, if you wish) influences the outcome of each game
in such a way that the competitions are drawn out as long as possible. We show
that in this case it is impossible to choose the first-, second-, and third-prize win-
ners among 128 players in fewer than 139 games, no matter how the elimination
competitions are carried out. 7
 2. Formulation of the theorem. We go directly to the general case, when
there are not necessarily 128 participants in the competitions, but an arbitrary
number n. We also introduce the following notation. Let N be an arbitrary number;
there are integers l such that 2' > N. Let I[N] be the smallest such integer.
EXAMPLES.
1. Since 2 3 < 10 < 2 4 , we have 1[10] = 4.
2. If 2 k - 1 < N < 2 k , then I[N] = k.
3. Below we shalllleed to know what I[N] is for N = 128. 127. Since 128 = 2 7
and 2 6 < 127 < 2 7 , it follows that 2 13 < 128.127 < 2 14 , and thus 1[128.127] = 14.
5If i = I, then there is no such player, of course; but if i > 1. then there are such players,
and no. i defeated the strongest of them.
6If he wins, then the leadership is wrong, and what to do then is not clear.
7Corresponding to the assumptions 1-5 in Chapter I. of course.

40 G. M. ADEL'SON-VEL'SKII, I. N. BERNSHTEIN, AND M. L. GERVER
THEOREM. To determine the first-, second-, and third-prize winners among n
chess players, at least
pen) = l[n(n - 1)] + n - 3
games must be played.
EXPLANATION. This theorem can be formulated in another way as follows.
If it is decided that there will be a maximum of R games, where
R < l[n(n - 1)] + n - 3,
then it can happen that after R games it is not yet possible to determine the first-,
second-, and third-prize winners (no matter what the rules are for arranging the
elimination competitions).
If n = 128, then l[n(n - 1)] = l[128. 127] = 14 (see Example 3). Hence,
P(128) = 14 + 128 - 3 = 139. It thus follows from the theorem that to determine
the first three places among 128 players at least 139 games are needed. In 139
games it is possible to determine them according to the VBMI rules, so the VBMI
rules are good rules!
 3. In the account book of III Fortune. In  1 of this chapter we antic-
ipated that III Fortune tries to draw out the elimination competitions. We now
indicate a strategy which enables him to ensure that at least
pen) = l[n(n-l)] +n-3
games are needed to determine the first three places among n players.
DEFINITION 1. Any pair (A, B) of players will be called a team. s We note that
the teams (A, B) and (B,A) are different; A plays at the first board for the team
(A, B) and at the second board for the team (B, A).
Before the beginning of the competitions all teams are candidates for partici-
pation in the Olympiad. How many of them are there?
Before the tournament each of the n players has a chance to play at the first
board. Furthermore, he can head n - 1 teams (any player except him can fall in
second place). Thus, the number of teams is n( n - 1).
In the course of the competitions the number of teams competing for the trip
to Rio decreases gradually (until there is one such team left).
Suppose that several games have already been played in the tournament. Cor-
responding to their results, we divide all the participants into three groups. In the
first group are all those who have not lost any games. In the second are those who
have lost exactly one game, necessarily to a player in the first group. In the third
are all the rest (those who have lost more than one game or one game to a player
not in the first group).
EXERCISE. Verify that in this situation the following teams have a chance to
go to Rio:
1) all the teams (A, B) in which A is in the first group and B in the second
group, and the only game B lost was to Ai
2) all the teams (0, D) in which 0 and D are in the first group.
8 A "team" consists of two and not three players: the alternate is not included in the team
(this is more convenient for the exposition).

WHO WILL GO TO RIO?
41
Verify that no other teams in the Olympiad have a chance to go.
HINT. If B lost to A, then B can certainly not become the champion, and he
can become the second-prize winner only if A becomes the champion. Thus, B 110
longer has the possibility of heading a team, and can only turn out to be the second
player on one teanl: (A. B).
DEFINITION 2. If at some point in the competitions A has won a games and B
has won b games, then we say that there are a + b points in the assets of the team
(A, B). The number 2 a + b is called the characteristic of the team (A, B).
After each new game the assets of any team either increase by 1 (if the win-
ner of the game belongs to this team) or does not change. Correspondingly, the
characteristic of any team either doubles or remains the same.
DEFINITION 3. Suppose that some number of games have been played. It is
convenient to characterize this situation by the number 1\I equal to the sum of
the characteristics of all the teams that are still competing for participation in the
Olympiad.
What is Al initially (before any competitions)? Nobody has won even a single
game, there are 0 points in the assets of every team, and the characteristic of any
team is equal to 2 0 = 1. Thus, 1\/ is initially just the total number of teams, that
is, AI initial = n( n - 1).
LEMMA. Suppose that in some situation characterized by the number 1\1 a game
is played between the players A and B. Denote by 1\I A the number characterizing
the situation that arises if A wins, and by AI B the characteristic of the situation in
the case when B wins. Then
1\I A + MB = 21\I.
so that at least one of A/A and M B is not less than 1\1.
PROOF. Before the game between A and B it is natural to divide all the teams
competing to go to the Olympiad into three groups.
Group I. The teams containing A and either not containing B or containing B
after A. 9
Group II. The teanlS containing B and either not containing A or containing
A after B.
Group III. The teams containing neither A nor B.
Let 1\11, 1\III, and 1\luI denote the sums of the characteristics of the teams in
Groups I, II, and III (so that 1\I = 1\11 + 1\III + 1\Iud.
We prove that 1\1.4 = 2MI + 1\ III 1 . Indeed, after A wins, only the teams in
Groups I and III are competing for the trip to Rio; further, in Group III the
characteristics of the teams do not change, while those in Group I are doubled.
It is proved similarly that 1\IB = 21\III + 1\1111. Thus,
1\/A + 1\IB = 2(1\11 + 1\III + 1\lud = 21\1.
The strategy of III Fortune. How is the elimination tournament arranged? As
we know, the games take place successively (one after the other). The participants
9 B occurs after A only in the one team (A, B); this team is in Group I, of course, only if it
is still competing to go to Rio.

-12 G. M. ADEL'SON-VEL'SKII. I. N. BERNSHTEIN, AND M. L. GERVER
of each new game are named in dependence on the results of all the preceding
games.
Suppose that a certain number of games have already taken place, and the next.
game should be between A and B. III Fortune computes the characteristics 111, lilA,
and 1I1B (see the lemma); if ilIA> AIB then he arranges it so that A wins, and if
AI B > AI..\ then he arranges it so that B wins; but if AlA = lvIB, then he does not.
interferC'. ShlCC' t.he larger of AlA and 1\1 B is certainly not less than AI (according
to t.he lemma), it follows in this situation that after each game the characteristic
Al docs not decrea..o:;e.
We emphasize that it suffices for III Fortune to be omnipotent and not neces-
sarily omniscient: without going into the plans of the tournament organizers, he
cmploys t.he same strategy for any schedule of games.
We will show that with this strategy at least
Pen) = l[n(n - 1)] + 11. - 3
games arc needed t.o determine the first three places.
 4. Proof of the theorem. Before the competitions 1I/ init ial = 11.(11. - 1).
What is Al when the competitions are over and the first-, second-. and third-prize
winners X. y, and Z have been det.ermined? The one team (.Y. Y) has been selected
for the t.rip to the Olympiad. Dcnote by l' the number of points in the assets of
this team. Then A/final = 2 V .
If III Fortune holds to the above strategy, then after each game the characteristic
Al does not decrease, so that Affinal is not less than Alinitial: 2 t . > 71(71 - 1), that
is, v > l[n(n - 1)]. Tlms, the first two prize winners X and Y have played at least
l[n(1l - 1)] games.
h1Ioreover, a minimum of 11. - 3 games were played without their participation.
Indeed, each of the 11. - 3 players not in the prize-winning triple must have lost to
someone besides X and 1 P J otherwise he would have claimed third place.
Thus. at least pen) = l[71(n -1)] + 11. - 3 games were played in the tournament.
The theorem is proved.
Chapter III. How can three prize-winners
be determined among n chess players?
In Chapter I rules were given for determining the first. tlll'ee prizes a1llong 128
chess players. We give analogous rules for the C8SC' of 11 players. Let l[11.] = k, that
is,
4)"'-1 < 2 k
... <n_ .
 1. Determination of the champion. The games are played according
t.o the Olympic system. In the first round the participants are broken up into
two groups: 2'" - 11. in the first group, and the 211 - 2'" others in the second; the
mcmbers of t.he second group are broken up into n - 2 k - 1 pairs; in each pair a
winner is determined, and he is admittC'd to the second round; the members of the
first gronp begin at Ollce to compC'te in the second rounel. In all,
(n - 2k-l) + (2 k - 11.) = 2 k - 1

WHO WILL GO TO RIO?
.J:i
participants are admitted to the second round. All the rounds bcginning with the
second are standard: 10 the participants in this round are brokcn up into pairs, a
winner is detcrmined in each pair, and he goes 011 to the ncxt round. The champion
is determincd in the final game of thc kth round. Since each of the 71. participants
aside from the champion loses exactly one game in this system, thcre are 71 - 1
games in all, in k rounds.
 2. Determination of the second-prize winner. The players who have
lost only to the champion compete for this place. There are at most : of them: we
give them the numbers 1,..., k (no. i is the on(' who lost to thc champion in the
ith round).ll
The games are conducted as follows: no. 1 plays no. 2,12 then the winner plays
no. 3, and so on (at most k - 1 games in all). The winner of the last game gets
second prize.
 3. Determination of the third-prize winner. It is easy to verify (see
 3 of Chaptcr I) that the second-prize winncr wins at most k games, and hence
at most k players compete for third place. The strongest of thcm is determined in
k -1 games. He is the third-prize winner.
 4. Conclusions. To find the first-, second-, and third-prize winners among
n chess players it suffices to have
(71. - 1) + (k -1) + (k -1) = 2k + n - 3 = 21[n] + n - 3
games played. We denote this number by Q(n).
Chapter IV. Discussion of results
Let n > 3 be an integer, and denote by 1(71.) the number satisfying the following
two conditions:
1) the first three prizes among 71 chess players can be determined with certainty
in l(n) games;
2) if R < l(n), then the results of R games can turn out to be such that the
first three places among 71. players cannot be determined.
Then the results obtained in Chapters II and III can be written as the formula
P(n) < l(n) < Q(n).
We recall that
P(n) =l[n(n -1)] + n - 3,
Q(n) =2l[n] + n - 3,
where l[n] = k for 2 k > 71. > 2 k - l .
It can be shown that Q(n) is equal either to P(n) or to P(n) + 1. In the first
case l(n) = P(n) = Q(n). In the second case there are two possibilities: either
lOIn contrast to the case analyzed under the VBMI rules, the first round is "nonstandard"
(that is, it requires an additional breaking up of the participants into groups as indicated above)
if n is not an exact power of 2.
11 We remark that the number 1 may possibly not be given to anyone (if the champion began
playing from the second round).
l2S ome times this game does not take place (see the preceding footnote), and everything
begins with the game between no. 2 and no. 3.

-14 G. M. ADEL'SON-VEL'SKIi. I. N. BERNSHTEiN. AND M. L. GERVER
B
F
A
FIGURE 1
l(n) = Pen) or l(n) = Q(n). Both possibilities can occur, as is clear from the
table.
n 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Pen) 3 5 7 8 10 11 13 14 15 17 18 19 20 21 23 24 25 26
l(n) 3 5 7 9 10 11 13 14 16 17 18 19 20 21 23 24 25 26
Q(n) 4 5 8 9 10 11 14 15 16 17 18 19 20 21 24 25 26 27
How l(n) behaves will be discussed in detail another time. But for the time
being try to work this out on your own. Try also to solve the following problems.
1. Verify the table above.
HINT. We outline the solution of this problem for n = 20. Here Pen) =
P(20) = 26.
Let us divide the 20 players into two groups: 16 in the first, and 4 in the second.
In the first group we use the standard method (see  1 and 2 of Chapter III) to
determine the first- and second-prize winners A and B. This requires 15 + 3 = 18
games. Here B defeats at most 4 players (see  3).
In the second group we determine t.he strongest player C by the Olympic system
(3 games). Here C defeats two opponents.
The next (22nd) game is between B and C. If B wins. then A is clearly the
champion, B wins second prize, and t.he 5 players who lost to B compete for the
third prize. Th(' third-prize winner can be found among them in the remaining 4
games.
On the other hand, suppose that C wins. Then the following situation arises
(see Figure 1): the players A. B, C, D, E, and F compete for the first three places
(the arrows point from the winner to the loser). There is a 23rd game between
D and E; suppose that E wins (the case when D wins is simpler and is handled
similarly) .
The 24th game is between A and E. If E wins, then C is the champion, E
is in second place, and A, D, and F compete for third place. The third prize is
determined in the remaining 2 games.
If A wins the 24th game, then (see Figure 2) A and C play for the first two
places, and Band E for the third place. The top three places are determined by

WHO WILL GO TO RIO?
45
A
f
FIGURE 2
these two games (between A and C and between B and E). Thus, 1(20) = 26 =
P(20).
The rules just given differ sharply from the standard rules in Chapter III.
According to the standard rules, players who have lost at least one game do not
take part in subsequent games until a champion is determined. Only by dropping
this we have been able to determine the first three places among 20 players in 26
(and not 27) games.
2. Prove that the first- and second-prize winners among n chess players can be
determined with certainty in l(n] + n - 2 games, and that it may not be possible to
determine them in fewer games.
3. Suppose that we want to determine the k strongest among n chess players
(the 1st-, 2nd-, . .. , kth-prize winners). Prove that:
a) this can be done with certainty in (k - l)l (n] + n - k games;
b) if R < l(n(n - 1)... (n - k + 2)] + n - k, then the results of R games can
turn out to be such that this cannot be done.
HINT. In b) we recommend arguing as in Chapter II, considering "teams"
(A h A2' . . . ,Ak-l) consisting of k - 1 players each. The total number of such
teams is n(n - 1)... (n - k + 2).


From the Life of Units
A. L. TOOM
"Alas!" said the Saturnian, "none of us live for more than five
hundred annual revolutions of the sunj . .. our existence is a point,
our duration an instant, our globe an atom."
Voltaire, /IIIicromegas
Not so long agod it became known that certain seemingly quite different phe-
nomena and processes that occur in life, for example, transfonnations of polymers,
vital activity of biological tissues, crystal growth, and even the operation of comput-
ers in which calculations take place simultaneously in all the working cells (such a
computer does not yet exist, but its construction would be a fascinating possibility)
have nevertheless something in common. This common property is revealed when
an attempt is made to describe the given processes in the language of mathematics
and to create what researchers call a mathematical model.
The well-known Soviet physicist Va. I. Frenkel' said that a mathematical model
should be more like a caricature than like a "realistic" picture. The main require-
ment of a model is simplicity: life processes are so complex that a realistic model
yields to mathematical study with difficulty. Very widespread at present are so-
called "lattice models" describing processes that take place on a lattice of identical
"cells". In such models there are difficulties already when each cell has only two
possible states. This is what we shall discuss below.
Colonies and operators
For a mathematician a piece of checked paper harbors many fascinating possi-
bilities. We make use here of one of them. Open a page of a notebook of checked
paper. You see on it a network of vertical and horizontal lines. For brevity we call
the intersection points nodes. Let us imagine a world consisting solely of all these
nodes. True, we do imagine the page here to be infinite. Suppose that some beings,
called units, can live at these nodes. In figures we denote the units by circles as in
Figure 1. Only one unit can be at a node at anyone time, and if there is not a unit
at a node, then there is a zero there. The collection of all nodes occupied by units
will be called a colony. If there are finitely many units, then we say that the colony
is finite. If there are no units at all, then we say that the colony is empty. (Like
the space, the time is discrete, that is, it can be counted by integers: 0,1,2.... .)
The Russian original is published in Kvant 1974, no. 9, pp. 31-39.
17

48
A. L. TO OM
y
.. L#
,. ".
.. "'''' , .. " "'''
#' 1">" #' '" " X
'" " '" " "'''
,. '\ ,. '" '" '\
FIGURE 1
An operator P must be given, that is, a rule which, for any colony K existing at
some time t, determines what colony P K is obtained from it at the next moment
of time t + 1.
Suppose that such an operator P is given. The basic question we are trying to
answer is the following. For the given operator P is there a finite colony that does
not die out, that is, a finite colony K such that no matter how many times P is
applied to it, the result will always be a nonempty colony? Or, on the contrary, is
the operator P such that every finite colony dies out over some time interval, that
is, not a single unit is left?
Let us start by analyzing two examples. We introduce coordinate axes by taking
one of the nodes as the origin 0, the axis of abscissas to the right and the axis of
ordinates upwards as usual (see Figure I), and a side of a cell to be of length 1.
EXAMPLE 1. Suppose that at time t + 1 there is a unit at the node A = (x, y)
if and only if most of the following five nodes were occupied by units at time t: A
and its four neighbors, namely, (x+ I, y) to the right, (x-I, y) to the left, (x, y+ 1)
above, and (x, y - 1) below. This defines the operator P.
EXERCISE 1. What do the colonies in Figure 1 (tbe circles and the crosses)
generate under the action of this operator? Follow the further evolution of the
colonies. For this operator does there exist a finite colony that does not die out?
EXAMPLE 2 (see Problem M215). Suppose that at time t + 1 there is a unit at
the node A = (x, y) if and only if most of the following three nodes were occupied
by units at time t: A and its two neighbors (.1' + 1, y) and (.r. y + 1) to the right
and above. This defines the operator P.
It follows from the solution of Problem fvl215 (published in I<vant 1974, no. 3)
that under the action of this operator every finite colony dies out. (Verify this for
the colony in Figure 1.) We shall prove this fact once more, by a method which
will be useful to us in what follows.
Let us look at tile evolution of colonies of a special form that fill isosceles right
triangles with legs directed to the right and upwards from the vertex of the right
angle (FigUl.e 2). It turns out that each such triangle passes at the next moment of
time into a triangle of the same form, but with legs shorter by one. The smallest
triangle with legs of length 1 passes into a single point, and it disappears at the
next step. (Verify this, by tracing the evolution of Figure 2.) Therefore, each such
triangle dies out in a time equal to the original length of the legs.

FROM THE LIFE OF UNITS
49


1' r\

FIGURE 2
"
"
r\


'"
FIGURE 3
Now take an arbitrary finite colony K. It can be included in an isosceles right
triangle, as follows from Figure 3. Then the colony obtained from it at the next
moment will be inside a smaller triangle of the same form, and so on.
Here we have used an important property of the operator P: if a colony Kl is
a part of a colony K 2 (this can be written as Kl C K 2 ), then P Kl is a subset of
P K2: P Kl C P K 2 (the possibility that P Kl coincides with P K2 is not excluded).
We call this property, which can be written briefly as
]{l C K 2 => PI\l C PK2,
the monotonicity of the operator P. Only monotone operators will be considered
in this article.
For nonmonotone operators the question of when there are finite colonies that
do not die out has not been solved in general form, and is possibly very difficult.
Interesting and extensive material on the investigation of a particular nonmonotone
operator, which has come to be called "The Game of Life" , is contained in an article
by M. Gardner in the October 1970 issue of Scientific American (p. 120).
We now describe the precise form of the operator P to be considered.
Let 0 be the "zero" node, the origin of coordinates. Part of the description
of P is a list U consisting of the r nodes Ul, . . . , U r on whose states at time t the
state of the node 0 at time t + 1 depends. In Example 1 the number of these nodes
is r = 5, and in Example 2 it is r = 3. The state of any node A at time t + 1
depends on the states of the nodes A + Ul, . . . , A + U r at time t. The symbol +
here denotes addition of vectors. For example, if A = (x, y) and Ul = (x', y'), then
A+Ul = (x+x',y+y').

so
A. L. TOOM
EXERCISE 2. Write out the coordinates of the vectors UI, . . . ,US in Example 1
and the vectors Ul! U2, U3 in Example 2.
Besides the list U, the specification of P includes the function determining
just how the state of a node A at time t + 1 depends on the states of the nodes
A + UI,..., A + U r at time t. To specify this function we must indicate what will
be at A (a unit or a zero) at time t + 1 for each combination of units and zeros
at the nodes A + UI, . . . , A + U r at time t. There are 2 r such combinations in all.
For example, we can make a table in which there is either a unit or a zero opposite
each combination of units and zeros, as done in Table 1 (verify that the function
given by this table determines the operator P in Example 2). It is not necessary to
make a table, of course. We can give the function verbally, though in such a way
that such a table could be uniquely determined by the verbal description.
Functions 1 = f(ab." ,a r ) whose arguments and values take only the two
values 0 and 1 are called Boolean or binary functions. A Boolean function is said
to be monotone if
f(al,...,a r ) < I(a,...,a)
whenever
al < a,. . . ,a r < a.
As already mentioned, we consider only monotone operators. They are given by
monotone functions. Moreover, we set 1(0,...,0) = 0 and f(I,..., 1) = 1.
These restrictions are not essential, since the only monotone fWlctions not sat-
isfying them are the constants-the functions taking only one value (always zero or
always one). The constant functions are very simple, and therefore uninterest.ing.
TABLE 1
States of nodes
at time t t+l
(0,0) (0,1) (1,0) (0,0)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
EXAMPLE 3. Suppose that at time f + 1 there is a zero at the node A = (x, y)
if and only if at time t at least one of the following two conditions holds:
a) there arc zeros at both the nodes (x, y) and (x, y + 1);
b) there arc zeros at both the nodes (x + 1, y) and (x + 1, y + 1).
This defines the operator P.
EXERCISE 3. a) Trace the evolution of the colonies in Figure 1 under the action
of this operator. Does one not get the impression that the colonies flatten out from
the right side but stretch upward?

FROM THE LIFE OF UNITS
51
b) Prove that every finite colony dies out under the action of the operator in
Example 3.
EXAMPLE 4. Suppose that at time t + 1 there is a zero at the node A = (x, y)
if and only if at time t at least one of the following two conditions holds:
a) there are zeros at both the nodes (.t., y) and (x + 1, Y + 1);
b) there are zeros at both tbe nodes (x + 1, y) and (x, y + 1).
This defines the operator P.
For this operator there do exist finite colonies that do not die out. It is true
that they are constantly changing, but they never become extinct. Find one of
t.hem.
2. Zero sets. The survival theorem
We now remind ourselves that, besides the nodes, there are also other points
in the plane. From the point of view of the units living only at nodes, of course, no
other points exist in natm'e, but for us they do exist. We shall consider all possible
geometric figures-sets of points in the plane. A figure M will be said to be filled
by zeros if there are zeros at all the nodes contained in this figure.
DEFINITION 1. A figure M is called a zero figure (for a given operator P) if
there will be a zero at the node 0 at time t + 1 whenever M is filled by zeros at
time t.
For instance, in Examples 1 or 2 a figure is a zero figure if it contains most of
the five (in Example 1) or three (in Example 2) nodes making up the set U.
For a line I drawn in the plane we define a half-plane to be the set of points
located on one side of the line, including the line itself.
Corresponding to Definition 1, a half-plane is called a zero half-plane if there
will be a zero at the node 0 at time t + 1 whenever it is filled by zeros at time t.
Let Up be the intersection of all the half-planes that are zero half-planes for
the given operator P.
SURVIVAL THEOREM. Every finite colony dies out under the action of the op-
erator P if and only if the set Up is empty.
EXERCISE 4 (Verification of the theorem for examples 1-4). Prove the following
assertions.
a) In Example 2 the three half-planes shaded in FigUl'e 4 are zero half-planes.
In Example 3 the two half-planes shaded in Figure 5 are zero half-planes. In both
cases the shaded half-planes do not have common points, that is, their intersection is
empty. Therefore, the intersection Up of all the zero half-planes is empty. According
to the theorem, all finite colonies die out.
b) In Example 1 the set Up consists of the single point 0 (and, according to
the theorem, there is a finite colony that does not die out).
In Example 4 the set Up consists of the single point  = (, ). (This is not a
node, which is why nodes were not enough for us!)
In Example 1 the point 0 is in Up, and a finite colony that does not die out
remains in place. In Example 4 the simplest colony that does not die out consists
of four nodes: the vertices of a unit square (Figure 6). At the next moment of time
it generates a "cross", and this cross in tun1 generates the same square, but shifted

S2
A. L. TO OM
y
, 

J I" 
 
III
,   X
,'\. ,'\.'\. ,"''' ""
.'\. '\., ,'\. ,'\. 'I.'\.'\.
., m ,
 

FIGURE 4
y
 '"
 [.,;
 
 ""
, [.,;
  x
,
 ""
, ,
, 
;.I
",
FIGURE 5
one unit to the left and downward. We say that a colony I{ fills a figure M if it
contains all the nodes in M. Both the cross and the square in Figure 6 can be
represented as a colony filling identical figures-the squares shown in these figures.
Thus, the colonies generated at successive moments of time can be represented as
filling one and the same square, shifted by the vector -( = (-, -) in unit time.
Note that the sides of this square are parallel to the lines Ui, where Ui E U. In
Example 1 the sides of the unit square fillcd by the colony are also parallel to the
lines uiO.
EXERCISE 5 (teasing). If you were a unit and lived in the world ruled by the
operator in Example 4, then would the point  = (4, 4) exist for you or not?
3. Convex sets and convex hulls
A set M of points in the plane is said to be convex if it satisfies the following
condition:

FROM THE LIFE OF UNITS
53
y y  y
.A
< > / , A
V , 7 < >
x x V ,.
x
FIGURE 6
..1
"u.
v .. .:,
Al 0:..... l' A ':., tA 'lion. '» A4
.... . ..... .e'\
: 2. D'"
-..... 0 ..:
.n _ . .. .,..... '/
.. . ,, .
,.. ..:' / 'A
r-d
1A6
FIGURE 7
For any two points A and B in M, all the points of the straight line segment
with endpoints A and B belong to M.
EXERCISE 6. Prove that every half-plane is a convex set.
EXERCISE 7. Prove that an intersection of convex sets is a convex set.
EXERCISE 8. In some textbooks a polygon is defined to be convex if it is located
on one side of the line drawn through each of its sides. Prove that a polygon is
convex in this sense if and only if the set of points located on or inside its contour
is convex.
Thus, if a convex set M contains the points At,..., A k , then it contains also
all the segments with endpoints at these points, and all the triangles with vertices
at these points. The union of all the points At,..., Ak, all the segments with
endpoints at these points, and all the triangles with vertices at these points is
called the convex hull of AI,.. . ,Ak (the convex hull of some points AI,.. . , A6 is
pictured in Figure 7). It can be said that the convex hull of a finite set of points is
what is necessarily contained in every convex set containing the points.
EXERCISE 9. a) Prove that a set of four points (in the plane) can always be
partitioned into two subsets whose convex hulls intersect.
b) The same statement when the set has n > 4 points.
Recall the definition of the set Up. To find Up from this definition we must
construct all zero half-planes, and there are infinitely many of them. True, in
Examples 1-4 we knew how to find Up, but it is not yet clear how to do this in the

54
A. L. TOOM
l
TT  W
- I:{
,;..
::: '(
"TV e
  ;;..

iffY  fA
FIGURE 8
general case. It turns out that with the help of convex hulls it is now possible to
construct Up for any operator P.
We consider all subsets of U. According to Definition 1, a set U' C U is called
a zero set if the fact that U' is filled by zeros at time t implies that there is a zero
at 0 at the time t + 1.
LEMMA 1. Up coincides with the intersection of the convex hulls of all the zero
subsets ofU.
Prove this lemma yourself.
HINT. A half-plane is a zero half-plane if and only if it entirely contains at
least one zero subset of U.
Using Lenulla 1, we can construct Up from any operator P given by its set U
and function f. Namely, we must write out all the subsets of U (there are 2 r of
thcm), then use our knowledge of f to choose the zero subsets among them, then
construct their convex hulls (each is a polygon, segment, or point), and then find
their intersection.
COROLLARY. The set Up is always the intersect-ion of a finite number of zero
half-planes.
EXERCISE 10. Using the method following from Lemma 1, construct again the
set Up for Examples 1-4.
4. Proof of the survival theorenl. The fanliliar
Helly theorem in the role of a deus ex machina
A. Let us begin by finding ("onditions under which all finite colonies die out.
First of all we makc somc important rema.rks. Suppose that a zero half-plane IT is
boundcd by a line l. In this rase' if IT waN fillcd with zeros at time t, then at time
t + 1 there will b(' a zero not only at thc node 0, but also at every node A for which
the line AO is parallel to l (Figure 8).
Further, we denute by v a vect,or by which l must be shifted in a parallel way in
order to pa')S through 0 in its new position (there are infinitely many such vectors,
but v can be taken to be anyone of them). If at time t the zero half-plane IT is
filled by zeros, then at time t + 1 the half-plane IT + v obtained from IT by shifting
it by the vector v will be filled by zeros (IT + v is shaded in Figure 8). Similarly, if

K vant SeIecta: Combinatorics, I
Serge Tabachnikov, Editor
There is a tradition in Russia that holds that mathematics can be both challenging and fun.
One fine outgrowth of that tradition is the magazine. K1 1 allt. which has been enjoyed by
many of the best students since its founding in 1970. The articles in K1 ' allt assume only a
minimal background. that of a good high school student, yet are capable of entertaining
mathematicians of almost any level. Sometimes the articles require careful thought or a
moment's work with a pencil and paper. However, the industrious reader will be gener-
ously rewarded by the elegance and beauty of the subjects.
This book is the third collection of articles from Kvant to be published by the AMS. The
volume is devoted mainly to combinatorics and discrete mathematics. Several of the topics
are well known: nonrepeating sequences. detecting a counterfeit coin, and linear inequal-
ities in economics, but they are discussed here with the entertaining and engaging style
typical of the magazine. The two previous collections treat aspects of algebra and analysis,
including connections to number theory and other topics. They were published as Volumes
14 and 15 in the Mathematical World series.
The articles are written so as to present genuine mathematics in a conceptual, entertaining,
and accessible way. The books are designed to be used by students and teachers who love
mathematics and want to study its various aspects, deepening and expanding upon the
school curriculum.
ISBN 0-8218-2171-7
MAWRLD/17
.
.. .
. . .. .
.
.: ..
.
". to:
_.e.
AMS on the Web
www.alDs.org
. . a. .

K vant SeIecta: Combinatorics, I
Serge Tabachnikov, Editor
There is a tradition in Russia that holds that mathematics can be both challenging and fun.
One fine outgrowth of that tradition is the magazine. K1 1 allt. which has been enjoyed by
many of the best students since its founding in 1970. The articles in K1 ' allt assume only a
minimal background. that of a good high school student, yet are capable of entertaining
mathematicians of almost any level. Sometimes the articles require careful thought or a
moment's work with a pencil and paper. However, the industrious reader will be gener-
ously rewarded by the elegance and beauty of the subjects.
This book is the third collection of articles from Kvant to be published by the AMS. The
volume is devoted mainly to combinatorics and discrete mathematics. Several of the topics
are well known: nonrepeating sequences. detecting a counterfeit coin, and linear inequal-
ities in economics, but they are discussed here with the entertaining and engaging style
typical of the magazine. The two previous collections treat aspects of algebra and analysis,
including connections to number theory and other topics. They were published as Volumes
14 and 15 in the Mathematical World series.
The articles are written so as to present genuine mathematics in a conceptual, entertaining,
and accessible way. The books are designed to be used by students and teachers who love
mathematics and want to study its various aspects, deepening and expanding upon the
school curriculum.
ISBN 0-8218-2171-7
MAWRLD/17
.
.. .
. . .. .
.
.: ..
.
". to:
_.e.
AMS on the Web
www.alDs.org
. . a. .

K vant SeIecta: Combinatorics, I
Serge Tabachnikov, Editor
There is a tradition in Russia that holds that mathematics can be both challenging and fun.
One fine outgrowth of that tradition is the magazine. K1 1 allt. which has been enjoyed by
many of the best students since its founding in 1970. The articles in K1 ' allt assume only a
minimal background. that of a good high school student, yet are capable of entertaining
mathematicians of almost any level. Sometimes the articles require careful thought or a
moment's work with a pencil and paper. However, the industrious reader will be gener-
ously rewarded by the elegance and beauty of the subjects.
This book is the third collection of articles from Kvant to be published by the AMS. The
volume is devoted mainly to combinatorics and discrete mathematics. Several of the topics
are well known: nonrepeating sequences. detecting a counterfeit coin, and linear inequal-
ities in economics, but they are discussed here with the entertaining and engaging style
typical of the magazine. The two previous collections treat aspects of algebra and analysis,
including connections to number theory and other topics. They were published as Volumes
14 and 15 in the Mathematical World series.
The articles are written so as to present genuine mathematics in a conceptual, entertaining,
and accessible way. The books are designed to be used by students and teachers who love
mathematics and want to study its various aspects, deepening and expanding upon the
school curriculum.
ISBN 0-8218-2171-7
MAWRLD/17
.
.. .
. . .. .
.
.: ..
.
". to:
_.e.
AMS on the Web
www.alDs.org
. . a. .

K vant SeIecta: Combinatorics, I
Serge Tabachnikov, Editor
There is a tradition in Russia that holds that mathematics can be both challenging and fun.
One fine outgrowth of that tradition is the magazine. K1 1 allt. which has been enjoyed by
many of the best students since its founding in 1970. The articles in K1 ' allt assume only a
minimal background. that of a good high school student, yet are capable of entertaining
mathematicians of almost any level. Sometimes the articles require careful thought or a
moment's work with a pencil and paper. However, the industrious reader will be gener-
ously rewarded by the elegance and beauty of the subjects.
This book is the third collection of articles from Kvant to be published by the AMS. The
volume is devoted mainly to combinatorics and discrete mathematics. Several of the topics
are well known: nonrepeating sequences. detecting a counterfeit coin, and linear inequal-
ities in economics, but they are discussed here with the entertaining and engaging style
typical of the magazine. The two previous collections treat aspects of algebra and analysis,
including connections to number theory and other topics. They were published as Volumes
14 and 15 in the Mathematical World series.
The articles are written so as to present genuine mathematics in a conceptual, entertaining,
and accessible way. The books are designed to be used by students and teachers who love
mathematics and want to study its various aspects, deepening and expanding upon the
school curriculum.
ISBN 0-8218-2171-7
MAWRLD/17
.
.. .
. . .. .
.
.: ..
.
". to:
_.e.
AMS on the Web
www.alDs.org
. . a. .

K vant SeIecta: Combinatorics, I
Serge Tabachnikov, Editor
There is a tradition in Russia that holds that mathematics can be both challenging and fun.
One fine outgrowth of that tradition is the magazine. K1 1 allt. which has been enjoyed by
many of the best students since its founding in 1970. The articles in K1 ' allt assume only a
minimal background. that of a good high school student, yet are capable of entertaining
mathematicians of almost any level. Sometimes the articles require careful thought or a
moment's work with a pencil and paper. However, the industrious reader will be gener-
ously rewarded by the elegance and beauty of the subjects.
This book is the third collection of articles from Kvant to be published by the AMS. The
volume is devoted mainly to combinatorics and discrete mathematics. Several of the topics
are well known: nonrepeating sequences. detecting a counterfeit coin, and linear inequal-
ities in economics, but they are discussed here with the entertaining and engaging style
typical of the magazine. The two previous collections treat aspects of algebra and analysis,
including connections to number theory and other topics. They were published as Volumes
14 and 15 in the Mathematical World series.
The articles are written so as to present genuine mathematics in a conceptual, entertaining,
and accessible way. The books are designed to be used by students and teachers who love
mathematics and want to study its various aspects, deepening and expanding upon the
school curriculum.
ISBN 0-8218-2171-7
MAWRLD/17
.
.. .
. . .. .
.
.: ..
.
". to:
_.e.
AMS on the Web
www.alDs.org
. . a. .

K vant SeIecta: Combinatorics, I
Serge Tabachnikov, Editor
There is a tradition in Russia that holds that mathematics can be both challenging and fun.
One fine outgrowth of that tradition is the magazine. K1 1 allt. which has been enjoyed by
many of the best students since its founding in 1970. The articles in K1 ' allt assume only a
minimal background. that of a good high school student, yet are capable of entertaining
mathematicians of almost any level. Sometimes the articles require careful thought or a
moment's work with a pencil and paper. However, the industrious reader will be gener-
ously rewarded by the elegance and beauty of the subjects.
This book is the third collection of articles from Kvant to be published by the AMS. The
volume is devoted mainly to combinatorics and discrete mathematics. Several of the topics
are well known: nonrepeating sequences. detecting a counterfeit coin, and linear inequal-
ities in economics, but they are discussed here with the entertaining and engaging style
typical of the magazine. The two previous collections treat aspects of algebra and analysis,
including connections to number theory and other topics. They were published as Volumes
14 and 15 in the Mathematical World series.
The articles are written so as to present genuine mathematics in a conceptual, entertaining,
and accessible way. The books are designed to be used by students and teachers who love
mathematics and want to study its various aspects, deepening and expanding upon the
school curriculum.
ISBN 0-8218-2171-7
MAWRLD/17
.
.. .
. . .. .
.
.: ..
.
". to:
_.e.
AMS on the Web
www.alDs.org
. . a. .

K vant SeIecta: Combinatorics, I
Serge Tabachnikov, Editor
There is a tradition in Russia that holds that mathematics can be both challenging and fun.
One fine outgrowth of that tradition is the magazine. K1 1 allt. which has been enjoyed by
many of the best students since its founding in 1970. The articles in K1 ' allt assume only a
minimal background. that of a good high school student, yet are capable of entertaining
mathematicians of almost any level. Sometimes the articles require careful thought or a
moment's work with a pencil and paper. However, the industrious reader will be gener-
ously rewarded by the elegance and beauty of the subjects.
This book is the third collection of articles from Kvant to be published by the AMS. The
volume is devoted mainly to combinatorics and discrete mathematics. Several of the topics
are well known: nonrepeating sequences. detecting a counterfeit coin, and linear inequal-
ities in economics, but they are discussed here with the entertaining and engaging style
typical of the magazine. The two previous collections treat aspects of algebra and analysis,
including connections to number theory and other topics. They were published as Volumes
14 and 15 in the Mathematical World series.
The articles are written so as to present genuine mathematics in a conceptual, entertaining,
and accessible way. The books are designed to be used by students and teachers who love
mathematics and want to study its various aspects, deepening and expanding upon the
school curriculum.
ISBN 0-8218-2171-7
MAWRLD/17
.
.. .
. . .. .
.
.: ..
.
". to:
_.e.
AMS on the Web
www.alDs.org
. . a. .

K vant SeIecta: Combinatorics, I
Serge Tabachnikov, Editor
There is a tradition in Russia that holds that mathematics can be both challenging and fun.
One fine outgrowth of that tradition is the magazine. K1 1 allt. which has been enjoyed by
many of the best students since its founding in 1970. The articles in K1 ' allt assume only a
minimal background. that of a good high school student, yet are capable of entertaining
mathematicians of almost any level. Sometimes the articles require careful thought or a
moment's work with a pencil and paper. However, the industrious reader will be gener-
ously rewarded by the elegance and beauty of the subjects.
This book is the third collection of articles from Kvant to be published by the AMS. The
volume is devoted mainly to combinatorics and discrete mathematics. Several of the topics
are well known: nonrepeating sequences. detecting a counterfeit coin, and linear inequal-
ities in economics, but they are discussed here with the entertaining and engaging style
typical of the magazine. The two previous collections treat aspects of algebra and analysis,
including connections to number theory and other topics. They were published as Volumes
14 and 15 in the Mathematical World series.
The articles are written so as to present genuine mathematics in a conceptual, entertaining,
and accessible way. The books are designed to be used by students and teachers who love
mathematics and want to study its various aspects, deepening and expanding upon the
school curriculum.
ISBN 0-8218-2171-7
MAWRLD/17
.
.. .
. . .. .
.
.: ..
.
". to:
_.e.
AMS on the Web
www.alDs.org
. . a. .

K vant SeIecta: Combinatorics, I
Serge Tabachnikov, Editor
There is a tradition in Russia that holds that mathematics can be both challenging and fun.
One fine outgrowth of that tradition is the magazine. K1 1 allt. which has been enjoyed by
many of the best students since its founding in 1970. The articles in K1 ' allt assume only a
minimal background. that of a good high school student, yet are capable of entertaining
mathematicians of almost any level. Sometimes the articles require careful thought or a
moment's work with a pencil and paper. However, the industrious reader will be gener-
ously rewarded by the elegance and beauty of the subjects.
This book is the third collection of articles from Kvant to be published by the AMS. The
volume is devoted mainly to combinatorics and discrete mathematics. Several of the topics
are well known: nonrepeating sequences. detecting a counterfeit coin, and linear inequal-
ities in economics, but they are discussed here with the entertaining and engaging style
typical of the magazine. The two previous collections treat aspects of algebra and analysis,
including connections to number theory and other topics. They were published as Volumes
14 and 15 in the Mathematical World series.
The articles are written so as to present genuine mathematics in a conceptual, entertaining,
and accessible way. The books are designed to be used by students and teachers who love
mathematics and want to study its various aspects, deepening and expanding upon the
school curriculum.
ISBN 0-8218-2171-7
MAWRLD/17
.
.. .
. . .. .
.
.: ..
.
". to:
_.e.
AMS on the Web
www.alDs.org
. . a. .

K vant SeIecta: Combinatorics, I
Serge Tabachnikov, Editor
There is a tradition in Russia that holds that mathematics can be both challenging and fun.
One fine outgrowth of that tradition is the magazine. K1 1 allt. which has been enjoyed by
many of the best students since its founding in 1970. The articles in K1 ' allt assume only a
minimal background. that of a good high school student, yet are capable of entertaining
mathematicians of almost any level. Sometimes the articles require careful thought or a
moment's work with a pencil and paper. However, the industrious reader will be gener-
ously rewarded by the elegance and beauty of the subjects.
This book is the third collection of articles from Kvant to be published by the AMS. The
volume is devoted mainly to combinatorics and discrete mathematics. Several of the topics
are well known: nonrepeating sequences. detecting a counterfeit coin, and linear inequal-
ities in economics, but they are discussed here with the entertaining and engaging style
typical of the magazine. The two previous collections treat aspects of algebra and analysis,
including connections to number theory and other topics. They were published as Volumes
14 and 15 in the Mathematical World series.
The articles are written so as to present genuine mathematics in a conceptual, entertaining,
and accessible way. The books are designed to be used by students and teachers who love
mathematics and want to study its various aspects, deepening and expanding upon the
school curriculum.
ISBN 0-8218-2171-7
MAWRLD/17
.
.. .
. . .. .
.
.: ..
.
". to:
_.e.
AMS on the Web
www.alDs.org
. . a. .

K vant SeIecta: Combinatorics, I
Serge Tabachnikov, Editor
There is a tradition in Russia that holds that mathematics can be both challenging and fun.
One fine outgrowth of that tradition is the magazine. K1 1 allt. which has been enjoyed by
many of the best students since its founding in 1970. The articles in K1 ' allt assume only a
minimal background. that of a good high school student, yet are capable of entertaining
mathematicians of almost any level. Sometimes the articles require careful thought or a
moment's work with a pencil and paper. However, the industrious reader will be gener-
ously rewarded by the elegance and beauty of the subjects.
This book is the third collection of articles from Kvant to be published by the AMS. The
volume is devoted mainly to combinatorics and discrete mathematics. Several of the topics
are well known: nonrepeating sequences. detecting a counterfeit coin, and linear inequal-
ities in economics, but they are discussed here with the entertaining and engaging style
typical of the magazine. The two previous collections treat aspects of algebra and analysis,
including connections to number theory and other topics. They were published as Volumes
14 and 15 in the Mathematical World series.
The articles are written so as to present genuine mathematics in a conceptual, entertaining,
and accessible way. The books are designed to be used by students and teachers who love
mathematics and want to study its various aspects, deepening and expanding upon the
school curriculum.
ISBN 0-8218-2171-7
MAWRLD/17
.
.. .
. . .. .
.
.: ..
.
". to:
_.e.
AMS on the Web
www.alDs.org
. . a. .

K vant SeIecta: Combinatorics, I
Serge Tabachnikov, Editor
There is a tradition in Russia that holds that mathematics can be both challenging and fun.
One fine outgrowth of that tradition is the magazine. K1 1 allt. which has been enjoyed by
many of the best students since its founding in 1970. The articles in K1 ' allt assume only a
minimal background. that of a good high school student, yet are capable of entertaining
mathematicians of almost any level. Sometimes the articles require careful thought or a
moment's work with a pencil and paper. However, the industrious reader will be gener-
ously rewarded by the elegance and beauty of the subjects.
This book is the third collection of articles from Kvant to be published by the AMS. The
volume is devoted mainly to combinatorics and discrete mathematics. Several of the topics
are well known: nonrepeating sequences. detecting a counterfeit coin, and linear inequal-
ities in economics, but they are discussed here with the entertaining and engaging style
typical of the magazine. The two previous collections treat aspects of algebra and analysis,
including connections to number theory and other topics. They were published as Volumes
14 and 15 in the Mathematical World series.
The articles are written so as to present genuine mathematics in a conceptual, entertaining,
and accessible way. The books are designed to be used by students and teachers who love
mathematics and want to study its various aspects, deepening and expanding upon the
school curriculum.
ISBN 0-8218-2171-7
MAWRLD/17
.
.. .
. . .. .
.
.: ..
.
". to:
_.e.
AMS on the Web
www.alDs.org
. . a. .

K vant SeIecta: Combinatorics, I
Serge Tabachnikov, Editor
There is a tradition in Russia that holds that mathematics can be both challenging and fun.
One fine outgrowth of that tradition is the magazine. K1 1 allt. which has been enjoyed by
many of the best students since its founding in 1970. The articles in K1 ' allt assume only a
minimal background. that of a good high school student, yet are capable of entertaining
mathematicians of almost any level. Sometimes the articles require careful thought or a
moment's work with a pencil and paper. However, the industrious reader will be gener-
ously rewarded by the elegance and beauty of the subjects.
This book is the third collection of articles from Kvant to be published by the AMS. The
volume is devoted mainly to combinatorics and discrete mathematics. Several of the topics
are well known: nonrepeating sequences. detecting a counterfeit coin, and linear inequal-
ities in economics, but they are discussed here with the entertaining and engaging style
typical of the magazine. The two previous collections treat aspects of algebra and analysis,
including connections to number theory and other topics. They were published as Volumes
14 and 15 in the Mathematical World series.
The articles are written so as to present genuine mathematics in a conceptual, entertaining,
and accessible way. The books are designed to be used by students and teachers who love
mathematics and want to study its various aspects, deepening and expanding upon the
school curriculum.
ISBN 0-8218-2171-7
MAWRLD/17
.
.. .
. . .. .
.
.: ..
.
". to:
_.e.
AMS on the Web
www.alDs.org
. . a. .

. . . - '. I. .
. ...1....1.... I
.
I
I a I
t!....- .. .
.
1-.. . ., . . .

. . . - '. I. .
. ...1....1.... I
.
I
I a I
t!....- .. .
.
1-.. . ., . . .

. . . - '. I. .
. ...1....1.... I
.
I
I a I
t!....- .. .
.
1-.. . ., . . .

. . . - '. I. .
. ...1....1.... I
.
I
I a I
t!....- .. .
.
1-.. . ., . . .

. . . - '. I. .
. ...1....1.... I
.
I
I a I
t!....- .. .
.
1-.. . ., . . .

. . . - '. I. .
. ...1....1.... I
.
I
I a I
t!....- .. .
.
1-.. . ., . . .

. . . - '. I. .
. ...1....1.... I
.
I
I a I
t!....- .. .
.
1-.. . ., . . .

. . . - '. I. .
. ...1....1.... I
.
I
I a I
t!....- .. .
.
1-.. . ., . . .

. . . - '. I. .
. ...1....1.... I
.
I
I a I
t!....- .. .
.
1-.. . ., . . .

. . . - '. I. .
. ...1....1.... I
.
I
I a I
t!....- .. .
.
1-.. . ., . . .

. . . - '. I. .
. ...1....1.... I
.
I
I a I
t!....- .. .
.
1-.. . ., . . .

. . . - '. I. .
. ...1....1.... I
.
I
I a I
t!....- .. .
.
1-.. . ., . . .

. . . - '. I. .
. ...1....1.... I
.
I
I a I
t!....- .. .
.
1-.. . ., . . .

FROM THE LIFE OF UNITS
55
II .
Ij VII  
-=
V/J.B -:. 
XL1 
] 1 1= bI' 'J'I 11 1 2
1-= W 'I(j

==  'IJ.J.t   
- 
V,
A !7"f' ' y ll3 '<J r/

FIGURE 9
I-=

lli -= r



=¥
7
=
,j,
, B'.=W

-II2
 ......"y .......,.
-
 .....,
["r-V

..."'-
............. .'
.'
II3
f
I
A' I'X" .....
FIGURE 10
at time t the half-plane II + w is filled by zeros, then at time t + 1 the half-plane
II + w + v is filled by zeros.
LEMMA 2. Given a triangle ABC, assume that the three half-planes IIbIl2,
bounded by the lines AB, BC, AC and located outside ABC are zero half-planes for
the operator P (they are shaded in Figure 9). Then every finite colony of units dies
out under the action of this operator.
PROOF. Let K be a finite colony. We shift the zero half-planes lIb 112, 113 by
vectors Wl, W2, W3 such that the resulting half-planes II = III +Wl, 11 2 = II2+ w 2,
II = 113 + W3 do not have points in common with Ii, that is, they are filled by
zeros (Figure 10). The boundary lines of 11 1 ,11 2 ,11 3 fornl a triangle A' B' C' similar
to ABC (and also oriented in the same way); denote the similarity coefficient by d.
We prove that the colony K dies out in a time not greater than d.
Let VI, V2, V3 be vectors that shift the half-planes 111.112,113 so that their
boundary lines pass through o. Fronl the similarity it then follows that if the half-
planes IlL 11 2 , II are shifted by the respective vectors dVb dV2. dV3, then their

56
A. L. TOOM
boundary lines will also pass through a single point; these same half-planes in the
new position cover the entire plane. But by our remarks, after t applications of
P the half-planes obtained from ITi,IT,n by shifting them by tVl,tv2,tva will
certainly be filled by zeros, and for t > d these half-planes cover the entire plane.
Hence, the whole plane is filled by zeros, which means that the colony has died out.
LEMMA 3. Suppose that two half-planes bounded by two parallel lines and dis-
joint from each other are zero half-planes for an operator P (as in Figure 5). Then
every finite colony of units dies out under the action of this operator.
Prove this lemma yourself.
HINT. Generalize the solution of Exercise 3.
Lemmas 2 and 3 can be combined into the following assertion.
LEMMA 4. If the intersection of three zero half-planes is empty, then every
finite colony of units dies out.
PROOF. If the intersection of three half-planes is empty, then either they are
arranged as in Figure 9, or some two of them are arranged as in Figure 5; but for
these two cases the assertion of Lemma 4 is proved.
B. Suppose now that Up contains at least one point. We prove that there then
exists a finite colony that does not die out.
LEMMA 5. Suppose that an infinite colony K fills (at time t) a half-plane IT
having at least one point in common with the set Up. Then the colony P K contains
the node O.
PROOF. Assume that P K does not contain O. Then there is a zero at 0 at
time t+ 1, that is, at time t some zero subset of U was entirely filled by zeros. Hence,
this zero subset did not have any points in common with IT, that is, it belonged
to the complement of IT. But the complement of IT is a convex set. Therefore, the
convex hull of this zero subset was also entirely contained in the complement of IT.
Hence (see Lemma 1), Up was entirely contained in the complement of IT, which
contradicts our assumption.
COROLLARY. Suppose that an infinite colony K fills a half-plane IT having at
least one point in common with the set A + Up, where A is a node. Then the colony
P K contains A.
The following statement is fundamental for the case B.
LEMMA 6. Suppose that the point { belongs to Up (like the point (, ) in
Example 4). Then there is a convex polygon M such that if a colony K fills M,
then the colony P K fills the polygon M -( (Figure 11), the colony p2 K fills M - 2£
and so on; in general, the colony pn K obtained from K in n units of time fills the
polygon M - n( obtained from M by a shift by the vector -n[ 1 FUrthermore, all
the colonies K, P K, p2 K, . .. are nonempty.
1 We are asserting that all the nodes belonging to M - n( are occupied by units, but possibly
not only those nodes: it is not excluded that there are units also outside this polygon.

FROM THE LIFE OF UNITS
57
y
/ l\. M
J( " V

4 ./ L\ M-
/PK " CI
,
0 /  x
p2i' CI 1""M-2
FIGURE 11
'- 
J 7  1'ס0o...
II" ,
\.
'1/ 1\
 \
1/  I,
.,
FIGURE 12
A particular consequence of this lemma is that if 0 belongs to Up I then there
is a "stable" colony that does not lose a single one of its nodes in the process of
evolution (but that possibly acquires new nodes).
PROOF. Note that we are not claiming to have found the smallest colony that
does not die out (as we did for Examples 1 and 4). It suffices for us to find anyone
such colony. Therefore, from the start we assume that M is very large. How large
we say below.
It suffices to prove the assertion of the lemma for n = 1 alone; for larger n this
will follow by induction. Accordingly, we assume that the colony K that exists at
time t fills M, and we prove that the colony P K fills the polygon M - (.
Suppose that some node A belongs to M - (see Figure 13). We show that A
is in PK (this is written as A E PK). Obviously, A +  E M. Denote by R the
largest of the distances from  to the nodes Ul, . . . , UTe Then the disk with center
A +  and radius R covers all the nodes A + Ul1 . . . ,A + UTe Choose M so large
that every disk of radius R centered inside M does not cover points of the sides
of M at all, or covers points only of one side of M, or covers points only of two
adjacent sides but no more. (Figure 12 shows a disk covering points of three sides
of a triangle-this Inust not be!) Let us consider the three cases.

58
A. L. TOOM
1VJ
/. A+ll.'
1 I ,
A+  
'",-  / I
I
A 0
M-
FIGURE 13
 ",.. """"""" I\.
.'- "  .'- ,,- ;& R  
 .'- l''- '-,
n \. A+ ) M
1'00.. 
- -
f
A 1
I
fo
M-
FIGURE 1-1
a) The disk centered at A +  with radius R is entirely inside M (Figure 13).
Then all the nodes A + 'il, are inside M. t.hat is. ther are all in 1\: hence, the node
A belongs to P I{ .
h) The' disk of radius R cent.C'l"cd at. A +  covers point.s of only one of the sides
of M (as in Figurc 14). Wc draw t.he linc l across t.his side. If t.he colony I( filled the
whole half-plane' II boundC'd by l (in Figure 1-.1 this half-plane is shaded), then the
colony P]{ would contain the node A by thc corollary to Lemma 5 (the half-plane
II contains the point A + , and hence intersects the set A + up). But the colony
P I{ will contain A also when I( fills only M, because the state of A at time t + 1
depends only on the states of the nodcs A + Ui at time t. and these nodes do not
belong to the diffcrencl' between II and M.
c) The disk of radius R with center A + { covers points of two adjacent sides of
M (Figure 15). We want to show that there is a unit at the node A at time t + 1

FROM THE LIFE OF UNITS
59
 ;:::..
....-
J ,   ';'<o-
--
A+.c   1:'-" M
Jt 
.?A+u z M"
   NILJ,
-
I    1:'--- 
  A 4
I

M- 0
FIGURE 15
if at time t there are units at those points A + Ul, . . . , A + U r in the intersection
of M with the disk. We prove that this actually holds even if there are units in a
smaller area: the intersection of the same disk with the polygon M I obtained from
M by a shift under which the common vertex of the two adjacent sides of M partly
covered by the disk goes to the point A +  (Figure 15). To this end we need to
impose on M one more, now the last, condition.
Let us draw lines through the point  and each of the nodes Ul, . . . , U r different
from  (if all the Ui are different from , then there are 7' lines; if one of them
coincides with , then there are r - 1 lines). We require that for each of these (7'
or 7' - 1) lines there be two sides of M parallel to it. Then each line parallel to the
line through  and SOllle one of the points Ul," . , U r different from  either does
not intersect M at all or has a whole segment in common with M. For example,
the square in Figure 6 (Example 4) satisfies this condition,
We now draw through the point A +  a line l having only A +  in common
with the polygon M I (see Figure 15). If the colony filled the whole half-plane IT
bounded by l (it is shaded in Figure 15), then by the corollary to Lemma 5. there
would be a unit at A at time t + 1. But the colony P ]( will contain the node A also
when ]( fills only M, since there are no nodes A + lit lying in IT but outside MI.
We prove this. Suppose that some node A + Ui is in the difference between IT and
MI. But at the same time it is in the disk of radius R centered at A+. Hence. the
node A + Ui lies in one of the two shaded sectors. Then the line passing tlu'ough
A + Ui and A +  has only one point in common with M / , which is impossible in
view of the choice of M. This proves Lemma 6
c. Belly's theorem. Thus, we have investigated the following two cases:
A) the intersection of some three zero half-planes is empty (Lemma 4);
B) the intersection of all zero half-planes is nonempty (Lemma 6).
It turns out that only these cases are possible. This follows from the well-known
theorem of Helly.
This is a very important and beautiful theorem, with many different formula-
tions, proofs, and applications. We need it only in the following variant.

60
A. L. TOOM
HELLY'S THEOREM. Suppose that there are n > 4 convex sets in the plane,
each three of which have a common point. Then all these n sets have a common
point.
Let us apply this to our case. By the corollary to Lemma 1, the set Up is the
intersection of finitely many half-planes. Suppose that the case B does not hold:
Up is empty. Then using Helly's theorem and arguing by contradiction, we get that
the intersection of some three zero half-planes is empty; but this is the case A. This
proves the survival theorem.

N onrepeating Sequences
G. A. GUREVICH
Arshon sequences
A sequence of digits is called a repeating sequence if it contains at least one
pair of identical groups of digits located one after the other. For example, the se-
quences 1, 2, 3, 4 , 2,3,4 ,2,1 and 1,2, 2, 7, 6 , 2, 7, 6 ,8 are repeating, but the sequences
4,2,1,2,3,4,2,3 and 3,2,3,1,2, 7 are not. We denote by B(n) the set of nonre-
peating sequences of length n, and by IB(n)1 the number of elements in this set.
It is intuitively clear that the longer a sequence is, the more likely that there
are two identical groups of digits appearing one after the other in it. Indeed, if we
write out at random a sufficiently long sequence, then the sequence will surely turn
out to be repeating.
We give this assertion a precise meaning.
PROBLEM 1. Prove that for any number E > 0 there is an n such that among
all sequences of length n the fraction of nonrepeating sequences is less than E, that
is, IB(n)lfl0n < E.
It is easy to prove that all sequences of length greater than three composed of
the two digits 1 and 2 are repeating.
However, one can compose an arbitrarily long nonrepeating sequence using
three different digits. This was proved in 1937 by the Soviet mathematician S. E. Ar-
shone He proposed the following inductive method for constructing nonrepeating
sequences.
Denote by Kl the nonrepeating sequence 1,2,3. Assume that the nonrepeating
sequence Kn has already been constructed. The sequence Kn+l is obtained from
it as follows.
If the number n + 1 is even and there is a 1 at the n + 1st place in Kn, then
adjoin the triple 3, 2, 1 to Kn; if there is a 2, then adjoin the triple 1, 3, 2; if there
is a 3, then adjoin the triple 2, 1, 3.
If the number n + 1 is odd and there is a 1 at the n + 1st place in Kn, then
adjoin the triple 1,2,3 to Kn; if there is a 2, then adjoin the triple 2,3,1; if there
is a 3, then adjoin the triple 3, 1, 2.
In particular,
K 2 = 1,2,3, 1,3,2
(n = 2 is even, and there is a 2 at the second place in K 1 ),
K3 = 1,2,3, 1,3,2,3, 1,2
The Russian original is published in KlIant 1975, no. 9 , pp. 7-11.
61

62
G. A. GUREVICH
(n = 3 is odd, and there is a 3 at the third place in [(2),
K4 = 1,2,3,1,3,2,3,1,2,3,2,1
(n = 4 is even, and there is a 1 at the fourth place in K 3 ), and so on.
The proof that the sequences obtained by Arshon's method are nonrepeating
is fairly cumbersome, and we shall not go through it. l
We now try to estimate the number IB(n)1 of nonrepeating sequences of length
n (in ten digits). If we can show that for any n this number is greater than zero,
then we shall have another (this time nonconstructive) proof of the existence of
arbitrarily long 110nrepeating sequences. In fact, we now derive the essentially
stronger inequality
(1)
IB(n)1 > Sn,
which 110t only proves the existence of arbitrarily long nonrepeating sequences, but
also gives us a fairly nice lower bound for these numbers.
Problem M310
We now recall Problem M310 from the UK vant Problem Book" in K vant 1975,
no. 2.
Prove that among n-digit numbers there are more than sn whose decimal ex-
pansions do not contain any group of digits (in particular, any digit) twice in suc-
cession.
It is clear that the solution of Problem M310 amounts to a proof of the in-
equality (1). We prove first a certain auxiliary inequality that will be useful to us
below.
An auxiliary inequality. Assume that all nonrepeating sequences of length n
have been written out (IB(n)1 in all), and that we want to write out all nonrepeating
sequences of length n + 1.
Let us take an arbitl'ary sequence al,... , an in B(n). and write ten new se-
quences of length n + 1:
ah'" ,an.O,
ah" ., an, 1,
ai, . . . , (I JJ . n.
We proceed in t.he same way with all the sequences in B( n). This gives us a certain
collection B* (n + 1) of sequences. Among them we choose those with two identical
digits at the end and denote the set of such sequences by BI(11 + 1). Similarly,
denot<, by B2( n + 1) the set of sequences in B* (n + 1) with the same subsequence of
length 2 appearing twice in succession at the end. In gcneral denote by B i (n + 1)
the set of sequences in B* (n + 1) with thc same subsequence of length i twice in
succession at the end. Since all the sequenccs in B* (n + 1) have length n + I,
[en + 1)/2] is the maximal i = nl for which Bi(n + 1) is not empty.
1 For a proof see Problem 124b of the book Nonelementary problems in an elementary pre-
sentation by A. M. Yaglom and I. M. Yaglom (Gostekbizdat, 1954 (Russian».

NONREPEATING SEQUENCES
63
All the sequences belonging to the sets B} (71. + 1), B 2 (n + 1), . . . ,Bnl (71. + 1) are
repeating. Prove that these sequences exhaust the repeating sequences ill B* (71. + 1)
and that B*(n + 1) contains all nonrepeating sequences of length 71. + 1.
Therefore, if we discard from B. (71. + 1) all the sequences belonging to the sets
Bi(n + 1), i = 1,..., nIt then we obtain the set B(n + 1). Consequently,
(2) IB(n + 1)1 > IB*(n + 1)1-IBI (71. + 1)1- . .. -IBnl (71. + 1)1.
QUESTION FOR THE READER. Can the sign > in (2) be replaced by =?
By the construction of the set B.(n+ 1) we have IB*(n+ 1)1 = 10'IB(n)I, and
we need only to estimate the number of elements in each of the sets Bi(n + 1). It
turns out that
(3)
IBi(n + 1)1 < IB(n+ 1- i)l.
The inequalities (2) and (3) imply an important inequality which we call an auxiliary
inequality:
(4) IB(n + 1)1 > 10 'IB(n)l- (IB(n)1 + IB(n - 1)1 + ... + IB(I)I).
Thus, we need to prove the inequality (3).
A little digression
Let A and B be two finite sets. We want to know which of them has more
elements. The first thing we think of is to count the number of clements in A
and B, and then compare the numbers obtained. But if a set contains very many
elements or has some Utricky" structure, then counting can be fairly complicated.
And we do not have any idea what to do if A and B are infinite. It turns out that
there is a universal method for comparing even infinite sets. We describe it using
an example.
Let A be a set of schoolchildren who come to a movie theater, and let B be
the set of seats. The children go in and try to find a seat. If some unoccupied
seats remain, then IBI > IAI. If all the seats are taken and some children remain
standing, then IAI > IBI. Finally, if it turns out that all the seats are occupied and
all the children are seated, then IAI = IBI.
What does this method consist of? We are placing elements of the set B into
correspondence with elements of the set A. If the elements of A are used up by
the elements of B, then IBI > IAI, but if the elements of B are used up, then
IAI > IBI. Here it is important that to different elements of A there correspond
different elements of B (we do not allow two kids to share one seat), and conversely,
to different elements of B there correspond different elements of A (we do not allow
one kid to occupy two seats at the same time). Such a correspondence is said to be
one-to-one.
Proof of the inequality (3)
Now we try to establish a one-to-one correspondence between the set Bi(n+ 1)
and part of the set B(n+l-i), i = 1,...,71.1' Recall that the sequences in B i (n+l)
have the form
(5)
a}, . . . , a" bit . . . ,bi, bit. . . . b r .

64
G. A. GUREVICH
where l + 2i = n + 1, and the sequence aI,..', at, bIt. . ., bi, bIt. .., bi-l is nonre-
peating. Hence, the sequence aI, . . . , al, b l , . . . ,b i is also nom"epeating. We associate
with the sequence (5) in Bi(n+ 1) the sequence aI,..., at, bIt..., bi in B(n+ I-i):
alo . . . , at, b l , . . . , b i , bIt . . . ,b i --. a}, . . . , al, b}, . . . , b i .
Obviously, this correspondence is one-to-one, and for each sequence in Bi(n + 1)
there is a corresponding sequence in B(n+l-i). Hence, IBi(n+I)1 < IB(n+I-i)l,
and this proves (3), and thus also (4).
Solution of Problem M310
We now prove (by induction on n) another inequality:
(6)
IB(n+ 1)1> 8.IB(n)l.
It is clear that the desired inequality (1) immediately follows from this since
IB(n)1 > 8 .IB(n - 1)1 > 8 2 .IB(n - 2)1 > ... > 8 n - 1 .IB(I)I
and IB(I)1 = 10.
Base of the induction. n = 1. We have IB(2)1 > 8 'IB(I)I since IB(I)I = 10
and IB(2)1 = 90.
Induction step. Suppose that we have already proved that
IB(n)1 > 8 .IB(n - 1)1,
IB(n -1)1 > 8 .IB(n - 2)1,
(7)
IB(2)1 > 8.IB(I)I.
We must prove the inequality (6).
It follows from (7) that
IB(n)1 > 8 i .IB(n - i)l,
or
(7') IB(n-i)1 < IB)I . i=I,...,n-l.
We substitute the estimates (7') found for IB(n - i)1 (i = 1,..., n - 1) in the
inequality (4), obtaining
IB(n+ 1)1> 10 .IB(n)I-IB(n)l. ( 1 +! +... +  ) .
8 8 n - 1
Since
1 1
1+-+...+-<2
8 8 n - 1 '
it follows that IB(n + 1)1 > 8 .IB(n)l. We now formulate some problems.
PROBLEM 2. Construct a nom"epeating sequence such that if any digit is ad-
joined to the end of it, then the resulting sequence is repeating.

NON REPEATING SEQUENCES
65
PROBLEM 3. Using Arshon's sequence, prove the existence of arbitrarily long
sequences composed using 1 and 2 in which there are no three identical groups of
digits appearing successively one after another.
PROBLEM 4. Prove that for any n there are more than 2 n nonrepeating se-
quences of length n composed of the four digits 1,2,3,4.
Problem 4 implies the existence of an arbitrarily long nonrepeating sequence of
four different digits. Arshon showed that in fact three digits suffice for the existence
of an arbitrarily long nonrepeating sequence.
Infinite nonrepeating sequences
Thus, we have proved the existence of arbitrarily long nonrepeating sequences.
In this section we prove the existence also of an infinite nonrepeating sequence (we
remark that the first does not yet imply the second).
PROBLEM 5. Prove that if there is at least one infinite nonrepeating sequence,
then there are infinitely many such sequences.
We denote by B the set of all finite nonrepeating sequences. Since B is infinite
and there are finitely many (10 in all) different digits, there is at least one digit,
say al, with which infinitely many of the sequences in B begin. We choose in B the
sequences that begin with al. This is an infinite set B(l). Similarly, there is a digit
G.2 that occurs in the second place of infinitely many of the sequences in B(l). We
choose in B(l) those sequences with second digit equal to G.2. This gives an infinite
set B(2), and so on.
We now consider the infinite sequence al, a2,'" and show that it is nonrepeat-
ing.
For this it suffices to show that for any n the finite sequence al, a2,"', an is
nonrepeating. But by construction all the sequences in B(n) begin with the sequence
all a2, . . . ,an, and B(n) is a subset of B, so all sequences in B(n) are nonrepeating.
But any beginning segment of a nonrepeating sequence is itself nonrepeating.
PROBLEM 6. Prove that among any eleven infinite decimal fractions there are
two fractions for which the digits coincide at infinitely many decimal places.
Generalization
We denote by P the property of being a nonrepeating sequence. Then the
assertion just proved has the following structure:
Premise Conclusion
[ There is an arbitrarily lOng ] => [ There is an infinite ]
sequence with property P sequence with property P
Does this assertion remain true if P is taken to be an arbitrary property of
numerical sequences? No, in the general case. We give an example: consider
the property of being a finite sequence. Obviously, there are arbitrary long finite
sequences, but there are no infinite finite sequences.
We observe now that in proving the existence of an infinite nonrepeating se-
quence we used only the following two facts, which are immediate consequences of
the definition of a nonrepeating sequence.

66
G. A. GUREVICH
1 0 . Every initial segment of a sequence with the property P also has this
property.
2°. An infinite sequence with arbitrarily long initial segments having the prop-
erty P also has this property.
DEFINITION. Any property of numerical sequences satisfying the conditions 1°
and 2° is called a hereditary property.
For example, the properties of not containing the digit 3, of consisting solely of
the digits 1, 2, 3, and of beginning with the digit 7 are hereditary properties, but the
properties of containing infinitely many digits 4 or ending with the digit 7 are not.
THEOREM. Let P be an arbitrary hereditary property. If there are arbitrarily
long sequences with the property P, then there is an infinite sequence with this
property.
We shall not dwell on the proof of this theorem, since it literally repeats the
proof presented in the preceding section.
Appendix
Let us consider numerical sequences composed of the three digits 1, 2, 3. We
shall call certain sequences (of length two and greater) forbidden. It is known
that any two forbidden sequences have different lengths. Sequences not containing
forbidden sequences will be called regular.
We turn again to the "K vant Problem Book" , Problem 1\1300 in K vant 1974.
no. 12 (see the article by A. M. Stepin and A. T. Tagi-Zade in this collection).
It follows from the assertion of Problem 1t1300 that there are arbitrarily long
regular sequences. But now we note that the property of being a regular sequence
is always a hereditary property (prove this)! Hence, the assertion that there are
arbitrarily long regular sequences can be replaced by a stronger assertion: there is
an infinite regular sequence, and the assertion of Problem 1\'1300 can be replaced
by the assertion that there is an infinite word without forbidden combinations of
digits.

Words with Restrictions
A. M. STEPIN AND A. T. TAGI-ZADE
The topic of this article is very close to that of the previous article "Nonre-
peating sequences" (by G. A. Gurevich) in this volume. It is devoted to proving
the existence of words of any length (also infinite) in a given alphabet with re-
strictions, and to estimating how many such words there are. In passing, Problem
lvI300 of the "Kvant Problem Book" in Kvant 1974, no. 12, is solved. Gurevich
proved the existence of and computed the number of sequences of any length (also
infinite) for which no group of digits appears twice in succession, and thereby solved
Problem lvI310. The combinatorial techniques used to solve Problems M300 and
M310 (and generalizations of them) find broad applications in serious mathematics:
group theory, theory of algebras, and algebraic number theory.
We begin our acquaintance with words and alphabets by analyzing Problem
lvI300 of the "Kvant Problem Book" in Kvant 1974, no. 12.
Problem M300
An alphabet consists of the three letters a, b, c. We define a word to be a sequence
of any length made up from these letters. Some combinations of letters (of length
two or more) are regarded as prohibited in forming words. It is !.,ilOwn that the words
in the list of prohibited letter combinations all have different lengths. Prove that
there are words of any length that do not contain prohibited letter combinations.
Problem lvI300 can be given another, more "entertaining" form:
A motorist is driving in a town with a rectangular street plan. When he comes
to an intersection, he either continues to drive straight or turns to the left or right
(he cannot make U-turns!), while taking into account that traffic rules forbid certain
combinations of these turns (to the left and to the right) and going straight. It is
known that all prohibited combinations have length at least 2 (for example, the
length of the combination "left-right" is equal to 2) and that there are no different
combinations of the same length. It turns out that if the town is sufficiently large
and if the motorist starts at the center, then in spite of all the prohibitions he can
drive through any specified number of intersections in the town.
Nevertheless, to solve Problem lvI300 it is convenient to use the terminology of
"letters" and "words".
The prohibited letter combinations will be called marked words, and a word
will be said to be good if it does not contain any marked words. The collection
The Russian original is published in Kvant 1975, no. 10, pp. 32-37.
fi7

68
A. M. STEPIN AND A. T. TAGI-ZADE
of marked words will be called the list of prohibitions or restrictions. A word
containing at least one marked word will be called bad.
We denote the number of good words of length I by G,. To prove the existence
of good words of any length it suffices to show that G, > 0 for any I. We now show
that there are fairly many good words of length l for any I: G, > 2 ' .
Let us order the marked words according to length and denote by Ii the length
of the ith marked word (li > i).
LEMMA 1.
(1)
G, > 3G'-1 - L G'-l,
2$l,'
( G 1 is clearly equal to 3; Go is set equal to 1). 1
PROOF. Note that all good words of length I are contained among the words
obtained by adjoining one of the letters a, b, c to the right end of a good word of
length 1- 1. This yields 3G'-1 words, among which there can be some bad words
of length l as well as good words. Let us estimate their number. Obviously, in a
bad word obtained in this way the marked word must occur only at the end, that
is, it is structured so that the last Ii letters form a marked word, while the first
I-Ii letters form a good word (2 < li < I). The number of bad words (of length I)
of the described type ending in the marked word of length Ii is not greater than the
number of good words of length l-li, that is, the number G'-l. (by assumption,
we have only one mal'ked word of length Ii). By adjoining one of the letters a, b, C
to the right ends of good words of length 1- 1 we obtain at most L2'.l G,_,.
bad words. Hence, among the 3G'-1 words of length I there are at least
3G'-1 - L G,-,.
2't'
good words.
The inequality (1) plays the main role in estimating the numbers G,.
LEMMA 2. For any positive integer l
(2)
G, > 2G'-1.
The proof of Lemma 2 is by induction.
Base of the induction. l = 1; obviousl)r, G 1 > 2Go.
Induction step. Assume that (2) holds for alll < L, that is,
(2')
GL > 2GL-lt GL-l > 2G L - 2 , ... , G 2 > 2G 1 .
We prove that G L + 1 > 2GL.
lIn general. the sum L2$1.$1 0,- " is not the same as L=2 0'-1: the first sum is over only
those values of L. with 2 ::: La ::; l for which there is a marked word of the corresponding length Ii
in the list of prohibitions (that is. Ii may possibly not take all the values 2,3.. . . t I): For example,
jf there are no marked words of length 3 in the list of prohibitions. then the term 0'-3 is absent
in the sum L2<1 <,0,-".
- ,-

WORDS WITH RESTRICTIONS
69
From (2') we have
GL > 2G L - 1 > 2 2 GL_2 > ... > 2 k GL_k,
that is,
(2")
GL-k < G L /2 k ,
where k = 1, . . . ,L.
By the estimate (2"), the inequality (1), and the footnote 1 we get 2
GL+1 > 3GL - E GL+1-1.
2SI,SL+1
1 1 1
> 3GL - :E GL-k > 3GL - GL:E 2 ' > GL(3 -1) = 2G L ,
k=1 k=1
and this is what was required to be proved.
Since G,- 1 > 2G,-2, G , - 2 > 2G,-3,. . . , G 1 > 2G o = 2, it follows that G, > 2 ' ,
and we get
THEOREM 1. Under the condition of Problem M300, for any 1 there are at least
2 ' good words of length l:
(3) G, > 2 ' .
This completes the proof of our theorem.
Infinite words
We now know that the "dictionary" of Problem M300 contains good words of
any length. But does it contain good words of infinite length?
Here we prove that if the list of marked words is finite (there are only finitely
many prohibited letter combinations), then there is also an infinitely long good
word. However, we remark at once that it is not really essential that the list of
marked words be finite: the assertion that there is an infinitely long good word
remains true even if there are infinitely many prohibitions. 3
Let us take the longest marked word (this can be done because by assumption
there are finitely many marked words); suppose that its length is n. Choose a
natural number N larger than n. Since we have good words of any length, let A
be a good word of length N(3 N + 1). We divide A into 3 N + 1 parts Bk of equal
length N: if A = Xl, X2, . . . ,X N(3N +1), where each Xi is one of a, b, or c, it follows
that Bk = XN(k-1)+hXN(k-1)+2,... ,XNk.
Since A is a good word, each Bk is also a good word, of length N. But our
alphabet has only three letters (a, b, c), and thus there are at most 3 N distinct good
words of length N. But we have obtained 3 N + 1 good words Bk, and hence two
of them must be identical, say Bnl = B n2 for some n1 < n2. We take the piece of
2Here the usual sum is meant: :E=1 GL-k = GL-l + GL-2 +... + GL-l.
3you can find a proof of this fact in G. A. Gurevich's article mentioned at the beginning.
In that article Gurevich actually proved that the property "there is an arbitrarily long good
word" implies the property "there is an infinitely long good word", that is, that the existence of
good words of any length is actually equivalent to the existence of an infinitely long good word.
However, we prove that under our assumptions there is a periodic infinite word, and we indicate
a method enabling us to construct such a word (as commonly said, we give a constructive proof).

70
A. M. STEPIN AND A. T. TAGI-ZADE
A. consisting of the parts Bk with indices k from nl through n2 - 1. This will be a
good word C of length nt > N:
C = xN(nl-l)+h... ,xN(n2-1).
Let us adjoin to the right end of C the same word C. This gives a word D of
length 2nt:
D = .I"N(nl-l)+h..., XN(n.2- 1 ) , xN(nl-l)+l,..., XN(n2-1).
We prove that. D is a good word.
Assume othenvise: D = CC is a bad word. Then it contains some marked
word. Obviously, this marked word must be contained in the "conjunction" of the
two good words C in such a way that its intersections with the "right" and "left"
words Care nonempty. But Bnl = Bn2' and the length of any marked word is less
than N. Hence, this marked word must be contained in the "conjunction" of the
parts B n2 - 1 and B n2 of the good word A; but this cannot be, and thus D is a good
word.
Of course, tbe infinite periodic word CC . . . C . .. with period C is also good,
and this gives us all that is needed.
Thus, our motorist can drive around town for an infinitely long time without
violating any traffic rules!
An interesting example
We return to the inequality (1) proved at the beginning of our solution of
Problem M300. Let us rewrite it as follows:
(4)
G, - 3G'-1 + L G,-I. > o.
2$l. $1
How sharp is this inequalit.y? Can the sign > in it be replaced by the sign =?
The answer is no in general, and we shall explain why.
The number 3G'-1 is the number of words obtained b). adjoining one of the
letters a, b, c to the right ends of good words of length I-I; all good words of length
l are among such words. By subtracting the numbers G,_,. from 3G'-h where the
li can take some of the values 2,3,..., l (possibly all these values). we in effect
eliminate from the constnlcted words of length 1 all the bad words obtained when
the marked word of length li is added to a good word of length 1 -lie However,
here it can happen that some bad word of length I is eliminated more than once
fr0111 the 3G'-1 words obtained. And if among our 3G'-1 words of length l there
arc no words obtained from good words of length 1 -I, by adjoining a marked word
of length II to the right end, then the corresponding number G,-,. need not be
subtracted at all.
However, under certain additional conditions on the list of prohibitions the
analogous recnrrence equalities
(4')
G, - 3G,- 1 + E G,-,. = 0
2$l.$l
will be satisfied for the numbers G, (I arbitrary) instead of the recurrence inequal-
ities (.t) . In such cases G , can be written explicitly as a function of I, and G, can
be computed for each concrete value of l.

WORDS WITH RESTRICTIONS
71
In particular, we see that the following two conditions suffice for the validity
of recurrence equalities of type (4'):
1 0 . Among the words of length l obtained by adjoining one of the letters a, b, c
to the right end of good words of length I - 1 are all words obtained from good
words of length l-li by adjoining the marked word of length li to the right end (by
assumption it is in the list of prohibitions).
2°. Each bad word of length I obtained by such an adjunction (of one letter)
can be uniquely represented as a good word (of smaller length) and a marked word.
The condition 2° holds if no marked word in the list of prohibitions is an end
of any other marked word.
EXERCISE 1. Verify that the conditions 1° and 2° hold for an alphabet of three
letters and the list of marked words
ab, acb, accb, . . . , a c. . . c b,
'-..-"
s-2
and that the recurrence relations
(5) G, - 3G'-1 + G'-2 + . . . + G,-s = 0
hold for the numbers G, (s is the length of the longest marked word).4
If the list of prohibitions in Exercise 1 is restricted to the two marked words ab
and acb, then we get the equation
(5') G, - 3GI- 1 + G'-2 + G'-3 = O.
The solution of (5') will be found in the fonn
(5") G l = AI.
Substituting (5") in (5'), we get
A 3 - 3A 2 +A+ 1 = 0,
which has the three distinct roots A = 1, A = 1 +../2, A = 1-../2. The general
solution of (5') can be written as
Gl = C 1 + C2(1 + J2)1 + C 3 (1- J2)',
where C 1 , C2, and C 3 are constants determined from the initial conditions Go = 1,
G 1 = 3, G2 = 8. Thus, the following system is obtained for determining C b C2. C 3 :
{ C1 +C2+C3 = 1,
C 1 + C 2 (1 +../2) + C3(1- J2) = 3,
C1 + C2(3 + 2../2) + C 3 (3 - 2J2) = 8.
From this,
1
C 1 = -2 '
3 J2
C2=4 +2'
3 J2
C3=4 -2'
4Equations ofthe form O,+bl Or-l +b20r-2+' ..+bsO,-s = 0 (bI. ... ,b s are some constants)
are called finite-difference equations. About methods for solving them see  4.2 in Chapter V of
A. O. Gel'fond's book The calculus of finite differences, "Nauka", Moscow, 1967; English transl.,
Hindustan Publ. Corp., Delhi, 1971.

72
A. M. STEP IN AND A. T. TAGI-ZADE
and hence
1 ( 3 0. ) 1ft' ( 3  ) 1ft ) '
G'=-2+ 4+"2 (1+v2) + 4-2 (1-v2
(in particular, G3 = 20).
Generalization of Problem M300
Suppose now that the alphabet consists of n letters ah...' an, and the list of
marked words (of length at least two) contains at most m different words of the
same length.
We prove that under certain restrictions on nand m, the "dictionary" contains
arbitrarily long good words, and moreover, for each I (I the length of a word) there
are fairly many of them.
As in the solution of Problem M300 (n = 3 and m = 1 for M300) we must first
prove
LEMMA 3. Under the conditions of the generalized Problem M300 the numbers
G, of good words of length I satisfy the relations
(6)
G, > nG,- 1 - L miG,-li.'
2SliS I
where mi denotes the number of marked words of length Ii (G 1 is obviously equal
to n, and we again set Go equal to 1).
Lemma 3 can be proved by exactly the same arguments as Lemma 1; we shall
not prove it here.
Since by assumption each mi is less than or equal to m (we assume that
m = max{ md in what follows, and we call m the multiplicity of the system of
restrictions), we have
(7)
G, > nG'-l - m L G,-l..
2SI.S1
The next step after Lemma 3 is to prove the important
LEMMA 4. If
( n - 1 ) 2
m< ,
- 2
then there exists a  > 1 such that for any I
(8)
(9)
GHl > G,.
Lemma 4, like Lemma 2 in the first section, can be proved by induction using
(7) and the relations (2') and (2"), with the number 2 replaced by. The induction
step from L to L + 1 is possible because the quadratic (with respect to ) inequality
n - m( - 1)-1 >  has nonnegative discriminant [«n - 1)/2)2 - m] (in view of
(8» and solutions
n+1 J ( n-1 ) 2
1, 2 = 2 :1: 2 - m.

WORDS WITH RESTRICTIONS
73
Since G 1 = nG o (recall that Go = 1) and
> n+l J ( n-l ) 2_
n - 2 + 2 m,
it follows that
( n+1 J ( n-l ) 2 )
G 1 > 2 + - 2 - m Go.
and the existence of A > 1 is proved.
Finally, we get the analogue of Theorem 1:
THEOREM 2. 1fm < «n-l)/2)2 under the conditions of the generalized Prob-
lem M300, then
G> ( n+l J ( n-l ) 2_ ) '
,_ 2 + 2 m.
Blocking restrictions
But is the restriction (8) on the multiplicity of the system of prohibitions nec-
essary in general?
We have already seen that the condition m < «n -1)/2)2 is sufficient for the
existence of arbitrarily long good words. This condition cannot be weakened in
general. Indeed, when n = 2 we get the condition m <  on the multiplicity for an
alphabet of two letters a and b. Let m = 1 and take the marked words to be ab,
aaa, and bbbb.
We prove that in this case there are no good words of length greater than 5. A
system of prohibitions for which there are not arbitrarily long good words will be
called a blocking system.
PROOF (by contradiction). Suppose that there is a good word of length 6. It
ends either with a or with b. If it ends with the letter b, then since the combination
ab is prohibited, our "good" word consists solely of the letter b, which cannot be,
because the combination bbbb is prohibited.
Suppose that this good word (of length 6) ends in a, and consider its next-to-
last letter. If it is b, then all the remaining letters (5 of them) must be b, which
cannot be the case. Hence, our word ends with aa. We now look at the third from
the last letter of our word. If this is again a, then we have the forbidden aaa, but if
it is b, then the remaining letters (4 of them) are also b, and we have the forbidden
bbbb.
We present one more example of a blocking system of prohibitions, for an
alphabet of three letters a, b, e. .For this alphabet the condition (8) gives us that m
must be at most 1. Setting m = 2, that is, assuming that two words of the same
length can be marked words, we take the marked words to be as follows: ab, ae;
bcb, bee; aaaa, bbbb; ccecc.
EXERCISE 2. Prove that these marked words form a blocking restriction on
good words. In this case what is the maximal length of a good word?
From the examples considered for n = 2 and n = 3 it follows that in both these
cases there is a blocking system of prohibitions with multiplicity m such that
«n - 1)/2)2 < m < «n - 1)/2)2 + 1.

i-l
A. M. STEPIN AND A. T. TAGI-ZADE
But the existence of a blocking system of prohibitions for an alphabet of n
letters and for multiplicity m satisfying these inequalities has not been proved for
an arbitrary n and the corresponding integer m. We prove that for an alphabet
with n letters al,.. . , an a blocking system of prohibitions with multiplicity m =
71.(-1) - 1)/2 exists. Indeed, let the system of prohibitions be: (1) ala2; (2) ala3;
... ; (11 - 1) alan; (n) a2a3; ... ; (71.(71. - 1)/2) an-Ian' Then there are no good
words of length greater than 271., and the only good word of length 271. is the word
a"anan-lCln-1 .. . alaI.
But in each concrete case everything depends on how the system of prohibitions
is constructed, of course. For example, in the case of an alphabet of two letters
a, b (11 = 2) and m = 1 it suffices to take the marked words to be aa, aba, abaa,
abaab, . .. , and we get that there even exists an infinitely long periodic good word
bb... b... . loreover, we can even take m to be 4 (and of course 2 and 3) and the
marked words to be, for example,
aa,ab,ba,aab,aba,baa,aaa,
and we again get the infinite good word bb. . . b. .. .
In conclusion we present some problems for the readers interested in "the ques-
tion of good words".
1. Prove that for the alphabet a, b there is no system of blocking restrictions
consisting of fewer than three words.
2. Prove that in the case 71. = 3 and m = 2 there is no blocking system of fewer
than six marked words.
3. Prove tbat if for the alphabet a, b, c the words ca, cb, ba are marked, then
G, grows as l2.
4. Prove that Gh +12 < G,. G ,2 .
5. Prove that for an alphabet of 71. letters there is a blocking system of restric-
tions with multiplicitr 111 such that
n(n - 2) 2 < n(n - 2) 3
2 + _m< 2 +.

Planar Switching Circuits
S. OVCHINNIKOV
What such a switching circuit is can easily be seen from FiglU'e 1. There are
two groups of n poles: a group of inputs and a group of outputs (n = 4 in Figure 1).
Each input pole is connected to one and only one output pole. Readers familiar
with the concept of a graph can observe that a switching circuit is a graph ofa
special fonn. Such graphs are called networks.
1
2
3
4
Inputs
1
2
3
4
Outputs
FIGURE 1
In making technical devices using switching circuits it is required that connec-
tions that cross be insulated from each other. In the usual devices, connections
are realized by wires, so this requirement is easily satisfied. (An example of such
a device is the switching circuit that connects your telephone to a station.) How-
ever, the problem becomes much more complex in passing to the microcircuits in
modern electronics. Connections in such circuits are realized by depositing a very
thin conducting film at the necessary places on an insulating layer. Clearly, con-
nections that cross must be located in different layers in these cases. For example,
consider the switching circuit shown in Figure 1. This circuit can be realized ill
two conducting layers as shown in Figure 2.
A natural question arises: what is the minimal number of layers needed to
realize a given switching circuit without connections that cross? (Here it is assumed
that all connections are in a circuit board: the rectangle in our figure.)
The Russian original is published in Kvant 1976. no. 1, pp. 12-18.
-
,.)

76
S. OVCHINNIKOV
1
2
3
4
1
Layer 1
1
2
3
4
2
3
4
1
Layer 2
2
3
4
FIGURE 2
1 2 3
. . .
n-l n
.., . .. .. '"
. . .
.. .. ..
.. .. . . . ..
1 2 3
n-l Il
FIGURE 3
Let us consider two "('xt.n'uu'" cases. Obviously, only one layer is needed for
the circuit in Figurc 3. Iu Figm"(' 4 thcre is a circuit realizing a symmetry of n
numbers: the ith input is connccted to the n - i + 1st output. For this circuit n
layers arc needed, since every two of connections must lie in different layers.
We now give the rigorous forlUulation of the problem and prove a fundamental
theorem.
Suppose that we are given a switching circuit with n inputs and n outputs, both
groups numbered 1,..., fl. Each such circuit determines a one-to-one mapping of
the set {I.... , n} onto itself; in other words, the circuit determines a permutation

PLANAR SWITCHING CIRCUITS
77
1 2 3
n-1 n
1 2 3
n-1 n
FIGURE 4
P of the set {I,..., n}, assigning to an input number the number of the output
connected to it. For example, the switching circuit in Figure 1 corresponds to the
permutation 1 --. 2, 2 --. 4, 3 --. 1, 4 --. 3. It is clear that, in turn, a switching circuit
corresponds to each permutation. Therefore, in what follows we do not distinguish
between switching circuits and the permutations corresponding to them.
The number n is the degree of the permutation P. The connection joining input
i to output j will be denoted by (i, j). Then P can be defined as the set {( i, j)} of
all connections.
We consider some examples. The circuit in Figure 1 corresponds to the per-
mutation of degree 4 that can be written as the set
P l = {(3, 1), (1,2), (4, 3), (2, 4)}
of connections.
The permutations of degree n corresponding to the circuits in Figures 3 and 4
are written as follows:
P2 = {(I, 1), (2, 2), . . . , (n, n)}, Pg = {(n, 1), (n - 1,2), . . . , (I, n)}.
PROBLEM 1. Prove that two connections (i,j) and (p, q) cross if and only if
(i-p){j -q) < O.
A subset of connections is called a layer of a permutation P if no two con-
nections in it cross. In Figure 2 we show two layers of the permutation Pl' The
permutation P 2 itself is a layer, and for the permutation P3 each layer consists
precisely of one connection.
The thic/.,"'f1,ess of a permutation P is defined to be the minimum number of
layers into which it can be decomposed. In our examples the thickness of P l is 2,
that of P 2 is I, and that of P3 is n. Obviously, the thickness of any permutation
does not exceed its degree n.
PROBLEM 2. Prove that for any integer p < n there is a permutation P of
degree n and thickness p.
Permutations of thickness 2 are said to be 2-realizable (they can be put in
exactly two layers), and they have the following property. Let us call a connection
(i, j) right if i > j, and left if i < j (Figure 5 shows a permutation whose right

78
s. OVCHINNIKOV
1
2
3
4
5
1
2
3
4
5
FIGURE 5
connections are indicated by double lines and left connections by solid lines). It
turns out that the set of all left connections of a 2-realizable permutation is a layer.
(Prove this.)
For example, the permutation in Figure 5 is not 2-realizable: its left connections
(2,5) and (3,4) cross. A concept opposite in meaning to that of a layer is the concept
of a bundle. A subset of connections is called a bundle if any two connections in it
cross. The thickness of a bundle is defined to be the number of connections in it.
Each connection will be regarded as a bundle of thickness 1.
Let us return to our examples. For the permutation P l (Figure 1) there are
three bundles of thickness 2:
{(3, 1), (1,2)}, {(3,1),(2,4)}, {(4,3),(2.-1)}.
All the bundles of P2 (Figure 2) have thickness 1. For the pemlutation Pol (Figure 4)
any subset of connections is a bundle. In particular, P.t itself is a bundle.
Among the bWldles of a given permutation, the bundles of ma.ximal thickness
are of special interest. Such bundles are said to be maximal.
PROBLEM 3. Prove that a maximal bundle of an arbitrary permutation cannot
consist solely of left connections.
There is an obvious dependence between the thickness of a permutation and
the thickness of a maximal bundle of it: the thicker the bundles, the thicker the
permutation. The following theorem gives this dependence a precise form.
THEOREl'vl 1. The thickness of a permutation is equal to the thickness of a
maximal bundle of it.
Since the connections in a maximal bundle must lie in different layers, the
number of layers cannot be less than the thickness of the bundle. Therefore, to
prove the theorem it suffices t.o construct for the given permutation a decomposition
with number of layers equal to the number of connections in a lnaximal bundle. In
other words, there must be exactly one connection of the maximal bundle in each
layer of such a decomposition.
Before proving Theorem 1, we establish an important property of a maximal
bundle.

PLANAR SWITCHING CIRCUITS
79
1234567
1234567
FIGURE 6
LEMMA. Let
(i l ,;1),(i2,;2),..., (ip,;p)
be the connections in a maximal bundle, with
;1 < ;2 < . . . < jp.
If some connection (i,j) crosses the connection (ibjd, then i < i l (and, therefore,
j > jl).
PROOF. Assuming the contrary, we get from the result of Problem 1 that
; < jl. But then the connection (i, j) crosses aU the connections of the given
bundle, and this contradicts the maximality of the bundle.
We say that a connection (i, j) begins at the pole j. Then the property proved
in the lemma means geometricaUy that any connection beginning to the left of a
maximal bundle does not cross its leftmost connection. Similarly, every connection
beginning to the right of a maximal bundle does not cross its rightmost cOlmection.
The permutation in Figure 6 illustrates our lemma. The cOlmections of a maximal
bundle are indicated by double lines; (1,5) is the rightmost connection of the max-
imal bundle, and (4,2) is the leftmost connection. Incidentally, note that there can
be several maximal bundles. For the permutation in Figure 6 there are three:
{(4, 2), (3,4), (1, 5)}, {(7, 3), (3,4), (1, 5)}, {(7, 3), (6,6), (5, 7)}.
PROOF OF THEOREM 1. We give a constructive proof, that is. we indicate a
process by which we can decompose each permutation into a minimum number of
layers.
Denote the thickness of a ma.."Cimal bundle by p. We put the comlection (Ul, 1)
(that is, the leftnlost connection of the permutation) in the first layer and denote
it by (Ub VI). Atnong all the connections (i,j) not crossing (Ub VI) take the con-
nection with smallest j. We denote it by (U2, V2) and put it also in the first layer.
Going through the connections in succession, beginning with the leftmost one, and
putting in the first layer those that do not cross those already chosen, we get a set
of pairwise noncrossing connections (Ub Vb)' (U2, V2),.... (Uk. Vk) which form the
first layer.

80
s. OVCHINNIKOV
1
2
3
4
1
2
3
4
FIGURE 7
The connections not in the first layer themselves form a permutation. Applying
the preceding construction to this permutation, we get the second layer, and so on.
Let us see what happens with a maximal bundle under this construction. De-
note the connections in this bundle by (il,;l), (i2,;2),.. ., (ip,;p), ;1 < ;2 < ... <
;p. According to the lemma, the connection (il,;l) does not cross a single con-
nection beginning to the left of it, and hence must fall in the first layer. No other
connections in this maximal bundle fall in the first layer, since they cross the con-
nection (ihjl). Therefore, one connection from each maximal bundle falls in the
first layer.
We single out the first layer in our permutation. It is easy to see that in
the remaining permutation the maximal bundles have thickness p - 1. Singling
out the second layer, we get maximal bundles of thickness p - 2 in the remaining
permutation. Continuing this process of singling out layers, we get in the p - 1st
step a permutation whose maximal bundles have thickness 1. But this means that
the connections in this permutation do not cross, and hence it forms the pth and
last layer itself.
Accordingly, we have shown that any permutation can be decomposed into a
number of layers equal to the thickness of a maximal bundle; this decomposition
proves the theorem.
EXERCISE. Verify the theorem for Pit P2, and P3.
We now consider switching circuits corresponding to permutations of thick-
ness 2, that is, 2-realizable permutations; they are of special interest because only
two conducting layers are required to manufacture them. Suppose that two such
switching circuits are connected as shown in Figure 7. Obviously, the circuit in
Figure 7 is equivalent to the switching circuit in Figure 8. Denote the permutation
corresponding to the circuit in Figure 8 by P, and the permutations corresponding
to the upper and lower circuits in Figure 7 by PI and P2, respectively. We say that
the permutation P is equal to the product PI . P2 of the two permutations.

PLANAR SWITCHING CIRCUITS
81
1
2
3
4
1
2
3
4
FIGURE 8
1
2
3
4
1
2
3
4
FIGURE 9
We can define the product of any number of permutations in a similar way.
The order of the factors in such a product is important: for example, if we take
the permutation P 2 . Pi (see Figure 7), then corresponding to it is the circuit in
Figure 9 (and not the one in Figure 8!).
It turns out that any permutation can be decomposed into a product of several
2-realizable ones! (Prove this.)
If a permutation is in the form of a product of s "pieces" of 2-realizable per-
mutations, it is called s-cascade realizable. (For example, the permutation P (of
thickness 3) in Figure 8 is 2-cascade realizable; a decomposition of P into two
cascades of 2-realizable permutations is implemented by the permutations in Fig-
ure 7.) Technically, an s-cascade realizable permutation has two conducting layers
and one insulating layer, interrupted s - 1 times. An interruption between cas-
cades corresponds to an interruption of the insulating layer; obviously, a crossing
of connections does not take place at an interruption of the insulating layer. Each
connection of an s-cascade realizable permutation (decomposed into a product of
2-realizable ones) goes through each cascade, but perhaps in different conducting
layers (see Figure 10; the connections lying in one conducting layer are denoted by
lines of the same type-solid or double).
Thus, as we said, for any permutation there is a cascade decomposition. But
what is the minimum number of cascades needed for a cascade decomposition of a
given permutation? Let us try to find this out.
We begin with the permutation Kp assigning to a number i the number p-i+ 1,
that is, realizing a symmetry of p numbers.

82
S. OVCHINNIKOV
1
2
3
4

Interruption
of the
insulating
layer
1
2
3
4
FIGURE 10
1
2
3
4
1
2
3
-l
FIGURE 11
As already noted, the permutation 1\ p coincides with its l11a.'\:hual bundle and
has thickness p. We now construct a cascade decomposition of l\p into two-layer
permutations and then show that the decomposition constructed is minimal.
For p = 2 the permutation 1\2 is itself a (unique) cascade. From Figure 11 it is
clear how to decompose I\.t (p = 4). Using th idea of decomposition into cascades
for 1(4, we construct a cascade decomposition of Ks (p = 8) (Figure 12). It is now
obvious how to construct a c'(1:-\{'a<!<' decomposit.ion of l\p if P is a power of 2. The
top cascade is pictured in Figur<, 13. The remaining cascades sYlumetrically realize
permutations of the pols 1,.... 2 r - 1 and the poles 2 r - 1 + 1,..., 2 r ; here the kth
cascade of the permutation of degree 2 T is obtained by combining two identical
k - 1st cascades of the permutation of degree 2 r - 1 . Obviously, the number of
cascades in the cascade decomposition of I(2 r constructed is equal to r.
Suppose now that p is not a power of 2; then there is an r such that 2 T < p <
2r+l. We consider a cascade decomposition of the perumtation K2r+l of degree
2r+l and single out in it the connections beginning at the poles with numbers
not exceeding p. It is clear that these connections determine the permutation K
p

PLANAR SWITCHING CIRCUITS
N3
5 6 7 8
1 2 3 4
5 6 7 8
FIGURE 12
1 2 1-1 1- 1 +1 i-I 1
1 2 2 1- 1 +1 i-I 1
FIGURE 13
(the inputs with numbers 2r+l - p + 1, 2r+l - p + 2, . . . ,2r+l must be renumbered
beginning with 1: 1,... ,p), and the given cascade decomposition of K 2 r+1 also
realizes a decomposition of K p . For example, in Figure 14 a cascade decomposition
for K6 is singled out in a decomposition for Ks.
Thus, we have constructed cascade decompositions for permutations K p that
are bundles. If p is such that 2 r - 1 < p < 2 r , then the number of cascades i!) f:qllal
to r. This can be written differently as: r =] log2 p[, where ]a[ is the smallest intf:gr:r
not less than a (the ceiling finction).
We now show that the cascade decompositions of the Kp con.1rllcted ';rJJLit of
the minimum number of cascades. To this end we use induction (In p. \\": r':mark
that if p < q, then a minimal cascade decomposition of a permlltati r JTJ (Jf d':l':t: 'I
requires no fewer cascades than for a minimal decomp(Jsiti(JJJ of a [Jt:rrll1Jtatj(JfI (Jf
degree p.
For p = 2 our assertion is clear. Suppose that thc: aSSf:rtj(JJJ ha. }Jt:t:TJ PT(J.;I.tJ
for p = k. We consider two cases.

84
s. OVCHINNIKOV
12345678
12345678
FIGURE 14
a) 2 r - 1 < k < 2 r . For the permutation Kk of degree k we have an r-cascade
decomposition. It follows from our remark that in passing from k to k+ 1 the number
of cascades does not decrease. But since k is an integer, we have k + 1 < 2T, and
hence we can construct an r-cascade decomposition of ]\k+l of degree k + 1, which
is clearly minimal.
b) k = 2 T . We consider the permutation ]\k+l = ](2r+l. Since 2 T + 1 < 2r+l,
we can construct for Kk+l an {r + I)-cascade decomposition. Let us show that r
cascades do not suffice for a decomposition of ]\k+l (and then an (r + I)-cascade
decomposition will be precisely minimal).
Assume the contrary: suppose that th('re is an r-cascade decomposition of
the permutation K2 r +l of degree 2 r + 1. We consider the top cascade of this
decomposition. One of the two layers of this cascade contains more than half of
the connections, that is, more than 2 T - 1 connections. These connections do not
cross, and hence the remaiuiug ,. - 1 cascades must realize a decomposition of the
bundle of these connections, which is impossible because the degree of this bundle
is greater than 2 r - 1 . This contradiction finishes the proof.
A cascade decomposition of an arbitrary permutation (that is not, like Kp, a
bundle) requires no fewer cascades than a decomposition of a nlaximal bundle of
it, hence the following result.
THEOREM 2. The minimum number of cascades needed for a two-layer real-
ization of a permutation of degree nand thicl.,-ness p is not less than] log2 p[.
We have obtained a lower estimate for the minimum number of cascades. Using
very similar arguments, we can get an upper estimate.

PLANAR SWITCHING CIRCUITS
85
THEOREM 3. An arbitrary permutation of degree n admits a ] log2 n[-cascade
realization.
PROBLEM 4. Prove Theorem 3.
The upper and lower estimates obtained differ little for "thick" permutations.
However, for permutations of small thickness the difference is substantial, and it
becomes necessary to get sharper estimates. The following two problems give some
progress in this question, though no exact formula for the minimum number of
two-layer cascades needed for a decomposition of a given permutation is known at
present.
PROBLEM 5. Prove that a permutation of thickness p admits a realization with
(2.] log2p[-I) cascades.
PROBLEM 6. Prove that a permutation of thickness p admits a realization with
(2.] log3(p/3) [+2) cascades.


Classification Algorithms
P. BLEHER AND M. KELBERT
In this article we discuss a relatively new research area: the theoI')r of pattern
recognition. l Namely) we discuss classification methods. A classification is a par-
tition of some collection of objects into groups of objects that are closely related
in some sense. For example) it is possible to classify factories of a given industry,
earthquakes in a certain region) the September weather over several years, extinct
lizards) and so on. It is only important that the objects to be classified have been
characterized by a definite set of numbers and criteria. For simplicity we consider
the case when each object is described solely by a set of numbers.
How can we classify schoolchildren?
Suppose that we want to divide all ninth-grade students in a particular scl1001
according to how they use their time outside school. We question each student and
write down the fraction of this free time he spends on homework and the fraction
spent on amusements. The rest of the time (eating, sleeping, transportation, and so
on) is not of interest to us here. As a result, each student will be characterized by
two numbers: time spent on homework and time spent on amusements. Therefore,
it can be represented as a point in the coordinate plane. We thus arrive at a purely
mathematical question: how do we divide this set of points in the plane into groups
of close points?
There are many serious applied problems that lead to this question, except
that in them the number of coordinates is much greater (of the order of several
dozens). For example, there are a large number of enterprises operating in the
textile industry. Among them there are specialized factories with a small assortment
of products) as well as industrial complexes outputting a variety of goods. There are
huge factories, factories of moderate size, and small local workshops. To compare
the activities of individual enterprises and to plan their operations it is necessary
to classify all these enterprises-to divide them into groups of enterprises of the
same type. They are distinguished by their economic indices. We choose some of
the most important such indices (for example, the cost of gross production, the cost
of production resources) and the cost of labor), and we carry out a classification
according to them. The number of indices chosen is denoted by n.
The Russian original is published in [(vant 1979, no. 6, pp. 2-8.
lTo the reader who wants to learn more about this topic, we recommend the fascinating
though not very simple book The recognition problem by M. M. Bongard ("Nauka", Moscow,
1967; English trans!., Pattern recognition, Spartan Books, New York, 1970).
R7'

88
P. BLEHER AND M. KELBERT
We associate with each enterprise an n-tuple (Xl,' . . ,x n ), where Xl is the value
of the first index, X2 the value of the second index, and so on.
The pair (x}, X2) determines a point in the plane, the triple (Xl, X2, X3) a point
in space, and the n-tuple (x},... ,x n ) a point in n-dimensional space.
Thus, we have now arrived at the problem of classifying points in n-dimensional
space.
This is hard without computers
To solve classification problems, various algorithms have been worked out that
enable us to use computers. There are two reasons why we have to use computers.
First, usually there are very many objects and it is simply impossible to process all
the data by hand. Second, the objects to be classified are most often multidimen-
sional.
If, as in the example with the schoolchildren, there are two coordinates in all
and the number of objects is not large, then a human being can deal with the
classification problem no worse than a computer. Namely, he looks at the plot of
the points representing the objects and singles out the regions where the points
seem to concentrate. Experiments show that all people do this in roughly the
same way. This is related to the fact that they (people) instinctively try to have
the points in a particular group close to each other and to have different groups
separated by a sufficient distance. But if the number of parameters is three or more,
then considerations of intuition are almost useless, and the classification problem
becomes very difficult for a human being.
Psychologists have performed the following experiment. 2 The subject was given
a set of cards each with three numbers, corresponding to the coordinates of points
in space, and it was required to separate the points into two natural groups. In fact,
there was a plane at an angle to the coordinate axes that separated the points into
two groups such that the distance from any point to this plane was sufficiently large
in comparison with the distances between the points inside each group. Most people
broke up the points according to the value of one of the coordinates, which resulted
in groupings that were not natural; almost no one succeeded in constructing the
correct grouping.
For this reason, classification algorithms have been developed for points in
multidimensional space. One of the criteria for the correctness of such algorithms
has been the requirement that they give the natural groupings-those found by
people-in the case of classification of points in the plane.
Trees of minimal length
We now describe an algorithm for constructing a connected system of segments
joining given points, with the minimal sum of the lengths (a system of segments
is said to be connected if it is possible to go from any given point to any other
given point along segments of this system). For clarity we consider a construction
on the plane. In a multidimensional space the algorithm is the same, but it is then
impossible to draw a picture.
2This and some other experiments are described in N. G. Zagoruiko's book Methods oj recog-
nition and their application ("Sovetskoe Radio" t Moscow 1972; in Russian). There one can read
in depth about many of the questions we mention only in passing.

CLASSIFICATION ALGORITHMS
89
Thus, suppose that N points AI, . . . I AN are given on the plane. For simplicity
we assume that an the pairwise distances between points are distinct. Let us write
out an the pairs (AI,A2),(AttA3),...,(AN-hAN) and order them so that the
pair with minimal distance between points is first, the pair with next-to-minimal
distance is second, and so on. We now join the first pair of points, then the second
pair, and so on. If upon drawing the next segment a cycle appears (that is, in the
system of segments already drawn we find some segments forming a closed polygonal
curve), then we omit this segment and pass to the next segment, and so on, until
we have considered all possible segments. The system of segments obtained does
not contain cycles by construction. A connected system of segments without cycles
is called a tree.
PROBLEM 1. Prove that the constructed system of segments has minimal
length among all connected systems of segments joining the given points.
PROBLEM 2. Prove that the same system of segments can be obtained by the
following dual (as mathematicians say) construction: join all pairs of points by
segments and order these segments by decreasing length; now discard the longest
segment, then the second longest, and so on; if, after the next segment is discarded,
the remaining segments do not form a connected set, then leave this segment and
go on to the next, and so on, wltil all the segments are considered.
PROBLEM 3*. Suppose that not an the pairwise distances between the points
AI, . . . , AN are distinct. Order the segments of equal length in an arbitrary way
and carry out the procedure described in the text or in Problem 2. Prove that
the system of segments constructed has nlinimallength no matter how the equal
segments were ordered. Of course, in this case a system of segments of nlinimal
length need not be unique.
The algorithm we described for constructing a tree of minimal length is rela-
tively simple, but requires a large amount of sorting, and thus a lot of computer
time. There are faster (but more complicated!) algorithms.
Partition into groups
After a tree r of minimal length has been constructed, a partition of the set of
points AI,.. . ,AN into groups can be realized by removing some of the segments
in the tree. It is natural to discard sufficiently long segments, but. in such a war
that the points in a single group are as close together as possible. TIns intuitive
consideration can be formalized if we introduce the following quantities. Suppose
that we want to break up the set of points AI,'..' AN into k+1 groups. We choose k
arbitrary segments ofr and discard them (Figure 1), getting k+1 connected groups
of points: r I, . . . , r k+l' For each group r i we divide the sum of the lengths of the
segments of r joining points in it by the number of such segments. thus obtaining
the average length of segments in r i. If some group consists of a single point,
then by definition this average length is zero. We denote the computed average
lengths by Ih. . . ,lk+l and the lengths of the discarded segments by b l ,..., bk, and
we define F = it + ... + lk+l - bl - . H - bk. It is clear that the smaller F, the
closer together the points in each group, and the farther apart the different groups.
Therefore, the following algorithm is natural: from a tree of minimal length we
discard k segments in all possible ways and compute the quantity F; among all the

9U
P. BLEHER AND M. KELBERT
AN
A4
FIGURE 1
partitions obtained we choose the one for which F is minimal: if there are several
uminimar' partitions. then we choose anyone of them.
In algorithms used in practice the quantity F is commonly determined in a
more complicated way.
Computational experience has shown that algorithms of the type described
lead to sufficiently reasonable partitions. The main deficiency of these algorithms
is that they require too much sorting. As the number of points becomes larger, the
problem becomes intractable even for modern computers.
The following idea is used to cope with this difficulty. Points at a distance less
than some quantity a from each other are put in the same group. The whole con-
struction is carried out in two stages. In the first stage the set of points AI" . .. Ax
is broken up into finer groups 0 1 "", Om in such a way that for each gTOUp G i
there is a circle S; of radius R = a/2 containing all the points in G i and only them.
We discuss how to do this below. At the second stage we consider only the centers
0) , . . . , Om of the disks SI. . . . , Sm and construct a tree of minimal length now for
the set of points 0 1 , . . . , Om. 1\Iinimizing the quantity F corresponding to this tree.
we construct a partition of 0 1 ...., Om into groups as described above. We thus
obtain a partition of the set of points AI,.. .. AN. Namely, two points A.; and Aj
arc in the same group if they lie in the same refined group G, or if the centers of
the disks of the refined groups corresponding t.o them fall in the same group when
the points 0 1 ..... Om are> partitioned. The> aim of this two-step procedure is to
reduce the number of the original points: the number III turns out to be much less
than N. and such a procedurC' can now be implemeuted on a computer.
The moving circle problem
It. relUctins t.o find out how to divide the points A!,..., AN into fine groups.
The "1\"ou1" algorithm iH us('cl to solve this problem (it is somehow reminiscent of
011e of the ways to catch trout). We shall describe this algorithm for points on the
plane. although it works in C'xactly the same way in multidimensional spaces.
Let At..... AN be N given points on the plane. We locate beads of unit mass
elt these points and draw a circle So of radius R containing at least one of the
beads. Let 01 be the center of mass of the beads in So, and let SI be the disk

CLASSIFICATION ALGORITHMS
91
8 3
.A7
A,
.
FIGURE 2
of radius R about 0 1 . Let 02 be the center of mass of the beads in 8 1 , let 82
be the disk of radius R about O 2 , and so on. For example, there are eight points
AI, . . . ,As pictured in Figure 2. The initial disk 80 contains the one point A3,
which will be the center of the disk 8 1 . The latter contains the points A2' A3, A4,
and the center of the disk 82 is their center of mass. The disk 8 3 contains the points
A2,A3, A 4 , As, A6, As, and its center is their center of mass, therefore all succeeding
disks coincide with it. We next prove that this is what always happens, that is,
for any points AI,..., AN and any choice of initial disk 8 0 containing at least one
point Ai, all the disks coincide beginning at some step. In other words, movement
of the disk along the route 8 0  81  82  . .. cannot go on indefinitely. We put
the points in the last disk in the first group. The same procedure is then applied
to the remaining points, that is, a new disk is "launched", whose final position
determines the second group. This process continues until all the points have been
put in some group.
Why does the disk stop?
The rest of the article is devoted to a proof that the disk really does "stop".
Looking at Figure 2, we see that the disks 8 0 , 8I, 8 2 , ... encompass a greater and
greater number of points and that their final position conesponds to a concentration
of points. It is natural to think that for any arrangement of the points AI,..., AN
and the disk 80 the number of points falling in the disks 80,8 1 ,8 2 ,... is at least
nondecreasing. Figure 3 shows that this is not so. However, in a certain sense the
concentration of points in the disks 80,8 1 ,82, . .. really does increase; it is just that
in addition to the number of points in a disk one must take into account how close
they lie to the center of the disk.
Namely, suppose that points Ail'...' Ail.: fall in some disk 8 with center 0,
and define the quantity
F(8) = (R 2 -IOAi l j2) +... + (R 2 -IOAiI.:12).

92
P. BLEHER AND M. KELBERT
8 2
FIGURE 3
The closer a point to the center of S, the greater its contribution to F(S). We
prove that the sequence F(So), F(SI), F(S2),'" increases until the disk stops.
To prove this we need the concept of the moment of inertia of a system of
material points AI,.", Am with respect to some point A, along with Steiner's
theorem, which is very useful for solving many problems not only in geometry but
also in mechanics. 3
The moment of inertia of a system of material points AI, . . . , Am with respect
to a point A is defined to be
leA) = IAAl12 +... + I AA mI 2 .
Steiner's theorem enables us to compute leA) if we know the moment of inertia
l( G) of this system of points with respect to their center of mass G. This theorem
asserts that
leA) = I(G) +mIGAI2.
Let us prove Steiner's theorem. We use a rectangular coordinate system with
origin at the center of mass G of the points Att..., Am. Let (Xl, yd,..., (X m , Ym)
be the coordinates of the points AI,..., Am. Then G has coordinates
«Xl +... + xm)/m, (YI +... + Ym)Jm),
and since G coincides with the origin, it follows that Xl +. . '+X m = YI +. . '+Ym = O.
Let the point A have coordinates (x, V). Then
leA) = [(XI - xf + (YI - y)2] + ... + [(X m - .)2 + (Ym _ y)2]
= (x + Y) + ... + (x + y) + m(x 2 + y2)
- 2x(xl + ... + .I'm) - 2Y(YI + ... + Ym)
= I(G) +mIGAI2,
because 2X(XI + . . . + x m ) = 2Y(Yl + . . . + Ym) = O. Steiner's theorem is proved.
3S ee M. B. Balk's book, Geometric applications of the concept of center of mass (Fizmatgiz,
Moscow, 1959; in Russian).

CLASSIFICATION ALGORITHMS
93
We prove that if the disk SI does not coincide with the disk So, then F(Sl) >
F(So). Let us renumber the points AI,... ,Am so that the points in So but not
in SI have numbers from 1 to p, the points in the intersection of So and SI have
numbers from p + 1 to q, and the points in SI but not in So have numbers from
q + 1 to r. Thus, the points AI,... ,Aq are in So and the points Ap+l'... ,Ar are
in 8 1 . It is clear that F(So) can be expressed in terms of the moment of inertia
1(0) of the points AI,..., Aq with respect to the center 0 of So, namely,
F(So) = (R 2 -IOA l I 2 ) + ... + (R 2 -IOA q I 2 ) = qR 2 - 1(0).
The center 0 1 of SI is the center of mass of the points AI,... ,Aq, and therefore
by Steiner's theorem 1(0) = 1(0 1 ) + q100112, that is,
F(So) = qR 2 -1(01) -q100112 = (R2-IOIAI12)+.. .+(R 2 -I O I A qI2) -qI0011 2 .
Let us compare this expression with
F(Sl) = (R 2 -IOIAp+11 2 ) +... + (R 2 -IOlArI 2 ).
The terms
(R 2 -I O I A lI 2 ),..., (R 2 -I O I A pI 2 )
are absent in the expression for F(SI), but the terms
(R 2 - 101Aq+112), . . . , (R 2 -IOIArI 2 )
have appeared. Therefore,
F(Sl) - F(So) = -(R 2 -IOIAI12) - ... - (R 2 -IOIApI2)
+ (R 2 -IOlAq+112) +... + (R 2 -IOIArI2) + q100112.
We remark now-and this is the decisive fact-that the points AI,..., Ap are
outside the disk SI by construction. Hence, the quantities R2 - 10 1 A112 , . . . ,
R 2 -IOIApI2 are negative. On the other hand, the points Aq+l'... ,Ar are inside
SI; therefore, the quantities R2 - 101A q + 1 12,..., R2 - 101Arl 2 are nonnegative.
Thus,
F(SI) - F(So) > q10011 2 ,
that is, F(SI) > F(So) if the points 01 and 0 do not coincide.
It can be shown in exactly the same way that F(Sk+l) > F(Sk) if Ok+l and Ok
do not coincide. With the help of this fact it is now easy to show that all the disks
Sn, Sn+l'... coincide beginning with some n. By construction, the point Om+l is
the center of mass of the points in the disk Sm. H we consider all the subsets of
the set of points AI, . . . ,AN and the centers of mass of the points in these subsets,
then Om+l is one of these centers of mass. Since the set of centers of mass is finite,
the sequence of centers 0,0 1 , O 2 ,... must have repetitions; say Oi and OJ are the
same. However, we have proved that
F(Si) < F(Si+l) < ... < F(Sj),

94
P. BLEHER AND M. KELBERT
c (0 0 ) 
A 
2 AS
FIGURE 4
and since S; = Sj, we have F(Si) = F{Sj), so that F(S,) = F(Si+l) = ... = F(Sj).
We now recall that the equality F(S;) = F(Si+l) is possible only if Si and
Si+l coincidc. It remains to obscrve that if two successive disks coincide, then all
the succeeding disks coincide with them by construction. Thus, we have proved
that the movement of the disk So -+ SI --+ S2 --+ . .. cannot continue indefinitely,
or, as mathematicians say, we have proved that the Trout algorithm converges.
At the same time, we have analyzed the solution of a problem posed in the last
:Mathematical Olympiad and in the "Kvant Problem Book" (see problem :M505 in
Kvant 1978, no. 5).
Two new problems
In conclusion we formulate two more problems. The procedures described in
these problems are also used for classifying points in multidimensional spaces. As
before, we confine ourselves to the plane.
PROBLEM -1. Suppose that N points AI"." AN are divided into 1 (nonempty)
groups Glt..., G,. Let 0 1 ,...,0, be the centers of mass of each of these groups.
A new partition of the points AI,.", AN is constructed according to the following
rule: a point is put in the ith group (i < l) if Oi is the center of mass closest to it (if
there are several such centers of mass, then choose the one with the smallest index).
Suppose that there are p groups left (p < l) after discarding the empty groups (give
an example in which some of the groups G I ,..., G, are empty!). Renumbering
them in an arbitrary way, we get a new partition G. . . . . G.
Finding the centers of mass Of, . . . , O of these groups and repeating the same
procedure, we construct a partition Gi,..., G (q < p), and so on. Prove that the
partitions coincide beginning at some step.
To formulate the ncxt problcm it is convcnient to introduce some notation. Let
A be a point on the planc and let G be an arbitrary subset of the set of points
AI,..., AN. We define
I(A,G) = IAAil 2 +... + IAAjl2
(the sum is taken over the points in G).
PROBLEM 5. As in Problem 4, let G I ,..., Gl be an initial partition of the set
of points AI" . . , AN into l nonempty groups. We describe a rule for constructing
a new partition GI, . . . ,G (p < l) of AI, . . . ,AN which is somewhat different from

CLASSIFICATION ALGORITHMS
95
the rule in Problem 4. Here the new partition differs from the original one only in
that one of the points faUs in a new group. Namely, Al is put in the group G i for
which I(A b Gi) is minimal (if there are several such groups, then Al is put in the
one with smallest index). If Al was alone in its group and as a result of moving it
the group became empty, then we discard this group and renumber the remaining
groups in an arbitrary way. Denote the partition obtained by GI...., G (p = l
or p = l - 1). We repeat the same procedure for the points A2,.. . , AN, and then
again for At, for A2' and so on. Prove that aU the partitions coincide beginning at
some step.
The advantage of the algorithms described in Problems 4 and 5, in comparison
with the Trout algorithm, is that they converge rapidly (that is, the construction of
the final partition requires less computer time). However, if there is an unfortunate
choice of the original partition, then the algorithms can lead to a not very natural
final partition into groups. One such example is given in Figure 4.


How to Detect a Counterfeit Coin
G. SHESTOPAL
Suppose that there is a pile of coins on a table, which are completely identical
in appearance, but you are told that one of the coins is counterfeit. It differs from
the others in weight, but you are not told whether it is lighter or heavier. You
have at your disposal balance scales but no set of nleasuring weights. How can
you identify the bad coin and determine its type (that is, whether it is lighter or
heavier) in the minimal number of weighings?
Many of you have surely solved this problem for twelve coins. Figure 1 presents
one possible solution. Corresponding to the three possible outcomes of the first
weighing are three variants of the choice of coins for the second weighing: in the
figure the left arrow corresponds to the case when the left pan is heavier, the middle
arrow to the case when the pans balance, and the right arrow to the case when the
right pan is heavier. Similarly, there are nine variants of the choice of coins for the
third weighing. (The coins are numbered in the figure, and the letters "L" and "H"
stand for "lighter" and "heavier", respectively.)
lt wcighin .
l@@@G)J
I
..,., . @@>  @,.''
- . 
...
nd weighing
FIGURE 1
The Russian original is published in Kvant 1979, no. 10. pp. 21-25.
!1";'

98
G. SHESTOPAL
A characteristic feature of this solution is the dependence of the choice of coins
for the next weighing on the result of the previous weighing.
Let us now pose the problem in general form.
We have m > 3 coins identical in appearance. All the coins except one have
the same weight, and that one differs from the others in weight, though it is not
/-'-nown in which direction. What is the smallest number of weighings needed to find
this coin and identify its type using balance scales without measuring weights?!
In t.he 1940s this problem attracted the attention of many mathematicians,
mainly in England and the USA. In 1945 a solution of the problem appeared in the
English journal The !vI athematical Gazette, which is similar in purpose to K vant.
Its author, R. L. Goodstein, later became a well-known specialist in mathematical
logic.
Goodstein indicated a method for determining the false coin and its type in
n > 3 weighings if the number of coins satisfies
1n <  (3 n - 2n + 3)
(note that m < 12 for n = 3).
However, it turned out that for n > 3 his solution is not the best possible: in n
weighings one can detect the counterfeit coin and determine its type from a greater
number of coins, namely,
m < (3n - 3).
This was observed independently by several mathematicians at once, and in the
following year of 1946 the same journal published a fairly long list of their names
and various degrees of success in the field of detecting false coins. In the same issue
a best possible solution was presented by Freeman Dyson, who would later become
famous as a theoretical physicist.
Dyson's idea was based on using the ternary number system: all the coins
are marked by specially chosen ternary numbers, the markers enabling us to con-
veniently reflect the course of the successive weighings. An especially fascinating
feature of this method of solution is the fact that the choice of coins for the next
weighing is independent of the results of the previous weighillgs.
In subsequent years other solutions of the problem were published,2 and Dyson's
method was undeservedly forgotten. Therefore, it may be of interest to discuss it
in detail.
Dyson's solution can be broken up into two steps.
A.If
m = (3n - 3), n = 2,3....,
then n weighings suffice to detect one false coin in a total number of m coins and
to determine its type.
B. If the number of coins is
m < (3n -3), m > 3,
then n weighings suffice for the same goal.
10bviously, it does not make sense to solve the problem for m < 3: for m = 1 the coin is
counterfeit, but the type is not known; for m = 2 the coins have different weights, and it is not
possible to determine which one is counterfeit.
2For example, in the book Probability and information by A. Yaglom and I. Yaglom (3rd ed.,
"Nauka", Moscow, 1973; German transI. of 4th ed., VEB Deutscher Verlag Wiss., Berlin, 1984).

HOW TO DETECT A COUNTERFEIT COIN
99
We treat each step separately.
First step
Suppose that the number of coins is m = (3n - 3).
Let us consider all n-digit Uternary numbers" (n-words made up of the digits
0, 1,2): 00...00,00...01,...,22...22. There are 31'1 of them. We use them to
mark the coins as described below. All these numbers are used as markers except
the three consisting of identical digits, namely, O. . . 0, 1 . . . I, 2 . . . 2.
We separate the totality of markers into pairs, a single pair being two comple-
mentary markers: the digits of the same order add up to 2 (that is, the sum of the
two markers in a pair is 22 . . . 22).
A marker is called a right marker if the first pair of unequal digits starting from
the left is 01, 12, or 20; otherwise, it is called a left marker. It is clear that in each
pair of complementary markers one is always a right marker and the other a left
marker.
We note that the number of pairs of markers is exactly equal to the number m
of coins. Let us number the coins from 1 to m and arbitrarily assign to each coin
one pair of markers. For example, twelve coins can be "marked" as indicated in
Table 1.
TABLE 1
coin left right
number marker marker
1 211 011
2 100 122
3 022 200
4 212 010
5 101 121
6 020 202
7 210 012
8 102 120
9 021 201
10 221 001
11 110 112
12 002 220
Let lv/(i,O), ltl(i, 1), and It/(i,2) denote the set of coins for which the ith digit
of the corresponding right marker is equal to 0, 1, and 2 respectively.
It is easy to see that the number of coins is the same in each of the sets It/(i, 0),
lvl(i, I), and A/(i,2) and that these sets do not have common elements (see the
table, for example).
The method devised by Dyson for weighing coins is as follows.
There are n weighings. For the ith weighing (i = 1,..., n) all the coins in the
set ltJ(i,O) are placed on the left pan of the scales, and all the coins in the set
lv/(i, 2) on the right pan. The result of each weighing will be denoted by the digit
o if the left pan is heavier, 1 if the pans balance, and 2 if the right pan is heavier

100 G. SHESTOPAL
I  , 1  .
  t
+
II = 0 1 2
FIGURE 2
(Figure 2). The result of the ith weighing is denoted by lie From the digits l}, . . . , In
we form the marker 3 1= 11" .In.
It turns out that I is the marker of the false coin F, and that F is heavier than
the others if I is a right marker and lighter if I is a left marker.
Indeed, let us see what happens when we carry out the ith weighing. As a
result of this weighing the pans either balance or one is heavier.
If they balance, then the false coin is not on them, and hence it is in the set
AI(i, 1). But tllis Ineans that the ith digit of its right (and left) lnarker is 1, and
the result Ii = 1 of the weighing indicates this.
If one of the pans is heavier, then the false coin is on the scales. Suppose, for
example, that the right pan is heavier, that is, Ii = 2. This is possible in two cases:
. the false coin is on the right pan (and then it is heavier than the others),
hence it is in the set AI (i, 2) and the ith digit of its right marker is 2, so that
the result of the weighing coincides with the ith digit. of its right marker;
. the false coin is on the left pan (and then it is lighter than the others), hence
it is in the set AI(i.O) and the ith digit of its right marker is O. so that t.he
result of the weiglling coincides with the ith digit of its left marker.
The "symmetric" case when the left pan is heavier (li = 0) is completely anal-
ogous. Therefore, the marker I = h.. .In formed as a result of the successive
weighings is indeed the marker of the false coin, and is a right marker when that
coin is heavier and a left marker when it is lighter, which is what was to be proved.
It is interesting to note that, as a rule, the type of the coin is determined before
all the weighings have been performed: as soon as two distinct digits appear in the
process of formation of the marker I.
As noted earlier, an essential feature of tills tuethod is that the choice of coins
for each weighing does not depend on the results of the previous weighings.
For example, for twelve coins marked as in the table it is necessary to carry
out the following three weighings: (1.4, i. 10). (3.6.9. 12); (3.6.9. 10). (2.5,8.12);
(3,4,8,12), (2.6,7,11).
Second step
We briefly sketch Dyson's method for the case 7n < (3n-3). If the markers are
assigned arbitrarily to the coins in this case, then the sets AI(i. 0) and AI(i, 2) may
have different number of coins. We therefore proceed as follows. Let us separate
all the markers into groups of six each: in a single group we put the right markers
obtained from each other by the cyclic pennutation of digits 0 -+ 1, 1 -+ 2, 2 -+ 0,
together with the left markers corresponding to them.
3Prove that this is really a marker, that is, that the digits it,. . . ,In cannot all be the same.

HOW TO DETECT A COUNTERFEIT COIN
101


Uf
A

FIGURE 3
In each group there are three right markers and three left markers. We dis-
tinguish the group containing the right markers 00. . .01,11. . .12,22. . .20. Let us
divide the coins into groups of three as long as possible, and mark them as follows.
To the coins in a single group we assign the pairs of markers in a single group, and
for the coins left over, if there are any, we use pairs of markers in the distinguished
group. If one coin was left over and not put in a triple, then we assign it the right
marker 11 . . . 12, and if two were left over, then we assign them the right markers
00...01 and 22...20 (and the corresponding left markers).
For such a marking of the coins the first n-l weighings are carried out according
to the old rules. How to do the last weighing you should figure out independently.
Dyson's method has been described. Let us now see that it is best possible in
a certain sense. Namely, we show that if in n weighings it is possible to find the
false coin among m coins and to determine its type, then 2m < 3 n - 3. Of course,
we shall not take into account the possibility of "luck": with luck, two weighings
could be enough to find the false coin in any number of coins.
Accordingly, suppose that n weighings suffice.
We number the coins by 1,. .. ,m and take 2m slips of paper, on which we write
all possible cases: the first coin is lighter, the first coin is heavier, the second coin
is lighter, and so on. It is clear that this will use all 2m slips of paper, and no
possible case will have been left out. The results of the weighings are denoted by
the digits 0, 1,2 as specified above. Each weighing shows that some of the possible
answers cannot be true but that some may still be true. Let coins be selected for
the first weighing. Without actually performing this weighing, we write on each
slip of paper the result of the first weighing that leaves its answer a possibility.
Clearly, on each slip of paper one of the digits 0, 1, or 2 has been written. Thus, all
the slips are divided into three groups, and so at least 2m/3 slips are in the largest
group. Therefore, no matter how we organize the first weighing, it can happen that
afterwards at least 2m/3 of the slips of paper are still possibilities.
Similarly, the second weighing sorts this group of possible answers into three
subgroups, and thus at least 2m/9 slips of paper are in the largest subgroup. In
exactly the same way we can get 2m/3 n possible slips of paper in one group after
n weighings. Consequently, if 2m/3 n > 1, then in general the false coin and its
type may not be determined in n weighings. Therefore, if n weighings suffice, then
2m < 3 n .
But this is not yet all! We have not yet analyzed the case 2m = 3 n - 1 (the
even number 2m cannot be equal to 3 n - 2 nor gn). The above arguments do not
suffice for this case. Let us look more carefully at the first weighing. The number
of papers on which 0 is written is clearly equal to the number on which 2 is written.
If there are p pieces of paper for each, then 1 is written on 2m - 2p pieces of paper.
We remark that p is an even number. Indeed, if there are k coins on each of the
left and right pans, then p = 2k. If p or 2m - 2p is greater than gn-l, then by the
above considerations the remaining n -1 weighings may not suffice for determining

102
G. SHESTOPAL
the necessary slip of paper. But if p = 2k < 3 n - 1 and 2m - 2p < 3 n - 1 , then since
3 n - 1 is an odd number, we have p < 3 n - 1 -1 and 2m - 2p < 3 n - 1 -1. But then
27n = (2m, - 2p) + 2p < 3 n - 1 - 1 + 2(3 n - 1 - 1) = 3 n - 3. Thus, if n weighings
suffice, then 2m, < 3 n - 3.
We conclude with some problems that can be solved by Dyson's method.
PROBLEMS.
1. There are two groups of n1.1 and 7n2 coins, it is known that one coin is false,
and it is lighter if it is in the first group and heavier if it is in the second group.
What is the minimum number of weighings needed to find the false coin?
2. Suppose that in addition to the groups of ml and m2 coins there is a group
of m3 standard (that is, definitely not false) coins. How many weighings are needed
in this case?
3. We have m coins among which is a false coin (it is not known whether it is
lighter or heavier), and we have one standard coin. Is it possible to determine the
false coin and its type in n weighings if m = !(3 n -I)? How many weighings are
needed for other m?
4. We are given m coins and it is known that there is at most one false coin
among them. How many weighings are needed to find the false coin and determine
its type or to determine that there is no false coin?
5. In the case 2n1. < 3" - 3 the last weighing depended in general on the results
of the previous weighings. Try to make it depend on the least possible number of
weighings.

The Generalized Problem of Counterfeit Coins
M. MAMIKON
Many readers are quite familiar with the following classical problem about
counterfeit coins, which is striking in that it is solvable.
The problem of the bag of false coins
There are N bags. each containing sufficiently many coins. All but one bag
contain identical "normal" coins, but in one bag all the coins are counterfeit. The
weight of a normal coin is known, and it is known that a false coin is one gram
lighter than a normal coin. It is required to find the bag with false coins by a single
weighing on scales with a set of weights.
Here is how this problem can be solved. The bags are numbered consecutively,
and from each bag a number of coins equal to the number on the bag is taken. The
total weight of all the coins selected in this way will "fall short of" the weight of
the same number of normal coins (which we know) by a number of grams equal to
the number on precisely that bag containing the false coins. l
While reflecting on this problem, I came to the more surprising conclusion that
an even more complicated problem ran be solved by a single weighing.
The problem of several bags with false coins
Suppose that under the conditions of the preceding problem there are not one
but several bags of false coins, and it is not "'-nown how many. It is required to find
all these bags by a single weighing on scales with a set of weights.
After solving this problem, I grew bolder and considered further complications.
The problem turned out to be solvable under even more surprising conditions.
The problem of bags with heavy and light coins
Among the N bags are some (unknown) number of bags with heavy coins and
some (also unknown) number of bags with light coins. a light coin being one gram
lighter than a normal coin and a heavy coin being one gram heavier than a normal
coin. It is required to find the bags with normal coins, those with heavy coins, and
those with light coins by a single weighing on scales with a set of weights. (Recall
that all the coins in a particular bag are of the same weight and that the weight of
a normal coin is known.)
The Russian original is published in Kvant 1980, no. 1, pp. 27-29.
IThis problem can also be solved. albeit with a bit more cleverness. in the case when the
weight of a normal coin is unknown and there is no set of weights. Try to figure out how.
10

104
M. MAMIKON
The solvability of this problem inspired me to the following almost evident
generalization. Up to this point we have actually considered problems of two or
three kinds of coins; therefore, it is natural to go further.
The problem of bags with several kinds of coins
Suppose that there are N bags, each containing sufficiently many coins. There
are coins of various kinds, but the coins in a particular bag are all of a single kind.
The number of bags with coins of a given kind is arbitrary and unknown. Two coins
of different kinds differ in weight by an integml number of grams. The set of all
possible weights of coins is known. It is required to determine the kind of coins in
each bag by means of a single weighing on scales with a set of weights.
Before proceeding to the solution below of the generalized problem of false coins,
we propose that the reader try to solve the preceding problems independently.
Solution of the problem of bags with several kinds of coins
We number the bags consecutively from 0 to N - 1. Denote the weight of the
lightest coin by m, and the wieght of the heaviest coin by m + k. Suppose that
the bag with number j contains coins of weight m + j, so that /)"j determines the
kind of coins in the jth bag. Depending on the kind of coins, the quantities /)"j can
take (integer) values 0,1,2,.. ., k.
From the bag with number j we now take k j coins, that is, 1 from the first bag,
k from the second bag, ... , k N - 1 from the last bag. The total number of coins
taken is
N-l k N 1
M= L ki = l+k+k2+...+kN-l = - .
. 0 k-l
J=
Their total weight S on the scales is
N-1 N-1 N-l N-1
S = L(m+ j)k; = m L ki + L /)"jk; = m..AI + L /)"jk j .
j=O j=O j=O j=O
Since j is always < k, the second sum
N-1
 = L jk; = o + lk + 2k2 + .. . + N_lkN-1
j=O
on the right-hand side is the translation of the number /)" from the decimal number
system (in which the weights are given) into the number system with base k. In
this system  is written as a n umber with the followi ng sequence of digits:
(*)  -. N-lN-2'" l/)"O.
We see that the digits in this expression indicate the kinds of coins in the
sequence of bags, taken in reverse order. This is the main idea for our solution.
Accordingly, from the total weight S of all the /vI coins selected we subtract
the weight M m of the same number of coins of the lightest kind and then represent
the difference  = S - M m in the number system with base k (we decompose into
powers of k, beginning with the highest power). This gives us a number of the form
(*). Its jth digit from the end (counting from zero) indicates the kind j of coins
in the bag with number j.

THE GENERALIZED PROBLEM OF COUNTERFEIT COINS
105
Example
In the table below we give the weights of coins contained in five bags. The
numbers on the bags are given in the top row of the table, from right to left (this is
the reverse order), and the kinds of coins are indicatcd under the weights of coins
in the bags. They are the desired numbers.
TABLE
4 3 2 1 0 number j on bag
11g 12g 109 12g 109 weight m + Aj of a coin
1 2 0 2 0 kind A j of coin
81 27 9 3 1 number k j of coins selected
In this case k = 3 and the numbers of coins taken correspond to powers of 3,
as shown in the last row of the table. We select Al = 121 coins in all. Their total
weight on the scales is S = 1351 g. Subtracting AI . m = 121. 10, we get A = 141 g.
Expressing A in the ternary number system,
A = 1 . 3 4 + 2 . 3 3 + 0 . 3 2 + 2 . 3 1 + 0 . 3 0 ,
we get the number 12020, and its sequence of digits coincides with the original
sequence of kinds given in the table.
If k = 10, then it is not necessary to translate A from one number system into
another. For the case k = 3 there is an interpretation of the solution of the problem
somewhat different from ours. We leave it to the reader to find this interpretation.
A little history
The classical problem of one bag with false coins can be found in many popular
books on mathematics. It is said that during the Second World War the English
dropped leaflets containing this problem on Gennan troops with the goal of dig..
tracting and thus disorganizing thelll; supposedly, they wasted 40,000 man-hours
on solving it.
In the book Logik macht Spass by G. Bizron and J. Herczeg (Akad. Kiad6,
Budapest, 1976, German translation from the Hungarian) the case of two bags with
false coins is considered, and this problem is solved by means of two weighings.
The classical problem of false coins has recently found applications in the theory
of coding and information for detecting errors in a code.


Truthtellers, Liars, and Deceivers
P.BLEHER
Among mathematical problems requiring quick wits, of particular interest are
logic problems. As a rule, such problems do not require special mathematical
knowledge, and they can be explained even to people very far from mathematics.
In this article we analyze four logic problems. They will involve truthtellers,
who always tell the truth, and liars, who always lie. However, the problems of
greatest difficulty, and of greatest interest as we shall see, will be those in which
we encounter also deceivers, that is, people who say anything whatsoever if only to
confuse the questioner.
PROBLEM 1. At a point where a road divides into two, one way leading to
town A where only truth tellers live and th.e other to town B where only liars live,
a mathematician meets an inhabitant of one of these towns. By asking a single
question, can the mathematician find out from the inhabitant which way leads to
town A?l
The answer in Problem 1 is positive even under the additional condition, which
we shall always hold to in this article, that the question must be phrased in such a
form that it can be answered by "yes" or "no". The question solving Problem 1 is:
"Does this road (pointing in the direction of one of the roads) lead to your tou/n?"
It is easy to see that the answer "yes" means that the road leads to A, and no"
nleans that it leads to B. Indeed, if the person asked lives in A, then he always
tells the truth and thus his "yes" means that the indicated road goes to A, and his
"no" means that it goes to B. But if he lives in B, then he always lies, and thus
his "yes" means that the road does not go to B, that is, it goes to A, and his "no"
means that the road goes to his town, that is, to B. Thus, in both cases ''yes''
means that the road goes to A and "no" means that it goes to B, as asserted.
Note that we do not determine from the answer whether we are speaking with
an inhabitant of A or an inhabitant of B, but this was not really required. The
author also knows of other solutions of Problem 1, but they are all based on the
same idea: the question of whether the particular road leads to town A must be
phrased so that a liar is forced to give a "double negative" answer. Since a double
negative answer is equivalent to a positive answer, a liar gives the same answer as
a truthteller in this case. This is what happens in the solution we presented.
The Russian original is published in Kvant 1980, no. 11. pp. 8-11.
1 Problems 1 and 2 were communicated to the author by the Hungarian mathematician
P. Major.
III,

108
P.BLEHER
The second problem we analyze is a complication of the first. This complication
involves the appearance of a deceiver among the possible respondents.
PROBLEM 2. Suppose that under the conditions of Problem 1 the mathemati-
cian meets not one but three people at the fork in the road, one of them an inhabitant
of town A. the second an inhabitant of town B. and the third a deceiver. Further-
more, the mathematician knows that among these three one is from A, another from
B. and the third a deceiver, but he does not know who is who. Can the mathemati-
cian determine the way to A by asking two questions?
We specify that each of the two questions can be put to anyone of the three
people encountered at the fork in the road, and only the person asked can answer.
htloreover, each of the people encountered knows "who is who" among the three,
and each knows which road leads to A and which to B.
The solution of Problem 1 leads us to wonder whether we can find someone
who is not the deceiver by the first question, in which case Problem 2 will have
been reduced to Problem 1, and we can learn the way to A by asking a selected
person the same question as in Problem 1. It turns out that there is such a first
question, though it is not, in the author's opinion, a simple matter to guess what
it is.
For convenience let us number the three people arbitrarily. The question is put
to the first person. Here it is: "Assume that each of you three now goes to A or to
B according to the following principle: the inhabitant of A goes to A. the inhabitant
of B goes to B. and the deceiver goes with you unless you yourself are the deceiver,
in which case you go whichever way you want. Under these conditions does this
person (pointing at the second person) go to A?"
We assert that the third person is not the deceiver if the answer is ')"es", and
the second person is not the deceiver if the answer is "no". hldeed. if we asked the
deceiver, then both the second and third persons are not the deceiver. Next, if we
asked the truthteller, then his "yes" means that the second person is the deceiver,
and hence the third person is not the deceiver. On the other hand. his "no" testifies
that the second person is the liar (only the liar does not go together with him). But
if we asked the liar, then his 'yes" means that the second person is the deceiver,
since the deceiver goes to B and the truthteller to A. and so the third person is the
truthteller. On the other hand, the liar's "no" means that the second person is the
truthteller and the third the deceiver.
After analyzing all possibilities it is not hard to see that ').es" means that the
third person is not the deceiver. and "no" means that the second person is not the
deceiver. Thus, in both cases we can find a person who is not the deceiver, and
Problem 2 is thereby solved.
As in the solution of Problem 1, the main idea is to force the liar to give a
double negative answer, that is. to ensure that his answers have the same sense as
those of the truthteller. and that they distinguish the deceiver and the nondeceivers.
PROBLEM 3. N scholars arrive at a congress of chemists; some of them are
chemists and the rest alchemists. and it is known that the majority are chemists.
A chemist answers all questions truthfully. and an alchemist always lies. A mathe-
matician shows up at the congress with the object of establishing who among all the
scholars is a ch.emist and 'who an alchemist. He is allowed to ask any scholar about
the identity of any other scholar. Find a method by which the mathematician can
clear up who is who by asking N - 1 questions.

TRUTHTELLERS, LIARS, AND DECEIVERS
109
The solution of Problem 3 is relatively simple. Namely, we ask any scholar (for
definiteness call him the first) about each of the others. As a result, these N - 1
scholars are divided into two groups: the group of those who are chemists according
to the first scholar, and the group of those who are alchemists according to the first
scholar. Let us put the first scholar in the first group. Choose the largest of these
groups. Then the scholars in this group are the chemists, and the scholars in the
second group are the alchemists (prove this!). The problem is thereby solved.
We have now come to the central problem of our article: Problem M585 (K vant
1979, no. 9). Its condition coincides with the condition of Problem 3, with the
exception that the alchemists are no longer liars but deceivers. In Problem M585 it
was proposed to clarify who is who at the conference by asking a) 4N, b) 2N - 2,
c) [3N/2] questions.
This problem is incomparably more complicated than Problem 3, again because
the answers of a liar, though incorrect, are "consistently incorrect", which enables
us to extract from them almost as much information as from the correct answers
of a truth teller. But the answers of a deceiver are arbitrary, and to extract any
information from them is a much more complex task.
The solution below aUows one to determine who is a chemist and who an
alchemist by asking even fewer than [SN /2] questions: namely, q = 3k questions if
N = 2k + 1 is an odd number, and q = 3( k - 1) questions if N = 2k is an even .
number.
Let us first assume that N is odd. We define the desired method by induction
on k. If there is N = 1 scholar at the conference (k = 0), then he is obviously
a chemist, since there are more chemists. No questions are necessary in this case:
q = 0 = 3 . O.
Assume now that for all odd numbers less than a given odd number N = 2k+ 1
we already have a method enabling us to solve the problem in the required number
of questions. We must find such a method for the number N = 2k + 1. For
convenience let us number all the participants of the conference in an arbitrary
way, and then begin asking the 2nd, Srd, ... scholars to identify the first scholar.
We stop the questioning as soon as one of the following two events takes place:
EVENT A. Among the scholars asked, most have identified him as an alchemist.
EVENT B. The number of scholars identifying the first scholar as a chemist is
equal to k.
It is clear that if Event A happens and if by this time t scholars have identified
the first scholar as a chemist and f as an alchemist, then / = t + 1. (Indeed, / > t,
and if we assume that f > t + 2, then Event A must have taken place at least
one question earlier.) Moreover, it is clear that in this interrogation we have asked
ql = / + t = 2/ - 1 questions. (A particular case of Event A is the situation when
the second scholar identified the first as an alchemist: here t = 0 and / = 1.)
But if Event B happens and / scholars have identified the first scholar as an
alchemist, then the total number of questions is ql = k + /.
It is not hard to see that the questioning stops before aU the scholars at the
conference have been asked. Indeed, assume the contrary. Then neither of Events A
and B has taken place before the last scholar is asked. Suppose that at this time
t scholars have identified the first scholar as a chemist and / as an alchemist.
Since Event A has not happened, it follows that / < t. Since Event B has not
happened, it follows that t < k - 1. Therefore, the total number of people asked
..

110
P. BLEHER
is 1 + t < 2(' - 1). Adding the first and last scholars to this number, we get that
the total number of participants at the conference is at most 2k, whereas there are
2k + 1 participants. This contradiction proves that one of Events A and B takes
place before the last scholar is asked.
Suppose that Event A happens. Then we assert that, in the group of scholars
made up of the first scholar and all the scholars who were asked, the number of
alchemists is not less than the number of chemists.
Indeed, if the first scholar is a chemist, then the 1 scholars identifying him as an
alchemist are themselves alchemists. Since there are a total of l+t+ 1 = 21 scholars
in the group under consideration, the number of alchemists in the group is not less
than the number of chemists in this case. But if the first scholar is an alchemist,
then the t scholars identifying him as a chemist are alchemists. Therefore, in this
case the number of alchemists also is not less than 1 + t = I, that is, not less than
half.
Further. since the total number of chemists exceeds the total number of al-
chemists by assumption, the number of chemists in the remaining group of N - 21 =
2(k- I) + 1 scholars must also exceed the number of alchemists. The number N - 21
is obviously less than N, therefore by t.he induction hypothesis, there is a method
enabling us to clarify who in the remaining group of scholars is a chemist and who
is an alchemist by asking q2 = 3(k - I) questions. From this group we now choose
an arbitrar)' chemist (there is clearly at least one) and ask him (this uses q3 = 1
questions) who the first scholar is.
If the first scholar is an alchemist. then the t scholars who identified him as a
chemist are alchemists. Therefore, it remains for us only to clarify, by asking our
selected chemist, who is who among the 1 scholars who identified the first scholar
as an alchemist (this uses up q4 = f questions). As a result we reconstruct a
complete picture of the partition of participants at the conference into chemists
and alchemists by asking q = ql + q2 + q3 + q.t = 21 -1 + 3(k - I) + 1 + f = 3k
questions. as required.
But if the first scholar happens to be a chemist, then the f scholars who iden-
tified him as an alchemist are themselves alchemists. Therefore. it only remains for
us to clarify, by asking our selected chemist, who is who in the group of t scholars
who identified the first scholar as a chemist. This requires q4 = t questions. The
total number q = ql +q2 +q2 +q4 = 21 -1 +3(k- f) + 1 +t = 3k -1 of questions
in this case is even less than the number of questions we are allowed to use. TIns
completes the analysis of the case when Event A takes place.
Let us now consider the ('ase when Event B takes place. \,,"c assert that in this
case the first scholar is a chemist.
Indeed, if he were an alchemist, thC.'1l the k scholars who identified him as a
chemist were also alchemists, and the total number of alchemists would be at least
k + 1, that is, more than half, and this contradicts a condition of the problem.
Accordingly, the first scholar is a chemist. and the 1 scholars who identified
him as an alchemist arc themselves alchemists. By asking the first scholar we now
clarify who is who among the k scholars who identified him as a chemist (this takes
q2 = k questions), and who is who among the remaining scholars, who did not take
part in the questioning (this uses up q3 = N -(l+k+ I) = 2k+l-l-k- f = k- 1
more quest.ions). Thus, we completely clear up who is who at the conference by
asking q = ql + q2 + q3 + q-t = k + 1 + k + k - f = 3k questions. Both the case

TRUTHTELLERS. LIARS. AND DECEIVERS
111
of Event A and the case of Event B have thereby been considered, and thus the
solution for an odd number of participants is complete.
For even N the solution of the problem repeats almost word for word the
solution we gave for odd N, and we leave it as all exercise to anyone who desires a
deeper understanding of this al'gument.


Solvable and Unsolvable Algorithmic Problems
V. A. USPENSKif AND A. L. SEMENOV
Algorithms
We all know how to add multidigit numbers-we learned this as children. Let
us think about what our knowledge consists of. When in Ionesco's play The les-
son a girl student demonstrates remarkable abilities to multiply to-digit numbers,
the shocked teacher realizes that her method is very simple: she has learned the
(infinite!) multiplication table of all numbers. It seems that our method is of a
different sort. We know a uniform finite method enabling us to solve an infinite set
of problems. In our case the infinite set consists of the problems of finding sums:
there is one problem for each pair of numbers. The method is uniform because it
is the same for all problems. The method is finite in the sense that it can be pre-
sented using finitely many words (if this were not so, then it would certainly not be
possible to teach the method!). This method is called "long addition" and consists
in writing one number (for example, 8357) below another number (for example, 64)
with their right-hand sides aligned (that is, as 83' and not, say, as 57) and
then beginning to use successively the addition table of single-digit numbers (which
must be learned in advance), carrying over to the next decimal place if necessary.
After several steps we get the result 8421.
Here we have not so much expounded the method as recalled it, since we are
sure it is known. However, it would be beneficial for the reader to write out this
method in entirety on a sheet of paper, in a way that it could be understood
and used by a person who did not know previously how to add multidigit numbers.
The exercise which we pose for the reader can be formulated scientifically as follows:
write an algorithm that solves the problem of adding numbers. We shall formulate
this and other problems involving the construction of algorithms in the following
form, indicating roughly what is required of an algorithm.
PROBLEM. Given two arbitrary natural numbers, it is required to find their
sum.
This form of expression will serve as a signal for us that the solution of the
problem consists not in finding for each two numbers their own individual method
of calculating the result, but in finding a uniform general method that works for all
pairs of numbers, that is, finding an algorithm (in this case an addition algorithm).
In this article by an algorithm we mean any finite system of rules which deter-
mines a computational process. This process begins by presenting (supplying the
The Russian original is published in Kvant 1985. no. 7. pp. 9-15.
1 : 0\

11-1
V. A. USPENSKII AND A. L. SEMENOV
input of the algoritilln) an arbitrary initial datum (arbitrary, but selected from a
set that is fixcd for thc particular algorithm). The process may end in a result
that is completely determined by this initial datum; we then say that the result
appears at the output of the algorithm. However, the process may also continue
indefinitely, and an algorithm does not always yield a result. For example, the
algorithm writing out the quotient of two numbers as a decimal fraction may never
stop (1 : 3 = 0.33333. . .).
The concept of an algorithm is one of the basic concepts in mathematics. The
theory of algoritllms together with mathematical logic forms a fundamental theo-
retical basis for constructing and using computational techniques. It is the avail-
ability of algorithms for various problems that enables us to solve these problems
on a computer.
Th" very tenn "algorithm" is interesting. Indeed, are there many tenns in
science with a geographical name in their composition? You may not discern such
a namc at once in the word "algorithm", but it is there: it is the name of the
city "Khwarizm". At the root for the term algorithm is the name al-Khwarizmi
(which means "from Khwarizm"), a great mathematician of the ninth century. In
September 1979 some of the world's most prominent mathematicians and experts
on algorithms paid tribute to the founding role of al-Khwarizmi and gathered in
the city of Urgench in the Khwarizm (Khorezm) Province of Uzbekistan to discuss
pressing questions in the theory of algorithms and its applications on the modern
stage. Academician A. P. Ershov, one of the organizers, has given a detailed account
of the meeting in K vant 1984, no. 8, p. 29.
We are going to demonstrate to the reader the most famous and intuitive ex-
amples of unsolvable algorithmic problems, that is, algorithmic problems for which
there are no solutions. For contrast, these examples will be paired with examples
where there is an algorithm (though sometimes a very complex one) or where the
question of the existence of an algorithm has not yet been resolved.
Solution of algebraic equations
We are interested in the solutions of the equation
(1) x 2 +2=y3.
In this case a solution is a pair (a, b) of numbers subject to the condition that
a 2 + 2 = b 3 ; for exanlple, the pair (5,3).
In solving an equation it is always necessary to know precisely what numbers
can be taken as solutions. If, for example, the solution of the cquation is the increase
in the number of goats in a herd over some period of time, then we hardly find the
answcr "two-thirds" suitable (howcver, th(> answer "negative ten" will make sense:
it means that the number of goats in the herd unfortunately did not increase but
decreased). For equation (1) we may bc interested in its real solutions (that is, pairs
of real numbers), rational solutions (pairs of rational numbers), or integer solutions
(pairs of integers). This equati on has infinitcly many real solutions: it suffices to
take any a and then set b =  a 2 + 2, and then the pair (a, b) will b e a solution
(question to the reader: can we take any b and then set a = y b 3 - 2 ?). It is not
hard to prove that (1) has infinitely many rational solutions; (0.383,0.129) is one
of them. There are only two integer solutions: (5,3) and (5, -3). But this is not
eay to prove.

SOLVABLE AND UNSOLVABLE ALGORITHMIC PROBLEMS
115
The solution of equations in integers is a very old problem (Pythagoras himself
studied it in the sixth century BC), and in general it is very diffic'ult. The main
difficulty lies in determining whether a given equation has at least one integer
solution. For example, it is unknown (in any case it was unknown until fairly
recently) whether the equations :r 3 + y3 + z3 = 30 and x 4 + y4 + z4 = u 4 have
integer solutions.
PROBLEM FOR THE READER. For each of the equations x" + y4 = 5z 2 J 3:("2 -
y2 = I. and x 2 + y3 = Z4 find a solution in the integer.s or prove that there are no
such solutions.
HINT. One can read about these and other equations in the integers in the
following popular pamphlets: A. O. Gel/fond, The solution of equations in the
integers, Popular Lectures in lvlathematics, no. 8, lvIoscow, 1952 (English transl.,
Freeman, San Francisco, 1961); W. Sierpinski, On the solutions of equations in the
integers, lvIoscow, 1961 (Russian; Polish original, PAN, Warsaw, 1956).
The problem of determining whether an arbitrary algebraic equation with in-
teger coefficients has a solution in the integers is one of the 23 so-called Hilbert
problems. '1Vhat are these problems?
When David Hilbert (1862-1943), one of the greatest mathematicians of the
twentieth century, prepared his address to the International Congress of lvIathemati-
cians in Paris in 1900, he selected 23 problems from diverse areas of mathematics.
These problems were his attempt "to penetrate into the forthcoming advances of
our science and into the secrets of its development in the new century." This at-
tempt turned out to be extraordinarily successful and valuable. Even to this day
a solution (even a partial solution) of one of Hilbert's problems is assessed in the
whole world as a high mathematical a.chievement. As a necessary requirement for a
really fundamental problem Hilbert suggested that the content of the problem could
be explained to virtually anyone. The problem of the existence of integer solutions
is the tenth problem in Hilbert's list. The reader himself can judge to what degree
its formulation is generally accessible. We now formulate Hilbert's tenth problem
according to the standards adopted here.
PROBLEM 1 (Hilbert's Tenth Problem). Given an arbitrary algebraic equation
with integer coefficients, it is required to find out whether it has solutions in the
integers.
THE DESIRED ALGORITHM. In 1970 the Soviet mathematician Yu. V. !\1atiya-
sevich proved the impossibility of an algorithm solving this problem (see lvIatiyase-
vich's article in the previous Kvant Selecta 1 ).
In connection with this problem we should add an observation that is applicable
not only to it but also (with appropriate modifications) to other cases. An algorithm
for finding a solution of any equation which is known to have a solution does exist!
Indeed, here is such an algorithm: simply substitute in the equation all tuples of
natural numbers. Eventually we will find a tuple satisfying the equation.
We present several natural modifications of the first problem.
1 Kvant Selecta: Algebra and Analysis. II. Mathematical World. vol. 15. Amer. Math. Soc..
Providence, RI. 1999. pp. 13-24.

116
V. A. USPENSKII AND A. L. SEMENOV
PROBLEM 2. Given an arbitmry algebraic equation with integer coefficients, it
is required to determine whether it has solutions in the real numbers.
THE DESIRED ALGORITHM. In this case it exists! A solution of Problem 2 was
obtained by the well-known Polish logician and mathematician Alfred Tarski in the
1940s. We shall discuss the use of this result below. Actually, Tarski constructed a
nlore general algorithm which enables one to determine the existence of solutions
of systems of equalities and inequalities.
To assess the degree to which Tarski's algorithm is nontrivial, try to solve
the following problem. Given an arbitrary algebraic equation in one variable with
integer coefficients, it is required to determine whether it has a solution in the real
numbers. (It is clear that this problem is a simple particular case of Problem 2.)
If the degree of the equation is odd, then we can answer at once that the equation
has a root. But what if the degree is even?
PROBLEM 3. Given an arbitrary algebraic equation with integer coefficients, it
is required to determine whether the equation has a solution in the rational numbers.
THE DESIRED ALGORITHM. In this case it is not known whether an algorithm
exists or not.
You see how close to each other our Problems 1, 2, and 3 are: the formulations
differ by only one word. And yet the answers to the question of whether or not
there exists a corresponding algorithm are different. 'D:uly surprising!
Transformation of words
In mathematics, words are defined to be arbitrary finite sequences of symbols.
For example, 1985 is a word of length 4. Words not only need not have any
particular meaning, they can even be unpronounceable. Thus, BRDRHSCO is a
word made up of English letters (and oflength 8), but it is not a word in the English
language. As a rule, the initial data for algorithms are words. When an algorithm
is defined, a set of letters is also defined, that is, symbols used to form the words
that serve as inputs to the algorithm. Such a set is called an alphabet. Alphabets in
which text is written in natural languages and programming languages and in which
books are printed contain at most a few hundred letters. The numbers in "school"
algorithms are words in the ten-letter alphabet consisting of the letters 0, 1.2, . . . ,9.
As we know, these letters are called digits. and to write decimal fractions we need
one more letter in addition to the ten digits: the decimal point.
Modern computers operate with binary words consisting of the letters 0 and 1.
To illustrate the flexibility and capacity of the "word" concept we remark that a
pair of words can be coded by a single word, for example, by putting between the
members of the pair a letter that is not in the alphabet in which these members are
written. Thus, as initial data for algoritlmls it is sufficient to consider words, and
not pairs, tliples, ... of words as initial data. We remark further that it is often
convenient to consider the word of length 0; it is called the empty word, since it
does not contain any letters at all.
Many of you must have played the following game. You are told, for instance,
"Change a wolf into a goat." Solution:
WOLF -+GOLF -+GOLD-+GOAD-+GOAT

SOLVABLE AND UNSOLVABLE ALGORITHMIC PROBLEMS
117
What is a single step of the change? It consists in replacing any letter of the
word just obtained by any other letter of the English alphabet in such a way that
the resulting object (a word in the mathematical sense of the word) is again a
meaningful word in English.
We now simplify the game by forgetting that among all sequences of letters
only words in the English language can appear. We allow all (in the mathematical
sense t that iS t both meaningful and meaningless) words in the English alphabet.
Can a wolf then be changed into a goat? Wellt this is now quite easy:
WOLF --. WOLT--. WOAT--.GOAT
Perhaps now any word can be changed into any other word. Of course not: the
words must be of the same length. But this condition is also sufficient!
PROBLEM. Given two words in the English alphabet, it is required to find out
whether one can be obtained from the other by a sequence of replacements of one
letter by another letter.
THE DESIRED ALGORITHM. Compare the lengths of the words. If they are the
same, then the answer is YES, and if they are not the same, then the answer is NO.
We remark that the original problem t that of meaningful alterations of a given
word in the English language, is also clearly solvable. To solve it we need only a
(finite!) dictionary of all the English words that can be used in the ganle, together
with a sufficient supply of time and paper. An easy computation shows that this
problem can be solved in practice on a modern computer.
Let us now again forget about the English language (but not about the alpha-
bet) and understand words to be arbitrary finite sequences of English letters, and
let us complicate the problem in another respect. Instead of being allowed to re-
place any letter by another letter (at any place in the word)t we choose some finite
list of admissible substitutions. For example, this list could be
A
!
B
BBB
!
AA
BA
!
ABA
As earlier, the transformation of a word in one step will consist in that at any place
in the word we replace an admissible fragment by a fragment that is allowed to
replace it. Further, all the admissible substitutions are invertible: if the fragment
X is allowed to replace the fragment Y, then Y is also allowed to replace X. For
example, if the list of admissible substitutions is the one we have just chosen, then
the transformation in one step can be: BAAB--.BBBBB, or BAB--.ABAB, or
BABA--.BAAA.
PROBLEM. Given two words in the English alphabet, it is required to find out
whether one can be changed into the other by using the following system of admis-
sible substitutions:
AV
!
VA
BV
!
VB
AU
!
UA
BU
!
UB
DVA
!
VD
DUB
!
UD
VVA
!
WAD
THE DESIRED ALGORITHM. In this case it does not exist. This was proved by
the Soviet mathematician G. S. Tsertin, who invented this system of substitutions.

118
V. A. USPENSKII AND A. L. SEMENOV
A similar problem in general form (that is, for an arbitrary system of admissible
substitutions) was first posed by the well-known Norwegian mathematician Axel
Thuc ill 191.... He himself proved the existence of an algorithm in a number of
special cases.
TIme singled out the cases where in every admissible substitution one of the
terms is t.he empty word, and thus every admissible substitution amounts to being
able to insert, at any place of a given word, the word indicated in the substitution,
or to deletc it. For example, by inserting and deleting the words AB and BA we
can get the word BABAB from ABBBA. Try to construct the desired algorithm,
i.e., an algorithm that determines when one word can be transformed into another
by inserting and deleting of AB and BA, that is, for the following list of admissible
substitutions:
AB BA
t t
empty word empty word
(even this elementary example is important for the area of algebra known as "group
theory" ).
For any set of admissible insertions-deletions, there exists an algorithm estab-
lishing whether it is possible to change one word into another. This was shown by
the Soviet mathematician S. I. Adyan in 1966.
Elementary geometry
Here we cannot give a thorough definition of what elementary geometry is in the
strict sense; this can be made precise using mathematical logic. We try, however, to
give a rough description. The primitive concepts of elementary geometry are points,
lines, planes, segments, circles, spheres, the relations "lies on'" ulies between", U are
congruent", and so on. The formation of new concepts is allowed, but without the
use of dots ( . .. ) and the phrase "and so on" (here the rigorous mathematical-logic
perception of elementary geometry departs from the vague traditional one). For
example, the concept of triangle belongs to elementary geometry: a triangle can
be defined as three segments AIA2' A3A.h AsA6 such that ..h = .-13. A-l = As,
and A6 = AI. But the general concept of a polygonal line does not belong to
elementary geometry, because its definition contains dots and the words u al1 d so
on": a polygonal line is a set of segments AIA2' A3A.s,..., An-I, .-i n (here are the
dots!) such that A 2 = A3, A4 = As, and so on.
PROBLEM. Gi11en an assertion in elementary geometry. it is required to check
whether it is true.
THE DESIRED ALGORITHM. It ('xists. The existence of an algorithm was in
essence established by Tarski in the 1940s and follows in a fairly simple way from
the existcncc of his algorithm that we discussed earlier. The connection between
problems in algebra and geometry was discovered long ago (analytic geometry),
and it is natural that this connection extcnds to algorithmic problems.
Tarski's result appears to be, and actually is, extremely powerful and even
paradoxical. There is a very extensive area of classical mathematics (namely, ele-
mentary geometry) which is traditionally thought to require a subtle intellect and
which can by no means be reduced to carrying out routine computations, and yet
at the same time there is an algorithm that can verify the truth of theorems in this

SOLVABLE AND UNSOLVABLE ALGORITHMIC PROBLEMS
119
FIGURE I
area (and if necessary, can also find their proofs). We can console ourselves only in
the fact that Tarski's algorithm is not realistic: it requires an inconceivably great
amount of time for its implementation.
It is useful to realize how soon we encounter some geometric assertions whose
truth or falseness is presently unknown despite the existence of the general algo-
rithm.
Here is an intuitive example. Let us take twelve round jars of the same diameter
(equal, say, to IOcm). We want to pack them, standing upright, in a round box.
This can be done, for exa.mple, as in Figure 1. However, it is possible to arrange
the jars even more closely, so that a box of smaller size can be used; for example,
as indicated in Figure 2. Finally, the packing shown in Figure 3 enables us to
use an even smaller box. We can ask whether we can find a round box of still
smaller diameter in which we can fit all our jars. No one knows the answer to
this question, even though the answer can be obtained with the help of Tarski's
algorithm: just apply the algorithm to the assertion that the third packing is best
possible, and consider what is obtained as a result, YES or NO. However, this
method is not realistic. since an astronomically long time is needed to get the
result of the algorithm.
Example of a proof of unsolvability
Assume that we work in a computer centel" This center has a wonderful com-
puter, which can perform calculations according to any program p written in a
certain programnling language, that is, from an input datum m it can find the
result p( m) of the program p (provided that it is defined, of course).
The programs can be numbered (for example, in alphabetical order. with each
program regarded as a word in the symbols of the programming language), so that
we have the library of all programs:
PI1P2,...,Pn,'.' .
It is best to deal with programs p that give a res1Llt p(m) for any input datum
m. For exanlple, a standard program for computing the function y = m 2 + 5711 - 6
is such a program. Unfortunately, there are programs that do not terminate their

120
V. A. USPENSKII AND A. L. SEMENOV
FIGURE 2
FIGURE 3
operations for certain values of the input data: there is an "endless loop", as
programmers say. For instance, the program for computing the decimal expansion
of the value of the function y = m/3 does not give a result when m = 10.
This situation is very unpleasant. For if we use such a program on the computer
together with "bad" initial data, then the computer will never stop, and we are
just wasting expensive computer time. To avoid this, it would be nice to have a
procedure (an algorithm!) that would tell us in advance from the number of the
program whether or not the program with this number will give a result with the
chosen input data.
PROBLEM. Given an arbitrary pair (n, m) of natural numbers, it is required to
construct an algorithm determining whether the operation of the nth program Pn
terminates when the input datum is m.
THE DESIRED ALGORITHM. It does not exist in this case, and we now prove
this.

SOLVABLE AND UNSOLVABLE ALGORITHlvllC PROBLEIS
121
PROOF ( Cantor diagonal process). Assume that the desired algorithm A exists.
We compose a table of all programs and all initial data:
PI (1) PI (2) . . . PI (7n)
P2(l) P2(2) ... P2(m)
Pm(l) Pm(2) ... Pm(m) ...
and we single out the diagonal.
Let us consider a program 15 the result of which "is different on the diagonal";
for example, it can be defined by the rule
_ ( ) { Pm(m) + 1 if Pm (7n) is defined . '
P 7n =
o if Pm (7n) is not defined.
This really is a program, that is, P can be computed with the help of an algorithm.
(Namely: check the condition "Pm(m) is defined" according to the algorithm A; if
this condition is satisfied, then we calculate Pm(7n) and add 1, and if 110t, then we
set 15(m) equal to 0.) But then 15 is on the list of all progranls in the library, and it
has a number k. Let us consider Pk(k) (which is on the diagonal!).
If Pk(k) is not defined, then 15(k) = 0, and hence p(k) =1= Pk(k). If Pk(k} is
defined, then 15(k) = Pk(k) + 1 =1= Pk(k}. In both cases 15(k) =1= Pk(k), which is
impossible, because 15 and Pk are one and the sanle program. This contradiction
concludes the proof.
The reader may possibly want to know why the proof above is called the "Can-
tor diagonal process". The fact is that the beautiful method of proof used here was
invented by the German mathematician Georg Cantor (1845-l9l8), the founder of
set theory. Actually, Cantor was establishing a very different statement: he was
proving that the set of real numbers cannot be enumerated by the natural num.bers,
that is, it is impossible to compile a list d 1. d2, d 3 , . .. of all real numbers. (To the
reader who finds this result obvious- "there are surely many more real numbers
than natural numbers" -we suggest proving that the rational numbers can be enu-
merated, even though there are also "many more rational numbers than natural
numbers." )
Following Cantor, we prove (by contradiction) that not even the set of real
numbers on the interval [0,1] can be enumerated. Assume that we have been able
to enumerate them. We arrange our numbers, represented as decimal fractions, in
the cOlTesponding order:
0.ala2 a 3 .. .
O.b I b 2 b3 . . .
O.CI C2C3 . . .
...........
(Here the letters a, b, c, . .. with subscripts denote the decimal digits 1,2,. . . .9. 0.)
We now produce a number in [0,1] that is not on our list. namely. a number whose
digits are "different on the diagonal". Consider the number O.abc. . .. where a is
any digit different from aI, b is any digit different from b2, C is any digit different
frOln C3, and so on. Contradiction!
Let us summarize. We have become familiar with the concept of an algorithm-
a very hnportant concept in contemporary mathematics and information science.

122
V. A. USPENSKII AND A. L. SEMENOV
Of course, many specific algorithms (for example, the algorithm for long addition
or the Euclid algorithm) have been known for a very long time, but the general idea
of an algorithm was formulated only in the first half of the 20th century. Every
at.t.C'lllpt. to use computers for solving some problem begins with the construction of
an algorithm that solves this problem. It is impossible to write a suitable computer
program unt.il there is such an algorithm. And if it happens that the desired algo-
rithm does not exist, then it is meaningless to try to write a program. Therefore,
results on the impossibility of various algorithms have an obvious practical signif-
icance. Ivloreover, arguments leading to a proof of such an impossibility enable us
to penetrate more deeply into the nature of the very concept of ualgorithm" .
The following question may occur to the reader: can every algorithm be pro-
grammed, that is, can it be tunled into a computer program? Answer: yes, theo-
retically. The word "theoretically" means here that the answer is affirmative if we
allow programs that are arbitrarily long (so that there may not be enough sheets of
paper, pencils, or ink on the whole Earth to write them) and that run for arbitrarily
long time (for example, trillions of years). We remark that this kind of assumption
is deeply rooted in mathematics. (We allow polygons with any number of sides;
and we believe that the algorithm for long addition enables us to add numbers of
any size, although we realize that if the summands have more decimal places than
there are atoms in the Earth, then it is not quite clear how to write such summands,
and the number of steps in adding them is astronomically large.) Furthermore, the
possibilities of computational techniques are continually growing. While the first
computers could perfonn hundreds of operations per second and were controlled
by programs composed of dozens of commands, modern high-speed computers have
reached hundreds of millions of operations per second, and the sizes of their pro-
grams can be hundreds of thousands of commands. 2 It is commonly thought that
computer power increases tenfold every five years. Nevertheless, estimates of the
size of an algorithm and the number of steps in its operation are of paramount
importance. But this is a topic for separate serious discussions.
2EDITOR'S NOTE. This article was written in 1985. Present day computers are much faster.

Best Bet for Simpletons
P. A. PEVZNER
"FUnny you don't gamble none," Shorty said to Smoke on(' night
in the Elkhofn. "Ain't it in your blood?" "It is." Smoke answered.
"But the statistics are in my head. I like an even break for my
money. "
Jack London, Smoke Bellew
You surely know the game Heads-Tails: player A chooses one side of a coin
(fOf example, heads: H), and he communicates this to B, who takes the other side
(tails: T). Then the coin is tossed. No one doubts that tIns is a fair way to settle
disputes.
In 1974 lYIaxtin Gardner, in the article "On the paradoxical situations that
arise from nontransitive relations," acquainted the readers of Scientific American
with the same kind of "fair" game, which he called "Best bet for simpletons". This
game is similar to Heads-Tails, except that the players think up words not of a
single letter, as in Heads-Tails, but of several letters. For example, player A thinks
up the word HTH and tells B; in turn, B thinks up a word of the same lcngth,
for example, HHT. Of course, the chosen words must not coincide, and this is why
A tells B. After this, the players begin to toss the coin, writing down the result
of each toss. For instance, after 6 tosses with outcomes tails, heads, tails, tails.
heads, tails the sequence THTTHT is written. The game ends when the word
chosen by A or B appears at the end of the sequence written. In the first case A
wins, and in the second case B. Thus, the winner is the player whose word appeal'S
first. For example, if H appears at the seventh toss of the coin, then A wins. since
THTTHTH will be written (the boldface letters single out A's word, which has
appeared in the sequence). If at the seventh toss the result is T. then the gall1e
should continue (since neither HTH nor HHT is contained in THTTHTT). In the
case when the eighth, ninth, and tenth tosses give H, H, T the player B wins, for
THTTHTTHHT will be written.
If you play the game Heads-Tails, then the choice of heads or tails is a matt.er
of taste, since Hand T are equally likely. At first glallCe it seems that all the
words in "Best bet for simpletons" are equally likely. But in 1969 t.he creator of
this grone, Walter Penney, discovered that not all words are on the same footing.
lYIost mathematicians fanliliar with the rules of the game refused to believe this
at first. Nevertheless, it is so. For many pairs of words the choice of one of them
The Russian original is published in Kvant 1987, no. 5, pp. 4-8, 15.
1 :!:\

124
P.A. PEVZNER
(the "stronger" word) givcs an advantage to the player making this choice: this
player wins more often than his opponent; the game is not fair. Moreover, there is
a formula enabling us to express this advantage quantitatively.
Associatcd with this formula is an almost detective story. Gardner presented
it in his article, citing as the source a letter received (without proof) from the well-
knownmathel11atician John Conway from England. Gardner admitted that he had
no idea how to prove it, and surmised that it had been obtained by "wizardry",
like many other results of Conway.
Conway's arguments concerning the problem have not yet appeared in print,
but at the end of the 1970s and beginning of the 1980s his formula was proved inde-
pendently and by different methods by severallnathematicians at once. However,
all these proofs use a fairly complicated mathematical apparat.us, and the formula
appears in them as a miracle: by manipulating with some complicated fractions.
It turns out that there is an elementary proof of Conway's formula, and we sketch
it in the conclusion of this article. Ioreover, there is now a simple algorithm for
finding the best response for the second player, although the original remarkable al-
gorithm (for three-letter words) in Gardner's article (due to his colleague B. Wolk)
is similar in obscurity and complexity to the alchemist's prescriptions for obtaining
the philosopher's stone.
But we digress. We have not explained why not all words in our ganle are on
the same footing.
What word is stronger?
Let us consider a concrete example. Suppose that in the game with two-letter
words player A bets on the combination TT, and B on the combination HT. Then
A wins only if the first two tosses result in TT. If t.he result is HT, then B wins
immediately, and if TH or HH, then B also wins, although not immediately: namely,
in the last two cases B wins as soon as a toss results in T (and this will happen
sooner or later, because H cannot always result if the coin toss is fair). Thus, of
the four equally probable cases (TT, HT, TH, HH) player A. wins in only one case
(TT), that is, the chances of A winning are three times worse than the chances of
B winning.
In connection with the game with two-letter words it is worth pointing out
that a smart player A will not choose the word TT (just as he will not choose HH).
He chooses HT (or TH), and then his chances of winning and losing are the same,
unless, of course, B chooscs one of the "weaker" words HH or TT (verify!).
But. if we pass to three-letter words, thcn the picture changes fundamentally.
Namely: whatever three-letter word A. chooses. h.is opponent B can choose another
word that gives him better chances of winning.
How can this be. you ask-why would player A not choose the "strongest" word,
since he chooses first'! But. the fact is t.hat there is no strongest word. Figure 1
clarifies the situation intuitively, All three-letter words in Hand T are written out
in it. and the arrows between two words show which of the two is stronger (that is,
has the better chance of winning).
Look at Figure 1: from each word at least one arrow goes out of it; hence, for
any word there is a stronger word, that is, no word is the strongest of all. Look at
t he cycle of words TTH, HTT, HHT, THH, TTH. We see that from the assumptions
t.hat the word X is stronger than Y and Y stronger than Z it does not at all follow

BEST BET FOR SIMPLETONS
125
HTH
HHT
HHH THH
FIGURE 1
that X is stronger than Z (a situation that often occurs in sport). Mathematicians
say that the relation of "being stronger" is not transitive (the title of Gardner's
article comes from this). Having Figure 1 at his disposal, player B, guided by the
arrows, can always respond to a choice of A by choosing a stronger word. And then
B will win more frequently than the opponent.
But how much more frequently? And why Figure 1 reflects the real situation
correctly? We shall try to answer these questions.
Estimation of the chances of winning
Let us return to the two-letter game. As before, we assume that the naive
player A chooses the word A = 11, while his clever opponent bets on the word
B = 01 (instead of H and T we now write the digits 0 and 1, and we denote a
player and the word he chooses by the same letter). A sequence of coin tosses
for which A wins will be called an A-series (a B-series is defined similarly). For
example, 11 is an A-series, and 01, 001, 0001, 101, 1001, and 10001 are B-series.
Obviously, 11 is the only A-series (that is, A wins if and only if the first two
coin tosses yield 1). Further, it is equally obvious that each B-series has the form
0.. .1 or 10...1 (the dots stand for any number of zeros).
So, 11 is the only A-series. Let us try to determine the probability! of A
winning, that is, the fraction of cases in which the sequence 11 appears after two
tosses.
There are two possible outcomes (0 and 1) of a single coin toss, and the probabil-
ity of each is i. There are four possible outcomes of two tosses, and the probability
of each is !. Consequently, the probability of A winning is ! (that is, he wins in !
of all cases):
1
P(A,B) = P(!I) = 4
(P(A, B) denotes the probability of A winning over B, and P(I!) denotes the
probability of the series 11).
1 We do not define here the concept of probabilitYi in our article the words "probability" and
Ilfraction of cases" are synonymous. To the reader desiring to know more about this concept we
recommend the book Introduction to probability theory, by A. N. Kolmogorovand I. G. Zhurbenko
(ICNauka", Moscow, 1978 (Russian».
d".

126
P. A. PEVZNER
TABLE 1
 00 01 10 11
00 1/2 1/4 1/2
01 1/2 1/2 3/4
10 3/4 1/2 1/2
11 1/2 1/4 1/2
As a result of n tosses there are 2 n (equally likely) outcomes; consequently, the
probability of each selies of length n is 1/2n. To get the probability PCB, A; n)
of B winning in n or fewer steps, we must find the probability of each B-series of
length < 71 and then sum these probabilities. We get
n-l
,...."...-.,
PCB, A; n) =P(OI) + P(OOI) + . . . + P(O. . .01) n-2
,...."...-.,
+ P(101} + P(1001) + ... + P(IO... Ol}
= ( ! + ! + . . . + .!. ) + ( ! + .!. + . . . + .!. ) =  -  .
4 8 2 n 8 16 2 n 4 2 n - 1
Consequently, B wins over A in n or fewer steps with probability which for
large rz is very close to 3/4. The probability that after rz tosses nobody has won
is equal to 1/2n-l (that is, is negligibly small for large rz). Passing to the limit
as n  00 in the equality P(B, A; n) = 3/4 - 1/2n-l, we obtain the probability
PCB, A) of B winning over A when the game continues "indefinitely":
3
P(B,A) = 4'
The probability of wiIming for arbitrary two-letter words A and B is shown
in Table 1 (the number at the intersection of a B row and an A column gives the
probability of B winning over A). This probability is 110t liard to compute.
Estimation of the advantage (odds)
From Table 1 we construct Tabl 2, which gives the odds favoring B over A:
(I)
P(B.A)
d(B,A) = P(A, B) .
Tabl(' 3 givp.s the odds for all three-letter words. It was using this table that
we ('ollstrl1cted the "llontransitive" graph shown in Figure 1.
But how were the numbers in Table 3 found? Unfortunately, formula (1) is not
very suitable for comput.ations when the lengths l of the words are > 3. Even for
three-letter words A and B the task of finding peA, B) directly is very unpleasant,
and for large l it is hopeless. But here the "wizardry" comes to our aid.

BEST BET FOR SIMPLETONS
127
TABLE 2
 00 01 10 11
00 1 1/3 1
01 1 1 3
10 3 1 1
11 1 1/3 1
TABLE 3
I 000 001 010 011 j(JO 101 110 111
000 1 2/3 2/3 1/7 5/7 3/7 1
001 1 @ @ 1/3 5/3 1 7/3
010 3/2 1/2 1 1 1 3/5 7/5
011 3/2 1/2 1 1 1 @ 0
100 0 @ 1 1 '// 1 1/2 3/2
101 7/5 3/5 1 1 1 1/2 3/2
110 7/3 1 5/3 1/3 @ @ 1
111 1 3/7 5/7 1/7 2/3 2/3 1
Conway's formula
Conway's formula enables us to find d(B, A} for arbitrary B and A without
computing any probabilities. To explain this formula, we must define the Conway
polynomial Cx}- (t) of words X and Y.
X = 100100
Y = 001001
001001
001001
001001
001001
001001
corr_ )(, Y
o
1
o
o
1
1
initial segment of X before Y
1
1001
10010
FIGURE 2

128
P. A. PEVZNER
In Figure 2 the word Y is written six times under the word X, with each new
Y shifted one place to the right relative to the previous one (for n-Ietter words Y
would be written n times under X). To each shift of Y we assign the number 1 or
0, depending on whether or not the letters of Y that are directly under letters of
X are all the same as those corresponding letters of X. The word (of length n) of
Os and Is obtained in this way is called the correlation of X and Y and denoted by
(XY). For instance, for the second (shifted) copy of Y the common positions for
the two words contain the same values, and therefore in the second row in Figure 2
we write 1, the second letter of the word (XY). In our example, (XY) = 01001l.
In the general case let (XY) = e1... en (where each ei is 0 or 1). Then the Conway
polynomial of the words X and Y is defined to be
CXy(t) = e1 + e2t +... + e n t n - 1 .
In our case CXy = t + t 4 + t 5 .
A very strange definition! In any case it is quite unclear how anyone could have
thought of it. But it works-Conway's formula is based on it:
(*)
d(B, A) = CAA() - CAB() .
CBB(2) - CBA(2)
We can understand Gardner when he ascribes the derivation of this unusual formula
to "otherwordly" forces: this is just wizardry!
Before touching on the proof of formula (*), we explain how to use it. We
must first find the correlations (AA) , (AB), (BB), and (BA). Then we write
four corresponding Conway polynomials, set t = ! in each of them, and, finally,
substitute the resulting numbers in (*). A concrete example is given in Figure 3.
X = 100100, Y = 001001
(XY) = 010011, CXy(t) = t + t 4 + t 5 , CX}" ( !) = 
X, Y initial segments: 1,1001,10010
(YX) = 001001, Cyx(t) = t 2 + t 5 , Cyx(!) = :2
Y, X initial segments: 00,00100
(XX) = 100100, Cxx(t) = 1 + t 3 , Cxx = 
X, X initial segments: 0,100
(YY) = 100100, Cyy(t) = 1 + t 3 , Cyy(!) = 
 Y initial segments: 0,001
d(Y, X) = (Cxx(!) - CXy(!»(C yy (!) - CYX(!»-1
- ( 2 _ 19 )( 2 _ .2. ) -1 _ !!
- 8 32 8 32 -27
FIGURE 3
Having the table of odds and knowing the word A, the second player easily finds
an optimal response B. To this end it is only necessary to find the maximum
value in the column under A. For example, dmax = 7 if the first word is A = 000
(Table 3), and he should take B = 100. This ensures a seven-fold advantage. The
maximal elements in the columns of Table 3 are circled. All of them are at least

BEST BET FOR SIMPLETONS
129
2; consequently, whatever A chooses, B can respond in such a way that he has at
least a double advantage in the game.
How should the responding word be chosen?
\Ve have already explained how to do this. But we assumed that the table of
odds was composed in advance. Is it possible to find directly from the word A an
optimal response B without computing the whole table (or a whole column of it,
which has length 2')?
This turns out to be possible. We discuss how to do it.
Suppose that player A chose the word A = ala2... a, (l > 2, and each ai is 0
or 1). Then player B should choose a word of the form B = bl'.. b, with
b2 = aI, b 3 = a2, . . . ,b, = a'-l
(so far, the first letter bl of B is not fixed).
In this case, if A is written under B and shifted one place to the right,
B =b1b2b3'.' b,
A = ala2... a'-la"
then all the corresponding letters (written one under another) coincide. Therefore,
the first term in the polynomial CBA(t) is ! at t = !. We thus try to maximize the
value CBA(!) in Conway's formula. In general, the proposed choice of an optimal
response is based on an analysis (fairly subtle) of Conway's formula, and we shall
not go through this.
It remains to explain how to choose b l . Let A' = ala2... a'-l and let r be
the minimal positive integer such that after A' is shifted r places to the right the
corresponding letters coincide:
A' = al . . . a r a r +l . . . a'-l
A '= a a a a
1 . .. l-r-l l-r... I-I
(that is, al = ar+lt a2 = a r +2,'" ,a,- r -l = ai-I). Then the letter b 1 should be
chosen according to the rule b l :F a r (for example, if A = 100100, then r = 3, and
hence choose B = 110010).
The American mathematicians J. Guibas and A. M. Odlyzko proved in 1981
that this choice of B is optimal. Moreover, they proved that the number
minmaxd(B,A)
A B
(that is, the odds favoring B over A for A's best choice of his word) tends to 2 as
l grows. In other words, for the indicated choice the response of the second player
wins on the average twice as often as the most clever first player. It remains for us
only to give the promised proof.
Sketch of the proof of Conway's formula
Words A and B of length l > 2 are given. Denote by SAthe (infinite) set of
truncated A-series, that is, all words obtained from A-series by deleting their last l
letters; SB is defined similarly. Let ml,.'., mk be the places where there are Is in
the word (XY) (recall that (XY) is the correlation of words X and Y). Let Hxy
denote the set of k words formed from the first mI, . . . ,mk letters in X, respectively.
,,-

130
P. A. PEVZNER
If A[ and H are arbitrary sets of words, then we write M * H for the fusion of M
and H, that is, the new set formed from all the words of the form XY (the words
)( and Yare written in succession to make a single word, X E 1\1, Y E H). Recall
that P(X) denotes the probability that the word X appears in the course of the
gaIue with the words A and B, and peA, B) is the probability of A winning over
B. Conway's formula is a consequence of the following three assertions (the proof
of each is left as a problem for the reader).
1. For any words X, Y of length I,
Cx}'() = L peS).
SeHx\'
2*. The set T of all words containing neither A nor B (that is, sequences for
which neither player has yet won) can be represented in the form
Tl = (SA * HAB) U (SB * HBB),
T2 = (SB * HBA) U (SA * HA A ),
and Tl = T2 = T (these two formulas define the same set T).
3. The sums of the probabilities of the words in Tl and T 2 are expressed by
the formulas
L peS) =2' [peA, B)CAB(!) + PCB, A)CBB(!)] ,
seT!
:L: peS) =2 ' [P(B,A)CBA(!) + peA, B)CAA(!)]'
seT2
To prove Conway's formula it remains only to equate the right-hand sides of
the last two equalities (this is possible because Tl = T2) and to use the definition
deB, A) = PCB, A)/ peA, B).
For the interested reader we present some problems.
Solved and unsolved problems
1. Suppose that we toss not a coin but a die. and a word made of digits
1,2,3,4,5,6 is chosen. Prove that the odds fa.voring t.he second player over the first
can be expressed by the formula
deB A) _ CA.-\() - C.4B()
, - CBB() - CB.o\() .
2. It is unknown how A should play in order to minimize his losses when I > 3
(in the game with a coin).
3. Th case where A choos('s an11-letter word and B chooses an 7lt-Ietter word
(111 > n) has not been investigated. What might be an optimal strategy in this
case?
4. No strategy is known for any of the players A, B, C in a three-player game.
Try to clarify how C should play in ordel' to maximize his winuings for fixed choices
of A and B.2
2In the threc--player game it is possible to consider a variant in which the first two players
can form a coalition, that is, can unite against C.

BEST BET FOR SIMPLETONS
131
5. In "Best bet for simpletons" 0 and 1 are equally likely, that is, they occur
with equal probability at each toss of the coin: P(O) = P(l) = . Imagine that the
coin is not "fair", say 0 results from a toss more often than I: P(O) > . Of course,
if P(O) is close to 1 (for example, P(O) = 0.999), then by choosing the 5-letter word
00000 player A wins with probability at least (0.999)5 > . The problem arises
as to the values of P(O) for which player B can continue to win in the game with
l-letter words. Even for l = 3 the answer to this question is unknown.
CONJECTURE. For any value of P(O) there is a winning strategy for B if the
length of the chosen words is sufficiently large.

K ,-ant Sdecta: Combinatorics, I
Serge Tahachnik,(w. Editor


Therl' i
 a tradition in Russia that hold
 thatlllathelllatics can he both challenging and fun.
One tine outgro\\ th of that tradition i
 the Illaga/ine. }.:nllll. which ha
 been enjoyed h}
man) of the he
t
tudelll

ince its founding in 11)70. The al1ides in Knllll assume only a
minimal had\ground. that of a good high '\chool studelll. )et are capabk of entertaining
mathematicians of almlJ
t an) level. Sumetimt:
 the articles n:ljuire cardul thought or a
momcnt\ \\oll with .1 pencil and paper. However. the industrious re.lder "ill he gener-
ousl} rc\\ arded h} the elegance and beaut} of the
uhjects.
Thi
 boo" I
 the third collection 01 altidcs from Kl'tllllto he puhlished hy the AMS. The
\ olume is (k\oted mainl) to comhinatoric
 and di
crete mathematics. Se\ eral of thc topics
are well "nu\\ n: flonrepeating
eljuences. detecting a counterfeit coin. and linear inequal-
itie
 in economic,. but the) arc di'cu
sed here with the cntel1aining and engaging
tyle
t} pical of the magallne. The t\\ 0 pre\'iou
 collections treat aspects of algehra and anal)
is.
induding connection
 to number theory and other topics. They were puhlished as Volumes
I
 and 15 in the rvlathem
lIical World
eries.


The artide
 are \\ riuen
o a
 to pre
ent genuine mathematics in a conceptual. entertaining.
and .lccessible \\ a). The hooh arc designed to be u
ed hy stmknts and teachers who love
mathematic
 and \\ ant to
tud\ it
 various aspect
. deepening and expanding upon the
school cUlTlculum.


ISBN 0-8218-2171-7


MAWRLD/17


AMS on the Web
www.ams.org