linear algebra
matrix
probability
IMO Shortlist
algebra
combinatorics

Consider a matrix of size $n\times n$ whose entries are real numbers of absolute value not exceeding $1$. The sum of all entries of the matrix is $0$. Let $n$ be an even positive integer. Determine the least number $C$ such that every such matrix necessarily has a row or a column with the sum of its entries not exceeding $C$ in absolute value.

[i]Proposed by Marcin Kuczma, Poland[/i]

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

:D ,ans. n/2,construction is easy,and to prove ans i use ideas of sub. desciption

Let $ n \equal{} 2k$, and let $ a_{ij}$ be the entry in the $ i$th row and $ j$th column. Then we claim that $ C \equal{} k$. We know that $ C \ge k$, since we can set $ a_{ij}$ to be 1 if $ i, j \le k$, -1 if $ i, j > k$, and 0 otherwise; this construction has every row and column sum having absolute value $ k$.

We will now show that $ C \equal{} k$ works. Suppose for sake of contradiction that we have a matrix whose row and column sums all have absolute value more than $ k$. WLOG we can assume that the first $ a$ row sums and first $ b$ column sums are positive, while the last $ 2k \minus{} a$ and $ 2k \minus{} b$ row and column sums are non-positive (this can be achieved simply by a permutation of the rows and columns). Furthermore, we can assume that $ a \plus{} b \ge 2k$, or else we may exchange $ a$ and $ b$ with $ 2k \minus{} a$ and $ 2k \minus{} b$ and flip all signs.

Define

$ P \equal{} \sum_{i \le a, j \le b} a_{ij}$;

$ N \equal{} \sum_{i > a, j > b} a_{ij}$;

$ X \equal{} \sum_{i \le a, j > b} a_{ij}$;

$ Y \equal{} \sum_{i > a, j \le b} a_{ij}$.

Since $ P \plus{} X$ is the sum of the first $ a$ row sums, it is strictly greater than $ ka$. Since $ P \plus{} Y$ is the sum of the first $ b$ column sums, it is strictly greater than $ kb$. Therefore,

$ P \plus{} X \plus{} P \plus{} Y > k(a \plus{} b)$.

Noting that $ P \plus{} X \plus{} Y \plus{} N \equal{} 0$, we have

$ P \minus{} N > k(a \plus{} b)$.

There are only $ ab$ entries in the sum by which we calculate $ P$, and there are only $ (2k \minus{} a)(2k \minus{} b)$ entries for the sum for $ N$. Thus,

$ k(a \plus{} b) < P \minus{} N \le ab \plus{} (2k \minus{} a)(2k \minus{} b)$
$ k(a \plus{} b) < 4k^2 \minus{} 2k(a \plus{} b) \plus{} 2ab$
$ 0 < 4k^2 \minus{} 3k(a \plus{} b) \plus{} 2ab$
$ k^2 < 9k^2 \minus{} 6k(a \plus{} b) \plus{} 4ab \equal{} (3k \minus{} 2a)(3k \minus{} 2b)$
$ 4k^2 < (6k \minus{} 2a \minus{} 2b)^2 \le (2k)^2 \equal{} 4k^2$,

a contradiction. (Recall that $ 4k \ge a \plus{} b \ge 2k$).

Let $n=2k$, then $C=k$. Construction is easy, so let's prove it.

In this solution, include 0 in positive numbers.
When $k=1$, there exists a row or a column where the two entries have opposite sign. If not, all entries must have the same sign and they must all be 0, which is a trivial case. Sum of two opposite numbers where each has absolute value not bigger than 1 yields a number also having absolute value not bigger than 1.
Here, notice that if we have one column not bigger than 1 in absolute value, the other column also satisfies this.

If $k>1$
let the matrix be $M$.
first, since switching rows or columns does not affect the problem, switch the order of rows and the order of columns so that both row sums and column sums are arranged biggest to smallest. (row sum : sum of entries in the row, column sum : sum of entries in the column)
Now let
$A= \sum_{1 \leq i,j \leq k} a_{ij}, B= \sum_{1 \leq i \leq k < j} a_{ij}, C= \sum_{1 \leq j \leq k<i} a_{ij}, D= \sum_{i, j>k} a_{ij}$,
and make a 2-by-2 matrix $M'$ with entries $A, B, C, D$, i.e., merge the four k-by-k squares in $M$.
Note that $|A|, |B|, |C|, |D| \leq k^2$ and $A+B+C+D=0$, so considering the $\frac{1}{k^2} M'$, by the result of case when $k=1$, we can assume $|A+C| \leq k^2$ and $|B+D| \leq k^2$, i.e. the sum of the column sums of first half columns and second half columns of $M'$ does not exceed $k^2$.
Since the column sums were arranged biggest to smallest, either all column sums are positive in the first half or all column sums are negative in the second half. Let it be the first half since we can consider $-M$ if it was not the case.
k column sums have sum smaller than $k^2$, so one of them must be smaller than $k$, and since it's positive, it's absolute value is smaller than k.

[quote=orl]Consider a matrix of size $n\times n$ whose entries are real numbers of absolute value not exceeding $1$. The sum of all entries of the matrix is $0$. Let $n$ be an even positive integer. Determine the least number $C$ such that every such matrix necessarily has a row or a column with the sum of its entries not exceeding $C$ in absolute value.
[/quote]
Divide the matrix into four $n/2 \times n/2$ quarters. Fill the top left with $1$s, the top right and bottom left with $0$s and the bottom right with $-1$s. Thus we get $C \ge n/2.$
We now show that $C=n/2.$ Assume on the contrary that there exists a matrix $A=(a_{ij})_{i,j=1}^n$ such that every row and column sum is either greater than $n/2$ or less than $-n/2.$ Let $R_i$ represent the $i$ th row sum and $C_i$ the $i$ th column sum. Permute the rows so that all the "positive" rows are on the top of the "negative" rows. Represent the positive ones by $R^+$ and negative by $R^-.$ Similarly permute the columns. Also, let $|R^+|$ denote the number of positive rows while $|R^-|$ the negative.
Note that the sum $=0$ condition implies that the sum of the positive rows equals the magnitude of the sum of the negative rows.

[b]Claim:[/b] $|R^+|=|R^-|=n/2.$ Similarly $|C^+|=|C^-|=n/2$.
[i]Proof:[/i] If $|R^+|>n/2,$ then $|R^-|<n/2.$ Note that $R^+>n/2$ and $-n \le R^- <-n/2$ by our assumption. Hence
$$\left |\sum R^- \right | \le \frac{n}{2}|R^-|<\frac{n^2}{4} < \frac{n}{2} |R^+|<\sum R^+$$
a contradiction. The other case is similar. $\square$

Note that sum of all the elements is given by the sum of the top $n/2$ rows and left $n/2$ colums, minus the top left $n/2 \times n/2$ square (which is double counted before) plus the bottom right $n/2 \times n/2$ square. These top rows and left colums have a positive sum by the claim, while the latter two have the maximum, minimum value when all the member are $1, -1$ respectively. Hence
Thus,
\begin{align*}
\sum_{i,j} a_{ij} =\sum_{i<n/2} R_i+\sum_{i<n/2} C_i +\sum_{i,j>n/2} a_{ij} -\sum_{i,j<n/2} a_{ij} >\left( \frac{n}{2} \right) \left( \frac{n}{2} \right)+\left( \frac{n}{2} \right) \left( \frac{n}{2} \right)-\frac{n^2}{4}-\frac{n^2}{4}=0
\end{align*}
a contradiction. $\blacksquare$

[b]Edit:[/b] As pointed out below, this solution has a fault; the lemma is wrong. I believe that it can be fixed, but I am yet to try it.

[quote=Wizard_32][quote=orl]Consider a matrix of size $n\times n$ whose entries are real numbers of absolute value not exceeding $1$. The sum of all entries of the matrix is $0$. Let $n$ be an even positive integer. Determine the least number $C$ such that every such matrix necessarily has a row or a column with the sum of its entries not exceeding $C$ in absolute value.
[/quote]
Divide the matrix into four $n/2 \times n/2$ quarters. Fill the top left with $1$s, the top right and bottom left with $0$s and the bottom right with $-1$s. Thus we get $C \ge n/2.$
We now show that $C=n/2.$ Assume on the contrary that there exists a matrix $A=(a_{ij})_{i,j=1}^n$ such that every row and column sum is either greater than $n/2$ or less than $-n/2.$ Let $R_i$ represent the $i$ th row sum and $C_i$ the $i$ th column sum. Permute the rows so that all the "positive" rows are on the top of the "negative" rows. Represent the positive ones by $R^+$ and negative by $R^-.$ Similarly permute the columns. Also, let $|R^+|$ denote the number of positive rows while $|R^-|$ the negative.
Note that the sum $=0$ condition implies that the sum of the positive rows equals the magnitude of the sum of the negative rows.

[b]Claim:[/b] $|R^+|=|R^-|=n/2.$ Similarly $|C^+|=|C^-|=n/2$.
[i]Proof:[/i] If $|R^+|>n/2,$ then $|R^-|<n/2.$ Note that $R^+>n/2$ and $-n \le R^- <-n/2$ by our assumption. Hence
$$\left |\sum R^- \right | \le \frac{n}{2}|R^-|<\frac{n^2}{4} < \frac{n}{2} |R^+|<\sum R^+$$
a contradiction. The other case is similar. $\square$

Note that sum of all the elements is given by the sum of the top $n/2$ rows and left $n/2$ colums, minus the top left $n/2 \times n/2$ square (which is double counted before) plus the bottom right $n/2 \times n/2$ square. These top rows and left colums have a positive sum by the claim, while the latter two have the maximum, minimum value when all the member are $1, -1$ respectively. Hence
Thus,
\begin{align*}
\sum_{i,j} a_{ij} =\sum_{i<n/2} R_i+\sum_{i<n/2} C_i +\sum_{i,j>n/2} a_{ij} -\sum_{i,j<n/2} a_{ij} >\left( \frac{n}{2} \right) \left( \frac{n}{2} \right)+\left( \frac{n}{2} \right) \left( \frac{n}{2} \right)-\frac{n^2}{4}-\frac{n^2}{4}=0
\end{align*}
a contradiction. $\blacksquare$[/quote]

i feel there is a flaw in ur solution.why is |R+| and |R-| same. i feel that this is not always true

[quote=Wizard_32]The [i]number[/i] of rows with positive sum is equal to the [i]number[/i] of rows with negative sum. I guess you got confused about the notation.

If you find a flaw or a counterexample, then kindly let me know.[/quote]

i feel u messed up with the inequality of sigma|R-| to prove that the sum of matrix is not zero
actually the max value of mod of the sum negative row is n but u have took it as n/2 so the inequality condition goes wrong

We claim that $C=\tfrac{N}{2},$ achieved by splitting the matrix into the four equal square submatrices $\begin{pmatrix}0 & 1 \\ -1 & 0\end{pmatrix}.$

Note that we can permute the rows and columns such that only the first $w$ columns and the first $y$ columns have positive sum. Let $x=N-w,z=N-y.$ Let the corresponding sums of the entries in each region be $W,X,Y,Z$ as shown:

[asy]
size(6cm);
draw((0,0)--(5,0)--(5,5)--(0,5)--(0,0));
draw((2.7,0)--(2.7,5));
draw((0,2.1)--(5,2.1));
label("$w$",(0,5)--(2.7,5),N);
label("$x$",(2.7,5)--(5,5),N);
label("$y$",(0,5)--(0,2.1),W);
label("$z$",(0,2.1)--(0,0),W);
label("$W$",(1.35,3.55));
label("$X$",(3.85,3.55));
label("$Y$",(1.35,1.05));
label("$Z$",(3.85,1.05));
[/asy]
So we easily get
\[W+Y\geq wC,\ X+Z\leq -xC,\ W+X\geq yC,\ Y+Z\leq -zC.\]
But for instance $X+Z\leq -xC\implies W+Y\geq xC,$ and similar inequalities give
\[W+Y\geq \max(w,x)C,\ W+X\geq \max(y,z)C,\ Y+Z\leq -NC+\min(y,z)C,\ X+Z\leq -NC+\min(w,x)C.\]
Summing in pairs, we get
\[2W+X+Y\geq C(\max(w,x)+\max(y,z))\geq C(\max(w,x)-\min(w,x)+\max(y,z)-\min(y,z))+2NC+X+Y+2Z\]
and the extreme inequalities gives
\[2(W-Z)\geq C(|w-x|+|y-z|+2N).\]
But $W-Z\leq wy+xz=wy+(N-w)(N-y)$ and $|w-x|+|y-z|=|2w-N|+|2y-N|,$ so we get
\[wy+(N-w)(N-y)\geq C(|2w-N|+|2y-N|+2N).\]
This rearranges to
\[(2w-N)(2y-N)+N^2\geq C(|2w-N|+|2y-N|+2N).\]
Finally, noting that $(2w-N)(2y-N)\leq |(2w-N)(2y-N)|$ and letting $a=|2w-N|,b=|2y-N|,$ we get
\[C\leq \frac{ab+N^2}{a+b+2N}\qquad (\spadesuit).\]
We show that $\tfrac{ab+N^2}{a+b+2N}\leq \tfrac{N}{2}.$ This is equivalent to $(2a-N)(2b-N)\leq N^2,$ which is true since
\[-N\leq 2w-N,2y-N\leq N\implies 0\leq a,b\leq N\implies -N\leq 2a-N,2b-N\leq N.\]
Thus we conclude $C\leq \tfrac{N}{2}$ from $(\spadesuit).$

The answer is $\tfrac{n}2$ with every in the top left quadrant $1$, all bottom right quadrant $-1$ and the rest are zero.

Assume on the contrary that we can have every row/column sum greater than $\tfrac{n}2$ or less than $-\tfrac{n}{2}$. We can rearrange rows and columns so arrange them in descending order from left to right, from top to bottom. Let $A$ be sum of top left quadrant, $B$ be top right, $C$ be bottom left, $D$ be bottom right.

