448 Algebra
as
(
n− 1
k
)
=
k+ 1
n− 1(
n− 1
k+ 1)
+
n−k
n− 1(
n− 1
k− 1)
.
To be more explicit, this identity implies that forc=n−1, the sequencexk=
(n− 1
k− 1)
satisfies the recurrence relation from the statement, andxn+ 1 =0.
Let us assume thatn−1 is not the largest value thatccan take. For a larger value,
consider an eigenvectorvofA. Then(A+In)v=(c+ 1 )v, and(A+In)nv=(c+ 1 )nv.
The matrix(A+In)nhas positive entries, and so by the Perron–Frobenius Theorem has a
unique eigenvector with positive coordinates. We already found one such vector, that for
whichxk=
(n− 1
k− 1)
. Its eigenvalue has the largest absolute value among all eigenvalues of
(A+In)n, which means thatnn>(c+ 1 )n. This impliesn>c+1, contradicting our
assumption. Son−1 is the largest valueccan take, and the sequence we found is the
answer to the problem.
(57th W.L. Putnam Mathematical Competition, 1997, solution by G. Kuperberg and
published in K. Kedlaya, B. Poonen, R. Vakil,The William Lowell Putnam Mathematical
Competition1985–2000, MAA, 2002)
267.Let us first show that if the two numbers are equal, then the product can be found
in six steps. Forx =−1, we compute (1)x→^1 x, (2)x→x+1, (3)x+ 1 →x+^11 ,
(4)^1 x,x+^11 →^1 x−x+^11 =x (^21) +x, (5)x (^21) +x →x^2 +x, (6)x^2 +x, x→x^2 .Ifx=−1,
replace step (2) byx→x−1 and make the subsequent modifications thereon.
If the two numbers are distinct, sayxandy, perform the following sequence of
operations, where above each arrow we count the steps:
x, y
1
−→x+y
7
−→(x+y)^2 ,
x, y
8
−→x−y
14
−→(x−y)^2 ,
(x+y)^2 ,(x−y)^2
15
−→ 4 xy
16
−→
1
4 xy,
1
4 xy,
1
4 xy17
−→1
4 xy+
1
4 xy=
2
xy,
2
4 xy,
2
4 xy18
−→2
4 xy+
2
4 xy=
4
4 xy=
1
xy19
−→xy.So we are able to compute the product in just 19 steps.
(Kvant(Quantum))
268.Building on the previous problem, we see that it suffices to produce an operation◦,
from which the subtraction and reciprocal are derivable. A good choice isx−^1 y. Indeed,
1
x=
1
x− 0 , and alsox−y=1
( 1 /(x−y)− 0 ). Success!
(D.J. Newman,A Problem Seminar, Springer-Verlag)