IMO Shortlist
counting
binomial coefficients
algebra
combinatorics

Let $n \geq 1$ be an integer. A [b]path[/b] from $(0,0)$ to $(n,n)$ in the $xy$ plane is a chain of consecutive unit moves either to the right (move denoted by $E$) or upwards (move denoted by $N$), all the moves being made inside the half-plane $x \geq y$. A [b]step[/b] in a path is the occurence of two consecutive moves of the form $EN$. Show that the number of paths from $(0,0)$ to $(n,n)$ that contain exactly $s$ steps $(n \geq s \geq 1)$ is

\[\frac{1}{s} \binom{n-1}{s-1} \binom{n}{s-1}.\]

Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=15623]introduction for the IMO ShortList/LongList project[/url] and regarding[url=http://www.mathlinks.ro/Forum/viewtopic.php?t=15623]solutions[/url]  :)

Define by $ f(k,l)$ the number of paths from $ (0,0)$ to $ (k,k)$ containing exactly $ l$ steps ($ 1\leq l\leq k$).
We will prove the result of the problem using mathematical induction, ie for any positive integers $ n, s$ and $ 1\leq s\leq n$ we have $ f(n,s) = \frac{1}{s}\binom{n - 1}{s - 1}\binom{n}{s - 1}$
[b]Base Step[/b]: For $ s = 1$ because the first move is $ E$ and last one is $ N$ (as we can only move in the half-plane $ x\geq y$), and there is only one move $ EN$ then there is only one path from $ (0,0)$ to $ (n,n)$ -- $ n$ $ E$ moves followed by $ n$ $ N$ moves. Therefore, $ f(n,1) = 1$ and $ \frac{1}{1}\binom{n - 1}{1 - 1}\binom{n}{1 - 1} = 1$ so the result is true for $ (n,1)$. Also, for $ n = 2$ if $ s = 1$ get the case $ (n,1)$ and if $ s = 2$ by inspection there is only one path with required properties, so $ f(2,2) = 1$ and $ \frac{1}{2}\binom{2 - 1}{2 - 1}\binom{2}{2 - 1} = 1$ so result is true for $ (2,2)$.
[b]Induction Step[/b]: Assume for $ n$ the result is true, ie for any $ 1\leq s\leq n$ where $ s$ is an integer, we have $ f(n,s) = \frac{1}{s}\binom{n - 1}{s - 1}\binom{n}{s - 1}$.
Call a path $ (k,l)$ a path from $ (0,0)$ to $ (k,k)$ with $ l$ steps.
Now, every path $ (n,s)$ can be transformed into a path from $ (0,0)$ to $ (n + 1,n + 1)$ by inserting a step between any two consecutive moves, or in the beginning or in the end of the $ (n,s)$ path -- note the new path will still completely stay in the required half-plane, this is really nice. Then, if this step is inserted in between an $ E$ and a $ N$ steps (in this order) then, the number of steps in the new path will be $ s$ -- so we get a path $ (n + 1,s)$, and otherwise get $ s + 1$ steps so get a path $ (n + 1,s + 1)$.
Now, for a $ (n,s)$ path there are $ s$ ways in which a step can be inserted in between an $ E$ and a $ N$ steps (in this order), so $ s$ transformations of a $ (n,s)$ path give a $ (n + 1,s) $ path. And there are $ 2n + 1 - s$ ways in which the step in not inserted in between an $ E$ and a $ N$ step in this order -- as in total there are $ 2n + 1$ spaces for the "new" step to go in the sequence of moves in path $ (n,s)$ -- so $ 2n + 1 - s$ transformations of a $ (n,s)$ path give a $ (n + 1,s + 1) $ path.
Therefore, there are $ s + 1$ ways to transform a $ (n,s + 1)$ path into a $ (n + 1,s + 1)$ path and $ 2n + 1 - s$ ways to transform a $ (n,s)$ path into a $ (n + 1,s + 1)$ path. But in each $ (n + 1,s + 1)$ path, there are $ s + 1$ steps so $ s + 1$ ways to reduce it to a $ (n,s + 1)$ or a $ (n,s)$ path by removing one step. Therefore:
$ (s + 1)f(n + 1,s + 1) = (2n + 1 - s)f(n,s) + (s + 1)f(n,s + 1)$
                          $  = (2n + 1 - s)\frac{1}{s}\binom{n - 1}{s - 1}\binom{n}{s - 1} + (s + 1)\frac{1}{s + 1}\binom{n - 1}{s}\binom{n}{s}$
                          $  = \binom{n}{s}\left(\frac{2n + 1 - s}{n - s + 1}\binom{n - 1}{s - 1} + \binom{n - 1}{s}\right)$
                          $  = \binom{n}{s}\left(\frac{(n - 1)!}{(s - 1)!(n - s)!}\right)\left(\frac{2n + 1 - s}{n - s + 1} + \frac{n - s}{s}\right)$
                          $  = \binom{n}{s}\left(\frac{(n - 1)!}{(s - 1)!(n - s)!}\right)\left(\frac{n^{2} + n}{(n - s + 1)s}\right)$
                          $  = \binom{n}{s}\binom{n + 1}{s}$
Therefore, $ f(n + 1,s + 1) = \frac{1}{s + 1}\binom{n}{s}\binom{n + 1}{s}$ so result is true for $ n + 1$ and the result follows by mathematical induction.

Inserting steps works nicely, but just for another method...

Let $f(p,q,s)$ denote the number of pairs of sequences of nonnegative integers $(\{a_i\}_{i=1}^{s},\{b_i\}_{i=1}^{s})$ such that
\[a_1+\cdots+a_i\ge b_1+\cdots + b_i\]for all $1\le i\le s$ and $p=a_1+\cdots+a_s$ while $q=b_1+\cdots+b_s$. For $s=1$, $f(p,q,s)=[p\ge q]$, and for $s\ge 2$,
\[f(p,q,s)=[p\ge q]\sum_{b_s=0}^{q}\sum_{a_s=0}^{p}f(p-a_s,q-b_s,s-1)=[p\ge q]\sum_{j=0}^{p}\sum_{k=0}^{q}f(j,k,s-1).\]By induction on $s$, we show that
\[\implies f(p,q,s)=[p\ge q]\left(\binom{p+s-1}{s-1}\binom{q+s-1}{s-1}-\binom{p+s-1}{s-2}\binom{q+s-1}{s}\right).\]Indeed, for $s=1$ and $s=2$ this is easy to verify, and for $s=3$ (assuming $p\ge q$, of course), the inductive hypothesis combined with repeated Vandermonde yields
\begin{align*}
f(p,q,s)
&= \sum_{j=0}^{p}\sum_{k=0}^{q}f(j,k,s-1) \\
&= \sum_{k=0}^{q}\sum_{j=k}^{p}\binom{j+s-2}{s-2}\binom{k+s-2}{s-2}-\binom{j+s-2}{s-3}\binom{k+s-2}{s-1} \\
&= \sum_{k=0}^{q}\binom{k+s-2}{s-2}\left(\binom{p+s-1}{s-1}-\binom{k+s-2}{s-1}\right)-\binom{k+s-2}{s-1}\left(\binom{p+s-1}{s-2}-\binom{k+s-2}{s-2}\right) \\
&= \sum_{k=0}^{q}\binom{k+s-2}{s-2}\binom{p+s-1}{s-1}-\binom{k+s-2}{s-1}\binom{p+s-1}{s-2} \\
&= \binom{q+s-1}{s-1}\binom{p+s-1}{s-1}-\binom{q+s-1}{s}\binom{p+s-1}{s-2},
\end{align*}as desired.

Returning to the original problem, it's not hard to see that there are $s-1$ corners of the form $NE$ if there are $s$ steps; these "upper" corners, including $(0,0)$ and $(n,n)$, form a sequence $(0,0),(x_1,y_1),(x_1+x_2,y_1+y_2),\ldots,(x_1+\cdots+x_s,y_1+\cdots+y_s)$ where $x_i,y_i\ge 1$ are integers for all $i$, $x_1+\cdots+x_i\ge y_1+\cdots+y_i$ for all $i$, and $x_1+\cdots+x_s=n=y_1+\cdots+y_s$. Hence our desired answer is
\begin{align*}
f(n-s,n-s,s)
&=\binom{n-1}{s-1}\binom{n-1}{s-1}-\binom{n-1}{s}\binom{n-1}{s-2} \\
&=\binom{n-1}{s-1}^2\left(1-\frac{n-s}{s}\frac{s-1}{n-s+1}\right) \\
&=\frac{(n-1)!^2}{(s-1)!^2(n-s)!^2}\frac{n}{s(n-s+1)} \\
&= \frac{1}{s}\binom{n-1}{s-1}\binom{n}{s-1},
\end{align*}as desired.

[hide="Motivation"]For $s=2$, it's $(q+1)(2p+2-q)/2$, and for $s=3$, it's $(p+2)(q+1)(q+2)(3p+3-2q)/12$. This obviously interpolates to
\[f(p,q,s)=\frac{(p+2)\cdots(p+s-1)(q+1)\cdots(q+s-1)(s(p+1)-(s-1)q)}{(s-1)!s!}.\][/hide]

[[b]Moderator edit:[/b] The above is a nice solution, but I think that what is referred to as "Vandermonde" is actually better known as the "hockey-stick identity" (the identity claiming that $\sum_{i=a}^b \binom{i+c}{d} = \binom{b+c+1}{d+1}-\binom{a+c}{d+1}$ for all integers $a$, $b$, $c$, $d$ satisfying $a\geq b+1$). Also, the induction base $s=2$ is unneeded, at least as long as binomial coefficients are extended to negative entries in an appropriate way (i. e., in a way respecting the recurrence equation). -- Darij]

Can somebody post a solution using generating functions :D ?

Here's a start.  What the problem calls "steps" I'll call "peaks".  Let the number of $n$-paths with $s$ peaks be $f(n, s)$, and let $F(x, t) = \sum_{n, s} f(n, s) x^n t^s$.  For $n \geq 0$, every path from $(0, 0)$ to $(n + 1, n + 1)$ with $s$ peaks can be decomposed as follows: let $k$ be the smallest nonneginteger such that $(k + 1, k + 1)$ belongs to the path.  Then either $k = 0$ and the portion of the path from $(1, 1)$ to $(n + 1, n + 1)$ is itself a path with $s - 1$ peaks, or $k > 0$ and there is some $j$ such that the portion of the path from $(1, 0)$ to $(k + 1, k)$ is a path with $j$ peaks while the portion of the path from $(k + 1, k + 1)$ to $(n + 1, n + 1)$ has $s - j$ peaks.  It follows immediately that \[
f(n + 1, s) = f(n, s - 1) + \sum_{k \geq 1} \sum_{j} f(k, j) f(n - k, s - j).
\]  Multiplying by $x^{n + 1}t^s$ and summing over all nonnegative $n$ and $s$ gives \[
F(x, t) - 1 = xt F(x, t) + x F(x, t)(F(x, t) - 1).\]  Solving this quadratic equation gives \[
F(x, t) = \frac{1 + x - xt - \sqrt{(1 + x - tx)^2 - 4x}}{2x}.\]

I'm surprised that this method (a "bijection") has not been posted yet?

If we consider any path from (0,0) to (n, n+1) such that they have s steps (and start with E, end with N), then we can cyclicly rotate the steps in this path to obtain s distinct paths, and then we can show that exactly one of them is a valid path for the original problem with an additional N step appended to the end. Since there are $\binom{n-1}{s-1} \binom{n}{s-1}$ paths from (0,0) to (n,n+1) with s steps (we can use balls and urns), we conclude that the answer is $\frac{1}{s}\binom{n-1}{s-1} \binom{n}{s-1}$.

[quote=rem] But in each $ (n + 1,s + 1)$ path, there are $ s + 1$ steps so $ s + 1$ ways to reduce it to a $ (n,s + 1)$ or a $ (n,s)$ path by removing one step. [/quote]

Why is this true? Is it not possible to have the following sequence: $EENENN$? There are two steps but if you remove the first $EN$, you'll get the exact sequence as if you remove the second $EN$?

[quote=MathPanda1]Why is this true? Is it not possible to have the following sequence: $EENENN$? There are two steps but if you remove the first $EN$, you'll get the exact sequence as if you remove the second $EN$?[/quote]

rem is talking about "ways to remove"; he isn't a building a bijection, so it is perfectly possible that two "ways to remove" yield the same result.

Let me use this occasion to comment on where the problem comes from. The number $\frac{1}{s} \binom{n-1}{s-1} \binom{n}{s-1}$ is the so-called [url=https://en.wikipedia.org/wiki/Narayana_number][i]Narayana number[/i][/url] $N_{n, s-1}$. The statement of the problem is the well-known interpretation of this Narayana number as the number of Dyck paths of semilength $n$ with $k$ peaks. This is proven in [url=https://www.springer.com/cda/content/document/cda_downloaddocument/9781493930906-c1.pdf]§2.4.2 of Kyle Petersen's [i]Eulerian Numbers[/i] text[/url].

Say hello to Alice, a [i]step[/i]:
[asy]
unitsize(24);
draw((0.0,0.0)--(1,0)--(1,1),blue);
[/asy]
Now say hello to Bob, [b]not[/b] a [i]step[/i]:
[asy]
unitsize(24);
draw((0.0,0.0)--(1,0)--(1,1)--(2, 1)--(2,2),green);
[/asy]This is just to make sure it's clear that we're on the lookout for Alices, not Bobs. Now we've got that sorted, we can start on the problem.
------------------------
Consider paths from $(0, 0)$ to $(m, n)$ using only $E$'s and $N$'s that start with $E$ and end with $N$ (which we call $\textit{derkish}$) - this is to make sure that the path doesnt cross $x \leq y$ in the first move or has crossed $x \leq y$ by the last move. I claim that there are\[\binom{m-1}{a-1}\binom{n-1}{a-1}\]derkish paths with $a$ Alices. Call the bottom right corner of an Alice its [i]anchor[/i]. Since derkish paths start with $E$ and end with $N$, their first anchor must be on the $x$-axis and their last anchor must be on $x = m$. I claim that we can biject derkish paths with $a$ anchors to selecting two sequences of integers $0 < x_1 < x_2 < \ldots < x_a = m$ and $0 = y_1 < y_2 \ldots < y_a < n$. Indeed, any derkish paths with $a$ Alices can extrapolate such a sequence; simply consider the $x$-coordinates and $y$-coordinates of the anchors arranged in increasing order. Furthermore, it is also clear that each pair of such sequences generates at least one derkish path with $a$ Alices; simply let $(x_i, y_i)$ be the $i$th anchor. Indeed, each anchor is to the top-right of the previous one, so such a path can always be generated. So indeed, this bijection is formed, and it is easy to count the number of pairs of such sequences, which does indeed match what we claimed earlier.

Now, consider derkish paths with $s$ Alices from $(0, 0)$ to $(n, n+1)$; there are $\tbinom{n-1}{s-1}\tbinom{n}{s-1}$ of those. Among its $2n+1$ cyclic shifts, note that the number of them that produce derkish paths is the same as the number of adjacent pairs of $NE$; this must be the same as the number of Alices, which is $a$. Furthermore, no two cyclic shifts may be the same since $n$ and $n+1$ are relatively prime. Furthermore, exactly one of them does not cross the line $(0, 0) \to (n, n+1)$, which is the same condition as not crossing $x \geq y$.

Hence, among every derkish path with $s$ Alices, $\tfrac{1}{s}$ of them are satisfying the problem, and this yields our final desired answer. $\blacksquare$

Probably shouldn't have tried recursion for the first 3 hours, oh well.

Consider any path from $(0, 0)$ to $(n, n+1)$ that has $s$ steps (not necessarily in the half plane) that starts with a E and ends with an N. The number of such paths is $\binom{n-1}{s-1}\binom{n}{s-1}$, since we can choose points $p_{1}, p_{2}, \ldots p_{s-1}$ such that $p_{i}$ is to the right and above $p_{i-1}$, and there is exactly one step from $p_{i-1}$ to $p_{i}$ (Let $p_{0} = (0, 0), p_{s} = (n, n+1)$). Since the x and y coordinates of these points are distinct, in increasing order, and range from $(0, n)$ for x coordinates and $(0, n+1)$ for y coordinates, there are $\binom{n-1}{s-1}\binom{n}{s-1}$ ways to choose such points.

Now consider taking this path, and putting the starting point at $(n, n+1)$. Now we have a path that goes from $(0, 0)$ to $(2n, 2n+2)$. Furthermore, if point $p_{i} = (x_{i}, y_{i}),$ let point $p_{i+n} = (x_{i} + n, y_{i} + n + 1)$ (which is also on this path). Now, for each $0\leq i < n$, consider the sub-section of this path from $p_{i}$ to $p_{i+n}$. I claim exactly one $i$ exists such that this subpath is below or on the line between $(x_{i}, y_{i})$ and $(x_{i}+n, y_{i} + n)$ (excluding the last move of this path, which is north). This is because, if we consider the point with the maximal $y_{i} - x_{i}$, and if there are multiple such points take the leftmost one, then this point must satisfy that condition, while no other point can (because of maximality and leftmost, leftmost ensures that the line of any other point will run into $(x_{i} + n, y_{i} + n+1)$). Let this path be the "mapped path". For each path that is in the half plane $y\leq x$, we can do the same thing to show that $s$ of the paths in the entire plane has it's mapped path as the path in the half plane (up to translation), by just appending a "N" at the end of it and copying it over. Thus, the number of paths in the half plane with $s$ steps is $\frac{1}{s}$ of the number of paths in the full plane, or $\frac{1}{s}\binom{n-1}{s-1}\binom{n}{s-1}$

We will prove this by induction on $n$, with $n=1$ as the base case. Let $f(n, s)$ denote the number of paths from $(0, 0)$ to $(n, n)$ with $s$ steps.

The number of ways to choose a path with $s$ steps and color one of the steps blue is $sf(n, s)$.

Consider removing the blue step. Then, you get a path from $(0, 0)$ to $(n-1, n-1)$.

Consider the case where the point where the blue step was removed has $E$ before it and $N$ after it. This case is equivalent to starting with a path from $(0, 0)$ to $(n-1, n-1)$ with $s$ steps, choosing a step, and turning it from $EN$ to $EENN$. There are $sf(n-1, s)$ ways to do this.

Consider the other case, where the point isn't in the middle of a step. This is equivalent to starting with a path from $(0, 0)$ to $(n-1, n-1)$ with $s-1$ steps, choosing a point that isn't in the middle of a step, and inserting a step into it. There are $2n-1$ total points, so there are $2n-s$ that aren't steps. So, there are $(2n-s)f(n-1, s-1)$ ways to do this.

So, adding, we get $sf(n, s)=sf(n-1, s)+(2n-s)f(n-1, s-1)$. By the inductive hypothesis,
$$sf(n, s)={{n-2}\choose{s-1}}{{n-1}\choose{s-1}}+\frac{2n-s}{s-1}{{n-2}\choose{s-2}}{{n-1}\choose{s-2}}={{n-2}\choose{s-1}}{{n-1}\choose{s-1}}.$$

Let $f(n,s)$ be the number of paths from going $n$ up and $n$ right containing exactly $s$ steps. Clearly, we have $f(n,1)=1$ and $f(n,n)=1.$
\\$~$\\
Consider any path from $(0,0)$ to $(n,n)$ with $s$ steps. Now, you can at any point in the path, insert a step without making any part of the path go over the line $x=y$. This is because any part of the path that is past the insertion will be shifting parallel to the line $x=y$.
\\$~$\\
With a path with $s+1$ steps, you can add a step where there already is a step in $s+1$ ways to make a path that is just two longer but preserve the number of steps. With a path with $s$ steps, you can add a step where there is not already a step in $2n+1-s$ ways to make a path that is just two longer and makes $s+1$ steps. Now, for a path from $(0,0)$ to $(n+1,s+1)$ with $s+1$, we can remove a step in $s+1$ ways to go back to a path from $(0,0)$ to $(n,n)$, with either $s$ or $s+1$ paths.
\\$~$\\
Since insertion and removal is two related transformations, and the ratio between insertions from $s$ steps and from $s+1$ is $2n+1-s:s+1$, the ratio for the removal to $s$ steps and to $s+1$ will be $2n+1-s:s+1$. Therefore, $f(n+1,s+1)=(2n+1-s)/(s+1)f(n,s)+f(n,s+1)$ at which point induction can be used to finish.

Let $f_s(m,n)$ be the answer but you start at $(n-m,0)$ instead of $(0,0)$. Our constraints are now $1\le s\le m\le n$.
We can really just visualize this problem as having $s$ "horizontally flipped L shapes" with their endpoints connected. This lends itself to this following formula, where $1<s\le M\le N\colon$
\[f_s(M,N)=\sum_{m=s-1}^{M-1}\sum_{n=m}^{N-1}f_{s-1}(m,n).\]
Now we will prove our main claim.

[b]Main Claim.[/b] For all positive integers $1\le s\le M\le N$,
\[f_s(M,N)=\binom{N}{s-1}\binom{M-1}{s-1}-\binom{N-1}{s-2}\binom{M}{s}.\]
[b]Proof.[/b] We proceed by induction on $s$. Base case $s=1$ is trivial, so assume $s-1$ works. Now
\begin{align*}
&f_s(M,N) \\
&=\sum_{m=s-1}^{M-1}\sum_{n=m}^{N-1}f_{s-1}(m,n) \\
&=\sum_{m=s-1}^{M-1}\sum_{n=m}^{N-1}\left(\rule{0cm}{1cm}\binom{n}{s-2}\binom{m-1}{s-2}-\binom{n-1}{s-3}\binom{m}{s-1}\right) \\
&=\sum_{m=s-1}^{M-1}\left(\rule{0cm}{1.2cm}\left(\rule{0cm}{1cm}\binom{N}{s-1}-\binom{m}{s-1}\right)\binom{m-1}{s-2}-\left(\rule{0cm}{1cm}\binom{N-1}{s-2}-\binom{m-1}{s-2}\right)\binom{m}{s-1}\right) \\
&=\sum_{m=s-1}^{M-1}\left(\rule{0cm}{1.2cm}\left(\rule{0cm}{1cm}\binom{N}{s-1}-\binom{m}{s-1}\right)\binom{m-1}{s-2}-\left(\rule{0cm}{1cm}\binom{N-1}{s-2}-\binom{m-1}{s-2}\right)\binom{m}{s-1}\right) \\
&=\binom{N}{s-1}\binom{M-1}{s-1}-\binom{N-1}{s-2}\binom{M}{s}+\sum_{m=s-1}^{M-1}\left(\rule{0cm}{1cm}\binom{m-1}{s-2}\binom{m}{s-1}-\binom{m}{s-1}\binom{m-1}{s-2}\right) \\
&=\binom{N}{s-1}\binom{M-1}{s-1}-\binom{N-1}{s-2}\binom{M}{s}\;\blacksquare
\end{align*}

Now note that for any $1\le s\le n$,
\begin{align*}
&f_s(n,n) \\
&=\binom{n}{s-1}\binom{n-1}{s-1}-\binom{n-1}{s-2}\binom{n}{s} \\
&=\frac{n!(n-1)!}{(s-1)!^2(n-s+1)!(n-s)!}-\frac{n!(n-1)!}{s!(s-2)!(n-s+1)!(n-s)!} \\
&=\frac{n!(n-1)!}{(s-1)!(s-2)!(n-s+1)!(n-s)!}\cdot\left(\frac{1}{s-1}-\frac{1}{s}\right) \\
&=\frac{n!(n-1)!}{(s-1)!(s-2)!(n-s+1)!(n-s)!(s)(s-1)} \\
&=\frac{1}{s}\binom{n-1}{s-1}\binom{n}{s-1}\;\blacksquare
\end{align*}

The gist of the problem is to solve it with endpoint $(n, n+1)$ without the restriction of the path within the half plane by using $s$ obvious cyclic shifts of the paths. Thus we need to show that the number of paths is \[ \binom{n-1}{s-1} \binom{n}{s-1}. \] Now the path can be split up into a sequence of ``fat steps" consisting of multiple right moves followed by multiple up moves, so we finish by Stars and Bars.

Inspired by the "cyclic shift" method of proving the Catalan number problem:

We instead consider paths from $(0, 0)$ to $(n, n+1)$ of $s$ steps below the slightly raised line from $(0, 0)$ to $(n, n+1)$. Obviously, counting the number of possible paths in this case is equivalent to the original question (an $N$ is forced to go last following any valid path). Here is an example for $n = 5$ and $s = 2$:
\[ EENNEEENNNN \]
Consider the $s$ cyclic shifts of this path, where we shift by consecutive $E$'s and $N$'s that precede and come after a step (call these big steps); in this case, the other shift is
\[ EEENNNNEENN \]
[color=#00f][b]Claim: [/b][/color]Exactly one of these shifts lies below the slightly raised line.

Indeed, we just note that there must be a big step consisting of more $N$'s than $E$'s. In particular, this big step must come last to satisfy the problem statement. $\square$

Thus, we just need to count the total number of paths from $(0, 0)$ to $(n, n+1)$ that have $s$ big steps, but do not need to stay below $y = x$.
To do this, we use stars and bars twice. First, we need to place the $E$'s to form $s$ groups of conseuctive $E$'s. First place $s$ $E$'s so these groups are nonzero, and then we have to place $n-s$ objects into $s$ buckets; this gives $\binom{n-1}{s-1}$ ways.
Similarly for the $N$'s, we want to form $s$ groups of consecutive $N$'s, so get rid of the nonzero condition by placing $s$ $N$'s. Then we have $n+1-s$ objects to place into $s$ buckets, giving $\binom{n}{s-1}$ ways.

This proves that the answer is $\frac{1}{s} \binom{n-1}{s-1}\binom{n}{s}$, as desired. $\blacksquare$


A triangle has sides of 24,31,51 units. FInd the smalleset in the triangle to the nearest

27.8
25.2
23.4
29.2
none of the above[/hide]

Do you mean angle?
[hide="Use"]the Law of Cosines[/hide]


Quite a big bunch frm Aops will be attending OCSC's this year (including me!!:yay:)

BEST OF LUCK...India beckons you!!!!!
i think maths and astro must've already started...

Its time to see who gets the VISA and who wins the PIZZA  :D

[hide]i m ordering in advance,keep a special 3 layered pizza with extra toppings reserved for me :P [/hide]

Here's a list...srry if i missed sm1

[b]MATHS:[/b]
ashwath
gauavpatil
Ram(A.Barath)
keshav
Akashnil

[b]BIO:[/b]
me

[b]PHY:[/b]
einstein
deepit
...

[b]CHEM:[/b]
einstein
tuhin
swahuum
....(i surely misssed sm)

[b]ASTRO:[/b]
sm1 else shud compile :P

[b]INFORMATICS[/b]
keshav_57
chetan bademi
phinfinity
crackjack987
arjunarul
mamama
saikrishna
shrivatsan

hey guys/gals (ritu :P)
have nyc tym out there in the camp
hope the best one makes it thru!!

~cheers~

*sniff* Good luck to you guys. Have fun! *sniff*

same here nuclear ,

 :(  i got selected for inmo , inao , injso....but for none of d camps........ *sniff*

btw.......i plan 2 become like vinit(einstien) next year.......so plz dont keep d KMOG flag running high.....otherwise ill need 2 take life insurance :rotfl:

it seems there r many budding einsteins on Aops :roll:

And par  :mad: u  post after such a long time and that also a Level 1 spam :D

my pj's r not as good as u guys ka re....... :(
big deal re.......i ws in 10th and was giving junior level (9ths and 8ths) because of my birthdate....so obviously was bound 2 get selected for the 2nd level........ :rotfl:
sad ..... no camps for me  :wallbash:
well everyone selected , njoy urself there!....and those not selected, maybe we can form a group calld kill camp guys... :rotfl: [hide] k dat ws a very poor one..... wat can i do..young generation ka jokes r lke dat oly![/hide]

i'll be the first one to join it.....
i m willing to give IBOTC a miss :rotfl:

Rituraj, you said Pardesi was spamming and you are the one spamming now. :lol:
All the best for your IBOTC.
And please someone update here regulalrly regarding the maths camp.I am missing it like anything but next 3 years are there.Rituraj, you know a lot of delhi guys.l So keep updating with news about IMOTC 2009 here. I am sure Ashwath is making it to the team.
you missed out ram{a barath} in chemistry camp. And also Sanjith{thealchemist}, gunaa{avg} in maths camp.
All the best to everyone attenidng the camps.

There's Gaurav, and there's the alchemist :(

[quote="rituraj007"]thats only possible if i m made Indian team's official cook,observer or sth..... :rotfl:[/quote]

how about indian cooking olympiad???   :rotfl:

[quote="franklampard8"]how about indian cooking olympiad???   :rotfl:[/quote]

ICO??good name :rotfl:

a substantial no. of Aopsians r thru to IO's(gaurav,akashnil,einstein...)

I hope i can join them ..i m off tomorrow :maybe:

PS:AIIMS paper was a howler..And ppl are talking abt paper leak.... :mad:

[quote="_MM_"]With the end of the informatics camp, Here is the final list of those representing India at the International olympiad in Informatics

Keshav Dhandania ( keshav_57 in AoPS)       Kolkata
B Srivatsan (srivatsan on AoPS)                  Chennai
V Prashant                                              Chennai
Adhiraj Somani                                         Kolkata

This year Chennai and Kolkata [hide="and"]AoPSians... :D .. [/hide]dominate...
All the Best...

Lets hope that we can better last year's three bronze medals[/quote]
WOOHOO!!! 2 aopsians! CONGRATS!

Congrats to all!! :)

The ranks were
1.Keshav  (XI)           - 661.8/900  :roll:  :wow:
2.V.Prashant (XII)      -314.8/900
3.Adhiraj Somani (XII) -285.7/900
4.B.Srivatsan (XII)     -258.2/900

Keshav is surely not a human.He just blasted through the tests.He will surely get a gold.
Anish Shankar(XI)(5th rank) (phinfinity in AoPS) missed it by a whisker.He got 256.4.Just 1.8 short of qualifing. :o
Arckhit Karandikar(XI)(6th) got 238.7.He had lost 100 marks due to a line,which he had written outside a 'for' loop by mistake, instead of inside it.If he had got it ,he would have been 2nd.
I got 176.6. (XI) 7 th rank.

Chetan Bademi(AoPS) got 4th in the qualifying rounds, but missed it in the finals.

Congrats to all those selected,especially AoPSians.It feels proud to be with you on the same forum :thumbup: Hope you win gold and make the country proud :coolspeak:

[quote="keshav_57"]Thanks people..

@Arjun
Cmon man, you can't take away my right to be called a normal human being![/quote]
That's right. Coz otherwise, you would'nt be able to participate in the IOI :lol:

Congratultions to all the finalists..

Special congrats to keshav (super human) for being adjudged codechef coder of the month and for promising us a Gold medal at the IOI... :)

Hard luck to Anish( phinfinity) and arjunarul...But you will be competing next year as well when the stage will be all yours...(and keshav's) :D

YOU GUYS ARE SO INSPIRING!!!!!!!!!!!!!!!!!
 :clap:  :first:  :thumbup:

AND GREAT TOO!!! :clap:  :winner_first:  :thumbup:

Hey good job keshav.. and all the best for the intl. Go in with a calm mind and dont get pressurized by what others say. :)

@Chronoz
Yup, I know there are a lot of expectations. But i also know, that the only ones I need to fulfill, are the ones which I have from myself.
No pressure at all..
:)

@_MM_
and no promises.. :P

Lol, Keshav got his perfect b'day gift this year!  :rotfl:
Btw, guys selected for IOs are KVPY scholars too by default right? So will I get to meet all you geniuses? :P Or is the camp too stupid for IO intellects?

@Nucleur
Do you know the timings of the camp and when would it end on 13th?
Also can any senior tell me what is basically done at the camp?
Are the any tests or projects for which we need to go prepared??

No tests..nothing to get prepared...

just timepass (full)

the most imp thing is that u get acquanted with the would b toppers of ur batch well in advance...


search
number theory unsolved
number theory

Prove the identity:
       (n+1)lcm(0Cn;1Cn;...;nCn)=lcm(1;2;..;n;n+1)
for any positive integer n.

What we need to prove is $ (n\plus{}1)[\binom{n}{0},...\binom{n}{n}]\equal{}[1,2,...,n\plus{}1]$
We're sufficient to show $ LHS | RHS$ and $ RHS | LHS$
First one follows quickly from the identity $ k \binom{n\plus{}1}{k}\equal{}(n\plus{}1) \binom {n}{k\minus{}1}$
The second get more complicated.We consider the exponent of prime $ p$ .
Well we divided it to two cases
$ 1$.$ p$ does't divide $ n\plus{}1$
assuming $ p^t \le n <p^{t\plus{}1}$ Then the exponent of $ p$ in $ \binom {n}{k}$ $ \equal{}\sum _{i\equal{}1}^{t}([\frac{n}{p^i}]\minus{}[\frac{k}{p^i}]\minus{}[\frac{n\minus{}k}{p^i}])$
is obviously $ \le t$ for each term is at most $ 1$
$ 2$ $ p^s\parallel{}n\plus{}1$ while $ s\ge 1$
assuming $ p^t \le n <p^{t\plus{}1}$
 the exponent of $ p$ in $ \binom {n}{k}$ $ \equal{}\sum _{i\equal{}1}^{t}([\frac{n}{p^i}]\minus{}[\frac{k}{p^i}]\minus{}[\frac{n\minus{}k}{p^i}])$ is not bigger than $ t\minus{}s$ for the first $ s$ term are $ 0$ which complete our proof :)

A nice solution using Kummer's theorem has been posted http://www.mathlinks.ro/viewtopic.php?t=290280


How do I get spaces between lines when i use
[code] \[....\][/code]. When I put spaces in between lines in the code, they show up as errors. When i use [code]\\[/code], nothing happens.

\ [...\ ] is for single line displayed formulae so \\ has no effect. For multiline, you can use
\begin{eqnarray*}
1+1=2 \\
2+2=4
\end{eqnarray*}
The * prevents equation numbering, if that's what you want.

Of course the simplest way is to use
\ [1+1=2\ ]
\ [2+2=4\ ]
but you may not like the spacing between the equations.

Ah, I see. My Texniccenter for some reason can't process the eqnarray- what package do I need for it?

It shouldn't need any special package. What error messages do you get with this complete document?
[code]\documentclass[12pt]{article}
\begin{document}
\begin{eqnarray*}
1+1=2 \\
2+2=4
\end{eqnarray*}
\end{document}[/code]If that works maybe there's a confilct with something else in your document.


geometry inequalities parallelogram conics hyperbola function

The pair of numbers $ (a,b)$ such that $ |a\plus{}bt\plus{}t^{2}|\leq 1$ for $ 0\le t\le 1$, fill a certain region in the $ (a,b)$ plane. What is the area of this region?

[hide="Setup"]We want the area of the set $ (a,b):\;\minus{}1\leq t^{2}\plus{}bt\plus{}a\leq 1\;\forall\; 0\leq t\leq 1$
Let's make three mutually exclusive cases:
$ \minus{}b/a\geq 1$ (extremum outside of t-range)
$ 0 <\minus{}b/a < 1$ (extremum inside of t-range)
$ \minus{}b/a\leq 0$ (extremum outside of t-range)

In cases 1 and 3, the expression in t is monotone, so it suffices to show that the inequality is satisfied for t=0 and t=1:

$ \minus{}1\leq a\leq 1$ [b]and  [/b]$ \minus{}1\leq 1\plus{}b\plus{}a\leq 1\iff\minus{}2\leq a\plus{}b\leq 0$

In case 2, we must show it is true at t=0, t=1, and t=-b/a (extremum)

$ \minus{}1\leq a\leq 1$ [b]and  [/b]$ \minus{}1\leq 1\plus{}b\plus{}a\leq 1\iff\minus{}2\leq a\plus{}b\leq 0$ [b]and [/b] $ \minus{}1\leq b^{2}/a^{2}\minus{}b^{2}/a\plus{}a\leq 1$[/hide]
[hide="Case 1"]
We want the region defined by:
$ \minus{}b/a\geq 1$ [b]and[/b] $ \minus{}1\leq a\leq 1$ [b]and  [/b]$ \minus{}2\leq a\plus{}b\leq 0$
The first restriction refers to the area between $ a \equal{}\minus{}b$ and $ a \equal{} 0$.
The second restriction refers to the vertical strip between $ a \equal{}\minus{}1$ and $ a \equal{} 1$.
The third restriction refers to the diagonal strip between $ a\plus{}b \equal{}\minus{}2$ and $ a\plus{}b \equal{} 0$.

Taking the intersection of these regions results in the parallelogram with vertexes (0,0), (1,-1), (0,-2), (1,-3)
The area of this region is $ (0\minus{}(\minus{}2))(1\minus{}0) \equal{} 2$
[/hide]
[hide="Case 2"]
This one's a beast to do rigorously.
We now have four criteria.
The first restriction refers to the region between $ b \equal{} 0$ and $ b \equal{}\minus{}a$.
The second restriction refers to the vertical strip between $ a \equal{}\minus{}1$ and $ a \equal{} 1$.
The third restriction refers to the diagonal strip between $ a\plus{}b \equal{}\minus{}2$ and $ a\plus{}b \equal{} 0$.

The fourth restriction $ \minus{}1\leq b^{2}/a^{2}\minus{}b^{2}/a\plus{}a\leq 1$ is beastly, but for our purposes, will represent the restriction |b|<a.

[hide="Brief Explanation"]The region $ b^{2}/a^{2}\minus{}b^{2}/a\plus{}a\leq 1$ is formed by the bounds of $ b^{2}/a^{2}\minus{}b^{2}/a\plus{}a \equal{} 1\iff (a\plus{}b)(a\minus{}b)(a\minus{}1) \equal{} 0$, which is a set of three lines. This makes a seemingly difficult formula work out nicely.
This set of points is the intersection of the following two regions:
- for a < 1, the set |b|<a
- for a> 1, the set |b| > a
Since we know $ |a|\leq 1$ from restriction 2, for our purposes, we require that $ |b| < a$.

Unfortunately, the $ \minus{}1\leq ~$ part of the original restriction blows out a chunk of the leftmost "triangle" subregion (|b|<a, a<0). We need to see if it affects us. This part is symmetric across the x axis, so the extremal part of the blown out chunk (which resembles a hyperbola) occurs when b=0, or a=-1. Hence the rightmost part of the blown out chunk does not pass the leftmost bound of the |a|<1 restriction, and we can ignore it.

Hence, for our purposes, the fourth restriction will require that |b|<a.[/hide]

Thus, the region that satisfies the above is the triangle with vertexes (0,0), (-1,0), (-1,1), which has area $ \frac{1}{2}(0\minus{}(\minus{}1))(1\minus{}0) \equal{}\frac{1}{2}$
[/hide]
[hide="Case 3"]
We want the region defined by:
$ \minus{}b/a\leq 0$ [b]and[/b] $ \minus{}1\leq a\leq 1$ [b]and  [/b]$ \minus{}2\leq a\plus{}b\leq 0$

The first restriction refers to quadrants I and III.
The second restriction refers to the vertical strip between $ a \equal{}\minus{}1$ and $ a \equal{} 1$.
The third restriction refers to the diagonal strip between $ a\plus{}b \equal{}\minus{}2$ and $ a\plus{}b \equal{} 0$.

Taking the intersection of these regions results in the triangle with vertexes (0,0), (0,-2), (-2,0)
The area of this region is $ \frac{1}{2}(0\minus{}(\minus{}2))(0\minus{}(\minus{}2)) \equal{} 2$
[/hide]
[hide="Answer"]
Because the three cases above are mutually exclusive, the area of the desired region is $ 2\plus{}2\plus{}\frac{1}{2}\equal{}\frac{9}{2}$
[/hide]

[color=darkblue]In the my opinion, the area is equally with $ 4$ !
I found a parallelogram $ ABCD$ (with the its interior) where the its vertices are $ A(\minus{}1,\minus{}1)$, $ B(\minus{}1,1)$, $ C(1,\minus{}1)$ and $ D(1,\minus{}3)$.
I hope that the my proof has no mistake. I"ll come back soon here.[/color]

Oops! Thanks. I can't edit it anymore =\

In any case, you're right; I considered the triangle $ (\minus{}2,0),\; (\minus{}1,0)\; (\minus{}1,\minus{}1)$ in addition to that region, which satisfies a host of other criteria, but fails the simple $ |a|\leq 1$ criteria. Subtracting the area of this region (1/2) from my initial answer (9/2) yields a final answer of $ \boxed{4}$, which agrees with what you got  :)

[quote="Virgil Nicula"][color=darkred]In the my opinion, the area is equally with $ 4$ !
I found a parallelogram $ ABCD$ (with the its interior) where the its vertices are $ A(-1,-1)$, $ B(-1,1)$, $ C(1,-1)$ and $ D(1,-3)$.
I hope that the my proof has no mistake. I"ll come back soon here.[/color][/quote]

[b]Very nice problem ![/b] I came back now. Here is the my proof.

[color=darkblue][b]Proof.[/b] Denote $ A(t) =\{(a,b)\in\mathcal R^{2}\|-1-t^{2}\le a+tb\le1-t^{2}\}$, where $ t\in [0,1]$ and $ M =\bigcap_{1\le t\le 1}A(t)$.
Observe that $ A(0) =\{(a,b)\in\mathcal R^{2}\|-1\le a\le 1\}$. For $ t\in (0,1]$ denote the lines $ \{\begin{array}{cc}d_{1}\ : & a+bt+t^{2}-1 = 0\\ \ d_{2}\ : & a+tb+t^{2}+1 = 0\end{array}$, i.e.
$ \{\begin{array}{cc}d_{1}\ : & b =-\frac{1}{t}\cdot a+\frac{1-t^{2}}{t}\\ \ d_{2}\ : & b =-\frac{1}{t}\cdot a-\frac{1+t^{2}}{t}\end{array}$, where $ (0,\frac{1-t^{2}}{t})\in d_{1}$ , $ (0,-\frac{1+t^{2}}{t})\in d_{2}$ , $ d_{1}\parallel d_{2}$ and for any $ t\in (0,1]$, $ -\frac{1+t^{2}}{t}<\frac{1-t^{2}}{t}$.
For $ t\in (0,1]$ the set $ A(t)$ is the surface between these lines $ d_{1}$, $ d_{2}$ and the origin $ O(0,0)\in A(t)$.
The function $ u(t) =\frac{1-t^{2}}{t}$ is decreasing and the function $ v(t) =-\frac{1+t^{2}}{t}$ is increasing.
Since $ \bigcap_{0 < t\le 1}[-\frac{1+t^{2}}{t}\uparrow\ ,\ \frac{1-t^{2}}{t}\downarrow] = [-2,0]$, then $ M = A(0)\cap A(1)$ i.e. the set of the points $ (a,b)$ for which $ \{\begin{array}{c}-1\le a\le 1\\ \ -2\le a+b\le 0\end{array}$.
In conclusion, the set $ M$ is the parallelogram $ ABCD$ with the its interior,

where $ A(-1,-1)$, $ B(-1,1)$, $ C(1,-1)$, $ D(1,-3)$ and the area of the set $ M$ is equally with $ 4$.[/color]


integration
calculus
real analysis
real analysis unsolved

Let $(a_n)_n,(b_n)_n$ be sequences of reals such that $a_n\to\infty$. Prove that the set consisting of those real $x$ for which the sequence $(\sin(a_nx+b_n))_n$ converges has measure zero. Can it have continuum cardinality?

If $sin(a_nx+b_n) \to 0$ on a set $E$, then as it follows from Lebesque dominant theorem $\int_E sin^2(a_nx+b_n)dx \to 0$ (1). From the other side,
$\int_E sin^2(a_nx+b_n)dx=\frac{1}{2} \int_E (1-2cos(2a_nx+2b_n))dx=\frac{1}{2}m(E)-cos2b_n \int_E cos(2a_nx)dx+sin2b_n \int_E sin(2a_nx)dx$ (2).
But the integrals $\int_E cos(2a_nx)dx$ and $\int_E sin(2a_nx)dx$ tend to $0$ ( $a_n \to \infty$)as a consequence of Riemann-Lebesque theorem, from where it follows that $m(E)=0$.

You can have uncountable sets of measure zero, e.g, the cantor set.


superior algebra
superior algebra unsolved

Given ring R.Prove that if $ x \in J(R)$ then $ 1\minus{}x$ is invertible

$ J(R)$ can be defined in several ways. One would need to know which definition you are working with in order to provide you with ideas on how to proceed.  :wink:

I suspect you mean the intersection of maximal ideals.

Let $ x \in J(R)$. If $ 1\minus{}x$ is not invertible, then $ I\equal{}(1\minus{}x)\neq (1)$, so $ I \subseteq m$ for some maximal ideal.
Since $ x\in J(R)\subseteq m$ we have both $ x$ and $ 1\minus{}x$ in $ m$. Hence $ 1\in m$. Contradiction.

I read in a Herstein's book called "noncommuative rings" ,it said that:" J(R) is the intersection of all maximal regular right ideal of R".
So what's the difference between maximal right ideal and maximal regular ideal in two definitions of J(R) ?

to Ottem : $ I \equal{} (1 \minus{} x) \neq (1)$  ,i dont under stand ^^!im sorry.Did you mean that R(1-x) is right ideal of R but $ \neq$ R then $ R(1\minus{}x)$ belongs to some maximal right ideal?

Yes. $ I\equal{}(1\minus{}x)\equal{}R\cdot (1\minus{}x) \subseteq m$.


[quote="dduclam"]For all $ a,b,c$ be nonnegative real numbers such that $ a \plus{} b \plus{} c \equal{} 3$, prove that
\[ 2\left(\frac a{b \plus{} c} \plus{} \frac b{c \plus{} a} \plus{} \frac c{a \plus{} b}\right)\ge\frac {a \plus{} b}{ab \plus{} c^2} \plus{} \frac {b \plus{} c}{bc \plus{} a^2} \plus{} \frac {c \plus{} a}{ca \plus{} b^2}\]
[/quote]

try

$ a\equal{}0.001,b\equal{}0.01,c\equal{}2.989$

[quote="hedeng123"][quote="dduclam"]For all $ a,b,c$ be nonnegative real numbers such that $ a \plus{} b \plus{} c \equal{} 3$, prove that
\[ 2\left(\frac a{b \plus{} c} \plus{} \frac b{c \plus{} a} \plus{} \frac c{a \plus{} b}\right)\ge\frac {a \plus{} b}{ab \plus{} c^2} \plus{} \frac {b \plus{} c}{bc \plus{} a^2} \plus{} \frac {c \plus{} a}{ca \plus{} b^2}\]
[/quote]

try

$ a \equal{} 0.001,b \equal{} 0.01,c \equal{} 2.989$[/quote]

Are you sure, hedeng123? ;)

For $ a \equal{} 0.001,b \equal{} 0.01,c \equal{} 2.998$ then $ LSH\minus{}RSH\equal{}99.811>0$

However, I still made a mistake on typing and I edited.

[quote="dduclam"]For all $ a,b,c$ be sidelengths of a triangle such that $ a \plus{} b \plus{} c \equal{} 3$, prove that
\[ 2\left(\frac a{b \plus{} c} \plus{} \frac b{c \plus{} a} \plus{} \frac c{a \plus{} b}\right)\ge\frac {a \plus{} b}{ab \plus{} c^2} \plus{} \frac {b \plus{} c}{bc \plus{} a^2} \plus{} \frac {c \plus{} a}{ca \plus{} b^2}\]
[/quote]
The inequality follows from the Cauchy-Schwarz Inequality
$ \frac{a}{b\plus{}c}\plus{}\frac{b}{c\plus{}a}\plus{}\frac{c}{a\plus{}b} \ge \frac{(a\plus{}b\plus{}c)^2}{2(ab\plus{}bc\plus{}ca)},$
and my old result
$ \frac {a \plus{} b}{ab \plus{} c^2} \plus{} \frac {b \plus{} c}{bc \plus{} a^2} \plus{} \frac {c \plus{} a}{ca \plus{} b^2} \le \frac{3(a\plus{}b\plus{}c)}{ab\plus{}bc\plus{}ca}.$

For all $ a,b,c$ be nonnegative real numbers, we have
\[ \frac {2a}{b^2 \plus{} c^2} \plus{} \frac {2b}{c^2 \plus{} a^2} \plus{} \frac {2c}{a^2 \plus{} b^2}\ge\frac {a \plus{} b}{ab \plus{} c^2} \plus{} \frac {b \plus{} c}{bc \plus{} a^2} \plus{} \frac {c \plus{} a}{ca \plus{} b^2}\]


geometry
analytic geometry
power of a point
radical axis
geometry proposed

Let $ ABC$ be an acute-angled triangle with $ AC > AB$, and $ H$ be the orthocenter. $ AD$ is the altitude on side $ BC$ and $ AD \equal{} BC$. $ M$ is the midpoint of $ BC$. Prove that $ HD \plus{} HM \equal{} MC$.
I have a solution using analytic geometry, I want to see a pure geometry method.

Let $ M'$ be the midpoint of $ [AD].$ We have $ HD \plus{} HM \equal{} MC \equal{} \frac {AD}{2} \equal{} R\Longleftrightarrow HM' \equal{} HM.$

Consider the circles $ \mathcal{C}(A;R),$ $ \mathcal{C}(M;R),$ and $ E,F\in\mathcal{C}(A;R)\cap\mathcal{C}(M;R).$ So $ EF$ is the [u]radical axis[/u] of these two circles.

It's easy to see that $ BH\cdot HB' \equal{} AH\cdot HD$ (because $ \triangle{BHD}\sim\triangle{AHB'}$)

$ \Longrightarrow \rho_{\mathcal{C}(A;R)}(H) \equal{} \rho_{\mathcal{C}(M;R)}(H)\Longrightarrow H\in EF\Longrightarrow HM'^2 \minus{} R^2 \equal{} HM^2 \minus{} R^2\Longrightarrow$

$ \Longrightarrow HM' \equal{} HM.$ So the problem is solved.

[url=http://imageshack.us][img]http://img514.imageshack.us/img514/6999/14297486as6.png[/img][/url]

We need to show
$ HD\plus{}HM\equal{}MC$
$ HM^2\equal{}MC^2\minus{}2MC \cdot HD \plus{}HD^2$
But $ HM^2\equal{}HD^2\plus{}DM^2$ and $ DM\equal{}\frac{BC}{2}\minus{}BD$
So we need to show
$ (\frac{BC}{2}\minus{}BD)^2\equal{}MC^2\minus{}2 \cdot MC \cdot HD$
$ MC\equal{}\frac{BC}{2}$, so we need to show
$ (\frac{BC}{2}\minus{}BD)^2\equal{}(\frac{BC}{2})^2\minus{}BC \cdot HD$
$ BC \cdot HD \plus{}BD^2\equal{} BC \cdot BD$
$ BC \cdot HD\equal{}BD \cdot (BC\minus{}BD)\equal{} BD \cdot DC$
But it is well known that $ BD \cdot CD\equal{} AD \cdot HD$, since $ AD\equal{}BC$, this completes the proof.


Must each person in your family have at least one grape flavoured piece?

Hint: Hockey Stick

When you have questions about Alcumus problems, you can click "Ask problem on forum". If you're trying to save karma....don't.

She means karma doesn't matter. It doesn't.

The hockey stick identity can be found [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=88383]here[/url] or on the AOPSWiki.

lol you dont need hockey stick identity..

idk why izzy said that

1) if each person in your family get at least 1 grape

let the grapes be o.

ooooooooooooooo

then we have 14 spaces between them, and we need 4 dividers to give it to 5 ppl.

therefore, its $ \binom{14}{4}$

generally, if there are n ppl and you need to distribute r grapes to them, where every person has to get at least 1 grape, the number of ways is

$ \binom{n\minus{}1}{r\minus{}1}$

2) if it doesn't matter

generally, if there are n ppl and you need to distribute r grapes to them, where they are allowed to get 0 grape, the number of ways is

$ \binom{n\plus{}r\minus{}1}{r\minus{}1}$

so the answer is $ \binom{19}{4}$

Maybe because Hockeystick can be derived from Balls and Urns?

[hide="Proof of the Hockeystick Identity"]
Say we want to distribute $ n$ indistinguishable pieces of candy to $ k$ distinguishable kids (I know, very cliché).

There are $ \dbinom{n\plus{}k\minus{}1}{k\minus{}1}$ ways to do this (balls and urns).

Alternatively, we could note that once we've given $ 0\leq X\leq n$ candies to the first kid, there are $ n\minus{}X$ candies left to distribute to $ k\minus{}1$ kids, which there are $ \dbinom{n\plus{}k\minus{}2\minus{}X}{k\minus{}2}$ ways to do, so there are $ \sum_{X\equal{}0}^n\dbinom{n\plus{}k\minus{}2\minus{}X}{k\minus{}2}$ ways to give the $ n$ candies to the $ k$ kids.

It is not difficult to see that this sum is equal to $ \dbinom{n\plus{}k\minus{}1}{k\minus{}1}$, proving our identity

$ \dbinom{k\minus{}2}{k\minus{}2}\plus{}\dbinom{k\minus{}1}{k\minus{}2}\plus{}\cdots\plus{}\dbinom{n\plus{}k\minus{}1}{k\minus{}2}\plus{}\dbinom{n\plus{}k\minus{}2}{k\minus{}2}\equal{}\dbinom{n\plus{}k\minus{}1}{k\minus{}1}$, or equivalently,

$ \dbinom rr\plus{}\dbinom{r\plus{}1}r\plus{}\cdots\plus{}\dbinom{n\minus{}1}r\plus{}\dbinom nr\equal{}\dbinom{n\plus{}1}{r\plus{}1}$.
[/hide]


$ c^2\equal{}a^2\plus{}b^2\minus{}2ab \cos \theta$
if we know that $ a,b$, and $ c$ are integers, does that imply that $ cos \theta$ is an integer as well?
Intuitively I would say yes, but something else leads me to believe the answer is no.

$ \cos\theta \equal{} \frac {a^2 \plus{} b^2 \minus{} c^2}{2ab}$

If $ a,b,c$ are integers, this is integral or at least rational. However, bear in mind that $ \minus{} 1\leq\cos\theta\leq 1$, so if $ \cos\theta$ is an integer, it's $ \pm 1$, which means $ \theta \equal{} 0,\pi,...$, and these can't be angles of triangles. So this will never be an integer.

It will, however, be a rational, proper fraction.

Edit: Oh, yeah, $ 0$ is an integer too :D Yes, a right triangle would have $ a^2\plus{}b^2\minus{}c^2\equal{}0$. That's the only special case though.

Quick counter-example: $ a \equal{} b \equal{} c$ for any integers implies that $ \cos \theta \equal{} \frac12$.  :wink: (grn_trtle's solution is good, though).

[quote="grn_trtle"]So this will never be an integer.[/quote]
Actually, come to think of it, if $ \cos \theta\equal{}0$, then we will have a right triangle (just a minor point).


trigonometry
geometry
geometric transformation
reflection
incenter
congruent triangles
geometry proposed

Let $ ABC$ be a triangle. Prove that $ \boxed {\ IO \equal{} IH\ \Longleftrightarrow\ 60^{\circ}\in \{A,B,C\}\ }$ .

Denote $ A_1$, $ B_1$, $ C_1$ the midpoints of sides $ BC$, $ CA$, $ AB$ of triangle $ ABC$, respectively.
\[ \boxed{\sum aMA^2 = \left(\sum a\right)MI^2 + \sum aIA^2\quad\forall M}
\]
Applying the above identity, your problem is equivalent with
\[ \begin{eqnarray*}IO = IH & \iff & \left(\sum a\right)R^2 = \sum aHA^2 \\
\left(\sum a\right)R^2 & = & 4\sum aOA_1^2 \\
\iff \left(\sum a\right)R^2 & = & 4\sum aR^2\cos^2\frac {\widehat{BOC}}{2} \\
\iff \sum a & = & 4\sum a\cos^2A \\
\iff 3\sum a & = & 4\sum a\sin^2A \\
\iff 3\sum\sin A & = & 4\sum\sin^3 A \\
\iff \sum\sin 3A = 0 & \iff & \prod\sin\frac {3(B + C)}{2} = 0\end{eqnaray*}
\]
The result follows.

[quote="Virgil Nicula"][color=darkred]Let $ ABC$ be a triangle. Prove that $ IO \equal{} IH\ \Longleftrightarrow\ 60^{\circ}\in \{A,B,C\}$ .[/color] [/quote]

[color=darkblue][b][u]Proof.[/u][/b]

$ \blacktriangleright\ \boxed {\ IH \equal{} IO\ }\ \Longleftrightarrow\ IH^2 \equal{} IO^2\ \Longleftrightarrow\ 4R^2 \plus{}$ $ 4Rr \plus{} 3r^2 \minus{} p^2 \equal{} R^2 \minus{} 2Rr\ \Longleftrightarrow\ p^2 \equal{}$ $ 3(R \plus{} r)^2\ \Longleftrightarrow\ \boxed {\ p \equal{} (R \plus{} r)\sqrt 3\ }$ .

$ \blacktriangleright\ \left\|\begin{array}{c} \tan\frac A2 \plus{} \tan\frac B2 \plus{} \tan\frac C2 \equal{} \frac {4R \plus{} r}{p} \\
 \\
\tan\frac A2\tan\frac B2 \plus{} \tan\frac B2\tan\frac C2 \plus{} \tan\frac C2\tan\frac A2 \equal{} 1 \\
 \\
\tan\frac A2\tan\frac B2\tan\frac C2 \equal{} \frac rp\end{array}\right\|\ \Longleftrightarrow$ the roots of the equation $ f(t) \equal{} p\cdot t^3 \minus{} (4R \plus{} r)\cdot t^2 \plus{} p\cdot t \minus{} r \equal{} 0$

are $ \left\{\tan\frac A2,\tan\frac B2,\tan\frac C2\right\}$ . Therefore, $ \boxed {\ 60^{\circ}\in \{A,B,C\}\ }$ $ \Longleftrightarrow$ $ f\left(\frac {1}{\sqrt 3}\right) \equal{} 0$ $ \Longleftrightarrow$ $ \boxed {\ p \equal{} (R \plus{} r)\sqrt 3\ }$ .[/color]

[quote="Virgil Nicula"]Let $ ABC$ be a triangle. Prove that $ \boxed {\ IO = IH\ \Longleftrightarrow\ 60^{\circ}\in \{A,B,C\}\ }$ .[/quote]
[hide="Solution"]
$ H$ and $ O$ are isogonal conjugates of $ \triangle ABC$, so $ \angle HAI = \angle OAI$.  Also, $ AI = AI$ and $ IO = IH$, so either $ \triangle AHI\cong \triangle AOI$ or $ AHIO$ is cyclic.

We can do the same with the other points.  Now, assume that more than two of the points (say $ A$ and $ B$) have the property that $ \triangle AHI\cong \triangle AOI$ and $ \triangle BHI\cong \triangle BOI$.  This means that $ AH = AO = BO = BH$.  Yet, since $ AB = AB$, we conclude that $ \triangle AHB\cong \triangle AOB$.  Thus, $ H = O$, or $ H$ is the reflection of $ O$ across $ AB$.  In the former case, we see that $ \triangle ABC$ is equilateral, so $ \angle A = \angle B = \angle C = 60$.  In the second case, we realize that either $ 2\angle ACB = \angle AOB = \angle AHB = 180 - \angle ACB\implies \angle ACB = 60$ if $ \angle ACB$ is acute or $ \triangle ABC$ must be obtuse with obtuse $ \angle C$.  In the former subcase, we are done since we have found an angle equal to $ 60$.  Considering the second subcase, $ \angle AOB = 360 - 2\angle ACB$.  The triangle congruency yields that $ 360 - 2\angle ACB = \angle AOB = \angle AHB = 180 - \angle ACB$, so $ \angle ACB = 180$, which is impossible.  Thus, $ H$ cannot be the reflection of $ O$ across $ AB$ if $ \angle ACB$ is obtuse.

If two of the points (say $ B$ and $ C$) have the property that $ BHIO$ and $ CHIO$ are cyclic, then we see that $ BCOIH$ is cyclic.  Thus, $ 90 + \frac {\angle BAC}{2} = \angle BIC = \angle BOC = 2\angle BAC\implies \angle BAC = 60$ if $ \angle ABC$ is acute.  If $ \angle BAC$ is obtuse, then $ 360 - 2\angle BAC = \angle BOC = 180 - \angle BIC = 90 - \frac {\angle BAC}{2}$, so $ 270 = \frac {3\angle BAC}{2}$, so $ \angle BAC = 180$, which is impossible.  We see that $ \angle BAC$ cannot be obtuse in this case, so $ \angle BAC = 60$.

All the cases are complete (since there are three points, $ A$, $ B$, and $ C$, two of them must have the property that congruent triangles or cyclic quadrilaterals are formed) and a $ 60$ degree angle is formed in each case, so we see that a $ 60$ degree angle appears if $ IH = IO$. [/hide]

how about this: prove that $ IH$ is an integer multiple of $ IO$ if and only if $ 60^{\circ}\in\{A,B,C\}$?  :D

[b]April[/b] where can I find the proof of lemma that you have used in your solution?

Hi [b]delegat[/b],

It's well-known that $ \sum a\overrightarrow{IA} \equal{} \overrightarrow{0}$, where $ I$ is the incenter of the given triangle $ ABC$. So now, we have $ \sum aMA^2 \equal{} \sum a\left(\overrightarrow{MI} \plus{} \overrightarrow{IA}\right)^2 \equal{} \left(\sum a\right)MI^2 \plus{} 2\overrightarrow{MI}\cdot \sum a\overrightarrow{IA} \plus{} \sum aIA^2$, it completes our proof for the lemma. Where $ M$ is an arbitrary point on the plane.

In fact, we have the following result: Let be given a triangle $ ABC$ and a point $ I$ such that $ \alpha\overrightarrow{IA} \plus{} \beta\overrightarrow{IB} \plus{} \gamma\overrightarrow{IC} \equal{} \overrightarrow{0}$, ($ \alpha \plus{} \beta \plus{} \gamma\neq 0$). Then we have $ \sum \alpha MA^2 \equal{} \sum\alpha IA^2 \plus{} \left(\sum\alpha\right)MI^2$, with any point $ M$ on the plane.


I tried to use

\begin{eqnarray*}
\end{eqnarray*}

It seems to work and it looks pretty nice.  But it displayed the exact same thing twice. (see [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=6474]this[/url]  for an example).

\begin{eqnarray*}
a+\sqrt{ab}+\sqrt[3]{abc}
&=& a^{\frac{1}{3}}a^{\frac{1}{3}}a^{\frac{1}{3}} + a^{\frac{1}{3}}(\sqrt{ab})^{\frac{1}{3}}b^{\frac{1}{3}}
	+ a^{\frac{1}{3}}b^{\frac{1}{3}}c^{\frac{1}{3}} \\
&\leq & (a+a+a)^{\frac{1}{3}} (a+ \sqrt{ab} + b)^{\frac{1}{3}} (a+b+c)^{\frac{1}{3}} \\
&\leq & (a+a+a)^{\frac{1}{3}} (a+ \frac{a+b}{2} + b)^{\frac{1}{3}} (a+b+c)^{\frac{1}{3}} \\
&=&3\sqrt[3]{a \cdot \frac{a+b}{2} \cdot \frac{a+b+c}{3}}.
\end{eqnarray*}

Very nice! The LaTeX double display problem has been fixed. Cheers!   :D

\begin{eqnarray*}5&=&5 \\
3&=&3
\end{eqnarray*}

I think it should work now (though your old posts may still be tied to the doubles - I'll see what I can do about fixing those).

[tex]

\begin{eqnarray*}
2+2&=&4\\
&=& 5
\end
[/tex]

Yay!  It works!

\begin{eqnarray*}
a &=& b\\
\ &=& c
\end{eqnarray*}

what's wrong with my test?

test start

\begin{eqnarray*}
p&=&q \\
3&=&3
\end{eqnarray*}

test end

there is a problem if the equation starts with a letter, not a number.

A workaround for the moment is to put in a blank line:
[code]\begin{eqnarray*}
8 &=& 4 + 4 \\
 &=& 2 + 2 + 2 + 2 \\
 &=& 1+1+1+1+1+1+1+1
\end{eqnarray*}[/code]
gives
\begin{eqnarray*}
8 &=& 4 + 4 \\
 &=& 2 + 2 + 2 + 2 \\
 &=& 1+1+1+1+1+1+1+1
\end{eqnarray*}

\begin{eqnarray*}5& = &5\\3&=&3\end{eqnarray*}

Fixed.  Thanks for the tip, stevem.


calculus
trigonometry
geometry
ratio
calculus computations

For $0 \leq \alpha$, $\beta \leq \frac{\pi}{2}$, and $\frac{\pi}{2}\leq \alpha+\beta \leq \pi$.

Show that $sin(\alpha+\beta) = sin(\alpha)cos(\beta)+sin(\beta)cos(\alpha)$

Look here for example

[url]http://www.phy6.org/stargaze/Strig5.htm[/url]

Thank you for the link. But the pictorial arguments that they have on their site are true for when $\alpha+\beta \leq \frac{\pi}{2}$ but not in the case in my post. If anyone knows of other links or wants to volunteer to write a pictorial argument or hint on how to proceed I will appreciate it.

I believe Apostol's Calculus Vol. 1 has what you are looking for.

Do you have the full info about the book?

Perhaps this will help. Have a look at this
site
[url]http://www.cut-the-knot.org/proofs/sine_cosine.shtml[/url]

It is, generally, a interesting page.

(Found this too: )[url]http://whyslopes.com/etc/CalculusAndBeyond/ch23a.html[/url]

You can get a description on Amazon. Author is Tom Apostol and the book is Calculus Vol. 1. It doesn't have exactly what you're looking for but the argument can be extended. Look on p104. It's hard to draw here, of course. Perhaps someone will find a picture otherwise I'll try my hand at it but I can't guarantee.

I couldn't open several of those links...
[img]8377[/img]
If we let $\alpha=\angle ABD, \beta=\angle CBD$ we have that \[\sin(\alpha)\cos(\beta)+\sin(\beta)\cos(\alpha)=\frac{DB\cdot AC}{AB\cdot BC}\] And we want to show that $\frac{DB\cdot AC}{AB\cdot BC}=\frac{AC}{EC}\iff \frac{EC}{BC}=\frac{AB}{DB}$ which is obvious since $\angle EAC=90=\angle EBC$ by construction, diameter and $\angle BEC=\angle BAC$ since they stubtend the same arc so $\triangle EBC\sim \triangle ADB$ and the problem is done.

Alternatively, notice that $DB\cdot AC$ is the area of $ABC$ so the ratio $\frac{DB\cdot AC}{AB\cdot BC}=\frac{K}{AB\cdot BC}=\sin b$ by a well known area formula ($K$ is area) but I hesitated about writing that since I think to prove that area relation requires the angle addition formula...

color,
The other link that you provided is useful but the same as your first link.

me@home,
It is clear that the sum $\alpha+\beta$ is too big to be contained in a triangle and this seems to be the case in your argument. Your argument works for $0 \leq \alpha+\beta \leq \frac{\pi}{2}$ but I doubt that it work for $\frac{\pi}{2}\leq \alpha+\beta \leq \pi$ (see the restrictions in my first post ;-).

But isn't it possible in this setting:
(IF YOU LET $D$ and $A$ approach $B$)
[img]http://www.cut-the-knot.org/proofs/sin_cosine3.gif[/img]

Se my first link

[url]http://www.cut-the-knot.org/proofs/sine_cosine.shtml[/url]

Sorry if I'm mistaken.  :oops:

Ooh for some reason when I was making the diagram I specifically looked at that constraint and thought that $\pi/2=45$... :oops:

Anyway the specific diagram doesn't matter, just points are shuffled around. But here is another diagram if you like [img]8380[/img]
the only affect of the requirement was to shuffle $E$ to the other side of $AC$...


I will be taking the us physics olympiad preliminary test this year. I was wondering where I could find some of the past exams and solutions. I tried searching it on google but came up with only the international physics olympiad stuff. Any help is greatly appreciated. Thanks.

there is an official website for the U.S. physics team.
most of the past tests with solutions are up there... ;)

also, there is a physics forum here as well, where you can post these questions there.


function
geometry
geometric transformation
reflection
analytic geometry
calculus
derivative

Here is a nice problem ( may be it is well-known ).

Consider a smooth function $ f: (0,+ \infty) \rightarrow \mathbb{R} $,
such that $ f(x) > 0 $ for every $ x > 0 $, $ f(x) $ is convex, decreasing and
$ lim_{x \rightarrow \infty } f(x) = 0 $.
Consider now a region between the graph of $ f(x) $ and the positive real axis.
Think of it as a "room" and positive real axis and the graph of $ f(x) $ as two
"walls". Now take a ball and through it inside the "room". When it touches the wall,
it reflects by the usual law. Prove that after some time the ball will
go back and exit the room.

[quote="Leva1980"]Here is a nice problem ( may be it is well-known ).
[/quote]
It is the one of the favorite problems of the authors of "Selected problems in real analysis". They even put the corresponding picture on the book cover. It was circulating in Leningrad during my school years and, possibly, even before that.

Nice!  :)
I got it throug my friend, who heard it in his job.

Hmm... Nice problem indeed.  Do you also have the proof and were just posting the question or did you need an answer?  If you have the proof, could you please post it?  I would like to see how a question like this is approached.

I have a proof, but I want other people to find it.  :)

Well, since nobody has posted it here, do you think you could?  I am interested.

Thanks,

Alex

Minor question: We take $f$ to be differentiable, right? Or not?

Another question (after two and a half years):

Are you sure the ball (which I considered to be a point) always exits the room? I did some silly angle chasing and I came to the conclusion that given a starting direction one can find (inductively) a convex function $ f$ such that the ball remains "trapped" between $ f$ and $ Ox$ (and the $ x$-coordinate keeps on increasing, but from my "picture" it's unlikely that it will go "very far").

Have you checked that you inductively constructed function tends to $ 0$? If there were a limiting point, the derivative at it would be $ 0$ already. ;) In general, "silly angle chasing" is the right way to approach the problem. :)

That's a big :oops: ...  :blush:

I think we can do something like this: given the direction of the ball $ \alpha$, the angle $ \gamma$ that the tangent to the graph of $ f$ in the point where the ball bounces off and the value of the function in that bouncing point, we determine some bounds on the value of the function in the next bouncing point. Apparently, it's at least $ \frac{\tan \left( \alpha \plus{} 2 \gamma \right) \minus{} \tan \gamma}{\tan \left( \alpha \plus{} 2 \gamma \right) \plus{} \tan \gamma}$ times the previous value (I really did not want to make this computation the first time around, I thought that taking points just a little bit over that tangent line would be "enough"). We really want this product to converge, i.e. we want $ \sum \frac{\tan \gamma}{\tan \gamma \plus{} \tan \left( \alpha \plus{} 2 \gamma \right)}$ to converge. Here we do note that $ \alpha \plus{} 2 \gamma < \frac{\pi}2$ and that since $ \alpha$ increases, it has a limit $ \leq \frac{\pi}2$ (furthermore, $ \gamma \to 0$). Thus, we can safely compare that thing with $ \sum \tan \gamma$, i.e. with $ \sum \gamma$. However, this is obviously convergent since to the original $ \alpha$ we keep adding $ 2 \gamma$'s, whilst remaining under $ \frac{\pi}2$.


[quote="boxedexe"]Consider this fortunate incident. A girl was crossing a railroad bridge when, halfway across, she saw a train 50 metres away moving toward her. She immediately turned and ran so that the train missed her by the narrowest of margins. If she had tried to cross the bridge, the train would have struck her one metre before she could have reached the end. How long is the bridge?

Masoud Zargar[/quote]

Does the "halfway across" mean that she was exactly at $\frac{1}{2}$ of the bridge? If it does, the girl would be hit even if he turned. If it doesn't, it seems that we need more information to solve this problem. For one thing, the only given value of distance is 50m, but that does not help in finding the width of the bridge.

Notation:

$l$ - the length of the bridge
$D$ - the initial distance between the girl and the train (given to be $50$ meters)
$d$ - the distance between a possible hit point and the endpoint of the bridge (given to be $1$ meter)
$v_{t}$ - the velocity of the train
$v_{g}$ - the velocity of the running girl

By the given conditions, we have two equations:

$\frac{D+{l\over 2}}{v_{t}}=\frac{{l\over 2}}{v_{g}}$

$\frac{D-{l\over 2}+d}{v_{t}}=\frac{{l\over 2}-d}{v_{g}}$

Expressing ${v_{t}\over v_{g}}$ from both of those and equating, we get

$\frac{D+{l\over 2}}{{l\over 2}}=\frac{D-{l\over 2}+d}{{l\over 2}-d}$

which is a quadratic equation in $l$. After rearranging we get

$l^{2}-2dl-2Dd=0$, and the solution is $l=d+\sqrt{d^{2}+2Dd}$. For the given numeric data, we obtain $l=1+\sqrt{101}\approx 11.05$ meters.


How many non-negative integer solutions are there to:

x + y + z  <= 100

It is a very standart problem.
In fact we are to find the number of solutions for $x+y+z+t=100$.
Consider $(x+1)+(y+1)+(z+1)+(t+1)=104$. Now imagine a sequence of 104 units. We are to divide it into 4 part (then number of units in the first part is $x+1$, in second - $y+1$, and so on). In order to divide sequence into 4 part we need to choose three points of 'cuts'. There are 103 possibilities to select such a point. So number of choices is $C_{103}^3$.

I appreciate your completely unselfish time!


The solution of $ax>-1$, $x+a>0$ is not a empty set. Find the range of $a$.

[quote="fourierseries"]Graphing, we get $-1 \le a \le \infty$[/quote]
$a$ cannot be equal to $-1$.

[quote="fourierseries"]Graphing, we get $-1 \le a \le \infty$[/quote]
How do you graph it?  :?

(i)When $a=0$ , there is always solution for $x$

(ii)When $a>0$ , we have $x>\dfrac{-1}{a}$ and $x>-a$ . We always have solution in this case since both sign is $>$

(iii)When $a<0$ , we have $x<\dfrac{-1}{a}$ and $x>-a$ . For this to have solution , the only possibility is $-a<x<\dfrac{-1}{a}$ which means $-a<\dfrac{-1}{a}$ . Solving this will give us $-1<a<0$

Combine the three cases above , $a>-1$ is the range .


I think it would be a wize idea to define all of the following for 8 integers: The mean, median, unique mode, and range :)

[quote="Kle"]The mean, median, unique mode, and range of a collection of eight integers are all equal to 8. What is the largest integer that can be an element of this collection?[/quote]

Please learn to post in the correct section.  Nearly all of your problems would be appropriate for Pre-Olympiad - the remainder would go in Calculus Computations and Tutorials. In particular, I recognize this as an old AMC (10) problem.

Is it[hide]6,6,6,8,8,8,8,14, so the answer would be 14?[/hide]


geometry
circumcircle
trigonometry
geometry proposed

Given triangle $ ABC$. Let the tangent lines of the circumcircle of $ AB$ at $ B$ and $ C$ meet at $ A_0$. Define $ B_0$ and $ C_0$ similarly.
a) Prove that $ AA_0,BB_0,CC_0$ are concurrent.
b) Let $ K$ be the point of concurrency. Prove that $ KG\parallel BC$ if and only if $ 2a^2\equal{}b^2\plus{}c^2$.

