geometry
counting
rectangle
IMO
combinatorics
IMO 1997

[quote="Valentin Vornicu"]In the plane the points with integer coordinates are the vertices of unit squares. The squares are coloured alternately black and white (as on a chessboard). For any pair of positive integers $ m$ and $ n$, consider a right-angled triangle whose vertices have integer coordinates and whose legs, of lengths $ m$ and $ n$, lie along edges of the squares. Let $ S_1$ be the total area of the black part of the triangle and $ S_2$ be the total area of the white part. Let $ f(m,n) \equal{} | S_1 \minus{} S_2 |$.

a) Calculate $ f(m,n)$ for all positive integers $ m$ and $ n$ which are either both even or both odd.

b) Prove that $ f(m,n) \leq \frac 12 \max \{m,n \}$ for all $ m$ and $ n$.

c) Show that there is no constant $ C\in\mathbb{R}$ such that $ f(m,n) < C$ for all $ m$ and $ n$.[/quote]

(a)  If m and n are both even, then f(m,n) = 0. Let M be the midpoint of the hypoteneuse. The critical point is that M is a lattice point. If we rotate the triangle through 180 to give the other half of the rectangle, we find that its coloring is the same. Hence $ S_1$ and $ S_2$ for the triangle are each half their values for the rectangle. But the values for the rectangle are equal, so they must also be equal for the triangle and hence $ f(m,n) \equal{} 0$.

If m and n are both odd, then the midpoint of the hypoteneuse is the center of a square and we may still find that the coloring of the two halves of the rectangle is the same. This time S1 and S2 differ by one for the rectangle, so $ f(m,n) \equal{} \frac{1}{2}$.

(b)  The result is immediate from (a) for m and n of the same parity. The argument in (a) fails for m and n with opposite parity, because the two halves of the rectangle are oppositely colored. Let m be the odd side. Then if we extend the side length m by 1 we form a new triangle which contains the original triangle. But it has both sides even and hence $ S_1 \equal{} S_2$. The area added is a triangle base 1 and height n, so area n/2. The worst case would be that all this area was the same color, in which case we would get $ f(m,n) \equal{} \frac{n}{2}$. But $ n \leq  max(m,n)$, so this establishes the result.

(c)  Intuitively, it is clear that if the hypoteneuse runs along the diagonal of a series of black squares, and we then extend one side, the extra area taken in will be mainly black. We need to make this rigorous. For the diagonal to run along the diagonal of black squares we must have n = m. It is easier to work out the white area added by extending a side. The white area takes the form of a series of triangles each similar to the new n+1 x n triangle. The biggest has sides 1 and $ \frac{n}{n\plus{}1}$. The next biggest has sides $ \frac{n\minus{}1}{n}$ and $ \frac{n\minus{}1}{n\plus{}1}$, the next biggest $ \frac{n\minus{}2}{n}$ and $ \frac{n\minus{}2}{n\plus{}1}$ and so on, down to the smallest which is $ \frac{1}{n}$ by $ \frac{1}{n\plus{}1}$. Hence the additional white area is 1/2 (n/(n+1) + (n-1)2/(n(n+1)) + (n-2)2/(n(n+1)) + ... + 1/(n(n+1)) ) = 1/(2n(n+1))  (n^2 + ... + 1^2) = (2n+1)/12. Hence the additional black area is n/2 - (2n+1)/12 = n/3 - 1/12 and the black excess in the additional area is n/6 - 1/6. If n is even, then f(n,n) = 0 for the original area, so for the new triangle $ f(n\plus{}1,n) \equal{} \frac{n\minus{}1}{6}$ which is unbounded

for part $c$ the triangle with lenghts $2^k$ and $2^{k-1}$ also works.

Solution from [i]Twitch Solves ISL[/i]: In general, we say the [i]discrepancy[/i] of a region in the plane equals its black area minus its white area. We allow negative discrepancies, so discrepancy is additive and $f(m,n)$ equals the absolute value of the discrepancy of a right triangle with legs $m$ and $n$.

For (a), the answers are $0$ and $1/2$ respectively. To see this, consider the figure shown below.
[asy]
size(8cm); pair A = (0,5); pair B = (9,0); pair M = midpoint(A--B); for (int i=0; i<=5; ++i) { draw( (0,i)--(9,i), grey ); } for (int j=0; j<=9; ++j) { draw( (j,0)--(j,5), grey ); } dot("$M$", M, dir(50)); dot("$A$", A, dir(90)); dot("$B$", B, dir(0)); dot("$C$", (0,0), dir(180)); filldraw(A--B--(0,0)--cycle, invisible, black+1.5); pair P = (0,2.5); pair Q = (9,2.5); dot("$P$", P, dir(180)); dot("$Q$", Q, dir(0)); draw(P--Q--B, blue+1.5);
[/asy]
Notice that triangles $APM$ and $BQM$ are congruent, and when $m \equiv n \pmod 2$, their colorings actually coincide. Consequently, the discrepancy of the triangle is exactly equal to the discrepancy of $CPQB$, which is an $m \times n/2$ rectangle and hence equal to $0$ or $1/2$ according to parity.

For (b), note that a triangle with legs $m$ and $n$, with $m$ even and $n$ odd, can be dissected into one right triangle with legs $m$ and $n-1$ plus a thin triangle of area $1/2$ which has height $m$ and base $1$. The former region has discrepancy $0$ by (a), and the latter region obviously has discrepancy at most its area of $m/2$, hence $f(m,n) \le m/2$ as needed. (An alternative slower approach, which requires a few cases, is to prove that two adjacent columns have at most discrepancy $1/2$.)

For (c), we prove:
[b][color=red]Claim:[/color][/b] For each $k \ge 1$, we have \[ f(2k, 2k+1)  = \frac{2k-1}{6}. \]
[i]Proof.[/i] An illustration for $k=2$ is shown below, where we use $(0,0)$, $(0,2k)$, $(2k+1,0)$ as the three vertices.
[asy]
size(8cm); fill( (0,4)--(5,0)--(5,4)--cycle, palered ); draw(box( (0,0), (5,4) ), black); fill( (0,3)--(1,3)--(1,3.2)--(0,4)--cycle, grey); fill( (1,2)--(2,2)--(2,2.4)--(1.25,3)--(1,3)--cycle, grey); fill( (2,1)--(3,1)--(3,1.6)--(2.50,2)--(2,2)--cycle, grey); fill( (3,0)--(4,0)--(4,0.8)--(3.75,1)--(3,1)--cycle, grey); fill(shift(1,0)*unitsquare, grey); fill(shift(0,1)*unitsquare, grey); for (int i=1; i<4; ++i) { draw( (0,i)--(5,i), grey ); } for (int i=1; i<5; ++i) { draw( (i,0)--(i,4), grey ); } draw( (0,4)--(5,0)--(0,0)--cycle, blue+2 );
[/asy]
WLOG, the upper-left square is black, as above. The $2k$ small white triangles just below the diagonal have area sum \[ \frac12 \cdot \frac{1}{2k+1} \cdot \frac{1}{2k} \left[ 1^2 + 2^2 + \dots + (2k)^2 \right] = \frac{4k+1}{12} \] The area of the $2k$ black polygons sums just below the diagonal to \[ \sum_{i=1}^{2k} \left( 1 - \frac12 \cdot \frac{1}{2k+1} \cdot \frac{1}{2k} \cdot i^2 \right) = 2k - \frac{4k+1}{12} = \frac{20k-1}{12}. \] Finally, in the remaining $1+2+\dots+2k$ squares, there are $k$ more white squares than black squares. So, it follows \[ f(2k, 2k+1) = \left\lvert -k + \frac{20k-1}{12} - \frac{4k+1}{12} \right\rvert = \frac{2k-1}{6}. \] $\blacksquare$


Let $ a,b,c>0; a\plus{}b\plus{}c\equal{}3$. Prove that:
$ \frac{2a^2\plus{}bc}{a^2\plus{}3}\plus{}\frac{2b^2\plus{}ca}{b^2\plus{}3}\plus{}\frac{2c^2\plus{}ab}{c^2\plus{}3} \ge \frac{9}{13\minus{}3(ab\plus{}bc\plus{}ca)}$

$ \sum {\frac {{2a^2 \plus{} bc}}{{a^2 \plus{} 3}}} \equal{} \sum {\frac {{2a^2 }}{{a^2 \plus{} 3}}} \plus{} \sum {\frac {{bc}}{{a^2 \plus{} 3}}}$
By the Cauchy Schwartz we have
$ \sum {\frac{{2a^2 }}{{a^2  \plus{} 3}}}  \ge 2\frac{{\left( {a \plus{} b \plus{} c} \right)^2 }}{{a^2  \plus{} b^2  \plus{} c^2  \plus{} 9}} \equal{} \frac{{18}}{{18 \minus{} 2\left( {ab \plus{} bc \plus{} ca} \right)}}$
$ \sum {\frac{{bc}}{{a^2  \plus{} 3}}}  \ge \frac{{\left( {ab \plus{} bc \plus{} ca} \right)^2 }}{{abc\left( {a \plus{} b \plus{} c} \right) \plus{} 3\left( {ab \plus{} bc \plus{} ca} \right)}} \equal{} \frac{{\left( {ab \plus{} bc \plus{} ca} \right)^2 }}{{3abc \plus{} 3\left( {ab \plus{} bc \plus{} ca} \right)}} \ge \frac{{\left( {ab \plus{} bc \plus{} ca} \right)^2 }}{{3 \plus{} 3\left( {ab \plus{} bc \plus{} ca} \right)}}$
So we have to prove that $ \frac {{18}}{{18 \minus{} 2q}} \plus{} \frac {{q^2 }}{{3 \plus{} 3q}} \ge \frac {9}{{13 \minus{} q}}$
with $ q \equal{} ab \plus{} bc \plus{} ca \le 3$
$ \Leftrightarrow \left( {q \minus{} 3} \right)\left( {3q^3 \minus{} 31q^2 \minus{} 30q \minus{} 36} \right) \ge 0$
which is true, equality holds for $ a \equal{} b \equal{} c \equal{} 1$


I have 3 questions about proving that $ e^{xi}\equal{}\cos{x}\plus{}i\sin{x}$.

1. What's Taylor Series?

2. Why is $ 1\minus{}\frac{x^2}{2!}\plus{}\frac{x^4}{4!}\minus{}\frac{x^6}{6!}\plus{}\cdots\equal{}\cos{x}$?

3. Why is $ x\minus{}\frac{x^3}{3!}\plus{}\frac{x^5}{5!}\minus{}\frac{x^7}{7!}\plus{}\cdots\equal{}\sin{x}$?

General tutorial on Taylor series (should answer your questions)
[url]http://tutorial.math.lamar.edu/Classes/CalcII/TaylorSeries.aspx[/url]

But, as discussed in this thread, this is not a way to prove Euler's formula.  Pay special attention to t0rajir0u's posts.
[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?t=213725[/url]

Would not this be better answered in the Calculus forum?  :wink:


solve equation :
                  $p(2^{p-1}-1)=x^k$
 where$p$ is prime and such that $\exists k,x \in N$ and $k>1$

[quote="{x}"]I assume $0$ does not belong to $\mathbb{N}$.
Suppose there is a prime $p$ satysfying $p \cdot ( 2^p - 1 ) = x^k$. Then $p \cdot ( 2^p - 1 ) = x^k$ implies $p|x^k$. But $p$ is prime so $p|x^k \Rightarrow p^k |x^k$. Recall that $x^k = p \cdot ( 2^p - 1 )$, so if $p^k |x^k$ then $p^k |p \cdot ( 2^p - 1 )$. So $p^{k - 1} |2^p - 1$. And since $k > 1$, $p|p^{k - 1}$ so $p| 2^p - 1$. But there is no prime $p$ such that $p| 2^p - 1$ (Fermat's Little Theorem). Contradiction.[/quote]

your solution are wrong.
you see $2^p$. the correct is $2^{p-1}$.  ;)

[quote="e.lopes"]you see $2^p$. the correct is $2^{p-1}$.  ;)[/quote]
Indeed that made the problem easier ;)


The mean of three positive integers is greater than 7 and less than 10. What is the greatest possible value for the largest of the integers?

This is achieved when the numbers are $ 1,1,\boxed{27}$.


complex analysis
complex analysis unsolved

[quote="serio7"]Find a biholomorphic mapping such that

it maps the upper half-plane to

$ {A(z) > 0, B(z) > 0, min(A(z), B(z)) < 1}$

$ z \in C$[/quote]

My mistake,

The correct question is:

Find a biholomorphic mapping such that

it maps the upper half-plane to

$ {Im(z) > 0, Re(z) > 0, min(Im(z), Re(z)) < 1}$
$ z \in C$


1. limx-->infinity(+)e^(-x)/x. How to find this?
2. imx-->2+ (from the right)1/(x-2). The answer is to the infinity, but will the y-value never get to a point that is fixed when x=2 from the right? It will just go infinitely forever? I don't get it. When we solve this one-sided limit, can we solve it analytically, or only graphically?

Thanks.

You are fundamentally clueless here. Read what your textbook has to say about limits, and try to understand the examples.
Evaluating at a single point "nearby" is never sufficient.


topology
real analysis
real analysis unsolved

Let $X$, $X'$ denote single set in topologies $\mathcal{T}$ ,$\mathcal{T}'$. Let $Y$, $Y'$ denote single set in topology $\mathcal{U}$, $\mathcal{U}'$. These set are nonempty.
We can prove that if $\mathcal{T}'$ finer than $\mathcal{T}$, and $\mathcal{U}'$ finer than $\mathcal{U}$, then the product topology on $X' \times Y'$ is finer than the product topology on $X \times Y$.

does the converse hold??

Yes. A set $U\subset X$ is open in the topology of $X$ iff the set $U\times Y$ is open in the product topology on $X\times Y$.

