Try the followings:

The eleven members of a cricket team are numbered from \(1,2, \cdots ,11\). In how many ways can the entire cricket team sit on the eleven chairs arranged around a circular table so that the numbers of any two adjacent players differ by one or two?

Compute the maximum area of a rectangle which can be inscribed in a triangle of area \(M\).

Let \(f(x)=ax^2+bx+c\) where \(a,b,c \in \mathbb{R}\). Suppose \(f(-1),f(0),f(1) \in [-1,1]\). Prove that \( f(x) \in [-1.5,1.5]\) for all \(x \in [-1,1]\).

Let \(1,2,3, \cdots ,9,11,12, \cdots\) be the sequence of all the positive integers which do not contain the digit \(0\). Write \(\{a_n\}\) for this sequence. By comparing with a geometric series, show that \(\sum_n \frac{1}{a_n} < 90\).

There are \(100\) people in a queue waiting to enter a hall. The hall has exactly \(100\) seats numbered from \(1\) to \(100\). The first person in the queue enters the hall, chooses any seat and sits there. The \(n\)-th person in the queue where \(n\) can be \(2, \cdots ,100\), enters the hall after \((n−1)\)-th person is seated. He sits in seat number \(n\) if he finds it vacant; otherwise he takes any unoccupied seat. Find the total number of ways in which \(100\) seats can be filled up, provided the \(100\)-th person occupies seat number \(100\).

Let \(1 \leq r \leq n\). Consider all subsets of \(\{1,2, \cdots , n\}\) consisting of \(r\) elements. Let \(F(n,r)\) denote the arithmetic mean of the smallest elements of these subsets. Prove that \(F(n,r) = \displaystyle \frac{n+1}{r+1}\).

## Comments

Sort by:

TopNewestParamjit, the following answers the last one.

Consider the subsets that have the element "\(1\)" in them. Clearly,there would be \(\binom{n-1}{r-1}\) such subsets created by choosing remaining \(r-1\) elements from the remaining \(n-1\) elements.Obviously, in all such subsets "\(1\)" will be the smallest element.

Now for the subsets with 2. There would again be a total of\(\binom{n-1}{r-1}\) subsets out of which all do not satisfy the condition that "\(2\) is the smallest element. We want only those subsets which have '\(2\)" as he smallest element i.e., the subsets should not have the element "\(1\)" in them. There would be \(\binom{n-2}{r-1}\) such subsets obtained by choosing \(r-1\) elements of \(n-2\) elements ( i.e., excluding \( 1\) and \(2\) ).

For the subsets with "\(3\)" as the smallest element we would have to make subsets of \(r-1\) elements out of \(n-3\) elements (i.e., excluding \( 1, 2 \) and \(3\) ) giving us a \(\binom{n-3}{r-1}\) subsets.

Similarly for "\(4\)" there would be \(\binom{n-4}{r-1}\) subsets.

This idea can now be easily extrapolated for any \(k^{th}\) element for \( 1 \leq k \leq (n-r+1)\).

Now, for the Arithmetic mean.........

Total number of elements = \(\binom{n}{r}\)

Therefore, \[ F(n,r) = \frac{ \sum_{k=1}^{n-r+1} k\binom{n-k}{r-1}}{\binom{n}{r}}\]

The sum ( let it be \(S\) ) can be more explicitly written as,

\(S = \binom{n-1}{r-1}+ 2\binom{n-2}{r-1} + 3\binom{n-3}{r-1} + \dots + (n-r+1)\binom{r-1}{r-1} \)

\( S = \Bigg( \binom{n-1}{r-1} + \binom{n-2}{r-1} + \binom{n-3}{r-1} + \dots + \binom{r-1}{r-1} \Bigg)\)

\(+ \Bigg( \binom{n-2}{r-1} + \binom{n-3}{r-1} + \binom{n-4}{r-1} + \binom{n-5}{r-1} + \dots + \binom{r-1}{r-1} \Bigg)\)

\( + \dots \dots + \Bigg( \binom{r-2}{r-1} + \binom{r-1}{r-1} \Bigg) + \Bigg(\binom{r-1}{r-1}\Bigg) \)

