The Life of a Dead Hamster

A cute problem

2011-09-13T11:19:00.001-04:00

Does there exist an algebraically closed field that is isomorphic to a proper subfield of itself?

The Best Chinese Food I've Had

2010-12-26T20:05:00.009-05:00

Comes from a restaurant called Grace Garden in Odenton, MD. I went there with family this Friday and had a great meal :). Of course, as with most Chinese restaurants, you have to go in a big group so you get lots of really good dishes.

Fish Noodles! How do they make fish into noodles? I really want to know.

Golden Shrimp. My cousin took two before I could get the picture :(

Crispy Eggplant: probably one of my favorite dishes that they have

Sichuan Triple Treasure: It's beef tongue, tripe, and intestines I think.

Braised Pork Belly: Always good

Pocket Tofu: It's so soft and has a really good flavor.

Some sort of green vegetable. Someone else can probably actually identify it.

Merry Day-After-Christmas!

Choices

2010-12-06T21:36:00.001-05:00

lead to decisions. And decisions are hard.

Too Hard

2010-11-24T16:03:00.000-05:00

Whoops, Tim already wrote a blog post with this same name. I'm using it anyway.

I was the problem czar for the Harvard-MIT November Tournament, which happened on Sunday, November 7, 2010. As problem czar, I was responsible for making sure that enough problems got written on time for the contest to run. That in itself was a huge task, made no easier by the relatively small amount of help that the February problem czars gave me. I personally wrote the majority of the test, with help from Travis in some key areas (he wrote many of the geometry problems), and from Jacob in not as key areas (he kept giving me problems about Bayesian inference...).

66 problems later, I get the (somewhat delayed) response from testsolvers: "Too Hard."

What is too hard?

Honestly I am probably too biased to comment, but I don't believe that it's possible for something to be too hard on its own. Being too hard can cause other issues, such as a lack of distinguishing power, but being too easy can also cause that. And I am fully aware of the issues that come from a test that lacks distinguishing power.

So when I see a complaint that something is too hard, what do I think? I feel that it is extremely more likely that some aspect of the undertaker is off rather than that the task is actually too hard. And it seems like others are the opposite -- they would much rather blame the test than the test takers, especially when they are the test taker.

Actually, I do that too. Lots of my blog posts last year were about things that I disagreed with in tests. Was it really the tests that were at fault or was it me? I think it was some of both. I don't think it's deniable that the HMMT calculus test was unable to distinguish between the top 4 competitors (hint: they tied), but at the same time it wasn't like the test gave them absolutely zero opportunity to distinguish themselves (the tie was at 28, not 50).

Regardless, I feel like there is this idea that if lots of people get two or fewer problems then the test is too hard. So, people say, make there be a few problems that everyone will get. But why? Now I've reduced my contest from 10 problems to 7. That doesn't seem useful at all.

I've rarely seen someone look at a test and say ``This is too easy,'' but many people will look at a test and say ``This is too hard.''

Linux iwlagn problems

2010-10-11T00:21:00.002-04:00

This isn't really a content-full post, but if any of you are trying to install linux on a new computer and are finding that your internet connection drops after a couple minutes and a bit of traffic, it was a really annoying problem for me that existed for essentially the entire life I've had this computer. I only found the solution a couple days ago.

Right now, the iwlagn driver does not have full support for 802.11n. In fact, having 802.11n enabled will oftentimes screw up your internet connection in a very strange way. You retain your IP address, everything says you're still connected, but no transmission is really happening. You might notice a drop in bitrate from the output of iwconfig, but setting it to be higher again doesn't fix the issue. The issue is 802.11n.

The fix is to initiate the module with the option 11n_disable=1 or 11n_disable50=1. I had to use the latter. I am not sure, but I think it depends on which version of the driver you have (iwl4965 vs iwl5000). So make sure that you are compiling the driver as a module (do not build it into the kernel) and the fix is below.

If you have already booted and want to fix the issue, run the following commands as root

rmmod iwlagn
modprobe iwlagn 11n_disable=1
(or modprobe iwlagn 11n_disable50=1)

If you want the module to be loaded properly on boot, edit the file /etc/modprobe.conf (on gentoo; on other distributions this file might be somewhere else) and append the following line:

options iwlagn 11n_disable=1
(or options iwlagn 11n_disable50=1)

You might also have to use both options. I had to use 11n_disable50 and not 11n_disable. Regardless, one of these two should work and leave you with a perfectly reliable wireless card (without n mode, though).

Hopefully I helped someone with this post! This is a really really difficult bug to google.

Contest Theory

2010-10-05T15:13:00.001-04:00

The IOI this year took a radically different approach to contest programming than the IOIs in the past. The Canadian Host Scientific Committee decided that it would be a good idea for the IOI to less favor the teams who have individuals who train very hard on standard algorithmic and data structure problems. I will put off judging whether that was a good or a bad decision until later in this post.

There is one fundamental aspect of writing a contest which is up for major contention and I don't believe that people pay enough attention to it. This is the question that you have to answer before you write a single problem for your test. That question is who should win.

Who should win? It seems like a simple question. The person who is best at math should win a math contest, the person who is best at skiing should win an Olympic medal for skiing. But these answers don't really tell you who should win. If I were to run a contest and I said that the winner would be the person who is best at life, nobody would take me seriously. Why? Because there are a relatively small number of things that would be on this contest. We wouldn't be able to determine the best sports player by just playing football, or just football and soccer, or any other (proper) subset of the sports in the world. And even if we were to play every sport in the world, I'd have to give an arbitrary weighting to each one. How do I compare two people if they have different strengths? It's simply not possible.

This problem arises at a lower level too. Let's look at football. Who is the best football player? I could say let's have a competition where everyone plays football. But this won't work. Maybe one player is a very strong quarterback and another is a very strong wide receiver, but only one of them gets their favored role. Well okay, let's have them pick their positions. We still have an issue. How are we supposed to compare someone's performance as a quarterback to another person's performance as a wide receiver?

Perhaps the answer is to have a quarterback competition, solely to determine who is the best quarterback. That is certainly a possible solution, but sometimes this will make the field too small. Say we object to a spelling competition because there are words from a plethora of sources, which some people will be better at than others. So we use our technique and say okay, we will have a spelling competition consisting of only English words of Sanskrit origin. How many people are specialists of such words? There are probably a few, but not enough to make a competition.

So we need some sort of compromise. We have to accept the fact that there are different specialties within whatever activity for which we hold a competition and that these are in some ways not comparable, but at the same time compare them somehow and determine a winner. It is for this reason that it is not the job of the contest to determine the best, but rather it is the job of the contest to determine the winner.

Of course, if there is a single best competitor, that person should win the competition. If one person is better than everyone else at every position in a football team, he would win a football competition. If your method of determining the winner didn't do that, then you have some problems. But this can be resolved by essentially any performance based scheme that uses positive weights on every event.

But in practically every case, there isn't a single dominating competitor, but rather several top competitors who all do well in different areas. So which one of them should win? It's up to the contest organizers to decide.

And this decision is often very debatable. Perhaps the most prominent example for me personally is the US IMO team selection. There is little argument to be made against the choice to favor those who will bring home the highest IMO scores. The argument stems from the fact that the US team leadership has seemingly decided that the most important subjects to be good at are algebra and geometry, casting aside combinatorics and, to a lesser extent, number theory. It's painful to look at the TST to see three geometry problems, graded in difficulty, so that it is almost certain that geometry skill will matter in team selection, in stark contrast with the single combinatorics problem, difficult enough that only Evan solved it (although I like to think I might have if I hadn't spent nearly all of my time on a geometry problem), clearly not mattering for team selection. The IMO claims to be a contest about all four main subject areas, but the US strategy says loud and clear that this is not the case.

Who is at fault? It's difficult to say. Maybe no one. Maybe everyone. It could be that the lack of combinatorics problems did not stem from a belief that combinatorics does not correlate to IMO score. It could be simply that there was not a sufficient supply of appropriate and interesting problems last year, so the TST was forced to be mostly comprised of the other subjects. But I'm not convinced that this was the case.

So now we return to IOI. The Canadians looked at the IOI and decided that they did not like the choice of winner that was made in the past. They didn't want someone who simply coded problems from online judges for the past year to have an easy road to victory. They wanted someone who could think about a problem which didn't have a standard complete answer and could still perform well.

So they changed the contest.

Gennady still won, of course. IOI might be a case where a dominating force actually exists. Regardless, the IOI change hurt my personal placement, but I can understand where it came from. The Canadians did well to explicate their goals, their means to reach those goals, and why those were their goals in the first place. I agree that the IOI had been reaching a less optimal position by simply escalating the difficulty of algorithmic problems, but I also think that the Canadians went too far in the other direction.

Next time you're involved in running a competition. Ask your group the question, ``Who do we want to win?''

MOP, ELMO, and thoughts on life

2010-07-10T04:07:00.002-04:00

Being a senior changes everything. Entering my fourth and final year as a student at MOP, I had been through everything: red once, blue once, black once (though this year they added a new green, which is the old red, and the new red is the USAJMO winners). Those three years I did everything in the most carefree manner I could. Tests weren't really important. Free time was for relaxing and making sure you don't burn out. Even the TST didn't seem like the biggest thing to worry about. There was always next year.

As a senior I went in to TST with an odd combination of emotions. I really wanted to be on the IMO team once, and this was my last chance, but at the same time I had been hoping to run the ELMO and then I later found out that it was traditional for a senior who did not make the team to run it. ``Okay fine, so I have a consolation prize if I don't make it.''

So I was putting pressure on myself to make the team, but at the same time I was trying to convince myself that it didn't really matter. I looked at the people with whom I was competing and realized that it wasn't a guarantee by any means, but I figured I had a good shot. I thought back to what I was told at Romania: ``Once you've already done well you have the confidence to do well again.'' I thought back to my performance at Romania. Better than I really could have asked for. I tried to be confident.

So I went into the TST room on the first day in an entirely confusing state. Pressured but confident but not really confident and darn blue MOPpers are taking the TST again and hmm I didn't do so well on TST last year and I really didn't spend enough time doing problems this year and also the USAMO didn't do much to get me back in practice and I'd be out of practice anyway and okay well I'm nervous except darn there's no adrenaline in my body. Yeah. It turns out that I do better on contests when I'm nervous and get an adrenaline rush.

TST was a flop. Day one went okay. I missed an inequality that plenty of other people got, but at the same time there weren't that many people ahead of me, and even they were only one problem ahead. Nothing insurmountable.

Day two went almost as badly as last year. You see there's an odd characteristic about geometry problems. You can make a lot of progress and not solve the problem. This is because geometric diagrams have a lot of structure in them. So when there's a geometry problem in the first problem slot, I end up working on it and not finding the solution. A little bit in, I think to myself, ``Hmm, I should probably stop working on this geometry problem and try the next problem which is not geometry.'' Within a minute, I'll find something new about the diagram that seems to be useful for the final angle chase in the solution and I think ``Okay, if this doesn't work I'll stop after five more minutes.'' This happened so many times during day two that I really didn't have a chance to look at the other problems. Yet at the end of the day, it went better than it did the year before. This year I spent 3.5 hours on a geometry problem and finished. Last year I did the same thing but didn't finish. 2010 defeats 2009 1-0.

So I went into day three at a rather large disadvantage. The way it had gone I basically needed all three problems on that final day to make the team. I sat down in Avery 106 at 8:00 for the third day in a row and turned over my paper to see a geometry problem as #7 and a binomial coefficient in a number theory number 9. I hate number theory problems about binomial coefficients (although, to be fair this one wasn't bad. I didn't really have a chance to work on it, though). So I killed number 8, then looked at 7 and didn't really get anywhere. When I turned in my papers I was pretty dejected. ``Ah well, no suspense for me.''

The thing is, nothing is ever completely free of suspense. Even when you're the most confident that you won, or the most sure that you didn't, there's a random worry or hope that keeps bugging you until the actual announcement. For that reason I didn't want to be in the blue room when the team got announced. It had nothing to do with who it would be. It was all that I didn't want to have to sit there while the annoying little voice inside of me would say, ``Maybe he'll ignore the TST score.''

Well, I didn't make the team but I did get to run the ELMO. The ELMO is a math olympiad put together by the returning MOPpers and taken by the first time MOPpers. I failed it massively when I was in red mop XD. The ELMO is always called the ELMO, but what the letters stand for is up to the organizers for that year. This year I decided to put as much of the decision making as possible into the hands of the team leaders, including the name and which shortlist problems would appear.

I had been looking forward to the ELMO for a long time and had written several problems before MOP. As soon as I could I posted a sign informing everyone of the first meeting and, following the tradition started last year, signed it Supreme Grand Ayatollah. I've realized in the last year that I enjoy writing contests a lot more than taking them, so I dived into my role as the head of ELMO with a lot of enthusiasm.

The first order of business when running a contest is to get as many problems as you can. It really doesn't matter whether the problems are extraordinarily good or not, since in a collection of 30 problems you'll probably have 6 that are good or can be made good. So I went about soliciting ELMO problems, ending up with 26 on the final shortlist (after the removal of some problems for various reasons). Of course, there were actually only very few sources for problems.

Name	Problems
Brian Hamrick	8.5
Evan O'Dorney	4
Carl Lian	3.5
Others (1 each)	9

Well, that's to be expected. One of the things I found out from this endeavor is that writing problems on command generally produces suboptimal results, similar to writing anything else. Inspiration doesn't come when you sit down and say ``Okay, I'm going to write a problem.'' It comes when it wants to, which makes writing large quantities quite difficult. In the end, only 1.5 of my problems made it onto the ELMO, although I think this was a result of almost all of them filling the same niche rather than problem quality.

In the end, here was ELMO Day 1:

and Day 2:

The problems were written by

Carl Lian
Evan O'Dorney
Mitchell Lee and Benjamin Gunby
Carl Lian and Brian Hamrick
Brian Hamrick
Amol Aggarwal

Overall, I thought the problems were reasonably good, although problem 1 is a rather annoying and not very interesting case bash, and of course I prefer my own combo problems to #3 :-). But anyway, the problems themselves were not too bad this year, but there were lots of traps that were very easy to fall in to (and many people did). So when people left day 1, there were a lot of people saying ``Oh yeah, I solved 1, 2, 3a.'' Very few of them actually got credit for all that. Day 2 was much better in that people basically knew what they solved, but #4 still had a rather large pit that needed to be avoided. Anyway, I'm going to not talk too much about specifics of the problems in case you guys want to try them.