WLOG suppose there are as many positive-summed rows as negative-summed ones, so the region of $A+B$ has all positive rows sums, so $A+B\ge \tfrac{n^2}{4}$. Since each column in the region $A+B$ sums to at most $\tfrac{n}2$, there are at least $\tfrac{n}2$ nonnegative sums. If the sum is nonnegative no amount of negative numbers can make the entire column a negative enough sum. Thus, $A+C\ge \tfrac{n^2}{4}$.

We have
\[n^2=A+B+C+D=(A+B)+(A+C)-(A-D)> \frac{n^2}{4}+\frac{n^2}{4}-(A-D)\]
so $A-D> \tfrac{n^2}{2}$, absurd.

[quote=Ali3085]let $n=2k$
we claim thet the answer $k$
the construction is easy
we will prove that $C=k$ work
WLOG let the first $x$ row are positive the next $y$ are negative and do the same for columns as the picture
[asy]
size(6cm);
draw((0,0)--(5,0)--(5,5)--(0,5)--(0,0));
draw((2.7,0)--(2.7,5));
draw((0,2.1)--(5,2.1));
label("$w$",(0,5)--(2.7,5),N);
label("$z$",(2.7,5)--(5,5),N);
label("$x$",(0,5)--(0,2.1),W);
label("$y$",(0,2.1)--(0,0),W);
[/asy]
[color=#f00][u][b]lemma: [/b][/u][/color]if we have a matrix $2 \times 2$ and $|a_{ij}| \le m$ and the sum of all entries is zero thene there exists a row or column with the sum of its entries not exceeding $m$ in absolute value.
it's obvious
$\blacksquare$
now split the matrix into four identical matrices
[asy]
size(6cm);
draw((0,0)--(5,0)--(5,5)--(0,5)--(0,0));
draw((2.5,0)--(2.5,5));
draw((0,2.5)--(5,2.5));
label("$W$",(1.35,3.55));
label("$X$",(3.85,3.55));
label("$Y$",(1.35,1.05));
label("$Z$",(3.85,1.05));
[/asy]
from the lemma suppose $|W+X| \le k^2$ but $W+X=-Y-Z \implies |Y+Z| \le k^2$
if $x>k$ then we're done from the PHP becuase $r_1+r_2....r_{k} \le k^2$
if $x < k$ then $ y >k$ just do the same
and we win :D[/quote]

I believe that it is not true that all quadrants have sum less than k^2.

your brain on smoothing

The answer is $n/2$, achieved by splitting the matrix into four $n/2 \times n/2$ submatrices and filling the top left with $1$ and the bottom right with $-1$. We now show that $C>n/2$ is impossible.

Suppose that there was some $n \times n$ matrix with every row/column having absolute value greater than $n/2$. Since every row/column also has absolute value at most $n$, it follows that there are at least $n/3$ rows with positive sum, and at least $n/3$ rows with negative sum (same for columns).

Now WLOG permute the matrix so that the rows are sorted in decreasing order from top to bottom, and the columns are sorted in decreasing order from left to right. Consider the top-left region, formed by the intersection of the positive rows and positive columns. If some entry in this region is not $1$, but we can find some other entry in its row lying in the top-right region, formed by the intersection of the positive rows and the negative columns, which is not $-1$, then we can increase the first entry and decrease the second at the same rate until some entry's absolute value reaches $1$: this clearly does not affect the minimum absolute value of any row/column nor change the signs of any row/column, and the sum of matrix entries should be the same, so we may apply this smoothing operation freely until we cannot (clearly this will terminate).

When this process terminates, I claim that the entire top-left region is filled with $1$s. Indeed, if there is still some term in the top-left region which is less than $1$, then all the terms in its row which are in the top-right region must be $-1$. Since there are at least $n/3$ columns in this top-right region, it follows that the sum of the term's row is at most $-n/3+2n/3<n/2$, and since it must be positive by definition we obtain a contradiction.

We may repeat the same process with the bottom-right and bottom-left region, so now suppose the top-left and bottom-right regions are filled with $1$'s and $-1$'s respectively. Let $a,b$ be the number of rows and columns respectively in the top-left region, and WLOG suppose that $a+b \geq n$ (otherwise apply the same argument to the bottom-right). Suppose the sum of values in the top-right region and bottom-left region are $x,y$ respectively. By expectation, we should have
$$b+\frac{x}{a}>\frac{n}{2} \implies x>\frac{na}{2}-ab \text{ and } a+\frac{y}{b}>\frac{n}{2} \implies y>\frac{nb}{2}-ab.$$
On the other hand, since the sum of the terms in the matrix is $0$, we should have
$$x+y=(n-a)(n-b)-ab=n^2-na-nb \implies n^2-na-nb>\frac{na}{2}+\frac{nb}{2}-4ab\geq \frac{n(a+b)}{2}-(a+b)^2 \implies (2n-(a+b))(n-(a+b))>0,$$
where we use $(a+b)^2 \geq 4ab$ (AM-GM), but this is clearly impossible for $2n\geq a+b \geq n$: contradiction. $\blacksquare$

Let $n=2k$(why is the problem not phrased this way lol). Then the answer is $\boxed{k}$, achieved by the top left quarter grid filled with $1$s and bottom right quarter grid filled with $-1$s.

Now suppose that we could achieve $C>k$. Then at least $k$ of the rows must have the same sum(by pigeonhole). WLOG assume these are positive and the first $k$ rows. Since the sum of these rows is greater than $k^2$, at least $k$ of these columns have their first $k$ rows sum up to a positive number(since each is at most $k$). But since each column has absolute value at least $C$, this means that those $k$ columns have a positive sum(they don't have eonugh cells to get to $-k$). Assume WLOG that these columns are the first $k$ columns.

Now consider the sum of the entire grid. The top half and the left half of the board are both greater than $k^2$, but by PIE their intersection and the outside can change the sum by at most $k^2$, meaning that the sum of the board is positive, contradiction. $\blacksquare$


you all remember the old boys vs girls game. click here is you dont:[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?t=293724[/url]

anyway, this is the boys vs girls game, but instead of adding 1 or subtracting 1, you are going to subtract how many stars you have (dont know what they are called), like the new members have 0 stars, yang-mills theory have 3, etc. if you are a girl, you subtract how many stars you have from the total. if you are a boy, you add how many stars you have.

new members can add 1 star.

if you have half stars, round up.

i will start from 25

25

wait, i guess i have 2.5 stars?

26.5

ill edit my first post

46

The message is too small. Please make the message longer before submitting.

once again, an unfair game...

more girls than boys! :(

Let's try again

u mean more boys than girls. ok, i'll be starting a new topic. lets play to 5. boys 1, girls 0

whoops... yeah, thats wut i meant! :oops:


abstract algebra
function
Support
inequalities
group theory
linear algebra
triangle inequality

Let $G$ be a finite abelian group, and let $\hat{G}$ denote the dual group of $G$ consisting of the linear complex characters of $G$ (i.e. the group homomorphisms $\chi : G \to \mathbb{C}^{\times}$). If $f : G \to \mathbb{C}$ is any complex-valued function on $G$, we may define the Fourier transform $\hat{f} : \hat{G} \to \mathbb{C}$ by
\[
\hat{f} (\chi ) := \frac{1}{|G|} \sum_{g \in G} f(g) \chi (-g).
\]
Denote by $\mathrm{supp} \, (f) := \{x \in G \mid f(x) \neq 0\}$ the support of $f$.

Problem. If $f \neq 0$ is not identically zero, show that
\[
|\mathrm{supp} \, (f)| \cdot |\mathrm{supp} \, (\hat{f})| \geq |G|.
\]

Enjoy!  ;)

--Vesselin

By the way, Vesselin, I'm the one who moved it over here. Since I was planning to answer it with analysis arguments, I didn't think it belonged in algebra. I'd also like to see "advanced fields" get more use, anyway.

A little background information: The set of all characters is itself a group. Call the group of characters $\hat{G}.$ The characters are orthogonal and span the set of functions on $G,$ so as a matter of linear algebra, $|G|=|\hat{G}|.$

In his definition of the Fourier transform, Vesselin wrote $\chi(-g).$ This could have been said in several other ways: $\chi(-g)=(\chi(g))^{-1}=\overline{\chi(g)} =\chi^{-1}(g)$ where by $\chi^{-1}$ I mean the group inverse in $\hat{G}.$

The orthogonality of the characters leads to the Plancherel theorem:

$\frac1{|G|}\sum_{g\in G}|f(g)|^2=\sum_{\chi\in \hat{G}}|\hat{f}(\chi)|^2.$

Futhermore, we can say just as a matter of the triangle inequality that

$\forall\chi\in \hat{G},$ $|\hat{f}(\chi)|\le\frac1{|G|}\sum_{g\in G}|f(g)|.$

Write $||f||_p=\left(\frac1{|G|}\sum_{g\in G}|f(g)|^p\right)^\frac1p$ for functions on $G.$ Out of deference to the different normalization, I'll refrain from this notation on $\hat{G},$ except that I will use $||\hat{f}||_{\infty}$ on $\hat{G}.$ The two theorems above can then be expressed as:

$||f||_2^2=\sum_{\chi\in \hat{G}}|\hat{f}(\chi)|^2$ and $||\hat{f}||_{\infty}\le||f||_1.$

(Continued in next post)

Proof of the problem:

Assume WLOG that $||f||_2=1.$ (Once we know the function is not the zero function, we may multiply by any nonzero constant without changing any of the supports.)

$||f||_1^2=\frac1{|G|^2}\left(\sum_{g\in\, \mathrm{supp}\,(f)}|f(g)|\right)^2 $

$\le\frac1{|G|^2}\cdot |\mathrm{supp}\,(f)|\cdot\sum_{g\in \,\mathrm{supp}\,(f)}|f(g)|^2$

(using the Cauchy-Schwarz inequality)

But $\frac1{|G|}\sum_{g\in \,\mathrm{supp}\,(f)}|f(g)|^2=||f||_2^2=1,$ so we have

$||f||_1^2\le\frac{|\mathrm{supp}\,(f)|}{|G|}.$

Now work with the other side of Plancherel's Theorem:

$1=\sum_{\chi\in \hat{G}}|\hat{f}(\chi)|^2= \sum_{\chi\in \,\mathrm{supp}\,(\hat{f})}|\hat{f}(\chi)|^2\le |\mathrm{supp}\,(\hat{f})|\cdot ||\hat{f}||_{\infty}^2$

$\le |\mathrm{supp}\,(\hat{f})|\cdot ||f||_1^2\le \frac{|\mathrm{supp}\,(\hat{f})|\cdot|\mathrm{supp}\,(f)|}{|G|}.$

Hence, $|\mathrm{supp}\,(\hat{f})|\cdot |\mathrm{supp}\,(f)|\ge |G|.$

[quote="Kent Merryfield"]We appear to have equality in this inequality if and only if $f$ is a scalar multiple of the characteristic function of a coset of a subgroup of $G.$[/quote]

Yes.

Actually, as recently discovered by Terence Tao, the inequality can be significally improved in the special case when $G = \mathbb{Z}_p$ is a cyclic group of prime order $p$:

Problem 2.  If $G = \mathbb{Z} / p\mathbb{Z}$ with $p$ prime, and if $f : G \to \mathbb{C}$ is not identically zero, show that
\[
|\mathrm{supp} \, (f)| + |\mathrm{supp} \, (\hat{f})| \geq p+1.
\]
Amazingly, the celebrated Cauchy-Davenport theorem (which was so much discussed on this forum  :lol: ) is a fairly straightforward corollary of this result:

Problem 3. Deduce the Cauchy-Davenport theorem (that $|A+B| \geq \min \{p,|A|+|B|  - 1\}$ for $A,B \subset \mathrm{Z}_p$) from Problem 2.

--Vesselin


inequalities
rearrangement inequality
inequalities unsolved

Help me to prove this inequality for $a,b,c$ are the sides of the triangle ,then:
$9(\frac{a^2}{b}+\frac{b^2}{c}+\frac{c^2}{a})\geq (a+b+c)^2(\frac{1}{a}+\frac{1}{b}+\frac{1}{c})$.

Hey, I managed to get the problem, or so i think, but required me to DA(dumbass it. Anyway, here is a hint
[hide]
if a,b,c are sides of triangle, then you can make the substitutions a = y+x, b = z+x, c = x+y, for x,y,z>0

Hope this helps
[/hide]

Uh-oh, didn't help, here's the solution
[hide]

after you clear the denominators, u can subtract a^3bc, b^3a, and c^3b from both sides, and you can rewrite that expression to: 8a^3c + 8b^3a + 8c^3b >= 5a^2bc + 5ab^2c + 5abc^2 + a^3b + b^3c + c^3a + 2a^2b^2 + 2a^2c^2 + 2b^2c^2. Now, doing the egregious substituion as suggested in the hint, we can tragically deduce the expressiion to be:
8x^4 + 32x^3y + 16x^3z + 24x^2y^2 + 48x^2yz + 24x^2z^2 + 16xy^3 + 48xy^2z + 48xyz^2 + 32xz^3 + 8y^4 + 32y^3z + 24y^2z^2 + 16yz^3 + 8z^4 >= 3x^4 + 16x^3y + 18x^3z + 29x^2y^2 + 62x^2yz + 29x^2z^2 + 18xy^3 + 62xy^2z + 62xyz^2 + 16xz^3 + 3y^4 + 16y^3z + 29y^2z^2 + 18yz^3 + 3z^4.
(I dare you to verify this  :P )

We can subtract the RHS from both sides to obtain something-simpler-but-still-complicated-...-unfortunately, to get:
5x^4 + 16x^3y + 16xz^3 + 5y^4 + 16y^3z + 5z^4>= 2x^3z+5x^2y^2+14x^2yz + 5x^2x^2 + 2xy^3 + 14xy^2z + 14xyz^2 + 5y^2z^2 + 2yz^3.

Now we show the following is true, and adding these up will give the inequality derived above:

2x^4 + 2y^4 + 2z^4 >= 2x^3z + 2xy^3 + 2yz^3 (is true by rearrangement inequality)

3x^4 + 3y^4 + 3z^4 >= 3x^2y^2 + 3x^2z^2 + 3y^2z^2 (is true by rearrangement inequality, or break it down into symmetric AM-GM, whichever you prefer, or Bunchning)

2x^3y + 2y^3z + 2z^3x >= 2x^2y^2 + 2x^2z^2 + 2y^2z^2 (holds by bunching)

14x^3y + 14y^3z + 14z^3x >= 14x^2yz + 14xy^2z + 14xyz^2 (holds by bunching)

[/hide]

Toodles

[quote="RealZeta"]
2x^3y + 2y^3z + 2z^3x >= 2x^2y^2 + 2x^2z^2 + 2y^2z^2 (holds by bunching)[/quote]
But this ineq is not true for all positive x, y, z. :P

Touche Vasc :P

(reworking solution)

Toodles,

When I'm beat, I'm beat, the problem is a little beyond me, yet it seems that I can get it. The expression is partially symettric, but the other half is missing. So I have no clue (dont think Bunching will get anywhere)...maybe a clever work on Schur? Or just coming up with something deviously clever.
It is one of th hardest inequalities i've dealt with.

Im assuming its a chinese olympiad problem?

If I understand you right, you want to show:

$3x^4 + 3y^4 + 3z^4 \geq 3x^2y^2 + 3x^2z^2 + 3y^2z^2$
$2x^3y + 2y^3z + 2z^3x \geq 2x^2y^2 + 2x^2z^2 + 2y^2z^2$

But these are not true on their own. But we can show the following:
$x^4 + y^4 + z^4 \geq x^2y^2 + x^2z^2 + y^2z^2$
$2x^4 + 2y^4 + 2z^4 \geq 2xy^3 + 2yz^3 + 2zx^3$ (rearrangement)
$2x^3y + 2y^3z + 2z^3x + 2xy^3 + 2yz^3 + 2zx^3 \geq 4x^2y^2 + 4x^2z^2 + 4y^2z^2$ (Now it is symmetric and true!)

And add them up ;)


Meh, how about besides search engines.

Hmm... I think, AOPS!!! :D

besides AoPS, my favorite site would have to be [url=http://www.dragongoserver.net]DragonGoServer[/url].

I enjoy reading political blogs.  Two of my favorites are [url=http://atrios.blogspot.com]Eschaton[/url] and [url=http://plumer.blogspot.com]Brad Plumer[/url].  I also read the [url=http://www.ucomics.com/boondocks/]Boondocks[/url] comic strip daily.

Well, since the questions is on AoPS, definently AoPS.


Let $G$ the centroid of a triangle $ABC$ and let a line which passes through $G$ and intersects the lines $AB,\ AC$ at the points $K,L$ respectively .Prove that
$(\frac{BK}{KA})^{4}+(\frac{CL}{LA})^{4}\geq\frac{1}{8}$

What's your proof for $\frac{BK}{KA}+\frac{CL}{LA}=1$  ? :wink:

I known that I need to explain more  :D  :D
Above a forgot the notation of algebraic lengths, here we always use algebraic lengths!
Now let $\frac{\overline{BK}}{\overline{KA}}=x,\frac{\overline{CL}}{\overline{LA}}=y$ then
$x\vec{KA}+\vec{KB}=\vec{0}\Rightarrow \vec{AB}=(x+1)\vec{AK}$
Similar $\vec{AC}=(y+1)\vec{AL}$ but
$\vec{AG}=\frac{1}{3}(\vec{AB}+\vec{AC})=\frac{1}{3}((x+1)\vec{AK}+(y+1)\vec{AL})$
but $G,K,L$ are colinear$\Rightarrow \frac{1}{3}(x+1)+\frac{1}{3}(y+1)=1\Rightarrow x+y=1$
Can you show your solution? :)


Ring Theory
superior algebra
superior algebra unsolved

let (R, m, k) be a commutative noether local ring.
$ p_i$ is prime ideal, not m.(i=1,2,...n)
I is an ideal, not m .
then m$ \nsubseteq$ $ I\cup (\cup_{i\equal{}1}^n p_i)$ ???

By union, do you mean the set-theoretic union or the ideal union, i.e. sum, of two ideals?

of course set-theoretic union is meant.

http://www.math.uiuc.edu/~r-ash/ComAlg/ComAlg0.pdf


search
limit
calculus
integration
logarithms
trigonometry
calculus computations

Sometimes someone appears on this forum asking how to make some computation that have already been done before in an old or recent post. Also, people that often post interesting problems forget or don't know if he/she have already asked that before. It is not also very easy (I think) to make a search in order to find some particular post.
Therefore I think it could be an usefull idea to make a sticky post having some kind of index of computations that have already been done before, together with the link(s) to the corresponding post(s), in order for people interested to find more easily what he/she is looking for. For example, I am thinking in something like the following:

1. Limit Computations

1.1 $ \lim_{n\to\infty}\frac{1^{k}+2^{k}+3^{k}+...+n^{k}}{n^{k+1}}$,  [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=118632]Post1[/url]

1.2 ...

...

2. Integral Calculations

1.1 ...

1.2 ...

...

1.10 $ \int^{\pi /2}_{0}[\ln(\sin x)]^{2}\,dx$, [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=154194]Post1[/url]

...

3. Series Computations

1.1 ...

...

1.6 $ \sum_{n=1}^{+\infty}\frac{\sin n}{2^{n}}$, [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=120999]Post1[/url]

...

What is your opinion about this?

Unfortunately, the list of such computations will be at least 20 pages long (and that is an optimistic estimate), so, despite it may be ordered a bit better than the forum itself, not many people will have enough patience to search through it :(. Besides, proper maintainance of such a list will be a full time job and I do not  know anyone who would wish to spend his/her free time copying the contents of the new posts to that sticky every day. So, my opinion is that this suggestion, despite being quite attractive, is not very practical.

I was only referring to the most common/important computations, not all of them. I also noted that in this forum, contrary to others, we cannot edit a post after some time, which, you are right, its not pratical for that purpose. Anyway, thanks for your opinion.


A driver approaches a toll booth and randomly selects two coins from his pocket. If the pocket contains 2 quarters, 2 dimes, and 2 nickels, what is the probability that the value of the two coins he selects will be at least enough to pay the 30-cent toll? Express your answer as a common fraction.

[hide]
To have 30 cents, the driver needs at least one quarter.
There are ${6 \choose 2}$ ways to pick two coins randomly.
To get two quarters, there is one way.
To get a quarter and a dime, there are $2\cdot2=4$ ways.
To get a quarter and a nickel, there are $2\cdot2=4$ ways.

$\frac{4+4+1}{{6 \choose 2}}=\frac{9}{15}=\boxed{\frac{3}{5}}$[/hide]


[quote="Pascual2005"]Este topic lo cree para quienes esten interesados en la Ibero y quieran saber algo acerca del lugar donde se va a llevar a cabo: Cartagena, Colombia! Ademas de lo que creen pasara alli! Chao![/quote]

Bueno, yo ando bastante desconectado de todo lo que respecta a la Ibero desde que estoy por aqui en el norte, pero... hasta ahora me entero que va a ser en Colombia  :D . En fin, esta bien, veinte aniversario, pues queda genial, la primera (1985, cuando ninguno de los actuales participantes habia tan siquiera nacido) fue en Colombia tambien.

Espero que quienes vayan la disfruten!

Si, este año es el 20 cumpleaños de la ibero y por eso va a estar llena de sorpresas: que se esperan de esta ibero?

Bueno, no se que esperar, pero espero pasarla bien, porque seria mi ultima olimpiada a la que puedo ir :D.

Por cierto, no estara pensando Colombia en tratar de llevar a cabo alguna IMO alli? Digo, en el 2001 la Centro, en el 2005 la Ibero, que tal si en el 2009 la IMO.

Bueno, solo una idea al aire. Ciao,

Pascual es cierto que Cartagena es la ciudad donde mas se festeja en colombia???? eso me dijo una colombiana ahi pero no sabia si era cierto...

Manuel: Si es cierto!

Jimenez: Creo que en el 2001 colombia iba a ser la sede de la IMO, pero problemas legales no lo permitieron, dudo que halla una dentro de poco aca, aunque a mi modo de verlo junto con Brazil son los 2 paises latinos mas probables en hacerla.

Leo: Creame que se va a divertir mucho, y ojala ganarse una dorada para venezuela.

Eso espero yo tambien ;) darle una segunda presea de oro a venezuela en la ibero. Pero eso lo veremos halla, :D

Hola yo solo quisiera saber un poco más sobre el SEMI2005 y si conoce los nombres de los guías le agradeceria q me dijera el de El Salvador! Adios :)

Los nombres de los guías están en la página de la Ibero (pero sin países) quizá alguien sepa algo más.
[quote]Por cierto, no estara pensando Colombia en tratar de llevar a cabo alguna IMO alli? Digo, en el 2001 la Centro, en el 2005 la Ibero, que tal si en el 2009 la IMO.
[/quote]
Y por cierto me parece que la IMO del 2009 ya tiene sede: Frankfurt, Alemania. Creo que la que todavía no se sabe ni qué es la del 2008 pero no estoy seguro.
Sale nos vemos en Cartagena y por cierto: ¿Qué se hace exactamente en el SEMI?
Nos preguntaron si queriamos ir y dijimos que sí. Sabemos que es un seminario de resolución de problemas o algo así pero exactamente ¿cómo se maneja?

Creo que al SEMI 2005 vienen Titu Andrescu Y Andy Liu a dictar algunas charlas....

No se todavia quien es guia de quien pero cuando sepa lo confirmo!

Suerte

Pascual que es el SEMI?
eso es el cmpamento de verano en bogota?

Semi no es el entrenamiento de colombia es un evento paralelo a la olimpiada que se hara en cartagena donde se hablara de resolucion de problemas

ahhh bacano,
que mal que me lo pierdo  :(


$ D$ es un punto variable en el lado $ \overline{BC}$ de un $ \triangle ABC.$ Por $ D$ se trazan las paralelas a los lados $ AB$ y $ AC$ que intersectan a $ AC$ y $ AB$ en $ X,Y,$ respectivamente. Demostrar que el lugar geométrico del circuncentro de $ \triangle AXY$ es una recta que es perpendicular a la A-simediana del $\triangle ABC.$

Si $ M$ y $ N$ sin puntos medios de $ AB$ y $ AC,$ con semejanza de triángulos es facil probar que $ \frac {_{MX}}{^{NY}} \equal{} \frac {_c}{^b}.$ Las circunferencias $ \odot(AMN)$ y $ \odot(AXY)$ se cortan pues en el centro de la semejanza espiral que lleva $ \overrightarrow{MX}$ a $ \overrightarrow{NY}.$ Entonces $  \frac {_{PM}}{^{PN}} \equal{} \frac {_{AM}}{^{AN}} \equal{} \frac {_c}{^b}$ $ \Longrightarrow$ $ P$ es fijo y pertenece entonces a la $ A$-circunferencia de Apolonio del triángulo $ \triangle AMN.$

Expandiendo con la homotecia de centro en $ A$ y coeficiente $ 2,$ se ve que $ P$ es punto medio de $ AQ,$ donde $ Q$ es el punto de corte de la  A-circunferencia de Apolonio de $ \triangle ABC$ con su circunferencia circunscrita, la cual no es mas que la recta de la A-simediana de $\triangle ABC.$ En definitiva, el lugar del circuncentro de $ \triangle AXY$ es la mediatriz de $ AP.$


I purposely put this topic in this forum.

i suppose that most people who post in the high school basics forum are not "advanced" problem solvers (yet?)

but i was wondering what are your goals? do you think you will ever be a top 3 USAMO winner? do you work toward that?

over the course of the last three years I ve realized I sucked at competition math in middle school. so over this summer, Im going to work extra hard for AIME and possibly (but unlikely) USAMO. along with that, Im going to try and hit the Intermediate forums  :P .

[quote="iamagenius"]for example, do you think you will ever go to IMO?[/quote]

well unless i get unnaturally lucky next year, no... if i reach USAMO id be pretty happy but right now looking at the pre-olympiad problems make my head spin  :D .

ive never taken AMC before so next year what i think i'll do is take it (and try AIME too) and see how far I can get. The summer after that I will study what needs work on and then try for USAMO.

My aims right now are similar to 7h3.D3m0n.117's. Really, I'll be ecstatic if I get into USAMO, and happy if I make a good score on AIME. I haven't taken the AMC before (in a competition at least, I've taken a few from the resources section, and of those I'm scoring well enough to qualify into AIME), but between now and next year I plan on learning a lot. The only problem is I wish I got an earlier start, as I'm going to be in 11th grade after summer is over.

well
i don't really study much
and i'm not really that interested in math
so i guess i'd be satisfied with blue mop one day

My goals are just like thedemon's and stuck's goals.  I've never taken an AMC before but hope to do well next year, and at least make it to AIME.


Just an idea... try mixing variables on it, and possibly mildorf's method of finding a tight bounding inequality to sandwich between...

Sorry I have little more than ideas but its what you asked for :wink:

See here
http://www.mathlinks.ro/Forum/viewtopic.php?p=202141#p202141
(Vasc's post about two thirds down the first page)  :)

[quote="mysterious"]

You can use HOLDER[/quote]
Please show how  :roll:  :?:


[quote="darkquantum"]Find the last two digits of 11^10-1[/quote]
11^10-1=(10+1)^10-1=(binomial theorem) 1+C(10,1)*10*1+bunch of terms divisible by 100 -1 :equiv:1+100-1:equiv:0, where i calculate modulus 100.

err
wat did u do mystic??/
dd u asnwer the question?

He just expressed 11^10-1 = (10+1)^10 - 1. Expanding (10+1)^10 by binomial theorem, all the terms cancel out mod 100 except for 1 and 100, so 1 + 100 - 1 = 100, and the last two digits are 00.


[b]Problem.[/b] Let $M,N,P,Q,R,S$ be the midpoints of the sides $AB,BC,CD,DE,EF,FA$ of a hexagon, respectively.  Prove that
\[RN^{2}=MQ^{2}+PS^{2}\]
if and only if $MQ\perp PS$.

[hide]
[b]VECTORS!!!!!!![/b]  :rotfl:  :P

The condition $RN^{2}=MQ^{2}+PS^{2}$ is equivalent to
\[|{\bf b+c-e-f}|^{2}=|{\bf a+b-d-e}|^{2}+|{\bf c+d-a-f}|^{2}\]
while the condition $MQ\perp PS$ is equivalent to
\[({\bf a+b-d-e})\cdot ({\bf c+d-a-f})=0\]
Now just observe that ${\bf b+c-e-f}={\bf a+b-d-e}+{\bf c+d-a-f}$. For all ${\bf u}$ and ${\bf v}$, $|{\bf u+v}|^{2}=|{\bf u}|^{2}+|{\bf v}|^{2}+2{\bf u}\cdot{\bf v}$, so that
\[|{\bf b+c-e-f}|^{2}\]
\[=|{\bf a+b-d-e}|^{2}+|{\bf c+d-a-f}|^{2}+2({\bf a+b-d-e})\cdot ({\bf c+d-a-f})\]
And that's it!
[/hide]

My solution was similar to yours, but I used Complex Numbers.  Is there a solution without using such powerful tools?:)


Let $a_{1}$, $\cdots$, $a_{k}$ and $m_{1}$, $\cdots$, $m_{k}$ be integers with $2 \le m_{1}$ and $2m_{i}\le m_{i+1}$ for $1 \le i \le k-1$. Show that there are infinitely many integers $x$ which do not satisfy any of congruences \[x \equiv a_{1}\; \pmod{m_{1}}, x \equiv a_{2}\; \pmod{m_{2}}, \cdots, x \equiv a_{k}\; \pmod{m_{k}}.\]

We look at residues $a \mod m= m_1 m_2 ... m_k$ and call $a$ "forbidden" iff $a \equiv a_1 \mod m_i$ for some $i$.

We clearly have $m_i \geq 2^{i-1} m_1$ for all $i$.
The total number of forbidden residues $\mod m$ by some fixed $i$ is $\frac{m}{m_i}$.
Thus the total number of forbidden residues $\mod m$ is at most $\sum_{i=1}^k \frac{m}{m_i} < \frac{m}{m_1} \cdot \sum_{i=1}^k \frac{1}{2^{i-1}} <  \frac{2m}{m_1} \leq m$.
So there is some residue class that is not forbidden, giving that all it's infinitely many members don't satisfy any of these congruences.


"Find the greatest integer x for which $3^{20} > 32^x$."

Is there anyone you can solve this without the use of calculator?

$\frac {20}{\log_3 32} > x$

You can kinda estimate at that.

Oh yeah.

I am just worried that the estimation would come out wrong.

[quote="amirhtlusa"]well, $\log_{3} 32$ is a number between $3$ and $4$, so $x=5$ ;)[/quote]

Can't $x=6$ work as well from this approximation? And btw, $x=6$ does work because $3^{20} > 2^{30}$.

To show that $\frac{20}{\log_3{32}} > 6$ we write $\log_3{32} = 5\log_3{2}$ so $\frac{20}{\log_3{32}} = \frac{4}{\log_3{2}} > \frac{4}{\frac{2}{3}} = 6$ because $\log_3{2} < \frac{2}{3}$.

[quote="frodo"]The way I solved is that since $ 2^5=32$, we have $(3^4)^5 > (2^x)^5$.  If you take the fifth root on both sides, the inequality still holds and we get $ 3^4 > 2^x$ => $81>2^x$.  The smallest power of two less than 81 is 64, which equals $2^6$.  Thus, the largest value of x is 6.[/quote]

Yeah. That's a much more efficient/slick way. I got caught up in the approximation frenzy  :dry:  :play_ball:

yes, $x=6$ is the correct answer,
i made a mistake. :P

Or, you could notice that log base 3 32 is right above log base 3 27...


Find the smallest positive integer $n$ such that $1! \cdot 2! \cdot 3! \cdot\cdot\cdot n!$ is divisible by 1998^1998.

[hide]First, factor 1998:

$1998 = 2^1 * 3^3 * 37^1$

So, we have to find an $n$ such that the factorial has the following factors:

$1998^{1998} = (2^1 * 3^3 * 37^1)^{1998} = 2^{1998} * 3^{5994} * 37^{1998}$

We will have an abundance of 2s and 3s, so we don't need to worry about those. We only have to count how many times 37 appears in the product. The amount of factors in each factorial that are divisible by 37 clearly goes up by 1 every 37 factorials. This means from 0-36 factorials, there are 0 factors divisible by 37, there is 1 per factorial from 37-73, 2 for 74-110, etc. So, in the first group we gain 0 of our 1998 37s, 37 in the next, then 74, etc. So, we have to minimize the LHS of this inequality:

$37(0) + 37(1) + 37(2) + 37(3) + \cdots + 37(x) + (x + 1)y \ge 1998$

where x is positive and $0 \le y < 37$. To do this, the first x terms must be less than 1998, so the largest possible x is 9, which yields

$(10)y \ge 333$

The greatest y must then be 34. Now, to calculate n, we first multiply x + 1 by 37 and subtract 1 (this counts the factorials up to $37(x+1)$, but we are also counting 0, which we don't want). Then, we add y. So, our answer is

$(9 + 1)37 - 1 + 34 = 370 + 34 = 403$[/hide]


algebra
polynomial
LaTeX
combinatorics unsolved
combinatorics

Find the number of $ P_n(x)$($ n$ is even) satisfying:
i)$ degP_n(x)\equal{}n$
ii)The coefficients of $ P_n(x)\in$ {$ \minus{}1,0,1$}
iii)There exists a polynomial $ Q(x)$ whose all the coefficients $ \in$ {$ \minus{}1,0,1$} satisfying $ P_n(x)\equal{}(x^2\minus{}1)Q(x)$

It's essentially the same as http://www.artofproblemsolving.com/Forum/viewtopic.php?t=276784 -- if we split the sequence of coefficients of such a polynomial into two sequences by taking every other term, each of the sequences we get must satisfy the property in the link (though one of them must begin with either 1 or -1).  But this means we can easily write the answer to this problem as (essentially) the product of two answers to the other problem.

A couple LaTeX suggestions: \deg exists.  To get curly brackets, use \{ and \}.


Given $ P(x)\equal{}a_{2008} x^{2008} \plus{} a_{2007} x^{2007} \plus{} ... \plus{} a_{1} x \plus{} a_{0}$ and $ Q(x)\equal{}x^{2} \plus{} 2x \plus{} 2008$. Let $ P(x)\equal{}0$ has $ 2008$ real roots and $ P(2008) \le 1$. Prove that there exists real number $ x$ such that $ P(Q(x))\equal{}0$.

Are you sure the problem statement is correct?  I don't think the current statement is true.  :|

[hide]$ Q(x) \equal{} (x \plus{} 1)^{2} \plus{} 2007$, so the range of $ Q$ is $ [2007,\infty)$.  We need to prove that $ P$ has a root greater than or equal to $ 2007$.

But we could just make $ P(x) \equal{} a(x \plus{} 1)x(x \minus{} 1)(x \minus{} 2)\cdots (x \minus{} 2006)$ and make $ a$ sufficiently small so that $ P(2008)\le 1$ still holds.[/hide]


pigeonhole principle
superior algebra
superior algebra unsolved

Let $ A$ be a finite ring.Prove that there exists two positive integers $ m,p,m \geq p \geq 1$ so that $ a^{m}\equal{}a^{p}, \forall a \in A$.

If $ A\equal{}\{x_i\}_{i\equal{}1}^n$, let $ S\equal{}\{(x_{i}^k)_{i\equal{}1}^n | k \equal{} 1, 2, ...\}$ be a set of n-tuples of powers of elements of $ A$.  Since $ S$ contains at most $ n^n$ elements, it is finite, so we must have $ (x_{i}^m)_{i\equal{}1}^n \equal{} (x_{i}^p)_{i\equal{}1}^n$ for some $ m>\equal{}p>\equal{}1$.

Oh, I have a feeling that we both meant: $ m>p>\equal{}1$. :)

