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) .


 Each midshipman submitting a correct solution with a correct explanation to
Problem 122 by 1700 on Thursday 28 February 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 121 were submitted by Midshipmen
Chris Buck, Joshua Estevan, Geoffrey Goldstein, Shane Kigin, Nathan Putzier,
and Ralph Rogers.  Professor Mark Kidwell also submitted a solution to
Problem 121.  My solution to Problem 121 is posted on the board and is on
the reverse side of this sheet.




MATHEMATICS  PROBLEM  #121

 The Maryland lottery "Big Game" is played by selecting five of the numbers
1, 2, 3, . , 50 and then selecting one of the numbers  1, 2, 3, . , 36.  The
first selection must consist of five different numbers with no repeats, and
the order in which they are picked does not matter.  The second selection
may or may not repeat one of the first five numbers.
 How many ways can this be done?  Put differently, how many plays would you
have to purchase (for one dollar each) in order to be sure that you have the
winning play?  (Be sure to include a careful explanation of your reasoning
and calculations in your solution!)

 Solution.  There are  50x49x48x47x46 = P(50, 5) ways to select five
different numbers in order from the set  {1, 2, 3, . , 50},  since there are
50 possibilities for the first number selected, then   49  for the second,
etc., and finally  46  ways to select the last.  But then this number must
be divided by  120 =  5! = 5x4x3x2x1
= P(5, 5), which is the number of  different ways that a particular set of
five balls can be arranged in order, to get  C(50, 5) = P(50, 5)/P(5, 5) =
(50x49x48x47x46)/( 5x4x3x2x1) = 10x49x2x47x46 = 2,118,760  ways to select an
unordered set of five numbers from the set of fifty numbers.  Multiplying by
the  36  ways of selecting one number from a set of  36  numbers, we see
that there are a total of   N = 2,118,760x36 =  76,275,360  different
selections possible.

 Remark:  The number  C(n, k) = (n!)/((k!)((n-k)!))  is called "the number
of combinations of  size  k  chosen from a set of size  n", or, more simply,
"n choose  k".  The number  P(n, k) = nx(n-1)x.x(n-k+1) =  (n!)/((n-k)!)  is
called "the number of permutations of  n  things taken  k  at a time".  In
general,  P(n, k) = C(n, k)xP(k, k)            = C(n, k)x(k!).