Against Hook-Length on USAMO 2016/2

A recent USAMO problem asked the contestant to prove that

\displaystyle  (k^2)! \cdot \prod_{j=0}^{k-1} \frac{j!}{(j+k)!}

is an integer for every {k \in \mathbb N}. Unfortunately, it appears that this is a special case of the so-called hook-length formula, applied to a {k \times k} Young tableau, and several students appealed to this fact without proof to produce one-line solutions lacking any substance. This has led to a major controversy about how such solutions should be graded, in particular whether they should receive the {7^-} treatment for “essentially correct solutions”, or the {0^+} treatment for “essentially not solved”.

In this post I want to argue that I think that these solutions deserve a score of {1}.

1. Disclaimers

However, before I do so, I would like to make some disclaimers:

  • This issue is apparently extremely polarized: everyone seems to strongly believe one side or the other.
  • This was an extremely poor choice of a USAMO problem, and so there is no “good” way to grade the HL solutions, only a least bad way. The correct solution to the dilemma is to not have used the problem at all. Yet here’s the bloodied patient, and here we are in the emergency room.
  • While I am a grader for the USAMO, I am one of many graders, and what I say in this post does not necessarily reflect the viewpoints of other USAMO graders or what score the problem will actually receive. In other words, this is my own view and not official in any way.

One last remark is that I do not consider the hook-length formula to be a “well-known” result like so many contestants seem to want to pretend it is. However, this results in the danger of what constitutes “well-known” or not. So in what follows I’ll pretend that the HL formula is about as well-known as, say, the Pascal or Zsigmondy theorem, even though I personally don’t think that this is the case.

One final disclaimer: I am unlikely to respond to further comments about an issue this polarized, since I have already spent many hours doing so, and I’ve done enough of my duty. So if I don’t respond to a comment of yours, please don’t take it personally.

2. Rule for citations

Here is the policy I use for citations when grading:

  • You can cite any named result as long as it does not trivialize the problem.
  • If the result trivializes the problem, then you are required to prove the result (or otherwise demonstrate you understand the proof) in order to use it.

This is what I’ve heard every time I have asked or answered this question; I have never heard anything to the contrary.

Some people apparently want to nit-pick about how “trivialize” is not objective. I think this is silly. If you really want a definition of “trivialize”, you can take “equivalent to the problem or a generalization of the problem” as a rule of thumb.

Clearly it follows from my rule above that the hook-length formula deserves {0^+} grading, so the remainder of the post is dedicated to justifying why I think this is the correct rule.

3. Subjective grading

I would rather have an accurate subjective criteria than a poor objective one.

In an ideal world, grading would be completely objective: a solution which solves the problem earns {7^-} points and a solution which does not solve the problem earns {0^+} points. But in practice this is of course not possible, unless we expect our contestants to write their solutions in a formal language like Coq. Since this is totally infeasible, we instead use informal proofs: students write their solutions in English and human graders assign a score based on whether the solution could in principle be compiled into a formal language proof.

What this means is that in grading, there are subjective decisions made all of the time. A good example of this is omitting steps. Suppose a student writes “case {B} is similar [to case {A}]”. Then the grader has to decide whether or not the student actually knows that the other case is similar or not, or is just bluffing. One one extreme, if {A} and {B} really are identical, then the grader would probably accept the claim. On the other extreme, if {A} and {B} have some substantial differences, then the grader would almost certainly reject the claim. This implies that there is some intermediate “gray area” which cannot be objectively defined.

Fortunately, most of these decisions are clear, thus USAMO grading appears externally to be mostly objective. In other words, accurate grading and objective grading are correlated (yay math!), but they are not exactly the same. All scores are ultimately discretion by human graders, and not some set of rigid guidelines.

Citations are a special case of this. By citing a theorem, a student is taking advantage of convention that a well-known proof to both the student and grader can be omitted from the write-up.

4. Citing the problem

In light of this I don’t think you should get points for citing the problem. I think we all agree that if a student writes “this is a special case of IMO Shortlist 1999 G8”, they shouldn’t get very many points.

The issue with citing HL in lieu of solving the problem is that the hook-length formula is very hard to prove, and it is not reasonable to do so in an olympiad setting. Consequently, it is near certain that these students have essentially zero understanding of the solution to the problem; they have not solved it, they have only named it.

Similarly, I think you should not earn points for trivializing a problem using Dirichlet, Prime Number Theorem, Zsigmondy, etc. This is also historically consistent with the way that grading has been done in the past (hi Palmer!).

5. Citing intermediate steps

Now consider the usage of difficult theorems such as Dirichlet, Prime Number Theorem, etc. on a solution in which they are merely an intermediate step rather than the entire problem. The consensus here is that citing these results is okay (though it is not unanimous; some super harsh graders also want to take off points here, but they are very few in my experience).

I think this is acceptable, because in this case the contestant has done 90% of the solution, and cannot do the remaining 10% but recognize it as well-known. In my eyes this is considered as essentially solving the problem, because the last missing bit is a standard fact. But somehow if you cannot do 100% of the problem, I don’t think that counts as solving the problem.