[quote="bogdanl_yex"]I think is obvious the case of equality :D...But can you be more specific with the demonstration? :blush:[/quote]

How much more specific?  It's an application of the pigeonhole principle.  We have an infinite sequence of n-tuples:

$ (x_{1}, x_{2},..x_{n})$
$ (x_{1}^2, x_{2}^2,..x_{n}^2)$
$ (x_{1}^3, x_{2}^3,..x_{n}^3)$
...etc.

 but there are only $ n^n$ possible, so two of them must be equal.  Say it's the m-th and p-th ones.  We have:

$ (x_{1}^m, x_{2}^m,..x_{n}^m) = (x_{1}^p, x_{2}^p,..x_{n}^p)$

But that's the same as ${ x_{1}^m=x_{1}^p, x_{2}^m=x_{2}^p}$, etc.  Which is exactly what we were looking for.


linear algebra
matrix
algebra
polynomial
linear algebra unsolved

We geometrize, let $f$ be the endomorphism associated to $X$.
Its characteristic polynomial is $x(x^{2}+1)$, then its eigenvalues are 0, i and -i, in $\mathbb{C}$, $f$ is diagonalizable.
The rest is simple.


Yale college Harvard MIT AMC AIME USA(J)MO

Hello AoPSers. I am beginning a new game that anybody can join. Basically, once we have enough people, we will begin.

  AoPS City, a game that I made up myself is one that can be set up many different ways. The people that sign up will be the townspeople that live in AoPS City. I am the mayor of AoPS City, and I make up all the rules that go on in AoPS. Basically you have to follow the rules to stay in the game. The last person in AoPS City is the winner, and they will learn what happens later. It is a game that is hard to explain, and you just have to begin, and you learn the idea of it as you play it. There are many different things that can happen in AoPS City. The mayor runs the only store in AoPS City.

