The Art and Craft of Problem Solving

60 CHAPTER 2 STRATEGIES FOR INVESTIGATING PROBLEMS

Prove that if T is a triangular number, then 8T + 1 is a

perfect square. You can do this with algebra, of course,

but try drawing a picture, instead.

2.4.14 Once again, you can easily use induction to

prove the very cool fact that the sum of the first n per­

fect cubes is equal to the square of the nth triangular

number, but can you do it with a picture, instead?

2.4.15 Prove that all positive integers except the pow­

ers of two can be written as the sum of at least two

consecutive positive integers. Once again, algebra can

be used, but so can pictures!

2.4.16 Complete the solution of the Planets problem,

started in Example 2.4.5 on page 57.

2.4.17 (Putnam 1984) Find the minimum value of

(u- v)2+ (J2-u^2 - �r

for 0 < u < v'2 and v > o.

2.4.18 A bug sits on one comer of a unit cube, and

wishes to crawl to the diagonally opposite comer. If

the bug could crawl through the cube, the distance

would of course be 0. But the bug has to stay on the

surface of the cube. What is the length of the shortest

path?

2.4.19 Let a and h be integers greater than one which

have no common divisors. Prove that

and find the value of this common sum.

2.4.20 Let ao be any real number greater than 0 and

less than (^1). Then define the sequence a I , a 2 , a 3 , ... by
a,,+ I = vr=a;;-for n = 0, 1,2, .... Show that

. 0 -1
11-+00 Iima,,= ---,
2

no matter what value is chosen for ao.

2.4.21 For positive integers n, define S" to be the min­

imum value of the sum

�I V(2k -I)^2 +af,

as the al,a 2 , ... ,all range through all positive values

such that

Find SIO.

2.4.22 (Taiwan 1995) Let a,h,c,d be integers such

that ad -bc = k > 0 and

GCD(a,h) = GCD(e,d) = 1.

Prove that there are exactly k ordered pairs of real

numbers (XI,X 2 ) such that 0 :S XI,X 2 < I and both

aXI + hX 2 and eXI + dX 2 are integers.

2.4.23 How many distinct terms are there when

(I +x7 +x

I (^3) )\OO
is multiplied out and simplified?
2.4.24 Several marbles are placed on a circular track
of circumference one meter. The width of the track and
the radii of the marbles are negligible. Each marble is
randomly given an orientation, clockwise or counter­
clockwise. At time zero, each marble begins to travel
with speed one meter per minute, where the direction
of travel depends on the orientation. Whenever two
marbles collide, they bounce back with no change in
speed, obeying the laws of inelastic collision.
What can you say about the possible locations of
the marbles after one minute, with respect to their orig­
inal positions? There are three factors to consider: the
number of marbles, their initial locations, and their ini­
tial orientations.