1) Given a sequence a1, a2, a3, ... of positive numbers such that the sum 1/a1 + 1/a2 + ... converges.  Let bn be the arithmetic mean (a1 + a2 + ... + an)/n.  Prove 1/b1 + 1/b2 + 1/b3 + ... converges.

2) Given a sequence a1, a2, a3, ... of positive numbers such that the sum a1 + a2 + ... converges.  Let bn be the arithmetic mean (a1 + a2 + ... + an)/n.  Prove b1 + b2 + b3 + ... diverges.

I'm also interested in what happens if you take a convergent sequence and look at other means, between 1 and -1, if they converge -- I suspect there is some amount of ambiguity in there, though.  The geometric mean version of this question might be interesting.

Well, the second one wasn't too bad:

Since the a sequence consists of all positive terms, it converges absolutely, and thus we don't have to worry about the mess we can get into with conditionally convergent series. So we can reorder the terms of bn: b1+b2+...=a1(1+1/2+1/3+1/4+...)+ (other positive stuff). Since a1 > 0, a1(1+1/2+1/3+1/4+...) is infinite, as the Harmonic series diverges. Then we're adding more positive stuff on, so it still diverges.

Yeah, I stumbled across the second one while trying to prove the first one.  I haven't made any substantial progress on the first, though.

Here's a hint on the first problem.  Spoiler: [hide] Note that bn :ge: (an/2 + ... + an) / n.  Now apply AM-HM to the right-hand side.[/hide]

There are slicker methods that give sharper upper bounds on the sum, but this method is good enough.

sorry if this is a stupid question, but how do you know you can rearrange terms like you did there simon to group all the a_1 terms together for instance? I thought in a divergent series, you couldn't rearrange terms or something. I'm rather fuzzy on that though...so maybe this is a stupid question. But I'll ask it anyway.

As ComplexZeta mentioned, if a series converges absolutely (which means the sum of the absolute values converges), then the series itself converges, and any rearrangement of the series converges (to the same sum).  That's a standard result in infinite series.

If you prefer, there is a way to present ComplexZeta's argument without rearrangement.  In the second problem, note that bn :ge: a1/n.  Because the harmonic series diverges to infinity, and because a1 is positive, the sum of the bn must also diverge to infinity.

Yeah. It's only conditionally convergent series that can cause trouble with rearrangement.

An idea for the first one :

Cauchy-Schwarz :  :Sigma: xi * :Sigma: 1/xi >= n
+ the fact that a1 + a2 + ... + an is increasing gives :

0 <= :Sigma: 1/bi <= 2  :Sigma: 1/ai

:Sigma: 1/bi is increasing, bounded hence it is convergent.

Sorry, I don't quite follow your argument.  What is your choice of xi?


What number is $1/3$ and a half of $100$ :read:

I think he means $x=\frac{1}{3}\times 100=\frac{1}{2}\times 100$. Impossible, of course, but maybe it's a trick question.

:lol: Ambiguous, but not a trick question...  Let's dissect it carefully:
[hide="word for word"]What number is $\frac{1}{3}$ and a half of $100$ ?
"Of" means $\times$ (multiplied by), for example, $1/2$ of $4$ equals $(1/2)\cdot4$.  Also, $2$ of $4$ ($2$ [groups] of $4$) means $2 \cdot 4 = 8$.  Now, we have:
What number is ($\frac{1}{3}$ and a half)  multiplied by $100$ ?
"And a half" means  "and (+) a half (1/2)", which means $+\frac{1}{2}$.  For example, "two and a half" means $2+\frac{1}{2}$.  This gives us:
[b]What number is $(\frac{1}{3}+\frac{1}{2})\cdot100$ ?[/b]
$250/3$.
But what if we did
What number is $1/3$ and a (half of 100) which gives us
$151/3$?
I guess our only clue [i]not[/i] to do that is the "a" before (half of 100).[/hide]

[quote="archimedes1"]You mean $(\frac{1}{3}+\frac{1}{2})\times100$?[/quote]
no. its
\[\frac{1}{3}\times 100+\frac{1}{2}\times\frac{1}{3}\times 100\]

So then it's
[hide]
$\frac{100}{3}\left(1\frac{1}{2}\right)=\boxed{50}$
[/hide]

[quote="@nn@"][quote="archimedes1"]You mean $(\frac{1}{3}+\frac{1}{2})\times100$?[/quote]
no. its
\[\frac{1}{3}\times 100+\frac{1}{2}\times\frac{1}{3}\times 100 \]
[/quote]
I'm pretty sure not one person on the earth would have guessed that from your original phrasing.

[quote="Temperal"][quote="@nn@"][quote="archimedes1"]You mean $ (\frac{1}{3}+\frac{1}{2})\times100$?[/quote]
no. its
\[ \frac{1}{3}\times 100+\frac{1}{2}\times\frac{1}{3}\times 100 \]
[/quote]
I'm pretty sure not one person on the earth would have guessed that from your original phrasing.[/quote]
Sorry i wrote it wrong :blush:

[quote="Temperal"]I think he means $ x=\frac{1}{3}\times 100=\frac{1}{2}\times 100$. Impossible, of course, but maybe it's a trick question.[/quote]

i am not a ,,He" im a girl  :mad:

[quote="@nn@"][/quote][quote="Temperal"][quote="@nn@"][quote="archimedes1"]You mean $ (\frac{1}{3}+\frac{1}{2})\times100$?[/quote]
no. its
\[ \frac{1}{3}\times 100+\frac{1}{2}\times\frac{1}{3}\times 100 \]
[/quote]
I'm pretty sure not one person on the earth would have guessed that from your original phrasing.[/quote][quote="@nn@"]
Sorry i wrote it wrong :blush:[/quote]
That's all right. I don't understand where the difficulty of this problem lies. Is it in trying to decipher the words?

well yea . but one thing, I am a girl :!:

WRONG! I think [size=200]''HE''[/size] means x=\frac{1}{3}\times 100=\frac{1}{2}\times 100. Impossible, of course, but maybe it's a trick question.

CORECT! I think [size=200]''SHE''[/size] means x=\frac{1}{3}\times 100=\frac{1}{2}\times 100. Impossible, of course, but maybe it's a trick question.


The vertex of the parabola $ y \equal{} x^2 \minus{} 8x \plus{} c$ will be a point on the $ x$-axis if the value of $ c$ is:

$ \textbf{(A)}\ \minus{} 16 \qquad \textbf{(B)}\ \minus{} 4 \qquad \textbf{(C)}\ 4 \qquad \textbf{(D)}\ 8 \qquad \textbf{(E)}\ 16$

The vertex occurs when $ x\equal{}4$. If the corresponding value of $ y$ is $ 0$, then our vertex will be on the $ x$-axis; we must have $ 0\equal{}4^2\minus{}8\cdot4\plus{}c\implies c\equal{}\boxed{\textbf{(E)}\ 16}$.

[hide="Solution"]The parabola opens downward, so the vertex is the minimum.
$ y'\equal{}2x\minus{}8\equal{}0\implies x\equal{}4$.
$ y\equal{}\minus{}16\plus{}c$ when $ x\equal{}4$, so $ c\equal{}\boxed{\textbf{(E)}\ 16}$ to make $ y\equal{}0$.[/hide]

[quote="grn_trtle"][hide="Solution"]The parabola opens downward, so the vertex is the minimum.
$ y' \equal{} 2x \minus{} 8 \equal{} 0\implies x \equal{} 4$.
$ y \equal{} \minus{} 16 \plus{} c$ when $ x \equal{} 4$, so $ c \equal{} \boxed{\textbf{(E)}\ 16}$ to make $ y \equal{} 0$.[/hide][/quote]

Please do not post calculus based solutions in High School Basics.

Thanks!

Sorry, wasn't paying attention :D

[hide="Non-calculus solution"]
$ x\equal{}\minus{}\frac{b}{2a}\equal{}4$

$ \minus{}16\plus{}c\equal{}0\implies c\equal{}\boxed{\textbf{(E)}\ 16}$.
[/hide]


IMO Shortlist
matrix
IMO
combinatorics
Inequality
IMO 1998
Set systems

In a contest, there are $m$ candidates and $n$ judges, where $n\geq 3$ is an odd integer. Each candidate is evaluated by each judge as either pass or fail. Suppose that each pair of judges agrees on at most $k$ candidates. Prove that \[{\frac{k}{m}} \geq {\frac{n-1}{2n}}. \]

Apparently, I have the same proof as the one on Kalva..

We count the cases when two judges agree on the result of a certain contestant. Let this number be $N$. On the one hand, we have $N\le k\cdot \binom n2=k\cdot\frac{n(n-1)}2$. On the other hand, if we show that $m\cdot \left(\frac{n-1}2\right)^2\le N$, we're done.

Consider the whole thing a $0,1$-matrix having the judges as rows and the contestants as columns, and having $a_{ij}=0$ is judge $j$ fails contestant $i$ and $a_{ij}=1$ otherwise. It suffices to show now that for each of the $m$ columns there are at least $\left(\frac{n-1}2\right)^2$ pairs of equal numbers.

Assume on a column there are $a$ $0$s and $b$ $1$s with $a+b=n=2k+1$. In this case the number of matching pairs on this column is $\frac{a(a-1)}2+\frac{b(b-1)}2=\frac{a^2+b^2}2-\frac n2$, which, knowing that $a+b$ is constant, is minimal when $|a-b|$ is minimal (i.e. when $a,b$ are as close to each other as possible), and this happens when $\{a,b\}=\{k,k+1\}$. If we compute the number of matching pairs on this column in this particular case, we get precisely $k^2=\left(\frac{n-1}2\right)^2$, so this is the minimal value. That is, on every column the number of matching pairs is $\geq \left(\frac{n-1}2\right)^2$. Thus, $N\geq m\cdot \left(\frac{n-1}2\right)^2$, Q.E.D.

Here is my proof which is same as above ...

Consider the set $\mathcal{T} = \left \{ (j_p,j_q) ,c_k\right \}$, where two judges $j_p,j_q$ agree on the contestant $c_k$. So it follows that $|\mathcal{T}| \le k\binom{n}{2}$.

We will count the elements of $\mathcal{T}$ in another way. Suppose $a_k$ number of judges rated $c_k$ as ''pass'' and rest of the judges rated $c_k$ as ''fail''. So $|\mathcal{T}|= \sum_{k=1}^{m} \left ( \binom{a_k}{2} + \binom{n-a_k}{2}\right )$. Since $n$ is odd $ \binom{a_k}{2} + \binom{n-a_k}{2}  \ge \binom{\left ( \frac{n+1}{2} \right )}{2} + \binom{\left ( \frac{n-1}{2} \right )}{2} =  \frac{(n-1)^2}{4}  $. [hide="more generally"] let $a_i \in \mathbb{N}$  ,and $\sum_{i=1}^{p}a_i= xy+ z$ where $0\le z < x$ then $\sum_{i=1}^{p} \binom{a_i}{2} \ge z \binom{y+1}{2} + (x-z)\binom{y}{2} $ ;) [/hide]

So we have $k\binom{n}{2} \ge | \mathcal{T}| = \sum_{k=1}^{m} \left ( \binom{a_k}{2} + \binom{n-a_k}{2}\right ) \ge \sum_{k=1}^{m}\frac{(n-1)^2}{4} = \frac{m(n-1)^2}{4}$

This gives $k\binom{n}{2} \ge \frac{m(n-1)^2}{4} \iff {\frac{k}{m}}\geq{\frac{n-1}{2n}}  $. qed

Suppose a candidate had $x$ judges pass him and $n-x$ judges fail him. Then, there would be $\binom{x}{2} + \binom{n-x}{2}$ pairs of judges that agree. Summing across and taking the average, we see that
\[k \ge \frac{m}{\binom{n}{2}} (\binom{x}{2} + \binom{n-x}{2})\]
So it suffices to show that
\[\frac{1}{\binom{n}{2}} (\binom{x}{2} + \binom{n-x}{2}) \ge \frac{n-1}{2n}\]
This reduces down to
\[(n-2x)^2 \ge 1\]
which is true unless $n = 2x$, but we are given that $n$ is odd, so this cannot be the case. Hence, the inequality holds true.

The problem can be solved easily with incidence vectors: define $m$-component incidence vectors $v_{1},v_{2},\ldots,v_{n}$ where the $j$th component of $v_{i}$ is $1$ if judge $i$ awarded candidate $j$ a pass and $-1$ if not.

We have $v_{i}\cdot v_{i}=m$ for all $i$. Furthermore as any pair of judges agree on at most $k$ candidates, they disagree on at least $m-k$ candidates. Two judges agree on the $l^{\text{th}}$ candidate if the $l^{\text{th}}$ components of their incidence vectors are the same (both 1 or $-1$) and disagree if they are different (one is 1 and the other is $-1$). Thus for $i\neq j$: $v_{i}\cdot v_{j}\leq k-\left(m-k\right)=2k-m$.

Finally, consider $\sum_{i=1}^{n}v_{i}$: each of the $m$ components is the sum of $1$s and $-1$s and as $n$ is odd we must have that each component is odd so in particular not zero. Thus $\left(\sum_{i=1}^{n}v_{i}\right)^{2}\geq m$.

Hence,
\[
m\leq\left(\sum_{i=1}^{n}v_{i}\right)^{2}
=\sum_{i=1}^{n}v_{i}^{2}+2\sum_{1\leq i<j\leq n}v_{i}\cdot v_{j}
\]
\[
\leq\sum_{i=1}^{n}m+2\sum_{1\leq i<j\leq n}\left(2k-m\right)
=mn+n\left(n-1\right)\left(2k-m\right)
\]
\[
\Rightarrow 0\leq\left(n-1\right)\left[m+n\left(2k-m\right)\right]
=\left(n-1\right)\left[2kn-m\left(n-1\right)\right]
\]
\[
\Rightarrow m\left(n-1\right)\leq 2kn
\Rightarrow\frac{n-1}{2n}\leq\frac{k}{m}.
\]
Furthermore, we also get a bound for $n$ even, $n\geq4$: we have $\left(\sum_{i=1}^{n}v_{i}\right)^{2}\geq 0$ and by the same argument get the bound $\frac{k}{m}\geq\frac{n-2}{2\left(n-1\right)}$.

EDIT: Fakesolved it. Thanks AstrapiGnosis for pointing out.

[quote=rterte]Assume that candidate $i$ has $x_i$ passes and $y_i$ fails. Then $x_i+y_i=n$. The number of pairs of judges agree with this evaluation is $\binom {x_1}{2} +\binom {y_i}{2}$. We have \[ \begin{aligned}
2\left(\binom {x_1}{2} +\binom {y_i}{2}\right)&=x_i(x_i-1)+y_i(y_i-1)\\
&=x_i^2+y_i^2-x_i-y_i\geq\frac{1}{2}(x_i+y_i)^2-(x_i+y_i)\\
&\Rightarrow 4\left(\binom {x_1}{2} +\binom {y_i}{2}\right)\geq (n-1)^2\quad (1)
\end{aligned} \] On the other hand, due to the fact that there are $\binom{n}{2}$ pairs of judges, hence \[ k\binom{n}{2}\geq\sum_{i=1}^n\left(\binom {x_1}{2} +\binom {y_i}{2}\right) \] combine with $(1)$, we receive $4k\frac{n(n-1)}{2}\geq m(n-1)^2$. Hence $QED$[/quote]

