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

## Reviews

There are no reviews yet.