2.2 STRATEGIES FOR GETTING STARTED 311 � 1 � 1 ; 1 ;^1 � 1 (�) 1 j 1!^1 ;^1 ;^1 ; 1
(��9 1 �^1!^1 ;^1 ;^1 ; I·
At this point, we can repeat the process, but before doing so, we observe that
already the largest number in the top row is at most as big as the smallest number in
the bottom row. So after we shift the top numbers, we no longer have to sort. We see
that eventually the number 3 in the top will join the number 3 in the bottom:
1 �^1!^1 ;^1 ;^1 ; 1 (�) 1!^1 �^1 ; 1 ; 1 ; 1
(�) 1 � 1!^1 ; 1 � 1 ;^1 (�) 1 � 1 � 1 ;^1 ;^1 ; I·
So, what actually happened? We were able to get the two 3 's to coincide, becau se
the top and bottom rows stopped "mixing," and there was a 3 in the top and a 3 in the
bottom. Will this always happen? Can you come up with a general argument? And
what role was played by the odd parity of 5? A few more experiments, perhaps with 7
people, should help you finish this off.
In the next example, not only do we fail to solve the problem, we explore a conjec
ture that we know to be false! Nevert heless, we make partial progress: we develop an
understanding of how the problem works, even if we do not attain a complete solution.
Example 2.2.5 (Putnam 19 83) Let f(n) = n + L v'nJ. Prove that, for every positive
integer m, the sequence
m,f(m),f(f(m) ),f(f(f(m))), ...
contains the square of an integer.^5
Partial Solution: At first, it seems rather difficult. The function f (n) has a strange
definition and the desired conclusion is also hard to understand. Let's first get oriented:
the problem asks us to show that something involving f(m) and squares is true for all
positive integers m. The only way to proceed is by getting our hands dirty. We need
to understand how the function f(m) works. So we start experimenting and making
tables.
9
125 Recall that lx J is the greatest integer less than or equal to x. For more information, see page 14 6.