Using the standard sum \( \binom{n}{r} + \binom{n-1}{r} + \binom{n-2}{r} +\binom{n-3}{r} + \dots + \binom{r}{r} = \binom{n+1}{r+1}\), we can evaluate the above expression.

\( \Rightarrow S = \bigg(\binom{n}{r}\bigg) + \bigg(\binom{n-1}{r}\bigg) + \bigg(\binom{n-2}{r}\bigg) + \bigg(\binom{n-3}{r}\bigg) + \dots + \bigg(\binom{r}{r}\bigg)\)

\( \Rightarrow S = \binom{n+1}{r+1} \)

Therefore, \( F(n,r) = \frac{\binom{n+1}{r+1}}{\binom{n}{r}} \Rightarrow F(n,r) = \frac{n+1}{r+1} \)

Note:I just used the property of the sum of combinatorial coefficients directly. Just in case you its proof as well, I can add that too. Also in the proof if we slightly change our method we can directly obtain \(S\). – Sudeep Salgia · 2 years, 9 months agoLog in to reply

For others, you may use this link for the proof of what Sudeep used. Lovely method! – Paramjit Singh · 2 years, 9 months ago

Log in to reply

For the fifth one, @Josh Rowley has provided an excellent solution in this note. – Sudeep Salgia · 2 years, 9 months ago

Log in to reply

– Paramjit Singh · 2 years, 9 months ago

Hurray! My answer was correct!Log in to reply

I guess it can be done in 22 ways. considering the rotation of 11 chairs as different cases. Here is my logic highest number is 11. So to his left and right only 9 and 10 can occupy. In similar logic 10 has left one side vacant which can be occupied by only 8. Going on further ,6,4,2,1 will be adjacent. Hence possible solution is 1,2,4,6,8,10,11,9,7,3,5 or 1,3,5,7,9,11,10,8,6,4,,2.

For all these 2 cases we can have 11 different chair positions each. Hence the total possible way must be 22 considering that each chair position is different.If rotation doesnt ,matters its 2 – Rashid Mohammed · 2 years, 8 months ago

Log in to reply

For second Question

Lets say base of triangle is B and height is H

Largest possible rectangle will be square

Its Side = B*H/(B+H) – Sanket Samant · 2 years, 8 months ago

Log in to reply

My proof for question 3 is kind of ugly, so I'm hoping someone can improve it. First, we may assume \( a \ge 0 \) since otherwise we could look at \( -f(x) \) instead of \( f(x) \). We can also assume that \( b \ge 0 \) since otherwise we could look at \( f(-x) \) instead of \( f(x) \) (note that this won't change \( a \)).

