===========================================================================
CSC 236                    Homework Assignment 1                Winter 2008
===========================================================================

Due: by 10am on Thu 31 Jan
Worth: 8%

For each question, please write your answer formally following the detailed
format given in lecture (in particular, define P(n) carefully in your
inductive proofs).  Keep in mind that approximately half of the marks for
each question will be given purely for having the correct proof structure,
written up clearly and precisely, irrespective of the correctness of the
proof.  Also, make sure that you use notation and terminology correctly,
and that you explain and justify what you are doing -- marks *will* be
deducted for incorrect or ambiguous use of notation and terminology, and
for making incorrect, unjustified, ambiguous, or vague claims in your
solutions.


1.  For each statement below, give *two* different inductive proof
    structures that could be used to prove the statement.  Fill in as much
    of each proof structure as you possibly can without knowing more about
    P(n).

    (a) For all odd integers n >= 3, P(n).

    (b) For all n that are positive multiples of 3, P(n).

    (c) For all n that are powers of 2 (i.e., n = 2^k for some k (- N),
        P(n).

    For example, the statement "\-/  n >= 12, P(n)" can be proved using any
    of the proof structures below (for this example, I'm giving more than
    two possibilities, but in your answers, you only need to give two).

    -   Predicate:  Let Q(n) = "n >= 12 -> P(n)" and prove \-/ n, Q(n) by
            simple induction.
        Base Case:  Q(0) is the statement "0 >= 12 -> P(0)", which is
            vacuously true (since 0 < 12).
        Ind. Hyp.:  Let n (- N and suppose Q(n), i.e., n >= 12 -> P(n).
        Ind. Step:  To prove Q(n+1), suppose n+1 >= 12 and consider two
            cases:
             .  Case 1:  If n+1 = 12, then prove P(12) [= P(n+1)] directly.
             .  Case 2:  If n+1 > 12, then n >= 12 so by the IH, we know
                    P(n) holds.  Use this to prove P(n+1).
            In either case, P(n+1) holds, so Q(n+1) holds as well.
        Conclusion:  By induction, \-/ n (- N, Q(n), i.e., \-/ n >= 12,
            P(n).

     -  Predicate:  Let Q(n) = P(n+12) and prove \-/ n, Q(n) by simple
            induction.
        Base Case:  Prove Q(0) = P(12) directly.
        Ind. Hyp.:  Let n (- N and suppose Q(n) = P(n+12).
        Ind. Step:  Prove Q(n+1) = P(n+13).
        Conclusion:  By induction, \-/ n (- N, Q(n), i.e., \-/ n >= 12,
            P(n).

     -  Predicate:  P(n).
        Base Case:  Prove P(12) directly.
        Ind. Hyp.:  Let n >= 12 and suppose P(n).
        Ind. Step:  Prove P(n+1).
        Conclusion:  By induction, \-/ n >= 12, P(n).


2.  Consider the following solitaire game, played with 2^k coins, for some
    k (- N, and some target natural number n <= 2^k.

     -  Divide the coins into two piles: initially, place all 2^k coins in
        one pile, and 0 coins in the other pile -- we represent this as a
        pair (2^k,0).

     -  The goal is to succeed in making one pile contain exactly n coins
        (either pile will do), i.e., we want to end up with either
        (n,(2^k)-n) or ((2^k)-n,n).

     -  There is only one way to move coins from one pile to the other:
        select one pile, split it in half, and move half of the coins to
        the other pile.  This means that there are two possible results
        starting from an arbitrary position (a,b): (a/2,b+a/2) or
        (a+b/2,b/2).  Obviously, a move can be carried out only if each
        pile contains an even number of coins, which means that the game is
        over if the piles ever end up with an odd number of coins.

     -  For example, if we start with 64 coins and n = 27, there is a
        winning sequence of moves: (64,0) => (32,32) => (48,16) => (24,40)
        => (44,20) => (54,10) => (27,37).

    For what values of k and n is it possible to solve this game?  Make a
    conjecture, state it precisely, and prove it formally.


3.  Read Examples 1.9 (pp.34-35), 1.10 (pp.35-37), and 1.13 (pp.41-42) in
    the course textbook, as well as the introductory material on pp.32-34.
    Then, prove that for all n >= 1, every full binary tree with n nodes
    contains exactly (n + 1) / 2 leaves.