linear algebra
matrix
algebra
polynomial
inequalities
LaTeX

Suppose $ A$ is an n by n matrix.
- The main diagonal elements of A are all -2, except positions (1,1) and (n,n), which are -3
- The values on the diagonals directly above and directly below the main diagonal are all 1
- The remaining values are 0

For example, for n=5 we have:
[code]
-3  1  0  0  0
 1 -2  1  0  0
 0  1 -2  1  0
 0  0  1 -2  1
 0  0  0  1 -3
[/code]

Prove that the eigenvalues of $ A_n$ are all real and are all negative.

This is equivalent to showing that the eigenvalues of $ A_n \plus{} 3I_n$ are real and less than $ 3$.  Real follows by the spectral theorem.  $ A_n \plus{} 3I_n$ is the adjacency matrix of a graph $ G_n$ on $ n$ vertices constructed from a path graph to which a loop has been added at each vertex except the beginning and the end.  Since each vertex has degree at most $ 3$, the eigenvalues are less than or equal to $ 3$.  It's a general fact that if $ H$ is a proper subgraph of $ G$, the largest eigenvalue of $ H$ is strictly less than the largest eigenvalue of $ G$, and since $ G_n$ can be turned into a graph with largest eigenvalue exactly $ 3$ by adding self-loops at the beginning and end and an edge between them, the result follows.

Alternately, you could show that $ \det A_n \neq 0$, which is probably straightforward by row-reduction.  Incidentally, do you know the characteristic polynomial of $ A_n \plus{} 2I_n$?  It should be a straightforward perturbation of the corresponding Chebyshev polynomial.

The eigenvalues are real, simply because the matrix is real symmetric.

As for negative: you're asking for a proof that this matrix is negative definite. It's diagonally dominant, although not strictly diagonally dominant, and that should suffice as long as we can show that zero is not an eigenvalue.

Suppose $ v$ is an eigenvector. Let $ v_j$ be the element of $ v$ such that $ |v_k|\le |v_j|$ for all $ 1\le k\le 5.$ Multiply $ v$ by a scalar so that $ v_j = 1.$

Case 1: suppose $ j$ is $ 2,3,$ or $ 4.$ Then the $ j$th entry of $ Av$ is

$ v_{j - 1} - 2v_j + v_{j + 1} = v_{j - 1} - 2 + v_{j + 1}\le 0.$

That last inequality comes from $ |v_{j - 1}|\le 1$ and $ |v_{j + 1}|\le 1.$

But if $ Av = \lambda v,$ then the $ j$th entry of $ Av$ is $ \lambda,$ so we have shown that $ \lambda\le 0.$

Case 2: suppose $ j$ is $ 1$ or $ 5.$ WLOG, $ j = 1.$ Then

$ \lambda = (Av)_1 = - 3 + v_2\le - 2.$

So in either case, we have $ \lambda\le0.$ Now all we have to do is rule out $ \lambda = 0.$

As it turns out, it's quite easy to do row elimination in $ A.$

(Note: TZF, you should learn the $ \text{\LaTeX}$ syntax for matrices - see this part of the post.)

$ \begin{bmatrix} - 3 & 1 & 0 & 0 & 0 \\
1 & - 2 & 1 & 0 & 0 \\
0 & 1 & - 2 & 1 & 0 \\
0 & 0 & 1 & - 2 & 1 \\
0 & 0 & 0 & 1 & - 3\end{bmatrix}$ is row equivalent to $ \begin{bmatrix} - 3 & 1 & 0 & 0 & 0 \\
0 & - \frac53 & 1 & 0 & 0 \\
0 & 0 & - \frac75 & 1 & 0 \\
0 & 0 & 0 & - \frac97 & 1 \\
0 & 0 & 0 & 0 & - \frac {20}9\end{bmatrix}.$

That - row equivalence with no scalar multiplications and no row swaps - preserves determinant, so we may read off the telescoping product on the main diagonal that $ \det A = - 20.$ Since that is not $ 0,$ $ A$ is invertible, and that means that $ 0$ is not an eigenvalue of $ A.$ Hence, all of the eigenvalues of $ A$ are negative, also known as $ A$ being negative definite.

[quote="Kent Merryfield"]$ \det A \equal{} \minus{} 20.$[/quote]
Incidentally, $ A_n$ is the (negative of the) reduced Laplacian of the graph $ G'_{n \plus{} 1}$ obtained by choosing a vertex in a cycle graph $ C_{n \plus{} 1}$ and adding an extra edge from that vertex to each of its neighbors, so by [url=http://en.wikipedia.org/wiki/Kirchhoff%27s_theorem]Kirchhoff's theorem[/url] $ \det A_n$ counts the number of spanning trees of this graph, which is obviously nonzero.  In fact, a spanning tree can be obtained uniquely by deleting three edges in the following ways:

- Delete three of the "doubled" edges.  There are $ 4$ ways to do this.
- Delete two "doubled" edges and any of the other non-doubled edges.  There are $ 4(n \minus{} 1)$ ways to do this.

This gives $ ( \minus{} 1)^n \det A_n \equal{} 4n$.

[quote="Kent Merryfield"] ... Let $ v_j$ be the element of $ v$ such that $ |v_k|\le |v_j|$ for all $ 1\le j\le 5.$ ...[/quote]
I think you mean :
Let $ v_j$ be the element of $ v$ such that $ |v_k|\le |v_j|$ for all $ 1\le k\le 5$

[color=green][Yes. I fixed that. - K.M.][/color]

Thanks for all the interesting and varied replies!  :)

My particular solution was just an algebraic one:
$ \lambda \| \mathbf{v} \| ^2 \equal{} (A\mathbf{v})^T \mathbf{v}$
$ \equal{} ( \minus{} 3 v_1 \plus{} v_2) v_1 \plus{} ( \minus{} v_1 \plus{} 2 v_2 \minus{} v_3) v_2 \plus{}$ $ \ldots \plus{} ( \minus{} v_{n \minus{} 2} \plus{} 2 v_{n \minus{} 1} \minus{} v_n) v_{n \minus{} 1} \plus{} (v_{n \minus{} 1} \minus{} 3 v_n) v_n$
$ \equal{} \minus{} 2 v_1 ^2 \minus{} (v_1 \minus{} v_2)^2 \minus{} \ldots \minus{} (v_{n \minus{} 1} \minus{} v_n)^2 \minus{} 2 v_n ^2$
$ \leq 0$

with equality iff $ v_1 \equal{} v_2 \equal{} \ldots \equal{} v_n \equal{} 0 \iff \mathbf{v} \equal{} 0$

By the Spectral Theorem, there must be an orthonormal basis of eigenvectors, so $ \mathbf{v} \equal{} 0$ is not an option, so we must have $ \lambda < 0$.

[b]Note:[/b] This matrix originally came out of modeling a non-dissipative spring-mass system with multiple springs and masses. One of our homework assignments was to prove that the eigenvalues are negative, basically by saying that if they weren't, then energy conservation would be violated.

t0raji0u mentioned a graph-theoretic concept called the Laplacian. TZF was talking more about the real (one-dimensional) Laplacian, which is to say, $ \frac {\partial^2}{\partial x^2}.$

TZF's model is a discretized version of the wave equation, $ \frac {\partial^2u}{\partial t^2} \equal{} \frac {\partial^2u}{\partial x^2},$ but with some extra wrinkle at the boundaries. It looks like you have a different, stronger spring at each end of the chain. If you used the same strength spring to attach this to the walls, you would have the matrix that QuyBac called $ A$ in his decomposition.

Added in edit:

TZF, consider this variation. Take out the springs that connect you to the walls altogether. You should have the following matrix:
\[ \begin{bmatrix}\minus{}1&1&0&0&0\\1&\minus{}2&1&0&0\\ 0&1&\minus{}2&1&0\\ 0&0&1&\minus{}2&1\\ 0&0&0&1&\minus{}1\end{bmatrix}\]
What can you say about the eigenvalues of this? What physical meaning might you attach to an eigenvalue of zero?

[quote="TZF"]Thanks for all the interesting and varied replies!  :)

My particular solution was just an algebraic one:
$ \lambda \| \mathbf{v} \| ^2 \equal{} (A\mathbf{v})^T \mathbf{v}$
$ \equal{} ( \minus{} 3 v_1 \plus{} v_2) v_1 \plus{} ( \minus{} v_1 \plus{} 2 v_2 \minus{} v_3) v_2 \plus{}$ $ \ldots \plus{} ( \minus{} v_{n \minus{} 2} \plus{} 2 v_{n \minus{} 1} \minus{} v_n) v_{n \minus{} 1} \plus{} (v_{n \minus{} 1} \minus{} 3 v_n) v_n$
$ \equal{} \minus{} 2 v_1 ^2 \minus{} (v_1 \minus{} v_2)^2 \minus{} \ldots \minus{} (v_{n \minus{} 1} \minus{} v_n)^2 \minus{} 2 v_n ^2$
$ \leq 0$

with equality iff $ v_1 \equal{} v_2 \equal{} \ldots \equal{} v_n \equal{} 0 \iff \mathbf{v} \equal{} 0$

By the Spectral Theorem, there must be an orthonormal basis of eigenvectors, so $ \mathbf{v} \equal{} 0$ is not an option, so we must have $ \lambda < 0$.
.[/quote]
 I will add with real symmetric matrix  .
Now applied with Hermitian matrices . You can Interedted it example as:
$ A \equal{} \begin{bmatrix} \minus{} 5 & 2 \minus{} i & 0 & 0 & 0 & ... & ... & ... & 0 \\
2 \plus{} i & \minus{} 4 & 1 & 0 & 0 & ... & ... & ... & 0 \\
0 & 1 & \minus{} 2 & 1 & 0 & ... & ... & ... & 0 \\
0 & 0 & 1 & \minus{} 2 & 1 & ... & ... & ... & 0 \\
... & ... & ... & ... & ... & ... & ... & ... & ... \\
0 & 0 & 0 & 0 & 0 & ... & \minus{} 2 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & ... & 1 & \minus{} 4 & 2 \plus{} i \\
0 & 0 & 0 & 0 & 0 & ... & 0 & 2 \minus{} i & \minus{} 5\end{bmatrix}$
Prove that the eigenvalues of $ A$ are all real and are all negative.


Find the arithmetic mean of the prime numbers in this list:      21, 23, 25, 27, 29

first, we have to find the prime numbers
in that list, the prime numbers are: 23 and 29

the mean of those two numbers are $ \frac {23\plus{}29} {2} \equal{} \frac {52} {2} \equal{} 26$


complex analysis
complex analysis solved

prove the followig form of weierstrass theorem : if f has an essential singularity at z=zo, then for given c belongs to C
and epsilon > 0 for each delta > 0 there is a number a, |c-a|< epsilon, such that f(z)=a has infinitely many solutions in the disc
B(zo,delta) centered at a and of radius delta.

thx for ur help


algebra
polynomial
linear algebra
matrix
ratio
function

