MATHEMATICS  PROBLEM  123

Two long (length at least  a + b + c  units) horizontal halls meet at right
angles.  The east-west hall is  a  units wide, and the north-south hall is
b  units wide.  Both have vertical walls and a horizontal ceiling  c  units
high.  What is the length of the longest rigid rod (of negligible diameter)
which can be carried along the east-west hall, around the corner, and along
the north-south hall?



 Each midshipman submitting a correct solution with a correct explanation to
Problem 123 by 1700 on Sunday 31 March 2002 will win a cookie.  Submit
solutions to Prof. Wardlaw at mathprob@usna.edu (please no attachments!) or
via his mailbox in Chauvenet 301.

 Correct solutions to Mathematics Problem 122 were submitted by Midshipmen
Talmage Brown, Chris Buck, Matt Gibson and Dan Willcox (jointly), Benjamin
Heineike, and Alan Kruppa.  Professor Richard Davis also submitted a
solution to Problem 122.  My solution to Problem 122 is posted on the board
and is on the reverse side of this sheet.



MATHEMATICS  PROBLEM  122

The  kth Fibonacci number  f(k)  is defined recursively by

     f(0) = 0,    f(1) = 1,  and     f(k+2) =  f(k)  +  f(k+1)

for  k > 0.   Find the last digit of     f(123456789) .


 Solution.  To solve this problem, we need only look at the last digit,
namely   f(k)  (mod 10), of   f(k) .

                         Table of   f(k)  (mod 10)
                                  for  k = i+j :

          i =           0   1   2   3   4   5   6   7   8   9

          j =   0      0   1   1   2   3   5   8   3   1   4
               10      5   9   4   3   7   0   7   7   4   1
               20      5   6   1   7   8   5   3   8   1   9
               30      0   9   9   8   7   5   2   7   9   6
               40      5   1   6   7   3   0   3   3   6   9
               50      5   4   9   3   2   5   7   2   9   1
               60      0   1   1   2   3   5   8   3   1   4

Since  f(0)  =  f(60) (mod 10)  and  f(1)  =  f(61) (mod 10),  it is clear
from the definition  f(k+2)  =  f(k)  + f(k+1)   that the table of last
digits repeats itself after sixty steps.  That is,  f(k) (mod 10)  is
periodic  with a period  of  60.  Since  123456789 =  2057613 x 60 + 9, the
last digit of  f(123456789)  is   f(123456789) (mod 10)  =  f(9) (mod 10)  =
4.