2019 H3 Solution

Su ggested Solution Remarks 1i      2 222 2 22236 23 6 4 9 2367 xyz xyz xyz        1ii 22 2 222 2 2367 1 236Since 2 3 6 7 , by observation, , , . 777 xyz xyz xyz        1iii 2 1 Suppose 1. n i i x   22 2 11 1 1 1 nn n n ii ii ii i i x xn x n x n                 Since if we let 1 ix n  for all 1 in , we yield 2 2 1 1 1 n i i xn n   and 1 1n i i x nn n   , the maximum possible value of 1 n i i x   is n . 1iv Suppose there are n squares of lengths xi contained in the unit square. Their total area is 2 1 1 n i i x   , and their total perimeter is 1 18 4 n i i x   . By part (iii), 1 18 20.254 n i i xn n     . Hence, there must be more than 20 such squares. 2ia 841Number of ways 165 41   [Bijection with a string of eight 0’s (objects ) and three 1’s (partitions). For example, the string 00100010100 would correspond to the combination of 2 A’s, 3 C’s, 1 G and 2 T’s.] 2ib 44 1Number of ways 35 41   [Place one 0 in each box and the remaining four 0’s into the boxes.] 2iia 8Number of sequences 4 65536 2iib 7Number of sequences 4 3 8748  2iic 88 8 8 444Number of sequences 4 3 2 1 40824321           Principle of inclusion / exclusion. 3ia 1 11 1 Given 1 and 0. 11 2 1 1... ...111 1 3 2 1 1 for all ii i i i xa ia i i i i ixx x x xi i ii ii i xi i                                   3ib From (3i(a)), 22 2 11 1 11 1 22 nn n i in in in x in     .

3ic  12 12 22 2 2 21 12 1 21 2 1 2 11 1... 22 lim lim is unbounded.2 nn n nn n iii i ii ii ii nnii nxxx x x x n nxx                     3iia Since   111 1 ii i i i iaix i x i x i x a x i        , summing from im to in yields the following.        11 2 1 11 11 2 1 ... 1 1 nn ii i m m m m im im nn n m a x ixi x mx m x m x mx nxn x nxm x                        Alternative Solution Let Pn be the statement  1 1 11 n in i ax n x     . 12 1 1 1 1RHS of P 2 1 2 1 LHS of P2 P is true. axa a x       Assume Pk is true for some k   .    1 k+1 1 11 11 1 22 1 1 1 LHS of P 11 11 121 2 RHS of P P is true P is true. kk ii k ii kk k kk k kk axax a x kx a x ka x kakx x x k                            Since P1 is true and  1P is true P is truekk  , Pn is true for all n   .     1 1 1 1 11 1 11 i f 1 Hence, 11 1 i f 1 1. n inn i i nm im ii n m ii nm xn x m x xx n x m x m nxm x                       Alt. Sol. We first ask ourselves what is the partial sum from 1 to n, and from there we would be able to find the sum from m to n. By observing the equation that we need to show, we may let 1m so that we obtain Pn which we will then prove. 3iib 1Let . Then . 1 M M MaM ax x M       Case 1: 0 Mx  . 1 1 Since 0, 0. 1 Consequently, for all , since 0, 0. 11 0 for all , . M nn nm Ma xM na nanM x x nn xx nm M              

Case 2: 0 Mx  . 1 1 Since 0, 0. 1 Consequently, for all , since 0, 0. 11 0 for all , . M nn nm Ma xM na nanM x x nn xx nm M               4ia Let Wn be the number of such n-digit numbers having first digit 3. Then by symmetry, nnWY for all n   . If the first digit is 2, then the next digit can only be 1 or 3. Hence, 11 1 1nn n n nYX W X Y   . 4ib If the first digit is 1, then the ne xt digit can be either 1, 2 or 3. 11 1 11 2 nn n n nn XX Y W XY       4ic  1 11 1 1 2 (by 4i(b)) 2 (by 4i(a)) (by 4i(b)) 2 nn n nn n nn n nn XX Y XX Y XX X XX           4ii Let Pn be the statement  2 1 mod 4nXn n  .     11 2 21 1 1 22 12 LHS of P 1 mod 4 LHS of P 3 mod 4 RHS of P =1 1 1 1 mod 4 RHS of P 2 2 1 3 mod 4 XX X Y W      12P and P are true. Assume Pk and Pk–1 are true for some k   , 2k .     11 1 22 2 2 1 2 LHS of P 2 + 22 2 1 1 1 31 1 (mod 4), if 0 or 3 (mod 4) 3 (mod 4), if 1 or 2 (mod 4) RHS of P = 1 1 1 1 1 (mod 4), if 0 or 3 (mod 4) 3 (mod 4), if 1 kk k k k XX X kk k k kk kk kk kk kk kk k                      11 or 2 (mod 4) P and P are true P is true.kk k k      Since P 1 and P 2 are true, and  11P and P are true P is truekk k  , P n is true for all n   . 4iii     2 2 1 11 1 1 m o d 4nn n nnTXY WX n n nn         