(Division by y is allowed because if y were 0, we would have 0 = 9 and 0 = 7 so we know y is never 0)
$\{ \begin{array}{l}y(x+y)^2=9 \\ y(x^3-y^3)=7 \\ \end{array}  \Rightarrow \{ \begin{array}{l}(\frac{x}{y}+1)^2=\frac{9}{y^3} \\ (\frac{x}{y}^3-1)= \frac{7}{y^4} \\ \end{array} $
$\rightarrow \frac{x}{y} = M$
$\frac{(M+1)^8}{3^8}=\frac{1}{y^{12}}$
$\frac{(M^3-1)^3}{7^3}=\frac{1}{y^{12}}$
$7^3(M+1)^8=3^8(M^3-1)^3$
$(M-2)(6561M^8+12779M^7+22814M^6+16341M^5+13474M^4+2938M^3+6351M^2+3098M+3452) = 0$

By $M^3 - 1 = \frac{7}{y^4}$ we know $M^3 - 1$ must be positive, so $M^3 > 1$ and $M > 1$ since it must be in the reals. With that we know the remaining 8th degree polynomial has no solution for $M$. So, $M = 2$ is the only solution. Plugging back in we get $y^3 = 1$ and $y^4 = 1$ which gives us $y = 1$. So, $2 = M = \frac{x}{y} = \frac{x}{1} = x$ and the only soln. is $(x,y) = (2,1)$.
Where did this system originate from and is there a nice non-ugly way to do it, i.e., factoring a 9th degree polynomial.

[quote="arqady"]Solve  system of equations in real numbers:
$\left\{ \begin{array}{l}y(x+y)^2=9 \\ y(x^3-y^3)=7 \\ \end{array} \right.$[/quote]

i was thinking that $a=x+y$ and $b=xy$ would help

$ya^2=9$

$y(a-2y)( a^2+b) )=7$

[hide="Here are two solutions for this unbearable system."]
[hide="The first method."] Observe that $0<y<x.$ Eliminate the variable $x$:

==============================
   x   $\cdot \ \ \ \ |\ yx^2+2y^2x+(y^3-9)=0$
 (-1) $\cdot \ |\ yx^3-(y^4+7)=0$
==============================
$2y^2\cdot x^2+(y^3-9)\cdot x+(y^4+7)=0$
$y\cdot x^2+2y^2\cdot x+(y^3-9)=0$
==============================

Here is the matrix of the coefficients which appear in the two above equations:

$\left( \begin{array}{ccc} 2y^2 & y^3-9 & y^4+7 \\ y & 2y^2 & y^3-9 \ \end{array}\right)\ .$ The above equations have at least a common root $(y)$

$\Longleftrightarrow\left| \begin{array}{cc} 2y^2 & y^4+7 \\ y & y^3-9 \\ \end{array}\right| ^2= \left| \begin{array}{cc} 2y^2 & y^3-9 \\ y & 2y^2 \ \end{array}\right| \cdot \left| \begin{array}{cc} y^3-9 &y^4+7 \\ 2y^2 & y^3-9 \ \end{array}\right|\Longleftrightarrow$

$y(y^4-18y-7)^2+3(y^3+3)(y^6+18y^3+14y^2-81)=0\Longleftrightarrow$

$4y^9+27y^6+28y^5+243y^3+378y^2-729=0\Longleftrightarrow$

$(y-1)(4y^8+4y^7+4y^6+31y^5+59y^4+59y^3+302y^2+680y+729)=0\Longleftrightarrow$

$\boxed {\ y=1\ \wedge\ x=2\ }\ .$[/hide][hide="The second method what is similarly with the Pork_Chop8-proof."]Denote $\boxed {\ x=t\cdot y\ ,\ t>1\ }\ .$

From the ratio of the two equations we obtain the relation:

$x-y=\frac{7(x+y)^2}{9(x^2+xy+y^2)}=\frac{7(t+1)^2}{9(t^2+t+1)}\ ;$

$\frac xt=\frac y1=\frac{x+y}{t+1}=\frac{x-y}{t-1}=\frac{7(t+1)^2}{9(t^3-1)}\ .$

From the first equation of the system we obtain the relation

$\frac{7(t+1)^2}{9(t^3-1)}\cdot \left[\frac{7(t+1)^3}{9(t^3-1)}\right]^2=9\Longleftrightarrow 7^3(t+1)^8=9^4(t^3-1)^3\ ,\ t>1$ a.s.o.
[/hide][/hide]

[hide] $y(x^3-y^3)=7 \Longleftrightarrow y(x-y)[(x+y)^2-xy]=7$ considering that : $y(x+y)^2=9$ we got:

$7=(x-y)(9-xy^2)$ the results follow
[/hide]

[quote="Altheman"]we want real solutions and that polynomial has no real solutions[/quote]
Why, Altheman? ;)

[hide="For Arqady"] $y(x+y)^2=9\ \wedge \ y(x^3-y^3)=7\Longrightarrow 0<y<x\ !$[/hide]

Thank you,Virgil.
My solution:
$\{ \begin{array}{l}y(x+y)^2=9 \\ y(x^3-y^3)=7 \\ \end{array} \Leftrightarrow\{ \begin{array}{l}x=\frac{3}{\sqrt y}-y\\ x=\sqrt[3]{\frac{7}{y}+y^3}\\ \end{array} $
Hence, $\frac{3}{\sqrt y}-y=\sqrt[3]{\frac{7}{y}+y^3}\Leftrightarrow$
$\Leftrightarrow y\sqrt y+\sqrt[3]{7\sqrt y+y^4\sqrt y}=3\Leftrightarrow y=1$ and $x=2.$ :)

Nice ! O.K. Because the left function is injective (yet strict increasing) !

arqady, where did this system come from? What inspired it to you?

[quote="Pork_Chop8"]arqady, where did this system come from? [/quote]
Source:by heart entrance examination in the Moscow University,1979 for jewish students.


http://www.artofproblemsolving.com/Wiki/index.php/2005_AMC_12A_Problems/Problem_7

 [geogebra]0a048c76c3f376ca7208ecbd61a858ed462693e4[/geogebra]

The solution given doesn't work if you use different labels like in the figure. And, the labels are slightly weird for example, A doesn't correspond to E in the solution. In a real competition, how would you know how to label stuff?

Usually I label squares ABCD, if there's another square it'll be EFGH or WXYZ, triangles are ABC.


prove that $ \forall a,b,c$ positive reals,
$ \frac{1}{a^2 \plus{} ab} \plus{} \frac{1}{b^2 \plus{} bc} \plus{} \frac{1}{c^2 \plus{} cd} \plus{} \frac{1}{d^2 \plus{}da} \ge \frac{4}{ac \plus{} bd}$

[quote="The Enigma"]prove that $ \forall a,b,c$ positive reals,
$ \frac {1}{a^2 \plus{} ab} \plus{} \frac {1}{b^2 \plus{} bc} \plus{} \frac {1}{c^2 \plus{} cd} \plus{} \frac {1}{d^2 \plus{} da} \ge \frac {4}{ac \plus{} bd}$[/quote]

It is an old result of Vasc . Actually the stronger one holds : $ \frac {1}{a^{2} \plus{} ab} \plus{} \frac {1}{b^{2} \plus{} bc} \plus{} \frac {1}{c^{2} \plus{} cd} \plus{} \frac {1}{d^{2} \plus{} da}\geq\frac {2}{\sqrt {abcd}}$ , and it is pretty easy to prove using Cauchy-Schwartz .

i am sorry but i cant prove the stronger inequality alex can you post the proof?

Since it's homogeneus assume $ abcd\equal{}1$ , and use the classical substitution $ a\equal{}\frac{x}{y}\ ,\ b\equal{}\frac{t}{x}\ ,\ c\equal{}\frac{z}{t}\ ,\ d\equal{}\frac{y}{z}$ . the inequality is equivalent with : $ \sum_{cyc}\frac{y^2}{x^2\plus{}yt}\ge 2$ .

Using AM-GM we have : $ LHS\ge \sum_{cyc}\frac{2y^2}{2x^2\plus{}y^2\plus{}t^2}$ , and now use Cauchy-Schwartz in Engel form .


A cube is randomly numbered from 1-20.  When dropped, it breaks into 7 pieces.  The probability that no two consecutive numbers share a piece is of the form $\frac{m}{n}$  Find $m+n$.

[quote="The Zuton Force"]What do you mean by, a cube is numbered from 1 to 20?[/quote]
I interpreted it as: given tiles numbered from 1 to 20, group them randomly in 7 piles. Find the probability no 2 consecutive numbers are in the same pile.


function
inequalities
inequalities proposed

Let $x,y>0, x\neq y, a=\frac{x}{y},b=\frac{y}{x}, z\in[x,y]$. prove that
\[\frac{a}{1-b}+\frac{b}{1-a}>\frac{x+y+z}{\sqrt[3]{xyz}}\]

does anybody have a solution? or is it too easy? say something..  :mad:

i have a nice solution but let's see what you've got. :lol:

At first we notice that $\frac{a}{1-b}+\frac{b}{1-a}= 1+\frac{x}{y}+\frac{y}{x}$. We have to prove
$1+\frac{x}{y}+\frac{y}{x}> \frac{x+y+z}{\sqrt[3]{xyz}}$.
Let us put $f(x,y,z)= \frac{x+y+z}{\sqrt[3]{xyz}}$. Then
$\frac{\partial f}{\partial z}= \frac{1}{3}\cdot \left(xyz\right)^{-\frac{1}{3}}\cdot\left((x+y)\cdot z^{-1}+2\right)$.
This expression is negative for $z<\frac{x+y}{2}$ and positive for $z>\frac{x+y}{2}$, so at the point $z=\frac{x+y}{2}$ the function $f(x,y,z)$ reaches its minimum value. Thus the maximum value of $f(x,y,z)$ for fixed $x,y$ and $z\in [x,y]$ can be reached only for $z\in\{x,y\}$. We will prove the inequality for $z=x$, because the second case in analogous.
The inequality becomes
$1+\frac{x}{y}+\frac{y}{x}>\frac{2x+y}{\sqrt[3]{x^{2}y}}$.
Transforming it and returning to the notation with $a$, we get
$1+a+a^{-1}> 2a^{\frac{1}{3}}+a^{-\frac{2}{3}}$.
Let $g(t)=a^{t}$ for any $t\in\mathbb{R}$. Then $g$ is strictly convex for any $a\in\mathbb{R}^{+}\setminus\{1\}$. We have $\left(1,0,-1\right)\succ \left(\frac{1}{3}, \frac{1}{3},-\frac{2}{3}\right)$, so by the Karamata inequality the desired inequality holds and is strict.

$1+\frac{x}{y}+\frac{y}{x}\geq \frac{x}{y}+\frac{y}{z}+\frac{z}{x}\geq \frac{x+y+z}{\sqrt[3]{xyz}}$
 :)

my solution:
$1+\frac{x}{y}+\frac{y}{x}=\frac{x}{y}+\frac{z}{z}+\frac{y}{x}\ge\frac{x+y+z}{\sqrt[3]{xyz}}$ :wink:


What is the greatest number that cannot be obtained by adding only 3's, 4's, or a combination of 3's and 4's?

Use the Chicken Mcnugget Theorem, which yields the largest number which cannot be expressed as $ mx + ny$. In this case m = 3 and n = 4.

$ 3 \cdot 4 - 3 - 4 = \boxed{5}$


Would anyone be willing to send me old Clemson Calculus Challenge problems?  They will not send out old copies of exams.  We have never gone, and it would be nice if we knew what to expect.  Thank You

If I still had mine with me I would...

If I remember right, it was mainly AP stuff with more of the harder AP stuff and maybe a few that are a little harder than AP.


geometry
rectangle
MATHCOUNTS
number theory
relatively prime

Yeah, I think it has posted atleast twice.

[quote="ckck"]I need help with this problem.

A 24 by 72 rectangle is split into 1 by 1 squares. A diaganol runs through a number of squares. How many of these 1 by 1 squares are passed through the diagonal?[/quote]

It has been posted many times actually, but for someone who's only been on here 2 weeks, they wouldn't know.

I do suggest looking through old posts, but here you go :

A 24 by 72 rectangle can be broken up into 1 by 3 rectangles as can be determined by dividing the dimensions by the GCF(24).  In order to get from one corner to the other the line would pass through 24 of these 1 by 3 rectangles.  In passing through each rectangle the line would pass through all 3 squares.  So the line passes through 24x3 = 72 squares.

If you play around with a few examples(I suggest starting with relatively prime dimensions) you'll find the formula is x + y - gcf(x,y) as was posted.  If you need proof of the formula, maybe you can get it from someone else in here.

[quote="mysmartmouth"]See the attachment that I created for MathCounts tutoring sessions:[/quote]

Do you have any other ones? If so, can you post it?

[quote="mysmartmouth"]Yes, I will find them and post them.  Are they helpful?  If so, I can make more.[/quote]

Yeah. There good practice. :)

I just remembered one of my former math team kids made a visual aide for this problem.  I'll attach it.  Not ground breaking or anything, but good for those visual learners:-)


In the image, ABCD is a quadrilateral where $ \overline{AB}\, \equal{} \,\overline{BC}$  ,   $ \hat{DAB}\, \equal{} \,80^o$  ,    and $ \hat{CBA}\, \equal{} \,40^o$.  A point $ P$ exists so that the triangle $ DPC$ is equilateral. Calculate the perimeter of the triangle $ APB$.

$ AB\, \equal{} \,BC\, \equal{} \,6$

$ CD\, \equal{} \,6$

I can't solve this problem no matter what. I added the $ L$ for reference.

Thanks guys!


geometry proposed
geometry
Locus problems
Geometric Inequalities
Germany
TST
Team Selection Test

Let $d$ be a diameter of a circle $k$, and let $A$ be an arbitrary point on this diameter $d$ in the interior of $k$. Further, let $P$ be a point in the exterior of $k$. The circle with diameter $PA$ meets the circle $k$ at the points $M$ and $N$.

Find all points $B$ on the diameter $d$ in the interior of $k$ such that
\[\measuredangle MPA = \measuredangle BPN    \quad \text{and} \quad    PA \leq PB.\]
(i. e. give an explicit description of these points without using the points $M$ and $N$).

If PM and PN intesect again the circle k at C and D respectively, it is well known by now that the center of k, the center of (CDP), the center of (MNP), that is, the midpoint of AP, and P form a parallelogram. It follows that B is the symmetrical of A about the center of k. I hope I am right...

Best regards,
sunken rock


Let a,b,c>0 ,then the inequality
$ (\sum\frac{a\plus{}b}{c})^2 \geq (36\minus{}9k)\plus{}k(a^2\plus{}b^2\plus{}c^2)(\frac{1}{a^2}\plus{}\frac{1}{b^2}\plus{}\frac{1}{c^2})$
holds if and  only if $ k \leq1$.

Let a,b,c>0 Prove that
$ 18 \plus{} 2(a^2 \plus{} b^2 \plus{} c^2)(\frac {1}{a^2} \plus{} \frac {1}{b^2} \plus{} \frac {1}{c^2}) \geq3(\sum\frac{a\plus{}b}{c}\frac{b\plus{}c}{a})$

sorry
the inequality is only true if a,b,c is 3 sides of 1 triangle


Okay I look through the list of avatars and mine isnt there!!!
I know this is not essential but it may end up as a bigger bug...
I use internet explorer on a windows operating system.
Help would be appreciated.  :maybe:

Did you just change your avatar? Because when I changed my avatar for a new one, it took a while (maybe a few hours or something) for it to appear in the classroom. Try during your next class...it should work.