[quote="Johan Gunardi"]Given triangle $ ABC$. Let the tangent lines of the circumcircle of $ AB$ at $ B$ and $ C$ meet at $ A_0$. Define $ B_0$ and $ C_0$ similarly.
a) Prove that $ AA_0,BB_0,CC_0$ are concurrent.
b) Let $ K$ be the point of concurrency. Prove that $ KG\parallel BC$ if and only if $ 2a^2 \equal{} b^2 \plus{} c^2$.[/quote]

[hide="Solution a)"]
Let $ w$ is circumcircle of $ \triangle ABC$.
Then it's clear to see that incrircle of $ \triangle A_0B_0C_0$ is $ w$, and $ A,B,C$ is tangent point's of $ B_0C_0, A_0C_0,A_0B_0$ respectively. Then we have $ \frac{A_0C\cdot B_0A\cdot C_0B}{CB_0\cdot AC_0\cdot BA_0}\equal{}1$(becouse $ A_0B\equal{}A_0C, B_0A\equal{}B_0C, CA_0\equal{}CB_0$)
So by $ Cheva$ $ Theorem$ we have that $ AA_0,BB_0,CC_0$ are concurrent.[/hide]

Hope that point $ b)$ will be clear as soon as possible(may be next year=)).

--------------------------------------------------------------
By th way Happy New Year everyone!!!!!!

