True/False problems!
1.Letx,y,andnbeintegerssuchthatx≡y modn. Thenx2 ≡y2 mod n2. (False)
2. If a divides b and c divides b, then ac divides b. (False)
3. Let r and s be positive integers such that r is an even number and s is
an odd number. Then rs + sr−1 + r + s is always even. (True)
4. Let n be an integer. Then n2%5 can take the values 0, 1, and 4. (True)
5. Every prime number other than 2 can be expressed in the form of 4k+1 or 4k − 3 for some k ∈ Z. (False)
6. (a) Consider the following algorithm:
Input: two positive integers m,n such that m > n.
(i) Sets=0anda=0. (ii) If a = m then stop.
(iii) Otherwise
– increase s by 1;
– definea=m+(−1)s((m−n)−s); – go to (ii).
Output: s.
If the input is n = 2 and m = 10 then this algorithm outputs 7. FALSE
(b) The algorithm from (a) is guaranteed to stop, no matter what the input is. TRUE
(c) If the algorithm from (a) stops then it goes through the step (iii) (m − n − 2) times. FALSE
1
7. Suppose that algorithm A has running time n2 + 10 log2(n) and the algorithm B has the running time n log2(n) + 5n (where both depend on the input value n). Then for a sufficiently large input value n, algorithm B is faster. TRUE
8. One day in a small town two magical creatures, called rav, appeared. A rav will stay with its owner only for one day, then it will double itself at night and each rav teleports to a new person. Ravs are very sensitive and they will not apper in front of a person who already has a rav on that day. Let T(n) be the number of ravs in the town n days after the first ravs appeared. Then T(n) satisfies the following recurrence relation and the initial condition:
T(n)=2T(n−1), ifn≥1, T(0) = 2.
TRUE
9. If a, b are rationals and m,n are integers then an + nb must also be rational. TRUE
10. If a,b are irrational numbers and m,n are integers then an + nb must also be irrational. FALSE
11. If a is irrational and b is rational then ab must be irrational. FALSE
12. There exist three strings x,y,z over a finite alphabet with the following properties:
(1) x is a prefix of y (2) y is a prefix of z (3) z is a prefix of x.
TRUE
13. Let p be the number of prefixes of the word “BOOKKEEPER” and s be the number of suffixes of the same word. Then 2s−p+1 = 11. FALSE
2
14. Let A = {n| n ∈ Zandniseven} and B = {n| (n−2)(n−3)(n− 4)(n − 5) = 0}. Then
((Z \ A) ∪ B) ∩ R = {3, 5}.
FALSE
15. There exists a set Y such that for any other set X if X ∈ Y then X ̸= X. TRUE
16. Letf:N→Nandg:N→Nbetwofunctionsdefinedbytherules: f(n)=n2 +1 and g(n)= n(n+1)(n+2)
3
Then g ◦ f (n) does not exist. FALSE
17. Consider a small dairy shop. Let A be a set containing all items sold in this shop. Then a rule f which takes as input an item sold in the shop and outputs its price in dollars (e.g. 1.25 corresponds to 1 dollar 25 cents) is a function from A to R. TRUE
18. Letf :N→Zbeafunctiondefinedbyarulef(x)=3x.Thenthe domain of f is N and the range of f is the set of all odd numbers. FALSE
10! 10! 10
19. There exist exactly 1!9! + 2!8! tables of size 10 by 10 of zeros and
ones with each row containing at most 2 zeros. FALSE
20. There are exactly (10!)10 tables of size 11 by 11 such that each row contains every number between 12 and 22 exactly once and the third column contains only zeros. FALSE
21. You have 4 pegs and 20 identical discs. Each peg can only fit a maxi- mum of 11 disks. Then there are 23 − 4 · 11 ways of placing all of
the disks onto the pegs
FALSE
3
32
22. There are exactly 6! strings which can be made by rearranging the letters of the word “ZOOKEEPER” such that there are two “O”s in a row and three “E”s in a row. TRUE
23. Alice goes to a high school with 350 girls and 400 boys. There will be a big netball tournament. The school needs to choose 5 boys and 5 girls to represent the school. The probability that Alice will be chosen as member of the netball team is less than 1%. FALSE
24. The function f(n) = 3n+1 grows faster than the function g(n) = 3n (FALSE)
25. Iff:N→Nandg:N→Naretwofunctionsandf growsfasterthan g, then for every natural number n, f(n) > g(n). (FALSE)
26. Suppose that an algorithm takes in a natural number n as an input, and the running time as a function of n is n2 elementary operations. Then doubling the input n will make the running time increase by a factor of four. (TRUE)
27. Consider the following argument that a graph with 100 edges must have at least 15 vertices:
This argument is a proof by contradiction. (TRUE)
28. Consider the following argument that there is a graph with 100 edges and 15 vertices:
4
Suppose G has 100 edges, but less than 15 vertices. Say G has n vertices. Then the largest possible number of edges that G can have is
if G is a complete graph, in which case there are n(n − 1) edges. But 14 × 13 2
since n < 15, the largest that this could be is 2 = 91. But G has
100 edges, so this is impossible, and therefore G must have at least 15 vertices.
Consider K15, the complete graph with 15 vertices, which has
15 × 14 = 105 edges. This is the wrong number of edges for our graph, 2
so we delete 5 edges from K15 and call the resulting graph G. Then G has 100 edges and 15 vertices, as desired.
This argument is a proof by contradiction. (FALSE)
29. If T is a tree, then T cannot have exactly one leaf (TRUE)
30. Every connected graph with the same number of edges as vertices con- tains a cycle graph as a subgraph. (TRUE)
31. If G is a connected graph, then G must contain two vertices v and w such that there is only one path from v to w. (FALSE)
32. If G is a graph with 10 vertices, then G cannot contain a vertex of degree 8 and a vertex of degree 2. (FALSE)
33. If G is a graph with 10 vertices, then G cannot contain a vertex of degree 8 and two vertices of degree 0. (TRUE)
34. Suppose that we wish to prove that there is a graph G with 10 vertices, in which half of the vertices have degree 2, and the other half have degree 4.
Proof by construction would be an appropriate method to use. (TRUE)
35. Suppose that we wish to show that there is an integer n such that
5n = n5.
Proof by induction would be an appropriate method to use. (FALSE)
36. Suppose we define a0 to be some particular value, and then define an+1 recursively by setting an+1 = a2n + 2an for each natural number n.
Consider the following argument that an must be odd for every n.
5
Suppose that for some natural number n, an is an odd number. Then a2n is odd, and 2an is even. Since an+1 = a2n +2an, it is the sum of an odd number and an even number, so it must also be odd.
Therefore for every natural number n, an is odd.
This argument correctly proves that an is odd for every natural number n. (FALSE)
37. Consider the following argument that if m and n are integers and m−n is odd then mn is even.
This argument correctly proves that if m and n are integers and m − n is odd then mn is even. (FALSE)
38. Consider the following argument that for any integer n, n%3 = n3%3.
This argument correctly proves that for any integer n, n%3 = n3%3. (TRUE)
Free-response problems!
1. Let n be a composite number such that every prime factor of n is greater than ⌈√3 n⌉. Prove that n is a product of two primes.
6
m−n is odd, so there is some integer k such that m−n = 2k+1. Therefore m=n+2k+1, so m must be odd, and n must be even. So there is an integer l such that n = 2l, and m = 2l+2k+1. So mn=2l(2l+2k+1)=2(2l2 +2lk+l)whichshowsmniseven.
If n%3 = 0 then n3%3 = 03%3 = 0.
If n%3 = 1 then n3%3 = 13%3 = 1.
If n%3 = 2 then n3%3 = 23%3 = 8%3 = 2.
In each case n%3 = n3%3.
For any integer n, n%3 is equal to one of 0,1, or 2, and therefore n%3 = n3%3.
(a) Since n is composite, n has a unique prime factorisation given by
n = p1p2 ...pm,m ≥ 2
where pi’s are prime for all i = 1,2,...,m. Note that, we do not assume pi’s must be all distinct. We are given that pi > ⌈√3 n⌉ ≥ √3 n because pi is an integer. We prove by con- tradiction. Assume that m ≥ 3. Then,
n=p1p2…pm ≥p1p2p3 >(√3 n)3 =n
which is a contradiction. Thus m = 2 and p is a product of two primes.
2. Consider the following algorithm: Input: a positive integer number n.
(i) Initialise by setting a=0,b=0,c=1
(ii) a) b)
(iii) a)
If a < n,replace a with a+1, and go to step(ii). Ifa=n,replaceawith0andgotostep(iii).
Ifb
Base case: The first time the algorithm arrives at step (iii) a=0,b=0 and c=1. So
c−(a+n)b = 1−(0+n)0 = 1−1 = 0 So everything is good in the base case.
Inductive Step: Assume that ck − nbk = 0 for an integer k ≥ 1. Prove that ck+1 −nbk+1 = 0. Indeed, bk+1 = bk +1 and ck+1 =ck ·n. So
ck+1 −nbk+1 =ck ·n−nbk+1 =ck ·n−n·nbk =n(ck −nbk) By inductive hypothesis ck − nbk = 0. Hence ck+1 − nbk+1 =
n(ck − nbk ) = 0, as required.
By the principle of mathematical induction ck − nbk = 0 for
every positive integer k. Therefore
ck −nbk −(ck+1 −nbk+1)=0−0=0.
That is the quantity c − (a + n)b at the start of step (iii) is the same as the value at the start of the next time we go through step (iii).
3. Suppose that T is a tree such that for every vertex v of T , (deg(v))%3 = 1. Prove that T cannot have 25 vertices.
9
Proof:
Suppose that T is such a tree, and that T does have 25 vertices. For each vertex, the degree is one more than a multiple of 3. Therefore adding all of the degrees together gives a number which is 25 more than a multiple of 3, say 3l + 25, for some integer l.
But a tree with 25 vertices has 24 edges. Therefore by the hand- shaking lemma we must have 3l+25 = 2×24, so that 3l+25 = 48, and 3l = 23, which is impossible, since 23 is not a multiple of 3. This gives the desired contradiction, and therefore shows that the tree cannot have 25 vertices.
10