Here are the basic rules;

1.) You need to be alive, or the mayor (me) will get rid of your body, and you will no longer be in AoPS City.
2.) You need to eat a proper amount of food and water to live each day.
3.) You can not live in AoPS City, unless you have a house.
4.) Sometimes there will be random events each day that either complicate the game, or make it easier.
5.) These rules will be described in better detail later.
6.) You must be active in AoPS City. (you have to post on the thread)

I will explain the game more when it begins.
Sign-ups begin now!!!
If you want to play then post it on the thread. Don't pm me!!!!

People Playing;
AIME15
ernie
dragon96
erabel
AIME15
Bugi
Poincare
pythag011
chenhsi
pacman2812
james41
zapi2007
mewto55555
isabella2296

I might drop out, but currently [b]in[/b].

[quote="dragon96"]in

[color=white]The message is too small. Please make the message longer before submitting.[/color][/quote]

I can see your white text against the gray background.

When will we start?  Also, describe the rules in better detail now.

*travels to AoPS City*
[size=0]means /in[/size]

I'm glad that a lot of actives are joining.

Stats -

lotsofmath - 83 dollars - house, car, food and water
erabel - 95 dollars - house, car, food and water
Poincare - 100 dollars - house, car, food and water
pythag011 - 74 dollars- house, car, food and water
chenhsi - 85 dollars - house, car, food and water
pacman2812 - 90 dollars - house, car, food and water
james41 - 65 dollars - house, car, food and water
zapi2007 - 80 dollars - house, car, food and water
mewto55555 - 95 dollars - house, car, food and water
isabella2296 - 85 dollars - house, car, food and water
Dojo - 84 dollars - house, car, food and water
crazychinesemaniac - 85 dollars - house, car, food and water
pcstaa - 85 dollars - house, car, food and water
icemathematician7 - 85 dollars - house, car, food and water
TOWN - 10,000 dollars

Okay, we only need five more dollars.

pays 10 dollars, gets an upgrade on arcade  :)

Stats -

lotsofmath - 83 dollars - house, car, food and water
Poincare - 100 dollars - house, car, food and water
pythag011 - 74 dollars- house, car, food and water
james41 - 65 dollars - house, car, food and water
zapi2007 - 70 dollars - house, car, food and water
Dojo - 84 dollars - house, car, food and water
icemathematician7 - 85 dollars - house, car, food and water
TOWN - 10,000 dollars

Oh, yes, and zapi2007 is also the richest person in AoPS City, what a coincidence.  :)

Now we have paid 35 dollars for the arcade.
Oh, and lotsofmath has graduated from college. I think we should take mewto out of this considering he has been banned from posting and pming. I am also getting rid of pcstaa and CCM for inactivity and not replying to the pm I sent, but opening it.  There are now seven people left in AoPS City.

Okay, now as for the jobs. Each person makes thirty dollars a week, and they must also pay 25 dollars a week for food, water, their car, and their house. Starting at day 4.

[size=200][b]Day 4[/b][/size]

Alright, if you are first on the list above, then you live in house 1, and you live in house 2 if you are second on the list above, and third on the list is in house three. (understand the pattern? :) )

Fortune Cookie: Listen for hints for an advantage in the game.

Alright, good morning to all seven of you. You have been playing for a long time, but now somebody is going to die. The murderer has dropped a bomb, but for some reason it is falling really slowly. It is about to fall on lotsofmath's house unfortunately. lotsofmath has the power to change houses with somebody else. All he has to do is say "I switch houses with *****" [b]in bold. [/b] If the person who has been offered to switch houses doesn't say anything in three days, then I will assume that they will accept to change houses with the person living in the house about to explode. Although, if the person does reply in three days, then they can decline the offer of changing houses. If the person declines the offer, then lotsofmath can offer the house to another person. If three people decline to change houses with the person living in house 1, then the person living in house 1 will have to stay (and die due to the bomb). The person living in house 1 three weeks from now will die. Let the moving begin.

Hint: There is a way for everybody to survive, so pay attention to this thread.

Plan A: Build a new house and move to it.
If not,
Plan B: [b]I switch houses with icemathematician7.[/b]

way to switch houses with the person most likely to be inactive

Way to play it safe lotsofmath.  :lol:

I also forgot to tell you that you can switch houses with a person even if you are not living in the house that is about to blow up. If you guys are all going to survive, it will require some generosity. (Hint ?)

Hmm... Would you like to replace icemathematician?

Remember if you guys all want to survive it is going to require some generosity.

Okay icemathematician and lotsofmath left their houses at Jan 31st, 2009 2:43 pm. They waited outside their houses while the packers took their things and put them in their new houses. It took about an hour, but once it had been an hour they were able to go into their new houses at Jan 31st, 2009 3:43 pm.

