Divisibility
number theory
Diophantine equation
Perfect Square
Vieta Jumping
IMO
IMO 1988

Let $ a$ and $ b$ be two positive integers such that $ a \cdot b \plus{} 1$ divides $ a^{2} \plus{} b^{2}$. Show that $ \frac {a^{2} \plus{} b^{2}}{a \cdot b \plus{} 1}$ is a perfect square.

The solution is given in Arthur Engel's [i]Problem-Solving Strategies[/i] in Chapter 6, problem E15 if you have a copy.  The solution does not look very simple; I had to read it a couple times to understand it.

For a fixed $k$, we denote $a_{0},b_{0}(a_{0}\ngeq b_{0})$ is a solution of this equation with $b_{0}$ smallest.

Then $b_{0}$ is one root of this equation $b^{2}-ka_{0}b+a_{0}^{2}+k=0$

Then this equation has another root $b_{1}$ and $b_{1}=\frac{a_{0}^{2}+k}{b_{0}}, b_{1}=ka_{0}-b_{0}$, such that $b_{1}$ is a positive integer.

Because $b_{0}$ is smallest, $b_{1}\geq b_{0}$, thus

$a_{0}^{2}+k\geq b_{0}^{2}=ka_{0}b_{0}+k-a_{0}^{2}$ or $2a_{0}\geq kb_{0}$
$ka_{0}-b_{0}\geq b_{0}$ or $ka_{0}\geq 2b_{0}$

So $a_{0}=b_{0}$, then $k=\frac{2x^{2}}{x^{2}+1}$, so $k=1$

[quote="libra_gold"]
Then $b_{0}$ is one root of this equation $b^{2}-ka_{0}b+a_{0}^{2}+k=0$
[/quote]

Shouldn't it be $b^{2}-ka_{0}b+a_{0}^{2}-k=0$ instead?

$k$ is fixed in his considerations so $a_{0}=b_{0}=1$ is a minimal solution only for $k=1$.

infact its possible to find all sol a,b where a*a+b*b/ab+1=k*k :D

Engel hyped this problem up a lot in his book making it sound horribly difficult. However, by today's standards I can't imagine this problem being anything higher than #2 on the IMO. Just look at problems like 2003 #2, or 2002 #3.

