Thursday, September 21, 2017

Acronyms and PHP

Whenever I teach discrete math and use FML to mean Formula the students laugh since its a common acroynm for  Fuck My Life. Now they laugh, and I say I know why you are laughing, I know what it means  and they laugh even harder.

BUT it got me thinking: Pigeonhole Principle! There are more things we want short acroynms for then there are short acroynms. Below are some I thought of. I am sure there are others, in fact I am sure there are websites of such, but I wanted to see which ones I just happen to know.

AMS- American Math Society and much much more:see here

DOA-

Dead on Arrival

Department of Aging. Scary!

ERA-

Earned Run Average in Baseball,

Equal Rights Amendment in politics

PCP-

Phencyclidine, a drug that you should never take.

Prob. Checkable Proofs. Obscure to the pubic but not to us.

IRA- 

Irish Republic Army

Internal Retirement Account

Several companies have had rumors they fund terrorism because they were giving their employees IRA's. The headline `Company X funds IRA's' could be misunderstood.


SAT-

Standard Aptitute Test

Satisfiability (of Boolena Formulas) Obscure to the pubic but not to us. Actually it may get less obscure as more ``proofs'' resolving P vs NP come out.

SJW

Single Jewish Female (in classified ads- more on that later). I think SJF is more common.

Social Justice Warrior (sounds like a good thing but might not be)

Classified ads are a source of many acronyms which can be used to teach combinatorics.

{S,M,W,D,G}{B,C,H,J,W}{M,F}


S-single, M-married, W-widowed, D-Divorced, G-Gay (this one I've seen alone making me wonder
about S/M/W/D? I've also seen four-letter acronyms to disambiguate).

B- black, C-Christian, H-Hispanic,  J-Jewish, W-White.

M,F- Male, Female, though I am sure there are ways to say other genders.

Great for combinatorics! especially if you add in other ones (like BD)

WTF-

Wisconsin  Tourism Federation

You know what else it means so I won't say it (this is a G-rated blog). When I first saw it I thought `what the fuck?- how could they have screwed up so badly?'


TEACHING TOOL- when teaching PHP (Pigeon hole Principle, not the language PHP which stands for Hypertex PreProcessing, not quite in order, or Personal Home Page) you can use the the fact that

number of concepts GREATER THAN  number of 3-letter combos

leads to some 3-letter combos will be used more than once.

Monday, September 18, 2017

A problem I thought was interesting- now...

On Nate Silver's page he sometimes (might be once a week) has a column edited by Oliver Roeder of problems. Pretty much math problems though sometimes not quite.

Some are math problems that I have seen before (e.g., hat problems). I don't bother submitting since that would just be goofy. I would be  ringer.

Some are math problems that I have not seen before, I try to do, I fail, but read the answer and am enlightened. I call that a win.

But some are math problems that I have not seen before, I try to do, I fail, but when I see the solution its a computer simulation or something else that isn't quite as interesting as I had hoped.

I describe one of those now; however, I ask if it can be made more interesting.

The problems is from this column: here

I paraphrase:  Let A be the numbers {1,2,3,...,100}.  A sequence is nice if  (1) it begins with any number in A, (2) every number is from A and is either a factor of multiple of the number just before it, and (3) no number can appear more than once.  Find the LONGEST nice sequence

Example of a nice sequence: 

4, 12, 24, 6, 60, 30, 10, 100, 25, 5, 1, 97

I worked on it

1) By hand I came up with a nice sequence of length 42. This was FUN! You can either have fun trying to find a long nice sequence or you can look at mine here.

2) I tried to prove that it was optimal, hoping that either I would find its optimal or be guided to a longer sequence. Neither happened. More important is that this was NOT FUN.

3) I looked forward to the solution that would be in the next column and would be enlightening. 

4) The next column, which did have the solution, is here! The answer was a sequence of length 77 found by a program that also verified there was no longer sequence. The sequence itself was mildly enlightening in that I found some tricks I didn't know about, but the lack of a real lower bound proof was disappointing.

They mentioned that this is a longest path problem (Graph is {1,..,100} edges are between numbers that are either multiples of factors) and that such problems are NP-complete. That gave the impression that THIS problem is hard since its a case of an NP-complete problem. Thats not quite right- its possible that this type of graph has a quick solution.

But I would like YOU the readers to help me turn lemon into lemonade.

1) Is there a short proof that 77 is optimal?  Is there a short proof that (say) there is no sequence of length 83.  I picked 83 at random.  One can easily prove there is no sequence of length 100.

2) Is the following problem in P or NPC or if-NPC-then-bad-thing-happen:

Given (n,k) is there a nice sequence of {1,...,n} of length at least k. (n is in binary, k is in unary, so that the problem is in NP.)

I suspect not NPC.

3) Is the following problem in P or NPC or ...

Given a set of numbers A and a number k, is there a nice sequence of elements of A of length at least k (k in unary).

Might be NPC if one can code any graph into such a set.

Might be in P since the input has a long length.

4) Is the following solvable: given a puzzle in the Riddler, determine ahead of time if its going to be interesting? Clyde Kruskal and I have a way to solve this- every even numbered column I read the problem and the solution and tell him if its interesting, and he does the same for odd number columns.


Thursday, September 14, 2017

Random Storm Thoughts

It's Monday as I write this post from home. Atlanta, for the first time ever, is in a tropical storm warning. Georgia Tech is closed today and tomorrow. I'm just waiting for the power to go out. But whatever will happen here won't even count as a minor inconvenience compared to those in Houston, the Caribbean and Florida. Our hearts goes out to all those affected by these terrible storms.

Did global warming help make Harvey and Irma as dangerous as they became? Hard to believe we have an administration that won't even consider the question and keeps busy eliminating "climate change" from research papers. Here's a lengthy list cataloging Trump's war on science. 

