algebra
polynomial
infinitely many solutions
equation
IMO Shortlist

Let $P$ be a cubic polynomial given by $P(x)=ax^3+bx^2+cx+d$, where $a,b,c,d$ are integers and $a\ne0$. Suppose that $xP(x)=yP(y)$ for infinitely many pairs $x,y$ of integers with $x\ne y$. Prove that the equation $P(x)=0$ has an integer root.

Suppose by contradiction that $P(x) \neq 0$ for all integer $x$.

For each $(x,y)$ such that $xP(x) = yP(y)$, we have
\[ a (x^4 - y^4) + b (x^3 - y^3) + c (x^2 - y^2) + d (x - y) = 0,  \]
that is, simplifying by $x-y \neq 0$ and letting $k=x+y$
\[ a k(2 x^2 - 2kx + k^2) + b (x^2 - kx + k^2) + c k + d = 0,  \]
thus
\[ x^2 (2ak+b) - kx(2ak+b) + P(k) = 0.  \]

If $2ak+b=0$, then we get $P(k)=0$, that is a contradiction.

If $2ak+b \neq 0$,
\[ x=\frac{k(2ak+b)\pm\sqrt{k^2 (2ak+b)^2 - 4 (2ak+b) P(k)}}{2(2ak+b)},  \]
that is
\[ 2x=k \pm \sqrt{k^2 - 4 \frac{P(k)}{2ak+b}},  \]
thus $4 \frac{P(k)}{2ak+b}$ is an integer.

We deduce that $\frac{8 a^2 P(k)}{2ak+b}$ also is. But it is equal to
\begin{eqnarray*} & & \frac{8 a^3 k^3 + 8 a^2 b k^2 + 8 a^2 c k + 8 a^2 d}{2ak+b} \\ &=& \frac{(4 a^2 k^2 + 2ab k + 4ac - b^2)(2ak+b) + (b^3 - 4abc + 8a^2 d)}{2ak+b} \\ &=& (4a^2 k^2 + 2abk + 4ac - b^2) + \frac{b^3 - 4abc + 8da^2}{2ak +b}. \end{eqnarray*}
Thus for all $(x,y)$ such that $xP(x) = yP(y)$, $2a(x+y)+b$ divides $b^3 - 4abc + 8da^2$, which is a constant.
$(x+y)$ thus takes only a finite number of values. Since we can compute $x$ and $y$ in terms of $x+y$ (in fact each value of $x+y$ gives two possible values of $x$), we get that there is a finite number of $(x,y)$ verifying the condition $xP(x) = yP(y)$. It also gives a contradiction.

As in the previous solution, we have
\[a(x^{4}-y^{4})+b(x^{3}-y^{3})+c(x^{2}-y^{2})+d(x-y) = 0. \]
Since $x \neq y$, we may divide by $(x-y)$ to obtain
\[a(x^{3}+x^{2}y+xy^{2}+y^{3})+b(x^{2}+xy+y^{2})+c(x+y)+d = 0, \]
or, using the notation $k = x+y$,
\[P(k) = xy (2ak+b). \]

Let $P(x)$ have roots $\lambda_{1}\le \lambda_{2}\le \lambda_{3}$.  We note that the function $xP(x)$ is bounded on the interval $\Big[ \min(\lambda_{1}, 0) , \max(\lambda_{3}, 0 ) \Big]$ and injective on each of the intervals $(-\infty , \min(\lambda_{1}, 0)) , \; (\max(\lambda_{3}, 0), \infty)$.  Because each value of $xP(x)$ yields at most finitely many solutions $x,y$, there are only finitely many solutions $x,y$ such that $x$ and $y$ have the same sign.

Clearly, if $P(k) \neq 0$, then each value of $k$ yields at most one solution.  But for arbitrarily large values of $k$, $P(k)$ and $(2ak+b)$ have the same sign, making our equation $P(k) = xy(2ak+b)$ impossible if $x$ and $y$ have different signs.  Thus there must be some integer $k$ such that $P(k) = 0$.  (Indeed, if $P(k) = 2ak+b = 0$, then any pair of integers with sum $k$ will work.)

My solution starts the same as previous ones but it is different in the later part. Maybe someone will find that interesting.

So, suppose that $P(x)$ satisfy given conditions but it doesn't have integer root. Therefore, it is irreducible in the $\mathbb{Z}[x]$. As before, we reach the form
$P(\alpha)=\beta(2a\alpha+b)=\beta Q(\alpha)$
where $\alpha=x+y$ , $\beta=xy$ and $Q(x)=2ax+b$. We will prove that this equation has solution only for finitely many $\alpha$. Indeed, suppose on the contrary. From the fact that $P$ is irreducible and $Q$ is a of lower degree than $P$ we conclude that $P, Q$ are relatively prime in $\mathbb{Z}[x]$. So, there exist $f, g \in \mathbb{Z}[x]$ such that:
$f(x)P(x)+g(x)Q(x) = C$ for some non-zero integer constant $C$.  From putting $x=\alpha$ and relation $Q(\alpha)|P(\alpha)$ we obtain that $Q(\alpha)|C$. Since $Q$ is non constant we see that $C$ must have infinitely many divisors, but that's impossible because $C \not = 0$.
So, our previous equation has solution for only finitely many $\alpha$. But then it has also solution for finitely many $\beta$ (since $\beta$ is linear in terms of $\alpha$). For given $\alpha, \beta$ there is at most one pair of integers $(x,y)$ satisfying $x+y=\alpha, xy=\beta$, so our equation has only finitely many solutions in pairs of integer $(x, y)$. That's contradiction with assumption.

[quote="TomciO"]but it doesn't have integer root. Therefore, it is irreducible in the $\mathbb{Z}[x]$.[/quote]
This is wrong. $8x^{3}-1=(2x-1)(4x^{2}+2x+1)$ has no integer root, but is reducible in $\mathbb{Z}[x]$.