[quote="Rust"]$x^{4}+1=0(mod \ p).$ Therefore $a=x_{p}^{3}(mod \ p^{k}),b=x_{p}(mod \ p^{k}$ or $a=x_{p}(mod \ p^{k}),b=x_{p}^{3}(mod \ p^{k})$.
[/quote]

Sorry, but i didn't understand that part.How did you get that ?

I was also going to post it to the forum, but the solution could be easily FOUND!

http://www.mathpages.com/home/kmath334.htm

Very tricky indeed!

Sorry about reviving this old thread, but something's been bugging me.

In [i]Mathematical Olympiad Challenges[/i], Titu Andreescu gives a pretty short and readily comprehensible proof that the pair $ (\alpha,\beta)$ with $ \alpha \plus{} \beta$ minimal produces a perfect square in $ \frac{a^2 \plus{} b^2}{1 \plus{} ab}$. However, I do not see how this shows that all possible $ (a,b)$ with $ \frac{a^2 \plus{} b^2}{1 \plus{} ab} \in \mathbb Z$ produce perfect squares.

I don't have the book, but the answer is:

For *fixed k* with a+b minimal, we get a perfect square, so it works for all k.

Same concept of descent, but maybe a little cleaner.

Since $a^4+1 = (a^2)(a^2+b^2)-(ab-1)(ab+1)$, and $b^4+1=(a^4+1)b^4-(a^4b^4-1)$, we have that $ab+1 \mid  a^2+b^2$ implies that $ab+1 \mid  a^4+1$ which itself implies that $ab+1 \mid  b^4+1$.

 So assume that $a \ge b$.  Then if $ab+1 \mid  a^4+1$, then we have $b^4+1=(ab+1)(bc+1)$, for integral $c$.  Clearly $c < b$, and $bc+1 \mid  c^4+1$.  This means that there is some $d<c$ such that $cd +1 \mid d^4 +1$.  We can continue to generate smaller and smaller pairs until we reach a zero.

Working backwards, we can guess that the solutions are of the form $a_0=0, a_1=k, a_{n+1}=k^2a_n-a_{n-1}$, and indeed it straightforward to verify that this recursion generates the correct terms in the sequence given $a_0,a_1$, and that $k^2=(a_n^2+a_{n+1}^2)/(1+a_na_{n+1})$.

I really like this problem, because if they had the initial condition less restrictive and thus "harder", i.e. $ab+1 \mid  a^4+1$ instead of $ab+1 \mid  a^2+b^2$, my guess is that a lot more contestants would have solved it correctly.

[hide=another vieta jumping sol, YUH]
First, suppose that $a=b$. This yields the solution $(a,b)=1$ (from standard methods) so $k=1$, which is clearly a perfect square. WLOG, assume $a>b$ (since the expression is symmetric).
Suppose $b=1$. This gives $\frac{a^2+1}{a+1}$, which is only a positive integer when $a=1$, which contradicts $a>b$. Thus, $a>b\geq 2$.
For the sake of contradiction, suppose there do exist positive integer solutions to $\frac{a^2+b^2}{ab+1}=k$ such that $k$ is not a perfect square, and among those, suppose the pair $(a_1,b_1)$ has the smallest sum.
Consider the quadratic $$a^2-(kb_1)a+b_1^2-k=0$$ which comes from rearranging the initial expression. Clearly $a=a_1$ is a solution, and this implies there is another real solution: let this be $a_2$. From Vieta's formulas, we have the relations $$a_1+a_2=kb_1$$ $$a_1a_2=b_1^2-k$$ From the first relation, $a_2$ must be an integer. Suppose that $a_2$ is negative. Returning to the original expression, the numerator $a_2^+b_1^2$ is always non-negative. As for the denominator, we have $b_1\geq 2$ and $a_2\leq -1$, so $a_2b_1\leq -2$, which means the denominator is negative, which leads to a contradiction of the fact that $k$ is positive. Thus, $a_2$ is non negative.
Now suppose that $a_2=0$. We then have $b_1^2=k$, which is a contradiction of the fact that $k$ is not a perfect square. Thus, $a_2$ is a positive integer.
I claim that $a_1>a_2$. Indeed it suffices to show , $$a_1>a_2 \iff a_1>\frac{b_1^2-k}{a_1}\iff a_1^2>b_1^2-k$$ which is immediately true from $a_1>b_1$. This contradictions the minimality of $a_1+b_1$, so there are no positive integer solutions such that $k$ is not a perfect square, so we are done.

[hide=solution set, for completeness]
Finding the solution set is easy. Going back to our quadratic, we see that we can only have a valid solution for $a_1$ if $a_2$ is not positive. If it is negative, it's easy to see the contradiction (use the same argument), so $a_2=0$. This means that $a_1=kb_1$ and $b_1^2=k$, so the solution $(b_1^3,b_1)$ works (and is easy to verify). From symmetry, $(a_1,a_1^3)$ works as well.
[/hide]
[/hide]

Hi guys I found in a NT book a stronger version of this problem. It says that the result is not just a square of an integer but GCD(a,b)^2. Can anyone give a proof??. Thanks in advance.

I tried to solve this problem by using elementary algebra.
However, by assumption X = a^2 if b=0, the solve for x is a^2 = -2

https://documentcloud.adobe.com/link/track?uri=urn:aaid:scds:US:ed532489-a454-48eb-b48e-128f876d3a24

https://twitter.com/globeconomia/status/1453053910353072133?s=20

Well it was a hard problem in the late 80s. But now since vieta jumping is well known, it ain't that hard.

P. S. Although Engel's solution is large and is hard to comprehend, the case with Titu's one is different.

[hide=Here's a comprehensible and easy solution.]
Fix some value $k$ that is a non-square positive integer. Assume there exist positive integers $(a, b)$ for which $k = \frac{a^2+b^2}{ab+1}$.

Let $(A, B)$ be positive integers for which $k = \frac{A^2 + B^2}{AB + 1}$ and such that $A + B$ is minimized, and without loss of generality assume $A \geq B$.

Fixing $B$, replace $A$ with the variable $x$ to yield $x^2-(kB)x + (B^2-k) = 0$. We know that one root of this equation is $x_1 = A$. By standard properties of quadratic equations, we know that the other root satisfies $x_2 = kB-A$ and $x_2 = B^2-\frac{k}{A}$.

The first expression for $x_2$ shows that $x_2$ is an integer, while the second expression implies that $x_2 \neq 0$ since $k$ is not a perfect square. From $\frac{x_2^2 + B^2}{x_2B + 1} = k > 0$ it further follows that $x_2$ is a positive integer. Finally, $A \geq B$ implies that $x_2 = \frac{B^2-k}{A} < A$ and thus $x_2 + B < A + B$, which contradicts the minimality of $A + B$.

Thus our initial assumption was false and the claim follows.
[i]Q.E.D[/i]
[/hide]

This problem feels somewhat unsatisfying; compared to [url=https://artofproblemsolving.com/community/c6h26232p164231]USA TST 2002/6[/url], it's only patting the surface of quadratic infinite descents and not really diving in more logically.

Suppose the assertion fails for some $(a, b)$ and pick $a+b$ minimal; WLOG $a \geq b$. In particular, let $$a^2+b^2=c(ab+1) \iff a^2-abc+b^2-c=0$$ for some positive integer $c$. This means that if $(a, b)$ is a solution, so is $(a', b)$ where $a' = bc-a = \frac{b^2-c}a$. Notice furthermore that obviously $bc-a$ is positive, because else $$c \geq a+b^2 \implies a^2+b^2=c(ab+1) \geq (a+b^2)(ab+1) > a^2+b^2$$ is a contradiction; we cannot have $a'=0$ either as $c$ is not a perfect square.

Then $(a', b)$ works as well, and $$a' = \frac{b^2-c}a < a,$$ contradicting minimality.

Although this is solved using Vieta Jumping, I made a Java Program (see attachment) to find some of the cases. MOST (NOT ALL) cases are here of type $(a, a^3)$ but that's isn't sufficient to prove the problem as $(8, 30)$ is a nontrivial solution.
Also, you can prove that the perfect square is actually the square of GCD of $(a, b)$.

Note that if $b=0$, then $\dfrac{a^2 + b^2}{ab+1} = a^2$, a perfect square.
Now suppose $\dfrac{a^2 + b^2}{ab+1} = k$.

Fix $k$.
We have a quadratic in $a$,
$$a^2 - bk \cdot a + \left( b^2 - k \right) = 0$$
Given a root for $a$, we can switch it to $\dfrac{b^2 - k}{a}$ and the quadratic still holds.

Suppose $a \geq b$ at first.
$$b = \dfrac{ab}{a} \leq \dfrac{b^2}{a} > \dfrac{b^2 - k}{a}$$

So now $b>a$,
We proceed to flip $b$ by considering a similar quadratic in $b$.
This eventually lead to one of $a,b$ being zero, thus the conclusion.

Otherwise the process forms a infinite chain of decreasing pairs,
So there exist a pair with exactly 1 of $a,b$ negative.
This leads to $k \leq 0$,
Impossible as $a,b \in \mathbb{Z^+}$ at first.

Thus the Infinite Descent Method always works, the conclusion follows. $\hfill \square$

It is easy to see that $a \neq b$ (if otherwise, $\tfrac{2a^2}{2a+1}$ takes on positive integer value only at $a=1$). Let $k$ be arbitrary non-square integer. For the sake of contradiction, assume $\tfrac{a^2+b^2}{ab+1}=k.$ Let $a_1$ and $b_1$ denote the values such that $\tfrac{a_1^2+b_1^2}{a_1b_1+1}=k,$ such that $a_1+b_1$ is minimized. Without loss of generality, assume $a_1 > b_1.$

Fix $b_1$ and let $a_1=x$ to obtain $x^2+x(b_1k)+(b_1^2-k)=0.$ Obviously, one of the roots is $x_1=a_1,$ and the other root satisfies $x_2=b_1k-a_1$ and $x_2=\tfrac{b_1^2-k}{a_1}.$ The first condition implies $x_2$ is an integer, and the second condition implies $x_2 \neq 0,$ as $k$ is not a perfect square.

Observe $\tfrac{x_2^2+b_1^2}{x_2b_1+1}=k,$ implying $x_2>0.$ From $a_1>b_1,$ it follows $x_2 = \tfrac{b_1^2-k}{a_1} < a_1.$ But this is a contradiction, since $a_1+b_1>x_2+b_1.$

[quote=solyaris]I am afraid the solution still does not seem to be complete.

You have shown that the minimal solution $(a_{0},b_{0})$ has the property
$b_{1}=0$ and thus $k$ is a perfect square. But in fact the minmal solution is
$(a_{0},b_{0}) = (1,1)$, so $k=1$, which is a perfect square.

But what about non-minimal solutions?

I think it is possible to adapt your proof to show that all solutions in positive integers
have the given property.[/quote]

I think it's okay. We assumed the opposite - there are solutions such that k is not a square. Then we chose the minimum such solution - for example with the minimum sum a + b. Then, using the fact that k is not a square by proving that a and b are distinct, we obtain the solution (a, b1), where b1 is less than b but is still a positive integer and k is the same as for (a, b ), so it is not square. So this contradicts that (a, b) was a solution with k not square and the minimal sum of a and b, and if the minimal solution does not exist, there is [i]none[/i] solution with k not square. This proves the result.

Clearly $a=b$ gives a perfect square as $a=b=1$ is the only possibility, implying that $\frac{a^2+b^2}{ab+1} = 1$.

Now, let $(a_0,b_0)$ be the solution such that $a+b$ is minimized to $\frac{a^2+b^2}{ab+1} = k$ for any fixed non-square integer $k$ where WLOG $b_0>a_0$. Then, $a_0$ is a root of $a^2+(b_0k)a+(b_0^2-k)=0$. The other root to this equation is $a_1 = b_0k-a_0 = \frac{b_0^2-k}{a_0}$ which must be a positive integer. However, this contradicts the minimality of $a_0+b_0$, so no solutions to the equation exist for non-square $k$.

Thank you to @Pyramix for the Java program. Based on the additional cases I have constructed the set of cases

$(a, b) = (x^3, x^5 - x)$

since the solution set

$(a, b) = (x, x^3)$ is already known. I stared for a long time and did not find Vieta's Jumping intuitive. I am interested to hear your thoughts on characterizing the solution space of the problem. In general it seems like

$$a, b \in Z_{>0}, (ab + 1)\ |\ (a^2 + b^2) \implies gcd(a, b)^2 = \frac{a^2 + b^2}{ab + 1}$$

Edit: as a separate note I would like to add that the logical considerations based on minimality of $a + b$ (such as Vieta's Jumping) are confusing with reference to contrapositive logic. Proof by contradiction allows us to yield proofs of the form

$$(P \land Q \implies \lnot P) \implies \lnot Q$$

due to contrapositive logic, but since the claim is stated as an if-then (restricting to $a, b > 0$) I want to say we only have the option of proving

$$\lnot Q \implies \lnot P$$

if not

$$P \implies Q$$

Here, $P$ is the statement

$$(ab + 1)\ |\ a^2 + b^2$$

and $Q$ is the statement

$$\exists k : \frac{a^2 + b^2}{ab + 1} = k^2$$

Let $(a, b)$ be the the "smallest solution" in the sense that $a + b$ is minimized. Then we claim that if $k = (a^2 + b^2)/(ab + 1)$, then $\boxed{k = b^2}$. Also without loss of generality, assume $a > b$.

Consider the quadratic $f(t) = t^2 - (kb)t + (b^2 - k)$. Then there are two roots $a, a_0$, and by Vieta we find that $a + a_0 = kb \in \mathbb{Z} \implies a_0 \in \mathbb{Z}$, and also that $aa_0 = b^2 - k$. Therefore if $(a, b)$ is a solution, we find that $\left(\frac{b^2 - k}{a}, b \right)$ is also a solution.

[color=#f00][b]Claim:[/b][/color] $a_0 = 0$, so that $k = b^2$.
[i]Proof:[/i] Assume then we have $a_0 > 0$. Then since $a$ is minimal, we must have $a_0 > a$, or else we contradict minimality. Hence
\begin{align*}
&\frac{b^2 - k}{a} > a \\
\iff& b^2 - a^2 > k \frac{a^2 + b^2}{ab + 1} \\
\iff& b^2(ab) > a^2(ab + 2),
\end{align*} which is a contradiction. Therefore $a_0 = 0 \implies k = b^2$, as desired. $\blacksquare$

First, let's lay out the Vedic theorem:
Theorem (Vedic theorem ) : establish $x_1, x_2$ forUnary quadratic equations $a x^2+b x+c=0$ of the roots, then there is $x_1+x_2=-\frac{b}{a}$ moreover $x_1 x_2=\frac{c}{a}$

Now that the tools are ready, let's get to work!
moreover $a b+1 \mid a^2+b^2$ Confirmation $c \triangleq \frac{a^2+b^2}{a b+1}$ is perfectly squared.

Proof that if $\mathrm{a}$ and $\mathrm{b}$ exist such that $\mathrm{c}$ is not perfectly squared, it can be constructedNon-empty collections ${ }^a S \subset \mathbb{N}^* \times \mathbb{N}^*$ make $\forall(a, b) \in S$ There is c that is not perfectly squared. according toThe principle of good order ${ }^a$ (well-ordering principle), you can know that there is $\left(a_0, b_0\right) \in S$ make $a_0+b_0$ The value is minimal. will $a_0, b_0$ Substituting C'sexpression ${ }^{\varrho}$ Get:
$$
a_0^2-a_0 b_0 c+b_0^2-c=0
$$

Now consider a quadratic equation:
$$
x^2-x b_0 c+b_0^2-c=0
$$

Know $a_0$ is one of the roots of the equation. according toFundamental theorems of algebra $^a$ (fundamental theorem of algebra), we can see that there is another root in this equation $a_1$ , and we can use Veda's theorem to get the relationship between the two:
$$
\left\{\begin{array}{l}
a_0+a_1=b_0 c \\
a_0 a_1=b_0^2-c
\end{array}\right.
$$

Without losing generality, we assume $a_0>b_0$, then due to $b_0 c$ and $a_0$ are all integers, $a_1$ is an integer. Because $\mathrm{c}$ is not perfectly squared, so $a_1 \neq 0$ 。 if $a_1<0$ Rule:
$$
a_1^2-a_1 b_0 c+b_0^2-c \geq a_1^2+c+b_0^2-c>0
$$
therefore $a_1$ as $a_0$ and $b_0$ are all positive integers

Now according to the equation $\left({ }^*\right)$, it can be seen $a_1=\frac{b_0^2-c}{a_0}<\frac{b_0^2}{a_0}<a_0$ imply $a_1+b_0<a_0+b_0$ 。 However, this is contrary to the principle of good order, so $\mathrm{S}$ must be an empty set. So for all satisfied $a b+1 \mid a^2+b^2$ positive integers $a$ and $b, \frac{a^2+b^2}{a b+1}$ Always perfectly squared.


The number of inches in the perimeter of an equilateral triangle equals the number of square inches in the area of its circumscribed circle. What is the radius, in inches, of the circle?

$\left(A\right) \frac{3\sqrt{2}}{\pi}$

$\left(B\right) \frac{3\sqrt{3}}{\pi}$

$\left(C\right) \sqrt{3}$

$\left(D\right) \frac{6}{\pi}$

$\left(E\right) \sqrt{3}\pi$

[hide]For some reason, I'm getting $\frac{6\sqrt{3}}{\pi}$. :huh: [/hide]

[hide="Solution"]
Using the fact that $[ABC]=\frac{a*b*c}{4R}$ we solve for $R$ to find:

$R=\frac{x}{\sqrt3}$ where x is a side of the triangle.

We need $3x=(\frac{x}{\sqrt3})^{2}*\pi$

Solving this we get $x=0$ or $x=\frac{9}{\pi}$ obviously $x\neq0$ so the radius of the circumscribed circle is $R=\frac{9}{\pi\sqrt3}= \frac{3\sqrt3}{\pi}$

$\boxed{B}$
[/hide]

[hide="sol"]Let $a$ be a side of the triangle. Then the perimeter is $3a$. The radius of the circumcircle is $\frac{a\sqrt{3}}{3}$, so the area of the circle is $\frac{a^{2}\pi}{3}$. Thus, $3a=\frac{a^{2}\pi}{3}\Longrightarrow a=\frac{9}{\pi}$. Plugging this back in $\frac{a\sqrt{3}}{3}$, we get the radius as $\left(B\right) \frac{3\sqrt{3}}{\pi}$[/hide]


The polynomial $4x^{3}-12x^{2}+3x-0.1=0$ has roots $r, s, t$.  Find the diagonal of a box with those dimensions (r, s, and t).

Note: Wording may be off

[quote="robinhe"]The polynomial $4x^{3}-12x^{2}+3x-2.9=0$ has roots $r, s, t$.  Find the diagonal of a box with those dimensions (r, s, and t).

Note: Wording may be off[/quote]

[hide]Is it $\sqrt{3^{2}-2(\frac{3}{4})}=\frac{\sqrt{30}}{2}$ :?: [/hide]

[quote="lingomaniac88"]How do you know the values of $r+s+t$ and $rs+st+tr$?[/quote] Vieta's formulas: In $f(x)=ax^{3}+bx^{2}+cx+d$, with roots $r,s,t$,

$r+s+t=-\frac{b}{a}$
and
$rs+st+tr=\frac{c}{a}$

also, $rst=-\frac{d}{a}$


inequalities
real analysis
real analysis theorems

Say we have proven

$ 2(\sqrt {n \plus{} 1} \minus{} \sqrt {n}) < \dfrac{1}{\sqrt {n}} < 2(\sqrt {n} \minus{} \sqrt {n \minus{} 1}) \qquad \qquad for\;\: n\ge1$

From this we have to deduce

$ 2\sqrt {m} \minus{} 2 < \sum_{k \equal{} 1}^{m}\frac {1}{\sqrt {n}} < 2\sqrt {m} \minus{} 1 \qquad \qquad \qquad \qquad \;\; for\;\: m\ge2$

Now the obvious way to me is to sum both sides of the first inequality, i.e.

$ 2\sum_{k \equal{} 1}^{m}(\sqrt {n \plus{} 1} \minus{} \sqrt {n}) \equal{} 2\sqrt {m \plus{} 1} \minus{} 2 \qquad \qquad (using\;\;telescoping)$

$ 2\sum_{k \equal{} 1}^{m}(\sqrt {n} \minus{} \sqrt {n \minus{} 1}) \equal{} 2\sqrt {m} \qquad \qquad \qquad \quad \;\: (using\;\;telescoping)$

But this proves,

$ 2\sqrt {m \plus{} 1} \minus{} 2 < \sum_{k \equal{} 1}^{m}\frac {1}{\sqrt {n}} < 2\sqrt {m}$

not exactly what we were looking for.... any help is appreciated.... if there is a mistake just lemme know the part that is wrong....

The right-hand-side of the starting inequality is very weak: $ 1 < 2$. So for the right-hand-side do the telescoping from $ 2$ to $ m$, getting $ 2(\sqrt{m} \minus{} 1)$, and for $ 1$ add $ 1$, to get $ 2\sqrt{m} \minus{} 1$, as required. Voila.


All clocks on a NASA space shuttle are set to $ \emph{Mission Elapsed Time}$ (MET). The MET clock is set at midnight and begins when the shuttle is launched. Hence, one hour after liftoff, the shuttle's clock reads 1:00 (MET). If a shuttle launches at 8:09 a.m., at what time that afternoon will the shuttle clock read 4:55 (MET)?

This task should clearly specify its output format. I just failed it for entering "1:04 PM" instead of the expected "1:04". Not to speak about the possibility to enter "13:04", which is the natural way for us non-Americans :wink:

Sadly, though, I think it's justified, as it said what time "in the afternoon" implying PM. I understand...it could get confusing.


There's no reason to suspect this statement is true.  For example, $ 3 \equiv 1 \bmod 2$ but clearly $ 3^k \not \equiv 1 \bmod 2^k$ for most $ k$.

I think your thinking about the congruence property that if a congruent to b modulo m, then a^k is congruent to b^k modulo m.

O.. Ok, my fault :mrgreen:
Thanks for helping guys!

I need to verify this statement:
$ 19\equiv \minus{}6 \mod 5$

Why don't you verify it by adding $ 6$ to both sides and then using the definition of $ \equiv 0$  :wink:

[quote="wangsacl"]If $ a\equiv b \mod n$, then $ a^k\equiv b^k \mod n^k$, for $ a,b\in\mathbb{Z}$, $ n,k\in\mathbb{N}$.[/quote]

Possibly typo?

A slight correction gives right statement:

If $ a\equiv b \mod n^k$, then $ a^k\equiv b^k \mod n^{k\plus{}1}$, for $ a,b\in\mathbb{Z}$, $ n,k\in\mathbb{N}$

digger: I don't think that's true either; try $ a \equal{} 1,b \equal{} 3,n \equal{} 2,k \equal{} 1$.

It should read something like $ a \equiv b \bmod n^k \implies a^n \equiv b^n \bmod n^{k\plus{}1}$ (with possibly one counterexample).  See [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=664257617&t=205928]lifting the exponent[/url].

Yes,  "the possible one" is "k=1", i've forgot to add $ k > 1$
The slight correction i've ment was
$ a\equiv b \mod n$, then $ a^k\equiv b^k \mod n^{k\plus{}1}$, for $ a,b\in\mathbb{Z}$, $ n,k\in\mathbb{N}, k\geqslant 2$

That for delirious post i've written!
I ment exactly those that t0rajir0u had wriitten.
The fact is immediate from $ (a^n\minus{}b^n)\equal{}(a\minus{}b)(a^{n\minus{}1}\plus{}a^{n\minus{}2}b\plus{} \dots \plus{} b^{n\minus{}1})$.
The additial $ n$ gives $ n$ congruent members $ a^{n\minus{}1}, a^{n\minus{}2}b,  \dots , b^{n\minus{}1}$.

But I dont understand what means "(with possibly one counterexample)".

Sorry; lifting the exponent is a stronger statement.  What it says is that, for a prime $ p$ (and possibly for nonprimes as well) if $ a \equiv 1 \bmod p^k$ but $ a \not \equiv 1 \bmod p^{k \plus{} 1}$ then $ a^p \equiv 1 \bmod p^{k \plus{} 1}$ but $ a^p \not \equiv 1 \bmod p^{k \plus{} 2}$, which is false when $ p \equal{} 2$ and $ k \equal{} 1$ but true in all other cases.


geometry
AMC
AIME
Pythagorean Theorem
similar triangles

I hope it's not too early to begin discussing yesterday's Mathleague problems. If so, moderators, please delete this thread :blush:

What is the area of a semicircle tangent to two adjacent sides of a square, where the endpoints of the diameter lie on the other two sides of the square?

I hated that question. :mad:

Only one I got wrong :(

I got a 6, so I am perfect so far...

Apparently I am the only one in my school who got a perfect through two contests so far...

Hint...this was like an AIME #10 problem...2005, or something like that...

Call the radius r, and try to find an equation relating r and the side of the square...

ahh... fun problem.

I solved it by looking at the isoceles right triangle with legs of length $1-r$ and hypotenuse of length $r$. Should be easy from there.

I took that test.

I think the answer was (3-2rt2)pi

Well at least that is what someone else said.

I am not sure about it. I worked it out though.

I ended up with a 4.  :(

I've gotten a 4 on both tests, but then again I am only in geometry,

ASMA 13/14
Mandelbrot-  I got an 11 this week. I missed the last one.
state math league- the one with semicircle-  8/12 =(

I used Treething's method (thanks) and got pi(3 - 2rt2)/9.

Huh. Did the original question ask for the area of the semicircle, or the area of the region between the semicircle and the square?

Because I tried to figure out the area between the semicircle and the square. Which means I was wrong on that problem in two ways. :blush:

So I got a 5/6 again... :(

I go to the high school nearby every school day to do math leagues and for math team.

[quote="mathnerd314"][quote="now a ranger"]area of the semicircle

I checked with my teacher

i got a 4/6 again.

I'm in 8th grade.[/quote]

I thought the test was 9th through 12th grade... :huh:

I drew a diagram and I don't see the isoscles right triangle...[/quote]

Outside of the semicircle. It's one-fourth the area of the isoceles right triangle between the semicircle and the square. I need a piece of paper, a pencil, and a cough drop.

yeah the isosceles right triangle has legs radius/rt2 and of course its hypotenuse is r for radius.

I think.

Yes, that's the way I figured out.

I made a stupid mistake on that one, I thought the semicircle was supposed to be around the square, stupid me. I ended up with a 5.

I got like the easiest qustion wrong last time (triangles), and #6, so so far I have 9/12.  :mad: I'm in 8th grade.

Using treething's method, isn't the answer $(3-2\sqrt{2})\pi$  ?

- NAWAHD WERDNA

Hmmm...

I am perfect through everything that I take so far...only 2

MML (12/12)
ASMA (14/14)

Yes the answer to the last one is whatever someone said with a root 2 in it...

8/12, utterly dissapointed. hehe 8th grade

This is weird. Do they give same questions to each state?

I talked to a guy from California and he had this question too. I am from Alabama.

Lol. I didn't know they give different state math leagues same questions.

What was you guy's method for number 5? the one with abcubed blah blah = 30, then other = 90 blah blah

Yes, it is called the Math League Contest, which is given the same in all states...

[quote="Treething"]I believe the answer is $\pi(3-2\sqrt{2})$, given I remember the question correctly.[/quote]

yea, this is right, it's not hard, use similar triangles to find the 45-45-90 thing

[quote="57_factorial"]So far I've missed question 6 on both of them, so 10/12.

I really should have got this one though; it's not too bad.  Just simple pythagorean theorem and then algebra :([/quote]

Not even pythagorean theorem really...

Just noting the algebra and that the median to the hypotenuse is half the hypotenuse...


An increasing arithmetic sequence with infinitely many terms is determined as follows.  A single die is thrown and the number that appears is taken as the first term. The die is thrown again and the second number that appears is taken as the common difference between each pair of consecutive terms.  Determine with proof how many of the 36 possible sequences formed in this way contain at least one perfect square.

[hide="Answer"]We must focus on the difference $d$ between each term in the arithmetic sequence.

$d=1$: all integers are included, so all perfect squares are included for every value of $a$.

$d=2$: if $a$ is even, then all even perfect squares are included; if $a$ is odd, then all odd perfect squares are included.

$d=3$: all perfect squares are $\equiv 0,1\bmod{3}$, so $a=1,3,4,6$ will work.

$d=4$: all perfect squares are $\equiv 0,1\bmod{4}$, so $a=1,4,5$ will work.

$d=5$: all perfect squares are $\equiv 0,1,4\bmod{5}$, so $a=1,4,5,6$ will work.

$d=6$: as with $d=3$, since all perfect squares are $\equiv 0,1\bmod{3}$, then $a=1,3,4,6$ will work. To demonstrate, $1+4(6)=25=5^2$, $3+6=9=3^2$, $4+2(6)=16=4^2$, and $6+5(6)=36=6^2$.[/hide]


Here is another hard problem for you guys:

From finite distance $ R$ a particle fall into the middle of $ U(r)\equal{}\minus{}\frac{\alpha}{r^n}$ potential. Meanwhile does it make a finite number of turns? Does he fall in in finite time?

I didn't rightly understand part I.
For part II, I got the differential equation $ \frac {dr}{dt} \equal{} \sqrt {2\alpha (\frac {1}{r^n} \minus{} \frac{1}{R^n})}$, which I cannot solve in general.
For $ n \equal{} 2$ it gives infinite value for time.


Prove that for every prime $p$, there is an $a \in \left\{1, 2, ..., 9\right\}$ such that both $a$ and $a+1$ are squares modulo $p$.

If at least one of $2$ or $5$ is square $\mod{p}$ then we can take $a=1$ or $a=4$ respectively. If not, then:
$(\frac{10}{p})=(\frac{2}{p})(\frac{5}{p})=(-1)*(-1)=1$
so we can take $a=9$.

I remembered reading it somewhere, but I forgot !!  :(
I mean the technique u use to solve this problem...
Can you tell me again, TomciO ???

He used the multiplicativity of the Legendre symbol.  :)


Suppose $x \ge y \ge z$, then $\frac{1}{xs+1} \le \frac{1}{ys+1} \le \frac{1}{zs+1}$, where $s = x+y+z$.

We have $xy \ge xz \ge yz$ and $z^2 \le y^2 \le x^2$, so by rearrangement, the result follows.


limit
integration
inequalities
real analysis
real analysis unsolved

Suppose $1<p<\infty$. $f_n\in L^p(\mathbb{R})$, $\|f_n\|_p \leq M$ holds for all $n$. $f\in L^p(\mathbb{R})$ and
$\lim_{n\to\infty} \int_0^x f_n(t)dt = \int_0^x f(t)dt, \quad x\in\mathbb{R},$
Show that it holds
$\lim_{n\to\infty} \int_{\mathbb{R}^n} f_n(x)g(x)dx = \int_{\mathbb{R}^n} f(x)g(x)dx$
for any $g\in L^q(\mathbb{R})$ where $q$ satisfies $1/p+1/q=1$.

[quote="liyi"]Suppose $1<p<\infty$. $f_n\in L^p(\mathbb{R})$, $\|f_n\|_p \leq M$ holds for all $n$. $f\in L^p(\mathbb{R})$ and
$\lim_{n\to\infty} \int_0^x f_n(t)dt = \int_0^x f(t)dt, \quad x\in\mathbb{R},$

Show that it holds
$\lim_{n\to\infty} \int_{\mathbb{R}^n} f_n(x)g(x)dx = \int_{\mathbb{R}^n} f(x)g(x)dx$

For any $g\in L^q(\mathbb{R})$ where $q$ satisfies $1/p+1/q=1$.[/quote]
Let $F_n(x) = \int_{-x}^x f_n(t)dt$ and $\phi_n(x) = \int_{-x}^x f_n(t)g(t)\,dt$.

By putting $f_n(t) \rightarrow f_n(t) - f(t)$ we can suppose that, WLOG: $f(t) = 0$. And from the first limit, by replacing $x$ by by $-x$ we can easily conclude

\[%Error. "limi" is a bad command.
_{n\to\infty}F_n(x) = \lim_{n\to\infty} \int_{-x}^x f_n(t)dt = 0\]

For any n and $x \in R$, this holds by using Holder's inequality

\[|\phi_n(x)| = |\int_{-x}^x f_n(t)g(t)\,dt| \leq (\int_{-x}^x |f_n(t)|^p\,dt)^{1/p}( \int_{-x}^x ||g(t)|^q\,dt)^{1/q} \leq M||g||_{q}\]

Since $\phi_n(x)$ is bounded in $\mathbb{R}$:

\[\lim_{n\to\infty}\lim_{x\to\infty}\int_{-x}^x f_n(t) g(t)\,dt
\&= \lim_{n}\lim_{x}(F_n(t)g(t)-F_n(-t)g(-t))|_{t=-x}^{t=x} - \lim_{n\to\infty}\lim_{x\to\infty} \int_{-x}^x F_n(t)\,dg(t) \\
\&=\lim_{x\to\infty}\lim_{n\to\infty}(F_n(t)g(t)-F_n(-t)g(-t))|_{t=-x}^{t=x} - \lim_{x\to\infty} \int_{-x}^x \lim_{n\to\infty}F_n(t)\,dg(t) \\
\&= 0 \]

I missed something so please correct if you find any :)


Fie $A \in M_{n}(N),m \in N^*\{1$} astfel incat (m,detA)=1.
Sa se arate ca $A^2+A+mI_{n}$ este nesingulara.

Consideram polinoamele $ P(x)=det(xI_n-A) , Q(X)=x^2+x+m$ , polinoame ce sunt prime intre ele (in caz contrar P(x)=Q(x)C(x) si ar rezulta ca $(-1)^ndet A=mc_0$ adica m si det A nu ar fi prime).
Atunci exista $T(x) , S(x) \in Z[X] $ astfel incat P(x)T(x)+Q(x)S(x)=1. Inlocuim x cu A si obtinem $(A^2+A+mI_n)S(A)=I_n$ si aplicand det rezulta ca $A^2+A+mI_n$ este nesingulara. ;)


A rectangular pool measuring 6 feet by 12 feet is surrounded by a walkway. The width of the walkway is the same on all four sides of the pool. If the total area of the walkway and pool is 520 square feet, what is the number of feet in the width of the walkway?


MATHCOUNTS
geometry
rectangle
perimeter
incenter
Pythagorean Theorem
angle bisector

The challenge is to solve this problem using middle school techniques.  This problem can be solved with nothing more than ...[hide]the Pythagorean Theorem and similar triangles.[/hide]
Do not use trigonometry.  Do not use the "angle bisector theorem".

Did it say how to express ur answer? That shoud give a hint about the answer...
And it would help to kno if calcs were allowed.... (for educated guessing)...
Finally, is the diagram correct... it would help to kno which one was the right angle?...
Thx....

[quote="cj"]2005 Mathcounts handbook Workout 8 # 8:

Right triangle ABC is divided such that angle BAC is bisected by AD. What is the length of AD.  (B is the right angle, AB = 9, AC= 15).[/quote]
[hide]
15 2  - 9 2 =b 2
225-81=144
 :sqrt: 144=12
12/2=6
81+36=c 2
117=c 2
AD= :sqrt: 117[/hide]

[quote="GoBraves"][quote="DarkKnight"][hide]
15 2  - 9 2 =b 2
225-81=144
 :sqrt: 144=12
12/2=6
81+36=c 2
117=c 2
AD= :sqrt: 117[/hide][/quote]
I disagree, its true that angle BAC is being bisected by AD but that does not mean that AD is bisecting BC too.[/quote]
Oh! Good point.
haha... I think i finally get why rcv said use similar triangles.

[quote="hockeyadi23"]Did it say how to express ur answer? That shoud give a hint about the answer...
And it would help to kno if calcs were allowed.... (for educated guessing)...
Finally, is the diagram correct... it would help to kno which one was the right angle?.[/quote]
The handbook says "express your answer as a decimal to the nearest hundredth".

Most Workout problems assume the use of a calculator.  For this problem, "yes", you may use a calculator.

The illustration closely resembles what was presented in the handbook.  You should generally not assume that drawings are "to scale".  Angle B is the right angle of triangle ABC.

Nice... btw is your diagram big enough??? :D  lol

[quote="GoBraves"]Ok i think i got the answer, but i think its gonna be hard to explain, so i made a picture.[/quote]
Could we have a little explanation to go along with the picture, please?

[quote="rcv"]Could we have a little explanation to go along with the picture, please?[/quote]
Of course

What i did was draw three points E,F, and G(thats not on the pic, i didn't have enough space!!)  that bisect each side of triangle ABC and connected e to f and f to g, which created rectangle EFGB. Then i realised that left me with two similar triangles, FGC and AEF. Since AE is equal to EB, and ED is bisecting rectangle angle BEF, we figure out that triangle EBD is an icosceles triangle. Therefore BD is equal to 4.5. Then we use the pythagorean theorem to find the answer.

Does anybody have an easier way to this?? This took some time.

[hide]The answer is 10.06 or 101.25 cubed.
This is a 3-4-5 triangle and the base is 12.  THerefore, we use the angle bisector formula to get 9/15=BD/DC where BD+DC=BC so 3/5=BD/DC and 3+5/5=BD+DC/DC which equals 8/5=12/DC so DC=7.5 and BD=4.5 so we use the Pythagorian theorem to solve for AD.
sqrt(9^2+4.5^2)=AD[/hide]

gobraves:  You are correct that ray BD bisects angle BEF, but I don't see a convincing argument that this is true.

dengmi:  The challenge is to solve this problem using middle school techniques.  "Do not use trigonometry.  Do not use the angle bisector theorem."

[hide="Two hints"]Hint 1 (harder):  If you know how to inscribe a circle in a right triangle, this might help you.
-- or --
Hint 2 (easier):  Draw a line segment from point D to line segment AC, perpendicular to AC.[/hide]

[quote="rcv"]gobraves:  You are correct that ray BD bisects angle BEF, but I don't see a convincing argument that this is true.[/quote]
I never said BD bisects BEF

[quote="rcv"][quote="GoBraves"]I never said BD bisects BEF[/quote]
Oops.  Sorry.  I think you said ED bisects BEF.  It does.  But I don't see a convincing argument that this is true.[/quote]

Thats a good point. I wonder why i claimed it bisected BEF then. I guess i messed up and got lucky! :P

I'd appreciate it if someone could draw in the other points that you marked (like points D,E,F so that we can see what you all are doing... thanks

OK.  I guess it's time for a better hint.  Beginning with the original drawing, I have labeled one additional point, I have drawn one additional line segment, and I have labeled one additional length.  Where can you go from here?

[hide][img]http://www.artofproblemsolving.com/Forum/files/bisector_383.gif[/img][/hide]

Thanks a lot: Now I got the answer.

[hide]Using rcv's second diagram, you realize that AB = AJ, so both are 9. Then, you see that CJ is 6. Now, you realize that ABC and CJD are similar, and you have two corresponding sides in 6 and twelve (they are similar because they both have a right angle, share an angle, and therefore the third angles are also congruent. Now you can take the 9 from side AB. and divide by two to get JD, and therefore BD also equals 4.5. With that, you can use the pythagorean theorem to get the length of the segment, as the legs of the right triangle are of length 9 and $\sqrt{9^{2}+4.5^{2}}=\sqrt{101.25}=10.062305898749053633841281509291\approx10.06$. Therefore, the answer is 10.06[/hide]
[hide="I forgot to mention"]I forgot to mention the fact that triangles ABD and AJD are congruent, which is probably the most important thing aside from the similar triangles to realize when doing this problem (for all you geometric proof people, they are congruent by Angle, angle, side, as AD is shared) Thanks for the hint RCV....[/hide]

[quote="rcv"][quote="hockeyadi23"]Thanks a lot: Now I got the answer.[/quote]
Nice job, hockeyadi23!

Now, for another method.  Suppose I tell you the radius of a circle inscribed in a triangle is $r=\frac{A}{s}$, where $A$ is the area of the triangle, and $s$ is the semi-perimeter (one-half of the perimeter).  [Some of you may already have known this formula, but it isn't used very often in MATHCOUNTS.]

Can you find another method of obtaining the length of AD.  [Point D and line segment AD are omitted from the following drawing, due to clutter.  Please refer to the previous drawings.]  Anyone game?[/quote]

Here's the solution with rcv's second method:

[hide="Solution"] The point I is the incenter of the triangle, where all of the angle bisectors meet. Using the formula $r=A/s$, I determined that the radius was three, which in a way gave me the entire answer. Square RIPB, made up of two of the radii, had the side length of 3. That gave me AR = 6. Now, because the angle bisector runs through the center of the circle, I could use similar triangles to find the length of the hypotenuse. You are given a smaller version of the triangle with bases 6 and three, and with proportins you get a roght triangle with bases 9 and 4.5. $\sqrt{9^{2}+4.5^{2}}=\sqrt{101.25}\approx10.06$ [/hide]
[hide="Another Point"]From the point where you identify the similar triangles, you could also find the length of the smaller hypotenuse, and use similar triangles in that way, to get $9\sqrt{5}/2\approx10.06$[/hide]


geometry
geometric transformation
reflection
search
incenter
geometry proposed

Let a triangle $ ABC$ with excircle center is $ A',B',C'$ and call $ A_1,B_1,C_1$ is reflect point of $ A',B',C'$ over $ BC,CA,AB$ respectively. Prove that $ AA_1,BB_1,CC_1$ are concur!

Because $ A',B',C'$ are the centers of the respective excircles than it is obvious that :

$ \angle A'BC\equal{}\angle C'BA$ , $ \angle A'CB\equal{}\angle B'CA$ , $ \angle B'AC\equal{}\angle C'AB$

From the reflection we can easily obtain :

$ \angle A_{1}BC\equal{}\angle C_{1}BA$ , $ \angle A_{1}CB\equal{}\angle B_{1}CA$ , $ \angle B_{1}AC\equal{}\angle C_{1}AB$

From [url=http://www.mathlinks.ro/Forum/viewtopic.php?search_id=1444517305&t=30114]Jacobi Theorem[/url] results $ AA_{1}, BB_{1} , CC_{1}$  concur.

Thanks for your solution! My solution:
We consider two triangle $ ABA_1$ and $ C_1BC$ we have:
$ \angle{ABA_1} \equal{} \angle{C_1BC}$ (Because $ \angle{ABC_1} \equal{} \angle{ABC'} \equal{} \angle{A'BC} \equal{} \angle{A_1BC}$)
$ \frac {AB}{A_1B} \equal{} \frac {AB}{A'B} \equal{} \frac {C'B}{CB} \equal{} \frac {C_1B}{CB}$
Then two this triangle are similar, hence $ \angle{AA_1B} \equal{} \angle{C_1CB}$, it mean $ \angle{ATC} \equal{} 180^0 \minus{} \angle{A_1BC} \equal{} 180^0 \minus{} \angle{A'BC} \equal{} 90^0 \minus{} \frac {B}{2}$ ($ T \equal{} AA_1\cap CC_1$)
Similar then OK!

PS: This is the result I found! And I wonder is it a new result? Or may be is it a well-known point? If that then what name is this point?

The point of concurrence is X(80), as listed in the [url=http://faculty.evansville.edu/ck6/encyclopedia/ETC.html]ETC[/url].  As the name implies, it is the reflection of the incenter in the Feuerbach point.

Darij Grinberg calls it the [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=109112]Antigray point[/url].


P4

Prove that for n>=2 n does not divide 3^n-2^n.

so your just asking for a proof that 3^n-2^n is prime?

No... he asks to prove that n cannot divide 3n - 2n; something else could possibly divide it. Take n = 4 for example.

[hide]I hope this is right cuz I'm not very good at number theory

First look at the case when n is prime. Then by Fermat's Little Theorem, 3 = 3^n = 2^n = 2 (mod n), which is impossible. So suppose n = p1^a1 * p2^a2 *... * pn^an.

Now if 3^n = 2^n (mod n), then 3^n = 2^n (mod p1) (I hope this is right). Again using Fermat's Theorem, we have 3 = 2 (mod p1), again an impossibility.[/hide]

Can you explain why [hide]3^n = 3 (mod p1) by Fermats little theorem?[/hide]

Oh...ok nvm... :-)

So how is this problem solved?

Ok..I have an idea...

Obviously n cannot be even...so assume n is odd. Also note that n cannot be divisible by 3.

3^n - 2^n = 0 (mod n)
(3^(n-1) + 3^(n-2) * 2^(1) + ... + 3^1 * 2^(n-2) + 2^(n-1)) = 0 (mod n).   <-- (1)

Now let n=5. 3^2 = 2^2 = -1 (mod 5) so the only possible values for the terms on the LHS of (1) are either 1 and 4 or 2 and 3. But the number of terms on the LHS is odd, so it can never be 0.

If n is a prime greater than 5 and not divisible by 3 or 5, the terms on the LHS of (1) form a complete set (that is {0,1,2,3,...,n-1}) of residues mod n except for 0. Since we have n terms on the LHS, and we know that n-1 of them make up the set {1,2,...,n-1}, there must be one more term that is a member of that set. The sum of the elements of {1,2,...,n-1} is = 0 (mod n), but the extra term cannot be 0 (mod n). Thus for prime n > 5 the LHS is =! 0 (mod n).

Now to attack the case for any n:

Look at 3^n - 2^n mod each of the prime factors of n. We have proved that it is impossible for the 3^n - 2^n to be = 0 (mod any prime >3) and it is obvious that the LHS is not 0 (mod 3) or (mod 2).

Thus since 3^n - 2^n =! 0 (mod any prime number), it =! 0 (mod n) for any positive integer n.

Hope it's at least a little more correct this time....

[quote="froufrou4189"]

If n is a prime greater than 5 and not divisible by 3 or 5, the terms on the LHS of (1) form a complete set (that is {0,1,2,3,...,n-1}) of residues mod n except for 0. [/quote]

Hmm.. I can't quite see why this is true.. assuming, say, 3^p 2^(n-1-p) and 3^q 2^(n-1-q) were congruent, then you get 3^(p-q) = 2^(p-q) mod this mod.. doesn't this sort of loop round to what we were trying to prove almost? Maybe theres another way of showing no two can be congruent that I haven't seen..

Ahha! I think I have solved this now.. though the answer was a lot easier than I thought it would be, so I may have a mistake somewhere..

[hide]

Consider the smallest n where 3^n = 2^n (mod n). Then consider the smallest a>0 where 3^a = 2^a (mod n).

Fact 1: a<n, because 3^(:phi:(n)) = 2^(:phi:(n)) (mod n), and :phi:(n) < n.

Fact 2: a|n, because we chose a to be minimal. (Basically you can keep taking powers of a out of 3^n and 2^n until you get to something <= a, and so it has to be actually a multiple of a).

So 3^a = 2^a (mod n) => 3^a = 2^a (mod a) since n is a multiple of a. Contradiction as we chose n to be minimal.

[/hide]

Something like that. My soln is similar:

[hide]It's not such a hard problem if you're familiar with Mersenne sequences: (a_n)n>=1 is a Mersenne sequence iff (a_m, a_n)=a_(m, n) for all m, n positive integers. It's a well-known fact that a^n-b^n is a Mersenne sequence for positive (I think they also have to be coprime) integers a and b. Anyway, 3^n-2^n is definitely a Mersenne sequence and that's accepted in competitions (you don't have to prove it; at least it's accepted in Romania).

Now for he soln:

Take p to be the smallest prime divisor of n. p|n|3^n-2^n (*) and p|3^(p-1)-2^(p-1) (**)(p is obviously different from 2 or 3). From (*) and (**) we get                                                                    p|(3^n-2^n, 3^(p-1)-2^(p-1)) = 3^(n,p-1)-2^(n,p-1) = 3-2 =1 because (n, p-1)=1 since p is the smallest prime which divides n.[/hide]


geometry
cyclic quadrilateral
projective geometry

ABC is a triangle. A circle passing through A and B intersects side BC again at D. A circle passing through vertices B and C intersects side AB again at E, and intersects the first circle again at F.

Suppose A, E, D, C lie on a circle centred at O. Show that BFO is a right angle.

Since AEDC is cyclic we can use a very powerful tool: inversion.

We have BA*BE=BD*BC, so it's natural to consider inversion of pole B and power k^2=BE*BA. Since by this inversion A turns into E and D turns into C then the circle ABD turns into the line EC. In the same way we prove that the circle BCE turns into AD. This means that F, the other intersection of the 2 circles, turns into F', the intersection of lines AD and EC, which means that BF*BF'=BE*BE=BD*BC. In order to prove that BFO=90 deg it's enough to prove that BO'F'=90 deg, where o' is the image of O by the above inversion.

So the new problem is this: We have a cyclic quadrilateral AEDC, inscribed in a circle centered at O. The intersection of AE and CD is B and the intersection of AD and EC is F'. The image of O by the inversion of pole B and power BE*BA=BD*BC is O'. Prove that BO'F'=90 deg.

First of all, it's easy to show (I won't do it here; take it as an exercise) that O' can be obtained like this: we draw the tangents from B to the circle. They touch the sircle at T1 and T2. The intersection of T1T2 and BO is O', which means that O' is on the polar of B with respect to the circle, so O' is the midpt of T1T2. However, it's well-known that the angular polar of B with respect to the angle formed by the lines AC and ED is the same as the polar of B with respect to the circle (you can find this result in any book dealing with basic projective geometry), and F' is on that angular polar (the same can be said abt this result), which means that F' is on the polar of B with respect to the circle, so F' is on T1T2, and since O' is the midpt of T1T2 and the triangle BT1T2 is isosceles, it means that angle BO'F'=90 deg, so BFO=90 deg (because BF*BF'=BO*BO', so O'OFF' is cyclic, so OFF'+F'O'O=180 deg), Q.E.D.

I know there's a lot of unproven stuff here, but they are all well-known results in projective geometry (the basic part of projective geometry, since I don't know any of the tougher part of proj geom :)). Sorry it's so long...


Sorry if this is in the wrong place but I didn't know where to put it.

My High school has no math team so I'm thinking of starting one (I'm a student not a teacher), the problem is, I have no idea what exactly a typical math team does (I know the team signs up for contests but I mean at the weekly meetings). Everyone that would go would be at the level of solving the harder AMC questions. What kinds of things do your math teams do at the meetings? Solve problems? Assign some problems and go over them at meetings? Lecture about math topics? Or something else?

Might I suggest this topic: [url]http://www.artofproblemsolving.com/Forum/viewtopic.php?t=203549&search_id=460341485[/url]


My school participates in this MATHCOUNTS thing called the "Monthy Challenge". Every month, the MATHCOUNTS Organization sends out $ 5$ problems for individual schools to do.
I was wondering how many other school participate in this "Monthy Challenge".

Thanks!

(Continue this thread if you have questions)

Yeah take them but I frequently fail on them.  Is it just me or are the monthly challenges so easy but yet so hard? :huuh:  I find myself making at least one stupid mistake per test.  :oops_sign:

Do you guys think monthly challenges or MOEMS is harder? (I'm referring to middle school MOEMS )

Nah the monthly challenges are pretty ez...however I make silly mistakes on them too!  :(

Monthy Challenges are definately harder than MOEMS.  :wink:


A six-digit integer XYXYXY, where X and Y are digits, is equal to five times the product of three consecutive odd integers. Determine these three odd integers.
Please show how you solved this problem. thx!

[hide="Solution"]$ y\equal{}5$ is an obvious statement. We note that the given number must be divisible by $ 10101 \equal{} 3 \times 7 \times 13 \times 37$. As a rough upper bound, the largest integer cannot be greater than $ \sqrt[3]{1000000} \approx 63$. Therefore, $ 37$ must be one of the integers present. Consider $ 5 \times 35 \times 37 \times 39 \equal{} \boxed{252525}$. Well... it works.

I do admit this process isn't purely rigorous; if you need help, I can explain in more detail my logic.[/hide]

[hide="Intriguing Problem"]

First, note that Y is 5 (5 times an odd product).

Also, note that only one of our three numbers is divisible by 3 (since one of the three numbers is 0 mod 3). So we need 3X divisible by 3, not 9. That eliminates 1, 4, 7.

After that, we can just plug in and start factoring. Fortunately, 252525 was the first number I tried, which factors as $ 3\cdot5^2\cdot7\cdot13\cdot37\cdot$.

[/hide]


I'm sure many of you have seen this problem and know the answer off the top of your head, but see if you can solve it using algebra:

find all sets of consecutive integers (x,y,z) such that x+y+z = xyz

Hint:
[hide]Set the integers x,y, and z to variables that will cancel out easily when you find their sum[/hide]

[hide]since y=x+1, z=x+2, hence
$x+x+1+x+2=x(x+1)(x+2)
3x+3=x^{3}+3x^{2}+2x
x^{3}+3x^{2}-x-3=0
This is the important step:
x^{2}(x+3)-(x+3)=0
(x+3)(x+1)(x-1)=0
x=-3, -1 or 1$

therefore the answers are: (-3, -2, -1), (-1, 0, 1) and (1, 2, 3)

P.S.even if x, y, z can be any numbers other than Integers, these 3 answers are still the only 3.
[/hide]

[quote="shake9991"][hide]since they are consecutive let us ue symettry about y.
x=y-1, y=y, z=y+1
so we are essentially solving this:
(y-1)+y+(y+1) = (y-1)(y)(y+1)
so simplifying we get:
3y = (y-1)(y)(y+1)
so
3=(y-1)(y+1)
we can then say:
0=y^2 -4
y=-2 or 2.
so our solution sets are:
(-3,-2,-1) and (1,2,3) of course we can always have y=0... which also works so another solution set would be:
(-1,0,1)[/hide][/quote]
[hide=""Remark for shake9991 solution""]I should note that when you are transitioning from $3y = (y-1)(y)(y+1)$ to $3=(y-1)(y+1)$ remember that $y\neq0$ and put $y=0$ as a separate case. ;) [/hide]

[quote="Treething"]Without doing any algebra, you can get them pretty easily. Of course, you'd have to use the algebraic method to confirm it.

[hide="How"]
-1, 0, 1. They add up to 0 and the product is 0.
1, 2, 3. 6 is a perfect number.
-1, -2, -3. Look at 1, 2, 3 and you'd probably think fo this.
[/hide]

3x, you don't have to put quotation marke around the text after the hide=.[/quote]

yeah, but thats why i asked to use algebra to find the answer, b/c many problems may have obvious answers, but one may overlook some. so by using algebra, you can be 100% sure of your answer.


So my teacher missed the USPhO deadline by a week! :( I've preparing the test since last summer due to my love of physics, I contacted AAPT and they told me to come back next year, but I'm not going to be in high school next year... I was just wondering if there is any space available at any high school in the U.S.?  Like sometimes kids registered for it and decided maybe not to take it?  I'm dying right now...

We might have some extra spots. I dunno though. I'll have to ask. Where are you from?

I'm in MA, but i have no problem travel to MI to take the test.  Can you please talk to your taecher tomorrow to see if there is any openings?  Please let me know asap, thank you so much!

Yea, sure... Our test is gonna be at 10am on Jan 29th. I'll talk to my teacher on Friday and give you a definitive answer tomorrow. By any chance, are you from Acton, MA?

If you want to take it on the weekend, ICAE is offering the test on the 24th at 11:30a, $ \$10$, [url]http://www.icae.org/[/url].  Email Dr. Khetan at [url]rkhetan@sbcglobal.net[/url].

My teachers says we have a spot. Decide whether you're gonna take in or not at our school.

PM me your name.

Our school's address is 4777 Northfield Pkwy, Troy, MI 48098. Hopefully I'll see you here.


A number is selected at random from the set of all five digit numbers in which the sum of the digits is equal to $43$. What is the probability that this number is divisible by $11$?

[quote="t0rajir0u"]Psh.  I thought you told me this problem was hard.

[hide="Solution"] Well, let the digits be $a, b, c, d, e$ (in order) and so forth, right?  Then $a+b+c+d+e = 43$ and we want $a-b+c-d+e \equiv 0 \bmod 11$.  So

$43-2(b+d) \equiv 0 \bmod 11$

[b]Case:[/b]  $b+d = 5$.  Out of $10 \cdot 10$ possibilities for the ordered pair $(b, d)$, this covers $6$.

[b]Case:[/b]  $b+d = 16$.  Each can only range from $7$ to $9$, so there are $3$ more possibilities.

The next case is too large.  $9$ possibilities are covered out of $100$ equally likely cases, so the probability should be $\boxed{ \frac{9}{100}}$.

However, it's late, so this is likely to be wrong :P [/hide][/quote]

Not hard, just annoying. Plus, I don't think the $100$ cases are equally likely... like in your first case, we have $a+c+e = 38$, which actually has no solutions. The second one has $a+c+e = 27$, so $a = c = e = 9$. So... whoa, I guess I'm done. There are only $3$ possibilities, I guess, but then we just need to count the total number.

it is not like there are that many numbers with that property...

[hide="those being..."]9,9,9,9,7
9,9,9,8,8

and permutations...[/hide]

[quote="paladin8"]like in your first case, we have $a+c+e = 38$, which actually has no solutions. The second one has $a+c+e = 27$, so $a = c = e = 9$. So... whoa, I guess I'm done. [/quote]

Oh yeah.  (Yep, it was definitely late...)

[hide="So then..."] Going off of Altheman's discovery, there are $5$ permutations of $99997$ and $10$ permutations of $99988$, of which $3$ produce a number divisible by $11$, so the actual probability is then $\frac{3}{15}= \frac{1}{5}$.  Maybe. [/hide]

Yep $\frac{1}{5}$ is correct.

Remember seeing it on a Mathcounts Warmup


Given $\Delta ABC$ equilateral, with $X\in[A,B]$. Then we define unique points Y,Z so that $Y\in[B,C]$, $Z\in[A,C]$, $\Delta XYZ$ equilateral.

If $Area\left(\Delta ABC\right) = 2 \cdot Area\left(\Delta XYZ\right)$, find the ratio of $\frac{AX}{XB},\frac{BY}{YC},\frac{CZ}{ZA}$.

take ABC to have sidelength x.

A trivial angle chase shows that the other 3 small triangles besides XYZ are similar.  Because XYZ is equilateral, the triangles are congruent.  Suppose the sides of the small triangles are $a, b$ and a side of XYZ.

Now ABC has area $\sqrt{3}x^2/4$ so that the area of the small triangle is $\sqrt{3}x^2/24$.  But it is also $ab\sin 60^{\circ}/2$, so that $x^2 /6 = ab$.  Finally, $a+b = x$.  So $(a+b)^2 = 6ab$ implying that $a^2 + b^2 = 4ab$.  Put $a/b = m$, the desired ratio.  Then $m^2 -4m + 1 = 0$ implies $m = 2 \pm \sqrt{3}$.


Find all functions $ f: \mathbb{R}\rightarrow \mathbb{R}$ such that
$ f(2x\plus{}f(y))\equal{}x\plus{}y\plus{}f(f(y)),\ \forall\ x,\ y\in\mathbb{R}$.

Functional equations is not high school basics.

Moderator, please move this thread.

[quote="Arrange your tan"]Functional equations is not high school basics.
This needs to be moved.[/quote] :!:

Is it possible for a continuous function f on [0,1] to be such that \int_0^1 xf(x)=1 and \int_0^1 x^n f(x)=0 for n=0,2,3,4,...?


Raskin and Bobbins cookie parlor offers 100 different varieties of cookies. If 72 varieties contain chocolate, 39 contain nuts, 16 contain oatmeal, 13 contain both chocolate and oatmeal, 10 contain both oatmeal and nuts, 21 contain both chocolate and nuts, and 9 contain all three ingredients, how many varieties contain none of these ingredients?

is there any formula or method to do these types of problems. If so, can you guys tell me it? :)

I don't know one. But drawing a venn diagram and subtracting might help.  :|

Maybe precalculus and up know that probably

[hide="Using PIE"]Add the singles, subtract the doubles, and add the triple. You get the total amount of cookies with one of those three.

$72+39+16-13-10-21+9=92$

$100-92=\boxed{8}$[/hide]

Think of it as a Venn Diagram:

[img]http://img132.imageshack.us/img132/8808/venndiagramtz9.jpg[/img]

The total number of items is...

$A+B+C-D-E-F+G$

If you think about it, it makes sense. :)

This is because in the venn-diagram above, we only want to count D once, but D is a part of both A and B. Then, when we add A, B, and C, and subtract D, E, and F, we add G three times, and subtract it 3 times, so we need to add it once more.

OH WOW!!!! Thanks! I am glad it has something to do with old vennyyy!!!!!

Grr.. I absolutely hate Venn Diagrams. PIE can be extended for any number of of things by the way, it just gets more complicated.

Venn Diagrams are a good resource for [i]learning[/i] PIE (and are definitely not a bad thing), but they're not as good as PIE for much larger sets of numbers. For example, once you have four or more circles in the diagram (or four or more flavors, in this problem), Venn Diagrams will no longer work, because they do not show every set combination.

[quote="anirudh"][quote="now a ranger"]same here. venn diagrams are really annoying[/quote]

That's why there's something called PIE!  :wink: Anyway, PIE can be really helpful, as you don't have to draw venn diagrams.[/quote]

I think the point that was trying to be made was that Venn Diagrams are useful for teaching people what PIE is and why it works, how to apply it, etc.


MIT college Stanford Harvard Yale Princeton search

I am currently interested in the college MIT, however I am slightly undecided for one reason. Does it really matter where you get your undergraduate degree? After all, its the graduate degree that matters right? So, what is the point of going to a top tier school thats costs over 40K a year and having over 160K in student loans when I can go to lets say for example the University of Washington at a much affordable price and then transfer to MIT for graduate school?

Also, does going to a top tier school as an undergraduate equal a better undergrad education?  Please give me advice because the questions I have posted have been hooked in my mind.

Not saying what i did was best, but i assessed my values and goals and figured this out:

I'm going to graduate school [dont know if you intend on it]... but my first choices were MIT [like you] and Stanford as well, i was relatively crushed when i didnt get in, but i figured the ppl going there were more qualified

but i figured, "take money and run"... just about anyone on these forums has a pretty dayum good head on their shoulders, and you should be able to get a gooood amount of merit based financial aid at a pretty good college [for instance, for me that would be OSU or Miami University of Ohio]... go to a good school [not great like MIT], and do really well there under the title of some scholarship, and then go to a great graduate school

that way i still can apply for jobs with the title of a really good school, and save a LOT of money on undergraduate school

btw: look into post-secondary enrollment and AP classes because they all can transfer to any good local colleges [like what happened w/ me at miami of ohio], that way you can take higher level classes sooner and if you graduate a year or two early, it looks even better for graduate school

but just my $.02

edit: i was in your exact situation last summer, so my advice may not be the best cause i still havent exactly experienced the results of my decision

This discussion, in various different flavors, has appeared many times on this forum.  Try perusing past threads to see what people have had to say.  I think the notion that "only your graduate degree matters" is obviously a partial truth -- later, tougher credentials carry more weight in many circumstances.  On the other hand, you may not want to go to graduate school five years from now.  And, of course, one has to get in to graduate school in the first place.

Also, and you can probably find me making this point repeatedly on this forum, the fact that MIT (and, of course, the other big, established private universities) charge fourty thousand dollars in tuition is not equivalent necessarily to an individual paying fourty thousand dollars in tuition.  In the past few years, an education at Harvard, Stanford, Yale, Princeton (not by any means an exhaustive list) has gotten significantly cheaper for families earning 80K a year or less.  Now, some students can earn a free ride via merit scholarships at their state universities, and for many (free ride or otherwise) that's still going to be the more affordable option, but it's not necessarily as much more affordable as it appears.

when you say "its the graduate education that matters" you're only talking about what people will think of you on paper, on your resume. I believe that the most important part of college (especially undergraduate) is the people you will be around, because they will be your motivation (or lack thereof) to learn, your desire to excel, your compass for your values. To me, thats worth the amount I'm paying for a "top tier" education. To me, that will shape me more than what i learn in lectures and classrooms, and if i do go to graduate school, I won't be regretting spending 4 or 5 years with people just like me at a "top tier" school. College admissions is like Hogwarts' Sorting Hat. a large part of the sorting is your academic prowess, but there is a significant part of the admissions process that takes into account you; your personality. So yes, in a sense graduate education is the important part because that will be what employers will see most. but you should also think about the experiences with your future classmates. not all undergraduate schools are made equally. a college is mostly made up of its students. and those students will push and pull you in a different direction at each university.

[quote="Chion"]When you say "its the graduate education that matters" you're only talking about what people will think of you on paper, on your resume. I believe that the most important part of college (especially undergraduate) is the people you will be around, because they will be your motivation (or lack thereof) to learn, your desire to excel, your compass for your values.[/quote]

I agree with this, and that is one of the reasons I am inclined, as a parent, to advise my children to wait till near the "normal" age to enroll in college, rather than go early to some nearby and inexpensive college, as some of my friends have their children do. Either possibility exists for learning the ACADEMIC content of college for some eager learners, but other aspects of the college experience are best

1) experienced at near the age of most college students, with other college students of similar age,

and

2) experienced at more highly selective colleges, with other students capable of being admitted to such colleges.

Reasonable minds can differ (and perhaps will, in this thread  :)  ) but that is how I resolve the trade-offs for my own family.

P.S. I will also back up JBL's point that the top colleges, those with scary list prices, offer a LOT of financial aid, so it is unlikely you will borrow much money to go to such a college if you are admitted. Apply for admission, and apply for financial aid (that takes your parents' help) and see what happens.

relative to what you make in a lifetime, 160K is not nearly as much as you think it is; I think it's always best to go to the better school to be around smart people

Unless you got a great job right out of college, you'll be paying that 160k off til you're 40-50+. Maybe even if you get a great job.

If it comes to that, I hardly see going prestigious as being worth it.

Your 40-50 numbers are way off base; I know a lot of MIT grads who made 200K in their first year out - that pays it off in a couple years; you're much much less unlikely to be an outlier like this at other schools; so if you want to be extraordinary, MIT is the place to do it
The better engineering jobs will pay 80+ out of college, almost any decent finance job will net you 100 all-in easily in your first year
A lot of peoples' senses of what you can make are somewhat skewed, you'd be surprised
Even if it took me a lifetime to pay off, I'd rather go to MIT just for the experience... college is the best 4 years of your life!

hey, It really doesn't matter where u go at undergrad.. but you should go to MIT just because you will learn a lot there... more than in many places.. and you will meet people who are very good in your aea of study..

but if you just care about getting to a good graad school and making big bucks in the future.. it doesn't really matter... but that's kinda of inmoral? right?

the thing is that MIT is expensive and your parent's could tell you.. im going to pay 50K bucks just for you to be a Mathematician!!?!?!....or somebody  who will not be a millionaire!??!
but try to get a good scholarship..

i am personally going now to do my undergrad at MIT..
and im going to be sincere... MIT is not the ideal place where i wan't to be.. i don't like its extreme competition, cuz it sometimes affects the social behavior of the people and it is not my favorite atmosphere..
but i really want to learn good good math and meet and work with many great people in math... i got in, i got a scholarship, so i won't reject the opportunity...

but if you don't get in.. it's ok... yo could still go to any place and be good in what u love

Most MIT undergraduate alumni I have met claim that it made economic sense to get an undergraduate degree from MIT, even with the high list price there (which not all of them paid, because many of them got greater or lesser amounts of financial aid). Apply and see what's on offer before deciding whether or not to attend.

I suppose my age forecast was a bit off, but I'm just not a fan of debt. Especially 160k.

it doesn't take a mathematician to realize that is a lot

There are few better ways to avoid going into debt later for something else than going into debt to get a truly high quality undergraduate education.

[quote="River Phoenix"]MIT is not the ideal place where i wan't to be.. i don't like its extreme competition, cuz it sometimes affects the social behavior of the people and it is not my favorite atmosphere..

Are you kidding? MIT is HIGHLY noncompetitive, especially compared to other schools. The atmosphere is and has always been "all the students vs. the institute" rather than "all the students vs. each other"[/quote]

well, i haven't get there.. but what i've heard is that they give exessive ammount of work, and i think that somewhat creates a competitive atmosphere.. don't know.. students vs. the institute is a type of competition, don't you think?
for example, compared to harvard... Harvard will also offer you a great preparation in math.. but it is a little bit more relax in terms of non-math work.
i am going to MIT mainly because of its combinatorics ( that's my main interest, i know i will discover a lot of beautiful things too).. I didn't get into harvard but almost all my IMO friends are going to harvard..

[i]students vs. the institute is a type of competition, don't you think?[/i]

no, it's a kind of cooperation
If you want to do combinatorics, Alex Postnikov is a badass, find him

I'm going to third tokenadult and Chion on this.  I went into my college search thinking something like this:

1. Where I go for undergrad doesn't really matter on my resume.
2. I'm intelligent and motivated enough that I'll make my education good wherever I go.
3. Therefore, I can go pretty much anywhere and be just fine.

However, not to knock on any of the other schools I was considering (as they're great places), I think picking Stanford was one of the best decisions I've ever made.  I would not be the person I am today if I had gone to state school.

One of the realizations I've made since finishing my first year there was that I was used to being the academic star in high school.  And had I gone to state school, it would have been more of the same, most likely, though there would have been a few others like me.  But at Stanford, I'm surrounded by people who were quite like me in high school.  I'm no longer the superstar; in fact, no one really is.  Or everyone is, depending on how you want to look at it.  And that's my argument as to why it's worth it to go to a highly selective school.

Postnikov is a super good friend!!

i had the great opportunity to meet him randomly 2 years ago in my country.. and we've keep in touch because he does the same kinda stuff that i like.. and we had dinner last time i went to cambridge!
iwanted him as an advisor but i heard he is only advising sophomores,.,,  :(

i applied to Stanley's seminar.. let see if i get in.. i really want to

You might still be able to get him as an advisor (he's really disorganized though, so it's questionable anyway :D)
My advisor is Denis Auroux, he's also really cool (a topology guy though)

I am just studying the content of the web page wrt Ph.D. admissions:

- http://www.eecs.mit.edu/grad/faqs.html

It says it is extremely competitive. They do not bother about usual test scores, e.g. GRE/GMAT. I mean everybody who dares to apply will get a score of about 800 anyway. Though I figured the language part is harder than IELTS (or TOEFL which is easier). I guess it requires some work to score higher than 600. Basically what do they judge you on? I mean the application deadline is quite early in Decembre. So they don't know how you did on your M.Sc. degree. So they can only consider your undergraduate degree. And top they probably already assume some publications and references from know researchers. Does anybody have some experience what importance is assigned to certain parts of the application? Thanks.

[quote="River Phoenix"]It will depend on your undergraduate research, grants, awards, as well as your undergrad grades and difficulty of curiculum, your letters of recommendation, and your perceived drive to do research...
what more can anybody say

MIT EECS grad school is very very very hardcore... my cousin got in but went to Harvard instead in order to go insane[/quote]

Yeah, I know that are some of the factors but I wanted to know how they value each attribute and on top what do you mean by grant? Do you assume any undergraduate gets money for guiding a research project? BTW how do they value if you have studied at several good, say TOP 30, universities in the world. You will have a M.Sc. degree but not finished by the time you apply. And you focussed more on your interests and say rejected M.Sc. offers from TOP 10/15 universities in the world assumed that the department of other TOP 30 universities is stronger than that. I am up to the challenge. What about the importance of practical exposure with some major companies or especially their research departments?
I am not afraid of the wordload. I am used to taking way more courses like, say, the average student. So are you capable comparing the respective schools of Stanford, Caltech, Carnegie Mellon, Berkeley and Cornell wrt Ph.D. admission issues and maybe under the constraints of the conditions mentioned above?

[quote="manuel"]
i applied to Stanley's seminar.. let see if i get in.. i really want to[/quote]

Hey, I applied to that one too.  Maybe we'll be classmates.

As far as the topic here, I'd like to point out that places like MIT sometimes give better financial aid packages than local or state colleges with a lower list price, simply because they have more money to give.  So don't be scared away by the $\$$45000/yr list price - it doesn't really mean anything.  The choice should come down to what kind of college atmosphere and educational background you're looking for.

yea i got a decent financial package...

hmmm you r maria right?

[quote="River Phoenix"]You might still be able to get him as an advisor [/quote]

How can i do this?

you get to choose your own advisor, and they can take on as many as they want; just insist

[quote="manuel"]even if I am a frosh?[/quote]

i don't understand the difference.. you choose your own advisor when you declare your major, which is usually at the beginning of the sophomore year
the freshman advisor is the same as the prof of your freshman advising seminar and is a completely different thing altogether


Let ABCD is convex quarilateral. Prove that;
$AB^2+BC^2+CD^2>\frac{DA^2}{3}$

Oke, I have a solution as following:
$\vec{AD}=\vec{AB}+\vec{BC}+\vec{CD}$. Square two hands ang used the fact:
$2\vec{AB}.\vec{BC}\leq2AB.BC$, we have conclusion for problem. Of coure the sign "=" don't happened


email
number theory unsolved
number theory

What does $\sigma$ represent?
Is it standard deviation?

I believe it's the sum of the divisors of $n$.

How do you calculate the sum of the divisors of $n$?

What do you mean?
We sum up all divisor of $n$, including $n$. There is a nice formulae via prime decomposition.

[quote="zhaobin"]prove that there is many unlimited a such that $\sigma(n)=a$ has no solution.[/quote]
Well, if $a=p^a$ with $p$ an odd prime, $a$ a positive integer , I suppose is not too hard to prove that tehre exists infinite values of $a$ fixed $p$ such that your equation has not solutions. Try in this way and remember that $\sigma$ is a multiplicative function.

Well in fact, if $n=p_1^{a_1}\cdots p_k^{a_k}$ [the standart prime descomposition] then $a_j+1$ is prime {if you can't see that i can explain deepest} for every $j$ then

case 1: $a_j=1$ then $p_j=p^\alpha-1$ which is NOT a prime (cause $p$ is an odd prime)!!!
case 2: $a_j>1$ then easily we show that $(a_j+1,p-1)\ne 1$ hence $p = 1 \ mod (a_j+1)$ for every $j$. And this case is harder to study, so good luck.

Bets regards.
RX the Crazy Math

[quote="Myth"]We sum up all divisor of $n$, including $n$. There is a nice formulae via prime decomposition.[/quote]
Can you show me this formula?

[quote="RobertuX"]

Well in fact, if $n=p_1^{a_1}\cdots p_k^{a_k}$ [the standart prime descomposition] then $a_j+1$ is prime {if you can't see that i can explain deepest} for every $j$ then

case 1: $a_j=1$ then $p_j=p^\alpha-1$ which is NOT a prime (cause $p$ is an odd prime)!!!
case 2: $a_j>1$ then easily we show that $(a_j+1,p-1)\ne 1$ hence $p = 1 \ mod (a_j+1)$ for every $j$. And this case is harder to study, so good luck.
[/quote]
Robertux,can you explain more about this?thank you. :)

[quote="Myth"]I have just invented completely different nice approach :)
Note that $\sigma(n!+i)>n!+n$ for all $i=2,3,...,n$. Since $\sigma(m)>m$, it follows that $|\{m\mid \sigma(m)\leq n!+n\}|\leq n!+1$. Therefore there are at least $n-1$ numbers $a$ in the set $\{1,2,...,n!+n\}$ s.t. $\sigma(m)=a$ has no solution.[/quote]
really nice. thank you.
but I stiil to complete RobertuX's. :(

[quote="Myth"]I have just invented completely different nice approach :)
Note that $\sigma(n!+i)>n!+n$ for all $i=2,3,...,n$. Since $\sigma(m)>m$, it follows that $|\{m\mid \sigma(m)\leq n!+n\}|\leq n!+1$. Therefore there are at least $n-1$ numbers $a$ in the set $\{1,2,...,n!+n\}$ s.t. $\sigma(m)=a$ has no solution.[/quote]
Not agree, can you prove there is NOT a prime $P_n$ suhch that $n!+1\le  P_n< n!+n$ because in this case $\sigma(P_n)=1+P_n\le n!+n$ !!!.
Best regards.

RX TCM

But dude! $2|n!+2,3|n!+3,\ldots,n|n!+n$ :? Those cannot be primes. Also note that you need not take $n!+1$ into consideration, since Myth only considered $n!+i,\ i\in\overline{2,n}$.

[quote="Myth"][quote="Pascual2005"]o take any prime $q=2^{2^m}+1$ and we get the result.[/quote]
Great joke!  :lol:  :lol:  :lol:[/quote]
Hey, he is trying to do, come onnnn!!!  :D  :D  :D

[quote="Myth"]I just wanted to say that $2^{2^m}+1$ is prime only for $m=0,1,2,3,4$, and it is uknown whether there are other such numbers. :)
Of course, I highly appreciate Pacual's work :)[/quote]
Well Myth, I was joking too  :D  :D  :D  :P  I apreciate your job in the forum. I am sure you are a good person and try people close to you becomes to be better mathematicians. Good job!!! :first:

This is what happens, I was stuck and it was the only think that came into my mind, but now I realise y proved that this sum cannot equal $5^t$ for all large $t$!, so there are infinitely many $a$'s.

So in fact what I said as a joke, because i didnt knew how to finish it, has lead me to the obvious solution which is obvious not nicer than Myth's solution!

I have quickly tried my approach here, but it fails. :(

[quote="Collins"]Myth, can you solve this:
Let $S=\{\sigma(n),n\in\mathbb{N}^*\}$.
For all $L\in\mathbb{N}$, can we find $a\in\mathbb{N}$ such that $[a,a+L] \cap S=\emptyset$?
Good luck :D[/quote]
Well I think is an interesting problem, but $a$ depends of $L$ or not? I have supposed that for every $L$ exists $a\equiv a(L)$ such that ....  anyway, you can put a new post cause people maybe don't read this one here.. ;)

Of course $a$ must depend on $L$. Otherwise, it would be absurd.

[quote="Collins"][quote="RobertuX"]Not agree, can you prove there is NOT a prime $P_n$ suhch that $n!+1\le  P_n< n!+n$ because in this case $\sigma(P_n)=1+P_n\le n!+n$ !!! RX TCM[/quote]
 :lol:  :lol:  :lol:
Very funny![/quote]
YES, I need to receive the FIELD MEDAL PRIZE for these  :D  :D , I am a teacher in the university but sometimes I don't know what happends, yesterday I spent 30 mins to draw with a friend  the line $x+y=1$, CRAZYYYY   :rotfl: but two days ago I corret 3.326 exams and more than 94% fails the exam  :(

RX TCM

[quote="RobertuX"][quote="pbornsztein"][quote="RobertuX"]but two days ago I corret 3.326 exams [/quote]

Are you joking?
Wow! I'm really impressed!

Pierre.[/quote]
No joking  :wacko: sometimes I want to disappear, and I correct all in a day, 7 hours.[/quote]
Although I don't get your meaning completly.but I think you are a stranged,crazy teacher. :lol:

[quote="RobertuX"][quote="Collins"][quote="RobertuX"]I corret 3.326 exams and more than [b][u]94%[/b][/u] fails the exam  :(
RX TCM[/quote]
Are you a good teacher? :D  :D  :D[/quote]
Well, I think, I sit with every student and I try he learns  :lol:  ;) , but the examinations usualy I dont see before they need to do!, so sometimes they made mistakes. Are you a good student?[/quote]
you are right. I'm not a good student :blush: But I try...
3.326 exams? multiple choice question papers? Why do not use machine?

[quote="zhaobin"][quote="RobertuX"]but two days ago I corret 3.326 exams

Are you joking?  No joking  :wacko: sometimes I want to disappear, and I correct all in a day, 7 hours.[/quote]
Although I don't get your meaning completly.but I think you are a stranged,crazy teacher. :lol:[/quote]
Well, sometimes I become a crazy teacher with green hair and crazy dresses  :D  :D
Last classes I was with BLUE hair.

RX

[quote="Collins"]Why do not use machine?[/quote]
Please, if you know wher I can buy, please send me an email   ;)  :D  :lol:

[quote="Bojan Basic"][quote="zhaobin"]prove that there is many unlimited a such that $\sigma(n)=a$ has no solution.[/quote]
Here is another solution:

First we note that $\sigma(15)=\sigma(23)$. Consequently, $\sigma(15\cdot 2^k)=\sigma(23\cdot 2^k)$. Now, if we apply $\sigma$ to set $\{1,2,3,...,23\cdot 2^k\}$ there would be at least $k+1$ pairs which give the same number as the result, and since $\sigma(n)>n$ there exists at least $k+1$ numbers $a$ less than $23\cdot 2^k$ such that $\sigma(n)=a$ has no solution.[/quote]
I don't get it.can you detail it?

I'm not sure which step you don't understand, but I'll try to make it as clear as possible:

1) $\sigma(15)=\sigma(23)$ cause $\sigma(15)=1+3+5+15=24$ and $\sigma(23)=1+23=24$;

2) $\sigma(15\cdot 2^k)=\sigma(23\cdot 2^k)$ for every $k$ cause $\sigma(15\cdot 2^k)=(2^{k+1}-1)\sigma(15)=(2^{k+1}-1)\sigma(23)=\sigma(23\cdot 2^k)$ (note that $2^k$ and $15$ are mutually primes, what holds for $2^k$ and $23$, too);

3) Considering the numbers $\sigma(1)$, $\sigma(2)$, $\sigma(3)$, $...$, $\sigma(23\cdot 2^k-1)$, $\sigma(23\cdot 2^k)$ we see that there is at least $k+1$ pairs of the equal ones between them (namely $\sigma(15)=\sigma(23)$, $\sigma(15\cdot 2^1)=\sigma(23\cdot 2^1)$, $\sigma(15\cdot 2^2)=\sigma(23\cdot 2^2)$, $...$, $\sigma(15\cdot 2^k)=\sigma(23\cdot 2^k)$);

4) Since $\sigma(n)>n$ we have $\sigma(any\ number\ greater\ than\ 23\cdot 2^k)>23\cdot 2^k$, so if we want to have $\sigma(n)\in\{1,2,...,23\cdot 2^k\}$ we find out that $n\in\{1,2,...,23\cdot 2^k\}$. On the other hand, since between the numbers $\sigma(1)$, $\sigma(2)$, $\sigma(3)$, $...$, $\sigma(23\cdot 2^k-1)$, $\sigma(23\cdot 2^k)$ there is at most $23\cdot 2^k-k-1$ different ones, we find out that there is at least $k+1$ numbers (call them $a$) from $\{1,2,...,23\cdot 2^k\}$ such that $\sigma(n)=a$ has no solutions.

5) Since $k$ may be arbitrarily large number, there is an arbitrarily many numbers $a$ with the desired property, what completes the proof.

I hope it is clear now, if it is not feel free to ask for more details.


Let $b,m,n\in\mathbb{N}$ with $b>1$ and $m\not=n$. Suppose that $b^{m}-1$ and $b^{n}-1$ have the same set of prime divisors. Show that $b+1$ must be a power of $2$.

Assume $m>n$.
By Zsigmondy's theorem, if $m \neq 2,6$, $b^m-1$ has a prime factor not dividing any $b^k-1$ for $k<m$. This especially holds for $k=n$, thus we get $m=2,6$ (and $b=2$ in the latter case).
If $m=2$, we have $b^2-1=(b+1)(b-1)$. Every prime $p|b+1$ also divides $b-1$, giving $p|2$. Thus $b+1$ can have only have the prime divisor $2$, giving the result.
If $m=6$, then we just have to check $5$ cases for $n$, left out now.

I know that a lot of people consider Zsigmondy's theorem to brutal, but since we can proof it on an elementary way and it kills really a lot of olympiad problems, I see no reason not to use it.

[To see what Zsiygmondy's theorem says, look at http://mathworld.wolfram.com/ZsigmondyTheorem.html ]

hello.unfortunately i didnt read Zsigmondys Theorem yet but lets check my solution:
 let m+n=k ,  now :using induction on k ($k\geq3): $
**consider $\forall m,n$ such that :$ k>m+n\geq1$ b+1 is power of 2.
now we prove it for m+n=k
consider n>m:

  if k=3  then n=2,m=1 wich this case is little obvious.
Lemma 1)n is not divisible by m: because $b^t-1$ has a prime factor not dividing any b-1 : it can easily proved by exponent lemma and this:$a^n-b^n>n(a-b)$

so $gcd(m,n) \neq m$

if gcd(m,n)=t $ \Longrightarrow gcd(b^n-1,b^m-1)=gcd(b^m-1,b^t-1) \Longrightarrow b^m-1  , b^t-1$ have the same set of prime divisors
and m+t <m+n=k .
so according to ** b+1 must be power of2

i think we can find the best solution for this problem in this link
http://www.artofproblemsolving.com/Forum/viewtopic.php?f=57&t=338898&p=1815036#p1815036

Yes but Zsigmondy's Theorem isn't much trivial!!

[quote=andria]It is trivial by using zigmondy theorem.[/quote]

A proof of Zsigmondy's theorem requires a lot of study and work !!

I think no $m,n,b$ statisfies problem's condition. Here is my proof.
Suppose $m$ is odd.
Let $d=\gcd(m,n)$ and $m=ad$. So $a,d$ are odd
Because $b^m-1,b^n-1$ have same set of prime divisors so $b^{ad}-1,b^{d}-1$ have same set of prime divisors.
Let $p$ be any prime such that $p\mid \dfrac{b^{ad}-1}{b^d-1}$. So $p\mid b^{ad}-1$ hence $p\mid b^d-1$.
It's also not hard to prove that $p$ is odd.
Let $j=ord_p(b)$. So $j\mid d$.
By lifting the exponent lemma;
$v_p\left(\dfrac{b^{ad}-1}{b^d-1}\right)=v_p(b^{ad}-1)-v_p(b^d-1)=v_p(b^j-1)+v_p\left(\dfrac{ad}{j}\right)-v_p(b^j-1)-v_p\left(\dfrac{d}{j}\right)=v_p(a)$.
So $a=\dfrac{b^{ad}-1}{b^d-1}=b^{(a-1)d}+b^{(a-2)d}+b^{(a-3)d}+...+1>1+1+1+...+1=a$ Contradiction.
So both $m,n$ must be even.
Assume $m=2^rc, n=2^sd$ when $c,d$ are odd and WLOG $r<s$
So $(b^{2^r})^{c}-1, (b^{2^r})^{2^{s-r}d}-1$ have same set of prime divisors which implies that $c$ is even.
So no such $b,m,n$ statisfies problem's condition.

I apologize to everyone for my solution being similar to that of ZetaX. :D But I'm beginner in [b]Zsigmondy's theorem[/b].I want to solve problem by using Zsigmondy's theorem.

WLOG $m>n$.Except for case1:$(b,m)=(2,6)$ or case2:$m=2$ and $b+1$ is power of $2$,Zsigmondy's theorem can be applied.If neither case1 nor case2,by Zsigmondy's theorem,∃$p$(prime) s.t. $b^m-1$ is divisible by $p$ but $b^n-1$ isn't divisible by $p$ which is absurd.If case1,the set of prime divisors of $b^m-1$ is $\{ 3,7\}$.That of $b^5-1$ is $\{ 31\}$,that of $b^4-1$ is $\{ 3,5\}$,that of $b^3-1$ is $\{ 7\}$,that of $b^2-1$ is $\{ 3\}$,that of $b-1$ is $\phi$.This is contradiction.Therefore case2 must hold,and then $b+1$ is power of $2$.The proof is completed.$\blacksquare$ :coolspeak:


ABCDEF is a regular hexagon with side length 6. Let m be the midpoint of EF. What is the area of pentagon BCDEm?

[hide="Solution"]Let n be the midpoint of BC. Drawing a diagram, we realize we can add a line through m and the midpoint of BC to make the area half the hexagon plus triangle mnB. Applying Pythagorean, we have the half of the hexagon is $27\sqrt{3}$. the triangle is just half of the base times height, or $9\sqrt{3}$. Adding, we get $36\sqrt{3}$.[/hide]


The student council at NHS is planning to sell Sweatshirts with the school logo for a fundraiser. The supplier of the sweatshirts has quoted the costs of production as: $500 for set up costs for the logo and$22.75 per shirt. If the student council plans to sell the sweatshirts for $30 each and would like to raise$5000 for student activities, what is the minimum number of sweatshirt they can sell?

$30x-22.75x-500=5000$ 30x=money gained, 22.75x+500=money spent. Subtract spent from gained to get profit. (x=number of shirts)


[quote="asintota"]$ 0.99999... \equal{} 1 \text{ ,if this is true so is}\ 0.8888... \equal{} 0.99999...$[/quote]

Wait, how did you get from the first step to the second step? (and no, its not true)

$ \text{Is not true? but } \displaystyle\frac{1}{3}\equal{}0.333...\\
\text{multiplying by 3 you got } 3\displaystyle\frac{1}{3}\equal{}0.999...$

You know the rule of converting the periodic numbers in fractions I haven't yet understand his logic.

$ 0.9999.....\equal{}\frac{9}{9}\equal{}1$     but  $ 0.777....\equal{}\frac{7}{9}$

$ \frac{7}{9}$ is not equal with $ \frac{9}{9}$

$ \text{I meant if }0.999.. \equal{} 1 \text{ because the difference is practically nothing so is }0.888... \text{with }0.999..$

$ 0.\overline{9} \minus{} 0.\overline{8} \equal{} 0.\overline{1}$, which isn't nothing  :wink:

Edit: My question was, how does $ 1 \equal{} 0.\overline{9}$ imply that $ 0.\overline{9} \equal{} 0.\overline{8}$? Indeed, $ 0.\overline{9} \equal{} \frac{9}{9} \neq 0.\overline{8} \equal{} \frac 89$

$ \frac{9}{9}\equal{}1>\frac{8}{9}>\frac{7}{9}$ this make untrue your hypothesis

$ \text{ok azjps so with that reasoning }0.999...\minus{}0.888...\equal{}0.111...\\
\text{so }1\minus{}0.999...\equal{}0.111... \therefore 0.999.. \not\equal{}1\\
\text{but this } \frac{9}{9}\equal{}0.999... \text{ says the contrary }$

In general,

$ 0.x_1x_2x_3 ... x_kx_1x_2... x_k ... \equal{} n$

where n is a fraction, each x is a digit, multiply the equation by the number of digits in the repeating block, in the case k. We now have $ x_1x_2...x_r.x_1x_2...x_kx_1x_2...x_k... \equal{} kn$
We now subtract n from both sides, leaving us with
$ (k \minus{} 1)n \equal{} x_1x_2 ... x_k$.
Now divide by (k - 1).

So in general, $ n \equal{} \boxed{\frac{x_1x_2...x_k}{k \minus{} 1}}$

Yeas maybe you are right but it was very funny when I thought.

The most rigorous proof I can think of is this:

$ 0.999\ldots \equal{} \lim_{n\to\infty}0.\underbrace{ 99\ldots9 }_{n} \equal{} \lim_{n\to\infty}\sum_{k \equal{} 1}^n\frac{9}{10^k}  \equal{} \lim_{n\to\infty}\left(1\minus{}\frac{1}{10^n}\right) \equal{} 1\minus{}\lim_{n\to\infty}\frac{1}{10^n} \equal{} 1$

Unfortunately, no proof will convince my classmates...

[quote="worthawholebean"][quote="Nerd_of_the_Ages"]In general,

$ 0.x_1x_2x_3 ... x_kx_1x_2... x_k ... \equal{} n$

where n is a fraction, each x is a digit, multiply the equation by the number of digits in the repeating block, in the case k. We now have $ x_1x_2...x_r.x_1x_2...x_kx_1x_2...x_k... \equal{} kn$
We now subtract n from both sides, leaving us with
$ (k \minus{} 1)n \equal{} x_1x_2 ... x_k$.
Now divide by (k - 1).

So in general, $ n \equal{} \boxed{\frac {x_1x_2...x_k}{k \minus{} 1}}$[/quote]

You're actually multiplying by $ 10^k$. So the final formula is $ n \equal{} \boxed{\frac {x_1x_2...x_k}{10^k \minus{} 1}}$[/quote]

Whoops, that's what I meant. Thanks for correcting my mistake.
Actually, I don't think you can really say Temperal's proof is more rigorous than the common 9/9 fraction one. Both are equally valid, it's just that one is more complicated.

I've seen normally smart people do stupid stuff, even after showing them the simple algebraic proof. Like the reasoning that 0.9999... is less than 1 because 1 - 0.999999.... = 0.0000....1. However, 0.000.....1 IS 0. We actually got in to a serious discussion of this is school during lunch, when when of my friends brought up the "disputed" 0.999.... = 1 thing. Among mathematicians, basically everyone holds that as truth.

$ 0.000...1$ isn't well-defined notation at all.  You can't tell me where the digit $ 1$ is.  Temperal's argument is correct.  The notation

$ 0.999...$

is [b]defined[/b] to mean

$ \lim_{n \to \infty} \sum_{k\equal{}1}^{n} \frac{9}{10^k}$

which is [b]equal[/b] to $ 1$.  Understanding this subtlety, however, requires a thorough understanding of the definition of a [url=http://mathworld.wolfram.com/Limit.html]limit[/url].

People who think $ 0.999... \neq 1$ make the implicit assumption that the map from a sequence of digits to a real number is a bijection.  This is [b]not[/b], in fact, the case (as the fact that $ 0.999... \equal{} 1$ shows).

In order to evaluate that limit, we are invoking a nontrivial property of the real numbers: the [url=http://en.wikipedia.org/wiki/Archimedean_property]Archimedean property[/url]. The ordinary rules of arithmetic tell us that the limit of $ 10^{\minus{}n}$ can't be any nonzero number (it's ten times itself), but they don't necessarily tell us that the limit exists at all.
There are two consistent alternatives here: $ 0.99999\dots\equal{}1$, or $ 0.99999\dots$ is not a number. The standard definitions of mathematics choose the first; we prefer to have more ways to write something down rather than fewer.

See also [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?&t=90033]here[/url].

[quote="t0rajir0u"]$ 0.000...1$ isn't well-defined notation at all.  You can't tell me where the digit $ 1$ is.[/quote]

As a matter of fact, I told the person something along the lines of that. You can't really say 0.000000.....1. You never "get to the 1." Infinite doesn't end. Yeah, kind of different, but kind of similar.

Umm, don't you mean $ 0.\overline{9} \equal{} 1$ ? Which is a ridiculously easy proof, simply have $ \frac{1}{3} \equal{} 0.\overline{3}$ and multiply both sides out by 3.

Prime factorization, please read the topic before posting. That proof has been posted and discussed already.

[quote="Seo-Yeon, Sohn"]sorry, but i can't understand what you mean.
0.9999999....=1/3 + 2/3
so it's 1.
but, 0.77777....=7/9 and 0.888888....=8/9[/quote]

yes... this is what we have been saying thoughout the entire thread. asintota was mistaken.


Prove that there are no positive integers $n$ and $k > 1$ that $3^{n^k} + 1$ is divisibly by 5.

by fermat, $3^m+1$ is divisible by 5 iff $m=2 mod 4$. thus $n^k$ must be divisible by 2, thus $n$ is even. but since $k>1$, $n^k$ is divisible by 4, contradiction.


Let $ a,$ $ b$ and $ c$ are positive numbers.
Prove that
1) $ \sqrt{\frac{a}{a+7b+c}}+\sqrt{\frac{b}{b+7c+a}}+\sqrt{\frac{c}{c+7a+b}}\geq1,$
2)$ \sqrt{\frac{a}{a+5b+c}}+\sqrt{\frac{b}{b+5c+a}}+\sqrt{\frac{c}{c+5a+b}}\leq\frac{3}{\sqrt7}.$
Disprove that
1)$ \sqrt{\frac{a}{a+6b+c}}+\sqrt{\frac{b}{b+6c+a}}+\sqrt{\frac{c}{c+6a+b}}\geq\frac{3}{\sqrt8},$
2)$ \sqrt{\frac{a}{a+6b+c}}+\sqrt{\frac{b}{b+6c+a}}+\sqrt{\frac{c}{c+6a+b}}\leq\frac{3}{\sqrt8}.$