You should be careful about closed, though. I think that it is the case that if a set in the product topology is closed does not necessarily mean that the set (projection) in just one of the sets is closed. Projection is an open mapping but not closed. Maybe you're OK for general product topology, but when you get to box you run into problems? Counterexample anyone?

I know that the projection of a closed set needs not be closed: $\{(x,y)\in\mathbb R^{2}\colon xy=1\}$ is a simple example. On the other hand, a set $U\subset X$ is closed in the topology of $X$ iff the set $U\times Y$ is closed in the product topology on $X\times Y$.

But I don't see how this is relevant to the question posed in this thread.  :maybe:


$\log{\sin{x}}+\log{\cos{x}}=-1$
$\log(\sin{x}+\cos{x})= 0.5(\log(n-1))$.
What is n?

I did:
[hide]
$\log{\sin{x}\cos{x}}=-1$ so $\sin{x}\cos{x}= 0.1$.
$(\sin{x}+\cos{x})^{2}= 1+2\sin{x}\cos{x}= 1.2$
$2\log(\sin{x}+\cos{x})= \log(n-1)$
$\log(\sin{x}+\cos{x})^{2}= \log(n-1)$
$\log{1.2}= \log(n-1)$
$1.2=n-1$
$n=2.2$
[/hide]

but n has to be an integer so i must be wrong. the answer key says [hide]n=12[/hide]. help?

EDIT: Latex by mod.

Your answer is correct. For one, $(sin \ x+cos \ x)^{2}$
 can never exceed $2$ so $12$ is absurd. for another , your method seems to be alright.

[quote="knexpert"]You messed up with the original problem. The one is outside the parentheses on the RHS. Therefore, the LHS become $\log{1.2}+1=\log{12}$. This is why in the original problem $n=12$.[/quote]

yea you're right... i read the problem wrong. sorry...  :blush:


\begin{eqnarray*}x&=&u^2+2 v^2\\&y=&u^3-6 u v^2\\1&=&2 v^3-3 u^2 v\end{eqnarray*}

