Sunday 25 September 2022

Little math update

Something that I should jot down as diary...

IMO this year was easy in the sense that Q1,2,4,5 are all classified easy under my standard. Namely, I can almost immediately (i.e. maybe 15 mins) figure out an outline that eventually works. That usually applies only to Q1, 4 and 2 occasionally, but definitely not 5.

Q1 is a nice little problem, a rather rare combinatorial question that is put up front. The key is to realize that the operation puts the number of chains into a non-increasing sequence, and the only it does not decrease if and only if you are moving the first or last chain. From here the lower bound is obvious. Then you move the last chain a cyclic shift occurs so you need at least 4 chains to force the dead loop, so you can not have k larger than quarter-to-last of 2n. Tightness of the bound follows from the same idea.

People have been realizing that no matter how messy the inequality questions are the contestants will eventually find a way to brute force it and we saw no inequality question this year again. Q2 looks like a functional equation problem but you immediately realize that inequality technique is the only way out.

When you run through positive reals so x and y on the LHS could get pretty big, forcing f to be of o(1/n). Apply the same argument when x and y are small and you know f needs to be O(1/n) close to zero. With $y/x+x/y \geq 2$ in mind, it is almost obvious that$ f(x)=1/x$ is probably the only answer unless there exists some galaxy brain functions. 

The proof though not super hard, is still something that barely meets (or misses) the standard of Q2 which requires non-obvious AM-GM. A bit unfortunate though I think the most direct solution involved perturbation where inequality applies to a point and its neighborhood. Some may not be happy with the calculus flavor in it.

Q4 is geometry so nothing to comment about but it is...a Q4 and as hard as it should be.

I am fairly surprised for Q5 to be this easy like almost shocked. Prime power chasing gives you reasonable bound like 10 on the factorial. After that an average high school Olympiad contestant can do that. 

As usual Q3 and 6 are a bit too hot to attempt, but 3 is really elegant in my eyes.


I didn't cover Simon Marais last year as well and the next one is coming. If you are reading this and is a current undergraduate in one of the participating school you should really give it a go!

My comment to the overall design of the problem set still stands: the first three are always too easy and the fourth is impossible. In other words, only one question out of four (Q3) makes sense. This year though they make Q4 a bit more approachable which is a nice start.

My focus is on B3 though:

(SM2021 B3) Find all real functions f that satisfy the following:
1) The function f is Riemann integrable over all finite real intervals. and
2) For all real x and positive integer n we have 
$$f(x) = \int ^{x+1/n}_{x-1/n}f(t) dt.$$
The solution is of course linear functions. To prove it the first step is proving the continuity of the function which should be the must take step without any doubt. But then the rest of the official solution triggered me to think of something else.

It is the easiest to prove linearity by showing that the derivative is constant, or that the second derivative is zero. But then you need differentiability. There are two ways to prove differentiability: one is the first definition and the other is by FToC. First definition might be out of reach because condition (2) is for integer n but not for large enough positive reals, then there may be technical problem when you take the limit to zero.

The official solution uses FToC and writes f as a sum of its integral F, and hence is differentiable. From there it repeats and show that f'' = 0 showing that f must be linear which indeed satisfies the conditions.

But are there any ways to prove linearity without using derivatives? Specifically, are there any ways to replace the condition f'' = 0? The answer is convexity.

If we define a function f to be convex in (a,b) if $f(x) < f(a) + (x-a)(f(b)-f(a))/(b-a)$ for all $a<x<b$. Obviously if it is convex on an interval then it is convex on any of its subintervals. One can then argue that condition (2) fails for x in any convex interal. Eventually f cannot be convex at any point. Similarly f cannot be concave at any point.

That forces the equality $$\frac{f(x)-f(a)}{x-a} = \frac{f(b)-f(a)}{b-a}$$ which gives linearity (...or differentiability if you like but we don't need that already).

There is a technical problem though. We cannot exclude functions that the intersection between the function and the line between $(a, f(a))$ and $(b, f(b))$ being dense on the line for every real a and b. If we know differentiability then this is immediate (in the official solution the first derivative is obvious -- try it yourself!). Again, any solution that completely avoids differentiability? I am not so sure.

This is what I got during my bath. In 15 minutes, a lot longer than usual. 

No comments:

Post a Comment