Miscellaneous questions: part II: solutions to tutorial practice for preRMO and RMO

Refer the blog questions a few days before:

Question 1:

Let $a_{1}, a_{2}, \ldots, a_{10}$ be ten real numbers such that each is greater than 1 and less than 55. Prove that there are three among the given numbers which form the lengths of the sides of a triangle.

Answer 1:

Without loss of generality, we may take $1<a_{1}\leq a_{2}\leq \ldots \leq a_{10}<55$ …..call this relation (i).

Let, if possible, no three of the given numbers be the lengths of the sides of a triangle. (That is, no three satisfy the triangle inequality. Note that when we say three numbers a, b and c satisfy the triangle inequality —- it means all the following three inequalities have to hold simultaneously: $a+b>c$ , $a+c>b$ and $b+c>a$ ). We will consider triplets $a_{i}, a_{i+1}, a_{i+2}$ and $1 \leq i \leq 8$ . As these numbers do not form the lengths of the sides of a triangle, the sum of the smallest two numbers should not exceed the largest number, that is, $a_{i}+a_{i+1} \leq a_{i+2}$ . Hence, we get the following set of inequalities:

$i=1$ gives $a_{1}+a_{2} \leq a_{3}$ giving $2 < a_{3}$ .

$i=2$ gives $a_{2}+a_{3} \leq a_{4}$ giving $3 < a_{4}$

$i=3$ gives $a_{3}+a_{4} \leq a_{5}$ giving $5 < a_{5}$

$i=4$ gives $a_{4}+a_{5} \leq a_{6}$ giving $8 < a_{6}$

$i=5$ gives $a_{5}+a_{6} \leq a_{7}$ giving $13 < a_{7}$

$i=6$ gives $a_{6}+a_{7} \leq a_{8}$ giving $21 < a_{8}$

$i=7$ gives $a_{7}+a_{8} \leq a_{9}$ giving $34 < a_{9}$

$i=8$ gives $a_{8}+a_{9} \leq a_{10}$ giving $55<a_{10}$

contradicting the basic hypothesis. Hence, there exists three numbers among the given numbers which form the lengths of the sides of a triangle.

Question 2:

In a collection of 1234 persons, any two persons are mutual friends or enemies. Each person has at most 3 enemies. Prove that it is possible to divide the collection into two parts such that each person has at most 1 enemy in his sub-collection.

Answer 2:

Let C denote the collection of given 1234 persons. Let $\{ C_{1}, C_{2}\}$ be a partition of C. Let $e(C_{1})$ denote the total number of enemy pairs in $C_{1}$ . Let $e(C_{2})$ denote the total number of enemy pairs in $C_{2}$ .

Let $e(C_{1}, C_{2})= e(C_{1})+e(C_{2})$ denote the total number of enemy pairs corresponding to the partition $\{ C_{1}, C_{2}\}$ of C. Note $e(C_{1}, C_{2})$ is an integer greater than or equal to zero. Hence, by Well-Ordering Principle, there exists a partition having the least value of $e(C_{1}, C_{2})$ .

Claim: This is “the” required partition.

Proof: If not, without loss of generality, suppose there is a person P in $C_{1}$ having at least 2 enemies in $C_{1}$ . Construct a new partition $\{D_{1}, D_{2}\}$ of C as follows: $D_{1}=C_{1}-\{ P \}$ and $D_{2}=C_{2}- \{P\}$ . Now, $e(D_{1}, D_{2})=e(D_{1})+e(D_{2}) \leq \{ e(C_{1})-2\} + \{ e(C_{2})+1\}=e(C_{1}, C_{2})-1$ . Hence, $e(D_{1}, D_{2})<e(C_{1}, C_{2})$ contradicting the minimality of $e(C_{1}, C_{2})$ . QED.

Problem 3:

A barrel contains 2n balls, numbered 1 to 2n. Choose three balls at random, one after the other, and with the balls replaced after each draw.

What is the probability that the three element sequence obtained has the properties that the smallest element is odd and that only the smallest element, if any is repeated?

Answer 3:

The total number of possible outcomes is $N=2n \times 2n \times 2n=8n^{3}$ . To find the total number of favourable outcomes we proceed as follows:

Let a be any odd integer such that $1 \leq a \leq 2n-1$ and let us count the sequences having a as least element.

(i) There is only one sequence $(a,a,a)$ with a repeated thrice.

(ii) There are $2n-a$ sequences of the form $(a,a,b)$ with $a<b \leq 2n$ . For each such sequence there are three distinct permutations possible. Hence, there are in all $3(2n-a)$ sequences with a repeated twice.

iii) When $n>1$ , for values of a satisfying $1 \leq a \leq (2n-3)$ , sequences of the form $(a,b,c,)$ with $a<b<c \leq 2n$ are possible and the number of such sequences is $r=1+2+3+\ldots+(2n+a-1)=\frac{1}{2}(2n-a)(2n-a-1)$ . For each such sequence, there are six distinct permutations possible. Hence, there are $6r=3(2n-a)(2n-a-1)$ sequences in this case.

Hence, for odd values of a between 1 and $2n-1$ , the total counts of possibilities $S_{1}$ , $S_{2}$ , $S_{3}$ in the above cases are respectively.

$S_{1}=1+1+1+\ldots+1=n$

$S_{2}=3(1+3+5+\ldots+(2n-1))=3n^{2}$

$3(2 \times 3 + 4 \times 5 + \ldots+ (2n-2)(2n-1))=n(n-1)(4n+1)$ .

Hence, the total number A of favourable outcomes is $A=S_{1}+S_{2}+S_{3}=n+3n^{2}+n(n-1)(4n+1)=4n^{3}$ . Hence, the required probability is $\frac{A}{N} = \frac{4n^{3}}{8n^{3}} = \frac{1}{2}$ . QED>

Cheers,

Nalin Pithwa

For the love of Maths: the Queen of all Sciences

Miscellaneous questions: part II: solutions to tutorial practice for preRMO and RMO

Leave a Reply Cancel reply

Share this:

Like this:

Related

Leave a Reply Cancel reply