MATH2222/6222 Introduction to Mathematical Thinking: Problem-Solving and Proofs 2021

Question 1

You can write your solution on a separate piece of paper.

Answer

(a)  This is false. Take the unique function f  : {1. 2} → {1}, let A = {1. 2}, and let B = {1} . Then A \ B = {2}, so f (A \ B) = {1}. But f (A) \ f (B) = {1} \ {1} = a, so we don’t have equality in this case.

(b)  This is true. We prove both set inclusions.

To show that f -1 (A \ B) - f -1 (A) \ f -1 (B) , let x e f -1 (A \ B) . By defnition that means f (x) e A \ B, so f (x) e A and f (x) 4 B . Hence x e f -1 (A) and x 4 f -1 (B) , which implies that x e f -1 (A) \ f -1 (B) .

To show that f -1 (A) \f -1 (B) - f -1 (A \ B) , let x e f -1 (A) \f -1 (B) . By defnition that means x e f -1 (A) and x 4 f -1 (B) , so f (x) e A and f (x) 4 B . Hence f (x) e A \ B , so x e f -1 (A \ B) .

This proves both inclusions, so we have equality.  (It is possible to combine the two arguments and show that x e f -1 (A \ B) e→ f -1 (A) \ f -1 (B) directly.)

Question 2

Compute the remainder of 22021  divided by 2021. You might and some of the following facts useful:

●  2021 = 43 . 47 , and 43 and 47 are both prime.

●  43 . 47 = 42 . 48 + 5 .

● 43 . 47 = 44 . 46 - 3 .

●  6 . 8 = 1  mod 47 , and 8 = 23 .

● The answer is one of 0 , 1 , 290 , 444 , 1322 , and 1949. (You’re allowed to test each one.)

You can write your solution on a separate piece of paper.

Answer We need to compute 22021   mod 2021 . Since 2021 = 43 . 47, and 43 and 47 are relatively prime, it follows from the Chinese Remainder Theorem that it sufces to compute 22021   mod 43 and 22021   mod 47 .

We recall that Fermat’s Little Theorem says thatfor p + a we have ap -1 = 1  mod p . Working mod 43 we then have 242 = 1  mod 43, and we fnd that

22021 = 242.48 . 25 = 25 = 32   mod 43

Similarly we have 246 = 1  mod 47, and we fnd that

22021 = 244.46-3 = 2-3 = 8-1 = 6   mod 47y

The last congurence follows from 6 . 8 = 1  mod 47, which implies that 8-1 = 6  mod 47 .    Hence the remainder r satisfes r = 32  mod 43 and r = 6  mod 47 . Since the answer is one of 0, 1, 290, 444, 1322 and 1949 we can simply test each one:

0 = 0 290 = 32 444 = 14 1322 = 32

1949 = 14

mod 43 mod 43 mod 43  mod 43

mod 43

0 = 0

290 = 8

444 = 21

1322 = 6

1949 = 22

mod 47

mod 47

mod 47

mod 47

mod 47

We see that 1322 is the only one that works. So the answer is 1322 .

Question 3

Suppose a2 + 2b2  = c2 with a. b. c e N pairwise relatively prime. Prove that there exists natural numbers m and n , and r e {1. 2} with

n2 - 2m2

r

=

2mn n2 + 2m2

r                      r      y

Hint 1: Start by think about the ellipse deaned by x2 + 2g2 = 1 and the intersection of the ellipse and a line through (-1. 0) with slope t .

Hint 2: Alternatively, start by proving that a and c are both odd and that gcd(c - a. c +a) = 2 . Then rewrite the equation as 2b2 = c2 - a2 .

You can write your solution on a separate piece of paper.

Answer

Answer 1: A solution (a. b. c) to a2 + 2b2 = c2 gives a point (x. g) = ( . ) on the ellipse. So consider a pair (x. g) with x. g ← 0 and x2 + 2g2 = 1 . Let t be the slope of the line through (-1. 0) and (x. g) . Then g = t (x + 1) , and by substituting into x2 + 2g2 = 1 we fnd that

x2 (1 + 2t2) + 4t2x + (2t2 - 1) = 0y

This has two solutions: x = -1 and

-4t2 + ′16t2 + 4(1 + 2t2)(1 - 2t2) 1 - 2t2

2 + 4t2                                 1 + 2t2 y

We also get g = t (x + 1) = . If x. g e Q then t e Q as well. If t = in lowest terms we then get x = and g = . Itfollows that

(a. b. c) = (n2 - 2m2. 2mn. n2 + 2m )2

is a solution to a2 + 2b2 = c2 .

If n is odd then it follows from the assumption that m and n are relatively prime that a , b and c are pairwise relatively prime (so r = 1). If n is even then a , b and c all share a factor of 2, while , and are pairwise relatively prime, so in this case r = 2 ..

Answer 2: If one of a and c  is even then so is the other, and a , b and c are not pairwise relatively prime. Hence a and c must both be odd. We see that c - a and c + a are both even, so 2 is a common factor. Moreover,

gcd(c - a. c + a) = gcd(c - a. 2a) = 2 gcd(c - a. a) = 2 gcd(c. a) = 2y

By working   mod 4 itfollows that exactly one of c - a and c + a is divisible by 4. If c - a is

divisible by 4 we write

b2 = (c - a) y

Since c - a and are relatively prime, the only wayfor their product to be a square is for each factor to be a square. Hence there exists m and n with c - a = 4m2  and = n2 . Moreover n is odd. In this case we get a = n2 - 2m2 , b = 2mn, and c = n2 + 2m2 , and because m and n are relatively prime and n is odd itfollows that a , b and c are pairwise relatively prime (so r = 1 in this case).

If instead c + a is divisible by 4 we write

b2 = (c + a) y

Again the only way for their product to be a square is for each factor to be a square. Hence there exists m and n with = m2  and c + a = 4n2 . In this case a = 2n2 - m2 , b = 2mn, and c = 2n2 + m2 . But we can rewrite this as a = , b = , and c = . Again it follows from the assumption that m and n are relatively prime thta a , b and c are pairwise relatively prime (so r = 2 in this case).

Question 4

Suppose you have two decks of cards. Each deck consists of 52 cards, but one is a standard deck and the other consists entirely of hearts collected from 4 standard decks.

(a) You pick one of the two decks at random. Then you pick one card from that deck at

random, and it is the ace of hearts. What is the probability that you picked the deck with all hearts?

(b) You pick a second card from the same deck at random. (Without putting the ace of

hearts back.) It is the 7 of hearts. Now what is the probability that you picked the deck with all hearts?

You can write your solution on a separate piece of paper.

Answer

(a) Let A be the event that you picked the deck with all hearts and let B be the event that

you picked the ace of hearts. By Bayes’formula we get

P (BlA) . P (A)                     P (BlA) . P (A)

P (AlB) = =

P (B)             P (BlA) . P (A) + P (Bl-A) . P (-A)

1/13 . 1/2             4

= = y

1/13 . 1/2 + 1/52 . 1/2    5

(Other arguments without an explicit reference to Bayes’formula are also possible.)

(b)  We argue the same way, now with B being the event that you picked the ace and 7 of

hearts. We need to compute P (BlA) and P (Bl-A) . To compute P (BlA) , we work with the deck with all hearts. Then there is a 1/13 chance of picking the ace of hearts, and then a 4/51 chance of picking the 7 of hearts, for a total of 1/13 . 4/51. To compute P (Bl-A) , we work with the regular deck. Then there is a 1/52 chance of picking the ace of hearts, and then a 1/51 chance of picking the 7 of hearts. Pluggin into Bayes’formula

we get

1/13 . 4/51 . 1/2                        16        16

P (AlB) = = = y

1/13 . 4/51 . 1/2 + 1/52 . 1/51 . 1/2     16 + 1     17

(Again other arguments without an explicit reference to Bayes’formula are possible.)

Question 5

Six people of di住erent heights are getting in line to buy donuts. Compute the number of ways they can arrange themselves in line such that no three consecutive people are in

increasing order of height, from front to back.

Hint: Use the inclusion-exclusion principle.

You can write your solution on a separate piece of paper.

Answer As the hint suggests, we use the inclusions-exclusion principle. Let A be the set of lineups where persons 1, 2 and 3 are in increasing order of height, let B be the set where 2, 3 and 4 are in increasing order of height, let c be the set where 3, 4 and 5 are in increasing order of height, and let D be the set where 4, 5 and 6 are in increasing order of height. Let U be the set of all possible lineups. Then we are looking for lU - (A u B u c u D) l , and by the inclusion-exclusion principle this is given by

lU l - lAl - lBl - lc l - lD l + lA n Bl + lA n c l + lA n D l + lB n c l + lB n D l + lc n D l -lA n B n c l - lA n B n D l - lA n c n D l - lB n c n D l + lA n B n c n D ly

This is a total of 16 terms. We calculate the size of each. First, we have lU l = 7! = 720 .          For A, we have ╱3(6)、= 20 ways of choosing the people in position 1, 2 and 3 and then 3! = 6 ways of arranging the remaining people in position 4, 5 and 6 . Hence lAl = ╱ 3(6)、. 3! = 20 . 6 = 120 . The same calculation applies to lBl , lc l and lD l .

For A n B, we have ╱4(6)、= 15 ways of choosing the people in position 1, 2, 3 and 4 and 2! = 2 ways of arranging the remaining people in position 5 and 6 . Hence lAnBl = ╱4(6)、.2! = 15 .2 = 30 . The same calculation applies to lB n c l and lc n D l .

For A n c the frst 5 people have to be in order, so we get lA n c l = ╱ 5(6)、. 1! = 6 . The same calculation applies to lB n D l .

For A n D the frst 3 and the last 3 people have to be in order, so we get lA n D l = ╱ 3(6)、= 20 . For A n B n c and B n c n D we get ╱ 5(6)、. 1! = 6, while for A n B n D and A n c n D all 6 people have to be in order so we get 1 .

Finally, for A n B n c n D all 6 people have to be in order so again we get 1 . Putting it all together we get

720 - 4 . 120 + 3 . 30 + 2 . 6 + 1 . 20 - 2 . 6 - 2 . 1 + 1 . 1 = 349y

Question 6