Your bound in (1) is incorrect; $n^2-n$ is not greater than $(n-1)^2$. Your bounding only uses Cauchy-Schwarz; as it turns out this problem is very tricky and a stronger bound is required. The Cauchy bound is just ever so slightly too weak.

Define
$$
f(a,p_i)=
\begin{cases}
1, \textnormal{if the pair $p_i$ agrees} \\
0, \textnormal{otherwise}
\end{cases}
$$
We have
$$\sum_{i=1}^{n} \sum_{a=1}^{m} f(a,p_i) \leq k{n \choose 2}$$
Now using $$\sum_{i=1}^{n} \sum_{a=1}^{m} f(a,p_i)=\sum_{a=1}^{m} \sum_{i=1}^{n}  f(a,p_i)$$
Suposing that $x$ judges pass and $n-x$ fail shuch that $x$ and $n-x$ are very closely, its well known ${x \choose 2} + {n-x \choose 2}$ is the fewest sum. Ergo,
$$\sum_{a=1}^{m} \sum_{i=1}^{n}  f(a,p_i)\geq m \left({x \choose 2} + {n-x \choose 2}\right).$$
And now we have to proof that
$$m \left({x \choose 2} + {n-x \choose 2}\right)\geq m{n \choose 2}\left(\dfrac{n-1}{2n}\right)$$
But this computation give us $$(n-2x)^2\geq 1$$ and the equality give us $n$ is an odd number. q.e.d.

Recently found next related question : If $m$ is an odd integer (instead of $n$) and each pair of judges agrees on at most $k$ candidates, then $\frac{k}{m}\geq\frac{n-2}{2n}$.

$\textbf{Solution to original problem :}$

Consider $a_i$- number of judges which evaluated $i$-th candidate as pass (and $b_i$ same for fail). Then $a_i + b_i = n, \forall i$. So let $c_i$ be number of pairs of judges wich agrees on $I$-th candidate. So $c_i = \frac{a_i(a_i-1)}{2} + \frac{b_i(b_i-1)}{2}$. On other hand if $k<\frac{m(n-1)}{2n}$, then $\sum_i c_i < \frac{m(n-1)}{2n}\frac{n(n-1)}{2} = \frac{m(n-1)^2}{4}$. Easy to check that if $n$ is an odd integer, then $\min_{x\in\mathbb{N}}\left(\frac{x(x-1)}{2} + \frac{(n-x)(n-x-1)}{2}\right) = \frac{(n+1)^2}{8} + \frac{(n-1)^2}{8} - n/2$. So $m\left(\frac{(n+1)^2}{8} + \frac{(n-1)^2}{8} - n/2\right)\leq\sum_i\left(\frac{a_i(a_i-1)}{2} + \frac{b_i(b_i-1)}{2}\right) = \sum_i c_i <  \frac{m(n-1)^2}{4}$, but $\frac{(n+1)^2}{8} + \frac{(n-1)^2}{8} - n/2 = \frac{(n-1)^2}{4}$ contradiction. And so $k\geq\frac{m(n-1)}{2n}$. $\Box$

$\textbf{Algebraical proof :}$

Consider algebra $\mathcal{A}$ of functions $\{1, 2,\ldots, m\}\to\mathbb{Z}$. Then decisions of $n$ judges can be seen as elements $a_j\in\mathcal{A}$, where $a_j\in \{-1, 1\}$. Consider morphism $\pi:\mathcal{A}\to\mathbb{Z}$, where $\pi(f) := \sum_i f(i)$. So one have that $\pi\left(\left(\sum_i a_i\right)^2\right) \leq mn + n(n-1)(2k-m)$. But $n$ is an odd integer, so $m\leq\pi\left(\left(\sum_i a_i\right)^2\right)$ and $m\leq mn + n(n-1)(2k-m)$. So $k\geq\frac{m(n-1)}{2n}$. $\Box$

I solved this problem as characterized in the Intermediate C&P textbook where there are $a$ contestants and $b$ judges (just to be clear about my usage of variables).

$\bullet$ Let $N$ be the number of times that any two judges agree on the rating of a contestant.
$\bullet$ Lets imagine that a $b\times a$ matrix represents the contestants and their respective ratings. Any entry $(i,j)$ in this matrix, (where $1\leq i\leq b$, and $1\leq j\leq a$) is 1 if the $j^{th}$ contestant has passed and is 0 if this contestant has failed according to the $i^{th}$ judge. In this scenario let, $i_1,i_2,i_3,\ldots i_a$, represent the number of 1's in columns 1 through $a$ respectively.
$\bullet$ Let $\beta = \frac{b-1}{2}.$
$\bullet$ Let $f_k(x) = i_k(b-i_k).$

[b]Lemma 1:[/b] $N = \sum_{k=1}^{a}\binom{i_k}{2} +\sum_{k=1}^{a}\binom{b-i_k}{2}$.
[b]Proof: [/b] The above formula holds, because, if there are $i_k$ 1's and $b-i_k$ in column $k$, any pairs of 0's or (non-inclusive) 1's correspond to a pair of judges that agree on the rating of a particular contestant. Summing over all $a$ columns yield the above formula. $\Box$

[b]Lemma 2:[/b] $N\geq a\beta^2$.
[b]Proof: [/b]  We start by maximizing $f_k(x)$. Since we can express $f_k(x)$ as a quadratic in terms of $i_k$ whose vertex form is $i_k(b-i_k)$, its roots are 0 and $b$, meaning that the optimal value of this function occurs when $i_k = b/2$. Making this substitution yields

\begin{align*}
f_k(x)&= \left \lfloor \left (\frac{b}{2}\right )^2 \right \rfloor,\\&= \left \lfloor \frac{(2\beta+1)^2}{4}\right \rfloor,\\&=\left \lfloor \frac{4\beta^2 +4\beta +1}{4}\right \rfloor,\\&= \beta^2+\beta.\end{align*}

Note that we take the floor function, as $(b/2)^2$ is not integral. Consequently, we have the inequality

$$\beta^2+\beta\geq i_k(b-i_k).$$

If we move $i_k(b-i_k)$ to the RHS, and add $\beta^2$ to both sides, this inequality becomes

$$i_k(i_k-b)+2\beta^2+\beta\geq \beta^2, or $$

$$\binom{i_k}{2}+\binom{b-i_k}{2}\geq \beta^2,$$

which the reader can verify through some simple algebra. Thus, since $N$ is the sum of $a$ pairs of binomial coefficients of the form $\binom{i_k}{2}+\binom{b-i_k}{2}$, we can conclude in saying that $N\geq a\beta^2$. $\Box$

From the definition of $k$, we know that $N\leq k\binom{b}{2}$, as the ratings of any pair of judges can coincide at a maximum of $k$ contestants. Sunstituting $N = ac\left (\frac{b-1}{2}\right )^2$, for rational $c$ greater than or equal to 1, this inequality becomes

\begin{align*}
ac\left (\frac{b-1}{2}\right )^2 &\leq \frac{kb(b-1)}{2},\\\frac{ac(b-1)^2}{4}&\leq \frac{kb(b-1)}{2},\\2ac(b-1)^2&\leq 4kb(b-1),\\\frac{2ac(b-1)^2}{4b(b-1)}&\leq k,\\\frac{ac(b-1)}{2b}&\leq k,\\k&\geq c\cdot \frac{a(b-1)}{2b},\\\frac{k}{a}&\geq c\left (\frac{b-1}{2b}\right),\\\frac{k}{a}&\geq \frac{b-1}{2b},\end{align*}

as desired. $\blacksquare$

Unless I'm insanely high, the straightforward solution with LoE+Global Jensen's works [i]and[/i] makes the equality case explicit.

Nice problem. Here's my solution (Inspired from [url=http://artofproblemsolving.com/community/c5h404364p11424078]USAMO 2011 P6[/url]): We reframe the problem in set notation as follows:-
[quote=Restated problem]Let $X=\{a_1,a_2, \dots ,a_m\}$ be a given set. Suppose we make subsets $A_1,A_2, \dots ,A_n$ of $X$ such that they satisfy $$|A_i \cap A_j|+|A^c_i+A^c_j| \leq k \text{   } \forall 1 \leq i<j \leq n$$
If $n$ is an odd integer $(n \neq 1)$, then show that the following inequality holds true- $$\frac{k}{m} \geq \frac{n-1}{2n}$$

NOTE: $A^c$ represents the complement of the set $A$.[/quote]
[b]PROOF:[/b] Consider a $n \times m$ chessboard, with the $n$ rows representing $A_1,A_2, \dots ,A_n$ and the $m$ columns representing the $m$ elements of $X$. On each square of the board, we write either zero or one, according to the following criterion - $1$ is written on the intersection of the $i^{th}$ row and the $j^{th}$ column if and only if $a_j$ is present in $A_i$; otherwise $0$ is written. Let $d_i$ denote the number of times $1$ appears in the $i^{th}$ row, i.e. the number of sets in which $a_i$ is present. Then we have \begin{align*} \sum_{1 \leq i<j \leq n} |A_i \cap A_j|+|A^c_i+A^c_j| &=\sum_{i=1}^m \left(\binom{d_i}{2}+\binom{n-d_i}{2} \right) \\ &=\sum_{i=1}^m \left(\frac{d_i^2-d_i}{2}+\frac{(n-d_i)^2-(n-d_i)}{2} \right) \\ &=\sum_{i=1}^m \left(\frac{n(n-1)}{2}+(d_i^2-n \cdot d_i) \right) \\ &=\frac{m \cdot n(n-1)}{2}-\sum_{i=1}^m d_i(n-d_i) \\ \end{align*}
And using the condition given in the problem, we get that $$m \cdot \binom{n}{2}-\sum_{i=1}^m d_i(n-d_i) \leq k \cdot \binom{n}{2} \Rightarrow \frac{k}{m} \geq 1-\frac{\sum_{i=1}^m d_i(n-d_i)}{\binom{n}{2}} \text{      }  (*)$$
Now, note that $$\sum_{i=1}^m d_i(n-d_i)=\sum_{i=1}^m \frac{((n-d_i)+d_i)^2-((n-d_i)-d_i)^2}{4}=\sum_{i=1}^m \frac{n^2-(n-2d_i)^2}{4}$$
This means that this expression takes its maximum value when $(n-2d_i)^2$ is minimum. As $n$ is odd, the minimum value of $(n-d_i)^2$ can not be less than $1$. This gives that $$\sum_{i=1}^m d_i(n-d_i) \leq \frac{n^2-1}{4} \Rightarrow \sum_{i=1}^m d_i(n-d_i) \leq \frac{n-1}{2} \times \left(n-\frac{n-1}{2} \right)$$ $$\Rightarrow \sum_{i=1}^m d_i(n-d_i) \leq \binom{n}{2}-\left(\frac{n-1}{2} \right)^2 \Rightarrow 1-\frac{\sum_{i=1}^m d_i(n-d_i)}{\binom{n}{2}} \geq \frac{2}{n(n-1)} \times \left(\frac{n-1}{2} \right)^2$$
Combining this inequality with $(*)$, we get our final result as shown below $$\frac{k}{m} \geq 1-\frac{\sum_{i=1}^m d_i(n-d_i)}{\binom{n}{2}} \geq \frac{n-1}{2n} \text{   } \blacksquare$$

[quote=twinbrian]What exactly is "smoothing"?[/quote]

Smoothing is a technique used to minimize or maximize a function of some variables by pushing them closer together. In particular, we prove that if we push the variables closer together, then the value of the function increases (or decreases). This proves that the maximum (or minimum) is achieved when we have made the variables as close together as possible. Note that we can only minimize if the function is convex, and maximize if the function is concave. Think about a convex graph with some points on it. To minimize the function, we can intuitively see that we want to ``push'' together all the variables together at the critical point to minimize them. We can similarly see for maximizing.

Can someone point out what's wrong with this solution. I somehow got a stronger bound and didn't use $b$ is odd?

Assume FTSOC that
$$k<\frac{m(n-1)}{2n}$$
Then, if $A$ is the total number of agreements, we must have
$$A\le k\binom{b}{2}<\frac{a(b-1)^2}{4}$$
Now, the expected number of agreements between any two judges is $\tfrac{a}{2}$. Thus, the expected value of $A$ is just
$$\frac{a}{2}\binom{b}{2}$$
Hence, it follows that there exists a scenario where
$$A\ge\frac{a}{2}\binom{b}{2}=\frac{ab(b-1)}{4}$$
But this contradicts
$$A<\frac{a(b-1)^2}{4}$$

