Assignment Information

Proof Creator Assignments are your opportunity to work on creating interesting and new proofs yourself!! The problems here are interesting.   On Proof Creator  1 the problems are mainly related to the natural numbers and general  “problem-solving” skills because they were assigned during Week  1 of the course. There are some problems where you will need to use the technique of mathematical induction.

Write careful and complete proofs to each of the problems, unless otherwise noted. Also, all numbers are assumed to be natural numbers (again, unless otherwise noted!).

· 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 some of them with your portfolio at the end of the term.

·  During Week 2 of the Semester (week of September 19) you will bring a copy of at a solution on paper

to tutorial for feedback by your peers.They will provide feedback on at least one of your solutions during the week of September 19 and the week of September 26 in tutorial.

· Your solutions are due on Grade Scope on September 30. If you do not submit the initial Proof Creator

then you cannot submit any further solutions for grading consideration.

·  Not all problem solutions are required. You need to submit 1 Breezy problem, 2 Windy problems,

and 1 Gale problems for full credit on this assignment.  Each problem will be graded independently, and you can submit each problem independently for “regrading” on subsequent drafts. *

· 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.

·  Submission will be on Gradescope.

– You will submit each problem separately.

– Not all problems will be submitted (only 1 Breezy, 3 Windy, and 1 Gale problem will be submitted)

– You will also submit evidence you participated in the Peer Reviewer: your peer-reviewed problem from tutorial and answers to 3 questions about your experience in peer reviewer. Make sure you leave a few minutes to answer these questions when you submit your assignment.

Contents

1    Breezy Problems

ONLY SUBMIT 1 PROBLEM FROM THIS SECTION

1.1    Fermi Problems

a) Watch this video on Fermi estimation problems. Write down your own definition of a Fermi problem, and the technique used to approximate a solution to Fermi problems.

b) Write your own unique Fermi problem that is related to something in your life  (e.g.   a hobby, an interest, something related to your family, etc.). Make sure it’s of a new style (i.e. not ‘how many XX are there in XX?’ or an easy variatio n of a problem off of a TOP XX Fermi problems! list.) Explain why you wrote it, and include a sample solution.

c)  Before you hand it in, trade Fermi problems with someone else. Include a picture of your classmates’ solution to your problem here, and your commentary on their solution.

1.2    Adding Up Odds

a)  Choose an odd number n, and add up all of the positive odd numbers less than or equal to n. What do you notice about the results that you get? Record your observations

b)  Use your observations to write a conjecture about the specific relationship between n and the outputs of the computations.

c)  Clearly prove your conjecture.

1.3    Divisibility

fIn this problem we’ll prove the following:

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

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

b)  Prove the theorem.

2    Windy Problems

ONLY SUBMIT 3 PROBLEMS FROM THIS SECTION

2.1    Pascal’s Triangle

Read how to draw Pascal’s Triangle.  (This means to read the first 2 paragraphs of the article, not to use every property in the article!) Then write down the first 10+ rows of the triangle for your own use.

a)  The outer diagonal of the triangle is all ones  (the  ‘dots’).   The second diagonal from the outside form the natural numbers (the ‘rectangular numbers’).  What about the third diagonal?  Prove that this sequence is exactly the triangular numbers T1 , T2 , . . . , T6 :  these are the numbers that form a triangular array of dots (image is from www.byjus.com).

b)  Prove that the fourth diagonal sequence is a the sequence of tetrahedral numbers, whose dots form pyramids with a triangular base (image from javatpoint.com).十

2.2    Mersenne Primes

The French monk Marin Mersenne lived at the same time as Fermat and corresponded with him.  In the search for primes he suggested considering numbers of the form

Mn  = 2n - 1.

a)  Find the first 10 Mersenne numbers. Which ones are prime? Which ones are not prime?

b)  Make a conjecture about which Mersenne numbers are prime and which ones are not prime based on your work in (a).

c)  Compute the products of the form

(2n + 1)(2n - 1)

for small natural numbers n. What do these products have to do with Mersenne primes? Use this to characterize as many Mersenne numbers as you can.  Does this support your initial conjecture? Why or why not? Modify it if necessary.

d)  The thirteenth, seventeenth, and nineteenth Mersenne numbers are all prime. Does this support your initial conjecture? Why or why not? Modify it if necessary.

e) Is the eleventh Mersenne number, M11  = 211  - 1 = 2047 prime?  What does this tell you about your conjecture?

f) It is said that Euler “noticed” that the Mersenne number M83  is not prime, but had 167 as a factor. This seems like a remarkable feat of genius.  But there’s a trick.  Notice that M83  = 283  - 1 and look at this number using modular arithmetic. Prove that

283 - 1 三 0   mod 167