Very nice, Yulia!
My second inequality is not true. Thank you!
It needs be the following inequality:
$ \sqrt{\frac{a}{a+3b+c}}+\sqrt{\frac{b}{b+3c+a}}+\sqrt{\frac{c}{c+3a+b}}\leq\frac{3}{\sqrt5}.$
Try to disprove him. :P


linear algebra
matrix
vector
linear algebra unsolved

Two complex square matrices A and B have the same rang and verify $ A=ABA$. Then $B=BAB$.

I'll tell you what: if it's linear algebra, and I could solve it, then you bet it's a heck of a lot easier than "not very hard"... :D

It's a well-known result that there are two invertible matrices $P,Q$ s.t. $PAQ$ is $diag(I_r,O_{n-r})$, where $r$ is the rank of $A$ (and $B$). We thus get $PAQ=(PAQ)(Q^{-1}BP^{-1})(PAQ)$, and we need to prove $Q^{-1}BP^{-1}=(Q^{-1}BP^{-1})(PAQ)(Q^{-1}BP^{-1})$, and since $Q^{-1}BP^{-1}$ has the same rank as $B$, we may very well assume that $A$ was $diag(I_r,O_{n-r})$ from the beginning.

From the condition $A=ABA$ we find that $B$ has $I_r$ as its submatrix formed by the first $r$ rows and columns. We need to show that $B=BB'$, where $B'$ is the matrix having the first $r$ rows the same as those of $B$, and the last $n-r$ rows all $0$. The first $r$ lines and the first $r$ columns are easily seen to coincide for $B$ and $BB'$, and the rest is easily deduced by analyzing cases when we add a line and a column to $I_r$ so that the determinant of the new $(r+1)\times(r+1)$ matrix is $0$. Sorry if I don't go into details, but it's hard to explain, but easy to see if you write it down.

