Blog | EGMO 2018http://www.egmo2018.org/blog/BlogenEGMOEGMO CountriesEnglishFlorenceGender IssuesIMOItalianoMy EgmoOlimpiadiProblem solvingWomen in Maths beyond StereotypesTue, 20 Feb 2018 10:34:39 +0000Thinking Out Loud – EGMO 2015 Problem 4http://www.egmo2018.org/blog/EGMO2015-P4/<p>
<script type="text/x-mathjax-config">// <![CDATA[
MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}
});
// ]]></script>
</p>
<blockquote>
<p><strong>EGMO 2015, Problem 4</strong>. Determine whether there exists an infinite sequence $a_1, a_2, a_3, \dots$ of positive integers which satisfies the equality \[a_{n+2}=a_{n+1}+\sqrt{a_{n+1}+a_{n}} \] for every positive integer $n$.</p>
</blockquote>
<p>My first thought is that these numbers grow, but not too quickly: roughly speaking, since $a_n < a_{n+1}$, one has $a_{n+2} \leq \sqrt{a_n}(\sqrt{a_n} + \sqrt{2}) < (\sqrt{a_n}+1)^2$. So in particular setting $b_n=\sqrt{a_n}$ I find that $b_{n+1} \leq b_n+1$. The reason I'm interested in this is that $a_{n+1}+a_n$ needs to be a square for every $n$ (so it grows fast!); maybe let's give this square a name: $c_n^2=a_{n+1}+a_n$. Now clearly $c_{n+1} \geq c_n + 1$, so the hope is that comparing the two inequalities will give a contradiction. Let's see: in deriving the first one I haven't been very careful, so I might as well do some rough estimates on the second one too. For example, $c_n^2 \leq 2a_{n+1}$, so $a_{n+1} \geq \frac{c_n^2}{2} \geq \frac{n^2}{2}$, which unfortunately is not good enough to contradict $a_n \leq n^2$ (which is what I get, at least as order of magnitude, from $b_{n+1} \leq b_n + 1$).</p>
<p><strong>Long, more honest version</strong><br/>Ok, I was hoping for too much, clearly. Let's be somewhat more precise. The same computation as before gives $a_{n+1} \leq (\sqrt{a_n} + \frac{\sqrt{2}}{2})^2$, so $b_n \leq \frac{\sqrt{2}n}{2}$ and $a_n \leq \frac{n^2}{2}$. Uhm... this is <em>exactly</em> the same as the upper bound, so now I need to do things properly. It's not clear that it will work, though: the precise additive constants in the inequalities will be important. Let's see: the true versions of the rough inequalities are<br/>\[<br/>b_n \leq b_0 + \frac{n\sqrt{2}}{2} \Rightarrow a_n \leq \frac{n^2}{2} + \sqrt{2a_0}n + a_0<br/>\]<br/>and<br/>\[<br/>c_n \geq c_0+n =\sqrt{a_0+a_1}+n \Rightarrow a_{n+1} \geq \frac{c_n^2}{2} = \frac{n^2+2\sqrt{a_0+a_1}n+(a_0+a_1)}{2}<br/>\]<br/>which maybe works? That is, maybe these inequality give a contradiction? Replacing $n+1$ by $n$ and comparing the upper and lower bound for $a_n$, the terms $n^2/2$ cancel out, and we find that<br/>\[<br/>\sqrt{2a_0}n + a_0 \geq \frac{-2n+1+2\sqrt{a_0+a_1}(n-1)+(a_0+a_1)}{2},<br/>\]<br/>which gives a contradiction for $n$ large provided that $\sqrt{2a_0} < \sqrt{a_0+a_1}-1$. But this needs not be true, if $a_1$ is smaller than $a_0$. Which makes me realize: my inequalities are not even technically correct, because I've assumed $a_n$ to be increasing, which is only true from $a_2$ onward! This is getting way too complicated, I think I just want a better lower bound on $c_n$ or a better upper bound on $a_n$.</p>
<p><strong>Abridged version – also continuation of the long (and true) version.</strong><br/>Do I know anything more about these numbers $a_n, c_n$? Something that sticks out is that there are parity conditions, namely $a_{n+1}$ has the same parity as $a_{n-1}$. And this implies that the parity of $c_n^2 = a_n+a_{n-1}$ is constant. Ah, this is great, because it gives $c_{n+1} \geq c_n+2$, and not just $+1$! Is this quite true? I guess $a_n > a_{n-1}$ is true at least for $n \geq 2$, so $c_{n}$ is increasing for $n \geq 1$. So to be on the safe side let's say $c_n \geq (c_0+c_1)+2(n-1)$. So for $n$ 'large' (which probably just means $2$ or more) $a_{n+1} \geq \frac{c_n^2}{2} \geq 2n^2 + (\text{stuff that is either constant or linear in }n)$, while we know $a_n \leq (\text{constant} + \frac{\sqrt{2}}{2}n)^2 \leq \frac{n^2}{2} + (\text{stuff which is constant or linear in }n)$, which is clearly a contradiction for $n$ large. Done: there's no such sequence $a_n$!</p>
<p></p>
<p><strong>Some additional comments</strong></p>
<p>I'm sure there are a number of different solutions to this problem, but this one is instructive at least because it's an instance (yet another one!) of the general principle that in many number-theoretical questions one needs to combine congruences and inequalities to get to the solution. Furthermore, this solution came naturally to me, at least in the sense that a very common technique to prove that a certain expression is not a square is to show that it lies strictly between two consecutive squares; while this is not what I ended up doing, such an idea would have required good upper and lower bounds on $a_{n+1}+a_{n}$, so I thought it couldn't hurt to start with those. And then, sometimes, you get lucky...</p>Davide LombardoTue, 20 Feb 2018 10:34:39 +0000http://www.egmo2018.org/blog/EGMO2015-P4/Thinking Out Loud – EGMO 2014 Problem 3http://www.egmo2018.org/blog/EGMO2014-P3/<p>
<script type="text/x-mathjax-config">// <![CDATA[
MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}
});
// ]]></script>
</p>
<p>It is a truth universally acknowledged that mathematicians like to state the obvious. As further confirmation of this well-established fact, it was recently pointed out to me that my 'thinking out loud' posts cannot rival with Marcello's. Now, what is one supposed to do in the face of this self-evident truth? Certainly not get offended – how can you get offended by something you agree with? So, maybe panic? Stop making these posts, to everyone's relief? After some deliberation, I decided that what the comment <em>really</em> meant was that I should strive to be more creative in my writing. I cannot guarentee that I succeeded, but it is a fact that I ended up composing an <em>even longer</em> post than usual. So read ahead at your own peril, you've been warned: long-winded ramblings follow.</p>
<blockquote>
<p><strong>EGMO 2014, Problem 3</strong>. We denote the number of positive divisors of a positive integer $m$ by $d(m)$ and the number of distinct prime divisors of $m$ by $\omega(m)$. Let $k$ be a positive integer. Prove that there exist infinitely many positive integers $n$ such that $\omega(n) = k$ and $d(n)$ does not divide $d(a^2+b^2)$ for any positive integers $a, b$ satisfying $a + b = n$.</p>
</blockquote>
<p>Now that's an ugly statement if I ever saw one! When a problem is this hideous, it often means that it's been built around a solution, instead of the other way around. And this should make it easier: I suspect that the requirement of having precisely $k$ prime factors might be there just to obfuscate what the problem is really about. Can I solve it with just one prime factor, that is, $\omega(n)=1$?</p>
<p>Let's see: I need to take $n=p^r$ for some prime $p$ and a positive integer $r$. Also I want $d(n)=r+1$ <em>not</em> to divide something, so maybe taking $r+1=q$ to be a large prime could be a good idea. Let's do just that. As for $p$, I don't see any good reason why one choice should be better than another, except that 2 (while one might argue that deep down $2$ is not <em>really</em> a prime number – come on, it's <em>even</em>!) tends to have stranger properties than other primes, so let's take $p=2$. If this doesn't work I'll try $p=3$, but I refuse to believe that I need to take $p=32003$.</p>
<p>So suppose $n=2^{q-1}$, $a+b=n=2^{q-1}$, and $d(n)=q$ divides $d(a^2+b^2)$. Now, where does $d(a^2+b^2)$ take its prime factor $q$ from? From some prime power $p^{q-1}$, or rather, $p^{kq-1}$. But this is a huge number: let's find out how big it really is. We have $a^2+b^2 \leq n^2 = 2^{2q-2}$, so $p^{kq-1} \leq 4^{q-1}$. This definitely cannot happen for $p \geq 5$. What happens for $p=2,3$? Assuming that $q$ is not too small (...to be made precise later), $p^{kq-1} \leq 4^{q-1}$ implies $k=1$. But is it possible that $3^{q-1} \mid a^2+b^2$? A well-known lemma (ok, I must confess – I'm a number theorist by trade. All the same, this problem is still not the most appealing one I've come across in my life) says that in this case $3^{(q-1)/2}$ divides both $a$ and $b$ – and if $(q-1)/2$ is not an integer, then probably I need to round it up. (Do I? Let's see: the basic lemma is that if $3 \mid a^2+b^2$, then $3 \mid a$ – because $3$ is $3 \bmod 4$. So for $q=1$... ehr, ok, I was mistaken: $a,b$ are divisible by $3^{\lceil q/2 \rceil}$. Well whatever, they are divisible by some large power of $3$). So anyway, if $3^{q-1}$ divides $a^2+b^2$, then $a,b$ are divisible by something like $3^{q/2}$. In this case $a+b \geq 2 \cdot 3^{q/2}$, which I was hoping to be larger than $2^{q-1}$, but that doesn't seem to be the case. Oh but wait, I'm being really obtuse: if $3^{\text{something}}$ divides both $a$ and $b$, then $3$ divides $a+b=n=2^{q-1}$, which is more than a little absurd. Ok, so the only possibility is $a^2+b^2 = 2^{kq-1} \times \text{something}$ with $k=1$ or maybe $2$. Can $k=2$ really happen? If I write down the obvious inequalities I find\[2^{2q-2} = n^2 \geq a^2+b^2 \geq 2^{2q-1}\]so no, that does not happen. Fine. Suppose $a^2+b^2=2^{q-1} \times \text{something}$: this would be a little surprising, because the powers of 2 need to recombine in very interesting ways to ensure that the same power of 2 divides both $n$ and $a^2+b^2$ with $a+b=n$. Can I turn this philosophy into an actual statement? Write $a=2^{m} x, b=2^{n} y$ and\[a^2+b^2 = 2^{2m} x^2 + 2^{2n} y^2.\]If (say) $x < y$ then I can collect a term $2^{2m}$ and find that $a^2+b^2 = 2^{2m}(x^2+2^{2n-2m}y^2)$, so the largest power of $2$ that divides $a^2+b^2$ is $2^{2m}$. It should also be $2^{q-1}$, however, so $2m=q-1$ and $n$ is larger. What's the other condition? $a+b=n$. But then no, the largest power of $2$ in $a+b$ is going to be $2^m$ (same argument), and $2^m = 2^{(q-1)/2} < 2^{q-1}$. Ok, this seems to do it, right? Ah no, I'm forgetting one case: what happens if $m=n$? Let me see again,\[a^2+b^2 = 2^{2m} x^2 + 2^{2n} y^2 = 2^{2m} (x^2 + y^2)\]with $x$ and $y$ odd. So $x^2+y^2 \equiv 2 \pmod 4$, and $a^2+b^2$ is divisible exactly by $2^{2m+1}$. So this time $2m+1=q-1$, which however cannot happen because $q$ is odd. Ok, that was not so hard... but boy am I glad that I'm writing this down! I think I've already forgotten 80% of what I've done. I'm also slightly worried at having used this lemma $3 \mid a^2+b^2 \Rightarrow 3 \mid a, b$. Is this going to generalize nicely when I take $n$ with $k$ prime factors?</p>
<p>Ok, let's stop for a sec and think before trying the general case – what have I used so far?</p>
<ul>
<li>That $n$ is small: this seems to be crucial, so I want to make $n$ very small.</li>
<li>On the other hand, I need (maybe? Or maybe I'm just on the wrong track altogether?) a prime with a largish exponent, in order to fabricate a largish prime in $d(n)$.</li>
<li>I've also used that $n$ is not divisible by $3$. I have no clue if this is going to be necessary in general, but it might be.</li>
<li>Putting everything together, I think that I should try to take $n = 2^{q-1} p_2 p_3 \cdots p_k$ where the $p_i$'s are distinct primes that as small as possible (which might mean either $p_2=3, p_3=5, p_4=7, ...$ or $p_2=5, p_3=7, p_4=11, ...$, depending on whether I want to enforce the condition $3 \nmid n$ or not).</li>
</ul>
<p>Ok, let's get started. Have I already mentioned that I don't like this problem? I don't like this problem. So, $n=2^{q-1} p_2 p_3 \cdots p_k$, $a+b=n$, and $d(a^2+b^2)$ is a multiple of $q$. Can this really happen? It means that $a^2+b^2$ (of order roughly $n^2$...) has a prime power factor of the form $r^{kq-1}$ with $r$ prime. Now, let's say something which is a bit false but philosophically very true: if $q$ is ginormous, then $n^2$ looks very much like $2^{2q-2}$. Ok, not really, but let's say that it's sort of true on a logarithmic scale, which is what I care about at the moment (because I'm looking at exponents). So anyway, mathematics, not philosophy:\[a^2+b^2 \leq n^2 \leq 2^{2q-2} (p_2\cdots p_k)^2,\]and on the other hand $r^{kq-1}$ divides $a^2+b^2$, so\begin{equation}\tag{1}\label{eq:ineq}r^{kq-1} \leq 2^{2q-2} (p_2\cdots p_k)^2\end{equation}If $r$ is at least 5, well, then we obtain an inequality of the form\[5^{q-1} \leq 4^{q-1} (p_2\cdots p_k)^2\]which (since the product $p_2 \cdots p_k$ is fixed... ok, not yet, but it will be fixed eventually) is impossible when $q$ is large. So $r$ is either 2 or 3. This is good, because it's the same conclusion we had in the $\omega(n)=1$ case. I know how to rule out 3: it suffices to take $(n,3)=1$. So we're saying $a^2+b^2=2^{kq-1} (\text{something})$, and \eqref{eq:ineq} gives $k \leq 2$. That IS unfortunate: before we had $k=1$ automatically. Ugh, this means one extra case. Fine, let's do it. Actually no, first let's check that the case $k=1$ generalizes. And by the way I've just realized that I'm such an idiot, I'm using $k$ both for $\omega(n)$ and for the exponent of $r$ in $a^2+b^2$. I'll need to fix this when I write an actual solution. Anyway: suppose $a+b=n=2^{q-1}(p_2\ldots p_k)$ and $a^2+b^2=2^{q-1}(\text{something})$. If $v_2(a) \neq v_2(b)$<a href="http://www.egmo2018.org/blog/author/darkcrystal/feeds/rss/#foot1">*</a> we have $q-1=v_2(a^2+b^2)=2 \min\{v_2(a),v_2(b)\}$ and $v_2(a+b)=\min\{v_2(a),v_2(b)\}$, which leads to a contradiction, just like before. What if $v_2(a)=v_2(b)$? Then $q-1=v_2(a^2+b^2)=2v_2(a)+1$, which is impossible because $q$ is odd. Good, this also works just as before, and leaves me with the case $a+b=n=2^{q-1}(p_2\ldots p_k)$ and $a^2+b^2=2^{2q-1}(\text{something})$. This $2$-adic valuation business is working so well that I think I should probably try using it on the missing case as well. I'll need to deal with the same two cases as above:</p>
<ul>
<li>$v_2(a) \neq v_2(b)$: then $2q-1=v_2(a^2+b^2)=2\min\{v_2(a),v_2(b)\}$. This is odd = even, so nope!</li>
<li>$v_2(a)=v_2(b)$: then $2q-1 = v_2(a^2+b^2) = 2v_2(a)+1$. This is not a contradiction per se, it just gives $v_2(a)=v_2(b)=q-1$. Hopefully this will contradict $a+b=n$, otherwise I'll throw the laptop out of the window in a fit of frustration... So: is it possible that $a+b=n$ with $v_2(a)=v_2(b)=v_2(n)=q-1$? If I write\[a+b = 2^{q-1}x + 2^{q-1} y = 2^{q-1}(x+y) = n...\](at this point I've stared at this equation for more than I care to admit, until...) I AM A TOTAL MORON. $x$ and $y$ are odd, so $x+y$ is even, and $v_2(a+b)=v_2(2^{q-1}(x+y))$ is at least $q$, contradiction.</li>
</ul>
<p>And with this we're finally done. So, to summarise (and write a decent proof in which we try to hide all the ugliness above)</p>
<ul>
<li>We want to construct such an $n$ with $\omega(n)=k$. Take $n=2^{q-1} (p_2 \cdots p_k)$, where $p_2,\ldots,p_k$ are the smallest $k-1$ primes larger than $3$, and $q$ is a prime so large that $5^{q-1} > 4^{q-1} (p_2\ldots p_k)^2$.</li>
<li>In this situation, $d(n)$ is divisible by $q$. We want to show that $a+b=n$ implies $d(n) \nmid d(a^2+b^2)$, so it suffices to show that $q \nmid d(a^2+b^2)$.</li>
<li>Suppose $a+b=n$ are such that $q \mid d(a^2+b^2)$. Then there exist a prime $r$ and an integer (which is most definitely not called $k$, but say $e$) such that $r^{eq-1} \mid a^2+b^2$. Since $a^2+b^2 \leq n^2 = 4^{q-1} (p_2 \ldots p_k)^2 < 5^{q-1}$, this implies that we are in one of the following three situations: $r=2, e=1$; $r=2, e=2$; $r=3, e=1$.</li>
<li>if $r=3$, then $3 \mid a^2+b^2$, which implies $3 \mid a, b$ (in a competition I would write down a proof for this lemma), which in turn implies $3 \mid a+b = n$, contradiction.</li>
<li>if $r=2$, let $A=v_2(a), B=v_2(b)$ [notice that these were called respectively $m$ and $n$ above. Using $n$ here is maybe not such a great idea...]. Then $v_2(a^2+b^2)=eq-1$, and there are two cases:
<ul>
<li>$A \neq B$: then $v_2(a^2+b^2)=2 \min\{A,B\}$, which is even, so $e=1$. But then $q-1=v_2(n)=v_2(a+b) = \min\{A,B\} = \frac{1}{2} v_2(a^2+b^2)=\frac{q-1}{2}$, contradiction.</li>
<li>$A=B$: then $eq-1=v_2(a^2+b^2)=2A+1$, so $e=2$ for parity reasons. But then $q-1=v_2(n) = v_2(a+b) \geq A+1=q$, contradiction.</li>
</ul>
</li>
<li>Since we reach a contradiction in every case, this shows that there are no pairs of positive integers $(a,b)$ such that $a+b=n$ and $d(n) \mid (a^2+b^2)$, as required.</li>
</ul>
<h5><strong>Closing remarks</strong></h5>
<p>$p$-adic valuations are your friends! Especially in a problem like this, where (almost) the only relevant property of $n$ and $a^2+b^2$ is their prime factorisation, you should definitely think in terms of valuations. And if you are not familiar with the notation $v_p(\cdot)$ and its basic properties (one above all: $v_p(x+y) \geq \min\{v_p(x), v_p(y)\}$, with equality whenever $v_p(x) \neq v_p(y)$), you may want to read up on it (one of many possible starting points: <a href="http://s3.amazonaws.com/aops-cdn.artofproblemsolving.com/resources/articles/olympiad-number-theory.pdf">http://s3.amazonaws.com/aops-cdn.artofproblemsolving.com/resources/articles/olympiad-number-theory.pdf</a>).</p>
<p>A final word of wisdom: powerful as they are, <strong>congruences</strong> (or $p$-adic valuations, in this case) <strong>can't do everything!</strong> As one of the organisers of our national Mathematical Olympiad likes to say, any good number theory problem involves both congruences and inequalities. This should be apparent in the problem we just solved!</p>
<p><a id="foot1"></a></p>
<p><strong>*</strong>here $v_2(x)$ is the exponent of $2$ in the factorisation of $x$: it's called the<em> $2$-adic valuation of $x$.</em></p>Davide LombardoTue, 13 Feb 2018 12:47:37 +0000http://www.egmo2018.org/blog/EGMO2014-P3/EGMOOlimpiadiProblem solvingThinking Out Loud – EGMO 2013 Problem 4http://www.egmo2018.org/blog/EGMO2013-P4/<p>
<script type="text/x-mathjax-config">// <![CDATA[
MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}
});
// ]]></script>
</p>
<p>by <strong>Davide Lombardo</strong></p>
<blockquote>
<p><strong>EGMO 2013, problem 4</strong>. Find all positive integers $a$ and $b$ for which there are three consecutive integers at which the polynomial \[P(n)=\frac{n^5+a}{b}\] takes integer values.</p>
</blockquote>
<p>The first thing I notice is that $b$ cannot be even, because the numbers $n^5+a$ and $(n+1)^5+a$ have different parity, so they can't both be divisible by an even number.</p>
<p>This being said, what is this problem really about? What we're being asked to study is really a congruence in disguise, because the condition can be rewritten as<br/>\[<br/>\begin{cases}<br/>(n-1)^5+a \equiv 0 \pmod b\\<br/>n^5+a \equiv 0 \pmod b\\<br/>(n+1)^5+a \equiv 0 \pmod b<br/>\end{cases}<br/>\]<br/>Now by the Chinese Remainder Theorem I probably only care about $b$ being the power of a prime, because if I can solve these congruences for two (powers of) primes then I can also solve them modulo the product. So let's say that $b$ is prime for now, I'll worry about powers later. Also I notice that $a$ is a bit of a red herring: if I rewrite the congruences as<br/>\[<br/>\begin{cases}<br/>a \equiv -n^5 \pmod b \\<br/>(n-1)^5-n^5 \equiv 0 \pmod b\\<br/>(n+1)^5-n^5 \equiv 0 \pmod b<br/>\end{cases}<br/>\]<br/>the truth seems to be that whenever I can find an $n$ that satisfies the last two equations, then I just choose $a$ appropriately from the first. So whatever, let's throw out the first equation altogether for now, and just work with<br/>\[<br/>\begin{cases}<br/>(n-1)^5-n^5 \equiv 0 \pmod b\\<br/>(n+1)^5-n^5 \equiv 0 \pmod b<br/>\end{cases}<br/>\]<br/>Now I'm slightly confused: it's clear that (given $b$) the first equation only has finitely many solutions, and so does the second. But how do I combine them? Oh, maybe the idea is something like "well, these equations each have some solution, but the solutions to the first and the solutions to the second are almost always all distinct modulo $b$". Or are they? Maybe there's an infinite class of $b$ for which these really have common solutions... unclear<strong><a href="http://www.egmo2018.org/blog/author/darkcrystal/feeds/rss/#footnote">*</a></strong>. While I think about how to proceed, I notice that $b$ cannot divide $n$, nor $n \pm 1$, because otherwise the congruences fail miserably for obvious reasons. I should probably rewrite the congruences again as<br/>\[<br/>(n-1)^5 \equiv n^5 \equiv (n+1)^5 \pmod b<br/>\]<br/>Now that I see them this way, I'm reminded of the fact that taking fifth powers is injective modulo 5 because of Fermat's little theorem, so $b$ cannot be 5. That is, if $b=5$ we have $(n-1)^5 \equiv n-1 \pmod 5$, $n^5 \equiv n \pmod 5$, $(n+1)^5 \equiv n+1 \pmod 5$ and therefore<br/>\[<br/>n-1 \equiv n \equiv n+1 \pmod 5,<br/>\]<br/>contradiction.<br/>Actually I know more: taking 5th powers is injective modulo $b$ (a prime) whenever $5$ does not divide $b-1$. Oh, that sounds like an almost interesting fact: if $b$ is not 1 mod 5, then I also obtain $n-1 \equiv n \equiv n+1$, which can hardly happen. So $b \equiv 1 \pmod 5$, that's something. And now I'm afraid I really have to compute something, don't I? The prime $b$ divides the 2 numbers <br/>\[<br/>(n+1)^5-n^5, (n-1)^5-n^5<br/>\]<br/>so I guess I can try to run a "Euclidean algorithm-style" kind of computation to reduce the powers of $n$ involved. Let's see: $\left( (n+1)^5-n^5, (n-1)^5-n^5 \right)$ is the same as<br/>\[<br/>\left( 1 + 5 n + 10 n^2 + 10 n^3 + 5 n^4, -1 + 5 n - 10 n^2 + 10 n^3 - 5 n^4 \right)<br/>\]<br/>so clearly the very first thing I want to do is sum these expressions to get rid of the $n^4$:<br/>\[<br/>\left( 1 + 5 n + 10 n^2 + 10 n^3 + 5 n^4, 10 n + 20 n^3 \right).<br/>\]<br/>Oh, that's actually nice. I can also throw out a factor of 10 from $10n+20n^3$ (because I know that $b$ is neither 2 nor 5) and a factor of $n$ (because I know that $b$ cannot divide $n$), so I end up with having to compute<br/>\[<br/>\left( 5 n^4 + 10 n^3+10 n^2+5n+1, 2 n^2+1 \right)<br/>\]<br/>The unfortunate detail is that I cannot divide $5 n^4 + 10 n^3+10 n^2+5n+1$ by $2n^2+1$ as polynomials, because the leading terms do not divide each other. But that's not really a problem, let me double the first polynomial (which I can do for free, since $2n^2+1$ is odd anyway) and try again: I want to compute<br/>\[<br/>\left( 2(5 n^4 + 10 n^3+10 n^2+5n+1), 2 n^2+1 \right).<br/>\]<br/>Ugh, long polynomial division. Never could abide those, but fine, let's do it: after some computations on a separate sheet of paper, I find<br/>\[<br/>2(5 n^4 + 10 n^3+10 n^2+5n+1) = (2n^2+1)(5n^2+10n)+15n^2+2<br/>\]<br/>Ok, so (subtracting a multiple of the second polynomial from the first) I now have that if $b$ divides $(n+1)^5-n^5$ and $n^5-(n-1)^5$, then $b$ divides<br/>\[<br/>(15n^2+2,2n^2+1)<br/>\]<br/>and I suppose I should do one more step and compute<br/>\[<br/>\begin{aligned}<br/>(15n^2+2,2n^2+1) & = (30n^2+4,2n^2+1) \\<br/>& = (30n^2+4-15(2n^2+1),2n^2+1)\\<br/>& =(-11,2n^2+1).<br/>\end{aligned}<br/>\]<br/>But this is excellent, 11 is an actual number (as opposed to a polynomial in $n$)! So who cares about the congruences and everything else I said at the beginning: if $b$ divides both $(n+1)^5-n^5$ and $(n-1)^5-n^5$, then $(b,10n)=1$ and computing the GCD shows that $b$ divides $(11,2n^2+1)$. So $b$ is either 1 or 11. I guess when $b=1$ there is not much else to say (I can just take $a$ to be whatever I like), so I only need to deal with $b=11$.<br/>In this case I know that I have to choose $a \equiv -n^5 \pmod{11}$ (we said that at the beginning, right?), and also -- since I'm assuming that $b=11$ divides $(11,2n^2+1)$ -- I know that $2n^2+1 \equiv 0 \pmod{11}$. This is a congruence I can do: if I multiply by 5 it becomes $10n^2+5 \equiv 0 \pmod{11}$, that is $n^2 \equiv 5 \pmod{11}$. Since $4^2 \equiv 16 \equiv 5 \pmod{11}$, the only solutions are $n \equiv \pm 4 \pmod {11}$. And so $a \equiv -n^5 \equiv -(\pm 4)^5 \equiv \mp 2^{10} \equiv \mp 1 \pmod {11}$. Mmmh, I realize I haven't done a single example (in my defense, I wouldn't have found 11 by examples...), so let's check that I haven't gotten anything wrong: I'm claiming that I can take $a \equiv -1 \pmod {11}$ and $n \equiv 4 \pmod{11}$. Is it true that $3^5-1, 4^5-1$ and $5^5 - 1$ are all 0 modulo 11? Well certainly $4^5 \equiv 2^{10} \equiv 1 \pmod{11}$ by Fermat's little theorem, and $5^5 \equiv (4^2)^5 \equiv 4^{10} \equiv 1 \pmod{11}$ for the same reason; also $3^5 \equiv 9 \cdot 9 \cdot 3 \equiv 12 \equiv 1 \pmod{11}$, so yeah, it seems to work out. Let's also do $a \equiv 1 \pmod{11}$ and $n \equiv -4 \pmod{11}$: we need to check that $-5^5 \equiv -1 \pmod{11}$, $-4^5 \equiv -1 \pmod{11}$, $-3^5 \equiv -1 \pmod{11}$, and these are the same congruences as before up to a sign, so they also work out.<br/>Conclusion:<br/>\[<br/>\boxed{b=1, a \in \mathbb{Z}_{>0} \text{ or } b=11, a \equiv \pm 1 \pmod{11}}<br/>\]</p>
<p><strong>Second solution.</strong> I also sketch a less elementary (but somewhat more direct, in my opinion) solution to this problem. The idea is that from the congruences<br/>\[<br/>\begin{cases}<br/>(n+1)^5 \equiv n^5 \pmod{b}\\<br/>(n-1)^5 \equiv n^5 \pmod{b}<br/>\end{cases}<br/>\]<br/>we see that $\frac{n+1}{n}$, $\frac{n-1}{n}$ are (primitive and distinct) fifth roots of unity modulo $b$. Call $t:=1/n$; then $1+t$ and $1-t$ are fifth roots of unity, and so are $(1+t)(1-t)=1-t^2$, $(1+t)^2=1+2t+t^2$ and $(1-t)^2=1-2t+t^2$. These are five 5th roots of unity, and all of them are primitive (because none of them is equal to 1!), so 2 of them are equal modulo $b$. We can remove 1 from each of them and divide by $t \neq 0$, and we find that two of the following 5 numbers are equal modulo $b$:<br/>\[<br/>1, -1, -t, 2+t, -2+t<br/>\]<br/>Since $t \not \equiv \pm 1 \pmod b$, it's easy to see that $t \equiv \pm 3 \pmod{b}$. Since $b$ divides both $(1+t)^5-1 \equiv (1+1/n)^5-1$ and $(1-t)^5-1 \equiv (1-1/n)^5 -1$, we find that $b$ divides either $(4^5-1,(-2)^5-1)=(1023,33)=33$ or $((-2)^5-1,4^5-1)=33$. Since $b$ cannot have a factor of 3 (recall the observation in the first solution that the prime factors of $b$ are congruent to 1 modulo 5!), this gives that $b$ divides 11.</p>
<p><a id="footnote"></a></p>
<p><strong>*</strong> For the really committed readers: there is an advanced tool to answer this sort of question, called the <a href="https://en.wikipedia.org/wiki/Resultant"><em>resultant</em></a>, which shows that we only need to care about $b$ being a power of $2$, $5$ or $11$. But during a competition, and without a computer, I probably wouldn't have been able to compute resultants...</p>Davide LombardoTue, 09 Jan 2018 10:13:34 +0000http://www.egmo2018.org/blog/EGMO2013-P4/EGMOOlimpiadiProblem solvingThinking Out Loud – EGMO 2015 Problem 5http://www.egmo2018.org/blog/thinking-out-loud-egmo-2015-problem-5/<p>
<script type="text/x-mathjax-config">// <![CDATA[
MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}
});
// ]]></script>
</p>
<p>by <strong>Davide Lombardo</strong></p>
<blockquote>
<p><strong>EGMO 2015, Problem 5</strong>. Let $m, n$ be positive integers with $m > 1$. Anastasia partitions the integers $1, 2, \dots , 2m$ into $m$ pairs. Boris then chooses one integer from each pair and finds the sum of these chosen integers.<br/>Prove that Anastasia can select the pairs so that Boris cannot make his sum equal to $n.$</p>
</blockquote>
<p>Well, Boris' sum lies between $1+2+\cdots+m = \frac{m(m+1)}{2}$ and $(m+1)+(m+2)+\cdots+(m+m) = m^2 + \frac{m(m+1)}{2}$; so any value of $n$ outside of this interval is fine, and we need to find a partition that prevents Boris from achieving a given $n$ only for $n$ in this interval. The first idea that comes to mind is to try and force Boris to do something <em>we</em> want, independently of what he may choose (as in the best conjurer's tricks). For example, the obvious partition $(1,m+1), (2,m+2), \ldots, (m,m+m)$ has the property that – no matter what Boris chooses – we know what his choice is modulo $m$: it's going to be $1,2,\ldots,m$. So with this partition poor Boris can only obtain sums that are congruent to<br/>$$1 + \cdots + m \equiv \frac{m(m+1)}{2} \pmod{m}.$$<br/>That's pretty good already: let's say that $m$ is odd, for the moment, so that $\frac{m(m+1)}{2}$ is zero modulo $m$. Then we're saying that if $n$ is not a multiple of $m$, we can just give him this partition and he'll be done for :). So this leaves us with only a few numbers to worry about, namely the multiples of $m$ in the interval $[\frac{m+1}{2} m,\frac{3m+1}{2}m]$. Wait though, I'm being way too generous with my friend Boris here: why should I let him choose all the big numbers and achieve a super-large sum? If he wants to take $2m$ he'll have to give up on $2m-1$, and likewise with $2m-2,2m-3$ etc... in other words, what happens if I offer him the other obvious partition, namely $\{1,2\}, \{3,4\}, ..., \{2m-1,2m\}$? His sum is going to be in the interval $[1+3+\cdots+(2m-1),2+4+\cdots+2m] = [m^2,m^2+m]$. Much better! So this partition ensures that he can never realise an $n \not \in [m^2,m^2+2m]$, and the one from before rules out all the multiples of $m$. Tough luck, eh, Boris? It's not looking good for you, brother... anyway: if $n \neq m^2, m^2+m$ we've won (assuming that $m$ is odd, that is). What do we do if $n=m^2$, say? What other invariant can I come up with? I've already used "size" and "residue class modulo $m$". Can I make sure that the sum is always odd, for example? This would require me to pair together numbers of the same parity (if for even just one pair Boris can choose between numbers of opposite parity then I have no control on the parity of the sum). Can I do it, even for small values of $m$? Say $m=4$: then I should try $\{1,3\},\{2,4\}$, so the sum is indeed always odd. But this probably depends on $m$ modulo 4, so I run into further trouble if $4 \mid m$.</p>
<p>Let me check: $m=4$, $\{1,5\}, \{2,6\}, \{3,7\}, \{4,8\}$. Then the sum is... well, whatever it is, this is a partition we already considered, so it cannot give me any new information (come to think about it, why did I try $m=4$ instead of $m=3$?). No, we need to find a different way.</p>
<p>While I'm thinking about this, let me work out which numbers in the interval $[m^2,m^2+m]$ I need to worry about when $m$ is even. It's those numbers $N$ such that $N \equiv \frac{m(m+1)}{2} \pmod{m}$, where $m=2k$. Then $N \equiv k(2k+1) \equiv k \pmod{2k}$, and the only such number in the interval $[m^2,m^2+m]$ seems to be $m^2+k = m^2+\frac{m}{2}$. So this is actually 'easier', at least in the sense that there's just a single number we need to make sure Boris cannot achieve.</p>
<p>This, however, does not solve the problem of how to actually stop that pesky Boris from making his sum equal to those few numbers left. To be fair, there are so few numbers I don't know how to deal with that maybe I can afford to leave Boris some choice, though I still don't want his sum to vary too wildly, at least with respect to some property (I mean: it can vary all it likes in size, so long as its residue class modulo something is fixed, for example). Maybe I can force Boris to choose between a sum that is "large", but of the wrong parity, and one that is of the correct parity, but too small to be $m^2$? This is worth a try: I should probably pair $\{1,2m\}$, and then pair the rest of the numbers so that numbers in every pair have the same parity and roughly the same size (so that, ideally, when Boris chooses between $1$ and $2m$, he either overshoots – if he picks $2m$ – or undershoots – if he picks $1$). I realize that I'm talking about over- and under-shooting and not caring about parity, but maybe parity will intervene in some mysterious way? I don't know: let's see this in action for a smallish $m$, say $m=3$. Following the recipe above, I should take $\{1,6\}; \{2,4\}; \{3,5\}$, and the numbers to avoid are $9, 9+3=12$. Let me check... this seems to work! I'm not sure whether this is just luck, though; I feel like trying another small case. Let's say $m=5$, so that the partition is $\{1,10\}, \{2,4\}, \{3,5\}, ...$. Ah. I was going to write $\{4,6\}$, but $4$ is already taken. So I need to have $\{6,8\}$... mmh, this does not sound very promising. Anyway, here is the partition:<br/>\[<br/>\{1,10\}, \{2,4\}, \{3,5\}, \{6,8\}, \{7,9\},<br/>\]<br/>and the numbers to avoid are $25$ and $25+5=30$. Darn, I can see that tiresome Boris gloating already... $10+2+3+8+7=30$. Nope, this doesn't work.</p>
<p>Going back to the idea of 'almost-forcing-Boris-to-do-something-but-not-quite', combined with 'there should be a single pair for which Boris' choice matters, and even then neither of the two choices should work (muahahaha evil laugh)', I'm eventually lead – after a significant amount of doodling, writing down partitions, noticing that they do not work, and cursing – to considering the following alternative. Let's try to fix the congruence class of the sum modulo some $M$ which is not quite $m$, but it's close enough that we can arrange most pairs to have elements that are congruent modulo $M$. In other words: let's try to force the sum to take some value modulo $M$; we'll fail, but maybe we can fail not tooo badly, so that the sum can only take <em>very few</em> values modulo $M$.</p>
<p>Natural choices are $M=m+1$ and $M=m-1$; let's try the former. The partition would then be<br/>\begin{equation}<br/>\begin{array}{cccccc}<br/>1 & 2 & 3 & \cdots & m-1 & m \\<br/>m+2 & m+3 & m+4 & \cdots & 2m & m+1;<br/>\end{array}\tag{$\star$}\label{eq:FinalPartition}<br/>\end{equation}<br/>can we finally trick Boris into making the wrong choice? Whatever he decides to do, he will end up with a sum which is either $1+2+\cdots+(m-1)+m$ or $1+2+\cdots+(m-1)+(m+1)$ modulo $m+1$. So, writing $S$ for Boris' sum, $S \equiv \frac{m(m-1)}{2} + \begin{cases} -1 \\ 0\end{cases} \pmod{m+1}$.<br/>Now the numbers we want to avoid are (let me take $m$ odd again...) $m^2+m \equiv (-1)^2-1 \equiv 0 \pmod{m+1}$ and $m^2 \equiv 1 \pmod{m+1}$, while (using that $m=2k+1$ is odd) <br/>\[<br/>S \equiv \frac{(2k+1)(2k)}{2} + \begin{cases} -1 \\ 0\end{cases} \equiv k(-1) + \begin{cases} -1 \\ 0\end{cases} \pmod{2k+2}.<br/>\]<br/>Oooh this looks very promising: it means we're done, provided that<br/>\[<br/>- k + \begin{cases} -1 \\ 0\end{cases} \not \equiv \begin{cases} 0 \\ 1\end{cases} \pmod{2k+2},<br/>\]<br/>that is, we have problems only if $k \equiv 0,-1,-2 \pmod{2k+2}$. But plainly this cannot happen, because a positive integer that is congruent to $0,-1,-2$ modulo $2k+2$ is at least equal to $2k$, so it cannot be equal to $k$. <br/>This only leaves us with the case of even $m=2k$. In this case the sum is<br/>\[<br/>S \equiv \frac{(2k)(2k-1)}{2} + \begin{cases} -1 \\ 0\end{cases} \equiv -2k+ \begin{cases} -1 \\ 0\end{cases} \pmod{2k+1}<br/>\]<br/>while the only $n$ we have to avoid is $m^2+\frac{m}{2} = 4k^2+k \equiv k(4k+1) \equiv 2k^2 \equiv -k \pmod{2k+1}$. And again we are done, provided that we do not have<br/>\[<br/>-2k + \begin{cases} -1 \\ 0\end{cases} \equiv -k \pmod{2k+1},<br/>\]<br/>that is $k \equiv -1,0 \pmod{2k+1}$, which is again impossible unless $k=0$, which however means $m=1$, that we do not need to consider. Yay, take that, Boris!</p>
<p>In conclusion,</p>
<ul>
<li>If $n \not \in [m^2,m^2+m]$, we present Boris with the partition $\{1,2\},\{3,4\},\cdots,\{2m-1,2m\}$: this forces his sum to lie in the interval $[m^2,m^2+m]$, and therefore different from $n$.</li>
<li>If $m$ is odd and $n \in [m^2,m^2+2m]$ is not $m^2,m^2+m$, then we give Boris the partition $\{1,m+1\}, \cdots, \{m,2m\}$. This forces him to end up with a sum that is congruent to $\frac{m(m+1)}{2} \pmod{m}$, which in particular is different from $n$. We use the same partition if $m$ is even, $n \in [m^2,m^2+2m]$, and $n \neq m^2+\frac{m}{2}$.</li>
<li>Finally, for the few remaining values of $n$ (namely $n=m^2+m/2$ if $m$ is even, $n=m^2, m^2+m$ if $m$ is odd), we foil Boris' evil plans by using the partition in \eqref{eq:FinalPartition}: Boris cannot obtain $n$ as sum, because this would lead to a contradiction modulo $m+1$.</li>
</ul>
<p><strong>Comments.</strong> While this problem is not <em>very</em> easy, there are many low-hanging fruits that one should reach early on in their solution attempts. Namely, the partitions $\{1,2\}, \{3,4\}, \ldots, \{2m-1,2m\}$ and $\{1,m+1\},\{2,m+2\}, \ldots, \{m,2m\}$ already rule out most of the values of $n$, and an experienced problem solver <em>should take very little time to notice that they work most of the time</em>. As for the extra idea to rule out the few remaining cases, it is less standard and certainly partially helped by doodling and making examples, but one should also keep in mind that (unless the problem is really hard!) there should be an easy description for these partitions. In other words: either we're completely off track, and the problem is done in an entirely different way<span style="text-decoration: underline;"><a href="http://www.egmo2018.org/blog/author/darkcrystal/feeds/rss/#footnote1"><sup><strong>1</strong></sup></a></span>, or <em>there has to be a way to write down the partitions we're missing</em>. So it only makes sense to try very regular partitions, obtained by following very simple patterns; and I wouldn't rule out the possibility that, among the <em>reasonable</em> partitions that one might write down, there's more than one that works for – say – $n=m^2$. As a matter of fact, more 'regular' (='easy to describe algorithmically') partitions are <em>a priori</em> better not just because there's a bias in olympiad problems towards having 'simple' solutions<span style="text-decoration: underline;"><a href="http://www.egmo2018.org/blog/author/darkcrystal/feeds/rss/#footnote2"><strong><sup>2</sup></strong></a></span>, but also because their simple description is often our only hope of <em>proving</em> something about them (in our case, congruences on the sums that can be obtained). In other words, what I'm saying is that, while you despair and attack various small cases, <em>you should not waste time trying random partitions</em>, because even if they <em>did</em> work, you would have no idea how to replicate that pattern for different values of $m$ and $n$.</p>
<p><a id="footnote1"></a></p>
<p><sup><b>1</b></sup> maybe by counting how many partitions there are in total, how many sums can be realized from any given partition, and then coming up with an incredibly clever idea</p>
<p><a id="footnote2"></a></p>
<p><sup><b>2</b></sup> yes, this is metagaming. Can you deny it's true?</p>Davide LombardoTue, 02 Jan 2018 10:27:19 +0000http://www.egmo2018.org/blog/thinking-out-loud-egmo-2015-problem-5/EGMOProblem solving