What I mean is there is a subjective dependence both on how much of the solution the student actually understands, and how accessible the result is. Unfortunately, the HL solutions earn the worst possible rank in both of the categories: the student understands 0% of the solution and moreover the result is completely inaccessible.

6. Common complaints

Here are the various complaints that people have made to me.

  • “HL is well-known.”
    Well, I don’t think it is, but in any case that’s not the point; you cannot cite a result which is (a) more general than the problem, and (b) to which you don’t understand the proof.

  • “Your criteria is subjective!”
    So what? I would rather have an accurate subjective criteria than a poor objective one.

  • “It’s the problem writer’s fault, so students should get {7}.”
    This is not an ethics issue. It is not appropriate to award points of sympathy on a serious contest such as the USAMO; score inflation is not going to help anyone.

  • “It’s elitist for the graders to decide what counts as trivialized.”
    That’s the grader’s job. Again I would rather have an accurate subjective criteria than a poor objective one. In practice I think the graders are very reasonable about decisions.

  • “I don’t think anyone disputes that the HL solution is a correct one, so certainly the math dictates a {7^-}.”
    I dispute it: I don’t think citing HL is a solution at all.

  • “Why do we let students use Pascal / Cauchy / etc?”
    Because these results are much more reasonable to prove, and the “one-line” solutions using Pascal and Cauchy are not completely trivial; the length of a solution is not the same thing as its difficulty. Of course this is ultimately subjective, but I would rather have an accurate subjective criteria than a poor objective one.

  • “HL solutions have substance, because we made an observation that the quantity is actually the number of ways to do something.”
    That’s why I wish to award {1} instead of {0}.

  • “Your rule isn’t written anywhere.”
    Unfortunately, none of the rules governing USAMO are written anywhere. I agree this is bad and the USAMO should publish some more clear description of the grading mechanics.

  • “The proof of the HLF isn’t even that complicated.”
    Are you joking me?

In summary, I don’t think it is appropriate to give full marks to a student who cannot solve a problem just because they can name it.

Advertisements