Let $n = 2n' +1$.Count the number of pairs of scores that agree. There are $\frac{n(n-1)}{2} k$ such pairs maximum. On the other hand for every student, we have at least $2m \frac{n'(n'-1)}{2}$ pairs of scores that agree.

Can someone confirm that this solution is right?

The probability that a pair of judges agree on one candidate is $\frac{1}{2}$. By Linearity of Expectation, the expected number of contestants that a pair of judges agree on is $\frac{a}{2}$. This means that $k \ge \frac{a}{2}$, which means that $\frac{k}{a} \ge \frac{b-1}{2b}$.

Sorry for the bump, but @above is incorrect (seems way too simple to be true anyway).
If we take $(m,n)=(6,3)$, then the following construction gives $k=2 < \frac{m}{2}=3$.

PPPFFF
PPFPPP
FFPFPP

Consider some random candidate; if they receive $a$ passing votes and $b$ failing votes, we have $a+b=n$ and exactly
\[ \binom{a}{2} + \binom{b}{2} \ge \binom{\tfrac{n-1}{2}}{2} + \binom{\tfrac{n+1}{2}}{2}= \frac12 (n-1)^2\]
pairs of judges agree on that candidate where the inequality is by Karamata (just wlog $a>b$).

It follows that
\[ \mathbb{E}[\text{number of candidates a pair of judges agree on}] = m \cdot \frac12 (n-1)^2 \cdot \frac{1}{\binom{n}{2}} = m \cdot \frac{n-1}{2n}. \]
By pigeonhole there is a pair of judges that agree on at least as many candidates as the expected number, so $k \ge m \cdot \frac{n-1}{2n}$, and we win. $\blacksquare$

Crispy double counting, posted before but anyways...
 We define a $n\times m$ incidence matrix where each row represents a judge and each column a candidate. We entry a $1$ or $0$ based on pass or fail.  We count the number of agreements among two judges. This is the same as counting number of pairs of $1$s  and $0$s that are same. Let this set be $A.$
Counting by columns, we have say $a$ $1$s and $b$ $0$s in a given column where $a+b = n.$ Furthermore, by using Karamatas majorization inequality for [hide=bounding sum of x choose 2,] Let $a_1, a_2, \ldots, a_n$ be positive integers and let $\sum a_i = nk + r$ where $k$ and $r$ are integers and $0\leq r < n.$ Then, \begin{align*} \sum_{i=1}^n \binom{a_i}{2} \geq r\binom{k+1}{2} + (n-r) \binom{k}{2}  \end{align*} [/hide] we obtain
\begin{align*}   |A| = m\left(\binom{a}{2} + \binom{b}{2}\right) &\geq    m\left(\binom{\frac{n+1}{2}}{2} + \binom{\frac{n-1}{2}}{2}\right) \\ & =\frac{m(n-1)^2}{4}\end{align*}
Counting by rows, we know that each pair of judges agree on at most $k$ candidates. So, you pick any two rows, and there will be at most $k$ instances where both rows have the same entry for a candidate. Therefore, we get \begin{align*}    |A| \leq k \binom{n}{2} \end{align*}
The black magic is done and we obtain \begin{align*}    \frac{m(n-1)^2}{4} \leq \frac{k(n^2-n)}{2} \implies \frac{k}{m} \geq \frac{n-1}{2n}. \blacksquare \end{align*}

[b]Solution.[/b]
We double count triples of the form $(\text{Judge}, \text{Judge}, \text{Contestant})$ such that the two judges agrees on the contestant. For every two judges, there are at most $k$ contestants, so there are at most $\binom{n}{2}k$ triples. For every contestant $i$, assume $x$ judges gives a pass to contestant $i$. We want to find the max number of triples of $(\text{Judge}, \text{Judge}, i)$. There are
$$\binom{x}{2}+\binom{n-x}{2}.$$
By Calculus, we can find that the max occurs when $x = \frac{n-1}{2}$ (or $x = \frac{n+1}{2}$). Doing it over all $i=1,2,..,m$, we have
$$m(\binom{\frac{n+1}{2}}{2}+\binom{\frac{n-1}{2}}{2}) \leq k\binom{n}{2}$$
Simplyfying it, this is equivalent to
$$\frac{k}{m} \ge \frac{n-1}{2n}$$

[quote=pad]Consider the total number of agreements by pairs of judges on a candidate, over all possible pairs of judges and over all possible candidates. Fix a candidate $d$. If $x_d$ judges approve the candidate, and $n-x_d$ disapprove, we have $\tbinom{x_d}{2}+\tbinom{n-x_d}{2}$ agreements. Now fix a pair of judges. We can have at most $k$ agreements, whence we have at most $k\tbinom{n}{2}$ agreements.  Therefore,
\[ \sum_{d=1}^m \binom{x_d}{2}+\binom{n-x_d}{2} \le k\binom{n}{2}. \]
We will now apply smoothing. Let $x<y$ be positive integers and $0<\epsilon \ll 1$. Since
\[ \binom{x}{2}+\binom{y}{2} = \frac{x^2+y^2}{2}-\frac{x+y}{2},\]
then
\[ \binom{x+\epsilon}{2}+\binom{y-\epsilon}{2}=\frac{x^2+y^2+2\epsilon(x-y)}{2}-\frac{x+y}{2} \le \frac{x^2+y^2}{2}-\frac{x+y}{2} =\binom{x}{2}+\binom{y}{2}.\]
Note that we have ignored the order two $\epsilon$ terms since we can take $\epsilon$ to be sufficiently small. Then, since $n$ is odd, by smoothing we have
\[ \binom{x_d}{2} + \binom{n-x_d}{2} \ge \binom{\frac{n-1}{2}}{2}+\binom{\frac{n+1}{2}}{2}.\]
Summing,
\[ m\left(\binom{\frac{n-1}{2}}{2}+\binom{\frac{n+1}{2}}{2}\right) \le k\binom{n}{2}, \]
so
\[ \frac{k}{m} \ge \frac{\binom{\frac{n-1}{2}}{2}+\binom{\frac{n+1}{2}}{2}}{\binom{n}{2}} = \frac{(n-1)(n-3)+(n+1)(n-1)}{4n(n-1)}=\frac{n-1}{2n}.\][/quote]

Can somebody elaborate on this so-called "smoothing" technique? What does the $\ll$ symbol mean for the $\epsilon,$ how can you assume that the $\epsilon$ is infinitesimally small?

EDIT: Also, just a remark about why @Temporal's sol is wrong. He basically computed the expected value of a configuration, so his proof suffices to show there EXISTS a configuration that satisfies the problem, but the problem statement is even stronger, it is claimed that the statement is true for all possible configuration(i.e. all possible decisions the judge smakes).

$\ll$ means "is a lot less than", it means that $\epsilon$ is close to $0$.

The number of pairs of judges is $\binom{n}{2}$ and each of the pair as AT MAX. $k$ agreements.
Hence, the upper bound is $k\binom{n}{2}$.
Now let's fix a participant and say he obtained $a$ passes and $b$ fails with $a+b=n$.
The then number of agreements is $$\binom{a}{2}+\binom{b}{2}=\frac{a^{2}+b^{2}-(a+b)}{2}=\frac{(a+b)^{2}+(a-b)^{2}-2(a+b)}{4}
=\frac{n^{2}-2n+(a-b)^{2}}{4}$$.
But, now $|a-b| \geq 1$ since $a+b=n$ is odd.
It follows that the number of agreements for any fixed candidate is AT MIN $\frac{(n-1)^{2}}{4}$.
Multiplying it by $m$ for that many candidates provides us with the lower bounds i.e. $m\cdot \frac{(n-1)^{2}}{4}$.
Putting it together and using that lower bounds is lower than the upper bound we have;
  $m\cdot \frac{(n-1)^{2}}{4} \leq k\binom{n}{2}$.
easy algebra yields way to...
$${\frac{k}{m}} \geq {\frac{n-1}{2n}}$$
                                                                                :D $\blacksquare$

Let us count $S$, the number of ordered pairs $((J_x,J_y),C_z)$ of an unordered pair of judges $J_x$ and $J_y$, who agreed on the candidates $C_z$. Clearly, since each pair of judges agree on at most $k$ candidates, we have \[S\le k\binom{n}{2}.\] Now, suppose candidate $C_z$ had $c_z$ judges give him a pass, then the number of judges that agree on $C_z$ would be $\tbinom{c_z}{2}+\tbinom{n-c_z}{2}.$ Since $f(x)=\tbinom{x}{2}$ is a convex function, $\tbinom{c_z}{2}+\tbinom{n-c_z}{2}\ge \tbinom{(n+1)/2}{2}+\tbinom{(n-1)/2}{2}=\tfrac{(n-1)^2}{4}$ so \[k\cdot \binom{n}{2}\ge S\ge m\cdot \frac{(n-1)^2}{4}\] which implies the result.

Double count pairs $(\{a, b\}, i)$, where judges $a, b$ agree on contestant $i$. The number of pairs is clearly upper bounded by $ k{n \choose 2}$. On the other hand, for any contestant, suppose $i$ judges rate him "pass". Then, the number of such pairs for that contestant is $${i \choose 2} + {n-i \choose 2} \geq \frac{(n-1)^2}4$$ for Jensen reasons. Thus $$k{n \choose 2} \geq \frac{m(n-1)^2}4,$$ which yields the result.

No way I just solved a C5 at 2am\\

but then again I've done otis global

Let $n=2s+1.$\\

Double count the number of triples $(J_1,J_2,C)$ such that judges $J_1$ and $J_2$ agree on candidate $C$. Let this number be $N$.\\

From the  condition that each pair of judges agree on at most $k$ candidates, $$N\leq k{{2s+1}\choose 2}.$$

We can also sum over the contestants, which gives $$N=\sum_{i=1}^m {{c_i\choose 2}+{2s+1-c_i\choose 2}}.$$ By Karamata, ${c_i\choose 2}+{2s+1-c_i\choose 2}$ is minimized when $c_i$ and $2s+1-c_i$ are as close as possible, which happens when $c_i=s$ or $s+1$. Hence, $$N=\sum_{i=1}^m {{c_i\choose 2}+{2s+1-c_i\choose 2}}\geq m({s\choose 2}+{s+1\choose 2}).$$

Therefore, we have $$m({s\choose 2}+{s+1\choose 2})\leq k{{2s+1}\choose 2}.$$ Finally, this rearranges to $$\frac{k}{m}\geq \frac{{s\choose 2}+{s+1\choose 2}}{{2s+1\choose 2}}=\frac{s}{2s+1}=\frac{n-1}{2n},$$ as desired.

Let $x=\frac{n-1}{2}$. Then we can double count the number of total agreements between any two judges:
\[\binom{n}{2}\cdot k\ge\text{Number of total agreements}\ge m\cdot\left(\binom{x}{2}+\binom{x+1}{2}\right).\]
Simplifying both sides,
\[nxk\ge mx^2.\]
Rearranging gives
\[\frac{k}{m}=\frac{x}{n}=\frac{n-1}{2n}.\]
QED.

We proceed by finding a lower and upper bound for the total number of agreements.

Note that since any judge can agree with any other judge on at most $k$ candidates, there is a maximum of $$\binom{n}{2}k$$ total agreements.

Now, we find a lower bound for the total number for the total number of agreements. For an arbitrary candidate, let $x$ judges pass the candidate and $n-x$ judges fail the candidate. Thus, there are $$\binom{x}{2} + \binom{n-x}{2}$$ agreements for this candidate. It is well known that this is minimized when $x = \lfloor \frac{n}{2} \rfloor$ or $x=\lceil \frac{n}{2} \rceil$ (if $n$ is even, these are the same). Thus, since $n$ is odd, the minimum number of total agreements is $$m \left( \binom{\lfloor \frac{n}{2} \rfloor}{2} + \binom{\lceil \frac{n}{2} \rceil}{2} \right) = m \left( \binom{\frac{n-1}{2}}{2} + \binom{\frac{n+1}{2}}{2} \right).$$ Since this expression is the minimum, while $\binom{n}{2}k$ is the maximum, we have $$\binom{n}{2}k \geq m \left( \binom{\frac{n-1}{2}}{2} + \binom{\frac{n+1}{2}}{2} \right).$$ This simplifies to $$\frac{k}{m} \geq \frac{\frac{(n-1)(n-3)}{4} + \frac{(n+1)(n-1)}{4}}{n(n-1)} = \frac{(n-1)^2}{2n(n-1)} = \frac{n-1}{2n},$$
as desired. $\square$

We can just assume that $k$ is the maximum number of
coinciding votes among any two judges. It remains to bound $k$.

Let $b = 2c + 1$.

For any one contestant, if $n$ judge rate a ``pass'' and $k - n$ rate
a ``fail'', then there are in total
\[
    \binom{n}{2} + \binom{b-n}{2} \ge \binom{c}{2} + \binom{c+1}{2}
\]
coinciding votes. Thus, over all $a$ contestants, there are at
least $a\left(\binom{c}{2} + \binom{c+1}{2}\right)$ coinciding votes.

Over $\binom{2c+1}{2}$ pairs of judges, by pigeonhole, it follows that
\[
    k \ge \frac{a}{\binom{2c+1}{2}}\left(\binom{c}{2} + \binom{c+1}{2}\right)
\]

Thus, the result follows since
\[
    \frac{1}{\binom{2c+1}{2}} \left(\binom{c}{2} + \binom{c+1}{2}\right) = \frac{2c}{2(2c+1)}
\]

Solved on [b]OTIS Excerpts[/b] where m and n are a and b.
This is a standard double counting problem. Counting by judges, we see that $N\le \dbinom{b}{2}k$, and letting b=2k+1 we count by contestant, from which it is clear by smoothing (essentially the minimum for sum of a_i choose 2 is when all a_i are close as possible together, which is a well known smoothing identity, can someone confirm that I can state this in contest though, although the two items are easy algebra and we sketch out induction for in general) that at MINIMUM each makes $\dbinom{k}{2}+\dbinom{k+1}{2}=k^2$ judges agree, hence $N\ge a(\frac{b-1}{2})^2.$ Transitive property and simplifying fully yields the desired result. $\blacksquare$

This is a nice problem!

To get an inequality, we consider the Maximum and Minimum of the # of pairs of judges that agree on certain participants, summed over once for each participant they cover.
Maximum: k*(n choose 2), this is where each pair of judges gets the maximum number of participants they are allowed to agree on.
Minimum: If a(i) is the number of pairs of judges which agree on the i-th participant, then this is (a(i) choose 2) + (n-a(i) choose 2) summed over all i. To minimize, we make a(i) and n-a(i) as close as possible, resulting in a(i) = (n-1)/2. Then this sum becomes m(n-1)^2/4.

Write Maximum ≥ minimum, you get the desired inequality after some trivial manipulations.

[hide=sol]
Let $b = 2k.$ Note that for each contestant, the $2k$ judges can give $n$ pass's and $2k-n$ fails. The minimum pairs that overlap occurs when $n = k.$ So, we have for each contestant, there are at least $(k)(k-1)$ pairs that give the same ratings. Since there are $a$ contestants, we have $$\frac{k}{a}\geq\frac{k(k-1)}{k(2k-1)} = \frac{k-1}{2k-1}.$$ Since, $\frac{2k-1}{4k}\geq\frac{k-1}{2k-1},$ the result follows. For $b = 2k+1,$ we use the same approach and get $$\frac{k}{a}\geq\frac{k(k-1)+(k+1)(k)}{(2k+1)(2k)} = \frac{k}{2k+1}.$$ In conclusion, $$\frac{k}{a}\geq\frac{b-1}{2b},$$ as desired.
[/hide]

Let $m=a, n=b$
Let ${j_n, j_m, c_q}$ be stuff
Make $q$ constant
Let a 1 be pass and a 2 be fail
The number of commons is (# of 1s choose 2)+(# of 2s choose 2)
Let $z$ be # of 1s and $y$ be # of 2s
# commons is $\frac{z^2+y^2-z-y}{2}$
to minimize this, note that it equals $\frac{(z-0.5)^2+(y-0.5)^2-0.5}{2}$ and $z+y=b$, so the minimum value is when $z$ and $y$ are closer together so let $z=\frac{b-1}{2}$ and $y=\frac{b+1}{2}$. Then this becomes $\frac{b^2}{4}-\frac{b}{2}+0.25$, but then divide by ${b \choose 2}$ for each pair to get $\frac{b-1}{2b}$ so $k \ge a*\frac{b-1}{2b}$ and $\frac{k}{a} \ge \frac{b-1}{2b}$


Euler
LaTeX
number theory unsolved
number theory

Let m belong to N, a belong to Z. gcd(a,m) =1. S is the set (Z/mZ)x
Prove that the map x->ax is a bijection from S to itself.
deduce that PI(s belongs to S^S) is congruent to PI (s belongs to S) mod m  [Note: s belongs to S is a subscript to PI where PI
is the multiplicative notation ie capital pi)
deduce P congruent to a^ phi(m) P ?
Sorry about the typing...have to learn Latex soon.
Thanks in advance.

NOTE: if $ b\in\{0,1,2,...,m-1\}$: $ \overline{km+b}=\overline{b}$

let $ S=\{\overline{y}\in\mathbb{Z}/m\mathbb{Z}: \ gcd(y,m)=1\}$
$ f: S\to S$ such that $ f(\overline{x})=\overline{ax}$
$ f(\overline{x})=f(\overline{y})$ gives $ \overline{a(x-y)}=\overline{0}$ gives $ m|a(x-y)$ then $ \overline{x}=\overline{y}$
$ \forall \overline{x}\in S: \ f(\overline{a^{-1}x})=\overline{x}$
then $ f$ is bijectiv.

so $ \prod_{\overline{x}\in S}\overline{x}=\prod_{\overline{x}\in S}f(\overline{x})=\overline{a^{|S|}}\prod_{\overline{x}\in S}\overline{x}$
then $ \overline{a^{|S|}}=\overline{1}$ ( $ a^{|S|}\equiv 1(mod\ m)$ )where $ |S|=\varphi(m)$


algebra
polynomial
complex analysis
complex analysis unsolved

p(z) is a polynomial of degree n with complex coefficients. All its roots lie on the unit circle. Show that all roots of            2zp'(z) - np(z) also lie on the unit circle.


In $\triangle ABC$, $\angle C = 90^\circ, AC = 6$ and $BC = 8$. Points $D$ and $E$ are on $\overline{AB}$ and $\overline{BC}$, respectively, and $\angle BED = 90^\circ$. If $DE = 4$, then $BD =$

[asy]
size(100); pathpen = linewidth(0.7); pointpen = black+linewidth(3);
pair A = (0,0), C = (6,0), B = (6,8), D = (2*A+B)/3, E = (2*C+B)/3; D(D("A",A,SW)--D("B",B,NW)--D("C",C,SE)--cycle); D(D("D",D,NW)--D("E",E,plain.E)); D(rightanglemark(D,E,B,16)); D(rightanglemark(A,C,B,16));[/asy]

$\mathbf{(A)}\;5\qquad
\mathbf{(B)}\;\frac{16}{3}\qquad
\mathbf{(C)}\; \frac{20}{3}\qquad
\mathbf{(D)}\; \frac{15}{2}\qquad
\mathbf{(E)}\; 8$

[hide="Answer"]We have a 6-8-10 right triangle, and $DE=4$, so by similar triangles, we have $BD=\frac{20}{3}\Rightarrow \boxed{C}$.[/hide]


$ PQRS$ is a square inside another square $ ABCD$ see the diagram below , prove that $ S_1 \plus{} S_3 \equal{} S_2 \plus{} S_4$
$ S_i$ means area

 [geogebra]aeaf06cffa8f1b9956740ed37f4eaf6f86116c03[/geogebra]

[hide="My Attempt  :maybe: "] [geogebra]811f92a3c2d7c049522c678b3320468c401947a1[/geogebra]

Since a diagonal of a rectangle splits the rectangle into triangles of equal area, we only need to prove $ A_1\equal{}A_2\equal{}A_3\equal{}A_4$. These are trapezoids, so if we show that $ AB\plus{}CD$ and all other similar lengths are equal, then we have proved the question. But by congruent right triangles, in the figure to the right, $ x\equal{}y$, so we have $ AB\plus{}CD\plus{}x\equal{}s$ where $ s$ is the side length of the square. This holds for all other similar lengths as well, so we have $ A_1\equal{}A_2\equal{}A_3\equal{}A_4$ and the problem is proved. [/hide]

Very nice problem. But let's generalize: Instead of being squares, $ ABCD$ and $ PQRS$ should be just two directly similar rectangles.


complex analysis
complex analysis unsolved

suppose that $ {a_n}$ is a sequence of complex nos in the unit disk. What can you say abt the radius of convergence of the series $ \sum_{n \equal{} 0}^{\infty} a_nz^n$ if $ |a_n|\rightarrow 1$. what can you say abt the radius of convergence if the set $ {a_n}$ is dense in the unit disk?

The radius of convergence is the reciprocal of $ \limsup_{n\to\infty}|a_n|^{1/n}$, which is $ 1$ in either case.


conics
ellipse
analytic geometry
algebra
system of equations
advanced fields
advanced fields unsolved

Let $C_N = \left \{ (x_n,y_n) \right \}_{n \in \{1,2,...,N\}}$ be a set of $N$ pairs of planar nonnegatives coordonates. Also, we
consider the general equation of an ellipse centered in orgin of the plane: $\left( \frac{x}{a} \right)^2 + \left( \frac{y}{b} \right)^2 =1$, where $a>0,b>0$ are the semiaxes of the ellipse.
[b]a)[/b] Determine an ellipse which is closest to all points in plane defined by coordonates $C_n$ in sense of minimization of
global square error $V(\theta); {\theta}^T=[a$  $b]$. (by deffinition: $V(\theta)=\sum_{n=1}^{N}{\epsilon}^2[n,\theta]$),where $\epsilon[n,\theta]$ is
the Euclidian distance between the point $(x_n,y_n)$ and a point situated on ellipse,collinear with $(x_n,y_n)$ and with origin;
[b]b)[/b]Determine the system of equations verified by semi-axes of the ellipse and prove that these are solutions of the equation:
$\sum_{n=1}^{N}\frac{{x_n}^2 + {y_n}^2}{u{x_n}^2 + v{y_n}^2} = \sum_{n=1}^{N}\frac{{x_n}^2 + {y_n}^2}{\sqrt{u{x_n}^2 + v{y_n}^2}}$,where $u=\frac{1}{a^2},v=\frac{1}{b^2}$ are two inversable transformations in the first cadran of the plane.


