## Thursday, December 09, 2010

### 46 free lunches!

(CONGRADS to all the new ACM fellows. Among them are theorists Jennifer Chayes, Anne Condon, Phil Klein, S. Muthu, and Dan Spielman.)

In my post about mentoring High School Students I noted that for every $1000 my HS mentees win in math and science research competitions I get a free lunch. Two of my students, James Pinkerton and Rafael Setra entered the Team Siemens Competition and won$23,000 each! (The article says $20,000 but James and Rafael tell me it's$23,000.) Looks like I will be eating well for a while. If you visit UMCP and they are free for lunch with us then you can have a free lunch from them.
1. Here is the announcement of the winners. They came in third place in the team category.
2. Their project was on DUPLICATOR SPOILER games. (Like most games defined in math papers this game is not fun.) Recall that these games provide a way to prove certain properties are not expressible in certain languages (e.g., well-foundness for linear orderings is not first-order expressible). These games go for a FINITE number of moves that is specified before the game begins. They looked at these games when the number of moves can be an ordinal. Here is how it works: (1) at the beginning of the game there is a counter that has in the ordinal &alpha, and (2) after SPOILER makes his move he decrments the counter to some ordinal &beta < &alpha of his choice. Here is one result: for any ordinal &alpha there exists two linear orderings L1 and L2 such that if the game is played with these two orderings and both DUPLICATOR and SPOILER play perfectly then SPOILER wins the game in exactly &alpha moves. This is not just an existence proof- they actually say what the orderings are. They are natural in that they were not constructed just for the purpose of having this property.
3. Here is their paper.
4. The money actually goes towards tuition and other college-related expenses.
5. What is the secret of mine or their success? There are two things that are needed here (this applies to ugrad projects, Masters Thesis, PhD thesis, and, if properly generalized, to life):
1. Student that are hard working, intelligent, and care about the material. (James actually thinks Dup-SPOILER games are fun!)
2. A project that is doable.
6. Note that if a project doesn't go very far it might be that the PROJECT wasn't good or that the STUDENTS weren't good. This happens quite a bit, though ALWAYS something can be salvaged for a high school project.
7. I usually get to re-use projects since some students don't do a good job or give up. This was the FIRST TIME I had done the DUP-SPOILER GAMES WITH ORDINAL NUMBER OF MOVES project. Now, alas, I can't use it again.

#### 2 comments:

1. Great news - as someone who has benefited from free lunches provided by GASARCH and associates, I am happy to hear that others will get the same treatment again soon.

2. Congrats all around!