2022 A Levels H3 Math Paper 1 Soln

Solutions 1. (a) (i) 104 1048576= (ii) S: set of all possible gradings received by the 10 students , , , ,A B C DA A A A : set of all possible gradings received by the 10 students where grade A, B, C, D respectively is not achieved by any student. 104S = 103AA = , 102ABAA= , 101A B CAAA  = , 0A B C DA A A A   = Number of possible gradings if every grade is achieved by at least one student, 10 10 10 104 4 44 3 2 1 01 2 3 818520 A B C D A B C DA A A A S A A A A   = −         = − + − +           = (iii) ( )818520 10, 4 4!S= ( )10, 4 34105S = (b) 1nk+ . Idea Special case: Consider a partition of n distinct objects into k non-empty subsets where there are 1k− subsets of 1 object each and the kth subset contains the remaining ( )12nk− +  objects:        1 , 2 , , 1 , , 1, ,k k k n−+  . There are at least nk− distinct ways to split the kth subset to produce a ( )1 thk+ subset of a single object ( 1nk−+ ways if 13nk− +  ):

2          1 , 2 , , 1 , , 1, ,k k k n−+           1 , 2 , , 1 , 1 , , 2, ,k k k k n− + +            1 , 2 , , 1 , , , , 1k n k n−−  Illustration: A partition of 4 objects into 2 subsets:    1 , 2,3, 4 . The second subset contains 4 2 1 3− + = terms, which can be split in 3 ways:      1 , 2 , 3, 4 ,      1 , 3 , 2, 4 ,      1 , 4 , 2,3 . A partition of 3 objects into 2 subsets:    1 , 2,3 . The second subset contains 3 2 1 2− + = terms, which can be split in 1 way:      1 , 2 , 3 . Solution General case: Consider a partition X of n distinct objects into k non-empty subsets 1nk+ . Since the subsets are non-empty, they contain at least 1 object each. The remaining nk− objects ( 1a , 2a ,  , nka − ) are distributed among the k subsets. We can split the subset(s) containing these nk− objects by creating an additional subset containing a single object from these nk− objects in turn. There are thus nk− possible distinct partitions of 1k+ subsets created. Hence X is the ancestor of at least nk− partitions into 1k+ non-empty subsets. (ii) Let A be the set of partitions of n distinct objects into k non-empty subsets which are ancestors of some partition of n distinct objects into 1k+ non-empty subsets. Let B be the set of partitions (descendants) of n distinct objects into 1k+ non-empty subsets which have ancestors in A. The mapping from ancestors to descendants where Y is a descendant of X if Y is obtained from X by splitting one subset of X into two, is surjective. Hence AB . Number of partitions of n distinct objects into k and 1k+ non-empty subsets are ( ),S n k and ( ),1S n k + respectively. By (b)(i), each partition X is the ancestor of at least nk− partitions into 1k+ non- empty subsets. Hence there are at least ( ) ( ),n k S n k− descendants (not necessarily distinct).

3 On the other hand, there are ( ),1S n k + partitions of n distinct objects into 1k+ non- empty subsets. For each partition, there are 1 2 k+  ways to combine 2 subsets to result in a partition of k non-empty subsets. By (MP), there are ( ) 1 ,12k S n k+ + ancestors (not necessarily distinct). Hence ( ) ( ) ( ) 1 , 1 ,2k S n k A B n k S n k+ +    − . When 1nk=+ , for each partition of n distinct objects into k non-empty subsets, there is only one subset which contains 2 elements, and this subset is split to yield only 1 descendant. In this case, LHS: ( ) ( ) ( ) 1, 1 1, 2kn k S n k S k k +− =  + =  RHS: ( ) ( ) 1 1 1 , 1 1, 12 2 2k k k S n k S k k+ + +      + = + + = =           LHS Conversely, when equality holds, i.e. number of ancestors = number of descendants, this is only possible if 1nk=+ . 2 (a) Let ,,x a y b z c= = = be an integer solution of the equation 2 2 2 3x y z xyz+ + = . 1 Prove that , 3 ,x a y ab c z b= = − = is also a solution of the equation. [3] (b) Starting with the solution 1, 1, 1x y z= = = of equation 1 , use the result of part (a) to find three further solutions. [2] (c) Use the result of part (a) to prove that ( ) ( ) 22 2 1 2 1 2 1 2 113 n n n nF F F F+ − + −+ + = , where nF are the Fibonacci numbers defined by 12 1, 1FF== and 11n n nF F F+−=+ for 2n . [5] 2 (a) Since ,,x a y b z c= = = is an integer solution of the equation 2 2 2 3x y z xyz+ + = , it follows that 2 2 2 3a b c abc+ + = . (1)

4 We must show that ( ) ( ) 222 3 3 3a ab c b a ab c b+ − + = − . ( ) 22 2 2 2 2 2 23 9 6a ab c b a b c a b abc+ − + = + + + − ( ) (1) 223 9 6 33 abc a b abc a ab c b = + − =− (b) 1, 1, 1x y z= = = is a particular solution of equation 1 . By (a) with 1abc= = = , 1, 2, 1x y z= = = is a 2nd solution. By (a) with 1, 2, 1a b c= = = , 1, 5, 2x y z= = = is a 3rd solution. By (a) with 1, 5, 2a b c= = = , 1, 13, 5x y z= = = is a 4th solution. (c) We have 1 2 3 4 5 6 71, 1, 2, 3, 5, 8, 13,F F F F F F F= = = = = = =  . To prove ( ) ( ) 22 2 1 2 1 2 1 2 113 n n n nF F F F+ − + −+ + = , n +  (*) amounts to proving ( )2 1 2 11, , nnFF+− is a solution of 1 for all n +  . Since 2 2 2 2 2 2 1 2 3 1 2 3 1 1 2 6 3 1 1 2 3F F F F F F+ + = + + = =    = , we conclude that ( )311, ,FF is a solution of 1 and so (*) holds for 1n= . Assume (*) holds for some k +  . That is, ( ) ( ) 22 2 1 2 1 2 1 2 113 k k k kF F F F+ − + −+ + = for some k +  . That is, ( )2 1 2 11, , kkFF+− is a solution of 1 . By (a), ( )2 1 2 1 2 11,3 , k k kF F F+ − +− is a solution of 1 . We wish to show ( )2 3 2 11, , kkFF++ is also a solution of 1 . That is, we must show 2 3 2 1 2 13k k kF F F+ + −=− or 2 3 2 1 2 1 3k k kF F F+ − ++= . 2 3 2 1 2 2 2 1 2 1k k k k kF F F F F+ − + + −+ = + + 2 1 2 2 1 2 1 2 1 2 2 1 2 1 2 1 21 2 2 3 k k k k k k k kk k F F F F F F F FF F + + − +− ++ + = + + + = + + =+ = Thus ( )2 3 2 11, , kkFF++ is a solution of 1 and (*) holds by induction.

5 3 For any real number s, the greatest integer less than or equal to s is denoted by s . For example, 3.7 3= and 55= . (a) For any positive integer a and real number t, it is given that t can be written as an p+ , where n is an integer and 0ap . Prove that 0 d a xt xta+ = . [4] (b) For any positive integers a and b and real number x, (i) prove that x xa b ab    =  , [4] (ii) find ( ) ( )( ) 0 fg gf d ab x x x− where ( )f xax b+= and ( )g xbx a+= . [4] 3 (a) x an p x p naa+ + +    =+       . Consider the mutually exclusive intervals  )0,ap− and  ,a p a− whose union is the closed interval  0,a . 0 0 1 x p x px a p n n aa++   −     + =  . 1 1 1 1 x p a pa p x a aa x p x pn n n aa ++−      +  +     + = + + − = +      since 0 1 1 1x p a p pa a a++ −  − =  . 00 d d aa x an p x p x n xaa+ + +    =+       0 d d a p a ap x p x pn x n xaa− −++   = + + +       ( ) 0 d 1 d a p a ap n x n x − − = + + ( ) ( )1n a p n p= − + +

6 an p t =+ = (b) (i) For any positive integer a and real number x, x an p=+ , where n is an integer and 0ap . [Note: The representation is not unique. For example, ( ) ( ) ( )5.4 3 1 2.4 or 6 0 5.4 or 1 5 0.4= + + + etc.] x an p p na a a b b b    +         +                    ==                 