Grading was an interesting, entertaining, and slightly stressful experience, as always.
``Can you tell what this says?''
``How many points is this worth?''
``Do I take off a point for this?''
``Whatever, I'll grade it down and let the team leader coordinate it up.''
This was my second time grading and I've enjoyed it a lot both years, although reading some of the red/green MOPpers' handwriting is pretty annoying. Worst style was not very surprising for me, after seeing the ELMO solutions (don't worry, we did all the grading anonymously. I matched the ID with a name after the grading happened).

After the grading for day 1 was done, we sorted the solutions into 24 folders: one per problem per team and distributed them. Coordination for day 1 would occur during day 2, and the grading for day 2 would be done immediately after with coordination for day 2 happening later that night. Unfortunately, this meant that coordination started at 8 am, so some people missed their coordination time.

Coordination seems like it would be more fun than the grading, but really it's just you arguing for a lower score and the team leader arguing for a higher score. And this almost always involves them pulling some bullshit on you saying that their team member could have done this easily and that they only were missing one tiny step and that the entire problem is trivial so they shouldn't even have to write down anything to get a 7.

The grading and coordination room after everything was complete.

In the end, the scores looked good for our efforts. Nobody had as high of a score as we would have liked (the highest being 33 out of a possible 42 by Thomas Swayze), but the medal cutoffs were approximately what one would see at the IMO, and the total number of points given on each problem were in decreasing order on each day, with 1 and 4 being highest and 3 and 6 being lowest. So although plenty of people (including me to some extent) disliked what the problems ended up being, they gave us a good score distribution.

As ELMO finished, so did MOP. Kazakhstan decided to have a ridiculously early IMO, so we ended MOP nearly a full week earlier than we did last year. This meant, among other things, that we had an extremely tight schedule for getting ELMO entirely graded and coordinated. Day 2 was on Sunday, and the departure day was Wednesday. That's how tight it was. Additionally, because so much of my time was spent on the ELMO, I didn't have time to participate in any of the prepared talent show acts. In practice, that meant that I couldn't dance to Gee. =[ I did, however, get to participate in the MathCounts act again, where I was narrowly defeated by David Yang.

After the talent show were superlatives and then MOP awards. In the superlatives, I procured ``best basher'' pretty easily, having managed to get a 7/0.8 for a dumbass solution to an inequality. In the MOP awards, I got recognized for the only times in all four years of being at MOP. First, I got best style in black, which wasn't too surprising considering I had mostly 0.8s and nothing below 0.7 that counted, while many other people had 0.4s on solutions that got 7 math points. For best style, I got a book of sudoku.

Actually I had another MOP first this year. You see, there are a lot of problems to do on the tests, team contests, mock IMO, and so on. So there is a MOP handbook created with all the problems and all the tests. In order to accomplish this, writeups are assigned to the people who did not solve the problem but had some good ideas on it (and in this year's case, to people who solved the problem in a less than beautiful manner). To assist them in writing up the problem, a consultant, who solved the problem in a very elegant fashion, is assigned. This was the first time I got assigned to be a consultant, and I was very happy when I found out In-Sung's test paper said ``You are writing up this problem. Please consult Brian Hamrick, Supreme Grand Ayatollah, and submit to MOP office by Monday.''

Finally the awards for highest MOP score came. Top four from each group were announced. I was pretty sure that I was in the top 5 in black, but I wasn't quite positive. Anyway, when it was black's turn, fourth was Calvin Deng. My heart sank there, since I was thinking that Calvin was ahead of me, but we were very close. I figured In-Sung was probably third then? In any case, I was wrong. With three fewer math points than Calvin, but a very slightly higher mop score, I came in third place :D. For this, I was awarded play money ``to count, because [I] am good at combinatorics.'' Allen was second and Evan was way ahead in first, although not quite as far ahead as Zhai was his senior year.

Overall, MOP was a pretty satisfying end to my math olympiad career. Although I never got to make the IMO team, I've had in total twelve weeks of great experiences and lots of fun at MOP, and I can definitely say that it has helped me improve a lot. Back when I was in red, I knew so little. I did badly on the red tests that I now find easy, I was horrible at writing proofs (I never got above a 0.7 back then, and this year I never got below a 0.7), and all the rest. I was the lucky one of us three seniors this year; Tim and Travis go nowhere near as satisfying a finish.

I'm very happy with what I got, but you know, I still wish I had IMO as well.

Contests

2010-07-01T14:17:00.003-04:00

As many of you have probably heard by now, I did not make the IMO team. Although I was definitely sad for the hours after the TST and perhaps for a few days after that, I am not bitter about it. After all, I'm in no position to say that I deserve a spot any more than the six who got it.

There's something about contests that I've known for a while, but TST brought it up again. Contests aren't for deciding the best, as much as people would like to think that. No, the person who wins the USAMO is not necessarily the best mathematician, nor is the person who wins ARML, nor is the person who wins HMMT, nor the winner of any other competition. Math contests don't crown the best mathematician. They crown the winner.

Sure, a trip to Kazakhstan would have been great. Winning certainly does come with perks. But when it comes down to it, I know that the fact that I lost on the TST just means that I'm not on the IMO team. It doesn't mean I'm worse at math.

Look forward to a more complete post on MOP soon.

Fin

2010-05-29T12:39:00.002-04:00

This is a column I wrote for English (the third of three). I won't be sharing the other two here for various reasons. If something is unclear or you disagree with it, it might be that I didn't state it as well as I could have. This is an unedited draft.

The end of school has always come early for me, at least much earlier than for everyone else. In fact, throughout my four years at TJ, I will have experienced the magical month known as June for no more than a handful of days. I have already said my goodbye to the school building as a high school student for the last time, and I have mixed feelings.

High school as a whole was definitely a positive experience, especially being at TJ. I doubt I would have been as well prepared for the rest of my life at any other school. The common sentiments about the school are all true. The teachers here are amazing compared to those elsewhere. The community is something unparalleled across the nation. The sheer amount of technology that we have access to is astounding. And the amount of work that everyone puts in is great to look at.

But I'm not sorry to leave. Senior year has been a trip from distaste to being downright sick of the school. Maybe it was a bad sense of planning; I had saved the requirements I really didn't want to do until senior year. But I don't think so. I spent the academics fair last year browsing the choices for my fourth history credit, and hit on History of Science and Ideas. Back then it struck me as an amazing concept, and indeed it turned out to be one of my favorite classes throughout the year.

So what is it that leaves such a bad taste in my mouth? It was the atmosphere of the place. Throughout my first three years of attending TJ, I saw a student body of people who diligently applied themselves to everything that they did. Maybe the seniors did a little bit less work, but what they did do they did with a passion that I could admire. This year I haven't seen that.

After college applications were submitted, I saw something that made me lose respect for many people at this school. Left and right, students were dropping the extracurriculars that they had worked hard to build up for the past three years. I realized that no, they were not actually passionate about the endeavors, but were just doing it as a way to add another line to their college application. That thought sickened me.

A friend of mine told me that he decided against a college because it was too much like TJ. The daily routine was wake up, go to class, do problem sets, go to sleep. Honestly, I couldn't agree more. Here at TJ, I don't see anybody thinking to themselves, “This would be a great project, let's work on it together!” In the past, I know it's happened. That kind of thinking is what created TjBash, Kings of Chaos, Intranet and many other great projects that we still enjoy today. Where is the entrepreneurial spirit that drove TJ students of yore? All I see now is “Ugh, time to do this dumb project for English.”

Ender's Game

2010-05-18T20:56:00.000-04:00

Ender's Game has been one of my favorite books for a long time. Card's book, with its hypothetical bugger wars, struck home with me, but it wasn't until recently that I thought about why. I picked it up again earlier this year and read it through in a couple days. Then I read the introduction.

They just don't talk like that, she said. They don't think like that.

A guidance counselor for gifted children doesn't believe Card's presentation. When I read this part of the introduction at the beginning of this year, it made me wonder. How can anyone not believe it?

Skip ahead to English class a few months in the future, where Mrs. Colglazier poses a question to the class, "How many of you will admit to liking trashy literature when you were a kid?" Practically everyone raises their hand and starts discussing series: Magic Tree House, Pee Wee Scouts, and so on. Then Mrs. Colglazier continues, "What about Ender's Game?" Immediately I wanted to speak out in the book's defense. Having read Ender's Game only a few months earlier, I had found extremely deep meaning that had not yet been paralleled anywhere.

So what is it that makes people not only not connect with Ender's Game, but hate it? Why is it considered "trashy"? How can so many people be unwilling to accept something that is simply true?

People's views of the world are inherently tied to their experiences. One will often project onto others feelings that he or she has had. The problem, of course, comes when the other has had entirely different experiences. Subtleties are lost, bad inferences are drawn, everything goes haywire. So, to avoid this, many people, I think, just assume that everyone operates exactly as they do and refuse to accept otherwise.

That was deep enough for me to consider Ender's game a meaningful book. But then I realized there's even more.

What made Ender into an Ender? Obviously his genes played a role, but genes alone do not create an Ender. The circumstances must have driven him to grow so strong that nothing could keep him from doing what he had to do. But what circumstances were those? The answer is loneliness. What Ender had going for him was that he didn't have many friends, so he needed to train, needed to improve, needed to show the rest of Battle School that he was the one they should look up at. As Card put it, he needed to become so good at what he does that the rest of the school would have no choice but to notice him. And so he did.

I used to envy the people who went to Haycock and Longfellow because they pretty much have always had friends that were as interested and as talented in math as them. Now I'm not sure envy is the right emotion at all. I had noticed for a long time that the extremely strong math team members at Thomas Jefferson did not come from Longfellow as often as one would think. Instead they come from seemingly random schools. So rather than be envious of the Longfellow students, I wonder if I should be grateful that I went to Frost.

And yet no matter how skilled an individual is, it's nearly impossible to actually accomplish anything without a group of highly skilled friends. Ender simply could not have defeated the Buggers without his crew, no matter how long he trained. At some point, friendships have to be formed, loneliness has to be abandoned, but what is that point?

When I look at our math team, I wonder how many of them would become Enders in another situation. How many of them could rise to be a force to be reckoned with, but don't because they know that they have friends no matter how good or bad they are. And now I wonder, is high school too early? Magnet schools provide great opportunities for very bright students to interact with other very bright students, an experience that I know is extremely useful, but there's something that you lose when you do that. You lose the ability to produce an Ender.

Project Teaser

2010-04-27T23:01:00.004-04:00

I haven't posted an update on my senior project for a long time now. I'll post a longer explanation and analysis when I'm fully done, but anyone worrying can rest assured that I have my program completed (and I believe bug free, finally). Here are a few images from it:

Fun Little Math Problem Of The Day 3

2010-04-11T21:59:00.003-04:00

Posts of actual content will resume at some point.

Fun Little Math Problem Of The Day 2

2010-04-04T11:35:00.002-04:00

Fun Little Math Problem Of The Day

2010-04-01T16:41:00.002-04:00

The title was stolen from Waffle.

Happy April Fool's Day everyone, and good luck to those of you hearing from colleges in 19 minutes!

A Mathematical Bridge Problem

2010-03-22T19:09:00.005-04:00

Playing a spade contract, you reach trick 10 in your hand to see the following four card configurations:

Dummy holds: ♠ - ♥ AQJ ♦ - ♣ A
You hold: ♠ 2 ♥ 2 ♦ 2 ♣ 2

How do you play to maximize your chance of getting all of the last four tricks? Assume that the only point card left is the king of hearts and there is a diamond higher than the 2 in one of the opponents' hands.

Obviously it depends on your situation, so say that the following happened: your partnership started with 21 high card points between you and during play LHO has played 16 points and RHO has played none. Does this change your answer? What are the probabilities now?

Does your answers change depending on which of the following situations happened?

Neither opponent bid during the auction
LHO opened an artificial 1♣ showing 16+ points
LHO opened a standard bid showing 13-21 points. Does it matter what bid it was?

I'm not sure of the answer to this question, so I'm interested to see what the readers of my blog think.

Medalia de Aur

2010-03-02T21:30:00.001-05:00

As some of you know, I went to Târgu Mureş, Romania for the Central European Olympiad in Informatics. This year, I went to Bucharest, Romania for the Romanian Masters in Mathematics. The team consisted of Allen Yuan, Vlad Firoiu, Sam Keller, Tim Chu, Albert Gu, and myself, headed by coaches Po-Shen Loh and Yi Sun.

Two days before we were to leave, Po-Shen sent us an email that, among other things, notified us that Lufthansa was currently experiencing a strike and that if our flight out of DC was canceled, the entire trip would be also. Obviously, this did not sit well with us, as we were all strongly looking forward to the trip.

Luckily, the strike was called off before we left, although Lufthansa was still short pilots, so some of the flights got canceled, but ours wasn't one of them. The flights to Bucharest actually went pretty well, including the AMC B. I did worse on the B than the A, but it really doesn't matter. I took it mainly because I figured everyone else would also and I didn't want to be bored for those 75 minutes. Tim had gotten a 96 on the A and was worried that he didn't qualify for AIME, and he wasn't exactly relieved when he got a 96 on the B as well.

On the trip there, we were expecting to be housed at Hotel Moxa, a 4 star hotel in Bucharest. However, it turns out that it was actually Complex Moxa, which is used for college dorms and is just an annex of the hotel or something. The rooms were pretty unfortunately bad, but ours had a TV in it! (the others apparently didn't). Because of the 7 hour time difference, the Olympics were on after all of the events for a day ended, which was extremely convenient. I definitely watched more of the Olympics while in Romania than any other time.

Sam checking out the room
We also found out that the complex didn't have an open wireless access point....But Vlad had this USB thing that allowed him to get internet access in Romania. It's called Zapp or something. At least we had internet access, even though it was pretty bad.

The next day we still weren't competing. We got our first taste of Romanian breakfast, which included an interesting tea (I think it was purple) that tasted pretty good, as well as some cheese. Being American, we obviously thought the portions were way too small so we ate masses of bread with oil and vinegar.

Our first Romanian breakfast
After breakfast, we met our guides and went to the high school where we would be taking the contest in the following two days. After touring the school and dropping in on a ``superior algebra'' class, the guides asked us if we wanted to go into the gym to play some sports. Inside, there were lots of people from various teams playing volleyball, but the court was pretty full so we didn't join them. Instead, we saw a ping-pong table, but nobody had any paddles, so we started playing basketball while we waited for a guide to retrieve paddles from the complex.

For some reason, someone thought it would be a good idea to play outside, even though there were huge puddles of water on the ground and the court was not very even. There were also ping-pong tables outside, but they looked pretty bad. They were really low, weren't flat, and the nets were actually iron fences.

China plays on them anyway
Eventually we got some paddles and played some ping-pong, as did the Chinese. The Chinese team didn't know much English and the only Chinese speakers were on the US team as either a student or a coach, so they spent a lot of time with us (and also Allen and Tim were in a room with two of them).

At some point we went back to our room to hang out until dinner, after which would be the opening ceremony. But as we were just starting to chill in our room, our guides came up to inform us that the opening ceremony got moved from 2000 to 1600, and we had to go back to the school.

The opening ceremony was actually quite nice. Only a small part of it was dual-run in Romanian and English. All of the guest speakers spoke in English, so translation was unnecessary, and they also all kept it very short. It made the opening ceremony much shorter than what I expected.

The next day was competition day 1.

Go go go!
I read the problems and solved 1i on sight, as did the rest of the team except for Vlad, who apparently took 1.5 hours on it. I then spent a bit of time on 1ii, but wasn't quite getting the details. I figured it would be easy anyway and went to do number 2 before finishing.

Number 2 was dispatched rather readily, and at this point I had about 3 hours left, if I remember correctly. I drew the diagram for 3 (although I actually drew the wrong diagram, thinking ``external'' meant that the quadrilateral was external to the circle, rather than the circle is external to the quadrilateral), wrote down some random stuff, and went back to 1ii. After all, surely a number 1 number theory would be easier for me than a number 3 geometry, right?

So it turned out that I didn't solve 1ii, and didn't have anything worth partial on 3, whoops. In the last 5 minutes I wrote down some stuff for 1ii that I figured had no hope of working, but it turned out to be extremely close to the correct solution. I left the room thinking ``Man, I'm going to have to tell the rest of the team that I didn't solve number 1.''

So talking with the others after day 1, it seemed initially that most of them had solved two problems: either 1 and 2 or 1 and 3. The exceptions were Allen, who solved only 1i and 2, and Sam, who solved only 1. After talking a bit more, however, Albert determined that his 1ii was completely wrong, and so he had only solved 1.5 problems as well. After day 2, we would find out that during coordination the coordinators had thought that Albert's solution had worked too, and Yi and Po-Shen had to tell them it was wrong to keep the spirit of the contest.

Allen and I both had essentially identical progress on 1ii, and since it was so close to the correct solution, we came out of coordination with 6s...somehow. The graders were apparently pretty lenient with scoring.

Day 1 Scores

ID	Name	P1	P2	P3	Total
USA1	Timothy Chu	7	7	0	14
USA2	Vlad Firoiu	7	3	7	17
USA3	Albert Gu	3	0	7	10
USA4	Brian Hamrick	6	7	0	13
USA5	Sam Keller	7	0	0	7
USA6	Allen Yuan	6	7	3	16

After day 1, we just went back to our room to hang out, being exhausted from the competition. Nothing much interesting happened. We just watched the Olympics and played card games, mostly.

We woke up the next day for day 2 of the competition.

No geometry! Wooo!

So I read the day 2 problems and I thought ``YES! There's no geometry! Let's get a 21 on day 2! Oh wait, these problems look time consuming. 4.5 hours might not be enough...'' Anyway I looked at problem 4 and killed it in about 20 minutes. I start working on problem 5 and it dies in another 50 minutes or so. At this point it's about 1050 and I have two complete solutions written up and I'm starting to think maybe number 6 is really hard and they gave us two really easy problems to compensate (a la IOI day 1).

So I spend the next 3 hours trying various stuff on number 6, but I don't do the thing that actually leads to a solution because it looked stupidly messy. Oh well. I wrote up what I had (which wasn't exactly the cleanest thing in the first place), and then turned in the test. When I was leaving the room, I figured I probably had a pretty standard result on day 2.

However, when I talked to the rest of the team, I found out that I could hardly be more wrong. They had all solved problem 4 (except Albert, who got a 0 on day 2, unfortunately), but nobody else had solved problem 5. I was really surprised. Tim thought he solved problem 6, but none of us could really verify it since he was the only one who felt that he had made significant progress.

Later in the day, we found out (with our awesome Chinese-speaking skills) that CHN1 had been the only Chinese team member to solve either 5 or 6 (and he solved both (and CHN was really Shanghai, not all of China)). Apparently 5 was supposed to be very difficult. I still don't really see why.

After day 2, we went to the mall to play some laser tag! Except that the game was actually pretty lame. At first there was only like one person on the red team, so it was just walking around for a while until the person running the thing decided to restart it. Unfortunately, the respawn time was still around 3 seconds, so whenever you killed someone they could just follow you until they respawn and kill you immediately. It made for a pretty annoying game.

We got back to the complex pretty late, so we missed the normal dinner and had to order pizza, and our discussion of day 2 with Yi and Po-Shen was at around 2230, way later than we expected.

Day 2 Scores

ID	Name	P4	P5	P6	Total
USA1	Timothy Chu	7	2	5	14
USA2	Vlad Firoiu	7	2	0	9
USA3	Albert Gu	0	0	0	0
USA4	Brian Hamrick	7	7	4	18
USA5	Sam Keller	7	2	0	9
USA6	Allen Yuan	7	2	0	9

The awards ceremony was the day right after day 2. But before that, coordination had to happen. So to get rid of us pesky contestants for a while, they sent us to the village museum: a collection of traditional Romanian houses. It would have been a really cool experience, but the ground was extremely muddy and it was simply unpleasant to walk around.

When we got back it was time for the awards ceremony. Well, almost. It was actually delayed for half an hour. Anyway, the awards ceremony, just like the opening ceremony, was very quick. The speakers knew that we didn't want to listen to a bunch of long speeches (and it was hard to understand some of their English anyway), so they went straight to the awards. Albert was the first USA competitor called up for honorable mention (solving at least one problem perfectly).

Next up was the bronze medals. There were a lot of bronzes, and Sam was among them. I was actually pretty nervous during the bronzes because I wasn't sure if I had screwed up something on day 2, in which case I would probably be in the low end of silver. As the bronzes ended, I breathed a sigh of relief.

The bronze medalists
Silvers started getting called now, and I was preparing to go up. They called the other three, and after a bit I handed my camera to Albert, expecting to be called up at any point. but the number of silver medals remaining was very clearly diminishing, and then they stopped. Stunned, I almost missed taking a picture of the silver medalists. At this point, I was just amazed.

The silver medalists
The gold medals started being announced, starting with the Chinese perfect scorer. Then the other gold medalists, and finally ending with me. The suspense was incredible. After going up to receive my gold medal, my hands were incredibly shaky. I could barely take pictures of the remainder of the ceremony, where China handed the trophy over to Russia (RMM has one trophy that the winning team keeps until another team ousts them), and then a few more short words.

After the award ceremony, Po-Shen informed us that the reason the awards ceremony was delayed was because they had to argue for my solution to #5 for about an hour. There was a step that I thought was obvious and Po-Shen thought was obvious, but the graders disagreed. Apparently they had to call in a third party to give an impartial opinion. Eventually, though, they agreed to give me a 7. Lesson from this: write more on combo problems because other people don't have the same idea of obvious as I do for combo.

Mathcamp pride!

Final USA Results

ID	Name	P1	P2	P3	Day 1	P4	P5	P6	Day 2	Total	Award
USA1	Timothy Chu	7	7	0	14	7	2	5	14	28	Silver Medal
USA2	Vlad Firoiu	7	3	7	17	7	2	0	9	26	Silver Medal
USA3	Albert Gu	3	0	7	10	0	0	0	0	10	Honorable Mention
USA4	Brian Hamrick	6	7	0	13	7	7	4	18	31	Gold Medal
USA5	Sam Keller	7	0	0	7	7	2	0	9	16	Bronze Medal
USA6	Allen Yuan	6	7	3	16	7	2	0	9	25	Silver Medal

The team with our lovely (and camera shy) guides

Thoughts on HMMT

2010-02-23T12:31:00.002-05:00

Overall, HMMT was well run. However, some of the tests could definitely have been better written. I'm going to just talk about the Combinatorics and Calculus subject tests from individual, since those were the two I took, and I'll also talk about team and guts.

First up is Calculus. I think everyone should realize that a 4 way tie for first at 29 is a problem with the test. The problems that I liked on calculus were 1, 2, 3, and 8. The rest of them have some issues.

Problem 4: Everyone who thinks about this problem can probably get it, but I think it's not exactly kosher to assume that people that people know the equidistribution theorem.

Problem 5: Just differentiate 4 times...seriously? I mean there's the nicer approach where you can notice that you only get 4 copies of when you differentiate the term 4 times, so you can directly pull out the coefficient by looking at just that term. By the time problem 5 rolls around I think you should be moving away from the stupidly straightforward problems.

Problem 6: I didn't actually solve this problem, although I had enough intuition that I could have finished it rigorously somewhat quickly. I just said, ``Let's put the line through the inflection point'', which is exactly what you want to do as cubics are symmetric about the inflection point.

Problem 7: This problem shares the same issue as many of the problems on the test. The answer (set two equal and imaginary and the third one real) is guessable (although I don't think anyone did), but it's completely unreasonable to expect students to prove it in 50 minutes when there are 9 other problems to work on.

Problem 9: Nice solution, but do you really expect anyone to get it?

Problem 10: This one is definitely doable...but it basically has seeing it before as a prerequisite. I thought that was what we were trying to avoid after last year's #10. It's a nice technique, but I don't think anyone would be able to come up with it during the test.

Overall, calculus had relatively easy problems #1-#6, a doable #8, and impossible #7, #9, and #10. 29 was getting all the doable problems. It really doesn't help the test to put a bunch of impossible problems on. The difficulty just has such a huge jump between 6 and 7, with 8 in between somewhere. I'd not be surprised if there is not only a huge tie at 29, but also a huge tie at 23. Perfect scores aren't a problem; ties are.

Next up: Combinatorics. Most of this test was actually good. I only really have complaints about problems 7 and 10.

Problem 7: This problem is just so out of place at HMMT. Looking at the rest of the problems, there is absolutely no strenuous computation. This problem, in contrast, is a complete computation-fest, after a moderately silly manipulation with expected values.

Problem 10: Same issue as Calculus #7. It's somewhat possible (although I doubt anyone did) to guess the optimal configuration, but not reasonable to expect students to prove it during the test. It's made even worse by the obfuscation that $16 = 4^2$, so instead of trying things like 5x5 with 4 numbers, people would rather have tried 4x4 with 2 numbers. I really dislike the problem for this kind of test. It would make a good team round problem, though.

I would have liked the test a lot better if problem 10 were what is now problem 7, and an actual problem 7 were in the problem 7 slot, although I really don't like the current problem 7 as problem 10 either.

Now for team round. I liked the team round more than other rounds this year (although that might have been because we won), because I think there was actually a scaling of difficulty (and the ability to give partial credit helps immensely). However, some of the problems had minor issues.

Problem 1: This is pretty classic. I'm pretty sure that Dan is not wrong when he says that he has seen it before.

Problem 2: I feel like I have seen this problem before, although it may have been slightly different (and the key observation should be that every divisor of an odd number is odd).

Problem 4: I'm pretty sure this is way too classic (although I forgot to cover the case where the 2x2 system for x+y and xy is singular, oops!). Actually I'm wondering if it's even possible for A, B, C, and D to be rational except at x=0, y=0.

Problem 5: I think it was fine, except that ``decreasing'' is ambiguous because you write polynomials starting from the highest order term, so we had the (unanswerable) question of does have decreasing coefficients or does ? We did eventually settle on the one in the official solution, luckily.

Problem 6: Okay darn, I gave a pretty bad argument for the existence of an infinite ray being inside the set (A better argument is to just look at the furthest distance at each angle. It's clearly continuous and then it should have a maximum since is compact, but that would mean it's bounded. Contradiction.). Mine can be made rigorous when you add in a weird continuity requirement and use the fact that is compact, but then you just get exactly the argument above. I actually like this problem, but I think that Jacob has mentioned that usually problems that have roots in college level math are rejected.

Problem 7: Maybe we're just bad at geometry, but it took Alex Zhu and I about 3 hours working together to solve this problem. Pretty sure this was harder than both 8 and 9 (and 10a, but having 10 be 10 is justified by 10b), but it was a good problem.

Problem 9: Maximum should run from i=1 to n, not i=0 to n-1, but I think that was pretty clear for most people. This problem was definitely easier than some of the ones that appear before it on the test. I'm not sure why it's a problem 9.

Problem 10: 10a is nice, but when Jacob says ``The idea for 10a works for 10b too after a few hours of work,'' it starts to look a bit unreasonable. I feel sad because I would have guessed and now I'm wondering why I didn't write that down. Maybe we would have gotten a point!

Finally, guts.

I really liked most of the guts round (in fact, almost all of it). But there were a few issues:

Problem 12: No, it is not ``obvious'' that does not need to be multiplied out. Replace the 9 by a 2010 and it would be. I don't see why that wasn't done.

Problem 17: Again, assuming people know (or can intuit) the equidistribution theorem (although in this case you don't actually need equidistribution) is a bit sketchy. However, I mind this a lot less in guts than in the other rounds.

Problem 32: I'm pretty sure our team had a fraction that we did not have time to turn into a decimal approximation. Without calculators, I find it a bit annoying that you would ask for a decimal to 5 places.

Problem 33: You have an exact form, so I'm not sure why the test is asking for the floor of . I'd also like to point out that Vieta jumping tells you that immediately (and it's odd because this recurrence was used earlier in the round). I would have rather asked for the exact form, although perhaps it is impractical to grade? Regardless, I would avoid approximation problems that can be solved exactly.

As you can see, I have many fewer issues with the guts round than the other rounds. This is probably because I consider guts to have a vastly different style, so it is easier to write problems for it and also there are so many problems that it's almost impossible to get the issues like what happened on the calculus individual test.

I guess a large part of my complaint is that the calculus test had a huge wall at 29 points that really made it hard for people who took calculus to compete with the people who took the other tests. This definitely has happened in the past (such as with the even harder wall at 50 for geometry a few years ago), and I guess I'm just a bit bitter that it happened to my tests this year. I do think (looking at results again) it affected this year's competition a lot more than last year's. Last year calculus was the test that suffered from the most ties (which was probably from the test being a bit too straightforward), but it wasn't a four way tie for first.

Overall, well done as always, but let's make next year's even better!

Please Never Use This Problem On A Contest

2010-02-10T19:47:00.007-05:00

2010 AMC 12A #24

There are so many things wrong with this problem that it made me make a blog post about it. The problem, of course, is that it relies on several conventions that are taught in math classes, but are not the conventions when you actually do math (or at least they aren't the conventions in every field of math).

First of all, I strongly object to the use of the word ``domain'' in this context. The domain of a function is absolutely not dependent on the definition of the function. A function is defined with a specified domain and codomain, of which this problem specifies neither. Instead, it tries to implicitly define the domain from the properties of the function. This is commonly used in math classes. I know I learned in some math class ``how to find the domain of a function'' such as , but I have never seen this outside of math class and a few competitions (and all of the competitions that I've seen it on, including the AMC, are very clearly tailored for average math class students, or at least students who don't have math education beyond that which you get in the classroom). Nevertheless, while I object to the use of the word ``domain'', it was clear what the AMC meant, so that would be admissible.

However, the real problem comes in the use of , which is clearly and unambiguously defined as . Furthermore, has a well-defined value. The problem is that has different meanings in different fields, and there is no way to know which one the AMC wants, except for the fact that people who have not learned math outside of the classroom can only be expected to know one of them.

The AMC never specfiied a codomain. And actually, since the AMC assumes the knowledge of complex numbers, this is a huge problem. is, for a vast number of fields, given the value of , even though any one of would work just as well. However, the point is that it is defined.

If I were to ask someone what is the domain of , I would almost certainly get the answer . But then, what if I say, ``Oh but is defined as !''? Then the person I'm talking to will, in many cases, revise their answer to all of . The exact same problem exists with . Is the domain or ? That question comes directly from the question as to whether the codomain is or .

So please, if you want to use this problem on a contest, word it like this:

Motivation

2010-02-01T15:02:00.002-05:00

On Friday, the 22nd of January, 2010, I was in my AP Government class for the last day of a model congress. The model congress was a great idea and one that worked very well for the first day. By the end of the simulation, however, the students decided they would rather screw with the system than actually try to learn. The result? Bills were passed that included provisions such as every April 23 is now National Korean Appreciation Day, also known as Kimchi Day. Those two weeks of class were not a model of congress. They were a mockery. At least I hope they were, or else I just lost all my faith in congress.

Very often, people bring up the issue of America's lackluster education performance. Efforts to alleviate the problem have been instituted, but they don't address the real cause of the problem. Our students simply don't want to learn. Throw as much money as you'd like at the education system, but if you don't change the attitude toward education, nothing will get done.

When a student goes through school, he or she is constantly bombarded with two conflicting messages: on the one hand, they have the American dream in one form or another, and at some level they understand that education is necessary to achieve this, but on the other hand, doing well in school is simply uncool. So students are essentially presented with a choice: work for a better future or shun school to become popular. It's obvious which one is chosen more, and not unreasonably.

When the issue goes to the government, they don't see this choice. All they see is under-performing students making their county/state/country look bad. They can make a law that requires improvement on standardized tests, but the people in charge of education locally, be it the school level, the county level, or the state level, won't make education better to meet the standards. Instead, they'll lower the standards so that more people can pass without increasing costs at all. Again, this is a rational decision, especially when the result of not meeting standards is punishment rather than help. Instead of improving, they cheat the system.

The same problem is present on a much smaller scale. I know many people who can say that they have what are colloquially known as "Asian Parents". As many of you know, Asian cultures value education highly. Unfortunately, the way that some parents carry this out is by punishing their child for every bad grade that they get. And a bad grade means a B+ (or an A- now, I guess). What do the kids do? They cheat the system. I don't mean that they necessarily cheat, but they get good grades without learning.

I'll do another blog post at some point on what learning is, exactly, but for this entry I want to talk about why students don't want to learn. The answer comes from History of Science. What Mr. Kelly said, and I think that this is very true, is that there are two types of motivation: intrinsic and extrinsic.

There are many reasons why students study for school: they need good grades to get in to college, they need good grades so that they don't get grounded, they need good grades so they don't get hit on the head, et cetera. Of all of those reasons, none of them are intrinsic. And that's the problem.

Think about the things that you do for fun. Do you do them to get in to college? Do you do them because your parents will hit you on the head if you don't? Do you have any reason to suspect that it will help you in the future? It's possible for school to be that way too, but a lot of things need to change.

First, people need to stop taking pride in their senioritis. Yes, your grades mostly don't matter for college now. Yes, you can slack off a little bit. But it's not something to be proud of.

Second, people need to realize that graduation is not the end of life. I'm sick of people telling me that they aren't going to work at math team because "It's too late" or that they don't want to do anything academic because they're "already in college" or have "already submitted [their] application." You aren't stepping off the face of the earth after you get your diploma, so stop acting like it.

Third, people need to stop telling other people to stop trying. Just because you want to be a slacker in your eighth semester of high school doesn't mean everyone does. Unfortunately, most people do. So this change needs to happen in teachers too. Half of the reason that geosystems is a horrible class is that the students don't care. The other half is that the teacher knows the students don't care and facilitates their not caring.

People wonder why our math team isn't doing well. I can answer that, but I'm also powerless to fix it without your help. You also won't like my answer. We aren't doing well because none of you want to do well. The only reason why you're going to competitions is for the prizes.

Why do I say this? Because none of the seniors are coming to math team anymore. They have no intrinsic motivation to do math or math team. They did it because it looks good on college applications. They ran for an officer position not because they wanted to help the team, but because they wanted to buff up their resume. But none of them actually say that straight up. Instead, when I ask a senior why they weren't at math team, they make an excuse.

At PUMaC, I said we had a chance to win HMMT if the team worked. From what I've seen, the team hasn't worked. I will be at HMMT and put in my part, and we will still lose. Chances are I won't be at ARML again. If the math team keeps going how it's been going, then this year will be our worst year yet.

Come on, prove me wrong.

POTW Beta

2009-12-28T23:02:00.011-05:00

As I hinted toward recently, I was thinking about running problems of the week. Well now I have created a beta test of the system to run over winter break. I am calling on you to help me test in the time between all your fun winter break activities. If you are a current member of VMT, go to http://activities.tjhsst.edu/vmt/pages/training/index.php after logging in to the wiki and you should be able to access the problems by clicking on the link that says POTW Beta. If you are not a member of the TJ math team, that link should direct you to a login/registration page where you can register for an account and log in as a guest. This beta will be open until the real POTW starts.

A note about the interface: All of the answers for this beta are positive integers. Therefore, there is no need to use the preview button. That is there so that if a problem has a more complicated answer, you can check to make sure that the system is parsing it correctly, and that the fact that your answer is incorrect is a result of your answer being wrong, rather than that it is formatted incorrectly.

I ask the following from you if you decide to participate in the beta:

Use your real name and grade and keep IDs appropriate. I will delete accounts that violate either one of these conditions.
Report any bugs with the system to me! These include broken links, bad formatting, anything that you think could be improved. This also includes feature requests!
Do not look up the problems or cheat on them in any other way. Because this is just a beta, I did not use original problems. However, these are still good practice problems and I think that much of the TJ math team can benefit from actually doing them.
Tell your friends! I want to get as many people as possible into the POTW system and to do that I need your help. However, make sure that they don't leave between now and the start of the real POTW.

Without further ado, I declare the beta for POTW open! The actual POTW will hopefully start shortly after break (maybe with 1-2 weeks in between). Note: This beta is completely voluntary and will not count for anything.

Ohaithar

2009-12-22T17:45:00.003-05:00

Snow!

2009-12-19T13:21:00.005-05:00

Rounds 3, 4, and 5

2009-12-17T17:00:00.004-05:00

The contests for HMMT team selection have now concluded. However, I started writing this blog post before performance contests 4 and 5, so you will see my thoughts progress over a week.

http://activities.tjhsst.edu/vmt/wiki/index.php/2010_Performance_Contest_3

Performance test 3. Halfway home. Something is clearly different. This time the curve is much more spread out. This is pretty much the exact score distribution that I was going for, but I wanted this to happen on performance test 1. So when I heard that the top 15 average was almost 10, I honestly winced: "Was this test too easy?" That question is still going through my mind. I like the score distribution, but I can't help but think that I only got it because the test wasn't at the same level as the last two.

And this is confirmed by others. When people commented on this test, they often said "I think this contest was much better than the last ones, mainly because problem 3 was completely trivial." When I look back over the test, I can't say that I really think it is too easy. Certainly problem 3 was easier than it has been before, but the hard problems were, I think, the same level as the ones before. The difference was that people had more time to work on them.

So no, this test wasn't too easy. What really gets me now is that nobody got a 4. Somehow people felt that problem 3 was easier than problem 2, and in fact more people solved problem 3 than problem 2. I don't know what to make of this. Problem 3 was a very classical problem that many people had seen before, but problem 2 was supposed to be an easy problem regardless of whether you've seen it before or not.

Problem 4 did pretty much exactly what it was meant to do: people who actually finished the problem (proved their answer) got it right, whereas people who sort of tried a few values and hazarded a guess didn't. Problem 5 turned out a bit easier than I anticipated, but that didn't affect the score distribution much at all. Finally, I was hoping more people would get problem 6, but I'm happy that one person got it right, even if he didn't quite finish the computation.

Let's go on to contests 4 and 5, which both happened on December 16, the day where all the seniors would find out about MIT early action decisions.

http://activities.tjhsst.edu/vmt/wiki/index.php/2010_Performance_Contest_4

http://activities.tjhsst.edu/vmt/wiki/index.php/2010_Performance_Contest_5

The graphs really interest me because the score distributions for the later contests were much smoother than those for the earlier contests. Contest 4 is the kind of score distribution that I would like if I were writing a real contest, where I'd want to name a top 3. This is because the top 3 are really distinct from the rest of the crowd. Test 5 is something that would be better for choosing a top 10 (although it looks like it's really only top 8), since there is a hump at 7. This means that the people who did better than that hump are distinguished, and should be named in the top 8. If you were to ask me my interpretation, I would say that contest 4 is better for training for the contests that we will be going to, and contest 5 is better for choosing the team (although the way our system works, getting an 8 on contest 5 doesn't help very much, unfortunately).

So what caused this change in score distribution? I can think of two possibilities: either my contests got easier or the team got used to my contests (hopefully improving in the meantime). I don't know if the contests really got easier. I will say, however, that I did feel that test 5 was definitely easier than test 4. However, what I didn't expect was that a nonzero number of people solved the last problem on test 4, whereas as far as I know only one person was close to solving the last problem on test 5 (and he finished incorrectly). This has a very simple explanation: the last problem on test 4 was a geometry problem, and I am relatively bad at geometry. Therefore, the geometry problems I think are the right difficulty are going to generally be easier than the nongeometry problems I think are the right difficulty. When I noticed that test 5 was easier than test 4, I thought about it a bit, then decided that I really liked test 5's problem 6, so I left it that way to give people time to work.

For those of you reading this, take a look at the tests now, after everything is done. Did the tests really get easier? Or can I safely say that the team is improving? Perhaps both, but I hope the tests didn't really get that much easier. So now I am interested in what people thought of this experiment (since it really was an experiment). Did the performance tests go well? Did you feel that they were better or worse than the other contests for determining teams (consider all three teams - I really didn't write these for the purposes of determining C team, but they had an effect down there)? Finally: did you like them?

My guess is that next year I won't be able to write performance tests for the team, although I had a lot of fun putting them together. However, I'm still not sure what I'll be doing second semester. I might (don't hold me to this) put together some contests and run them problem-of-the-week style. Would the people currently at TJ be interested? (this would also be open to people outside of TJ, so feel free to say that you would be interested if you aren't at TJ as well). If I get enough interest, I'll definitely try to do it.

I have some other blog posts that I want to write now, so this post is a bit short compared to some of my previous ones. For those of you who haven't read the solutions to performance contest 5 yet, I invite you to try this generalization of the last problem:

Brian flips a coin repeatedly. Before each flip, he decides randomly with equal probability to either continue flipping or to stop (so he flips 0 times half of the time). What is the probability that, after he stops, he has flipped exactly k more heads than tails in terms of k?

The Second PUMaC 2009

2009-11-22T22:27:00.004-05:00

This story begins long before Saturday, and in fact I'm writing this sentence on Wednesday. But while there's an interesting story that started far earlier, I'm going to start at the Saturday a week before the competition, when the power round was sent out. The power round this year was about lattices, meaning subsets satisfying the following properties:

If , then

If and then

Those of you who like thinking of as an abelian group should immediately notice that a lattice is simply a subgroup of . Those of you who are reading my mind and thinking of it as a -module are noticing that it's a submodule (now of course abelian groups and -modules are the same thing, but some of the ideas later are better to think of in terms of modules).

The power round was basically then an excursion into basic results for -modules. It defined isomorphisms and asked for some isomorphism invariants, which were relatively simple. It then asked to show that all these submodules of are finitely generated, and then finally went into the canonical form of the submodules (which is better known for the quotient modules as the Structure Theorem for Finitely Generated Modules over a PID). So essentially I had made a post on this power round more than a month before it was released. Awesome.

So how did the power round go? Well basically I didn't want to do my homework on Sunday, so I did the power round again. By Sunday night, I had done every problem done except 3.5 and 5.6, both of which I knew how to do but it involved proving or citing the above mentioned Structure Theorem, or at least special cases (other teams went the citing route, I would have proven it but I didn't want to go through the entire proof). On Monday I came up with a clean proof of 3.5, but 5.6 still eluded me. Finally I gave up and just wrote up the proof...it started on page 5 and ended on page 10 of section 5 (well at the time it took up fewer pages, but we later changed it from 11 point to 12 point font and while the wording didn't change, the number of pages did).

So now that the power round was written up, I sent an email to the team telling them to check it for readability and correctness. So while Sam and Adam had checked the round fully before the Wednesday mandatory practice, the other five team members were made to read over the round, even if they didn't know linear algebra. By the time I left for school on Friday morning, this was the chart of who checked what (the initials of the team members are at the top):

Yes, I have a whiteboard in my room.

Okay, so every problem was checked by at least half of the team except for 5.7. Looks like we should be good to go for power. After printing the twenty-two pages that can be found on the wiki, I snapped the above photo and then went to school.

At lunch, the car arrangement was a source of some great entertainment. We set everything up, including a car with Grace, Allison, and Divya. Then, as a joke, we switched Divya with Lawrence to see Lawrence's reaction. Allison arrived first, and reacted with "WHAT THE HELL?" But after a few minutes, she said "Whatever, I'll have Grace's laptop with Asian dramas." XD

Then Lawrence arrived, and he also reacted with "WHAT THE HELL?" But instead of just switching himself with Divya (as we expected), he switched himself with Seung In. Somehow that stuck and the car ended up being Allison, Grace, and Seung In. I still have no idea how that actually happened.

My car consisted of Aviv, Sam, Renjie, Akshar, Jenny, and me, so we were a bit cramped in the van (Jenny had to sit in the middle of the back between Akshar and me). On the car ride, we played hearts for a bit and house for a bit. I sat out the first game of hearts, where Akshar got completely destroyed. Second game, Sam and Renjie decided to play as a team and I was in. I got to shoot once, having two runnable suits (I believe my distribution was 2056) and by leading the spades early, so that when I got the lead again I took the last 7 tricks, or something insane like that, which contained all of the points. Shortly afterward, I ended up getting the queen a few times and eventually lost, but that round of shooting was quite fun :).

Upon getting to the hotel, I was disappointed to find out that I had one of the small rooms, but it was fine. I played around with google wave for a few minutes (I had finally gotten my official invite just that morning) and realized that it was actually pretty laggy. I wouldn't want to use it for most communication in its current form. Especially big threads start to lag massively. I'm not sure what it is, but it reminds me of the lag you get when you're X forwarding. But really, if document viewers can display 200+ page pdfs without lag, you'd think that google wave would be able to handle waves with only 100 messages.

After just a few minutes of google wave and finding the latex bot (watexy@appspot.com for those of you who don't know about it yet) I went back to the lobby to wait until dinner time. We ate dinner at Quaker Ridge Mall, which is a horrible idea. There's basically nothing there to eat, except for an applebee's out in the parking lot, which we went to. The food was decent, but then Jenny tried to cheat us out of $1.50. We caught her when we ended up short a bit of money, and then she decided to complain that she didn't have any coins so she had to pay $.50 too much. I tried to give her the rest of my coins ($.03) but she wouldn't take it. This was after she decided to buy $.60 gravy...

Anyway after dinner I took my laptop up to Renjie's room where we were going to play mafia. While playing I read through the google wave API. It looks simple enough, but based on my googling javascript has unfortunately little support for dynamic graphics and I don't want to use flash, so I want to find a good way around that. The game of mafia went extraordinarily well. After the first day, where we killed Seung In for voting for no lynch, Sam and I saved Luke, who was also targetted by the mafia. Second day, we killed a mafia, and then Sam insisted on saving himself. I had no better ideas, so I shrugged and let him do it. But the best part was after the next night, when Sam wanted to save himself again. I was like man this is a pretty silly and pointed to someone else, but Sam eventually won the fight. Next day, Sam said "I think Brian is the mafia, because he and I are the medics and he wouldn't save me last night!" The game ended where, in the last night, I wanted to save Jenny, Sam wanted to save himself, and then after we agreed on Jenny, Sam said (in the middle of the night), "Wait! Do you think it's more likely that they killed one of them or one of us?" Turns out Sin had tried to kill Jenny, and I was right. Hah.
(On the other hand, if Sin believes that Sam and I are the medics, targetting Jenny ensures his loss. However, he says that he didn't think that Sam was telling the truth, so his decision is defensible.)

Anyway, it's time to talk about competition day. I skipped breakfast, as always, and we headed out shortly after our hoped departure time of 730 (Aviv was late, as always). We got to Princeton at some time which I don't know because I don't wear a watch, and then after Mrs. Gabriel registered us we started walking toward McCosh, during which I heard Jenny yell from behind me, "Hey Brian, look behind you!" I turned around and saw Sherry there, so I slowed down a little, but she stayed behind me by a bit. Oh well.

On the way into McCosh 50, I saw Amy Zhou just a few feet in front of me! But she didn't notice me. Anyway, once we got in, I decided I wanted to talk to some people, so I went back outside and went to the registration table where Damien and his team were standing. While I was there, several members of the Exeter team showed up and I talked to them. It was pretty much my first time talking to David Xiao since red mop. We talked about the power round, and I found out that both North Carolina and Exeter had failed to solve problem 5.6. Awesome, we looked to be in good shape. Good lead on all of the other teams. In the middle of the courtyard, Sherry was pacing around waiting for the rest of the AAST team, and I considered going over and talking to her, but her parents were there and I would have felt kinda awkward. So instead I just continued talking to Damien and the Exeter people. It was pretty good to catch up with them. Also that this time I said hi to Amy (she actually saw me this time), who I hadn't seen for over a year since I missed MathCamp '09 :(. Well anyway that was that for the outside talking. We then all went into McCosh 50 and continued talking. There I saw several more people that I knew, but AAST still wasn't there. When finally they walked in, I went up to the door and said "Way to be late, guys." (it was after the scheduled start of the opening ceremony I believe). The opening ceremony started shortly afterward, 5 minutes late I believe. They gave us our proctors and we headed off to our testing room. But when we got there, the door to the building was locked, so we had to go in the other entrance, up to the second floor, and then back down to get to our room. Door unlocking fail. We got to our room and sat down, informed our proctor that Sam and Seung In were switching some subject tests, and then started. Our proctor was Arthur Safira's roommate, and as he put it we "probably got the only non math or science guy" there. In any case, my first test was number theory. Many of the problems were classical, but two of them were pretty decent:

Then again, the second is pretty straightforward if you know continued fractions (and are able to compute that in the time limit, unlike Damien). Some of the problems were a bit too classical. #1 was essentially the same as a Math Prize problem, #2 was find the number of solutions to for positive integers a and b, and #4 is problem 103 in Engel's number theory section, according to Andre.

Next up was combinatorics. Again the test was mostly straightforward, although I made a few mistakes that had to be corrected. And there was the now infamous problem:

As pointed out on AoPS, the fourth largest number of the set is 2, not 4. Many people interpreted it the other way (including the test writers and myself), so the answer 606 was considered correct, rather than 303. This could have been worded much better ("When these numbers are sorted in increasing order, what is the expected value of the fourth number?" or a variety of other ways), but regardless I got the points :). Unfortunately, Sam didn't, so our team suffered a bit because of the unclarity. Darn.

At this point PUMaC's amazing grading system that would announce individual finalists immediately after team round was revealed to us. All the answers were integers, so the proctor called us up one at a time to verify that he typed in our answers correctly to an online submission interface, which presumably handled grading automatically.

So next up was the team round. I forbade the team to discuss the individual round until after the team round, because they might become depressed about how badly they had done (if they had done badly), and also because I didn't want to answer questions about individual during the team round. Team round was quite interesting, with the answer sheet being a crossword puzzle. We got everything (either by solving or guessing) except for one problem, which we had 3 out of 6 digits for, but guessed all the other three wrong. That got us a total of 93.5 points out of 100. Not bad.

After team round, we were told that we had one individual finalist: me. It was a large disappointment that none of the rest of the team made finals, but I was happy that I had qualified. I decided to not bother waiting in line for lunch at that time, and went straight to the finals room where Peter Diao was the proctor. We both kinda partially recognized each other, and then he bothered me about giving him a weird look when he said hi. Then an AAST contingent including Sherry, who thought she had no chance of making finals, walked in. They certainly had more finalists than we did, but by no means did that necessarily mean that they did better on individual, since our scores were all reasonably high, just not high enough on any one test to qualify for finals.

Finals went okay. I looked at the problems and saw how to do problem 2 pretty quickly. It was a simple bounding argument and then a bit of cleanup at the end to eliminate two bad cases. After that problem was taken care of, I looked at the other two. Problem 3 looked obnoxious (47 46-gons? No thanks), so I worked on problem 1, which was a pretty annoying analysis proof that I wasn't completely satisfied with at the end, but I figured it was okay since it looked like 1 and 3 were both hard, so I probably had about as much as anyone else.

After individual finals, Sherry and I lagged behind everyone else, where I found out that Jenny had called her twice and texted her twice during individual finals XD. Way to go, Jenny. She tried calling back, but no answer, so we just went outside and started walking around. There was still free food for the individual finalists, so I decided to take some. I then offerred her some milkis, but she declined for the time being. We found Nassau street and went to the Panera, where I had a turkey artichoke panini and she just had some broccoli and cheese soup because she had eaten the PUMaC lunch before finals. It was a good lunch, though :). Afterward, we walked around Princeton campus for a bit, getting lost because her map from google maps had very few buildings marked on it. Eventually we ran into Divya, Grace, and Allison who were "totally not stalking" us. Of course not.

When I got back to McCosh 50, Greyson said "Congratulations on number theory." Apparently I had gotten all the problems right. I then asked to see the combinatorics answer sheet, and I had gotten all of those right too! With a double perfect score, some of the results were a bit less suspenseful.

The awards ceremony needed another 10 minutes of stalling after minievents to get a powerpoint made with results, so they had the math bowl finals, where AAST had a substantially better showing than last year. And one of the questions was StarCraft! But as Damien pointed out, StarCraft actually came out in 1996, BroodWar came out in 1998. Always recheck your facts. And apparently Damien was actually wrong, so he just fails.

The way they had the divisions split probably contributed a lot to the pumctuality of the awards, though, since we didn't have to listen to all the B division awards. First up was the subject tests. Geometry, Algebra, Number Theory, and finally Combinatorics. Vlad won geometry, so I was really happy off the bat, since he was my roommate at MOP last year. Then Chong won Algebra, who I knew from MOP 2008 (where he will be forever known as stomachache) with a perfect score. Interesting difficulty level, allowing perfect scores. It doesn't really appeal to me that much, since it potentially leaves people having nothing to do at the end of a test, but that's okay I suppose.

They finally got to number theory, and I won (Did anyone not see that coming? If not, you need to read the entire post). When I went up to receive the medal, it wasn't large enough to go over my hair properly, so it got stuck on my hair and glasses, much to the amusement of the audience. Going back to my seat, the rest of TJ said I should just stay there. I decided not to take this piece of advice. So next up was Combinatorics, where I won again (seriously, if you didn't see this coming read the post). And again, the medal got stuck on my hair, again to the amusement of the audience. I now had two medals to show for my trip :) Laura got a picture of this event, which has some hilarious comments.

Then overall results. Here, because of lack of communication about the method for finals, I had no idea if I would place or not. I was especially worried when Vlad placed 8th, since he had gotten problems 2 and 3, while I had only gotten problem 2 and most of 1. But I ended up winning overall as well, completing my sweep of individual events.

Yay two medals an a trophy :)

Next was power results. We sat through places 10 through 2: Beijing STFX1, The Evil Geniuses for a Better Tomorrow, Montgomery Blair High School, AAST Mu B, North Carolina, PEARL, Albany Area Math Circle, Murph and the Magictones, and Lehigh Valley Fire. Now at this point we should probably be suspicious since AAST Mu A and TJ A are both missing, but we didn't think about it too much. As the announcer said "and in first place...", a shout from the audience came: "Brian Hamrick!" (This was from the North Carolina area, so I'm not sure exactly who said it. If anyone knows, I'd be happy to hear). "AAST Mu A"

Okay, at this point, all of us in the back right corner of the auditorium (where TJ always sits) are thinking "WHAT THE ****?" And this wasn't limited to just the TJ team: Peter Diao immediately ran off to the grading room to figure out what went wrong, since we were definitely supposed to place. We were thinking somehow one of our problems got lost, either in printing or by the sponsors, or by PUMaC themselves. We even considered that maybe they mixed up our solutions with another team, but every single page of our power round had TJ A on it, so that was pretty unlikely. Meanwhile, AAST, to our left, was ecstatic because we had apparently massively screwed up the power round.

What?!?

We sat listlessly through the rest of the ceremony, as we placed fifth on the team round and sixth overall. We all knew that we were supposed to place higher, but we didn't know how high. I know I barely could pay attention to the top rankings, as PEARL took third, Beijing STFX1 took second, and Lehigh Valley took first (who is on Lehigh Valley, anyway? They didn't do so well on team and power so they must have had pretty good individuals). After the conclusion of the official awards ceremony, we met Peter againat the front, where he informed us that our power round score had failed to be entered, and that we had actually won the power round and taken third overall. So we missed out on a huge trophy because of a PUMaC screwup. Way to go, guys. Peter said that we got 78/86 on the power round, and I asked him what the second place score was, to which he replied 74. He also said that we had only beaten the teams that were at the actual competition; the German IMO team had gotten a perfect score. (Note: I've now been informed by Peter that he was mistaken and AAST in fact got an 85 on power, so we were actually second on power and third overall. He also says he thinks we lost a substantial number of points on 5.6, which I think is completely correct, so my guess is that the graders simply didn't understand it and took off points, which has happed before, such as to Alex Zhai on USAMO. Also apparently our score was entered, but it was entered as an 11 because someone sucks at reading. Massively.)