apparentlly eqnarray isn't supported in the forums?
[url=http://www.mathlinks.ro/LaTeX/AoPS_L_TeXer.php]texer[/url]
if you plug it in here you see what happens

this doesn't look too good
but what is different that makes it so?
can anyone explain

\begin{eqnarray*}x&=&u^2+2 v^2\\y&=&u^3-6 u v^2\\1&=&2 v^3-3 u^2 v\end{eqnarray*}

It looks okay to me... :?

\begin{eqnarray*}x&=&u^2+2 v^2\\&y=&u^3-6 u v^2\\1&=&2 v^3-3 u^2 v\end{eqnarray*}

\begin{eqnarray}x&=&u^2+2 v^2\\&y=&u^3-6 u v^2\\1&=&2 v^3-3 u^2 v\end{eqnarray}

Well first of all the star thing seems to be completely irrelevant
but let me point out that my latex at home only accepts this eqnarray without dollar signs
i just have to type begin and end
what is going on here?

Oh my the error is soo dumb
i placed on of my & before the y instead of between the y and the equality sign

sorry to have bothered anyone here
I wish the question could be removed :blush:

From what I understand, eqnarray is outdated and its use
discouraged.

The prefered method is to use \begin{align} ... \end{align}
or \begin{align*} ... \end{align*} and the \tag command
to control manually the numbering of equations.

Could you post an example using the align environment?


I thought you were going to post about sad kermit.

http://en.wikipedia.org/wiki/Sad_Kermit

Um..... What is this??? He doesn't even look like Kermit.


A club has 5 members from each of 3 different schools, for a total of 15 members. How many possible ways are there to arrange a presidency meeting at one of the schools if the host school gets two representatives at the meeting and each of the other schools only gets to send one?

I don't think the wording suggests that the meeting could be held at any of the three schools.

I assumed that the meeting location had been chosen, and it took me a while to figure out what the intent of the problem was.

[hide= A 8-years old problem with no solution]
$$3 \times \binom{5}{2} \times 5 \times 5=4 \times 10 \times 5 \times 5=4 \times 10 \times 25 =40 \times 25=\boxed{750}$$


Find a $k \in N$ such that $k2^n+1$ for all natural numbers like $n$ be a composite number.

[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?highlight=Zagier&t=4960[/url]

It's not exactly the same problem, but you can easily adapt that solution.


[quote="max1546"]between the numbers 1245 and 5421 inclusive, how many numbers do not have any of the digits 1,2,4,5?
How could I solve this using combinatorics and permutations?[/quote]

[hide]The only possible thousands digit for such numbers is $3$. Then the number should be of the form $3abc$, where $a$, $b$, and $c$ are digits that are not $1$, $2$, $4$, or $5$. There are $10-4=6$ choices for each of $a$, $b$, and $c$, giving $6^{3}=\boxed{216}$ such numbers.[/hide]

[quote="max1546"]between the numbers 1245 and 5421 inclusive, how many numbers do not have any of the digits 1,2,4,5?
How could I solve this using combinatorics and permutations?[/quote]

[hide]The thousands digit must be from 1 to 5, inclusive.  However, it cannot be 1, 2, 4, or 5, so it must be 3.  Then, for each of the next 3 digits, there are 6 choices, for a total of $6^{3}=216$ numbers.[/hide]


If $ y \equal{} \sqrt{x^2 \minus{} 2x \plus{} 1} \plus{} \sqrt{x^2 \plus{} 2x \plus{} 1}$, then $ y$ is:

$ \textbf{(A)}\  2x\qquad
\textbf{(B)}\ 2(x \plus{} 1)\qquad
\textbf{(C)}\ 0\qquad
\textbf{(D)}\ |x \minus{} 1| \plus{} |x \plus{} 1|\qquad
\textbf{(E)}\ \text{none of these}$

[hide="Solution"]
$ \sqrt{x^2\minus{}2x\plus{}1} \equal{} \sqrt{(x\minus{}1)^2} \equal{} |x\minus{}1|$.
$ \sqrt{x^2\plus{}2x\plus{}1} \equal{} \sqrt{(x\plus{}1)^2} \equal{} |x\plus{}1|$.

$ y \equal{} \sqrt{x^2\minus{}2x\plus{}1}\plus{}\sqrt{x^2\plus{}2x\plus{}1}\equal{}\boxed{|x\minus{}1| \plus{} |x\plus{}1|}$ so the answer is $ \textbf{(D)}$.
[/hide]

We can see that the two trinomials underneath the radicals are perfect squares, so
$ y\equal{}|(x\plus{}1)| \plus{} |(x\minus{}1)|$

therefore the answer is $ d$

EDIT: aww owned b/c i dont know how to use LaTex and couldnt figure out absolute value


An ordinary deck of 52 cards with 4 aces is shuffled, and then the cards are drawn one by one until the first ace appears. On the average, how many cards are drawn?

[quote="draperp"]$\sum_{n=0}^48((n+1)\frac{48!(52-n)!}{(48-n)!52!}\frac{4}{52-n})=\frac{53}{5}$[/quote]
Uh, could you explain how you got that expression?

(I made a mistake in the summation expression, but did I edit my post.)

Consider the probability that $n+1$ cards are select until an ace appears.  The first n cards must be non-ace cards and the last must be an ace.
The probablity of selecting n non-ace cards is $\frac{48}{52}\frac{47}{51}\frac{46}{50}...\frac{48-n+1}{52-n+1}=\frac{48!(52-n)!}{(48-n)!52!}$
The probgability that an ace is drawn after that is $\frac{4}{52-n}$.
Multiplying $n+1$ (the number of cards drawn) by the two probabilities yields the expression which is summed from $n=0$ to $n=48$.

The sum can actually be simplified to:
$\sum_{n=0}^{48}\left((n+1)\frac{(51-n)(50-n)(49-n)}{1624350}\right)$


1+y+y^2+y^3+y^4=A whole square of a nnumber.y is a prime number.rate it from 0 to 10 and send me a solution

Rating difficulties is rather subjective, but it is number theory and I have solved it, so it can't be hard. Here's the solution, I don't claim it is the easiest possible one:

[color=blue][b]Problem.[/b] Find all primes y such that $1+y+y^2+y^3+y^4$ is a perfect square.[/color]

[i]Solution.[/i] The prime y = 3 works: $1+3+3^2+3^3+3^4=11^2$ is a perfect square.

We will show that 3 is the only prime with this property. So we will show that, if y is a prime with $y\neq 3$, then $1+y+y^2+y^3+y^4$ is not a perfect square. In fact, for y = 2 this is trivial to check ($1+2+2^2+2^3+2^4=31$ is not a perfect square), and y = 3 was excluded, so we can assume that y > 3. Also note that y is odd, since y is a prime > 2, and thus, $\frac{y+1}{2}$ is an integer. Thus, $y^2+\frac{y+1}{2}$ and $y^2+\frac{y+1}{2}-1$ are two consequent integers.

Now, since y > 3, we have y - 1 > 2, so that $\frac{y-1}{2}>1$, and thus

$1+y+y^2+y^3+y^4=\left(y^2+\frac{y+1}{2}\right)^2-\left(\frac{y-1}{2}\right)^2+1$
$<\left(y^2+\frac{y+1}{2}\right)^2-1^2+1=\left(y^2+\frac{y+1}{2}\right)^2$;

on the other hand,

$1+y+y^2+y^3+y^4=\left(y^2+\frac{y+1}{2}-1\right)^2+\frac14\left(y+1\right)\left(7y-1\right)+1$
$>\left(y^2+\frac{y+1}{2}-1\right)^2$.

Hence, the number $1+y+y^2+y^3+y^4$ lies between the squares of two consequent integers, namely of $y^2+\frac{y+1}{2}$ and $y^2+\frac{y+1}{2}-1$, and hence cannot be a perfect square. So the problem is solved.

  Darij


A vertical cylinder with porshen of mass $M$ contains gas insde it.N number small spheres with mass $m$ are having vertical movement on the porshen.They collide with the porshen and so the porshen is in equilubrium.Atmospheric pressure is $P_{0}$ and the area of porshen is $A$.Find the pressure of gas inside the cylinder.

Porshen  is a plate  which can move inside the cylinder.


[quote="7h3.D3m0n.117"]a 10x10 square is posted as a problem. my classmate thinks there are 100 total squares on it. my other friend says that it should be at least 3x that or something

to solve it would it be $10^{2}+9^{2}+8^{2}+7^{2}+...+3^{2}+2^{2}+1^{2}$?

then would u count the overall square (the big 10x10) so the final equation for completing the problem would be

$10^{2}+9^{2}+8^{2}+7^{2}+...+3^{2}+2^{2}+1^{2}+1$?[/quote]
Just for clarification, if you are looking for the number of squares than $10^{2}+9^{2}+8^{2}+7^{2}+...+3^{2}+2^{2}+1^{2}$ is right. If you are looking for the number of unit squares than there are 100.

to look for the number of squares you could also use the formula n(n+1)(2n+1)/6 which is useful

and for rectangles n(n+1)/2 x m(m+1/2

[quote="now a ranger"]in my formula sheet it says total number of squares is n(n+1)(2n+1)/6 lol  :)[/quote]
Fixed. :blush:

Anyway, the same question was posted in the topic that I posted a link to.

[quote="7h3.D3m0n.117"]
then would u count the overall square (the big 10x10) so the final equation for completing the problem would be

$10^{2}+9^{2}+8^{2}+7^{2}+...+3^{2}+2^{2}+1^{2}+1$?[/quote]

wait a moment. why count the overall square twice? when added the $1^{2}$, you counted it, so you don't need to add $1$. all the other posts are just tricky methods for summing up squares.

[quote="i_like_pie"][quote="7h3.D3m0n.117"]a 10x10 square is posted as a problem. my classmate thinks there are 100 total squares on it. my other friend says that it should be at least 3x that or something

to solve it would it be $10^{2}+9^{2}+8^{2}+7^{2}+...+3^{2}+2^{2}+1^{2}$?

then would u count the overall square (the big 10x10) so the final equation for completing the problem would be

$10^{2}+9^{2}+8^{2}+7^{2}+...+3^{2}+2^{2}+1^{2}+1$?[/quote]
The amount of squares in an $n\times n$ grid is $\sum^{n}_{k=1}k^{2},$ or $\frac{n(n+1)(2n+1)}{6}.$ So there would be $385$ sqaures in a $10\times10$ grid.

The amount of rectangles in an $m\times n$ grid is $\frac{mn(m+1)(n+1)}{4}.$

From [url]http://www.artofproblemsolving.com/Forum/viewtopic.php?t=113738[/url].[/quote]

The amount of rectangles in an $m\times n$ grid is $\frac{mn(m+1)(n+1)}{4}.$
This is from $(\binom{n+1}{2})(\binom{m+1}{2})$.

[quote="bpms"]The amount of rectangles in an $m\times n$ grid is $\frac{mn(m+1)(n+1)}{4}.$
This is from $\binom{n+1}{2}\binom{m+1}{2}$.[/quote]
Yep. You don't need extra parentheses. :wink:

[quote="Ihatepie"][quote="7h3.D3m0n.117"]a 10x10 square is posted as a problem. my classmate thinks there are 100 total squares on it. my other friend says that it should be at least 3x that or something

to solve it would it be $10^{2}+9^{2}+8^{2}+7^{2}+...+3^{2}+2^{2}+1^{2}$?

then would u count the overall square (the big 10x10) so the final equation for completing the problem would be

$10^{2}+9^{2}+8^{2}+7^{2}+...+3^{2}+2^{2}+1^{2}+1$?[/quote]

[hide]There are just 100 total squares in a 10*10 square[/hide][/quote]

There can bee 1 by 1 squares, 2 by 2, 3x3....

Also, do the need to have integral lengths?

i think they don't have to be integer lengths, since the formula works for both nonintegral and integral

duno :lol:

[quote="i_like_pie"][quote="nutz_for2.718281828"]Also, do the need to have integral lengths?[/quote]
If they can be non-integral, then aren't there infinity?[/quote]
But then they aren't rectangles. We are getting off topic, the original poster didn't mean a grid he meant a hundred unit squares combined to make a 10 x 10 square (unless I'm missing something important).


(0,0,0) and (0,1,-1) (with permutations). Not sure if there are any more though.
Edit: Forgot the negative sign in front of the second 1.

[quote="Hokkage"](0,0,0) and (0,1,1) (with permutations). Not sure if there are any more though.[/quote]
$(0,1,1)$? How would a bunch of 1's add together to give you 0?

$x^2+y^2+z^2+x^2y+y^2z+z^2x+x^2z+y^2x+z^2y= (x+y+z)^2$

So $x+y+z= 0$

Algorithm: Set any two numbers for $x$ and $y$, and $z=-(x+y)$.


What do you write down in order to label a line? Like, the arrow that goes right above AB. It would also be helpful to learn how to write the notation for rays and line segments...

\overline{AB}
$ \overline{AB}$

\overrightarrow{AB}
$ \overrightarrow{AB}$

\overleftrightarrow{AB}
$ \overleftrightarrow{AB}$

Hoped it helped!!!  :)

Thanks it really helped!...but now when I put that in it showed an error "undefined control sequence." The same thing shows up whenever I do a box.

You must have \usepackage{amsmath} in your preamble. You should use it in all your documents along with \usepackage{amssymb}.

[quote="Dojo"]Find it [url=http://www.ams.org/tex/amslatex.html]Here[/url]

However, it is already installed on the forum.[/quote]
And it will be already installed in any LaTeX distribution on your computer; you just have to use it.


What do you think are the advantages and disadvantanges of diversity in a society?

I think this is a very interesting question.  Perhaps you want to do something to get a discussion started?  For instance, what piqued your curiosity?

A good think is that you can know new cultures, and a bad one is discrimination...........

If there is no diversity, everyone is the same, society does not change, does not develop, we are doomed. It is progress which really defines humankind, and only the people who choose to be different drive the progress. If you are the same as everyone else, nobody remembers you. This is my belief.

True. They remember you if you are different, if you make "the" difference


function
inequalities
limit
logarithms
abstract algebra
inequalities unsolved

Prove that for all $ n\in N*$ we have :$ \frac{1}{n\plus{}1}\plus{}Ln n\leq Ln(n\plus{}1)$

The lhs of the equation can be simplified like this:

$ \frac{1}{n\plus{}1} \plus{} Ln(n) \equal{} \frac{1}{n\plus{}1} Ln(e) \plus{} Ln(n) \equal{} Ln(n e^{\frac{1}{n\plus{}1}})$

Because the function $ Ln$ is one to one:  $ Ln(n e^{\frac{1}{n\plus{}1}}) \leq Ln(n\plus{}1)$

becomes $ n e^{\frac{1}{n\plus{}1}} \leq n\plus{}1$ or $ e \leq (1\plus{}\frac{1}{n})^{n\plus{}1}$

wich is a well know inequality with $ e\equal{} \lim_{n \to \infty} (1\plus{}\frac{1}{n})^{n\plus{}1}$

... or if you know Lagrange's theorem you can easily apply it here (and generally for many inequalities):
$ \ln(n\plus{}1)\minus{}\ln n \equal{} (n\plus{}1\minus{}n) (\ln c)'$, where $ c \in (n; n\plus{}1)$ so $ \ln(n\plus{}1)\minus{}\ln n \ge \frac{1}{n\plus{}1}$.

Yes, I had it for homework (using Lagrange).

You can somewhat extend the problem, to make it a little bit more interesting (although the ideas remain the same):

$ \frac {1}{a \plus{} 1} < \ln \left(1 \plus{} \frac {1}{a}\right) < \frac {1}{a}$

where $ a\in\mathbb{R}^ \plus{}$.


abstract algebra
group theory
function
induction
superior algebra
superior algebra unsolved

hi

elementary abelian means: of form Cp*...*Cp with prime
let G be a pgroup and H the intersection of all maximal ideals

show that G/H is elementary abelian, and that if N is a normal subgroup of
G, G/N elementary abelian implies N contains H

i can do the first but not the second

while showing the first, i showed that H contains all pth powers

but for the second , i would have to show that H is also generated by them
any ideas

For the first if M_1, ..., M_n are the max subgroups then the natural induced homomorphism G -> G/M_1 x ... x G/M_n has ker = H and each M_i have order |G|/p (because G is p-group) so done.

For the second part if G/N is elementary abelian suppose (by rearranging if necessary) M_1, M_2, ..., M_k are [i]all[/i] the max subgroups containing N.  Consider K, the intersection of all those.  So N <= K.  Note that a max subgroup M contains K iff it contains N (if it contains K then clearly contains N.  If it contains N then it is one of M_i, i = 1 to k so contains N).  So the number of max subgroups of G/N and G/K are the same.  Furthermore, they are both clearly elementary abelian.

We only need to prove the following thing:

If G is an elementary abelian p-group of order p^m, then it has (p^m - 1
)/(p-1) max proper subgroups.

In that case since (p^m - 1)/(p - 1) is a increasing function in m, the fact that G/N and G/K have the same number of max subgroups implies that |G/N| = |G/K| (in fact G/N ~= G/K) whence |N| = |K|, hence N = K since N <= K.

The above is not hard to prove, by induction on m.  For m = 0, 1, 2 it's clear.  For the 2nd induction step, if |G| = p^m there are (p^m - 1)/(p-1) subgroups of order p and mod G by each of them and use induction hypothesis.


Because I don't want to write stuff out myself, I let google do it for me! :)

http://www.math.ucsb.edu/~mckernan/Teaching/02-03/Autumn/202A/l_26.pdf

[quote="amcavoy"]How do you prove that $\sum_{n}a_{n}$ converges if and only if $\prod_{n}\left(1+a_{n}\right)$ converges?[/quote]

this is false. Absolute convergence is true. Otherwise you need also $\sum_{n} a_n^2$ converges.


geometry
geometric transformation
reflection

We know that the sum of the interior angles of a convex polygon is $ 180(n\minus{}2)$. This is derived by forming $ (n\minus{}2)$ triangles from a convex polygon with n sides or n vertices. We also know that this is true for non-convex polygon.

How do we prove that for any non-convex polygon, we can also form $ n\minus{}2$ triangles?

Suppose the $ n$-gon has vertecies $ a_1,a_2...a_n$. If the polygon is not convex then there is atleast one interior angle $ > 180^o$. wlog let one be $ \angle a_1a_2a_3$.

If we reflect the point $ a_2$ over the line $ a_1a_3$ then that interior angle becomes $ < 180^o$.

Furthermore the sum of the angles in the new polygon has remained unchanged, which is easy to see if you sketch it.

So if you can prove that after a finite number of such reflections the polygon becomes convex then the rest of the proof will be the same as for a convex n-gon


Congrats!!!
Team China got 6 gold! :lol:

[quote="shobber"][quote="Skyward_Sea"]Where's Jin? Now he really got a "Jin" medal.
I would like him to post the CHINA TST solution...[/quote]
Yep. A real Jin medal!  :rotfl:

By the way, I have the solutions to China TST 2006, do you want it now?[/quote]
Of course!!!!    How did you get access to the answers?
m_ty1@hotmail.com   please.
Congratulations to Jin again!

Hi Jin, welcome back.

Do you have the problems of past China TST Quizzes? I mean, before 2001. They are really difficult to find via Internet......

[quote="Skyward_Sea"][quote="José"][quote="José"]Hi Chinese Community!!!! I'd like to know what do you think about your contestants in this IMO and what do you think about problem number 6, that only 2 out of 6 could solve it. Please, talk in English because I know no Chinese. Thanks.[/quote]

I'd appreciate if anyone could answer me. Thanks.[/quote]

To José:
IMO(=In My Opinion), P6 is not so hard. At least I solved it.
The contestants would all get 42 if they are in good style. Even the ones who were eliminated in TST and other qualifications are possibly to win a gold medal.

To Jin:I had the solutions already. BTW,有人提前确定自己进入国家队吗？（最后一场考试前领先第七63分以上）[/quote]
Come on, you were solving the problem in a really relaxing condition, but all the other contestants were stressed and huge pressure was pushing them throughout the 4.5 hours. Therefore it was of no suprise at all to see only 2 of the six Chinese Team members successfully solved the problem. After all, you won't worry about something like inadequate time, cut-offs, etc if you simply solve it for leisure at home.
As what I've known from one of the 2005 Chinese team member, the 5th and 6th place of Chinese team are determined by "voting", rather than simply comparing their total scores at the TST. So the guy you are mentioning (if really exist) has to beat the 5th by more than 63 points, instead of the 7th.

To mecrazywong:I know, I know. That's why the 6 people who passed several selective tests would make mistake--the stress! And maybe that's why I can't get through those qualifications.
And if the 6th and 7th(or more) have the same score, I recommand PK. :ninja:

[quote="Soarer"][quote="jin"]OK I'm here,thank you for your congratulation.
I must have some time to find out the solutions to the TST.
So if shobber did give you,then I'm happy I needn't to think what's the problem.
Thank you shobber,and also Skyward_Sea.
Another thing:Although I soluted the last six problem in TST,but because of bad writing,I just got less than five problem's score:102. :(
But luckily I can be in IMO2006 and get a gold medal. :)[/quote]

congratulations!
May I know if you will go to Bei da next year?[/quote]

I'll go to PKU this year.

In fact,problem 6 can be solved by everyone of us if we have enough time.Three of us(including me) spent too much time(about 3 hours) on the 5th problem.
But to have a really good solution like the official one is difficult.


trigonometry
inequalities
geometry proposed
geometry

Prove that

$ \sum\sin \frac{A}{2}\geq2\sum\frac{\sqrt{(s\minus{}b)(s\minus{}c)}}{b\plus{}c}$

.

Since $ \sin\frac A2\equal{}\sqrt{\frac{(s\minus{}b)(s\minus{}c)}{bc}}$ and $ \sqrt{bc}\le \frac{b\plus{}c}{2}\ \implies\ \sin\frac A2\ge 2\cdot\frac{\sqrt{(s\minus{}b)(s\minus{}c)}}{b\plus{}c}$

Adding up the similar inequalities yields the desired result .


group theory
abstract algebra
superior algebra
superior algebra unsolved

[quote="Jacobson"]Can someone find a non-normal subgroup of $\mathcal{Q}_{8}\times \mathbb{Z}_{4}$ for me.

thanks :)[/quote]

I dont think so.
Because $\mathcal{Q}_{8}$ is a very special group*. All its subgroups are normal.
And $\mathbb{Z}_{4}$ is abelian so all subgroups are normal.

So the product of these is such that any subgroup of $\mathcal{Q}_{8}\times \mathbb{Z}_{4}$ is normal.

*Groups that have all subgroups normal are called Dedekind groups. Note, abelian groups are Dedeking but not conversely. Those groups are called Hamiltonian groups. The smallest example of a Hamiltonian group is $\mathcal{Q}_{8}$

[quote="sylow_theory"]
any subgroup of $\mathcal{Q}_{8}\times \mathbb{Z}_{4}$ is normal.
[/quote]

According to [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?highlight=hamiltonian&t=127859]the general structure theorem[/url] on Hamiltonian groups, that's wrong :).

There are non-normal subgroups, and I could write one down, but wouldn't you find it more satisfactory to find one yourself, Jacobson? :). Try a little harder. There aren't that many possibilities anyway.

[quote="grobber"]
There are non-normal subgroups, and I could write one down, but wouldn't you find it more satisfactory to find one yourself, Jacobson? :). Try a little harder. There aren't that many possibilities anyway.[/quote]
It seems your general stucture theorem is unproven  :wink:


calculus
function
inequalities
calculus computations

We are given a real function $ g(x) $ s.t. $ g(0) = 0 $.

Also, we are given that $ g'(x) + 3 g(x) \leq 1 $ where $ g'(x) = \frac{d (g(x))}{dx} $.

Prove that $ g(x) \leq \frac{1}{3} $

$g'(t)+3g(t)\leq 1$. Multiply by $e^{3t}$ to get $e^{3t}g'(t)+3e^{3t}g(t)\leq e^{3t}$. Integrate from $0$ to $x$ to get $e^{3x}g(x)\leq \frac{e^{3x}}{3}-\frac{1}{3}$ from which we take $g(x)<\frac{1}{3}$

This is a wondeful question indeed!!!! How did you think of multiplying $ e^{3x} $ ??????

[quote="Rushil"]How did you think of multiplying $e^{3x}$  ??????[/quote]
I can't speak for galeos' mind, but here's a very good reason:
Suppose we have a first order linear differential equation $f'(x)=p(x)f(x)+q(x)$, where $P(x)$ is an antiderivative of $p(x)$. We solve this equation with a multiplying factor: let $f(x)=g(x)e^{P(x)}$. The equation becomes
$g(x)p(x)e^{P(x)}+g'(x)e^{P(x)}=p(x)g(x)e^{P(x)}+q(x)$, so $g'(x)=q(x)e^{-P(x)}$, and we can integrate (using the initial condition) to find $g$.
It is only natural to apply this method to the inequality and find out where it leads.


Prove that in a triangle ABC in which m(A)<=m(B)<=m(C)<90 and m(B)>=60 then we have mb>=ha.

okay.. g'luck!

I don't think it's true. Think of the following case: A<B=C. B will be of course >60, but ha=ma>mb because a<b and by using the median thm which gives us the length of the median, we ca see that the longest median corresponds to the shortest side and vice-versa.

Hey, happy birthday :D
How about what I asked? Do you think the problem is wrong or what?  :)

10x

I am thinking.. it can't be wrong cause somebody gave it to me and he said that it was from a contest, a math contest... and I don't think that they give false problems at contest!!

just let me think a bit more! :D