a) clearly the concur in the gergonne point of the tangential triangle. It's also well-know that $ AA_0$ is a symmedian so K is also the symmedian point of ABC.

b) Let M,N,L the midpoint of BC,CA,AB. Let J the midpoint of the altitude from A, so is know that K stay on JM i.e. in the medial triangle MNL, K is the isotomic conjugate of the orthocenter of MNL. But the centroid G of ABC is also the centroid of MNL so the thesis becomes:

Let Q the isotomic cojugate of ABC and let AQ,BQ,CQ meet BC,CA,AB in D,E,F. Prove that $ \frac{AQ}{QD} \equal{} 2 \ \Longleftrightarrow \ 2a^2 \equal{} b^2 \plus{} c^2$.

for menelaus on BDA and trasversal FQ we have: $ \frac{AQ}{QD} \equal{} \frac{BC}{CD} \cdot \frac{AF}{FB} \equal{} \frac{a}{c \cos B} \cdot \frac{a \cos B}{b \cos A} \equal{} \frac{a^2}{bc \cos A}$

so $ \frac{AQ}{QD} \equal{} 2 \ \Longleftrightarrow \ a^2 \equal{} 2 bc \cos A  \ \Longleftrightarrow \ a^2 \equal{} b^2 \plus{} c^2 \minus{}a^2  \ \Longleftrightarrow \ 2a^2 \equal{} b^2 \plus{} c^2$


