algebra
polynomial
calculus
integration
inequalities
combinatorics
polynomial method

Let $ F$ be an arbitrary field, and let $ f \equal{} f\left(z_{1},z_{2},...,z_{k}\right)$ be a polynomial in $ F\left[z_{1},z_{2},\dots,z_{k}\right]$. Suppose that the degree $ \text{deg}\left(f\right)$ of $ f$ is $ \sum_{i \equal{} 1}^{k}t_{i}$, where each $ t_{i}$ is a nonnegative integer. Also suppose that the coefficient of $ \prod_{i \equal{} 1}^{k}z_{i}^{t_{i}}$ in $ f$ is nonzero. Then, if $ S_{1}$, $ S_{2}$, ..., $ S_{k}$ are subsets of $ F$ with $ \left|S_{i}\right| > t_{i}$ for every $ i\in\left\{1,2,...,k\right\}$, then there exist $ s_{1}\in S_{1}$, $ s_{2}\in S_{2}$, ..., $ s_{k}\in S_{k}$ such that $ f\left(s_{1},s_{2},\dots,s_{k}\right)\neq 0$.

This is indeed a revolutionary theorem. Here is where you can read more about this [url=http://www.artofproblemsolving.com/Forum/download.php?id=1239]extraordinary technique[/url].

This theorem, discovered around 1996, has now become a permanent and integral part of every good course in algebraic combinatorics. I have written an article, aimed at high school students, about the numerous applications of the CN to olympiad problems, but it is in Bulgarian, so I won't upload it here. (Though those of you who speak Russian won't have any troubles understanding it). I can translate it into English in the near future, though.  ;) But, sam-n, don't you think it's posted in the wrong forum?  :maybe:  College Playground? Calculus?! I think it would be more appropriate for either the Combinatorics or Algebra section, for it's an algebraic technique in combinatorics.  :P

Here are some nice corollaries of the CN (believe it or not!):

Corollary 1. (The Cauchy-Davenport theorem) If $A, B \subseteq \mathbb{Z}_p$, then $|A+B| \geq \min (p, |A|+|B|-1)$.

Corollary 2. (EGZ) From any $2n-1$ integers one may choose $n$ with sum divisible by $n$.

Corollary 3. (Proposed by Gabriel to MOP) If $p$ is prime and $d \in \mathbb{N}$, then any integer is the sum of $d$ $d$th powers modulo $p$.

Corollary 4. (My problem) Let $G$ be a digraph with no directed cycles. Then, there is a non-empty subset $X \subseteq V (G)$ such that
  (i) If $x \in X$, then $x$ is oriented to an even number of vertices in $X$; and
  (ii) If $x \notin X$, then $x$ is oriented to an odd number of vertices of $X$.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?f=44&t=4658]Corollary 5. (Already discussed in the forum)[/url] If we add an edge to an arbitrary 4-regular multigraph, then the resulting multigraph has a 3-regular subgraph.

Corollary 6. (The celebrated Erd\H{o}s-Heilbronn conjecture) If $A \subset \mathbb{Z}_p$ and $A \dot{+} A = \{a+b \, | \, a, b \in A, a \neq b\}$, then $|A \dot{+} A| \geq \min (p, 2|A|-3)$.

This is only a small sample of the straking corollaries of the Combinatorial Nullstellensatz. This should give you an idea why I call this theorem "revolutionary."  :lol:

--Vesselin

Looks like a very great theorem; I'll try to read the text you linked to (thanks a lot!). I remember having discussed with Peter about Corollaries 1 and 2; if I am not wrong, proving Corollary 2 requires Corollary 1 only in the particular case |B| = 1; this particular case is very easy without any use of advanced theorems, so I would say that Corollary 2 doesn't really require the Combinatorial Nullstellensatz. Am I right?

  Darij

[quote="darij grinberg"] ... I would say that Corollary 2 doesn't really require the Combinatorial Nullstellensatz. Am I right?

  Darij[/quote]

Thus put, you're absolutely right --- Corollary 2 is the celebrated Erd\H{o}s-Ginzburg-Ziv theorem which has over six very different simple proofs. The original proof (from 1961) uses Corollary 1 for the special case $|B|=2$ (not $|B|=1$, in which case the inequality is indeed trivial  :) ). However, one of these proofs --- though not the most simple one --- relies on the Nullstellensatz. But, in reality, none of these corollaries actually *requires* CN --- each was discovered before the CN was invented.  :P

[quote="vess"]Thus put, you're absolutely right --- Corollary 2 is the celebrated Erd\H{o}s-Ginzburg-Ziv theorem which has over six very different simple proofs. The original proof (from 1961) uses Corollary 1 for the special case $ |B| \equal{} 2$ (not $ |B| \equal{} 1$, in which case the inequality is indeed trivial  :) ).[/quote]

Yeah, you're right - sorry. Anyway, for |B| = 2, Corollary 1 is very easy (we can WLOG assume that one of the two elements of B is 0, so that the set A + B contains the set A, and it remains to show that the set A + B contains at least one element not contained in A, what can be easily seen using the fact that the additive group modulo a prime p has no nontrivial subgroup).

  Darij

Vess, I think it would be a great idea to provide a link to the article you mentioned in bulgarian. Many mathlinkers know russian, and an article about Algebric Combinatorics for high school would be great, because I tried to read some articles by N. Alon, but it is too hard for me...
Thank you very much...

corollary 1: assume we would get only $|A|+|B|-2$ values $a_1,...,a_{|A|+|B|-2}$ as sums(if it are even less, just add some zeroes). set $f(x,y)=(x+y-a_1)\cdots (x+y-a_{|A|+|B|-2})$. this is a polynomial of degree $|A|+|B|-2$; the coefficient of $x^{|A|-1}y^{|B|-1}$ is ${|A|+|B|-2\choose |A|-1}\neq 0$ in $\mathbb{F}_p$ since $|A|+|B|-2<p$. so taking $S_1=A$, $S_2=B$, we get a contradiction.

corollary 2: i wonder if one may get it directly from the CN; else take the old proof using corollary 1 in the case $|B|=2$.

corollary 3: we may assume that $d|p-1$; else take $d'=\gcd(d,p-1)$. let $f(x_1,...,x_d)=(x_1^d+...+x_d^d-c)^{p-1}-1$, where $c\in \mathbb{F}_p$ is the number we want to represent. this is a polynomial of degree $d(p-1)$, and the coefficient of $\prod_{i=1}^{d} x_i^{p-1}$ is $(-c)^{\frac{p-1}{d}}\frac{(p-1)!}{(d!)^{\frac{p-1}{d}}}\neq 0$ in $\mathbb{F}_p$. thus, taking $S_1=...=S_d=\mathbb{F}_p$, we get some numbers $x_1,...,x_d$ such that $(x_1^d+...+x_d^d-c)^{p-1}-1\neq 0$; but if we had $x_1^d+...+x_d^d\neq c$, then $(x_1^d+...+x_d^d-c)^{p-1}-1=0$, so we get a desired representation.

corollary 6: (almost the same proof as corollary 1). assume there are only $2|A|-4<p$ sums $a_1,...,a_{2|A|-4}$ (if it are even less, add some zeroes). take $f(x,y)=(x+y-a_1)\cdots (x+y-a_{2|A|-4})(x-y)$. it is a polynomial of degree $2|A|-3$; the coefficient of $x^{|A|-1}y^{|A|-2}$ is ${2|A|-4\choose |A|-2}-{2|A|-4\choose |A|-1}=\frac{(2|A|-4)!((|A|-1)-(|A|-2))}{(|A|-2)!(|A|-1)!}\neq 0$ in $\mathbb{F}_p$ since $2|A|-4<p$. thus, taking $S_1=S_2=A$, we obtain a contradiction.
(note: one might wonder why the proof doesn't work for $2|A|-3$ in place of $2|A|-4$ cause in the last moment, we have one variable more than necessary. however, with $2|A|-3$ the coefficient of $x^{|A|-1}y^{|A|-1}$ was zero.)

Peter

How do you prove $n=k$, in a different way that the one pointed out by Vess in the link?

I see Peter proof and  now i think i understand.

For corrollary 2 assume p is prime.
$x_1,x_2...x_p$ are in $F_p$ and $f(x_1,x_2...,x_p)=(x_1+x_2...+x_p)^{p-1}-1$

Since the degree of $f$ is $p-1$ and the coefficient of  $\displaystyle \prod_{i=2}^p x_i$ is $(p-1)!$ not zero in $Z_p$ Since $t_1=0$ and $t_2=t_3=...=t_p=1$ we need $2p-1$ numbers because $|S_1|=1$ and $|S_2|=|S_3|...=|S_p|=2$.

Finish it as peter did with corollary 3.

Other nice proof is to considere all the sums $(x_1+x_2...+x_p)^{p-1}$ over all subsets of size p from the $2p-1$ numbers, and showing this sum is 0. However there are $\binom{2p-1}{p}$ diferent from zero in $Z_p$ sums, so they cannot all be 1, so one of them is 0!.

I believe Peter's proof of the theorem is wrong. Here is a counter-example to his reasoning:

Let $f=f(x_1,x_2)=x_1^2+x_1x_2-2$, $t_1=t_2=1$ and $S_1=S_2=\{-1,1\}$. Notice that $f(-1,1)=f(1,-1)\neq 0\iff (x_1,x_2)\in\{(-1,1),(1,-1)\}$. On the other hand, in that case(s) the coefficient of $x_1$ is equal to zero and hence we cannot use the induction hypothesis.

Anyhow, two corollaries remain unsolved, so I'll try to complete it now.

[quote="vess"]Corollary 4. (My problem) Let $G$ be a digraph with no directed cycles. Then, there is a non-empty subset $X \subseteq V (G)$ such that
  (i) If $x \in X$, then $x$ is oriented to an even number of vertices in $X$; and
  (ii) If $x \notin X$, then $x$ is oriented to an odd number of vertices of $X$.[/quote]
Let $a_{i,j}\in\{0,1\}$ and $a_{i,j}=1\iff i\leadsto j$ where $i,j\in V$. Consider the following polynomial:
\[P=\prod_{i\in V}\left(\sum_{j\in V}x_ja_{i,j}+x_i\right)=\begin{array}{c}
(x_1+x_2a_{1,2}+x_3a_{1,3}+\cdots+x_{|V|}a_{1,|V|})\cdot\\
(x_1a_{2,1}+x_2+x_3a_{2,3}+\cdots+x_{|V|}a_{2,|V|})\cdot\\
(x_1a_{3,1}+x_2a_{3,2}+x_3+\cdots+x_{|V|}a_{3,|V|})\cdot\\
\cdots\\
(x_1a_{|V|,1}+x_2a_{|V|,2}+x_3a_{|V|,3}+\cdots+x_{|V|})\end{array}\quad(*)\]
It is obviously of degree $|V|$ and the coefficient of $\displaystyle\prod_{i\in V}x_i$ is $1$ because every product other than the "main diagonal" results in $0$ since the graph has no cycles. Hence, in every field, there are $x_i\in\{0,1\}$ such that $P\neq 0$. If we now consider everything modulo $2$ then $P=1$ from which is obvious that every factor in $(*)$ is odd, and hence the assertion (take $i\in X\iff x_i=1$).

[quote="vess"][url=http://www.artofproblemsolving.com/Forum/viewtopic.php?f=44&t=4658]Corollary 5. (Already discussed in the forum)[/url] If we add an edge to an arbitrary 4-regular multigraph, then the resulting multigraph has a 3-regular subgraph.[/quote]
Let $a_{v,e}\in\{0,1\}$ and $a_{v,e}=1\iff v\text{ and }e\text{ are incident}$, where $v\in V,e\in E$. Consider the following polynomial:
\[P=\prod_{v\in V}\left(1-\left(\sum_{e\in E}a_{v,e}x_e\right)^2\right)-\prod_{e\in E}(1-x_e)\]
It is of degree $|E|$ because the first term is of degree $2|V|$ and this is less than $|E|$ because every but two vertex is of degree $4$ and the mentioned two are of degree $5$. The coefficient of $\displaystyle\prod_{e\in E}x_e$ is $(-1)^{|E|+1}$ and obviously not equal to $0$. Hence, over any field, we may choose $x_e\in\{0,1\}$ such that $P\neq 0$. Note that if all of the $x_e=0$ then $P=0$, hence at least one of $x_e$ is $1$. Therefore $\displaystyle 1\neq\left(\sum_{e\in E}a_{v,e}x_e\right)^2$ for each $v$ and considering everything modulo $3$ because of Fermat's little theorem it must be $\displaystyle 3\mid\sum_{e\in E}a_{v,e}x_e$. But since the maximal vertex degree is $5$ therefore $\displaystyle\sum_{e\in E}a_{v,e}x_e\in\{0,3\}$ for each $e$ and we may choose all of the edges $e$ such that $x_e=1$ to form a desired subgraph.

Also, I have one question about Peter's solution of corollary 6). How may we suppose that $2|A|-4<p$?

By the way, Vess's brilliant article is translated into Russian and even published here. Ask me for the file.

@Bojan Basic:I think this's insignificant case.
  Indeed,If $ 2|A| \minus{} 2\geq p$ then assuming that $ |A \plus{} A| < p$ obtain that there exists ome $ c\ne a \plus{} b$ for all $ a\ne b$.Thus,$ |A| \plus{} |A| \minus{} 2 < p$,because for $ a\in A$ s.t $ a\plus{}a\ne c$(there are 2 number dosent satisfy) the number $ b$ st $ a \plus{} b \equal{} c$ must be out of $ A$.

It is always nice to have an answer after two years of waiting. :)

By the way, I see that the Peter’s proof I was refering to is not here anymore. I am not sure about the reason, but I luckily have it preserved. Here it is:

[quote="Peter Scholze"]hmm...noone here gave a proof, though i guess everyone here is able to, but however, here it goes:

let's do it by induction:

the case $ (n\equal{})k\equal{}1$ (i guess $ n\equal{}k$ in general :) ), is trivial since every polynomial of degree $ t_1$ has at most $ t_1$ roots.