anybody else got any comments cause I am beggining to think that grobber is right! :D


The date of the membership of Vornicu will give you a pretty good upper bound ...

[url=http://www.mathlinks.ro/Forum/profile.php?mode=viewprofile&u=2&sid=35f9ff4442d6966b356a9758e576f3d6]Valentin Vornicu's profile[/url]

Note that Valentin Vornicu started this site MathLinks in February 2003.  (I joined in July 2003.)

The merge AOPS-Mathlinks was in 2004. I still use MathLinks.

I find it weird  :|  that this site [url=http://www.artofproblemsolving.com/AboutUs/AoPS_A_Company.php]this site[/url] says Valentin Vornicu "joined" AOPS.

[quote="Xevarion"][quote="fredbel6"]I find it weird  :|  that this site [url=http://www.artofproblemsolving.com/AboutUs/AoPS_A_Company.php]this site[/url] says Valentin Vornicu "joined" AOPS.[/quote]
I think it means "joined" as in "joined the staff of the company."[/quote]
Isn't it more like... he was part of MathLinks and MathLinks merged with AOPS?

[quote="Xevarion"][quote="fredbel6"]Isn't it more like... he was part of MathLinks and MathLinks merged with AOPS?[/quote]
Well I am not an authority on this, but I was under the impression that Mathlinks was just a forum, whereas Art of Problem Solving is actually a company that does other stuff too. Before, Valentin was running Mathlinks; after the merge, he was part of the AoPS staff, an employee of the company. Maybe as a Mathlinker you only see it as the forums and there the merge is "equal" in a sense, but if you see the old AoPS forum as just a part of AoPS then it makes more sense to speak of the merge as Mathlinks joining AoPS.[/quote]
Ah I see.  Well I have always spoken of MathLinks (I find its layout much better  :wink: .)
I have never really used any of the other things AOPS provides.  It seems MathLinks itself started as a nice international community (with outrageously powerful members  :o ) and AOPS is more commercial . :|

EDIT : does anyone know what happened to the MathLinks shirts you could order? :D

[quote="Xevarion"]
Well I am not an authority on this, but I was under the impression that Mathlinks was just a forum, whereas Art of Problem Solving is actually a company that does other stuff too. Before, Valentin was running Mathlinks; after the merge, he was part of the AoPS staff, an employee of the company. Maybe as a Mathlinker you only see it as the forums and there the merge is "equal" in a sense, but if you see the old AoPS forum as just a part of AoPS then it makes more sense to speak of the merge as Mathlinks joining AoPS.[/quote]

I'll agree with this.  I don't recall mathlinks doing anything beyond the forum and the mathlinks contest.  But AoPS was certainly a company with their two books and classes.  On a sidenote, the AoPSer t-shirts came after the merge.

EDIT:

[quote]Ah I see. Well I have always spoken of MathLinks (I find its layout much better :wink: .)
I have never really used any of the other things AOPS provides. It seems MathLinks itself started as a nice international community (with outrageously powerful members ) and AOPS is more commercial . :|

EDIT : does anyone know what happened to the MathLinks shirts you could order? :D [/quote]

The ones with $\pi^{2}>2^\pi$?  I almost forgot about those!  Yeah...dunno what happened to those.

Well, mathlinks was started by Valentin when he was still in school I think.  AoPS the website was started by Rusczyk and Crawford after they had gone to school and had held other jobs for a little while.  They needed to make a living, so the only way they could start AoPS up and devote all their time to it was to to make it a business.  But AoPS is not just about making money (the founders made more with their other jobs).  Rather, they provide as much free, accessible math resources to the public as possible...the message boards, math jams, and the wiki.  I feel that people should use the wiki more and contribute to it.  I have to admit that I haven't been able to do much on it now that school's started, but I still suggest everyone else helping out.  The internet deserves to have a large, comprehensive searchable database of problem solving math topics.  Mathworld's OK, but very unsatisfying in many ways...


inequalities
function
four variables
4-variable inequality
algebra
IMO Shortlist

[quote="cezar lupu"]Clearly, it follows from Cauchy-Schwarz inequality. ;)[/quote]
Again you start the same bad behavior. If you don't post a full solution don't post anything. maybe you are a genius and you understand all things with a first sight and with only a hint. If yes congratulations you are the best. :lol:

[quote="silouan"][quote="cezar lupu"]Clearly, it follows from Cauchy-Schwarz inequality. ;)[/quote]
Again you start the same bad behaviour. If you don't post a full solution don't post anything.[/quote]
Agreed... however a little frustration a day seems to be healthy. ;)

(solution split off into new post for resource project)

[quote="Peter"]By Cauchy-Schwarz we have $ \left(\sum_{cyc}\frac{a}{b\plus{}2c\plus{}3d}\right)\left(\sum_{cyc}a(b\plus{}2c\plus{}3d)\right)\ge\left(\sum_{cyc}a\right)^{2}$

So our LHS is greater than $ \frac{(a\plus{}b\plus{}c\plus{}d)^{2}}{4(ab\plus{}ac\plus{}ad\plus{}bc\plus{}bd\plus{}cd)}\ge\frac{2}{3}$, where the latter follows from 6 times AM-GM on the numerator.

Alternatively one can apply Jensen on the convex function $ f(x) \equal{}\frac{1}{x}$ to obtain the same results.[/quote]
$ (a\plus{}b\plus{}c\plus{}d)^{2}\equal{} 2(ab\plus{}bc\plus{}cd\plus{}da\plus{}ac\plus{}bd)\plus{}a^{2}\plus{}b^{2}\plus{}c^{2}\plus{}d^{2}\geq\frac{8}{3}(ab\plus{}bc\plus{}cd\plus{}da\plus{}ac\plus{}bd)$
So,we have $ \frac{(a\plus{}b\plus{}c\plus{}d)^{2}}{4(ab\plus{}ac\plus{}ad\plus{}bc\plus{}bd\plus{}cd)}\ge\frac{2}{3}$

[quote="Peter"]By Cauchy-Schwarz we have $\left(\sum_{cyc}\frac{a}{b+2c+3d}\right)\left(\sum_{cyc}a(b+2c+3d)\right) \ge \left(\sum_{cyc}a\right)^2$

So our LHS is greater than $\frac{(a+b+c+d)^2}{4(ab+ac+ad+bc+bd+cd)}\ge\frac{2}{3}$, where the latter follows from 6 times AM-GM on the numerator.

Alternatively one can apply Jensen on the convex function $f(x)=\frac1x$ to obtain the same results.[/quote]
well my solution with Cauchy Schwarz was same. But i am a bit uncomfortable with Jensen's. So, could you elaborate that solution too.. ??

[quote="Fermat -Euler"]Prove that \[ \frac{a}{b+2c+3d} +\frac{b}{c+2d+3a} +\frac{c}{d+2a+3b}+ \frac{d}{a+2b+3c} \geq \frac{2}{3} \] for all positive real numbers $a,b,c,d$.[/quote]

Using Titu's lemma we get,
\[ \frac{a^2}{a(b+2c+3d)} +\frac{b^2}{b(c+2d+3a)} +\frac{c^2}{c(d+2a+3b)}+ \frac{d^2}{d(a+2b+3c)} \geq \frac{(a+b+c+d)^2}{4(ab+ac+ad+bc+bd+cd)}.\]

From here it is sufficient to prove that,
\[\frac{(a+b+c+d)^2}{4(ab+ac+ad+bc+bd+cd)}\ge \frac{2}{3}.\]

Cross multiplying we get,
\[3(a+b+c+d)^2\ge 8(ab+ac+ad+bc+bd+cd).\]
Expanding $3(a+b+c+d)^2$, rearranging terms, and adding $a^2+b^2+c^2+d^2$ to both sides we get,
\[4(a^2+b^2+c^2+d^2) \ge (a+b+c+d)^2.\]

Since this is true by Cauchy-Schwarz, we are done. $\blacksquare$

[hide="Cool"]

Let $W = b+2c+3d, X = c+2d+3a, Y = d+2a+3b, Z = a+2b+3c$.  The inequality becomes:

$\dfrac{-5W+7X+Y+Z}{24W} + \dfrac{-5X+7Y+Z+W}{24X} + \dfrac{ -5Y + 7Z + W+X }{24Y} + \dfrac{-5Z+7W+Y+X}{24Z} \ge \dfrac{2}{3}$
which is true from AM-GM.
[/hide]

Quite easy ISL, once you know Titu Lemma.
Multiply numerator and denominator of each fraction by its numerator.
$LHS\geq\frac{(a+b+c+d)^2}{4(ab+bc+cd+da+ac+bd)}$
We need to prove $3(a+b+c+d)^2\geq 8(ab+ac+ad+bc+bd+cd)$.
Expand RHS, and we get something obvious by C-S

[quote=sqing][quote=Fermat -Euler]Prove that \[ \frac{a}{b+2c+3d} +\frac{b}{c+2d+3a} +\frac{c}{d+2a+3b}+ \frac{d}{a+2b+3c} \geq \frac{2}{3} \] for all positive real numbers $a,b,c,d$.[/quote]
[url=https://artofproblemsolving.com/community/c6h1089033p13060380]Prove that[/url]
$$\frac{a}{4a+5b+c+5d}+ \frac{b}{4b+5c+d+5a}+\frac{c}{4c+5d+a+5b}+\frac{d}{4d+5a+b+5c}\leq \frac{2}{5}$$ for all positive real numbers $a,b,c,d.$[/quote]

shouldnt be the sign on the opposite side?

[quote=Vidush]Sir what is Jensen pl tell[/quote]

Jensen Inequality
https://en.m.wikipedia.org/wiki/Jensen%27s_inequality

[quote=Vidush]Sir what is Jensen pl tell[/quote]

If a function is convex in an interval $A\subseteq \mathbb{R}$($f''(x)>0$ for every $x\in A$) then for every $a_i\in A$ holds that $\frac{f(a_1)+f(a_2)+...+f(a_n)}{n}\geq f(\frac{a_1+a_2+...+a_n}{n})$.
If a function is concave in an interval $A \subseteq \mathbb{R}$($f''(x)<0$ for every $x\in A$) then for every $a_i\in A$ holds that$\frac{f(a_1)+f(a_2)+...+f(a_n)}{n}\leq f(\frac{a_1+a_2+...+a_n}{n})$

[quote=Cezar Lupu]Clearly, it follows from Cauchy-Schwarz inequality. ;)[/quote]

whats that?(too lazy to spell it out)

[quote=jacoporizzo][quote=isaacmeng]Could someone post a solution using Jensen's with $f(x)=\frac{1}{x}$?[/quote]

Using the weighted form of Jensen, $$\sum_{\text{cyc}} (\frac{a}{a+b+c+d} \cdot \frac{1}{b+2c+3d}) \geq \frac{1}{\frac{1}{a+b+c+d} \cdot (\sum_{\text{cyc}} a(b+2c+3d))} = \frac{a+b+c+d}{4(ab+ac+ad+bc+bd+cd)}$$ $$\Rightarrow  \sum_{\text{cyc}} \frac{a}{b+2c+3d} \geq \frac{(a+b+c+d)^2}{4(ab+ac+ad+bc+bd+cd)}$$ and then proceed as in the above solutions.[/quote]

Thanks!