Ok...so right now im doing AoPS vol 1, and on chapter 8, there's this proof that some greek guy made to disprove the widely-accepted belief that rational numbers are the only numbers possible in the mathematical world. it goes like this:

[b] Suppose $ \sqrt{2}$ can be written as the quotient of two integers p and q such that $ p/q=\sqrt{2}$, so $ p^{2}/q^{2}=2$ or $ p^{2}=2q^{2}$
clearly p is even, otherwise the right side is divisible by 2 and the left isn't. thus there is some integer $ r$ such that $ p=2r$, so we have $ 4r^{2}=2q^{2}$ or $ 2r^{2}=q^{2}$
now q must be even, otherwise the left is divisible by 2 and the right isn't. but if both p and q are even, then the fraction $ p/q$ could not have been in lowest terms, because the numerator and the denominator has a common factor of 2. this is a contradiction, so the assumption that $ p/q=\sqrt{2}$ must have been false[/b]

this is directly out of the book. what i don't understand is how this proves that rational numbers are not the only numbers in math. all i get from this proof is that if you were to right $ \sqrt{2}$ as a fraction $ p/q$ the fraction would never be in simplest form. help explaining this proof would be appreciated.

Consider the number $ \frac{a}{b}$, where $ a$ and $ b$ are integers. There are two cases: either $ gcd(a,b)=1$, and $ \frac{a}{b}$ is in simplest form, or $ gcd(a,b)=k, k \not = 1$, and expressed in simplest form, the number is $ \frac{a/k}{b/k}$. Either way, the number [b]can[/b] be written as a fraction in simplest form.