5 thoughts on “Against Hook-Length on USAMO 2016/2

  1. Ok, now grading is over(I think), and since anything I post won’t affect scores anymore, I’ll feel free to share my actual opinion. I’ll reveal here that I wasn’t just arguing for my score, I actually felt that accepting was the morally right thing to do, and actually felt pretty strongly about it.

    First at your criteria. I think that $v_p$ + legendre(which was definitely accepted) also trivializes the problem, the solution is literally 3 lines right here: $v_p(N)=\sum_{i=1}^\infty \lfloor \frac{k^{2}}{p^{i}} \rfloor+\sum_{j=0}^{k-1} \sum_{i=1}^\infty \lfloor \frac{j}{p^{i}}\rfloor-\sum_{j=k}^{2k-1} \sum_{i=1}^\infty \lfloor \frac{j}{p^{i}} \rfloor$, by Legendre. Clearly, $\lfloor{\frac{x}{p}}\rfloor={\frac{x-r(x,p)}{p}}$, and $\sum_{i=0}^{k-1} r(i,m)\leq \sum_{i=k}^{2n-1} r(i,m)$, where $r(i,m)$ is the remainder function. Thus, $v_p(N)=\sum_{m=p^{i}, i\in \mathbb{N}}-\frac{k^{2}}{m}+\lfloor{\frac{k^{2}}{m}}\rfloor-\frac{\sum_{i=0}^{k-1} r(i,m)-\sum_{i=k}^{2k-1} r(i,m)}{m} \geq \sum_{m=p^{i}, i\in \mathbb{N}} \lceil -\frac{k^{2}}{m}+\lfloor{\frac{k^{2}}{m}}\rfloor\rceil \geq 0$, other than defining what $v_p$ is(which I’m not sure if it’s necessary, but a WOOT grader told me to do so to be safe). The only observation here is $\lfloor{\frac{x}{p}}\rfloor={\frac{x-r(x,p)}{p}}$ and sum of floors is an integer, in my opinion, this is sufficiently trivial, as everything else just follows by simple computation. Similarly, you still need the observation to rewrite the expression as
    $\[N = \frac{\left(k^2\right)!}{\prod_{1\le i, j\le k}(i+j-1)}.\]$. Those 2 observations are comparatively similar in difficulty, and legendre isn’t exactly easy to prove either(if you’re proving your results all the way down to axioms, otherwise you wouldn’t know how to prove your result).

    Also, I don’t think Hook Length is as well known as Zsig or Pascal, I think it’s way more well known. It’s referred in papers as “classic”, while it actually takes me a little bit of effort to find a proof of zsig’s on the internet(as in not a direct google search like hook length formula is).

    Further, I don’t think that “you understand 90% of the problem” if the theorem doesn’t trivialize the problem. Take, for example, a solution that is about IMO 3/6 difficulty to reduce to fermat’s last theorem, and the student just cites FLaT at the end. Does that mean they understand 90% of the problem? I’m sure you’d agree that IMO 3/6 difficulty isn’t trivial. However, they still understand only about 2% of the problem, given that FLaT is much, much harder to prove than an IMO 3/6. Furthermore, I think it’s more than 2% of the problem to reduce to hook length formula, as the hook length formula actually isn’t too long(there are pretty simple elementary proofs, as in potentially easier than a normal USAMO 2/5, on the internet, also meaning that this formula is very accessible). From your criteria, I’d enjoy wasting a lot of time proving everything from axioms again, as that’s what you seem to be implying by “you don’t know the proof”. The truth is, we build off of other people’s work, and take a lot of things for granted without even knowing it. Just like in mathematical papers, sometimes you work with a group, and you immediately use someone else’s result to make further progress, sometimes without even knowing how to prove it(though granted, that means you’re trusting the other person to not have made a mistake).

    Also, accurate subjective criteria? In my opinion, this criteria isn’t even accurate, as 1.What’s accurate is subjective, and 2.Legendre falls dangerously in the black area as well. Also, a lot of people thought hook length was the right thing to do, possibly the intended solution, and immediately wrote it up, thinking it would get a 7. In reality, they easily could’ve solved it with $v_p$ + legendre afterwards. Also, no, the rule that you have to draw a diagram or lose a point is written on top of the problem sheet, they could put the criteria if they really wanted to on top of the problem sheet too. The “naming a problem” and the G8 is not the point; the hook length is a [b]well established theorem[/b] and has several proofs on the internet. In summary, I think this solution is ranked about the same as legendre’s.

    Like

    • Grading is *not* over, but I’ll reply anyways.

      1. From having read a few papers on U2, I assure you that v_p plus Legendre does *not* trivialize the problem (the number of students who attempted v_p and failed is staggering). Under the rubric, the three lines you wrote above would earn 0 points; nearly all correct v_p solutions were at least 2-3 pages long.

      Just because you can compress the proof into three lines by omitting all the content does not make the solution “trivial”.

      2. I am confused you keep insisting that HL is olympiad difficulty. It really isn’t. And *especially* not so in comparison to Legendre.

      I do think “fairness”, “objectivity”, “transparency”, “HL is somewhat well-known”, etc. are valid concerns. The claims “Legendre trivializes the problem too”, “HL is USAMO 2/5 difficulty”, and “you don’t understand ZFC axioms” are completely ridiculous, in the sense that if someone said these things I would think they were joking. I think this is why users on AoPS are making fun of you.

      Like

      • Sorry, I thought grading took place on the weekend and finished.

        I personally don’t think I’m trolling; I think that I’m making actual points and either I’m horribly wording them or people are reading them too fast and not understanding them, maybe people have very different habits on the internet, as internet certainly trains people to think fast but not deeply. I’m going to add that I’m posting a lot of this thing because it’s distracting me from sleeping, and I’m just wanting to get my thoughts out so I wouldn’t have to keep thinking about it during sleep. Also, I’d like to add that my points have been called “trolling” on a different online forum because people didn’t know how to address them.

        I’m confused why this would earn a 0 in the rubric. It seems like a full solve, valid solution, assuming you define what $v_p$ is and show that the sum of floors is an integer, and show that if $v_p(x)$ is nonnegative for every $p$, then x is an integer. The only observation you need to make is $\lfloor{\frac{x}{p}}\rfloor={\frac{x-r(x,p)}{p}}$, as I said above. I don’t see what’s wrong with this solution, just say it out loud here(I don’t really care) if this is a utter fake solve. This would probably be a little over half a page, just like how long my hook length solution took after stating exactly what the hook length formula said, and rewriting the expression. If this really earns a 0 after adding what I said, then I’m not sure what to do to make sure your proof gets full score in USAMO, and also explains why I overestimate my score a lot in the practice Olympiads/past 2 USAJMOs. I’m also sure that some people knew hook length and still didn’t solve the problem with it.

        I’m not sure if you’ve read the actual paper on any bijective proof, you said “15 pages”, though most of the proof is just diagrams, definitions, and the introduction/conclusion. In my opinion, after understanding the proof of hook length, it isn’t really complicated at all. Being completely honest here, it seems like you didn’t know hook length formula before the contest, and you just quickly googled hook length formula to make your point, and your point of view was caused by Zsig getting rejected before. Also, it’s not “you don’t understand ZFC axioms”, it’s “you don’t know how to prove everything down to axioms”, as this was to address the point that you shouldn’t cite something you don’t know how to prove. The proof is also completely elementary.

        Also, I’m going to remind you that you may be accidently commenting on grading without intention, so take off all clues revealing about the actual decision.

        Like

  2. Also, I’ll like to add that another reason of my “you don’t know how to prove everything down to axioms” is that people take things for granted that they have no idea how to prove all the time, as we build off of other people’s work, so why shouldn’t we accept HLF?

    Like

  3. Also, sorry if I’m being a little mean here; I just want to get all my thoughts out so I no longer have to think about this thing.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s