Ya know, there are two hints in this post for everybody surviving. The first one was in the previous post so you guys should know what it is. The other one is the most important.

Oh.

It takes an hour to switch houses. THat will be very important.

The bomb will land on house 1 at Feb 18, 2009 12:33 pm.

Hmm... That's interesting.

especially the fact that nothing will happen now.

Well, like I said. You don't have to be living in house 1 to switch houses with somebody. If a person declines the offer in three days however, then they remain in their current homes. You just have to offer the house at just the right time.


ratio
ceiling function
logarithms
integration
calculus
derivative
geometric sequence

[quote="F u r u y á"]Consider the sum:

$S=(x)+ (xx) + (xxx)+(xxxx)+...+(xx...n \ times...xx)$,

where [b]x[/b] is a natural number and [b]a[/b] is the number of algarisms of x. Find a general formula for $S$.

ps: (xxx) is not (x³), (xxx) is just the juxtaposition of x. For instance, for x equal to 31, (xxx) will be 313131.[/quote]

Hmm ... I just got something like $S=\frac{x}{9}\left(\frac{10^n-1}{9}\times 10-n\right)$

Is it true ? :?

[quote="fourierseries"]I don't think that's correct.

Plugging in x=1 and n=3 should yield 111+11+1=123, but the formula returns something else.[/quote]

when $x=1$ , $n=3$ ;

$S=\frac{1}{9}\left(\frac{999}{9}\times 10 -3\right)=\frac{1}{9}\times 1107=123$

 :ninja:

You have to find a way to put the variable [b]a[/b] into the formula, so it will work with any natural x. I tried x=23, n=4:

$S=\frac{23}{9}\left(\frac{10^4-1}{9}\times 10-4\right)=28382$
$23+2323+232323+23232323=23466992$

I think something is wrong, your formula is returning a negative decimal number.

[hide][img]http://img.photobucket.com/albums/v280/Furuyah/soma.png[/img][/hide]

[quote="Altheman"]let $r = \lceil \log{x} \rceil$

$\sum_{k=0}^{n-1} ( (10^{r})^{(n-k)} * (n-k) * x$[/quote]
i get the sam thing, but can it get simplified easily?

you can move over the x since it is a constant, but i am not sure if that can be simplified...i have a feeling that it can
there might be a general simplification of

$x* \sum^{n}_{k=0} ( y^{n-k} * (n-k) )$ could be
$x* \sum^{n}_{k=1} (k* y^{k})$ since this generates the same terms
so having $y = 10^{\lceil \log{x} \rceil}$
$x* \sum^{n}_{k=1} ((k+1)* y^{k}) - x* \sum^{n}_{k=1} (y^{k})$
consider $\int (n+1)* y^{n} = y^{n+1} + C$
so $D_y(y^{n+1} + y^{n} + ... + y^{3} + y^{2})$ equals the first summation symbol
the inside is a geometric sequence so
$x * D_y(\frac{y^{2}*(1- y^{n})}{1-y}) + x* \frac{y*(1- y^{n})}{1-y}$
i bet that this is completely unnecessary, but i don't see the other way to do it...
i don't feel like doing the differentiation now...it is not that difficult (think quotient rule)
sorry about the calculus if i made a mistake, i am not that good at calculus, i just recognized that pattern with the derivitives and the geometric sequence


linear algebra
matrix
vector
linear algebra unsolved

Each entry of the matrix $A=(a_{ij})\in M_{n}(\mathbb{R})$ is equal to $0$ or $1$ and moreover $a_{ii}=0,\,a_{ij}+a_{ji}=1\,(1\leq i<j\leq n).$ Prove that $\mathrm{rk}A\geqslant n-1.$

if it is not the case then we can find a vector $x\neq 0$ such that $xA=0$ and $xJ=0$ by assumption $A+A^{t}=J-I$ so $0=x(A+A^{t})x^{t}=-xx^{t}<0$ contradiction.

[quote="sam-n"]if it is not the case then we can find a vector $x\neq 0$ such that $xA=0$ and $xJ=0$ [/quote]

$xA, xJ$ ?

$x$ is in $M_{1,n}(R)$ ?

Why such $x$ exist ?

because if not $dim(Ker(A^{t}))+dim(Ker J^{t}) \geq n+1$ so $Ker(A^{t}) \cap Ker(J^{t}) \neq \{0\}$.
Nice solution sam-n :)


algebra
polynomial
modular arithmetic
number theory unsolved
number theory

Let $a>1$ be a fixed integer. For a prime p that does not divide a, let $ f(p)$ be the order of a modulo p. Prove that $\frac{p}{f(p)}$ is unbounded.

oh thanks, i did it with a more general result as showed below:
${\bf Problem.}$ Let be given $a>1$ is integer and $h$ is a polynomial with integer coefficients($h\not\equiv0$). For each prime $p$ which $(p,a)=1$ we put $f(p)$ is the order of $p$ respectively to $a$. Then $\frac{p}{h(f(p))}$ is unbounded.

Proof.  If $h$ is constant , it's trivial. Assume that $deg(h)\ge1$. It's enough to show that for each positive integer $d$ then
\[\frac{p}{(f(p))^d}\]
is unbounded. Okie,
Assume that \[\frac{p}{(f(p))^d}\] is bounded, ie... there exist $n$ positive integer such that $p<(f(p))^d\cdot n$. Now by Dirichlet Theorem there exist infinitely many $q$ is prime and $q>a$ and $q\equiv1\pmod{(n+1)!}$. Take $p$ is a prime number which
\[p\mid \frac{a^{q^d}-1}{a^{q^{d-1}}-1}\]
1st) At first let us show $p\nmid a^{q^{d-1}}-1$
In fact , if not then
\[a^{q^{d-1}}\equiv1\pmod{p}\]
so
\[\frac{a^{q^d}-1}{a^{q^{d-1}}-1}\equiv q\pmod{p}\]
then $p=q$. We now get $q\mid a^{q^{d-1}}-1$ ,then $q\mid (a^{q-1}-1,a^{q^{d-1}}-1)=a-1$ this contracts to the definition of $q$.

2nd) The next step, we show $f(p)=q^{d}$.
we have $p\mid (a^{f(p)}-1,a^{q^d-1}-1)=a^{q^t}-1$ where $t\le d$. By the fist step $t>d-1$. So $t=d$ ie... $f(p)=q^d$ (note $f(p)$ min)
Now we have
$p-1=uf(p)=uq^d$ with $1\le u< n$. Then
\[p\equiv1+u\pmod{(n+1)!}\]
so $p=1+u$ then $q^d=1$ contracts!

So we have \[\frac{p}{(f(p))^d}\]
is unbounded. We are done!!!!

I am wondering that if \[\frac{p}{e^{f(p)}}\]
is bounded or unbounded?

What a pity that when i were home i found that there is something wrong in my proof. In fact the proof is only true for $h$ with $deg(h)\le 1$ and you can do as we said!


geometry
conics
parabola
analytic geometry
symmetry
LaTeX

A bridge is to be built in the shape of a parabolic arch and is to have a span of 100 feet. The height of the arch a distance of 40 feet from the center is to be 10 feet. Find the height of the arch at its center.

[hide]Is it 250/9?  If thats right i can post a solution-all I did was anylytic geometry, lable the highest point (0,h)[/hide]

I'm almost certain my answer is right this time:

[hide="My Answer"]250/9[/hide]

it's the same thing Art of Owna got, but i think the way i got it is rather different.

[hide="My Rather Lengthy Solution"]First, i drew the parabola on a cartesian coordinate grid such that the axis of symmetry was on the y axis and the zeros were 50 and -50. And you also know that in the equation of the parabola ($ax^{2}+bx+c = y$), a has to be negative (since it opens downward). You also know that $b = 0$, because $\frac{-b}{2a}= 0$ (using the fact that the axis of symm. is zero). So, then you start writing the equation (lets start by using the point (40,10) given to us in the problem):

$-ax^{2}+c = y$ becomes $(-a)(1600)+c = 10$. So you get $c = 10+1600a$.

Sub that back into the original equation and you get $-ax^{2}+10+1600a = y$.

Now you apply the formula for the point (50,0). You should get $(-a)(2500)+1600a+10 = 0$. Simplify it to get $a = \frac{1}{90}$.

Remember that we took a to be negative in the original, so when you plug it back in, you get $\frac{-1}{90}x^{2}+\frac{1600}{90}+10 = y$

The problem is asking for the y value (height) when $x = 0$, so you plug in $0$ for $x$ and the final equation is $\frac{1600}{90}+10 = y$

Solve for $y$ and you get $y = \boxed{\frac{250}{9}}$[/hide]

Well, my equation turned out to be x^2=-90(y-250/9), plugging in (50,0) (-50,0) and (40,10) seem to work out..

is the bridge supposed open upward (valley) or downward (hill)? i thought it was like a hill but my dad was reading over my solution and he kept thinking that it was like a valley... so which one is it?

O I just had a general equation of x^2=a(y-h), then had two points (50,0) and (40,10) plug them in for x and y, two equations for two variables a and h.  I found a, then found h, and h is the vertex, which is also the height.

And, wouldnt it have to be a hill (I mean a bridge isnt usually valley shaped),

[quote="Art of Owna"]
And, wouldnt it have to be a hill (I mean a bridge isnt usually valley shaped),[/quote]

that's exactly what i thought

[hide="Answer and my solution"]
Art of Owna got it, the answer is $\frac{250}{9}$.

a parabola: $y = a(x-h)^{2}+k$

from this, one can conclude:
$10 = a(40-0)^{2}+k$
$10 = 1600a+k$
$0 = 1600a+k-10$ ... 1

$0 = a(50-0)^{2}+k$
$0 = 2500a+k$ ... 2

now set the two equations equal to each other

$1600a+k-10 = 2500a+k$
$-10 = 900a$
$a =-\frac{1}{90}$

then plug in $a$ in equation 2:
$0 = 2500 \cdot-\frac{1}{90}+k$
$\frac{2500}{90}= k$
$k = \frac{250}{9}$
[/hide]

and yes, it's a hill, not a valley

-----------------

GAHH i hate LaTeX errors.. spent like 20 minutes to figure out i had a parenthesis instead of a curly bracket :rotfl:

hey! i got it too!! and i had a couple LaTeX errors, also. just hit preview and see what ur missing.


Let $ a,b,c$ be positive real numbers that satisfy $ ab+bc+ca=1$. Show that $ a+b+c-3abc\ge \frac{1}{3}(\sqrt{a^{2}+1}+\sqrt{b^{2}+1}+\sqrt{c^{2}+1})$.

We have
\begin{eqnarray*}\frac{1}{3}\cdot\sum\sqrt{a^{2}+1}&\le&\sum a-3\cdot abc\\ \iff\frac{1}{3}\cdot\sum\sqrt{(a+b)\cdot (a+c)}&\le&\sum a-3\cdot abc\\ \iff\frac{1}{3}\cdot\sum\frac{2a+b+c}{2}&\le&\sum a-3\cdot abc\\ \iff a+b+c&\ge& 9\cdot abc \end{eqnarray*} What is truly because \[ \left\{\begin{array}{c}1=ab+bc+ca\ge 3\cdot\sqrt[3]{a^{2}b^{2}c^{2}}\implies abc\le\frac{1}{3\sqrt 3}\\ a+b+c\ge \sqrt{3\cdot\left(ab+bc+ca\right)}=\sqrt 3 \end{array}\right\|\\ \implies a+b+c\ge 9\cdot abc \]


Let triangle ABC be inscribed in the circle C(O).
a) Build the triangle MNP such that MN, NP, MP are perpendicular on OC, OA and OB and M, N, P lie on the circle C(O).
b) Let MS be perpendicular on BC. OS intersect the arc BC in R ( the arc BC which doesn't contain the point A). D lies on (OS such that DR=RS. The points E and F are for B and C what is D for A ( the analogous points). Prove that the circumscribed circles of the triangles OMD, ONE and OPF are meeting in a point different by O.
 :gathering:  :diablo: ( I'm from USA)

Just a hint for a) MN is perendicular to OC iff $\angle MOC=\angle CON$ and similar equivalence holds for the othe perpendiculars.
So we denote
$a=|\angle NOA|=|\angle AOP|$,
$b=|\angle POB|=|\angle BOM|$,
$c=|\angle MOC|=|\angle CON|$.
Now we have $a+b=|\angle AOB|$,$b+c=|\angle BOC|$,$c+a=|\angle COA|$, solving this system
$a=\frac{|\angle AOB|+|\angle COA|-|\angle BOC|}{2}$.
After constructing angle $a=|\angle NOA|=|\angle AOP|$ we can draw the lines OP and ON, then the perpendicular to OB lead via P meets the circle in M.

Thank you for your answer.  :D
Any ideas for b) ? :help:
I'm waiting ...

Is it imposible ? Help me, please. I have to know it until next week. :help:  :help:  :help:

a) – This is exactly the configuration of a given triangle ABC, with it’s altitudes AS, BT,
CU, which intersect the circumcircle of ABC, at points M, N, P and the lines MN, NP, MP, are perpendicular to OC, OA, OB respectively ( well known ).

b) – If now, R, Q, L, are the intersection points of circumcircle of ABC, from the lines OS, OT, OU respectively and we denote as D, E, F, the symmetrical points of S, T, U, with respect to the points R, Q, L respectively, then the circumcircles of the triangles OMD, ONE, OPF, have not any common point, other than O ( they are not coaxal circles ).

     Kostas Vittas.


Find all numbers $x$ such that $3^{2x}+3^{x}=90$

[hide="hint"]
Make a substitution. [hide=":)"]Why do you randomly click smileys? :huh: Well, since you have such weird habits, here's another hint for you. :D $y=3^x$[/hide]
[/hide]

if you consider 3^x as t and 3^2x as t^2, then you get this equation: t^2 + t-90=0. Then you solve it, and the right solution is 9. so, as 3^x is 9, x must be 2 because 3^2 =9, and that's your solution.
Anyway, you can solve it without doing this.


modular arithmetic
calculus
integration
function
MATHCOUNTS
number theory
totient function