[url=http://www.mathlinks.ro/Forum/viewtopic.php?t=127361]Here[/url] I showed $xP(x)=Q((x-{t\over 2})^{2})$ for some $Q(x)\in\mathbb{R}[x]$ and $t\in\mathbb{Z}$.
Then $0=0\cdot P(0)=Q(({t\over 2})^{2})=tP(t)$.
If $t\not =0$, then $P(t)=0$ with $t\in\mathbb{Z}$.
If $t=0$, then $Q(0)=0$ and $x^{2}|Q(x^{2})=xP(x)$ and $P(0)=0$.

Sorry for reviving an old topic
[quote="toumaf"]

If $2ak+b=0$, then we get $P(k)=0$, that is a contradiction.

[/quote]
For this to be a contradiction , we need $\frac{b}{2a}$ to be an integer. How  is that so?

For $ xP(x)=yP(y) $, suppose, $ x=\frac {u+v}{2} $ and $ y=\frac {u-v}{2} $ where $ u,v $ are integers. Simplifying the equation we get that $ v^2(2au+b)=-(2au^3+3bu^2+4cu+4d) $. f $ u=\frac {-b}{2a} $, then $ f(\frac {-b}{2a})=0 $. Otherwise note that dividing $ 2au^3+3bu^2+4cu+4d $ by $ 2au+b $ we get that the remainder(which is $ 8a^3f(\frac {-b}{2a}) $) is divisible by $ 2au+b $ for infinitely many $ u $. So $ f(-\frac {b}{2a})=0 $. So $ xP(x)=(-\frac {b}{2a}-x)P(-\frac {b}{2a}-x) $. So if $ y\ne -\frac {b}{2a}-x $ for all $ x $, then note that the value of $ xP(x) $ is equal for three values of $ x $, but this is possible only within a bounded region, but $ x $ is not bounded. So $ y=-\frac {b}{2a}-x $ after the bound. So $ \frac {b}{2a} $ is integer. So done.

Sahil I don't really understand what's bothering you we have set $k=x+y$ so that is an integer value regardless of $a$ and $b$ there is no need for RSM's proof.

Am I missing something? Let $Q(x)=xP(x)$ Consider $Q(a-x)-Q(x)$. We can see that for $a$ with large enough magnitude, this will have no integer roots. Therefore, for some $a, Q(a-x)-Q(x)=0$ as a polynomial, and so $P(a)=0$.

First of all, don't use $a$, since that already is the leading coefficient of $P$. So, replacing with $\alpha$, even if your claim that for large enough magnitude of $\alpha$ you have the polynomial $Q(\alpha - x) - Q(x)$ to have no integer root, all you do is rule out the pairs $u\neq v$ with $u+v=\alpha$ for which $Q(u) = Q(v)$. But there exist infinitely many pairs  $u\neq v$ with $u+v<\alpha$, so there is room for infinitely often having  $Q(u) = Q(v)$. What are you trying to do there?

There do indeed exist infinitely many such pairs, but if we bound $a$ it follows by polynomial identity that for a specific value of $a$, $Q(x)=Q(a-x)$ is true for all $x$. Then either $a=0$, in which case $Q$ is even and so $0$ is a double root and must be a root of $P$, or $a \neq 0$ and $a$ is a root of $P$.

Ok. So we agree that if for all those infinitely many pairs $(u,v)$ with $u\neq v$ for which $uP(u) = vP(v)$ we had the set $\{\alpha = u+v \mid u\neq v, uP(u)=vP(v)\}$ to be bounded, then for some $\alpha$ we would have infinitely many pairs $(u,v)$ with $u+v=\alpha$, and then $R_{\alpha}(x) = Q(\alpha-x) - Q(x)$ would be identically null.

It is your claim relative to that set needing to be bounded that is unsustained as yet. In fact $R_{\alpha}(x) = Q(\alpha-x) - Q(x)$ always has an integer root for even $\alpha$ (albeit being related to $u=v$, which is not allowed).

For $a$ large enough, suppose $Q(a-x)-Q(x)$ has a root $a/2+r$ where $r$ is nonzero. Then $Q(a/2+r)=Q(a/2-r)$. For $a$ large enough magnitude, the polynomial$ R(x)=Q(a/2+x)$ will have  $x^3$ and $ x$ terms with the same sign. Therefore, $R(x)-R(-x)$ will have no roots other than at $x=0$.

This problem is solved if you think to reduce the polynomia to degree $2$ by setting $x+y=k$. There is really nothing much else to it. And without this trick I don't think there is a nice solution is there?

[hide="solution"]
Ugh, what a terrible problem...
\begin{align*}
xP(x)=yP(x), x\ne y &\iff a(x^4-y^4)+b(x^3-y^3)+c(x^2-y^2)+d(x-y)=0, x\ne y\\
&\iff a(x+y)(x^2+y^2)+b(x^2+xy+y^2)+c(x+y)+d=0\\
&\stackrel{\substack{p=x+y\\q=xy}}{\iff}  ap(p^2-2q)+b(p^2-q)+cp+d =0\\
&\iff q=\dfrac{ap^3+bp^2+cp+d}{2ap+b}\in \mathbb{Z}
\end{align*}
Plugging in $p=-\dfrac{b}{2a}$ in to $ap^3+bp^2+cp+d$ to find the remainder of our division, we get $\dfrac{b^3}{8a^2}-\dfrac{bc}{2a}+d$ so $$2ap+b \mid b^3-4abc+8a^2d$$ But since the RHS is a constant and this has solutions for infinitly many pairs $(x,y)$, then the LHS is constant infinitely many times, so $p=x+y$ is constant for infinitely many values; let this constant be $p'$.
Now consider the polynomial $xP(x) - (p'-x)P(p'-x)$; it has infinitely many roots so it is identically zero; that is, $xP(x)$ is symmetric about $x=\dfrac{p'}{2}$. But since $x=0$ is certainly a root of $xP(x)$, then $x=p'$ is a root as well; furthermore, it is a root of $P(x)$ so we are done. $\Box$
[/hide]

[url]https://artofproblemsolving.com/community/c6h1231860_generalization_of_sl_2002_a3[/url]
This is the best solution!

Hopefully this is right.

The equation $xP(x) = yP(y)$ rewrites as \[a(x^4-y^4) + b(x^3-y^3) + c(x^2-y^2) + d(x-y) = 0.\] Since $x\neq y$, we can divide out $x-y$ to get \[a(x^3+x^2y+xy^2 + y^3) + b(x^2+xy+y^2) + c(x+y) + d = 0.\] Now let $s = x + y$, $p=xy$.  Then \[a(s^3 - 2sp) + b(s^2 - p) + cs + d = 0,\] or $p(2sa+b) = P(s)$.  Thus $2as + b$ divides $P(s)$ for infinitely many pairs $(x,y)$.  But this means $2as + b$ divides $P(s)$ for infinitely many integer values of $s$.

Write $P(x) = (2ax + b)Q(x) + R$ for some rational $R$ and rational polynomial $Q(x)$ .  Scaling up by some positive integer $N$, we may assume that $Q(x)$ and $R$ are integers at the expense of dividing into $NP(x)$ instead.  Hence $2as + b$ divides $R$ for infinitely many integers $s$, implying $R = 0$.  (Here we use $a\neq 0$.)

Thus $2ax + b$ divides $P(x)$ as polynomials, ergo $P(x)$ has a rational root (again using $a\neq 0$).  Thus $P(x)$ is reducible in $\mathbb Q[x]$, so by Gauss's Lemma it's also reducible in $\mathbb Z[x]$.  In turn, $P$ has an integer root.

We more generally show the assertion when $P$ is replaced by any polynomial of odd degree.

[b][color=#f00]Lemma: [/color][/b] Given an non-constant even degree polynomial $Q(x)$ such that $Q(x) = Q(y)$ holds for infinitely many pairs $(x,y)$ of integers with $x \ne y$. Then $Q(x) \equiv Q(c-x)$ for some constant $c \in \mathbb Z$.

[i]Proof: [/i] WLOG assume leading coefficient of $Q$ is positive, otherwise change $Q \to -Q$. First choose a constant $M,K,N \in \mathbb Z_{> 0}$ such that both sequences
$$ P(M),P(M+1),P(M+2),\ldots ~~;~~ P(-M),P(-M-1),P(-M,-2),\ldots $$
are strictly increasing ; and
$$Q(x) - Q(N-x) >0 ~~ \forall ~ x \ge K \qquad , \qquad Q(x) - Q(-N-X) < 0  ~~ \forall ~ x \ge K$$
By changing $M \to \max(M,K)$, WLOG $M \ge K$. Let set
$$ S_1 = \{M,M+1,M+2,\ldots\} ~~,~~ S_2 = \{-M,-M-1,-M-2,\ldots\} $$
Basically, all elements of $Q(S_1),Q(S_2)$ are distinct. Now for infinitely such $x,y$ with $Q(x) = Q(y)$, we have that one of $x,y$ is in $S_1 + K$ while other is in $S_2$. Now for any $x \in S_1 + K$, We know the element $y \in S_2$ for which $Q(x) = Q(y)$ must satisfy
$$ y \in (-N-x,N-x) $$
Basically, $x+y$ can take finitely many values only. So there is a constant $c$ such that for infinitely many pairs $x,y$ we have $x+y = c$ and $Q(x) = Q(y) = Q(c-x)$. More particularly, the polynomial
$$Q(x) - Q(c-x)$$
has infinitely many roots, and hence is identically $0$. This proves our Lemma. $\square$

Our Lemma for $Q(x) \equiv xP(x)$ implies for some $c \in \mathbb Z$ we have
$$ xP(x) \equiv (c-x)P(c-x)  $$
If $c \ne 0$, then $x=c$ just gives $P(c) = 0$. Otherwise for $c=0$ we have
$$ xP(x) \equiv -xP(-x) \qquad \text{or} \qquad P \text{ is odd} $$
But then $P(0) = 0$, completing the proof. $\blacksquare$

Because the polynomial $Q(x)=xP(x)$ is bounded on the interval containing its turning points, for $xP(x)=yP(y)$ to hold infinitely often we need $x$ and $y$ to lie on the "left branch" and the "right branch" of $Q$ infinitely often. If $y=-x+k$, then $k$ must be bounded both below and above for size reasons, else the absolute value of the $x^2$ term in $Q(y)$ is greater than $|b|$, and thus $Q(y)-Q(x)$ is nonzero for large enough $x$. Then by infinite pigeonhole, we must pick some value of $k$ infinitely many times, in which case $0 \equiv xP(x)=yP(y) \equiv kP(k) \pmod{x}$ for infinitely many $x$. But then $kP(k)=0$, so we're done unless $k=0$. If $k=0$, then $Q(x)$ is odd and thus is of the form $ax^3+cx^2$, hence $x=0$ is a root of $P$. $\blacksquare$

This proof works for any odd degree $P$

Suppose otherwise. Let $x+y=s$. Since $x-y\neq 0$, for infinitely many $x$, $y$, the following is zero:
\[\frac{xP(x)-yP(y)}{x-y}=as(s^2-2xy)+b(s^2-xy)+cs+d\]
Therefore, we have $P(s)=xy(2as+b)$. If $s$ is made constant, then $xy$ is determined, so there are finitely many $(x,y)$ that work per $s$. Therefore, it is true for infinitely many $s$. Thus, $|P(s)|=|xy||(2as+b)|\le \tfrac{s^2}{4}|2as+b|$. For large values of $s$ the left will overpower the right due to a larger leading term. Contradiction.

Let $Q(x) = x P(x) = ax^4 + bx^3 + cx^2 + dx$. WLOG $a > 0$ since we can swap $Q$ with $-Q$.

 Note that there must be infinitely many integers $x,y$ with opposite sign satisfying $Q(x) = Q(y)$ (as $Q$ is injective over the large positives and the large negatives). Letting $p = x + y$, we have \[ \frac{Q(x) -Q(y)}{x-y} = a \cdot p (p^2 - 2xy) + b \cdot (p^2 - xy) + c \cdot p + d = P(p)  - xy (2ap - b)\] Hence there are infinitely many integers $x,y$ with opposite sign satisfying $P(p) = xy(2ap - b)$. Notice that $xy$ is fixed for a given value of $p$ (as if $2ap - b = 0$ then $P(p) = 0$, absurd), so there can be at most one solution for each $p$. Now if we take $p$ sufficiently large, then $P(p)$ and $2ap - b$ are greater than $0$, which contradicts the fact that $x,y$ are opposite signs.


Let $ A$ and $ B$ be $ n \times n$ diagonalizable matrices. Is it true that $ AB$ are always diagonalizable? If true, give a proof. If not, give a counter-example.

I'm pretty sure it's false... but I'm having the hardest time finding a counter example, any help?

$ \begin{bmatrix}1 & 1 \\
0 & - 1\end{bmatrix} \begin{bmatrix}1 & - 1 \\
0 & - 1\end{bmatrix} = \begin{bmatrix}1 & - 2 \\
0 & 1\end{bmatrix}$

$ \text{\LaTeX}$ tip: let $ A$ and $ B$ be $ n\times n$ diagonalizable matrices ... That's n\times n .


Actually this is known as Carlson's Inequality and equality can never be achieved...Also $ \frac{\pi^2}{6}$ is the best possible constant...

[quote="Potla"][quote="Rijul saini"]Actually this is known as Carlson's Inequality and equality can never be achieved...Also $ \frac {\pi^2}{6}$ is the best possible constant...[/quote]
But when $ n\to \infty$ and $ a_i \equal{} a_j \forall i,j \equal{} 1,2,\cdots n$ we can have equality... :huh:[/quote]
Well we can't exactly set $ n\equal{}\infty$... we can get arbitrarily close to reaching equality, but we will never reach it. Another example if it's not quite clear: if we have $ x$ as a positive real, we can say $ x>0$. We can get $ x$ arbitrarily close to 0, but equality will never be reached.


How do you do those questions that say something like, What is the maximum number of intersections of a 3rd degree polynomial and a 4th degree polynomial?

Sample problem?

I think I asked about one of these the other day in the thread called 1999 AHSME questions.

uhhh. i dont know if this helps, but to solve that, you could just set the two polys equal and bring them on one side, then see the maximum amount of roots the resulting equation could have. of course, it could always be an infinite amounts if they're of the same degree. but i dont know.

Well a question off the top of my head would be...

What is the maximum number of intersections of a cubic polynomial and a fourth degree polynomial?

doing what i said, i think there could be 4 maximum, as long as the leading coefficients of both are not 0. if not, then 4 max if cubic has 0 for l.c., or 3 max if quartic has 0 for l.c.

Well, s0mp is saying to just set the polynomials equal, so given

f(x) = ax^4+bx^3+cx^2+dx+e
g(x) = fx^3+gx^2+hx+i

we have

f(x) = g(x)
ax^4+bx^3+cx^2+dx+e = fx^3+gx^2+hx+i
ax^4+(b-f)x^3+(c-g)x^2+(d-h)x+(e-i) = 0

The LHS is a quartic, so it obviously has 4 roots (though not necessarily real).

the maximum number of intersections of polynomials P(x), Q(x) of degree n,k where n>k is n. the intersections are where the two polynomials are equal so, P(x)=Q(x) => P(x)-Q(x) = 0. Since P(x)-Q(x) is a polynomial of degree n it can have at most n real roots. if P and Q are of equal degree, the maximum number of intersections is the degree, unless the leading coefficent (s) are equal, in which case some get canceled out.


solve the equation in integers (x^2-y^2)^2=1+16y

Obviosly $ y\ge 0$. Consider $ y\equal{}0,1,2,3,4,5$. It give $ (x,y)\equal{}(\pm 1,0),(\pm 4,3),(\pm 4,5).$
If $ y>5$, then $ 1\plus{}16y<(2y\minus{}1)^2\to \parallel{}x|\minus{}y|<1$. Becauase $ |x|\equal{}y$ is not solution, we find all solutios.

[quote="Taoli"]$ (x^2 \minus{} y^2)^2 \plus{} 64y^2 \equal{} (1 \plus{} 8y)^2$[/quote]
Pythagorean triples yields
$ |1\plus{}8y|>|x^2\minus{}y^2|,|1\plus{}8y|>8|y|$ and $ y$ is even.


PT: $ \frac{x \plus{} y}{2z \plus{} x \plus{} y} \plus{} \frac{y \plus{} z}{2x \plus{} y \plus{} z} \plus{} \frac{z \plus{} x}{2y \plus{} z \plus{} x} \ge \frac{3}{2}$ for positive $ x, y, z$.

Let $ a\equal{}x\plus{}y$ $ b\equal{}y\plus{}z$ $ c\equal{}x\plus{}z$. Nesbitt. Q.E.D.

sorry but am i wrong?
substitute,
$ x \plus{} y \equal{} a$
$ y \plus{} z \equal{} b$,
$ z \plus{} x \equal{} c$
and it is nesbitt's

edit: i dint know rofler posted sry

Sorry, the trap worked in the reverse direction. And obviously Nesbitt is immune to traps as it is so well known. The problem does not work. My bad. :P


You have 12 gold coins, one of which you know is counterfeit and has a different mass than the other coins. You also have a scale. Using this scale at most three times, how can you determine which coin is counterfeit, and if it is lighter or heavier than the real coins?

It is "12 balls problem"!
[url]http://www.newton.dep.anl.gov/newton/askasci/1995/math/MATH007.HTM[/url]

Actually, I have never seen that problem before!


A, B, and C each can be any digit 0 through 9, possibly the same.  The seven-digit whole  number:   20ABC01   is a perfect square.    What is the middle digit, B?

A.1    B.  3    C. 5      D.7      E. 9


algebra
polynomial
group theory
abstract algebra
geometry
3D geometry
rotation

I am looking for the Galois Group of the polynomial $ x^6\plus{}x^3a\plus{}a^2$ where $ a$ is an integer not a perfect cube. I already showed that the splitting field is $ \mathbb{Q}(\sqrt[3]a,\xi)$ where $ \xi$ is a primitive ninth root of unity and i already showed that the degree of the extension is 18. My goal is to construct the whole diagram.
Thanks for any help

The Galois is naturally a subgroup of the symmetric group $ S_6$ on the roots, and we know one element $ c$: conjugation, which is  product of three disjoint transpositions. A group of order 18 has a unique normal subgroup of order 9. The Sylow subgroups in $ S_6$ of order 9 are of the form $ \{a^mb^n\}$, where $ a$ and $ b$ are disjoint 3-cycles; the order-9 subgroup $ H$ of our Galois group $ G$ must be one of these.
Now, which two cycles did we use? If $ a$ is an element of $ H$, $ cac^{\minus{}1}$ is as well. Conjugation in $ S_n$ is relabeling of the cycle decomposition, so either $ c$ permutes the elements moved by $ a$ or $ c$ sends those elements to the elements moved by $ b$. The former is inconsistent with what we know about $ c$, so these triples are conjugate to each other (in both senses).

All right, it's time to label the roots. Let $ r_k\equal{}e^{2\pi i k/9}a^{1/3}$ for $ k\equal{}1,2,4,5,7,8$. Our purely group-theoretic argument in the preceding gives us the whole group if we can name the cycles $ a$ and $ b$. The choices for $ a$ (making the arbitrary choice that $ r_1$ is moved by $ a$) are $ \{r_1,r_2,r_4\}$, $ \{r_1,r_2,r_5\}$, $ \{r_1,r_4,r_7\}$, and $ \{r_1,r_5,r_7\}$. We need to determine which one is right, although it's pretty easy to guess.
Here, note that $ \frac{r_k^3}{a}$ is a cube root of unity, and the degree-2 field for this root of unity corresponds to an index-2 subgroup of $ G$, which must be $ H$. This means that $ H$ fixes $ r_k^3$ for each root $ r_k$, and this means that $ \{r_1,r_4,r_7\}$ and $ \{r_2,r_5,r_8\}$ must be the generating 3-cycles.

We can also write the group as a direct product of a dihedral group $ S_3$ and a cyclic group of order 3; the former part rotates or reflects the whole polygon of roots, while the elements of the latter consist of a rotation of one triangle and a rotation of the other in the opposite direction, keeping conjugate pairs together.


Let a,b,c,d>0 satisfying $ a \plus{} b \plus{} c \plus{} d \equal{} a^2 \plus{} b^2 \plus{} c^2 \plus{} d^2$.Prove that:
$ a^3 \plus{} b^3 \plus{} c^3 \plus{} d^3 \plus{} a \plus{} b \plus{} c \plus{} d$≤$ 8$

Let $ a^2\minus{}a\equal{}x,b^2\minus{}b\equal{}y,c^2\minus{}c\equal{}z,d^2\minus{}d\equal{}t$ so we have $ x\plus{}y\plus{}z\plus{}t\equal{}0$ and we must prove

\[ \sum{(2\plus{}x)\sqrt{1\plus{}4x}}\leq 8\]

and it is so clear because $ (2\plus{}x)\sqrt{1\plus{}4x}\leq 5x\plus{}2$ and $ a,b,c,d<2$ :wink:


vector
superior algebra
superior algebra solved

hi all,

let E a vector space of finite dimension n. Let f a linear map
from E to E. Consider the following endomorphism T:
T(g)=fg-gf.
Prove that if f is diagonalizable then so is T.
Prove that if f is milpotent then so is T.
Is there any converse ?

my teacher gave a solution using nearly no calculation ..  :D

Sorry if this is clear for everybody else, but there's something I don't understand: is $g$ another endomorphism of $V$, and you meant to say that those properties are true for $T(g)$ for all endomorphisms $g$?

There's another way to interpret this: $T$ itself is an endomorphism of $End(E)$ regarded as a vector space over the same field as $E$, but in order for $End(E)$ to be a vector space (so that it can itself have endomorphisms), we should mention that the field is commutative.

This is really confusing for me :?.

oh sorry, it's true that it was not very clear. Let me reformulate the problem:

**
let E a vector space of finite dimension n over a commutative field K. Let f be a fixed  linear map from E to E. Consider the following endomorphism T_f.(it is an endomorphism of End(E) and End(E) is a vector space over the same field K):
(T_f)(g)=fg-gf for every g in End(g).
Prove that if f is diagonalizable then so is T_f.
Prove that if f is milpotent then so is T_f.
Is there any converse ?

I think the nilpotence is clear, because for sufficiently large $n$, all terms of $T_f^n$ have $f$ with an exponent $\ge k$ no matter what $k$ we choose. If $k$ is chosen s.t. $f^k=0$, we're done.

If $f$ is diagonalisable in the basis $e_i$, $f(e_i)=x_i.e_i$ where $x_i \in K$
Construct $t_{ij}$ a basis of $End(E)$ by $t_{ij}(e_k)=\delta_{jk}e_i$
It is easy to check $T_f(t_{ij})(e_k)=\delta_{jk}(x_i-x_k)e_i$ and $T_f(t_{ij})=(x_i-x_j)t_{ij}$


linear algebra
matrix
superior algebra
superior algebra solved

A,B \in Mn(R)
a) suppose A^2-B^2=AB-BA prove that det(A+B)=0 or det(A-b)=0
b)suppose that A^2+B^2=AB+BA prove that det(A-B)=0
Florin Rotaru, Focsani
GM4/1999

b) A^2+B^2=AB+BA which is equivalent to (A-B)^2=0 which gives det(A-B)=0