so if got $ k\plus{}1$ variables, let's eliminate the last. when taking some value for $ s_{k\plus{}1}$, we get a polynomial in $ k$ variables and we could use the induction hypothesis if the coefficient of $ \prod_{i\equal{}1}^{k} z_i^{t_i}$ is nonzero. but the coefficient of $ \prod_{i\equal{}1}^{k} z_i^{t_i}$ is a polynomial of degree $ t_{k\plus{}1}$ in $ s_{k\plus{}1}$ (remember $ \sum_{i\equal{}1}^{k} t_i\equal{}\deg f$) which has at most $ t_{k\plus{}1}$ zeros, so since $ |S_{k\plus{}1}|>t_{k\plus{}1}$ we get some $ s_{k\plus{}1}$ where it is nonzero.

so, just having seen that this was that easy, let's try some easy corollaries:[/quote]

I also dont think this magnificient theorem could be proven with only such slightly thing  :wink:
  Moreover I've just though corollary 3 could be too solved by the same method as 2nd one  :?: ,with a result states that the number of natural solutions of the equation:
  $ x_o\plus{}x_1\plus{}x_2\plus{}...\plus{}x_{p\minus{}1}\equal{}d$
is $ \binom{d\plus{}p\minus{}1}{p\minus{}1}$
  I will check it as soon as I can... :P

Well, my "proof" was in fact wrong (which is the reason i deleted it). However, one can prove it with very simple methods(even something more general) - look at http://www.mathlinks.ro/Forum/viewtopic.php?t=160415 (leaving those things that are unnecessary for only CNS, this gives a proof of maybe 4 lines).

In fact, we do not need that the degree of $ \prod_{i\equal{}1}^k z_i^{t_i}$ equals the degree of $ f$. We only need that there is no other monomial of the form $ \prod_{i\equal{}1}^k z_i^{s_i}$ with nonzero coefficient such that $ s_i\geq t_i$ for all $ i\equal{}1,...,k$. Still, for most applications, this might not be a significant improvement.

Two things I can't believe that nobody has noticed earlier:

[b]1.[/b]

[quote="Peter Scholze"]corollary 3: we may assume that $d|p-1$; else take $d'=\gcd(d,p-1)$. let $f(x_1,...,x_d)=(x_1^d+...+x_d^d-c)^{p-1}-1$, where $c\in \mathbb{F}_p$ is the number we want to represent. this is a polynomial of degree $d(p-1)$, and the coefficient of $\prod_{i=1}^{d} x_i^{p-1}$ is $(-c)^{\frac{p-1}{d}}\frac{(p-1)!}{(d!)^{\frac{p-1}{d}}}\neq 0$ in $\mathbb{F}_p$.[/quote]

I think this coefficient should rather be $\frac{\left(p-1\right)!}{\left(\frac{p-1}{d}\right)!^d}$. This does not change the solution, of course, since this is still $\neq 0$ in $\mathbb F_p$.

(Also, I don't understand Pascual2005's proof of corollary 2, but there are whole topics devoted to corollary 2: http://www.artofproblemsolving.com/Forum/viewtopic.php?t=57546 http://www.artofproblemsolving.com/Forum/viewtopic.php?t=28929 http://www.artofproblemsolving.com/Forum/viewtopic.php?t=355012 .)

[b]2.[/b] Corollary 4 is easier to prove without the Combinatorial Nullstellensatz than with it.

[quote="vess"]Corollary 4. (My problem) Let $G$ be a digraph with no directed cycles. Then, there is a non-empty subset $X \subseteq V (G)$ such that
  (i) If $x \in X$, then $x$ is oriented to an even number of vertices in $X$; and
  (ii) If $x \notin X$, then $x$ is oriented to an odd number of vertices of $X$.[/quote]

Let us slightly extend this corollary:

[color=blue][b]Corollary 4a.[/b] Let $G$ be a digraph with no directed cycles such that $V\left(G\right)\neq\emptyset$. Then, there is a non-empty subset $X \subseteq V (G)$ such that
  (i) For every $x \in X$, the number of all edges starting at $x$ and ending at a vertex in $X$ is even; and
  (ii) For every $x \notin X$, the number of all edges starting at $x$ and ending at a vertex in $X$ is odd.
[/color]

Corollary 4a is clearly equivalent to Corollary 4 when the digraph $G$ has no multiple edges, but is stronger otherwise:

[i]Proof of Corollary 4 from Corollary 4a.[/i] Replace all multiple edges in the graph $G$ by simple edges, and denote the resulting graph by $G^{\prime}$. Then, Corollary 4 for the graph $G$ is clearly equivalent to Corollary 4a for the graph $G^{\prime}$. Thus, Corollary 4 follows from Corollary 4a.

[i]Proof of Corollary 4a.[/i] In the following, "walk" will mean "directed walk in $G$". For every vertex $x$ of $G$, the empty walk $\left(x\right)$ (with no edges) will count as a walk.

Let $n=\left|V\left(G\right)\right|$. Then, every walk in $G$ of length $> n$ must pass through some vertex twice (by the pigeonhole principle), and thus contains a directed cycle, which is impossible (since $G$ has no directed cycles). Thus, every walk in $G$ must have length $\leq n$. Hence, there are only finitely many walks in $G$.

For every vertex $x$ of $G$, let $p\left(x\right)$ denote the number of walks in $G$ starting at $x$. (This is well-defined since there are only finitely many walks in $G$.)

Let $X=\left\{x\in V\left(G\right) \mid p\left(x\right)\text{ is odd}\right\}$.
We claim that this set $X$ satisfies the two assertions (i) and (ii) and is nonempty.

In fact, let $x\in V\left(G\right)$ be arbitrary. Let $e_1$, $e_2$, ..., $e_m$ be all the edges of $G$ starting at $x$ (numbered in such a way that $e_1$, $e_2$, ..., $e_m$ are pairwise distinct), and let $y_1$, $y_2$, ..., $y_m$ be the endpoints of these respective edges. Then, every nonempty walk starting at $x$ begins with one and only one of the edges $e_1$, $e_2$, ..., $e_m$. Therefore,

[color=green][b](1)[/b][/color] (number of all nonempty walks starting at $x$) = $\sum_{i=1}^m$ (number of all walks starting at $x$ and beginning with the edge $e_i$).

Hence,

(number of all walks starting at $x$) = (number of all nonempty walks starting at $x$) + $1$ (since there exists one and only one empty walk starting at $x$)
= $\sum_{i=1}^m$ (number of all walks starting at $x$ and beginning with the edge $e_i$) + $1$ (by [color=green][b](1)[/b][/color]).

For every $i\in\left\{1,2,...,m\right\}$, there is a bijection

(set of all walks starting at $y_i$) $\to$ (set of all walks starting at $x$ and beginning with the edge $e_i$)

(this bijection maps every walk $u$ starting at $y_i$ to the walk which is obtained by adding the edge $e_i$ to the beginning of the walk $u$). Hence, for every $i\in\left\{1,2,...,m\right\}$, we have

|set of all walks starting at $y_i$| = |set of all walks starting at $x$ and beginning with the edge $e_i$|.

Since

|set of all walks starting at $y_i$| = (number of all walks starting at $y_i$) = $p\left(y_i\right)$

and

|set of all walks starting at $x$ and beginning with the edge $e_i$| = (number of all walks starting at $x$ and beginning with the edge $e_i$),

this rewrites as

$p\left(y_i\right)$ = (number of all walks starting at $x$ and beginning with the edge $e_i$).

Hence,

$\sum_{i=1}^m p\left(y_i\right) + 1$ = $\sum_{i=1}^m$ (number of all walks starting at $x$ and beginning with the edge $e_i$) + $1$
= (number of all walks starting at $x$) = $p\left(x\right)$.

But it is easy to see that whenever $a_1$, $a_2$, ..., $a_m$ are some integers, we have

[color=green][b](2)[/b][/color] (the number of all $i\in\left\{1,2,...,m\right\}$ such that $a_i$ is odd) $\equiv \sum_{i=1}^m a_i\mod 2$.

Now,

(the number of all edges starting at $x$ and ending at a vertex in $X$)
= (the number of all $i\in\left\{1,2,...,m\right\}$ such that the edge $e_i$ ends at a vertex in $X$) (because the edges starting at $x$ are $e_1$, $e_2$, ..., $e_m$)
= (the number of all $i\in\left\{1,2,...,m\right\}$ such that $y_i \in X$) (because the edge $e_i$ ends at $y_i$)
= (the number of all $i\in\left\{1,2,...,m\right\}$ such that $p\left(y_i\right)$ is odd) (since $y_i \in X$ is equivalent to $p\left(y_i\right)$ being odd, by the definition of $X$)
$\equiv \sum_{i=1}^m p\left(y_i\right)$ (by [color=green][b](2)[/b][/color], applied to $a_i=p\left(y_i\right)$)
[color=green][b](3)[/b][/color] $= p\left(x\right) - 1\mod 2$ (since $\sum_{i=1}^m p\left(y_i\right) + 1 = p\left(x\right)$).

For every $x\in X$, the number $p\left(x\right)$ is odd (by the definition of $X$), so that [color=green][b](3)[/b][/color] yields that the number of all edges starting at $x$ and ending at a vertex in $X$ is even. This proves (i).

For every $x\notin X$, the number $p\left(x\right)$ is even (by the definition of $X$), so that [color=green][b](3)[/b][/color] yields that the number of all edges starting at $x$ and ending at a vertex in $X$ is odd. This proves (ii).

Thus, the set $X$ satisfies assertions (i) and (ii).

Also, $X$ is nonempty (otherwise, (ii) would yield that for every $x\in V\left(G\right)$, the number of all edges starting at $x$ and ending at a vertex in $X$ would be odd; but this clearly contradicts the assumption that $X$ be empty). Corollary 4a is thus proven.

[i]Remark.[/i] The above proof of Corollary 4a was completely elementary, but probably the easiest way to come up with it is using linear algebra: We have to prove the existence of a vector $x\in \mathbb F_2^{V\left(G\right)}$ such that $Ax-x=e$, where $A$ is the (directed) adjacency matrix of $G$ and $e$ is the vector all of whose coordinates are $1$'s. This is equivalent to $\left(A-I\right)x=e$. Now it turns out that $A$ is nilpotent since $G$ has no directed cycles, so the matrix $A-I$ is invertible with inverse $I+A+A^2+A^3+...$ (this series converges in the sense that $A^i$ is zero for every $i > \left|V\left(G\right)\right|$). Hence, explicitly $x=\left(I+A+A^2+A^3+...\right)e$. This translates into the definition of $X$ I gave above.

Another interesting application of the theorem is to prove a nice characterisation of prime numbers as being sizes of finite fields whose elements can be separated into pairs with prescribed distances, for any set of distances.
More precisely, it says the following  :
[b]Combinatorial characterisation of prime numbers (source : E. Preissmann & M. Mischler)[/b]
Let $n$ be a positive integer. Then for any given $d_1, d_2, ... , d_n \in \{1,2,...,n\}$ we can partition $\mathbb{Z}_{2n+1}$ as $$\mathbb{Z}_{2n+1} = (0) \cup (\alpha_1 , \alpha_2 , ... , \alpha_n) \cup (\beta_1, \beta_2 , ..., \beta_n),$$ satisfying, $\beta_i - \alpha_ i = d_i, ~~ \forall i \in \{ 1,2, ... ,n \}$, if and only if $2n+1$ is a prime number.

This lemma, was later reworked and extended to a much generalised setup by professors Fedor V. Petrov and R. N. Karasev (see citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.752.67&rep=rep1&type=pdf ).

Recently I prepared an essay on Combinatorial Nullstellensatz, and wanted to share here for reference.

Thank you! Side note: You have a great style :D


Let x,y,z are positive numbers such that $ x\plus{}y\plus{}z\equal{}1$. Prove that
$ 2(\frac {x}{y}\plus{}\frac yz\plus{}\frac zx)\ge \frac {1\plus{}x}{y\plus{}z}\plus{}\frac {1\plus{}y}{z\plus{}x}\plus{}\frac {1\plus{}z}{x\plus{}y}$
  :D

the inequality is equivalent to:
$ \sum {\frac{x}{y}} \minus{}\sum {\frac{x}{y\plus{}z}}\geq\frac{3}{2}$
$ \Leftrightarrow \sum_{cyc} {\frac{xz}{y(y\plus{}z)}}\geq\frac{(xy\plus{}yz\plus{}zx)^2}{2xyz(x\plus{}y\plus{}z)}\geq\frac{3}{2}$
 this is another proof
$ 2(\frac{x}{y}\plus{}\frac{y}{z}\plus{}\frac{z}{x})\geq\sum_{cyc} {\frac{1\plus{}x}{y\plus{}z}}$
$ \Leftrightarrow M*(x\minus{}y)^2\plus{}N*(x\minus{}z)(y\minus{}z)\geq 0$
assume that $ z\equal{}min (x;y;z)$ and  $ M\equal{}\frac{z^2\plus{}yz\plus{}xy}{xz}>0, N\equal{}\frac{1}{xz} \minus{}\frac{x\plus{}y\plus{}2z}{2(x\plus{}y)(y\plus{}z)(z\plus{}x)}>0$
Now,we are done! :D

Why is this true?

[quote="toanIneq"]$ \sum_{cyc} {\frac{xz}{y(y\plus{}z)}}\geq\frac{(xy\plus{}yz\plus{}zx)^2}{2xyz(x\plus{}y\plus{}z)}$[/quote]

?

 :)