This proof shows that $ \sqrt{2}$ [b]can't[/b] be written as a fraction in simplest form.

We then have the following logic flow:

1. If a number is a rational number, it can be expressed in simplest form.

2. So if a number cannot be written in simplest form, it cannot be a rational number.

3. Since $ \sqrt{2}$ cannot be written in simplest form, $ \sqrt{2}$ cannot be a rational number.

4. Thus, $ \sqrt{2}$ is a number, but is not a rational number.

5. Hence, not all numbers are rational.

I would reconsider slightly your wording:

[quote]0. $ \sqrt2$ is a number.

1. If a number is a rational number, it can be expressed in simplest form.

2. So if a number cannot be written in simplest form, it cannot be a rational number.

3. $ \sqrt{2}$ cannot be written in simplest form.

4. Thus, $ \sqrt{2}$ is not a rational number.

5. Hence, not all numbers are rational.[/quote]

I think that all the 'simplest form' stuff is a waste.

We can WLOG say that $ p$ and $ q$ are coprime. But then we get a contradiction that finishes the proof.


I have a question for former semifinalists.

I know the test is in january, which leaves about 16 weeks.
If I go through "Fundamentals of Physics" by Resnick & Halliday &Walker (both Vol 1 and Vol 2) there is about 32 chapters.
I already know most of the beginning chapters so reviewing them will only take a little bit of time. I can finish both volumes by the test date.