In this case, it's clear that the maximum value of \( f(x) \) on \( [-1,1] \) will occur at one of the endpoints, so all we have to show is that the minimum is greater than \( -1.5 \). It's enough to prove that this is true if \( m = {\rm min}(f(-1), f(0), f(1)) = -1 \), because otherwise \( f(x) - (m+1) \) will still satisfy the conditions of the problem plus our extra condition, and will have a smaller minimum than \( f(x) \), since \( m+1 \) would be positive. Also, we can assume that \( b \le 2a \), because the minimum value for \( f(x) \) is either at one of the endpoints, in which case there is nothing to prove, or at its one local minimum \( x = -b/2a \). So the only meaningful case is when that minimum \( x \)-value is greater than \( -1 \) (it's negative by the above assumptions on \( a \) and \( b \)). In this case the minimum value is \( -\frac{b^2}{4a}-c \).

The conditions of the problem imply the three inequalities \( -1 \le a-b+c \le 1 \), \( -1 \le c \le 1 \), and \( -1 \le a+b+c \le 1 \). We will use these repeatedly.

There are three cases. Case 1: \( f(1) = -1 \). Then \( a+b+c = -1 \) and \( a-b+c \ge -1 \) implies that \( b \le 0 \), but we've assumed \( b \ge 0 \), so \( b = 0 \). Now \( a+c = -1 \), \( a \ge 0 \), and \( c \ge -1 \) imply equality, so \( f(x) = -1 \), with a minimum greater than \( -1.5 \).

Case 2: \( f(0) = -1 \), so \( c = -1 \). So the minimum value is \( -\frac{b^2}{4a} - 1 \). Now we use \( a-b-1 \ge -1 \) and \( a+b-1 \le 1 \) to get \( a \ge b \) and \( a+b \le 2 \). Note that this implies \( b \le 1 \). So \( \frac{b}{a} \le 1 \) and \( \frac{b}4 \le \frac14 \), so \( \frac{b^2}{4a} \le \frac14 \), so the minimum is \( \ge -\frac54 \). (Equality holds when \( a = b = -c = 1 \).)

Case 3: \( f(-1) = -1 \). So \( a-b+c = -1 \). We use the two inequalities \( c \ge -1 \) and \( a+b+c \le 1 \) against the equality to get \( a \le b \) and \( b \le 1 \). Note that the minimum here is \( -\frac{b^2}{4a} - (b-1-a) = -\frac{(2a-b)^2}{4a} - 1 \). Now \( 2a-b \le a \le 1 \), so \( (2a-b)^2 \le a \cdot 1 \), so \( \frac{(2a^-b)^2}{4a} \le \frac14 \), so once again the minimum is at least \( -\frac54 \). (Equality holds when \( a = b = -c = 1 \) as above.)

If I got all this right, I'm pretty sure I proved that \( f(x) \in [-1.25,1.25] \), which is the strongest possible (since if \( f(x) = x^2+x-1 \), \( f(-0.5) = -1.25 \)). – Patrick Corn · 2 years, 9 months ago

Log in to reply

The first one (quite a cool result):

I assume that being in a circle the seats themselves are not numbered, so if you can rotate one seating so that it becomes another, these 2 will in fact be considered the same.

Firstly, consider the question with only 3 people. We clearly only have 2 options (in clockwise order): \[ (1,2,3) \] \[ (1,3,2) \]

Consider what happens now when we had a 4th person. There are only 2 numbers in the set \[ { 1,2,3 } \] which are either 1 or 2 away from 4, namely 2 and 3. More generally, if we have a valid arrangement with \( n \) cricketers and then an \( n+1 \)th cricketer appears, he can only sit in one place - between cricketer \( n \) and cricketer \( n-1 \). Therefore we have the trivial recursion that \[ f(n+1) = f(n) \] when \( n \geq 3 \) Therefore the number of seatings for 11 cricketers is \( f(11) = f(3) = \fbox{2} \) – Josh Rowley · 2 years, 9 months ago

Log in to reply

– Paramjit Singh · 2 years, 9 months ago

I think you are missing something. Simply consider this: Consider the cricketers numbered \(1,2, \cdots , 11\) around a circle in order \((1,2, \cdots ,11)\). Clearly, you can swap places \((n,n+1)\) for \(n \in \{2,3, \cdots 10\}\) without disturbing the condition, and you can possibly cause such simultaneous swaps. All these configurations are valid and more than two in number.Log in to reply

The only configuration for the 4 cricketers between \( C_{1} \) and \( C_{11} \) is \( 3,5,7,9 \). We then see that \( C_{10} \) must hold the other spot next to \( C_{11} \), since otherwise \( C_{11} \) will be next to someone whose label is more than 2 different from his. We only have the even numbers to place so it is trivial to see that the other half of the circle must go \( 2,4,6,8,10 \).

Therefore \( (4,5) \) yields one arrangement and \( (5,4) \) yields one arrangement, so there are \( \fbox{2} \) – Josh Rowley · 2 years, 9 months ago

Log in to reply

– Paramjit Singh · 2 years, 9 months ago

Nice solution!Log in to reply

– Siddhartha Srivastava · 2 years, 9 months ago

If you put them in order \( (1,2,3,\dots,11) \), you'll have \( 1 \) next to \( 11 \), which is invalid.Log in to reply

circular! Got it! Thanks. – Paramjit Singh · 2 years, 9 months agoLog in to reply

54 – Sankalp Chawla · 2 years, 9 months ago

Log in to reply

– Paramjit Singh · 2 years, 9 months ago

First one? Care to give a proof?Log in to reply