Multiply each $ \frac{xz}{y(y\plus{}z)}$ through by $ xz$, so $ \frac{x^2z^2}{xyz(x\plus{}y)}$. Now apply cauchy in engel form, heuristically summing over the bottom fractions as well as the insides of the top square. :)


search
modular arithmetic
induction
number theory
number theory unsolved

I was thinking about this problem:

http://www.mathlinks.ro/viewtopic.php?search_id=1597502048&t=150373

and trying to find out if it can be solved with modular arithmetic. But then I discovered that x^2-15xy+y^2=-1 (mod n) is solvable modulo every n. So you can't use modular arithmetic to solve the problem, because modulo every n the equation x^2-kxy+y^2=-1 has a solution in which k is not 3.

But I can't prove it  :oops: :
I can't prove that x^2-15xy+y^2=-1 (mod n) is solvable (in integers of course) modulo every n.
help please  :)

So You need us to show $ x^2\minus{}15xy\plus{}y^2\equiv \minus{}1\pmod n$ is sovable, here some hints:
1) [hide]If $ 5\nmid n$ then put $ x\equal{}2y$ and $ 5y\equiv 1\pmod n$.[/hide]
2) [hide]If $ n\equal{}5^a$ for some positive integer $ a$, then just prove it by induction on $ a$.[/hide]
3) [hide]Use the Chinese Remainder theorem to get your requirement.[/hide]

Thank you very much, I used your hints and solved the problem. :)


[hide="2"]So its a 144 in by 225 in rectangle. That has an area of 32400 in. Divide that by 81 in to get 400 square tiles.[/hide]

[hide=" The answer to #1 is..."]$x = 1$ child

$y = 1$ adult

$z$ = elevator max weight

$(i) 20x = z$
$(ii) 15 y = z$

$(iii) 12x+Ky = z$

$K$ is the coefficient of $y$

from $(i) and (ii)$ we get $(iiii) 20x = 15 y$

$x= \frac{15y}{20}$
we multiply that by 12
$12x = 12 \times \frac{15y}{20}$
$12x = 9y$
we change the variable in the 3rd equation

from $(ii) (iii)$ and $(iiii)$ we get $9y+Ky = 15y$

we get rid of the y and get $9+K = 15$
thus $K=15-9 =6$

so if there are 12 children in the elevator, then it could also fit with 6 adults.
QED[/hide]

#2

ckck,

you are missing needed "square inches" or "sq. in." in your calculations to make your work accurate (foremost) and also to be more complete.

[quote="rise89"]Hello everyone, got two brain teasers for ya. Please show your work, Enjoy!

1. "Elevator"

The capacity of an elevator is either 20 children or 15 adults. If 12 children are currently in the elevator, how many adults can still get in?

2. "Floor Tiles"

How many 9-inch-square floor tiles are needed to cover a rectangular floor that measures 12 feet by 15 feet?[/quote]

[hide="#2"]
12*12=144
15*12=180

so it's 180x144=20x16 rectangle with the square tiles
=320[/hide]

[quote="lotrgreengrapes7926"][quote="rise89"]1. "Elevator"

The capacity of an elevator is either 20 children or 15 adults. If 12 children are currently in the elevator, how many adults can still get in?[/quote]
Same problem, but this time, its capacity isn't exactly 20 children, but in the interval of $[20,21)$ children, and $[15,16)$ adults.[/quote]

uhhh half a child and half an adult don't exist, so same answer


How many way to arrange some stones in a grid n*n (a cell either has only one stone or nothing)
such that the number of stones in every rows and every columns is an odd number.

:roll:

What if we request that the number of stones in each row and each column be the [i]same[/i] odd number?

Unfortunately, I don't have a solution.  If the odd number is $ 1$ or $ n$ or $ n\minus{}1$, it is easy.  What if it is $ 3$?


Suppose that all the letters of the english alphabet are arranged in a circle. Prove that there must be five
consecutive consonants.

[hide="By No Way Rigorous"]
$ C_{1}\ V_{1}\ C_{2}\ V_{2}\ C_{3}\ V_{3}\ C_{4}\ V_{4}\ C_{5}\ V_{5}\ C_{6}\ C_{7}... C_{21}$
There are not enough of vowels to prevent all the consonants from being consecutive.
EDIT Spelling  :oops:
[/hide]

[quote="AstroPhys"][hide]
$ C_{1}\ V_{1}\ C_{2}\ V_{2}\ C_{3}\ V_{3}\ C_{4}\ V_{4}\ C_{5}\ V_{5}\ C_{6}\ C_{7}... C_{21}$
There are not enough of vowels to prevent all the consonants from being consecuative.
[/hide][/quote]

actually if you wanted to use that argument you would have to put 4 consanets between each vowel

The easiest way to prove this rigorously is to use pigeonhole. I'm pretty sure that "There are not enough of vowels to prevent all the consonants from being consecuative." doesn't constitute a rigorous proof, so here goes:

Assume to the contrary that it is possible to arrange the letters so that there are no more than four consecutive consonants. However, since there are 21 consonants and only five vowels ($ 4\cdot5=20$), you can pigeonhole the last consonant into creating a string of five consecutive consonants. We have a contradiction.

[hide]To be even more explict, place the 5 vowels on the circle. Let the holes be the places between adjacent vowels; there are 5 holes. Let the cosonants be the pidgeons. We have that one hole must have $ \left\lceil\frac{21}{5}\right\rceil=5$ consonants, as desired.[/hide]

[hide="1 quick question"]
Ummm $ y$ can be considered a vowel for $ \frac{1}{2}$ the time here I think. So...  now it's true only half the time?[/hide]


[quote="4everwise"]When the base of a triangle is increased $10\%$ and the altitude to this base is decreased $10\%$, the change in area is

$\text{(A)} \ 1\%~ \text{increase} \qquad \text{(B)} \ \frac12 \%~ \text{increase} \qquad \text{(C)} \ 0\% \qquad \text{(D)} \ \frac12 \% ~\text{decrease} \qquad \text{(E)} \ 1\% ~\text{decrease}$[/quote]

[hide] Area of the original triangle: $\frac{1}{2}bh$.

$b_1= \frac{11}{10}b$.

$h_1=\frac{9}{10}h$.

Finally, new triangle's area: $\frac{1}{2}* \frac{11}{10}b* \frac{9}{10}h=\frac{99}{200}bh$.
Then, the area decrease $1\%$, so the answer is $\boxed {E}$[/hide]

[quote="Woohoo"]I disagree:
1/2*10/10*10/10=100/200=50%
1/2*11/10*9/10=99/200=49.5%
Thus it is a decrease in 0.5%
So the correct answer should be [i][b]D[/b][/i]1/2% decrease
(OR AM I WRONG :maybe: )[/quote]

you are wrong.  since there is nothing squared or cubed or whatever, you dont even need the forumulas.

[hide]1.1*.9=.99

which is a 1 percent decrease. E[/hide]

[quote="Woohoo"]I disagree:
1/2*10/10*10/10=100/200=50%
1/2*11/10*9/10=99/200=49.5%
Thus it is a decrease in 0.5%
So the correct answer should be [i][b]D[/b][/i]1/2% decrease
(OR AM I WRONG :maybe: )[/quote]
Actually, your mistake starts when you say, "Thus it is a decrease in 0.5%."  It is actually .5%*100/50=1%, since you are looking at how much percent is .5% of 50% (sorry, this is kind of confusing).

[quote="ckck"][quote="4everwise"]When the base of a triangle is increased $10\%$ and the altitude to this base is decreased $10\%$, the change in area is

$\text{(A)}\ 1\%~ \text{increase}\qquad \text{(B)}\ \frac12 \%~ \text{increase}\qquad \text{(C)}\ 0\% \qquad \text{(D)}\ \frac12 \% ~\text{decrease}\qquad \text{(E)}\ 1\% ~\text{decrease}$[/quote]
[hide]These kinds of problems I just plug in numbers. Say that the base is 20 and the altitude is 10, so the area is 100. Then the 10% increase and drop means that the new base and altitude are 22 and 9 respectively. So the new area is 99. Since form 100 to 99 is easy calculated it is a 1% decrease or E.[/hide][/quote]

chris, good luck with that method when it comes up in countdown.  :P


I wanted to create a fun new game for FF and here's how it works:  I start by posting a quote and the next person has to say who said it and then come up with a new quote.  If it takes more than 12 hours for someone to guess, that person gets 10 points and I will post a new quote.

We'll start with an easy one:  "Imagination is more important than knowledge".

Albert Einstein.

Easy one:

$ \text{Eeeekuals um see square...}$


What is the smallest number between 50 and 100 which can be written as the product of two primes?

Does doesnt seem like a real Chapter Competition Problem.  :huh:

No offense math12514, your solution was great!


Yeah, just use backwards change-of-base formula and the rest follows.

[quote="amirhtlusa"]that simplifies to four ;)[/quote]
Yea i forgot to put the last step :blush:

[quote]Simplify $\frac{\log_2 a^3b-\log_2 a^2b}{\log_4\sqrt a}$.[/quote]
[hide]
Numerator:$\log_2 {a}$
denomemator:$log_2 {\sqrt[4]{a}}$
[b]4[/b]
[/hide]


well, I'm not [i]against[/i] america, but I'm not exactly Wonder Woman - I mean Wonder Man.

isnt this in the round table, and the poll forum....

No, it used to be in the Round Table and the Polls and then they both got moved to G&FF  :( .

The USA has ruined my life yet helped it in many ways.

yeah me too...

i have a love-hate relationship with spaghetti

i mean i love it, but i always burn my tongue  :P see? its red.

I love the United States.  However, there may be times where I hate how it is being run, such as now.

i have a hate-dislike relationship with america. although if you're talking food, i have a hate-loathe relationship with fast food. i have a love-like relationship with chinese food, but not really patriotic to the country ('cause i live in america.) so really, the only country i'm truly patriotic to is my very own Lalaland.  :D


calculus
integration
function
trigonometry
logarithms
calculus computations

One of my exam questions in the first semester was integration of this same subintegral function, but the interval was $ (0,\frac {\pi}{2})$. That one had a pretty clean solution using the fact that the log cos and log sin integrals on that interval were same. Here, no such equivalence can be made, so I ended up in numerical methods... Is there an "elementary solution"? A possible method could be maybe transforming it in sines (changing the bounds), then in a sine of double angle... But then it's  pretty hard to get some sort of equivalence between the integrals that appear... And exactly that equivalence was the "trick" for solving the (much easier) [url=http://math.ucsd.edu/~ebender/20B/7_DefInt.pdf]integral[/url] I mentioned earlier.

It most likely doesn't have an elementary antiderivative. Since the limits aren't nice, that means no exact solution.

As far as antiderivative is concerned, I'm positive that it isn't elementary. The solution I've got numerically is -0.166. And I'm 99% sure that it can't be expressed through $ \ln 2$, $ \sin \ln 2$, $ \sin 1$ and similar constants which would be logical...


Prove that for every positive integer $n$ and every positive real $a$
\[a^n+\frac{1}{a^n}-2\geq n^2\left(a+\frac{1}{a}-2\right)\]

$\displaystyle a^n+\frac{1}{a^n}-2\geq n^2\left(a+\frac{1}{a}-2\right)\Leftrightarrow (a^n-1)^2\ge n^2\cdot a^{n-1}(a-1)^2\Leftrightarrow (a^{n-1}+...+1)^2\ge n^2\cdot a^{n-1}$
 the last inequality follows from $a^{n-k}+a^{k-1}\ge 2a^{\frac{n-1}{2}},k\ge 1$

[quote="mathpk"]$(\sqrt{a})^{n}+\frac{1}{(\sqrt{a})^{n}} \geq n(\sqrt{a}+\frac{1}{\sqrt{a}}) $[/quote]

It's false (For exemple when a=1) :P  :P  :P

Did you mean ?

$|(\sqrt{a})^n-\frac{1}{(\sqrt{a})^n}| \ge n|\sqrt{a}-\frac{1}{\sqrt{a}}|$


allright, no-one is posting any problems, so I will commence with starting the "olympiad geometry challenges". BTW, I do have the answers but have not looked at them yet.

Inequalities should not go under algebra. They are closer to analysis.


inequalities
LaTeX
linear algebra
matrix
geometry
geometric transformation
rotation

Suppose that $ u \equal{} (x,y,z)$ and $ v \equal{} (y,z,x)$ are both unit vectors. What is the range of the inner product $ k \equal{} u \cdot v$?

In other words, what values does the inner product $ k \equal{} u \cdot v$ take?