I think it is in a nice form. You can write it also as
\begin{eqnarray*}\sum_{i=1}^{b}(L_{i}-1)n^{b-i}&=&\sum_{i=1}^{b}L_{i}n^{b-i}-\sum_{i=1}^{b}n^{b-i}=\sum_{i=1}^{b}L_{i}n^{b-i}+\frac{n^{b}-1}{n-1}. \end{eqnarray*}

can we get n usin the bzz and Lzzz. in other word how to make n the subject of the formula.
 is it possible ?


OK, I really didn't want to start a new topic just to ask this question but I couldn't find anywhere else to ask and I'm really stumped. I was filling out an application for a scholarship. They asked for my "ACT Composite Score." I took the new ACT (with the essay) and it basically gives you TWO composite scores:
Essay Included: 34
Essay Not Included: 35

Which one should I put on the application? Does it even matter? Note that the entire scholarship is based off of ACT scores, SAT scores, GPA, and class rank.

OK, I'm being stupid, aren't I? There are not going to be twenty other applicants for this scholarship that have 35s and 36s on their ACTs.

And for those who want to know what the scholarship is, don't worry about it. You can't apply, it's one of those "dependent of employee" scholarships. You should all probably check with your parents' places of employment for scholarship opps like this one, though.

If it doesn't specify, why not put 35? Chances are it's an old app that is just being reused and thus the essay was not included.


calculus
derivative
calculus computations

In the following 2 questions, find all the critical points and classify each one as a local maximum, local minimum, or saddle point.
(a) $ f(x, y) \equal{} \minus{} x^3 \plus{} 2y^3 \plus{} 27x \minus{} 24y \plus{} 3$.

(b) $ f(x, y) \equal{} 5x^2 \plus{} 5y^2 \plus{} 5xy \minus{} 10x \minus{} 5y \plus{} 18$

$ \nabla f\equal{}(\minus{}3x^{2}\plus{}27,6y^{2}\minus{}24)\equal{}(0,0)\rightarrow \minus{}3x^{2}\equal{}\minus{}27\rightarrow x\equal{}\pm3$ and $ y\equal{}\pm2$ so the critical points are $ (3,2)$ and $ (\minus{}3,\minus{}2)$.  I'm not sure though if $ (3,\minus{}2)$ and $ (\minus{}3,2)$ are also critical points though.

a): $ f_{x}(x,y) \equal{} \minus{} 3x^2 \plus{} 27 \equal{} 0 \implies x \equal{} \pm 3$
and     $ f_{y}(x,y) \equal{} 6y^{2} \minus{} 24 \equal{} 0 \implies y \equal{} \pm 2$

So that the critical points are: $ (3, \minus{} 2), ( \minus{} 3, 2), (3, 2), ( \minus{} 3, \minus{} 2)$

2nd Derivative Test: $ f_{xx}(x,y) \equal{} \minus{} 6x$ and $ f_{yy}(x,y) \equal{} 12y$ and $ f_{xy}(x,y) \equal{} 0$
So that D = -6x(12y) < 0 whenever x and y have the same sign. So that f(x,y) is not a maximum or minimum whenever x and y have the same sign. Thus $ (3,2)$ and $ ( \minus{} 3, \minus{} 2)$ are neither maxima nor minima. From here we know that (3, 2), (-3, -2) are also saddle points in addition to be being critical points (not all critical points give rise to maxima or minima;-)

By the Second Derivative Test: $ f( \minus{} 3,2)$ is the local minimum while $ f(3, \minus{} 2)$ is the local maximum

b): the critical point is $ (1, 0)$ by a similar method and $ f(1, 0)$ is the local minimum.


inequalities
function
calculus
derivative
inequalities unsolved

Oho ,  :oops: !
I'm sorry ! I have said a wrong things !! I condsidered it homogenous and it was so stupid :) !

I better change the variables to $a,b,c,d$.

Let $E(a,b,c,d)=\frac{a}{\sqrt{a+b}}+\frac{b}{\sqrt{b+c}}+\frac{c}{\sqrt{c+d}}+\frac{d}{\sqrt{d+a}}$.

Assume that $(a,b,c,d)$ realize the maximum of $E$.

Case 1: None of $a,b,c,d$ is 0. Then the function $f(t)=E(a,b+t,c-t,d)$ must satisfy $f'(0)=0$ by Fermat's Theorem.

But $f'(0)=\frac{-c-2d}{2(c+d)^{\frac{3}{2}}}+\frac{1}{\sqrt{b+c}}-\frac{a}{2(a+b)^{\frac{3}{2}}}$.

So $\frac{-c-2d}{2(c+d)^{\frac{3}{2}}}+\frac{1}{\sqrt{b+c}}-\frac{a}{2(a+b)^{\frac{3}{2}}}=0$(*).

Analogously by taking $g(t)=E(a+t,b,c,d-t)$ since $g'(0)=0$ we deduce

$\frac{-a-2b}{2(a+b)^{\frac{3}{2}}}+\frac{1}{\sqrt{a+d}}-\frac{c}{2(c+d)^{\frac{3}{2}}}=0$(**).

By summing the condition (*) and (**) we deduce $\frac{1}{\sqrt{a+b}}+\frac{1}{\sqrt{c+d}}=\frac{1}{\sqrt{b+c}}+\frac{1}{\sqrt{a+d}}$. Since we also have $a+b+c+d=b+c+a+d$ we can deduce $\{a+b,c+d\}=\{b+c,a+d\}$ hence either $a+b=b+c$ or $a+b=a+d$ so $a=c$ or $b=d$.

WLOG $a=c$.

Then $a+2b+c=1$ and $E(a,b,a,d)=\frac{a}{\sqrt{a+b}}+\frac{b}{\sqrt{a+b}}+\frac{a}{\sqrt{a+d}}+\frac{d}{\sqrt{d+a}}=\sqrt{a+b}+\sqrt{a+d}\leq \sqrt{2(a+b+a+d)}=\sqrt{2}<\frac{3}{2}$.

Case 2: One of $a,b,c,d$, say $d$, is $0$. Then $E(a,b,c)=\frac{a}{\sqrt{a+b}}+\frac{b}{\sqrt{b+c}}+\sqrt{c}$.

If $c>a$ then $E<\sqrt{a+b}+\sqrt{c}\leq \sqrt{2(a+b+c)}$. If $c<a$ so $c<\frac{1}{2}$ we have by CBS ${E\leq \sqrt{(a+b)(\frac{a}{a+b}+\frac{b}{b+c}})}+\sqrt{c}$. However we can check by derivative that ${\frac{a}{a+b}+\frac{b}{b+c}}\leq 2(1-\frac{\sqrt{c}}{\sqrt{1-c}})$ and so $E\leq \sqrt{2(1-c)-2\sqrt{c(1-c)}}+\sqrt{c}$.
So we are left to prove that $\frac{3}{2}-\sqrt c\geq \sqrt{2(1-c)-2\sqrt{c(1-c)}}$. By squaring this reduces to $\frac{1}{4}+3c+2\sqrt{c(1-c)}\geq 3\sqrt{c}$. However $\frac{1}{4}+3c\geq \sqrt 3 \sqrt c$ by AM-GM
 and $2\sqrt{c(1-c)}\geq 2\sqrt{\frac{c}{2}}\geq \sqrt 2\sqrt{c}$, and we get the desired conclusion.

[quote="iura"]However we can check by derivative that ${\frac{a}{a+b}+\frac{b}{b+c}}\leq 2(1-\frac{\sqrt{c}}{\sqrt{1-c}})$ [/quote]
I think ${\frac{a}{a+b}+\frac{b}{b+c}}\leq 2(1-\frac{\sqrt{c}}{\sqrt{1-c}})+\frac{c}{1-c}.$  :wink:  But nothing changes . The fine proof!

Wow, iura's used such a complex method. Is there any easier?

By Cauchy

\[(\sum \frac{a_{1}}{\sqrt{a_{1}+a_{2}}})^{2}\le (a_{1}+a_{2}+a_{2}+a_{4})(\sum \frac{a_{1}}{a_{1}+a_{2}}) \le 3\]

so

\[\sum \frac{a_{1}}{\sqrt{a_{1}+a_{2}}}\le \sqrt{3}.\]

It is slighter but I think this method can be re-applied in a better way to prove this original problem.

[quote]$f(t)=E(a,b+t,c-t,d)$ must satisfy $f'(0)=0$ by Fermat's Theorem.
[/quote] any idea about this theorem please. :maybe:

It says that if a function $f : I \to \mathbb R$, where $I$ is an open interval, has a local minimum or maximum at $x_{0}$ and is differentiable at $x_{0}$, then $f^\prime \left( x_{0}\right) = 0$.

Could anybody work out the value of
$\sup\left\{\frac{a}{\sqrt{a+b}}+\frac{b}{\sqrt{b+c}}+\frac{c}{\sqrt{c+d}}+\frac{d}{\sqrt{d+a}}\right\}$
thanks a lot for any idea about it. :lol:

[quote="perfect_radio"]I've written a ($C++$) program that finds the maximum of $E(a,b,c,0)$. It seems to be approximatively $1.435262$.
That's very strange. Maybe I made some mistake?[/quote]
I guess $1.435262\cdots$ may be the right one which could be very strange I feel.

[quote="perfect_radio"]I've written a ($C++$) program that finds the maximum of $E(a,b,c,d)=\frac{a}{\sqrt{a+b}}+\frac{b}{\sqrt{b+c}}+\frac{c}{\sqrt{c+d}}+\frac{d}{\sqrt{d+a}}$. It seems to be approximatively $1.435262$.[/quote]
$E\left(\frac{59}{103},\frac{24}{103},\frac{20}{103},0\right)=1.435266\cdots$.

[quote="Bourne"]$a+b+c\geq 0,a+b+c=1$
Prove that
$\frac{a}{\sqrt{a+b}}+\frac{b}{\sqrt{b+c}}+\frac{c}{\sqrt{c+a}}\leq \frac{5}{4}$
How to solve this one?[/quote]
See here http://www.mathlinks.ro/Forum/viewtopic.php?t=138851

And for the supremum of
$\frac{a}{\sqrt{a+b}}+\frac{b}{\sqrt{b+c}}+\frac{c}{\sqrt{c+d}}+\frac{d}{\sqrt{d+a}}\ (a+b+c+d=1)$
See here [url]http://www.mathlinks.ro/Forum/viewtopic.php?t=140587[/url].

[quote="iura"]I better change the variables to $ a,b,c,d$.

Let $ E(a,b,c,d) = \frac {a}{\sqrt {a + b}} + \frac {b}{\sqrt {b + c}} + \frac {c}{\sqrt {c + d}} + \frac {d}{\sqrt {d + a}}$.

Assume that $ (a,b,c,d)$ realize the maximum of $ E$.

Case 1: None of $ a,b,c,d$ is 0. Then the function $ f(t) = E(a,b + t,c - t,d)$ must satisfy $ f'(0) = 0$ by Fermat's Theorem.

