CS 2104 Problem Solving in Computer Science                               OOC 3
-------------------------------------------------------------------------------

1.  [20 points] A number of bacteria were placed in a Petri dish at 10:00 am.  
    One second later, each bacterium reproduces by dividing into two bacteria, 
    each as large as the original bacterium was to begin with.  At 10:01 am (on 
    the same morning), the Petri dish becomes full.  At what time was the Petri 
    dish half-full?  Why?

    At the end of each second, each bacterium divides into two; so the number
    (and volume) of bacteria in the Petri dish doubles at the end of each
    second.  Therefore, the dish must have been half full at 10:00:59, since it 
    was full at 10:01:00.


2.  [20 points] A total of 101 spur gears are placed in a closed chain, so that 
    each gear meshes with exactly two others; is it possible for all the gears 
    to rotate simultaneously?  Why or why not?

    Arbitrarily pick one gear and call it A1, then number the remaining gears
    in succession, up to A101 (which is meshed with A1).  Note that if A1 
    rotates clockwise, then A2 must rotate counter-clockwise, and if A1 rotates
    counter-clockwise then A2 must rotate clockwise.  (Hence, this is a parity
    problem.)
    
    Now, the rotational direction alternates as we proceed along the chain of
    gears, so that odd-numbered gears all rotate one way and even-numbered 
    gears all rotate in the opposite way.  Hence, gear A101 must rotate in the
    same direction as gear A1, and therefore they cannot mesh and rotate at the
    same time.


3.  [20 points] Fifteen boys gathered a total of 100 nuts.  Is it possible that 
    no two boys gathered the same number of nuts?  Why or why not?
    
    Assuming each boy gathered a different number of nuts than the other boyes,
    the smallest total number of gathered nuts would occur if the fifteen boys
    gathered 0, 1, 2, 3, 4, ..., 13, 14 nuts, respectively.  But the sum of 
    those integers is 105, so they could not all have gathered a different
    number of nuts.
    

4.  [20 points] Prove there must be an integer, whose base-10 representation 
    consists entirely of 1's, that is divisible by 23.  Note:  writing a program 
    to search for such an integer will not be considered to be a valid analysis.
    
    When you divide an integer N by 23, you will obtain a remainder that lies
    between 0 and 22, inclusive.  So, there are 23 possible remainders.
    
    Now, consider the following base-10 integers:
    
       1                               1 digit:  A1
       11                              2 digits: A2
       111                             3 digits: A3
       1111                            4 digits: A4
       11111                           5 digits: A5
       ...
       1111111111111111111111         22 digits: A22
       11111111111111111111111        23 digits: A23
       111111111111111111111111       24 digits: A24
       
    Since there are 24 numbers in the list, there must be two that leave the same
    remainder when divided by 23; we don't care what their values are, but let's
    say they are Am and An, where n > m.

    Then their difference has n digits, the last m of which are zeros (think about
    how the subtraction must work out.  Call this difference X, then X looks like:
    
        1111...11111000...0000 = Ak * 10^m, where k = n - m.
        
    And, X is divisible by 23 since X = An - Am, and both those integers yield 
    the same remainder when divided by 23.
    
    But, 10 = 2 * 5, neither of which divide 23 (since it's prime).  And the only
    divisors of 10^m are powers of 2 and powers and 5 and products of powers of 2
    with powers of 5, and 23 can't divide into any of those either.
    
    So, 23 must divide into Ak (whatever k is).
    

5.  [20 points] The two-player game of Divido begins with three piles of small 
    stones, one with 10 stones, one with 15 stones, and one with 20 stones.  On 
    each turn, the current player must choose a pile of stones and divide it into 
    two smaller piles.  Aside from the rule that a pile may not be empty, there 
    are no restrictions on how many stones may be in each of the piles a player 
    creates.  The loser is the player who cannot carry out a valid move.
	
	 What strategy, if any, can the player who goes first use to guarantee that he 
    wins?  What strategy, if any, can the player who goes second use to guarantee 
    that she wins?
   
    The winner is the player who divides the last multi-stone pile into two piles
    that each hold one stone, leaving only one-stone piles and thus leaving the
    other player no valid move.
   
    But, any valid move will increase the total number of piles of stones by 1.
   
    Since there are 3 piles to begin with, holding a total of 45 stones, there
    will be 45 piles after exactly 42 moves, NO MATTER WHAT THE MOVES ARE.
   
    So, the second player always wins, no matter what strategy she employs, and
    the first player cannot win, no matter what strategy he employs.