by initially studying powers of 2   mod 167, and then breaking down the one above.What does it say about your initial conjecture? Prove this like Euler – without a calculator!! How many digits does M83 have?

2. Write a program (in whatever langauge you choose) that deciphers a text using a Vigenere cipher.

2.6    Pairing Up Twin Primes

a) What type of number will result from the following algorithm?  We call this the MULTIPLY-PAIR- THEN-REPEATEDLY-DIGIT-ADD algorithm.

INPUT: a pair of positive natural numbers

(i)  multiply the pair of numbers together

(ii)  add the digits of your result together.

(iii)  if you get a one-digit number, STOP. If you do not get a one-digit number, repeat step (ii).

b)  Go to oeis.org and search for ‘twin primes’ .   Apply the MULTIPLY-PAIR-THEN-REPEATEDLY- DIGIT-ADD algorithm to several pairs of twin primes less than 2000. As a result of your work, write down a clear conjecture.

c)  Prove your conjecture is true.

3    Gale Problems

ONLY SUBMIT 1 PROBLEM FROM THIS SECTION

3.1    Folding Paper Money

3.1.1    Folding Paper Money - Description

Consider folding an American paper bill (or an older Canadian bill, prior to the introduction of the plastic money).

Ultimately, we would like to fold it into N equally-sized lengths along the long end to create some pretty patterns. Let’s assume that A is odd. How can we do this?

Here’s a procedure that works for N = 11.  The problem is:  For what other numbers A does this procedure work?  Can you prove it?

1.  Fold the left-hand short end in a distance that you guess  is 1/N distance along the long edge; make a small pinch there.  (In the example:  guess 1/11 of the way along the long edge and make a pinch there.)

Notice that there is approximately 1 part of the bill before the pinch and approximately N - 1 (10 in the example) parts of the bill after the pinch.

2.  Divide the remaining N - 1 (10) part region in half with a pinch by bringing the right hand corner to the first pinch. The bill is now partitioned into 3 regions: a 1-part region, a (N - 1)/2 region, and another (N - 1)/2 region. In the example, there is a 1-part region, a 5-part region, and another 5-part region.

·  Considering the regions   to  the pinch that we just made, there is one 1 + (N - 1)/2 region, and

another (N - 1)/2 region

· In the example:  before the pinch that we just made, there is one 6-part region and one 5-part region.

3.  The folding procedure will continue by halving the even part.  So, in the example, we fold the left edge to the pinch mark that we just made and we make a mark defining a 3-part region and an 8-part region.

The table below shows how many regions the bill will be divided into as we continue on with the procedure with the N  =  11?.   For example, the 4th row means that in the 4th pinch the bill will have (approximately) a 7-part region on the left and a 4-part region on the right (where each part is

3.1.2    Folding Paper Money - The Problems

Let N be the number of parts you are dividing the bill into.

a)  Explain where each step of the table above comes from.

1.  Let A = 1/N bill lengths be the desired length of the first pinch from the left side of the bill, and let E be the error of the first pinch (so you want it to be A but it’s actually A + E).

Recall that the desired positions of the pinches are equally spaced, every A bill lengths.

Prove that the errors in subsequent pinches (that is, the distance between their desired positions) get smaller as the number of pinches gets larger.

Therefore, when N = 11, you end up with an improved estimate for 1/11.

b)  Does this procedure always give an improved estimate for a 1/N pinch?  (That is, does it always give an improved estimate for the first pinch?)

We say that the procedure‘works’ when it gives an improved estimate for then 1/N pinch. Give a couple of N where it doesn’t work and at least one additional N where it does.

c)  From the improved estimate pinch in the case where N = 11, you can follow the pinching procedure again except with full folds.  This will give you a bill that is divided into N  (approximately) even pieces. You can imagine that this can be used in many paper arts!

We say that this procedure ‘works’ when

Use induction to prove that the procedure works if and only if the N is a reptend prime in base 2.

·  a reptend prime is a number N such that taking the powers 2k  where k varies from 0 to N - 2

produces the numbers 1 to N - 1, modulo N .

3.2    Her Favourite Dress

3.2.1    The Set-Up

This is a legend from Hollywood’s Golden Age of the 1940s.  It concerns Actor Hedy Lamarr, called one of the greatest actresses in the history of Hollywood who also happened to produce her own movies (in an age where this was unheard of for women) and to develop radio-guidance systems and frequency-hopping technology for WWII whose principles are incorporated into GPS technology.

Hedy was always looking for ways to put games into her everyday work. Every time she had a public appearance coming up, she would be sent several dress choices from all of the known and upcoming dress designers around town.  Instead of choosing a dress by trying on each one, she made a game out of it.