But $ f'(0) = \frac { - c - 2d}{2(c + d)^{\frac {3}{2}}} + \frac {1}{\sqrt {b + c}} - \frac {a}{2(a + b)^{\frac {3}{2}}}$.

So $ \frac { - c - 2d}{2(c + d)^{\frac {3}{2}}} + \frac {1}{\sqrt {b + c}} - \frac {a}{2(a + b)^{\frac {3}{2}}} = 0$(*).

Analogously by taking $ g(t) = E(a + t,b,c,d - t)$ since $ g'(0) = 0$ we deduce

$ \frac { - a - 2b}{2(a + b)^{\frac {3}{2}}} + \frac {1}{\sqrt {a + d}} - \frac {c}{2(c + d)^{\frac {3}{2}}} = 0$(**).

By summing the condition (*) and (**) we deduce $ \frac {1}{\sqrt {a + b}} + \frac {1}{\sqrt {c + d}} = \frac {1}{\sqrt {b + c}} + \frac {1}{\sqrt {a + d}}$. Since we also have $ a + b + c + d = b + c + a + d$ we can deduce $ \{a + b,c + d\} = \{b + c,a + d\}$ hence either $ a + b = b + c$ or $ a + b = a + d$ so $ a = c$ or $ b = d$.

WLOG $ a = c$.

Then $ a + 2b + c = 1$ and $ E(a,b,a,d) = \frac {a}{\sqrt {a + b}} + \frac {b}{\sqrt {a + b}} + \frac {a}{\sqrt {a + d}} + \frac {d}{\sqrt {d + a}} = \sqrt {a + b} + \sqrt {a + d}\leq \sqrt {2(a + b + a + d)} = \sqrt {2} < \frac {3}{2}$.

Case 2: One of $ a,b,c,d$, say $ d$, is $ 0$. Then $ E(a,b,c) = \frac {a}{\sqrt {a + b}} + \frac {b}{\sqrt {b + c}} + \sqrt {c}$.

If $ c > a$ then $ E < \sqrt {a + b} + \sqrt {c}\leq \sqrt {2(a + b + c)}$. If $ c < a$ so $ c < \frac {1}{2}$ we have by CBS ${ E\leq \sqrt {(a + b)(\frac {a}{a + b} + \frac {b}{b + c}})} + \sqrt {c}$. However we can check by derivative that ${ \frac {a}{a + b} + \frac {b}{b + c}}\leq 2(1 - \frac {\sqrt {c}}{\sqrt {1 - c}})$ and so $ E\leq \sqrt {2(1 - c) - 2\sqrt {c(1 - c)}} + \sqrt {c}$.
So we are left to prove that $ \frac {3}{2} - \sqrt c\geq \sqrt {2(1 - c) - 2\sqrt {c(1 - c)}}$. By squaring this reduces to $ \frac {1}{4} + 3c + 2\sqrt {c(1 - c)}\geq 3\sqrt {c}$. However $ \frac {1}{4} + 3c\geq \sqrt 3 \sqrt c$ by AM-GM
 and $ 2\sqrt {c(1 - c)}\geq 2\sqrt {\frac {c}{2}}\geq \sqrt 2\sqrt {c}$, and we get the desired conclusion.[/quote]

In case 2 we have another very simple proof like this:

$ \frac {a}{\sqrt {a + b}} + \frac {b}{\sqrt {b + c}} + \sqrt {c} \\
\le \frac {a}{\sqrt {a + b}} + \sqrt {(b + c)\left(\frac {b}{b + c} + 1\right)} \\
= \frac {a}{\sqrt {a + b}} + \sqrt {1 - a + b} \\
\le \sqrt {\left( a + (1 - a + b)\right)\left( \frac {a}{a + b} + 1 \right)} \\
\le \sqrt {(1 + b)(2 - b)} \le \frac {(1 + b) + (2 - b)}{2} = \frac {3}{2}$

See also here

http://www.mathlinks.ro/weblog_entry.php?t=198160

[quote="Mircea Lascu"]Let $ a,b,c,d \ge 0$, with
$ a\plus{}b\plus{}c\plus{}d\equal{}1$, prove that
\[ \sum \frac{a}{\sqrt{a\plus{}b}} \le \frac{3}{2}
\]
[/quote]
It is a corollary of Jack Garfunkel Inequality
\[ \frac{a}{\sqrt{a\plus{}b}}\plus{}\frac{b}{\sqrt{b\plus{}c}}\plus{}\frac{c}{\sqrt{c\plus{}a}} \le \frac{5}{4}\sqrt{a\plus{}b\plus{}c} \quad \forall a,b,c \ge 0\]
Here is my solution for it :)

[quote="geniusbliss"][quote="GacKiem"]By Cauchy
\[ (\sum \frac {a_{1}}{\sqrt {a_{1} \plus{} a_{2}}})^{2}\le (a_{1} \plus{} a_{2} \plus{} a_{2} \plus{} a_{4})(\sum \frac {a_{1}}{a_{1} \plus{} a_{2}}) \le 3
\]
so
\[ \sum \frac {a_{1}}{\sqrt {a_{1} \plus{} a_{2}}}\le \sqrt {3}.
\]
It is slighter but I think this method can be re-applied in a better way to prove this original problem.[/quote]

i am really sorry for this stupid doubt but can anyone tell me how
$ \sum{cyc} \frac {a_{1}}{a_{1} \plus{} a_{2}}) \le 3$
really sry if it is obvious[/quote]
It is because
$ \frac {1}{x_1 \plus{} 1} \plus{} \frac {1}{x_2 \plus{} 1} \plus{} \cdots \plus{} \frac {1}{x_n \plus{} 1} \le n \minus{} 1,$
for all $ x_i > 0$ satisfying $ x_1x_2\cdots x_n \equal{} 1.$ :)


calculus
function
real analysis
real analysis unsolved

Greetings,

Well, i was in solving this problem (concerning numerical methods) but i couldn't do it, so please if anyone can help me.... thanks in advance :) , I've already put this in another place in this forum, but someone advised me to post it in the calculus section.

""I need to solve the van der Pol equation using second order Taylor method""

here's the equation of van der pol :

y'' + :mu: (y :^2: - 1 )y' + y = 0

thanks for helping.

what do you mean by "solve". What do you expect to get ? a close formula ? an asympototic development ? I don't understand .

by solve, i mean that the original function of " Y " is required...

Yes, but his question was in what form do you expect the function to appear.  For example, I am not familiar with what the "second order Taylor method" is (except that I can figure it uses second order Taylor series), and I can invent a method that will give me the first few coefficients of the Taylor series of y in terms of y(0) and y'(0), but is that what you are expecting?

i need to get y=f(x) , without any intial values or boundary values... thx for trying to help

That equation does not have a nice closed-form solution, so to say that you are looking for y = f(x) is not helpful unless you can describe what form f should take.

I know there's no specific solution ( with canstants) to this formula, but  , using second order of taylor's , will give a general solution, the problem is that i'm stuc at the beginning :(


limit
real analysis
real analysis theorems

What about Stolz-Cesaro case $\frac{0}{0}$? ;)

Once you know the proof for this variant, Cezar, I imagine it is not hard to prove the other part.

[quote="Moubinool"]Stolz Cesaro:

Let $(x_n)$ and $(y_n)$ be two sequences with the properties:
a)$y_n> 0$ for any n natural;
b) $y_n<y_{n+1}$ for any n
c) $(y_n)$ is not bounded superior;
d) there exists $a=\lim \frac{x_{n+1}-x_n}{y_{n+1}-y_n}$
then there exists $\lim \frac{ x_n}{y_n}$ and even more
$\lim \frac{x_n}{y_n}=a$[/quote]

First question: do we really must have $y_n > 0$ for all $n$? I think there is no harm in letting some terms be negative

Second question: how is the $\displaystyle \frac00$ case?

[quote="cezar lupu"]Almost the same. I'd rather say exactly the same. ;)[/quote]

i still don't understand :(

I am asking again this question: can we apply this theorem while calculating the $\var\limsup or \liminf$


search
linear algebra
linear algebra unsolved

Let $ S, A\in M_n(\mathbb{R})$ be matices with all elements are integers and $ detA \equal{} 1, detS\neq0.$
Let $ B \equal{} S^{ \minus{} 1}AS$. Prove that there exist $ m\in \mathbb{N}$ such that all elements of $ B^m$ are integers.

Very nice indeed.
Already posted on this forum ans soolved by loup blanc: http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=1033760780&t=132689


Prove that any integer which is not a power of 2 can be written as the sum of consecutive integers.

$ n \plus{} (n \plus{} 1) \plus{} ... \plus{} (n \plus{} k \minus{} 1) \equal{} \frac {k(2n \plus{} k \minus{} 1)}{2}$
If any integer $ x$ is not a power of $ 2$ , we can express $ 2x$ as $ 2^l m$ , where $ m$ is odd $ (m \neq 1,0,\minus{}1)$.
Then the question becomes we can find integers $ n$ and $ k$$ (k \neq 1, \minus{} 1)$ such that $ 2^l m \equal{} k(2n \plus{} k \minus{} 1)$
Obviously $ 2^l m \equal{} m(2\frac {2l \minus{} m \plus{} 1}{2} \plus{} m \minus{} 1)$ satisfies the condition.Done.

But $ m(2\frac {2l \minus{} m \plus{} 1}{2} \plus{} m \minus{} 1) \equal{} 2lm\ne 2^lm$. It should be $ m(2\frac {2^l \minus{} m \plus{} 1}{2} \plus{} m \minus{} 1)$ right?

It must have just been  a typo. Never mind, the solution is nice and correct.


function
integration
complex analysis
complex analysis unsolved

Any suggestion to prove that $ ((\frac{1}{(1\minus{}z)})^{(\frac{1}{2})})$ is not in $ H^2$ is highly appreciated. Thanks and regards.

Let us consider the function $ f(z)\equal{}\frac{1}{(1\minus{}z)^{\alpha}}$, where $ \alpha>0$.

We have that

$ f(z)\equal{}\sum\limits_{n\equal{}0}^{\infty}\frac{\Gamma(n\plus{}\alpha)}{\Gamma(\alpha)n!}z^{n}$.

Thus

$ \parallel{}f\parallel{}^{2}_{H^{2}}\equal{}\sum\limits_{n\equal{}0}^{\infty}\left(\frac{\Gamma(n\plus{}\alpha)}{n!}\right)^{2}$.

Note that $ \frac{\Gamma(n\plus{}\alpha)}{\Gamma(n\plus{}1)}\approx n^{\alpha\minus{}1}$, and hence

$ \parallel{}f\parallel{}^{2}<\infty$  (i.e., $ f\in H^{2}$) if and only if $ \alpha<\frac{1}{2}$.

There is another method for studying the membership of this function in the Hardy space namely to show that

$ \sup\limits_{0<r<1}\frac{1}{2\pi}\int\limits_{0}^{2\pi}|f(re^{i\theta})|^{2}d\theta<\infty$,

 but this requires a little bit of work.


logarithms
inequalities
real analysis
real analysis unsolved

Prove that the series $\sum{\frac{x^n}{(1+x^n)^n}}$ converges uniformly on $[0,1]$.

Nice, a sum of strictly positive numbers equals 0. Wow! To be more serious, just look closer, you don't have a telescopic sum there.

Denote $a_n(x): =\frac{x^n}{(1+x^n)^n}$ then $a_n$ increases for $x\le\dfrac1{\sqrt[n]{n-1}}=\dfrac1{1+\epsilon_n}$ where $0<\epsilon_n=o\,(1)$ as $n\to\infty$.

Choose $\epsilon>0$ small.

1) Prove that our series converges uniformly on $\left[0,\dfrac1{1+\epsilon}\right]$. Since $\exists\,n_0\in\mathbb N$ such that $\forall\,n\ge n_0\;\;\epsilon_n\le\epsilon$, we derive that $\forall\,n\ge n_0\;a_n$ increases on $\left[0,\dfrac1{1+\epsilon}\right]$. Thus $\sum\limits_{n\ge n_0} a_n(x)\le\sum\limits_{n\ge n_0} a_n\left(\dfrac1{1+\epsilon}\right)<\infty$ and so the series converges uniformly on the mentioned interval.

2) Prove that our series converges uniformly on $\left[\dfrac1{1+\epsilon},1\right]$. For convenience let's substitute $x$ with $x^{-1}$ and so consider $\sum\frac{x^{n(n-1)}}{(1+x^n)^n}$ on $[1,1+\epsilon]$.

The estimate $\sum\frac{x^{n(n-1)}}{(1+x^n)^n}\le\sum\frac{(1+\epsilon)^{n(n-1)}}{2^n}<\infty$ gives us what demanded.

Now 1) and 2) prove the statement.

The last series you wrote clearly does not converge.

A complicated proof is there : http://les-mathematiques.u-strasbg.fr/spip/article.php3?id_article=22
And you, harazi, have you got an easier proof ?
 :cool:

No, it's the same place I saw the exercise and after some hours of horrible computations I got exactly nothing.

Here is a simpler presentation of a similar solution. The first natural idea is to try the Weierstrass M-test. It is easy to see that it fails, but barely so: the maximal possible value of the $n$-th term is about $\frac 1n$ and is attained when $x^n=\frac 1{n-1}$. This suggests the idea to choose $a<1<b$ very close to $1$ and to split the sum over large indices into three: the sum over $n$ with $x^n\le\frac 1{n^b}$, which is trivially estimated by the tail of the convergent series $\sum{\frac 1{n^b}}$,  the sum over $n$ with $x^n\ge \frac 1{n^a}$, which is also dominated by the convergent series $\sum \frac1{\left(1+\frac 1{n^a}\right)^n}$ and the sum over the set $S(x)=\left\{n>1 : \frac 1{n^b}<x^n<\frac 1{n^a}\right\}$. Since everything is OK on any interval $[0,t]$ with $t<1$, it suffices to show that $\sum_{n\in S(x)}\frac 1n<\varepsilon$ when $x$ is close to $1$ and $b-a$ is small enough. Let $N(x)$ be the smallest and let $M(x)$ be the largest element in $S(x)$. Note that $N(x)\to\infty$ as $x\to 1-$. Let $c=\frac{M(x)}{N(x)}$. Our task is to show that $c$ is close to $1$ if $b-a$ is small and $x$ is close to $1$. But, from the definition of $M(x)$ and $N(x)$, we have
\[ [cN(x)]^{-b}=M(x)^{-b}<x^{-M(x)}=x^{-cN(x)}<N(x)^{-ca} \]
whence
\[ c^{-b}< N(x)^{b-ca}\,. \]
Let $\alpha=a/b$. Then $c>N(x)^{\alpha c-1}>1+\log N(x)(\alpha c-1)$. Solving this inequality, we get $c<\frac{\log N(x)-1}{\alpha\log N(x)-1}\to \frac 1\alpha$ as $x\to 1-$ and we are done.


Let $a,b$ be two perpendicular lines which interesect at $O$ and $d$ be a fixed line which passes through $O$. $A$ is a fixed point of $a$; $P$ is a variable point on $b$, and $Q$ is its symmetric wrt $O$. Also, let $\displaystyle \left\{ U \right\} = AP \cap d$ and $\displaystyle \left\{ V \right\} = AQ \cap d$.

Prove that $PV \cap UQ$ is a fixed point.

