Mathematical Thinking Quiz 2: 4 August 2024 (May 2024 term)

1 Section I (10 Marks)

1. Consider the graph $G$ whose adjacency matrix is provided below. [Marks: 4]

$\begin{bmatrix} 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 \end{bmatrix}$

Choose all the correct option(s).

(a) The degree of every vertex of $G$ is 2.

(b) There are 7 edges in $G$.

(c) $G$ has a proper 3-colouring.

(d) $G$ is not planar.

1. How many inversions does the permutation 41235 (one-line notation) have ? [Marks: 2]

2. Which of the following options is/are true? [Marks: 4]

(a) If $\phi$ is the Euler's totient function, then $\phi(n)$ is odd for all $n > 2$.

(b) There is a natural number $n > 3$ for which the numbers $n, n+2, n+4$ are all prime.

(c) Let $n \geq 1$. Then $78n + 15$ cannot be a prime.

(d) $\sum_{k=1}^{n-1} \binom{n}{k} = 2^n - 2$ for all $n \geq 2$.

2 Section II (20 Marks)

1. (a) Prove that any permutation of $1, 2, \ldots, n$ can have at most $\dfrac{n(n-1)}{2}$ inversions. [Marks: 5]

(b) Construct an example of a permutation of $\{1, 2, 3, 4, 5\}$ with exactly 7 inversions. [Marks: 5]

1. (a) In a classroom, there are 25 students. Each student is asked to choose any number from 1 to 10. Prove that there must exist a number which is chosen by at least 3 students. [Marks: 5]

(b) More generally, fix a natural number $n$. Suppose there are $k$ students in the class and each of them chooses a number from 1 to 10. Find the minimum value of $k$ to guarantee that some number will be chosen by at least $n$ students? [Marks: 5]