CSC165H1 Problem Set 3

CSC165H1 Problem Set 3

1. [9 marks] build up a result...
(a) [3 marks] Suppose a; b; c are integers with ab 6= 0, gcd(jaj; jbj) = 1, and a j bc. Prove that a j c. Hint:
Use Theorem 2.2 on page 56 of the course notes.
(b) [3 marks] You may assume without proof that if n 2 N is the size of set S, and k 2 N has 0  k  n,
the expression

n
k
!
=
n!
k!(n  k)!
called \n choose k" is the number of subsets of S of size k. This is an integer, indeed it is a natural
number. Prove that if p is a prime, and 1 < k < p, then p
k


is divisible by p. Hint: Use the previous
part of this question.
(c) [3 marks] Suppose n; p 2 N, and that p is prime. Prove that n
p  n (mod p). Hint: Try induction
on n, and you may use this instance of the Binomial Theorem without proof:
(n + 1)p =
k
X=p
k=0

p
k
!
n
pk

1
k
2. [9 marks] big greek letters...
(a) [3 marks] Suppose b 2 R
+. Prove, without using Theorem 5.1 from page 86, that bn2 2 O(2n
) but
bn2
62 
(2n
). Hint: You may want to take logarithms and consider a starting point where n is an
integer power of 2.
(b) [3 marks] Prove or disprove: For all f; g : N ! R
+, that f 62 
(g) ) f 2 O(g).
(c) [3 marks] Prove or disprove: For all f1; f2; g1; g2 : N ! R
+, that f1 2 (g1) ^ f2 2 (g2) )
max(f1; f2) 2 (max(g1; g2)), where max(f1; f2)(n) = max(f1(n); f2(n)).
3. [3 marks] code... Devise an exact formula for repeat(n) below. You can check your results by running the
code in a Python interpreter (version 3.6 or higher). Explain how you derived your formula. Simplify
your calculations by stating a big- asymptotic bound for repeat(n), and explain your reasoning.
1 def repeat(n: int) -> int:
2 summation = 0
3 for i in range(n):
4 for j in range(n**(i % 3)):
5 summation = summation + 1
6 return summation
4. [9 marks] n to n + 1...
(a) [3 marks] Use induction to prove that for n 2 N, 6 divides 52n+1 + 1. You may not use Ex. 2.19 on
modular arithmetic.
(b) [3 marks] Use induction to prove that for any natural number n,
i
X=n
i=0
(1=7)i =
7  (1=7)n
6
You may not use any formulas for geometric series.
Page
CSC165H1, Fall 2019 Problem Set 3
(c) [3 marks] Notice below that any square could be tiled (exactly covered without overlapping) using
four squares that are half its width. It could also be tiled using six smaller squares: one that is 2=3
its width tucked into the upper-left corner, and 5 that are 1=3 its width across the bottom and up
the right margin. Or it could be tiled using seven smaller squares: three that are half its width,
plus four that are 1=4 its width. Or it could be tiled using eight smaller squares: one that is 3=4 its
width tucked in the top-left corner, plus seven that are 1=4 its width bordering the larger one on
the bottom and right.
Assume the facts in the above paragraph, or make some drawings if you are unconvinced. Then use
those assumptions, and induction on n, to prove the following three facts:
De ne P6(n) : \Any square can be tiled by 6 + 3n smaller squares." Prove 8n 2 N; P6(n).
De ne P7(n) : \Any square can be tiled by 7 + 3n smaller squares." Prove 8n 2 N; P7(n).
De ne P8(n) : \Any square can be tiled by 8 + 3n smaller squares." Prove 8n 2 N; P8(n).
Finally, use all three facts to prove that any square can be tiled by m smaller squares, provided
m  6 is an integer.
Page 3/3