[b]The first (syntetical) method.[/b] Denote: the (fixed) line $p$ for which $A\in p$ and $p\perp a$; the intersections $L\in p\cap d$, $F\in p\cap VP$. Observe that the quadrilateral $AQPF$ is a trapezoid and the point $O$ is the middlepoint of the side $[QP]$. Thus, the (fixed) point $L$ is the middlepoint of the side $[AF]$, the point $F$ is fixed and the point $U$ belongs to the line $QF$, i.e. $F\in QU\cap VP\ .$

[b]The second (analytical) method.[/b] Choose $Ox: =a\ ,$ $Oy: =b\ .$ Thus: $A(a,0)$; $P(0,p)\ ,$ $p\in R$; $Q(0,-p)$; the equation of the (fixed) line $d$ is $y=kx\ ,$ $k\ne 0$. Then $U\left(\frac{ap}{p+ka},\frac{kap}{p+ka}\right)\ ,$ $V\left(\frac{-ap}{-p+ka},\frac{-kap}{-p+ka}\right)$. The equations of the  lines $PV$, $QU$ are: $PV\ : \ (p-2ka)x+ay-ap=0$ and  $QU\ : \ (p+2ka)x-ay-ap=0\ .$ Come to the conclusion that the intersection of the lines $PV$, $QU$, i.e. the point $F(a,2ka)$ is fixed.

After finding the analytic solution (your second solution), I tried in vain to find the synthetic solution... Thank you very much.


Why is the mechanical energy in a mass-spring system not constant? When i make a plot of the mechanical energy it looks more like a sine-courve? Im sure that all my calculations are right as my teacher has told me so, and he always gets such a courve when making that experiment. Can anybody explain why?

If the mechanical energy is not constant that's because there is some force acting on the system that dissipates energy, like friction.

I know that has to be the case but it still doesnt make any sense to me...
Why does the friction only work in one direction then? It looks like it is the potential energy that doesnt make any sense... The kinetic energy courve looks fine.. any ideas?
Description:
A spring hanging from the ceiling with som mass in the end. The spring goes up and down, and the position and speed of the mass is measured with ultrasound.
E(kin)=0,5*mass*v^2
E(pot)=0,5*k*x^2
Where k is the spring-constant and x is the length from equilibrium.


number theory
greatest common divisor
number theory unsolved

Let $ a,b,c>0$ intigers and $ GCD(a^2\minus{}1, b^2\minus{}1, c^2\minus{}1)\equal{}1$. Prove that $ GCD(ab\plus{}c, ac\plus{}b, bc\plus{}a)\equal{}GCD(a,b,c)$

clearly $ \gcd(a,b,c)|\gcd(ab\plus{}c,ac\plus{}b,bc\plus{}a)$. now we must prove $ \gcd(ab\plus{}c,ac\plus{}b,bc\plus{}a)|\gcd(a,b,c)$.

assume first that $ p^k\|\gcd(ab\plus{}c,ac\plus{}b,bc\plus{}a)$, where $ p$ is a prime and $ k\geq 1$. (the notation $ p^k\|n$ for $ n\in \mathbb{N}$ means that $ p^k$ is the highest power of $ p$ dividing $ n$.) then $ p^k|(a\plus{}1)(b\plus{}c),(b\plus{}1)(a\plus{}c),(c\plus{}1)(a\plus{}b)$. We will prove that $ p$ does not divide $ a\plus{}1,b\plus{}1,c\plus{}1$, implying that $ p^k|b\plus{}c,a\plus{}c,a\plus{}b$. if $ p|a\plus{}1$, then $ p|(bc\plus{}a)\minus{}(a\plus{}1)\equal{}bc\minus{}1$, $ p|ab\plus{}b$, and $ p|(ab\plus{}b)\minus{}(ab\plus{}c)\equal{}b\minus{}c$. So $ p|bc\minus{}c^2$ and $ p|b^2\minus{}bc$, so $ p|(bc\minus{}1)\minus{}(bc\minus{}c^2)\equal{}c^2\minus{}1$ and $ p|(b^2\minus{}bc)\plus{}(bc\minus{}1)\equal{}b^2\minus{}1$. but then $ p|\gcd(a^2\minus{}1,b^2\minus{}1,c^2\minus{}1)$, a contradiction. Similarly, $ p$ doesn't divide $ b\plus{}1$ or $ c\plus{}1$.

therefore, $ p^k|(b\plus{}c)\minus{}(a\plus{}c)\equal{}b\minus{}a$, and $ p^k|(b\minus{}a)\plus{}(a\plus{}b)\equal{}2b$, and similarly $ p^k|2a$ and $ p^k|2c$. If $ p$ is odd, then we get $ p^k|a,b,c$ and thus $ p^k|\gcd(a,b,c)$. If $ p\equal{}2$, then we have $ 2^k|2a,2b,2c$, which implies that $ 2^{k\minus{}1}|a,b,c$. To complete the proof, we need to show that $ 2^k|a,b,c$. so assume for a contradiction that $ 2^{k\minus{}1}\|a,b,c$. then $ 2^{2(k\minus{}1)}\|ab$, so $ 2^{k\minus{}1}\|ab\plus{}c$ -- a contradiction -- unless $ k\equal{}1$. if $ k\equal{}1$, then we simply need to show that $ a,b,c$ are all even. note that at least one of $ a,b,c$ must be even because of the given condition. assume wlog that $ a$ is even. then since $ ab\plus{}c$ and $ ac\plus{}b$ are both even, it follows that $ b$ and $ c$ are even too. so the proof is complete.


[hide]
we get $\frac{1}{2}\sin{6x} = \sin{2x}$, let $u = 2x$, so $\sin{3u} = 2\sin{u}$, solving get $u = k\pi, \frac{(2k+1)\pi}{4}$.  therefore $x = \frac{k\pi}{2}, \frac{(2k+1)\pi}{8}$.[/hide]

[hide]
$\sin(3x)=3 \sin x - 4 \sin^3x$
$\cos(3x)=4 \cos^3x-3 \cos x$

$\sin(3x)\cos(3x)=12 \sin x \cos x( \cos^2x + \sin^2x) -16 \sin^3x \cos^3x- 9 \sin x \cos x= \sin(2x)$

$\sin x \cos x= \frac{1}{2} \sin(2x) \rightarrow \frac{3}{2} \sin(2x)=0$

$\sin(2x)=0 \implies x=\frac{\pi}{2}+k \frac{\pi}{2}$[/hide]

$x=0,\frac{\pi}{12},\frac{5\pi}{12},\frac{\pi}{2},\frac{7\pi}{12},\frac{11\pi}{12}$. Adding any multiple of $\pi$ to any of these answers works.

A lot of people are getting different answers  :huh: ?

inom, jhcreinhardt, and yours are basically the same answer but in different forms.


$ x,y,z$ are positive real numbers such that : $ xy+yz+zx=1$ . Prove that :

$ \frac{x^{3}}{x^{2}+2yz+1}+\frac{y^{3}}{y^{2}+2xz+1}+\frac{z^{3}}{z^{2}+2xy+1}\geq \frac{x+y+z}{6}$


inequalities
limit
floor function
absolute value
number theory proposed
number theory

Let $a\geq 2$ be a natural number. Prove that $\sum_{n=0}^\infty\frac1{a^{n^{2}}}$ is irrational.

This number in a sistem can be read $s=0,1001000010000001...$. Because it is not periodic s - irrational.

[quote="ZetaX"]Show that it is transcendental.[/quote]

Can you show it?

It is not difficult to show that $\sum a^{-2^{n}}$ is transcendental, but for $\sum a^{-n^{2}}$ this would be much more difficult. [... I believe it to be an open problem, but I can't point to a reference... ]

Poor me, I still don't see why proving that the sum of $1/a^{2^{n}}$ is transcendent is so easy  :blush: . On the other hand, I don't think one can use Liouville's theorem in this problem.

For \[\sum_{n}a^{-[b^{n}]}\] work Rota's theorem, if a>1 natural, b>2 real.

Indeed, but for $a=2$ this powerful theorem does not work. I know Mahler investigated this type of series and proved its transcendent character, but I've never found his paper nor a discussion about his method.

[quote="harazi"]Indeed, but for $a=2$ this powerful theorem does not work. [/quote]
It don't work for $b=2$  a can be any integer >1.

Actually, I didn't have Roth's theorem in mind when I said that it's not too difficult to prove the transcendence of $\sum a^{-2^{n}}$; and I will give a self-contained proof in the next post. But first, let's see how Roth actually DOES imply this fact pretty easily :). Well, maybe not the most classical version of Roth, but rather two [I will give proofs by] two different strengthenings of it.

The first more general Roth result (due to Schmidt, and the very special case of his "subspace theorem") is as follows: for any algebraic numbers $\alpha_{0}, \ldots, \alpha_{d}\in \overline{\mathbb{Q}}$ and every $\varepsilon > 0$, the inequality $0 < |\alpha_{0}x_{0}+\cdots+\alpha_{d}x_{d}| < \max_{i}\{|x_{i}|\}^{-d-\varepsilon}$ has only finitely many solutions in integers $x_{0}, \ldots,x_{d}$; this is basically the most basic version of Roth's result in dimension $d$, with the classical Roth result appearing as $d=1$. To deduce from the theorem just stated the transcendence of $\sum a^{-2^{n}}$, we will only use the case $d=2$ and $\alpha_{0}: = 1, \alpha_{1}: = \beta, \alpha_{2}: = \beta^{2}$, where $\beta : = \sum a^{-2^{n}}$. Letting $\beta_{n}: = \sum_{k \leq n}a^{-2^{k}}$, the rational approximation $|\beta-\beta_{n}| = a^{-2^{n+1}}+a^{-2^{n+2}}+\cdots = O(a^{-2^{n+1}})$ is good, but not good enough to apply Roth to it directly. Instead, one looks at an identity like

$(\beta-\beta_{n})^{2}-2a^{-2^{n+1}}(\beta-\beta_{n})+a^{-2^{n+1}}-(\beta-\beta_{n}) = (a^{-2^{n+1}}+\cdots)^{2}-2a^{-2^{n+1}}(a^{-2^{n+1}}+\cdots)+a^{-2^{n+1}}-(a^{-2^{n+1}}+\cdots) =-a^{-6 \cdot 2^{n+1}}+\cdots = O(a^{-6 \cdot 2^{n+1}}),$

and sees that it is good enough to imply the desired transcendence: one applies the above-mentioned result with, say, $\varepsilon = 1/2$ (any $\varepsilon < 1$ will do).

An alternative way to "see" the transcendence of $\sum a^{-2^{n}}$ is by another, this time much more straightforward, generalization of Roth: by approximating directly, but using several absolute values at once. Such result was first given by Ridout (and, afterwards, Mahler), and the simplest version reads:

[b] Roth's theorem with several absolute values. [/b] Let $S$ be a finite set of primes, including the "infinite prime," the symbol $\infty$. For every $p \in S$ we have the $p$-adic absolute value $|\cdot|_{p}$ on $\mathbb{Q}$, normalized as usual: if $p = \infty$, then $|\cdot|$ is the "standard" archimedean absolute value; if $p$ is finite, then $|x|_{p}: = p^{-\mathrm{ord}_{p}{x}}$.

For every $p \in S$, consider an algebraic number $\alpha_{p}\in \overline{\mathbb{Q}}$. Extend each absolute value $|\cdot|_{p}$ to $\mathbb{Q}(\alpha_{p})$ in some way. Then for every $\varepsilon > 0$ there are only finitely many rational solutions $r/s$ to the inequality
\[\prod_{p \in S}|\alpha_{p}-r/s|_{p}< s^{-2-\varepsilon}. \]
To deduce the transcendence of $\beta = \sum a^{-2^{n}}$, take $S$ to consist of $\infty$ and the finitely many prime divisors of $a$. Choose $\alpha_{\infty}: = 1/\beta$, and for the other $p$s, choose $\alpha_{p}: = 0$. Of course, we then choose $r/s : = 1/\beta_{n}= \big( \sum_{k \leq n}a^{-2^{k}}\big)^{-1}$, with $r = a^{2^{n}}$ (this time we approximate directly). Then $|\alpha_{\infty}-r/s|_{\infty}= |1/\beta-1/\beta_{n}| = |\beta-\beta_{n}| / |\beta\beta_{n}| < 2 a^{-2^{n+1}}$ and $\prod_{p \in S \setminus \{ \infty\}}|\alpha_{p}-r/s|_{p}= \prod_{p \mid a}|r/s|_{p}= \prod_{p \mid a}|a^{2^{n}}|_{p}= a^{-2^{n}}$, whence $\prod_{p \in S}|\alpha_{p}-r/s|_{p}< 2a^{-3 \cdot 2^{n}}$, and this is true for every $n$, contradicting the above-stated inequality for any $\varepsilon < 1$.

Now, I had the intention to write a self-contained (and not too long) proof of the transcendence of $\sum a^{-2^{n}}$ in my next post, but now that I explained how to deduce this from the two-dimensional Roth theorem, I see that what I wrote there is an excellent hint on how to proceed "ad hoc," without recourse to Roth. This hint should really convey the essential point in the proof; if it doesn't, then I'll write the proof myself.

Finally, notice that the second deduction from "Roth-type" generalizes immediately to show: if $n_{0}< n_{1}< \cdots$ is an increasing sequence with $\lim\sup n_{i+1}/n_{i}> 3/2$, then $\sum a^{-n_{i}}$ is transcendental. (The "classical" Roth theorem immediately told us that this were the case if the weaker condition $\lim\sup n_{i+1}/n_{i}> 2$, which did not suffice for the problem, held). A similar argument, slightly refined, would show that it suffices to assume $\lim\sup n_{i+1}/n_{i}> 1$; in particular,  taking on Rust's example, $\sum a^{-\lfloor b^{n}\rfloor}$ is transcendental for any integer $a > 1$ and any real $b > 1$. Further, along similar lines (but we'd have to recourse to Schmidt's far-reaching generalization of Roth -- the one-dimensional case won't suffice anymore, even in the case that $\alpha \in \mathbb{Q}$!), it is possible to show that $\sum \alpha^{n_{i}}$ is transcendental for any $\alpha \in \overline{\mathbb{Q}}$ algebraic with $|\alpha| < 1$, and $n_{0}< n_{1}< \cdots$ with $\lim\sup n_{i+1}/n_{i}> 1$!

Now, I leave you the pleasure of proving the transcendence of $\sum a^{-2^{n}}$ without recourse to Roth's theorem :) The hint is very explicit in the first part of this post. On the other hand, for the stronger problems with the $n_{i}$, I don't think think it would be possible to give a short proof avoiding Roth or a result of comparable depth (the approach I know for $\sum a^{-2^{n}}$ certainly breaks down if we try this more general problem... )