a)A^2-B^2=AB-BA which is equivalent to (A-B)(A+B)=0 which is what we wanted!

cheers!


function
calculus
derivative
analytic geometry
graphing lines
slope
quadratics

Consider any C-infinity function f(x).  (That means that the function and all of its derivatives are continuous.)  If f is linear, it has the property that f(x+1) = f(x) + f'(x).  (This is the same thing as saying that when you move one unit to the right, the function increases by its slope, which happens for linears to be constant.)  Now, the question is, will any other functions have this property?

Things I've tried:  no quadratic or cubic polynomials work.  No function of the form d*e^(c*x) works.  Any linear equation works.  Taylor series lead to nothing nice -- either expanded around 0 or around 1/2.  So.  I believe that only linear functions work -- but can you prove it?

Modifications:  try f(x+1) = f(x) + f'(x+1).
f(x+1) = f(x) + f'(x+c), c any real constant.

Most general:
f(x) = c1*f(c2*x + c3) + c4*f'(c5*x + c6), for constants c1, c2, c3, c4, c5, and c6.

Does anyone know of a program that might let you try and sketch such a function?  Because if you can trace out the function on [0, 1] it determines the entire function.

If it's a differential equation, then you can use Taylor series. (Sorry, but that's the only way I can solve them most of the time, so it has become somewhat automatic for me.) Let's just expand around 0. We want:

a+b(x+1)+c(x+1)2+d(x+1)3+... = a+bx+cx2+dx3+... + b+2cx+3dx2+4ex3+...