Regardless, I was pretty happy with my individual results, and third overall wasn't too bad for the team. When we left, I realized that I still had all of the milkis in my backpack, I had forgotten to give Sherry one after we went to panera :(. I was going back home in my dad's car, rather than in the car I went up with, so I gave them six milkis because we had done pretty well and took the other six in our car. Hopefully Jenny got her milkis this time. She complained after Duke that I had given Sherry milkis and not her. Heh.

The trip back was pretty uneventful. I slept a bit but the way the seat was I had a really sore neck upon waking up. Bleh. Whatever. I got home pretty much satisfied from the trip. While PUMaC certainly still had some kinks, it was run much, much better than past years. I think the contests could have been a bit harder, since the finals cutoffs seemed a bit high (probably around 30) to have 7 and 8 point problems, and a lot of the later problems were actually pretty easy and/or guessable. But besides the screwup on power and the couple of mistakes on the tests, it was a good event, and I got some good stuff out of it.

The spoils

Failure

2009-11-13T00:50:00.002-05:00

The second of five performance contests was this Wednesday at math team. This one went a lot worse than the last one, which I think is evident from the score distribution:

First, nobody got a zero! Why? Well, turns out that question 2 was flawed. The triangle with side lengths 5, 15, and 16 does not have an area of 72 and does not have an inradius of 4. This was brought to my attention during the contest and I decided to give everyone credit for the problem. After all, every triangle satisfying the problem statement has a side length of 1, and 2, and 56, and :). (Hint: there are no triangles satisfying the problem statement)

