Question 1

**1 Note to Students** - Section-1 is objective (MCQ-MSQ-NAT). You will be given full marks if your final answer is correct. You are encouraged to write down the steps you used to arrive at the solution. This would help us in awarding partial marks if your final answer is incorrect. - Section-2 has short-answer type questions. You have to give a detailed explanation of your solution to each question. **2 Section-1 (16 marks)** 1. (4 points) Consider a graph $G$ whose adjacency matrix is given below: $$\begin{bmatrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \end{bmatrix}$$ Which of the following are true? (MSQ) (a) $G$ is a tree.\ (b) The chromatic number of $G$ is 2.\ (c) $G$ is not planar.\ (d) $G$ is not bipartite. 2. (4 points) Which of the following are true? $\phi$ is Euler’s Totient function. (MSQ) (a) For every positive integer $n$, there exist primes $p$ and $q$ such that $|p - q| \geq n$\ (b) $\phi(mn) = \phi(m)\phi(n)$ for all $m, n \in \mathbb{N}$\ (c) $\phi(100) = 40$\ (d) $\phi(n)$ is even if and only if $n$ is prime. 3. (4 points) Compute the following quantities. (a) (2 points) The inversion table for a permutation $\sigma \in \text{Perm}(8)$ is 22020210. Find the permutation $\sigma$. \_\_\_\_\_\_\_\_\_\_ (b) (2 points) If $D_n$ is the number of derangements of $n$ objects, find $\dfrac{D_{2025} + 1}{D_{2024}}$. \_\_\_\_\_\_\_\_\_\_ 4. (4 points) For each question, give an example if such a graph exists. If it doesn’t, enter “impossible” as the answer. (a) (2 points) A graph $G = (V, E)$ with $|V| = 5$ such that the degree of each vertex is two.\ (b) (2 points) A graph $G = (V, E)$ with $|V| = 6$ and $|E| = 5$ such that $G$ is *not* a tree. **3 Section II (14 Marks)** 5. (7 points) Ten students solved a total of 35 problems in a math contest. Each problem was solved by exactly one student. There is at least one student who has solved exactly one problem, at least one student who has solved exactly two problems, and at least one student who has solved exactly three problems. Show that there is at least one student who has solved at least five problems. 6. (7 points) There are $n$ people who have applied for an expedition. A set of $k$ people get chosen for the expedition, where $1 \leq k \leq n$ and one of these $k$ people is nominated as the captain of the expedition team. For instance, if $n = 2$, there are four possible teams: $$\left\{\boxed{1}\right\}, \left\{\boxed{2}\right\}, \left\{\boxed{1}, 2\right\}, \left\{1, \boxed{2}\right\}.$$ The number within the box is the captain. (a) (2 points) Find (as a function of $n$) the total number of teams of all possible sizes which have a given person as captain – for instance in the above $n = 2$ example, there are two teams which have person **1** as captain and two teams with person **2** as captain.\ (b) (2 points) Find the total number of teams of all possible sizes.\ (c) (3 points) Using the above result (or otherwise), prove the following identity for all $n \in \mathbb{N}$: $$1 \cdot \binom{n}{1} + 2 \cdot \binom{n}{2} + 3 \cdot \binom{n}{3} + \cdots + n \cdot \binom{n}{n} = n \cdot 2^{n-1}$$