Blog | EGMO 2018http://www.egmo2018.org/blog/BlogenEGMOEGMO CountriesEnglishFlorenceGender IssuesIMOItalianoMy EgmoOlimpiadiProblem solvingWomen in Maths beyond StereotypesTue, 30 Jan 2018 12:50:29 +0000Thinking Out Loud – EGMO 2013 Problem 1http://www.egmo2018.org/blog/EGMO2013-P1/<p>
<script type="text/x-mathjax-config">// <![CDATA[
MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}
});
// ]]></script>
</p>
<p>by <strong>Marcello Mamino</strong></p>
<p><a href="http://www.egmo2018.org/blog/EGMO2013-P2">< Go to the previous post in the series</a></p>
<p>Finally problem 1. Geometry. I'm not going to like it.</p>
<blockquote>
<p><strong>EGMO 2013, problem 1.</strong> The side $\textrm{BC}$ of the triangle $\textrm{ABC}$ is extended beyond $\textrm{C}$ to $\textrm{D}$ so that $\textrm{CD} = \textrm{BC}$. The side $\textrm{CA}$ is extended beyond $\textrm{A}$ to $\textrm{E}$ so that $\textrm{AE} = 2\textrm{CA}$. Prove that if $\textrm{AD} = \textrm{BE}$, then the triangle $\textrm{ABC}$ is right-angled.</p>
</blockquote>
<p><img alt="" src="http://www.egmo2018.org/static/media/uploads/post/EGMO2013-1/egmo2013.1-1.jpeg" style="float: right;" width="40%"/>Yeah, sure, right-angled. See why I hate the stuff? I don't know where the right angle is. I study my figure, accurately reproduced to the right, with growing discomfort. Somehow, I decide that $\textrm{B}$ and $\textrm{C}$ look wrong, which makes $\textrm{A}$ right, right? I check by Pythagoras' theorem that if $\textrm{A}$ is right, then $\textrm{AD}=\textrm{BE}$.</p>
<p>This problem just screams for Cartesian coordinates. I need to prove that $(x,y):=\textrm{A}$ is on the circle with diameter $\textrm{BC}$. I call $\textrm{B}$ and $\textrm{C}$ respectively $(1,0)$ and $(-1,0)$, so the circle is $x^2+y^2=1$. Point $\textrm{D}$ is $(-3,0)$. Point $\textrm{E}$ is $(3x+2,3y)$. $\displaystyle (x+3)^2 + y^2 =(3x+1)^2 + (3y)^2 \;\Rightarrow\; 8 x^2 + 8 y^2 = 8 $.</p>
<p>Average score was 6.14, most contestants obtained the maximum score of 7 points, curiously 9 out of 87 got 5: those that did it with analytic geometry? Number of <em>official solutions</em>: eight. Three by synthetic geometry, plus a variant, two by trigonometry, one by vectors, one by complex numbers, and one by areal coordinates. I'm not kidding, <em>areal coordinates</em>. Seriously, it wasn't so bad, but I don't understand geometry. </p>
<p></p>
<p><img alt="" src="http://www.egmo2018.org/static/media/uploads/post/EGMO2013-1/egmo2013.1-2.jpeg" width="100%"/></p>
<p>Alfred Tarski's quantifier elimination method guarantees that all problems of Euclidean geometry can, indeed, be solved algebraically by Cartesian coordinates. Unless you are an extremely fast computer, however, you should not be too excited about the idea of applying Tarski's method in practice: the number of operations required to solve a problem is a <em>tower of exponentials</em> as high as the text of the problem is long (when expressed in a suitable formal language which is, in general, more verbose than English). Tarski's method has been substantially improved by several people, and now computer programs can, indeed, solve geometric problems using these techniques. Yet, unfortunately, such methods are not nearly usable by mere mortals. So, is Tarski's theorem the silver bullet that kills geometry? Of course not. Can I use Tarski's theorem to justify my contempt for the stuff? Definitely.</p>Marcello MaminoTue, 30 Jan 2018 12:50:29 +0000http://www.egmo2018.org/blog/EGMO2013-P1/EGMOOlimpiadiProblem solvingThinking Out Loud – EGMO 2013 Problem 2http://www.egmo2018.org/blog/EGMO2013-P2/<p>
<script type="text/x-mathjax-config">// <![CDATA[
MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}
});
// ]]></script>
</p>
<p>by <strong>Marcello Mamino</strong></p>
<p><span style="text-decoration: underline;"><a href="http://www.egmo2018.org/blog/EGMO2013-P3">< Go to the previous post in the series</a></span></p>
<p>Emboldened by my success with problem 3, I move with confidence up the list. To be honest, this is exactly what I did, uncountable years ago, at the IMO. Even better, I then did problem 2 in a matter of minutes. Save discovering shortly after the competition that my solution was worth precisely nought, because I misread the statement. Certainly, that was an excess of boldness. Still, at that time, we considered 7-0-7 a decent result. And I put forward, in my defence, that I could not have solved that problem anyway. Let's see if history repeats itself (it won't: I would never confess in writing a blunder so gross). It's time for combinatorics.</p>
<blockquote>
<p><strong>EGMO 2013, problem 2</strong>. Determine all integers $m$ for which the $m\times m$ square can be dissected into five rectangles, the side lengths of which are the integers $1, 2, 3, \dotsc, 10$ in some order.</p>
</blockquote>
<p>This is a typical <em>search problem</em>, I want to spend a few words about them. Suppose for a moment that the value of $m$ is fixed, then the problem would be stated as "is there a tiling of the $m\times m$ square$\dotsc$" which question has a similar structure to "is there a disposition of eight queens on a chessboard such that they don't attack each other?", or "can a chessboard without two opposite corners be covered by dominoes?". Notably, these questions do not ask for <em>all</em> configurations, and this suggests two different approaches. If the set of solutions is small or even empty, then one needs to analyze the hypothetical solutions very carefully, and often to fully describe the set: this is the case of the dominoes. If the set of solutions is large and rather unstructured, as for the eight queens, then the best approach is to try and construct one, by trial and error, a bit of intuition, and common sense. In either case, taking the wrong strategy might spell disaster. So this type of problems often involves some kind of alternation between an experimental mode and an analytic mode, and sticking to one would be ill advice.</p>
<p>My expectation, at first sight, is that only a few values of $m$ will matter, limited by the maximum possible area of the rectangles. For each of these $m$, I have a different search problem. I expect the ones that have solutions to be easy to solve by just some trial and error. After all, problem 3 has been so easy that this one must really be a piece of cake: I have no reason to expect any difficulty with the feasible cases. For the ones that can not be solved, there will be some colouring, or parity, or modular thing going on, like in the dominoes problem. So I have my strategy: first find the admissible values of $m$ with areas, second look for a few solutions by trial and error, third figure out which values don't have a solution and look for an invariant.</p>
<p>The maximum total area of our rectangles is clearly \[ A_{\textrm{max}} \;=\; 10\times 9 + 8\times 7 + 6\times 5 + 4\times 3 + 2\times 1 \;=\; 190\] and the minimum \[ A_{\textrm{min}} \;=\; 10\times 1 + 9\times 2 + 8\times 3 + 7\times 4 + 6\times 5 \;=\; 110\] Why? Well, it just looks right, and it is also almost the <em>rearrangement inequality</em>. I will not spend time looking for a proof until I have completed the rest of the solution, but I think it likely that an argument by induction, similar to that of the rearrangement inequality, will yield these bounds. If I need it in my solution, I will find it later, or, in <em>zeitnot</em> as a chess player would say, I will just pretend that these are well known facts. Anyway, I am left with just three values of $m$ to check, $11$, $12$, and $13$, which surprises me slightly because, at first, I had the impression of a greater variety of cases.</p>
<p><img src="http://www.egmo2018.org/static/media/uploads/post/EGMO2013-2/egmo2013.2-1.jpeg" style="float: right;" width="30%"/>I did good progress so far, which makes me hope for a quick conclusion by just finding configurations for $m=11,12,13$. So I draw three little figures that look more or less like the one on the right: I will call this disposition of five rectangles in a square <em>windmill configuration</em>. I make sure to draw the rectangles of the figure for $m=11$ skinny and tall, and those of $m=13$ quite square-ish. I don't know whether or not there are other arrangements of the five rectangles to consider, however, for now, this one seems reasonable, so I hope to find solutions that look like this. Finally, I set out to find my configurations by writing numbers on the edges of the rectangles.</p>
<p>I spend most of the time of this blind search on the case $m=11$, somewhat less on $m=12$, I give up before even trying $m=13$. It might be bad luck, it might be that there are actually not so many solutions, but after a few minutes it becomes apparent that I am not going anywhere. Can I prune the search space somehow? I notice that the perimeter of the square, $4m$, needs to equal the sum of the dimensions of the four outer rectangles. This means that I can compute the sum of the dimensions of the inner rectangle by adding together all the sides, obtaining $1+2+\dotsb+10=55$, and then subtracting $4m$. This gives me $11,7,3$ respectively for $m=11,12,13$.</p>
<p><img alt="" src="http://www.egmo2018.org/static/media/uploads/post/EGMO2013-2/egmo2013.2-2.jpeg" style="float: left; padding-right: 5px;" width="30%"/>My new observation seems more incisive for $m=13$, because, in this case, it leaves only one choice for the dimensions of the inner rectangle, namely $2\times 1$. I give it a try and, at the first attempt, with a bit of luck, I immediately hit upon a solution. (If you are curious to know how much luck did I actually use, it turns out that the likelihood was one in three. So it was not just a bit of luck, it was indeed about $1.58$ bits.) This is the configuration on the left of this paragraph. Unfortunately, my good luck does not hold for the other cases, so I set forth for more analysis.</p>
<p><img alt="" src="http://www.egmo2018.org/static/media/uploads/post/EGMO2013-2/egmo2013.2-3.jpeg" style="float: right;" width="30%"/>I am still in the mood for finding solutions rather than proving that they don't exist, and I have a bad feeling about $m=12$: it's <em>even</em>. So I begin from $m=11$. I have various choices for the inner rectangle: $6\times 5,\, 7\times 4 \dotsc$ (sum$=11$). Starting from $6\times 5$, I make a list of the choices available for $a_1, a_2, a_3, a_4$ in the figure, subject to the constraint that $a_1+a_3=11-6=5$ and $a_2+a_4=11-5=6$.</p>
<p>My little table of choices now looks like this.</p>
<table width="40%">
<tbody>
<tr>
<td style="border: black;">$a_1+a_3$</td>
<td>$2+3$</td>
<td>$1+4$</td>
</tr>
<tr>
<td style="border: black;">$a_2+a_4$</td>
<td>$2+4$</td>
<td>$1+5$</td>
</tr>
</tbody>
</table>
<p></p>
<p>as you can see below the figure. On the line $a_2+a_4$ I didn't write $3+3$ because, of course, $a_2$ and $a_4$ need to be different. By the same principle, I can now cross out $1+5$ from the same line, because $5$ is already one of the sides of the inner rectangle. So I have established that $a_2$ and $a_4$ are $2$ and $4$, it doesn't matter in which order because $a_2$ and $a_4$ are exchanged by a rotation of the figure by $180^\circ$. Looking at the line $a_1+a_3$, I must now cross out the combination $2+3$, because $2$ is already used for $a_2$ or $a_4$. Similarly I cross out also $1+4$, because $4$ is used. So no option is left but to discard the whole case that the inner rectangle is $6\times 5$.</p>
<p><img alt="" src="http://www.egmo2018.org/static/media/uploads/post/EGMO2013-2/egmo2013.2-4.jpeg" style="float: left; padding-right: 5px;" width="30%"/>The method of the little table is clearly general. I will not write here all the boring details, as anyone can turn that handle by himself; it suffices to say that, in the next case examined, $7\times 4$, all options cross out except one, which gives the solution on the left. Having found solutions for $m=11$ and $m=13$, I turn my method to $m=12$ and in short order I discard all combinations, thus excluding this case. Have I finally concluded problem $2$? Not yet, not even close$\dotsc$</p>
<p>I look back to what is missing, now, in my argument. Definitely I need to prove the inequalities, and that gives the impression of a merely technical exercise. Also I need to check whether there are other dispositions of rectangles besides the windmill configuration. This second gap might actually hold some surprise, so I decide to look into it first. Any tiling of the square needs to cover the four corners of it, and, since the side length of the square is larger than any of those of the rectangles, I can observe that two corners cannot be covered by the same rectangle. Now I want to say that the remaining rectangle is in the center. If not, it must be on one side, hence, on the opposite side, I have only two rectangles. I represent the situation like this.</p>
<p><img src="http://www.egmo2018.org/static/media/uploads/post/EGMO2013-2/egmo2013.2-5.jpeg" style="display: block; margin-left: auto; margin-right: auto;" width="70%"/></p>
<p>They fit like a three-stepped peg in a two-stepped hole (observing that the steps are really three and two because all the side lengths of the rectangles are different). I conclude that the fifth rectangle can not be on one of the sides, as a consequence each of the four rectangles in the corners must touch those of the adjacent corners, and I am in the windmill configuration. Or am I?</p>
<p>I have stumbled upon the problem of balancing precision and practicality in mathematics. We all agree that correctness of a mathematical proof should be a <em>purely</em> logical matter. However, in practice, one can not trace back everything to the axioms of Euclid (or, better said, their modern substitutes). If for no other reason, at least for lack of space and time. In this particular case, I have no real definition of the windmill configuration, which makes it impossible to prove anything about it. Of course, I can identify it as a configuration such that precisely four of the rectangles touch the sides of the square. However, this is hardly a definition in the sense of allowing me to <em>formally</em> prove properties like $a_1+a_3=5$. But why? One definition is never an isolated entity. What does it mean to "touch the sides"? What is a "dissection of the square"? When do two polygons "overlap"? If I go down the rabbit hole, I will end up realizing that I don't even know what a rectangle is, or a number. Everyone must accept a reasonable level of imprecision, it might even be a <em>necessity</em> for effective communication. I satisfy myself with my imperfect definition because it achieves what is important: that the reader understands it clearly, and agrees that my conclusions are correct. Nevertheless, this windmill configuration is just the tiniest bit above my level of comfort with imprecision.</p>
<p>Now that the windmills are sorted (sort of), I need to focus on the areas. Honestly, the technique that I am most eager to use on those things is called avoidance. I search the information that I managed to collect for anything that could help me bound the side of the square. My attention is attracted by the sum of the dimensions of the inner rectangle, that I know to be $11,7,3$ for $m=11,12,13$. The next term of the series $11,7,3$ is obviously $-1$. Fine, the dimensions of the inner rectangle sum to $55-4m$, hence $55-4m>0$, and $m<13.75$. I dispensed with $A_{\textrm{max}}$, but, unfortunately, I cannot find anything like this to get rid of $A_{\textrm{min}}$ as well. Clearly $m\ge 10$, because $10$ is one of the dimensions of the tiles, but my proof of the windmill configuration relies on each corner of the square belonging to a different tile, which in turn requires $m>10$. So I can not use the windmill to exclude the case $m=10$, and, since essentially all that I have proven so far is based on the windmill configuration, here I am back to square one. After considering the idea of classifying more configurations, I decide that the most expedient course of action is to just prove the inequality.</p>
<p>I want to prove \[ A_{\textrm{min}} \;=\; 10\times 1 + 9\times 2 + 8\times 3 + 7\times 4 + 6\times 5 \;=\; 110\] my impression is that I need to generalize it and then prove it by induction. I choose the following generalization.</p>
<p><em>Let $x_1<x_2<\dotsb<x_{2n}$ be positive real numbers. Partition the set $\{x_1, x_2\dotsc x_{2n}\}$ into $n$ pairs $\{a_1,b_1\},\,\{a_2,b_2\}\dotsc$ Then \[ x_1x_{2n} + x_2x_{2n-1} + \dotsb \;\le\; a_1b_1 + a_2b_2 + \dotsb \]</em> </p>
<p>Obviously I needed to replace $10$ with $n$. I decided to also replace the numbers with indeterminates because, otherwise, I might find myself embarrassed when, to make the inductive step, I remove the product $1\times 2n$ and I end up with the wrong set of numbers: $2\dotsc 2n-1$ instead of $1\dotsc 2(n-1)$.</p>
<p>The inductive step should be immediate. I assume the negation of the thesis \[ a_1b_1 + a_2b_2 + \dotsb \;<\; x_1x_{2n} + x_2x_{2n-1} + \dotsb \] If $x_1$ is paired with $x_{2n}$, I just erase the product $x_1x_{2n}$ thus contradicting the inductive hypothesis. So $x_1$ is not paired with $x_{2n}$, therefore, without loss of generality, I can assume $a_1=x_1$ and $b_2=x_{2n}$. Now it should happen that \[ a_1b_2 + a_2b_1 \;\le\; a_1b_1 + a_2b_2 \tag{$\star$} \] which, by the way, is case $n=2$. If this happens, then \[ a_1b_2 + a_2b_1 + \dotsb \;\le\; a_1b_1 + a_2b_2 + \dotsb \;<\; x_1x_{2n} + x_2x_{2n-1} + \dotsb \] and I have contradicted the hypothesis again because $a_1b_2$ is just $x_1x_{2n}$. To check ($\star$), I bring everything to the right hand side of the inequality \[ 0 \;\le\; a_1b_1 + a_2b_2 - a_1b_2 - a_2b_1 \;=\; (a_2 - a_1) (b_2 - b_1) \] and the two parentheses are positive because $a_1=x_1$ is the smallest of the indeterminates, and $b_2=x_{2n}$ is the largest.</p>
<p><em>Sonnez trompettes et clairons!</em> I am finally out of this madness.</p>
<p>I have indeed completed a proof that I am confident, if competently written, would give me full points. Writing it up, however, is no easy task (and I can tell because, indeed, I did turn my thoughts into words, at least partially, in the paragraphs above). There is the death of a thousand cuts of the tables of cases to eliminate. There is all the handwavy arguing around windmills. There is the lemma of the inequality that needs to be formulated properly. And, also, I am not satisfied by bludgeoning through the problem in this way. A quick perusal of my tables of cases for $m=12$ shows an array of all possibilities, all neatly arranged, and all carefully crossed out. Arguably, this artifact is precisely as informative as a fresh table of all cases, all neatly arranged, no one crossed out. Since I need to reconstruct an argument anyway, I might as well look for a quick one. Indeed, I spend a moment looking for a simple way to do the exclusion of cases, and I find it. But really this is not what I want to do: I want to get rid of the windmills.</p>
<p>Now, in a competition, I would probably evaluate how much time I have left. Maybe I would turn my attention to another problem, and leave the write-up of this one for later. There are two benefits in finding a much shorter proof, or one that is considerably easier to write: the first is that it takes less time to write it, the second is that the probability of introducing errors is decreased. These benefits come at the cost of time to look for a better solution, and at the risk of not finding it. The optimal strategy is not easy to divine. Fortunately for me, I am in no competition, so I just carry on thinking about this problem. (I am also known to make very bad decisions in these matters. As a student, I remember factoring during some exam a polynomial of ridiculous degree, like $10$, just because I saw that I could do it. Well, it was a polynomial in two indeterminates, and I could have as well solved for the other one, which was of degree $2$.)</p>
<p>I need a parity or colouring argument to exclude $m=12$, but I wouldn't know how to use colouring here. By parity, I know that there is an even number of rectangles of odd area. In other words, if the numbers are paired $(a_1,b_1)\dotsc(a_5,b_5)$, either all the products $a_ib_i$ are even, or there are three even ones and two odd ones (four odds can be excluded because that would require eight of the numbers to be odd). To begin with, I want to look further into the first case. Checking modulo $4$, or perhaps a larger power of two, seems to be a good idea. I notice that \[ \textrm{even} \times \textrm{odd} \;\equiv\; \textrm{even} \quad \textrm{(mod $4$)}\] or, more precisely, $(2x)\times(2y+1)=4xy+2x\equiv2x$ modulo $4$. I assume that all the products are even, namely, without loss of generality, $a_1\dotsc a_5$ are even and $b_1\dotsc b_5$ are odd. Then I can write \[ a_1b_1 +\dotsb+a_5b_5 \;\equiv\; a_1+\dotsb+a_5 \;=\; 2+4+\dotsb+10 \;=\; 30 \;\not\equiv\; 12^2 \quad \textrm{(mod $4$)}\] This leaves me with the case of two odd and three even products.</p>
<p>I attack the second case with a similar method. There are two products of the form $\textrm{odd}\times\textrm{odd}$, this leaves one mixed product and two of the form $\textrm{even}\times\textrm{even}$. Clearly the congruence modulo $4$ ignores the $\textrm{even}\times\textrm{even}$ summands. Adding the observation that \[ \textrm{odd} \times \textrm{odd} \;\equiv\; \textrm{odd} + \textrm{odd} - 1 \quad \textrm{(mod $4$)}\] I quickly compute that the mixed product $\textrm{even}\times\textrm{odd}$ must satisfy $\textrm{even}-\textrm{odd}\equiv 1$ modulo $4$. However, I can't make any more progress, and I begin to suspect that one pairing such that the sum of the products is $12^2$ might exist. Eyeballing one approximation and then improving it, I get \[ 10 \times 4 + 6 \times 2 + 8 \times 3 + 9 \times 7 + 5 \times 1 \;=\; 12^2 \] Therefore the numbers alone do not exclude $m=12$.</p>
<p><img src="http://www.egmo2018.org/static/media/uploads/post/EGMO2013-2/egmo2013.2-6.jpeg" style="float: left; padding-right: 5px;" width="30%"/>I want a quick way to exclude configurations that have two $\textrm{odd}\times\textrm{odd}$ rectangles, two $\textrm{even}\times\textrm{even}$ rectangles, and a mixed one, for the case $m=12$. I immediately see a dissection of the $12\times12$ square into tiles that have the right parities (even though not the right dimensions), and indeed anyone can see it, here on the left. The existence of this configuration suggests to me that colouring arguments are not likely to work, definitely not one modulo $2$. Making this tiling, I had the impression that I could not have chosen the two $\textrm{odd}\times\textrm{odd}$ rectangles with dimensions that are all different. I felt forced to stack them one above the other as in the figure. This might lead to something, so now I am attracted by the idea of studying the relative position of the odd-sided tiles.</p>
<p><img alt="" src="http://www.egmo2018.org/static/media/uploads/post/EGMO2013-2/egmo2013.2-7.jpeg" style="float: right;" width="30%"/>One of the $\textrm{odd}\times\textrm{odd}$ rectangles must be in a corner of the square. No windmill here, just the good old pigeon hole principle. So the sides of the square that form that corner are divided by the tiles touching them into segments, at least one of which has odd length. Since $m=12$ is even, on each of these sides there must be another odd length segment, therefore each of the two remaining odd-sided tiles is adjacent to one of the sides of the corner. In the figure to the right, I put the corner to the bottom left, and I draw the side with the $\textrm{odd}\times\textrm{even}$ tile horizontally. I observe that, because $x\neq y$, I can draw a vertical line (dashed in the figure) that crosses one of the $\textrm{odd}\times\textrm{odd}$ tiles but not on the other. This line intersects each tile in an even length segment except one, which contradicts its length being even.</p>
<p>I have a new argument for the case $m=12$, and, what is better, I notice that one can clean it up substantially. Ignore the relative position of the tiles, and just call <em>horizontal</em> the direction of the odd side of the tile $\textrm{odd}\times\textrm{even}$. The intersection of a <em>vertical</em> line with any tile is a segment of even length, unless the tile is of type $\textrm{odd}\times\textrm{odd}$, in which case the segment has odd length. The horizontal lengths of the two $\textrm{odd}\times\textrm{odd}$ tiles differ, therefore one can find a vertical line that intersects just one of them, and this brings about the same contradiction as before. I am rather pleased with this argument, and I cannot fail to notice that it works for all even values of $m$, not just $12$. Beauty! I know very well that I was prompted to prove the $A_{\textrm{min}}$ inequality to exclude the single case $m=10$, so this new argument replaces also the inequality.</p>
<p>I quickly bring together my little armament. Of course $m\ge10$, and my latest advancement proves that $m$ is odd. The upper bound $m\le13$, however, still relies on $55-4m>0$, which was obtained as a consequence of those hellish windmills. At this point, I won't allow them to destroy my proof. I look into this $55-4m$, and it becomes presently apparent that the only observation required is that a tile can not have two opposite sides on the perimeter of the square. In fact, this implies that the perimeter of the square, which has length $4m$, is subdivided by the tiling into segments of distinct lengths between $1$ and $10$. Therefore $4m\le1+\dotsb+10=55$. I finally have an argument to be pleased with, read it just after this section.</p>
<p>The participants have obtained generally high scores on this exercise. In average 4.01 out of 7 points, median 5. I am confident that those of my readers that attempted the task did not fail. Personally, it took to me a marginally greater effort, compared with problem 3, to reach a first solution at the clarions. Writing that solution formally, which I didn't do, would have been quite time consuming. This problem then lingered in my mind for a few days, during which time I performed the remaining work piecemeal, often while doing something else, by mostly mental computation. Obviously I have no written record for this part, so it has been reconstructed in my narration, but I think faithfully.</p>
<p>I can't hide my satisfaction with the solution. In my opinion, it is a rather lovely argument. Comparison with the <em>official solution</em> shows that the key ideas of ours are completely different. The official solution, which argues through the windmill configuration and area inequalities, is remarkably well engineered. Even though it uses the windmill configuration, there is a visible effort to do it <em>sparingly</em>. In particular, it avoids the relations, such as our $a_1+a_3=5$, that connect the dimensions of the inner rectangle with those of the outer rectangles. These relations are, in fact, the hardest to justify formally, so I see it as an indication that its author, or authors, shared our same discomfort with windmills. The trick used in the official solution to <em>deduce</em> the $A_{\textrm{min}}$ and $A_{\textrm{max}}$ inequalities from rearrangement, instead of <em>re-proving</em> them, is really nice and worth remembering.</p>
<hr/>
<h4>Solution to problem 2</h4>
<blockquote>
<p>Determine all integers $m$ for which the $m\times m$ square can be dissected into five rectangles, the side lengths of which are the integers $1, 2, 3, \dotsc, 10$ in some order.</p>
</blockquote>
<p><img alt="" src="http://www.egmo2018.org/static/media/uploads/post/EGMO2013-2/egmo2013.2-8.jpeg" style="float: right;" width="30%"/></p>
<p>The values are precisely $m=11$ and $m=13$, and tilings for these values are exhibited in the figure. To exclude all other values, we begin with the observation that $m\ge10$, otherwise the tile having one side of length $10$ would not fit. Furthermore, we will prove that (a) $m\le 13$ and (b) $m$ is odd. This is enough to conclude.</p>
<p>For (a), assume $m\ge 14$. Observing that no tile can contact two opposite sides of the square, we conclude that the perimeter of the square, which has length $4m$, is subdivided by the tiling into segments of distinct lengths between $1$ and $10$. Therefore $4m\le1+\dotsb+10=55$, contradicting $m\ge 14$.</p>
<p>For (b), let $a_1\times b_1\dotsc a_5\times b_5$ be the tiles covering a square of even side length $m$. Since the area of the square must equal the total area of the tiles, either none or two of the products $a_ib_i$ are odd (four can be excluded because it would require eight of the dimensions to be odd). Considering the first case, by the pigeon hole principle, each product $a_ib_i$ contains one even factor and one odd factor: without loss of generality the $a_i$ are the even factors. Observe that \[ a_ib_i\; =\; a_i + a_i(b_i-1) \;\equiv\; a_i \quad \text{(mod $4$)}\] Therefore, computing the congruence modulo $4$ of the tiles' total area \[ a_1b_1 + \dotsb + a_5b_5 \;\equiv\; a_1 +\dotsb+ a_5 \;=\; 2 +\dotsb+10 \;\equiv\; 2 \quad \text{(mod $4$)}\] This contradicts $m^2$ being a multiple of $4$, thus excluding the first case. As a consequence, two of the products must be odd and three even. Hence two of the tiles are of type $\textrm{odd}\times\textrm{odd}$, one of type $\textrm{odd}\times\textrm{even}$, and two of type $\textrm{even}\times\textrm{even}$.</p>
<p>Call <em>horizontal</em> the direction of the odd side of the tile $\textrm{odd}\times\textrm{even}$. Any <em>vertical</em> line intersecting a tile must do it in a segment of even length, unless the tile is of type $\textrm{odd}\times\textrm{odd}$, in which case the segment is odd. The dimensions of all tiles differ, so do in particular the horizontal lengths of the two $\textrm{odd}\times\textrm{odd}$ tiles, hence we can find a vertical line intersecting one of them but not the other. This vertical line is divided into a union of segments precisely one of which has odd length, contradicting that $m$ is even. This excludes also the second case, thus establishing claim (b).</p>
<p></p>
<p><img alt="From xkcd by Randall Munroe (https://xkcd.com/556/)" src="https://imgs.xkcd.com/comics/alternative_energy_revolution.jpg" width="100%"/></p>
<p style="text-align: right;"><em>From <strong>xkcd</strong> by <strong>Randall Munroe</strong> (<span style="text-decoration: underline;"><a href="https://xkcd.com/556/">https://xkcd.com/556/</a></span>)</em></p>
<p style="text-align: right;"><a href="http://www.egmo2018.org/blog/EGMO2013-P1">Continue to the next problem ></a></p>Marcello MaminoTue, 23 Jan 2018 09:45:02 +0000http://www.egmo2018.org/blog/EGMO2013-P2/EGMOOlimpiadiProblem solvingThinking Out Loud – EGMO 2013 Problem 3http://www.egmo2018.org/blog/EGMO2013-P3/<p>
<script type="text/x-mathjax-config">// <![CDATA[
MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}
});
// ]]></script>
</p>
<p>by <strong>Marcello Mamino</strong></p>
<div style="margin-left: 50%; padding-bottom: 10px;">
<p><em>He who would cross the Bridge of Death</em><br/><em>Must answer me</em><br/><em>These questions three</em><br/><em>Ere the other side he see.</em></p>
</div>
<p>When Alessandra sent around an e-mail looking for contributors to this series, I had already solved most of past EGMO problems. It is tempting to reconstruct solution paths retrospectively, but, doing so, one goes at risk, in all honesty, of producing unnaturally elegant solutions, and also of forgetting the most embarrassing blunders. Fortunately, I noticed that I didn't tackle yet any of the three problems of Day 1 EGMO 2013, so I set out to do them <em>from the point of view of a contestant</em>. I took this as a sort of psychological experiment, so I will describe my solution process as it happened, and not as it could or should have happened.</p>
<p>To obtain the best instructional value out of this experiment, if you are not already familiar with the problems, I suggest that you solve them before going any further. Unfortunately, it happens at times that one problem just won't give. In this predicament, if you can say on your honour that it resisted a most gallant assault, then don't hold yourself vanquished. Read, instead, the relevant section just until a new idea comes up, and then stop to try again. Good luck!</p>
<hr/>
<p>Let's do the bold thing and start from <strong>problem 3</strong>.</p>
<blockquote>
<p><strong>EGMO 2013, problem 3.</strong> Let $n$ be a positive integer.</p>
<ol style="list-style-type: lower-alpha;">
<li>Prove that there exists a set $S$ of $6n$ pairwise different positive integers, such that the least common multiple of any two elements of $S$ is no larger than $32n^2$.</li>
<li>Prove that every set $T$ of $6n$ pairwise different positive integers contains two elements the least common multiple of which is larger than $9n^2$.</li>
</ol>
</blockquote>
<p>There are two parts, and if there is any dependency between the two, then it's going to be <strong>(b)</strong> depending on <strong>(a)</strong>, so I should better start from <strong>(a)</strong>. It wants me to build a large set $S$ of positive integers with small pairwise lcm.</p>
<p>Intuitively, elements of $S$ should have common factors, to keep the lcm low. So I suspect that $S$ might be something similar to the set of products $p_1^{e_1}\cdot p_2^{e_2}\dotsb$ with small primes $p_i$ and some balancing act to be performed on the exponents. Before I embark on something so complicated, I want to check the most trivial cases to set a baseline. For instance, what happens if I take the set of the first $6n$ numbers? Well, obviously the lcms are bounded by little less than $36n^2$: not so far off considering that I am only aiming for $32n^2$.</p>
<p>These numbers need to have some common factor, so what if instead of taking the first, say, $a$ numbers, I take the first $a$ <em>even</em> numbers? Clearly my bound on the lcms jumps from $a^2$ to $2a^2$, and that's a loss, the corresponding gain is that, now, I freed up all the odd numbers. To make a rough first attempt, I want to see what happens adding to $S$ those odd numbers that are halves of even numbers already in: clearly they cannot produce any larger lcm. My new $S$ contains $a$ even numbers and $\frac{1}{2}a$ odd numbers, total $\frac{3}{2}a$, so the square of the cardinality of $S$ has gone up by a factor of $\frac{9}{4}$ at the expense of increasing the largest lcm by a factor of $2$: that's a win.</p>
<p>I'm making some progress: even numbers are good. I want to check multiples of $3$ now. So I have the first $a$ multiples of $3$, namely all up to $3a$. In addition to these $a$ numbers, I have the non-multiples up to $\frac{1}{3}$ of $3a$, which makes a grand total of $\frac{5}{3}a$ numbers. My upper bound on the lcms is $3a^2$, and this means a loss of $3$ for a gain of $\frac{25}{9}<3$: not good.</p>
<p>I'm back to the multiples of $2$. First, I want to see how far I am from the goal. I take $a$ even numbers, namely up to $2a$, and $b$ odd numbers, namely below $2b$. I chose $a=2b$, and from $a+b=6n$ follows $b=2n$. My lcms are now bounded by more or less $2a^2=32n^2$. Surprising: it seems that this is already the solution. Or almost the solution, maybe I have ignored some $+1$ in the counts and that's where the devil is. So let's be precise. \[ S = \{ \text{even nrs.} \le 8n \} \cup \{ \text{odd nrs.} < 4n \} \]The lcm is definitely <em>no larger than</em> $32n^2$, the first set has $4n$ elements, the second $2n$. Fine: part <strong>(a)</strong> solved.</p>
<p></p>
<p style="padding-top: 15px;">Part <strong>(b)</strong>. From part <strong>(a)</strong> I have got some intuition about the critical $S$, the largest one having all lcms below $9n^2$. It will probably contain most small numbers, because if $x\in S$ then all divisors of $x$ need to be in $S$. On the other hand the larger numbers, those of an order of magnitude larger than $n$, must be rather sparse, because they need to have lots of common factors. Then, of course, there are no elements of $S$ above $9n^2$. To begin with, I want to take a closer look at this $S$ from the sparse side, namely down from $9n^2$.</p>
<p>Note: the choice of strategy just described is the <em>key step</em> to the solution. It came to my mind in a natural and, I should say, subconscious way. It is, however, interesting to spell out in words which choices have been made. First, I decided to fix the maximum lcm to $9n^2$ and try to look for the largest $S$ that fits, with a view, obviously, of proving that this $S$ has necessarily less than $6n$ elements, thus obtaining a contradiction. A symmetric approach, which we can call direct, would have been to fix the cardinality of $S$ instead of the largest lcm, and then prove that one of the lcms is $>9n^2$. In other words, one tactic is to fit as many objects as possible in a limited space, the other is to fit a fixed number of objects in the smallest possible space. I cannot offer a rational argument to justify my preference for the first, except, possibly, this: in an attempt to figure out which mechanism limits the space, it appears natural to just fill it up until whatever it is that becomes exhausted prevents further progress, thus making itself visible. Such a general consideration is not satisfactory, and, in other circumstances, I would probably just do it the other way round without giving much thought. The second choice is to look first at the largest numbers in this critical $S$. Why? It is obvious that the <em>big end </em>of $S$ is where the hypothesis that all lcms are $\le 9n^2$ imposes the most immediate constraints.</p>
<p>So I want to look just below $9n^2$. Clearly I cannot have two numbers $x$ and $y$ <em>just below </em>$9n^2$, because their lcm would be at least $2x$ or $2y$, and this is already too much. Indeed, this argument tells me that there is at most one number between $\frac{9}{2}n^2$ and $9n^2$. I paid one single number to halve the upper bound: that's good business in my book. I call $A$ the number $9n^2$, and I draw a picture like this</p>
<p><img src="http://www.egmo2018.org/static/media/uploads/post/2013.3-1.jpeg" style="display: block; margin-left: auto; margin-right: auto;" width="60%"/></p>
<p>to signify that the interval between $\frac{1}{2}A$ and $A$ contains at most one element of $S$. Another one-element interval seems to be between $\frac{1}{3}A$ and $\frac{1}{2}A$, because two elements in there cannot differ only by a factor of $2$, thus the lcm is at least $3$ times one of them (actually even $4$ times maybe, but it's not time for fine tuning yet). My picture displays now more detail, and an obvious conjecture. <img alt="" src="http://www.egmo2018.org/static/media/uploads/post/2013.3-2.jpeg" style="display: block; margin-left: auto; margin-right: auto;" width="60%"/>Does the pattern continue? It seems so.</p>
<p>To state the last observation formally, it should happen that, for all $i\ge 1$, if $\frac{A}{i+1} < x < y \le \frac{A}{i}$, then $\operatorname{lcm}(x,y) > A$. Arguing about the common factors of $x$ and $y$ is cumbersome, so I would prefer to control the lcm somehow more algebraically. Considering that $x$ and $y$ are sandwiched in a small interval, there is an obvious upper bound on the gcd, namely the size of the interval. This calls for the well known relation connecting lcm and gcd \[ \operatorname{lcm}(x,y) = \frac{xy}{\operatorname{gcd}(x,y)} \ge\frac{xy}{y-x} > \frac{\left(\frac{A}{i+1}\right)^2}{\frac{A}{i}-\frac{A}{i+1}} = A \frac{i}{i+1} \]OK, I hoped to get $A$, but I got a little bit less (the fraction $\frac{i}{i+1}$ is quite close to $1$). Probably I just need to do my computation more carefully, because the claim itself, I already observed, wastes information. Yet it's promising enough. Before I spend more time fixing this argument, I prefer to assume the claim and see what benefit can be drawn from it. Joining the intervals, the claim tells me that there are at most $i$ elements of $S$ above $\frac{A}{i+1}$. Remembering that $A=9n^2$, it seems reasonable to try $i+1=\sqrt{A}=3n$, so $S$ has at most $3n-1$ elements above $3n$. Of course it also has at most $3n$ elements $\le 3n$, which makes $6n-1$. Here we go: the only missing step is the proof of the claim.</p>
<p>The computation above is patently very rough: I just replaced both $x$ and $y$ in the product $xy$ with their smallest possible value $\frac{A}{i+1}$, and then I replaced $y-x$ with the upper bound $\frac{A}{i}-\frac{A}{i+1}$. That's wasteful because $x$ and $y$ cannot be at the same time maximally small and maximally apart from each other. Let's try to keep $x$ and $y$ as indeterminates for a little longer \[ \operatorname{lcm}(x,y) \ge \frac{xy}{y-x} = \frac{1}{\frac{1}{x}-\frac{1}{y}} \]Now from the hypothesis $\frac{A}{i+1} < x < y \le \frac{A}{i}$, taking the reciprocals, I get \[ \frac{i}{A} \le \frac{1}{y} < \frac{1}{x} < \frac{i+1}{A} \;\;\Rightarrow \;\; \frac{1}{x}-\frac{1}{y} < \frac{1}{A} \]And, substituting in the formula above, $\operatorname{lcm}(x,y) > A$. Done.</p>
<p>It remains to collect the thoughts above and write up a formal solution, you will find it in the next section. The problem turned out to be much easier than expected, however I suspect that good luck helped me considerably. So always remember to throw gems at unicorns before contests. In hindsight, the large gap between part <strong>(a)</strong>, $32n^2$, and part <strong>(b)</strong>, $9n^2$, should have told me that there was no razor-sharp construction going on. On the other hand, I can only be grateful that it was so: this is a sort of problems where often one can make improvements by considering more and more intervals, and constructing proofs like that can be tedious.</p>
<p>Don't be put off if you encountered difficulties solving this exercise, the stats show that the best score obtained by any of the 87 participants is 3 points out of 7, and 69 persons didn't make any point at all. Comparison with the two <em>official solutions</em> shows that they are based essentially on the same mechanisms as ours. Both the official solutions, however, do part <strong>(b)</strong> through the approach that we called direct. There is a distinct smell of black magic around these solutions, which confirms, in my mind, the intuition that the approach by contradiction opposes fewer obstacles.</p>
<hr/>
<h4>Solution to problem 3</h4>
<blockquote>
<p>Let $n$ be a positive integer.</p>
<ol style="list-style-type: lower-alpha;">
<li>Prove that there exists a set $S$ of $6n$ pairwise different positiveintegers, such that the least common multiple of any two elements of $S$ is no larger than $32n^2$.</li>
<li>Prove that every set $T$ of $6n$ pairwise different positive integerscontains two elements the least common multiple of which is larger than $9n^2$.</li>
</ol>
</blockquote>
<p><strong>(a) </strong>Let $S$ contain precisely the positive even numbers $\le 8n$ and the odd numbers $<4n$, hence a total of $6n$ numbers. Let $x$ and $y$ be elements of $S$, we show that $\operatorname{lcm}(x,y)\le 32n^2$. In fact, if at least one of them is odd, then\[\operatorname{lcm}(x,y) \le xy < (8n)(4n) = 32n^2\]Otherwise\[\operatorname{lcm}(x,y) = \frac{xy}{\operatorname{gcd}(x,y)} \le\frac{xy}{2} \le \frac{(8n)^2}{2} = 32n^2\]This concludes part <strong>(a).</strong></p>
<p><strong>(b)</strong> Assume towards a contradiction that $\operatorname{lcm}(x,y) \le 9n^2$ for all $x,y\in T$: we will prove that $T$ has less than $6n$ elements. We claim that, for all $i\ge 1$, the set $T$ contains at most one element in the interval $I_i:=\left(\frac{9n^2}{i+1}, \frac{9n^2}{i}\right]$. Assuming, for the moment, the claim, $T$ has at most $3n-1$ elements in the interval $(3n,9n^2] = \bigcup_{i=1}^{3n-1} I_i$. On the other hand, all elements of $T$ must not exceed $9n^2$, and there are at most $3n$ elements $\le3n$, therefore $T$ can have at most $6n-1$ elements, hence the statement.</p>
<p>It remains to prove the claim. Let $\frac{9n^2}{i+1} < x < y \le \frac{9n^2}{i}$. Taking reciprocals we get \[ \frac{i}{9n^2} \le \frac{1}{y} < \frac{1}{x} < \frac{i+1}{9n^2} \;\; \Rightarrow \;\; \frac{1}{x}-\frac{1}{y} < \frac{1}{9n^2} \]hence \[ \operatorname{lcm}(x,y) = \frac{xy}{\operatorname{gcd}(x,y)} \ge\frac{xy}{y-x} = \frac{1}{\frac{1}{x}-\frac{1}{y}} > 9n^2\]It follows that $x$ and $y$ cannot belong both to $T$, and the claim is proven.</p>
<p style="text-align: right;"><span style="text-decoration: underline;"><a href="http://www.egmo2018.org/blog/EGMO2013-P2">Continue to the next problem ></a></span></p>Marcello MaminoTue, 16 Jan 2018 09:40:22 +0000http://www.egmo2018.org/blog/EGMO2013-P3/EGMOOlimpiadiProblem solving