[PDF] UKMT - BMO Round 2 - British Mathematical Olympiad 2021 - Solutions.pdf | Plain Text

British Mathematical Olympiad Round 2 © 2021 UK Mathematics Trust supported by Solutions

British Mathematical Olympiad Round 2 2021 SolutionsThese solutions are intended as outlines. In particular, they do not represent the full range of approaches possible, nor the difficulties which lie in finding them. © 2021 UK Mathematics Trust www.ukmt.org.uk 2

British Mathematical Olympiad Round 2 2021 Solutions1.A positive integer �is called good if there is a set of divisors of �whose members sum to �and include 1. Prove that every positive integer has a multiple which is good. Solution Firstly we show that if � > 1is good, then so is 2�. This is true since some proper divisors of �, including 1 (and hence not including � itself ), sum to �; if we consider all these together with �, they will all be factors of 2� which sum to 2� . This means that it suffices to prove the claim for odd numbers. The claim holds for 1 since good numbers exist (such as 6, which is 1+ 2+ 3, for example). If � > 1 is odd and � = 2� � for some �, then � + 2� + 4�+ · · · + 2�− 1 � = ( 2� − 1)� = �− � which is close to �. This value of �will be good if we can find some other factors of �, including 1, which sum to �. To do this, we write � as a sum of powers of 2, including 1, by writing � in binary, and then choose � to be large enough for all those powers of 2to be factors of �. (We may take � to be ⌈log 2( � )⌉ , the smallest integer greater than or equal to the base-2 logarithm of �.) None of these powers of 2 are multiples of � so there is no risk that we are using the same factor of � twice. Alternative A variation on the proof above can be obtained by instead considering 2� −1 ( 2� − 1). This is good for any �≥3, since 2 � −1 (2 � − 1) = 1+ 2+ 22 + · · · + 2� −1 + ( 2� − 1) + 2(2 � − 1) + · · · + 2� −2 (2 � − 1). It can be shown using the Fermat-Euler theorem that any number �is a factor of a number of this form. Indeed, suppose � = 2� � , with � odd. Then the Fermat-Euler theorem tells us that 2� � (� ) − 1is a multiple of � for any positive integer �(where � (� ) is the number of numbers between 1and � which are coprime to �). This means that if we choose �such that � < � � (� ) , then we will have �a factor of 2� � (� )− 1 (2 � � (� ) − 1) Alternative We show that the numbers �!are all good for all � ≥ 3, which is enough to solve the problem since �is always a factor of �!. We proceed by induction, using 3! = 6= 3+ 2+ 1for the base case. For the inductive step, suppose that �! = 1+ Õ � � � where � �are distinct factors of �! other than 1. Then we have ( � + 1)! = 1+ �+ Õ � ( � + 1)� �, and all these factors are different, so (� + 1)! is also good. © 2021 UK Mathematics Trust www.ukmt.org.uk 3

British Mathematical Olympiad Round 2 2021 Solutions2.Eliza has a large collection of � × � and �× � tiles where � and � are positive integers. She arranges some of these tiles, without overlaps, to form a square of side length �. Prove that she can cover another square of side length �using only one of her two types of tile. Solution Number the rows of the �× �square from 1 to �. We say that a cell is specialif it is in the top row of a �× �square. In any row, the number of cells that are in a �× � square is congruent to �, modulo �. Since each special cell has �− 1cells in the �− 1rows underneath it, we can see by induction that the number of special cells in rows 1, � + 1,2�+ 1, . . . is congruent to � modulo �, and the number of special cells in rows with other numbers is congruent to 0. Now, the cells in � × � squares in row �are all in squares whose top cells are in row �− �+ 1, and hence the number of special cells in row �− �+ 1is congruent to �(modulo �). Hence either � ≡ 0(modulo �), in which case �is a multiple of �, or �− �+ 1is of the form � � + 1, in which case �is a multiple of �. Alternative Number the rows of the square to be tiled from 1 to �and suppose that �does not divide �. If the row number is congruent to 1 modulo � write +1in every cell in that row, and if the row number is congruent to 0modulo � write −1in every cell in that row. Write 0 in every other cell. The sum of all the entries on the board is exactly �. The entries covered by an � × � tile sum to 0, and the those covered by a �× � tile sum to a multiple of �. Thus the total of the entries covered by any collection of tiles is congruent to zero modulo �, so �|� as required. Alternative Suppose that �is divisible by neither � nor �. Imagine tiling plane with � × � rectangles and colour in the four corners of each rectangle as shown (for �= 3, � = 4, � = 10 ). More precisely, we shade the cell with coordinates (�, � )(for 1≤ �, � ≤�) just when �|� or � − 1, and �|� or �− 1. © 2021 UK Mathematics Trust www.ukmt.org.uk 4

