Math 165: Mathematics Seminar for Freshmen

Problems from the course

One requirement to pass the course is that you correctly complete at least 5 of the assigned problems, and submit them by the last day of the course (Th., Dec. 2). When submitting problems, label them by the topic and number, e.g., the first problem below should be called "Knot Theory-1" on your paper.

We will maintain a list of these problems here for easy reference.

Week 1: (8/26) Knot Theory

1. Show that there are no knots with only 2 crossings; i.e., show that if a knot diagram has only 2 crossings, that it is equivalent to the unknot.




2. Using rope, calculate the ropelength of the following 4 knots: the trefoil knot, the figure 8 knot, 5₁, 5₂.
   To do this: tie the appropriate knot with the rope and try to make it as small as possible; connect the two 'ends' and cut away any excess (or mark where the ends would meet. Now calculate the length of the rope you needed to do this. Ropelength is defined as the scale-invariant ratio of the length divided by the radius of the rope. (n.b., the radius of the rope provided in class on 8/26 is 3/32".)

Week 2: (9/02) Congruences

1. Compute 3^90 (mod 91) using the squaring method presented in class.




2. (a) Show that if x is even, then x^2 = 0 (mod 4). Show that if x is odd, then x^2 = 1 (mod 4).
   (b) Use this to show that if x and y are integers, x^2 - y^2 can never be congruent to 2 (mod 4).
   (c) Show that if n is not congruent to 2 (mod 4), then there are integers x and y with x^2 - y^2 = n.
   [Hint: Consider two cases, n is odd, and n is a multiple of 4].

Week 3: (9/09) Primes & Internet Security

1. Find a new prime number with at least 7500 digits.

   • To do this, download the program "Proth" available here.
   • When you run the program go to the "Form" menu, and change the form to "k*2^n + 1".
   • Pick a single value of n creatively between 24915 and 32700 and enter this in the two boxes at the top of the program.
   • Pick a range of k values [you probably need about 20000 values], and hit "Start". The program will run and test each number for some small prime factors before performing a deterministic primality test.
   • When it finds a prime number (which may take a while), it will write it to the screen and double-check it. Write it down and turn it in! [Try to pick n and the range of k creatively so you don't have the same prime number as another student.]

2. Send an enrypted message to Dr. Rouse.

   • Go to http://islab.oregonstate.edu/koc/ece575/02Project/Mor/.
   • Open the file n.txt, and copy and paste the number into the n box in the Java applet. When you copy the value of n into the box, make sure there aren't any spaces or line breaks around the number, even at the end.
   • Enter 50051 in the box for e.
   • Erase "Plain text message" and type the message you want to encrypt.
   • Press the "Convert to Number" button.
   • Press the "Encrypt" button.
   • Copy the number in the botton box (the one that use to contain the phrase "Encoded numerical message") into an e-mail and send it to Dr. Rouse. If nothing happens when you press the "Encrypt" button, then there are probably spaces or line breaks around the number n.

Week 4: (9/16) Platonic Solids

The first 3 problems appeared on the in-class worksheet; the fourth is on the slides. There are 2 other problems.

1. Construct, ideally using better materials than toothpicks and candy, a dodecahedron and an icosahedron. (You may work in pairs on this one.)

2. At the end of the worksheet, we defined the dual of a Platonic solid. What is the dual of the dual of a Platonic solid? How does it compare in size with the original solid? What if you take the dual of the dual of it (i.e., four iterations of duals)? Draw pictures of this for a tetrahedron, and a cube.

3. (a) Referring to the worksheet table (from section 10), describe how the cases $m=2$ and $n=2$ represent polygons which tile the sphere. ( hint: one of them represent bi-gons, and the other is dual to bi-gons.) Can you draw pictures?
   (b) Explain how duality is expressed in the table.

4. (a) Show that the Euler characteristic of a double-torus (a surface with two holes) is χ = -2.
   (b) Show that the Euler characteristic of a triple-torus (a surface with three holes) is χ = -4.
   (c) Show that the Euler characteristic of a g-holed torus (a surface with g holes) is χ = 2-2g.

5. Explore Archimedean solids, such as a soccer ball. Are there finitely many of these or infinitely many? At a minimum, list them, with pictures and state (a) which polygons comprise the solid's faces; (b) how many of each polygon are needed.

6. Phizz unit -- to be added later.

Week 5: (9/23) Graph Theory

1. Play the online game Planarity, at www.planarity.net. The goal of the game is to rearrange a graph so that it forms a planar graph, i.e., no edges cross (except at vertices). To earn credit, you must complete levels 1-5. To demonstrate your levels, you should right-click on the screen (before you check your answer) and print your solution for each of levels 3, 4, and 5. [You may print these on paper or print them as pdf's and email to Dr. Parsley.]

2. Prove that, if you take any six people randomly at a party, that either there exists a group of three people who all know each other or there exists a group of three people who all don't know each other.
   To do this problem, draw 6 vertices, one for each person. Draw a green edge between any two people who know each other and a red edge between any two people who don't know each other. (So every possible edge of will be drawn in either red or green.) Argue why you must either have drawn a red triangle or have drawn a green triangle.

3. Show that if n people attend a party and some shake hands with others (but not with themselves), then at the end, there are at least two people who have shaken hands with the same number of people.

Week 6: (9/30) Benford's Law

A nice pdf of the problems is here.

1. 1. Show that the probability that a number starts with either 10,11, 12, 13, or 14 is the same as the probability that it starts with a 2.

2. (a) Draw the interval [0, 3] and mark the points log(2^k) for 1 ≤k ≤ 9.
   (b) If x is a real number, let ⌊x⌋ denote the result of rounding x down to a whole number. For example, ⌊Pi⌋ = 3, and⌊0.99999⌋ = 0. Show that if n is any integer, there are exactly⌊ n log(2)⌋ values of k, 1 ≤ k ≤ n, so that 2^k begins with a 1.




Week 7: (10/7) Hyperbolic Geometry

1. Find out a little about how M.C. Escher utilized hyperbolic geometry in his art. Pick one artwork and write 1-2 paragraphs describing the mathematics behind his approach.

Week 8: (10/14) Conway's Soldiers

1. Get a piece 4 squares above the line. Indicate the initial starting configuration and at each step show which piece moves where.

2. Read the webpage http://www.chiark.greenend.org.uk/~sgtatham/solarmy/ and summarize their argument that the 5th square can be reached with an infinite number of moves. Comment on whether or not you think their formulation of the problem is reasonable (in particular, whether the move sequence they call a "whoosh" is valid).

Week 9: (10/21) Permutations, Parity, Puzzles

1. Solve the 15-puzzle in 200 or fewer moves.*

2. Read the solution to the M₁₂ puzzle and then solve it.*

3. Learn to solve a 4x4x4 Rubik's Cube (sometimes called a Revenge Cube). You can borrow a physical one from a friend (if you know anyone who has one) and learn to solve it, or you can use the CubeTwister program. When you can solve it, come to Jeremy Rouse's office hours and show him.

* For problems 1 and 2, get a picture of the solved puzzle (and the move count for the 15 puzzle) and submit to Jeremy Rouse. You can use the PrintScreen button ("PrtSc") to copy your current screen to the clipboard on your Thinkpad and then paste that into a Word or other file.


Week 10: (10/28) Mathematics of Voting

1. Examine the recent NC election for Court of Appeals in which a variant of instant runoff voting was utilized.

   • How many candidates were running? What percentage of the first-place votes did each one receive? Who 'advanced' to the runoff in this race?
   • Describe the process NC used to elect a judge in this race. Compare and contrast it with true instant-runoff voting.
   • Do you believe the outcome would be different if NC used a pure form of IRV? Would voters want to rank all 13 judges in order? What if they still only had to rank 3 judges?

2. Pick a team ranked in the AP basketball poll (other than Duke). Go to pollspeak.com or some other site that lists how each sportswriter in the AP voted that week. Compute the points each voter gave to your chosen team, and sum them. You should get the total points received, as reported by the poll.

3. Describe the process by which the Heisman Trophy is awarded (to the best college football player). Focus more on the process, but explain the results from 1956 and 2007 in detail.

4. Problem 4 concerns kids voting for their desserts. You have to determine the winner using different systems. If fully correct, this is worth 2 problems, since it's a little lengthy.

5. Problem 5 concerns choosing a movie.

6. Problem 6 is a follow-up to the previous problem. It shows how you can lie and change the outcome of an election under IRV.




Week 11: (11/04) Levels of Infinity

1. Show that the following sets are countable:

   • O = {1,3,5,7,9, 11, ... }, the odd natural numbers
   • EZ = { ... , -6, -4, -2, 0, 2, 4, 6, ... }, the even integers
   • M = {2,3,4,5,6, ... }$, all the natural numbers bigger than a
   In each case, come up with an explicit formula for the bijection mapping N (the natural numbers) to the set in question.

2. The Hilbert Hotel is a 5-star luxury hotel with one room for each natural number. Suppose on a busy night, every room is occupied. A traveler arrives late in the evening, and the manager, who's a mathematician, finds a way to give her one of the rooms without forcing any guests to leave the hotel. Describe how the manager could do this. (Some guests may have to change rooms, but no one is forced to share a room.)

3. Hilbert's Hotel again That same night, all of the presenters at the Infinitely-Long Awards Show descend on the Hilbert Hotel and need rooms. There are as many presenters as natural numbers. Describe how our intrepid hotel manager could accommodate all of the presenters in rooms, without forcing anyone to leave. (Some guests may have to change rooms, but no one is forced to share a room.)




Week 12: (11/11) Chaos and Fractals

1. Find another baby Mandelbrot set. Do this as follows:

   • Download the program ChaosPro (available from http://www.chaospro.de/)
   • Install and run the program
   • Select the Mandelbrot fractal (go to file, select fractal, select Escape Time)
   • Double-click somewhere on the fractal to zoom in.
   • When you have a baby Mandelbrot set on the screen, save the picture and e-mail it to Dr. Rouse.

2. Take the equilateral triangle handed out in class (or print/construct a large one yourself.) Play the `chaos game' as follows; you'll need a ruler and dice.

   • Label the vertices of the triangle 1,2,3.
   • Pick a point at random on the triangle.
   • Roll a 6-sided dice. If you roll a 1 or 4, move halfway towards vertex 1. If you roll a 2 or 5, move halfway towards vertex 2. If you roll a 3 or 6, move halfway towards vertex 3.
   • Roll again, using the point you landed on.
   • Mark your first 10 moves in pencil.
   • Mark your next 50-100 moves in pen.
   • Your pen marks should approximately draw the Sierpinksi triangle.



Week 13: (11/18) Algebra and Geometry

1. Use GeoGebra to construct a regular pentagon. You may NOT use the regular polygon tool, but you may use that cos(2 Pi/5) = (sqrt(5) - 1)/4. E-mail or turn in a picture of your pentagon, as well as the sequence of moves you used to make it. [You may work with other students (say groups of 2) on this, but please don't look up solutions online].

2. Use GeoGebra to construct a regular 17-gon. E-mail or turn in a picture. Instructions are available in this PDF file.




Week 14: (12/02) 7 Million Dollar Problems

Solve any of the 7 problems. (ha!) Not only will this satisfy your math 165 requirement, but you will become rich and famous.