关键词 > MATH2222/6222
MATH2222/6222 Introduction to Mathematical Thinking: Problem-Solving and Proofs 2020
发布时间：2022-06-05
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
EXAMINATION: Semester 1 — Final Exam, 2020
MATH2222/6222 Introduction to Mathematical Thinking: Problem-Solving and Proofs
Question 1
(a) Let f : s - T be a function, and suppose B s A s s . Either prove or give a counterexample to the following statement:
f (A \ B) = f (A) \ f (B) .
(b) Negate and simplify the following statement:
╱ ax e s、! ╱P (x) v o (x)、 =马 R(x)! .
Answer
(a) This is false. Let s = {1, 2}, let T = {1}, and let f : s - T be the function f (1) = f (2) = 1 . Also let A = s and let B = {1}. Then f (A \ B) = f ({2}) = {1} and f (A) \ f (B) = {1} \ {1} = a .
(b) First, rewrite ╱P (x)vo (x)、 =马 R(x) as - ╱P (x)vo (x)、vR(x) . Then we work our way through. The negation of ax e s is Vx e s . The negation of - ╱P (x) v o (x)、v R(x) is ╱P (x) v o (x)、A (-R(x)) . So the negation of the whole statement is
(Vx e s) ! ╱P (x) v o (x)、A (-R(x))! .
Question 2
Let f : A - B , g : B - A and h : A - B be functions. Suppose both g o f and h o g are injective.
(a) Is f necessarily injective? What about h ? Give a proof or counterexample for each.
(b) Prove that A and B have the same cardinality.
Answer
(a) Itfollows that f is injective. Let a1, a2 e A and suppose f (a1) = f (a2) . Then g(f (a1)) = g(f (a2)) , and because g o f is injective it follows that a1 = a2. Hence f is injective.
The function h is not necessarily injective. For a counter-example, let A = B = N and
defne f , g and h by f (n) = n + 1, g(n) = n + 1 and h(n) = 
. Then
g o f (n) = n + 2 and h o g(n) = n , so both g o f and h o g are injective. But h is not injective, since h(1) = h(2) = 1 .
(b) It follows that g is injective for the same reason that f is injective. So we have injective functions A - B and B - A. It follows from the Schroeder-Bernstein theorem that A and B have the same cardinality.
Question 3
Let k and n be integers, with 0 < k < n . Find a formula for
(-1)n-i ╱ 、i(n) ik
in terms of k and n . (Partial credit for a correct statement without proof.)
Answer The sum evaluates to n! for k = n and 0 for k < n .
First approach: Let U be the set of n -tuples (a1, . . . , an) with each aj e {1, . . . , k }, and let Ai c U be the subset of n -tuplies with each aj ≠ i . Then we are interested in lU \ (uAi)l . By the Inclusion-Exclusion principle this is given by
lU l - L lAil + L lAi n Ajl - . . . ,
and this gives exactly the sum in the problem (starting from i = n ). Now, if k < n then every (a1, . . . , an) is in some Ai so lU \ (uAi)l = 0. If k = n , U \ (uAi) has order n! .
Second approach: We prove this by induction on n . The n = 0 case is clear, and if n > 0 and k = 0 this reduces to the well-known formula((-n)n-i ╱i(n)、= 0. If n > 0 and k > 0, we use that ╱ i(n)、. i = n . ╱ 
、to get
L(-1)n-i ╱ 、i(n) ik = n L(-1)n-i 
、ik-1 .
Reindexing this gives
n L(-1)n-1-i ╱ ni(-) 1、(i + 1)k-1 = 
╱ kj(-) 1、n L(-1)n-1-i ╱ ni(-) 1、ij
If k < n then j < n - 1 for each term on the right hand side, so by the inductive hypothesis the term of the outer sum indexed by j is zero for each j , and hence we get zero.
If k = n then the term of the outer sum indexed by j = k - 1 gives n . (n - 1)! = n! by the inductive hypothesis, and the remaining terms give zero, for a total of n! .
Question 4
(a) The sum of two natural numbers is 2716 and their least common multiple is 111510 .
Find the numbers.
(b) What is the smallest positive real number x that can be expressed as
m n
25 35
for m, n e N? Find such an expression for x .
Answer
(a) Let the two numbers be a and b . Suppose a prime p divides both a + b and lcm(a, b) . Then p divides at least one of a and b , and since p l a + b it must divide the other one too. Hence we can divide a , b , their sum, and their lcm by p . We continue like this until we have divided by d = gcd(a + b, lcm(a, b)) . We use Euclid’s algorithm to compute gcd(2716, 111510) = 14. Let A = a/14 and B = b/14. Then A + B = 2716/14 = 194 and lcm(A, B) = lcm(a, b)/14 = 7965 .
Because A and B are relatively prime lcm(A, B) = AB . So we have the two equations A + B = 194 and AB = 7965 . Substitute B = 194 - A into the second equation to get a quadratic in A with solutions 59 and 135 . If we assume A < B then A = 59 and B = 135, and hence a = 14 . 59 = 826 and b = 14 . 135 = 1890 .
(b) Because lcm(25, 35) = 175, we multiply both sides by 175 to get 175x = 7m - 5n . Because gcd(7, 5) = 1, it is possible to choose m and n such that 7m - 5n = 1, for example m = 3, n = 4. Then 175x = 1, or x = 
. Because 175x is an integer, it is not possible to obtain a smaller positive value for x .
(a) Let a, s, t e N and let d = gcd(s, t) . Suppose as = 1 mod m and at = 1 mod m .
Prove that ad = 1 mod m .
(b) Let p be an odd prime and suppose g is a prime divisor of 2p - 1. Prove that g is of
the form 2kp + 1 .
Hint: Use part (a) with m = g .
Answer
(a) We know we can choose b and c with d = b . s + c . t . One of b and c will not be positive.
Assume without loss of generality that b > 0, c < 0 . Then
b . s = d + lc l . t.
Then
1 = (as)b = abs = ad+lc lt = ad . (at) lc l = ad . 1lc l = ad,
so ad = 1 .
(b) If g is a prime divisor of 2p - 1 then g is odd and 2p = 1 mod g . By Fermat’s little theorem we also have 2g-1 = 1 mod g . Hence by part (a) we have 2d = 1 mod g for d = gcd(p, g - 1) . Since p is prime, gcd(p, g - 1) is either 1 or p . It cannot be 1, since 21 去 1 mod g , so we must have gcd(p, g - 1) = p . Hence p l g - 1, or g = fp + 1 for some f > 0 . Because g is odd, f must be even, so f = 2k and g = 2pk + 1 .
Question 6
(a) Suppose f (x) = anxn + an-1xn-1 + . . . + a0 is a polynomial with integer coedcients, and let g(x) = a0xn + a1xn-1 + . . . + an. Prove that f (x) is irreducible over 0 if and
only if g(x) is irreducible over 0 .
(b) Prove that f (x) = 3x5 + 9x4 - 12x3 + 10x2 - 5x + 1 is irreducible over 0 .
Hint: Use part (a).
Answer
(a) We note that for x ≠ 0 we have g(x) = xnf (1/x) . Suppose f is not irrreducible, so
f (x) = f1 (x) . f2 (x) for polynomials f1 and f2 of positive degeee d and e respectively with d + e = n . Then f (1/x) = f1 (1/x) . f2 (1/x) , and
g(x) = xnf1 (1/x) . f2 (1/x) = ╱xdf1 (1/x)、. ╱xef2 (1/x)、.
Since f1 (1/x) is a degree d polynomial in 1/x , multiplying by xd gives a degree d polynomial in x , and similarly for xef2 (1/x) . So if we defne g1 (x) = xdf1 (1/x) and g2 (x) = xef2 (x/1) then g(x) = g1 (x) . g2 (x) so g is not irreducible.
The problem is symmetric in f and g, so it follows in the same way that if g is not irreducible then f is not irreducible.
(b) By part (a) this is equivalent to g(x) = x5 - 5x4 + 10x3 - 12x2 + 9x - 3 being irreducible. We cannot use the Eisenstein criterion directly on g(x) , but we note that if we substitute x = u + 1 then g(x) simplifes:
g(u + 1) = (u + 1)5 - 5(u + 1)4 + 10(u + 1)3 - 12(u + 1)2 + 9(u + 1) + 3 = u5 - 2u2 + 6.
Now the Eisenstein criterion with p = 2 applies, so g(u + 1) is irreducible. Now, g(u + 1) is irreducible if and only if g(x) is irreducible, so we are done.
Suppose you throw a single fair, 6 -sided die/dice (the singluar of dice is disputed) repeatedly, until the result is a 6 .
(a) What is the expected number of throws (including the last one, which gives a 6)?
(b) What is the expected number of throws (including the last one, which gives a 6) conditioned on the event that none of the throws gave a 5? (No credit for claiming
that this is the same as throwing a fair, 5 -sided die.)
Answer
(a) If we don’t want to do calculus we can do thefollowing: Let E denote the expected number
of throws. Then
E = 1 + 
E,
since after we throw the dice once we have a 5/6 probability of being in the same situation again. Solving for E gives E = 6 .
(b) This is not like throwing a 5 -sided dice. Since we don’t count the result if we get a 5, this is equivalent to the expected value of throwing the dice until it gives a 5 or a 6 and starting over (including the count) if we ended with a 5 . The expected number of throws until we get a 5 or 6 is 3, and the fact that we have a 0.5 probability of having to start over doesn’t change this. So the anwer is E = 3 .
Second approach: Use that in this case E = 1 + 
E and solve for E .
Third approach: The probability of recording a 6 on the k ’th throw is 
. ╱ 、
k-1 . Summing
this gives 
. The probability that we end with a 6, rather than a 5 (in which case we have to start over) is 1/2, so (using Bayes theorem) we have to divide 
by 
.
Fourth approach: Reason that E = 
+ 
E + 
(E + 1) , and solve for E . Here the frst term represents rolling a 6, the second term represents rolling a 5 (so we have to start over) and the third term represents rolling 1-4.
Question 8
Let s1, . . . , sn be natural numbers. For I s「n[ = {1, 2, . . . , n}, let 口(I) = ( si . Now suppose
i eI
ILs「n[ (-1) lIl ╱ m -n口(I)、= 
si .
Hint: For「m[ = {1, 2, . . . ,m}, let the _rst s1 elements be block 1 , let the next s2 elements be block 2, and so on. Now count the number of n-element subsets of「m[ with exactly one element from each block in two diferent ways.
Answer We choose to follow the hint. For an n-element subset of「m[ with exactly one element in each of the n blocks, we have s1 choices of the frst element, s2 choices of the second element, and so on for a total of L
1 si choices.
The alternating sum on the left hand side is a hint that we should use the inclusion-exclusion principle. Let Ai denote the n-element subsets of「m[ which are disjoint from the i ’th block. For I s「n[ , let AI = nieIAi . Then an n-element subset of「m[ is in AI if and only if it is
disjoint from the i ’th block for each i e I . Since there are m - 口(I) elements left to choose from we have lAil = ╱mn(-)口I、.
An n-element subset of「m[ has exactly one element in each of the n blocks if and only if it is not in any of the Ai . Hence we get the left hand side from the inclusion-exclusion principle.
Recall that the chromatic number x(G) of a graph G is the smallest k such that G has a proper k -colouring. Let G be the graph with vertices o1, o2, . . . , o2020 . Two vertices oi and oj for i ≠ j are adjacent (connected by an edge) if and only if i l j or j l i . Compute the chromatic number x(G) for this graph.
Answer We frst note that the induced subgraph on o2k for k = 0, 1, . . . , 10 forms a complete graph on 11 vertices, so these 11 vertices must have diferent colour and hence x(G) 2 11 . To show that x(G) < 11 we exhibit a proper colouring of G with 11 colours c0, c1, . . . , c10 by giving oi colour cm if i has exactly m prime factors counted with multiplicity. (So, for example, o1 gets colour c0 , o2 and o3 get colour c1 , o4 and o6 get colour c2 .) Because log2 2020 < 11, no i e「2020[ has more than 10 prime factors so this does describe a colouring of G .
If i ≠ j and i l j then j has more prime factors than i , so oi and oj have diferent colour. This shows that the 11 -colouring of G is proper, so x(G) < 11 .
We have shown that x(G) 2 11 and x(G) < 11, so we conclude that x(G) = 11 .
Question 10
Fix a real number x > -1/4, and de_ne
an = 
I ╱ n k(-) k、xk
for n 2 0 . Find a recurrence relation for an , and use it to _nd a formula for an as a function of n and x without binomial coedcients. Here Ln/2I denotes the foor function, returning the greatest integer less than or equal to n/2 .
Answer We use that ╱nk(-)k、= ╱n-k(k) -1、+ ╱n
、to compute
an = L╱n - k(k) - 1、xk + 
、xk
= L╱(n - k(1)) - k、xk + 
、x(k-1)+1 .
We recognise the frst sum on the right hand side as the sum defning an-1 and the second sum as the sum defning xan-2 , so the recurrence relation becomes
an = an-1 + xan-2 .
This is a homogeneous linear second order recurrence relation with characteristic polynomial p (t) = t2 - t - x . We have a0 = a1 = 1, so these are the initial values.
The roots of the characteristic polynomial are
1 + ′ 1 + 4x A1 =
2
A2 = ,
2
so the general solution to the homogeneous recurrence relation is
an = c . A 1(n) + D . A 2(n) .
With the initial values a0 = a1 = 1 we get c + D = 1 and cA1 + DA2 = 1, which has the
solution
c = 1 + 1 D = 1 - 1
2 2 ′ 1 + 4x 2 2 ′ 1 + 4x .