I keep seeing things about 'mods'. I might've done something with them at one point or another, but I'm really not sure. i keep seeing them used, and have also heard that some problems with them in them don't necessary require them...there are alternate methods?
I would check the AoPS wiki, but it's down for maintenance?
Thanks for all your help. :lol:

Example: $ 42 \equiv 6 \mod 9$.  So if you take $ \mod x$, where $ x$ is the divisor, then $ 6$ is the remainder when $ 42$ is divided by $ 9$.

Hmm. I thought it was something like that. Thanks. :lol:

Basically, if $ x\equiv y$ (mod m), then $ x\minus{}y$ is divisible by $ m$

wait, $ x$, $ y$, $ k$, and $ k$???

and remember that adding kz mod z is just like adding 0

[quote="ZhangPeijin"]Basically...
$ x \equiv y(mod z)$
Means that..
$ x \equal{} y \plus{} kz$
Where $ x, y, z$ and $ k$ are integers. They do not need to be positive.[/quote]

i thought just k and z had to be integers

$ 3.5 \equiv 9.5 \pmod{6}$

no, I don't think so

using the idea of remainders, how would you define remainders for non-integral values?

Yeah, like in fractions, you don't have remainders.

know important mod formulas (but know how to derive them first!!!)  such as Fermat's little theorem, Euler's Totient Formula...

Yeah, they basically mean:
If p is prime and a is a natural number,
$ a^p\equiv a (\mod {p})$

And
When p and a are relatively prime.
$ a^{p \minus{} 1} \equal{} 1 (\mod {p})$

Oh no, I don't know any of those. Better start studying...[/b]

[quote="ZhangPeijin"]Yeah, they basically mean:
$ a^p\equiv a (\mod {p})$
And
$ a^{p \minus{} 1} \equal{} 1 (\mod {p})$
Where p and a are relatively prime.[/quote]

those 2 are equivalent, and it's still the wrong formula

here, $ a$ is any integer, and $ p$ is a prime.  Try $ a\equal{}5$ and $ p\equal{}12$, you'll see that formula doesn't work.

don't see it there, I think you misread it

No, you forgot to specify that p is prime.

If p is a prime number and a a natural number, then
$ a^p \equal{} a (mod p)$.
(1)

Furthermore, if p∤a (p does not divide a), then there exists some smallest exponent d such that
$ a^d \minus{} 1 \equal{} 0 (mod p)$
(2)

and d divides p-1. Hence,
$ a^{(p \minus{} 1)} \minus{} 1 \equal{} 0 (mod p)$.
(3)

The theorem is sometimes also simply known as "Fermat's theorem" (Hardy and Wright 1979, p. 63).

Taken exactly from Wolfram.

[quote="ZhangPeijin"]If p is a prime number and a a natural number, then
$ a^p \equal{} a (mod p)$.
(1)

Furthermore, if p|a (p does not divide a), then there exists some smallest exponent d such that
$ a^d \minus{} 1 \equal{} 0 (mod p)$
(2)

and d divides p-1. Hence,
$ a^(p \minus{} 1) \minus{} 1 \equal{} 0 (mod p)$.
(3)

The theorem is sometimes also simply known as "Fermat's theorem" (Hardy and Wright 1979, p. 63).

Taken exactly from Wolfram.[/quote]

you forgot to specify that in the second formula, $ p$ is prime.

do NOT treat them as separate theorems though, one easily follows from the other

Yes, $ a^p\equiv{a}\pmod{p}$ is just a corallary of Fermat's Little Theorem, taken by multiplying by a. I just don't remember either of them and just go with the totient formula.

lol... $ a^{\phi(p)}\equiv1\mod p$

Where $ \phi$ represents the totient function... and $ p$ is any natural number so that $ (a,p)\equal{}1$

Hmm...
...and where did you learn this?

But, thanks! :D
I would've never learned this on my own...:mad:

[quote="ZhangPeijin"]What's the totient function?[/quote]
Basically a generalization of FLT. Look it up.

I think we should stop talking about this, it's not exactly Mathcounts level.

Actually, totient and fermat's can be applied to lots of mathcounts problems... I think.

Totient function isn't a generalization of FLT, totient theorem is. The totient function is how many numbers less than a number are relatively prime to it.

Well, that's what I meant, considering the totient function appears in the theorem.
Yeah, I've used it for countless problems, such as target #7 on state last year.


I don't really know whether this will work,but

$ x^2 \plus{} y^2$=884
$ \implies$  $ 2(x^2 \plus{} y^2)$=1768

or, $ (x \plus{} y)^2 \plus{} (x \minus{} y)^2 \equal{} 1768$
or $ (x \plus{} y)^2 \plus{} (x \minus{} y)^2 \equal{} 1764 \plus{} 4$
or,$ (x \plus{} y)^2 \plus{} (x \minus{} y)^2 \equal{} 42^2 \plus{} 2^2$
or when $ (x \minus{} y)^2 \equal{} 4$, $ (x \plus{} y)^2 \equal{} 42^2$
or, max. value of (x+y)=42.

[quote="bbgun34"](a) Compute the greatest value of $ x \plus{} y$ for integers $ x,y$, such that

$ x^2 \plus{} y^2 \equal{} 884$

(b) Compute the greatest value of $ x \plus{} y$ for integers $ x,y$, such that

$ x^2 \minus{} y^2 \equal{} 884$[/quote]

[hide="a"]We want $ x$ and $ y$ to be as close as possible to obtain the maximum possible value. The closest square to 442 is 441. So after a bit of brute force, the two integers whose squares add up to 884 are 20 and 22, which give a sum of 42.[/hide]

[hide="b"]This factors into $ (x\minus{}y)(x\plus{}y)\equal{}884$. Since we want to maximize the $ (x\plus{}y)$ term, we set $ x\minus{}y\equal{}1$ and $ x\plus{}y\equal{}884$. But this doesn't give us integer values for x and y, thus the next factors are $ x\minus{}y\equal{}2$ and $ x\plus{}y\equal{}442$. This does give us integer values $ (222,220)$, thus the max is $ 442$.[/hide]

(b)  We can factor $ x^2\minus{}y^2 \equal{} 884$ into $ (x\plus{}y)(x\minus{}y) \equal{} 884$.  We now simply find the factors of 884 and plug them in.  If we use 884 and 1 as the factors, $ x$ would not be an integer.  If we go to the next set of factors, 2 and 442, we see $ x\equal{}222$ which is an integer and therefore $ y$ must be an integer too.  The maximum value that can be attained for $ (x\plus{}y)$ is then $ \boxed{442}$.

I hate when someone replies while someone else is posting...


Hello
I have previous never had any problems with references, but now for some reason they are not properly reference in the text. The caption of a figure or table is correct, i.e "Table 1 shows..." "Table 2 is ...". But in the text the \ref{} shows only the section number; "Table 4.2.1 shows" "Table 4.2.1 is...."!  I am using winedt, and maybe I have toggled the wrong button, but not that I know of. Can anyone help?

Regards
JT

Double-check that in each table, your \label command comes after the \caption command, but before the \end{table} command.  Having the \label command in the wrong place often produces spurious references.

Thank you. I had my \label before \caption. Now it works if I compile twice. (I though WinEdt would compile the necessary number of times with just 1 click on the texify button..)

JT


How many different 4-digit numbers can be formed using the digits 2, 4, 5, 6, and 7 such that no digits repeat and the number is divisible by four?

A number is divisible by 4 only if the last two digits form a number divisible by four(e.g., 12, 24, etc.) Out of the five given digits, the possible last two digits are 24, 52, 56, and 64.

No matter what we choose as the last two digits, there are $ 3 \cdot 2 = 6$ ways to choose the other two digits, so there are $ 6 \cdot 4 = 24$ ways, out of $ 5 \cdot 4 \cdot 3 \cdot 2 = 120$ total ways, giving us a probability of 1/5.

When I asked this question, this page was pulled up. The correct answer is given as 36.

1) The question did not ask for probability
2) You missed the last two digits being 72 or 76

so $ 6\cdot 3!\equal{}\boxed{36}$

[quote="mathgenie"]How did you get $6 \cdot 3!$? I think the 6 is from the possible last digit combinations, but where does the $3!$ come from?[/quote]

I think that the 3! is actually 3 chose 2 (cause there are 3 numbers left and and you want only 2 of them). Which equals 6.
6*6=36

[b]Solution:[/b]

There are [u]6[/u] different types of endings:
$24$
$52$
$72$
$64$
$56$
$76$

Since we want 4 digit numbers, [u]with no digit repeating[/u], there are $3\cdot 2$ ways to place the first 2 numbers, nomatter the ending.

So, in total we have $6\cdot 6=36$ different numbers.


[quote="epsilonist"]Does anyone has a proof for the Vasile's RCF LCF Theorem?
I can't find it, Who has the proof please post a link here, please.
Thank you.  :)[/quote]
You can find  very nice proof in  Vasc's book:
http://www.artofproblemsolving.com/Forum/viewtopic.php?t=100399


For people who are going to private high schools next year(like myself), which are you considering greatly? I'm going to either Belmont Hill, Rox. Lat., or B.U.A.

[quote="jhredsox"]I'm going to Belmont Hill. Hope to see you there!

-jorian[/quote]

Oh no...

I'm getting the impression you don't like me :maybe:
-jorian

Your powers of observation never cease to [b]ASTOUND[/b] me.

[quote="yunorman"]Umm, why go to a private school when you could go to a beter Public school. Boston Latin and Lexington are way more 1337 than BUA.
Lexington more so for math.
BLS more so for getting into Harvard :P w00t 16 people got in early, expecting 35 to make it overall.[/quote]

Yeah but...so many people go to Boston Latin, and so many are children of Harvard alumni. I think we still have a better ratio.

Anyway, s private schools are not necessarily better for getting into colleges if you'd be a star in a public school and just top 30 or so in a private school.

Yes Lexington is pretty 1337. Well I would consider applying to PEA if my parents wanted to pay all the money, but I don't think private schools are a whole lot more of an advantage.

I think Belmont Hill is overrated. A friend of mine started there in 7th grade and he told me it was a jock school and the kids there weren't that much smarter than the people at our middle school (then again, Lexington's schools are 1337)

Lol my b. I just assumed it because of the Boston connection. There must be some legacy going on though?

Philips Exeter, which is a stronger and more selective high school than Boston Latin, has fewer of its students (both absolutely and per capita) attend Harvard than the admissions numbers from BLS.  Assuming the huge yield rate for Harvard is at least as true at BLS as it is nationwide, the same should be true for attendance as well.   I believe that the reverse is true for MIT admissions -- P.E. sends 10 or so people per year and I don't think BLS has anywhere near that success rate.   This is evidence of a Harvard-BLS special relationship.

http://www.exeter.edu/documents/Profile_2006_final.pdf
http://www.bls.org/cfml/l3tmpl.cfm?page=Demographics

[quote="yunorman"]dude... most BLS kids are not harvard alumni children. None of us who got into harvard were alumni children this year. and there were only 2 last year.[/quote]

Harvard alumni tend not to live in neighborhoods served by BLS, except for Beacon Hill, some medical personnel living in areas near the hospitals (JP, etc), and a sprinkling of BU/Harvard/MIT academics living in Brighton.    BLS is not as minority-heavy as it used to be before the anti-discrimination lawsuit, but as far as I know it is still more or less a representation of the city of Boston, a mostly middle-class cross-section of it with some upper- and working-class (largely immigrants) mixed in.

Boston Latin is considered a public school, correct?

Statiscal,

Boston Latin school does have many students matriculate to MIT every year. Though we have far fewer applicants ap[plying to MIT than P.E. Pretty much most of the elite students get into Harvard Early and only those who have MIT as their top choice will bother with the MIT app after getting into Harvard. There is a "connection" between BLS and Harvard, but from first hand experience, 95% of the people who are admitted are absolutely amazing. This is probably true for P.E. [Some kid aren't so amazing... but get in through their own connections]

[quote="yunorman"]Boston Latin school does have many students matriculate to MIT every year. [/quote]

For acceptance to every prestigious school *other than Harvard*, BLS is strongly outperformed by PE and PA. This is in line with the much greater objective strength of PE/PA in any measurable category such as SAT scores, number of college-level courses offered, level of faculty, size of library, teacher/student ratio, geographic reach, budget and endowment, athletics.    For Harvard, BLS suddenly outperforms Philips.  This reversal with Harvard indicates that it has some form of special preference for BLS that other universities do not.

For example, for MIT the BLS web site reports 12 matriculants over 4 years 2003-6  (3 per year) and 7 accepted last year.   PE website shows 7 matriculated per year during the same time.  One also expects more acceptances per matriculant at Exeter, because it is not a Boston-specific school, and as the web site data indicate, students at PE/PA have other comparable options even if accepted to Harvard/MIT, which is not (statistically) the case at BLS.   In other words, one expects yield to be higher at BLS.

For all schools other than Harvard and MIT, PE/PA completely dominate compared to BLS and the discrepancy is clearer.

[quote]There is a "connection" between BLS and Harvard, but from first hand experience, 95% of the people who are admitted are absolutely amazing. [/quote]

But are they amazing by BLS standards or Harvard standards?  It can be argued whether Harvard's preferential admission of Boston Latin students is objectively reasonable (let's say, if BLS schooling were better adapted for success at Harvard than the schooling elsewhere), or a lowered admission standard due to the history and proximity.


Have you got a proof ,RaduSorici ? Can you post it ?

yes , a nice ineq :D

i spent  2 hours solving it and found that cauchy is a good idea

using $\sqrt{(ab+1)a}$

or some number like this, i will complete it this afternoon :)

ok just prove this ineq: ;)

$\frac{3((xz)^2+(yz)^2+(xy)^2)^2}{(xyz)^2(3+xz+zy+xy)}\geq\frac{(yz+zx+xy)(x+y+z)^2}{xyz(x+y+z)+yz+zx+xy}$ :D

can you use caughy-schwarz theorm directly? :)

no , let $a=\frac{1}{x}$..... :D

after that using CAUCHY_SCHWART ;)

THE REST     'S  MAYBE EASY :blush:


