2007 Math, Science, and Engineering Camp


What you learned from Dr. Dan (math)



Monday, June 4: Euler's Formula

What you learned: If you construct a polyhedron out of polygons, then you can count the number of faces, edges, and vertices.  No matter what polygons you use, no matter how you put them together, the number of faces, edges, and vertices always satisfies V - E + F = 2.  This is known as Euler's formula.  If you put polygons together in a form of a donut, and you do the same count, you will always get V - E + F = 0.  If you have a two-holed donut, then you get V - E + F = -2, and in general if "g" is the number of holes in your donut, the formula is V - E + F = 2-2g.  

Why we care: This formula links the concept of geometry (how things are constructed) to the concept of topology (how things are shaped).  The basic formula has been studied to death, and entire branches of (very high level) mathematics has sprung out from it.  The formulas allow us to describe the shape of objects we have difficulty visualizing, like, oh, the universe.

Extending the problem: It is possible to have an object where V - E + F = 1, or V - E + F is equal to any negative odd number.  If you look up objects called projective planes or klein bottles, then you can see what happens.  Unlike a cube or a pyramid, these objects do not have an inside and an outside.


Tuesday, June 5: Haar Wavelet Transform

What you learned: You learned how to do the Haar Wavelet Transform, and the Inverse Haar Wavelet Transform.  This is simply a construction that takes a list of numbers and replaces them with a new list on numbers.  The main aspect of this transform is that the new list consists of one number that represents the average, and the rest of the numbers represent differences focusing on various parts of the list.  As a result, lots of patterns and repetitions in the original list are listed as zeros or small numbers in the transformed list.

Why we care: Heh.  Wavelet transforms make it easy to analyze signals.  The shear and utter usefulness of these things have taken the math/engineering world by storm.  In particular, wavelets turned out to be extremely effective in compressing images, and they are currently used in JPEG pictures.  

Extending the problem: Again, heh.  The Haar wavelet is only one of, well, an infinite number of wavelets.  There are a dozen or so wavelets that are used in Real Life.  The Haar wavelet is the easiest one to describe, but it is also the least useful.  If you are willing to get more complicated, then you can have more features in your wavelet (for instance, better data compression).  And people have found many applications of these creatures: signal analysis, noise reduction, image comparison, compression.

Handouts:


Wednesday, June 6: Flipping a coin over email:

What you learned: We want to play a game similar to "flip the coin", only we want to play it over email.  And we want to play it when the two players don't trust anyone (including each other).  So: no third party helping out, no video emails, nothing.  The big difficulty: how to we design a game that both players know will be completely fair?

We did this by using a hard math problem: factoring big numbers.  If I take two really big prime numbers (say 200 digits each), multiply them together, and then tell the world what the 400-digit product is, no one on Earth can factor the number.  We used this fact to design a game of "flip the coin over email" that is completely fair.  

Why we care: Well, now we can play flip the coin over email!  More importantly, one of the world's most popular forms of cryptography, called the RSA code, depends on the fact that we cannot factor really big numbers.  So the principle behind our game is used every day as people send private information across the internet.

Extending the problem: First and foremost, if you find a way to factor really big numbers quickly, then you would destroy our game, as well as the RSA code, and you would make a lot of people really nervous.  While RSA is no longer offereing cash prizes for factoring big numbers, still if you find a way to do this factoring, you can name your salary at any university, or at the NSA.

There are many other "hard math problems" like factoring: problems that would take an enormous amount of time to solve ("enormous amount of time" means "until the end of the universe").  Most of these can be used for a "flip the coin" game.

It is possible to come up with "flip the coin" games that does not need these hard math problems.  Some of them are less "pure" than the game I gave you, but they still work.  

Finally, the math behind RSA is within the reach of most of you.  I don't think I can convey it in this camp, but I put some material about it down below.

Handouts:

And for RSA:


Thursday, June 7: Huffman Compression

What we learned: This is another compression method, known as "lossless" compression.  This is a compression method where we cannot lose any of our information: after compression, the file needs to be identical to the original.  We compare this to "lossy" compression, where we can change the file slightly if it will make the compression better.  Lossless compression is .zip, .rar, .gz.  Lossy compression is .jpg, .gif, .mp3, .mpg, .wav, etc.  Anything audio/video is a lossy compression.

Huffman compression is a means of lossless compression used in ZIP files.  It assigns shorter codes to characters that are used frequently, and it assings longer codes to characters that are not used much.  It then creates a tree that is used to interpret these codes.

Why we care: It makes files smaller.  That is a good thing.

Extending the problem: Gosh golly there are a bunch of compression methods out there.  You've only seen two out of hundreds.  Many compression methods are within your grasp.

Handouts:


Monday, June 11: P vs NP

What we learned: We looked at three different problems: Logical Expressions, Traveling Salesman Problem, and Bin Packing.  All three have two common properties:

1) As the problem gets larger (more letters in the logic problem, more cities in TSP, more items to pack in bins), the number of potential solutions grows outrageously.  Thus for a large-ish problem, finding the best solution by brute force (searching through all potential solutions) is not possible.

2) If we know the solution, the solution is easy to describe (for contrast: the answer to "Does the first player have an advantage in chess?" is not easy to describe).

Problems of this form are called NP problems (stands for nondeterministic polynomial).  Problems which have easy solutions to them are called P problems (stands for polynomial).  "Easy" means that we don't need to go through all the possible solutions to find our answer.  The question of the ages: Is there an easy solution to an NP problem.  In other words, are NP problems actually P problems?

The answer is almost certainly "no".  But no one knows for certain that this is the answer.  People have been trying to prove the answer yes or no for decades.  This problem, called P vs NP, has been deemed one of the premier unsolved math problems of our time, and the Clay Institute (which is tied into Harvard) has offered a $1,000,000 prize for its solution.  A list of the seven "Millennium Problems", including P vs NP, can be found here.

Why we care: There are many, many, many NP problems out there, and many of them apply to real-world situations, and a solution to these NP problems would save businesses billions of dollars.  And here is an amazing point: IF you find a solution to ANY of these NP problems, then its solution can be adapted to solve ALL of the NP solutions.  Thus you can solve thousands of problems in one try.  On the flip side, if you can show there is no easy solution for just one NP problem.

Extending the problem: Well, go and find an easy solution to an NP problem, get rich, and then give me a "Finder's Fee" for telling you about this problem.


June 12 and 13: Cryptpography

I'll have this up soon (as in June 15).



Thursday, June 14: Billiards

What you learned: Given a billiard table that is m units by n units, you can trace the path of a ball that is hit from one corner at a forty-five degree angle.  There are many questions you can ask about the path taken, and all of the answers depend on the dimensions of the table.

Why we care: Well, it's not really a million dollar question, is it?  The main reason why I find this interesting is that it gives you a geometric representation of two concepts from arithmetic: greatest common factor and least common multiple.  Both of these are instrumental in the structure of the path.  Math people love it when they can combine different fields in math (like Euler's formula above).

Extending the problem: We can change the shape of the billiard table.  Instead of being rectangular, it can be L-shaped, or it can have a hole in it.  Or we can have a 3-D billiard table, whose dimensions are m x n x p.  In any situation, the same questions can be asked.

Handouts:


June 6-14: Unsolved Problems

If you solve any of these, then remember me when you become a millionaire.

Factoring large numbers: Given a number, find a fast way to factor it.  Most people do not believe that it is possible, though no one knows for certain that it is not possible, and there is a bit of evidence out there that says it IS possible to factor big numbers.  Mathematicians have been working feverishly on this problem for the past thirty years, ever since RSA came about.

Twin Prime Conjecture: Twin primesare two primes that are only two apart from each other.  For example, 3 & 5, 11 & 13, 29 & 31, etc.  We know for a fact that there are an infinite number of primes.  The question is: is there an infinite number of twin primes.  Everyone believes that there is, but no one has a clue how to show it.  The largest known pair of twin primes has 57,811 digits.  This problem is thousands of years old.

P vs. NP: One of the mothers of all unsolved math problems.  Solve this and people will be talking about you centuries from now.  This is one of the seven Millennium Problems, so it has already been recognized as one of the greatest math problems of our time.  This problem is about thirty years old.

Goldbach Conjecture: Can every even number greater than 4 be written as the sum of two primes?  For example, 32 = 3 + 29, 102 = 5 + 97, etc.  Everyone believes this conjecture is true, but again, no one knows how to prove it.  It has been verified that every even number up to 300,000,000,000,000,000 can be written as the sum of two primes.  This problem is a mere 260 years old.

Collatz Conjecture: Start with any positive integer, and apply the following rule: if the number is even, divide by 2.  If the number is odd, then multiply by 3 and add 1.  Continue doing this rule over and over again.  For instance, if you start with 30, you get

30, 15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1

The conjecture states that no matter what integer you start with, you will always end up at the number 1.  This has been verified for all numbers up to 60,000,000,000,000,000.  This problem is a very simple example of a discrete dynamical system.  These are heavily used in all applications of mathematics, most notably physics and engineering.  The fact that we cannot answer this question about this very simple dynamical system is a slap in the face to the mathematical world.  It clearly shows that we do not understand enough about math, and that we need to do more research.  This problem is only 70 years old.

Cities and Roads Picture: The term 3-regular meant that there are EXACTLY three roads going in to each city.  A graph has a diameter of 3 if there are two cities for which you must use three roads to get from one city to the other, but there is no pair of cities where you must use more than three roads to connect.  The problem is: Can you draw a bunch of cities and roads that: 1) is 3-regular, 2) is 3-diameter (I do mean 3, even though I got confused in class), and 3) has more than 12 cities?  Can you draw one, or can you show that it is impossible to draw such a graph?

Handouts: