Be aware that work that is illegible, because of poor hand-writing say, or due to poor contrast within the scan or photograph, will not be marked.

Where it is reasonable to work out large numbers exactly with a calculator, you should do so. Furthermore, solutions without at least a brief explanation or justification will receive no, or only partial, marks.

1. (a) An online portal requires a user to login with a password, which must be from 6 to 8 characters long where each character is an uppercase letter or a digit. A password must contain at least 1 digit. How many possible passwords are there?

(b) Suppose we choose a day of the week 100 times. For example: ‘Wed’, ‘Mon’, ‘Mon’, ‘Sun’, ‘Sat’ and so on. Prove that, no matter what sequence of days we choos (randomly or otherwise) to write down, we must have written down at least one of the days of the week at least 15 times.

(c) In how many different ways can the letters of REARRANGEMENT be arranged?

(d) How many bit strings containing exactly eight 0s and twelve 1s have either all the 0s consecutive, or have all the 1s consecutive?

2. Consider the non-negative integer solutions for the equation x1 + x2 + x3 + x4 + x5 = 36.

(a) How many distinct solutions are there?

(b) How many distinct solutions are there if x1 ≥ 12 ?

(c) How many distinct solutions are there if x1 < 18 ?

(d) How many distinct solutions are there if x1 < 18 and x2 < 6 ?

3.Let g be the greatest common divisor of 9883529 and 759345. Find g using the Extended Euclid’s algorithm implemented via the ‘table method’, and hence find
integers x and y so that g = 9883529 x + 759345 y .

4. Use Euclid’s algorithm to find integers x, y and d for which 3936 x + 1293 y = d is the smallest possible positive integer. Using your answers to this as your starting point, do the following tasks.

(a) Find a solution of 3936 x ≡ d mod 1293.

(b) Find an integer r that has the property that r ≡ d mod 1293 and r ≡ 0 mod 3936.

(c) Find an integer R that has the property that R ≡ 126 mod 1293 and R ≡ 0 mod 3936.

(d) Find an integer s that has the property that s ≡ d mod 3936 and s ≡ 0 mod 1293.

(e) Find an integer S that has the property that S ≡ 573 mod 3936 and S ≡ 0 mod 1293.

(f) Find an integer T that has the property that T ≡ 126 mod 1293 and T ≡ 573 mod 3936.

(g) Is T the only number satisfying those two congruences; if not, which other numbers?