The idea is to show that if the matrix obtained from $I_r$ by adding a column vector $u$ as its last column and a row vector $v^T$ as its last row (consider $u,v$ without element $a_{r+1,r+1}$) has determinant $0$, then $a_{r+1,r+1}=<v,u>$ (the scalar product of the two vectors).

Well, grobber, you know, difficulty is a verry relative concept. For me, who is zero in linear algebra, this wasn't trivial at all. If for you it is easy, then so be it.  ;)


inequalities
geometry
angle bisector
triangle inequality

In a triangle ABC  the lengths of the interior bisectors af angles A,B and C are denoted by

(L_a),  (L_b),  (L_c)  respectively

Prove that a(L_a),   b(L_b)  and   c(L_c)  are the sides of a triangle.

I assume that a(L_a), b(L_b), c(L_c) are products of the triangle sides with the internal angle bisector lengths. Let $a = BC, b = CA, c = AB$ be the triangle sides, $K, L, M$ the intersections of the bisectors of the internal angles $\angle A, \angle B, \angle C$ with the sides $a, b, c$ and $k = AK, l = BL, m = CM$ the angle bisector lengths. Then the products $ak, bl, cm$ do not necessarily obey the triangle inequality. Consider a point $P$ on the side $AB$, such that $\frac{AP}{AB} = \frac 1 4$ and let the vertex $C$ approach the point $P$, say on a normal to the side $AB$. Then