My question is:
If I go through only this book (all the chapters of both volumes), is it enough to qualify for the semifinal test?
Also, what are the major chapters/topics that I have to go through to qualify for semifinal? (Chapters that I will need to spend a bit more time on)

Have you checked out the USAPhO site? They have some previous exams to qualify for the semifinal round. If there was one subject that I would study to get to the semi round, I would go over tension. In most of the exams, there are about five questions dealing with tension. If you do qualify for semi round, study about wave nature of light including much about the $\psi$ function. I am not familiar with your book, but if you could give me some more information about the major topics the book contains, I may be able to help more. Neway, hope this helps for now.


combinatorial geometry
combinatorics unsolved
combinatorics

everybody help me this problem:
we have n lines in a plane.Find the most intersection points.

thanks!

At best, every pair of lines intersects in a unique point; thus the answer is $ {n \choose 2}$.

How about if three lines are concurrent?This problem is not simple as you solve :wink:

You mean you want to show that it's possible for lines in a plane to be arranged so that they all intersect in distinct points?  Very well.  Here's a number-theoretic construction (which is somewhat overkill):

Consider the lines

$ L_k : y \equal{} m_k x \plus{} k, k \equal{} 1, 2, ... n$

where $ m_1, m_2, ... m_n$ are algebraically independent over $ \mathbb{Q}$.  Then the intersection of any two of the points is algebraically independent of (and therefore cannot be equal to) any of the others.  :)

[b]Edit:[/b]  I feel bad for how non-geometric that construction was.  Here's an inductive construction:

Two lines intersecting in $ 1$ point is clearly possible.

Given $ n$ lines intersecting in $ {n \choose 2}$ distinct points, consider the convex hull of those points, and add an extra line outside that hull not parallel to any of the given lines.  This line clearly intersects each of the $ n$ existing points in $ n$ new points.


If $ \left (a\plus{}\frac{1}{a} \right )^2\equal{}3$, then $ a^3\plus{}\frac{1}{a^3}$ equals:

$ \textbf{(A)}\ \frac{10\sqrt{3}}{3} \qquad
\textbf{(B)}\ 3\sqrt{3} \qquad
\textbf{(C)}\ 0 \qquad
\textbf{(D)}\ 7\sqrt{7} \qquad
\textbf{(E)}\ 6\sqrt{3}$

