Sucky Contests

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

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

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

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

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:

1. 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?
2. 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?
3. 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?
4. 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?