First, the number of dresses being considered would be counted and they would be hung on a circular clothing rack. Then, a second number, the “throw away number” was chosen by Hedy. A starting dress was decided upon, and the dress choosing game began.

An assistant counted the dresses one-by-one:  “1, 2, 3, 4...  ” up to the throw away number. When that dress was reached, it was discarded and taken off of the rack. Then the assistant went on to the next dress, starting over at 1:  “1, 2, 3,...  ” up to the throw away number.  When the throw away number was reached again, that dress was discarded.

This process went on and on until there was just one dress left. This is the dress that Hedy would wear. See the picture below for an illustration with 10 dresses and throw-away number 5. The counted numbers are on the inside; the first ones read are in black and the second are in pink.

3.2.2    The Questions

Let d be the total number of dresses and t be the throw away number.  If we number the dresses at the beginning of the game (as with the red numbers on the dresses), let C(d, t) be the number of the chosen dress at the end. That is, C(d, t) is the one that is not thrown out.

a)  Name at least 2 situations when Hedy might want to control the game by being able to predict which dress is chosen at the end. What type of information would she need and what type of problem would she need to solve in order to be able to predict in order to take control?

b)  Prove that

C(d, t) = C(d - 1, t) + t   mod d.

(Hint:  You don’t need to go very far to prove this .  Look at the first throw away in the case of d dresses and a throw- away number of t and remember that you are working modulo d in this statement.  I suggest playing around with different expressions for the numbered labels of the dresses .)

c)  The previous part relates the problem to the case where there are fewer dresses.  Now, we are going to look at the case where there is a small throw-away number:  actually, the smallest possible throw away number, 2. In this special case , we actually have a closed-form expression for the chosen dress’s number:

C(d,2) = 2k + 1

where d = 2a  + k for a > 0, 0 < k < 2a .|    (Direction:   To  make  your proof clear you should use  two separate proofs  by induction  to prove  this .  First  assume  that k = 0 and do  a proof by induction  and then do  a second proof by induction to  complete the argument.  )

It turns out that this problem has strong connections to both modular arithmetic and induction.

A    Alberti Writing

From Alberti,  Leon Battista,  A  Treatise  on  Ciphers,  trans.   A.  Zaccagnini.   Foreword by David Kahn, Galimberti, Torino 1997.

Chapter XIV. I will first describe the movable index.  Suppose that we agreed to use the letter k as an index letter in the movable disk.  At the moment of writing I will position the two disks of the formula as I wish, for example juxtaposing the index letter to capital B, with all other small letters corresponding to the capital letters above them.  When writing to you, I will first write a capital B that corresponds to the index k in the formula.  This means that if you want to read my message you must use the identical formula you have with you, turning the movable disk until the letter B corresponds to the index k.  Thus all small letters in the ciphertext will receive the meaning and sound of those above them in the stationary disk. When I have written three or four words I will change the position of the index in our formula, turning the disk until, say, the index k is under capital R. Then I will write a capital R in my message and from this point onward the small k will no longer mean B but R, and the letters that follow in the text, will receive new meanings from the capital letters above them in the stationary disk.  When you read the message you have received, you will be advised by the capital letter, which you know is only used as a signal, that from this moment the position of the movable disk and of the index has been changed. Hence, you will also place the index under that capital letter, and in this way you will be able to read and understand the text very easily.  The four letters in the movable disk facing the four numbered cells of the outer ring will not have, so to speak, any meaning by themselves and may be inserted as nulls within the text.  However, if used in groups or repeated, they will be of great advantage, as I will explain later on.

Chapter XV. We can also choose the index letter among the capital letters and agree between us which of them will be the index. Let us suppose we chose the letter B as an index. The first letter to appear in the message will be a small one at will, say q. Hence, turning the movable disk in the formula you will place this letter under the capital B that serves as an index.  It follows that q will take the sound and meaning of B. For the other letters we will continue writing in the manner described earlier for the movable index. When it is necessary to change the set up of the disks in the formula, then I will insert one, and no more, of the numeral letters into the message, that is to say one of the letters of the small disk facing the numbers which corresponds to, let’s say, 3 or 4, etc. Turning the movable disk I will juxtapose this letter to the agreed upon index B and, successively, as required by the logic of writing, I will continue giving the value of the capitals to the small letters.  To further confuse the scrutinizers you can also agree with your correspondent that the capital letters intermingled in the message have the function of nulls and must be disregarded, or you may resort to similar conventions, which are not worth recalling.  Thus changing the position of the index by rotating the movable disk, one will be able to express the phonetic and semantic value of each capital letter by means of twenty-four different alphabetic characters, whereas each small letter can correspond to any capital letter or to any of the four numbers in the alphabet of the stationary disk.  Now I come to the convenient use of the numbers, which is admirable.