The fifth and eighth terms of a geometric sequence of real numbers are $ 7!$ and $ 8!$ respectively. What is the first term?

$ \textbf{(A)}\ 60\qquad
\textbf{(B)}\ 75\qquad
\textbf{(C)}\ 120\qquad
\textbf{(D)}\ 225\qquad
\textbf{(E)}\ 315$

[hide="Answer"]
$ 8!\equal{}8\cdot7!$ You had to multiply by three common ratios to get there, therefore $ r^3\equal{}8 \implies r\equal{}2$ Since $ 7!$ is the fifth term, you have to divide $ r$ four times to get the first term, giving $ \frac{7!}{2^4}\equal{}315 \implies \boxed{(E)}$
[/hide]


conics
parabola
algebra
polynomial
geometry
projective geometry

Prove or disprove that there is a way to "fit" a circle in a parabola by having it be tangent at at least 3 points without any intersections other than the tangents. Intuition tells me it can't be possible because those three points define the circle, and can never define a parabola...

You can have a circle intersecting a parabola at exactly 3 points, for example the two equations $x^2+(y-1)^2=1$ and $x^2=y$ meet at (-1,1), (0,0), and (1,1).  However, I think you may have meant the circle fits inside the parabola and the parabola doesn't ever go inside the circle, which would be impossible with 3 points of intersection.  Not sure of the proof, however.

Yes, that's what I meant about no other intersections...except the tangents, wumbate. I want the circle to "stay inside the parabola".

Of course not. to have $n \geq 3$ tangent points your polynomial needs to be of grade $n \geq 3$ :D

And anyway you could've tried projective geometry if all else fails :P


group theory
abstract algebra
topology
linear algebra
superior algebra
superior algebra unsolved

I'm struggling with the following:

a) determine the automorphisms Aut(Q) of the additive group
b) determine the automorphisms Aut(Q*) of the multiplicative group

as for a) the only thing I have managed to find so far is that there must be a subgroup H in Aut(Q) which is isomorphic to Q*, namely the automorphisms that multiply by a nonzero rational constant.
Are there others?

as for b) I have no idea altogether. x -> 1/x seems to be one. But there are certainly many, many more, aren't there.

How does one attack such a problem in general?

a)
There are no others, since the whole automorphism is defined by the mapping of any non-zero element.
proof: WLOG assume that this element is $1$ and set $f(1) = a$. Then you get that also all multiplies (the integers) are defined by this as $f(n)=an$ and now you get $y\cdot f(\frac{x}{y}) = f(y\cdot \frac{x}{y})= x$ and so also all rational numbers are defined by this.

b)
The map is exactly defined by the values the primes take. But it looks complicated to get all automorphisms...
For example all values taken on at primes must be 'squarefree' in the sense that every prime factor in a value occurs with power $0,1$ or $-1$. Also they must be 'multiplicativly independet' in the sense that every rational occurs only once to be bijective...

That's not exactly the answer on the multiplicative automorphisms- the images of primes can have square factors. For example, we can send 3 to 12 while preserving all other primes.

An equivalent form which might be easier to think about: Consider the $\mathbb{Z}$-module of finitely supported integer sequences on countably many elements. The automorphisms we're looking for are the invertible linear transformations: each is a change of basis transformation.

If you care about the topology, the identity and inversion are the only continuous automorphisms.

thank you!

a) thanks, ZetaX. I had already known this idea for the integers, but I didn't know that it can be extended to all the rational numbers so easily.

b) the automorphisms need not be continuous for my purposes. They just have to be automorphisms w.r.t. multiplication... I've understood that an automorphism is determined by its values for the prime integers...
Now, what numbers exactly is it allowed to map prime integers to in an automorphism?
Did I get your point right, jmerry, that there must be some kind of 'unique factorization property' for all integers together with the images of the primes?
Isn't it that we CANNOT send 3 to 12 because then we inevitably lose the integers that are powers of 3 without having equally many powers of 4, for instance? As, to repair this, we would have to send another prime to 3 (and analogously some prime to 2) and doing this will destroy uniqueness of factorization...

more help still appreciated...  :)

[quote="ido2005"]Isn't it that we CANNOT send 3 to 12 because then we inevitably lose the integers that are powers of 3 without having equally many powers of 4, for instance?[/quote]
Rationals, not integers. $\frac34$ is sent to 3. I could have sent 2 to $\frac{-4954}{909}$ if I wanted to, fixing 3 and all other primes.

On the first pass, I neglected the negatives: you are free to choose $+$ or $-$ signs randomly for the images of primes. Formally, $\mathbb{Q}^*$ is the direct product of $\mathbb{Z}_2$ and a free abelian group on countably many variables. There is no simple description of the automorphisms of the second structure, although you can translate to the group of finitely supported integer sequences and use linear algebra language.


algebra
polynomial
search
algebra unsolved

Let $ P(x) \in \mathbb{R}[X]$ a polynomial such that $ P(t) \in \mathbb{Q} \leftrightarrow t \in \mathbb{Q}, \forall t \in \mathbb{R}$.

Show that $ \exists (a,b) \in \mathbb{Q}^2$ such that $ P(x) \equal{} ax \plus{} b$.


Let $ a,b,c$ be length of edges of a triangle.Prove that
$ 10(a^2b\plus{}b^2c\plus{}c^2a)\plus{}4abc \ge 6(ab^2\plus{}bc^2\plus{}ca^2)\plus{}(a^2\plus{}b^2\plus{}c^2)(a\plus{}b)(b\plus{}c)(c\plus{}a)$

