COMP 280 — Exam 1

Seven problems:

0. (2 points)

   Sign your name, and write the Honor Code Pledge.

1. (14 points — 5 points part a, 9 points part b)

   1. Find a formula for

      1 1×2

      +

      1 2×3

      + … +

      1 n×(n+1)

      by examining the values of this expression for small values of n.

   2. Prove the formula you conjectured in part (a).

2. (14 points — 5 points part a, 9 points part b)

   Show that it is possible to arrange the numbers 1, 2, …, n in a row so that the average of any two of these numbers never appears between them.

   1. Show that it suffices to prove this fact when n is a power of 2.

   2. Then use mathematical induction to prove the result when n is a power of 2.

3. (14 points)

   Consider this variation of the game of Nim. The game begins with n matchsticks. Two players take turns removing matchsticks — one, two, or three at a time. The player removing the last matchstick loses. Use strong induction to show that if each player plays the best strategy possible, the first player wins if n is of the form 4j, 4j+2, or 4j+3 for some nonnegative integer j, and the second player wins in the remaining case when n is of the form 4j+1 for some nonnegative integer j.

4. (14 points — 2 points part a, 6 points each parts b and c)

   Let S be the subset of the set of ordered pairs of integers defined recursively by

   Basis Step:

   (0,0) ∈ S

   Recursive step:

   If (a,b) ∈ S, then (a+2,b+3) ∈ S, and (a+3,b+2) ∈ S.

   1. List the elements of S produced by the first five applications of the recursive definition.

   2. Use strong induction on the number of applications of the recursive step of the definition to show that 5 | a+b when (a,b) ∈ S.

      As a reminder, x | y means that x divides y.

   3. Use structural induction to show that 5 | a+b when (a,b) ∈ S.

5. (14 points)

   Suppose that f(x), g(x), and h(x) are functions such that f(x) is O(g(x)) and g(x) is O(h(x)). Show that f(x) is O(h(x)).

6. (14 points)

   Show that if f(x) and g(x) are functions from the set of real numbers to the set of real numbers, then f(x) is O(g(x)) if and only if g(x) is Ω(f(x)).

7. (14 points)

   A knight on a chessboard can move either one space horizontally (in either direction) and two spaces vertically (in either direction) or one space vertically (in either direction) and two spaces horizontally (in either direction). Suppose that we have an infinite chessboard, made up of all squares (m,n), where m and n are nonnegative integers. Use mathematical induction to show that a knight starting at (0,0) can visit every square using a finite sequence of moves.

   Hint: Use induction on the variable s=m+n.