What seemed to be an untractable problem involving trillions of quadrillions of compu... - far more than required to process all the data produced or collected on Earth since the beginning of times - has been reduced to something computationally feasible and even possibly quite simple. One applicant has used extremely smart ways to sample the universe of all permutations, reducing computational complexity from O(n!) to O(n). His contribution will be featured when we announce the winner. No proof or formula is yet available, but my two weaker results (in particular, the fact that q(n) is asymptotically equivalent to n^2/3) are now considered erroneous. In particular, the factor 1/3 in n^2/3 is believed to be erroneous. The correct value seems to be 3/8: this has been suggested by two candidates, one with strong arguments in favor of 3/8 versus 1/3, though we don't have a formal proof yet. I will not share answers submitted by candidates, for obvious reasons, until winners are identified.
Maxim's Permutation - The least "linear" permutation of (0, ... , 20)
Standard correlation between X and Y is 0.0458
Another great news is that we decided to offer two, rather than one award, both with the same $500 price (multiplied by 2 if you have a reverse sponsor). The reason is because I now believe that there is no finite formula to compute q(n) though I'd love to be proven wrong. If you come up with an infinite, simple series or integral or recurrence relationship for q(n), and that's the best that we can get, you'll get the first award!
The second award will be offered to someone who finds the limiting normalized distribution for either fundamental quantity T or t when c=1, defined in my paper about the new correlation. I believe t is multimodal and might be very complex, possibly with an infinite number of local maxima as n tends to infinity. By normalized distribution, I mean after an appropriate transformation so that it is not a singular distribution, just like you normalize the sample mean by removing expectation and dividing by SQRT(n) to obtain the limiting Gaussian distribution (bell curve). Is the limiting normalized distribution also a bell curve in this case? I don't think so, but my guess is based on nothing - just gut feelings. In any case, finding the limiting normalized distribution is very important for business applications, and you can easily get a good approximation using Monte-Carlo simulations. But we are interested in the theoretical limit distribution here, not approximations.
We will also feature insights about the geometrical shape of these extreme, weird permutations (for large n) that maximize min(u, v). One example is posted in my comment dated July 14, at 11:28pm. I'm wondering if these "least linear" permutations look like concentric circles, when n becomes large. They definitely have a pattern that make them far different from any other permutations.