If the inner product is dot product, then :
[hide]
$ xy\plus{}yz\plus{}xz \leq x^2\plus{}y^2\plus{}z^2$
Proof :
$ 0 \leq 0,5x^2\plus{}0,5y^2\minus{}yx \equal{} 0,5(x\minus{}y)^2$
$ 0 \leq 0,5x^2\plus{}0,5z^2\minus{}zx \equal{} 0,5(x\minus{}z)^2$
$ 0 \leq 0,5z^2\plus{}0,5y^2\minus{}yz \equal{} 0,5(z\minus{}y)^2$
Adding all the inequality to obtain that :
$ xy\plus{}yz\plus{}xz \leq x^2\plus{}y^2\plus{}z^2$
Then we can conclude that $ u.v \leq 1$
The equality holds when : $ x\equal{}y\equal{}z$
The dot product can attain negative infinity
For example, take $ x\equal{}0$ then take $ y\equal{}\minus{}z$, then $ u.v\equal{}\minus{}z^2$, take $ z$ as large as possible, it attains negative infinity.
Sorry if I am wrong.
[/hide]

The lower limit is not $ -\infty$, because we have the restriction $ x^2+y^2+z^2=1$, and that forces each variable to be $ \le 1$ in absolute value.

Notation note: Use . rather than , for the decimal separator, at least when dealing with Americans. $ \text{\LaTeX}$ puts a bit of space after a comma, so it looks bad without negative space to counter that. For the dot product, use \cdot.

From mucking around with Lagrange multipliers, I believe that the range is $ \left[\minus{}\frac12,1\right].$

One place where the maximum is achieved is $ (x,y,z)\equal{}\frac1{\sqrt{3}}(1,1,1).$

One place where the minimum is achieved is $ (x,y,z)\equal{}\frac1{\sqrt{6}}(1,\minus{}2,1).$

Here's a better way to look at this:

The transformation that sends $ (x,y,z)$ to $ (y,z,x)$ is given by an orthogonal matrix $ T$ that satisfies $ T^3\equal{}I.$ Physically, this matrix is a 3-fold rotation.

The one real eigenvalue of $ T$ is $ 1,$ and the eigenvector associated with that eigenvalue is $ (1,1,1).$ This is the direction of the axis of rotation. If $ u$ lies in this direction, then $ v\equal{}Au\equal{}u$ and $ u\cdot v\equal{}\|u\|^2,$ which in turn equals $ 1$ for $ \|u\|^2\equal{}1.$

Now take any $ u$ that is orthogonal to the axis of rotation and of length $ 1.$ Since $ T$ is an orthogonal matrix (a rotation), we have that $ \|v\|\equal{}\|Tu\|\equal{}1$ as well. Since $ T$ preserves angles as well as distances, we still have that $ v$ is orthogonal to the axis of rotation. So $ u$ and $ v$ both belong to the plane orthogonal to $ (1,1,1).$ Since $ T^3\equal{}I,$ we must have that $ T$ acts on this plane by rotating by $ \frac{2\pi}3.$ Hence the angle between $ u$ and $ v$ is $ \frac{2\pi}3$ and $ u\cdot v\equal{}1\cdot1\cdot\cos\left(\frac{2\pi}3\right)\equal{}\minus{}\frac12.$

Since the unit sphere is connected and $ u\cdot (Tu)$ is a continuous function of $ u,$ then the range of this mapping must be an interval.

A proof that $ \minus{}\frac12$ is minimal:

$ (x\plus{}y\plus{}z)^2\equal{}(x^2\plus{}y^2\plus{}z^2)\plus{}2(xy\plus{}yz\plus{}zx)\ge 0$. Rearranging, $ 1\equal{}x^2\plus{}y^2\plus{}z^2\ge \minus{}2(xy\plus{}yz\plus{}zx)\equal{}\minus{}2(u\cdot v)$

... another proof using linear algebra which can easily be generalized to higher dimensions: the function to be considered is the quadratic form on $ \mathbb R^3$ induced by the symmetrization $ S$ of Kent's matrix $ T$. Since $ S$ can be [b]orthogonally[/b] diagonalized, the minimum of the function on the unit sphere is the minimal eigen value of $ S$, i.e. the minimum of $ \{\minus{}\frac{1}{2},1\}$, hence $ \minus{}\frac{1}{2}$.


calculus
integration
trigonometry
calculus computations


Billy Bob is going to the annual pie eating contest. He has to eat a small pie and large pie in each of these flavors: apple, blueberry, pecan, blackberry, and cherry. In how many ways can he eat all the pies? (order counts)

[hide]You better write that as "10!"....3628800 is just too big for me  :D   [/hide]

[hide]10 different pies, so 10![/hide][/quote]


I find that writing up a physics homework that has 4 problems with 3-6 parts each can take 3-4 hours of focused work, AFTER I have all the answers down on scratchwork.

And I'm not at all new to LaTex, I've been using it on this forum and my blog for a while, although I have really only started writing entire documents in LaTeX two weeks ago.

I was wondering how long it takes for those of you who type their math homework to do so, as well as how long it takes for people to hand-write their homework in a neat, organized, scrutinized format for handing in for grading. Assume your homework is around the same size as my physics homework. If it takes far less time to hand-write homework, I may consider doing some things hand-written, although I am more likely to keep doing LaTeX and just devote more time on my schedule to the write-up. In high school I never had to hand in homework -- the teacher only checked it, so you see I don't have much experience to draw on when thinking of how long it takes to hand-write a fine-tuned pass-in homework.

EDIT: I should note that I only have one physics homework per week. With math, I have one homework and one coursework learning sheet per week.

Don't do your homework in $ \text{\LaTeX}$.  It takes a very long time, correcting errors, making sure everything is right.  I tried it and will not be doing it agian.  Maybe when you have to write very elaborate proofs with very advanced symbols it is a good idea, but otherwise probably not.

Well, you could always Latex your homework in your blog, then copy and paste it into Microsoft Word, where you can edit the texts if you want to. I texed my Chemistry homework once in the downloaded software, it was tedious like you said. Then I blocked my blog to only I can view it and type up all my fancy mathematical work there. It saves a ton of time and looked nice.

Hope this helps.

I've been doing my work in $ \text{\LaTeX}$ for two years now, in addition to the time I spent learning math mode on the forum before that. It definitely gets faster- I average about one or two errors per document on first typeset now.

I wouldn't do the mixed version- TeX is a full-featured typesetting language, not just a tool for pretty math. I've basically abandoned the word processor entirely.
My two biggest reasons to do homework this way: I have ugly handwriting, and I like having the clean copy saved.

JRav: For physics homework it is very time-consuming, with lots of eqnarrays and stuff. Homework for my physics class just doesn't go as smoothly as math proofs when it comes to typing it up. For math homework I find it is not as time-consuming, though the extra time is still something to consider. I wouldn't want to give up doing my math homework in LaTeX (yet), but maybe my physics homework.

jeez123: I don't really see how writing LaTeX document-style would be more time-consuming than blog-style. I have the same fast-preview option in my front-end, and I can't really think of anything else that may be different.

jmerry: How much more time do you think it takes you to type up math homework in LaTeX than it would take hand-written? Do you type up homework from other subjects, and do you see any difference in how much time it takes for different subjects?

Thanks for the replies.

EDIT: What font size do you use for LaTeX? I use 12pt, because in my experience with the fonts I use anything less is hard to read. But LaTeX may use a font that's readable when set to 10pt or 11pt. I'd print it out and see for myself but I'd like other opinions and printing costs money + time t.t.

I typed all of my homework for graduate classes, mostly because it made it easier to rewrite it. The first (and probably second) versions are never good enough for me.

Also, typed homework is much easier to grade. If I were teaching a graduate math class, I'd give bonus points for homework assignments done with LaTeX. (Don't think this would work in calculus, though.)

I'm a graduate student, so other subjects aren't an issue. As an undergrad, I didn't know $ \text{\LaTeX}$ at all.
Most of the time that goes into it is writing- how to translate an idea into a proof. The time that goes into typesetting is offset by the easy editing- I don't have to rewrite everything if there's a flaw in the first draft.

I also type all of my math homework in LaTeX. Freshman year, I didn't type physics, because (as others have said) it's more tedious, and also I was a beginner with LaTeX then.

Now, like jmerry, I almost never make syntax errors. I'd say that it probably takes me about 50% longer to typeset a problem set than it would to write it by hand, but if I wrote by hand then I might have to redo things when I make mistakes, which (again, as people have already said) may make hand-writing take far longer (especially if you insist on turning in neat problem sets).

I recommend using LaTeX. As you practice it, you'll get faster at doing all the things that come up frequently, and you'll make fewer errors. Eventually, you'll wonder why you ever hand-wrote things at all!

I use LaTeX to write up homeworks that I submit online, but not for ones that I can hand in personally. It probably takes me two hours to type up about four pages if I haven't done the scrap work beforehand, but my code is ugly; I don't leave space or indent or do anything to differentiate different sections or equations. That means correcting errors takes much longer than it has to. I feel like I need more experience with LaTeX to use it regularly.

I've started using unruled paper and it seems neater. I wrote up a problem set today in about 40 minutes. In general, I think writing $ \binom{n}{\lfloor\frac{n}{2}\rfloor}$ is faster than typing \binom{n}{\lfloor\frac{n}{2}\rfloor}. However, I've been told that my handwriting is amazing, so the neatness might vary for you. Xevarion brings up a good point about correcting errors, but I don't mind a crossed-out line here or there, and I don't think my graders do, either.


When the circumference of a toy balloon is increased from 20 inches to 25 inches, the radius is increased by:
\[ \text{(A)}\ 5\ \text{in.} \qquad \text{(B)}\ 2\frac{1}{2}\ \text{in.} \qquad \text{(C)}\ 5/\pi\ \text{in.} \qquad \text{(D)}\ 5/2\pi\ \text{in.} \qquad \text{(E)}\ \pi/5\ \text{in.} \]

[hide]D.  The radius was originally $\frac{10}{\pi}$, and the new radius is $\frac{12.5}{\pi}$.[/hide]

[quote="4everwise"]No, actually it's not C [quote]C. The radius was originally , and the new radius is . [/quote]

The reason for this is: [hide]The increase was 2.5/(pi) Since you can't have decimal fractions, multiply top and bottom by 2 to get

D 5/2(pi)[/hide][/quote]Woopsies, I will edit my post.  I had the correct answer but wrote the wrong letter.  :blush:

[hide]

Increase: 5=2r * pi
r= 5/2pi

Answer: D [/hide]


Does anyone know how to make the closed loop integral sign in latex?
Thats the integral sign with a circle through the center.

Thanks

