NSolution

11

2 1, 2, 1

3 1, 2, 1, 3, 1, 2, 1

4 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1

5 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1,

2, 1, 3, 1, 2, 1

transformation 503

ber of moves required to solve the N-disc version of the

puzzle, then it follows from the above procedure that:

T(N+ 1) = T(N) + 1 + T(N)

= 2T(N) + 1

with T(1) = 1 and T(2) = 3. This

RECURRENCE RELA

-

TION

has solution:

T(N) = 2N– 1

This shows that the 64-disc version of the puzzle

requires 264 – 1 = 18,446,744,073,709,551,615 moves.

According to the legend, the end of the world will thus

come in approximately 5.05 ×1016 years.

If one wishes to transfer Ndiscs to a specific pole,

then one begins solving the puzzle by moving the small-

est disc to the desired pole if Nis odd but to the third

pole if Nis even.

If we number the Ndiscs 1, 2,…, Nfrom smallest

to largest, then the following table shows the order in

which discs are moved to solve the first five small ver-

sions of the puzzle:

Each line of the table is generated by repeating two ver-

sions of the previous solution and inserting the number

Nin the center. Surprisingly, the rth number in any

sequence representing a solution to the puzzle equals 1

more than the exponent of the largest power of 2 that

divides the number r. For example, the largest power of

2 that divides 12 is 22, and 2 + 1 = 3 is the 12th number

in any sequence representing a solution to the puzzle.

Since 16 = 24is the largest power of 2 that divides the

number 10,000, this observation also shows that Brah-

man priests will move disc 4 + 1 = 5 on day 10,000.

tractrix (equitangential curve, tractory) If one drags

the front end of a bicycle along a straight path, then

the path traced out by the back wheel (assuming the

wheels of the bicycle were initially offset) forms a curve

called the tractrix. This curve has the property that the

endpoint of each line segment of fixed length (the

length of the bicycle)

TANGENT

to the curve meets the

straight-line path.

The curve was first studied by Dutch physicist

Christiaan Huygens (1629–95), who described the path

in terms of an object being dragged by a fixed length of

string. He coined the name “tractrix” for the path,

deriving it from the Latin word trahere meaning “to

drag.” The curve is also sometimes called the “hund-

kurve” (German for “hound curve”), inspired by the

image of a reluctant dog being dragged on a leash by

an insistent owner.

trajectory The path of a moving object or particle is

called its trajectory. The trajectory of a particle is often

described via

PARAMETRIC EQUATIONS

. For example,

the equations x(t) = cos(t) and y(t) = sin(t) give, at each

time t, the x- and y-coordinates of a particle whose tra-

jectory is a

UNIT CIRCLE

. The trajectory of a ball

thrown in the air is an inverted

PARABOLA

, assuming

the effects of air resistance can be ignored.

The term trajectory is also used in the theory of

DYNAMICAL SYSTEMS

as an alternative name for the

ORBIT

of a point.

transcendental number See

ALGEBRAIC NUMBER

.

transformation Any

FUNCTION

or mapping that

changes one quantity into another is called a transfor-

mation. Although the term is essentially synonymous

with the term function, it is usually used only in the

context of geometry, where one speaks of a

GEOMET

-

RIC TRANSFORMATION

and a

TRANSFORMATION OF

COORDINATES

.

Matrix notation is often used to describe geometric

transformations of the plane. A point in the plane is

represented by a column

VECTOR

and a geometric

transformation as a 2 ×2 matrix A. The effect of the geo-

metric transformation is given by matrix multiplication.

For example, application of the following 2 ×2 matrices