[hide="Click for solution"]
$ a^3\plus{}\frac{1}{a^3}\equal{}\left ( a\plus{}\frac{1}{a} \right )^3\minus{}3 \left (a\plus{}\frac{1}{a} \right )\equal{}3\sqrt{3}\minus{}3\sqrt{3}\equal{}0$, or $ \boxed{\textbf{(C)}}$.
[/hide]

[hide]$ \left | a \plus{} \frac {1}{a} \right | \not \in [ \minus{} 2 \ldots 2] \implies a \not \in \mathbb{R}$

$ \therefore \text{Im }a \equal{} \text{Im } \frac {1}{a} \neq 0 \implies |a| \equal{} 1 \implies a \equal{} \text{cis } \theta$

$ \therefore \text{cis } \theta \plus{} \text{cis} (\minus{} \theta ) \equal{} 2 \cos \theta \equal{} \sqrt {3} \implies \theta \equal{} \frac {\pi}{6}$

$ \therefore a^3 \plus{} \frac {1}{a^3} \equal{} \text{cis } \frac {\pi}{2} \plus{} \text{cis } \frac { \minus{} \pi}{2} \equal{} 0$
[/hide]

[quote="AIME15"][hide="Click for solution"]
$ a^3 \plus{} \frac {1}{a^3} \equal{} \left ( a \plus{} \frac {1}{a} \right )^3 \minus{} 3 \left (a \plus{} \frac {1}{a} \right ) \equal{} 3\sqrt {3} \minus{} 3\sqrt {3} \equal{} 0$, or $ \boxed{\textbf{(C)}}$.
[/hide][/quote]

Why $ a\plus{}\frac{1}{a}>0?$

[quote="kunny"][quote="AIME15"][hide="Click for solution"]
$ a^3 \plus{} \frac {1}{a^3} \equal{} \left ( a \plus{} \frac {1}{a} \right )^3 \minus{} 3 \left (a \plus{} \frac {1}{a} \right ) \equal{} 3\sqrt {3} \minus{} 3\sqrt {3} \equal{} 0$, or $ \boxed{\textbf{(C)}}$.
[/hide][/quote]

Why $ a \plus{} \frac {1}{a} > 0?$[/quote]
If you have $ a \plus{} \frac{1}{a} < 0$, then the answer is still the same:

$ \left(a \plus{} \frac{1}{a}\right)^3 \minus{} 3\left(a \plus{} \frac{1}{a}\right) \equal{} \minus{}3\sqrt{3} \plus{} 3\sqrt{3} \equal{} 0$

[quote="TZF"][hide]$ \left | a \plus{} \frac {1}{a} \right | \not \in [ \minus{} 2 \ldots 2] \implies a \not \in \mathbb{R}$

$ \therefore \text{Im }a \equal{} \text{Im } \frac {1}{a} \neq 0 \implies |a| \equal{} 1 \implies a \equal{} \text{cis } \theta$

$ \therefore \text{cis } \theta \plus{} \text{cis} ( \minus{} \theta ) \equal{} 2 \cos \theta \equal{} \sqrt {3} \implies \theta \equal{} \frac {\pi}{6}$

$ \therefore a^3 \plus{} \frac {1}{a^3} \equal{} \text{cis } \frac {\pi}{2} \plus{} \text{cis } \frac { \minus{} \pi}{2} \equal{} 0$
[/hide][/quote]
What do you mean by $ [\minus{}2\ldots2]$?

[quote="MCTP"][quote="kunny"][quote="AIME15"][hide="Click for solution"]
$ a^3 \plus{} \frac {1}{a^3} \equal{} \left ( a \plus{} \frac {1}{a} \right )^3 \minus{} 3 \left (a \plus{} \frac {1}{a} \right ) \equal{} 3\sqrt {3} \minus{} 3\sqrt {3} \equal{} 0$, or $ \boxed{\textbf{(C)}}$.
[/hide][/quote]

Why $ a \plus{} \frac {1}{a} > 0?$[/quote]
If you have $ a \plus{} \frac {1}{a} < 0$, then the answer is still the same:[/quote]

Yes, since $ a\cdot \frac {1}{a} > 0$, thus the signs of $ a$ and $ \frac {1}{a}$ are same.

Here is my solution:

Use $ \boxed{A^3 \plus{} B^3 \equal{} (A \plus{} B)^3 \minus{} 3AB(A \plus{} B)}$,

$ a^3 \plus{} \frac {1}{a^3} \equal{} \left(a \plus{} \frac {1}{a}\right)^3 \minus{} 3\left(a \plus{} \frac {1}{a}\right)$

$ \equal{} \left(a \plus{} \frac {1}{a}\right)^2\left(a \plus{} \frac {1}{a}\right) \minus{} 3\left(a \plus{} \frac {1}{a}\right) \equal{} 0$.


invariant
function
algorithm
geometry solved
geometry

Has this question ever been answered?

Using a straightedge only, is it possible to construct a perpendicular from a given point to a given line?

[quote="Bojan Basic"]Using a straightedge only, is it possible to construct a perpendicular from a given point to a given line?[/quote]

This is impossible. In fact, a construction using a straightedge alone is a construction consisting of the following two fundamental operations, repeated several times: draw a line through two given points, and draw the point of intersection of two given lines. These operations are part of the incidence structure of the plane and thus invariant under every projective transformation; however, perpendicular lines are not invariant under projective transformations, i. e. in general, a projective transformation can map two perpendicular lines to two non-perpendicular lines, and thus there cannot be a projectively invariant construction of perpendiculars.

If you are not too familiar with projective transformations, replace all the above appearances of the word "projective" by "affine"; the argument would still work.

  Darij

[quote="darij grinberg"]In fact, a construction using a straightedge alone is a construction consisting of the following two fundamental operations, repeated several times: draw a line through two given points, and draw the point of intersection of two given lines.[/quote]
And what about choosing an arbitrary point?

[quote="Bojan Basic"]And what about choosing an arbitrary point?[/quote]

Okay, but that's as well projectively invariant.

Let me make the argumentation a bit more precise:

Assume that there is a construction of the perpendicular to a given line through a given point by straightedge only. In other words, there exists a function a(P; g) which ascribes to any point P and any line g the perpendicular to the line g through the point P, and this function can be described as an algorithm composed of the following elementary operations:

- taking an arbitrary point;
- drawing a line through two given points;
- drawing the point of intersection of two given lines.

Then, since these elementary operations are invariant under projective transformations, the function a itself must be invariant under projective transformations; thus, if $\pi$ is any projective transformation, we have $a\left(\pi\left(P\right);\;\pi\left(g\right)\right)=\pi\left(a\left(P;\;g\right)\right)$. Now, let's choose $\pi$ to be a projective transformation which maps the two perpendicular lines g and a(P; g) to two non-perpendicular lines, i. e. which satisfies $\pi\left(a\left(P;\;g\right)\right)\not\perp\pi\left(g\right)$ (in fact, such a projective transformation must exist, since in general, projective transformations don't preserve perpendicularity).

Now, since the output a(P; g) of the function a for a point P and a line g is a line perpendicular to g, we must have $a\left(\pi\left(P\right);\;\pi\left(g\right)\right)\perp\pi\left(g\right)$; since $a\left(\pi\left(P\right);\;\pi\left(g\right)\right)=\pi\left(a\left(P;\;g\right)\right)$, this rewrites as $\pi\left(a\left(P;\;g\right)\right)\perp\pi\left(g\right)$, what contradicts with $\pi\left(a\left(P;\;g\right)\right)\not\perp\pi\left(g\right)$. Thus, we got a contradiction, and it follows that there is no construction of the perpendicular to a given line through a given point by straightedge only.

Similarly we can prove that, e. g., there is no construction of the parallel to a given line through a given point by straightedge only.

  Darij


On a cube, 27 points are marked in the following manner: one point in each corner, one point on the middle of each edge, one point on the middle of each face, and one in the middle the cube. The number of lines containing three out of these points is

A. 33
B. 42
C. 49
D. 72
E. 81

[hide]I am going to try casework here.

Different types of lines that contain 3 points:

On each edge, of which there are $ 12$.

Across each face diagonally.  We have $ 2$ such lines on each of $ 6$ faces, for a total of $ 12$ lines.

Across each face vertically/horizontally (through the midpoint of the face).  Again, there are $ 2$ lines on each of $ 6$ faces, for a total of $ 12$ lines.

Through the middle of the cube diagonally.  There are $ 4$ diagonals from one vertex of the cube to the complete opposite (i.e., longest diagonals) and $ 6$ diagonals that connect the midpoints of the edges from opposite sides of the cube.  There is a total of $ 10$ lines here.

Through the middle of the cube horizontally or vertically (i.e., connect the middles of two opposite faces).  There are $ 3$ such lines.

This covers all possibilities, so the total is $ 12 \plus{} 12 \plus{} 12 \plus{} 10 \plus{} 3 \equal{} 49 \equal{} > C$[/hide]

[hide="Much Faster Way"]

We can divide the lines in two cases: ones that contain the one in the middle of the cube and ones that do not contain the one in the middle.

For the latter: There are 12 segments that are also edges; 12 segments found by connecting the midpoints (these midpoints are on same face); and 12 segments that are also diagonals = 36 segments

Now, for the ones that contain the one in the middle, we can do casework but there is much better way. Note that excluding middle one in the cube, there are 13 pairs of points so there are 13 distinct lines that contain the one in the middle. Thus, the answer is 36+13 = 49. [/hide]


What are the topics of IIT Physics and math syllabus that I need to cover beforehand so that I may be able to utilize FIIT-JEE coaching properly :?: One of my friends found it difficult to understand what they taught at the coaching classes as they were far ahead of what was being taught at school and tuitions. They even skipped some of the basic lessons.Please help! :read:

hi scary math....
I myself was a FIITJEEian during my class 9 & 10...but i left the institute since they started showing irresponsibility towards children & their career....
if u would consider my advice,it would b better if u join some other institute......
in which class r u?????????

Well,I am in mid-10th right now,and trying to prepare for the ICSE and RMO simultaneously.I have not joined any coaching centre yet,but one of the girls living in my colony greatly benefitted from FIIT-JEE coaching (Kolkata centre) and ranked 1264 in the IIT-JEE.She took training from 9th and was also selected in RMO and ISI.Please suggest the topics that I need to cover.


Thursday eve at Nationals

8:00, during coaches meeting
EVERYONE COME TO MY ROOM(wherever that may be)

we can play cards and watch SURVivor best show ever
if anyone's interested

Sorry, I can't make it...But can you imagine 227 mathletes stuck in the same room watching survivor?

If Nationals included Wednesday, I'd have a LOST night. :D Good thing my flight's at 11:20, because I'm going to be up until 10 o'clock watching that. :D

we're all in the same hotel so it couldn't be too hard...I'll come if I can convince any teammates to come with me

I'll come... and ruin the whole thing

it'll be fun

How about a meeting of AoPSers only. Maybe at dinner on thursday we can all move into one particular corner, at one particular time :D.

Yeah. that would greatly improve our scores...

*can nobody feel the sarcasm*

I'm pretty sure all the teams will want to meet.

We dont practice the night before at all. last time all we did is stay up really late and drink beer

[quote="k8reindeer"][quote="biffanddoc"]...and drink beer[/quote]
um...
that can't really help your score can it?[/quote]

well passing out early = more sleep :roll:

I'll be busy cramming, obviously.

[quote="biffanddoc"]...and drink beer[/quote]

...[/quote]

Sorry to hear your disappointment tz, but Michigan is one of the hardest states.

[quote="Fanatic"]I. AM. IN. What state are you from ?

Name: Richard Ni
Place:[b] 5th
[/b]
I can spoil the show for you if you want... lol.

Here's what happens if you want to know for the next few episodes

[hide]Aras wins Immunity, Cirie goes home (possible tiebreaker required)

Then I think Aras wins the immunity and takes Danielle, or vice versa. Terry goes home.

Aras is heavily favored to win.[/hide][/quote]

[hide="Off Topic"]
I doubt that's true unless Terry voted for Cirie, while Aras, Danielle, and Cirie all voted for Terry and he used the immunity idol.[/hide]

Fanatic:

Either Aras or Terry will win.
The next immunity is crucial. If Aras wins, then Danielle's gone and Terry is once again, without allies. Even if Terry wins final immunity, he'll lose to whoever he brings to the two.