Second, 2 and 4 have about the same number of people! That's pretty easy to explain. The contests are set up so that there will be three tiers. The top tier consists of A teamers who are capable of solving all of these problems. They are expected to always get 1 and 2, usually get 3 and 4, and then sometimes get 5 or 6. The second tier consists of B teamers who are capable of doing well, but either don't have the speed or the knowledge to complete the entire contest in the time allotted. They are expected to always get 1 and 2 and then get some of 3 and 4. Finally, there are the lower teams who are expected to be working on 1 and 2 the entire time.

So what does this mean? This essentially means that A team has a 6 question contest, B team has a 4 question contest, and the rest of the team has a 2 question contest. When #2 turns out bad, it turns the A team's contest into 5 questions, the B team's contest into 3 questions, and the rest of the team's contest into 1 question. The impact on the A and B contests is negligible, especially since they are supposed to always solve the first two problems. However, the contest for the majority of the team was reduced from two problems to one, which resulted in the massive clump at 2 and 4.

Let's look at the test in more detail (you can see it on the wiki page linked to in the first paragraph).

The first problem is straightforward, provided that you can list the primes up to 43 and count them correctly.

The second problem is screwed up, as I said, but you can see what I had intended on the solutions page. (Maybe I should've solved for the true side lengths that would make it work so that you can also solve it with e.g. Heron's formula)

