Foundations of Computer Science: Honors
Homework 3B
Problem 8 You have 10000 kilograms of pickles. Pickles are 99 percent water by volume. Water comprises 100 percent of the mass of the pickle. Time goes by, and you observe that some water has evaporated. Now water comprises only 98 percent of the volume. What is the weight of the pickles now?
Problem 10
Prove the following using mathematical induction:
1. 2n ≤ 2n
2. 1 + 3 + 5 + ... + (2n−1) = n2
3. 12 + 22 + 32 + ... + n2 = (n)(n+1)(2n+1
Problem 11
You have an n×m bar of chocolate. Your goal is to separate all of the squares of chocolate. The way that you can break the chocolate is to take a single piece of chocolate (connected component of squares) and break it along one horizontal or vertical line. What is the minimum number of breaks necessary? Please prove your answer.
Problem 12 You have an n×n checkerboard with an initial set of checkers placed on it. You are allowed to add additional checkers under the following conditions: You can place a checker on a square if two or more neighboring squares also have checkers on them. Neighboring cells are those above, below, to the left and to the right. As we showed in class, there are initial configurations of n checkers that enable the entire board to be covered. Prove that no configuration of n−1 checkers can let you cover the board.