However, if Terry wins next immunity, he gives the idol to Danielle and Aras is gone. Then, either Danielle or Terry wins the final immunity, and will bring each other to the two (since Cirie can't win final immunity, but will most likely get the vote of the jury.

If Terry goes to the two with Danielle, he'll win, since Austin, Sally, Shane, and Courtney will all vote for him. Austin, Sally, and courtney were his former allies, and will vote for him. Shane won't vote for anyone else because everyone but Terry sold him out.

Mad analysis.

Umm.. what I said wasn't analysis.

It was a spoiler. I said "I can spoil the show for you if you want...".

Trust me. [hide]Cirie goes home, then Terry. DDL and Aras F2[/hide]

[quote="XxHarryxX"][quote="Waxing Rhapsodic"]I'll be busy cramming, obviously.[/quote]

Me too. We should cram together... (I'll do it on the plane!)[/quote]

Cramming is probably not a good idea. All the real preparation has been done months before the actual competition (like in sports), and you should be tapering the last week or so. Cramming is only useful for short term rote memorization of facts, formulas, etc, certainly not anything that will help you in MathCounts.


[hide]\documentclass[11pt]{article}
\begin{document}
What number is less than, greater than 35^2, divisible by 19, and a multiple of 9?

\vspace{19\baselineskip}

Alfreda hiked half her planned trip the first day; tiring, she only covered one-third the remaining distance the second day; rain slowed her to one-forth the remaining distance the third day, and the fourth day she hiked three miles, which was one-fifth of what she had left.  How many miles did she hike during the four days?

\end{document}[/hide]

Look at that.

Why does it italicize all the document after 35^2?  Please make it stop!!!


calculus
derivative
function
calculus computations

[size=150]Hello Everybody,
I am new to this forum, and I wish that I can be helpful as everybody else. :lol:
Well, I have a partial derivatives problem that I couldn't answer at all, please if anybody can answer it please reply. Here is the problem:

Find the second partial derivatives of the following function:
z=arctan ((x+y)/(1-xy))[/size]

Thanks

Hello and welcome  :) Please write with small letters .

[hide="Hint"]
Use the identity $\arctan \left( \frac{x+y}{1-xy}\right) = \arctan x+\arctan y$ .[/hide]

Thanks Ramanujan for your help.
I will make sure that I write in small letters!  :blush:

I have also another question
when a problem says:

Find ∂z/∂x and dz/dx if:
z=xy, where y=f(x)

If I am going to find ∂z/∂x, I will find it with ∂y/∂x !?
Is that right? and it will be ∂z/∂x=x*(∂y/∂x) + y

and how can I find dz/dx if I have to variables which are x & y, but if I am going to put f(x) instead of y and make the equation as
z=x*f(x), then I will find it with f'(x), is that right?

By the way, I am new to Partial Derivatives, so please don't get mad of me if I am asking alot of questions. :oops:

Thanks


trigonometry function calculus derivative

For $60^\circ \leq \theta \leq 120^\circ$ find the maximum and minimum value of the function $y=\cos \frac{\theta }{2}+\sin \frac{\theta }{2}$.

[hide="nonsense"]For easier understanding let's consider $\theta\in \left[\frac{\pi}{6},\frac{\pi}{3}\right ]$ and the function $y=\cos \theta+\sin \theta$.
Since $y'=\sin\theta-\cos\theta$. For $\theta\in \left[\frac{\pi}{6},\frac{\pi}{4}\right ),\sin\theta-\cos\theta<0$,for $\theta\in \left(\frac{\pi}{4},\frac{\pi}{3}\right ],\sin\theta-\cos\theta>0$, so the function decreases and then increases which means that the maximum is in one of the edge points $\frac{\pi}{6}$ or $\frac{\pi}{3}$, and as we can see $y(\frac{\pi}{6})=y(\frac{\pi}{3})=\frac{1+\sqrt{3}}{2}$.[/hide]

For easier understanding let's consider $\theta\in \left[\frac{\pi}{6},\frac{\pi}{3}\right ]$ and the function $y=\cos \theta+\sin \theta$.
Since $y'=\cos\theta-\sin\theta$. For $\theta\in \left[\frac{\pi}{6},\frac{\pi}{4}\right ),\sin\theta-\cos\theta>0$,for $\theta\in \left(\frac{\pi}{4},\frac{\pi}{3}\right ],\sin\theta-\cos\theta<0$, so the function increases and then decreases which means that the maximum is in $\frac{\pi}{4}$. Which gives $y(\frac{\pi}{4})=\sqrt{2}$.

Heh, too much integrating :blush: . (edited now)
Another solution, because $\sin$and $\cos$ are both postive on the given interval we can apply $AM-GM$ to get $\sin(\theta)+\cos(\theta)\geq \sqrt{2}\sqrt{\sin(2\theta)}$,so the maximum is attained when $2\theta=\frac{\pi}{2}\leftrightarrow \theta=\frac{\pi}{4}$

Can anyone solve the problem without using differentiation?

$y = \sqrt{2}\sin\left(\frac{\theta}{2}+\frac{\pi}{4}\right)$

Maximum obviously occurs at $\theta=\frac{\pi}{2}$, yielding $y\left(\frac{\pi}{2}\right)=\sqrt{2}$, and minimum occurs at either $\theta=\frac{\pi}{3}$ or $\theta=\frac{2\pi}{3}$, yielding $y=\frac{1+\sqrt{3}}{2}$.

Another way to do it, which makes it a bit easier to see, is as follows:
$y=\cos \frac{\theta}{2}+\sin \frac{\theta}{2}$
$y^{2}= \cos^{2}\frac{\theta}{2}+\sin^{2}\frac{\theta}{2}+2 \cos \frac{\theta}{2}\sin \frac{\theta}{2}= 1+\sin \theta$
$y = \pm \sqrt{1+\sin \theta}$

Note that from 60º to 120º, we really only need the positive branch, $y=\sqrt{1+\sin \theta}$

Now, clearly the highest sine will give the highest $y$ and the lowest sine will give the lowest $y$

[hide="for the maximum"]
Try QM-AM[/hide]


Well, don't most people think in a language? How do deaf people think, then? How did Helen Keller think?

Hellen Keller thought in a language.  How does anyone think?   She could think she just couldn't reproduce the sound until later in life with help.  She didn't know how.

[quote="JBL"]
How do you know that you think in a language (or at least, what we conventionally think of as a language)? Haven't you ever had thoughts you had difficulty expressing in words?[/quote]

Right, and that's the problem. I don't know if I really think in words. I was just assuming it.

And this is the point where all of this gets deep, and it blows my mind.

[quote]Haven't you ever had thoughts you had difficulty expressing in words?[/quote]

Like when you're in love...  :mrgreen:

Hehe.  I read a book a long time ago called [u]The Language Instinct[/u], by Stephen Pinker.  I vaguely remember that it dealt in part with this problem, but I might be wrong.  There's a very interesting question that can be asked about this -- what capacity do humans have inbred for language?  That is, we see a lot of commonalities among all (well, let me say only "a great number of," since I'm not 100% sure) spoken languages (such as identifiable concepts of noun and verb, for example), and also a wide range of differences (English and French have a singular and plural, while Slovene has a singular, dual and plural.  Many languages don't have pronouns of any identifiable sort, but instead conjugate by suffixes on verbs and so on.)

In answer to your original question, I'd be inclined to say that the deaf probably have a fine understanding of language for the most part -- just not spoken language.  Another interesting question in a similar vein is "what do blind people 'see' when they think of objects?"  Certainly, they have some 'image' of things -- but could you imagine them ever describing it in a way that both you and they understood meaningfully?

Wow, and since I'm going off-topic already, here's another (totally unrelated) question:  computers are immensely commonplace nowadays.  And they all require sight to use.  What do the blind do?  Are they totally cut off from the world of the internet?

well, Deaf people do know how to read, so I would assume that they think the same way they read.  Most people sound out words when they read, but that is not necessary, and I think it would be the same when they think, it seems hard to understand, but its natural to them.

Interesting topic. I always used to take it for granted that everyone thought in some language or other ... until I go talking about this to a woman who was brought up bilingual in English and Polish. I asked her which language she thought in, and she said "Neither - that is like asking me 'what colour are your thoughts' - the question doesn't make sense".

So that made [i]me[/i] think. Maybe it is different for different people ...

I speak both Japanese and English: I came to America in second grade and I didn't speak any English, so I obviously thought in Japanese. Around sixth grade when I moved here I started thinking in both (since my Japanese vocabulary was degenerating some of the words I forgot so I substituted the English equivalant for the Japanese words I forgot) and now I think solely in English. When I move back I predict I'll start thinking in both as my English degenerates and my Japanese gets better, and eventually I'll be back to thinking in Japanese.

My point is, it's very hard to think without the backframe of language. Sure you can think whether you're blind or deaf or whatnot, but I think it'll be immensely more difficult to just think about things with limited information. Like math if you aren't given some material in the first place, it's very hard to create new things. Same with thinking, if you have no prior knowledge of anything or very little knowledge of say language or math, then it'll be very hard to think and come up with logical conclusions.

As to how they think, *shrug* Perhaps they just use their imagination.

why wouldnt deaf people know a language?

Well, many people who are deaf from birth are never able to speak, since they don't have the feedback loop that most of us (who can hear what we say) have.  So what he meant was really "spoken language," not language.

tare why are you going to go back?

i speak chinese, and english i only know how to write the basics in chinese. like 我是中国人。

I think that is a very interesting question. Now you made me wonder. It seems likes people think in a language, otherwise how would they think? It seems that people who are deaf from birth and can't speak would not think the same way. Maybe they have their own language they think in, but then again what do I know?

I guess it is possible for someone to weave out a language of their own from completely nothing but then that person must be a genius since they have to do so with no prior knowledge...

I'm going back because I must, otherwise face extradiction. I choose the former :lol: (and I'm not going to get a citizenship either)

I think you all are taking your personal experiences and assuming that there's something universal about them. Although most people sound out the words when they read, there's nothing mandatory about it. That's just the way that most of us learned to read when we were young, so it's become a part of our reading process. Most speed reading techniques actually teach people to stop thinking audibly when they read.

Also, the deaf do have language. They read in the same languages that we do, and they also have sign language. So in some cases they may translate written words or ideas to familiar representations from sign language.

There are lots and lots of studies about how the brain visualizes and manipulates ideas and information. It turns out that people can think and visualize in many different ways - some that you aren't even conscious of. But what's common between all of them is that people always take familiar representations (be they sounds, or visualizations, or even emotions) as models for whatever they're thinking. People who lack one sense on which to base these representations just construct representations based on their other senses.

There is a very good book called [u]Conversations on Mind, Matter, and Mathematics[/u] by Jean-Pierre Changaux and Alain Connes, which talks about how the brain visualizes and thinks about ideas - specifically mathematical ideas.

Here is a relevant article: [url]http://www.straightdope.com/columns/031226.html[/url].

I found that article interesting.  Something to think about...  I don't know if I agree with it all, but it was interesting.


geometry
3D geometry
search
number theory unsolved
number theory

Prove that $ 26$ is the only number which lies immediately between a perfect square and a perfect cube.


[quote="vittasko"][quote="stancioiu sorin"]From nowhere,...I found this problem:
[color=blue]Problem[/color]
 We take a triangle $\ ABC$ and the points $\ A',B',C'$ on $\ (BC),(CA),(AB)$ such that $\ A'B=B'C=C'A$.Denoting $\ D$ the intersection between $\ CC',AA'$, $\ D$ is closer by $\ A$ and the analogus..$\ E$ on $\ BB'$, closer by $\ B$,$\ F$ on $\ CC'$, closer by $\ C$, what conditions may we have so that the circumcircle of the triangle $\ DEF$ be tangent to a side of the $\triangle ABC$?
ps:Please think about it.Maybe is a stupid a problem, but I found it unusually. :roll:[/quote]
But, it is not true.

kostas Vittas.[/quote]
Even If The Figure is not comming out to be that we can have some conditons on the sides and angles..that's what we require

I Got Something Which May Help You
Let $D\implies z_1$,$E\implies z_2$,$F\implies z_3$
If The circle is tangent to the sides it is it's incircle
Therefore Let The Point Of Tangency Be $P\implies{z_4}$,$Q\implies{z_5}$,$R\implies{z_6}$
Then $A\implies\frac{2z_4z_6}{z_4+z_6}$,$B\implies\frac{2z_4z_5}{z_4+z_5}$,$C\implies\frac{2z_5z_6}{z_5+z_6}$
Let A',B',C' be $z_8,z_9,z_10$
We CAn Put A Condition For A,D,E,B' to be collinear and similarly others ..i hope it works..just try it


(I know the solution already, but it's a cute application.)

Prove that $ S^2 \vee S^4$ and $ \mathbb{C}P^2$ are not stably homotopic.

Two spaces $ X$ and $ Y$ are stably homotopic if $ \Sigma^n X$ and $ \Sigma^n Y$ are homotopic for sufficiently large $ n$.

The second steenrod operation is trivial on $ {\mathbb S}^2\vee{\mathbb S}^4$, but not on $ {\mathbb C}P^2$. As the steenrod operations are stable, the same is true for any supsension of the spaces $ {\mathbb S}^2\vee{\mathbb S}^4$ and $ {\mathbb C}P^2$.

Yeah, that's how I solved it as well. Surprisingly "high-tech" for such a simple result :).


Cybil and Ronda are sisters. The 10 letters from their names are placed on identical cards so that each of 10 cards contains one letter. Without replacement, two cards are selected at random from the 10 cards. What is the probability that one letter is from each sister's name? Express your answer as a common fraction.

It doesnt matter what you piick first. For the 2nd card to be in other name, there are 5 possibilities and 9 cards left. 5/9


algebra unsolved
algebra
trig identities


you can still do the practices and discuss with us on this forum.  Math jams about USAMTS are also available after each round.  The people who made the problems or the chief graders will go over the solutions personally online.

off topic: you're from Taipei American School?? You know an american teacher call Mr. Wittry?? He teaches computer science.  Tell him that Eric Chang from Troy says hi, and all the ACSL team from last year and many other people misses him, because the new comp sci A teacher doesn't know how to teach and ruin the sophomores.... They didn't even make ACSL intermediate this year :o

[quote="rrusczyk"][quote="adeadsniper"]I am a student in the Taipei American School in Taipei, Taiwan. I read the FAQs on the usamts website, and it said the competition is open to all US highschoolers or younger. Does that mean that everyone else, students from other countries, are not allowed to participate? I was part of the MathCounts national competition and learned about the USAMTS through that event. I would really like to participate in another math competition. So could someone find out if there is a way that I can join too?[/quote]

If you are an American citizen, then you can participate.  The USAMTS is currently funded by a branch of the US government, and they can only fund the participation of US residents and US citizens.  I will note that Taiwan has several ARML teams!  Perhaps you could join one.[/quote]

Um. First of all... what is the ARML?
I am a U.S. citizen, but I don't live in the U.S. How should I register? Should I use the state and address of my aunt and uncle who live in the States?

ARML = American Regional Math League

Think this way.. You take best people from "high school" Mathcounts level contests and put them in one or two teams and these incredible people meet on either of three sites (PSU, Univ. of Iowa, and Univ. of Las Vegas) to do a contest.

You can use http://www.arml.com for more information.


Give a positive integer $ n$, let $ p(n)$be the product of the non-zero digit of $ n$.
Let $ S\equal{}p(1)\plus{}p(2)\plus{}...\plus{}p(999)$
Determine the largest prime factor of $ S$

We can count 0 as 1 in the product, so the value is (1+1+2+3+...+9)^3 whose largest prime divisor is 23.

nice method but you have added $ 1$ for $ p(0)$ which is not included so the sum should be $ 46^3 \minus{} 1$  whose largest prime factor is $ 103$

Similar to problem 1, Centroamerian Olympiad 2009

http://www.mathlinks.ro/viewtopic.php?p=1648025#1648025