- Jimmy Carter (President 1976-1980, lost re-election) was trained as a Nuclear Engineer, so he knew some math a long time before becoming president. (I do not know if he ever actually had a job as an Engineer.) I doubt he knew much when he was president.
- Herbert Hoover (President 1928-1932, lost re-election) was a Mining Engineer and actually did it for a while and was a success. Even so, I doubt he know much when he was president.
- James Garfield (President 1881-1881, he was assassinated) Had a classical education and came up with a new proof of the Pythagorean Theorem
- Thomas Jefferson (President 1801-1809) had a classical education and is regarded by historians as being a brilliant man. He invented a Crypto system in 1795. Note that this is only 6 years before becoming president, so he surely knew some math when he was president.
- Misc: Lyndon B. Johnson was a high school math teacher, Ulysses S. Grant wanted to me one but became president instead. George Washington was a surveyor which needs some math. Many of the early presidents had classical educations which would include Euclid. And lastly, Warren G. Harding got an early draft of Van Der Waerden's theorem, conjectured the polynomial VDW, but was only able to proof the quadratic case (not surprising—he is known as one of our dumber presidents).
Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
Monday, December 31, 2007
Presidential Math
Thursday, December 27, 2007
Oral Homework
- The students are in groups of 3 or 4. The groups are self-selected and permanent (with some minor changes if need be).
- The groups do the HW together.
- They are allowed to use the web, other students, me, other profs.
- The HW is not handed in–they get an Oral Exam on it.
- The HW is usually "read this paper and explain this proof to me."
- Savitch's theorem and Immerman-Szelepcsenyi Theorem.
- Show that VC and HAM are NPC.
- E(X+Y)=E(X)+E(Y), Markov, Chebyshev, Chernoff
- Reg Exp with squaring NOT in P.
- Matrix Group Problem in AM. (Babai's paper "Trading Group Theory for Randomness").
- The students learned ALOT by doing this. They learned the material in the paper, they learned how to read a paper, and they learned how to work together. (Will all of these lessons stick?)
- Some proofs are better done on your own than having a professor tell you them (HAM cycle NPC comes to mind). This is a way to make them learn those theorems without me having to teach it.
- Some theorems are needed for the course, but are not really part of the course (Chernoff Bounds come to mind). The Oral HW makes them learn that.
- This was a graduate course in theory so the students were interested and not too far apart in ability. This would NOT work in an ugrad course if either of those were false.
- This course only had 19 students in it, so was easy enough to administer.
Monday, December 24, 2007
The Twelve Days of Tenure
12 people asking her questions in her office, 11 times taught Intro Programming, 10 journal articles, 9 pieces of software, 8 book chapters, 7 invited panels, 6 submitted articles, 5 mil-lion bucks!, 4 invited talks, 3 students, 2 post-docs, and a degree from MIT. |
NOTE: The 12 days of Christmas is (easily) the most satirized song ever. I used to maintain a website of satires of it here but it was too hard to keep up? Why? Because anyone can write one. I wrote the one above in about 10 minutes during a faculty meeting to decide someone's Tenure case.
Friday, December 21, 2007
A Bad Deal
I don't usually watch Deal/No Deal. I like some of the interesting math or dilemmas it brings up, but the show itself is monotonous. As Host Howie Mandel himself says "we don't ask you a bunch of trivia questions, we just ask you one question: DEAL or NO DEAL!" Here is a scenario I saw recently where I thought the contestant made the obviously wrong choice.
- There are two numbers left on the board: $1000 and $200,000.
- She is offered a $110,000 deal.
- She has mentioned that $110,000 is about 5 times her salary (so this amount of money would make a huge difference in her life).
- Usually in this show you have the audience yelling `NO DEAL! NO DEAL!' This time the audience, including her mother, her sister, and some friends, were yelling `TAKE THE DEAL! TAKE THE DEAL!'. While this is not a reason to take the deal, note that the decision to say NO DEAL is NOT a `caught up in the moment' sort of thing.
- If she takes the deal, the worst case is that she gets $110,00 instead of $200,000.
- If she rejects the deal, the worst case is that she gets $1000 instead of $110,000.
Wednesday, December 19, 2007
More on VDW over the Reals
I had claimed that the proof that if you 2-color R you get a monochromatic 3-AP USED properties of R- notably that the midpoint of two elements of R is an element of R. Someone named ANONYMOUS (who would have impressed me if I knew who she was) left a comment pointed out that the proof works over N as well. THIS IS CORRECT:
If you 2-color {1,...,9} then there will be a mono 3-AP. Just look at {3,5,7}. Two of them are the same color.
- If 3,5 are RED then either 1 is RED and we're done, 4 is RED and we're done, or 7 is RED and we're done, or 1,4,7 are all BLUE and we're done.
- If 5,7 are RED then either 3 is RED and we're done, or 6 is RED and we're done, or 9 is RED and we're done, or 3,6,9 are all BLUE, and we're done.
- If 3,7 are RED then either 1 is RED and we're done, or 5 is RED and we're done, or 9 is RED and we're done, or 1,5,9 are BLUE and we're done.
- More Interesting: If VDWr is proven true using analysis or logic, then we get a NEW proof of VDW!
- Less Interesting: Since it is unlikely to get a new proof of VDW, it is unlikely that there is a proof of VDWr using analysis.
Monday, December 17, 2007
Bad News for American Science Funding/Good News for Australia Science Funding
Good news for Australian Science Funding: click here
Friday, December 14, 2007
Complexity Theory Class Drinking Game
Complexity Theory Class Drinking Game
- Whenever a complexity class is defined that has zero natural problems in it, take one drink.
- Whenever a class is defined that has one natural problem in it, take two drinks.
- Whenever you are asked to vote on whether or not a problem is natural, take three drinks.
- Whenever a mistake is made that can be corrected during that class, take one drink.
- Whenever a mistake is made that can be corrected during the next class, take two drinks.
- Whenever a mistake is made that cannot be corrected because it's just wrong, take three drinks.
- Whenever a probability is amplified, refill your cups since a class with zero or one natural problems in it is on its way.
- Whenever the instructor says that a theorem has an application, take a drink.
- Whenever the instructor says that a theorem has an application, and it actually does, take two drinks.
- Whenever the instructor says that a theorem has an application outside of theory, take two drinks.
- Whenever the instructor says that a theorem has an application outside of theory, and it really does, take four drinks.
Monday, December 10, 2007
An ill define question inspired by that HS question
Each point in the plane is colored either red or green. Let ABC be a fixed triangle. Prove that there is a triangle DEF in the plane such that DEF is similar to ABC and the vertices of DEF all have the same color.The answers to all of the problems on the exam are posted See here for the webpage for the competition. The problem above is problem 5.
One of the key observations needed to solve the problem is the following theorem:
If the reals are 2-colored then there exists 3 points that are the same color that are equally spaced.
Before you can say `VDW theorem!' or `Roth's Theorem!' or `Szemeredi's theorem for k=3 !' realize that this was an exam for High School Students who would not know such thing. And indeed there is an easier proof that a HS student could (and in fact some did) use:
Let a,b both be RED. If (a+b)/2 is RED then a,(a+b)/2,b works. If 2b-a is RED then a,b,2b-a works. If 2a-b is RED then 2a-b,a,b works. IF none of these hold then 2a-b,(a+b)/2,2b-a are all BLUE and that works.By VDW the following, which we denote VDWR, is true by just restricting the coloring to N:
VDWR: For any k,c, for any c-coloring of R (yes R) there exists a monochromatic arithmetic progression of length k.
This raises the following ill-defined question:
Is there a proof of VDWR that is EASIER than using VDW's theorem. Or at least different- perhaps using properties of the reals (the case of c=2, k=3 used that the midpoint of two reals is always a real).
Friday, December 07, 2007
Funny Answers on a Math Olympiad (MD)
Each point in the plane is colored either red or green. Let ABC be a fixed triangle. Prove that there is a triangle DEF in the plane such that DEF is similar to ABC and the vertices of DEF all have the same color.I think I was assigned to grade it since it looks like the kind of problem I would make up, even though I didn't. It was problem 5 (out of 5) and hence it was what we thought was the hardest problem. About 100 people tried it, and less than 5 got it right, and less than 10 got partial credit (and they didn't get much).
I got two funny answers:
All the vertices are red because I can make them whatever color I want. I can also write at a 30 degree angle to the bottom of this paper if thats what I feel like doing at the moment. Just like 2+2=5 if thats what my math teacher says. Math is pretty subjective anyway. (NOTE- this was written at a 30 degree angle.)
I like to think that we live in a world where points are not judged by their color, but by the content of their character. Color should be irrelevant in the the plane. To prove that there exists a group of points where only one color is acceptable is a reprehensible act of bigotry and discrimination.Were they serious? Hard to say, but I would guess the first one might have been but the second one was not.
Wednesday, December 05, 2007
Crypto problem inspired by politness
My mother-in-law Margie and her sister Posy had the following conversation:
POSY: Let me treat the lunch.
MARGIE: No, we should pay half.
POSY: No, I want to treat.
MARGIE: No, I insist.
This went on for quite a while. The question is NOT how to avoid infinite loops- my solution to that is easy- if someone offers to treat, I say YES and if someone offers to pay 1/2 I say YES, not because I'm cheap, but to avoid infinite loops.
Here is the question. It is not clear if Posy really wanted to treat lunch, or is just being polite. Its not clear if Margie really wants to pay half or is just being polite. SO, is their some protocol where the probability of both getting they DO NOT WANT is small (or both getting what they want is large), and the other one does not find out what they really want. Here is an attempt which does not work.
- Margie has a coin. Margies coin is OFFER with prob p, and DO NOT OFFER with prob 1-p. If she really wants to make the offer to treat then p is large, else p is small. Could be p=3/4 or p=1/4 for examples.
- Posy has a similar coin.
- Margie flips, Posy Flips.
- If Margie's coin says OFFER, than make the offer. If not the don't.
- Same with Posy.
In solutions you may offer or point me to we can of course assume access to random coins, and that neither Posy nor Margie can factor or take discrete log.