1. {5 marks} Currently, the oldest living person in the world is Susannah Mushatt Jones, who was born on July 6 1899.
The current world population is at least 7 billion. Prove that there exists one particular minute in history such that 100
people currently alive were born within that minute.
2. {5 marks} Prove that for any subset S of {1, 2, . . . , 40} of size 10, there exist two different subsets A, B of S of size
3 where the sum of the elements in A is the same as the sum of the elements in B. For example, if we pick S =
{4, 7, 14, 15, 17, 19, 23, 31, 38, 40}, then A = {4, 7, 31} and B = {4, 15, 23} are both subsets of S of size 3, and both have
a sum of 42. (*)
ID: ECE 103 Assignment 4, Winter 2016, Page 2 of 4 Initials:
3. {5 marks} Prove by induction that for any integer n = 1,
Xn
k=0
2
k = 20 + 21 + · · · + 2n = 2n+1 – 1.
4. {5 marks} Prove by induction that for any integer n = 0, 2
n+2 + 32n+1 is a multiple of 7. (*)
ID: ECE 103 Assignment 4, Winter 2016, Page 3 of 4 Initials:
5. {7 marks} The Fibonacci sequence fn is defined by fn = fn-1 + fn-2 for n = 2, with initial conditions f0 = 0, f1 = 1.
The first few terms in the Fibonacci sequence are
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, . . .
Use strong induction to prove that for any integer n = 7,
10
7
n
< fn <
12
7
n
.
(Note: Treat the result as two separate inequalities.)
ID: ECE 103 Assignment 4, Winter 2016, Page 4 of 4 Initials:
6. {3 marks} We are given a rectangle with several line segments, each joining border to border inside of the rectangle.
This divides the rectangle into several regions. We wish to paint these regions with red and blue so that any two
regions that border each other through some line segment are painted with different colours (two regions that touch
each other at only a point may have the same colour). An example is given below.
By using induction on the number of line segments n = 0, prove that regardless of how we divide the rectangle, we
can always paint the rectangle in this way.