The third problem has an amusing story. It originated from a dinner at IOI when we were eating with the Canadians. One of them proposed a few problems to us. The first was a geometry problem which I can't remember, but Travis eliminated it rather quickly. Then he said "Here's a problem that took me a while to solve. See if you can do it. Find if ." To this, I responded, "Wait, isn't that utterly trivial? It's just the difference of two geometric series..." Their response? "Damn! Why didn't I think of that?"

The fourth problem has a somewhat different history. I first saw this kind of problem at MathCamp 2006 in a class titled "Calculus Without Calculus". It was a nice problem, but I basically never saw it again until last year, when it appeared on an ARML practice. However, the lines in the ARML problem were given to be perpendicular (BAD was right) and so most of the people who solved the problem simply calculus bashed it. After the calculus solution was presented, I went up to the board, drew the circle, and explained that not only could the problem be solved with just power of a point, it was independent of the fact that BAD was a right angle.

The next week, I wrote a TJML and included a similar problem, but changed the angle to something obnoxious: 82.5 degrees. The result was that one person solved the problem and nobody else, and many people didn't even realize that I had presented the exact same solution at the previous week's ARML practice.

Fast forward to the summer when I was writing problems for performance contests. I remembered this failing in the team and decided it was about time that they learned to listen to and remember solutions, so I put the problem in my database and aggressively classified it as a medium level problem.