Tesla temporarily upgraded to its Florida Owners' cars giving them an extra 30 miles of battery life. Glad they did this but it begs the question why Tesla restricted the battery life in the first place. Reminds of when in the 1970's you wanted a faster IBM computer, you paid more and an IBM technician would come and turn the appropriate screw. Competition prevents software-inhibitors to hardware. Who will be Tesla's competitors?

During all this turmoil the follow question by Elchanan Mossel had me oddly obsessed: Suppose you flip a six-sided die. What is the expected number of dice throws needed until you get a six given that all the throws ended up being even numbers? My intuition was wrong though when Tim Gowers falls into the same trap I don't feel so bad. I wrote a short Python program to convince me, and the program itself suggested a proof.

Updates on Thursday: I never did lose power though many other Georgia Tech faculty did. The New York Times also covered the Tesla update. 

Sunday, September 10, 2017

The Scarecrow's math being wrong was intentional

In 2009 I had a post about Movie mistakes (see here). One of them was the Scarecrow in The Wizard of Oz after he got a Diploma (AH- but not a brain) he said

The sum of the square roots of any two sides of an isoscles triangle is equal to the square root of the remaining side. Oh joy! Rapture! I have a brain!

I wrote that either this mistake was (1) a mistake, (2) on purpose and shows the Scarecrow really didn't gain any intelligence (or actually he was always smart, just not in math), or (3) It was Dorothy's dream so it Dorothy was not good at math.

Some of the comments claimed it was (2).  One of the comments said it was on the audio commentary.

We now have further proof AND a longer story: In the book Hollywood Science: The Next Generation, From Spaceships to Microchips (see here) they discuss the issue (page 90). The point to our blog as having discussed it (the first book not written by Lance or Lipton-Regan to mention our blog?) and then give evidence that YES it was intentional.

They got a hold of the original script. The Scarecrow originally had a longer even more incoherent speech that was so over the top that of course it was intentional. Here it is:

The sum of the square roots of any two sides of an isosceles triangle is equal to the square root of the remaining side: H-2-O Plus H-2-S-O-4 equals H-2-S-O-3 using pi-r-squared as a common denominator Oh rapture! What a brain!

While I am sure the point was that the Scarecrow was no smarter, I'm amused at the thought of Dorothy not knowing math or chemistry and jumbling them up in her dream.

Thursday, September 07, 2017

Statistics on my dead cat policy- is there a correlation?

When I teach a small (at most 40) students I often have the dead-cat policy for late HW:

HW is due on Tuesday. But there may be things that come up that don't quite merit a doctors note, for example your cat dying, but are legit for an extension. Rather than have me judge every case you ALL have an extension until Thursday, no questions asked. Realize of course that the hw is MORALLY due Tuesday. So if on Thursday you ask, for an extension I will deny it on the grounds that I already gave you one. So you are advised to not abuse the policy. For example, if you forget to bring your HW in on thursday I will not only NOT give the extension, but I will laugh at you.

(I thought I had blogged on this policy before but couldn't find the post.)

Policy PRO: Much less hassling with late HW and doctors notes and stuff

Policy CON: The students tend to THINK of Thursday as the due date.

Policy PRO: Every student did every HW.

Caveat: The students themselves tell me that they DO start the HW on Monday night, but if they can't quite finish it they have a few more days. This is OKAY by me.

I have always thought that there is NO correlation between the students who tend to hand in the HW on Thursday and those that do well in the class.  In the spring I had my TA keep track of this and do statistics on it.

The class was Formal Lang Theory (Reg Langs, P and NP, Computability. I also put in some communication complexity. I didn't do Context free grammars.)  There were 43 students in the class. We define a students morality (M) as the the number of HW they hand in on Tuesday. There were 9 HW.

3 students had M=0

12 students had M=1

9 students had M=2

5 students had M=3

4 students had M=4

4 students had M=5

1 student had M=6

1 student had M=7

2 students had M=8

2 students had M=9

We graphed grade vs morality (see  here)

The Pearson Correlation Coefficient is 0.51. So some linear

The p-value is 0.0003 which means the prob that there is NO correlation is very low.

My opinion:

1) The 5 students with M at least 7 all did very well in the course.This seems significant.

2) Aside from that there is not much correlation.

3) If I tell my next semesters class  ``people who handed the HW in on tuesday did well in the class so you should do the same'' that would not be quite right- do the good students hand thing in on time, or does handing things in on time make you a good student? I suspect the former.

4) Am I surprised that so many students had such low M scores? Not even a little.










Monday, September 04, 2017

Rules and Exceptions

As a mathematician nothing grates me more than the expression "The exception that proves the rule". Either we bake the exception into the rule (all primes are odd except two) or the exception in fact disproves the rule.

According to Wikipedia, "the exception that proves the rule" has a legitimate meaning, a sign that says "No parking 3-6 PM" suggests that parking is allowed at other times. Usually though I'm seeing the expression used when one tries to make a point and wants to dismiss evidence to the contrary. The argument says that if exceptions are rare that gives even more evidence that the rule is true. As in yesterday's New York Times
The illegal annexation of Crimea by Russian in 2014 might seem to prove us wrong. But the seizure of Crimea is the exception that proves the rule, precisely because of how rare conquests are today.
Another example might be the cold wave of 2014 which some say support the hypothesis of global warming because such cold waves are so rare these days.

How about the death of Joshua Brown, when his Tesla on autopilot crashed into a truck. Does this give evidence that self-driving cars are unsafe, or in fact they are quite safe because such deaths are quite rare? That's the main issue I have with "the exception that proves the rule", it allows two people to take the same fact to draw distinctly opposite conclusions.