Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Proof Creator 1 Problems

MAT246 LEC0101, Fall 2021

Assignment Information

● Writing Tips: See the handout posted on the course website. Also the additional writing supports (writing centres, ELL supports, office hours).

● Save all of your ‘rough work’ and drafts, including things that didn’t work. We’ll ask you to submit them.

● A Draft of some of the problems will be due in your tutorial during Week 3 of the semester.

● Your full problem set is due in Week 4. You need to submit 1 Breezy problem, 3 Windy problems, and 2 Gale problems for full credit.

● Your problem set solutions should be typed in LaTeX. The exception is pictures, which you should take a picture of and insert as a picture (we’ll provide resources for this). LaTeX templates specific to this assignment will be available on Overleaf.

● You can (and should!) work with people in the class on the problems, but do not work with anyone on the write-up. You should be very careful about working with people outside of the class.

        Write careful and complete proofs to each of the following, unless otherwise noted. Also, all numbers are assumed to be natural numbers (again, unless otherwise noted!). Problems in magenta require material from Chapter 3 of Rosenthal, which we will discuss during Week 3.

1 Breezy Problems

1. (Divisibility) In this problem we’ll prove the following:

Theorem 1.1. If n, m ∈ N, n, m > 1 (STRICTLY greater than 1!!), and n|m, then n km + 1.

(a) Give an intuitive explanation why this theorem makes sense, using a picture.

(b) Prove the theorem.

2. (Quintic Powers)

(a) For several numbers x with different ones’ digits, compute x5 and x.∗ What do you notice about the relationship between the ones’ digits of the resulting numbers? Does it matter what the ones’ digit is for x?

(b) Use your observations to write down a conjecture about the relationship between x5 and x modulo 10.

(c) Prove your conjecture is true.

2 Windy Problems

3. (Geometric Induction) Exercise 16 of Ch 2 (will require some extra reading in Rosenthal to complete)

4. (6n + 1 primes)

(a) Write down several numbers in the set {6n + 1|n ∈ N}. What percentage of the numbers that you wrote down are prime numbers? Do you think that this percentage will increase or decrease if you were to write out more numbers in the set?

(b) Test out your hypothesis by writing out 10 more numbers in the set in part (a).

(c) Prove that there is an infinite number of primes in the set in part (a).†

5. (Modular Inverses)

a) Just as we have inverses under the usual addition and multiplication operations, we can also define inverses in modular arithmetic too. For example, the inverse of a in addition modulo m is the number b (if it exists) such that

a + b ≡ 0 mod m.

Carefully define the multiplicative inverse of a number modulo m.

b) Draw a picture that demonstrates how you envision modular arithmetic modulo 8 and modulo 10. Then use two copies of each picture to pair up the additive inverses and the multiplicative inverses modulo each base by drawing a line or other suitable connector between them.

c) Prove that a does not have an inverse mod m when a|m.

d) What is the converse of (c)?‡ Do you think that it is true or false based on your work in (c)? (You do not need to prove your answer)

6. (Modular Squares) In this question we will explore square numbers in modular arithmetic.

(a) Choose one odd number γ less than 20 and one even number ζ between 5 than 20. Draw a picture that demonstrates how you envision modular arithmetic modulo γ and ζ. For each t = 0, 1, . . . γ − 1, compute t2 mod γ, and for each s = 0, 1, . . . ζ − 1, compute s2 mod ζ.§ Mark the results of your calculations on the appropriate diagram, by circling the result. How many squares are there mod γ and mod ζ?

(b) Let ζ = 8. Repeat part (a). (If you happened to choose 8 in (a), choose a different ζ and switch for your final copy!)

(c) Suppose that t is an odd number. Carefully prove why for any odd number (not just those in the range 0, 1, . . . 7), t2 mod 8 will always give the same answer.

7. (Popcorn Garlands) Suppose that we are making garlands out of glittered popcorn (it’s never too early in the fall semester to get in the holiday spirit!).¶

a) Suppose that we have an unlimited amount of silver and gold-glittered popcorn kernels, and that we would like to put three popcorn kernels on a garlands. Show that there are exactly 8 different ways to do this and that 6 of them are mini-garlands with both gold and silver kernels.

b) Now suppose that we have an unlimited number of silver, gold, and red popcorn kernels, and that we would like to put 5 kernels on a garlands. How many different ways are there to do this? How many of these mini- garlands contain more than one colour?

c) Suppose once again that we have an unlimited number of silver and gold kernels, but would like to make garlands with p popcorn kernels on them. How many different garlands can we make? How many of these garlands contain both silver and gold kernels?

d) Now suppose that we have an unlimited stock of popcorn kernels of a different colours, and would like to make garlands with p popcorns on them. How many different garlands can we make? How many of these garlands contain more than one colour?

e) To prepare this for what comes next in MAT246, we need to make loops out of our garlands: that is, we need to throw them around the tree!! Let’s throw out the garlands that only contained popcorns of one colour, and make loops out of each of the remaining garlands. Show that if we place the looped garlands from part (a) into groups based on which ones look the same (e.g. which ones are rotationally equivalent), we will obtain 2 groups of 3 loops.

f) Now consider the case where we have a colours and garlands of p popcorns. As before, throw out the garlands that only contain one colour and make loops out of the other ones. Show that you can divide these loops into groups of p loops.

g) Let’s bring this all back to the world of mathematics. Can you restate part of this problem in terms of an operation in mathematics? Can you translate part of this problem to a theorem in math? (Note: At this point, it might not be possible to do it all, and that’s okay!!

3 Gale Problems

8. (Numbers on foreheads) Here is the set-up of a game that has been used in psychology research studies on topics like cooperation, trust, and reward.

● The game involves two participants. Both participants have the same amount of information, and know nothing about the game ahead of time.

● Participants are told that a Research Assistant will tape a whole number greater than 0 on their foreheads, so that they can each see each others’ numbers, but they cannot see the number taped to their own forehead.

● After the Research Assistant has left the room the participants will alternate asking each other the same question: ‘do you know what your number is?’ The other participant must answer this question honestly with a yes or no answer.

In one variation of the game the Participants are also told that their numbers are consecutive (although not in what order). For this variation, determine if the game ever ends sometimes, always, or never. Does your answer change if you are guaranteed that the participants will always play perfectly rationally (e.g. use all of the available information and make perfect conclusions)?

9. (Fashionistas) Following the New York MET Gala each year there is a secret group of Fashionistas - the MET Fashion Police (MFP) - that meets to discuss what they saw and to make plans for the future.

One condition of membership in the MFP is that the members cannot commit a Fashion Crime. Any member who has committed a Fashion Crime should immediately make an announcement of this fact, and promptly (that is, IMMEDIATELY) resign. Since its inception there have been no members who have been aware of their own Fashion Crimes, so the membership in the group has only grown.

In fact, at one MET Ball or another every member of the MFP has committed a Fashion Crime. The Crimes have been mentioned to all other members of the MFP other the person who has committed the Crime (yes, the members of the MFP are also big gossips): all other members of the MFP therefore knew that everyone else had committed a fashion crime. The person committing the Fashion Crime was not told because the MFP members want to avoid resignations.

Recently, the MFP invited a new member to the group: Gemma Chan. Gemma immediately was invited to the gossip mill and found out about the past Fashion Crimes. She was stunned to learn that all of her former members of the MFP had committed Fashion Crimes but were unaware of it (even though everyone was aware that everyone else had committed a fashion crime). So, Gemma decided to make a move.k

At the September meeting of the MFP, Gemma came in front of the group and said: “If we just create and do not think about what might happen, that’s when we get into trouble. That’s why I need to tell you that at least one of you has committed a Fashion Crime, which has been discovered by others in the group.”∗∗

A condition for membership in MFP is that members must be excellent at deductive logic. Assuming that they are able to figure out the full consequences of Gemma’s declarations immediately, what will happen? What should happen? Explain all of the consequences.

10. Here’s another game that has interested researchers, especially those of the type who work in the Max Gluskin House on campus at UofT. It’s also a two-player game, but this time the payment is integral to describing the game. There is no direct Researcher involvement in the game, other than potentially as the source of a payout.

For the sake of describing the game, imagine that Anson and Kanav are our two players and that they are playing the game virtually via Zoom for bitcoins, denoted . There are always two piles of bitcoin in play: a larger one and a smaller one. Ahead of the game Anson and Kanav decide the maximum number 2n of turns, for some n ∈ N greater than or equal to 1.

● During the first turn the large pile of bitcoin has 4 and the smaller pile of bitcoin has 1 . Anson can either take the bitcoin or pass. If Anson (4 B) takes the bitcoin he gets the larger pile, Kanav gets the smaller pile (1 ) and the game ends. If he passes, the size of each pile is doubled.

● Now the large pile of bitcoin has 8 Band the smaller pile has a 2 . During the second turn Kanav can either take the bitcoin or pass. If he takes the bitcoin, Kanav leaves with 8 , Anson leaves with 2 , and the game ends. If he passes the piles double.

● In general, during odd-numbered turns Anson can either take the bitcoin or pass. After each pass the piles double. If Anson takes the bitcoin the game ends.

● (Piles of Bitcoins) In general, during even-numbered turns Kanav can either take the bitcoin or pass. After each pass the piles double. If Kanav takes the bitcoin the game ends.

(a) What do you think usually happens when two players engage in a game like this? That is, how many rounds do you think they usually play to? You can state your guess as either a number or as a percentage of 2n, depending on what you guess. Give a reason that doesn’t have anything to do with math.

(b) How many rounds will the game end in if both players are playing entirely strategically, and they both know that each other is playing strategically? Here, a strategic approach means that you care only about maximizing your amount of money. Prove your answer using an induction-type argument.

(c) What can you say about the number of rounds the game will last if only one player is playing strategically? (Economists have found that even when both players are aware of the best strategy they do not play strategically.)