British Mathematical Olympiad Round 2 2021 SolutionsIt is easy to verify (using the periodicity of the colouring) that each �× � or �× � tile covers an even number of shaded cells, but that there are an odd number of shaded cells in total. Thus the �× �square cannot be tiled with �× �and �× �tiles, as desired. Alternative Stretch the board by 1/ � in one direction and by 1/ � in the other. Now each of Eliza’s tiles has one side equal to 1. A theorem of De Bruijn now implies that the whole board must have an integer side length, which, after reversing the stretches, implies the result. Remark The second alternative opens up many possible approaches, since De Bruijn’s result has many proofs. For example we can divide the original board into rectangles whose dimensions are � / 2and �/ 2and apply a standard chessboard colouring. Each of Eliza’s tiles covers an equal black and white area, but it can be checked that the board only consists of equal black and white areas if its side is divisible by either �or �. © 2021 UK Mathematics Trust www.ukmt.org.uk 5

British Mathematical Olympiad Round 2 2021 Solutions3.Let � �� be a triangle with � � > �� . Its circumcircle is Γ and its incentre is �. Let � be the contact point of the incircle of � ��with��. Let �be the point on Γsuch that ∠�� � is a right angle. Prove that � �and � � meet on Γ. Solution The line � � meets the circumcircle Γ at the midpoint � of the minor arc �� . We produce � � to cut the circumcircle again at �′ . We will show that ∠�� ′ � is a right-angle and so �′ = �. Angle in the same segment gives ∠� � ′ � =∠� � � =� 2 and so � � is tangent to circle � � � ′ at �, and the tangent-secant theorem applies so � �2 = � � . � � ′ . We also know that � � =� � =� � , and substituting � � into this relation, the converse of the tangent-secant theorem tells us that � � is tangent to the undrawn circle � � � ′ at �. Now ∠ � � � +∠� � � = ∠ � � � = 90 ◦ − � 2 . Therefore ∠ � � � =� −� 2 (we have just used the fact that ∠ � < ∠� . Putting all this together, we find that ∠ �� ′ � = ∠�� ′ � − ∠� � ′ � −∠� � ′ � =∠�� � −∠� � � −∠� � � = 180 ◦ − � − � −� 2 −� 2 = 180 ◦ − � +� +� 2 = 90 ◦ as required. Alternative We know that � � meets the circumcircle again at � , the midpoint of the arc �� . Since Γ is also the circumcircle of △ � �� , we know that � � also passes through � precisely if � � is the angle bisector of ∠�� � . Let � , � be the contact points of the incircle with � � ,� � , respectively, so �� � � � is cyclic (by the converse of Thales’s theorem). Now �, the intersection of Γ and circle �� � � , is the ©2021 UK Mathematics Trust www.ukmt.org.uk 6

British Mathematical Olympiad Round 2 2021 Solutionscentre of spiral similarity which carries the directed segment � �to� � . Therefore � � � � = �� � � = � � ��since tangents from a point to a circle have the same length. Now, by the converse of the angle bisector theorem, � �is the angle bisector of angle ∠� � � . Alternative It is possible to adjust the approach above so as to not to require knowledge of the spiral similarity theorem. One way to proceed is by chasing angles to prove that △ � � � and △ � � � are similar. © 2021 UK Mathematics Trust www.ukmt.org.uk 7

British Mathematical Olympiad Round 2 2021 Solutions4.Matthew writes down a sequence � 1, � 2, � 3, . . . of positive integers. Each � � is the smallest positive integer, different from all previous terms in the sequence, such that the mean of the terms �1, � 2, . . . , � � is an integer. Prove that the sequence defined by ��− � for �= 1,2 ,3 , . . . contains every integer exactly once. Solution Write � � = � �− � . We prove by induction that � 1, . . . , � � consists of consecutive integers in some order. Let �� = max {� 1, . . . , � �} . Since � 1 = 0, we have � � < � . The mean of the sequence � 1, � 2, . . . , � �, � + 2+� � is an integer, as it is the sum of the two sequences 1,2, . . . , �, � + 1and � 1, � 2, . . . , � �, � �+ 1of consecutive integers, and the mean of any sequence of � + 1consecutive integers is an integer (respectively a half-integer) according as �is even (respectively odd). It follows that � �+ 1 is congruent to � + 2+ � � mod � + 1. Since �+ 2+ � � is greater than any of �1, . . . , � � (as �� = �+ � � with � < � + 1and � � < � �+ 1, we know that � �+ 1 ≤ �+ 2+ � � , and hence ��+ 1 is equal to � + 2+ � � or 1+ � � (as �� − � < 0). Thus � �+ 1 is equal to � � + 1 or � � − � , and the integers � 1, . . . , � �+ 1 are consecutive. This completes the induction. It follows that every integer appears in the sequence � 1, � 2, . . . at most once. To complete the problem, we need only check that � � > 0infinitely often and also that � � < 0 infinitely often. For the former, we simply note that if � � < 0, then we cannot also have � �+ 1 < 0. Indeed, since 0 = � 1 is among the consecutive integers �1, . . . , � � , the only way we could have ��+ 1 < 0would be if � �+ 1 = � � − 1, in which case � �+ 1 = � � , which is not possible. For the latter, suppose for contradiction that there is some �0 such that � � > 0for all � > � 0 . It follows that for � > � 0 we have �� = �− � , and hence � � = 2� − � , for some �. Since the mean of � 1, . . . , � �− 1, � −� is also an integer, it follows that �− � must appear in the sequence � 1, . . . , � �− 1 for all � > � 0 . If in addition �is odd, we cannot have �− �= � �′ = 2�′ − � for an integer �′ > � 0 , and hence �− � must even appear in the sequence � 1, . . . , � �0 . But there are infinitely many odd integers � > � 0 and only finitely many integers in the range �1, . . . , � �0 , which is impossible. Alternative Let � be the Golden Ratio, so 1/ � = �− 1. Define �(� ) to be the ceiling of �/� . If � (� ) = �(� − 1)then define �(� ) = �(� − 1)(case 1). If � (� ) = �(� − 1) + 1 then define �(� ) = �(� − 1) + � (case 2). Then �(� ) is the mean of � ( 1), � ( 2), . . . , � (� ) because � (� ) = �(� − 1) + � � and �(� ) = �(� − 1) + � always, where � is an integer. Case 1 is �− 1 < (� − 1)/ � < � /� < � , which rearranges to (� − 1)/ � < � −� < � /� . Case 2 is (� − 1)/ � < � −� < � /� , which rearranges to � − 1 < (� − 1)/ � < � /� < � . It follows that � (� ) is self-inverse, in particular bijective. Note that � (� (� − 1)) < �� (� − 1) < � ( (�− 1)/ �+ 1) < � + 1, so �(� − 1)is used by position �. So if we are in case 2, � (� − 1)has been used previously. So we are always using the smallest unused � (� − 1) + � � (since � < 0is impossible). Hence our sequence is the same as the one in the question. Case 2 has �(� ) − � equal to each positive integer once, as �ranges over all positive integers. Case 1 has �(� ) − � equal to each negative integer once, as � ranges over all positive integers. Since �( 1) − 1 = 0, that completes the problem. © 2021 UK Mathematics Trust www.ukmt.org.uk 8