[quote="vess"]The first more general Roth result (due to Schmidt, and the very special case of his "subspace theorem") is as follows: for any algebraic numbers $\alpha_{0}, \ldots, \alpha_{d}\in \overline{\mathbb{Q}}$ and every $\varepsilon > 0$, the inequality
(*) $0 < |\alpha_{0}x_{0}+\cdots+\alpha_{d}x_{d}| < \max_{i}\{|x_{i}|\}^{-d-\varepsilon}$
has only finitely many solutions in integers $x_{0}, \ldots,x_{d}$; this is basically the most basic version of Roth's result in dimension $d$, with the classical Roth result appearing as $d=1$. To deduce from the theorem just stated the transcendence of $\sum a^{-2^{n}}$, we will only use the case $d=2$ and
$\alpha_{0}: = 1, \alpha_{1}: = \beta-\beta_{n}, \alpha_{2}: = (\beta-\beta_{n})^{2}$,
where $\beta : = \sum a^{-2^{n}}, \beta_{n}: = \sum_{k \leq n}a^{-2^{n}}$ (assuming the algebraicity of $\beta$, it also follows that $\beta-\beta_{n}$ and $(\beta-\beta_{n})^{2}$ are algebraic). Now, the rational approximation $|\beta-\beta_{n}| = a^{-2^{n+1}}+a^{-2^{n+2}}+\cdots = O(a^{-2^{n+1}})$ is good, but not good enough to apply Roth to it directly. Instead, one looks at an identity like

$(\beta-\beta_{n})^{2}-2a^{-2^{n+1}}(\beta-\beta_{n})+a^{-2^{n+1}}-(\beta-\beta_{n}) = (a^{-2^{n+1}}+\cdots)^{2}-2a^{-2^{n+1}}(a^{-2^{n+1}}+\cdots)+a^{-2^{n+1}}-(a^{-2^{n+1}}+\cdots) =-a^{-6 \cdot 2^{n+1}}+\cdots = O(a^{-6 \cdot 2^{n+1}}),$

and sees that it is good enough to imply the desired transcendence: one applies the above-mentioned result with, say, $\varepsilon = 1/2$ (any $\varepsilon < 1$ will do).
[/quote]
It give only one solution (*) $x_{0}=1,x_{1}=-(a^{2^{n+1}}+2), x_{2}=a^{2^{n+1}}$.
For contradition you must give infinetely many solutions (*) with same $\alpha_{0}, \ \alpha_{1}, \ \alpha_{2}.$

Sorry, I meant to apply the result with $\alpha_{0}: = 1, \alpha_{1}: = \beta, \alpha_{2}: = \beta^{2}$. Expand $\beta^{2}+\beta \cdot (2 \beta_{n}-2a^{-2^{n+1}}-1)+(\beta_{n}^{2}+2a^{-2^{n+1}}\beta_{n}+a^{-2^{n+1}}+\beta_{n})= (\beta-\beta_{n})^{2}-2a^{-2^{n+1}}(\beta-\beta_{n})+a^{-2^{n+1}}-(\beta-\beta_{n}) = O(a^{-6 \cdot 2^{n+1}})$, and you get a solution with $\{\alpha_{0},\alpha_{1},\alpha_{2}\}= \{1,\beta,\beta^{2}\}$ for every $n$, hence you get infinitely many solutions, in contradiction to Roth's theorem in two dimensions (a contradiction is easily obtained by taking any $\varepsilon < 1$).

Thanks for pointing this out, I'll edit.

[Edit. I edited the inaccurate sentence in my post above. Everything should now be correct. ]

I think, your method work for $\sum_{n}a^{-[b^{n}]}$ for any integer $a$, and real $b>1$.

[quote="vess"][quote="ZetaX"]Show that it is transcendental.[/quote]

[...] for $ \sum a^{-n^{2}}$ this would be much more difficult. [... I believe it to be an open problem, but I can't point to a reference... ][/quote]
Actually, it [i]not[/i] an open problem, although it has been solved relatively recently.
Namely, in 1996, Yuri Nesterenko proved that $ \sum_{n \geq 1}2^{-n^{2}}$ is transcendental.
The general result (with an algebraic $ |a| < 1$) has then been obtained as a corollary by Daniel Bertrand, who proved a more general statement involving the so-called "modular functions."

For a good survey of such results, I suggest reading the following article by François Gramain (it's in french, though) :
http://www.numdam.org/item?id=JTNB_1999__11_1_73_0

If someone's interested, I might try to give an explanation here, but it will certainly not be as good as in the above article.

mathmanman,

If you don't mind, then could you sketch the ideas used in the proof.  Thanks.


$ x,y,z$ are 3 positive numbers such that $ x\plus{}y\plus{}z\equal{}\frac{3}{2}$. Find the smallest value of
$ P\equal{}\frac{1}{x^3}\plus{}\frac{1}{y^3}\plus{}\frac{1}{z^3}.$

Let f(x)=1/x³  then  f''(x)=12/x^(-5)>0  then f(x) is convex for x>0

 1/x³+1/y³+1/z³=f(x)+f(y)+f(z)≥3f([x+y+z/3])=3f(1/2)=24  by Jensen
Then the minimun is 24

another solution

by AM-GM
$ \frac{1}{x^3}\plus{}16x\plus{}16x\plus{}16x \geq 4\sqrt[4]{16^3}\equal{}32$

therefore
$ \frac{1}{x^3}\plus{}\frac{1}{y^3}\plus{}\frac{1}{z^3}\equal{} \frac{1}{x^3}\plus{}16x\plus{}16x\plus{}16x\plus{}\frac{1}{y^3}\plus{}16y\plus{}16y\plus{}16y\plus{}\frac{1}{z^3}\plus{}16z\plus{}16z\plus{}16z\minus{}48(x\plus{}y\plus{}z) \geq 3 \cdot 32\minus{}48\cdot \frac{3}{2}\equal{}24$

equallity occurs when $ x\equal{}y\equal{}z\equal{}\frac{1}{2}$

[quote="ricardokaka"]$ x,y,z$ are 3 positive numbers such that $ x \plus{} y \plus{} z \equal{} \frac {3}{2}$. Find the smallest value of
$ P \equal{} \frac {1}{x^3} \plus{} \frac {1}{y^3} \plus{} \frac {1}{z^3}.$[/quote]
easy problem!
by holder we have $ 9P\geq (\frac{1}{x}\plus{}\frac{1}{y}\plus{}\frac{1}{z})^3\geq 6^3$
So,$ P\geq 24$

Thanks all for your help!
And now, we'll conside this problem!

Find the smallest value of
$ P \equal{} \frac {1}{(cosa)^6} \plus{} \frac {1}{(cos(a \plus{} \frac {\pi}{3})) ^6}\plus{} \frac {1}{(cos(a \plus{} \frac {2\pi}{3}))^6}$

I think that the new problem can be solved by using the first problem! But now, i known that i'm false! :P

[quote="ricardokaka"]Thanks all for your help!
And now, we'll conside this problem!

Find the smallest value of
$ P \equal{} \frac {1}{(cosa)^6} \plus{} \frac {1}{(cos(a \plus{} \frac {\pi}{3})) ^6} \plus{} \frac {1}{(cos(a \plus{} \frac {2\pi}{3}))^6}$

I think that the new problem can be solved by using the first problem! But now, i known that i'm false! :P[/quote]
I think this is an easy problem,but this is a problem from M&Y, issue 1,,2008, and we can't discuss it now.
Mods should lock this topic!

Please continue to solve it! It can accidental be a problem from a contest!

[color=green]Please don't reply this problem. And mods, please lock it. Thanks.

@ricardokaka. Why did you do it?  :mad: [/color]

I said before, it can accidental be a problem from a contest from any nation, but i'm not interested in it. It's null! I want a proof for my problem!


In how many different ways can 40 be written as a sum of two positive prime numbers? The sums $ a\plus{}b$ and $ b\plus{}a$ are considered to be the same.

We could just list them, since we suspect that there aren't that many pairs of prime numbers that sum to $ 40$. The possible pairs $ (a, b)$ are $ (37, 3), (29, 11), (23, 17), (17, 23), (11, 29), (37, 3)$. But we are told that the pair $ (37, 3)$ is the same as the pair $ (3, 37)$. Eliminating doubles, we find that our answer is $ \boxed{3}$ pairs $ (a, b)$ of prime numbers that sum to $ 40$.

I believe the only possible way to answer this question is by using casework counting. In the format (x,y), the only pairs are (37,3), (29,11), and (23,17).

Don't post if you are not going to add something to the solution.


probability
combinatorics proposed
combinatorics

I want to find the probability of getting a straight out of 12 cards dealt from a deck.

So for the denominator it is 52 nCr 12.

For the numerator... I know that there are 10 possible straights if I don't break up A and 2. Out of the 10 straights, I choose one. Then, I need to choose five corresponding cards out of 4 suits. I get this:

(10 nCr 1)*[(4 nCr 1)^5]

Finally, since I am choosing 12 cards, I need to choose 7 more cards out of the remaining 47 cards.

So the numerator would be:

(10 nCr 1)*[(4 nCr 1)^5]*(47 nCr 7)

And putting that with the numerator to get the probability, I would get:

(10 nCr 1)*[(4 nCr 1)^5]*(47 nCr 7)
-------------------------------------
(52 nCr 12)

But if I divide this, I get 3.xx... and probability should be 0 => 1.. what am I doing wrong?

At the very least, you've made substantial over-counting by counting situations with more than one straight repeatedly.  I suspect you've also overcounted lots of other situations, as well.


In $\triangle ABC$, $AB=6$, $BC=8$, and $CA=7$.
Also, $D$ is on $AB$, $E$ is on $BC$, and $F$ is on $CA$.

$G$ is a point inside the triangle such that $DG\parallel BC$, $EG\parallel CA$, $FG\parallel AB$, and $DG=EG=FG$.

Find the length of $DG$.

[hide]let $DG=EG=FG=x$
draw in $HF$ and $ID$ parallel to $DG$ and $EG$ respectively.
parallelograms are formed so these are also of length $x$
$AH=\frac{AB}{BC}x=\frac 68 x$
$HD=\frac{AB}{AB}x=\frac 66 x$
$DB=\frac{AB}{AC}x=\frac 67 x$
$6x(\frac 18+\frac 16+\frac 17)=6$
$x(\frac {21+28+24}{168})=1$
$x=\boxed{\frac{168}{73}}$[/hide]

just out of curiosity, was this problem in any way inspired by 1986 AIME #9?

No, I didn't know that there was a similar problem to this...

Anyway, your answer is correct :)


calculus
integration
derivative
topology
Gauss
function
real analysis

Anyone ever heard of it? It generalizes the fundamental theorem of calculus, the divergence theorem, stoke's theorem, etc. in one neat, compact equation. Here it is:

\[\int_{\partial S} \omega = \int_{S} d\omega\]

where $\omega$ is a differential k-form and $S$ is a (k+1)-dimensional manifold. $d\omega$ signifies the exterior derivative of $\omega$ and $\partial S$ signifies the boundary of $S$.

If you let $S$ be an interval $[a,b]$ and $\omega$ be the 0-form $f(x)$, then you get the fundamental theorem of calculus. Very useful formula  :)

Spivak's [i]Calculus on Manifolds[/i] is an entire textbook - well, a fairly skinny book - devoted to setting up, proving, and using this theorem.

Yes. Sometimes I find that Gauss Theorem and Stokes Theorem in three dimensional space escape from my brain, then I deduce it from this generalised one.

The most important Theorem in modern analysis I would say! Look

$\int_{\partial S}\,\omega = \int_{S}\,d\omega$

is an equation in both Analysis and Topoplgy. It relates not only the "differential" of one function or form $\omega$ to another but also has something to do with the manifold $S$ and its boundary $\partial S$
Much has been talked about the analysis side but not enough has been talked about the topological side of the equation and I realy want to see good further remark on it in this forum. :D

One idea always makes me puzzle:
"Stokes Theorem"   $\int_{\partial \Omega}\,\omega=\int_{\Omega}\,d\omega$
and  "Change of Variable Theorem" $\int_{\Omega}\,d\mu =\int_{\Omega}
\frac{d\,\mu}{d\,\nu}\, d\nu$
are the two most frequenctly used Theorem in analysis. Could we some how deduce one theorem from the other?
 :idea:


conics
hyperbola
ellipse
geometry
geometric transformation
reflection
incenter

Before going into the solution of the problem, we solve two previous constructions.

[b]Construction 1:[/b] Given four points $M,N,P,Q,$ no three of them collinear, and a line $m$ through $M,$ constuct the conic $\mathcal{H}$ through $M,N,P,Q$ tangent to $m.$

[b]Solution:[/b] Construct the homologous $P',Q',N'$ of $P,Q,N$ in a circle $\gamma$ tangent to $m$ through $M,$ which is the center of the homology mapping the wanted conic $\mathcal{H}$ into $\gamma.$ Three pairs of homologous points $(P,P'),(Q,Q')$ and $(N,N')$ are sufficient to construct the axis $e$ and limit line $\ell$ of the homology. Construct the pole $O'$ of $\ell$  WRT $\gamma$ and the conjugate points $K,K'$ on $\ell$ WRT $\gamma$ such that $MK \perp MK'.$ This is, construct $U \equiv \ell \cap m$ and the circle $(U)$ with radius $UM$ cuts $\ell$ at $K,K'.$ Then $MK,MK'$ are parallel to the axes of $\mathcal{H}$ $\Longrightarrow$ lines $O'K,O'K'$ cut $\gamma$ at $A',B'$ and $C',D',$ i.e. images of the vertices $A,B$ and $C,D$ of  $\mathcal{H}.$ Thus, it remains to construct the homologous points $A,B,C,D$ of $A',B',C',D'$ under the referred homology to get the axes $AB,CD$ and the center $O \equiv AB \cap CD$ of $\mathcal{H}.$ If the limite line $\ell$ cuts $\gamma$ (say at two points), then the wanted conic $\mathcal{H}$ is a hyperbola and we might consider the construction of its asymptotes.
_______________________________________________

[b]Construction 2:[/b] Given an ellipse $\mathcal{E}$ with foci $D,F$ and semi-major axis legth $a$ and a line $\ell,$ which cuts the ellipse, then find the intersections $\mathcal{E} \cap \ell$ with ruler and compass.

[b]Solution:[/b] Label $P_1,P_2 \equiv \mathcal{E} \cap \ell$ the desired intersections. Reflections $U,V$ of $D$ about the tangents of $\mathcal{E}$ at $P_1,P_2$ lie on the focal circle $\mathcal{F} \equiv (F,2a)$ $\Longrightarrow$ circles $(P_1),(P_2)$  that pass through $D,F$ are internally tangent to $\mathcal{F}$ at $U,V.$ Thus, if $D'$ is the reflection of $D$ about $\ell,$ then we shall construct the two circles that pass through $D,D'$ and touch $\mathcal{F}$ internally. Draw two arbitrary circles $\omega_1,\omega_2$ passing through $D,D',$ then the radical axes $\tau_1$ and $\tau_2$ of $\mathcal{F},\omega_1$ and $\mathcal{F},\omega_2$ meet at the radical center $R$ of the pencil of circles through $D,D'.$ Therefore, tangents from $R$ to $\mathcal{F}$ touch $\mathcal{F}$ at $U,V$ $\Longrightarrow$ $P_1 \equiv \ell \cap FU$ and $P_2 \equiv \ell \cap FV.$
_______________________________________________