Problem five is a classic use of Hensel Lifting. Many people commented after the contest "I have never heard of Hensel's Lemma." That was intended, but you can solve the problem without knowing Hensel's Lemma if you think of first solving the equation mod 5, then "lifting" it to mod 25, and then mod 125. This was a problem that was simply meant as a "here is a useful technique that you should remember if you want to do well" problem.

Finally, we get to problem six. This one was thrust into the performance contests because of some team contest last year (I can't remember which contest it was) in which there was a similar problem and none of the rest of the members of my team knew how to do it (meaning none of the top members of last year's math team). Again, this problem was meant as a wake-up call, so that people would learn how to approach problems like this, since they have appeared on various contests in the past (I think there was one at Duke last year). In another sense, it was a problem that said "This is something that is useful to know if you want to win." Essentially, some of my problems are problems that nobody will get, and if you know how to do them you have a huge advantage. An obvious example of this is HMMT 2009 Calculus #10. TJ A essentially got 24 free points because we knew complex analysis and nobody else did (it should have been 40 free points, but Kee Young and I were pretty silly during the test).

So how would I have liked this to turn out? Well, barring the screwup on number 2, I'd expect from our current team:

All of the top 15 to solve #1
All of the top 15 to solve #2
Most of the top 15 to solve #3
Some of the top 15 to solve #4
Few of the top 15 to solve #5
Few of the top 15 to solve #6

and I'd want:

All of the top 15 to solve #1
All of the top 15 to solve #2
Most of the top 15 to solve #3
Most of the top 15 to solve #4
Some of the top 15 to solve #5
Few of the top 15 to solve #6

What I wanted actually pretty much happened for problems 1, 2, 5, and 6. Problem 5 is supposed to get a few more solvers than #6, but still not many The problem is the midrange problems. However, as bad as the distribution is, I strongly disagree with making the middle section of the contest easier. The fact is, our A team is not up to par. I'm actually not sure why this is the case. I said in an earlier post that this might be because the class of 2010 made a block that just rose to the surface as a single chunk as the pieces of the team above it disappeared, so as long as nobody else in that block was working, anyone in the block would see their ranking go up for nothing, so why would they work?

Other people (namely Dan) have suggested that the problem is inherent in the ranking system itself. If rankings were kept private, as schools such as Exeter do, then unless one is vastly superior to the rest of the team, there is no magic website to go to that will tell one whether or not he will be on the A team or the B team or on any team at all. TJ has such a magic webpage, and given the fact that these are TJ people, it's inevitable that somebody will notice that no matter what happens, they will be on A team even if they skip the last practice. And then some people might go further and actually skip the practice.

I'm not going to say that Dan's theory doesn't hold water. It very well could. In fact, there are some people who I think would be likely to fall into such mental traps. However, I do have issues with keeping rankings private. The first is somewhat obvious: TJ kids will figure it out anyway. Even if we radically change how scores are calculated, unofficial results will become commonplace. This has been seen in the world of informatics. USACO releases all scores on a month-to-month basis. While their specific parameters are not releasd, our senior computer team keeps its own rankings page which does a simple average and generally correlates well with the camp selections. Additionally, during the International Olympiad in Informatics, results from day 1 appear on Russian sites even before day 2 starts. The International Mathematics Olympiad does it differently, since all grading is done after both days occur and everyone's score except for one problem is made entirely public officially as coordination proceeds. That is much more similar to what we do at math team. The difference is that when 5 of the 6 IMO problem scores are posted, you might know that you definitely made the gold cutoff, but you still have already done problem 6. When 13 of the 14 math team practices are posted, you might know that you definitely made A team, but you're still able to not go to the last practice, and so some people might just do that.

So maybe Dan's idea has some merit, but I think all of this is fundamentally a problem of the idea that results are what matter. Many people take this so far as to believe in the "big fish in a small pond" theory, which says that being valedictorian at a small, no-name school is better than being simply an above average student at a large, prestigious school. By being at TJ, I think most of you have realized that there are some things more important than being valedictorian. But have you realized that there are more important things than being on our A team?

My worry with the block of 2010ers was that they might think to turn TJ into one of the lesser schools so that they could in turn become higher ranked in terms of their own school and put something more impressive on their college application, which would make the admissions officers think that they are better than they actually are, since the TJ name carries a large reputation, and changes in that reputation won't propagate very fast. And with the large block of lazy 2010ers, this was actually possible.

At this point, I think I've broken the block. Our B team contains almost no seniors and the seniors on A team definitely deserve it, since most of them have performed well on at least one of my performance contests. Looking down at the lower spectrum of the rankings, I can see that many of the seniors that I felt were being too lazy to do as well as they were doing are in fact dropping like flies. But most importantly, the seniors are no longer a huge block floating to the surface. And while there might be a huge group of seniors at the top, in all honesty the gap between the A team and the B team is the smallest it's been in years. If the B team improves just a little bit, I am completely confident that they can continue the TJ legacy in the coming years.

However, some people, who will remain nameless here but probably aren't hiding it very much, believe the big fish in a small pond theory to an unacceptable extent. They think that winning the B division of ARML is better than being a random team in A division because they get more prizes. That's a problem.

Some people, when they read this post, probably thought that when I said our A team isn't up to par, I meant that they can't keep up with the other teams. That's not at all what I meant. Actually, I think that perhaps other than AAST and Exeter, we have one of the strongest A teams in the nation. And with the gap between A and B as small as it is, that also goes for the ARML A team. However, we're still not up to par. We're lacking on the mathematical thought process and how to attack a problem that has never been seen before.

I always wondered: how was it possible that some people made our ARML A team and then performed substantially worse at the competition than members of our B team? Obviously something was wrong with the selection process, but what? Well, I believe the answer was that our contests were too formulaic; they could be mastered by just doing math team for a few years and then recognizing the problems. But what happens then when ARML comes up with a new problem type? Those who are good at problem solving but not as fast because they don't have the problem types memorized are on our B team and get the problem, while those who were fast from just problem recognition flounder. That was the fundamental problem of our selection process.

In fact, 99% of all contest problems are very similar to a previous contest problem. So this formulaic method works to a very large extent, and China is able to use it to great success at IMO. And the results of this method are extremely clear: China dominated problems 1-5, while Japan dominated problem 6. Quite simply, had Japan gotten a perfect score on problem 4 and even a single more point on problem 3, China would not have won the IMO. Why did Japan dominate problem 6? Because nobody had ever seen that kind of problem before. Why did China dominate problems 1-5? Because they had all seen those same types of problems before.

I've had several arguments with Richard Peng, who coached the USA IOI team the past few years, about what the correct training method is. He insists that the Chinese method is the correct one because it brings in the most gold medals, while I say that the correct method is to pretend that the Chinese method doesn't work, and instead work on how to solve new problems.

TJ's method tries to emulate the Chinese method of training by providing a thorough overview of all of the types of contest math problems. The first error is that it only covers an overview of the types of problems that we do during eighth period. Those problems that are written by ARML, HMMT, and PUMaC are completely out there, and our eighth period practices don't cover the correct material. The second error is that there simply isn't enough time to provide a thorough covering of all of contest math. We are in school for about 40 weeks per year, of which about 30 are used for math team. If you do 12 problems every week in eighth period, that is only 360 problems. Can 360 problems cover all of contest math? Not at all.

So back to my performance tests. They are my way of pretending that the Chinese method of training doesn't exist. Instead of having the problems be archetypical problems that are likely to appear on a contest, my problems are the kinds of problems that are challenging and "out there". They're meant to have people exercise the thinking process that they use when they don't know how to do a problem, so when they invariably are stuck on a problem at PUMaC or HMMT, they have had practice with dealing with that situation before. In fact, since Arvind is reviewing the performance contests, I'll say that it's not unlikely that HMMT will specifically dodge the types of questions that I have given you. That should not detract from their usefulness if I have done my job right.

Will it be enough to win? In truth, it doesn't matter. Winning is great fun when it happens, but it shouldn't go to your head and you should be focusing on learning first, winning second (if even that). I have made the math team wiki public for that reason: I would rather have our competitors know much of what we know and give us a good contest than have a trophy on my shelf.

AAST

2009-11-07T21:17:00.000-05:00

is dense.

Sucky Contests

2009-10-25T01:37:00.001-04:00

Sometimes I wonder if math team is worth it. How does one get onto the teams that we send to Duke Math Meet, the Harvard-MIT Mathematics Tournament, the Princeton University Mathematics Competition, and the American Regions Mathematics League? Well you have to do well on contests given during eighth period. Fine, so what contests do we do? Well the main one that counts for these away contests (except for ARML) is the NYCIML: the New York City Interscholastic Mathematics League (Mandelbrot also counts, but occurs much less often). When I first joined math team, this was fine. Now I'm not so sure.

So what is wrong with NYCIML? For a large portion of the math team, absolutely nothing. However, for the people who actually have the potential to make our A team, there is a lot wrong with NYCIML. The biggest is that it is completely unrepresentative of the contests that they will have to face if they get selected for the team. For example, freshman year I qualified to be one of the members of TJ A at PUMaC. I got a 0 on number theory, what I considered at the time to be my best subject. That's right. I didn't get a single number theory question correct.

What went wrong? Well, it was a combination of PUMaC being crazy hard and a severe lack of preparation for that kind of math. To put it simply and bluntly, the contests that we do simply do not prepare people for contests, and they furthermore test for something completely different than what PUMaC and HMMT test for.

After three years of experience at PUMaC and HMMT, I think I have a good idea of what characteristics makes one successful at each of them. PUMaC rewards knowledge and an ability to work through standard computations, regardless of how ugly they get. Many PUMaC problems are not theoretically difficult, but finding the actual numerical answer is the bulk of the work. HMMT, on the other hand, focuses much more on problem solving. Most of their problems require little prior knowledge; almost everythign necessary can be derived on the spot. Some exceptions exist: the fact that has been used, for example. But by and large, HMMT is a contest based around how well you can handle things you've never seen before.

So what is NYCIML? NYCIML is just a hard math test. Practically everything can be seen instantly. There is no creativity involved. In fact, the last NYCIML this year essentially repeated two of the problems from the previous one. Contests that do that are generally bad. They become formulaic; anybody who has seen enough problems will do well, regardless of how good they are at math. As a result, for the people competing for the top spots on our math team, NYCIML is not about solving problems. It's about eliminating stupid mistakes. While I am all for stupid mistakes being considered in rankings, it should not be the determining factor as it is here.

This is why I wrote more than 50 problems over the summer. I wanted to create contests that would prepare the team for what they will face at PUMaC and HMMT. So far, the team has not met my expectations, but I believe that they will grow now that they have been faced with the challenge and the knowledge that there are three more to come. The biggest difference between the contest that I wrote and the NYCIMLs is the average. Out of 6 points, the NYCIML top 15 averages have been around 5. Out of 19, the top 15 average on my contest was a little over 6. What does this mean? It means that you have more than one route to victory. The first is to do the same thing as NYCIML: do the problems you know how to do and do them right. The problem is that I ramped the difficulty up quickly, so many of these people probably got a 4, or possibly a 2 because they still missed one of the first two problems (the contest was six problems weighted 2,2,3,3,4,5 respectively). The other method to victory is to be more ambitious, solving more problems, and then maybe you make a mistake or two that drops your score from 11 to 8. You'll still be ahead of most of the people. However, making a single mistake on a NYCIML costs you dearly, even if you know how to do all the problems.

At HMMT, the top score is not 50. If you know how to do all the problems, you will win, even if you make stupid mistakes. I speak from experience: On the 2009 Calculus test, I solved all 10 problems. I made some stupid errors on 9 and 10, dropping my score down to 35. As a result, I tied with Kee Young for first, but lost the tiebreaker. Regardless, the fact that I could make two mistakes and still tie for first demonstrates how different HMMT and NYCIML are. The two mistakes probably cost me the overall first place, but I was second, not eighth. One mistake is much more acceptable at HMMT than on NYCIML.

