22 1 Methods of Proof
67.An ordered triple of numbers is given. It is permitted to perform the following
operation on the triple: to change two of them, sayaandb,to(a+b)/√
2 and
(a−b)/√
- Is it possible to obtain the triple( 1 ,
√
2 , 1 +
√
2 )from the triple
( 2 ,√
2 , 1 /
√
2 )using this operation?
68.There are 2000 white balls in a box. There are also unlimited supplies of white,
green, and red balls, initially outside the box. During each turn, we can replace two
balls in the box with one or two balls as follows: two whites with a green, two reds
with a green, two greens with a white and red, a white and a green with a red, or a
green and red with a white.
(a) After finitely many of the above operations there are three balls left in the box.
Prove that at least one of them is green.
(b) Is it possible that after finitely many operations only one ball is left in the box?
69.There is a heap of 1001 stones on a table. You are allowed to perform the following
operation: you choose one of the heaps containing more than one stone, throw away
a stone from the heap, then divide it into two smaller (not necessarily equal) heaps.
Is it possible to reach a situation in which all the heaps on the table contain exactly
3 stones by performing the operation finitely many times?
70.Starting with an ordered quadruple of positive integers, a generalized Euclidean
algorithm is applied successively as follows: if the numbers arex, y, u, vand
x>y, then the quadruple is replaced byx−y, y, u+v, v. Otherwise, it is
replaced byx, y−x, u, v+u. The algorithm stops when the numbers in the first
pair become equal (in which case they are equal to the greatest common divisor ofx
andy). Assume that we start withm, n, m, n. Prove that when the algorithm ends,
the arithmetic mean of the numbers in the second pair equals the least common
multiple ofmandn.
71.On an arbitrarily large chessboard consider a generalized knight that can jumpp
squares in one direction andqin the other,p, q >0. Show that such a knight can
return to its initial position only after anevennumber of jumps.
72.Prove that the figure eight knot described in Figure 10 is knotted.Figure 10