352 Methods of Proof
e
ee
ee
eee
e
a aae
aaa
aaa
b
b
bb
b
bb
b
b
c
c
ccc
c
cc
c
Figure 55(i) at least two residue classes are used;
(ii) at each crossing,a+c≡ 2 b(mod 5), wherebis the residue class assigned to the
overcrossing, andaandcare the residue classes assigned to the other two arcs.
A coloring of the figure eight knot is given in Figure 56, while the trivial knot does
not admit 5-colorings since its simplest diagram does not. This proves that the figure
eight knot is knotted.
43 1 0Figure 5673.The answer is no. The idea of the proof is to associate to the configuration (a) an
encoding defined by a pair of vectors(v, w)∈Z^22 such that the(i, j )square contains a
+if theith coordinate ofvis equal to thejth coordinate ofw, and a−otherwise. A
possible encoding for our configuration isv=w=( 1 , 1 , 0 ). Any other configuration
that can be obtained from it admits such an encoding. Thus we choose as the invariant
thepossibilityof encoding a configuration in such a manner.
It is not hard to see that the configuration in (b) cannot be encoded this way. A slick
proof of this fact is that the configuration in which all signs are negative except for the
one in the center can be obtained from this by the specified move, and this latter one
cannot be encoded. Hence it is impossible to transform the first configuration into the
second.
(Russian Mathematical Olympiad 1983–1984, solution by A. Badev)
74.The answer is no. The essential observation is that
99 ... 99 ≡ 99 ≡ 3 (mod 4).