Problematic Problems

Try the followings:

  • The eleven members of a cricket team are numbered from 1,2,,111,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 MM.

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

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

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

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

Note by A Brilliant Member
5 years, 7 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

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 - 5 years, 7 months 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 - 5 years, 7 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 a0 a \ge 0 since otherwise we could look at f(x) -f(x) instead of f(x) f(x) . We can also assume that b0 b \ge 0 since otherwise we could look at f(x) f(-x) instead of f(x) f(x) (note that this won't change a a ).

In this case, it's clear that the maximum value of f(x) f(x) on [1,1] [-1,1] will occur at one of the endpoints, so all we have to show is that the minimum is greater than 1.5 -1.5 . It's enough to prove that this is true if m=min(f(1),f(0),f(1))=1 m = {\rm min}(f(-1), f(0), f(1)) = -1 , because otherwise f(x)(m+1) 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) f(x) , since m+1 m+1 would be positive. Also, we can assume that b2a b \le 2a , because the minimum value for f(x) 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 x = -b/2a . So the only meaningful case is when that minimum x x -value is greater than 1 -1 (it's negative by the above assumptions on a a and b b ). In this case the minimum value is b24ac -\frac{b^2}{4a}-c .

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

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

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

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

If I got all this right, I'm pretty sure I proved that f(x)[1.25,1.25] f(x) \in [-1.25,1.25] , which is the strongest possible (since if f(x)=x2+x1 f(x) = x^2+x-1 , f(0.5)=1.25 f(-0.5) = -1.25 ).

Patrick Corn - 5 years, 7 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,2,3) (1,3,2) (1,3,2)

Consider what happens now when we had a 4th person. There are only 2 numbers in the set 1,2,3 { 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 n cricketers and then an n+1 n+1 th cricketer appears, he can only sit in one place - between cricketer n n and cricketer n1 n-1 . Therefore we have the trivial recursion that f(n+1)=f(n) f(n+1) = f(n) when n3 n \geq 3 Therefore the number of seatings for 11 cricketers is f(11)=f(3)=2 f(11) = f(3) = \fbox{2}

Josh Rowley - 5 years, 7 months ago

Log in to reply

I think you are missing something. Simply consider this: Consider the cricketers numbered 1,2,,111,2, \cdots , 11 around a circle in order (1,2,,11)(1,2, \cdots ,11). Clearly, you can swap places (n,n+1)(n,n+1) for n{2,3,10}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.

A Brilliant Member - 5 years, 7 months ago

Log in to reply

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

The only configuration for the 4 cricketers between C1 C_{1} and C11 C_{11} is 3,5,7,9 3,5,7,9 . We then see that C10 C_{10} must hold the other spot next to C11 C_{11} , since otherwise C11 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 2,4,6,8,10 .

Therefore (4,5) (4,5) yields one arrangement and (5,4) (5,4) yields one arrangement, so there are 2 \fbox{2}

Josh Rowley - 5 years, 7 months ago

Log in to reply

@Josh Rowley Nice solution!

A Brilliant Member - 5 years, 7 months ago

Log in to reply

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

Siddhartha Srivastava - 5 years, 7 months ago

Log in to reply

@Siddhartha Srivastava Oh, it's circular! Got it! Thanks.

A Brilliant Member - 5 years, 7 months ago

Log in to reply

For the fifth one, @Josh Rowley has provided an excellent solution in this note.

Sudeep Salgia - 5 years, 7 months ago

Log in to reply

Hurray! My answer was correct!

A Brilliant Member - 5 years, 7 months ago

Log in to reply

Paramjit, the following answers the last one.
Consider the subsets that have the element "11" in them. Clearly,there would be (n1r1)\binom{n-1}{r-1} such subsets created by choosing remaining r1r-1 elements from the remaining n1n-1 elements.Obviously, in all such subsets "11" will be the smallest element.
Now for the subsets with 2. There would again be a total of(n1r1)\binom{n-1}{r-1} subsets out of which all do not satisfy the condition that "22 is the smallest element. We want only those subsets which have '22" as he smallest element i.e., the subsets should not have the element "11" in them. There would be (n2r1)\binom{n-2}{r-1} such subsets obtained by choosing r1r-1 elements of n2n-2 elements ( i.e., excluding 1 1 and 22 ).

For the subsets with "33" as the smallest element we would have to make subsets of r1r-1 elements out of n3n-3 elements (i.e., excluding 1,2 1, 2 and 33 ) giving us a (n3r1)\binom{n-3}{r-1} subsets.
Similarly for "44" there would be (n4r1)\binom{n-4}{r-1} subsets.
This idea can now be easily extrapolated for any kthk^{th} element for 1k(nr+1) 1 \leq k \leq (n-r+1).

Now, for the Arithmetic mean.........
Total number of elements = (nr)\binom{n}{r}
Therefore, F(n,r)=k=1nr+1k(nkr1)(nr) F(n,r) = \frac{ \sum_{k=1}^{n-r+1} k\binom{n-k}{r-1}}{\binom{n}{r}}

The sum ( let it be SS ) can be more explicitly written as,
S=(n1r1)+2(n2r1)+3(n3r1)++(nr+1)(r1r1)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=((n1r1)+(n2r1)+(n3r1)++(r1r1)) S = \Bigg( \binom{n-1}{r-1} + \binom{n-2}{r-1} + \binom{n-3}{r-1} + \dots + \binom{r-1}{r-1} \Bigg)

+((n2r1)+(n3r1)+(n4r1)+(n5r1)++(r1r1))+ \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)

++((r2r1)+(r1r1))+((r1r1)) + \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 (nr)+(n1r)+(n2r)+(n3r)++(rr)=(n+1r+1) \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.

S=((nr))+((n1r))+((n2r))+((n3r))++((rr)) \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)

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

Therefore, F(n,r)=(n+1r+1)(nr)F(n,r)=n+1r+1 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 SS.

Sudeep Salgia - 5 years, 7 months ago

Log in to reply

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!

A Brilliant Member - 5 years, 7 months ago

Log in to reply

54

Sankalp Chawla - 5 years, 7 months ago

Log in to reply

First one? Care to give a proof?

A Brilliant Member - 5 years, 7 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...