Question 2: 2 Section II (20 Marks) (a) Prove that any permutation of…

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]