$a \rightarrow \frac {3c}{4}, b \rightarrow \frac c 4$

$k = \sqrt{bc \left ( 1 - \frac{a^2}{(b + c)^2} \right ) } \rightarrow \sqrt{\frac{c^2}{4} \left ( 1 - \frac{9}{25} \right ) } = \frac{2c}{5}$

$l = \sqrt{ca \left ( 1 - \frac{b^2}{(c + a)^2} \right ) } \rightarrow \sqrt{\frac{3c^2}{4}\left ( 1 - \frac{1}{49} \right ) } = \frac{6c}{7}$

$m = \sqrt{ab \left ( 1 - \frac{c^2}{(a + b)^2} \right ) } \rightarrow \sqrt{\frac{3c^2}{16} \left ( 1 - \frac{1}{1} \right )} = 0$

$ak \rightarrow \frac{3c^2}{10}, bl \rightarrow \frac{3c^2}{14}, cm \rightarrow 0$

and a position of the vertex $C$ exists, such $ak > bl + cm$. For the vertex $C$ approaching the point $P$ on a normal to the side $AB$, the triangle inequality for the products $ak, bl, cm$ breaks down when the angle $\angle C > 155^o$ (approximately).

Thanks YETTI for your counter-example.
My apologies to any members of the forum who attempted to prove my faulty submission.

Michael Niland