[b][color=#00f]My Solution:[/color][/b]
So in this problem we can apply holder's inequality or we can say cauchy's functional equation since holder at power 1 is cauchy so yeah whatever.\\
this can be written as\[\sum_{cyc}\frac{a}{b+2c+3d}\geq \frac23\]
we can apply holder's here like below
\[\left(\sum_{cyc}\frac{a}{b+2c+3d}\right)^1\left(\sum_{cyc}a(b+2c+3d)\right)^1\geq (a+b+c+d)^2\]
So its suffice to prove that
\[(a+b+c+d)^2\geq \frac23\left(\sum_{cyc}a(b+2c+3d)\right)\]
\[a^2+b^2+c^2+d^2+2ab+2ac+2ad+2bc+2bd+2cd\geq \frac23\left(\sum_{cyc}ab+2ac+3ad\right)\]
\[\implies \sum_{cyc}a^2+2\sum_{sym}ab\geq \frac23\left(4\sum_{sym}ab\right) \]\[\implies 3\sum_{cyc}a^2+6\sum_{sym}ab\geq 8\sum_{sym}ab\]
\[\implies 3(a^2+b^2+c^2+d^2)\geq 2\sum_{sym}ab\]
which is true by AM-GM so we are done !.$\blacksquare$

this inequalities homogeneous , so we can assume that $a+b+c+d=1$
and by titu's lemma we have $LHS \ge \dfrac{(a+b+c+d)^2}{4(ab+ad+ac+bc+dc+bd)}$
we know that  $ab+ad+ac+bc+dc+bd\le \frac83$ (by newton's inequality) so $LHS\ge \frac23$

$\color{magenta} \boxed{\textbf{SOLUTION A3}}$

By $\textbf{Titu's Inequality,}$
$$\frac{a^2}{a(b+2c+3d)} +\frac{b^2}{b(c+2d+3a)} +\frac{c^2}{c(d+2a+3b)}+ \frac{d^2}{d(a+2b+3c)} \geq \frac{(a+b+c+d)^2}{4(ab+ac+ad+bc+bd+cd)}$$
$$\implies \frac{(a+b+c+d)^2}{4(ab+ac+ad+bc+bd+cd)}\ge \frac{2}{3}$$
$$\implies 3(a+b+c+d)^2\ge 8(ab+ac+ad+bc+bd+cd)$$
$$\implies 4(a^2+b^2+c^2+d^2) \ge (a+b+c+d)^2$$

But by $\textbf{Cauchy-Schwarz Inequality,}$
$$(1^2 +1^2 +1^2 + 1^2)(a^2+b^2+c^2+d^2) \ge (a+b+c+d)^2 \implies 4(a^2+b^2+c^2+d^2) \ge (a+b+c+d)^2 \blacksquare$$


function
limit
real analysis
real analysis unsolved

Let $ f,g: \mathbb{R} \to \mathbb{R}$ two functions satisfying :

1.$ |f(x\plus{}y)\minus{}f(x)\minus{}f(y)|\leq \frac{|g(y)|}{1\plus{}|x|} ,\forall x,y \in \mathbb{R}$
2.f is diferentiable at $ 0$ and $ f'(0)\equal{}a \in\mathbb{R}$

Prove that $ f(x)\equal{}ax$ , $ \forall x\in \mathbb{R}$

First observe that $ f(0) \equal{} 0$, putting $ y \equal{} 0$ and taking $ x\to\infty$ . Then fix $ y$. Then taking $ x\rightarrow\infty$ we have $ \lim_{x\rightarrow\infty}(f(x \plus{} y) \minus{} f(x)) \equal{} f(y)$ (*)
Then because $ x\rightarrow\infty\Leftrightarrow x \plus{} y\rightarrow\infty$ we can put $ x\leftarrow x \plus{} y$ so we will have from (*):
$ \lim_{x\to\infty}(f(x \plus{} 2y) \minus{} f(x \plus{} y)) \equal{} f(y)$ (**).
But because $ y$ was arbitrary we can put $ 2y$ in (*):
$ \lim_{x\rightarrow\infty}(f(x \plus{} 2y) \minus{} f(x)) \equal{} f(2y)$ (***).
Then from (***)-(**)-(*) we get $ f(2y) \equal{} 2f(y)$ (for any $ y$).
So we have $ f(y) \equal{} 2^{n}f(\frac {y}{2^{n}})$, $ \forall n\in \mathbb{N}$. Taking $ n\to\infty$ we have $ f(y) \equal{} y\lim_{n\to\infty} \frac {f(\frac {y}{2^{n}}) \minus{} f(0)}{\frac {y}{2^{n}}} \equal{} ay$


Please help me with mod. explain to me how it works.

how do we solve this

2^2007 divided by 5=?

First we find a pattern in powers of 2, when divided by 5

$ 2\equiv 2\pmod{5}$
$ 2^2 \equiv 4 \pmod{5}$
$ 2^3 \equiv 8 \equiv 3 \pmod{5}$
$ 2^4 \equiv 16 \equiv 1 \pmod{5}$
$ 2^5 \equiv 32 \equiv 2 \pmod{5}$

One fact that we can get from this pattern is $ 2^{4k \plus{} 1} \equiv 2\pmod{5}$ and since $ 2^{2007} \equal{} 2^{2004 \plus{} 1} \cdot 2^2$
$ 2^{2007} \equiv 2^{2004 \plus{} 1} \cdot 2^2\pmod{5}$
$ 2^{2007} \equiv 2 \cdot 4 \pmod{5}$
$ 2^{2007} \equiv 8 \equiv \boxed{3} \pmod{5}$

Another form:
$ 2^2 \equiv 4 \equiv \minus{}1 \pmod{5}$
$ (2^2)^n \equiv (\minus{}1)^n \pmod{5}$
$ 2^{2n} \equiv (\minus{}1)^n \pmod{5}$
$ 2^{2007}\equiv 2^{2006} \cdot 2 \equiv (\minus{}1)^{1003} \cdot 2\equiv \minus{}2 \equiv \boxed{3} \pmod{5}$

Also, by Fermat's little theorem, $ 2^{4}\equiv 1\pmod 5$. Obviously, $ 2004\equiv 0\pmod 4$, so $ 2^{2007}\equiv 2^{3}\equiv 8\equiv \boxed{3}\pmod 5$.

ok thx a lot!!!!!

This method was taught to me already but ive just forgot it!
TY!


Four bugs sitting at the corners of the unit square begin to chase one another with unit speed, each maintaining a course in the direction of the one pursued. Describe the trajectories of their motions. What is the length of each trajectory? What is the law of motion (in Cartesian or polar coordinates)?

[hide="my answer"]Are they four quarters of a circle?[/hide]


Let $ P$ be a set of n points in general position in $ \mathbb{R}^2$, where $ n$ is even. Prove that the number of $ (\frac{n}{2} \minus{}1)$-edges of $ P$ is no greater than the number of $ (\frac{n}{2} \minus{}2)$ edges of $ P$.

A $ k$-edge is a pair of points in $ P$ so that the line passing through them has exactly $ k$ points of the set $ P$ in the open half-plane which is to the "left" of the line. Also, [url=http://graphics.stanford.edu/~jgao/kset.ps]see this[/url].


If a+b+c=0 and a,b,c>= -5
find all possible integral solutions for a,b,c.

[hide]Make substitution $ x\equal{}a\plus{}5, y\equal{}b\plus{}5, z\equal{}c\plus{}5$ (notice that $ x, y, z \ge 0$)

Now we have:

$ x\plus{}y\plus{}z\equal{}15$

Since there are no restrictions besides $ x, y, z$ are non-negative integers, the number of solutions is just $ \binom {17}{2}\equal{}\boxed{136}$

It would take too long to list them all :)[/hide]


Find all polynomials $ P$ with real coefficients satisfying
$ P(x^2) \equal{} P(x)P(x \plus{} 2)$
for all real numbers $ x$.

$ x \equal{} r$ gives $ P(r^2) \equal{} 0$. If $ 0 < |r| < 1$ or $ |r| > 1$, then this equation can be used to generate an infinite amount of roots. (admittedly the zero polynomial is another solution)

[quote="mto"]Let r be any complex root of P(x), then r=0 or |r|=1

If r=0, we have P((-2)^2)=0 --> 4 is a root of P(x), contradiction

If |r|=1, r=a+i.b

We have |r-2|=1, from here we have a=1 and b=0

Hence P(x)=(x-1)^n[/quote]

the problem said $ P(x^2) \equal{} P(x)P(x \plus{} 2)$ only for real numbers

Why are you so quick to dismiss correct things? You do this all the time... the identity holds everywhere, since the polynomial $ P(x^2) \minus{} P(x)P(x\plus{}2)$ has infinitely many roots and is hence zero.


inequalities
inequalities proposed
algebra

[quote="cezar lupu"][color=green]
Let $a, b, c>0$ such that $a+b+c=1$. Prove that the following inequality holds true:

                   \[ \sqrt{ab+c}+\sqrt{ca+b}+\sqrt{bc+a}\geq 1+\sqrt{ab}+\sqrt{bc}+\sqrt{ca}.  \]
[/color][/quote]

Happy New Year!!

It's equivalent to APMO 2002 (http://www.kalva.demon.co.uk/apmo/apmo02.html) via the substitution $(a,b,c)\rightarrow (x^{-1}, y^{-1}, z^{-1})$.

We have that:

$\sqrt{ab+c}+\sqrt{ca+b}+\sqrt{bc+a}\geq a+b+c+\sqrt{ab}+\sqrt{bc}+\sqrt{ca}$.

So, we have to prove that:

$\sqrt{ab+c}\geq c+\sqrt{ab}$

$\Rightarrow  ab+c\geq c^2+ab+2c\sqrt{ab}$
$\Rightarrow  1\geq c+2\sqrt{ab}$
$\Rightarrow  1\geq 1-a-b+2\sqrt{ab}$
$\Rightarrow  a+b\geq 2\sqrt{ab}$
$\Rightarrow  (\sqrt{a}-\sqrt{b})^2\geq 0$, which is true $\blacksquare$

By C-S,
$\sum \sqrt{bc+a}=\sum \sqrt{(a+b)(a+c)}\le \sum (a+\sqrt{bc})=1+\sum \sqrt{bc}.$

Let $a, b, c>0$ such that $a+2\sqrt{bc}=1$. Prove that
$$ \sqrt{ab+c}+\sqrt{ca+b}+\sqrt{bc+a}\geq 1+\sqrt{ab}+\sqrt{bc}+\sqrt{ca}$$
Let $a, b, c>0$ such that $a+2bc=1$. Prove that
$$ \sqrt{ab+c}+\sqrt{ca+b}+\sqrt{bc+a}\geq\frac{3(\sqrt 3-1)}{2}+\sqrt{ab}+\sqrt{bc}+\sqrt{ca}$$


ratio
trigonometry
Pythagorean Theorem
geometry

the problem is a bit long but simple.
           we all know that in a triangle,the side opposite to the greater angle is always greater than the side facing a smaller angle.we also know if the angles becomes equal, the opposite sides also become equal.
          now , can we say the sides always vary in the ratio of the angles they are facing????
      for eg if two angles of a tringle is 90 and 30 degrees, will their opposite sides be in the ratio of 3#1[as,90#30=3#1]
           please help me........

[hide="Explanation"]
The example you gave is a special case, it is the 30-60-90 triangle. We can prove, using the Pythagorean Theorem, the ratios seen [hide="here"][img]http://upload.wikimedia.org/wikipedia/commons/4/45/30-60-90_triangle.jpg[/img][/hide].

From this we see a possibility that the ratio of the sides isn't the same as the ratios of the angles. Here is an example:

 [geogebra]a63e04774552d6007a0bba84b4a6d0a355388fd2[/geogebra]

In both triangles, we have a right angle at the bottom. The vertical line in the bottom triangle is bisected by a point in the triangle. Now we will compare them (top to bottom). So we have two triangles, with one side the same, one side cut in half, and one side changing slightly (in length). Now we compare that to the angles. We know the right angle stays the same. We know that the top right one changes slightly. The question is, how much did the bottom right angle change? To answer this, we will think about a protractor.

 [geogebra]a498f33ef018af1fe19d52f841f97bec5cc3890a[/geogebra]

Now, there are two angles going out from the center of the circle. If we look at the triangle formed by the larger angle, the line dropping down to the radius, and the radius, that is our first triangle. The second one does not appear, since there are no points on the longes vertical line, except for where the smaller angle intercepts it. So, if we prove that the only point on the largest vertical line is NOT the bisector of the largest vertical line, then we have proved that the ratios between the angles and side lengths of triangles don't hold true.

We know the smaller angle is half of the larger angle. This implies that the arc length between the radius and smaller angle is equal to the arc length between the smaller angle and the larger angle. We also know that the arcs aren't vertical, they are slightly slanted. Now, imagine there was a line from the intersections of the circle with both the angles. That is an approximation of the arc. Now, as we slide the bottom point down so that the line has a vertical position, we have extended the line, therefore, ruining the ratios. So we have proved that the ratios don't hold true.

We can also use trigonometry to prove this in a more rigouris way. So the answer to your question is no. If it was true, then trigonometry wouldn't exist!
[/hide]

[quote="PowerOfPi"]
So the answer to your question is no. If it was true, then trigonometry wouldn't exist!
[/quote]

Ha ha, great thought to put in. A world without trig....

If there are two congruent (equal) angles in a triangle, then the sides opposite the angles are congruent. If there are three congruent angles in a triangle, then all sides are equal (equilateral triangle).


$ a^9\plus{}b^9\equal{}2$.
Prove that $ a^3\plus{}b^3 \ge 2ab$

[quote="Litlle 1000t"]$ a^9 \plus{} b^9 \equal{} 2$.
Prove that $ a^3 \plus{} b^3 \ge 2ab$[/quote]

Posted before

[url]http://www.mathlinks.ro/viewtopic.php?t=176919[/url]


Try the formulas out:

cone=1/3bh, where b is base area
cylinder=bh
sphere=4/3pir^3

[quote="ackter78692"]A cylinder,a sphere and a cone are identical in height and width. Do their volumes have any sort relationship? if so, what is it?[/quote]
The ratio is 3:2:1.

Well let the width be n. Since we have a sphere, the heihgt is also n.

Cylinder- Diameter=n so pi(n/2)^2xn=n^3pi/4

Cone-Diameter=n so 1/3pi(n/2)^2xn=n^3 pi/12

Sphere radius=n/2. 4/3pi(n/2)^3=n^3 pi/6.

Multiplying all by 12/n^3pi we get 3(cylinder):2(sphere):1(cone)


Prove that if we color each edge of the complete graph on order 6 by red or blue, there exists a mono-colored quadrilateral. :?:

In simpler terms, if we have 6 noncollinear points. And we colour the edges with blue and red paint. There exists a monocolored quadrilateral

Maybe I'm misreading the problem, but I don't see any quadrilaterals in the coloring below.  If you made it a graph of order 7, then I think it would work.

If each vertice has 5 edges. By pidgeonhole, there must be two edges of the same colour :wink:

Even better- there must be 3 edges of the same color, but I don't see how that proves the existance of a quadrilateral.

Renatzu, the quadrilateral need not be convex. In your picture (repeated here for convenience) you have both blue quadrilateral $BCFD$ and red quadrilateral $ABEC$.

[quote="cats..."]use the fact that we're guaranteed to have two monochromatic triangles, then it should be pretty easy from here.  (that fact comes from ramsey's theorem)[/quote]

Do you have a proof, is it the fact tha $R(3,3) \ge 6$

well $R(3,3)=6$ just means we're guaranteed one monochromatic triangle (that's easy to show).  The proof that K_6 gives us two monochromatic triangles comes from Goodman's theorem... you can look it up, here is some discussion on it.  http://www.mathlinks.ro/Forum/viewtopic.php?t=5820

i'll post a simpler proof this when i get the chance (it comes from my book), i wont have time until this weekend though.

WLOG let ABC be a red triangle. Consider the lines from D to A,B,C.
1) At least two must be blue (else a red chain).
The same is true for lines from E and F to A,B,C.
2) If three lines from D are blue and say EA,EB are blue will get a blue chain.
So [b]exactly [/b]2 lines from D,E,F to A,B,C are blue. And this is the only possible configuration (see diagram).
Now line EF must be blue (else a red chain BEFC).
But then what color is ED? If red (red chain ADEB) if blue (blue chain (BDEF).


group theory
abstract algebra
topology
search
superior algebra
superior algebra unsolved

Let $ K/F$ be an infinite Galois extension. Prove that there are subgroups of $ \text{Gal}(K/F)$ that are not closed.

Let $ K=\mathbb{Q}(\sqrt{p}| p\in\mathbb{P})$, $ F: =\mathbb{Q}$. This is obviously a galoisextension (union of finite galoisextensions!). The galoisgroup is isomorphic to $ \mathbb{Z}_{2}^\mathbb{P}$ by the obviuos isomorphism, which maps $ (a_{2}, a_{3}, a_{5}, ...)$ to the automorphism $ \sqrt{p}\mapsto(-1)^{a_{p}}\sqrt{p}$.

The subgroup $ \mathbb{Z}_{2}^{(\mathbb{P})}$ is not closed, which can be seen by the correspondence of closed subgroups and intermediate fields of $ K|F$.

It's my understanding that we have to prove this for [i]every[/i] infinite Galois extension, not merely give an example :?.

Infinite Galois groups are infinite [url=http://planetmath.org/encyclopedia/ProfiniteGroup.html]profinite[/url] groups, so, in particular, they are infinite compact Hausdorff groups. It suffices then to prove that an infinite compact Hausdorff group $ G$ has a non-closed (non-compact, that is) subgroup $ H$. Just take $ H$ to be any countably infinite subgroup of $ G$. $ H$ can't be compact, for there are no countably infinite compact Hausdorff groups. For a short proof of this using Haar measure, see [url=http://www.mathlinks.ro/Forum/viewtopic.php?search_id=674069400&t=123830]this other topic[/url].


If  the sum of the real number $ a,b,c,d$ is $ 0$ show the inequality  $ \left ( \sum ab \right )^2 \plus{} 12 \ge 6 \sum abc$

hello, we have $ a\plus{}b\plus{}c\plus{}d\equal{}0$ and where ist $ d$ in your sum?
Sonnhard.

hello, do you mean $ (ab\plus{}bc\plus{}cd)^2\plus{}12\geq6(abc\plus{}cda\plus{}dab)$?
Sonnhard.

It's symmetrical sum.

http://www.mathlinks.ro/viewtopic.php?t=71504

Thanks for the reference Gunardi..I was struggling with this inequality..


Sara has a bag which at the start contains 10 red marbles and
12 white marbles. When she draws out a red marble, she puts
the marble back and adds five more red marbles. When she
draws out a white marble, she puts the marble back and adds
three more white marbles. What is the fewest number of
rounds of draws/replacements/additions after which the bag
could contain exactly 43 marbles?

Sara currently has 22 marbles, and is trying to get 21 more to get 43 total. She can add 5 marbles or 3 marbles at a time. The fastest way to do this is 3 times 5 marbles plus 2 times 3 marbles, for 5 draws total.


2006 ARML pics posted. More to come over the next couple of days.

Click the button at the top of this page marked "album."

Or, more specifically, go [url=http://www.artofproblemsolving.com/Forum/album_cat.php?cat_id=6]here.[/url]

[quote="joml88"][quote="K81o7"]How do we view the pictures?[/quote]

Go to the album (as Dr. Merryfield explained) and then click on each picture to see them.[/quote]

But there's no picture to view...
There's just picture information, but no link or preview...

There are previews for me...maybe it's your browser settings or something.

Ah thanks...got it from another computer...

Hello. Sorry for reviving this thread (it's still on the first page though  :D ), but where can I get the pictures? There is no 'album' button on the top of this page...

The album feature is not available at this time. I am not sure when - or if - it is coming back.


Enumerate the number of ways of arranging 'n' white balls and 'n' black balls on the circumference of a circle.

To arrangements are considered identical if one can be obtained from the other by rotation.

what if there are 'n' white and 'm' black balls and n(not)=m  ?

Such arrangements are called [b]necklaces[/b]. See [url=http://oeis.org/A047996]A047996[/url] for the formula and further references.


The first six rows of Pascal's triangle are shown below, beginning with row zero. Except for the '1' at each end, row 4 consists of only even numbers, as does row 2. How many of the first 20 rows have this property?

$ \begin{tabular}{ccccccccccc}
&&&&&1&&&&&\\
&&&&1&&1&&&&\\
&&&1&&2&&1&&&\\
&&1&&3&&3&&1&&\\
&1&&4&&6&&4&&1&\\
1&&5&&10&&10&&5&&1\\
\end{tabular}$

Modulo 2, the pascal triangle is actually the Sierpinski triangle. Therefore, on powers of two rows, the numbers will be exclusively even.
But Row 0 satisfies conditions too.

So, rows 0,1,2,4,8,16 => 6 rows

How does the Sierpinski triangle relate to this?

:maybe:

I don't think 0 or 1 are included in the answer.


This seems more algorithmic than mathematical... in which case, I think the easiest solution would be to construct a histogram.

ok. but histograms usually deal with proportions right? how do the proportions come in?

we went over a specific example of this type of counting in the intermediate class. I think if someone wants to verify they should think through a simple case first. like 5 sets, how many people in atleast 3. you use PIE principles, but you add and subtract differently so that a member in a certain number of sets, like 4, is counted only once in your final sum.

[quote="drunner2007"]given sets $A_1$, $A_2$,...,$A_n$ how can we find how many elements are in atleast $k$ of these  sets?

I came up with this conjecture. Can anyone verify?

Suppose we have sets $A_1$, $A_2$,...,$A_n$ with $\#(A_1)$, $\#(A_2)$,...,$\#(A_n)$ elements, respectively. Let $S_k$ denote the $kth$ cyclic "sum" of the elements of $A_1$, $A_2$,...,and $A_n$. For example, $S_2=\#(A_1 \cap A_2)+\#(A_1 \cap A_3)+...+\#(A_{n-1} \cap A_n)$. Then the number of objects in atleast $k$ of the sets $A_1$, $A_2$,...,$A_n$ is

$a_kS_k+a_{k+1}S_{k+1}+a_{k+2}S_{k+2}+...+a_nS{n}$ where $a_{k+i}$ is defined recursively by the relation $a_{k+i}=1-%Error. "displaysum" is a bad command.
{\sum_{j=0}^{i-1}(-1)^{j}\binom{k+i}{k+j}a_{k+j}}$
and $a_k=1$[/quote]
Hmm, as a general rule, don't think you should talk about math class outside of mathclass. The AoPS people are running a bussiness, and giving away parts of their wares for free is not a good thing.

[quote=[url=http://en.wikipedia.org/wiki/Fight_club#Plot_synopsis]Math Class Rules[/url]]
1)You don't talk about Math Class.
2) You don't talk about Math Class.
[/quote]

hahaha. yeah, i guess ur right. but this is an extension of the class, done on my own. everything in an entire branch of mathematics could be considered an extension of what's taught in the class, so there is a pt. where the material is not exclusively from the class


geometry
number theory
projective geometry

hi all,
What is the procedure for admission to doctoral programme in mathematics in ENS,Though i am now in FRANCE,i do'nt speak french and I am from India,I will be 23 next year,hopefully i am still eligible for admission.I tried their website but could'nt make out much from there :(   .
thanks in advance   :).

Hi,

you know, there is an english version of the site. :)

Maybe this may help :
http://www.ens.fr/entrer/statuts_en.php#predoctorat
http://www.ens.fr/entrer/predoctorat_en.php
http://www.ens.fr/entrer/doctorat_en.php

thanks mathmann,
but the problem is that they do'nt elaborate much about the admission procedures,like i heard from some people over here that even if i apply for mathematics,i will have to give an exam in a subject other than mathematics,say physics etc.But i ca'nt find anything about all these in their site.
Also will the examination and interview(ofcourse only if i qualify the written exam  :D ) be in french?.So in short if anyone of you know more about all these please do tell me.
thanks again
Rohith
  :)

Well, then, I can't help you anymore...

Maybe you could ask [b]Moubinool[/b] or [b]alekk[/b].

Good luck with it, let us know how it goes! :)

hi,
Through alekk i got the mail id of one of the administrative staffs in ENS (paris i believe) and then from him i came to know unfortunately  :(  that there are no programs for postgraduate students to get admitted in the doctoral school of ENS!!!.

Oh! Darn! :(

What will you do then? Did he tell you some advice?

hi mathmanman,
Nope he did'nt give me any advice,but i still ca'nt believe that they do'nt admit any post graduate students to their doctoral programme,quite strange  :? ,this is what he (admin staff) wrote to me
------------------------------------------------------------------------------------------------------------------
Dear Sir,
there is no admission procedure in mathematics after
the master at the Ecole Normale Supérieure. The FIMFA
(Formation Interuniversitaire de Mathématiques Pures et
Appliquées) at the ENS has an admission procedure after
the first two years at the university, or seldom after
the third year (called L3 in the Europeen system). For
an admission to a doctoral program, please contact the
universities.
Yours sincerely,
Frédéric Paulin
Responsable de la FIMFA

I do'nt understand what he meant by that last line,to contact univ for doctoral admissions? :?
Anyway I think i will have to try some where else after graduation  :( ,probably at paris-sud or even I can continue here in bordeaux,God knows what will happen :|

Hi,

hmm ok..
Well, I think that he indicated you to do a "LMD". (stands for "License, Master, Doctorat")

So, I think that if you're already at the university in Bordeaux, the simplest thing would be to ask your (math?) teacher about it. :)

Maybe dumb question, but if you came all that way from India, going a little further would be okay too.  Perhaps Belgium, Germany, UK, the Netherlands?
Or am I naive now? :?

Hi,
Actually I thought of applying to ENS since i heard its quite a good place for mathematics,but ofcourse i will be happy if i can get into any university with a reasonably good faculty.I do'nt know about many univeristies in europe.I have heard from my freinds that Maxplanck in Germany,ENS,ETH Zurich etc are among top reasearch institutions in the world in mathematics,but i do'nt know about any other university :( in europe.It would be nice if you could tell me about some good univ in europe :)  and ofcourse as u say i should'nt have problems going to germany or netherlands or any other country since i have already come this far,moreover i will be in leiden next year and its in netherlands  :roll: .

Well, I only know mine of Ghent, I only did a brief tour of all Flemish uni's when in IMO preparation.
What is your interest/specialisation : number theory /finite (projective) geometry, statistics, analysis,astronomy,....?
Leiden, perhaps you should go to the Dutchspeaking subcommunity here on Mathlinks, I heard they are quite good in Number Theory :?

Edit : you have come to Europe only for doctoral work, or you were gonna live here anyway?

I came here for my masters through erasmus mundus programme(now its open to non EU students too),I actually would very well like to live in my place,but unfortunately i do'nt see any chance for it even in the distant future :( ,ofcourse if i leave my state in India,except for food and general cultural atmosphere everyything else would be alien to me includinng lannguage,so its not very different from living here,as i do'nt interact muchh with people in general).

Regarding my intrests,i am still not very sure about it,everything is intresting though i have an inclination more towards subjects which employ methods from algebra.

Yeah I heard leiden is good in number theory(Lenstra,Edixhoven,...).What about Ghent? :|

Well we have some analysts, some algebraists (one professor , Van Geel, can prove Fermat), but Ghent is the place to be for (finite) incidence geometry.  Joseph Thas leads the incidence geometry group. (type incidence geometry in google and you will quickly find sites from Ghent).  I believe right now they already have the biggest research group in that field in the world and it's still growing, and they have non Dutch speaking foreigners (I think they learn while they are working).

So geometry, it's all about projective planes, generalized quadrangles, hexagons, polar spaces, unitals,...
[url]http://cage.ugent.be/zwc/index.en.html[/url] and especially
[url]http://cage.ugent.be/zwc/groups.en.html[/url]

Nice!! and the subject looks intresting,probably i should think about ghent too while applying   :)

Well being a humble student at Ghent myself, I can only provide links, I have no power whatsoever :? ,but :

Frank de Clerck is one those geometers, he has a page, containing info on scientific activities, courses by himself and others at high level, etc. :[url]http://cage.rug.ac.be/%7Efdc/fdceng.html[/url]

There is something called "Selection internationale" dans ENS, Paris. It holds every summer, you can have a try, there is a homepage in the website of ENS for this.
If you can pass it, the government will give you money to help you
finish your L3-M2 period of study.(Maybe 2 years.)
Maybe it is in the "International relation" in the English version of the homepage.


I don't specifically need a full answer to this, just some direction as to how
this problem needs to be started. I'm still fuzzy on Matrices.

Find matrices A, B, C, and X such that the maximization problem in Example 1 can be written as:

Maximize:	      CX
Subject to:      AX [u]<[/u] B
With:              X [u]>[/u] 0

Example 1:

Maximize: 	z = 3x[size=59]1[/size] + 2x[size=59]2[/size] + x[size=59]3[/size]

Subject to:

2x[size=59]1[/size] + x[size=59]2[/size] + x[size=59]3[/size] [u]<[/u] 150
2x[size=59]1[/size] + 2x[size=59]2[/size] + 8x[size=59]3[/size] [u]<[/u] 200
2x[size=59]1[/size] + 3x[size=59]2[/size] + x[size=59]3 [/size][u]<[/u] 320

With: 	      x[size=59]1[/size] [u]>[/u] 0, x[size=59]2[/size] [u]>[/u] 0, and x[size=59]3[/size] [u]>[/u] 0

Key words: Linear programming.

We can write $ 3x_1\plus{}2x_2\plus{}x_3$ as $ \begin{bmatrix}3&2&1\end{bmatrix} \begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}.$

And $ \begin{bmatrix}2x_1\plus{}x_2\plus{}x_3\\ 2x_1\plus{}2x_2\plus{}8x_3\\ 2x_1\plus{}3x_2\plus{}x_3\end{bmatrix}\equal{} \begin{bmatrix}2&1&1\\ 2&2&8\\ 2&3&1\end{bmatrix} \begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}.$

At this point you realize that when you go to write $ AX\le B,$ that that is no ordinary use of the symbol $ \le.$ This isn't the usual total order on the real numbers; rather it is a partial order on $ \mathbb{R}^n$ in which we write $ X\ge 0$ only if all of $ x_1\ge0,x_2\ge0\dots,x_n\ge0$ are true - in other words, if $ X$ lies in the "first octant."

Hi WTF,
"find $ A,B,C$ and $ X$" is a quasi nonsense.
Obviously $ A,B,C$ are given and the unknown is $ X$.
$ K\equal{}\{x: 2x_1\plus{}x_2\plus{}x_3\le150,\cdots,x_1\ge{0},\cdots\}$ is a compact and convex subset of $ {\mathbb{R}}^3$; its edge consists of a polyhedron with 6 faces. $ f: x\rightarrow{Cx}$ is a convex continuous function. Then $ sup(f)$ exists and is obtained in an extremal point of $ K$. After you can use linear programming (as Kent said) or calculate with hand all the extremal points $ A_1,\cdots,A_n$ and conclude $ Sup(f)\equal{}sup\{f(A_1),\cdots,f(A_n)\}$.


For each positive integer $n$, define $S(n)$ as the sum of the digits of $n$, and define $P(n)$ as the product of the digits of n. For example $S(1234)=10$ and $P(1234)=24$. How many four digit integers $n$ satisfy $S(n)=P(n)$?

If they were variations of 1124, there would be:

$4\cdot3\cdot2\cdot1$ solutions, wouldn't there?

[quote="happyme"]Can you explain that solution more, as that was the only problem out of the set that I didn't understand.  :mad:[/quote]

sure

[hide]

[quote="zserf"]3<S(n)<37[/quote]
there can't be any zeros because then P(N) would equal zero therefore the lowest possible sum is 1+1+1+1=4 and the highest possible is 9+9+9+9=36 therefore 3<S(N)<37

[quote="zserf"]if P(N)<37 then S(n) <16[/quote]

because S(N)=P(N) if 3<S(N)<37 then P(N)<37 the largest sum of 4 digits that multiplies to <37 is 15 (1+1+4+9)

[quote="zserf"]If P(N)<16 then S(N)<13[/quote]

by substitution P(N)<16, the largest sum that follows that is 12 (9+1+1+1)

[quote="zserf"]If P(N)<13 then 12, 11, 10, 9, 7, 6, 5 and 4 don't work.[/quote]

brute forced this not 12 because 1+1+3+4 and 1+1+2+6 don't equal 12

not 11 because can't factor 11 into digits less then 10

not 10 because 1+1+2+5=9

not 9 because 1+1+3+3=8 and 1+1+1+9=12

not 7 because 1+1+1+7=10

not 6 because 1+1+2+3=7 and 1+1+1+6=9

not 5 because 1+1+1+5=8

not 4 because 1*1*1*1=1

which leaves 8

not 1118 because it equals 11
not 1222 because it equals 7
which leaves 1124=8

[quote="zserf"]4+2+1+1=4*2*1*1 4!/2!=12[/quote]
[quote="happyme"]If they were variations of 1124, there would be:

4\cdot3\cdot2\cdot1 solutions, wouldn't there?[/quote]

there are two 1s so you have to divide by 2! or 2.
 4*3*2/2=12
[/hide]

Thanks man, I've been working on this problem for an impossible amount of time.

no problem, by the way is my answer correct? After all I used inductive reasoning rather than deductive reasoning.

I'm pretty sure it is. I'll have to check with my coach to be 100%


Let a; b; c be positive reals such that $ abc \equal{} 1$. Show that
$ \frac {2}{(a \plus{} 1)^2 \plus{} b^2 \plus{} 1} \plus{} \frac {2}{(b \plus{} 1)^2 \plus{} c^2 \plus{} 1} \plus{} \frac {2}{(c \plus{} 1)^2 \plus{} a^2 \plus{} 1}\leq 1$

[quote="Protonios"]$ (a \plus{} 1)^2 \plus{} b^2 \plus{} 1 \equal{} (a \plus{} 1)^2 \plus{} (b \plus{} 1)^2 \minus{} 2b\geq2(a \plus{} 1)(b \plus{} 1) \minus{} 2b \equal{} 2ab \plus{} 2a \plus{} 2$

Άρα

$ \frac {2}{(a \plus{} 1)^2 \plus{} b^2 \plus{} 1}\leq\frac {1}{ab \plus{} a \plus{} 1}$

Εφαρμόζουμε και προσθέτουμε κυκλικά και αρκεί να αποδείξουμε ότι

$ \sum_{cyc}\frac {1}{ab \plus{} a \plus{} 1} \equal{} 1$

Εκτελούμε το γνωστό μετασχηματισμό $ a \equal{} \frac {x}{y}$

οπότε αρκεί $ \sum_{cyc}\frac {yz}{xy \plus{} yz \plus{} zx} \equal{} 1$ που ισχύει[/quote]
$ \sum_{cyc}\frac {1}{ab \plus{} a \plus{} 1} \equal{} 1$
Eίναι ωραία ασκησούλα αυτή εαν φυσικά δεν πάμε με τον μετασχηματισμό που βγένει σε δύο γραμμές....
$ \frac{1}{bc\plus{}b\plus{}1}\equal{}\frac{1}{\frac{1}{a}\plus{}b\plus{}1}\equal{}\frac{a}{ab\plus{}a\plus{}1}$
Και $ \frac{1}{ca\plus{}c\plus{}1}\equal{}\frac{1}{\frac{1}{b}\plus{}\frac{1}{ab}\plus{}1}\equal{}\frac{ab}{ab\plus{}a\plus{}1}$
Ara
$ \sum_{cyc}\frac{1}{ab\plus{}a\plus{}1}\equal{}1$


Given a triangle $ ABC$ with the area 1. $ D,\ E$ are on sides $ AB, AC$ respectively. Line segments  $ BE,\ CD$ intersects at $ P$. When $ D,\ E$ move on the sides $ AB,\ AC$ respectively under the condition : $ [BCED]\equal{}2[PBC]$, find the maximum area of $ \triangle{PDE}$.

[quote="kunny"]Given a triangle $ ABC$ with the area 1. $ D,\ E$ are on sides $ AB, AC$ respectively. Line segments  $ BE,\ CD$ intersects at $ P$. When $ D,\ E$ move on the sides $ AB,\ AC$ respectively under the condition : $ [BCED] \equal{} 2[PBC]$, find the maximum area of $ \triangle{PDE}$.[/quote]
$ AP\cap BC \equal{} F$
Let $ P \equal{} [\frac {A}{\alpha},\frac {B}{\beta},\frac {A}{\gamma}]$($ \alpha,\beta,\gamma\ge 0$ because $ P$ lie in $ ABC$)
We have
$ [BCED] \equal{} 2[PBC]\Rightarrow \frac {DC}{PC}.\frac {BE}{BP} \equal{} 2$   (1)
and $ [DPE] \equal{} \frac {[DPE]}{[ABC]} \equal{} \frac {PF}{AF}.\frac {PD}{PC}.\frac {PE}{PB}$  (2)
easy to show
(1) $ \Leftrightarrow \frac {(\beta \plus{} \alpha)(\alpha \plus{} \gamma)}{(\alpha \plus{} \beta \plus{} \gamma)^2} \equal{} \frac {1}{2}\Leftrightarrow \alpha^2 \equal{} \beta^2 \plus{} \gamma^2$
(2) $ \Leftrightarrow [DEP] \equal{} \frac {\alpha.\gamma.\beta}{(\alpha \plus{} \beta \plus{} \gamma)(\beta \plus{} \alpha)(\alpha \plus{} \gamma)}$
So $ [DEP] \equal{} \frac {2\alpha.\gamma.\beta}{(\alpha \plus{} \beta \plus{} \gamma)^3} \equal{} \frac {\sqrt {\beta^2 \plus{} \gamma^2}.(\beta \plus{} \gamma)}{(\beta \plus{} \gamma \plus{} \sqrt {\beta^2 \plus{} \gamma^2})^3}\le \frac {1}{(1 \plus{} \sqrt {2})^3}$
Easy to prove by Cauchy
 :D

$ E,F$ are on sides $ CA, AB$ of a triangle $ ABC$ respectively. Line segments  $ BE,CF$ intersects at $ P$.

If $ 1< k\leq\frac{3\plus{}\sqrt{5}}{2}$ and $ {\rm Area}(BCEF) \leq k{\rm Area}(PBC)$, then

$ {\rm Area}(\triangle{PEF})\leq \left(\frac{2}{\sqrt{k}}\minus{}1\right)\left(\sqrt{k}\minus{}1\right)^2{\rm Area}(\triangle{ABC})$.

A proof of the case $ k\equal{}\frac{16}{9}$ see: http://www.mathlinks.ro/Forum/viewtopic.php?t=206127


A rook makes a closed tour on a chessbaord of m ranks (rows) and n files (columns), visiting each square exactly once. Of course, the tour's length is mn.
The tour consists of horizontal segments and vertical segments.
Prove: the total length of the horizontal segments is divisible by 4 iff m is not divisible by 4 and n is odd.
The attached image provides an example: here m=n=8 and the total length of the horizontal segments is 30.

I just checked this theorem on a computer for small values of m and n, and it holds. Can somebody prove it?


Prove that in any triangle with the property: $a\geq b \geq c$ we have:
$ \frac{ \sum a \cot(A)}{\sum a\cos(A)} \leq \frac{1}{\sin(C)}$.

(standard notations).

I hope this is original and even more: correct!

enjoy :cool:

do you think we have mistake with RHS ? Is it symetric ?

I think there is no mistake in the previous post! The sums are cyclic.

I tried it and I think it is easy for every bodies .


modular arithmetic
Integer sequence
recurrence relation
number theory
Divisibility
IMO Shortlist
Kazakhstan NMO 2022 p6

For the first part, it's easy to see that it suffices to show the following: given a prime $p$ and a sequence $x_n,n\ge 0$ of residues $\pmod p$ s.t. $x_0=0,x_1=1$, show that there is some $n>0$ s.t. $x_0=0$. This can be shown as follows: assume there are nu such $n$. The sequence becomes periodic from some point onwards, so we can find $m<n$ s.t. $x_m=x_n,x_{m+1}=x_{n+1}$. Now start from $x_{n+1}$ downwards with the recurrence formula $x_t=\frac{x_{t+2}-1}{x_t}$ (where $\frac 1{x^t}$ is the inverse of $x_t\ne 0\pmod p$). Since $x_{m+1}=x_{n+1}$ and $x_m=x_n$, the portion between $x_m$ and $x_n$ is repeated indefinitely, and since it does not contain $0$, we can't reach $0$ by this procedure. However, we must reach $0$ when we reach $x_0$, so we have a contradiction.

As for the second part, take $a_1=22,a_2=15$ (I need $a_2$ to be odd and $6\pmod 11$). $2|a_n$ iff $3|n$, while $11|a_n$ iff $n\equiv 10\pmod 6$.

Approach by [url=http://www.mathlinks.ro/profile.php?mode=viewprofile&u=423]dblues[/url]:

Let $ m > 1$ and $ p$ be a prime divisor of $ a_m$. Define $ \{ u_k \}$ by $ u_k \equiv a_k \pmod{p}$ such that $ 0 \leq u_k \leq p - 1$. Thus, we have $ u_{k + 2} \equiv u_{k + 1}u_k + 1 \pmod{p}$. We note that $ u_m = 0$.
Since there are only finitely many distinct pairs $ (u_k, u_{k + 1})$, $ \{ u_k \}$ is eventually periodic.

[b][i]Lemma:[/i][/b] $ \exists \ k_p > 0$ such that $ u_{m + k_p} = 0$.
Suppose not, then $ \{ u_k \}$ is purely periodic from $ u_r$ for some $ r > m$. (Note that inequality is strict, since otherwise, letting $ d_p$ be the length of this period, we have $ u_{m + d_p} = 0$, implying that we have $ k_p = d_p$ as required, which contradicts our original assumption that no such $ k_p$ exists.)
Thus we have $ (u_r, u_{r + 1}, \ldots , u_{r + d_p - 1})$ and $ (u_{r + d_p}, u_{r + d_p + 1}, \ldots , u_{r + 2d_p - 1})$ as the first two periods.
Note that $ u_ru_{r - 1} \equiv u_{r + 1} - 1 = u_{r + d_p + 1} - 1 \equiv u_{r + d_p - 1}u_{r + d_p} \pmod{p}$.
$ \Rightarrow u_{r - 1} = u_{r + d_p - 1}$, since $ u_r = u_{r + d_p} \not\equiv 0 \pmod{p}$ (by our assumption).
This contradicts the fact that $ (u_r, u_{r + 1}, \ldots , u_{r + d_p - 1})$ and $ (u_{r + d_p}, u_{r + d_p + 1}, \ldots , u_{r + 2d_p - 1})$ are the first two periods, thus our assertion must be true.

Note that from the above lemma, $ u_m = u_{m + k_p} = 0 \Rightarrow u_{m + 1} = 1 = u_{m + k_p + 1} \Rightarrow \{u_k \}$ is purely periodic from $ u_m$. Denote $ q$ to be the least common multiple of all $ k_p$ corresponding to all the distinct prime divisors $ p$ of $ a_m$. We thus have $ a_{m + tq}$ is divisible by each of these primes $ \forall t \in \mathbb{Z}^ +$. Let $ e_m$ be the highest exponent of all the primes in the prime factorisation of $ a_m$. Choosing a sufficiently large $ t$ such that $ n = m + tq > me_m$, we have $ {a_m}^m \mid {a_n}^n$ as desired.

As for the second part of the problem, this is not necessarily true. The argument breaks down when $ m = 1$ because it is not necessarily true that $ u_{m + 1} = u_2 = 1$, due to the fact that $ u_0$ is not defined in the recurrence $ u_{k + 2} = u_{k + 1}u_k + 1$. Thus, $ \{ u_k \}$ is not necessarily purely periodic from $ u_m$. As an example, we let $ a_1 = 33, a_2 = 20$. Taking $ p = 3$, we have for $ n > 1, 3 \mid a_n$ iff $ n \equiv 0 \pmod{4}$, while taking $ p = 11$, we have for $ n > 1, 11 \mid a_n$ iff $ n \equiv 5 \pmod{6}$. Note that both conditions cannot be achieved simultaneously as the first condition implies $ n$ is even, while the second condition implies $ n$ is odd. Thus $ a_1 \nmid a_n \forall n > 1$ and we are done.

[quote="Pascual2005"]Define the sequence $ a_1, a_2, a_3, ...$ as follows. $ a_1$ and $ a_2$ are coprime positive integers and $ a_{n \plus{} 2} \equal{} a_{n \plus{} 1}a_n \plus{} 1$. Show that for every $ m > 1$ there is an $ n > m$ such that $ a_m^m$ divides $ a_n^n$. Is it true that $ a_1$ must divide $ a_n^n$ for some $ n > 1$?[/quote]
See    http://www.mathlinks.ro/viewtopic.php?t=150805

Here is my solution for the first part.

Define a sequence $\{ x_n \}$ such that $x_1=x_2=1, x_{n+1}=x_{n}x_{n-1}+1$. We have $x_{n+1} \equiv x_1 \pmod{x_n}, x_{n+2} \equiv x_2 \pmod{x_n}, x_{n+3} \equiv x_3 \pmod{x_n}$. Eventually, $x_{2n} \equiv x_n \pmod{x_n}$ or $x_n \mid x_{2n}$. It is not hard to prove that $x_a \mid x_{ab}$ and $x_{ab+k} \equiv x_k \pmod{x_{a}}$.

Note that $a_{m+1} \equiv x_1 \pmod{a_m}, a_{m+2} \equiv x_2 \pmod{a_m}, ...$ Eventually, $a_{m+k} \equiv x_k \pmod{a_m}$. From this, my idea is to prove that for every prime divisor $p$ of $a_m$, there exist $x_k$ such that $p \mid x_k$.

Indeed, for any prime $p$, in sequence $\{ x_n \}$, there are infinitely many $i$ such that $x_i \equiv t \pmod{p}$ for some $1 \le t \le p-1$ (otherwise $\{ x_n \}$ will be not a infinite sequence). For such $x_i$, we consider $x_{i-1}$. There will exist $2<k<l$ such that $x_k \equiv x_l \equiv t \pmod{p}$ and $x_{k-1} \equiv x_{l-1} \pmod{p}$ (otherwise if $x_{k-1} \not\equiv x_{l-1} \pmod{p}$ for every $k,l$ then there won't exist infinitely number $x_i$). If we know $x_k,x_{k-1} \pmod{p}$, we can determine $x_{k-2},x_{k-3}, \cdots x_2,x_1  \pmod{p}$. Similarly to $x_l,x_{l-1}$. Since $x_2 \equiv x_1 \equiv 1 \pmod{p}$ so eventually, there will exist $x_{h} \equiv x_{h-1} \equiv 1 \pmod{p}$ for $h>2$. This implies that $p \mid x_{h-2}$.

Back to our sequence $\{ a_n \}$, we consider every prime divisor $p_i \; (1 \le i \le k)$ of $a_m$. According to the proof above, there exist $b_i$ such that $p_i \mid x_{b_i}$. Therefore, $\prod_{i=1}^k p_i \mid x_{b_1b_2 \cdots b_k}=x_l$. Thus, $a_{m+lk} \equiv x_{lk} \pmod{a_m}$. This prove that every prime divisor of $a_m$ is also a prime divisor of $a_{m+lk}$. We can find $l_0$ large enough such that $m v_p \left( a_m \right) \le (m+l_0k) v_p \left( a_{m+l_0k} \right)$ for every $p \mid a_m$. Thus, this follows $a_m^m \mid a_{m+l_0k}^{m+l_0k}$ or $a_m^m \mid a_n^n$.  $\blacksquare$

For the first part, we only need to show that $a_i$ modular $p$ is purely periodic starting at $i$, for all prime $p|a_i$.
Then, taking a large $N$ which divides all such periods of all such primes, we can see that $a^i_i$ is a divisor of $a^{i+N}_{i+N}$.

To prove this, we will look at the structure $f(a,b)=(b,ab+1)$. (in mod $p$, of course)
Since $i>1$, we know that $a_{i+1} \equiv 1 \pmod{p}$. So we are starting at $(0,1)$. Denote $T_n= f^n (0,1)$.
By PHP, we will have $T_n = T_m$ for some $0 \le n < m$. Take one pair with minimum $n+m$. I claim that $n=0$.
Assume otherwise - $n \ge 1$. Note that $T_m$ is not $(0,1)$. Otherwise, we can take $n=0$.
Now since $T_m \neq (0,1)$, $f^{-1} (T_m)$[b] exists, and it is unique.[/b] (this is the key to this problem)

So if $T_m \neq T_0$ and $n \neq 0$, $T_{m-1}=T_{n-1}$ and we have a contradiction. This shows that there is a cycle.

For Part 2, now we know that starting with stuff like $(0,2)$ may lead us into problems. Use that to form a  construction.

[quote=Pascual2005]Define the sequence $ a_1, a_2, a_3, ...$ as follows. $ a_1$ and $ a_2$ are coprime positive integers and $ a_{n \plus{} 2} \equal{} a_{n \plus{} 1}a_n \plus{} 1$. Show that for every $ m > 1$ there is an $ n > m$ such that $ a_m^m$ divides $ a_n^n$. Is it true that $ a_1$ must divide $ a_n^n$ for some $ n > 1$?[/quote]

The answer is $\boxed{\text{Yes}}$ for $\textit{a)}$ and $\boxed{\text{No}}$ for $\textit{b)}$
$\textit{a)}$Define a sequence $x_i$ of integers satisfying
$\;\;\;\;\;\;\; \bullet$ $x_i \equiv a_i \pmod {p^C}$ where $p|a_m$ and $C\ge m\nu_p(a_m)$
$\;\;\;\;\;\;\; \bullet$ $x_i =x_{i-1} x_{i-2}+1$ and $0=x_0 \equiv x_m \equiv x_{2m} .................. \equiv x_{km} \pmod {p^C}$
Define $i_j$ as $$\underbrace{x_m}_{i_0=0},\underbrace{x_1}_{i_1=1}.................$$
[b][color=#f00]Lemma #1:-[/color][/b] $i_{mk+t} \equiv i_t \pmod {p^C}$
[b][color=#f00][/color][/b] This trivally follows from the second $\bullet$ from which we obtain both $x_j$ and $i_j$ periodic.

The result follows from choosing $n=m^{k \nu_p(m)} $ of which there are clearly infinitely many.

Solved with [b]elcinmusazade[/b].
[b]First part:[/b] Let $p_1,p_2,\ldots p_s$ be all prime divisors of $a_m$.
Now let's look at $a_m,a_{m+1},...$ in $\pmod{p_1}$. We will get sequence $x_1,x_2,x_3,...$ where $x_1=0,x_2=1$. It's obvious that $(x_i)_{i\geq 1}$ is finally periodic starting from some point. Let's assume that this point is $x_j$ where $x_j\ne x_1=0$. So we will get the sequence like this $$x_1,x_2,...,x_j,x_{j+1},...x_r,x_j,x_{j+1},...$$ So we get that $x_j\cdot x_{j-1}+1\equiv x_{j+1}\equiv x_j\cdot x_r+1 \implies p_1\mid x_j\cdot (x_r-x_{j-1})$. Since $x_j\not\equiv x_1\pmod{p_1}$ we get $x_r\equiv x_{j-1}\pmod{p_1}$, but then we get that period starts from $x_{j-1}$, not from $x_j$, which is contradiction. So $x_j=x_1=0$ and $x_{j+1}=x_2=1$. So $(x_i)_{i\geq 1}$ is periodic starting from $x_1$. Let $r_1$ be the length of this period. Then we get that $x_{tr_1+1}=0$ for all $t\in \mathbb{N}_0$, so $p_1\mid a_{tr_1+m}$ for all $t\in \mathbb{N}_0$
Similarly define $r_2,r_3,...,r_s$ according to $p_2,p_3,...,p_s$. So $p_i\mid a_{tr_i+m}$ for all $t\in \mathbb{N}_0$ and for all $i=1,2,...,s$.
Now choose $n=Tr_1r_2\cdots r_s+m$ where $T$ is very large that $n=Tr_1r_2\cdots r_s+m>max\{m\cdot v_{p_1}(m),..., m\cdot v_{p_s}(m)\}$. And this gives that $n\cdot v_{p_i}(n)\geq n>m\cdot v_{p_i}(m)$ for all $i=1,2,...,s$. So we get that $a_m^m\mid a_n^n$ as desired.

[b]Second part:[/b] The answer is negative. Choose $a_1=33,a_2=31$. Now lets look at residues $a_i$ gives in $\pmod{3}$ over all $n$. We get sequence $0,2,1,0,1,1,2,0,1,1,2,...$ We get that sequence has period starting from $4$th term. So $3\mid a_i\iff 4\mid i$ or $i=1$. Now lets look at residues $a_i$ gives in $\pmod{11}$ over all $n$. We get sequence $0,9,1,10,0,1,1,2,3,7,0,1,1,....$  We get that sequence has period starting from $5$th term. So $11\mid a_i\iff i\equiv 5\pmod{6}$ or $i=1$. If there is $a_i$ which is divisible by $33$, then$4\mid i$ and $i\equiv 5\pmod{6}$, so $i$ is both odd and even, which is contradiction. So there is no $a_i$ which is divisible by $a_1=33$. So there is no $n>1$ such that $a_1\mid a_n^n$. So we are done!!! :-D


geometry
perimeter
rectangle
inequalities
geometric transformation
reflection
search

Let $ABCD$ be a rectangle. We choose 4 points like $P,M,N$ & $Q$ on $AB,BC,CD$ & $DA$. Prove that the perimeter of $PMNQ$ is at least two times the diameter of $ABCD$.

i have gotten somewhere which comes to a very difficult inequality which its proof i'm not aware of. Does anyone have more geometric ideas?

Try to reflect the rectangle around its own edges a couple of times. See what you get.

nothing. :)  because i really don't know what the math. meaning of reflection is. ;)

First you reflect it  by BC then new rectangle by C1D1 (C1=C ,B1=B). Again in new by A2D1 and you get nice picture. Now the prove is simple.

If this is a question of vocabulary:

The [b]reflection[/b] of a point P in a line g is defined as the point R such that $PR\perp g$ and such that the distance PR equals twice the distance from the point P to the line g. Generally, the [b]reflection with respect to a line[/b] is the transformation mapping each point P to the reflection of the point P in this line.

Anyway, let me try to detail the proof. Note that [b]I changed the notations of the problem.[/b]

[color=blue][b]Problem.[/b] Let ABCD be a rectangle, and let M, N, P, Q be four points on its sides AB, BC, CD, DA, respectively. Prove that $MN+NP+PQ+QM\geq 2\cdot AC$.[/color]

[i]Solution.[/i] Look at this picture:

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

Here is how it was constructed: First, we reflect the rectangle ABCD, together with the points M, N, P, Q on its sides AB, BC, CD, DA, with respect to its sideline AB. We get a new rectangle EBCF. Now, we reflect this rectangle EBCF, together with the reflected points on its sides, with respect to its sideline CF. We obtain a new rectangle GHCF. Then, we reflect this rectangle GHCF with respect to its sideline GF. We obtain a new rectangle GJIF. Okay, enough done, all in all we have reflected our rectangle ABCD three times in its sidelines, and each time, of course, we reflected the inscribed quadrilateral MNPQ with it. Since reflection preserves distances, we thus have NR = NP, RS = PQ and ST = QM, where the notations are those introduced in the picture above. Thus, MN + NP + PQ + QM = MN + NR + RS + ST. But by the polygon inequality, $MN+NR+RS+ST\geq MT$. Now, remains to show that $MT=2\cdot AC$, and the problem will be solved.

Why do we have $MT=2\cdot AC$ ? There are various ways to see that; one of them is to note that, because of the many reflections which all preserve distances, we have GT = AM; moreover, the segments GT and AM lie on parallel lines and are equally directed, so that the quadrilateral AMTG is a parallelogram. Thus, MT = AG. But now, again because of the many reflections preserving distances and angles, CG = AC, while < GCH = < ECB = < ACB, so that the point C lies on the segment AG, and thus $AG=AC+CG=AC+AC=2\cdot AC$. Hence, $MT=2\cdot AC$, and the solution is complete.

  Darij

It was not a question of vocabulary. I got the same picture, but it wasn't obvious to me that $MT=2AC$.  :blush:

nice. :lol:  (This is the first problem i've seen solved with a geometric transformation.)

[u]The law of the nature[/u]: a endless chain of the experiments, but on the shortest (optimum) way of its every achievement (particularly, the search of the optimum is a "natural" characteristic and for the human society). For example, in the case of the light, the angle of the incidence is equal with the angle of reflection. The only point $M\in AB$ which respects the above principle is the midpoint of the side $AB\ !$ a.s.o. Now you will understand better the Darij's drawing: A detached (in a plane) cardboard box without lid and bottom !!!

For [b]Perfect_Radio[/b] (why $MT=2\cdot AC\ ?$): Let $U$, $V$ be the points for which

$U\in (BE)$, $BU=BM$; $V\in (GH)$, $HV=BU$; ($F\in BJ$) $\Longrightarrow$

$JT=HV=BU=BM$ $\Longrightarrow JT=BM\Longrightarrow BJTM$ is a parallelogram $\Longrightarrow$

$MT\parallel \overline {BFJ}\Longrightarrow MT=BJ=2\cdot AC\Longrightarrow MT=2\cdot AC$.