Waste less time on Facebook — follow Brilliant.
×

Problematic Problems

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}\).

Note by Paramjit Singh
3 years, 1 month ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Paramjit, 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 · 3 years, 1 month ago

Log in to reply

@Sudeep Salgia Excellent! I deduced the expression, but didn't apply the hockey stick identity (as you did) to solve it. Thanks! I know it's proof.

For others, you may use this link for the proof of what Sudeep used. Lovely method! Paramjit Singh · 3 years, 1 month ago

Log in to reply

For the fifth one, @Josh Rowley has provided an excellent solution in this note. Sudeep Salgia · 3 years, 1 month ago

Log in to reply

@Sudeep Salgia Hurray! My answer was correct! Paramjit Singh · 3 years, 1 month ago

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 · 3 years 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 · 3 years 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 · 3 years, 1 month 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 · 3 years, 1 month ago

Log in to reply

@Josh Rowley 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. Paramjit Singh · 3 years, 1 month ago

Log in to reply

@Paramjit Singh The answer is 2. I will show you in a second way: Denote 'cricket \( i \)' as \( C_{i} \). \( C_{1} \) must be sitting somewhere, and so must \( C_{11} \). Define \( a \) as the number of cricketers going clockwise from \( C_{1} \) to \( C_{11} \) (non-inclusive) and define \( b \) as the number of cricketers going clockwise from \( C_{11} \) to \( C_{1} \) (non-inclusive). Clearly, \( a + b = 11 - 2 = 9 \). We are now going to try and find the minimum possible value of \( a \). To minimise it we should have people sitting next to people 2 away from their number, so the minimum value of \( a \) occurs when we have \[ 1,3,5,7,9,11,?,?,?,?,? \] Therefore the minimum possible value of \( a \) is 4. An indentical argument holds to show that \( min(b) = 4 \). Therefore the only integer solutions \( (a,b) \) to \( a + b = 9 \) are \( (4,5) \) and \( (5,4) \).

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 · 3 years, 1 month ago

Log in to reply

@Josh Rowley Nice solution! Paramjit Singh · 3 years, 1 month ago

Log in to reply

@Paramjit Singh If you put them in order \( (1,2,3,\dots,11) \), you'll have \( 1 \) next to \( 11 \), which is invalid. Siddhartha Srivastava · 3 years, 1 month ago

Log in to reply

@Siddhartha Srivastava Oh, it's circular! Got it! Thanks. Paramjit Singh · 3 years, 1 month ago

Log in to reply

54 Sankalp Chawla · 3 years, 1 month ago

Log in to reply

@Sankalp Chawla First one? Care to give a proof? Paramjit Singh · 3 years, 1 month ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...