$ \oint$ See [url=http://www.artofproblemsolving.com/Wiki/index.php/LaTeX:Symbols#Multi-Size_Symbols]LaTeX:Symbols[/url]


A square 2005x2005 grid of points contains 2005 red dots, exactly one in each row and each column. Show that any 1003x1003 grid contained within this one must contain at least one red point.

Is there a generalized approach to this type of problem?

[hide]I think it's something like this:

Assume for the sake of contradiction that there is a 1003 x 1003 grid does not contain any red dots. Remove all points in the smaller grid from the larger grid. Every point remaining is in either one of the 1002 full rows or one of the 1002 full columns (or both). Since each row/column can only contain one dot, the maximum number of dots we can have outside of the grid is 1002 x 2 = 2004, a contradiction. Thus our original assumption was wrong, and every 1003 x 1003 grid contained within the 2005 x 2005 grid must contain at least one red dot.

From this you can easily derive the general formula (whose proof is almost exactly the same): If the larger grid is a (2k - 1) x (2k - 1) grid, then any smaller grid with side length k will contain at least one red dot.[/hide]

[quote="b-flat"]The only way to have a dot in every row and every column ($N$ dots), in an $NxN$ grid, is to have them all on either of the diagonals.  Therefore, it will have each one at each point $(1,1);(2,2);...;(N,N)$.  Place the grid that has more than $\frac{N}{2}$ points in the very corner, so you are trying to squeeze it into either triangle.  The corner opposite the that corner will be at the point $(N-x,x)$, which if $x>\frac{N}{2}$, will be at least $(x,x)$, which we already know contains a dot.  If you try to move it up, or to the side, it will contain another dot.

This is kind of hard to understand, but it helps to draw a figure and place it in the coordinate plane, where you can see it much easier.[/quote]

Actually, it's not necessary for the points to all be on either of the diagonals. For example, we could have (1,3), (2,2), (3,1), (4,4), (5,5),... (N,N). The only necessary condition is that each number 1 through N appears exactly once in the x values and exactly once in the y values.
Also, proving the case where the smaller grid is in the corner is not enough; you have to prove it for every possible case.

Your proof is better than mine, because, mine is not complete, but you can use the same idea, and it will work (it's just not very elegant).

Yes, the first thing I thought of would of proved it for all cases where the points are on the diagonal, but not the other cases where the points are not. nebula's way is the best.

[quote="Franz Joseph"]Just wondering, what if it was a nxn grid where n is an even number?[/quote]

It wouldn't work if the second number were $\frac{n}{2}$ (consider $n=2$) and it would obviously work if the second number were $\frac{n}{2} + 1$ (weaker than this case.)


If $3  \text{smiles}=10  \text{grins}$ and $6  \text{grins}=9  \text{laughs}$, how many $\text{laughs}$ does it take to equal $2  \text{smilies}$?

3 smiles= 15 laughs.  2 smiles = 10 laughs.

[quote="math92"]what's the black square thing[/quote]
try typing in
[code]\displaystyle \blacksquare[/code] in dollars's
for
$\displaystyle \blacksquare$

[quote="math92"]what's the black square thing[/quote]In some mathematic texts it means q.e.d. or "end of proof". Usually a white square like this one $\square$ is used.


Hello,

Does any one here read
[quote]Complex Number from A to Z
By: Titu Andreescu and Dorin Andrica[/quote]
Because I need some advices in navigating the book

Thanking you for a reply

hello, I have not read the book myself, but amazon has some wonderful reviews for this particular book.
http://www.amazon.com/Complex-Numbers-Z-Titu-Andreescu/dp/0817643265/ref=sr_1_1?ie=UTF8&s=books&qid=1264124585&sr=8-1

Thanks a lot

I needed one who read it because I already have it but I'm not sure if I can skip some chapters but I will skip some of them and I will see to myself if I can continue or not.

Thanks again


Hello everyone.

I got a matlab assignment regarding projectile motion. Im just wondering how they obtained the value $ 4077.471967$ for the max. travel range of projectile.

[hide="This is the qn"][img]http://i29.tinypic.com/2wn1zso.jpg[/img][/hide]
[hide="How did they get max. travel range?"][img]http://i28.tinypic.com/1t0vpc.jpg[/img][/hide]

I don't know how to do the MATLAB part but I can show you how to solve it by hand.  However, the maximum range will be in terms of $ \theta$ and $ v_{0}$ so since I don't have any actual values, I won't get that exact number you want:

Find the time that it takes to reach it's maximum vertical height ($ v_{0}\sin{\theta}\equal{}0$).  Call it $ t_{1}$.  Then find the time to reach the bottom ($ y\equal{}0$).  Call this $ t_{2}$ and  find the horizontal distance it travels and add it with your previous result to get an answer.

A simpler way would be to differentiate but I can't use calculus in this forum.

[quote="bos1234"]I got a matlab assignment regarding projectile motion. Im just wondering how they obtained the value $ 4077.471967$  for the max. travel range of projectile.[/quote]

As JRav pointed out already, the solution requires the calculus, and that is disallowed in the Introductory Physics forum. Provided you're familiar with calculus, there are a couple of hints I can give you about how the value $ 4077.471967$ was obtained.

First using differential calculus, one can show that the max horizontal range, $ R$ is obtained for an elevation angle, $ \theta$, of $ \theta \equal{} \frac{\pi}{4}$.

Second using integral calculus the path distance $ s \equal{}\int_{0}^{X_T} \sqrt{1 \plus{} \left(\frac{\mathrm{d}y}{\mathrm{d}x}\right)^2}\, \mathrm{d}x$.

The value obtained by your professor's $ \text{MATLAB}^{TM}$ program, $ 4077.471967$ was evidently the solution of $ s_{max} \equal{}\int_{0}^{R} \sqrt{1 \plus{} \left(\frac{\mathrm{d}y}{\mathrm{d}x}\right)^2}\, \mathrm{d}x$ by numerical integration.

While calculus does make this problem a lot easier, it is till possible to solve it using elementary methods, it just takes a lot longer.


im having this conversation with someone on IM
i asked him what the pigeon hole pricipal was. he said

alawetemperal: if there are n holes
alawetemperal: and n*k pigeons,
alawetemperal: at least one hoole contains at least k+1 pigeons

can someone please elaborate that. just knowing that wont help me much as ive learned. it kinda defeats the concept of "problem solving"

what the person you were talking to said. instead, if there are n holes and nk+1 pigeons, one hole would have k+1 pigeons. it makes sense does it not?
there have been a lot of posts on this. search it. :)

You were talking with Peter?
Anyway, IF there are n holes, with nk+[b]1[/b] pidgeons, there must be k+1 pideons in one hole.
Note that if there were nk pidgeons and n holes, each could have k pidgeons.

The reason, which is really common sense, is-assume each of the n hole contains k pidgeons. Then the maximum of pidgeons can be nk, but there are nk+1 of them. Thus, one must have k+1 pidgeons.

EDIT-Here's a good one-[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=1819448730&t=98597[/url]

ehh...i don't agree...pigeonhole can be used for intermediate/olympiad level problems...it's not all that basic. the concept is simple, but I myself still don't understand how to "actually" use it.

[quote="abacadaea"]can someone please elaborate that. just knowing that wont help me much as ive learned. it kinda defeats the concept of "problem solving"[/quote]

problem solving is applying various things that you know in creative ways to solve problems, is it not? I think general consensus is to practice by doing problems and you will get better from there.

[quote="Temperal"]Sorry about that. It was a typo.  :oops: I meant more than $ nk$.

Anyways... [[Pigeonhole Principle]] for more info and problems.

This should actually be in Basics or even Classroom math; pigeonhole is actually pretty basic.[/quote]
hm it didnt turn up on wiki wheni searched it.

[quote="mihail911"]ehh...i don't agree...pigeonhole can be used for intermediate/olympiad level problems...[/quote]
addition can also be used for intermediate/olympiad level problems

The subtlety of pigeonhole is that pigeons and holes can be almost anything.  As such, it can be used in a wide variety of counting problems, and in very complex ways.


calculus integration trigonometry function algebra domain limit

Is it allowed to replace $x$ by $sint$:
$\int\limits_0^2 {x^3 \sqrt{1 - x^2 } dx}$

There is a serious problem with your integral: it takes non-real values for part of its interval.  The integral will only be defined if its bounds are in the set $[-1, 1]$, in which case a trig substitution is perfectly reasonable.  It can also be done by parts, I believe.

[hide="is this allowed?"]
$\displaystyle\int x^3\sqrt{1-x^2}dx=\int (\sqrt{1-x^2})(x^2)(xdx)$
sub in $u=\sqrt{1-x^2}$
$du=\frac{-x}{\sqrt{1-x^2}}dx$
$du=\frac{-x}{u}dx$
so
$-udu=xdx$
and
$x^2=-u^2+1$

so we now have
$\displaystyle\int x^3\sqrt{1-x^2}dx=\int (u^4-u^2)du$
then its easy to solve.
[/hide]
is that one way to do it or did i make a mistake?

[quote="Nea"]Ok this is quite correct, but the dilema is still can we replace it by sint? Or like JBL said it would only be possible if the bounds were in the set [-1,1]?[/quote]

JBL said that there is a problem because the function ${x^3 \sqrt{1 - x^2 }}$ is defined  for $x \in [-1,1]$ and integral is $\int_{0}^{2}$ .

[quote="maokid7"]
is that one way to do it or did i make a mistake?[/quote][hide="Only for Maokid7."][color=darkred]It is allowed what you wrote only if you find a primitive on the interval $I\subset (-1,1)$. If $\{-1,1\}\cap I\ne\emptyset$ then what you wrote isn't correctly.[/hide][/color]

[quote="Virgil Nicula"][color=darkred]It is allowed what you wrote only if you find a primitive on the interval $I\subset (-1,1)$. If $\{-1,1\}\cap I\ne\emptyset$ then what you wrote isn't correctly.[/color][/quote]

what do u mean by a  "primitive"

and when i did the problem i assumed that the boundes were in the domain $[-1,1]$

"Primitive" = "antiderivative." Also sometimes called "indefinite integral" although I don't particularly like that as it causes confusion with $\int_a^xf(t)\,dt.$ The usual notation for primitive (antiderivative) is $\int f(x)\,dx.$

maokid7, what Virgil Nicula was trying to tell you was this: your formal manipulation to produce an antiderivative was correct, as long as you remain within the domain of the functions in question. If we assume that we're talking about real-valued functions, then the maximum possible domain of $\sqrt{1-x^2}$ is $[-1,1].$ That's where that that restriction come in - it doesn't matter whether you explicitly mentioned the restriction $|x|\le1,$ it's there whether you said anything or not.

$\int_0^1x^3\sqrt{1-x^2}\,dx$ can be explicitly computed by maokid7's method, or by the substitution $x=\sin t$ (that would work, too), or probably by some other method as well.

$\int_0^2x^3\sqrt{1-x^2}\,dx$ is undefined, since the integrand is undefined on a portion of the domain with finite measure.

The definite integral $\int_0^2 x^3\sqrt{1-x^2}\ dx$ hasn't real sense because
$[0,2]\not \subset [-1,1]$ which is the definition maximum domain of the function
$f(x)=x^3\sqrt{1-x^2}$, i.e. $f: [-1,1]\mapsto R\ .$

But we will calculate for any $x\in [0,1]$ the definite integral $\boxed {F(x)=\int_0^x t^3\sqrt{1-t^2}\ dt}\ .$
Denote $F_1=\int t^3\sqrt{1-t^2}\ dt=\frac 12\int t^2\sqrt{1-t^2}\cdot (t^2)'\ dt$ on the interval $[0,1)\ .$
Thus, $\boxed {F_1(t)=\frac 12\cdot G(t^2)}$, where $\boxed {G(u)\in \int u\sqrt{1-u}\ du +C}$ and $\boxed {u\equiv u(t)=t^2\in [0,1)}$ for $t\in [0,1)\ .$ By the substitution $\boxed {r\equiv r(u)=\sqrt{1-u}\in (0,1]}\ (u=1-r^2)$ we obtain $r'(u)=-\frac{1}{2\sqrt{1-u}}=-\frac{1}{2r}$ and $G(u)=H\left(\sqrt{1-u}\right)$, where $H=-2\int r^2(1-r^2)\ dr$, i.e. $\boxed {H=-\frac 23 r^3+\frac 25 r^5+C}\ .$ Therefore, $\boxed {G=-\frac 23(1-u)\sqrt{1-u}+\frac 25(1-u)^2\sqrt{1-u}+C}$ and $\boxed {F_1=-\frac 13 (1-t^2)\sqrt{1-t^2}+\frac 15(1-t^2)^2\sqrt{1-t^2}+C}\ .$
We came to the conclusion that for any $x\in [0,1)$ we have $F(x)=F_1(x)-F_1(0)=-\frac 13(1-x^2)\sqrt{1-x^2}+\frac 15(1-x^2)^2\sqrt{1-x^2}+\frac{2}{15}$ and $F(1)=\int_0^1 x^3\sqrt{1-x^2}\ dx=\lim_{x\nearrow 1}F(x)=\frac{2}{15}$, i.e. $\boxed {\boxed {\ \left(\forall\right) x\in [0,1]\ ,\ F(x)=\frac{1}{15}\left[2+\left(x^2-1\right)\left(3x^2+2\right)\sqrt{1-x^2}\right]\ }}\ .$


1. If $\log_83=P$ and $\log_35=Q$, express $\log_{10}5$ in terms of $P$ and $Q$.

2. If $(\log_23)(\log_34)(\log_45)(\log_56)(\log_67)(\log_78)=x$, find x.

3. Given that $\log_{4n}40\sqrt{3}=\log_{3n}45$, find $n^3$.

All of these problems are from AoPS Volume II Chapter 1.

Interesting solution. I did it the following way:

$P=\log_83 \Rightarrow \frac{1}{P}=\log_38=\log_32^3 \Rightarrow \frac{1}{3P}=\log_32$
$\frac{1}{3P}+Q=\log_310 \Rightarrow \frac{3P}{1+3PQ}=\log_{10}3$
$Q=\log_35=\frac{\log_{10}5}{\log_{10}3} \Rightarrow \log_{10}5=Q\cdot \frac{3P}{1+3PQ}=\boxed{\frac{3PQ}{1+3PQ}}$, which is equivalent to your solution.

Also, there's another problem in the original post now.

[quote="JesusFreak197"]
2. If $(\log_23)(\log_34)(\log_45)(\log_56)(\log_67)(\log_78)=x$, find x.
[/quote]
${\log_xy} = {\frac{\log_ay}_{\log_ax}}$

Writing all numbers base [i]e[/i] the expression equals
${\frac{Ln3}{Ln2}} * {\frac{Ln4}{Ln3}} * {\frac{Ln5}{Ln4}} ... {\frac{Ln8}{Ln7}}$
Canceling out equivalent terms from numerator and denominator
it equals
${\frac{Ln8}{Ln2}} = (\log_28)=3$

A more difficult problem has been added. I think it's still appropriate to Intermediate.

2: Apply, change of base formula and you see everything cancels out except $\frac{\log{8}}{\log{2}}$, thus $x=\boxed{3}$. Classic problem :)


Very nice inequality, Harazi. When do you post your solution?

Thank you very much.

In fact, the problem is so "simple" that everyone to whom I gave it didn't know how to solve it.
  We obviously have 1/(1-xy)<=1/(1-(x^2+y^2)/2)<=1/2(1/(1-x^2)+1/(1-y^2)). So we have sum 1/(1-xy)<=sum 1/(1-x^2). One can easily deduce that (1+M)sum 1/(1-x^2)<=sum 1/(1-x), using Cebasev inequality.


linear algebra
matrix
superior algebra
superior algebra solved

Does anyone here know of a nonabelian group where every element has order 3?

Thanks.

This matrix group could work, unless I am mistaken: \[\left\{\begin{pmatrix}1 & x & z \\ 0 & 1& y \\ 0 & 0 & 1\end{pmatrix}\colon x,y,z\in\mathbb Z/3\mathbb Z \right\}\]

@mlok: You're right.

Of course, bobbydylan meant order 3 or 1 ;).


I keep trying to edit my blog settings and my colors and css code never changes.
I have tried Google Chrome and IE8 and neither works.
My colors and css are typed in every time I try to change it but clicking submit never applies any changes.