Expanding out the constant terms gives a+b = a+b + (c+d+e+f+...). Thus c+d+e+f+...=0. Expanding out the linear terms gives b+2c = b+2c + (3d+4e+5f+...), so 3d+4e+5f+...=0. Expanding out the quadratics gives (4 choose 2)e+(5 choose 2)f+(6 choose 2)g+...=0, etc. But we have a system of linear equations (let's ignore a and b, since they just make life difficult), and those have 0, 1, or infinitely many solutions. If there are infinitely many, they must lie on some hyperplane, but I don't see that happening. (Proof would be nice, but it eludes me right now.) We know of one solution already, namely all zeros, so that must be the only one.

This is a system of infinitely many equations in infinitely many variables -- do those rules you stated still apply?  I wasn't able to convince myself mathematically (as opposed to intuitively) that the system wouldn't have as many solutions as I want.

Ignoring a and b, of course, is the same thing as saying that any linear equation will work -- they're my two degrees of freedom and can be whatever they want and that shouldn't cause any problems.

Geometrically, the problem asks you to find f(x) s.t. that the slope of (x, f(x))-(x+1,f(x+1)) is equal to the slope of the curve at (x,f(x)). I bet you can do stuff with, like, the mean value theorem or something. I think a more interesting generalization would be f(x+k)=f(k)+k*f'(x), because of the above.

Did you mean f(x+k) = f(x) + k*f'(x) ?  Because if you did, that is one of the cases covered by my general equation.  Only, in the way I wrote it, it would appear as f(x) = f(x-k) + k*f'(x-k).  And I think if the specific example of my problem can be solved, then that equation should follow without a whole lot of work.

I am hoping that someone will take another crack at this.  I have still gotten nowhere.

I've had a little think about this, aren't there heaps and heaps of solutions? For example, lets say we define f(0)=0, f(1)=1, and draw any continuous curve joining them with f'(0) = f'(1) = 1.

Now we can just use f(x+1) = f(x) + f'(x) to shift this along one..

Since the sum of two continuous functions is continuous, and each time we get to x = an integer, the value there is f(x-1) + f'(x-1) = f(x-1) + 1 = f(x-2) + 2 = ... = x. So we get f(x) = x for integers x, and also f'(x) will remain equal to 1.. you can see that just by looking 1 unit to the left and doing the same sort of thing..

And then of course you could have different gradients at each integer and stuff like that..

I think the bit where you argue that f(x) = x at all integers doesn't really work out -- you'll need to fix the second and higher derivatives at x = 0 in order to get that.  You will start needed the first derivative at f(x + 2), which depends on the second derivative at f(x + 1), and so on.  And that (I'm afraid) will end up fixing your function to the function f(x) = x.  On the other hand, I understand exactly what you're saying -- any nice function on [0, 1] with this property should give you a function on [0, infinity).  But, because all of the derivatives of f(1) get fixed by those at f(0), that equation might really force it to be linear.  At least, I'm not sure that it won't.  If you could try to give me a function that works, I'd love to see it -- if it's as straightforward as you suggest, that shouldn't be a problem.

TripleM, I don't think what you are doing will work since you're sort of fixing the placements of some points in (0,1) when you deal with f'(0). I thought about doing that a bit, motivated by functional equations like f(x+y)=f(x)+f(y) which have horribly messy solutions. (We can only prove that f=ax at rational points, and then we can take f=bx, f=cx, etc. for linearly independent irrationals over the field of rationals.) I don't think it will work nicely though. If you find some, I'd love to see them. I guess the idea is that the set of integers is nowhere near a dense set, and so you can play around inside, but I'm just not convinced that it will work.

On second thought, what if you make f(x/y)=ax/y, where x and y are integers? You might have a small amount of flexibility with irrationals, and it may be enough.

I'm still not exactly sure whats wrong. Heres what my "proof" is:

Define a continuous curve on [0,1) and choose f(0) and f'(0) so that f(1) = f(0) + f'(0) so that its continuous on [0,1]. Then for each x>1 (I'll forget negatives for now) define f(x) = f(x-1) + f'(x-1). Now we have a curve that is continuous everywhere except possibly x=each integer point.

We know that the curve is continuous at x=1. Suppose that it is continuous at x=1, 2, 3, .., n.

Now we want to prove lim(x->n+1) f(x) = f(n+1).
lim(x->n+1) f(x) = lim(x->n+1) f(x-1) + lim(x->n+1) f'(x-1)
= lim (x->n) f(x) + lim (x->n) f'(x).

But we know that lim (x->n) f(x) = f(n) and lim (x->n) f'(x) = f'(n) by induction.

So lim(x->n+1) f(x) = f(n) + f'(n) = f(n+1).

So it is continuous everywhere..

Whats wrong with this?

I will be convinced if you can show me a function that works.  Until then, I will agree that what you've written is convincing, but I'm still not entirely sure.  Particularly because of higher derivatives -- will your function be differentiable?  Will the condition of higher derivatives force it to be linear, despite everything you've said?  If you can show me a function that works, I will shut up and admit I'm wrong -- until then, I'll be skeptical.

Well following my last post, just take any function between 0 and 1 like I said and that should work.. there won't be any general formula for one though.

But I think I may have found the problem, it doesn't prove f'(x) is continuous.. still have to work on that. For now, I'd have to say I'm pretty sure there will be other solutions than linear.

x+x^2-x^3 satisfies your conditions, but yet it doesn't work. If you then change your mind and decide to define it piecewise on each unit interval, then all of a sudden the function won't be everywhere differentiable.

In fact, any quadratic and cubic only works if it is in fact linear.  That's not hard to show by equating coefficients.  That's what I mean when I say the condition might force your function to be linear -- it's stronger than it looks because it says something about all of the derivatives, not really just the first derivative.  So when you start with a higher-degree polynomial, you end up forcing all the coefficients to 0.  I haven't been able to show that it works for non-polynomial functions, though.

Here is my attempt to show that there is a nonlinear solution to this equation.

Let c be a nonzero, complex number such that ec = 1 + c.  I don't know a proof that such a number exists.  But numerically, they seem to exist.  For example, c = 2.088843016 + 7.461489286 [b]i[/b] is approximately a solution.  For now I will assume that there exists an exact solution.

Now let f(x) = ecx.  If you prefer that f be real-valued, just take the real part of that function.  It is easy to see that f(x+1) = f(x) + f'(x), precisely because ec = 1 + c.

To finish off the proof, let me try to prove that there exists a nonzero, complex number c such that ec = 1 + c.

Define the complex function g by g(z) = ln(1+z) + 2 :pi: [b]i[/b],
where ln is the principal branch of natural logarithm (having imaginary part between - :pi: and  :pi: ).  Let D be the set of complex numbers having imaginary part at least  :pi: .  Because we chose the principal branch, g maps D into D.  Also for z in D, we have |g'(z)| = 1 / |1+z|  :le: 1/ :pi: .  Hence, by Banach's contraction fixed-point theorem, g has a fixed point c.  But a fixed point c of g must satisfy ec = 1 + c, so we are done.

Interesting -- I played around on Mathematica and it appears that you are correct -- I can generate a function from it according to your argument that looks like a standard sin wave in need of anti-psychotic medication.  My knowledge about what you've done is not very good, however, so I wanted to ask a few questions:

Is Re[dw/dz] = d(Re[w])/dz?  Because if not necessarily, then this will only work as a complex function, not a real function.

Is there going to be a nice way of writing this function down?  If it really is continuous and infinitely differentiable, which it at least sort of appears to be (although the derivitives are perilously close to infinity, very often), it should have some sort of power series expansion, should it not?  What might that be?  Because it certainly doesn't appear that it will have one.

Any thoughts for a way to get a less-disgusting creature with the same properties?

First, yes, the real part and differentiation commute.  We can see that from the definition of derivative and properties of the real part such as additivity: Re(p+q) = Re(p) + Re(q).

Second, for writing the function down, you might prefer to think of it this way.  The real part of ecx is equal to eax cos(bx), where a and b are the real and imaginary parts, respectively, of c.   So the real function is just an exponential times a cosine.  That's not so disgusting, is it?  :)

Third, sure, the function has a power series and in particular is infinitely differentiable; the complex function is analytic.  We can use the power series for exponentials to see that the the nth term of the complex function is cn xn / n!.  For the power series for the real function, we can take the real part of cn; alternatively, we can multiply the power series for the exponential and cosine from the previous paragraph.

The number c itself does not have a reasonable representation itself, however.   That was what I really meant.

a Fourier transform could have helped to guess that one possible answer was: $ t \to \exp(i \xi t)$ zhere $ \exp(i \xi) \equal{} 1 \plus{} i \xi$

Your equation f(x+1)=f(x)+f'(x) we can understand as a functional equation. Now imagine any differentiable function defined only in interval from 0 to 1. The rest of the function, for example from 1 to 2 is immediately defined and quite easy to construct. Then again from 2 to 3 and so on. So we can construct starting from any value [i]a[/i] (above, we did for 0, but that is the same for any other starting value), taking any differentiable function, the function that satisfies the above condition. Below the value [i]a[/i] (in the above case 0) we simply solve g(x)+g'(x) = f(x+1) and attach g to f from -1 to 0, then solve h(x)+h'(x) = g(x+1) and attach h to f from -2 to -1 and so on. However this backward construction might not unique. On the other hand, if we have a function that is a solution to f(x+1)=f(x)+f'(x) we can easily find its initializer (its values from some a to a+1 ) and use it to define a function in a specific interval from a to +infinity, but not backwards (below a). This construction shows that there is no specific function satisfying f(x+1)=f(x)+f'(x), because it can be created from ANY differentiable and continuous function starting from one interval a, a+1. The only point to analyze better is what is happening at 0 and 1 (i.e. at a and a+1) Interesting point is that by this construction every function must has its initializer in form of interval at infinity some sort of interval -infinity, -infinity+1, which would be a starting block for our procedure, but that is almost impossible to define, or at least not always possible.
Just to illustrate everything, if we ignore for the moment the continuity at 0,1,2,3.. one solution would be this function ... $ \frac{e^{x}}{4}$ from -2 to -1, $ \frac{e^{x}}{2}$ from -1 to 0, $ e^{x}$ from 0 to 1, $ 2e^{x}$ from 1 to 2, $ 4e^{x}$ from 2 to 3, values at ...-2,-1,0,1,2... could be set by an agreement.

Observe that with this procedure we have simplified everything. First if we have function G(x) defined from 0 to 1 we can extend its value to 1 to 2 by G(x+1) = G(x) + G'(x) and so on, on the other hand to get the value from -1 to 0 we are not limited to G(x), which we still did not define there, in any way. We simply ask for the solution of f1(x)+f1'(x) = G(x+1) and of course if we want to specify good conditions we add f1(0)=G(0) and f1'(0)=G'(0) to avoid any problems about continuity. Then for the interval -2, -1 again we are looking for f2(x)+f2'(x) = f1(x+1) and so on. Now combining extension of G(x) from 0 to infinity and all f1(x) f2(x)... we have defined our final solution. Obviously if f1(x)+f1'(x) = G(x+1) does not have unique solution solving f2 f3... will bring the explosion of our solutions set size.

However if we want to have a smooth solution then we represent G(x) as a power series (Laurent's series) where we would have probably at the end that the only possible solution is a constant function. Of course I assume G(x) is analytic.

$ \sum^{ \plus{} \infty}_{n \equal{} 0}{a_{n}z^{n}} \plus{} \sum^{ \plus{} \infty}_{n \equal{} 1}{a_{n}nz^{n \minus{} 1}} \equal{} \sum^{ \plus{} \infty}_{n \equal{} 0}{a_{n}\left(z \plus{} 1\right)^{n}}$ ... (expand (z+1)^n and collect coefficients around z^n)

However, I do not see exactly how to solve tis directly.

It would be interesting to examine what kind of other non-constant functions satisfies the equation (like how many poles and where, though it looks that it can't have a pole of finite order etc.) but the above procedure covers the rest of the story quite nicely.

I think that this story covers the problem in full, so either we have a constant function or a function that has discontinuities as above.

Solution to  y+y' = f(x) is
$ y \equal{} \frac {\int{e^{x}f(x)dx} \plus{} c}{e^{x}}$
constant c could be defined by initial condition

Regarding the Laurent's series we have to solve this set of equations for every k, 0 or above
$ \sum^{ \plus{} \infty}_{n \equal{} k \plus{} 2}{n \choose k}a_{n} \equal{} 0$
knowing that here Laurent's series must be infinite, i.e. we might have some coefficient $ a_{k} \equal{} 0$ equal zero but not all beyond k>m for any m. If there is a solution to this infinite set of equations that would be the analytic solution to the problem. Since this is not something I see how to do we can combine both requests we have and go another way.
$ f(x) \equal{} \frac {\int{e^{x}f(x)dx} \plus{} c}{e^{x}}$
$ \int{e^{x}f(x\plus{}1)dx} \equal{}f(x)e^{x}\plus{}c$
Now present f(x) as a Fourier series in any desirable interval L (or for that matter any reasonable sum representation including Laurent but z is complex there) and get the coefficient values. Not something impossible to do. Observe that if f(x) is a solution than f(x)+t is a solution as well
$ \int{e^{x}(f(x\plus{}1)\plus{}t)dx} \equal{}(f(x)\plus{}t)e^{x}\plus{}c$
$ e^{x}t\plus{}\int{e^{x}(f(x\plus{}1)\plus{}t)dx} \equal{}f(x)e^{x}\plus{}e^{x}t\plus{}c$
$ \int{e^{x}f(x\plus{}1)dx} \equal{}f(x)e^{x}\plus{}c$
so you can remove the zero-th coefficient in Fourier series.
$ f(x)\equal{}\sum^{ \plus{}\infty}_{\minus{}\infty}{a_{n}cos\frac{n\pi x}{L}\plus{}b_{n}sin\frac{n\pi x}{L}}$
Now at the end you get
$ pa_{n}\plus{}qb_{n}\equal{}0$
$ ra_{n}\minus{}sb_{n}\equal{}0$
for some fixed p,q,r,s and that means that all coefficients are zero as told. Of course a fixed interval L is not an obstacle since we can ask for a solution within that interval only.
Now the only question remains to answer is why using Fourier series does not show the above solution with $ e^{x}$. I leave that to you  :) (Hint: Could p,q,r,s be zero?)


If $ P$ is an internal point of the triangle $ ABC$ such that triangles $ PAB, PBC$ and $ PCA$ has the same area, then prove that $ P$ must be the centroid of the triangle $ ABC$. Prove also why $ P$ can't be the incenter, or the orthocenter or the circuncenter of the triangle $ ABC$.

Let $ D$, $ E$ and $ F$ the intersections of $ AP$, $ BP$ and $ CP$ with $ BC$, $ CA$ and $ AB$ respectively.

If $ P$ is the centroid is easy to verify this holds.

If $ (APB)\equal{}(BPC)\equal{}(CPA)\equal{}\frac{(ABC)}{3}$ then $ \frac{(APB)}{(ABC)}\equal{}\frac{(BPC)}{(ABC)}\equal{}\frac{(CPA)}{(ABC)}\equal{}\frac{1}{3}$, so $ \frac{PD}{AD}\equal{}\frac{PE}{BE}\equal{}\frac{PF}{CF}\equal{}\frac{1}{3}$, so $ P$ belongs to the line parallel to $ AB$ wich divides the altitude from $ C$ in $ 1: 2$ (the smallest segment is closer to $ AB$), the same for $ BC$ and $ CA$. This three lines have at most $ 1$ intersection points and as the centroid works it is the unique point.

 :)

jiji all those points coincide but it is still the centroid

 :rotfl:

 :)

[quote="1=2"]For the second part, what if ABC is equilateral?  :wink:[/quote]

Notice that it is a particular case.


Can anyone post the graph of $ f(x,y)\equal{}3sin(3x\minus{}5y)$
Thank you


induction
graph theory
combinatorics proposed
combinatorics

It seems that this week problems of hamilton cycles want to be solved. a friend just told me this one.
I really liked it!

Let $G$ be a graph with every vertex of odd degre. We know $G$ contains a hamilton cycle $C$. Prove $G$ contains another hamilton cycle $C'$ different from $C$.

actually one can prove more(for instance this result appears in Bollobas's "Extremal Graph Theory"):
  Let $W=W(G)$ denote the set of vertices of even degree of a graph, $\mathcal{L}(x_0,W)$ denote the set of hamiltonian paths from a given fixed vertex $x_0$ ending up in a vertex in $W$. Then the set $\mathcal{L}(x_0,W)$ is even(the proof of this is quite short, and uses a nice little trick).

the current problem falls out quite trivially from this. let $C$ be a hamiltonian circuit of $G$ and let $e=\{u,v\}$ be an edge appearing in $C$. Then $W(G\setminus e)=\{u,v\}$ and so the number of hamiltonian paths starting from $u$ and ending in $u$ or $v$ is even.there is one anyways(because of $C$) and so there has to be another,different from $C\setminus e$ which in either case gives another hamiltonian circuit in $G$ other than $C$.
  the proof of the stated result can be looked up in EGT,chapter. III or one can try and prove it oneself so i won't post it's proof here.

that was my same approach!
proving that every edge is contained in an even number of hamilton cycles..

i remembered i've heard this realted question:
prove that  if $G$ is 3-regular and has a hamilton cycle $C$,
then $C$ has an edge e such that $G - e$ is hamiltonian.

yes, the statement i posted is actually a generalization of that.that original statement is due to Smith(of the BEST theorem).

[quote="seshadri"]actually one can prove more(for instance this result appears in Bollobas's "Extremal Graph Theory"):
  Let $W=W(G)$ denote the set of vertices of even degree of a graph, $\mathcal{L}(x_0,W)$ denote the set of hamiltonian paths from a given fixed vertex $x_0$ ending up in a vertex in $W$. Then the set $\mathcal{L}(x_0,W)$ is even(the proof of this is quite short, and uses a nice little trick).
[/quote]

I believe it can be shown by induction:

Let $x_1,\ldots,x_n$ be the neighbours of $x_0$. After we take a step, i.e. we go from $x_0$ to some $x_i$, delete $x_0$ and all its adjacent edges. We then have an even number of hamiltonian paths from $x_i$ to the even vertices in the new graph $G_i$ (all the $G_i$'s are the same, in fact, namely $G-x_0$).

There are some problematic paths, namely those from $x_i$ to $x_j$ for $x_j$'s which are even in $G_i$, but were odd in $G$. If $x_i$ is also even in $G_j$, then these paths are counted twice, and they don't matter in the parity of the number of paths. If, on the other hand, $x_j$ is even in $G_i$ and $x_i$ is odd in $G_j$, then the path from $x_0$ to $x_i$ (which is valid since $x_i$ is even in $G$) is counted as a path from $x_i$ to $x_j$ in $G_i$.

I hope it's clear and correct.


Could someone please show me some applications of the principle of inclusion exclusion, because even though i knnow what it states i dont know how to use it to solve any problems. thanks.

Bob lives at $(0, 0)$ and works at $(6, 6)$.  Each move he takes to walk to work increases either his $x-$ or $y-$ coordinate.  In how many ways can he get to work if $(2, 1)$ and $(2, 4)$ are closed?

Find the number of positive integers less than or equal to 100 that are divisible by atleast one of 3, 5, or 7

[hide]
[integers divisible by 3] + [integers divisible by 5] + [integers divisible by 7] - [integers divisible by 3 and 5] - [integers divisible 3 and 7] - [intgers divisible by 5 and 7] + [integers divisible by 3, 5, and 7]

$\lfloor\frac{100}{3}\rfloor+\lfloor\frac{100}{5}\rfloor+\lfloor\frac{100}{7}\rfloor-\lfloor\frac{100}{15}\rfloor-\lfloor\frac{100}{21}\rfloor-\lfloor\frac{100}{35}\rfloor+\lfloor\frac{100}{105}\rfloor$
$33+20+14-6-4-2+0=\boxed{55}$
[/hide]

yeah these types i do get. But i mean like the more suprising cases. like in the tougher AIME combinatorics problems.

In how many ways can $4$ balls labeled $1-4$ be placed in $4$ buckets labeled $1-4$ if a ball cannot be placed in its corresponding bucket and there is a maximum of $2$ balls per bucket?

ok. so how do u do this one?

I'm so bad at combinatorics....

I mean ther's 70 total ways and then you just need to subtract the cases where a ball is placed in its corresponding bucket, but how would you do that using PIE?

And when i try to do this i get that there is only one way

Tho you probably already knew but PIE states:
N(A[i][union][/i]B)=N(A)+N(B)-N(A[i]([intersection][/i]B)
I have to get to bio test. :(

[quote="Kamil Witek"]so could someone tell me if this solution is correct?
so we have something like this:
_ _ I_ _I_ _I_ _  where I are basically the dividers
now we choose 4 out of the total eight spots, in 70ways. We have to multiply this by 24 to get the total number of ways that the balls could be placed. so there is 1680 ways. now we just need to subtract all the combinations where the requirements are violated. using PIE the number of such combinations is 4(7C3)- 6(6C2)+4(5C1)-1=69. Now we subtract 1680-69= 1611, which is the final answer.[/quote]

1611 is clearly more than the number of ways to place them.  Your first step is wrong; 1_I... is no different than _1I...

So how do you do it?

I suck at combinatorics..........................

[quote="chickendude"][hide]
First, we focus on the rule of the ball not being placed in it's own numbered bucket

Each ball has 3 choices of buckets it can be put into, yielding

$3^{4}$ ways to place the balls

now, we must exclude the cases that break the rule of having a max of 2 per container
There will never be 4 balls in a container (because one of the balls would be the same number as the container)

so we must look at the cases where there are 3 balls in a container

case 1: Container $1$ contains balls $2,3,4$
Ball 1, is in either container $2,3$ or $4$, meaning there are 3 possible scenarios in this case

case 2: Container $2$ contains balls $1,3,4$
similar logic, 3 possible scenarios

cases 3 and 4 also have 3 possible scenarios each

that means there are a total of $12$ scenarios we must exclude from our original $3^{4}$

$3^{4}-12 = 81-12 = \boxed{69}$
[/hide][/quote]

That's the basic idea, however you needn't break it up into cases.  Just note that three balls will be placed in the bucket that has the number of the not included ball.  Thus the not included ball has $\binom{3}{1}$ places it can be put.  Finally, there are $\binom{4}{3}$ ways to pick the $3$ balls that are included.  This means we get $\binom{3}{1}\binom{4}{3}$.

[b]Kamil Witek:[/b] Try the same question with $5$ buckets and $5$ balls, but the same restrictions.


function
floor function
inequalities
logarithms
calculus
integration
articles

The positive function $p(n)$ is defined as the number of ways that the positive integer $n$ can be written as a sum of positive integers. Show that, for all positive integers $n \ge 2$, \[2^{\lfloor \sqrt{n}\rfloor}< p(n) < n^{3 \lfloor\sqrt{n}\rfloor }.\]

The proof for the leftside inequality:
Handle $ n = 2,3,4$ separately. Let now $ n\ge5$.
Let $ m = [\sqrt n]$ and $ V = \{1,2,\ldots,m\}$. For a finite $ X\subset Z$ let $ \displaystyle f(X) = \sum_{x\in X}x$. We prove that for $ n\ge 5$ we have $ e = f(V) + m\le n$. For $ n = 5,6,7,8$ $ m = 2$ and the inequality is trivial. Assume $ n\ge9$. Then $ e = \dfrac{m^2 + m}2 + m\le\dfrac{n + 3\sqrt n}2\le n$. Moreover equality takes place iff $ n = 5$ or $ n = 9$. Thus for any subset $ A\subset V$, $ A = \{a_1,a_2,\ldots,a_k\}$ we can associate the partition of $ n$: $ (a_1,\ldots,a_k,n - f(A))$ with $ n - f(A) > a_i$, for any $ i$ if $ A\neq V$ or maybe $ n - f(A) = m$ if $ A = V$. It is clear that this is an injective map. Since there are $ 2^m$ different subsets of $ V$, we get $ 2^{[\sqrt n]}\le p(n)$.

I'll think for a normal proof of the rightside inequality. For now, here's a strange proof for it:
Handle $ n = 2$ separately.
We use the following strong bound for $ p(n)$ for $ n > 2$:
$ \boxed{p(n) < \dfrac{\pi}{\sqrt {6(n - 1)}}e^{\pi\sqrt {\frac {2n}3}}}$.
Now for $ n\ge3$ we easily have $ \dfrac{\pi}{\sqrt {6(n - 1)}} < 1$, so it is sufficient to prove $ e^{\pi\sqrt {\frac {2n}3}} < n^3{[\sqrt n]}$, or $ e^{\pi\sqrt {\frac23}} < n^3$. Direct calculations show that ${ \pi\sqrt {\dfrac23}} < 3$, and since $ e < 3\le n$, the desired inequality holds.

I'll post tomorrow the proof for the stated bound for $ p(n)$. If anyone does that before me, I'd be glad :). I gotta go now.

As I promised, here's the proof of the following fact:
[i]If[/i] $ p(n)$ [i] is the number of partitions of $ n$ as a sum of several positive integers then [/i]
$ \boxed{p(n) < \dfrac{\pi}{\sqrt {6(n \minus{} 1)}}e^{\pi\sqrt {\frac {2n}3}}}$
[i][b]Proof:[/i][/b]

We'll use the following $ 3$ facts:

$ F1.$  $ \displaystyle\sum_{n \equal{} 1}^{\infty}p(n)x^n \equal{} \dfrac1{(1 \minus{} x)(1 \minus{} x^2)(1 \minus{} x^3)\ldots}$, where $ p(0) \equal{} 1$.
$ F2.$  $ \displaystyle\sum_{i \equal{} 1}^{\infty}\dfrac1{i^2} \equal{} \dfrac{\pi^2}6$.
$ F3.$  $ \ln(1 \minus{} x)^{ \minus{} 1} \equal{} \minus{} \ln(1 \minus{} x) \equal{} \displaystyle\sum_{j \equal{} 1}^{\infty}\dfrac{x^j}j$.

Denote $ P(x) \equal{} \displaystyle\sum_{n \equal{} 1}^{\infty}p(n)x^n \equal{} \dfrac1{(1 \minus{} x)(1 \minus{} x^2)(1 \minus{} x^3)\ldots}$ (by $ F1$) the generating function for the sequence $ p(n)$. Let $ f(t) \equal{} \ln P(t)$. Then
$ f(t) \equal{} \displaystyle\sum_{i \equal{} 1}^{\infty}\ln(1 \minus{} t^i)^{ \minus{} 1} \equal{} \sum_{k \equal{} 1}^{\infty}\left(\sum_{j \equal{} 1}^{\infty}\dfrac{t^{kj}}j\right) \equal{} \sum_{j \equal{} 1}^{\infty}\dfrac1j\left(\sum_{k \equal{} 1}^{\infty}(t^j)^k\right) \equal{} \sum_{j \equal{} 1}^{\infty}\dfrac1j\cdot \dfrac{t^j}{1 \minus{} t^j}$.
Now take $ 0 < t < 1$. From $ \dfrac{1 \minus{} t^j}{1 \minus{} t} \equal{} 1 \plus{} t \plus{} t^2 \plus{} \ldots \plus{} t^{j \minus{} 1} > jt^{j \minus{} 1}$, we have $ 1 \minus{} t^j > j(1 \minus{} t)t^{j \minus{} 1}$, or $ \dfrac{t^j}{1 \minus{} t^j} < \dfrac1j\cdot\dfrac t{1 \minus{} t}$. Then
$ f(t) \equal{} \displaystyle\sum_{j \equal{} 1}^{\infty}\dfrac1j\cdot \dfrac{t^j}{1 \minus{} t^j} < \dfrac t{1 \minus{} t}\sum_{j \equal{} 1}^{\infty}\dfrac1{j^2} \equal{} \dfrac{\pi^2}6\cdot\dfrac t{1 \minus{} t}$. We obtained the following important inequality $ \boxed{f(t) < \dfrac{\pi^2}6\cdot\dfrac t{1 \minus{} t}}$.
Also, using the fact that $ p(n)$ is an increasing sequence $ P(t) \equal{} \displaystyle\sum_{j \equal{} 1}^{\infty}p(j)t^j > \sum_{j \equal{} n}^{\infty}p(j)t^j > \sum_{j \equal{} n}^{\infty}p(n)t^j \equal{} \dfrac{p(n)t^n}{1 \minus{} t}$. Taking logarithm of both sides we get
$ f(t) > \ln p(n) \plus{} n\ln t \minus{} \ln(1 \minus{} t)$, or
$ \ln p(n) < f(t) \minus{} n\ln t \plus{} \ln(1 \minus{} t) < \dfrac{\pi^2}6\cdot\dfrac t{1 \minus{} t} \minus{} n\ln t \plus{} \ln(1 \minus{} t)$.
Further setting $ t \equal{} (1 \plus{} u)^{ \minus{} 1}$ for some $ u > 0$ (remember that $ 0 < t < 1$) we get $ \ln p(n) < \dfrac{\pi^2}6\cdot\dfrac1u \plus{} n\ln(1 \plus{} u) \plus{} \ln\dfrac u{1 \plus{} u}$. It follows that $ \boxed{\ln p(n) < \dfrac16\pi^2u^{ \minus{} 1} \plus{} (n \minus{} 1)u \plus{} \ln u}$. Here we have used the well-known inequality $ \ln(1 \plus{} x) < x$ for $ x > 0$. Setting $ u \equal{} \dfrac{\pi}{\sqrt {6(n \minus{} 1)}}$, we get the desired inequality, as $ \dfrac16\pi^2u^{ \minus{} 1} \plus{} (n \minus{} 1)u \equal{} \pi\sqrt {\dfrac{n \minus{} 1}3} < \pi\sqrt {\dfrac{2n}3}$.

Note that setting different values for $ u$ or using slightly different inequalities along the proof will yield different bounds for $ p(n)$.
________________________
[i][b]Proofs of the facts[/i][/b]
$ F1$: $ \dfrac1{(1 \minus{} x)(1 \minus{} x^2)(1 \minus{} x^3)\ldots} \equal{} (1 \plus{} x \plus{} x^2 \plus{} \ldots \plus{} )(1 \plus{} x^2 \plus{} x^4 \plus{}$ $ \ldots \plus{} )(1 \plus{} x^3 \plus{} x^6 \plus{} \ldots)$ and the conclusion is immediate.
$ F2$: This is well-known.
$ F3$: Consider the relation $ \dfrac1{1 \minus{} x} \equal{} 1 \plus{} x \plus{} x^2 \plus{} x^2 \plus{} \ldots$. Taking integrals of both sides, we have $ \minus{} \ln(1 \minus{} x) \equal{} \dfrac x1 \plus{} \dfrac{x^2}2 \plus{} \dfrac{x^3}3 \plus{} \ldots$, which is $ F3$.
________________________
Hope there are no typos or mistakes...
For references see the following good article on partitions (it's in Bulgarian):
[i]"Разбивания"[/i]([i]Partitions[/i]) by [i]Иван Ланджев[/i] in the book [i]"Олимпийски теми 2006"[/i] ([i]Olympiad Topics 2006[/i]).
The above proof can be found there but with some small mistakes and with quite few explanations.


geometry
trapezoid
inequalities
symmetry
rotation
geometric transformation

Two perpendicular lines divide a square into four parts, three of which have area 1.  Show that the fourth part also has area 1.

Source: 1991 Iberoamerican Mathematical Olympiads.  On the kalva site, John Scholes requests a solution to this problem.  I figured I would help him out by posting the problem here.

I'm not 100% sure and I need help explaining, but my proof in spoiler:

[hide]

Suppose we partition square ABCD with perpendicular lines m going through AB and CD and n going through AD and BC.  We will begin with m and n intersecting at the square's center.  Let the partitions containing points A, B, C, and D be labled w, x, y, and z, respectively.

If we move line m such that it still intersects the same two sides, then we will have w =/= z and x =/= y because the trapezoids lopped off/added are unequal (I wish I could explain this more clearly).  With those inequalities, it is impossible for more than one partition from each inequality to be 1; therefore, three of them can not all be 1 in this scenario.

If we want to counteract this inequality by moving line n so that either w=z or x=y, however, it is necessary to make both trapezoids lopped off/added to be equal.  Doing so implies that both w=z and x=y, which still doesn't work, because having three of the four equal would imply a fourth also equal.

The only remaining case is when m is moved such that it ceases to intersect AB and CD.  Let's say that it moves so far that it intersects BC and CD (this could also be AD and CD, but the concept will be the same).

First assume that line n intersects C.  This implies that x and y are triangles.  We can establish that y < z since the triangle formed by the intersections of m and n, m and CD, and n and AD is necessarily larger than y (this is hard to describe, but it should be very obvious if drawn), and z contains that triangle.  Similarly, it can be shown that x < w.

Now comes the part that I find hard to describe.  Basically, by moving n to intersect DC, x does not increase as much as w, and the same is true for y and z when n is moved to intersect BC.  Hence,  x < w and y < z both still hold even if n is moved.  With those two inequalities, as in the first case, there can not be 3 partitions of equal area.

[/hide]

Even assuming that this is right, could someone give me feedback as to how to write more clearly?  Of course, diagrams would help (I'm not proficient at making them on the computer, though)...

We need to show that having three areas equal to 1 will only work if the point at which the lines intersect is the center of the square, because it's obvious that this is the necessary condition for all 4 areas to be equal.  (Proving that when they intersect at the center, the four parts are equal, is a one-liner by symmetry.)  Anyhow, let's take our two lines, and let's consider lines parallel to them through the center of the square, as shown.

Each of the four original areas a, b, c and d will be transformed as follows:

a -> a + x1 + x2 + x3
b -> b - x1 + x4
c -> c - x2 + x5
d -> d - x4 - x5 - x3

After this transformation, the three areas will be all the same.  Thus, obviously, a and d could not have been equal beforehand, since one increases and the other decreases in area and they end up the same.  Now, we just need to show that the changes in b, c and d or in a, b and c cannot all be the same.  We'll do (WLOG) a, b, and c.  Assume
x1 + x2 + x3 = x4 - x1 = x5 - x2.  We need to show that this leads to a contradiction somehow.
First, we see that it implies x1 + x5 = x2 + x4, or that the areas of the two strips (x1 + x3 + x5) and (x2 + x3 + x4) are equal.

Allright, now this is a little hard to justify, but we know as a result that the two strips are of equal width.  The reason for this is due to the symmetry of having the right angles there: if one strip hits a corner, the other one should, as well.  Or, alternatively, if we make one of the strips wider, it necessarily increases its area (even if part of it gets "chopped off" at one corner).  Increasing the width of the other square will also cause it to get chopped off, as well.  So, anyhow, I believe that this is true, although I admit it was not exactly fully rigorous.  Anyhow, this gives me that x3 is in fact a square.
Okay, gotta go to lunch -- will try to finish up later.

Probability1.01, I didn't understand your argument.  When you say let the partitions be labeled w, x, y, and z, did you mean the areas of the partitions?  When you said w =/= z and x =/= y, did you mean w <> x and z <> y?  I am assuming that A, B, C, and D are the vertices of the square in cyclic order.  My biggest problem was with your next paragraph.  "If we want to counteract this inequality by moving line n so that either w=z or x=y, however, it is necessary to make both trapezoids lopped off/added to be equal."  When you say both trapezoids, which two are you referring to?  I think your argument would be helped with some suitable notation.

Joel, it looks like you are off to a decent start.  I await the finish...

Okay, I've solved this, and it's totally different than what I was working on before:

Look at the diagrams below.  They represent our square, with three equal regions, and the same square showing only one of the two lines involved in each.  Note that if we rotate the second image 90 degrees, the line segment cutting the square will be forced to be parallel to the line segment in the third diagram.  Additionally, they cut the square into the same areas.  Thus, we can determine that they are in fact the same segment.  Or in other words, a 90 degree rotation around the center of the square carries one of our segments on to the other.  Now, let's rotate our original diagram 180 degrees, to divide the square up as shown in the lower diagram.  Each of the small triangles has area (1 - 3x); thus, each of the trapezoids (containing parts of the sides) has area (4x - 1).  Adding up, we see the central region must have area (1 - 4x).  Areas being non-negative, we get as a result that x = 1/4, so all 4 regions are equal in area.

I'm fairly confident that this works no matter what the diagram looks like.  Worst-case, you'd have to make another copy of the same diagram with different things labelled "x" and you should still end up with the same result in the end.  Alternatively, a nice method to turn that last step without relieing on the specifics of the diagram would be nice.

Wow, beautiful proof!  That was a great use of rotations.  As you said, there may be a few other cases for what the original diagram looks like, but I think they all succumb to your method.

Thanks :)

I think you can reduce the other alternative to the case in which the 2x is on the other side of the line, and that gives you what you need even more quickly.


[quote="greentreeroad"]how do you get this..... please be specific[/quote]
For you, greentreeroad!
$ \sum_{cyc}\left(\frac {a^2}{b^3} \minus{} \frac {1}{a}\right) \equal{} \frac {a^2}{b^3} \plus{} \frac {b^2}{a^3} \minus{} \frac {1}{a} \minus{} \frac {1}{b} \plus{} \frac {b^2}{c^3} \minus{} \frac {1}{c} \plus{} \frac {c^2}{a^3} \minus{} \frac {b^2}{a^3} \equal{}$
$ \equal{} \frac {a^5 \minus{} a^3b^2 \minus{} a^2b^3 \plus{} b^5}{a^3b^3} \plus{} \frac {(c^3 \minus{} a^3)(c^2 \minus{} b^2)}{a^3c^3}\geq0,$ which true for $ c \equal{} \max\{a,b,c\}.$
$ \sum_{cyc}\frac {1}{a}\geq\sum_{cyc}\frac {a \plus{} b}{c^2 \plus{} ab}\Leftrightarrow\sum_{cyc}\left(\frac {1}{c} \minus{} \frac {a \plus{} b}{c^2 \plus{} ab}\right)\geq0\Leftrightarrow\sum_{cyc}\frac {(c \minus{} a)(c \minus{} b)}{c(c^2 \plus{} ab)}\geq0.$
But $ \frac {(a \minus{} b)(a \minus{} c)}{a(a^2 \plus{} bc)} \plus{} \frac {(b \minus{} a)(b \minus{} c)}{b(b^2 \plus{} ac)} \equal{} \frac {(a \minus{} b)^2(a \plus{} b)(ac \plus{} bc \minus{} ab)}{(a^3 \plus{} abc)(b^3 \plus{} abc)}\geq0.$

OK, would anyone please give me any help on how to manipulate SOS-Schur well.(also what kind of question will you choose to use this method)
Last time somebody give me a file in which there are lots of problems, but they are  not in English... :blush:

What's the main trick in rewrite an inequality in form A(a-b)^2+B(a-c)(b-c), it still seems inaccessible to me.

[quote="greentreeroad"]
What's the main trick in rewrite an inequality in form A(a-b)^2+B(a-c)(b-c)[/quote]
To get $ (a \minus{} b)^2$ :wink:
For example, in the following equal
$ \sum_{cyc}\left(\frac {a^2}{b^3} \minus{} \frac {1}{a}\right) \equal{} \frac {a^2}{b^3} \plus{} \frac {b^2}{a^3} \minus{} \frac {1}{a} \minus{} \frac {1}{b} \plus{} \frac {b^2}{c^3} \minus{} \frac {1}{c} \plus{} \frac {c^2}{a^3} \minus{} \frac {b^2}{a^3}$
the expression $ \frac {a^2}{b^3} \plus{} \frac {b^2}{a^3} \minus{} \frac {1}{a} \minus{} \frac {1}{b}$ gives $ (a \minus{} b)^2.$
In the equal $ a^2 \plus{} b^2 \plus{} c^2 \minus{} ab \minus{} ac \minus{} bc \equal{} a^2 \minus{} 2ab \plus{} b^2 \plus{} c^2 \minus{} ac \minus{} bc \plus{} ab \equal{} (a \minus{} b)^2 \plus{} (c \minus{} a)(c \minus{} b)$
we get $ (a \minus{} b)^2$ and it ends our problems.  :wink:
Else example:
$ a^3b^3 \plus{} a^3c^3 \plus{} b^3c^3 \minus{} a^3b^2c \minus{} b^3c^2a \minus{} c^3a^2b \equal{}$
$ \equal{} a^3c^3 \plus{} b^3c^3 \minus{} c^3b^2a \minus{} c^3a^2b \plus{} a^3b^3 \minus{} b^3c^2a \plus{} c^3b^2a \minus{} a^3b^2c \equal{}$
$ \equal{} c^3(a^3 \minus{} a^2b \minus{} ab^2 \plus{} b^3) \plus{} b^3a(a^2 \minus{} c^2) \plus{} ab^2c(c^2 \minus{} a^2) \equal{}$
$ \equal{} c^3(a \plus{} b)(a \minus{} b)^2 \plus{} ab^2(a \plus{} c)(c \minus{} a)(c \minus{} b).$  :)

[quote="greentreeroad"]Thanks

is that in major inequality(if SOS-Schur works), when we get (a-b)^2, then (a-c)(b-c) will come out itself? :?:[/quote]
No, not always. If it does not turn out then try another way to get $ M(a\minus{}b)^2.$ :wink:


AMC
AIME
USA(J)MO
USAMO
probability
geometry
AIME II

I've heard that the AIME II is MUCH harder than the AIME I.  Our school took the AIME I two years ago, and had 4 USAMO qualifiers.  Because of spring break, we took the AIME II last years with all of the qualifiers returning, and NOBODY made USAMO.  Is thise supposedly true?  :?

It's not true.

Last year the average score on the AIME I was 2.25 and on the AIME II it was 1.96.  Also, the other day I checked the percentage of students getting at least a 5.  It was the same on both exams, about 11%.

In 2003 the average scores were AIME I: 3.06, AIME II: 3.05

The exams are intended to be of roughly equal difficulty.

The average could be affected by who takes the tests, mbe more good ppl take the AIME I?

Okay on
2002 AIMEI I scored an 8 in practice, on 2002 AIMEII I scored a 10 in practice. However on both 2002 AIME's I solved 11 questions, it's just that I made 2 more careless mistake in 2002 AIMEI

2004 AIMEI I scored an 8 on practice(but that was 2 month ago, I could've improved :) ), 2004 AIMEII I scored a 9. On AIMEI I solved 10 questions, on AIMEII I solved 11 questions, on both AIME I made 2 careless mistakes.

Hmm so I think both AIME's are still about the same level of difficulty. Although my scores on AIMEII had been higher...

There shouldn't be any systematic difference in level of difficulty between the two versions of the AIME in each year. There will be some unpredictable and uncertain difference between the group of test-takers each year, but the scores come out pretty similarly on each test year by year.

depends....overall it's same level..but it could be different depends on the person and subject...like i can do most of the algebra/trig,while i had to struggle with probability or counting.....thus a probability based Aime could easily destroy me.....

do the two aimes come out differently, for example, in types of problems?
because if AIME I is geometry-oriented, but AIME II is probability/algebra oriented, i would rather take AIME II.

and do the difference in number of people taking AIME I/AIME II take into effect in USAMO selection?

I personally thought that last year's AIME II was easier than the AIME I of the same year, based on their Math Jam.


Each bounce of a ball goes $ \frac{3}{4}$ as high as the previous bounce.
The second bounce was 24 inches high. What was the height,
in inches, of the first bounce?

If the second bounce was 24, and each bounce is 3/4 as high as the previous, that means 24 is 3/4 of the first bounce, which we are trying to find. Thus our answer is simply $ 24 \div \frac{3}{4} \equal{} \boxed{32}$.


vector
invariant
linear algebra
linear algebra unsolved

Let A,B be n by n matrices satisfying $A^2=A,B^2=B$show that AB=BA iff$range(AB)=range(BA)$ and $range(A^TB^T)=range(B^TA^T)$

i know that u know rank so i can define the range with it:rank is the dimension of the range of specific matrice.

I didn't know what $\hbox{range}(A)$ meant either. I googled it, and the only deifnition I found (in quite a few places), is: the set of vectors $y$ s.t. there is a vector $x$ s.t. $Ax=y$, or, in other words, the set of all linear combinations of the columns of the matrix. Is this what you meant, sam-n? I still can't make anything of your explanation, since all you say is that the dimension of the $\hbox{range}$ is the rank of $A$, but that does not say what the $\hbox{range}$ is.

Boy, was I confused back then or what! :)

Since for every real linear transformation $T$ we have $(\mbox{Im}\ T^t)^{\perp}=\ker T$ (I assume $A,B$ are real, right? :?), the second condition translates to $\ker AB=\ker BA$ (by applying the above to $T=AB$ and $T=BA$), while the first condition is $\mbox{Im}\ AB=\mbox{Im}\ BA$. These two imply that both $\mbox{Im}\ B$ and $\ker B$ are invariant subspaces of $A$.

Now, if $x\in \ker B$, then $ABx=0=BAx$, and if $x\in\mbox{Im}\ B$, then $Bx=x$, so $BAx=Ax=ABx$, so $AB$ and $BA$ agree on $\ker B$ and $\mbox{Im}\ B$. Since the entire space is the direct sum of these two, we get $AB=BA$, as desired.


Find $ 1\plus{}\frac{1}{1\plus{}\frac{1}{1\plus{}\frac{1}{1\plus{}...}}}$ in simplest radical form

[hide]Let $ x\equal{}1\plus{}\cfrac{1}{1\plus{}\cfrac{1}{1\plus{}\cfrac{1}{1\plus{}\hdots}}}$
$ x\equal{}1\plus{}\frac{1}{x}$
$ x^2\equal{}x\plus{}1$
$ x^2\minus{}x\minus{}1\equal{}0$

$ x\equal{}\frac{1\plus{}\sqrt{5}}{2}$ since we want the positive value.[/hide]


number theory
prime numbers
number theory unsolved

Let A be a fnite subset of prime numbers and let a be a positive integer.
Show that the number of positive integers m for which all the prime divisors of a^m-1 are in A is finite.

Bomb

I remember something like this. I believe you can find it here in the "Number Theory" section.


find all $x;y$ satisfies $x^4+x=3y^2$ and $x;y$ are positive integer

it doesn't hard to prove that the problem doesn't have the solution when x,y is positive integer. :D  :D  :D


Hello,

Find all positive integer solutions for following equation.

$ x^2\plus{}x\equal{}y^4 \plus{} y^3 \plus{} y^2 \plus{} y$

An inelegant solution...
[hide]
x(x+1)=y(y^3+y^2+y+1)
x(x+1)=y(y^2+1)(y+1)

Now, just consider all possibilities:
x = 1

x = y

x = y+1

x =  y^2+1

x = y(y^2+1)

x = y(y+1)

x = (y^2+1)(y+1)

x = y(y^2+1)(y+1)

With each of these "x = ..." equations, we know x+1 = y(y+1)(y^2+1)/x. So, we have two equations and two unknowns; if we solve all the equations, then we will have all solutions...
I am sure there is a better solution, but sadly I know very little number theory myself...
[/hide]

[hide="said better solution"]Multiply the equation by 4 and add 1.  The left side is $ 4x^2\plus{}4x\plus{}1\equal{}(2x\plus{}1)^2$ is a square, so the right side, $ 4y^4\plus{}4y^3\plus{}4y^2\plus{}4y\plus{}1$ must be also.

Note that
$ (2y^2\plus{}y)^2\plus{}(3y\plus{}1)(y\plus{}1)\equal{}(2y^2\plus{}y)^2\plus{}3y^2\plus{}4y\plus{}1\equal{}4y^4\plus{}4y^3\plus{}4y^2\plus{}4y\plus{}1$
$ \equal{}(2y^2\plus{}y\plus{}1)^2\minus{}y^2\plus{}2y\equal{}(2y^2\plus{}y\plus{}1)^2\minus{}(y\minus{}2)y$.

By the first equality, if $ y$ is a positive integer, then $ 4y^4\plus{}4y^3\plus{}4y^2\plus{}4y\plus{}1>(2y^2\plus{}y)^2$, because $ (3y\plus{}1)(y\plus{}1)$ is always going to be greater than 0.

By the second equality, if $ y$ is a positive integer greater than 2, then $ 4y^4\plus{}4y^3\plus{}4y^2\plus{}4y\plus{}1<(2y^2\plus{}y\plus{}1)^2$ because $ (y\minus{}2)y>0$.  So the only possible case is if $ y\equal{}1$ or $ y\equal{}2$.  But if $ y\equal{}1$, then what needs to be a square is in fact 17.  But when $ y\equal{}2$, we need $ 4y^4\plus{}4y^3\plus{}4y^2\plus{}4y\plus{}1$ to be a square, and it is, 121.  This is $ 11^2\equal{}(2x\plus{}1)^2$ so $ x\equal{}5$.

Thus the only solution in positive integers is $ (x, y)\equal{}(5, 2)$.[/hide]


What is the age limit for IMO contestants?

20 or 19?

20 if i remember well? thought the rules say "younger than 21" so that's at maximum 20

isn't that somewhere on their site http://www.imo2004.gr ?

it is there: "Contestants must not have formally enrolled at a university or any other equivalent post-secondary institution, and they must have been born on or after July 14, 1984" for 2004. so you cannot be 20 when you reach there.


limit
integration
logarithms
real analysis
real analysis unsolved

If $f\in C([0,1])$ it follows easily that $\displaystyle \lim_{y\to\infty}\int_0^1 x^y f(x) dx=0$. The problem is to find \[ \displaystyle \lim_{n\to\infty}n\int_0^1 x^n f(x)dx \].
I theoretically have a solution [hide]By using L'Hopital Rule we have that
$\displaystyle\lim_{y\to\infty}y\int_0^1 x^y f(x) dx=\lim_{y\to\infty}\frac{\int_0^1 x^y f(x) dx}{\frac{1}{y}}= \lim_{y\to\infty}\frac{\int_0^y\int_0^1 x^z f(x) dx dz}{\ln y}=\lim_{y\to\infty}\frac{\int_0^1 f(x)\int_0^y x^z dz dx}{\ln y}=$$\lim_{y\to\infty}\frac{\int_0^1 f(x)\cdot\frac{x^y-1}{\ln x} dx}{\ln y} (*)$, and since $\displaystyle \frac{x^y-1}{\ln x}\leq x^{y+1}$ for $y\geq y_0$ ($y_0$ big enough, $x\in(0,1)$) and also $\displaystyle\lim_{x\to {0;1}} \frac{x^y-1}{\ln x}\leq \lim_{x\to{0;1}} x^{y+1}$ it follows $\displaystyle\left|\int_0^1 f(x)\cdot\frac{x^y-1}{\ln x} dx\right|\leq\left|\int_0^1 f(x) x^{y+1} dx\right|$ so by the previosly mentioned we get
$\displaystyle 0\leq\lim_{y\to\infty} \left|\int_0^1 f(x)\cdot\frac{x^y-1}{\ln x}dx\right|\leq\lim_{y\to\infty} \left|\int_0^1 f(x) x^{y+1}dx\right|=0$, which in $(*)$ leads to
$\displaystyle \lim_{y\to\infty}y\int_0^1 x^y f(x) dx= \frac{0}{\infty}=0$, hence $\displaystyle \lim_{n\to\infty}n\int_0^1 x^n f(x) dx=\lim_{y\to\infty}y\int_0^1 x^y f(x) dx=0$.[/hide] but something is wrong about it since for $f\equiv 1$ the limit is infinity. I believe that correcting my strange rationing might be difficult but I would appreciate any new way of approaching the problem.

The limit you're looking for is : $f(1)$. :)

Anyway, I think this problem has already been posted (at least twice) and solved. (by grobber, Moubinool, and others)

If somebody could point me to were the problem has been discussed I would be gratefull. :?

Sure :
http://www.mathlinks.ro/Forum/viewtopic.php?t=68241
and
http://www.mathlinks.ro/Forum/viewtopic.php?t=70062 .

:)


Hi! I was programming some exercises in C. They consist of reading a text file with the names and the qualifications of some students, and printing them on the screen, and I although I'm suggested to use fgets and sscanf in order to get those data from the file, I consider that using fscanf would be more useful. Can you tell me the differences between the use of sscanf,fgets and fscanf, and why would be sscanf/fgets better than fscanf please?

The problem with fscanf is that you can't easily detect the end of the line. So for example if one line of your text file contains information about one student, you won't be able to tell where the first student ends and the next one starts. I think it [i]is possible[/i] to do [i]somehow[/i] but I can never remember how so I usually just go for fgets. Or use C++ streams.

In terms of performance, both methods should be equally fast.

Streams are slow. I wouldn't recommend you to use streams. fscanf and scanf and sscanf are slower than gets, fgets, getc etc. But fgets reads until either it has read a specific number of characters or has encountered EOF or '\n'. I think it is not necessary for fscanf to look for the EOF since you can do this:
[code]
while(!feof(fin)){
     fscanf(fin,"%s",&student[i]);
}
[/code]
My advice is that if you read from a file use fscanf and rarely fgets. In the USACO grader you won't have any problem regarding time. If you read from stdin use getc, gets, getchar etc. You may have problems in UVa, timus etc if you use scanf.


calculus
integration
logarithms
function
geometry
geometric transformation
reflection

i hope i have not asked this one before...  :maybe:

$ \int_0^1\;\;\dfrac{x^2\cdot\ln x}{(x^2\minus{}1)\cdot(x^4\plus{}1)}\;\;\textbf dx\;\;\equal{}\;\;\boxed{\dfrac{\pi^2}{16}\left(1\minus{}\frac{1}{\sqrt 2}\right)}$

$ P \equal{} \int_0^1 \frac {x^2 \log (x)}{\left(x^2 \minus{} 1\right) \left(x^4 \plus{} 1\right)} \, dx$

My solution for this problem is not beautiful. Sorry.

$ x \equal{} e^{ \minus{} \sqrt {y}}$ $ \Rightarrow$ $ P \equal{} \minus{} \int_0^{\infty } \frac {e^{ \minus{} 3 \sqrt {y}}}{2 \left(1 \plus{} e^{ \minus{} 4 \sqrt {y}}\right) \left( \minus{} 1 \plus{} e^{ \minus{} 2 \sqrt {y}}\right)} \, dy$

Using the simple fact that $ \sum _{i \equal{} 0}^{\infty } x^{4 i \plus{} 1} \plus{} \sum _{i \equal{} 0}^{\infty } x^{4 i} \equal{} \minus{} \frac {1}{\left(x^2 \plus{} 1\right) (x \minus{} 1)}$

we can get $ P \equal{} \int_0^{\infty } \left(\sum _{i \equal{} 0}^{\infty } \frac {1}{2} e^{ \minus{} (8 i \plus{} 3) \sqrt {y}} \plus{} \sum _{i \equal{} 0}^{\infty } \frac {1}{2} e^{ \minus{} (8 i \plus{} 5) \sqrt {y}}\right) \, dy$

chaging the order $ P \equal{} \frac {1}{2} \left(\sum _{i \equal{} 0}^{\infty } \int_0^{\infty } e^{ \minus{} (8 i \plus{} 3) \sqrt {y}} \, dy \plus{} \sum _{i \equal{} 0}^{\infty } \int_0^{\infty } e^{ \minus{} (8 i \plus{} 5) \sqrt {y}} \, dy\right)$

and a simple integral $ \kappa > 0\Rightarrow \int_0^{\infty } e^{ \minus{} \kappa \sqrt {y}} \, dy \equal{} \frac {2}{\kappa ^2}$

$ P \equal{} \frac {1}{2} \left(\sum _{i \equal{} 0}^{\infty } \frac {2}{(8 i \plus{} 3)^2} \plus{} \sum _{i \equal{} 0}^{\infty } \frac {2}{(8 i \plus{} 5)^2}\right)$

by the definition of polygamma fuction
http://en.wikipedia.org/wiki/Polygamma_function

$ \sum _{i \equal{} 0}^{\infty } \frac {1}{(i \alpha \plus{} \beta )^2} \equal{} \frac {\psi ^{(1)}\left(\frac {\beta }{\alpha }\right)}{\alpha ^2}$

$ P \equal{} \frac {1}{64} \left(\psi ^{(1)}\left(\frac {3}{8}\right) \plus{} \psi ^{(1)}\left(\frac {5}{8}\right)\right)$

Using the reflection formula

$ \psi ^{(n)}(1 \minus{} z) \plus{} ( \minus{} 1)^{n \plus{} 1} \psi ^{(n)}(z) \equal{} ( \minus{} 1)^n \pi \frac {d^n\cot (\pi z)}{dz^n}$

And simplifying, and we are donne.


Let $ 0<a \leq b \leq c \leq d$ so that $ a\plus{}b\plus{}c\plus{}d \geq 1$. Prove $ a^2\plus{}3b^2\plus{}5c^2\plus{}7d^2 \geq 1$.

[hide="solution"]
We have to prove that:
$ a^2\plus{}3b^3\plus{}5c^2\plus{}7d^2 \ge (a\plus{}b\plus{}c\plus{}d)^2 \Longleftrightarrow a^2\plus{}3b^3\plus{}5c^2\plus{}7d^2\ge a^2\plus{}b^2\plus{}c^2\plus{}d^2\plus{}2ab\plus{}2ac\plus{}2ad\plus{}2bc\plus{}2bd\plus{}2cd \Longleftrightarrow 2b^2\plus{}4c^2\plus{}6d^2 \ge 2ab\plus{}2ac\plus{}2ad\plus{}2bc\plus{}2bd\plus{}2cd$
But $ b^2\plus{}d^2\ge 2bd,b^2\plus{}c^2\ge 2bc,d^2\plus{}c^2\ge 2dc$
So we only have to prove that:
$ 2c^2\plus{}4d^2\ge 2(ab\plus{}ac\plus{}ad)$, which follows easily from the given condition[/hide]

[hide="A shorter solution"]
Since $ 4d^2 \geq 3a^2 \plus{} b^2$, we have: $ LHS\geq 4(a^2 \plus{} b^2 \plus{} c^2 \plus{} d^2)$ $ (1)$.
Applying Cauchy-Schwartz's inequality, we get:
$ 4(a^2 \plus{} b^2 \plus{} c^2 \plus{} d^2)\geq (a \plus{} b \plus{} c \plus{} d)^2 \equal{} 1$ $ (2)$
From $ (1)$ and $ (2)$, we're done![/hide]

Edit: Oopps.. I mistyped the coefficient of $ d^2$. It should be $ 4$, instead of $ 7$.

[quote="ghjk"][hide="A shorter solution"]
Since $ 7d^2 \geq 3a^2 \plus{} b^2$, we have: $ LHS\geq 4(a^2 \plus{} b^2 \plus{} c^2 \plus{} d^2)$ $ (1)$.
Applying Cauchy-Schwartz's inequality, we get:
$ 4(a^2 \plus{} b^2 \plus{} c^2 \plus{} d^2)\geq (a \plus{} b \plus{} c \plus{} d)^2 \equal{} 1$ $ (2)$
From $ (1)$ and $ (2)$, we're done![/hide][/quote]

Sorry, but could you clarify your first line. How does $ 7d^2 \geq 3a^2 \plus{} b^2$ and the succeeding result?
Thanks.

What am I doing wrong?

$ (a^2\plus{}3b^2\plus{}5c^2\plus{}7d^2)(1\plus{}\frac13 \plus{}\frac15\plus{}\frac17)\ge (a\plus{}b\plus{}c\plus{}d)^2 \ge 1$

$ \Leftrightarrow a^2\plus{}3b^2\plus{}5c^2\plus{}7d^2 \ge \frac{105}{176}$

[quote="dgreenb801"]You've done nothing wrong, but that bound you came up with can be made tighter by another method different from Cauchy.[/quote]

Oh, thanks.

[hide="A different method"]

If your values are $ \frac {1}{4}$ each then the answer is $ 1$. If your values are not $ \frac {1}{4}$ each then clearly you took some from the left letters and gave them to the right. For example:$ 0 < .1 \leq .2 \leq .35 \leq .35$

 $ .1$ was taken from $ A$ and given to $ D$, then $ .05$ was given to $ C$, then $ .05$ was taken from $ B$ and given to $ C$. So, it suffices to show that any transfer from a letter to one farther right will increase the sum.

The squares are multiplied by odd numbers, so let the left number be equal to $ 2E \plus{} 1$ and the right $ 2F \plus{} 1$. By definition $ 0 < E < F$

If both values are $ \frac {1}{4}$ then the sum is

$ (2E \plus{} 1)(\frac {1}{4})^2 \plus{} (2F \plus{} 1)(\frac {1}{4})^2$

which simplifies to
$ \frac {E \plus{} F \plus{} 1}{8}$

If the values are not $ \frac {1}{4}$ then one is $ \frac {1}{4} \minus{} X$ and the other is $ \frac {1}{4} \plus{} X$

Putting those values into the equation above gives

$ (2E \plus{} 1)(\frac {1}{4} \minus{} X)^2 \plus{} (2F \plus{} 1)(\frac {1}{4} \plus{} X)^2$

Which simplifies to

$ \frac {E \plus{} F \plus{} 1}{8} \minus{} EX \plus{} 2EX^2 \plus{} 2X^2 \plus{} FX \plus{} 2FX^2$

We wish to show that $ \minus{} EX \plus{} 2EX^2 \plus{} 2X^2 \plus{} FX \plus{} 2FX^2 \geq 0$

Because all the variables are positive, we can remove terms with positive signs.

$ FX \minus{} EX \geq 0$

$ F \minus{} E \geq 0$

$ F \geq E$

Which was established before. So, any change in values from $ \frac {1}{4}$ increases the value and therefore, $ a^2 \plus{} 3b^2 \plus{} 5c^2 \plus{} 7d^2 \geq 1$.[/hide]


During summer time,does the amplitude and time period of a simple pendulum increase?

not much of an advanced problem i guess :roll:

Yes, obvously.
 the length of the metal or whatever increases,
 and the time period of a simple pendulum is given by

 $T = 2 \pi \sqrt{\frac{L}{g}}$

 which increases with $L$


integration
logarithms
calculus
function
LaTeX
calculus computations

$ \int_0^1 \frac{x^2}{x^2 \plus{}1}dx$

a. $ \frac {4\minus{}\pi}{4}$
b. $ \ln {2}$
c. $ 0$
d. $ \frac {\ln {2}}{2}$
e. $ \frac {4\plus{}\pi}{4}$

[hide]I think it's c. but I'm not positive.[/hide]

The indefinite integral of that function is $ x \minus{} \arctan x$

So  $ (1 \minus{} \arctan 1) \minus{} (0 \minus{} \arctan 0) \equal{} 1 \minus{} 0.785398163 \equal{} \frac {4 \minus{} \pi}{4} \equal{} \boxed{a}$.

sneezywalrus I think it's a!
Write $ x^2/(x^2\plus{}1)\equal{}1\minus{}1/(x^2\plus{}1)$
So Integral[x^2/(x^2+1)]=Integral[1-1/(x^2+1)]=Integral[1]-Integral[1/(x^2+1)]=x-ArcTan[x]+C where C is a constant
Now the definite Integral equals 1-ArcTan[1]-(0-ArcTan[0])=1-π/4=(4-π)/4

[quote="sneezywalrus"]I think it's c. but I'm not positive.[/quote]
Was the pun intended?  :)

[quote="salonikios"]sneezywalrus I think it's a!
Write $ x^2/(x^2 \plus{} 1) \equal{} 1 \minus{} 1/(x^2 \plus{} 1)$
So Integral[x^2/(x^2+1)]=Integral[1-1/(x^2+1)]=Integral[1]-Integral[1/(x^2+1)]=x-ArcTan[x]+C where C is a constant
Now the definite Integral equals 1-ArcTan[1]-(0-ArcTan[0])=1-π/4=(4-π)/4[/quote]

thanks very much.

[quote="JBL"]In fact, (c) is the answer choice that's most obviously wrong: you're integrating a positive function (well, except at one endpoint, but close enough), so the result better be positive.  We can similarly rule out (b) and (e) (they're both larger than 1/2, while our function is at most 1/2 on an interval of length 1).  One could use slightly more sophisticated estimates to eliminate (d), as well (it's bigger than 1/4), so this is a pretty good example of a problem one can solve without really knowing anything about how to calculate integrals.  On the other hand, knowing how to calculate some integrals is a useful skill, especially for people in calculus classes.

salonikios, please learn about [[LaTeX]].  (On the forum rather than the wiki, http://www.artofproblemsolving.com/Forum/viewtopic.php?t=123690 is a good place to start.)[/quote]

Thank you for telling me the answer, but as far as insulting me (as subtly as you tried to) was uncalled for. I am, obviously, aware that the answer I posted was incorrect, that is why I asked the question. People come to this forum to answer people's questions, but more importantly to help....not insult. Please understand that.

That message would have been much more appropriate as a PM, which is how I've responded.