So why do we choose our team based mostly on a contest where problem solving is minimal? And why do we pass it off as good practice? It's good practice for most of the team, but not A team. But A team is the team that represents us at competitions, so it seems weird that we train the rest of the team more. Hopefully these performance contests will help jolt people into realization that being good at NYCIML does not mean that they will do well at every contest and will continue to work to improve in order to conquer the challenges I have given them.

The performance contest (to be done in 35 minutes):

And as an amusing sidenote:

Information is not Knowledge

2009-10-15T11:12:00.041-04:00

In the search for an answer to the question, I have come to the realization that a certain message from various sources (among them is Zuming) is extremely important for people to understand. This is a place where conventional math classes have a huge failing, and before people have realized it, they've assimilated the same failing into all of their studies, both inside and outside of school.

I realized that this is a problem when Dan sent out his latest email. Here is an excerpt from it:

"For a small subset of you, it was your mathematical knowledge that prevented you from making the calculation. To this subset, I assure you that we will attempt to teach you the mathematics. However, at the meeting last Tuesday, I believe that the majority of the people who did not take the relevant derivative, even after repeated requests from me, had the capacity to do so but lacked the motivation."

What is this saying? It's basically saying what I said in my last blog post: that people don't want to work when they know that they can. But I have to question something that Dan said. Do people actually have the capacity to do what they have the information to do? There are some people who "know" the product rule but would almost certainly be unable to do the problem that Dan posed. That is, they have the information but not the knowledge.

I have observed this failing in many places, not just at TJ. Perhaps the most surprising place for some of you would be red MOP. Yes, not everyone at MOP is good at math, as shocking as that may seem. They may be better than you. That doesn't make them good.

I was walking through the blue room (the main lounge) one day and I overheard some red moppers talking about abstract algebra. Some of the things I heard were along the lines of "Yeah, rings are really cool...except I don't really know what they are." This was when I realized the truth of Zuming's statement, but the importance had not yet hit me. What I did know at that point was that informing them of what a ring is would be completely useless. They would surely forget it by the next day, and most of the effect would be lost on them.

Now I think I understand what's going wrong. People love information. When they feel they understand one piece of information, they immediately grab for the "next" piece. Then why they think they're done with that piece, they grab for the next, and the next, and the next. What is the result of this process? It's a ton of information, but no knowledge. When you follow a trail of crumbs, you eat one, then the next, then the next. But did you ever wonder why the second crumb comes after the first, and not before? Sometimes it's obvious - the second explicitly cites the first. But what about when the first cites the second? Why do we learn about real numbers before we learn about Cauchy sequences or Dedekind cuts? Why is calculus the "next" step after algebra and geometry? The people who don't consider these questions are doomed for failure. They will never understand where they are going, and when the line of breadcrumbs dies out, they won't know where they are, unable to find any familiar landscape, hopeless until they find a new trail of bread crumbs that won't help, but rather just lead them further into the wilderness.

So what is the answer? I am not saying that you should be contrary and head off into a completely different section of the woods from where the crumbs lead you. This will probably lead you to just as much failure. After all, there are crumbs there for a reason: this path has worked for other people before, and it will work for you too - if you walk it the right way. You should walk this path, but don't swallow bread crumbs as fast as possible. Savor them. Enjoy the scenery. Maybe even deviate from the path in order to learn the surrounding area. Then come back to the next crumb and do the same thing. Each time, you'll feel more and more comfortable with the area, allowing you to move further and further out into the wild, while still always knowing where you are.

All around me, I see people who have been adversely affected by the bread crumb trail. There was a trail of crumbs. They ate the crumbs; they did their homework. Every once in a while, there was a signpost; they took a test. They got to the end of the trail, marked by a final signpost: the final exam. Where were they? They had no idea. What they did know is that there was another trail of crumbs waiting for them: the next class.

People tend to like hammers, like the Fundamental Theorem of Calculus, or Muirhead's Theorem, or Combinatorial Nullstellensatz. But think: If you have no idea how to use them, how useful are they? Not at all. Information is not knowledge.

Smith Normal Form...Finally

2009-10-11T17:25:00.010-04:00

Okay, so I'm writing this post about Smith Normal Form just as I decided that my first point of attack is going to be avoiding it. This is because the fastest algorithm I found to compute Smith Normal Form is general is time, whereas an algorithm that uses geometric properties of spaces can compute homology groups in time. This is a huge gap, although the big issue is going to be how to handle torsion, since the paper that computes homology groups in assumes the space is embedded into , which implies that there is no torsion (so the homology groups are all isomorphic to for some k). Well let's look at why Smith Normal Form is hard to compute. To do that, I should explain what it is.

Consider an m x n matrix A whose entries are elements of a PID (in our case, ). Then we can find invertible square matrices P and Q with entries in the PID such that PAQ is diagonal and if i < j. This matrix need not be square, for varying i. Here is how I think you should think about it:

A is a matrix that represents a quotient module of . Each column represents one generator, and each row represents one relation.
P represents combining of the relations. This is like how you can take and to get and by subtracting the second from the first. With P alone you can get into a row reduced form, but not necessarily diagonal.
Q represents combining the generators. So maybe instead of using the generator set we want to use . Q lets us do that.

These two matrices together allow us to eliminate all the off diagonal elements, and when that's done we have our module as something of the form . However, this may cause the elements on the diagonal to get larger. This is probably not obvious to you, but when I explain the algorithm for computing the normal form it should become more clear. The divisibility condition is also one of the weirder things, but it is essentially just removing all the ambiguities caused by the Chinese Remainder Theorem: . Smith normal form uses the divisibility condition to give the latter, although in the form .

Okay, so how to actually compute this mysterious Smith normal form? Well, let's use a simple example. Suppose we have the following module that we want to simplify:

The generators are
The relations are and .

We represent this module by the matrix . We then do row and column operations to eliminate entries: subtracting two times the first row from the second row gives . Then subtracting twice the first column from the second column and one times the first column from the third column, we get , which is our Smith normal form, and we now know that our module can be better written as . The generators corresponding to each of these three components can be obtained from the column operations that we did. In this case, the generating set is , and our relations become and .

There is still a question, though. What do we do when the top left element doesn't divide the row or the column elements? We need to make sure that P and Q have inverses with integer entries, so how do we do this? The answer lies in Bezout's Identity. Suppose we're looking at a portion of our matrix that looks like . To make it simpler, let's pretend it just looks like . It might take a while, but you should be able to see that it doesn't matter what the dimensions of the stretched version is, as long as we multiply by square matrices on either side. So now say we want to eliminate c. How can we do that? Well, what we do is we write where g is the greatest common divisor of a and c. Then , so we know that is invertible because the determinant is 1. Furthermore, when we multiply we get , and we have eliminated c, just as we wanted. The problem is: this might have undone our elimination of some of the columns! Well, never fear! We can alternate between eliminating the rows and eliminating the columns, leading to a sequence of top left elements where each divides the previous. Therefore at each step the top left element gets smaller, meaning it terminates eventually. (For general PIDs, we create an increasing sequence of ideals and then use the fact that our ring is a PID to show that it is Noetherian, and therefore the sequence becomes constant eventually). So once both the first row and first column are eliminated, we ignore the element that's now in the top left and proceed to diagonalize the rest.

Each of these row or column operations can be represented by an invertible matrix that can be absorbed into either P or Q (P for row operations, Q for column operations), giving us the construction we wanted before. That the divisibility condition can be satisfied with row and column operations is a simple exercise.

So how does this relate to homology? Well it's relatively simple. We can represent our bundary homomorphisms easily with matrices. The kernel of a homomorphism is just the null space of the corresponding matrix and the image by its column space. So to compute the homology group, we just reduce the matrix into Smith normal form, and then read off the module. The one thing that we need to watch is that we don't use the components that correspond to rows that don't exist, because our module is generated by elements of the null space, not just any columns. That means that the rank of our module can't be more than m, as it could before.

As I said, making progress here seems difficult. The methods to compute Smith normal form are pretty complex and it would be very difficult to surpass them. However, the large gap between and gives me hope for finding at least something for orientable manifolds in dimensions higher than 3 that runs faster than just computing the boundary matrices and their smith normal forms.

Ugh

2009-10-04T17:33:00.001-04:00

Homecoming. Blah.
It was my first and last homecoming of high school, and while I know that I would have greatly regretted not going, I also can't say that I had the great time I was hoping for.

Since I don't have my driver's license yet (in fact I was the only person in our group without a license), I had to get rides from Luke (thanks!). Of course, that's not to say that everyone was able to drive. Parents apparently get in the way.

Well dinner was pretty good, but it was stupidly expensive. I blame everyone who voted for Italian for causing this...including myself. Regardless, the bread was really good, but I was basically full when we got our entrees. How people could still eat dessert is beyond me.

After dinner, we went to the dance. It was okay, except that we were waiting outside for Jason for about as long as we were at the dance...miscommunication ftl.

Luke's afterparty looked to be redeeming. There was a lot of food, although I was still mostly unable to eat after the dinner. I managed to eat a small piece of mooncake...and a couple of chips. That was about it. We played melee for a while. First round I decided to play Jigglypuff (she's so fun to use :)) and got second behind Lenny (who has been playing melee instead of bridge...grrrr). Next round I played ice climbers, since the last time I had played melee was at Ved's house and I went about 1-8 in 1v1s...with the 1 win being from ice climbers. Well, that happened again, and I somehow won, even though we were playing on flat zone, so nana got KOd basically instantly every time I spawned. I'm probably the only person to be best with ice climbers.

Then the poker started. Each person started with 210 (10 1s, 10 5s, 5 10s, and 4 25s), and we started with 1/2 blinds. I managed to be the first one out (blargh). Here's the last hand I played. I call preflop with KJ suited.

Flop: AQ10 rainbow

At this point I have 39 left and an ace high straight, so I go all in and get called.

Turn: 8
River: A

This looks pretty good for me. I confidently flip over my KJ showing my straight and my opponent shows pocket queens. Not only did I get completely screwed on this hand, I was the clear favorite until the river came up. He NEEDED the board to pair to win that. Ugh.

So then at this point Luke kinda stopped playing and he's short stack anyway, so I take over and lose all his chips. On one hand I picked up KJ suited and jokingly told him that he was going to get eliminated on that round. Didn't quite happen, but it was pretty close (I took a pretty big hit from that one). So then after that I managed to lose again. Yup. Out of a 10 person poker game, I was both 9th and 10th.

Renjie got out next and we played some melee. I think I went like 2-5 or something like that against him. Not a good percentage for me.

Anyway after the poker died out I was pretty much meleed out, so I got up and watched stuff happen for a bit. Then I realized that I was REALLY tired (it was around 3, I think?) and started to go to sleep. I forget whether Amanda came before or after I had gotten out my sleeping bag and was lying down...oh well. I know she came in before I actually went to sleep though. Part of that was because while I was trying to fall asleep, people were talking loudly. I wouldn't have minded, but they were talking about homework and college apps. Ugh.

Well eventually I fell asleep. I was vaguely aware of some of the activities that went on while I slept, like cleaning up Luke's pool table and more conversations that annoyed me. As I started to regain consciousness, I listened to the conversation that was going on. It was not so bad, but I decided to just stay lying down and not officially "wake up" for a while. When I did, I was pleasantly surprised. I had gone to sleep being annoyed at some of the people at the party, but when I woke up it was a smaller crowd and the conversations were more fun. Regardless, I still can't say that the homecoming party was amazing. It was fine, and I know I would be feeling much worse if I hadn't gone, but it could have been better...for those of you who don't know why, I'll let you imagine what I might be referring to. GLHF :)

When I got home I was still feeling kinda bad after the afterparty. No offense to Luke, but last year's parties were a lot more fun. I got home around 10 and just went to sleep until probably 2 in the afternoon. When I woke up I was still had some residual annoyances with our class, but not nearly as bad as it was during the afterparty.

I'm still really annoyed at a lot of the people in the class of 2010. The combination of laziness and hypercompetitiveness is unbelievably irritating. If you're going to be lazy, don't bitch about your lackluster college application. If you're going to be hypercompetitive about college apps, don't be lazy in your extracurriculars (*cough* math team *cough*). You know why TJ's math team has sucked the past three years? I'll tell you why. It's because of the class of 2010. Look at last year's rankings. Look at how many 11s (the class of 2010) there are in B and C team. Think about how much work you would want people to do to make the B team for a school like TJ. If everyone on math team had done that much work then we'd probably win ARML easily. No joke. The class of 2010 is extremely talented, but their laziness is only compounded by the fact that they can just slide into the TJ B team without working for it, and therefore don't work for it. And now basically all of them have stopped working toward doing well on math team altogether. Here is the top of last year's ARML rankings after removing seniors.

Brian Hamrick
Dan Li
SeungIn Sohn
Jimmy Clark
Renjie You

Now look at the skill gap that appears somewhere in here. For the first math team practice, we did an old Mandelbrot that wouldn't count for anything but lettering, so Renjie and I decided to do it without paper: the only thing you're allowed to write down is the answer. On the 14 point contest, I got 13; Renjie got 6. That's the gap in our top 5. When you get down to 15th, people just suck massively. We got two fours at ARML last year - out of TEN. Everyone on TJ A should be getting 7 MINIMUM.

I'm not saying that everyone needs to spend all their free time on math team, but the people who say that they care about math team should care about the math, and they should be competent at it. Ugh.

At least the freshmen look promising ^_^. Seriously, the best thing that could happen for math team right now is that enough freshmen qualify for our HMMT teams that all the seniors from 15 down on ARML rankings don't get to go. Maybe that will shock them enough that they might become good enough to win ARML.

At least some stuff is going well...kinda. Ugh.

TJUSAMO

2009-10-02T13:34:00.000-04:00

Wow, TJUSAMO was huge yesterday. There must have been at least 15 people, and another 20 in TJAIME. Not even the first practices have been this big in past years. Hopefully everyone will keep coming. That would be pretty sweet. I decided for this year that since David Yang got a 27 on USAMO with horrible proof writing skills that I didn't need to teach people what a proof is, and they can pick it up on the fly. So I gave them the following four problems. Maybe you guys will enjoy them as well:

