Wow I thought IMO is in August. Is that a sign showing high school math is no longer in my range?
Q1. I don't expect anyone else to notice that floor function related problems is one of the most frequent type of questions appearing on this site but this is indeed a fact, so naturally I like this question a lot.
The integral case is clear: $\sum i\alpha = \alpha n(n+1)/2$, so it works for even integral $\alpha$ but not odd -- note that it must hold for all $n$. Now what about the decimal case? Well, notice that there are $n$ floor functions which means the summands is at most $n$ away from $\alpha n(n+1)/2$. If we choose $n$ so that $\alpha (n+1)/2 \approx m $ is almost an integer -- some fractional approximation here -- we can show that
$|mn - \sum [i\alpha]|\leq |mn - \alpha n(n+1)/2| + |\sum (i\alpha - [i\alpha])| \leq \varepsilon + (n-1/2)$.
Scrolling through the AoPS solutions I feel like my approach is overly analytical (which again, is natural), because it is actually easy to find an explicit $n$ for that.
Q2. Oh...number theory that I can solve. It is fun that both Q1 and Q2 contain conditions to hold for all large enough parameters, then the key is to pick the critical number that actually works.
This is a nicely constructed question, but the "key" is clear when the motivation is grabbed: you want to reduce the power into something $n$-irrelevant. There are a few choices like reducing it to (1) power one but that is trivial (2) power zero which does not help... and (3) power minus 1. In that case we are looking at $(1/a+b, 1/b+a)$ which gives a common denominator of $ab+1$ where a nice characterization arises from here.
Many solutions started immediately proceed to show that $ab+1$ is a power of 2. It works of course but only in the refined final answer. To me it is still easier to start from the traditional Archimedean approach.
Consider a simpler version where $(a,b) = 1$. The key step is to notice that we can actually tweek the gcd terms as follows:
$(a^n + b, b^n + a) = (a^{n+1}+ab, b^n+a) = (a^{n+1}+ab, b^{n+1}+ab)$.
And now, the terms are ready to be subtracted each other:
$(a^{n+1}+ab, b^{n+1}+ab) = (a^{n+1}-b^{n+1}, b^{n+1}+ab)$.
Suppose the above equals $g$ for large enough $n$ and $g$ admits a prime factor $p$. The first term implies $a=b$ mod $p$. For the second term, choosing $n+1 = 2$ mod $p-1$ gives $b^2+ab = a+b = 0$ mod $p$. Since $(a,b) = 1$ the only possibility is $p=2$ with $a,b = 1$ mod 2.
We now know that $g = 2^r$. i.e., $(a^n-b^n, b^n-ab) = 2^r$ for all large enough $n$, but that sounds counter intuitive because we could certainly expect some coincidences where the gcd is more than $2^r$, say $2^{r+1}$.
It turns out that you do not need to go very far away because mod 4 is enough. If $4\mid g$ we know that $a = b = 3$ mod 4 but then the GCD clearly oscillates between 2 and 4, so $g$ must be 1 or 2. From here the term $ab+1$ kicks in. Take $n = k\varphi (ab+1)-1$ which is of minimum 2, it follows that $ab+1=2$ and so $a=b=1$ is the only solution. The case where $(a,b)\neq 1$ is similar.
I really wonder if there is a reasonable solution without the use of $ab+1$. One possible approach is to argue mod $2^r$ for all $r$ to force $a=b=1$ mod $2^r$ for any $r$ which would lock them at $a=b=1$. Some field theory would be handy, but certainly not expected at this level.
The author says that the problem arose from a CS assignment. Although we do not observe any higher insight behind this is still an elegant number theory problem.
*Update: I suddenly realized my attempt of using alternate powers is not too bad at all. Taking $n = k\varphi (a+b)+1$ we actually reduced $a^n+b$ and $b^n+a$ to $a+b$ -- using the same argument we show that it must be a multiple of $a+b$ which is at least 2, locking $a=b=1$! Is that too clever to be correct...?
Q3. Wow, a combinatorial question hidden behind algebra. This is an interesting one and is probably the third question in a row I said that. The solution given in AoPS by mapping it on $\mathbb{N}^2$ to show boundedness hence periodicity is as elegant as you can get, and I managed to write down full solution the second I saw that. Anyone else?
Q4. Ohoho. A geometry Q1/4 means 7 less points for me.
Reading through the solutions I do have chance if I stare at the problem for 1 hour plus, but this is not going to happen right now. Complex bashing is still good up to this level of geometry questions...but what about harder ones?
Q5. I can't decide whether this is a combinatorial/game theory problem or just an algo problem, really. It lacks the taste of past questions where you find invariants/intrinsic structures that solves the problem. The question really is about finding a single, simple algorithm that works. It takes me longer to find prove lower bound than to find a solution.
It reminds me of SIMC which is also algo heavy but man this is IMO...
Q6. Functional equation is always amusing...and this time it returns stronger and harder. A family of functions based on an "OR" condition, and the question asks about a harsh character of the family. Definitely exceeds my ability to solve in a few hours, but this is something I am willing to try -- so no comment here I guess ;)
In overall I would say my solvable problems are very much to my taste and strength, but I would like to see a more balanced/classical setup.
I asked for a NT Q6 but that did not happen in 2024 either -- even worse we are hit by a truckload of "easier" NT-algebra problems. I don't know what others might think but easier NT problems are usually disappointing than anything. Q5 is a huge upset, I entirely do not expect such question in IMO.
Oh well, we will see again in 2025.
No comments:
Post a Comment