i-l q -I* /Ye( l-',( c<- f{ tL *Ygc; r¤-

,t-

,(

-t
,s
Tualqug 193t

-_l_
rl
i

I
_-_j_t
--T_-

=r
J

)
,/) l
--.---*<P

=+- I

-+- I

.-i+

l&-
+ I

-1--
I
 Some lhinus ltgtter chaltue
So use invariadlity to your advantage

by Yury lonin and Lev Kurlyandchik

HE PROBLEMS DISCUSSED the numbers on the blackboard re- the parity of the sum of zeros and
in this article are alike in that mains unchanged (because multipli- ones, the parity of the number of
each of them involves (perhaps cation is both commutative and minuses. The solutions to the prob-
with an appropriate reduction) associative). This product was origi- lems and exercises that follow are
some "configurations" of numbers nally -1, so finally it must also be also based on aptly selected invari-
or other symbols and a set of opera- equal to -l-that is, the last number ants.
tions that can be applied to these will be -1, or the last sign will be a Exercise 1. A number of plus and
configurations. We'1l ask such ques- minus. minus signs are written on the
tions as these: Is it possible to find The same reasoning can be re- blackboard. It is permitted to erase
a sequence of operations that turns shaped as follows. Let's replace all any two signs and write a plus in-
one given configuration into an- the pluses by zeros, minuses by stead if they were different and a
other? Under what conditions re- ones, and note that the sum of any minus if they were the same. Prove
stricting the configurations and the two numbers is of the same parity as that the last sign that will be left
sequence of operations can this be the number written down in their doesn't depend on the order of era-
achieved? What configurations can place when they are erased. Since SUIC.
be obtained from a given one? initially the sum of all the numbers Problem 2. Plus and minus signs
We'll see that problems like these was odd (it was equal to 15), the last are arranged in a 4 x 4 table as
are most efficiently solved by find- number left on the blackboard has shown in figure 1. It is permissible
ing unchangeable features in a to be odd-that is, 1; so the sign left to reverse all the signs in one hori-
changing con{iguration as it is sub- on the blackboard is a minus. zontal line, one column, or along
jected to the allowed transforma- Final1y, a third solution can be any line parallel to a diagonal of the
tions. based on the observation that under table (in parLicular, in any corner
Problem l. Ten plus signs and fif- every operation the number of mi- unit square). Does there exist a se-
teen minus signs atewritten on the nuses either doesn't change or de- quence of these operations leading
blackboad. You can erase any two creases by two. Initially the number to a table without minus signs/
signs and write in their place a plus of minuses was odd, so a minus will Replace the pluses and minuses
sign if they were the same and a be left in the end. with +1's and -1's again. Multiply
minus if they weren't. This opera- Now let's examine all three solu- the numbers in the squares shaded
tion is repeated 24 times. What sign tions.
remains on the blackboard! The first one was based on the
Let's replace every plus sign with invariability of the product of the
the number I and every minus sign numbers on the blackboard, the sec- I

= with -1. Then the ailowed opera- ond on the invariability of the par-
!

o tions can be described as erasing any ity of their sum, and the third on the rl:.:l:!l:.r:i.
"."1".".
-oo two numbers and writing down invariability of the parity of the
-

lilal;liill:l:
--j

l their product. So the product of al1 number of minus signs. We can say ri;iril:i!ll;
. I ll.l;
;l;lli;1;i:
o that in each of these solutions we
Ia rl:ii!lfiil:iil: :ilfb:#:i!

f At left: "A mathematician on were able to find an invafiant: the

o vacatiorr." product of ones and negative ones, Figure

OUAlllIlJllll/IIATURI 05
 Our solution implies that in the sub arr ay and increase all the numb ers
case when all three numbers Xo,X' in itby one. Is it always possible to ob-
x2are of the same parity it's impos- tain numbers divisible by 3 in all
sible to erase all figures but one. initial anay!
squarcs of the
However, our solution does not im- The answer is no. Let's find the
ply that this can rcal\y be done if sum of the numbers in the 48
there are both odd and even num- squares shaded in figure 6. Since any
bers among them (and at least two 4 x 4 square contains 12 shaded unit
of the initial numbers are nonzero). squares and any 3 x 3 square con-
Figure 2 tains 9 or 6 such small squares, the
In fact, such a sequence of opera-
in figure 2. This product is an invari- tions can always be found in this allowed operations do not change
ant, because any of our operations case-we leave this fact as a tather the remainder of this sum when di-
either leaves these numbers intact or simple exercise for the reader. vided by 3. Therefore, if this sum is
changes exactly two of them. Origi- Let's change the operations in not divisible by 3 initially, the
nally this product is eclual to -1, so problem 3: we'll require that four shaded squares always contain
it's impossible to get a table without figures are erased at a time-two of numbers not divisible by 3.
minuses, for which this product is +1. one kind and two of another-and Exercise 3. Given the conditions
Exercise 2. Solve problem 2 for that one figure of the third kind is of problem 4, is it possible to obtain
the tables in figures 3, 4, and 5. written down in their place. Sup- aL affay not containing even num-
Problem 3. Written on the black- pose that after a number of such bers from arrarbitrary initial array?
board ate a numbet of zetos, ones, operations only one figure is left. Problem 5. The numbers 1, 2, ...,
andtwos. Instead of any two differ- Can we tell in advance, knowing the n are aftanged in some ordet. We
ent digits we can vwite a digit dif- initial numbers of zeros, ones, and can exchange any two adiacent
ferent from these two (0 and 1 can twos, what figure will remain on the numberc. Prove that an odd num-
ba replaced by 2, and so on). These blackboard? ber of such exchanges produces an
operations are repeated until only The parity argument doesn't work aru angement neces s adly diff er ent
one figure remains on the black- here, because one of thenumbersXsr x1r fuom the initial one.
board. Prove that this figure doesn't x, changes its parity under each opera- Let ar, a2, ...t anbe the numbers 1,
depend on the order in which these tiorl while the parities of the other two 2, ..., fi written in the given order.
operations are performed. are preserved, so numbers with initially Such a string of numbers is called a
Let xo, x,, and x, be the numbers different parities can get the same peruutation of l, 2, ..., fr .The num-
of zeros, ones, and twos/ respec- parities. But if we consider the re- bers a- and a,in this permutation are
tively. Every operation changes each mainders of xo, X'x, modulo 3 rather said to form an invercion if i < I but
of these numbers by one, and so it than modulo 2 (looking at parities is, a. > a-that is, the greatet of these
changes the parities of all three after all, equivalent to reducing the two numbers precedes the smaller.
numbers. When there's only one fig- numbers modulo 2), we notice that our Exchanging any two adjacent num-
ure left, two of the numbers Xo, X,, operations leave them equal if they were bers, we reverse their order, but the
ar-.d xrbecome equal to 0, and the equal and different whenever they were order of any other pair of numbers is,
third is 1. Therefore, initially two of different initially. (h other words, the re- of course, preserved. So the number
these numbers were of one parity mainders of x, - xo, xr- Xrt xtd xo- x, of inversions increases or decreases
and the third was of the other parity. modulo 3 are invariant.) The rest of the by one. A{ter an odd number of pair
So regardless of the order of the op- reasoning follows that of dre solution to exchanges we change the parity of
erations, the only number among x, problem 3. the number of inversions and, there-
xy artdxrthat can be equal to 1 in Problem 4. In each square of an fore, the permutation as well.
the end is the one that initially dif- B x B aruay an integer is vwitten. We Exercise 4. Prove that the state-
fered in parity from the other two. can choose an arbitrary 3 x 3 or 4 x 4 ment of problem 5 remains valid

.Il' -rI iTi i, r l,'l

,*'
r
i!fi, : i i+ +,'i :

,,t ,*, .Lt. ,+ .t:

. I.. i+ + .#;,!
I ".1. !i
r*r,
.,r +, ..I t

**,
+ .:*l .""i"
.1f": .:r:i
" .t I
. .t-'
! T:, r;L,:
,*, tffi
''.t..
:T:. ,-t -r -r

.+ ,* +, TJ. + + itl: ii:& ,*, ;{r;a :T-., + ,.L.

_ 1, * .t,.
-tl
"-t. .:r
I 3..' ;i{* ,*, i:iHi ;ff:i ,f, * + .+ ,i* i:5r!::
!:i!:r;r:1;

-'rLr ""1.
. t.
! l;*li .r,:::.1 -L trr: ,::t'
:t{-t I:ltlli

Figure 3 Figure 4 Figure 5 Figure 6

3$ srPrrirBtR/0cI0BtR 1 ss3
even if we're allowed to swap any If the yellow car passes another one, neighboring sectors but they must
two numbers in the given permuta- the permut ation a, a2r . . .r a24 turns move in opposite directions. Is it
tion. (Hint: show that any two num- into a24t ar1 a2t ...r aru. This can also possible to bring all the chips to-
bers can be exchanged by means of be achieved by a series of 23 trans- gether in one sector?
an odd number of "adjacent ex- positions (how?). 11. (a) A minus sign is placed at
changes.") Thus, any pass amounts to an the vertex A' of a regular 12-gon
Another term for a pair exchange odd number of transpositions-that ArAz...AD, and plus signs are placed
is transposirlon. Using this term, we is, changes the parity of the indi- at all other vertices. One is allowed
can formulate the statement of ex- cated permutation. But the final per- to reverse signs at any three vertices
ercise 4 as follows: an odd number mutation coincides with the initial forming an isosceles but not a right
of transpositions changes a permu- one/ so/ by exercise 4, the total num- triangle. Can we get a minus sign at
tation. The solution to problem 5, ber of transpositions must be even A, and plus signs at all other verti-
hint
along with the fact stated in the (in other words, the overall permu- ces after a number of such opera-
to exercise 4, shows that every tation must be even). Therefore, the tions?
transposition changes the parity of number of passes had to be even as (b) Will the answer to part (a) re-
the number of inversions. A permu- we1l. main true if we're allowed to change
tation is called even or odd if the With this introduction, you're on signs at the vertices of any isosceles
number of inversions in this permu- your own. We're confident you can triangie?
tation is even or odd, respectively. handle the exercises that follow. J2. A plus or minus sign is writ-
So we can now say that performing Exercises ten in every scluare of a 4 x 4 aruay.
a transposition changes the parity of 5. Four ones and five zeros are We can change all the signs in any
the permutation whose elements written around a circle in an arbi- line or any column. The smailest
are transposed. trary order. A one is inscribed be- number of minus signs that can be
Problem 6. Twenty-five cars tween every two equal numbers and arrived at via these operations start-
started from different points along a zero between different numbers; ing with a given aruay is called the
a closed speedway in the same di- then the initial numbers are erased. character of this aray.What values
rection and at the same time. Ac- Is it possible to obtain a set of nine can the character take?
cording to the rules of the race, the zeros atter a series of these opera- 13. Thirty chips-ten white and
cars can pass one anothet, but tions? twenty black-are placed around a
double passing is forbidden. The 5. Wendy tore up a sheet of paper circle. Any two chips with three
cars finished simultaneously, all at into 10 pieces, then tore some of chips between them carr be
their r espective starting posit ions. these into 10 pieces, and so on. swapped. Two arrangements of
Ptove that there was an even num- Could she obtain 1993 pieces in this chips are ecluivalent if one of them
ber of passes during the race. way? can be obtained from the other after
Imagine that one of the cars is 7. The numbers I, 2, ..., 1993 are a number of such transpositions.
painted yellow and number the re- written on the blackboard. Two What is the greatest possible num-
maining cars in their order at the start numbers are erased and replaced by ber of nonequivalent arrangements?
(car number one starts immediately the remainder of their sum when 14. The numbers l, 2, ..., 1993 arc
behind theyellow car, the second one divided by 13. This operation is re- written in increasing order. Any
behind the firsq and so on). Imagine peated until one number is left. four numbers can be rearranged in
there is a scoreboard indicating the What is this number? reverse order in the same places. Is
order of the cars as they follow the 8. Every number from I to it possible to obtain the reverse order
yellow car. Then every time a num- 1,000,000 is replaced by the sum of 1993,1992, ...,2, L of the entire set of
bered car overtakes another num- its digits. The resulting numbers are numbers? O
bered cart two numbers on the repeatedly subjected to the same op-
scoreboard exchange places. eration until all the numbers have ANSWERS, HINTS & SOLUTIONS
Let's see what happens when a one digit. Will the number of ones in ON PAGE 60
numbered car passes the yellow one. the end be greater or less than the
If the order of the numbers before number of twos?
the pass was art a2t ...t arn, then a{- 9. The sum of digits of a three-
ter the pass the scoreboard will read digit number is subtracted from the
art a3t ...t aro, ar.. But we can obtain number. The same is done to this
the same permutation as a result of difference, and so on. What number
23 transpositions: is obtained after a hundred repeti-
tions?
Al, AZ,A3r ...r AZ4-+ Ay Ay A3t ...r 10. A circle is divided into 10 sec-
az+) a2, a3, ay...r a24)... -) a2t tors and one chip is placed in each.
A3t ...t AI, AZ4) A2t Ay ..., A241 A1. We can move any two chips to the

OUANIUflll/IIATIJBt 37
tions-they're built not on sand but medicine-no one made sacrificial clothing.
on bedrock. offerings to him in honor of military 32. The word "sharovars" is of
15. Ikhnaton also had an under- deeds. Turkic origin and appeared only in
ground tomb, not a pyramid. 14. The Tarpeian Rock is in the Middle Ages.
15. The ancient Egyptians knew Rome.
nothing about silk or cotton-they 15. "Bazaat" is a word of Turkic
used only linen. origin-it was unknown in Greece.
17. Ishtar wasn't an Egyptian god- 16. Pythagoras died of old age on
$omelhinus
dess-she was Babylonian. the eve of the Greco-Persian wars. 1. Replacing every plus sign in
18. The protector-goddesses of 17. Socrates lived one century this exercis e by a minus sign, and
both lands-Upper and Lower later than Pythagoras. every minus sign by a plus sign, we
Egypt-were Nekhbet (depicted as a 18. Paracelsus was a medieval turn it into a simple generalization
l.ulture) and Buto (depicted as a co- physician ( 16th century). of problem I discussed in the article.
bra). Maat was the Egyptian goddess 19. Euclid lived two centuries 2. Write 1 instead of " +" and -1
+
of truth. later than Pythagoras. instead of "-." If we choose any 4 x 4
Commentary on Greecefs frac- 20. Greek geometers did not com- subsquare of our diagram and create
tured history: pile problem books. within it the pattern of shaded
1. At Thermopylae the Athenians 21. Plato and Aristotle lived one squares illustrated in figure 2, the
and other Greeks were defeated by and a half centuries later than product of the eight numbers thus
the Persians. Pythagoras; Diophantos lived even chosen will be invariant under the
2. During the second Greco-Per- later. operations allowed (you can check
sian war the king of Persia was 22. The Greeks sacrificed not this yourself). With this observation,
Xerxes. horses but oxen and sheep. we can apply the method of problem
3. The "immortal" guard was 23.Hecate was the goddess of the 3 in the text: the product of the
unmounted-they weren't horse- Moon and of witchcraft. A sacri{ice shaded numbers must be positive
men. in thanksgiving for a scientific dis- for any position of the 4 x 4 sub-
4. "Woman's chiton" is a sense- covery would have been offered to square or we will not be able to
less turn of phrase-the chiton is Athena, the goddess of wisdom. achieve atable consisting entirely of
Greek clothing for males only. 24.Plato spent all his life in Ath- +1's. For the distributions of the
5. Archery was not included ens and was never in Rome. signs given in {igures 3 and 5 (p.3511,
among the Olympic games-the 25. Macedonia is situated to the this product equals -1 if the "tem-
Greeks considered this kind of sport north, not to the south, of Greece. plate" of shaded squares is placed in the
"barbaric." 26. Alexander reached India, but top left position on the given 6 x 5
5. According to legend, Pythag- he probably only heard about China. seuare; for figure 4 it's -1 for the bot-
oras was an Olympic boxing cham- The Persians apparently called this tom right position. This means that
pion. country something else-"Sin" or the answer to all three questions is no.
7. "Percian horde" is a senseless "Ser." 3. Shade the first, second, fourth,
turn of phrase-the word "horde" is 27. Alexander of Macedonia did fifth, seventh, and eighth rows of the
of Turkic origin and didn't appear in not have the title "King of Greece," table considered in the problem. We
Europe until the time of the Huns. despite his control over this coun- can see that the parity of the sum of
8. Iron crowns appeared in Persia try. the numbers in the shaded squares
during the reign of the Sasanian 28. Cane sugar wasn't white in is not changed by the permitted op-
dynasty (3rd century e.n.)-Xerxes Alexander's time, but yellow or erations. For a table without even
was of the Achaemenian dynasty even brown-no one knew how to numbers, this sum is even (a8 odd
and wore a golden crown. purify it. numbers) initially. If this sum is ini-
9. The forum was in Rome-in 29. Palm-leaf manuscripts were tially odd, then we can never get all
Athens there was an agora. common in both China and India. the numbers to be even with the
10. Pericles lived considerably 30. The "Indiatt" proof of the given operations.
later than the Greco-Persian wars. Pythagorean theorem (dividing a 4.lf(i, l) denotes the exchange of
1 1. Euripides lived later than larger square into smaller squares the numbers standing in the rth and
Pericles and considerably later than and right triangles) became known Ith places in a permutation, then the
Pythagoras. in Greece much later than Pythag- exchange of two nonadjacent num-
12. During the Greco-Persian oras discovered his proof. bers-say, in the first and kth
wars/ there were no bodyguards in 31. The turn of phrase "Pythag- places-can be organized as a series of
Greece-they appeared during the orean trousers" emerged only in (2k - 3l neiglrbor exchange s: (1, 21, (2, 31,
military democracy (at the time of modern times. It could not have ..., (k- t, kl, (k - 2, k - tl, lk - 3, k -21,
Homer and earlier). been used in ancient Greece-the ..., (1,2). A worked example will
13. Asclepius was the god of Greeks despised such "barbaric" make this solution clear.

00 stPTt]vlBtB/0cT0BtR 1 gg3
 5. Let's use -1's instead of zeros. the chip's number inueases by one the squares or has exactly one com-
If x,, ..., xe are the current nurnbers modulo 10. Similarly, a clockwise mon vertex with each square. So the
in their order around the circle, then rtove decreases the chip's number products of the numbers at the ver-
the operation we consider simply by one modulo 10. So, when two tices of each square change their
replaces them with the products chips are moved in opposite direc- signs under any allowed operations
XrXr., X.rX.,, "', XrXgr xrx, (if X, : Xzr tions, the sum S of the numberc of simultaneously. But in passing from
thenx,xr: 1; other^wisexrx, = -l). So all chips modulo 10lthat is, the re- one of the given arrangements to
the product o{ the numbers after the mainder of the sum of a1l the num- another, only two of the three prod-
operation is (x,r, . . .xn 1r : 1 no matter bers when divided by 10) is preserved. ucts should be changed, so this tran-
what x,, .../ xe werc. But the product In the case when all chips are in one sition is impossible.
of nine -1's is -1, and so it cannot sectorn/ S : 0, since 10n = 0 (mod i0); (b) Changing the signs at the ver-
appear aftel our operation. if there is one chip in each sector, S = tices of three isosceles right tri-
6. Every tlme \Vend)- tears/ the 0 + 1 + 2 + ... +9 : 45=5 (mod 10). So angles A ry4 rA u, A A 4 r, and A a4, rrA u
number oi pieces increases by 9, so we can/t gather all the chips in one results in changing only the sign at
its remainder modulo 9 is invariant. SCCtOI. A' and yields plus signs every-
But 1 * i993 rn-rod 9', She can never We can say a bit more about the where. After that, we similarly
get 1993 pieces. situation given in this problem. Sup- change the sign atAronly, thus cre-
7. The ans\\.er is 10 ,the remain- pose the chips are distributed hap- ating the required arrangement.
derof 1 +2+... - 1991r'-hendivided hazardly among the ten sectors (and 12. The character can take any
by 13). not one to each sector). Then we can value from O to 4. Changing signs
B. There wili be more ones than always gather any 9 chips of the 10 along columns that have a minus
twos. The operation rn qu(.tlon pre- in, say, the zero sector. One chip sign in the top place, we get plus
serves the rernainde rs modulo 9, so keeps traveling clockwise, enabling signs in the top row. Then we
after a certain numbe r ..i steps each each of the others to move counter- change signs in the rows that have
number turns inro its remainder clockwise, step by step, until the more than two minus signs. Now
modulo 9. Since I rl00 000 : 9 .
other chips each reach the targetted minus signs occur only in the three
111,111 + 1, it folltrrs that 111,112 sector. Then the tenth chip ends up bottom rows/ no more than two
of these remainders :rre ones and in sector S, where S is the value of minus signs in each. If the total
111,111are nr-os. our invariant for the initial arrange- number of minus signs is 5 or 6, two
9. Let x, be the grr-en number and ment. It follows that all arrange- of these rows have exactly two mi-
X, Xjr ..., xr0i. the successtt-e numbers ments fall into 10 classes corre- nus signs and we can change signs in
obtained Lry repsnlc,l subtractions of sponding to the 10 values of S such both, one, or none of them to get a
their sums oi digits. Then all these that two affangements can be trans- column having three minus signs
numbers (except -r ' and all their re- formed into each other if and only if without changing the total number
spective sums of digits are divisible they are in the same class (have the of minus signs. Finally, we change
by9. Ifr >0thtnr >9,x.,>9- same value of S). signs in this column, decreasing the
9, X,rr)9 . 3 and -\,,, 9 . 80 = 720. 11. (a) Replace the signs "+" arrd total number of minus signs by two,
Since there are on11' three 3-digit "-" withthe numbers +1 and-1, re- arriving at no more than 4 minus
numbers g.eater than 720 whose surn spectively. Consider three squares signs. And this number, in general,
of digits is equal to 9 1801, 810, and ArAAAro, AA\A", and Ay'.aay',r, can't be diminished. Among other
9001, at least I (r oi the 19 nurnbers x,,,, (fig. 13). Any isosceles triangle in- possibiJities, the reader may examine
Xy, . . .r r. have a surr] of digits not less scribed in the given 12-gon is either the situation starting with four minus
then I 8. But that u-ould rnean that xl a right triangle inscribed in one of signs along a diagonal of the array and
>xr2xrr+ 16 18 +3.9) 720 +315 > plus signs everywhere else.
1,000, which is not a 3-diglt nurnber. 13. Number the places occupied
Therefore, X,oo = 0. by the chips around the circle from
10. Label the sectors counter- 1 to 30. Any allowed transposition
clockwise by the numbers 0, l, ..., swaps the chips in places with num-
9 and define the number of a chip bers of the same parity. Consider the
(for some given arrangement of the t5 "odd" places. |oin place 1 to 5, 5
chips) as the number of the sector to 9, ...,25 to 29,29 to 3, ...,27 to
where it belongs. When a chip i-that is, those pairs of places
makes a counterclockwise move where "transposable" pairs o{ chips
(from sector I to sector i + 1 ), its are positioned. We get a closed 15-
number increases by one except for sided (self-intersecting) polygonal
the move from sector 9 to sector 0, curve. And two chips adjacent along
which decreases the number by 9. this curve can be swapped. So any
But in either case we can say that Figure 13 two chips in odd places can be

OUANIUlll/AIlISlllIRS, IIIlllTS & SOI.UIIOllJS 8I

 swapped (see the solution to exer- number of times, so the number of
cise 4). It follows that any permuta- moves was even. But evenly many
tion of these chips is feasible. Like- pair exchanges make an even per-
wise, any permutation of the chips
in even places is feasible as well.
mutation.
Conversely, the operation de-
Beadel's
This means that two arangements scribed in {igure 5b in the article,
of chips are equivalent if and only if
they have the same number o{ white
and its modifications, allow us to
create any desirable arrangement of
l,llrile...
chips in the odd places (and there- all chips, with the possible excep-
fore in the even ones/ too). This tion of the two located at the oppo- The article "superheated by
numbercantake 11values (0, l,..., site vertices of the central hexagon Equations" in the last issue
10), so 11 is the number in question. of the network in figure 4 (they cor- of Quantum was read with
14. The operations in the problem respond to chips a and b in figure pleasure by Dr. Richard
consist of two transpositions each (a 5b). These last two chips may or Grant of the Albert Einstein
transposition of the two extreme may not end up being swapped in Medical Center in Philadel-
numbers of a quadruple and a trans- the end. Suppose they are. This phia. In tact, itreminded him
position of the two inner numbers). would mean that we have gotten an of a natural phenomenon. He
So they can generate only even per- even permutation (the empty space writes: "The teaser below the
mutations. But the permutation we came back to its starting position!), cover art on the contents
need to create is odd, because it con- which differs from the required (also page suggests that Dmitry
sists of an odd number (9971of trans- even) permutation in exactly one Fomin's technique of heat ex-
positions: ll, 1993), (2, 19921, ..., pair exchange-that of the last two change may be impractical.
(997, 99Bl.In general, the answer chips. But this is impossible, be- As a matter of fact it is used
will be no for any number of the cause a pair exchange alters the par- all the time in nature by hav-
lorm 4k + 2 (as well as 4k + 3) in- ity of a permutation. ing veins and arteries en-
stead oI 1994. twined in 'retia mirabiles.'
For numbers of the forrn4k or 4k These allow heat exchange
+ 1, the inverse order is an even per- Col'l'eclions exactly as described by
mutation/ and the consideration of Fomin (though of course not
parities is not sufficient to answer Vol. 3, No.6l 100% efficient)." He adds
the question. In fact, it's not difficult p. 6, co1. 1, 1. 11: for I - llt that the mechanism works
to show that here the answer is yes. read I lle. for diffusible substances (for
A more involved analysis proves p. 7, col. l, I.22: for i = n read example, oxygen or urea) in
that our operations generate any i=k. addition to heat.
even permutation. p. 7, co1. 2,1I. l-1: the form of Dr. Grant offers a citation
the equation that "telescopes" is for further reading on the
subject: "The Wonderful
S*-S^ t:312-tl.,i. Net" by P. F. Scholander in
Toy $tore r.
the April 1957 issue of Scien-
1. The number of arrangements p. 56, table in M86: for D. read tific American.
for a given (nr, ..., n,r) is equal to D);;for D.,read Dj.
24!l@rlnr!...nrrl). This also ac-
counts for the various locations of
empty space. The number of pos-
sibie sets (nr, ..., n,r)is 34!lftIlz}\. lndex olAduerlisel's
Z.Let's put a chip numbered 0 on
the empty space. Then every move Burleigh Instruments Inc. 25
becomes an exchange of the zero
chip with some other chip. Notice Cross Educational Software 9
that during such an exchange the
Duracell/NSTA Scholarship Competition 26
orientation of the grid's triangle
where the zero chip is located turns Independent Educational Services 4I
to the opposite direction (if it was
pointed north, it will point south, NCTM 50
and vice versa). Since the zero chip
Northwestem University 18
ends up at its starting location, the
orientations of the triangles that it Sharp Electronics 31, Cover4
passed must have changed an even

82 srPTrlt4Btn/0tr0BrR lsss