No.
Actually, this problem has been bugging me for a couple weeks... :(

Also if you know, it would help if you (the person answering this) tell me what types of pic are accepeted in the classroom. (ie jpg,jpeg,gif...)

I think it has to do with the size.
Mine is the biggest it can be (80x100).
My previous one was smaller but it worked and was GIF.  Now I have a big PNG and it doesn't load in the classroom... :huh:

Just put something like
[code][img id=http://www.artofproblemsolving.com/Forum/images/avatars/776825435484df1668574f.png[/code]
 in the box when you click "...".

Okay that worked fine. Now if I resize the image as I have done, how do I get a new code for the pic?

Right Click / Control Click your avatar on
http://www.mathlinks.ro/profile.php?mode=viewprofile&u=37836
and choose Copy Image Location
Then when you click ... type [img id= and then CTRL-P (Edit->Paste) and click OK/Enter whatever it says.  That should work.  :)

If you mean that it is missing in the classroom, this problem has (I hope) been fixed.  The "missing avatars" should start appearing again tomorrow (Thursday).


Circle $l$ is tangent from inside to the circle $k$ , and touches the radius $PQ$ of the circle $k$ in the point $C$ . Let $A$ be the point on $k$ , and $B$ the point of the segment $CQ$ such that $AB$ is tangent to the circle $l$ which is perpendicular to $PQ$. Prove that $AC$ bisects $\angle PAB$.

If I correctly understand you, then, in order to make the problem correct, PQ must be not just a radius, but a diameter of the circle k. The problem was discussed at http://www.mathlinks.ro/Forum/viewtopic.php?t=23606 and http://www.mathlinks.ro/Forum/viewtopic.php?t=17446 .

  darij


$c<a,d<b$ prove that:
$(a+b+c+d)^2>8(ad+bc)$

Right, I hope you changed it into the correct version now.

[quote="ehsan2004"][quote="Arne"]Counterexample: take $a = d = 2$, $b = c = 1$.[/quote]

But he said $c<a , d<b$  ;)

and it's very easy  :lol:[/quote]

if you see the time arne posted and the time mathx edited his post, you will know why arne has the post. I really think that mathx should tell others he has edited the post.

He did:[quote]Last edited by Mathx on Wed Aug 31, 2005 7:53 pm; edited 1 time in total[/quote]but it does not matter either.


conics geometry circumcircle ellipse ratio vector invariant

Given triangle $ABC,P$ is an arbitrary point, $A'B'C'$ is cevian triangle of $P$, denote $G_{a},G_{b},G_{c}$ are centroid of $AB'C',BC'A',CA'B'$ and $I_{a},I_{b},I_{c}$ are midpoint of $PA,PB,PC$,reps. Prove that the lines $G_{a}I_{a},G_{b}I_{b},G_{c}I_{c}$ are concurrent at a point $P'$ and $P'$ lies on nine-point conic (conic is through points $I_{a},I_{b},I_{c}$,$A',B',C'$ and three midpoints of $BC,AC,AB$).
Note that: It is an extension of [url=http://mathworld.wolfram.com/JerabekAntipode.html]Jerabek point[/url]

Let us to say the triangle $\bigtriangleup A_{1}B_{1}C_{1},$ as the cevian triangle of $P,$ with respect to $\bigtriangleup ABC,$ instead of $\bigtriangleup A'B'C'.$

 At first we will study the configuration as the [b][size=100]gemath’s[/size][/b] problem states, in the particular case of which the cevian triangle of $P,$ is the orthic triangle of the reference one.

So, let $\bigtriangleup A'B'C'$ be, a given triangle, with $A'_{1}B'_{1}C'_{1},$ its orthic triangle and we denote as $I'a,$ $I'b,$ $I'c,$ the midpoints of the segments $P'A,$ $P'B,$ $P'C$ respectively, where $P',$ is the orthocenter of $\bigtriangleup A'B'C'$ and as $G'a,$ $G'b,$ $G'c,$ the centroids of $\bigtriangleup A'B'_{1}C'_{1},$ $\bigtriangleup B'C'_{1}A'_{1},$ $\bigtriangleup C'A'_{1}B'_{1},$ respectively.

It is easy to show that the midpoint $I'a$ of $P'A',$ is the circumcenter of $\bigtriangleup A'B'_{1}C'_{1}$ and similarly for the points $I'b,$ $I'c.$

So, the segment lines $G'aI'a,$ $G'bI'b,$ $G'cI'c,$ are the [b][size=100]Euler’s lines[/size][/b] of $\bigtriangleup A'B'_{1}C'_{1}$ $\bigtriangleup B'C'_{1}A'_{1}$ $\bigtriangleup C'A'_{1}B'_{1}$ respectively and based on [b][size=100]Thebault’s theorem[/size][/b], we conclude that they are concurrent at one point, so be it $T',$ lies on the nine point circle $(N'),$ of $\bigtriangleup A'B'C'.$

 The only one proof of [b][size=100]Thebault’s theorem[/size][/b] I have in mind, has already been posted in this Forum, at http://www.mathlinks.ro/Forum/viewtopic.php?t=113311

$\bullet$ We consider now, a parallel projection of the triangle $\bigtriangleup A'B'C',$ on a plane [[b]p[/b]], not parallel to the plane [[b]p'[/b]] of $\bigtriangleup A'B'C'.$

Based on the bellow [b][size=100]LEMMA  1[/size][/b], we conclude that the points $A,$ $Ia,$ $P,$ as the projections of $A',$ $I'a,$ $P'$ respectively, are collinear and also the point $Ia,$ is the midpoint of the segment $PA.$

Similarly the points $Ga,$ $Gb,$ $Gc,$ as the projections of $G'a,$ $G'b,$ $G'c$ respectively, are the centroids of the triangles $\bigtriangleup AB_{1}C_{1}$ $\bigtriangleup BC_{1}A_{1}$ $\bigtriangleup CA_{1}B_{1}$ respectively.

As the result of the parallel projection, we have that the segment lines $GaIa,$ $GbIb,$ $GcIc,$ are concurrent at one point, so be it $T,$ as the projection of $T'\equiv G'aI'a\cap G'bI'b\cap G'cI'c,$ lies on the nine point ellipse $(N)$ of $%Error. "bigtriangle" is a bad command.
ABC$ $($ passing through the points $Ga,$ $Gb,$ $Gc$ and $Ia,$ $Ib,$ $Ic$ and the midpoints of the side segments of $\bigtriangleup ABC$ $),$ as the projection of the nine point circle $(N')$ of $\bigtriangleup A'B'C'.$

$\bullet$ In your configuration now, based on the bellow [b][size=100]CONSTRUCTION PROBLEM[/size][/b], we can to consider the triangle $\bigtriangleup ABC,$ as the parallel projection of a triangle $\bigtriangleup A'B'C',$ such that its arbitrary cevian triangle $\bigtriangleup A_{1}B_{1}C_{1},$ to be the projection of the orthic triangle $\bigtriangleup A'_{1}B'_{1}C'_{1},$ of $\bigtriangleup A'B'C'.$

Hence, the results as the problem states, are true and the proof is completed.

[b][size=100][color=darkblue]LEMMA  1. – The parallel projection of three collinear points, on an arbitrary plane, are also collinear points, form two segments with the same ratio, as it is formed by the given points.[/color][/size][/b]

 It is easy to prove. If $A,$ $B,$ $C,$ are the given collinear points and $A',$ $B',$ $C',$ their parallel projections on an arbitrary plane [[b]p[/b]], then because of $AA'\parallel BB'\parallel CC',$ we conclude the collinearity of $A',$ $B',$ $C'$ and that $\frac{A'B'}{B'C'}= \frac{AB}{BC}.$

[b][size=100][color=darkblue]CONSTRUCTION  PROBLEM. – A triangle $\bigtriangleup ABC$ is given and let $\bigtriangleup A_{1}B_{1}C_{1},$ the cevian triangle of an arbitrary point $P,$ in the plane, with respect to $\bigtriangleup ABC.$ Construct another triangle $\bigtriangleup A'B'C',$ of which the given triangle is a parallel projection and also that the cevians $AA_{1},$ $BB_{1},$ $CC_{1},$ of $\bigtriangleup ABC,$ are the projections of the altitudes $A'A'_{1},$ $B'B'_{1},$ $C'C'_{1}$ of $\bigtriangleup A'B'C'.$[/color][/size][/b]

I hope that I am not mistaken in the solution of this problem I have in mind and I will post here later, after another checking of my notes.

Kostas Vittas.

Thank you vittasko for your nice solution and your interest. I see your solution is nice and true. My solution is base on properties of affine tranformation.
Given triangle $ABC$ and an arbitraty point $P$ then there is always an affine tranformation (difference a isometry) tranform them into triangle $A'B'C'$ and $P'$ such that $P'$ is orthocenter of $A'B'C'$.Indeed we contruct $ABC,P$ and $A''B''C''$ with $P''$ is orthocenter of $A''B''C''$ exist unique an affine tranformation $f$ tranform $ABC$ into $A''B''C''$ and let $P'=f(P)$ now we translate $A''B''C''$ by vector $\vec{P''P}$ (we denote that's tranlation by $T$ here $T$ is an isometry) into triangle $A'B'C'$ easily check $P'$ is orthocenter of $A'B'C'$, thus our the affine tranformation is $T\circ f$. By that property we easily seen my problem is only problem Thebault’s theorem through that tranformation note that midpoint , concurrent is invariant of affine tranformation, and through affine tranformation nine-point circle is tranformed into nine-point conic. :)


geometry
circumcircle
projective geometry
power of a point
radical axis

Four points in the order $A,B,C,D$ lie on a circle with the extension of $AB$ meeting the extension of $DC$ at $E$ and the extension of $AD$ meeting the extension of $BC$ at $F$. Let $EP$ and $FQ$ be tangents to this circle with points of tangency $P$ and $Q$ respectively. If $EP=60$ and $FQ=63$, determine the length of $EF$

Let $w$ the circumcircle of $ABCD$.

Constuct the circle $f = (F,FQ)$. $f$ intersects $w$ again in $Q'$, were $FQ'$ is also tangent of $w$.

Line $QQ'$ is the polar line of $F$ with respect to the circle $w$. $QQ'$ is also the radical axis of $f$ and $w$.

Since $F=AD \cap BC$ and $E = AB \cap DC$, the point $E$ lies on the polar line of $F$ w.r.t. the circle $w$
(see [url=http://www.cut-the-knot.org/cgi-bin/dcforum/ctk.cgi?az=read_count&om=390&forum=DCForumID6]here[/url] and [url=http://www.mathlinks.ro/Forum/viewtopic.php?p=316994#p316994]here[/url]).

Hence $E$ is on the radical axis of $f$ and $w$.
Hence $E$ has equal tangents to the two circles, that is, if $EH$ is tangent to $f$ then $EH=EP$.

So we construct the circle $e = (E,EP)$, and if $H$ is an intersection point of $e$ and $f$ then $EH$ is tangent to $f$.

Since $EH$ is tangent to the circle $f$, we have $EH \perp HF$.

$EH=EP=60$
$FH=FQ=63$

Hence for the hypotenuse $EF$ of the triangle $EFH$ we have:

$EF^2=EH^2+FH^2$

$EF^2=60^2+63^2$

$EF^2=7569$

$EF=87$


probability
geometry
geometric transformation
rotation

Three numbers, $a_1$, $a_2$, $a_3$, are drawn randomly and without replacement from the set $\{1, 2, 3, \dots, 1000\}$.  Three other numbers, $b_1$, $b_2$, $b_3$, are then drawn randomly and without replacement from the remaining set of 997 numbers.  Let $p$ be the probability that, after a suitable rotation, a brick of dimensions $a_1 \times a_2 \times a_3$ can be enclosed in a box of dimensions $b_1 \times b_2 \times b_3$, with the sides of the brick parallel to the sides of the box.  If $p$ is written as a fraction in lowest terms, what is the sum of the numerator and denominator?

[quote="mna851"][hide=" Hint "]WLOG, assume $\ a_1, a_2, a_3, b_1, b_2,b_3$ are selected from the set $\ {1,2,3,4,5,6}$ [/hide][/quote]Good idea. :D

[hide]WLOG, assume $\ a_1, a_2, a_3, b_1, b_2,b_3$ are selected from the set $\ {1,2,3,4,5,6}$. First of all, we know that one of the dimensions of the box must be $6$, and one of the dimensions of the brick must be $1$.

Now, if the box has two dimensions of $6$ and $5$, it can have any of the three remaining dimensions as its last side, so there are 3 possible configurations here. If the brick has two dimensions of $6$ and $4$, it can have $3$ or $2$ as its remaining side, for 2 configurations.

There are $\binom63=20$ possible configurations. Thus, the probability is $\frac5{20}=\frac14$ and the answer is $1+4=5$.[/hide]

Maybe i'm reading the problem wrong or my spatial thinking abilites have finally left me, but how could a 2 by 3 by 4 box fit in a 6 by 5 by 1 box?

[quote="mna851"]I don't think it can.  I'm not exactly positive what 4everwise did.  When I did this problem I just listed most of the combinations out.  There really aren't that many.[/quote]That's not good. How can I make my explanation better?  :(

That I'm trying to say is: The box must have dimensions $6\cdot a_2\cdot a_3$ and the block must have dimensions $b_1\cdot b_2\cdot 1$.

Then, we let $a_2=4$ or $a_2=3$ to find the dimensions that work.

As a list, these are $654$, $653$, $652$, $643$, and $642$.

3 of them from $6\cdot 5\cdot a_3$: $654$, $653$, $652$.

2 of them from $6\cdot 4\cdot a_3$: $643$, and $642$.

Oh yea well thats pretty much what I did.

Yeah I love that problem...when I solved it (the same solution as 4everwise's) after being intimidated by it before, is was like ...DAH?!?!?

Yeah I had no idea what to do on this problem at first :wallbash:

this is what I did at first, but when I saw that my answer would have been 1/4 -> 005, I got scared and tried really hard other ways of doing this. now I know I was fine...thanks

why is there no loss of generality when we reduce the problem to just 1,2,3,4,5,6?

because the actual dimensions of the brick and the box are irrelevant, as long as each of the bricks dimensions has a corresponding dimension of the box that is larger.

in other words, the 3 dimensions of the brick and the 3 dimensions of the box will have a specific order, like 1,2,3,4,5,6, but it doesn't matter what the actual dimensions are.

The first box fits into the second box, if, for some permutation $ \sigma$, we have:
$ a_{\sigma(1)} < b_1$, $ a_{\sigma(2)} < b_2$, $ a_{\sigma(3)} < b_3$

Now, when we pick six numbers from that set, it doesn't matter which exact [i]values[/i] we pick for the $ a$'s, but which rank they are within the list (largest, second largest ... smallest).

So, we can use any list of six distinct elements.

By the way, I think this is a really nice problem.  :)

[b]Edit:[/b][i] Same as above post[/i]

[hide=What I did
Let $a$ be the smaller box's dimension, and let $b$ be the bigger box's dimensions.
WLOG, we can let the $6$ chosen numbers be $1,2,3,4,5,6.$
We look for which $3-3$ split for ${a,b}$ means the conditions described.

Let's make a little chart:
$a:$
$b:$

Observe that $1$ must be part of $a$ and $6$ must be part of $b.$
From here, we just decide what could happen to each of $2,3,4,5.$
There are only $6$ arrangements, and trying every one of them, we realize that all but $1$ work. This one "bad" arrangement is when $a=1,4,5$ and $b=2,3,6.$

Total cases is $\binom{6}{3}=20.$

Thus $\dfrac{5}{20}=\dfrac{1}{4}.$
Add the numerator and denominator, and we get $5.$

[/hide]

[hide=What I did]
Let $a$ be the smaller box's dimension, and let $b$ be the bigger box's dimensions.
WLOG, we can let the $6$ chosen numbers be $1,2,3,4,5,6.$
We look for which $3-3$ split for ${a,b}$ means the conditions described.

Let's make a little chart:
$a:$
$b:$

Observe that $1$ must be part of $a$ and $6$ must be part of $b.$
From here, we just decide what could happen to each of $2,3,4,5.$
There are only $6$ arrangements, and trying every one of them, we realize that all but $1$ work. This one "bad" arrangement is when $a=1,4,5$ and $b=2,3,6.$

Total cases is $\binom{6}{3}=20.$

Thus $\dfrac{5}{20}=\dfrac{1}{4}.$
Add the numerator and denominator, and we get $5.$

[/hide]

Also, can someone tell me the hook-length formula solution and how and why it works here? (I have no experience with this formula)

[hide = Solution]
The same as everyone above choose $1,2,3,4,5,6$....

We color the numbers with $a, b$ such that the amount of $b$ does not exceed the number of $a$ from left to right. This is just $$\frac{C_3}{\binom{6}{3}} = \frac{\frac{1}{4} \binom{6}{3}}{\binom{6}{3}} = \frac{1}{4}$$where $C_n$ is the nth Catalan Number, so the answer is $5$.


Let $ n>1,k\in\mathbb{R}$ and $ 3^{n}\minus{}1\equal{}k\times n$. Prove that $ n\equal{}2p$

I don't understand your problem.
If $ n|3^{n}\minus{}1$ then $ 2|n$
$ k\in R$?

yes, I want to prove that n is a odd  ($ n\equal{}2k$) if n such that above condition.

PS  TTsphn: ý mình là chứng minh $ n$ chỉ có thể là số chẵn thì :  $ 3^{n}\minus{}1$ chia hết cho $ n$

Let $ p$ is least prime divisible $ n$ , $ d\equal{}ord_{3}(n)$ .

We have : $ 3^{n}\minus{}1\vdots p$,$ 3^{p\minus{}1}\vdots p$.

Then :$ n\vdots d,p\minus{}1\vdots d$.

-Case 1 . $ p>2$ then$ p\minus{}1\vdots q$, $ q$ is a prime so $ n\vdots q$ and $ p>q$ contracdiction .

-Case $ p\equal{}2$ we're done  :)

WE can solve it very easy as following:
$ p$ is smallest prime divisor of n
$ p|\gcd(3^{n}\minus{}1,3^{p\minus{}1}\minus{}1)\equal{}2$ so $ p\equal{}2$
I have some problems has same method example
$ n|3^{n}\plus{}2^{n}$ prove that $ 5|n$
$ n|(\frac{p\plus{}1}{2})^{n}\plus{}(\frac{p\minus{}1}{2})^{n}$ where p is a prime number .
Prove that $ p|n$
More...


conics
ellipse
geometry
trigonometry
vector
calculus
calculus computations

Once we know that the area bounded by a circle of radius $r$ is $\pi r^{2}$, we can find the length of the circle as follows. When the radius is increased by amount $h$, the area grows by $\pi((r+h)^{2}-r^{2})$. Dividing by $h$ and letting $h\to 0$, we find the length of the circle $L(C)=2\pi r$.

Now try this with an ellipse: the area bounded by an ellipse with semi-axes $a$ and $b$ is $\pi ab$. When both semi-axes are increased by $h$, the area grows by $\pi((a+h)(b+h)-ab)$. Dividing by $h$ and letting $h\to 0$, we find that $L(E)=\pi (a+b)$. But this is wrong. Why?

(In fact, $L(E)\ge \pi(a+b)$.)

Let $h$ be a small positive number, and consider the area between the ellipse with semi-axes $a$ and $b$ and that with semi-axes $a+h$ and $b+h.$ We have a narrow band of area. As mlok indicated, the area of this narrow band is $\pi(a+b)h+o(h)$. Now, what is the width of the band? If the width were $h,$ then we would be perfectly justified in dividing by $h$ and letting $h\to0.$ But is the width really $h?$

Consider a parametric representation of the ellipses. Let $P(t)=(a\cos t,b\sin t)$ and $Q(t)=((a+h)\cos t,(b+h)\sin t).$ $P$ is a point on the inner rim, and $Q(t)$ is a point on the outer rim. The distance between $P(t)$ and $Q(t)$ is $h.$

So does that clinch it? Not so fast - yes, $P(t)$ and $Q(t)$ were "corresponding" points in some vague sense, but was the distance between then "straight across" the band? To answer that, we need to know what direction "straight across" should be. For that we'll take the normal direction to the inner ellipse. (That's not identical to the normal direction to the outer ellipse, but the difference in directions is small for $h$ small.) A unit vector in that normal direction is

$\vec{u}=\frac{\langle b\cos t,a\sin t\rangle}{\sqrt{b^{2}\cos t+a^{2}\sin t}}$

Whereas a unit vector in the direction from $P(t)$ to $Q(t)$ is

$\vec{v}=\langle \cos t,\sin t\rangle.$

The two unit vectors are not identical. Their dot product, which is the cosine of the angle between them, is

$\vec{u}\cdot\vec{v}=\frac{b\cos^{2}t+a\sin^{2}t}{\sqrt{b^{2}\cos^{2}t+a^{2}\sin^{2}t}}.$

If $a\ne b$ and $t$ is not a multiple of $\frac{\pi}2,$ that cosine is less than 1. The distance $h$ from $P(t)$ to $Q(t)$ is not the distance straight across the band, it is the length of an angled path. The distance straight across is $h$ times the dot product given above, which is less than $h.$ Since the width of the band averages to less than $h,$ then the arclength must be greater than $\pi(a+b)$ to keep the area the same.


Problem. Give $ A \equal{} {(a_1;...;a_n)}$ and $ B \equal{} {(b_1;...;b_m)}$ with $ n \leq m$:
a. Is injection from $ A$ to $ B$?
b. Are injection and surjection from $ A$ to $ B$?

a. there's an injection as long as we can map any two elements in $ A$ to different elements in $ B$, and this is possible because $ n\leq m$.

b. for injection, see a. a map is a surjection if every element in $ B$ is the image of an element in $ A$. this is only possible if $ m\equal{}n$.


Tamantha wants to buy boxes in which to put her 77 compact discs. If each box holds 12 discs, how many does she need to buy?

She has 77 discs, and each box holds 12 discs. So we need to find $ \lceil{\frac{77}{12}}\rceil$, which is $ \boxed{7}$.

Note that $ \lceil{n}\rceil$ means the smallest integer greaten than than $ n$.


probability
floor function
trigonometry
limit
function
vector
modular arithmetic

For fixed integer m, let Xn have Binomial (n, 1/2) distribution. Let Yn = (Xn mod m) take values in Im = {0,1,2,..,m-1}
SHow that the total variation distance between the distribution of Yn and uniform distribution on Im converges to 0 as n -> infinity.

First of all, what is Yn????  Say Xn has probability (n choose k) (1/2)^n....does it mean Yn has probability from one of : (1 choose K)(1/2) ...... (m choose k) (1/2)^m???

And what does it mean by Yn take values in Im???

What we actually have is this. For $ 0\le k\le m \minus{} 1,$

$ P(Y_n \equal{} k) \equal{} \sum_{j \equal{} 0}^{\lfloor (n \minus{} k)/m\rfloor}P(X_n \equal{} k \plus{} jm) \equal{} \sum_{j \equal{} 0}^{\lfloor (n \minus{} k)/m\rfloor}\binom{n}{k \plus{} jm}\frac1{2^n}.$

My gut instinct is to seek a transform method. I'll find the Fourier transform (on $ \mathbb{Z}$) of the binomial distribution, then use Poisson summation ideas to find the discrete Fourier transform of the distribution of $ Y_n$ (which can be seen to be periodic).

Expanding on that idea:

Let $ f_n(x)\equal{}\sum_{k\equal{}0}^nP(X_n\equal{}k)e^{\minus{}2\pi ikx}.$

By the binomial theorem, we can compute that $ f_n(x)\equal{}\frac1{2^n}(1\plus{}e^{\minus{}2\pi ix})^n.$

Now let $ g_n(\ell)\equal{}\sum_{k\equal{}0}^{m\minus{}1}P(Y_n\equal{}k)e^{\minus{}2\pi ik\ell/m}.$

The theorem I'll quote (the proof is just a manipulation of sums) is that

$ g_n(\ell)\equal{}f_n\left(\frac{\ell}{m}\right).$ Hence, $ g_n(\ell)\equal{}\frac1{2^n}(1\plus{}e^{\minus{}2\pi i\ell/m})^n.$

But $ |1\plus{}e^{2\pi i\ell/m}|\equal{}2\left|\cos\left(\frac{\pi \ell}{m}\right)\right|.$ Since this is strictly less than $ 2$ for all $ \ell\ne0,$ we have this:

$ \lim_{n\to\infty}g_n(\ell)\equal{}\begin{cases}1,&\ell\equal{}0\\0&\ell\ne 0\end{cases}.$

This is exactly the discrete Fourier transform we would get from the "discrete uniform" distribution that has probability function $ \frac1m$ at each value in $ \{0,1,\dots,m\minus{}1\}.$

As for the nature of the convergence: all norms are equivalent in a finite dimensional vector space.

---

Now I claim that there was nothing particularly special at all about the binomial distribution with $ p\equal{}\frac12.$

Claim: Suppose $ X_j$ is an i.i.d. sequence of integer-valued random variables satisfying [condition to be named later]. Fix $ m.$ Define $ Y_n\equiv\sum_{j\equal{}1}^nX_j\pmod{m}.$ Then $ Y_n$ converges (in any reasonable sense) to the "uniform discrete" distribution on $ \{0,1\dots,m\minus{}1\}$ as $ n\to\infty.$

Can someone fill in a reasonable [condition to be named later] and prove this? The techniques of this post should be sufficient.

Sorry for my stupidness,
but where does the summation come from?
Yn = Xn (mod m)
So how does the P(Yn=k) is a sum?
Do you mind to explain this bit a little more?

Let's suppose $ m\equal{}3$ and $ n\equal{}8.$ Then $ X_8$ takes on the values $ 0,1,2,3,4,5,6,7,8$ with probabilities $ \frac1{256},\frac8{256},\frac{28}{256},\frac{56}{256},\frac{70}{256},
\frac{56}{256},\frac{28}{256},\frac8{256},\frac1{256}.$

Now, $ Y_8\equiv X_8\pmod{3}.$ $ Y_8$ takes on only the value $ 0,1,2.$

We have $ Y_8\equal{}0$ whenever $ X_8\equiv 0\pmod{3},$ which is whenever $ X_8\equal{}0,3,$ or $ 6.$ Hence:

$ P(Y_8\equal{}0)\equal{}P(X_8\equal{}0)\plus{}P(X_8\equal{}3)\plus{}P(X_8\equal{}6)\equal{}\frac{1\plus{}56\plus{}28}{256}
\equal{}\frac{85}{256}.$

We have $ Y_8\equal{}1$ whenever $ X_8\equiv 1\pmod{3},$ which is whenever $ X_8\equal{}1,4,$ or $ 7.$ Hence:

$ P(Y_8\equal{}1)\equal{}P(X_8\equal{}1)\plus{}P(X_8\equal{}4)\plus{}P(X_8\equal{}7)\equal{}\frac{8\plus{}70\plus{}8}{256}
\equal{}\frac{86}{256}.$

We have $ Y_8\equal{}2$ whenever $ X_8\equiv 2\pmod{3},$ which is whenever $ X_8\equal{}2,5,$ or $ 8.$ Hence:

$ P(Y_8\equal{}2)\equal{}P(X_8\equal{}2)\plus{}P(X_8\equal{}5)\plus{}P(X_8\equal{}8)\equal{}\frac{28\plus{}56\plus{}1}{256}
\equal{}\frac{85}{256}.$


function
vector
real analysis
real analysis unsolved

let $ C$ be  the algebra of functions defined on $ \mathbb{R}$,continuous  with complex values.

let $ p\in\mathbb{N}$ and  $ E(p)$ the set of all functions $ f$ belonging to $ C$  for which there are two real $ (A,B)\in\mathbb{R}^{2}$, such  that $ \forall x\in\mathbb{R}$ we have $ |f(x)|\leq\ A\plus{}B|x|^{p}$

show that: for every $ p$ we have $ E(p)\subset E(p\plus{}1).$

Use (weighted) AM-GM. $ |x|^p\le \frac{p}{p\plus{}1}\plus{}\frac{1}{p\plus{}1}|x|^{p\plus{}1}$, so $ A\plus{}B|x|^p\le \left(A\plus{}\frac{pB}{p\plus{}1}\right)\plus{}\frac{B}{p\plus{}1}|x|^{p\plus{}1}$.

thanks jmerry!

I have another question:

how to prove that the vector space $ E(p)$  is infinite-dimensional?

$ E(p)$ certainly contains all bounded functions.
Let $ f_i$ be a  nonzero continuous function bounded by $ 1$ where $ f$ vanishes outside the interval $ [i,i\plus{}1]$. Then the $ f_i$ are independent.


I am really stuck on this one, any input?

Let S be the set of ordered pairs of integers that are defined in the following
way:
• (0, 0) 2 S.
• If (a, b) 2 S then (a + 2, b + 3) 2 S.
• If (a, b) 2 S then (a + 3, b + 2) 2 S.
Prove the following:
For every element (a, b) in S, we have that a + b is divisible by 5.

Thanks guys

[hide]Every ordered pair can be written as $ (2x \plus{} 3y, 3x \plus{}2y)$ for nonnegative integers $ x,y$. Also $ 5x \plus{} 5y$ is divisible by $ 5$.[/hide]

How do you know that, say $ (1,1)$ in not in $ S$? I mean the following $ S$,

$ S\equal{}\{(2x\plus{}3y,3x\plus{}2y),(1\plus{}2s\plus{}3t,1\plus{}3s\plus{}2t): x,y,s,t\text{ non negative integers}\}$

also satisfies the 3 conditions but makes the claim not true.

My point is that the definition of $ S$ doesn't say that $ S$ has $ (0,0)$ as its only "initial point", does it? Or perhaps it does?

Unfortunatly the text was not formatted properly. But you can assume that in the places where the number (2) are next to the round brackets are there to mean that the orderd pair belongs to S.

In other words:

(0,0) belongs to S
(a,b) belongs to S

and so forth.

[hide="Solution"]
We are given that the transformation are $ (x,y) \rightarrow (x \plus{} 2,y \plus{} 3)$ and $ (x.y) \rightarrow (x \plus{} 3,y \plus{} 2)$

Consider $ S(x,y) \equal{} x \plus{} y$

Clearly for $ 5|S(0,0)$

Assume that $ 5|S(x,y)$ for all points which have been generated so far.

Then we can go to two more points. Consider one of them (the other one is obvious once the other is shown.

$ S(x \plus{} 2,y \plus{} 3) \equal{} x \plus{} y \plus{} 2 \plus{} 3 \equal{} x \plus{} y \plus{} 5$ But $ 5|x \plus{} y$ therefore $ 5|x \plus{} y \plus{} 5 \equal{} S(x,y)$
[/hide]

When you write 5|S(0,0) what do you mean by 5bar?

Technically this problem is false as packham's point is legitimate, though it's clear what the intent is. There's two fixes I can see.
1. Define a 2-dimensional sequence than a set.
2. Let $ T$ be the intersection of all such sets $ S$ and prove stuff about $ T$ instead.


Find the positive difference between the total number of rectangles and the total number of squares in a 5X3 grid. (please show how the number of recs and squares was acquired)

[hide="Solution"]WLOG, assume $ n\geq m$ in an $ m\times n$ grid.

A rectangle is defined by two horizontal and two vertical lines. There are $ \binom{m + 1}{2}\cdot\binom{n + 1}{2}$ rectangles.

In the case of squares only, two horizontal lines and one vertical line define a square (WLOG, the second vertical line will always be below the first one). There are $ n\cdot\binom{m + 1}{2}$ squares.
\begin{align*}\binom{m + 1}{2}\cdot\binom{n + 1}{2} - n\cdot\binom{m + 1}{2} & = \binom{m + 1}{2}\cdot\left(\binom{n + 1}{2} - n\right) \\
 \\
& = \binom{m + 1}{2}\cdot\left(\frac {(n + 1)!}{(n - 1)!2!} - n\right) \\
 \\
& = \binom{m + 1}{2}\cdot\frac {n(n + 1) - 2n}{2} \\
 \\
& = \binom{m + 1}{2}\cdot\frac {n(n - 1)}{2} \\
 \\
& = \binom{m + 1}{2}\cdot\binom{n}{2}\end{align*}
Although I have no idea how to get this result with pure combinatorics, there are $ \binom{m + 1}{2}\cdot\binom{n}{2}$ non-square rectangles in an $ m\times n$ grid with $ n\geq m$.

For this particular problem, $ \binom{3 + 1}{2}\cdot\binom{5}{2} = 6\cdot10 = \boxed{60}$.[/hide]


geometry AMC AIME MATHCOUNTS probability function counting

I will be in Birmingham this Thursday and Friday.  I will be guest teaching at several area schools including Vestavia Hills High School and the Alabama School of Fine Arts.  I am trying to schedule visits with Pizitz Middle School and Hoover High School.

If there are any topics high school students would like to discuss before the AIME, put in your request now.  If there is a preferred lesson for middle school students before state MATHCOUNTS, let me know and I will try to arrange material for these topics before my flight tomorrow.

Probability? I have a good amount of trouble with that, though I doubt anything I could be taught in an hour would help too much.

General AIME test-taking and problem-solving skills would help.

I have a great probability lecture virtually memorized.

Really...then I'm sure quite a few of us would appreciate it (Mrs. Tipton was absent the entire probability chapter, and Kevin and I are both fairly weak in the area).

[quote="LuCy4EvA"]I was there the last time you came to Birmingham... I thought the problems were too hard... at least for middle school/sixth grade... my dad thought I was a little stupid for not knowing these stuff and tried to explain. If you come to Pizitz again, you should try to teach something about geometry, or something from Mathcount, because mathcount district is this saturday[/quote]

That talk was very tough even for 8th graders.  I wanted to display how much math there is that is out there to learn.  If I come talk again, it will be on MATHCOUNTS level topics.

However, Mrs. Chilton never got back to me, so it looks like I won't be visiting Pizitz this time.

[quote="Elemennop"]Excellent talk you gave, thanks very much... I especially liked the generating functions idea...it really helps alot....

Just to kind of go off on what you were saying at the end --

Given n variables, (ie. a + b + c), that are supposed to equal a number, m, and all the variables are non negative, then the number of possible n-tuples that equal m is [tex]{m+2\choose n-1}[/tex] ?[/quote]

With $n$ variables, there are $n-1$ dividers around the $m$ unit objects.  Of the $m+n-1$ objects and dividers, there are $\binom{m+n-1}{n-1} = \binom{m+n-1}{m}$ ways to order the $m$ identical unit objects and $n-1$ identical dividers.  This is exactly like finding the number of ways to arrange $m$ A's and $n-1$ B's to make distinct "words."

I'm glad you enjoyed the talk.  It's too bad I didn't have enough time to do generating functions justice.

Much thanks for the talk. It was very interesting and thought-provoking like always (like the class I should be at now...).

Were you able to connect our online and real life identities? :) Maybe we should have mentioned it...

[quote="MCrawford"]With $n$ variables, there are $n-1$ dividers around the $m$ unit objects.  Of the $m+n-1$ objects and dividers, there are $\binom{m+n-1}{n-1} = \binom{m+n-1}{m}$ ways to order the $m$ identical unit objects and $n-1$ identical dividers.  This is exactly like finding the number of ways to arrange $m$ A's and $n-1$ B's to make distinct "words."[/quote]

As a side note, this is equivalent to what I remember as the 'balls in urns' formula. That is, the number of ways that $b$ indistinguisable balls can be placed into $u$ distinguisable urns is $\binom{b+u-1}{b}$.

For the [i]$n$ non-negative integer variables with sum $m$[/i] counting problem, each variable would be an urn and $m$ balls would make up the final sum. You could also think of it more like you did as $m$ objects lined up with $n-1$ dividers. The gaps between the objects and positions before and after are where the $n-1$ can be placed, so those locations would be the urns, and the dividers would be the balls. Gaps between ($m-1$) and positions before and after total to $m+1$ for urns. That and $n-1$ balls will give you the same thing when plugged into the formula. Whatever makes the most sense to you.

By the way, I learned about this in Zeitz's [i]Art and Craft of Problem Solving[/i].

Yes, binomial coefficients pop up everywhere.  As long as you can make the analogies solidly, you can see how they tie an enormous amount of math together.

I'm glad you're reading Zeitz.  Great book.


How would I get $\mathbb{N}$ in TeXnicCenter?
Is there some package I need to use to view it?

Currently, when I type that, I'm gettng "undefined control sequence"

Never mind, I added the 5 packages ( \usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{array}
\usepackage{xy})

to the beginning and it's fine now.

However, something else happened, now it says:
[quote]
Package amsmath warning: Foreign command \atopwithdelims; \frac or \genfrac should be used instead on input line 392.[/quote]

But on line 392, all I have is [quote] Evaluate $\sum_{k=0}^{n}2^{k}{9\choose 3}$[/quote]

what's wrong?

[quote="stevem"]That's a LaTeX warning which won't stop the compilation (unlike an Error) and in this case is an informational message that in the amsmath package \choose has been superseded by \binom.
If you use
[color=red]\sum_{k=0}^{n}2^{k}\binom{9}{3}[/color]
you will get $\sum_{k=0}^{n}2^{k}\binom{9}{3}$ with no warnings.

To explain part of the warning: \genfrac allows one to define all sorts of fractions (different brackets, lines between top & bottom etc) and amsmath just defines \frac and \binom in terms of \genfrac. You can do outrageous things with \genfrac, for example: $\genfrac{(}{]}{5pt}{2}{9}{3}$  :wink:[/quote]

Wow, cool, thanks. I decided to not use amsmath for the time being...

For the $\mathbb{N}$ problem, you need the amsfonts package.


solve 1\a + 1\b + 1\c + 1\d + 1\e = 7\3.a,b,c,d,e are natural nos.

[hide="Solution"]

Take $ a\ge b\ge c\ge d\ge e$.

Now $ \frac73\le \frac5e$, so $ e\le2$. Now try solving with the same procedure for a,b,c,d... [/hide]


quadratics
algebra
inequalities proposed
inequalities

Let x,y,z are real number such that x+y+z = 2004. Find the maximum of
M = sinC*xy+sinA*yz+sinB*zx . Here ABC is a given triangle.

[quote="treegoner"]Let $x,y,z$ be real number such that $x+y+z = 2004$. Find the maximum of
$M = sinC\cdot xy+sinA\cdot yz+sinB\cdot zx$ . Here $ABC$ is a given triangle![/quote]

[color=darkred]Happy Christmas!![/color]

 :)

[quote="treegoner"]Let x,y,z are real number such that x+y+z = 2004. Find the maximum of
$M = xysinC+yzsinA+xzsinB$ . Here ABC is a given triangle.[/quote]

  The first: Merry Christmas( even i'm not a Christian :D )
Second: With this type of problem mean there is no restiction for variables x,y,z absolutely Lagrange undetermine multipliers will be the most effective..
  If u don't want to use this method,the fact that : $M={2004}^2 \frac{M}{{2004}^2}= \frac{{2004}^2M}{(x+y+z)^2}$ will be useful by treat 2 variables( such as y,z as parametters ) and combine with the condition of positive delta for a quadratic equation of x only..Ok ( I hope my solution is not too abstract )


I've found that I can't do problems similar in this example...

x^y, find the units digit in this number

and other problems that are very similar to the example I gave.

Can you guys help me approach to how to solve this type of problem?

Thanks

You basically need to find a pattern. For example, in 3^2004, I would see that 3*3=9, 9*3=27, 7*3=21, 1*3=3. So the pattern is 3, 9, 7, 1. Since 2004 has a remainder of 0 when dividing by 4, you know that the answer is 1.

Hope this helps.

Oh yeah...I understand now.  Thanks.

But is there a more complex example maybe in the form of...

x^y * z^n

or something like that...the more complex the better...hehe

Its exactly the same. All you need to know that if you want the units digit of a*b, its the units digit of a * the units digit of b (this is what modulo 10 is). So you would just find x^y and z^n separately, multiply them, and take the units digit.

Yeah, eg:

Find the units digit of:

4^2004 * 1999^4

Units digit of 4^2004:

well look for the pattern (always fun):

4*4 = 16, 4*16 = 64, 4*64 = 256
So it goes 4, 6, 4, 6, when we have 4^2, 4^3, 4^4. Even powers of 4 given units digits of 6.

Units digit of 1999^4, well since tens or any higher digit cannot influence the units digit, it is just the units digit of 9^4. which is 9*9*9*9, 81*81, or 1*1.

Multiply these together, 1*6 = 6

So the units digit of 4^2004 * 1999^4 is 6! (that is just 6, not 6 factorial)
Note the two examples of m^n, the former when m<<n, the latter when m>>n.

How would you go about doing a question like this: ( 2^k)(5^300)=a 303 digit interger, what is the sum of the intergers?

I assume you meant the sum of the digits. There are several answers to this question, three to be precise.

The main point here is to note that [tex]2^{300}*5^{300}=10^{300}.[/tex] [tex]10^{300}[/tex] has 301 digits: a 1 followed by 300 0s. By increasing k by 1, you are multiplying the number by 2. So let's make a chart:
[code]
k=300     n=   100000...
k=301     n=   200000...
k=302     n=   400000...
k=303     n=   800000...
k=304     n=  1600000...
k=305     n=  3200000...
k=306     n=  6400000...
k=307     n= 12800000...
k=308     n= 25600000...
k=309     n= 51200000...
k=310     n=102400000...
[/code]

As you can see n is a 303-digit number only for k=307, 308, or 309. Finding the sum of the digits is easy, because there are only 3 digits you have to add; the rest are 0s. So the possible answers are 11, 13, and 8.

Rep123, the question does not ask the sum of the digits of the smallest such integer, so I believe there are three valid answers.

Thanks both of you.  11 is the answer i needed, I missed the part of the question which said that k was the smallest positive interger.

Thanks everyone.  You covered a lot of questions that I was about to ask.

Are there anymore questions that are similar to this except the question is asking for something else and maybe not the units digit or the sum of the digits.


Discuss the convergence of
\[ \sum_{n\equal{}1}^{\infty}\left(\frac{p_n}{2p_{n\plus{}1}\minus{}p_{n\plus{}2}}\right)^n\]
where $ p_k$ is the k-th prime.

It is not converge, because exist h, suth that $ 2p_{n \plus{} 1} < p_n \plus{} p_{n \plus{} 2} \plus{} h$ for infinetely many n.

Of course (if it is true) it immediately implies that my series is divergent.

I have checked in 3 books about number theory, but none of them contains the fact you wrote or even something similar.

Could you explain it (give a sketch of proof) or say where it can be found?

tkank you

It is easy to prove for h=0 (h>0 followed from h=0).
Let exist only finite numbers n, suth that $ p_{n\plus{}1}\minus{}p_n<p_{n\plus{}2}\minus{}p_{n\plus{}1}, n\equal{}n_1,...,n_m$. Let  $ A\equal{}max_{i\equal{}1,..m} p_{n_i\plus{}2}\minus{}p_{n_i\plus{}1}$ Then for any n $ p_{n\plus{}1}\minus{}p_n\le A$ contradition with not bounded $ p_{n\plus{}1}\minus{}p_n$.

Thanks for this proof.

But I've got next question: if $ h\equal{}0$ is good, what else we need?

if $ h\equal{}0$ is good, my series contains infinitely many elements $ \ge 1$, am I right ??

[quote="knoppix"]Thanks for this proof.

But I've got next question: if $ h \equal{} 0$ is good, what else we need?

if $ h \equal{} 0$ is good, my series contains infinitely many elements $ \ge 1$, am I right ??[/quote]
Yes.


algorithm
algebra
polynomial
superior algebra
superior algebra unsolved

Find the smallest subfield $K$ of the reals which is closed under taking real radicals, i.e., under all applications $r_{n}\colon\mathbb R_{>0}\to\mathbb R_{>0},\ x\mapsto\sqrt[n]x$ for $n=2,3,\ldots$. Here, "find" means at least some algorithm which decides whether a given polynomial with rational coefficients has a root in $K$ or not.

(I have no solution to this problem.)

owk

Isn't this the maximal solvable extension of $\mathbb{Q}$? (-> There are algorithms to compute Galois groups and deciding solvability)

oops, *real* -> so $\mathbb{Q}^\text{solv}\cap \mathbb{R}$?

This field is full of weird corner cases, but I can tell you this- it's as far from Galois as possible. The order is built into the algebra, and that means that it has no nontrivial automorphisms.

It's not the intersection of solvable numbers and real numbers; this field doesn't contain the roots of a typical irreducible (over $\mathbb{Q}$) cubic with all three roots real.

uhm..
what do you mean by "the order is built into the algebra"?
and why can't it have nontrivial automorphisms? if you send $\sqrt2 \mapsto-\sqrt2$, can't you extend this from an automorphism of $\mathbb{Q}(\sqrt2)$ to an automorphism of the whole field?

You can't send $\sqrt{2}$ to $-\sqrt{2}$, since one has a square root and the other doesn't. A number is positive in this field (a topological condition) if and only if it has a square root (an algebraic condition). Therefore, any automorphism must send positive numbers to positive numbers; this forces the automorphism to fix everything.


[color=darkblue]Prove that: $ \boxed{n^{n\plus{}3}\plus{}(n\plus{}1)^{n\plus{}3}<(n\plus{}2)^{n\plus{}3}, \forall n \in N^*}$[/color]

[quote="thanhnam2902"][color=darkblue]Prove that: $ \boxed{n^{n \plus{} 3} \plus{} (n \plus{} 1)^{n \plus{} 3} < (n \plus{} 2)^{n \plus{} 3}, \forall n \in N^*}$[/color][/quote]
by binomial Newton's :
 $ (n \plus{} 1 \plus{} 1)^{n \plus{} 3} \geq (n \plus{} 1)^{n \plus{} 3} \plus{} n(n \plus{} 1)^{n \plus{} 2} \geq (n \plus{} 1)^{n \plus{} 3} \plus{} n^{n \plus{} 3}$ (  right because of $ (n \plus{} 1)^{n \plus{} 2}\geq n^{n \plus{} 2}$)

[color=darkblue]It's true and nice![/color]


Is Picard's Theorem

http://mathworld.wolfram.com/PicardsExistenceTheorem.html

neccasary and sufficent for the differential equation

$\frac{dx}{dt} = f(x,t)$ with $x(t_0)=x_0$

to have a unique solution.

Obviously it is sufficent, but is it neccasary?

Never mind, I have resolved my issues :)


quadratics
number theory
prime factorization
algebra
quadratic formula

Let $p\ge 5$ be a prime number. Prove that $p^{a}+p^{b}$ is never a perfect square, not even a rational square, where $a,b$ are integers.

about perfect square , i have an idea
assume that , there's exist x where $p^{a}+p^{b}=x^{2}$ , WLOG $a \geq b$ , so that $x^{2}=p^{b}(p^{a-b}+1)$ , we can easily see that b is even and $p^{a-b}+1$ is also a perfect square
let $y^{2}=p^{a-b}+1$ , so that $(y-1)(y+1)=p^{a-b}$ , we obtain $p^{a-b}|2$ , but $p \geq 5$ then it's a contracdition

your solution is almost right. but why should $p^{a-b}|2$?
 [hide="you can continue like this"]since we have $y$ is even so $\gcd(y+1,y-1)=1$ so $(y+1)(y-1)=p^{a-b}\Longrightarrow y+1=p^{m},y-1=p^{n}$
thus $p^{m}-p^{n}=2$,contradiction.[/hide]
okey, now who can prove it for rational squares i.e. when $a$ or $b$ or both $<0$? :wink:

[quote="nayel"]
okey, now who can prove it for rational squares i.e. when $a$ or $b$ or both $<0$? :wink:[/quote]

It's the same argument.  You'd multiply both sides by $p^{2}$ enough times to make both sides integral.  The rationals have unique prime factorization over the integers with integer exponents, so you again get $p^{a-b}+1$.  If we let one of $y \pm 1$ then be $\frac{p^{a-b}}{q}$ with q an integer, we have $p^{a-b}\pm 2q =q^{2}$, quadratic formula,
$q=\pm q \pm \sqrt{q^{2}+p^{a-b}}$, that thing in the square root is clearly a multiple of $q^{2}$, so $q|p^{a-b}\implies q|p$, so $q=1$, we're done...


I was using Firefox when it was ugly. In Safari, it isn't ugly. Maybe it's Firefox?

I don't know how to post a screenshot on a Mac. :(

Command (The apple logo) Shift 3.
If you want to select a certain region, use command shift 4.
It will then put a PDF on your desktop and will say "Picture 1".
(That is what it does for the version of mac I have.)


Find t:

$ p^t\plus{}\frac{1}{p^t}\equal{}\frac{p\plus{}1}{\sqrt{p}}$


Find all positive integers $ n$ exceeding $ 1$ such that if $ 1 < k < n$ and $ (k, n) \equal{} 1$ for all $ k$, then $ k$ is a prime.

[hide="Solution"]
Assume that if $ p_x$ is the lowest prime that does not divide $ n$, then $ p_x\ge 8$.  Let the primes below $ n$ be $ p_1, p_2, p_3, \cdots, p_x, p_{x \plus{} 1}, p_{x \plus{} 2}, \cdots, p_i$ in increasing order so that $ p_i$ is the largest prime below $ n$.  Now, by Bertrand's Principle, we have that $ p_{x \minus{} 1} > \frac {p_x}{2}$ and $ p_{x \minus{} 2} > \frac {x_{x \minus{} 1}}{2}$, meaning that $ p_{x \minus{} 2}p_{x \minus{} 1}p_x > \frac {p_x^3}{8}\ge p_x^2$.  This means that $ n < p_{x \minus{} 2}p_{x \minus{} 1}p_x$ since or else, $ n > p_x^2$, but $ n$ is coprime with $ p_x$ as shown before, meaning that $ n$ is greater than $ p_x^2$, but coprime with it, yielding a contradiction.  This means that $ p_1p_2p_3\cdots p_{x \minus{} 1}\le n\le p_{x \minus{} 2}p_{x \minus{} 1}p_x$.  When $ p_x\ge 5$, we get a contradiction, so $ p_x \equal{} 2, 3$.  Yet, $ p_x\ge 8$, so we have a contradiction.

Now, $ p_x\le 7$.  If $ p_x \equal{} 7$, then we have that $ 2, 3, 5|n\implies 30|n$, so $ n\ge 30$.  Yet, $ n\le 49$ since $ n < p_x^2$ or else $ p_x^2$ is coprime with $ n$, but is not prime itself, yielding a contradiction.  Thus, $ n \equal{} 30$, which works.  Now, if $ p_x \equal{} 5$, then $ 2, 3|n$ and $ n\le 25$.  This gives that $ n$ could equal $ 24, 18, 12, 6$.  All of these work.  If $ p_x \equal{} 3$, then $ n\le 8$, and $ 2|x$.  This gives that $ n \equal{} 2, 4, 8$ work.  Finally, if $ p_x \equal{} 2$ then $ n \equal{} 3$ works.  We conclude that the solutions are $ 2, 4, 6, 8, 12, 18, 24, 30$. [/hide]


In general USAMTS geometry, I had no idea on how to solve the problem. Last year, I managed to attempt 2 out of 4 geometry problems and got like 1/5 on each (surprisingly, I guessed on one of them and got the right answer  :rotfl: ). So is there any good level problems or books that I can use to study for USAMTS level geometry? I want to at least get close to the answer but I can't and this is frustrating.

I hope this is OK.. I don't mean to this year's round but all USAMTS geometry problems in general.

uh...well, I'd just do AIME geometry...

I mean, I personally don't see USAMTS geometry problems being harder than #13-15 geometry problems on AIME

Of course, a lot of the "problems" are actually proofs...but the basic knowledge of the math involved isn't much more than that needed for the AIME problems...

But maybe you should also look at[i] Challenging Problems in Geometry[/i]


here is my solution:
$(x_1+x_2+...+x_n)^2=\displaystyle\sum_{i=1}^{n}x_i^2 +\displaystyle\sum_{1\le i \prec j \le n}{2x{}_ix{}_j}
                                \ge c(n)[(\displaystyle\sum_{i=1}^{n}x_i^2)(2^c^(^n^){}^-{}^1)(\displaystyle\prod_{i=1}^{n}x_i){}^n{}^-{}^1]^1^|^c^(^n^)$ By AGM and the result follows from it. I want to see other solutions. :?


algebra
polynomial
induction
algebra unsolved

Find all the polynomials P(x) with the real coefficent satisfy
$ P(x,y)\equal{}P(x\plus{}y,y\minus{}x)$ for all the real number x,y

repeated application of the given relation produces $ p(x,y) \equal{} p(x \plus{} y,y \minus{} x) \equal{} p(2y, \minus{} 2x) \equal{} p(2y \minus{} 2x, \minus{} 2x \minus{} 2y) \equal{} p( \minus{} 4x, \minus{} 4y)$. so by induction, $ p(x,y) \equal{} p(( \minus{} 4)^nx,( \minus{} 4)^ny)$ for all natural $ n$. this implies that $ p(x,y)$ must be constant.


How many strings with 6 numbers (formed using only 1 and 2) we can construct if we do not permit appearence of adjacent "ones". Example of working strings: 121212, 212121, 222221, 222122. We do not permit 221122, 112222, 112212 etc...
Thank you for your help

Try to write out a recursion, replacing $ 6$ with $ n$.

Very Thanks t0rajir0u. i don't believe it!!!
For $ n\equal{}1$ we got two strings: (2) and (1)
For $ n\equal{}2$ we have 3 strings: (21), (22), (12)
For $ n\equal{}3$ we have 5 strings:  (212), (221), (222), (122), (121)
For $ n\equal{}4$ we have 8 strings:  (2121), (2122), (2212), (2221), (2222), (1221),(1222), (1212)

Fibonnaci sequence!
So for $ n\equal{}5$ we will have 5+8=13 strings and for $ n\equal{}6$ we achieve 13+8=21 strings

But how can i make it formal? induction?

[hide="Hint"]First let the first number in the string of length $ n$ be "2", then "1". How does the number of each of these relate to the number of strings with length $ n\minus{}1$ and $ n\minus{}2$?[/hide]


A metal slug weighing 25.17g is added to a flask with a volume of 59.7mL. It is found that 43.7g of methanol (d = 0.791g/mL) must be added to the metal to fill the flask. What is the density of the metal?

[hide]The volume of methanol is $\frac{43.7}{0.791}\approx55.2465$. That means that 59.7-55.2465=4.4535 mL is taken up by the metal slug. The density of the slug is then $\frac{25.17}{4.4535}\approx5.65$ g/mL. [/hide]

Shouldn't this be physics or chemistry?

Physics? I think Chemistry would be fine...


I invented the following inequality, but I am not sure it is true  :?  :
Let $a,b,c>0$ positive real numbers such that : $ab+bc+ca=1$
Prove that : $a^2bc+b^2ca+c^2ab \leq \frac{1}{3}$

[quote="erdos"]Let $a,b,c>0$ positive real numbers such that : $ab+bc+ca=1$
Prove that : $a^2bc+b^2ca+c^2ab \leq \frac{1}{3}$[/quote]

Of course, this inequality is true: Since ab + bc + ca = 1, it rewrites as $a^2bc+b^2ca+c^2ab\leq\frac13\left(ab+bc+ca\right)^2$, or, equivalently, $ca\cdot ab+ab\cdot bc+bc\cdot ca\leq\frac13\left(ab+bc+ca\right)^2$. But this is equivalent to $3\left(ca\cdot ab+ab\cdot bc+bc\cdot ca\right)\leq\left(ab+bc+ca\right)^2$, what is true since

$\left(ab+bc+ca\right)^2-3\left(ca\cdot ab+ab\cdot bc+bc\cdot ca\right)$
$=\frac12\left(\left(bc-ca\right)^2+\left(ca-ab\right)^2+\left(ab-bc\right)^2\right)\geq 0$.

  Darij

[quote="Myth"]And again... :(
Please, no more titles like "Is it true ??"! Titles should describe essences of problems!

Read http://www.mathlinks.ro/viewtopic.php?p=140098 !!![/quote]
I am really sorry  :blush:  :blush:  :blush:  I won't do that any more  :lol:  :lol:
Thanks [b]Darij[/b]


linear algebra
matrix
algebra
polynomial
invariant
function

Aceeasi tehnica se aplica foarte bine si aici.

I am sure there is a solution without diagonalisation

Let's consider the matrix in $M_n(C)$

$A^2=I_n$ , A is a symetry it is diagonalisable the eiengenvalues are $\pm 1$

$B^3=I_n$, the polynomial $x^3-1=(x-1)(x-j)(x-j^2)$ split with simple roots

B is  diagonalisable

But $A,B$ commute they are diagonalisable in the same basis

$A+B+I_n$ is similar to a diagonal matrix with eigenvalue $a+b+1$

$a=\pm 1$, $b = 1,j,j^2$ so $a+b+1$ is not zero

$det(A+B-xI_n)$ is real polynomial the root are conjugate

$det(A+B+I_n)>0$

Can you post solution without diagonalisation ?

Presupunem prin absurd ca $\det(A+B+I_n)=0$. Atunci $\det(2AB+B^2)=0$. Cum detB<>0 rezulta det(2A+B)=0 si astfel prin inmultire cu detA (care e diferit de 0) rezulta $\det(2I_n+AB)=0$.dar $(AB)^6=I_n$.Notam $D=2I_n+AB$
si obtinem prin aplicarea binomului lui Newton ca $D(D^5-12D^4+...-192I_n)=-63I_n$ de unde detD<>0 (contradictie)
$\det(A+B+I_n)=\frac{1}{2^n}det(2A+2B+2I_n)=\frac{1}{2^n}det[(A+I_n)^2+(\sqrt2B^{-1})^2] >= 0$
$ B=(B^{-1})^2$

[quote="silviu"]Fie  matricile $A,B \in M_n(R),n \in N^*.$
Daca $A^2=B^3=I_n$ si $AB=BA$ demonstrati ca:$det(A+B+I_n)>0$.[/quote]

To avoid diagonalization one can compute a resultant  $\Pi (\alpha_i A + \beta_j B + I)$ where $\alpha_i^2 = \beta_j^3 = 1$ are roots of unity.  The result will be a invariant under $A \to \alpha A$ and $B \to \beta B$, therefore a function of $A^2$ and $B^3$, therefore a scalar $rI$.  By computation one checks that it is nonzero, or note that $r$ is the resultant of the polynomials $(t-1)^2 - 1$ and $t^3 - 1$.


geometry
angle bisector
geometry proposed

I am posting some nice geometry problems I enjoyed during my holidays in Italy:

1) The excircle of ABC opposite vertex C touches AB and AC at P and Q. The excircle opposite A touches AC and AB at U and X. Prove that the intersection of PQ and UX is equidistant from the lines AB and BC.

op02 project, Hungary problem 1. Again, I'm copying the wording from the book and my solution (pretty straightforward).

[hide="Solution"][color=blue][b]Problem.[/b] The excircle to the side AB of the triangle ABC touches the lines AB and AC at P and Q, respectively. The excircle to the side BC touches the lines AC and AB at U and X respectively. Prove that the intersection of the lines PQ and UX is equidistant from the lines AB and BC.[/color]

[i]Solution.[/i] Let T be the orthogonal projection of the point C on the external angle bisector of the angle ABC. Of course, this external angle bisector passes through the centers I and J of the C-excircle and the A-excircle, respectively. We will prove that the point T lies on the lines PQ and UX.

Since < CTJ = 90°, the triangle CTJ is right-angled, so that < TCJ = 90° - < TJC. Since < CTJ = 90° and < CUJ = 90°, the quadrilateral CTJU is cyclic, so that

  $\measuredangle TUJ=\measuredangle TCJ=90^{\circ}-\measuredangle TJC=90^{\circ}-\measuredangle BJC$
  $=90^{\circ}-\left(180^{\circ}-\measuredangle JBC-\measuredangle JCB\right)$       (since < BJC = 180° - < JBC - < JCB by the sum of angles in triangle BJC)
  $=-90^{\circ}+\measuredangle JBC+\measuredangle JCB$
  $=-90^{\circ}+\left(90^{\circ}-\frac{B}{2}\right)+\left(90^{\circ}-\frac{C}{2}\right)$        (since the point J, being the A-excenter of triangle ABC, lies on the external angle bisectors of the angles ABC and BCA)
  $=90^{\circ}-\frac{B}{2}-\frac{C}{2}=\frac{180^{\circ}-B-C}{2}=\frac{A}{2}$        (since 180° - B - C = A by the sum of angles in triangle ABC).

On the other hand, since < AXJ = 90° and < AUJ = 90°, the quadrilateral AXJU is cyclic, and thus $\measuredangle XUJ=\measuredangle XAJ=\frac{A}{2}$. Hence, < TUJ = < XUJ, and our point T lies on the line UX.

Since < CTI = 90°, the triangle CTI is right-angled, and thus < TCI = 90° - < TIC. Since < CTI = 90° and < CQI = 90°, the quadrilateral CTIQ is cyclic, so that

  $\measuredangle TQI=\measuredangle TCI=90^{\circ}-\measuredangle TIC=90^{\circ}-\measuredangle BIC$
  $=90^{\circ}-\left(180^{\circ}-\measuredangle IBC-\measuredangle ICB\right)$       (since < BIC = 180° - < IBC - < ICB by the sum of angles in triangle BIC)
  $=-90^{\circ}+\measuredangle IBC+\measuredangle ICB$
  $=-90^{\circ}+\left(180^{\circ}-\left(90^{\circ}-\frac{B}{2}\right)\right)+\frac{C}{2}$        (since the point I, being the C-excenter of triangle ABC, lies on the external angle bisector of the angle ABC and on the internal angle bisector of the angle BCA)
  $=\frac{B}{2}+\frac{C}{2}=\frac{B+C}{2}=\frac{180^{\circ}-A}{2}$       (since B + C = 180° - A by the sum of angles in triangle ABC)
  $=90^{\circ}-\frac{A}{2}$.

Meanwhile, since < API = 90° and < AQI = 90°, the quadrilateral APIQ is cyclic, and we obtain $\measuredangle PQI=\measuredangle PAI=90^{\circ}-\frac{A}{2}$. Hence, < TQI = < PQI, and our point T lies on the line PQ.

Hence, T is the intersection of the lines PQ and UX. Now, since the point T lies on the external bisector of the angle ABC, it is equidistant from the lines AB and BC. Qed..[/hide]

[b]PS.[/b] The problem is actually equivalent to this one: http://www.mathlinks.ro/Forum/viewtopic.php?t=5438 . In fact, saying that the point T is equidistant from the lines AB and BC is equivalent to saying that it lies on the angle bisector of the angle CBX, i. e. that the line BT bisects the angle CBX.

  Darij

Nice game. Arne proposes an op02 problem and Darij carries out the "copy&paste" job on the forum. As there are quite a few problems the game might take some time...  :D


rotation
geometry
geometric transformation
reflection
combinatorics proposed
combinatorics

A (2n+1)x(2n+1) chessboard is covered by pieces of the shapes: (1), (2) and (3) (see below), which we can always rotate by 90 degrees and reflect across the horizontal and vertical axis. Prove that at least 4n+2 trominoes (3-square pieces) are used.

[img]http://www.mathlinks.ro/Forum/album_pic.php?pic_id=267[/img]

I managed to prove that the number of trominoes(1) is at least 4n+3, but i'm not sure. Please verify me:

I colored the board with 4 colors: A, B, C and D, this way(I'll draw here for n = 3)

ADADADA
BCBCBCB
ADADADA
BCBCBCB
ADADADA
BCBCBCB
ADADADA

So, let:
a = number of trominoes that contain B, A, D (with A in corner)
b = number of trominoes that contain A, B, C (with B in corner)
c = number of trominoes that contain D, C, B (with C in corner)
d = number of trominoes that contain C, D, A (with D in corner)
These are all the posibilities
We have ${(n+1)}^2$ 1x1 squares with A, ${n(n+1)}$ squares with B, ${n}^2$ squares with C, and ${n(n+1)}$ squares with D.
Also, each piece (2) or (3) always contains all 4 colors, A, B, C and D.
Let m = number of squares(2) and t = number of pieces of type (3)
SO:
${a+b+d+m+t = {(n+1)}^2}$
${a+b+c+m+t = {n(n+1)}}$
${b+c+d+m+t = {n}^2}$
${a+c+d+m+t = {n(n+1)}}$
By substracting second, third and forth equality from the first one, we obtain:
${d-c = n+1}$
${a-c = 2n+1}$
${b-c = 2n+1}$
Adding them, we get:
${a+b+d-3c = 4n+3}$, which means ${a+b+c+d = 4n+3+4c \geq 4n+3}$
This means the number of trominoes is at least 4n+3.
Please, tell me if I did something wrong.

You use n in two different meanings which is not correct, but fortunately it doesn't affect the solution.


i know its an easy problem, but i can't remember how to solve it in algebric way.

[img]http://img171.imageshack.us/img171/3563/1av9.gif[/img]

any help will be appreciated

thanks.

[hide] First find the intersection points by solving $\sqrt{7-x}=5-|x|$.

[b]Case 1[/b]: $x \geq 0$.
Upon solving, you get $x=3$ or $x=6$. The latter is extraneous.
[b]Case 2[/b]: $x < 0$.
Upon solving, you get $x=-2$ or $x=-9$. Again, the latter is extraneous.

So, now divide the number line into three regions: $x <-2$, $-2 < x < 3$, and $3 < x \leq 7$ (since the domain of $\sqrt{7-x}$ has to be taken into account).

By picking a test point from each region, you find that the first and the third satisfy the inequality.

Thus, the solution is $\boxed{x\leq-2\,\,\,\,\,or\,\,\,\,\,3\leq x\leq 7}$.

I'm not 100% sure if this method works...  :maybe: [/hide]


function
real analysis
real analysis solved

It is [url=http://www.mathlinks.ro/Forum/viewtopic.php?p=155779#155779]easy[/url] to see that if $S$ is a countable set and $f : S \times S \to \mathbb{R}^+$ is any function, then there exists a function $g : S \to \mathbb{R}^+$ such that $f(x,y) < g(x)g(y)$. It can [url=http://www.mathlinks.ro/Forum/viewtopic.php?p=155779#155779]also[/url] be shown that this fails if $S$ has cardinality at least equal to the continuum. Can it be shown, without the Continuum Hypothesis, that this fails if $S$ is uncountable?

I don't know man.. This looks like it's suitable for the "Open Questions" section. I don't know your proof for that problem you mentioned, but the example I mentioned there relies more on the topological properties of the real line than on its cardinality.

We might want to investigate questions such as this one: is there a closed subset of $\mathbb R$ having cardinality $S$? If the answer is positive, I think that property does indeed fail, but I'm not sure my argument is correct right now.

Edit:

Actually, I don't think that condition I mentioned is enough.. :(

Are you both kidding? Or am I missing something?

What a pity!!  Because I am pretty sure that closed subsets in $\mathbb{R}$ cannot have cardinal between countable and continuum!!

Pretty much everything I said up there is stupid :). Sorry about that. The original problem does indeed seem to rely only on the uncountability.

Ok, grobber asked me to write my arguments.
Let $S$ be an uncountable set, $f(x)=\frac{1}{|x-y|}$ and $g:S \to\mathbb{R}$ be an arbitrary function. Consider the subsets $S_n=\{x\in S\mid n<g(x)\leq n+1\}$. Then there is an $n$ s.t. $S_n$ is uncountable. Uncountable set $S_n$ has a finite limit point $s$. So there exists $\{s_m\}\subset S_n$ s.t. $s_m\to s$. Then $f(s_m,s_{m+1})\to +\infty$ and $g(s_m)g(s_{m+1})$ is bounded!

:blush:  :blush:  :blush:  I apologize; my solution depended heavily on the continuum (I made use of a bijection between $S$ and the set $S^{\aleph_0}$ of sequences $(s_1,s_2,\ldots,s_n,\ldots)$ with entries in $S$ to construct a non-explicit function). In fact, I didn't know that $\frac{1}{|x-y|}$ works before grobber showed it ...  :blush:


Is it allowed to have more than one account on AOPS? On the FTW ToS, it says no multiaccounts, but to my knowledge, there is nothing about it on the AOPS ToS. Would it be allowed to have more than one AOPS account but not use them at the same time on FTW?

We don't like multiaccounting. If I were you I wouldn't risk a ban just to have a secondary account (usually the reasons for that are not on the good side.)


algebra
polynomial
group theory
abstract algebra
Galois Theory
superior algebra
superior algebra unsolved

Determine if the polynomial $ f(x)\equal{}90x^{5}\plus{}446x^{4}\plus{}880x^{3}\plus{}860x^{2}\plus{}440x\minus{}30$ is solvable by radicals (I'm almost positive that it isn't but I would like to see a solution).  I am aware that this is a somewhat weird polynomial but it actually does have relevance for something.  I have not yet learned how to compute Galois groups and determine solvability.

You can't do that without Galois theory.
Let $ p\equal{}f/2$ and $ G$ be the $ p$-Galois group over $ \mathbb{Q}$. The discriminant of $ p$ is not a square. Here $ n\equal{}5$ then there are $ 2$ cases:
1) $ G\equal{}F_{20}$ ,the Frobenius group of order $ 5\times{4}$,and $ p$ is solvable.
2) $ G\equal{}S_5$ and $ p$ is not solvable.
In $ F_2$ the $ p$-decomposition in irreducibles is $ p\equal{}(x^3\plus{}x\plus{}1)(x^2\plus{}x\plus{}1)$ then $ C_3\times{C}_2$ is the $ p$-Galois group over $ F_2$ and $ G$ has an element of order $ 3$. It's impossible because $ 3$ is not a divisor of $ 20$.
Conclusion: we are in the case 2).

Thank you.  I don't entirely understand the solution but that's okay. :oops:

We can also use the Van Der Warden's method:
We have seen that, $ mod\; 2$, the $ p$-Galois group is $ C_2\times{C}_3$.
$ mod \;23$, $ p$ is irreducible then its Galois group is $ C_5$.
The only subgroup of $ S_5$ which has elements of order $ 2,3,5$ is $ S_5$.

A fault in my last post.
$ A_5$ would be also solution.
The correct argument is : the only subgroup of $ S_5$ which has elements of order $ 5,6$ is $ S_5$.

My point is that I do not know how you determined the Galois group.  I know that $ S_{5}$ is not solvable-my only question is how you determined that $ S_{5}$ was the appropriate group (theorems, factorizations,...)


inequalities
trigonometry
geometry unsolved
geometry

Prove that for every $\Delta ABC$, we have:
$\sum_{cyclic} \sin\frac{B}{2}\sin\frac{C}{2} \ge \frac{3}{4}\prod_{cyclic}\cos\frac{B-C}{2}$

We have $\sum sin{\frac{B}{2}}sin{\frac{C}{2}} \geq \frac{3}{4} \prod{cos{\frac{B-C}{2}}} \leftrightarrow \frac{8}{3}(\sum sinBsinCcos{\frac{A}{2}} \geq \prod(sinBsinC)$.
 Notice that $cos{\frac{A}{2}} \geq \frac{sinB +sinC}{2}$. Hence if we can prove
 $LHS \geq \frac{4}{3}.\sum sinBsinC(sinB+sinC) \geq \prod (sinB+sinC)$, then we are done. But it is obvious.


group theory
abstract algebra
superior algebra
superior algebra unsolved

Let $ p$ be an odd prime and let $ m\geq 2$. Let $ U_k\equal{}U_k(p^m)$ be the subset of $ (\mathbb{Z}/p^m\mathbb{Z})*$ consisting of those elements which have a representative in $ \mathbb{Z}$ which is $ \equiv 1\bmod{p^k}$. Thus,

$ U_k\equal{}1\plus{}p^k\mathbb{Z}\bmod{p^m\mathbb{Z}}$

(i) Show that for $ k\leq m\minus{}1$ that the map

$ \mathbb{Z}/p\mathbb{Z}\to U_k/U_{k\plus{}1}$

tiven by $ (a\bmod{p})\to 1\plus{}p^ka\bmod{p^{k\plus{}1}\mathbb{Z}}$ is an isomorphism.

(ii) Prove that the order of $ U_1$ is $ p^{m\minus{}1}$

first, $ U_k$ is a subgroup because it's closed, contains $ 1$ and $ (\mathbb{Z}/p^m)^*$ is finite.

(i) direct calculation yields $ ord(1\plus{}p^k a)\equal{}p$ in $ U_k / U_{k\plus{}1}$.
(ii) use (i) (m-1) times and that $ U_m$ is the trivial group.


Well,The solution that i have seen for this has tons of calculation.Lets see a different one.
Let $ABC$ be a triangle,$S(ABC)$ be its area and $P$ be a point in its plane.(No in the triangle).
Let $PA,PB,PC$ intersects $BC,AC,AB$ in $D,E,F$,respectivly.
We have $S(PBD)=S(PAF)=S(PCE)=k$.
The prove :
$S(ABC)=k$

Also posted at http://www.mathlinks.ro/Forum/viewtopic.php?t=17467 and solved at http://www.kalva.demon.co.uk/short/soln/sh01g6.html . Okay, the solution given there is not quite synthetic either...

  darij


A snail is at the bottom of a 20 meters deep pit. Every day the snail climbs 5 meters upwards, but at night it slides 4 meters back downwards.
How many days does it take before the snail reaches the top of the pit?

15 days to get 15 meters up, then it makes it out on the 16th day.


function
limit
combinatorics proposed
combinatorics

let f(n) from N* toN* f(1)=a :geq 1 and f(n+1)=f(n)+2 if n :in f(N*) and f(n)+1 otherwise.Find Lim :frac{f(n)}{n} as n:rightarrow :infty

I am not a mod here so I am just LaTeXing it in a separate post:

Let $f: \mathbb{N}^* \rightarrow \mathbb{N}^*$ be a function such that \[ f(1) = a \geq 1  \] and also \[ f(n + 1) = \left\{ \begin{aligned} f(n) + 2 & \ \ \textrm{ if } n \in f\left(\mathbb{N}^*\right) \\ f(n) + 1 & \ \ \textrm{ otherwise.} \end{aligned} \right..  \] Find \[ \lim_{n \rightarrow +\infty} \frac{f(n)}{n}.  \]

mumath, can you post a solution ? The problem is very interesting.

Hope it's correct:

Put $\epsilon _i = \{ \begin{aligned} 1 & \ \ \textrm{ if } i \in f(\mathbb{N}^*) \\ 0 & \ \ \textrm{ otherwise.} \end{aligned} $.

Then $f(n+1)=n+a+\epsilon _n +....+ \epsilon _1$.

Now suppose $\epsilon _l=...=\epsilon _{l+r}=1$. If $l+m = f(i_{l+m})$ we obtain $\epsilon _{i_l}=...=\epsilon _{i_{l+r}}=0$ and so we conclude that $f(n)$ behaves analytically as function $g(n+1)=g(n)+\frac{3}{2}$ so $\lim_{n \rightarrow \infty} \frac{f(n)}{n} = \lim_{n \rightarrow \infty} \frac{g(n)}{n}=\frac{3}{2}$

Megus,the answer is $\frac{1+\sqrt{5}}{2}$


Every term of the two sequences $\{ a_{n}\}$ and $\{ b_{n}\}$ are positive. For any natural number $n$, $a_{n}$, $b_{n}$ and $a_{n+1}$ forms an arithmetic progression while $b_{n}$, $a_{n+1}$ and $b_{n+1}$ forms a geometrical progression. If $a_{1}=1$ and $b_{1}=2$, then find $a_{n}$ and $b_{n}$.

$a_{n}= \frac{n(n+1)}{2}, b_{n}= \frac{{(n+1)}^{2}}{2}.$ Then, we may use induction to complete the proof.

[hide="Direct solution"]We have

\begin{eqnarray}b_{n}&=& \frac{a_{n}+a_{n+1}}{2}\\a_{n+1}&=& \sqrt{b_{n}b_{n+1}}\end{eqnarray}

Plugging $(2)$ into $(1)$ we get

$b_{n}=\frac{\sqrt{b_{n-1}b_{n}}+\sqrt{b_{n}b_{n+1}}}{2}\iff \sqrt{b_{n}}=\frac{\sqrt{b_{n-1}}+\sqrt{b_{n+1}}}{2}$

From this it's obvious that $\sqrt{b_{n}}$ is an arithmetic sequence. From the initial values we calculate $b_{2}={9\over 2}$, giving $\sqrt{b_{1}}=\sqrt{2},\sqrt{b_{2}}=\frac{3\sqrt{2}}{2}$, hence the common difference is $d=\frac{\sqrt{2}}{2}$, giving $\sqrt{b_{n}}=\sqrt{2}+(n-1)\frac{\sqrt{2}}{2}=\frac{(n+1)\sqrt{2}}{2}\iff b_{n}=\frac{(n+1)^{2}}{2}$

Now from $(2)$ we get $a_{n}=\sqrt{b_{n-1}b_{n}}=\frac{n}{\sqrt{2}}\cdot\frac{n+1}{\sqrt{2}}=\frac{n(n+1)}{2}$[/hide]

you can also make the substitution:

$b_{n}=a_{n}+2n$

at which point the problem becomes trivial using characteristic equations


advanced fields
advanced fields unsolved

Show that there is $ 2^{\aleph_0}$ well-orderings of the set of all natural numbers.

let $ X$ be an infinite set. there are $ 2^{|X|}$ well-orderings on $ X$:

every well-ordering is determined by the relation in $ \mathcal{P}(X \times X)$, thus there are at most $ 2^{|X \times X|} \equal{} 2^{|X|}$. for the latter and the following we have to assume choice.

now fix a well-ordering $ <$ on $ X$. every $ f \in Sym(X)$ transforms $ <$ into another well-ordering on $ X$ so that $ f$ becomes an order-isomorphism, i.e. we have $ f(x) < ' f(y) \leftrightarrow x < y$, and $ f(x)$ is the least element of $ X \backslash \{f(y) : y < x\}$ with respect to $ < '$. when $ f,g \in Sym(X)$ determine the same well-ordering, the latter implies $ f \equal{} g$ by transfinite induction. thus, there are at least $ |Sym(X)|$ well-orderings, and it is known that this equals $ 2^{|X|}$.


um...pretty sure i put 31 on the test... so A :D

on #2, i had A till the last 5 mins of the test, when i realized i can not do simple algebra.

Hmm half of the people in the room laughed at this problem.

[quote="Fanatic"]A. 15+16.

I think that might have been #1 on the AMC 10 too.[/quote]

It was. I actually double checked just because of how embrassing it is to get #1 wrong.

Not so bad as the first problem on the AMC10 B 2004...

There are 3 math classes at a school, and each class has exactly 24 students.  No student is in two math classes.  How many math students are there at the school?

I have a friend who got that wrong.  He got a 99.  That must suck.

First time I saw it I re-read it 3 times to make sure there wasn't a catch

[quote="K81o7"][quote="Fanatic"]LOL that exact problem was on a Mathcounts Chapter!![/quote]

That's a problem you'd see when you're first learning mutiplication...so I wonder what it's doing on the AMC10/12...even on mathcounts...[/quote]

Hmm...all my experience with mathcounts indicates that it's almost all stupid trivial stuff like that.

[quote="calc rulz"]AMC 12 A 2006 #1

Sandwiches at Joe's Fast Food cost 3 dollars each and sodas cost 2 dollars each. How many dollars will it cost to purchase 5 sandwiches and 8 sodas?

(A) 31
(B) 32
(C) 33
(D) 34
(E) 35[/quote]

(3*5)+(2*8)=15+16=31 (A).


For every  $ 0 \leq x \leq 1$ and $ n \in N$ prove an inequality $ (1\minus{}x\plus{}\frac{x^{2}}{2})^{n} \minus{}(1\minus{}x)^{n} \leq \frac{x}{2}$

________________________________________
Azerbaijan Land of Fire    :ninja:

[quote="Pirkuliyev Rovsen"]For every  $ 0 \leq x \leq 1$ and $ n \in N$ prove an inequality $ (1 \minus{} x \plus{} \frac {x^{2}}{2})^{n} \minus{} (1 \minus{} x)^{n} \leq \frac {x}{2}$

when$ n \equal{} 1$,$ LHS \equal{} (1 \minus{} x \plus{} \frac {x^2}{2}) \minus{} (1 \minus{} x) \equal{} \frac {x^2}{2}\leq \frac {x}{2},for\,0 \leq x \leq 1$,
Assume that when $ n \equal{} k$,the inequality holds.
when$ n \equal{} k \plus{} 1$ by hypothesis,
$ (1 \minus{} x \plus{} \frac {x^2}{2})^{k \plus{} 1} \minus{} (1 \minus{} x)^{k \plus{} 1} \equal{} (1 \minus{} x \plus{} \frac {x^2}{2})(1 \minus{} x \plus{} \frac {x^2}{2})^{k} \minus{} (1 \minus{} x)^{k \plus{} 1} \leq (1 \minus{} x \plus{} \frac {x^2}{2})[\frac {x}{2} \plus{} (1 \minus{} x)^k] \minus{} (1 \minus{} x)^{k \plus{} 1} \equal{} (1 \minus{} x \plus{} \frac {x^2}{2})\frac {x}{2} \plus{} \frac {x^2}{2}(1 \minus{} x)^k\leq (1 \minus{} x \plus{} \frac {x^2}{2})\frac {x}{2} \plus{} \frac {x^2}{2}(1 \minus{} x) \equal{} \frac {x}{2} \minus{} \frac {x^3}{4} \leq \frac {x}{2}$

so above inequality holds for arbitary $ n$,when $ 0 \leq x \leq 1$

________________________________________
Azerbaijan Land of Fire    :ninja:[/quote]


Suppose $a$ and $b$ are positive numbers for which

\[ \log_9 a = \log_{15} b = \log_{25} (a+2b). \]

What is the value of $b/a$?

[quote="varun"]So, I have a nice problem for you all:

If $a^{1/x}=b^{1/y}=c^{1/z}$ and x,y,z are in AP. Then prove that a,b,c are in GP.

Try this as a practice . Nice time.. :arrow:[/quote]

Let $a^{1/x}=b^{1/y}=c^{1/z}=k$ then $a=k^x$ , $b=k^y$ , $c=k^z$.

which is $ac=k^{x+z}=k^{2y}=b^2$  ;)


[quote="sinankaral53"]$ D$ is common tangent point  and $ AC$ is tangent to the circle at $ C$
$ |AB| \equal{} |BC|$
$ |BD| \equal{} 4$
$ |AD| \equal{} ?$[/quote]

If it is the situation that looks to be from the diagram, you must
explicitly state in your given that points $ A$ and $ B$ are located
on the circle on the left-hand side, or state for the diagram that
it is not necessarily drawn to scale, and that the locations of
points $ A$ and $ B$, in relation to being on the circumference of
either circle, are not to be assumed.  It should not be assumed
from the diagram.

For instance, if the circles are the same size, point $ C$ is definitely
known to be on the right-hand circle (from the given), point $ A$
is at the top of the left-hand circle (on the circle), then point $ B$
is directly above point $ D$ (depending on how far to the left that
point $ A$ would be).  Then $ BD$ would make a right angle to $ AC$.
 Additionally, triangle $ ABD$ would be an isosceles right triangle,
because the line segments $ AB$ and $ DC$, which are tangent to
the same circle, would be equal in length to each other.
Then $ AD$ would be the hypotenuse of triangle $ ABD$.

In this scenario, the length of $ AD \equal{} 4\sqrt {2}$.


Let $ AB$ be the diameter of a circle with centre $ O$. Pick a point $ C$ on the circle so that $ OC$ is perpendicular to $ AB$. Let $ P$ be any point on the circle between $ C$ and $ B$, and let the lines $ CP$ and $ AB$ intersect in $ Q$. Choose $ R$ on $ AP$ such that $ RQ$ and $ AB$ are perpendicular to eachother. Prove that $ BQ \equal{} QR$

[geogebra]08ace0f4bde45871da64149ae49d17a9e4b780c5[/geogebra]

Here's a diagram.

I'm not sure, but it probably has to do with proving COB and RQB similar and comparing the two asked-for segment with the two corresponding congruent radii. I just don't know how to arrive there.

[hide="Solution"]Draw in BP, since AB is a diameter, $ BP \perp AP$, so since $ \angle BPR \equal{} \angle BQR \equal{} 90$, BPRQ is cyclic. So $ \angle RBQ \equal{} \angle RPQ \equal{} \angle CPA$. But $ \angle CPA$ intercepts arc AC, which is 90 degrees, so $ \angle CPA \equal{} 45$, so $ \triangle BRQ$ is isoceles right.[/hide]
EDIT: Sorry, yes, $ BP \perp AP$.

[quote="dgreenb801"][hide="Solution"]Draw in BP, since AB is a diameter, $ BP \perp AB$[/hide][/quote]

[hide="ummm.."]
If AB is the diameter then wouldn't that mean that BP couldn't be perpendicular, because perpendicular lines to radii are tangents?
Edit: oh, I think you meant it's perpendicular to AP[/hide]


inequalities
special factorizations
inequalities theorems
Computer solutions
109

I have seen many times now, the use of order in inequalities. For example, (in Hojoo Lee's Inequalities booklet [i]http://ultrametric.googlepages.com/tin2006new.pdf[/i]) a solution (originating from [i]http://www.lix.polytechnique.fr/Labo/Ilan.Vardi/publications.html[/i]) to the IMO 2002 #2:

[i]Prove, given [/i]$abc=1$, $a, b, c>c$ [i]that [/i]

$1\ge (a-1+\frac{1}{b})(b-1+\frac{1}{c})(c-1+\frac{1}{a})$

goes as follows:

Using $abc=1$, assume $a\ge 1\ge b$

Then manipulating, we see that $1-(a-1+\frac{1}{b})(b-1+\frac{1}{c})(c-1+\frac{1}{a})=(c+\frac{1}{c}-2)(a+\frac{1}{b}-1)+\frac{(a-1)(1-b)}{a}\ge 0$, clearly, by assumption.

When I see these algebraic manipulation insights to take advantage of order, I am amazed. I don't know how to think of them, to have that insight. Can someone help me out? Do you just manipulate classically (e.g. completing the square, factor, etc) and hope to get something, do you work backwards, are there specific things/expressions you look for and want to use, etc?

Thanks so much for your help,

Sunchips

Please, some help and comments from all who are experienced :help: :help:  :help:

[quote="sunchips"][b]IMO 2000, Problem 2[/b] Let $a$, $b$, $c$ be positive real numbers such that $abc=1$. Prove that

$\left(a-1+\frac{1}{b}\right)\left(b-1+\frac{1}{c}\right)\left(c-1+\frac{1}{a}\right)\leq 1.$

Do you just manipulate classically (e.g. completing the square, factor, etc) and hope to get something, do you work backwards, are there specific things/expressions you look for and want to use, etc? [/quote]If $abc=1$, then at least one of the ordered pairs $(b,c)$, $(c,a)$, or $(a,b)$ has its first element $\leq1$ and the second $\geq1$. One can, without loss of generality, take this ordered pair to be $(b,c)$.

$1-\left(a-1+\frac{1}{b}\right)\left(b-1+\frac{1}{c}\right)\left(c-1+\frac{1}{a}\right)$

$\equiv F(a,b,c)=F\left(\frac{d^2}{yz},\frac{y}{d},\frac{z}{d}\right)\equiv\frac{G(y,z,d)}{yz^2d^3},$

where $G(y,z,d)=G(y,y+s+t,y+t)$

$=(s^2-st+t^2)y^4+3t(s^2+t^2)y^3+t^2(8s^2+3st+3t^2)y^2$

$+t^2(2s^3+8s^2t+2st^2+t^3)y+s^2t^3(s+2t)\geq0,$

which is clearly true for $0<y\leq d\leq z$.

More general result see : http://www.artofproblemsolving.com/Forum/viewtopic.php?t=117481

[quote="sunchips"]
[i]Prove, given [/i]$abc=1$, $a, b, c>0$ [i]that [/i]

$1\ge (a-1+\frac{1}{b})(b-1+\frac{1}{c})(c-1+\frac{1}{a})$

[/quote]
After substitution $a=\frac{x}{y}$, $b=\frac{y}{z}$ and $c=\frac{z}{x}$ you can get something obvious.  :wink:


Euler
geometry
circumcircle
geometry proposed

Given a triangle $ ABC$ with altitudes $ AA_1$ and $ BB_1$. $ A_0$ and $ B_0$ are midpoints of $ BC$ and $ CA$ respectively. $ A_0B_0$ and $ A_1B_1$ meet at $ C'$. prove that $ CC'$ is perpendicular to the Euler Line of triangle $ ABC$

[b]REMARKS:[/b]
[b]1) [/b]$ A_0B_0C_0 \mbox{ pedal triangle of circumcircle O of triangle ABC, and } A_1B_1C_1 \mbox{ pedal triangle of H;}$
[b]2)[/b] $ \mbox{H and O isogonal conjugate points in triangle ABC; and apply }$
[b]luisgeometria remark and Mashimaru solution for the PROBLEM of:[/b]  http://www.mathlinks.ro/viewtopic.php?t=308889

Well, NSato has given an excellent solution using nine point circle poles and polars  in the following topic:
[url]http://www.mathlinks.ro/viewtopic.php?p=471718#471718[/url]

Dear Mathlinkers,
you can find a pure synthetic proof on
http://perso.orange.fr/jl.ayme/  vol. 2  Les deux points de Schroeter p. 4-5
Sincerely
Jean-Louis