Sorry,but $ ab \plus{} bc \plus{} ca \equal{} 1$  :( I cann't  edited my post. Thank you,hungkhtn!


Find all functions $ f: \mathbb R^ \plus{} \rightarrow \mathbb R^ \plus{}$ satisfying $ f(x^y) \equal{} (f(x))^{f(y)}$ for every $ x,y\in\mathbb R^ \plus{}$

[hide]Replace $ y$ by $ mn$ and compute $ f(x^y)$ in two different ways.

What do you conclude?

The used property here is $ a^{(bc)} \equal{} (a^b)^c$. What other properties of multiplication can you use?

What do you conclude with these properties?[/hide]

[hide="Solution!"]$ f(1) \equal{} f(1^1) \equal{} f(1)^{f(1)}$, so $ f(1) \equal{} 1$.

$ f(x) \equal{} 1$ is clearly a solution, so from now on assume $ f(x_0) \ne 1$ for some $ x_0$. Then $ f(x_0)^{f(yz)} \equal{} f(x_0^{yz}) \equal{} f(x_0^y)^{f(z)} \equal{} f(x_0)^{f(y)f(z)}$, so $ f(yz) \equal{} f(y)f(z)$.

Also, $ f(x_0)^{f(y \plus{} z)} \equal{} f(x_0^{y \plus{} z}) \equal{} f(x_0^y x_0^z) \equal{} f(x_0^y) f(x_0^z)$ $ \equal{} f(x_0)^{f(y)} f(x_0)^{f(z)} \equal{} f(x_0)^{f(y) \plus{} f(z)}$, so $ f(y \plus{} z) \equal{} f(y) \plus{} f(z)$.

If $ x > y$, we can write $ x \equal{} y \plus{} z$ for some $ z > 0$, and then $ f(x) \equal{} f(y) \plus{} f(z) > f(y)$, so $ f(x)$ is increasing. Thus $ f(x) \equal{} x^c$ for some constant $ c$ (because if $ f(x) \equal{} x^c$, $ f(y) \equal{} y^d$, then for any integers $ a, b$ with $ x^a < y^b$, $ x^{ac} \equal{} f(x^a) < f(y^b) \equal{} y^{bd}$ since $ f(x)$ is multiplicative, so $ c \le d$, and similarly $ c \ge d$ so $ c \equal{} d$).

From $ f(2)^2 \equal{} f(2*2) \equal{} f(2^2) \equal{} f(2)^{f(2)}$, we get $ f(2) \equal{} 1 \equal{} 2^0$ or $ f(2) \equal{} 2 \equal{} 2^1$, so $ c$ is either $ 0$ or $ 1$, and $ f(x)$ is either $ 1$ or $ x$.[/hide]

Edit: Oh, ninja'd.

Also, hide tags look like a good idea.

[quote="thaithuan_GC"][quote="zeb"]
Thus $ f(x) \equal{} x^c$ for some constant $ c$ (because if $ f(x) \equal{} x^c$, $ f(y) \equal{} y^d$, then for any integers $ a, b$ with $ x^a < y^b$, $ x^{ac} \equal{} f(x^a) < f(y^b) \equal{} y^{bd}$ so $ c \le d$
[/quote]
Why?[/quote]

This is easier to explain if we first assume $ x,y > 1$...

Let $ \frac {ln(y)}{ln(x)} \minus{} \epsilon < \frac {a}{b} < \frac {ln(y)}{ln(x)}$, then from $ x^a < y^b$ we get $ x^{ac} < y^{bd}$ so $ \frac {ac}{bd} < \frac {ln(y)}{ln(x)}$ so $ \frac {c}{d} < \frac {\frac {ln(y)}{ln(x)}}{\frac {a}{b}} < \frac {\frac {ln(y)}{ln(x)}}{\frac {ln(y)}{ln(x)} \minus{} \epsilon}$, true for all $ \epsilon > 0$, so $ \frac {c}{d} \le 1$.

Edit: Ok, there's a simpler way to do it once we know it's multiplicative, additive (unless $ f \equal{} 1$), and increasing (unless $ f \equal{} 1$) - we know that $ f$ acts like the identity on the rationals (unless of course $ f \equal{} 1$), and it's increasing. Whatever. I thought of this way first.


geometry
trapezoid
ratio
geometric transformation
dilation
rotation
geometry proposed

Let ABCD be an orthodiagonal trapezoid (AB || CD), O the common point of its diagonals, M and N the projections of O onto AB, CD respectively, and Q the orthocenter of the triangle ABN.
Prove that the perpendiculars from D onto AN and from C onto BN concur at P on MN and NP = OQ.

Best regards,
sunken rock

To: md45

Orthodiagonal = having perpendicular diagonals.

Best regards,
sunken rock

It is easy, based on the below Lemma (well known and easy to prove).

[b][size=100][color=DarkBlue]LEMMA. - A triangle $ \bigtriangleup ABC$ is given and let $ AD$ be, its altitude. We draw the cemicircle $ (K),$ with diameter the side-segment $ BC,$ which intersects the line segment $ AD,$ at one point so be it $ Z.$ Prove that $ (AD)\cdot (HD) \equal{} (ZD)^{2},$ where $ H$ is the orthocenter of $ \bigtriangleup ABC$[/color][/size][/b].

Kostas Vittas.

[hide]We draw a line through the point $ O$ and parallel to the bases $ AB,\ CD,$ of the given orthodiagonal trapezoid $ ABCD,$ which intersects the line segments $ BQ,\ AQ,$ at points $ E,\ F,$ respectively.

It is enough to prove that $ OE \equal{} ND$ and similarly $ OF \equal{} NC,$ which is equivalent to prove, by [b][size=100]Thales theorem[/size][/b], that $ \frac {MQ}{QO} \equal{} \frac {MO}{ON}$ $ \Longrightarrow$ $ (MQ)\cdot (MN) \equal{} (MO)^{2}$ $ ,(1)$

But $ (1)$ is true, because of the above [b][size=100]Lemma[/size][/b] $ ($ $ Q$ is the orthocenter of the triangle $ \bigtriangleup NAB$ and the point $ O,$ lies on the semicircle $ (K),$ with diameter its side-segment $ AB$ $ ).$ [/hide]
Kostas Vittas.

[quote="sunken rock"]The aim of this problem was to emphasyze the following
[b]Lemma[/b]
[i]Let D be the projection of A onto BC, E the projection of D onto AC and P a point on (DE) such as PE/PD=BD/DC ( * ), ABC being a triangle. Then AP and BE are perpendicular[/i]
(It appeared on this forum some time ago for and isosceles triangle, this being a sort of extention).

Proof: Let R be the projection of B onto AC. Then triangles ADE and BCR are similar, E and P divide similar sides to same ratio, therefore they are similar, and so are AP and BE. As the subject triangles have the correspondent sides perpendicular, it follows that AP and BE are perpendicular too.
From the proof we can see that the said lines are perpendicular iff equality (*) holds.

Now the problem: O is the projection of D onto AC, N the one of O onto CD, so the perpendicular from D onto AN divides ON at the ratio NP'/OP'=OA/OC ( according to (*) ), P' being the intersection of this perpendicular with ON; analogously, the perpendicular from C onto BN divides ON at the ratio NP"/OP"=OB/OD, so P"=P'=P and NP/PO=OA/OC ( 1 ). Then see that the triangles OCP and OAQ are similar, consequently OQ/OP=OA/OC ( 2 ), from (1) and (2) getting OQ = NP.

Best regards,
sunken rock

[/b][/quote]
Dear [b]sunken rock[/b] and dear [b]vittasko[/b]: nice solutions!  I have a slightly different solution for the concurrency, however:
[hide="Solution"]
Let the feet of the perpindiculars of $ D$ and $ C$ on $ AN$ and $ BN$ be $ X$ and $ Y$ respectively and let $ DX$ and $ CY$ meet at $ R$.  It follows that $ \angle ABO \equal{} \angle BDC$ since $ AB\parallel DC$.  Also, $ DX\perp AN$ and $ BQ\perp AN$, so $ BQ\parallel DX\implies \angle OBQ \equal{} \angle ODX$.  We thus find that $ \angle ODC$ and $ \angle ABO$ are equal and are partitioned into the same angles as each other by $ DX$ and $ BQ$ respectively.  Similarly, $ \angle OCD$ and $ \angle OAB$ are equal and they are partitioned into the same angles by $ CY$ and $ BQ$ respectively.  Thus, after a dilation around $ O$, with $ 180$ degrees, with a scale factor of $ \frac {OC}{AO}$ maps $ \triangle AOB$ to $ \triangle COD$ since $ \triangle AOB\sim \triangle COD$ since $ AB\parallel CD$.  Thus, line $ AQ$ maps to line $ CY$ and line $ BQ$ maps to line $ DX$, so after a $ 180$ degree rotation about $ O$, $ Q$ maps to $ R$.  This means that $ Q$, $ O$, and $ R$ are collinear, so $ R$ lies on $ MN$, which means that $ R \equal{} P$, as desired. [/hide]

[quote="sunken rock"][color=darkred]Let $ ABCD$ be an orthodiagonal trapezoid ( $ AB\parallel CD$ ), the common point  $ O$ of its diagonals, the projections $ M$ , $ N$ of $ O$ onto $ AB$ , $ CD$ respectively and the orthocenter $ Q$ of the triangle $ ABN$ . Prove that the perpendiculars from $ D$ onto $ AN$ and from $ C$ onto $ BN$ concur at $ P$ on $ MN$ and $ NP = OQ$ . [/color][/quote]
[color=darkblue][b][u]Proof.[/u][/b]

$ \blacktriangleright$ I"ll apply the [b]Carnot's lemma[/b] to $ \triangle ABN$ and the points $ M$ , $ C$ , $ D$ :

$ (MA^2 - MB^2) + (CB^2 - CN^2) + (DN^2 - DA^2) =$ $ (OA^2 - OB^2) + CB^2 + (ND^2 - NC^2) - AD^2 =$

$ (OA^2 - OB^2) + (OB^2 + OC^2) + (OD^2 - OC^2) - (OA^2 + OD^2) = 0$ . In conclusion,

the perpendiculars from the points $ M$ , $ C$ , $ D$ onto the lines $ AB$ , $ BN$ , $ NA$ are concurrently ( in $ P$ ).

$ \blacktriangleright$ $ \triangle AQB\ \sim\ \triangle CPD\ \implies\ \frac {PN}{MQ} = \frac {CD}{AB} = \frac {ON}{OM}$ . Thus, $ MO^2 = MA\cdot MB = MQ\cdot MN$ $ \implies$

$ \frac {MN}{OM} = \frac {OM}{QM}$ $ \implies$ $ 1 + \frac {ON}{OM} = 1 + \frac {OQ}{QM}$ $ \implies$ $ \frac {ON}{OM} = \frac {OQ}{QM}$ $ \implies$ $ \frac {PN}{QM} = \frac {OQ}{QM}$ $ \implies$ $ \boxed {\ PN = OQ\ }$ .[/color]

[quote="Virgil Nicula"][color=darkred][b][u]An equivalent enunciation.[/u][/b] Let $ ABC$ be an acute triangle with orthocenter $ H$ . Denote the point $ L\in (AH)$

and which belongs to the circle with diameter $ [BC]$ . Construct the points $ \{\begin{array}{c} M\in BL\ ,\ MA\parallel BC \\
 \\
N\in CL\ ,\ NA\parallel BC\end{array}$

and the intersection $ K$ of the perpendiculars from $ M$ , $ N$ onto $ AC$ , $ AB$ . Prove that $ K\in AH$ and $ AK = LH$ .[/color][/quote]
[b][u]Proof.[/u][/b]

$ \blacktriangleright\ \{\begin{array}{ccc} NK\perp AB & \implies & NA^2 - NB^2 = KA^2 - KB^2 \\
 \\
MK\perp AC & \implies & MC^2 - MA^2 = KC^2 - KA^2 \\
 \\
AL\perp MN & \implies & AM^2 - AN^2 = LM^2 - LN^2 \\
 \\
LM\perp LC & \implies & LM^2 + LC^2 = MC^2 \\
 \\
LN\perp LB & \implies & NB^2 = LN^2 + LB^2\end{array}\|\ \bigoplus$  $ \implies$

$ KC^2 - KB^2 = LC^2 - LB^2$ $ \implies$ $ KL\perp BC$ $ \implies$ $ \boxed {\ K\in AH\ }$ . Denote $ D\in BC$ for which $ HD\perp BC$ .

$ \blacktriangleright\ \{\begin{array}{ccccc} \triangle KAM\sim\triangle HDB & \implies & \frac {KA}{HD} = \frac {AM}{DB} & \implies & \frac {KA}{HD} = \frac {LA}{LD} \\
 \\
LD^2 = DB\cdot DC = DH\cdot DA & \implies & \frac {DA}{LD} = \frac {LD}{DH} & \implies & \frac {LA}{LD} = \frac {HL}{DH}\end{array}\|$ $ \implies$

$ \frac {KA}{HD} = \frac {HL}{HD}$ $ \implies$ $ \boxed {\ KA = HL\ }$ .


inequalities
algebra
polynomial
calculus
calculus computations

$ \parallel{}p(x)^k\parallel{}\ \parallel{}p(x)\parallel{} \leq \parallel{}p(x)^{k\plus{}1}\parallel{}$
Is this true?

Hey!

In this case: http://mathworld.wolfram.com/PolynomialHeight.html

Edit: Maybe it is just true in the real case and not for complex coefficients.

This is just false: take $ k\equal{}1$ and $ p(x)\equal{}x^2\minus{}10x\minus{}1$.


inequalities
calculus
algebra unsolved
\/closed

At some point tonight, a whole bunch of forums started showing 0 threads. The threads are still there, and in some cases still accessible; [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=313109]this thread[/url] is reachable as the newest post in its section, even though the unsolved and proposed subforum shows no posts. The test forum shows no posts from the outside, but shows 50 topics when you actually go there.

Forums definitely affected: MS Classroom, MS Contests, HS Basics, HS Intermediate, HS Pre-Olympiad, Algebra Unsolved, Inequalities Proposed, NT Proposed, Calculus U&P, Calculus T&F, Linear Alg U&P, Superior Alg U&P, Intro. Physics, Test forum.

I thought it only happened to me..

Please fix this soon..


[i][color=red]Problem 1[/color][/i]

In the first shape $KB ,KF$ are perpedicular  to $CB,CF$ respectively. $EB//FD$ .Proove that $A$ is the midpoint of $FD$

[i][color=red]Problem 2[/color][/i]

In the second shape ABCD is a parallelogram with $AB=2BC$
$BE$ is perpedicular to $AD$.Proove that  $EMC=3DEM$(angel)

Nice.

[u][b]First problem: [/b][/u]Call $\left\{S\right\}=BF \cap DE$.
$BF$ is the polar of $D$ wrt the circle, so $E$ and $C$ are harmonically divided by $P$ and $D$.
$\Rightarrow BE, BF,BC,BD$ is a harmonic bundle.

Because $DF \parallel BE$, their intersection point lies at infinity.
Hence it has to be true that $\left\{A\right\}=BC\cap DF$ is the midpoint of $\left[DF\right]$.

A question about prob 1:  Isn't $K$ on the circle, because $C$ is on the circle?  Then, because of the similarity of $\triangle{BCE}$ and $\triangle{ACD}$, and Power of a Point, it reduces to showing that $2BC=EC$, which clearly isn't always true...

[u][b]Second Problem:[/b][/u]
We can easiley see that $\vec{AM}= \vec{AD}+\vec{DM}$ and $\vec{MB}=\vec{MC}+\vec{CB}$
This leads us to $\vec{AM}.\vec{MB}=\left(\vec{AD}+\vec{DM}\right).\left(\vec{MC}+\vec{CB}\right)$

Now because $\vec{CB}=-\vec{AD}$ and $\vec{DM}=\vec{MC}$, we can see that the above expression equals $\vec{DM}^{2}-\vec{AD}^{2}=0$
Hence $AM \bot MB$.

Now, clearly $BM$ bisects $\angle ABC$ (Proof: $\left|MC\right|=\left|CB\right|$ so $\angle MBC = \frac{\pi-\angle BCM}{2}= \frac{1}{2}\angle ABC$)
This gives us $\angle AEM = \angle ABM$.

Now, construct point $G$ on $\left[AB\right]$ such that $GM \parallel BC$.
We see that $\angle EMC = \angle GMC+\angle GME = 2\angle AEM+\angle AEM$

Done!

[quote="Jan"]Amen.

K81o7: I think giannis meant that K is the center of the circle, I don't understand your comment. Please look at the diagram[/quote]

I have already looked at the diagram: that's where the confusion arose.  The information given implies KBCF is cyclic.  So if B, C, F are all on the circle, K is too.

I think there is a typo in the question, but anyway, it's clear what he means. CP,CF should be replaced with DP,DF.  :wink:
He just means that DP,DF are tangent to the circle. If my interpretation is incorrect, please let me know giannis and I'll try to find a solution to the new problem, but I think it makes sense this way and it is a nice and easy problem.

Very nice solutions Jan , and yours notes are correctly.
A have another solution using similarity. :)


calculus
integration
function
trigonometry
calculus computations

Find the constants $ a,\ b,\ c$ such that a function $ f(x)\equal{}a\sin x\plus{}b\cos x\plus{}c$ satisfies the following equation for any real numbers $ x$.

\[ 5\sin x\plus{}3\cos x\plus{}1\plus{}\int_0^{\frac{\pi}{2}} (\sin x\plus{}\cos t)f(t)\ dt\equal{}f(x).\]

hello kunny, do you mean
$5\sin(x)+3\cos(x)+1+\int_{0}^{\frac{\pi}{2}}(\sin(t)+\cos(t))f(t)\,dt=f(x)$?
instead of
$ 5\sin x+3\cos x+1+\int_{0}^{\frac{\pi}{2}}(\sin x+\cos t)f(t)\ dt=f(x).$
Sonnhard.

One solution
$5\sin x + 3\cos x + 1 + \int_0^{\frac{\pi }{2}} ( \sin x + \cos t)f(t)\;dt = f(x) \Leftrightarrow $

$5\sin x + 3\cos x + 1 + \sin x\int_0^{\frac{\pi }{2}} {f\left( t \right)} dt + \int_0^{\frac{\pi }{2}} {\cos t} f(t)\;dt = f(x) \Leftrightarrow $

$\left( {5 + \int_0^{\frac{\pi }{2}} {f\left( t \right)} dt} \right)\sin x + 3\cos x + 1 + \int_0^{\frac{\pi }{2}} {\cos t} f(t)\;dt = a\sin x + b\cos x + c$

But

\[\int_0^{\frac{\pi }{2}} {\cos t} f(t)\;dt = \int_0^{\frac{\pi }{2}} {\cos t} \left( {a\sin t + b\cos t + c} \right)\;dt = \]

\[c + \frac{a}{2}\int_0^{\frac{\pi }{2}} {\sin 2tdt}  + \frac{b}{2}\int_0^{\frac{\pi }{2}} {\left( {1 + \cos 2t} \right)dt}  = c + \frac{a}{2} + \frac{{b\pi }}{4}\]

and
\[\int_0^{\frac{\pi }{2}} {f\left( t \right)} dt = \int_0^{\frac{\pi }{2}} {\left( {a\sin x + b\cos x + c} \right)} dt = a + b + \frac{{\pi c}}{2}\]

So
$\left( {5 + a + b + \frac{{\pi c}}{2}} \right)\sin x + 3\cos x + 1 + \frac{a}{2} + \frac{{b\pi }}{4} + c = a\sin x + b\cos x + c \Leftrightarrow $

$\left( {5 + b + \frac{{\pi c}}{2}} \right)\sin x + 3\cos x + 1 + \frac{a}{2} + \frac{{b\pi }}{4} = b\cos x \Leftrightarrow $ , for every real x

For
$\left. {\begin{array}{*{20}{c}}
   {x = 0:4 + \frac{a}{2} + \frac{{b\pi }}{4} = b}  \\
   {x = \pi : - 2 + \frac{a}{2} + \frac{{b\pi }}{4} =  - b}  \\
   {x = \frac{\pi }{2}:6 + b + \frac{{\pi c}}{2} + \frac{a}{2} + \frac{{b\pi }}{4} = 0}  \\
\end{array}} \right\} \Leftrightarrow \begin{array}{*{20}{c}}
   {b = 3}  \\
   {c =  - \frac{{16}}{\pi }}  \\
   {a =  - \frac{{3\pi }}{2} - 2}  \\
\end{array}$

So we have
$f\left( x \right) =  - \left( {\frac{{3\pi }}{2} + 2} \right)\sin x + 3\cos x - \frac{{16}}{\pi }$
the only thing left is to check if it satisfies the ypothesis


My classroom has 11 rows of chairs, with 11 chairs in each row.  The chairs in each row are numbered from 1 to 11.  How many chairs have odd numbers?

Each row has $ 6$ odd numbered chairs (1,3,5,7,9,11), and there are $ 11$ rows, so $ 6\cdot 11\equal{}\boxed{66}$

[quote=Tacy]how do you know its 6 odd numbered chairs.
                   Thank you[/quote]

because you count 1,3,5,7,9,and 11 :-D

[quote=AlexLikeMath]... Why is this in the multiplication principle in counting?[/quote]

I had the same question.

[hide=Answer to @AlexLikeMath]Maybe because you could realize that there are $11$ rows of $6$ odd numbers so you could multiply them to get $\boxed{66}$. [/hide]

This was a relatively easy question.

[hide=Problem Vitals]
Level 11 PA
Level 3 C&P
[/hide]

[hide=Sol]From 1 to 11, the odd numbers are 1, 3, 5, 7, 9, and 11. Since there are 11 rows, 6x11 is 66.[/hide]

Here is[hide=my solution]There are 11 rows, each with 11 chairs. But only 6 of those chairs are odd numbers. So it is 6 $\cdot$ 11 = $\boxed{66}$ chairs.[/hide]. Here is a [hide=mistake]There are 11 rows, 11 columns, and 11 numbers, but only 6 of those are odd. So we do 11 $\cdot$ 11 $\cdot$ = $\boxed{726}$.[/hide]. Here is why it[hide=does not work] This does not work, because the 11 chairs in each row [i]are[/i] the chairs numbered 1 to 11. So we do 11 $\cdot$ 6, not 11 $\cdot$ 11 $\cdot$ 6.[/hide].

[hide=My reasoning][tip=Hover plz][hide=Just to be safe *thumbsup*]So since there are $6$ odd numbers from $1$ through $11$, there are $6$ odd numbers per row. Which means there should be $6\cdot11$ odd seats. Therefore, the answer is $\boxed{66}$. :D[/hide][/tip][/hide]

when you forget that 9 is odd because you just had a problem about the first 5 odd primes :(