[url=http://www.artofproblemsolving.com/Forum/weblog.php?w=1758]Here is my blog.[/url]
For me I see default blog settings.
EDIT: Got css to work, but I can't edit blog title colors and block background colors.

Hi,

I'm not very familiar with the blog system. I personally use CSS to modify the colors of the individual blog titles and blocks with CSS.

[code].entrytitle {color: #ff0000;}
.entrywrap {background-color: #0000ff;}[/code]

View the source for various class names of the elements. Search for "css tutorials" on Google to learn more about CSS options.


On a dark and stormy night Snoopy suddenly saw a flash of lightning.
Ten seconds later he heard the sound of thunder.  The speed of sound
is $ 1088$ feet per second and one mile is $ 5280$ feet.  Estimate, to the
nearest half-mile, how far Snoopy was from the flash of lightning.

$ 1088 \times 10 \equal{} 10880$ feet away from the lightning. We want it in miles, so:

$ 10880 \div 5280 \approx \boxed{2}$


Given positive real numbers a, b, and c such that a + b + c = 1, show that (a^a)(b^b)(c^c) + (a^b)(b^c)(c^a) + (a^c)(b^a)(c^b) <=1

please solve this problem as soon as possible

Do not double post:
[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?t=247678[/url]


A number with two identical digits is multiplied by 99. What is the four-digit product if the third digit is 5 ?

[size=75][i]from book "The Moscow puzzles" by Boris A. Kordemsky

Please hide Your solution . Write inside Hide ... /Hide[/i]
[/size]

 :P

Guessing and checking gives $ 99\cdot44\equal{}\boxed{4356}$.

Not sure how to do this without guess and check.

[quote="$ LaTeX$"]Guessing and checking gives $ 99\cdot44 \equal{} \boxed{4356}$.

Not sure how to do this without guess and check.[/quote]
I don't like "Guessing and checking"
 :huh:

[quote="$ LaTeX$"]Okay, I found out a non bashy way.

When any number with two identical digits is multiplied by 99, the 1st and 3rd numbers, and the 2nd and 4th numbers, sum to 9. Also, the first digit is one more than the first. From this, we get our number $ \boxed{4356}$.[/quote]
Why  the first digit is one more than the first ?


What do you think of the mathematics in this article:

[quote]NORWICH, England (Reuters) -- Many people have experienced the phenomenon of receiving a telephone call from someone shortly after thinking about them -- now a scientist says he has proof of what he calls telephone telepathy.

Rupert Sheldrake, whose research is funded by the respected Trinity College, Cambridge, said on Tuesday he had conducted experiments that proved that such precognition existed for telephone calls and even e-mails.

Each person in the trials was asked to give researchers names and phone numbers of four relatives or friends. These were then called at random and told to ring the subject who had to identify the caller before answering the phone.

"The hit rate was 45 percent, well above the 25 percent you would have expected," he told the annual meeting of the British Association for the Advancement of Science.

"The odds against this being a chance effect are 1,000 billion to one."

He said he found the same result with people being asked to name one of four people sending them an e-mail before it had landed.

However, his sample was small on both trials -- just 63 people for the controlled telephone experiment and 50 for the email -- and only four subjects were actually filmed in the phone study and five in the email, prompting some skepticism.

Undeterred, Sheldrake -- who believes in the interconnectedness of all minds within a social grouping -- said that he was extending his experiments to see if the phenomenon also worked for mobile phone text messages.[/quote]

I haven't the time to do the binomial distribution and all that but the stated probability seems very, very wrong.

It's all part of the "mind over matter" theory

[quote]but the stated probability seems very, very wrong[/quote]

Surely it all depends on the number of repeats? If each of the 63 participants were tested once, and 28 of them got it right, then one in a billion would be way wrong. However, if each person was tested 20 times, then the chances of an overall 45% hit rate will be minute, and I'd happily go along with one in a billion.


calculus
integration
arithmetic sequence

Given a harmonic sequence $a_{n}$ (for integral $n$) in which  $a_{1}\cdot a_{2}= a_{3}$, find $a_{1}$ such that $\frac{a_{8}}{a_{7}}= \frac{a_{1}}{a_{2}}$ and $a_{4}\neq a_{5}$.

More generally, find $a_{1}$ in terms of $k$ such that $\frac{a_{k+1}}{a_{k}}= \frac{a_{1}}{a_{2}}$ and $a_{4}\neq a_{5}$.

[hide="Hint"]By the definition of harmonic sequence, the reciprocals of its terms make an arithmetic sequence, hence ${1\over a_{n}}={1\over a_{1}}+(n-1)\left({1\over a_{2}}-{1\over a_{1}}\right)$, so derive the formula for the general term and solve the equations.[/hide]


A graph has $ n$ vertices and $ \frac {1}{2}\left(n^2 \minus{} 3n \plus{} 4\right)$ edges. There is an edge such that, after removing it, the graph becomes unconnected. Find the greatest possible length $ k$ of a circuit in such a graph.

[b]Solution:[/b]
We may assume that our graph $ G$ is connected.
Therefore,
\[ n^2 \minus{} 3n \plus{} 4 > 2n \minus{} 2
\]
It means that if $ G$ has a cycle then $ n\geq 4$.
Suppose that after removing of some edge from $ G$,we obtained a new not connected graph $ G'$ with connected components $ G_1,G_2,\dots,G_m$,where $ m\geq 2$.It is easy to understand that $ m$ can not be greater than $ 2$,because after deleting the edge,that connected vertices $ A,B$,we obtained a new graph,whose vertices are divided into two groups,one of them are connected with $ A$ and the others are connected with $ B$.Also suppose that $ |G_i| \equal{} n_i$ and $ n_i\geq 1$,where $ i \equal{} 1,2$.
Therefore there are exactly $ \frac {n(n \minus{} 3)}{2} \plus{} 1$ edges and $ n \equal{} n_1 \plus{} n_2$ vertices in $ G'$.
Therefore there are less than $ \frac {n_1(n_1 \minus{} 1) \plus{} n_2(n_2 \minus{} 1)}{2}$ edges in $ G'$,hence
$ n^2 \minus{} 3n \plus{} 2 \equal{} n_1^2 \plus{} n_2^2 \plus{} 2n_1n_2 \plus{} 2 \minus{} 3n_1 \minus{} 3n_2\leq n_1^2 \plus{} n_2^2 \minus{} n_1 \minus{} n_2$,so
$ n_1n_2 \plus{} 1\leq n_1 \plus{} n_2$,or
$ (n_1 \minus{} 1)(n_2 \minus{} 1)\leq 0$
So we may assume that $ n_2 \equal{} 1$,hence there was a vertex in $ G$ with degree exactly $ 1$,and therefore $ k\leq n \minus{} 1$.
Example is obvious.
$ \blacksquare$.

If there is a lenght $ n$ circuit, this graph can't be unconnected with removing just one edge. Because, there are at least two disjoint paths between any 2 vertices. Moreover, take a $ K_{n\minus{}1}$ and another vertice. Join this vertice to an arbitrary vertice ok $ K_{n\minus{}1}$. This satisfies the conditions.

[quote="Umut Varolgunes"]If there is a lenght $ n$ circuit, this graph can't be unconnected with removing just one edge. Because, there are at least two disjoint paths between any 2 vertices. Moreover, take a $ K_{n \minus{} 1}$ and another vertice. Join this vertice to an arbitrary vertice ok $ K_{n \minus{} 1}$. This satisfies the conditions.[/quote]
Nice,but you forgot to said that $ n\geq 4$,because otherwise there is no cycle.
P.S:
Congratulations with gold medal.
Will you participate to IMO next year?
Best regards.


inequalities
logarithms
irrational number
number theory unsolved
number theory

Ok i know it may be annoying but i need a detailed solution.I'm just a freshmen,i've just heard about the irrational number [b]e[/b],but i dont know anything about it.I also don't understand your first assertion.Any help,please? :)

Arne! The aim of this problem to show without any machine computations that lg(2)=0.301...

I know, but I know the values of $\log_{10}2$ and $\log_{10}3$ by heart :)

[quote="Arne"]Well, $\log_{10}2 = 0.30103...$ which gives $10^{301} < 2^{1000} < 10^{302}$.
So our number has 302 digits.[/quote]

Actually $\log_{10} 2 = 0.301029995 \ldots$ (it's about the same, I just don't like rounding off the digit before the $\ldots$ :) )

On this note, the question "How many digits are there in $2^{100}$" came out as one of the questions in the first round of the Singapore MO this year (the first round consists of multiple choice questions; the second round is a 4.5 hour long paper similar to IMO); the standard way would be to notice that $2^{10} = 1024$ and thus guess (*gasp!*) that the answer is $1 + 3 \times 10 = 31$; however quite a few of us had memorised $\log_{10} 2$ by heart and therefore didn't need to worry quite so much :lol: .


$ \mathfrak{Who's}\text{ }\mathfrak{top}\text{ }\mathfrak{poster}\text{ }\mathfrak{in}\text{ }\mathfrak{AOPS?}$ :huh:  :huh:  :huh:

It's t0rajir0u. Just see the Memberlist and you'll see he has the most posts.

Still t0rajir0u, as I doubt AIME15 has 2k+ FF and TF posts.

@dragon96: I have 8302 total posts, including FF/TF.

t0rajir0u  t0rajir0u
has a lot of... posts :O

[quote="maybach"]How does someone have over 11,000 posts? Is AOPS their entire life?[/quote]

If t0jair0u joined in 2003, and posted 4-6 posts a day, then t0jair0u would have about that much posts.


calculus
integration
trigonometry
limit
real analysis
real analysis solved

Let $I_n=\int^{\frac{\pi}{2}}_0 \sin ^n\theta d\theta\ (n=0 ,1,2,\cdots)$
Evaluate  \[\lim_{n\to\infty} nI_n^2\]

There's a fine and useful recursion that calculates $I_n$ in terms of $I_{n-2}.$ This leads to exact formulas for $I_n$ that can be used to answer this question. I'll let someone else post that; I want to get right to the answer. My methods will be a little informal, but could be formalized if necessary.

The first thing I'll do is flip the interval around and write $I_n=\int_0^{\frac{\pi}2}\cos^n\theta d\theta.$

For $\theta$ not near zero, $\cos^n\theta$ tends to zero rapidly as $n\to\infty$ and will be disregarded. For $\theta$ near zero, $\cos^n\theta\approx\left(1-\frac{\theta^2}2\right)^n\approx e^{-\frac{n\theta^2}2}.$

Hence, $I_n\approx\int_0^{\frac{\pi}2}e^{-\frac{n\theta^2}2}d\theta\approx \int_0^{\infty}e^{-\frac{n\theta^2}2}d\theta.$

Under the change of variables $x=\sqrt{n}\theta$, this becomes

$I_n\approx\frac1{\sqrt{n}}\int_0^{\infty}e^{-\frac{x^2}2}dx= \frac{\sqrt{2\pi}}{2\sqrt{n}}.$

Hence, $nI_n^2\approx n\left(\frac{\sqrt{2\pi}}{2\sqrt{n}}\right)^2=\frac{\pi}2.$

So the answer is $\frac{\pi}2.$

Oh!you solve always in very easily! Of course, you are right,thank you!

kunny

Now that Moubinool has moved this over to the "solved" column, I'll mention the details of the recursion, which are in most of the calculus textbooks I know. Integrate by parts once, use the Pythagorean trig identity, and solve for the unknown integral which appears on both sides of the equation, to obtain

\[I_n=\frac{n-1}nI_{n-2}\]
Since $I_0=\frac{\pi}2$ and $I_1=1$, this leads to
$I_{2k}= \frac{(2k-1)(2k-3)\cdots3\cdot1}{(2k)(2k-2)\cdots4\cdot2}\cdot\frac{\pi}2$
$I_{2k+1}=\frac{(2k)(2k-2)\cdots4\cdot2}{(2k+1)(2k-1)\cdots3\cdot1}$

From this it is evident that $I_{2k+1}I_{2k}=\frac{(2k)!}{(2k+1)!}\cdot\frac{\pi}2$ and thus $(2k+1)I_{2k+1}I_{2k}=\frac{\pi}2.$ If now we can show that $\lim_{k\to\infty}\frac{I_{2k+1}}{I_{2k}}=1$ then we have our answer by a different means.


geometry
perimeter
circumcircle
inequalities proposed
inequalities

Prove that:
     $p^2 \le 4R^2-\frac{11}{\sqrt[3]{3}}S$
while $p$ is semi-perimeter
          $S$ is area of triangle
          $R$ is radius of circumcirle

This inq isn´t true. Take an equilateral triangle.


Let [tex]A=(a_{ij})_{n\times n}[/tex] be an [tex]n\times n[/tex] matrix such that [tex]a_{ij}=\pm2[/tex] when [tex]i<j[/tex] and [tex]a_{ij}=\pm1[/tex] when [tex]i\ge j[/tex]. Show that  the matrix [tex]A[/tex] is invertible.

[hide]Claim: each matrix of that form has an odd determinant.  We will prove it by induction.  In the case n = 1, it is trivial.  Assume it's true for n = k.  Consider n = k + 1.  Using the standard expansion of the determinant along the top row, we see that the first term will be +-1 times the determinant of the matrix for n = k.  Each additional term is +-1 times the determinant of a matrix with first column composed entirely of 2's, and all other entries integral.  All such terms will be even.  The sum of one odd number and a bunch of even numbers is odd.  Thus, we see that all such matrices will have odd determinants.  Thus, no such matrix will have a 0 determinant, so they are all invertible.[/hide]

Nice question.  Your own invention?

That is a nice question. And a nice solution JBL!

Nice job, JBL. The idea of creating the problem is using mod 2 arithmetic.

JBL provided a very nice proof above. I am posting a slight different proof here.

[hide]

As we know the mapping [tex]\phi: {\mathbb Z} \rightarrow {\mathbb Z}_2, \phi(a) = (a\mod 2)[/tex] preserves addition and multiplcation. Then [tex]\phi(\det(A))=\phi(\det(a_{ij}))=\det(\phi(a_{ij})) = 1\in{\mathbb Z}_2[/tex], since [tex]\phi(a_{ij})=0\in{\mathbb Z}_2[/tex] when [tex]i<j[/tex] and [tex]\phi(a_{ij})=1\in{\mathbb Z}_2[/tex] when [tex]i\ge j[/tex]. So [tex]\det(A)[/tex] is not zero (in fact, it's odd).

[/hide]


Let $ a;b;c\geq 0$ satisfying $ \sum a\equal{}3.$Prove that:
      $ \sum\frac{a}{ab\plus{}3c}\geq\frac{3}{4}$

[quote="karis"]Let $ a;b;c\geq 0$ satisfying $ \sum a \equal{} 3.$Prove that:
      $ \sum\frac {a}{ab \plus{} 3c}\geq\frac {3}{4}$[/quote]
The inequality is equivalent to
\[ \sum \frac{a}{(a\plus{}c)(b\plus{}c)} \ge \frac{3}{4}\]
\[ \Leftrightarrow a^2\plus{}b^2\plus{}c^2\plus{}ab\plus{}bc\plus{}ca \ge \frac{3}{4} (a\plus{}b)(b\plus{}c)(c\plus{}a)\]
\[ \Leftrightarrow (a\plus{}b\plus{}c)(a^2\plus{}b^2\plus{}c^2\plus{}ab\plus{}bc\plus{}ca) \ge \frac{9}{4} (a\plus{}b)(b\plus{}c)(c\plus{}a)\]
\[ \Leftrightarrow [(a\plus{}b)\plus{}(b\plus{}c)\plus{}(c\plus{}a)][(a\plus{}b)^2\plus{}(b\plus{}c)^2\plus{}(c\plus{}a)^2] \ge 9(a\plus{}b)(b\plus{}c)(c\plus{}a)\]
which is obviously true by AM-GM. :)


[quote="Elio (n)"]Prove that if $ p_{1},p_{2}$ are 2 prime numbers such $ p_{1} \neq p_{2}$ than :$ (\frac {p_{1}}{p_{2}} \plus{} \frac {p_{2}}{p_{1}})$ can not be natural[/quote]

[hide="Solution"]$ \frac{p_{1}}{p_{2}}\plus{}\frac{p_{2}}{p_{1}}\equal{}\frac{p_{1}^{2}\plus{}p_{2}^{2}}{p_{1}p_{2}}$

Suppose this is natural, then $ p_{1}$ divides $ p_{1}^{2}\plus{}p_{2}^{2}$, so $ p_{1}$ divides $ p_{2}^{2}$.  Therefore, $ p_{1}$ divides $ p_{2}$, a contradiction.[/hide]

Your induction is strong matt276eagles .

[quote="mathwizarddude"]This is a little unrelated, but in your signature, what does the quote
"'Your induction is weak, old man!'" mean?[/quote]

The actual quote is "Your powers are weak, old man!" from Star Wars - Darth Vader says it to Obi-Wan when they fight.  The quote from my sig was a joke from Blue MOP in 2007.

If you're asking what it means mathematically, there are certain problems where if you want to use induction, you need to use induction on a stronger statement than the original problem statement, or you might need to use what is known as "strong induction."  If you tried to use induction on the original statement in this case, you might say your induction is weak.

Elio (n):  :P


Find all positive integers $ x,y$,such that
$ 7^x\plus{}x^4\plus{}47\equal{}y^2$

[hide="Hint"]-) $ x$ odd then $ LHS\equiv 3(mod 4)$ then don't exist $ y$ satisfy!
-) $ x\equal{}2k$: if $ k\geq 4$ then $ 7^{2k}<LHS<(7^k\plus{}1)^2$[/hide]

That's right,but instead of posting a hints,you should have posted the proof.
Thank you.

I hope this can be helpful.

No solution for x=0,1,2.
 Consider

 Case 1.  Let $ x \equal{} 2k\plus{}1$ (k:natural number), so
\[ 7^x \plus{}x^4\plus{} 47 \equal{} 7^{2k\plus{}1} \plus{} (2k\plus{}1)^4 \plus{}47 \equal{} y^2\]
If $ y^2\equal{} 0$ (mod 4),
\[ 7^{2k\plus{}1}\plus{} (2k\plus{}1)^4\plus{} 47\equal{} 3(\minus{}1)^{2k}\plus{} (2k\plus{}1)^4 \minus{}1\equal{} 0 (\mod4)\]
But, $ (2k\plus{}1)^4 \equal{} 2 (\mod 4)$
So it is impossible

If $ y^2\equal{} 1 (mod4)$,
 then $ (2k\plus{}1)^4\equal{} 3 (mod4)$
impossible

Case 2. Let $ x\equal{} 2k$
then
\[ 7^x\plus{}x^4\plus{}47\equal{}7^{2k} \plus{} (2k)^4\plus{}47\]
if $ y^2\equal{} 0 (mod 4)$ then
\[ (\plus{}1)^k \plus{}(2k)^{\minus{}1}\equal{} 0(mod4)\]
and so $ (2k)^4\equal{} 0 (mod 4)$ which is possible
if $ y^2 \equal{} 1  (mod4)$
then
$ (2k)^4 \equal{} 1 (mod4)$   impossible.

For  $ k\equal{} 1$ ,we have 112 which is not perfect square,
 but for $ k\equal{}2$, we have $ 7^x\plus{}x^4\plus{}47\equal{}2704$ which is perfect square;
So, the possible solution is
\[ (x,y)\equal{} (4, 52).\]


[b]Show that if $ n$ is either perfect or abundant, then every positive multiple of $ n$ that is greater than $ n$ is abundant.[/b]

See [url=http://www.artofproblemsolving.com/Forum/weblog_entry.php?t=132982]an old blog post of mine[/url].


Support
function
integration
calculus
derivative
advanced fields
advanced fields unsolved

Suppose that $f \in C^{\infty}(\mathbb{R}, \mathbb{R})$ is a function with compact support. Find the support of its Fourier Transform.

The Fourier transform of any compactly supported integrable function is entire.
$\frac{d}{ds}\int_A^B e^{ist}f(t)\,dt=\int_A^B ise^{ist}f(t)\,dt$; that's a derivative in the complex numbers. Since $\left|\int_A^B ise^{ist}f(t)\,dt\right|\le \int_A^B \left|ise^{ist}f(t)\right|\,dt\le \int_A^B \max\{|A|,|B|\}\left|f(t)\right|\,dt$, the integral exists for all $s$ and the Fourier transform is differentiable everywhere.

By the identity principle, the zero set of the transform is discrete unless $f$ and its transform are identically zero; for nonzero $f$, the support is $\mathbb{R}$.


Which of the following statements is false?

$ \textbf{(A)}\ \text{All equilateral triangles are congruent to each other.}$
$ \textbf{(B)}\ \text{All equilateral triangles are convex.}$
$ \textbf{(C)}\ \text{All equilateral triangles are equilangular.}$
$ \textbf{(D)}\ \text{All equilateral triangles are regular polygons.}$
$ \textbf{(E)}\ \text{All equilateral triangles are similar to each other.}$

[hide]A. The lengths of the sides can be different in different triangles.[/hide]

A is false ( i did that fast so it better be right)

Ha. Problem two, no wonder. A, of course. I'm surprised they made it that easy though. Just factual knowledge on the definitions of the words.

Reeeeeeeally.

Meh?!

Yes... I agree it is A. This looks like a Mathcounts or lower level problem...


How long does it take to type up $\LaTeX$ solutions for you guys??? I spend A LOT of time (like 5 hour for each problem...). I was wondering if I can be less formal and picky about the  grammar.

5 hours per problem? i spend about 45 minutes on each... but it really depends on how rigorous my proof is. Maybe yours are just waaay longer than mine  ;)

I usually take about 30 minutes per solution, though sometimes if I'm not sure how to state something clearly, it can take longer.  How long are your solutions, usually?  Length generally contributes significantly to time required to write them (well, duh  :roll: )

About 45 minutes each for me. unless I have to insert a lot of images, which hasn't come up yet.

I highly doubt you spend 25 hours typing up USAMTS solutions...

Once I have the solution method down it isn't too hard to type them up (probably about 30 minutes on average).  I think this year the fastest I've typed up a solution is about 5 minutes and yet the longest was 2 to 3 hours.  The one that took me the longest was also my longest solution lengthwise and I used many facts and equations.  There were a ton of different ways I could have structured my solution and I had to wade through the options while I was writing up the solution.

[quote="pkerichang"]well...Once I finished typing the solution (like 20 min per problem), I spend A LOT of time revising it over and over again....Something like grammar, layout, but most importantly is the wording, I try to make it as clear as possible...Then it ends up taking hours.  For round 1, I have LONG solutions, but this round I have 2-3 pages per problem (except for number 5, but that's because I have one full page of images)[/quote]
Well, if most of your time is revising, probably at some point you just have to stop and say "okay, it'll never be ideal, but it's good enough."  It's always good to have nice solutions, but you're not publishing a book, so as long as your solutions make sense to someone familiar with the problem, you probably shouldn't have to revise your solutions too much.

I spend about 30 minutes each or less [i]writing[/i] them up. :P

It takes me a while to type them up too, pkerichang.  I don't really completely plan out my solution before I type it, so lots of times I see a better way to explain something and I have to edit my solutions.  Sometimes, something seems really obvious to me but it takes me a while to figure out how to explain it.  I usually spend 1-2 hours per problem.

If they have a lot of images, tables, or anything that requires a lot of work outside of typing and basic TeXing, it can take me quite a long time.  I know I've spent over three hours on typing up a single problem before. :-\

[quote="solafidefarms"]I generally start writing and get inspired while writing up my solutions. Worked on 2.5! Takes about 2 hours.[/quote]

THat's what I do too. Worked on 1 and 4! :lol:

I just writeup all of my solutions in maybe 2 hours.  Once that's done, I walk away.  I come back once a week or so and look at it to make any adjustments.


[quote="fjwxcsl"]Moreover,we also have

                          $ A_n - G_n\geq{k_n(M_n - H_n)(n\ge2)}$

holds  for any  $ {x_1,x_2,...,x_n} > 0$ iff $ k_n\leq{\frac {1}{3}}$.[/quote]

  If  $ M_n - H_n\ge{k(n)(A_n - G_n)},$ then$ k(n)_{max} = ?$  we have $ k(n)_{max} =\sqrt{ \frac {n}{n-1}.}$

Therefore

           $ A_n - G_n\geq{\frac{1}{3}(M_n - H_n)\ge{ \frac {\sqrt{n(n-1)}}{3(n-1)}}(A_n-G_n).}$


Find all sets comprising of 4 natural numbers such that the product of any 3 numbers in the set leaves a remainder of 1 when divided by the remaining number.

It is easy to prove $abcd|abc+abd+acd+cda+1$ So we get $f(a,b,c,d)=1/a+1/b+1/c+1/d+1/abcd$ is at least $1$. So from here we get that $min(a,b,c,d)=1,2,3,4$ and using that $f(a,b,c,d)$ is cecreasing on each variable, we may plug in $a=1,2,3,4$ and find possible values for the remaining numbers. This gives not too much hand work to check solutions.


The apothem of a square having its area numerically equal to its perimeter is compared with the apothem of an equilateral triangle having its area numerically equal to its perimeter. The first apothem will be:
(A) equal to the second
(B) $\frac{4}{3}$ times the second
(C) $\frac{2}{\sqrt{3}}$ times the second
(D) $\frac{\sqrt{2}}{\sqrt{3}}$ times the second
(E) indeterminately related to the second

the apothem is basically the distance from the center of a polygon to its side, otherwise known as the inradius i think

[quote="xenon_nightmare152"][hide]side of square = $4$
side of equilateral triangle = $4\sqrt3$
therefore both apothems are $2$

their apothems are the same?
 :?[/hide][/quote]
No, the perimeters and areas are the same for the square and triangle.

for the square, both the area and perimeter are $16$
 for the triangle, both area and perimeter are $12\sqrt 3$

is the apothem in an equilateral triangle just half its height?

[quote="buzzer11"]I do NOT get this problem... :blush:[/quote]
I am not sure what is it that you do not understand but here are a few things to explain better the problem for you:

Apothem: it is length of the perpendicular segment from the center of the regular polygon to a side of the polygon.

The problem says area is numerically equal to perimeter. If $A$ is area and $P$ is perimeter, $A=P$. If you are still stuck, perhaps the level of this forum is too hard for you???  :?

[EDIT][color=red]ATTENTION EVERYONE WHO ARE STUCK IN THIS PROBLEM[/color]: I'll give you a hint if you are all stuck
[hide="CLICK HERE TO SEEK HELP---HINT"]$a=\text{apothem}$
$P=\text{perimeter}$
$A=\text{area}$

For any regular polygon, $A=\frac12aP$. Now I just gave away the problem...  :blush: [/hide]

[quote="4everwise"]It isn't. just draw a diagram and see.  :)[/quote]

I did in my sleep and it surely wasn't. For an equilateral triangle, the apothem of the triangle is $\frac{s\sqrt3}{6}$, where s is the side.

Wait, that means that xenon_nightmare was correct  :?

[img]http://4aunlimited.co.nr/AoPS/images/apothegm.PNG[/img]

All the stuff is in the image above:

[quote="chess64"][quote="10000th User"][hide="CLICK HERE TO SEEK HELP---HINT"]$a=\text{apothem}$
$P=\text{perimeter}$
$A=\text{area}$

For any regular polygon, $A=\frac12aP$. Now I just gave away the problem...  :blush: [/hide][/quote]

But can you prove it? I know most proofs aren't getting started level, but I learned this one in school so I'm sure it's not too hard! :D[/quote]
:( No, I am not going to prove it here. If you want, you can start a topic asking for proof in Intermediate Topics.

I think a proof of the formula would be more approiate here than the intermediate forum.  It's not too complicated.  But I guess I'll hide it.

[hide]Let's divide the n-gon into triangles, with the apothem = height, and the side = base for each triangle.  Then, the area of each triangle is $\frac{1}{2}\cdot a \cdot s$.  Since there are n of these triangles in an n-gon, you would multiply the area by n to get $\frac{1}{2}\cdot a\cdot s \cdot n$.  Since each side length is equal to s, and there are n sides, $s\cdot n = \text{the perimeter of the polygon}$.  So replacing $n\cdot s$ gives us $\frac{1}{2}aP$[/hide]


vector
function
topology
real analysis
real analysis unsolved

The plane is covered by open sets of diameters $< 1$.Prove that then some $3$ of them have non-empty intersection.

I think if $U$ and $V$ are two open bounded subsets of the plane, and $\partial(O)$ is the boundary of $O$, then if $U \cap V$ is non-empty, then $\partial(U) \cap \partial(V) \cap \partial(U \cap V)$ is non-empty.

But $U\cap V$ need not be one of the covering sets. Also, the boundaries are not included.

It's essential that the diameters are uniformly bounded: the open sets $U_{n}= \{(x,y)\colon n<\sqrt{x^{2}+y^{2}}<n+4/3\}$, $n\ge 0$, together with a small open disk at $(0,0)$, cover the plane with multiplicity at most $2$.

Here's a nice way to prove it with Brouwer's theorem: of course, if $X_{1}X_{2}X_{3}$ is a compact triangle sufficiently large, it will be covered by some finite set $O_{1},...,O_{n}$ of these open sets and moreover, any such open set will cut at most two edges of the triangle. This means that we have a cover of this triangle with three open sets $U_{1},U_{2},U_{3}$ such that $U_{1}$ does not touch $X_{2}X_{3}$ and similarly for the others. This implies a cover of the triangle with three closed sets $F_{1},F_{2},F_{3}$ such that $F_{1}$ does not touch $X_{2}X_{3}$ and so on. Now, let $x_{i}$ the vectors corresponding to $X_{i}$ suppose the $F_{i}$ have no common point and define the function $f(x)=\frac{d(x,F_{1})x_{1}+d(x,F_{2})x_{2}+d(x,F_{3})x_{3}}{d(x,F_{1})+d(x,F_{2})+d(x,F_{3})}$ on the triangle. Clearly, this function has a fixed point $x$ in the triangle (Brouwer's theorem). But this is impossible, because $x$ must be in $F_{1}$ for instance and then either it is in $F_{2}$ too and in this case it must be $x_{3}$, impossible, either it is only in $F_{1}$ and then $x$ must lie on $F_{1}$ and $X_{2}X_{3}$, impossible.


How many two-digit numbers are there in which the tens digit is greater
than the ones digit?

We could just list them using casework by the tens digit.
$ \text{Case 1: Tens digit is 1}:$
$ 10$
$ \text{Case 2: Tens digit is 2}:$
$ 21, 20$
$ \text{Case 3: Tens digit is 3}:$
$ 32, 31, 30$
$ \vdots$
$ \text{Case 8: Tens digit is 8}:$
$ 87, 86, 85, 84, 83, 82, 81, 80$
$ \text{Case 9: Tens digit is 9}:$
$ 98, 97, 96, 95, 94, 93, 92, 91, 90$

There are a total of $ 1 \plus{} 2 \plus{} 3 \plus{} 4 \plus{} 5 \plus{} 6 \plus{} 7 \plus{} 8 \plus{} 9 \equal{} \boxed{45}$ numbers.


I think it's old and I hope the solution.(TST 1993 VN).

Sorry,<A is nothing.I try to repair but becauseLATEX....

Nobody interested in it.I want a solution.


NO CALCULATOR for this one please (because it's not very easy and fun to do).

Let $f_i (x), i = 1,2,3...$ be defined by $f_1 (x) = \frac{1}{1-x}$ and $f_{i+1} (x) = f_i (f_1 (x))$. Then compute $f_{1998} (1998)$.

It can be found by direct computation that $f_3(x) = x$, whereby $f_1998(1998) = 1998$, as $3 | 1998$.


AMC
AIME
geometry
geometric transformation
reflection
conics
hyperbola

(1) I don't remember the constants, but the question went like:
a+b=c1, a :^2: +b :^2: =c2, a :^3: +b :^3: =c3, a :^4: +b :^4: =c4, find a :^5: +b :^5: .

How do I even start this one?

(2) Reflect the hyperbola xy=1 about the line y=2x+1. What is the equation of the graph?

Are you sure you're remembering number 1 correctly?  The reason I ask is because the first two equations (the values for (a + b) and (a2 + b2)) determine a and b, so it seems like the other two equations would be sort of unnecessary.  Here's a fairly basic suggestion for it, though:  [hide]use the first two equations to find out what ab is.  Then, multiply two of your equations together to get something involving (a5 + b5).  You'll be able to use the other equations and the value of ab in order to elliminate all of the other terms nicely.  Alternatively, you could factor (a5 + b5) and use the other equations and the value of ab to find its value by substitution.[/hide]

A good way to figure out the second one is to [hide]reflect a general point on the graph (a, b) through the line and see where it ends up.  Then express a relationship that holds between the x and y coordinates (for example, it might be something like x2 - y2 = 3, or something -- but it has to be independent of the point (a, b) that you started with -- in other words, treat a as a variable, and the equality has to work.  And that describes the new position of the hyperbola.[/hide]

i remember the first one to be more complicated than that. i think it was actually ax+by=c_1,  ax^2+by^2=c_2, ax^3+by^3=c_3, ax^4+by^4=c_4, find ax^5 + by^5. if this wasnt so, it would be too simple to substitute in y=c_1-x into x^2+y^2=c_2 and solve by quadratic formula. My suggestion:

[hide]Use this identity: x^(n+1) + y^(n+1) = (x^n + y^n)(x+y) - (x^(n-1) + y^(n-1))xy.[/hide]

my hint(for #1):

 [hide]Note that (ax^2+by^2)(x+y)=ax^3+by^3+(ax+by)xy

                 (ax^3+by^3)(x+y)=ax^4+by^4+(ax^2+by^2)xy[/hide]

Further hint:

     [hide]let x+y=m, xy=n. We have c_2(m)=c_3+c_1(n)

                                                c_3(m)=c_4+c_2n

Just solve it for m,n.[/hide]

I found problem number 1: The real numbers a, b, x, y satisfy ax + by = 3, ax :^2:  + by :^2:  = 7, ax :^3:  + by :^3:  = 16, ax :^4:  + by :^4:  = 42. Find ax :^5:  + by :^5: .

Another one along the same lines:
w and z are complex numbers such that w :^2:  + z :^2:  = 7, w :^3:  + z :^3:  = 10. What is the largest possible real value of w + z?

Ah, that's right.  Well, the other two people have given good hints for that one.  As for the other one, I would recommend [hide]letting (w + z) = a, wz = b, compute those two expressions in terms of a and b, and then try and maximize (or solve for) a.  Not 100% sure on this, but that seems the most straightforward.  Alternatively, factoring the cubed expression and then using the sum and product (along with the relationship you get between them from the squared equation) might be nicer.[/hide]


Find all functions f : R-->R satisfying the equation
   f(x+y) + f(x)f(y) = (1+y)f(x) + (1+x)f(y) +f(xy)

its easy to show that f(1) = 0 or 2
and if f(1)=0, f(x)=0 for all x

but if f(x)=2, i could show for numbers upto all rationals only that f(x) = x^2 + x

${f(x) f(y)+f(x+y)=(y+1) f(x)+(x+1) f(y)+f(x y)}$

${\{y\to 1,x\to 0\}}$

${f(0) f(1)+f(1)=3 f(0)+f(1)}$
${f(1)=3}$

${\{ x \to 1\text{ }, f[1] \to 3 \}}$

${3 f(y)+f(y+1)=3 (y+1)+3 f(y)}$
${3 y+3=f(y+1)}$
${f(y)=3 y}$

must be others solutions, but, since you didnt rigth it in latex. comit a lot of trivials errors. i dont know if this is a serious post.

so this solution is good enought

it is [url=http://www.mathlinks.ro/viewtopic.php?t=152241]here[/url] :wink:


geometry
trigonometry
circumcircle
geometry proposed

Let $ABC$ be a triangle inscribed in the circle $\mathcal{C}$ and let $M$ be a point on the arc $BC$ which does not contain $A$. The tangents from $M$ to the inscribed circle in the triangle $ABC$ intersect $\mathcal{C}$ in the points $N$ and $P$.

Prove that if $\angle BAC = \angle NMP$, then the triangles $ABC$ and $MNP$ are congruent.

I have no solution yet, but I just wanted to note that the line NP touches the incircle of triangle ABC (Poncelet's porism). Maybe this helps.

  Darij

This topic is related to one of the problems in the Mathlinks contest, if I remember correctly. Poncelet's theorem (a particular case of it, actually) states that $NP$ is also tangent to the incircle of $ABC$, so $ABC$ and $MNP$ become triangles which have $R,\ r,\ \angle BAC=\angle NMP$ in common, and it can be shown that they're congruent.

I don't expect this to be a suitable approach for a junior participant, but it's a useful observation.

[quote="grobber"]This topic is related to one of the problems in the Mathlinks contest, if I remember correctly. Poncelet's theorem (a particular case of it, actually) states that $NP$ is also tangent to the incircle of $ABC$, so $ABC$ and $MNP$ become triangles which have $R,\ r,\ \angle BAC=\angle NMP$ in common, and it can be shown that they're congruent.[/quote]

Yes, actually a triangle is determined uniquely if the values R, r and A are given, since we have

[tex]r=\frac{2R\sin A}{\cot \frac{B}{2}+\cot \frac{C}{2}}[/tex],

so that we can find $\cot \frac{B}{2}+\cot \frac{C}{2}$, and we also have

[tex]\tan \frac{A}{2}=\frac{\cot \frac{B}{2}\cot \frac{C}{2}-1}{\cot \frac{B}{2}+\cot \frac{C}{2}}[/tex],

so we can compute $\cot \frac{B}{2}\cot \frac{C}{2}$.

Now, from $\cot \frac{B}{2}+\cot \frac{C}{2}$ and $\cot \frac{B}{2}\cot \frac{C}{2}$, the values of $\cot \frac{B}{2}$ and $\cot \frac{C}{2}$ are determined up to the shuffling B <--> C.

  Darij

I think there are easier ways of doing that, since we don't actually have to calculate the elements of the triangle: Let $AB,\ AC$ touch the incircle at points $X,\ Y$ respectively. Since $\angle XAY$ is fixed, $\angle XIY=\pi-\angle XAY$ is also fixed, so $AI$ is fixed because a leg of the right triangle $AXI$ is fixed and it's angles are fixed. This means that $A$ is on a circle centered at $I$ which cuts the circumcircle of $ABC$. Unless $I=O$, which is easily solved, the two circles only intersect at two points which are symmetric wrt to $OI$,  so the two triangles are either one and the same (which isn't possible because $M$ is on the arc $BC$ which doesn't contain $A$) or symmetric wrt $OI$ and thus congruent.

However, I still think that junior participants to the TST are not usually familiar with Poncelet's result. There is a synthetic proof of this theorem for our case (triangle), but it's not that easy to spot and this probably wasn't regarded as an easy problem (I have no idea, but I'm guessing :D).

hi
for each triangle ABC, i think there would be a unique point M on arc BC (not containing A) s.t. <BAC=<NMP (N and P, as in the problem, points where tangents from M to incircle intersect circumcircle).
Is there any nice construction for this point? just interested.
oh and whats Junior Balkan?

Like I said in my previous post, the point $M$ should be the symmetric of $A$ wrt the line $OI$. If we compute the length of $AI$ given the values of $R,\ r,\ \angle A$, then $M$ and $A$ are the intersections of the circle centered at $I$ and radius $AI$ with the circumcircle of $ABC$. I don't know if the point $M$ constructed as stated above always lies on the arc $BC$: maybe sometimes it lies outside that arc. Anyway, there is only one such point on the circumcircle of $ABC$ (except for $A$, of course).

hi guys!
indeed grobber you are right, the original idea came from the old mathlinks problem, which stated that, and from the fact that I happen to like a nice little lemma which states
\[ \cos A + \cos B + \cos C = 1 + \frac rR. \]
Obivously using Poncelet and this lemma, the problem follows from a simple trigonometric approach.
However, a much simpler aproach is possible (which has been given by some of the contestants): let $A',B',C'$ denote the intersection points of the incircle with the oposite sides of the coresponding vertices. Define in the same way $N',P'$. You must prove that the triangles $AIC'$ and $MIP'$ are congruent ($P$ is supposed to lie between $A$ and $C$ on $\mathcal{C}$.
This follows easily, so now you can also prove that the triangles $AMN$ and $MAB$ are congruent $\angle NAM = \angle A/2 + \angle NAB = \angle A/2 + \angle NMB = \angle AMB$, $AM=AM$ and $\angle BAM = \angle A/2 = \angle NMA$.
Thus $AB=MN$ and we are done :)