Consider an analog clock with an hour hand and a minute hand that move continuously.
a) How many times (in a 12-hour period) are there such that when you switch the hour and the minute hand they still form a valid time?
b) What is the first such time after 1:00?
You have n cubes of sizes 1, 2, 3, ..., n. You want to build a tower out of these cubes, but in this tower the cube on top of the cube of size k must be at most size k+2 for every k. How many ways to build this tower are there?
a) There are six people in a room. For each pair, they are either friends or enemies. Show that there are three of them such that each is either friends with the other two or each is enemies with the other two.
b) There is another room where each pair of people is either friends, enemies, or they don't know each other. How many people do there need to be to guarantee that there are three people such that each is friends with the other two, each is enemies with the other two, or no two of them know each other?
The numbers 2, 3, ..., 2010 are written on the board. Then someone comes up with the idea that they should repeatedly take two numbers x and y on the board and replace them by the number (x+y)/(1+xy) until only one number remains. What are all possibilities for this last number?

Homology

2009-09-24T11:52:00.000-04:00

It's been a while since I gave an update on my research project, and since I got working on blogger, it's time to write a new post.

So to explain what Smith Normal Form is, I should explain what it does, and to do that I need to explain the problems that I am looking at. I'm going to assume that you are at least somewhat familiar with the concept of a group and quotient groups. If not, read the wikipedia article on it.

So the first important idea is a homology group. Suppose that we have an infinite sequence of abelian groups and homomorphisms that satisfy the condition (that is, applying two of these homomorphisms always results in the identity). Then we see immediately that . Furthermore, since these are abelian groups, we have , so the quotient group is defined. This infinite sequence of abelian groups is called a chain complex and these quotient groups are called the homology groups. The nth homology group is defined as .

Okay, that's probably pretty opaque if you don't already know what I'm talking about, so here is a simple example (which will need an example of its own to illustrate, but that will come in time) called simplicial homology. We will build up a space as follows: To begin, we start with some set of isolated points, which we will call the 0-skeleton of our space. Next, we'll draw some lines (these are topological lines, so we're assuming that none of them touch except at points in the 0-skeleton and they don't have to be straight) between points of the 0-skeleton. The collection of points and lines that results will be called the 1-skeleton. Now, we take some triangles (that are "filled in") and glue them on so that their boundary is part of the 1-skeleton. The 1-skeleton, along with these triangles, form the 2-skeleton. We create the 3-skeleton, the 4-skeleton, et cetera by gluing in tetrahedra, 4-simplices, 5-simplices, and so on. (this gets harder to visualize past the 2-skeleton, so I'll stop there).

Now let's define a chain complex on this simplicial complex as follows. Our abelian groups are the free abelian groups generated by the n-simplices (so they'll all be isomorphic to for some k). The homomorphisms are the boundary maps, with orientation done so that the composition requirement is satisfied. For example, the boundary of a line will be (as one possibility), the formal difference of the start point and the end point (the reason for using addition as the group operation here will become apparent later). Then the boundary of a triangle will be directed so that the differences all cancel out when the boundary is taken again.

So as an example consider the following simplicial complex:
This complex is made up of six points, nine lines, and three triangles. So the chain groups are , and all the rest are trivial. We can then compute the homology groups. The first homology group is . I claim that this is isomorphic to . To see this, consider the top triangle. Suppose that our element of has a component with the top right line. Then the boundary includes a contribution of the top point. We must then have an equal component of the top left line to cancel out this contribution, but we have the relation that the sum of the boundary of the top triangle is trivial (because of the quotient). That means that we can effectively replace all the components of the top left and top right lines with the bottom line of the top triangle. Similarly, we can do this for the other two triangles and reduce our element to just a combination of the middle three lines. Then for these to have trivial boundary, the three components must all be equal, but they can be anything. This means that our homology group is , since it is simply determined by how many times it contains this loop around the center. The second homology group is much simpler, since the image of is trivial because is trivial, so the second homology group is the kernel of . The kernel of is also trivial, since the boundaries of the three triangles are all independent and none of them are empty. This means that the second homology group is the trivial group.

Wooo, if you followed that you probably understand as much as I do about homology (although I was pretty lazy about keeping track of orientation, which is bad)! In the next post on this series I'll explain what this has to do with matrices and Smith normal form.

LATEX

2009-09-21T22:58:00.000-04:00

Hurrah! I finally have working on Blogger!

Bezout's Identity

2009-09-16T23:10:00.000-04:00

Before making a blog post on Smith Normal Form, I want to step back and look at an identity that many of you probably know or think is obvious. This is, as the title suggests, Bezout's Identity. Additionally, I am trying to figure out a way to put LaTeX in these entries and I haven't quite gotten it yet, so this gives me something to write about without trying to format matrices in text format.

Bezout's Identity states that for any two integers, a and b, if g is their greatest common divisor then there exist integers x and y such that ax + by = g. A consequence of this fact is that the set of possible values for ax + by for any integers x and y is simply the set of multiples of g, since g clearly divides ax + by and Bezout's identity guarantees a construction for any multiple (just multiply x and y by the same number). Let us quickly prove this identity.

Let us induct on pairs (a,b) by the magnitude of b. If |b| = 0, then g = a, x = 1, and y = 0, so our base case is done. Now suppose we know Bezout's identity is true for all pairs with |b| < k. We will establish the identity for a pair (a,b) with |b| = k. Write a = qb + r with 0 <= r < |b| = k. Then notice that gcd(a,b) = gcd(b,r). Thus by the inductive hypothesis there are integers x' and y' with bx' + ry' = g, but bx' + ry' = bx' + (a - qb)y' = b(x'- qy') + ay' = g, establishing the identity for a pair (a,b) with b = |k| and completing our induction.

This proof has the added benefit of providing us with an algorithm to compute these coefficients. Let us consider the example of a=73, b=17. We start by writing out the division algorithm repeatedly as we would to compute the gcd:

73 = 4*17 + 5
17 = 3*5 + 2
5 = 2*2 + 1

Now we start from the bottom and write them in the following way:

1 = 5 - 2*2
= 5 - 2*(17 - 3*5) = 7*5 - 2*17
= 7 * (73 - 4*17) - 2*17 = 7* 73 - 30*17

So our coefficients are 7 and -30. This algorithm is also very nice for computing modular inverses. Notice at the end that if we take our entire equation modulo 73, we immediately have that the inverse of 17 is -30, or 43. However, this algorithm, being recursive, is not optimal for a computational method due to the need to remember each step. Because of this, I want to show you another algorithm to compute these coefficients.

We will begin exactly the same as before, using the division algorithm repeatedly until we reach the gcd.

73 = 4*17 + 5
17 = 3*5 + 2
5 = 2*2 + 1

But now, instead of working our way up from 1, we're going to work our way down toward 1, writing the equations as follows:

5 = 73 - 4*17
2 = 17 - 3*5 = 17 - 3*(73 - 4*17) = 13*17 - 3*73
1 = 5 - 2*2 = (73 - 4*17) - 2*(13*17 - 3*73) = 7*73 - 30*17

Notice that we arrived at the exact same answer as before, with coefficients of 7 and -30. In general, when working down only the last two results are necessary, similar to how when you compute Fibonacci numbers you only need to keep the last two in order to compute the next one. This trick means that to compute these coefficients only a constant amount of memory is necessary, although possibly a logarithmic amount of time.

Hopefully the example of 17 and 73 is illustrative enough, I don't feel like writing out a formal algorithm right now, but as an exerpt from my code, here is the function to compute the gcd of two numbers and the coefficients for Bezout's Identity.

int gcd(int a, int b, int& x, int& y) {
 int ax=1, ay=0, bx=0, by=1;
 while(b != 0) {
  int q = a/b, r = a%b;
  int tx = ax - q*bx, ty = ay-q*by;
  a = b;
  b = r;
  ax = bx;
  ay = by;
  bx = tx;
  by = ty;
 }
 x = ax;
 y = ay;
 if(a < 0) {
  a = -a;
  x = -x;
  y = -y;
 }
 return a;
}

You can see all the code that I've written so far at http://github.com/bhamrick/csl.

The Beginning of Research

2009-09-14T17:00:00.000-04:00

Six days ago school started. Fourth period that Tuesday I walked in to the Computer Systems Lab to see all of the projects we had proposed last year projected on the wall. at that point, I did not know what I really wanted to do, but knew that it was not what was on the wall. I did, however, know that I wanted to do something related to math, but because I'm in a computer systems lab, I would have to relate it to computing somehow. So that day I told the teacher that I had changed my mind about what I wanted to do over the summer and that I would do some sort of computational mathematics, but I didn't know what.

So that evening I started googling. What sorts of topics could I do computationally? My first thought was group theory, and indeed a google search for computational group theory yielded results, but I quickly realized that I did not know the important questions in group theory and would be more or less at a loss for what I could actually make progress on. As a next thought, I thought about what I could do that I knew a little bit about but not much, so while doing my research on something that I know about, I could be learning some interesting tidbits about the topic at hand. My topic of choice was topology.

Now I had learned some topology at Mathcamp, but of course a couple weeks isn't enough to say that I really know topology. I had some background in homotopy theory as well, as JR had gone through and shown us several nice applications of the fundamental group, and on the last day had briefly gone over the skeletal concepts behind homology. So if I were going to do a topological project, I would need to determine a few things:

1) How am I going to represent a topological space? Practically all interesting spaces have an infinite number of points (although maybe there is something interesting computationally in enumerating the finite spaces as there is for finite groups - I haven't looked into it), so there needs to be some implicit form.
2) What am I going to compute? I had some idea that homology was much easier to compute than homotopy (and that higher homotopy groups were often computed via what I later found out is called the Hurewicz Theorem), but since I really didn't know what homology was I wasn't sure how much I could do with this and the only homology I had seen was simplicial homology, and I wasn't sure about it's applicability.

So in order to answer these questions I started searching computational topology. What I quickly found was the Computational Homology Project (CHomP) and I also found references to this program called Kenzo. After reading through the documentation on the Kenzo site and the CHomP site, I realized that most of it was beyond what I could learn in a reasonable amount of time. So I abandoned this line of thought and went to a backup: complexity.

The biggest impression that I got from reading about CHomP and Kenzo was that their algorithms sucked. I had no idea what their algorithms really were, I couldn't find any satisfactory descriptions, but I knew that they took a long time, although much faster than humans (Kenzo claims to have experimentally determined homology groups that no human has). So I thought what is the most basic question that I can study the complexity for? My decision solved the first issue above - the formatting of the space. I said, "Okay, I know the definition (at least) of Simplicial Homology, so let's see how fast Simplicial homology can be computed theoretically."

That search yielded fruitful results. The first paper I found was titled On the Complexity of Computing the Homology Type of a Triangulation. Reading through this paper I found that this was pretty much exactly what I was looking at. The authors took a finite simplicial complex in matrix form (each column of the matrix simply being the boundary of the corresponding simplex) and probabilistically computed the homology groups in O(Dn^2) time where D is the dimension of the complex and n is the number of simplices. So this was a great start. Even better was at the end the authors wrote that area for future research could include probabilistic computation of homology for regular cell complexes and CW complexes, which are not conceptually much trickier than simplicial complexes. They also say that the computation of the cohomology ring operations could be useful, since while the cohomology is determined by the homology, there are spaces with the same homology and cohomology with different ring operations. So these two areas are where I am looking toward for my research. Currently I have only actually read into the first. I don't actually yet know what they are referring to by the cohomology ring operations.

So now I have a topic, but I need a plan of attack. While reading this first paper and thinking about it a little in my head, this problem of computing homology groups is really about computing something from an integer matrix, since the boundary maps can each be simply represented as an integer matrix. What I had gathered was that this was called Smith Normal Form, but I couldn't really understand what Smith Normal Form was, why it existed, or how to compute it naively. This was what I looked for today, and found this rather readable paper that introduces the concept of Smith Normal Form and explains how to compute it in a finite amount of time (although not bounded by anything, since the fact that it's finite simply comes from the fact that the integers are Noetherian). So now I have at least a plan for the first part of my research. I can for now remove myself from the topological nature of my problem and attack a very simple problem of computing Smith Normal Form. The topology will come back in because the fact that the matrix represents a simplicial (or regular cell or CW) complex means that it may be forced to satisfy certain sparsity or regularity requirements, which (as in the paper linked in the preceding paragraph) can be exploited in order to obtain a much faster expected running time than the naive or even less naive deterministic algorithms.

This series of posts will probably run two or three times a week, but most of the posts won't be this long as I was covering essentially an entire week here.

The Birth Of A Dead Hamster

2009-09-13T19:34:00.001-04:00

This blog fad has been going for a while. Many of my friends have blogs. I was opposed to it at first because I had nothing useful to do with it, just as I was opposed to Facebook. Actually I'm still opposed to it, but the opposition is quickly draining. I expect I'll actually break down and get one around this time next year, maybe earlier. For now, though, I will not.

So what made me get a blog? Well, quite simply, I realized that I could do something useful with it - that is I can chronicle my work on my senior research project and at the same time dump other thoughts into here. As such, at least for this year, it is quite possible that I'll be making several updates a week as I work toward getting something useful done.

I suppose I will explain the name of my blog up front. For several years now I have used the name Hamster1800. I actually created this name in elementary school when I got my AIM account. Hamster by itself was, of course, already taken, so I put a number after it, which happened to be 1800. It was not until later that it was pointed out to me that it could be interpreted as the phone number 1-800-HAMSTER. Anyway, I use this name in many places, including iccup, probably the most competitive ladder for playing starcraft outside of Korea. However, at some point a friend of mine thought it would be cool for us to put fake clan tags on our name, so he created the name [AhungrY]Melon, and another of my friends followed with [AhungrY]Argh. However, when I tried to create the account [AhungrY]Hamster, I was told that it was too long, so I changed it to [AdeaD]Hamster. This is the account that I use currently for playing Protoss. I have another account separate from both Hamster1800 and [AdeaD]Hamster that I use for playing Zerg, but I'm not going to release that name just yet.

So I was going to make my blog and I was trying to think of what the URL should be. I first tried bhamrick and hamster, but they were both unfortunately taken. Then after quite a bit of thought I remembered that I am also [AdeaD]Hamster and sure enough adeadhamster.blogspot.com was untaken. The title of the blog followed pretty quickly from that.

So this has been a pretty long intro post. I'm going to let it end here. Look for a post either later tonight or tomorrow depending on when I decide to post again.

For your amusement in the meantime: http://sendables.jibjab.com/view/ayCdy5tARoEdgXtb