5i 2 2 dd dd d1 d1 dd ln d ed ed e x xx uu xx t tt xxt tx C u tAx uA x AB          5ii  f( ) d 2 2 2 22 2 e d1 d f( )df ( ) d dd d f ' () f () f ()dd d df ' () f () f () g () f () d f' ( )d 1 d d 1 d g( )f( ) d d d d f' ( ) d g( )f( ) d df( ) d xyx u uu xy u yxx u x uy u xy x u xyxx x ux y u x u xy xy xy x xu u u u xxx ux x ux xu xxx ux                    2 df '( ) f ( )g( ) 0 (shown)d uxx xxx  5iii   2 2 22 2 ed22 2 2 22 2 22 ed 22 d e3d ddBy (5ii), e 2e e 3 0, where edd dd d de0 dd d d By (5i), e ee ee d ln e e -------(1) e 1When 0, . 4 x x x yxxx x x x yx x x xx x x y yyx uu uxx uu u u xx x x uA B AB Ayx A B y AB xy                             2 3 1 So, 3 .4 eBy (1), e e3 e e3 x x x x x A BAAB Ay AA y        

6i Let 12 2, ,..., nx xx be the positions of the ( 1 )’s and ( 1 )’s. With this arrangement, we are able to find a consecutive pair of 1 and 1 in the clockwise direction (i.e. in the clockwise direction, the 1 precedes the 1 ). Remove this pair of numbers and there will be 22n numbers left arranged in the circle. We will repeat this procedure by removing consecutive pairs of 1  and 1 in the clockwise direction until there is a final pair of 1 and 1 left. Let kx be the position of this final 1 . We claim that kx is the starting position for which iT is never negative. Since the pairs of 1 ’s and 1 ’s removed were consecutive, and within each pair, the 1 preceded the 1 , there will always be an increase of the partial sum kT prior to a decrease. Hence, iT is never negative for all 12 in . Alternative Solution Let 12 2, ,..., nx xx be the positions of the ( 1 )’s and ( 1 )’s, and let 1x be the starting position. As we evaluate iT for 12 in , there exists a k such that kT is minimum. We then claim that 1kx  is a starting position for which iT is never negative for all 12 in . Relabel 12 1,..., , ,...,kn kx xx x as 12 2, ,..., ny yy respectively, so 11 ky x  is the starting position. To avoid confusion, we shall let iS be the new partial sum from position 1y to iy . Since kT is a minimum, 0 ii k kST T   for 12 in k  . With equal number of ( 1 )’s and ( 1 )’s, 2 0nT  . Hence, 2nk kST  . Furthermore, 0jk kjTT TT  for all 1 j k , we have that 22 2 0i n ki n k ki n kSS T T T        for 21 2nk i n . 6ii Note that (mod 2)iTi due to the following. Enumerate iT starting with the index 1i . We have 1 1 (mod 2)T  regardless of the first value, 1 or 1 . Subsequently, as the index i increases each time by 1, we add 1 or 1 to the value of iT , changing its parity. Hence, 22 11 2 0 (mod 2) nn i ii nT ni n n n        ; i.e. 2 1 n i i nT   is even. 7i cos sinac d   and sin cosbc d   7ii “” Suppose on the contrary that db , then acdb and cos sin cos sin 2 cos 4dc b b b          since 10c o s 24 2      . “” Choose  small enough such that sin : min ,ca c b d   . Then cos sin cos sincdccc a 