[b]Solution to the problem:[/b] Clearly, the internal bisector of $\angle (\mathcal{L}_b,\mathcal{L}_c)$ cuts $r$ at the incenter $I,$ thus the incircle $(I)$ of $\triangle ABC$ is that with center $I$ tangent to $\mathcal{L}_b,\mathcal{L}_c$ at $Y,Z.$ Project any line through $A$ (not cutting the incircle) to infinity and the incircle $(I)$ into a circle $(I').$ If we denote the projected points with primes, then $Y,Z$ go to $Y',Z'$ diametrically opposed in $(I'),$ $\mathcal{L}_b,\mathcal{L}_c$ go to the tangents $\mathcal{L}_b',\mathcal{L}_c'$ of $(I')$ at $Y',Z'$ and variable tangents $BC \equiv \mathcal{L}_a$  of $(I)$ at $X$ go to variable tangents $\mathcal{L}_a'$ of $(I)'$ at $X',$ cutting $\mathcal{L}_b',\mathcal{L}_c'$ at $C',B'.$ Thus, Gergonne point $G_e \equiv BY \cap CZ$ of $\triangle ABC$ goes to ${G_e}' \equiv B'Y' \cap C'Z'$ and $P \equiv YZ \cap AX$ goes to $P' \equiv Y'Z' \cap A'X'.$

Now, for convenience, we get rid of the primes in the projected figure. Then, we have $PG_e \parallel \mathcal{L}_b \parallel \mathcal{L}_c,$ i.e. $G_eP \perp YZ$ and since the cross ratio $(P,X,G_e,A)$ is harmonic, it follows that $\overline{G_eP}=-\overline{G_eX}$ $\Longrightarrow$

$\overline{G_eP}^2=\frac{\overline{XP}^2}{4}= \frac{ \overline{PY} \cdot \overline{PZ}}{4}=\frac{ \overline{IY}^2-\overline{PI}^2}{4} \Longrightarrow 4 \cdot \frac{ \overline{G_eP}^2}{\overline{IY}^2}+\frac{\overline{PI}^2}{\overline{IY}^2}=1.$

This means that $G_e$ moves on the ellipse with pedal circle $(I),$ focal axis $YZ$ and semi-minor axis length $\frac{_1}{^2}IY.$ Hence, in the original figure, $G_e$ moves on an ellipse $\mathcal{E}$ tangent to $\mathcal{L}_b,\mathcal{L}_c$ at $Y,Z,$ since $G_e$ is always an ordinary point (not at infinity), consequently, $G_e$ will be the intersection $\mathcal{E} \cap r.$ Two arbitrary tangents $\mathcal{L}_1$ and $ \mathcal{L}_2$ to $(I)$ determine two points $G_1$ and $G_2$ lying on $\mathcal{E},$ namely the Gergonne points of $\triangle (\mathcal{L}_b,\mathcal{L}_c,\mathcal{L}_1)$ and $\triangle (\mathcal{L}_b,\mathcal{L}_c,\mathcal{L}_2).$ Using the [b]Construction 1[/b], we locate the axes and foci of the ellipse passing through $Y,Z,G_1,G_2$ tangent to $\mathcal{L}_b$ and subsequently,  using the [b]Construction 2[/b], we find the intersections $G_e \equiv \mathcal{E} \cap r$ $\Longrightarrow$ $B \equiv YG_e \cap\mathcal{L}_c$ and $C \equiv ZG_e \cap\mathcal{L}_b,$ which completes $\triangle ABC.$ Note that $r$ and $\mathcal{E}$ have at most 2 intersections, which, in general, yields two possible triangles $\triangle ABC.$


How many ordered sets of positive integers $ (w,x,y,z)$ satisfy $ w\plus{}x\plus{}y\plus{}z\equal{}12$?

This is not necessarily a partition problem. For instance, in this problem the pair $ (1, 1, 1, 9)$ is distinct from $ (9, 1, 1, 1)$, whereas in counting partitions it is not.

[hide]
The way to do this problem is to set up a one-to-one correspondence with something easy to count. This type of problem is known as balls and urns, and is found in AoPS Volume II. We set up a correspondence with $ 0$s and $ |$. The number of $ 0$s between two $ |$ is the number of the value. For instance, $ 000|00\parallel{}0000000$ corresponds to $ (3, 2, 0, 7)$. Notice three are $ 13$ places to place the |. However, it asks for positive integers, so $ 0$ may not be an option. To solve this we simply place by default a $ 0$ in each unit, and therefore subtracting $ 4$ from the total number of places we may place a $ |$. So we need to count the total number of places we may place 3 $ |$ in $ 9$ spaces. This is $ \binom{9}{3} \equal{} 84$.
[/hide]

[hide]
There are 12 items and 3 markers will separate the 12 items into 4 groups. Since each group must have at least one object, there are 11 spaces to put the marker. $ 00$^$ 0000$^$ 00000$^$ 0$ is one example. Therefore there are $ \binom{11}{3}$ solutions. The general number of solutions for $ x_1 \plus{} x_2 \cdots x_k\equal{} m$ in positive integers is $ \binom{m\minus{}1}{k\minus{}1}$
[/hide]

[hide]Balls and urns, but each urn needs 1 ball.
$ \frac{11!}{3!8!}$[/hide]

[hide]
Note that there is a one-to-one correspondence between the solutions to $ w + x + y + z = 12$ in ${ \mathbb{Z}^ + }$ and the solutions to $ w + x + y + z = 8$ in ${ \mathbb{Z}^ + _0}$. The latter is much easier to count using the "divider" argument; if there are 8 balls to place in 4 urns with no restrictions, then we simply find all permutations of "$ oooooooo | | |$", which is $ \frac {11!}{8!3!} = \binom{11}{3}$.

This also leads to the generalization that RisingStar noted:
Each solution in positive integers to $ \displaystyle\sum_{i=1}^kx_i=m$ corresponds to a solution in non-negative integers to $ \displaystyle\sum_{i=1}^kx_i=m-k$. Thus we need to permute $ m-k$ balls and $ k-1$ dividers, which gives $ \binom{m-1}{k-1}$.
[/hide]


probability
geometry
inequalities
analytic geometry

theone853-11
Tare-7
MagnusRex-2
notfunny/confuted,leeyuhang/frodo-1

1. A baseball player gets on average 4 hits out of every 10 times at bat.  (Therefore the probability for a hit is 0.400)  The player gets 2 at bats in a game.  What is the probability that he will get at least 1 hit in a game?

2. In the school band 5 children each own their own trumpet.  In how many different wyas can exactly 3 of the 5 children take home the wrong trumpet while the other 2 take home the right trumpet?

3. (a + b) (a^-1 + b ^-1)^-1=
a.) (a + b)^2
b.)1/(ab)
c.) 1
d.) ab
e.) none of the above

4. What is the area of the region in cartesian plane whose points satisfy the inequality |x| + 2|y| less than or equal to 2?

5. A box contains a uniform mixture of 6 quarts of oats and 9 of corn, and another box contains a uniform mixture of 6 quarts of oats and 2 of corn.  If x is the number of quarts to be taken from the first box, and y is the number of quarts to be taken from the second box in order to obtain a mixture of 7 quarts that is half oats and half corn then what does x equal and what does y equal?

1) [hide].4 + .6*.4 = .64[/hide]

2) [hide](5*4)(3*2) = 20*6=120[/hide]

3) [hide](a+b)/(1/a+1/b) = (a+b)/((a+b)/ab) = ab[/hide]

edit: crud, I knew I should have hit submit after each sol'n

MagnusRex gets #3.

Incorrect for #1

Tare incorrect #2

#4 & #5 still out there.  I'll check back later...

5. Aren't there many solutions? Is your answer 7/2?

5) x=4 y=3?  There might be various answers to this, or is the answer unique, topper?

I'm convinced there's only one solution. It's equivalent to solving the system [hide]2/5 x + 3/4 y = 7/2, x + y = 7[/hide], which yields x = [hide]5[/hide] and y = [hide]2[/hide].

I agree with Osiris. Maybe some of you have misread the question?

ah, yes. I misread; I ignored that they were mixed  :shock:

MagnusRex gets #4
Theone gets #5

After 5 rounds...

theone853-12
Tare-7
MagnusRex-5
confuted-2
leeyuhang, notfunny, frodo-1 each

Thanks to all for providing solutions and everyone who also gave input on problems with more than one answer posted.

I'll start Edition 7 in 10 minutes


hi every body
i want to put a question, and i wish that [u][b]more experienced problem solvers[/b][/u] advise me what to do.
i love doing olympiad problems but i have also lots of homework of the "official maths" and physics, so how can i become a very good problem solver and at the same time maintain a high level at "official" studies at school :(  :?
Can you tell for example your experiences ?

[quote="rrusczyk"]My experience was that once I became a very good problem solver, my 'regular' math and science classes became very easy.  I highly recommend younger students, particularly, to focus more on problem solving rather than accelerating through the curriculum.  The problem solvers will run down and exceed the accelators in due time.[/quote]

Thank you very much
i appreciat your idea
but what's other probleme solvers view?

What rrusczyk wrote is very very true.  If you basically know your stuff, and concentrate on the problem solving, the other less interesting school math becomes easy.  Then again, if it's a question of homework, well, I know this sounds generic, but managing your time can do wonders for you!

BTW...bad advice but I find the break before classes is useful for those last few questions you didn't do cuz you found a cool math problem on AoPS instead...

[quote="Al-Khawarizmi"]To M Valentin Vornicu, can you say something?[/quote]Hmm, I don't think I really have much to add besides what Richard already said above :) Do more problem solving and you will automatically feel the benefits in other parts of science ;)

Ok, I will try to apply your advise, thanks :)

[quote="rrusczyk"]My experience was that once I became a very good problem solver, my 'regular' math and science classes became very easy.  I highly recommend younger students, particularly, to focus more on problem solving rather than accelerating through the curriculum.  The problem solvers will run down and exceed the accelators in due time.[/quote]

I am so sorry :blush: , i did not know you are thr author of "AoPS"
But after reading your articles, i am now more convinced than you do :lol:  that extracurriculum math is the real math ;)  thanks


number theory
Diophantine equation
number theory solved

Solve the following diophantine equation:

x^2-xy+2y^2=0, if (x,y)=1, x>y, x and y cannot be both odd or even.

thank you very much.

Well,this problem is clearly wrong,since:
[tex] x^2-xy+2y^2>0 ,\forall x,y [/tex]


geometry
parallelogram
rotation
geometric transformation
reflection
combinatorics proposed
combinatorics

Show that for every convex polygon whose area is less than or equal to $1$, there exists a parallelogram with area $2$ containing the polygon.

Let $ABCD$ be a parallelogram which contains our polygon $\mathcal P$ and which has minimal area (by a compactness argument we can prove that such a parallelogram does indeed exist).

Let $PQ$ be the segment along which $\mathcal P$ intersects $AB$, with $Q$ between $P$ and $B$ ($P$ and $Q$ can coincide), and let $RS$ be the segment along which $\mathcal P$ intersects $CD$, with $S$ between $R$ and $D$. Suppose the line $\ell_Q$ through $Q$ parallel to $AD$ cuts $CD$ strictly between $R$ and $D$. Then keep the lines $AD,BC$ fixed, and slightly rotate $AB$ around $Q$ such that $B$ moves into the segment $BC$. At the same time, rotate $CD$ around $R$ so as to keep it parallel to $AB$. Then the distance between the lines $AD,BC$ remains fixed, but the sides on $AD,BC$ of the new parallelogram $ABCD$ are shorter, contradicting the minimality of the area of the initial parallelogram.

The same happens if we assume that the line $\ell_P$ through $P$ parallel to $AD$ cuts $CD$ strictly between $S$ and $C$. This means that there is a line parallel to $AD$ which cuts $AB,CD$ in the points $X_{AB}\in[PQ],X_{CD}\in[RS]$. In the same way we show that there is a line parallel to $AB$ which cuts $AD,BC$ in the points $X_{DA},X_{BC}$ belonging to the polygon. The area of $\mathcal P$ is at least the area of the parallelogram $X_{AB}X_{BC}X_{CD}X_{DA}$, and this is precisely half the area of $ABCD$.

It clearly suffices to show that a parallelogram exists such that it contains the polygon, and has area twice or less the area of the polygon.

If the polygon is a triangle, reflect it on the midpoint of one of its sides, join both triangles, you have a parallelogram that contains the triangle with area exactly twice the area of the triangle.

If the polygon has $4$ or more sides, consider the quadrilateral with maximum area formed by four of its vertices, call it $ABCD$ (which is actually the polygon if the number of sides is $4$).  Draw parallels to its diagonal $AC$ through $B$ and $D$, and parallels to its diagonal $BD$ through $A$ and $C$.  This parallelogram contains completely the polygon inside it, since otherwise wlog a vertex $V$ would exist farther than $A$ from diagonal $BD$ and on the same side of $BD$, but then $VBCD$ would have area larger than $ABCD$, contradiction.  The area of the parallelogram is exactly twice the area of $ABCD$, hence at most twice the area of the polygon with equality iff $ABCD$ is the polygon.


I thought this should also go here. The Indian team for IOI 2005 is:
Ks hitij Bansal
Arnold Joseph Noronha
Preyas Popat
Harpreet Singh (me)

For those who don't know IOI is International Olympiad in Informatics. IOI 2005 will be held in Nowy Sacz, Poland from 18th to 25th of August. This is the 4th time India is competing in the IOI. For information on the team selection process go to [url]http://www.iarcs.org.in/inoi[/url].

Does anyone know Greece team.I mean the members that are going to participate at IOI this year. :?:

can u tell me where preyas popat is reading?? :?:

Preyas as well as Arnold (the only two passing out of school this year) have joined Chennai Mathematical Institute.

You can find all the teams here: [url]http://www.ioi2005.pl/olympiad/whoiswho/delegations.php[/url]

Harpeet  congrats!~. Hope you have lot of fun in Poland and wish you and the whole team  the best. Please do keep us posted.

[quote="#include<math>"]
For those who don't know IOI is International Olympiad in Informatics. IOI 2005 will be held in Nowy Sacz, Poland from 18th to 25th of August. This is the 4th time India is competing in the IOI. For information on the team selection process go to [url]http://www.iarcs.org.in/inoi[/url].[/quote]

I checked the site.. what exactly is the process of going for IOI? Is it via school?

The Indian team got 2 silvers and 2 bronze. India's scores were (from 600):

Ks hitij Bansal, 420 (170+250), Silver
Harpreet Singh, 400 (230+170), Silver
Preyas Popat, 356 (165+191), Bronze
Arnold Joseph Noronha, 328 (170+158), Bronze

Cutoffs were: Gold: 496, Silver: 393, Bronze: 275

There were 4 perfect scores. You can find the detailed scores of all medallists here: [url]http://www.ioi2005.pl/competition/results/medalists.php[/url]

coolamit: Sorry for the late reply. Yes, usually you would enroll via your school. However, if your school doesn't have any such information and you are interested, you could probably mail the coordinators (as given on the website) and find out what to do.

Harpreet.

Can someone please tell about the procedure (with dates/where to register/what books to do/ what to practice/which language to learn etc) for getting to the IOI from India???

Thanks!!!

hey happy(include<maths>), cool that u r out here.what a coincidence!


Hello everyone,
So who got the best ranks in JEE2008 this time? :)
ANy news about the top ten!

It seems out of the top 10, 7 are from Bansal and also there's speculation that Shi-tikant is the topper (Bansal Classes)
See more updates here: http://iit-redefined.zzl.org/viewtopic.php?f=34&t=448

[quote="madness"]It seems out of the top 10, 7 are from Bansal and also there's speculation that - is the topper (Bansal Classes)
See more updates here: http://iit-redefined.zzl.org/viewtopic.php?f=34&t=448[/quote]
Dear madness,
what is this new forum,for which you gave the link?
Kindly inform me about this.

Its a new forum created by pardesi here for iit and olympiads :)