cmi-entrance 2016 QB4

cmi-entrance · India · ugmath 14 marks Number Theory Combinatorial Number Theory and Counting

Let $A$ be a non-empty finite sequence of $n$ distinct integers $a_{1} < a_{2} < \cdots < a_{n}$. Define
$$A + A = \left\{ a_{i} + a_{j} \mid 1 \leq i, j \leq n \right\}$$
i.e, the set of all pairwise sums of numbers from $A$. E.g., for $A = \{1,4\}$, $A + A = \{2,5,8\}$.
(a) Show that $|A + A| \geq 2n - 1$. Here $|A + A|$ means the number of elements in $A + A$.
(b) Prove that $|A + A| = 2n - 1$ if and only if the sequence $A$ is an arithmetic progression.
(c) Find a sequence $A$ of the form $0 < 1 < a_{3} < \cdots < a_{10}$ such that $|A + A| = 20$.

Let $A$ be a non-empty finite sequence of $n$ distinct integers $a_{1} < a_{2} < \cdots < a_{n}$. Define

$$A + A = \left\{ a_{i} + a_{j} \mid 1 \leq i, j \leq n \right\}$$

i.e, the set of all pairwise sums of numbers from $A$. E.g., for $A = \{1,4\}$, $A + A = \{2,5,8\}$.

(a) Show that $|A + A| \geq 2n - 1$. Here $|A + A|$ means the number of elements in $A + A$.

(b) Prove that $|A + A| = 2n - 1$ if and only if the sequence $A$ is an arithmetic progression.

(c) Find a sequence $A$ of the form $0 < 1 < a_{3} < \cdots < a_{10}$ such that $|A + A| = 20$.

Paper Questions

QB1 QB2 QB3 QB4 QB5 QB6 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 Q10