geometry
rectangle
analytic geometry
induction
vector
function
geometric transformation

On the cartesian plane are drawn several rectangles with the sides parallel to the coordinate axes. Assume that any two rectangles can be cut by a vertical or a horizontal line. Show that it's possible to draw one horizontal and one vertical line such that each rectangle is cut by at least one of these two lines.

Lemma: If we are given a finite number of horizontal (resp. vertical) lines such that for any two of these lines there exists a vertical (resp. horizontal) line intersecting both lines, then there exists a vertical (resp. horizontal) line that goes through all of the lines.

Proof: Consider the projections $ p_1,p_2,\dots$ of all these lines on the $ x$ axis. We have to show that the intersection of the projections is nonempty. For any two initial projectoins $ p_1,p_2$. we have that $ p_1\cap p_2\neq\emptyset$. Suppose that the intersection $ S \equal{} \bigcap_{i \equal{} 1}^np_i$ of $ n$ such projections is nonempty. Then there exists a $ p_i$ and a $ p_j$ such that no portion of $ p_i$ lies on the left of $ S$ and no portion of $ p_j$ lies on the right of $ S$. For a new projection $ p_{n \plus{} 1}$ we are to show that $ S\cap p_{n \plus{} 1}$ is nonempty. Assume the contrary. Then $ p_{n \plus{} 1}$ lies either on the left or on the right of $ S$. WLOG let $ p_{n \plus{} 1}$ lie on the left. Then $ p_{n \plus{} 1}\cap p_i \equal{} \emptyset$, contradiction. Hence our claim is proved by induction. $ \blacksquare$

Now for our problem, call a pair of rectangles [i]horizontally good[/i] if there exists a vertical line intersecting both of the rectagnles. Define [i]vertically good[/i] pairs analogously. Verify that we can WLOG assume that every pair of rectangles are disjoint.

Divide the rectangles into two sets $ P$ and $ Q$ such that every pair of rectangles in $ P$ are horizontally good and every pair of rectangles in $ Q$ are vertically good. Verify that $ |P\cap Q|\le 1$. Because if $ |P\cap Q|\ge 2$, there must exist two rectangles which are both horizontally good and vertically good, which is impossible as the rectangles are disjoint. Also note that $ P\cap Q\neq \emptyset$, since every pair of rectangles are either horizontally good or vertically good. Therefore $ |P\cap Q| \equal{} 1$. Let this common rectangle be $ K$. Now by our lemma, there exists a vertical line through $ K$ that intersects every rectangle in $ P$, and a horizontal line through $ K$ that intersects every rectangle in $ Q$. Hence these two lines are the desired ones.

There is a slight mistake in the above post. Actually $ |P\cap Q| \equal{} 1$ isn't necessarily true. The correct is $ |P\cap Q|\le 1$, as I had shown. Just consider the following configuration:

[img]http://img2.freeimagehosting.net/uploads/70a2f2e2c4.gif[/img]

Then we can draw a line that goes through all of the elements in $ P$ and another line that goes through all of the elements in $ Q$. And these two lines satisfy our problem. Also, I think we need to prove that we can divide all the rectangles into such sets $ P,Q$, but I have been trying to find a proof of this without much luck. :(

To nayel:
Is your proof incorrect at all or just incomplete?

I think my proof is correct but incomplete, since showing the existence of $ P$ and $ Q$ implies the conclusion.

Can anyone post a complete solution for this problem?

We'll apply mathematical induction on the number of rectangles. When the number is small, the proposition is trivial.

Assume that for $ n$ rectangles that satisfy the conditions, the problem statement holds.

For $ n \plus{} 1$ rectangles, consider the leftmost sides of these rectangles; select the one that has its leftmost side at the "rightmost" in our planar configuration.
(Figure) Denote the line by $ l$

Apply the inductive hypothesis for $ n$ rectangles, excluding the one we've just selected. Now we have a horizontal line (call it $ l_x$) and a vertical line (call it $ l_y$).

We'll divide cases;

Case 1) The selected rectangle is on one of the two lines $ l_x$ and $ l_y$: the proposition is trivial.

Case 2) (excluding case 1) The selected rectangle is on the 'left' side of the line $ l_x$.
The rectangles on $ l_x$'s leftmost lines must be on the left of $ l$. Since $ l$ is on the left of $ l_x$, this implies that $ l$ passes through all of the rectangles on $ l_x$. Then $ l$ and $ l_y$ satisfies the desired properties.

Case 3) The selected rectangle is on the 'right' side of the line $ l_x$.
We may safely assume WLOG that the selected rectangle is on the upper side of the line $ l_y$
All of the rectangles that are not on $ l$ must be on the left side of $ l$. (Due to our selection of the rectangle)
Denote by $ m$ the line containing lower side of the selected (red) rectangle.

Partition the set of the $ n$ non-selected rectangles into sets;
$ A$ is the set of rectangles on the line $ l$
$ B$ is the set of rectangles on the line $ m$
$ C$ is the set of rectangles not on $ l$ or $ m$.
Trivially, if $ C$ is an empty set, the proposition holds (let the two lines be $ l$ and $ m$)
Assume $ C$ is not an empty set.

Claim 1) All rectangles on $ l_x$ must be on either $ l$ or $ m$.
Proof) It is trivial. If a rectangle on $ l_x$ is not on $ l$, due to the conditions given on the problem, there must be a horizontal line (there cannot be a vertical line) cutting this rectangle and the red one. This implies this rectangle is cut by $ m$.

Claim 2) There is a vertical line going through all rectangles in the union of $ (A \minus{} B)$ and $ C$.
Proof) Due to Claim 1, all rectangles in $ C$ must be on $ l_y$ and not on $ l_x$. This implies these rectangles must be on the upper side of $ m$ (since it is not cut by $ m$ or $ l$, but there must exist a vertical or horizontal line that cuts through this rectangle and the red one).

Select a rectangle $ x \in A \minus{} B$ and $ y \in C$. These two cannot have a horizontal line going through them, and therefore must have a vertical one.
If we project these rectangles onto the $ x$-axis, we have that these projections have an intersection.

Project all rectangles in $ (A \minus{} B)$ and $ C$ onto the x-axis.
Observe that any two projections of rectangles in this set must have an intersection (if $ a,b \in (A \minus{} B)$, due to the line $ l$; if $ a,b \in C$, due to the line $ l_y$; if $ a \in (A \minus{} B)$ and $ b \in C$, due to what we've just proved).
By Helly's theorem for 1-dimension, we have that all of these projections have an intersection.

Denote a point in this intersection by $ P$, and define $ p$ to be the vertical line passing through $ P$.
Then $ p$ and $ m$ satisfy the problem conditions!
($ p$ passes through $ (A \minus{} B)$ and $ C$ and $ m$ passes through $ B$)

=> The induction is complete, and the problem statement holds!

I don't understand the proof of claim 1 of qwerty414's proof.

Here is another proof. It's not mine, but I think it's really beautiful.

Assume the opposite. Call two rectangles "separate" if no vertical line can cut them. For each pair of separate rectangles, consider the line containing the lowest horizontal side. Among all these lines, let L be the highest line.

(i) There is no pair of separate rectangles below L.
Consider all rectangles not cut by L.

Suppose no two of them are separate. Consider the rectangle with rightest leftside and the rectangle with the leftest rightside (am I inventing new words here?). Since no two rectangles are separate, clearly the vertical line cutting these two rectangles (call it M) must cut all other rectangles. So L and M have the desired properties.

Now suppose two of them are separate, call them A and B. By the assumption, one of them is above L, WLOG it's A. But L is the highest lower side of separate rectangles, therefore B must be below L. Hence there is no vertical nor horizontal line which cut both A and B, a contradiction.

(ii) There is a pair of separate rectangles below L.

Call them C and D. Suppose A and B be the pair of separate rectangles such that the lower horizontal side is H. WLOG suppose A and C are on the right side of B and D, respectively. Then it is easy to see that either A and D or B and C cannot be cut by any horizontal or vertical line, we get a contradiction.

Hmm... I think the key is to elaborate on the idea of considering the leftmost right and rightmost left sides (which comes from the one-dimensional analog).

Let $l(\mathcal{\mathcal{R}}),r(\mathcal{\mathcal{R}}),b(\mathcal{\mathcal{R}}),t(\mathcal{\mathcal{R}})$ denote the left, right, bottom, and top coordinates of rectangle $\mathcal{\mathcal{R}}$. Two rectangles are [i]connected[/i] if they can be cut by a line; [i]vertical and horizontal connectivity[/i] refer to the orientation of the line. (Although it doesn't really matter, in this solution we'll include the boundary in the "interior" of a rectangle.)

Suppose we have $n\ge 3$ rectangles ($n\le 2$ is trivial), and order them according to $r(\mathcal{\mathcal{R}}_1)\le r(\mathcal{\mathcal{R}}_2)\le \cdots\le r(\mathcal{\mathcal{R}}_n)$. If $\mathcal{R}_i$ and $\mathcal{R}_j$ are horizontally connected for all $1\le i<j\le n$, we're done by the one-dimensional analog. Otherwise, let $2\le k\le n-1$ denote the smallest index such that there exists $1\le i\le k-1$ with $\mathcal{R}_i,\mathcal{R}_k$ horizontally disconnected. For $k+1\le m\le n$, place $\mathcal{\mathcal{R}}_m$ in set $S_{-}$ if $l(\mathcal{\mathcal{R}}_m)\le r(\mathcal{\mathcal{R}}_k)$ and $S_{+}$ if $l(\mathcal{\mathcal{R}}_m)>r(\mathcal{\mathcal{R}}_k)$.

For all $\mathcal{R}_m\in S_{-}$, $l(\mathcal{R}_m)\le r(\mathcal{R}_k)\le r(\mathcal{R}_m)$, so we place a vertical line at $r(\mathcal{R}_k)$ to account for $\{\mathcal{R}_k\}\cup S_{-}$.

WLOG $b(\mathcal{R}_i)>t(\mathcal{R}_k)$. For all $\mathcal{R}_m\in S_{+}$, $l(\mathcal{\mathcal{R}}_m)>r(\mathcal{\mathcal{R}}_k)\implies \mathcal{R}_m$ is vertically disconnected from $\mathcal{R}_1,\ldots,\mathcal{R}_k$ and thus horizontally connected to each of $\mathcal{R}_1,\ldots,\mathcal{R}_{k-1},\mathcal{R}_k$ (including $\mathcal{R}_i,\mathcal{R}_k$!). Furthermore, $\mathcal{R}_1,\ldots,\mathcal{R}_{k-1}$ are pairwise horizontally connected by the minimality of $k$, while $\mathcal{R}_{m_1},\ldots,\mathcal{R}_{m_\ell}$ (where $|S_{+}|=\ell$) are pairwise horizontally connected by the horizontal lines in $[t(\mathcal{R}_k),b(\mathcal{R}_i)]$ (which belong to the vertical "gap" in between $\mathcal{R}_k$ and $\mathcal{R}_i$), so by the one-dimensional analog, there exists a horizontal line in
\[[\max(b(\mathcal{R}_1),\ldots,b(\mathcal{R}_{k-1}),b(\mathcal{R}_{m_1}),\ldots,b(\mathcal{R}_{m_\ell})),\min(t(\mathcal{R}_1),\ldots,t(\mathcal{R}_{k-1}),t(\mathcal{R}_{m_1}),\ldots,t(\mathcal{R}_{m_\ell}))],\]as desired (because $\mathcal{R}_1,\ldots,\mathcal{R}_{k-1},\mathcal{R}_{m_1},\ldots,\mathcal{R}_{m_\ell}$ are pairwise horizontally connected).

So Thinkflow and I came up with this excellent solution: (although this is kind of a sketch)

Ok so assume the problem is not true. First, WLOG, make every vertex of a rectangle a lattice point (a point with integer coordinates) with the orderings preserved. Now for every lattice point P, consider the horizontal and vertical lines through P. These hit some of the rectangles (as in the above solution, boundaries are included). Now, there are 4 quadrants formed by the 2 lines, and some of them have at least 1 rectangle that is not hit by the lines, else the problem is true, contradiction. But if 2 opposite quadrants have a rectangle, the problem statement is violated. Thus, either 1 quadrant has at least 1 rectangle, or 2 adjacent ones each have at least 1 rectangle. For any point, we can naturally associate a vector depending on the quadrants:

If there is one quadrant, make the vector point in that quadrant's direction with magnitude $\sqrt {2}$, so for example if it is the upper right quadrant, the vector is $<1,1>$. If there are 2, make the vector have unit length. For example, if the 2 upper quadrants have rectangles, the vector is $ <0,1>$.

Note that this vector field points inward when we go sufficiently far away from the rectangles. Also, it's easy to verify that any two points with distance 1 have associated vector that differ by at most 45 degrees. Also, again, no vectors are 0. So take an arbitrary point, and follow the vector field by simply, at each stage, adding the associated vector to the position of where you are. Since the vector field eventually points inward, you get a cycle, and because of the 45 degrees condition, it's easy to see that the cycle doesn't cross itself, and hence it has an interior.

Now, for any two points that differ by the vector $ <1,0>$ we can sort of interpolate the vector field into a continuous vector field, just by making the vector field piece-wise linear on each unit horizontal segment. (As in, you know what the function is on the 2 endpoints, so this determines a unique linear function) Now, all unit squares have the top and bottom edges defined, so we can interpolate them linearly on the vertical segments in the same way. The 45 degree observation guarantees that at no place is the vector field equal to the 0 vector. Now, the boundary is homotopic to a circle (like you can stretch it and make it a circle with the normal topologicial restrictions), hence we can stretch it into a hemisphere while preserving the vector field. Now, reflect the hemisphere about it's boundary plane to get another vector field, and these 2 vector fields together form a continuous, never 0 vector field defined on the surface of the sphere, violating the hairy ball theorem (see http://en.wikipedia.org/wiki/Hairy_ball_theorem )

So we have a contradiction.

This is a very beautiful  and simple looking (and incredibly difficult!) problem that calls for a very natural solution.  Unfortunately I have not seen any in the above, ( frankly some are sketchy even).

The one dimensional version is taken to be trivial. I will not repeat the proof as it is posted above.

Observation: If any of the rectangle is in fact a trivial point, we have proven the statement.
 Method : We try to mess around with the initial condition such that the statement become more and more trivial.

It is absolutely non-trivial to either get this observation nor learnt the method elsewhere. If you found one, you will naturally think of the other. This method is uncommon: The only other place I have seen it is in IMO Shortlist 14C9. If one is willing to accept these magical thoughts, the rest become intuitive and flows easily.
Terms: By left/right/up/bottom boundary of a rectangle, we mean the horizontal/vertical line that spans all of space. (So we can talk about Left Boundary of A = right boundary of B etc.)

Focus on any one rectangle X. Try to shrink it as much as possible, while keeping condition of common horizontal/vertical unviolated. If this process does not fail the rectangle becomes a point. The conclusion would then be obvious. Suppose the rectangle stays 2-dimensional. Since we cannot move the upper boundary downwards (by assumptions of termination of shrinking process), we have

(1) There is a rectangle whose bottom boundary is the top boundary of X, and does not have a common horizontal line with X.
Same holds for all other directions.

We call rectangles that satisfies (1) for some directions a strange rectangle.

Consider the set of points bounded by LR boundary union Up-Down boundary of X (i.e. extend X into a cross shape naturally).  This divides the complement into 4 areas.Any strange rectangle is totally contained in one of the 4 areas. Also, in each of the two pairs of diagonally opposite areas, one must be absent of strange rectangle, (otherwise the main condition is violated). By staring at the condition a lot, this implies we have both upper areas empty ( does not contain strange rectangle), or both lowers, or both right, or both left. So (1) fails from at least one direction.

Thus we may assume all rectangles are one dimensional, i.e. segments,  by repeating this process on all rectangles. This is highly simplified, so the remaining should not be hard to come up with.

If there are two horizontal segments A,B (A to the left of B) that share a horizontal line L, then notice all vertical segments must be cut by L since they cannot share vertical line with two segments. Also all horizontal segments not on L must be cut by right boundary of L. So L and the right boundary of L are enough. (If A,B does share a point, then one dimensional case hypothesis still holds so the below falls through).

Otherwise, using one dimensional case, there is a vertical line cutting all horizontal segments. There is a horizontal line cutting all vertical segments. The proof is complete.

Very good question. :)

Call a pair of rectangles [i]bad[/i] if they cannot be cut with a vertical line (and so must be cut a horizontal line). For each [i]bad[/i] pair of rectangles, consider the line containing the lowest horizontal side among one of these rectangles. Among such lines, let $l$ be the highest line. Suppose it corresponds to the pair $R_1, R_2.$

We claim that for any [i]bad[/i] pair of rectangles, $l$ cuts through one of the rectangles in this pair. Suppose we have a [i]bad[/i] pair of rectangles $Q_1,Q_2$ where this is not the case. If both rectangles lie entirely above $l,$ this contradicts the maximality of $l.$ If one rectangle lies entirely above $l$ and the other one lies entirely below $l,$ then they cannot be cut by a horizontal line.

So both rectangles must lie entirely below $l.$ Suppose WLOG $R_1$ and $Q_1$ lie to the left of $R_2$ and $Q_1$ respectively. It's not hard to see if $Q_1$ and $Q_2$ are [i]bad[/i], we must either not be able to find a vertical line cutting $Q_1$ and $R_2$ violating the given, or a vertical line cutting $R_1$ and $Q_2$ violating the given.

So now consider the set of rectangles not cut by $l,$ no two rectangles can be [i]bad.[/i] It's not hard to see there must be a vertical line cutting through all these rectangles as desired (project onto $x$-axis and use Helly's theorem). $\square$


function
algebra proposed
algebra
pigeonhole principle

Let $ n\geq 3 $ be an integer and let $ \mathcal{S} \subset \{1,2,\ldots, n^3\} $ be a set with $ 3n^2 $ elements. Prove that there exist nine distinct numbers  $ a_1,a_2,\ldots,a_9 \in \mathcal{S} $ such that the following system has a solution in nonzero integers:
\begin{eqnarray*} a_1x + a_2y +a_3 z &=& 0 \\ a_4x + a_5 y + a_6 z &=& 0 \\ a_7x + a_8y + a_9z &=& 0. \end{eqnarray*}

[i]Marius Cavachi[/i]

I believe that this is a very beautiful problem  ;)

[i]Solution:[/i]

Suppose that $x_1<x_2<...<x_{3n^2}$ be the elements of $X$ and $X_1={\{x_1,x_2,...,x_{n^2}}\} , X_2{\{x_1,x_2,...,x_{2n^2}}\} , X_3{\{x_1,x_2,...,x_{3n^2}}\}$ and for every $(a,b,c)\in X_1\times X_2\times X_3$ we define $f(a,b,c)=(b-a,c-b)$ then we have function $f$ s.t. $f: X_1\times X_2\times X_3 \rightarrow Y\subset {\{1,2,...,n^3}\}\times {\{1,2,...,n^3}\}$ and $Y$ is the set of ordered pair $(x,y)$ s.t. $x+y\leq n^3$. we know that $X_1\times X_2\times X_3$ has a $n^6$ elements and $Y$ has $\sum\limits_{x=1}^{n^3-1} (n^3-x)=n^6-n^3-\dfrac {(n^3-1)n^3}{2}=\dfrac {n^6-n^3}{2} <\dfrac {n^6}{2}$ elements, and it's obviuosly that there exist distinct triples pair $(a_1,a_2,a_3) , (a_4,a_5,a_6)$ and $(a_7,a_8,a_9)$ s.t. $a_3-a_2=a_6-a_5=a_9-a_8=x$ and $a_1-a_2=a_4-a_5=a_7-a_8=$ and we know that all of the numbers $a_1,...,a_9$ are distinct numbers .Because $a_1,a_2,a_3\in X_1 , a_4,a_5,a_6\in X_2$ and $a_7,a_8,a_9\in X_3$ and we can see that the system has an root $x_0=a_4-a_7 , y_0=a_7-a_1$ and $z_0=a_1-a_4$ and we are done  :D


induction
combinatorics unsolved
combinatorics

Let $ M(n )\equal{}\{\minus{}1,\minus{}2,\ldots,\minus{}n\}$. For every non-empty subset of $ M(n )$ we consider the product of its elements. How big is the sum over all these products?

The expression $ ( \minus{} 1 \plus{} 1)( \minus{} 2 \plus{} 1)\cdots( \minus{} n \plus{} 1) \minus{} 1\equal{} \minus{}1$, when expanded, gives the desired sum? edit; take out the extra 1.  :)

In fact, this problem is solved in 5 minutes  :D
But the answer is -1  :lol:

An alternative way to express the key insight is to note that we can pair every subset $ A \subseteq M(n)$ except $ \{\minus{}1\}$ with $ A \Delta \{\minus{}1\}$, where $ \Delta$ denotes the symmetric difference, and the sum of the two elements of each pair so-formed is 0.  This method (the involution principle) generalizes poorly for this problem, but it can be very powerful in many other circumstances.

If we define $ S(n)$ to be the required answer, then we have:

$ S(1)\equal{}\minus{}1$, and for $ n \geq 2$, $ S(n)\equal{}S(n\minus{}1)\minus{}nS(n\minus{}1)\minus{}n\equal{}\minus{}(n\minus{}1)S(n\minus{}1)\minus{}n$

It follows by induction that $ S(n)\equal{}\minus{}1$.


Δίδεται κύκλος $ (O),$ με διάμετρο $ AB,$ και έστω $ C,$ $ D,$ τα σημεία τομής του από τυχόντα κύκλο $ (A),$ με κέντρο το σημείο $ A.$ Δια του $ B,$ φέρνουμε τυχούσα ευθεία η οποία επανατέμνει τον $ (O)$ στο σημείο $ B'$ $ ($ $ B',$ μεταξύ των $ A,$ $ C$ $ )$ και τέμνει επίσης τον $ (A),$ στα σημεία $ E,$ $ E'$ $ ($ $ E',$ μεταξύ των $ B,$ $ B'$ $ ).$ Εάν $ P,$ είναι σημείο επί της $ CD,$ τέτοιο ώστε $ PE\parallel BC$ και $ M,$ $ N,$ τα σημεία τομής της ευθείας $ BC,$ από τις $ PB',$ $ PE'$ αντιστοίχως, αποδείξτε ότι $ CM \equal{} PE$ και $ NB \equal{} NC.$'

Κώστας Βήττας.

Δυστυχώς κατάφερα να λύσω μόνο το δεύτερο μέρος της άσκησης ($ NB \equal{} NC$). :oops:

Κατ' αρχάς παρατηρούμε ότι $ CD$ η πολική του $ B$ ως προς τον $ (A)$, αφού $ BC, BD$ εφαπτομένες στον $ (A)$.

Ετσι $ B,S$ αρμονικά συζηγή των $ E,E'$. Αρα $ PE, PC, PN, PB$ αρμονική δέσμη. ($ S$ είναι η τομή των $ CD$, $ BE$)
Κι αφού $ BC$ παράλληλη στην $ PE$ σύμφωνα με βασικό θεώρημα το $ N$ είναι μέσο του $ BC$.

[quote="bilot4"]Δυστυχώς κατάφερα να λύσω μόνο το δεύτερο μέρος της άσκησης ($ NB \equal{} NC$). :oops:

Κατ' αρχάς παρατηρούμε ότι $ CD$ η πολική του $ B$ ως προς τον $ (A)$, αφού $ BC, BD$ εφαπτομένες στον $ (A)$.

Ετσι $ B,S$ αρμονικά συζηγή των $ E,E'$. Αρα $ PE, PC, PN, PB$ αρμονική δέσμη.
Κι αφού $ BC$ παράλληλη στην $ PE$ σύμφωνα με βασικό θεώρημα το $ N$ είναι μέσο του $ BC$.[/quote]

Δημήτρη τα κατάφερες πολύ καλά. Εγώ στην αρχή δεν το είχα δεί αυτό κι ας το έχω χρησιμοποιήσει αρκετές φορές.

( Μια ευθεία παράλληλη προς μία ακτίνα αρμονικής δέσμης, τέμνεται από της άλλες τρεις ακτίνες της, σε τρία σημεία που ορίζουν δύο ίσα ευθύγραμμα τμήματα )

Αυτή η άσκηση είναι εμπνευσμένη από μία άλλη που προτάθηκε από τον [b][size=100]radio[/size][/b], στο αγγλικό φόρουμ πριν δύο μήνες

στο

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

Για το πρώτο μέρος, έχουμε τη λύση που έδωσε ο [b][size=100]Huyen Vu[/size][/b] και έτσι έχουμε ολοκληρωμένη λύση στο πρόβλημα όπως τέθηκε εδώ.

Έδωσα τότε ένα Λήμμα που έλυνε το δεύτερο μέρος, ξεφεύγοντάς μου ότι λύνεται πολυ απλά, έτσι όπως παρουσιάστηκε από τον Δημήτρη, σήμερα.

Μετά βασιζόμενος σε ένα άλλο Λήμμα, είδα ότι αποδεικνύονται ταυτόχρονα και τα δύο ζητούμενα. Αποφάσισα λοιπόν να βάλλω εδώ το πρόβλημα γιατί νομίζω μπορεί να φανεί χρήσιμο το παρακάτω Λήμμα για αργότερα.

[b][size=100][color=DarkBlue]ΛΗΜΜΑ. - (βλέπε σχήμα t=165675) - Δίδεται κύκλος $ (O),$ με διάμετρο $ AB,$ και έστω $ C,$ $ D,$ τα σημεία τομής του από τυχόντα κύκλο $ (A),$ με κέντρο το σημείο $ A.$ Δια του $ B,$ φέρνουμε τυχούσα ευθεία η οποία επανατέμνει τον $ (O)$ στο σημείο $ B'$ $ ($ $ B',$ μεταξύ των $ A,$ $ C$ $ )$ και τέμνει επίσης τον $ (A),$ στα σημεία $ E,$ $ E'$ $ ($ $ E',$ μεταξύ των $ B,$ $ B'$ $ ).$ Εάν $ S\equiv CD\cap BB',$ αποδείξτε ότι $ \frac{SE'}{SB'}\equal{}\frac{SB}{SE}.$[/color][/size][/b]

Κώστας Βήττας.

ΥΓ. Θα δώσω περισσότερες λεπτομέρειες αργότερα, ανάλογα με το ενδιαφέρον σας :)

Λοιπόν έχω λύση .(Μπράβο στο Δημήτρη που το έβγαλε τόσο άμεσα  :) ) (αλλά θα βάλλω τη λύση μου για το ΝΒ=ΝC γιατί στο άλλο είναι μακροσκελής και δεν προλαβαίνω )

Λημματάκι
Έστω ότι η ΕP tεμνει τον (Α) στο G και η NP t;emnei ton (A) sto Q .Νδο τα B,G,Q είναι συνευθειακά
Αποδ (ευχαριστώ τον κ Κώστα για αυτή)
για το ότι δηλαδή τα $ B,$ $ G,$ $ Q,$ είναι συνευθειακά, προκύπτει άμεσα από το ότι το σημείο $ P,$ είναι το σημείο τομής των διαγωνίων $ EG,$ $ E'Q,$ του εγγραψίμου τετραπλεύρου $ EE'GQ.$

$ ($ E στω $ Q'\equiv (A)\cap BG.$  Το σημείο τομής των διαγωνίων του εγγραψίμου $ EE'GQ',$ κείται ως γνωστό, επί της $ CD,$ πολικής του $ B,$ ως προς τον κύκλο $ (A).$  Άρα η ευθεία $ E'Q',$ δέρχεται από το σημείο $ P,$ ως σημείο τομής των $ CD,$ $ EG$ και άρα έχουμε $ E'Q'\equiv E''Q$ $ \Longrightarrow$ $ Q'\equiv Q,$ που σημαίνει ότι τα $ B,$ $ G,$ $ Q,$ είναι συνευθειακά $ ).$

Αποδ της άσκησης
Από δύναμη σημείου είναι $ NC^{2}\equal{} NE'\cdot NQ$
Επιπλέον τα τρίγωνα (χρησιμοποιώντας την παραλληλία) ΝΕ'Β και ΝQB είναι όμοια άρα
$ \frac{NB}{NE'}\equal{}\frac{NQ}{NB}$ άρα $ NB^{2}\equal{} NE'\cdot NQ$ άρα $ NB \equal{} NC$

(ελπίζω να είναι καλή  :) )

[quote="vittasko"]
[b][size=100][color=DarkBlue]ΛΗΜΜΑ. - (βλέπε σχήμα t=165675) - Δίδεται κύκλος $ (O),$ με διάμετρο $ AB,$ και έστω $ C,$ $ D,$ τα σημεία τομής του από τυχόντα κύκλο $ (A),$ με κέντρο το σημείο $ A.$ Δια του $ B,$ φέρνουμε τυχούσα ευθεία η οποία επανατέμνει τον $ (O)$ στο σημείο $ B'$ $ ($ $ B',$ μεταξύ των $ A,$ $ C$ $ )$ και τέμνει επίσης τον $ (A),$ στα σημεία $ E,$ $ E'$ $ ($ $ E',$ μεταξύ των $ B,$ $ B'$ $ ).$ Εάν $ S\equiv CD\cap BB',$ αποδείξτε ότι $ \frac{SE'}{SB'}\equal{}\frac{SB}{SE}.$[/color][/size][/b]

[/quote]

Κατ' αρχάς κ. Βήττα σας ευχαριστώ πολύ για τα καλά σας λόγια :)

Σε ότι αφορά το λήμμα δεν ξέρω αν εννοείται κάτι άλλο αλλά αυτό που ζητείται να αποδειξουμε είναι άμεση απόρεια του ριζικού άξονα $ CD$ ή πιο απλά της δύναμης σημείου του $ S$ ως προς τους 2 κύκλους οπότε δεν χρειάζεται καν το Α να είναι κέντρο του ενός κύκλου :huh:

Συγχωρέστε με αν δεν έχω καταλάβει κάτι σωστά...

Σε ευχαριστώ Δημήτρη, για την παρατήρηση.

Εσύ σωστά το έχεις καταλάβει, απλά εγώ κόλλησα στο συγκεκριμένο σχήμα με το $ A,$ πάνω στον κύκλο $ (O),$ το οποίο βέβαια, δεν είναι απαραίτητο για τη σχέση αυτή. :(

Σ’ ευχαριστώ Σιλουανέ και σένα, για άλλη μία ενδιαφέρουσα προσέγγιση, για την απόδειξη του δεύτερου μέρους.

Θα βάλλω αργότερα ολοκληρωμένη την απόδειξη που έχω υπόψη μου, βασισμένη στη σχέση (Λήμμα) που προανέφερα, που μας πάει από το $ CM \equal{} PE,$ στο $ NB \equal{} NC.$

Μπορούμε όμως να ολοκληρώσουμε την απόδειξη, συνεχίζοντας την ιδέα του Δημήτρη, που μας πάει αντίστροφα, από το $ NB \equal{} NC,$ στο $ CM \equal{} PE.$

Δεν θα σας το χαλάσω όμως (μαρτυρώντας τη λύση), γιατί τελικά δεν είναι δύσκολο.

[hide]Αρκεί να δούμε τη χαρακτηριστική ιδιότητα που έχει το σημείο $ B'$ $ ($(που οφείλεται στο ότι το $ A,$ είναι πάνω στον κύκλο $ (O)$... :) $ )$ και πως αυτή μας οδηγεί στο $ B'P\parallel CE',$ και αυτό, στο ζητούμενο.[/hide]
Σας ευχαριστώ για το ενδιαφέρον σας, Κώστας Βήττας

Η απόδειξή μου για το δεύτερο σκέλος .
Από το θεώρημα της δύναμης σημείου ως προς τους δύο κύκλους έχουμε ότι $ SB'\cdot SB \equal{} SE\cdot SE'$ άρα
$ \frac{SB'}{SE'}\equal{}\frac{SE}{SB}\equal{}\frac{SP}{SC}$  από την παραλληλία των BC ,EP .
Από την $ \frac{SB'}{SE'}\equal{}\frac{SP}{SC}$ συμπεραίνουμε ότι $ CE'//B'P$ .

Άρα από το θεώρημα Θαλή έχουμε $ \frac{NC}{CM}\equal{}\frac{NE'}{E'P}\equal{}\frac{BE'}{E'E}\equal{}\frac{NB}{EP}$  και αφού
$ NC \equal{} NB$ $ CM \equal{} EP$ , το ζητούμενο .


AMC AIME email trigonometry USA(J)MO USAMO geometry

Good luck to everyone taking the AIME II on Tuesday!

Thank

But of course if the difficult rises...the school board is going to pay for their well chosen spring break.... :(

i jope it is harder than AIME1  !!!! so ican qualify.

sorry for those taking AIMEII for saying that, but i want to QUALIFY!!!

btw, after AIMEII, can someone TeX them and send them to me through email???? is that legal?

Technically it is not ILLEGAL because there is nothing that says you can not do this in the teacher's manual while in previous years there has been a statement specifically asking that this not be done. However, I would advise you to wait until the answers are released by the AMC or AoPS before asking for someone to send you the questions.

[quote="yif man12"]
Here's to hoping the AIME II is the easiest AIME of all time!  :)
[/quote]

then here's to hoping the AIME II is NOT the easiest AIME of all time!!!!!

It wasn't really that easy, but I did well on this AIME in comparison to the other ones that I've taken for practice. (I've done '83-01) I thought it was easier than AIME I, but other people from my school disagreed.

Questions 1-10 were just as easy as the AIME 1. I thought 11 and 12 were difficult, but 12 was easy for a 12. Of course, it wasn't as easy as #12 on the AIME 1 but yeah.

13 was easier than its AIME 1 counterpart. Unfortunately, I waited until there were only 10 minutes left to start it and didn't finish in time. (I had simplified the problem to two linear equations. bleh...)

Over all, it was a bit tougher than the AIME 1, but still easy for an AIME. It wasn't that much tougher, and I expect scores not to be as high, but it was generally kinda fair I guess.

9 would be a bummer for anyone who hasn't had trig. But then again, these AIMEs have much less trig than they used to anyways so that's really not an excuse for anyone.

Besides that, if your goal is for USAMO qualification it looks like pretty smooth sailing.

[quote="joml88"]I took the AIME I but I've looked at the alternate already.  Finally there is a trig/complex numbers problem!  And I think 4 of the last 5 were geometry which is really strange imo.[/quote]

More than half of AIME I was geometry as well...

[quote="joml88"]I took the AIME I but I've looked at the alternate already.  Finally there is a trig/complex numbers problem!  And I think 4 of the last 5 were geometry which is really strange imo.[/quote]

And both #12 and #14 can be "trigged". Especially #14, you can find sin(DAC), and find sin(ABE), and use Law of Sinces on triangle ABE to find BE. It's not very pretty and in the end it may save you more time than the elegant solution.

WHERE CAN I GET THE QUESTIONS IN AIME II?

[quote="joml88"]The amount of geom problems wasn't what was strange to me...the fact that 4 of the last 5 was of one topic was what seemed strange.[/quote]

Well what I was attempting to point out (probably unsuccessfully) was that because of the number of geometry problems on AIME I, there had to be a lot on AIME II. As you can see, there is actually a good variety in the first half. That would mean that the problems near the end would be almost all (or at least mostly) geometry...

[quote="Mildorf"]From the math jam, I thought there were a LOT of nice problems on the Alternate AIME - particularly the recursion and the 900-square questions.

I wish I could've taken it. :)[/quote]

Same here! 14, 15 were pretty cool!

[quote="Mildorf"]From the math jam, I thought there were a LOT of nice problems on the Alternate AIME - particularly the recursion and the 900-square questions.

I wish I could've taken it. :)[/quote]Aye, but my Geometry needs work.  I spent 3 days studying--getting all the formulas--and still couldn't apply it to the trig.  So much for having a handle on that.  (Cheesey high school classes tell you about Cosines and the complex plane, but don't really give you a way how to use them.)  Still, it was a good test--and I had fun with it.  Is that all that matters?~


Fie sirul $\displaystyle(a_n)_{n\geq 1}$ definit prin $\displaystyle a_{n+1}=1+a_1a_2...a_n, a_1=1$

Sa se arate ca sirul $\displaystyle b_n=\frac{1}{a_1}+...+\frac{1}{a_n}$ este monoton si marginit si sa i se calculeze limita

Avem evident ca sirurile $(a_n),(b_n)$ sunt crescatoare.Se demonstreza usor prin inductie ca  $(a_n)>(n-1)!$.(1)
Fie $(e_n)$ sirul lui Euler.Avem: $e_n  = 1 + \frac{1}{{1!}} + \frac{1}{{2!}} + \frac{1}{{3!}} + \frac{1}{{4!}} +  \cdot  \cdot  \cdot  + \frac{1}{{n!}}$
Si $b_n  = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{7} + \frac{1}{{43}} +  \cdot  \cdot  \cdot  + \frac{1}{{a_{n - 1} }}$.
Si din (1) rezulta ca $b_n<e_n<e$ deci sirul $(b_n)$ este marginit si monoton.
Limita nu am reusit inca sa o calculez.

Se foloseste faptul ca $a_{n+1}=1+(a_{n}-1)a_n$

Este un şir faimos, al celor mai bune aproximaţii ale unităţii prin fracţii egiptene. Astfel, se poate arăta că dacă $b_1,b_2,\ldots ,b_n$ sunt numere naturale astfel ca$\frac {1}{b_1}+\ldots +\frac{1}{b_n} < 1$ atunci $\frac {1}{b_1}+\ldots +\frac{1}{b_n} \le \frac {1}{a_1}+\ldots +\frac{1}{a_n} $.
Detalii se găsesc in cartea "Mathematics Miniatures" de S. Savchev şi T. Andreescu.

A proof that $\Sigma \frac{1}{a_n}$ is an optimal Egyptian fraction < 1 appears  [url=http://arxiv.org/math.CA/0502247]here[/url].


This is just a plug for a thread I've set up in the intermediate section. Though it's outside the Getting Started forum's scope, it's definitely solvable by the more ambition beginners; maybe this way I can "induct" a few beginners into the intermediate forum too. ;)

Anyway, it's at [url]http://www.artofproblemsolving.com/Forum/viewtopic.php?t=14581[/url].

Thanks, Osiris, every beginner gets better sooner or later, and its good to know that there is an increasing variety of appropriate problems on the Intermediate Topics forum.

Hey thanks for the problems, i was actually able to do them (geometry is not my strong point), i encourage others to try this set (dont be discouraged by the mention of Ceva  :) ). Anyway good luck.

p.s.- angle chasing is for losers...like me.

They're doable is your strong point is geometry and of course, Ceva isn't nessacary. (Though I think it not using it makes you a loser like me and badapproximation)


topology
advanced fields
advanced fields unsolved

Let $ X$ be a CW complex that is the union of subcomplexes $ A$ and $ B$. My book says that $ B/(A \cap B)$ and $ X/A$ are homeomorphic as long as $ A \cap B \neq \emptyset$.

Is there an easy way to see this?

Wow. Could this be any more odd? Corollary 2.24 in Hatcher? I read this today.

Yes, that's where its from. Do you know why its true?


Box A contains marbles numbered 1-8 and Box B contains marbles numbered 1-11. If two marbles are drawn without replacement from Box A and placed into Box B, and then two marbles are drawn with replacement from Box B, find the probability that the product of the two numbers drawn from Box B is odd.

[hide]
the only way for the two marbles to have an odd product is if they are both odd. the probablility is thus:
$(\frac{6}{11})(\frac{1}{2})$ or $\frac{3}{11}$
[/hide]

Take a look at the problem again: the marbles from A are being placed into B.  Then, only the marbles picked from B are part of the product.  Here is my solution (I am not sure if it is right  :( ):
[hide] I will divide the possiblities into cases
Case 1: The ones picked from A are both even
The probability that both will come out even is (4/8)(3/7)=3/14.  Now, the probability that both marbles picked from B will be odd is (6/13)(5/12)=5/26.  Multiply these to get 15/(14*26)
Case 2: The ones picked from A will be even and odd
The probability of this occuring is 1*4/7=4/7.  Now, the probabity of both odds being picked is (7/13)(6/12)=7/26.  Multiply these to get 2/13.
Case 3: The ones picked from A will be both odd.
The probablity of this happening is (4/8)(3/7)=3/14.  Now, the probability of both being picked odd is (8/13)(7/12)=14/39.  Multiply these to get 1/13.
Add all of our final products to get 99/(14*26)=99/364, which is our answer. [/hide]

[quote="Kyokun013"]The Quatto Master, your thinking is correct, but you're not there yet. Remember though, an even*an even=an even, an even*an odd=an even, and an odd*an odd=an odd. Consider to the hidden. I'll divide mine into three cases as well, with 2 subcases for each.
[hide]
Case 1: (Both from A are odd)
In bag A there's 4 odds and  4 evens, there's a 1/2 chance of a the number to be even, and same odds for it to be odd. But then, the odd of picking another odd changes to 3/7, so for the probability of picking both odds, it will be 3/14, since 1/2*3/7=3/14, and that is what you stated, but then, in Bag B, you have now 8 odds, and 5 evens.
Subcase A:
For both numbers to be odd from bag B, you have an 8/13 chance for the first number, and a 7/12 chance for the second number. Which gives you a probability from this case of both numbers to be odd to be 14/39 for both to be odd, and that means a 14/39 chance for the product to yield an odd.
Subcase B:
Now then, since the only case is that an odd*an odd= an odd, that's the only thing we need, if you wish to know, 25/39 probability that in this case, the numbers' products would yield an even.
Case 2: (1 From A is odd, and 1 From A is even)
For this case to occur, there's 1/2 chance for there to be an even, then a 4/7 chance for there to be an odd after that, and vice versa. With that, there's a 2/7 chance times 2 since both cases can happen, which means a 4/7 chance of this case occuring. In Bag B you now have 7 odds, and 6 evens.
Subcase A:
For both numbers from bag B to be odd, that's 7/13 for the first to be odd, and 6/12 for the second to be odd. That's 7/26 chance for both to be odd, since 7/13*6/12=7/26. Therefore, for this case, there's a 7/26 chance for there to be a product of odd to be yielded.
Subcase B:
Now then, since the only case is that an odd*an odd= an odd, that's the only thing we need, if you wish to know, 19/26 probability that in this case, the numbers' products would yield an even.
Case C: (Both numbers from Bag A are even)
For this to occur, that's 1/2 for the first number to be even, and 3/7 for the second to be even. The chance of this happening is 3/14. Which has 6 odds and 7 evens in bag B
Subcase A:
For both numbers in bag B to be odd, that's 6/13 for the first number to be odd, and a 5/12 chance for the second number to be odd. The total chance of both numbers to be odd is 5/26.
Subcase B:
Now then, since the only case is that an odd*an odd= an odd, that's the only thing we need, if you wish to know, 21/26 probability that in this case, the numbers' products would yield an even.
So now we have a 5/26 chance, a 7/26 chance, and a 14/39 chance. Well, here's what you do. Add up the denominators, and that's how many combinations of pulling numbers. Then add up your numerators and that's how many of the products will be odd. So basically, 26/91 which is really, 2/7.

*NOTE* The way I added these fractions is not how you add up fractions. It only works in this case because the denominators all share the same fact that they represent combinations.[/hide][/quote]
Wait, I am confused.  Shouldn't the probability of both being picked odd from A [b]and[/b] the probability of both being picked odd from B be (3/14)*(14/39) to get 1/13?  Then shouldn't you just take (7/26)*(4/7)=2/13 for one picked even and one picked odd [b]as well as[/b] both being picked odd from B?  Finally, shouldn't the (5/26)*(3/14) for the chance that all evens will be picked from A [b]and[/b] all odds from B?  Then you should just add all of the fractions.


geometry
trigonometry
ratio
trig identities
Law of Sines
area of a triangle
analytic geometry

What is the area of a triangle $ABC$ with 2 given angles $A,B$ and the length of $AB$?

Subtract the 2 angles from 180 to get the third and then use Law of Sines (I know I'm overcomplicating this) to get side b.

b=c(sinb)/(sinc)

Then use the area of the triangle formula b(c)(sinA)/2 so you get (c(sinb)/(sinc))(c)(sinA)/2.

here is another way to do this problem.
well since you know 2 angles you can eaisly find the other one.
now from the law of sines we have $\frac{a}{sinA}=\frac{b}{sinB}=\frac{c}{sinC}$
and the area of a triangle can be expressed as $\frac{absinC}{2}$
so lets way the side length we are given is $c$. so we will find the area useing sides $c$ and $a$ with included angle $B$.  by manipulating the law of sines we have $a=\frac{csinA}{sinC}$. so the final area is $\frac{c^2sinA}{2sinC}$.

hope this was helpful.

also can be done by analytic geometry

the ara of a triangle formed by two $\vec{A}, \vec{B}$ is $\frac{1}{2}\vec{A}\times \vec{B}=|\vec{A}||\vec{B}|\sin{\alpha}$  where $\alpha$ is the angle between $\vec{A}$ and $\vec{B}$

I'm wondering if there is a less trigonometric way of doing this. What I mean is without using Law of Sines because Law of Sines hides the geometric properties of it  :blush: . Like amirthlusa's hints, that has some geometric flavor. But thank you to Bestone & maokid7 for the help

i dont think there is a non-trignometrical solution because since we are given the angles, the only property that relates sides with angles and consequently area, are the trignometric ratios!!!

I think the Law of Sines proof has more geometric flavor than amirhtlusa's proof, of course not saying any one is better than the other.

The cross product is defined, pretty much, using trigonometry.

the area according to me is
a^2 sinAsinB/2 and has no direct relation to angles
area doesnt depend on sides or if sides could tend to infinity even with the same angles and therefore leading to invalid result


Hello,

First than all, I don't want to discuss about specific books, if I do, it is just as an example to clarify my idea. I want to know what people thinks about the most nice writing style for math books.

For examples, I took an undergrad course in Analysis way back in '99, using the book "Elements of Analysis" by J.A. Dieudonne. The book is a great reference, but is, acconding to my opinion, not a good book to learn from. Most of the proofs don't really tell you how to apply other theorems, and basically, many of the proofs are one line that says:

The resoult follows from 1.2.5, 1.6.8, 2.1.2, 2.6.35, 3.4.23, 4.2.19, 4.8.64, 5.6.39, 6.6.75 and 7.4.21.

OK, I agree that it is a one line proof, but it is not clear at all (starting because if you want to track arguments of the proof, probably you will have to read the whole book again!)

On the other hand, I took my Diff Eq course with the "Differential Equations" of Simmons. I loved that book, pretty well written, everything clear, explained step by step, beautiful (according to my personal opinion). But anyway, with the old scheme of [b]Definition-Theorem-Proof[/b].

I have never use the book of Algebra by Artin, but many people have told me that it has a good scheme that first tells you about a problem, then, almost as an informal exposition of ideas, he goes solving the problem, and at the end expose the resoult as a Theorem. Some of my friends found it very nice to read.

Any way, what do you consider the best writing style for math books, thinking that those books are going to be used as text book to learn from them, and not to use them as a reference only.

Best,

For me, I learned math best with the good ol' definition-theorem-proof style of writing.

However, you cannot just read math, you have to write out stuff.


$ x_{n}$
$ x_{1}$=3
$ x_{n\plus{}1}$=$ \sqrt{9x^{2}_{n}\plus{}12x_{n}\plus{}3}$
Find all a such that
$ \large\frac{x_{n}}{a^{n}}$  converge at a point different from 0

$ x_{n\plus{}1}\equal{}\sqrt{(3x_{n}\plus{}2)^{2}\minus{}1}$
we take $ (u_{n})$ and $ (v_{n})$ such that $ u_{1}\equal{}v_{1}\equal{}x_{1}\equal{}3$ and $ u_{n\plus{}1}\equal{}3u_{n}\plus{}2,v_{n\plus{}1}\equal{}3v_{n}$
then we have $ u_{n}>x_{n}>v_{n}$ where $ u_{n}\equal{}4.3^{n\minus{}1}\minus{}1,v_{n}\equal{}3^{n\minus{}1}$
then $ \forall a,n:\ \frac{4.3^{n\minus{}1}\minus{}1}{a^{n}}>\frac{x_{n}}{a^{n}}>\frac{3^{n\minus{}1}}{a^{n}}$
if $ a>3$ then $ 0\ge lim\frac{x_{n}}{a^{n}}\ge 0$
if $ 3>a>0$ then $ lim\frac{x_{n}}{a^{n}}\equal{}\plus{}\infty$
if $ a<0$ $ \frac{x_{n}}{a^{n}}$ goesn't converg
so $ a\equal{}3$ where we have $ 4/3\ge\frac{x_{n}}{a^{n}}\ge 1/3$


It looks like the question is missing something. sri340, could you edit this?

Since $ \frac{27}{45} \equal{} \frac{3}{5} \equal{} \frac{9}{15} \equal{} \frac{60}{100}$ gives $ a\equal{}3, b\equal{}15, c\equal{}100$ and $ a\plus{}b\plus{}c\equal{}118$ is option $ E$, I think the question might have been:What does $ a\plus{}b\plus{}c$ equal?


geometry
geometric transformation
homothety
ratio
3D geometry
sphere

I'm looking for a proof of the [b]Descartes circle theorem[/b]:
Given four pairwisely externally tangent circles of radii $r_{1}$, $r_{2}$, $r_{3}$, $r_{4}$, we have the following relation:

$2\left(\frac{1}{r_{1}^{2}}+\frac{1}{r_{2}^{2}}+\frac{1}{r_{3}^{2}}+\frac{1}{r_{4}^{2}}\right)=\left(\frac{1}{r_{1}}+\frac{1}{r_{2}}+\frac{1}{r_{3}}+\frac{1}{r_{4}}\right)^{2}$.

hey, I'm sure you have this proof. Please, send me ;-)

This is going to be long?

First let 1/ri=ai. Consider the inversion of pole O = the point where C1 and C2 touch and power 4r1*r2. Consider this inversion is negative (that means that for each pt M, M and its image M? are on opposite sides of O). Our configuration turns into the following thing: 2 parallel lines C1? and C2? (images of C1 and C2) for which C1? is at distance 2r2 of O and C2? is at distance 2r1 of O. Then there is a circle C3? (image of C3 and generally figure F? is the image of figure F) tangent to both lines, so its radius is r1+r2 and another circle C4? also tangent to both lines (also with radius r1+r2) and with its center farther from O than C3? because C4 has its center closer to O than C3. Circles C3? and C4? are also tangent to each other.

Now let A be the proj of O on line C2?, B the pt of tangency between C3? and C2? and C the pt of tangency between C4? and C2?.  Obviously BC=2(r1+r2) and let AB=a. For any circle C let C(O) be the power of O with respect to C. There is an important result which you can prove yourself. If we transform a circle C by an inversion of pole O (which is not situated on C) and power k^2 (k is a segment), the image is the same circle that would be the image of C if we had transformed it by a homothety of center O and ratio k^2/C(O). Call this result R.

Since by applying the inversion again to circle C3? we get circle C3, by applying R to this we get r3/(r1+r2)=4r1*r2/C3?(O), so C3?(O)=4r1*r2(r1+r2)/r3. At the same time C3?(O)=OO3?^2-(r1+r2)^2= (r1-r2)^2+a^2-(r1+r2)^2= a^2-4r1*r2. From these 2 expressions of  C3?(O) we get a^2= 4r1*r2*(r1+r2+r3)/r3 (*). C4?(O)= OO4?^2-(r1+r2)^2= (r1-r2)^2+(a+2(r1+r2))^2-(r1+r2)^2 (**). By applying R to C4? we get r4/(r1+r2)=4r1*r2/C4?(O) (***). By replacing a in (**) with the value found in (*) we can find C4?(O) in terms of r1, r2, r3. From (***) we get a4= C4?(O)/4r1*r2*(r1+r2), so we can find a4 as an expression of r1, r2, r3. If we write a4 as an expression of a1, a2, a3 we get sth really nice: a4=a1+a2+a3+2((r1+r2+r3)/r1*r2*r3)^1/2. This is after all the boring calculations. Just write the equality in Descartes? thm as an 2nd deg eqn in a4 and you?ll see that one of the roots is exactly the value we found for a4, so that equality is verfied.

Sure hope there are no calculation mistakes. Bye!

thaxn a lot Grobber. I love inversion ;-)

It's a nice proof! Is it yours ? Or is it from a book ?(if it is, what is the title of this book ?)

The proof's mine (quite proud of it too :D). I'm sure you'll find similar stuff in books. I can't imagine where to start without inversion. Actually I remember I proved this quite a while ago, but it took me some time to remember the proof.

hey,just a wicked thought
if descartes found this theorem,he cudnt have come up with sumthing half as beautiful as Grobber did (with due regards to descartes :D  :D inversion wasnt known at that time ).so duz ne1 have ne ideas abt a different proof.the french guys here,mayb??
best regards

Here another of proof

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

---------------------------------------------------------------------------------

Wilker,J.B "Four proofs of a generalisation of the Descartes Circles
Theorems" Amer.Math.Monthlly 76, 278-282, 1969.

Sorry mathematics library is closed now, i cannot see this article to
give the ideas.

----------------------------------------------------------------------------------
We have also a version in n-dimensional space, n+2 mutually touching
n-spheres can always be found , and the relationship pf their curvature
is

n(k_1^2 +...+k_(n+2)^2) = (k_1+...+k_(n+2))^2 where k_i=1/R_i

[color=darkred][b][u]A well-known property.[/u][/b] Let $C_{k}=C(R_{k})\ ,\ k\in\overline{1,3}$ be three externally tangent circles (two-two) and the all these are externally tangent to the circle $C(r)$ and internally tangent to the circle $C(R)$. Then $\{\begin{array}{c}R_{1}+R_{2}+R_{3}=m\\\ R_{1}R_{2}+R_{2}R_{3}+R_{3}R_{1}=n\\\ R_{1}R_{1}R_{3}=p\end{array}\|$ $\Longrightarrow$ $\{\begin{array}{c}R=\frac{p}{2\sqrt{mp}-n}\\\ r=\frac{p}{2\sqrt{mp}+n}\end{array}$.
[b]Remark.[/b] With another words, $R_{k}\ ,\ k\in\overline{1,3}$ are the roots of the equation $x^{3}-mx^{2}+nx-p=0$.[/color]


geometry
3D geometry
sphere
rotation
geometric transformation
probability
expected value

I am thinking of writing a math olympiad...requiring bs solutions for each question. It will contain two parts, with 3 questions in each. Scores will be based on creativity, humor and the relative likelihood of getting away with that bs solution. However, there won't be any comments unless you have an extraordinary solution. Example question:

1. Given a circle, square it.
[hide="Solution"]
$ \circ^2$. The circle has been squared, as desired.
[/hide]

Not a great example, but you get the idea.  :)

Signing-up is not necessary, but if you are interested, it'd be nice to post in this thread so I can get an idea of how many solutions I'll be reading. Also, the best bs solutions to each question will be posted.

Cool. How will Creativity/Humor/Likelihood categories be weighted?

[quote="zephyredx"]Likelihood will probably have a little less weight since most solutions will have extremely small likelihoods of passing. Also, creative bsing usually results in humor, so I would focus on creativity.[/quote]

I join.

BTW, there have been incidents where total BS solutions have been accepted...

[quote="pythag011"][quote="zephyredx"]Likelihood will probably have a little less weight since most solutions will have extremely small likelihoods of passing. Also, creative bsing usually results in humor, so I would focus on creativity.[/quote]

BTW, there have been incidents where total BS solutions have been accepted...[/quote]

True. However, extremely long and seemingly complicated proofs will receive a $ \minus{}0$ in this olympiad (otherwise, those incidents would happen quite often with me). Bs elegantly!  :wink:

Total join, I do this on all my math quizzes since he takes the top 5 scores and I have 5 100's. Bonus points for a right answer?

[quote="zephyredx"][quote="pythag011"][quote="zephyredx"]Likelihood will probably have a little less weight since most solutions will have extremely small likelihoods of passing. Also, creative bsing usually results in humor, so I would focus on creativity.[/quote]

BTW, there have been incidents where total BS solutions have been accepted...[/quote]

True. However, extremely long and seemingly complicated proofs will receive a $ \minus{} 0$ in this olympiad (otherwise, those incidents would happen quite often with me). Bs elegantly!  :wink:[/quote]

-0 is the same thing as 42 modulo 42. That is actually not BS. So a -0 is the same thing as a perfect score. Alternately, you could intepret -0 to = 1/0 = white MOP.

I will join.
Can we do nitpicking solutions (especially for story problems)?

@evilhamster: Sure, but it better be hilarious  :)

@mewtwo: There won't be any right answers  :P ...well, there might be a favored answer...

EDIT: Nevermind. I'll be too busy this week, so I'll have to postpone it a bit.

This seems fun.

I predict my score will be $ \minus{}(\minus{}(\minus{}(\minus{}(\minus{}(\minus{}(0))))))\equal{}0$

[quote="Brut3Forc3"]Can we do this on a Thursday so that zero is negative?
(Sorry, it's a stupid inside joke...)[/quote]

Good idea. That way, there could be NEGATIVE ZEROES!

Part One begins today! Bs solutions are due by pm on or before Thursday, Nov. 27 (in which case zero will be considered negative. Zero is considered positive tomorrow).

1. I play 5 games of chess against pythag011. I am always black, and he is always white. We both play strategically. What is the closest integer to the expected number of games that I lose?

2. Find [i]all[/i] solutions to $ x^y \minus{} 1 \equal{} 0$.

3. Let $ S$ be the set of all set. Suppose that $ S$ exists. Find the number of contradictions resulting from the existance of $ S$. Express your answer as an ordinal number.

[quote="mathblitz"]though im not in this i think i have the answer to 1 and 2 but i cant seem to figure out 3....[/quote]

You can still join in. Thursday is the deadline for submissions.

k i join and ill give you my answers in a correct fashion hopefully

apparently deadline is not until tomorrow meaning that someone hasnt finished...

Hurry! Never turn in an empty paper on any contests as long as it doesn't hurt you! (ok I'm being a hypocrite, but I learned  :) ) Send it in by the end of today!

Part 2 begins! Bs solutions are due on Monday, Dec 1.

4. If:
-A lemma llama is always a llama lemma
-Two llama lemmas are never together a lemma lemma
-Among any three numa numas there is always a lemma lemma
-Llama lemmas that are also lemma llamas can not be grouped in pairs,
How many lemmas are necessary to prove or disprove that the above is possible?

5. How many ways are there of getting from the point $ (0,0)$ to the point $ (\frac{1}{0},\frac{1}{0})$? Neglect the effects of friction, air resistance, etc.

6. Define $ m$ to be an undefined unit of length. Consider two parallel planes $ m$ units apart, and a sphere of arbitrary size with its center equidistant from the planes. The sphere is said to do a [i]barrel roll[/i] if it rotates in a way such that, from the point of view of the center of the sphere, the planes pass through every point in space except the points inside the sphere. The sphere rotates $ \frac{pi}{3}$ radians every second, but changes its direction of rotation every second. Let $ E$ be the expected number of seconds before the sphere does a barrel roll. Let $ N$ be a random point in space, and let $ P$ be the probability that, before the first barrel roll, $ N$ will be on a plane as the sphere changes its direction of rotation. It is known that the inverse of $ N$ is defined. Compute $ \frac{E}{P}$. Give your answer in terms of $ m$.

Bonus!: Find the limit of $ 6$ as $ 7$ approaches $ 9$.

At the end of this round. Grading might take a while though.

Hurry! Solutions are due at the end of today.

Hey can I have one more day pretty please? I was in Indiana and I have no time tonight?

@mewto: Alright, because Indiana was one of the best places I've been  :)

:rotfl: Solution to #1 by andersonw

1. I play 5 games of chess against pythag011. I am always black, and he is always white. We both play strategically. What is the closest integer to the expected number of games that I lose?

Clearly, Chewbacca comes from Kashyyyk. However, he lives on Endor. Clearly, that does not make any sense. Just think about it, does that make any sense to you? Why would Chewbacca want to live on Endor if he is 4 times taller than everyone there? That just does not make sense. Are you hearing me? I am not making sense. I'm answering this problem, but it does not make any sense! How does this relate to the problem? It doesn't, which is why it doesn't.... make... any... sense.
Q.E.D.

Chewbacca defense! You... you...
Can I hire you?


A disc jockey for the school dance downloads eight new songs from an online music store.  If he now must choose exactly two of these eight new songs to bring to the dance, how many different combinations of two songs are possible?

The key word is COMBINATIONS, here specifically the combination of choosing 2 from 8. Using a combination (nCr),

$ 8C2$
$ \equal{}\frac{8!}{2!(8\minus{}2)!}$ (by definition)

$ \equal{}\frac{8!}{2!6!}$

$ \equal{}\frac{8\times7\times6\times5\times4\times3\times2\times1}{2\times1\times6\times5\times4\times3\times2\times1}$

$ 6\times5\times4\times3\times2\times1$ in both the numerator and denominator cancel out, leaving

$ \frac{8\times7}{2\times1}$

$ \equal{}\frac{56}{2}$

$ \equal{}\fbox{28}$

There are 8 ways to choose the first song, and 7 ways to choose the second song.  However, we overcounted by a factor of $ 2!$ since order doesn't matter, so we get $ \frac{8\cdot 7}{2!}\equal{}\boxed{28}$

Try this problem where you choose $ r$ songs from the $ n$ total, and you get the formula mentioned above, $ \binom{n}{r}\equal{}\frac{n!}{r!(n\minus{}r)!}\equal{}\frac{n(n\minus{}1)(n\minus{}2)\cdots (n\minus{}r\plus{}1)}{r!}$

cookieboy, please do not post useless posts and multi-post, it's just :spam: :spam: :spam:


The following is also true:
\[ \sum \sqrt{\frac{a^2\plus{}4bc}{b^2\plus{}c^2}}\ge 2\plus{}\sqrt{2}\]

[quote="can_hang2007"][quote="shfdfzhjj"]I think they are true[/quote]
http://www.mathlinks.ro/viewtopic.php?t=124415
:)[/quote]

I slove it by the same way .:lol:


As I learned last year, the chatting that occurs before Nats - 'getting to know each other', 'what was the top score in your state?', 'how do you think you'll do?', etc. - is not good for one's study. The less you post in those topics, the better (most probably) you will do. Observe that cutiepi, piggypi, dnas, hexahedron, and the other AoPSers in the countdown last year did little if no chatting in those topics. The less time you spend on those topics, the better you will do probably.

This is not to say those topics are bad, but concentrate on the problems if you want to do best.

Billy

The thing is, there aren't many problems. There are only so many years you can review past years of problems and if you've been doing them for many months or a year or so, you've probably done all the ones you can find. The only thing left is maybe to redo some problems you missed that are posted on AoPS or see how to do them, but there aren't a lot of those kind of topics especially arround this time ;)

[quote="solafidefarms"]Observe that cutiepi, piggypi, dnas, hexahedron, and the other AoPSers in the countdown last year did little if no chatting in those topics.[/quote]

Who are cutiepi, piggypi, dnas, and hexahedron (for reference)?

I agree with this advice. I spent too much time on those kind of threads.
It is a bit too late for me though. :(

I agree with that, but there are not enough problems to practice...There are not many (so far I have not found any) middle school competitions that have questions on the national level.  If you delve into high school competitions, there are alot of stuff that will pop up that you won't need for nationals...

Nationals Nationals competitions are also not very easy to find or plentyful...

If you are good enough that all the previous comps you have done and do well on when you do them again, try writing questions, and posing them to us. Learn to understand the problems. Keep in practice. And you never know what will appear on MC, so do try harder competitions.

(They whom I did mention are, in no order, Andrew Ardito, David Benjamin, Karlanna Lewis, and Patricia Li, who are some of the AoPSers who made CD last year.)

Oh, hexahedron, I kept thinking hexaditiom.

Umm. Dnas and hexahedron only had about 50 posts anyways. Also look at I_Would_Say. About 75% of his posts last year were in forums like those and he still got second written as a [b]seventh[/b] grader.

Well I wouldn't say that posting here necessarily lowers your score...unless you're wasting a lot of time stalking all of your potential competitors.

I didn't make nationals either, but I am still working on problems so that I can be a good assistant coach for my homeschool team :D

[quote="Fanatic"]Meh, I didn't make it so I'm posting all the way[/quote]

Me neither, but there's always next year to study for.

But but but I ENJOY wasting my time pointlessly posting here so I have an excuse IF I dont win nats :P

Spammers for lyf.

I agree with biffanddoc's point, even though i hope to win.


quadratics
algebra
number theory unsolved
number theory

Prove that there are infinitely many pairs of positive integers $ a,b$ such that $ a^{2006}\plus{}1$ is divisible by $ b$, and $ b^{2006}\plus{}1$ is divisible by $ a$.

$ a^2\plus{}1|a^{2006}\plus{}1\equal{}(a^2\plus{}1)(a^{2004}\minus{}...\plus{}1), \ b^2\plus{}1|b^{2006}\plus{}1$.
Therefore sufficiently consider $ ab|a^2\plus{}b^2\plus{}1$. Pell's equation $ a^2\minus{}3ab\plus{}b^2\plus{}1$ had infinetely many solutions.

[quote="Rust"]Pell's equation $ a^2 \minus{} 3ab \plus{} b^2 \plus{} 1$ had infinetely many solutions.[/quote]

I'm sorry, but how is this Pell?

I am not sure as well but it is easy to prove that equation $ a^2 \minus{} 3ab \plus{} b^2 \plus{} 1 \equal{} 0$ has inifinitely many solutions with using quadratic equation (just consider the second root).

$ a^2 \minus{} 3ab \plus{} b^2 \plus{} 1 \equal{} 0 \Leftrightarrow$
$ 4a^2 \minus{} 12ab \plus{} 4b^2 \equal{} \minus{} 4 \Leftrightarrow$
$ (2a \minus{} 3b)^2 \minus{} 5b^2 \equal{} \minus{} 4$

which has the infinite solutions $ (2a \minus{} 3b) \plus{} b \sqrt{5} \equal{} (1 \plus{} \sqrt {5})(9 \plus{} 4 \sqrt {5})^n$.


algebra
polynomial
logarithms
induction
calculus
calculus computations

The coefficients of the polynomial part of $f_{k}$ are the Stirling numbers of the second kind.  I don't see how to turn this into anything useful, though  :oops:

Well $e^{x}=\sum \frac{x^{n}}{n!}$
[hide="All formalities left out below (that is, this is just a suggestion of an outline of a proof)"]We only need to prove, that $f_{k}(1)$ approximates $e^{k}$
That is, prove that $f_{k+1}(1)/f_{k}(1)$ approximates $e$.
We wish to prove \[\left(x\cdot \frac{\frac{d}{dx}\left(f_{k}(x)\right)}{f_{k}(x)}\right)\] at $1$ is close to $e$
In other words, show that if (all the following is at $x=1$)\[\frac{d}{dx}\ln f(x)\iff \frac{f'(x)}{f(x)}\] is within a neighborhood of $e$, then so is \[\frac{d}{dx}\ln\left[ x \cdot \left(\frac{d}{dx}f(x)\right)\right]\]
We may evaluate this as \[\frac{1}{x}+\frac{d}{dx}\ln f'(x)=\frac{1}{x}+\frac{f''(x)}{f'(x)}=1+\frac{f''(x)}{f'(x)}\]
Now we use $f_{k}=P_{k}\cdot e^{x}$\[f'_{k}=\left(P'_{k}+P_{k}\right)\cdot e^{x}\qquad f''_{k}=\left(P''_{k}+2P'_{k}+P_{k}\right)\cdot e^{x}\]
So it remains to prove that, at $1$, \[\frac{P'_{k}+P_{k}}{P_{k}}\approx e\implies \frac{P''_{k}+2P'_{k}+P_{k}}{P'_{k}+P_{k}}+1\approx e\]
Substituting $P'_{k}\approx (e-1)P_{k}$ into the last yields \[\iff \frac{P''_{k}+(2e-1)P_{k}}{eP_{k}}+1\approx e\iff P''_{k}\approx \frac{e(e-1)}{2e-1}\]
Which, if worked into a valid way somehow, can be shown by induction on $k$ and would result in an end of the proof after adding in appropriate epsilons, deltas, and error bounds :)

Someone tell if this method actually works :( [/hide]

On planet math about stirling numbers, this might be helpful:
\[ e^{x(e^{t}-1)}= \sum_{n=1}^\infty \sum_{k=1}^{n}S(n,k)\, x^{k}\,\frac{t^{n}}{n!}.\]


inequalities
induction
number theory proposed
number theory

Let $n$ be a positive integer. Define a sequence by setting $a_{1}= n$ and, for each $k > 1$, letting $a_{k}$ be the unique integer in the range $0\leq a_{k}\leq k-1$ for which $a_{1}+a_{2}+...+a_{k}$ is divisible by $k$. For instance, when $n = 9$ the obtained sequence is $9,1,2,0,3,3,3,...$. Prove that for any $n$ the sequence $a_{1},a_{2},...$ eventually becomes constant.

Exactly for $k\ge \sqrt{2n}$ we get $a_{k}=a_{k+1}=...$

Not sure if revival of these topics is allowed or not, but I've come up with a solution and wouldn't mind having it evaluated.
[hide]For any such sequence $(a_n)$, let $(b_n) = \sum_{i=k}^n a_k$.  By the properties of this sequence, we know that $b_n = n d_n$ for some positive integers $b_n$ and $d_$ for all $k \in \mathbb{N}$.

Now choose a specific element of the sequence $b_k = k d_k$.  Since $d_k \in \mathbb{N}$, we either have $0 < d_k < k$ or $d_k \geq k$.  In the first case, $b_{k+x} = b_k + a_{k+1} + a_{k+2} + ... + a_{k+x} = k d_k + x d_k = (k+x) d_k$.  Because $0 < d_k < k < k+x$, for any $a_n$ where $n \geq k$, $a_n = d_k$, so $(a_n)$ eventually becomes constant.

In the second case, where $d_k \geq k$, we shall prove that $d_n \geq d_{n+1}$ for all $n \geq 2$.  For contradiction, assume that $d_n < d_{n+1}$ for some $n \in \mathbb{N}$.  We then have $b_{n+1} = b_n + a_{n+1} \leq n d_n + n$.  However, we also have $b_{n+1} = (n+1)(d_{n+1}) \geq (n+1)(d_n + 1) = n d_n + n + d_n + 1$.  These two inequalities imply that $n d_n + n + d_n + 1 \leq n d_n + n$ or $d_n + 1 \leq 0$, which is clearly a contradiction.  We thus conclude that $d_n \geq d_{n+1}$ for all $n \geq 2$.  Thus, even if $d_k \geq k$, we know that $0 < d_{d_k+1} \leq d_k < d_k + 1$.  Thus, the second case ultimately reduces to the first case, so $a_n = d_{d_k + 1}$ for all $n \geq d_k+1$, so $(a_n)$ eventually becomes constant and we are done.[/hide]

[quote="yankeesrule007"]By the properties of this sequence, we know that $b_n = n d_n$ for some positive integers $b_n$ and $d_$ for all $k \in \mathbb{N}$. [/quote]

Specifically what properties of the sequence did you use to determine that?

[hide]Let $S_i$ be the sum of the first $i$ terms of $a_k$. Then, let $\frac{S_i}{i}=D_i$. Notice that if $D_j<j$, for some integer $j$, then the sequence becomes constant with $a_x=D_j$, where $x$ is an integer and $x> i$.

Lemma: There is a point where $D_j<j$

Since $S_k<S_{k-1}+k$,

 $S_k<S_1+\frac{(k)(k+1)}{2}-1=n+\frac{(k)(k-1)}{2}$

$\frac{S_k}{k}<\frac{n}{k}+\frac{k-1}{2}$

When $k=n$,

$\frac{S_n}{n}<1+\frac{n-1}{2}<n$

Which proves the lemma.

Thus, from the lemma, there is always a point where $D_j<j$, so all sequences will eventually become constant.[/hide]

[hide="Even simpler?"]Let $b_i = \frac{a_1+\cdots +a_i}{i}$. Because $b_{i+1} = \frac{a_1+\cdots +a_{i}+a_{i+1}}{i+1}< \frac{a_1+\cdots +a_i+i}{i} = b_i+1$, the sequence $\{b_i\} _{i=1}^\infty$ is nonincreasing.

Because the $b_i$ are positive integers, $b_i$ eventually becomes constant, so $\{a_1+\cdots +a_i\}_{i=1}^\infty$ eventually becomes arithmetic, so $a_i$ becomes constant, as desired. [/hide]

In ThinkFlow's solution, why does $b_i$ have to become constant? I am sorry if this is a dumb question.

[quote="ThinkFlow"]Let $b_i = \frac{a_1+\cdots +a_i}{i}$. Because $b_{i+1} = \frac{a_1+\cdots +a_{i}+a_{i+1}}{i+1}< \frac{a_1+\cdots +a_i+i}{i} = b_i+1$, the sequence $\{b_i\} _{i=1}^\infty$ is nonincreasing.

Because the $b_i$ are positive integers, $b_i$ eventually becomes constant, so $\{a_1+\cdots +a_i\}_{i=1}^\infty$ eventually becomes arithmetic, so $a_i$ becomes constant, as desired. [/quote]
1. $b_i = \frac{a_1+\cdots +a_i}{i}$ is a positive integer, precisely by the way $a_i$ is chosen;
2. $a_{i+1} \leq (i+1) - 1 = i$, so $b_{i+1} = \frac{a_1+\cdots +a_i + a_{i+1}}{i+1} \leq$ $ \frac{a_1+\cdots +a_i + i}{i+1} <$ $ \frac{a_1+\cdots +a_i + i}{i} = $ $\frac{a_1+\cdots +a_i}{i} + 1 = b_i + 1$;
3. Since the sequence $(b_i)_{i\geq 1}$ is made of positive integers, from $b_{i+1} < b_i +1$ follows $b_{i+1} \leq b_i$, hence the sequence is non-increasing;
4. Therefore the sequence $(b_i)_{i\geq 1}$ must become eventually constant, since there are only a finite number of times (namely $b_1=a_1=n$ times) when it may strictly decrease (by at least $1$ at each step).

[hide="A little different"]I think you can do this with induction. Obvious for n=1 (the sequence is 1, 1, 1,...). Now we can split the inductive step into two cases: going from odd to even and going from even to odd. Say k is odd and the sequence for n=k is $k, 1, k_3, k_4 \dots$ Then the sequence for k+1 is $k+1, 0, k_3, k_4 \dots$ In other words, the sequences are identical after the first two terms.

Then when going from even to odd: say n=k is even and sequence is again $k, 0, k_3, k_4, \dots$ and then we can look at what happens for n=k+1. This sequence is different from the previous one by the following: $+1, +1, +1 (-2), +1(-3), +1(-4) \dots$ and so on. In other words, we're looking at the sequence defined by the difference between the terms of the sequence defined by n=k+1 and n=k. Notice that whenever we reach a negative number in this sequence it's partial sum will be zero and the rest of the sequence defined by n=k+1 will be identical to the sequence defined by n=k. Finally if this never happens then the sequence is the same except with each term one more than the previous sequence. Then we're essentially done.[/hide]

Let us define $S_i= \Sigma a_i$
Consider  the number ${D_x= \frac {S_x + \frac{S_x}{x}}{x+1} =\frac{S_x}{x}}$
Since ${\frac{S_x}{x}}$ is an integer $D_x$ is an integer .But since $a_{x+1}$  is the unique integer such that $0 \le a_{x+1} \le x$ and $S_{x+1}$ is divisible by $x+1$
if ${a_{x+1}\not= \frac{S_x}{x}}$ for all x we would  have ${{\frac{S_{x+1}}{x+1}}=\frac{S_x+a_{x+1}}{x+1}} >D_x$ .Therefore ${\frac{S_x}{x}} > x  (\frac{S_x}{x} also satisfies \frac{S_x+r}{x+1} is an integer)$ for all $x$  . But we can choose sufficiently large $x$ such that ${\frac{S_x}{x}} \le x(since a_x <x)$ Hence for a sufficiently large $x$ we would have ${a_{x+1}=
\frac{S_x}{x}}$ Hence ${{\frac{S_x}{x}}=\frac{S_{x+1}}{x+1}} =a_{x+1}$
Now if we proceed by induction we would get  ${{\frac{S_{x+i}}{x+i}}=\frac{S_x}{x}}$ for all $i \ge 0((x+i)^2 \ge S_{x+i})$ and this gives the desired result $a_{x+i}= a_{x+1}$ for all $ i \ge 0$

[hide="Solution"]
Define $S_k=a_{1}+a_{2}+...+a_{k}$. Let $S_k=km_k$, and let $r_k=m_k \mod k+1 \Leftrightarrow m_k=r_k+(k+1)q_k$, with $0 \leq r_k <k+1$. We claim that $a_{k+1}=r_k$. Indeed,

$S_{k+1}=S_k+a_{k+1}=k(r_k+(k+1)q_k)+r_k=(r_k+q_k)(k+1)$

Then $m_{k+1}=r_k+q_k \leq m_{k}$, with equality iff $q_k=0$. By the well-ordering principle, we must eventually have equality; let $t$ be the largest integer such that $m_t=m_{t+1}$. Then $q_t=0 \to m_t=r_t$, and for all $k \ge t$, $m_k=m_t=r_t \to r_k=r_t \to a_k=a_t$.
[/hide]

[hide="Solution"]Let $S_k=\sum_{i=1}^ka_i$. Since $S_k-k^2$ is monotonically decreasing, there exists $k$ such that $S_k\le k^2$; take the least such $k$. It readily follows that $\frac{S_k}{k}\le k$, whence $a_{k+1}=\frac{S_k}{k}$ since $S_{k+1}=S_k+\frac{S_k}{k}=\frac{S_k}{k}(k+1)$ is divisible by $k+1$. Similarly, we may conclude that $a_{k+2}=\frac{S_k}{k}$, $a_{k+3}=\frac{S_k}{k}$, and so on; that is, $a_n=\frac{S_k}{k}$ for all $n>k$. It follows that $a_1$, $a_2$, $a_3$, ... eventually becomes constant, as desired. $\blacksquare$[/hide]

[hide=" Solution"]
Let $a_1 + a_2 + \cdots + a_k = kb_k$ for all $k$. Note that $(k+1)b_{k+1} - kb_k < k \implies b_{k+1}<b_k+1$, so $b_k$ is decreasing (not strictly). Hence, $b_k$ must eventually be constant, so for some $n_0,$ we have that for all $k\geq n_0$, $b_k= b_{n_0}$. Now, note that for any $k\geq n_0,$
\[b_k= b_{k+1} \implies (k+1)(a_1 + a_2 + \cdots + a_k) = k(a_1 + a_2 + \cdots + a_{k+1})  \\ \implies a_{k+1} = b_k = b_{n_0},\]
which is constant. $\blacksquare$ [/hide]

[hide="my solution"]
Note that once $\displaystyle\sum_{i=1}^{k}a_i = km$ where $m\le k$, then we are done as $\displaystyle\sum_{i=1}^{n}a_i=nm$ works for all $n>k$.
Thus, we just need to show that $\displaystyle\sum_{i=1}^{k}a_i\le k^2$ eventually, which is evident as $$\displaystyle\sum_{i=1}^{k}a_i\le n+\dfrac{k(k-1)}{2} \le k^2\implies k^2+k\ge 2n$$ which can be done for big enough $k$.
[/hide]

Define

$$b_i = \frac{a_1 + ... + a_i}{i}$$

Note that $b_i$ is always an integer by the problem statement. Now for all $i$ we have

$$b_{i+1} < \frac{a_1 + ... + a_{i+1}}{i} = b_i + \frac{a_{i+1}}{i} \le b_i + 1$$

so $\{b_i\}$ is nonincreasing. In particular, since $\{b_i\}$ is a sequence of positive integers, it is eventually constant and equal to some $c$ at which point

$$\frac{a_1 + ... + a_{i+1}}{i+1} = \frac{a_1 + ... + a_i}{i}=c\implies a_i = c$$

so $\{a_i\}$ is constant too.

Define $$b_i=\frac{a_1+\dots+a_i}{i}.$$ Now if $b_i\leq i$ for some $i$ we may set $a_j = b_i$ for all $j\geq i$, giving a constant sequence.
It suffices to show that we cannot have $b_i>i$ for all $i$. Define a new sequence $c_i=b_i-i$; we will show that $c_i$ is decreasing when $c_i\geq 0$, proving the problem.
Notice that $$c_{i+1}=b_{i+1}-(i+1)=\left\lceil \frac{ib_i}{i+1} \right\rceil-(i+1)=\left\lceil \frac{ic_i-2i-1}{i+1} \right\rceil,$$ we wish to show $$c_i>\left\lceil \frac{ic_i-2i-1}{i+1} \right\rceil\iff \left\lceil \frac{-c_i-2i-1}{i+1} \right\rceil < 0\iff -c_i-2i-1<-i-1\iff i>-c_i,$$ which is true. $\blacksquare$

Let $x_i=a_1+\dots+a_i$ and $b_i=x_i/i.$ Notice that $$b_i+1=\frac{x_i+i}{i}>\frac{x_i+a_{i+1}}{i+1}=b_{i+1}$$ so $b_i$ and therefore $a_i$ is eventually constant. $\square$

We first claim that $b_i=a_1+a_2+ \cdots + a_i \le i^2$ for sufficiently large $i$.
To prove this, note that $$a_1+(a_2+a_3+ \cdots +a_i) \le a_1+\frac{i(i-1)}{2} \le i^2$$ for sufficiently large $i$.

Using this, if $b_m=mp$ for $p<m$, then $m+1 \mid b_m+p $ and $0 \le m \le p-1$, so $b_{m+1}=(m+1)p$. Thus by induction, we get that $b_m$ is constant for sufficiently large $m$.

Define $b_k=\frac{a_1+a_2+\cdots+a_k}{k}$.

We claim that the sequence $b_i$ eventually becomes constant.
Proof: We have\[b_{k+1}=\frac{a_1+a_2+\cdots+a_{k+1}}{k+1}<\frac{a_1+a_2+\cdots+a_{k}+k}{k}=b_k+1\]Thus, the sequence is non-increasing, which implies it must at some point go constant. $\blacksquare$

Suppose it becomes constant at $c$. Then for all $k\ge N$, $a_1+a_2+\cdots+a_k=ck$. Now, when we add $a_{k+1}$ to the LHS, we add $c$ to the RHS, so $a_{k+1}=c$, which implies $a_i$ stays constant at $c$.

Since $1\le n$, $\frac{n+1}{2}\le n$. Therefore, $a_1+a_2+\ldots+a_n\le n+1+2+\ldots + (n-1) = \frac{n(n+1)}{2} \le n^2$.

Let $a_1+a_2+\ldots+a_n = cn$ for some positive integer $c\le n$. Since $k \mid cn + c(k-n) = ck$, $a_k = c$ for all $k>n$.

Let $s_k$ be the prefix sum. Note that $s_k \leq n + (k-1)k/2,$ which is asymptotically slower than $k^2$, so $s_k\leq k^2$ for some $k$. Now consider what happens if $s_k=mk$ for some $m\leq k$. Now, $s_{k+1}$ must then be $m(k+1)$, since $(m-1)(k+1)=mk-k+m-1<mk$ is smaller than $s_k$ and $(m+1)(k+1)=mk+k+m+1$ is too much of an increase from $s_k$. This means that $a_{k+1}=s_{k+1}-s_k=m.$ We can repeat this argument indefinitely, since of course $m\leq k+1$, $m\leq k+2,$ etc, so $a_i=m$ for all $i\geq k+1$, so we are done.

First note that there is exactly one unique sequence satisfying this property for each $n$.

Let $a_1 + a_2 + \cdots + a_n = cn$. Notice that \[a_1 + a_2 + \cdots a_n  \le n + 1 + 2 + \cdots + (n-1) = \frac{n(n+1)}{2}  \le n^2 ,\]so $c\le n$.

We claim that $a_k = c$ for all $k>n$. Its easy to see that such a sequence works because $a_1 + a_2 + \cdots + a_k = cn + c(k-n) = ck$ and $c\le n < k$ for any $k>n$, so $(a_n)$ is eventually constant.

Define
\[b_k=\frac{a_1+a_2+\dots+a_k}{k}.\]
Trivially we find
\[b_{k+1}=\left \lceil \frac{k}{k+1}\cdot b_k \right \rceil\]
implying that $\{b_k\}$ is nonincreasing; however, it is also bounded below and therefore is eventually constant, which also implies that $\{a_k\}$ is constant. We are done. $\blacksquare$

We claim that if $a_1+a_2+\dots{}+a_k=xk$ for some $x\leq{}k$, after $a_k$, the sequence becomes constant. The proof is trivial by modulos mod $k+1$.

We now claim that if $a_1+a_2+\dots{}+a_k=x_kk$ for some $x_k>k$, then $\frac{a_1+a_2+\dots{}+a_{k+1}}{k+1}=x_{k+1}<x_k$. Since $x_k>k$, by modulos, we clearly have that $a_{k+1}<x$, which implies that $x_{k+1}<x_k$, proving the claim.

Since $x_i$ keeps decreasing as $i$ keeps increasing, eventually we will have that $x_i\leq{}i$. By the first claim, the sequence will eventually become constant, and we are done.

Let $f(k) = \frac{1}{k}\sum_{i = 1}^ka_i$ for each integer $k > 0$. Note that $a_{k+1} = k + 1 - kf(k) + (k+1)\lfloor kf(k)/(k+1)\rfloor$. Then,
\[f(k+1)\le f(k)\iff \frac{k}{k+1}f(k) + \frac{a_{k+1}}{k+1}\le f(k)\iff f(k)\ge a_{k+1}\]
\[ \iff f(k)\ge k+1 - kf(k) + (k+1)\lfloor kf(k)/(k+1)\rfloor\iff f(k)\ge 1 + \lfloor kf(k)/(k+1)\rfloor,\]
which clearly holds for $k$ sufficiently large. Thus, $f$ is nonincreasing for all $k$ sufficiently large, meaning $f$ is eventually constant (keeping in mind that its codomain is $\mathbb{N}$). It follows that $(a_k)_{k\ge 1}$ is also eventually constant, as desired.
[hide = .]i kind of overcomplicated this in the middle oops[/hide]

I claim that there must exist some k such that a(1) + .... + a(k) is less than k^2 regardless of what you start with. To prove this, assume for the maximization that for each a(i) = i-1 for i≥2. Then this becomes a(1) + (1+...+(k-1)) = k(k-1)/2 + a(1). If you increase k enough then this will be true.

Now define the first k for which this value is true has a(1) + .... + a(k) = ck, for c some positive integer. Then we show that all a(i) afterwards must have a(i) = c. This now becomes an induction problem. For the inductive step, we assume that a(1) + ..... + a(n) = cn for n ≥ k. Then by taking mod n+1, this becomes -c mod n+1. c<n+1< n+1+c, so a(n+1) must be c.

Thus after this k the sequence becomes constant with all terms = c.

Pretty funny problem.

[b][color=#f00]Claim.[/b][/color] If $a_k = rk \leq k^2$, then $a_{k+1} = a_{k+2} = \cdots = r$.

[i]Proof.[/i] Note that $r \leq k$, and $r$ also creates multiples of $i > k$ at every juncture. $\blacksquare$

On the other hand, we must have $a_k < k^2$ at some point, because $$a_k < n + 1 + 2 + \cdots + (k-2) = n+\frac{k(k-1)}2.$$

nice :-D Let $S_i=a_1+a_2+\cdots a_n$
[color=blue][b]Claim.[/color] if $m\mid S_m=m\cdot k$ and $0\leq k\leq m$ for some $k$ we are done
[color=red]Proof:[/color]
This is true since in the following steps we may choose $k$ as $m+i\mid S_{m+i}=S_m+ik=mk+ik=k(m+i)$

So note that this would be impossible only if $S_m=mk>m\cdot m=m^2$ for every $m$. Now
$$S_m=a_1+a_2+a_3+\cdots a_m\leq n+1+2+\cdots (m-1)=n+\frac{m(m-1)}{2}$$
But $S_m\leq n+\frac{m(m-1)}{2}\leq m^2$ for enough large $m$

Note that for large $k$, we have $a_1 + a_2 + \dots + a_k \le a_1 + 1 + 2 + \dots + (k-1) \le a_1 + \frac{k(k-1)}{2} \le k^2$. Let $s = \frac{a_1 + a_2 + \dots + a_k}{k}$, then $s \le k$. Then we get $a_{k+1} = a_{k+2} = \dots = s$, so we're done. $\blacksquare$


For those who happen to like game music, what are your favorites? I'm presently on a FF/Xenogears/Chrono Cross downloading spree, that's why I'm asking. And I feel that the Chrono Cross soundtrack is the best of all...though the main theme for FFX isn't too bad.

some of the halflife tracks are pretty good. but the deus ex soundtrack, in my opinion, is by far the greatest game music i have ever heard in my short life.

Ganja and really fast Sitar music floats my boat..

Final Fantasy 7 and Chrono Trigger have the best!

FF7 has the best music of the FF's and I'm currently split between Chrono Trigger and Chrono Cross, but I think Chrono Cross is better. =)

Personally my favorite soundtrack relating to RPGs would have to be from Final Fantasy the Movie. All the pieces are amazingly orchestrated, blah blah blah. Chrono Cross has a pretty cool track too.

How interesting.  I don't particularly like game music.  I listen to *real* music...

jk.  Game music is real music, it's just not usually the best music.  But then again, I've never played any of the games you mentioned.

Where "real" is defined as music created before the year 1900. :)

Which FF7 tracks besides Aeris' theme and the main theme?

Do any of you have a favorite piece? Right now I'm torn between Chrono Trigger's To Far Away Times and FFX's main theme.

I think the music is not that good to listen to when you are doing work , the music is good when you want to relax [hide=tho]though[/hide].

I'm biased since I love this game but Breath of the Wild has good music [s]which can bring nostalgia if your a long-time fan[/s]. Most of it is good for relaxing, but there are a lot of exciting tracks for when you need them.

s a n s
[url]https://www.youtube.com/watch?v=ECCwqZRJeSE[/url]

[hide=@Eric2009 #11:][quote name="Eric2009" url="/community/p18264048"]
terraria and undertale hits me
[/quote][/hide]

Yes terraria
but also

may I introduce you all to the HOI4 soundtrack
very epic
one of my favorites is probably Hearts of Men or Krakow, Luftwaffe Strikes Again is nice too

was anyone a fan of the Halo theme before it was a meme?

Why would you bump a thread older than most people on Aops.

I'm questioning whether posting is allowed despite the insane bump
favorite music: Pokémon, Undertale, Minecraft, a bunch of random songs from various games, etc

oh and to the person who asked "what FF7 music," obviously the standard battle theme

[quote=ilovepizza2020]Oldest unlocked FF thread![/quote]

Wow. Rare appearance of ilovepizza2020 in FF.

Also this thread was made before i was even born what

[quote=SamuraiA][quote name="Galinagames" url="/community/p18820547"]
UT/DR music... I listen to it absolutely whenever I can. Original, remix, doesn't matter, I just soak up every single song in existence. There's a kind of fine balance between it distracting me and it helping me work. [hide]I should take a break some time.[/hide]
Terraria music is really good too, though hard to hum along with.
Minecraft music actually makes me cry.
Cuphead music, though, is also so good.
[/quote]

yessssssssssssssssssssssssssssssssssssssssssssssssssssss
honestly though Pokémon music is amazing too
there are tons of underrated indie game OSTs[/quote]

yeeesssssssssss- i can agree with pokemon, i have to listen to some more of that-

K/DA :P

[s]Totally jk[/s]

[quote=pezzeepenguinstalker]I would be around 6 months old when this thread was made.[/quote]

I wouldn't even be born...

game music you say...
[url = hehe ]https://www.youtube.com/watch?v=EhgDibw7vB4[/url]

is homestuck a game? homestuck is a game. the alterniabound soundtrack is amazing. toby fox wrote a lot of it.

most Nintendo music is pretty sweet

[quote=Galinagames][quote=Jianning]I was -5 years old[/quote]

same... this place is ancient[/quote]

+1

last time  i bumped a 110 yr old thread i got post banned by the sheriff

[quote name="SamuraiA" url="/community/p20462400"]
Kirby final bosses are always top tier, both in design and in music. Moonstruck Blossom and PROGRAM are stellar (pun sort of intended)
[/quote]

Update to this post: Two Planets Approach the Roche Limit is amazing

also Splatoon 3 music
specifically Till Depths do us Part and alterna mission 2

a fellow till depth do us part enjoyer, I see

"RT-2PM2 Topol-M Silo-based intercontinental ballistic missile strikes on the long streak" HIII


If $ x, y$ and $ z$ are positive real numbers such that $ x\plus{}y$ $ \ge{z}$ then $ \frac{x}{1\plus{}x}\plus{}\frac{y}{1\plus{}y}$ is always greater than or equal to
$ a) \frac{1}{1\plus{}z}$

$ b) \frac{z}{1\plus{}z}$

$ c) \frac{x}{1\plus{}z}$

$ d) \frac{y}{1\plus{}z}$

$ e)$ $ None$ $ of$ $ these$

Please give reasons...
Thank you.

well, it's not b; let x=y=2;z=4. it's also not c or d, since the truth of one implies the truth of the other(symmetry), so either they're both correct or neither is, but if you're only allowed to pick one then they can't both be correct, so theyre both wrong. so it's either a or e. and it's not (a) since letting x, y, and z all be very tiny numbers(approaching 0), then the expression goes to 0, while 1/(1+z) goes to 1. therefore the answer  is e.

[quote="mathking123"]well, it's not b; let x=y=2;z=4.[/quote]

That's

$ \dfrac{2}{3} \plus{} \frac{2}{3} > \frac {4}{5}$...which is true

If $ x\equal{}y\equal{}z$ and $ x,y,z$ is positive real number, how can $ x\plus{}y \ge z$

[quote="doabli"]If $ x \equal{} y \equal{} z$ and $ x,y,z$ is positive real number, how can $ x \plus{} y \ge z$[/quote]

Are you saying $ x\plus{}y\equal{}2z\not\geq z$??? :huh:

[quote="oley"]If x = y = z, then none of (a, b, c, d) holds true, therefore it's e.[/quote]

No, let $ x\equal{}y\equal{}z\equal{}a \longrightarrow \frac{a}{1\plus{}a}\plus{}\frac{a}{1\plus{}a} \ge \frac{a}{1\plus{}a}$ which is true

Here's a non-calculus solution to show that;
$ \frac{x}{1\plus{}x} \plus{}\frac{y}{1\plus{}y}\ge \frac{z}{1\plus{}z}$

For a fixed $ x$ let $ x' \equal{} x\plus{}n$ where $ n>0 \Rightarrow \frac{x'}{1\plus{}x'}\minus{}\frac{x}{1\plus{}x} \equal{} \frac{n}{(1\plus{}x)(1\plus{}x\plus{}n)}>0$
Therefore $ \frac{x}{1\plus{}x}$ is a strictly increasing function of $ x$ and if the inequality holds for $ x\plus{}y\equal{}z$ then it also holds for $ x\plus{}y>z$

So we need to show that
$ \frac{x}{1\plus{}x}\plus{}\frac{y}{1\plus{}y} \ge \frac{x\plus{}y}{1\plus{}x\plus{}y}$
$ \frac{z\plus{}xy\plus{}xy}{1\plus{}z\plus{}xy} \ge \frac{z}{1\plus{}z}$ which we saw before was an increasing function so we are done

[quote="doabli"]If $ x \equal{} y \equal{} z$ and $ x,y,z$ is positive real number, how can $ x \plus{} y \ge z$[/quote]

x = 2, y = 2, z = 2.
x+y=4>2=z - what's wrong with that? :)

oh... I see what's wrong... (b) is still true under that.

[quote="Kyoshiro"][quote="Darmani"]The infimum is where $ x \equal{} z$, $ y \equal{} 0$. That yields the expression $ \frac {z}{1 \plus{} z}$. So $ (b)$.[/quote]
$ x,y,z \neq 0$[/quote]

You might want to look up the word "infimum."

[quote="ocha"][quote="mathking123"]well, it's not b; let x=y=2;z=4.[/quote]

That's

$ \dfrac{2}{3} \plus{} \frac {2}{3} > \frac {4}{5}$...which is true[/quote]

oops :blush:

[quote="doabli"]If $ x \equal{} y \equal{} z$ and $ x,y,z$ is positive real number, how can $ x \plus{} y \ge z$[/quote]

o_O;;; O_o;;;  :wallbash:  :wallbash:  :wallbash:
That has GOT to be (and better be) the craziest post I've seen in this website...


The game of Ibish is played in rounds. In the first round, you
earn 0, 10 or 11 points; in the second round, you earn 0, 10, 11 or 12 points; in the third round, you earn 0, 10, 11, 12 or 13 points, and so on, including the next greatest integer in the possible point values. What is the fewest number of rounds
after which your total score can have a 9 in the units digit?

For the nth (when 0<n<10) round, we can add 0, 1, 2, ...n to our units sum. To maximize the pace of arriving at 9, we take, in the orunds, a units digit of 1, 2, 3, and now another 3 to reach 9. This is $ \boxed{4}$ rounds.


geometry
angle bisector
geometry unsolved

In triangle $ABC$, $\angle B=3\angle A$. Let $M,N$ be on side $CA$ such that $\angle CBM=\angle MBN=\angle NBA$. Let $X$ be on $BC$, $L$ be the intersection of $AM$ and $BN$, and $K$ the intersection of $NX$ and $BM$. Show that $KL\parallel AC$.

[quote="Jumbler"]...$L$ be the intersection of $AM$ and $BN$.[/quote]

This should read $AX$ and $BN$. See the attached diagram for notation.

$\angle NAB=\angle NBA=\alpha\implies AN=BN=a$

1. $\angle CNB=2\alpha=\angle CBN\implies CB=CN$. Extend $CB$ to $T$ such that $BT=a$. Then $CT=CA$. Now $CB=CN\land CT=CA\implies BN\parallel TA\implies{XL\over LA}={XB\over BT}={XB\over a}$

2. $BK$ is an angle bisector in $\triangle XBN$, hence ${XK\over KN}={XB\over BN}={XB\over a}$

Thus ${XL\over LA}={XK\over KN}\implies KL\parallel NA\implies KL\parallel AC$

By Menelaus theorem: $\frac{(CM)(NK)(XB)}{(MN)(KX)(BC)}=\frac{(CN)(AL)(XB)}{(NA)(LX)(BC)}$

By bisector theorem: $\frac{CM}{MN}=\frac{BC}{BN}=\frac{CN}{NA}$

Then: $\frac{NK}{KX}=\frac{AL}{LX}$, so $\boxed{KL//AC}$  $\mathbb{QED}$


Stromatolites aka the antithesis of incompetence


can you give my the name of this théoreme , and the demonstration ?

\[ \sum \frac{a_{i}}{b_{1}}\geq \frac{(\sum a_{i})^{2}}{\sum b_{i}}\]

The correct form is $ \sum \frac {a_i^2} {b_i} \geq \frac {(\sum a_i)^2} {\sum b_i}$, for $ b_i > 0$.
Some people call it "Titu" (Andreescu) form of Cauchy-Schwartz.


prove that :
  $\sum \frac{\sqrt{y+z}}{x}\geq \frac{4(x+y+z)}{\sqrt{(x+y)(y+z)(z+x)}}$
where $x,y,z>0$

As I know , this is Darij's problem . It's posted long time ago .
  To solve this problem , you can use AM-GM's ineq and a very useful ineq :
 $9(a+b)(b+c)(c+a) \geq 8(a+b+c)(ab+ac+bc)$

Cool, my inequalities start coming back...

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

;)

  Darij


$ f$ is a real valued function on the reals satisfying (1) $ f(0) \equal{} \frac{1}{2}$, (2) for some real $ a$ we have $ f(x\plus{}y) \equal{} f(x) f(a\minus{}y) \plus{} f(y) f(a\minus{}x)$ for all $ x, y$. Prove that $ f$ is constant.

Consider a function satisfy .
For $ x\equal{}a,y\equal{}0$ we have $ f(a)\equal{}\frac{1}{2}$
For $ y\equal{}0$ then $ f(x)\equal{}f(a\minus{}x)$
So $ f(x\plus{}y)\equal{}2f(x)f(y)$
So $ f(x\plus{}y)\equal{}f(a\minus{}x\plus{}y)$
For $ x\equal{}y$ then $ f(2x)\equal{}f(a)\equal{}\frac{1}{2}$
It mean that $ f(x)\equiv \frac{1}{2}$


integration inequalities algebra polynomial trigonometry calculus symmetry

Lets define $ I_n$ as
$ I_n(r,z) \equal{} rz\int_z^r\frac {T_n(\frac {p}{z})T_n(\frac {p}{r})}{p\sqrt {(r^2 \minus{} p^2)(p^2 \minus{} z^2)}}\,dp$

Where $ T_n(x) \equal{} \cos(n \arccos(x))$, for $ \minus{} 1 < x < 1$ and
$ T_n(x) \equal{} \cosh(n\, arccosh(x))$, otherwise
$ T_n(x)$ is the Chebyshev polynomial of the first kind.

I know that $ I_0 \equal{} I_1 \equal{} \frac {\pi}{2}$. For $ I_0$, check [url]http://www.artofproblemsolving.com/Forum/viewtopic.php?t=210059[/url]. $ I_1$ is simpler and uses the same formula.

Prove that $ I_{n \plus{} 1} \equal{} I_{n \minus{} 1}$

ps: I have some 33 pages of failed attempts at solving this, but I might be overlooking something obvious!! (wouldn't be the first time... :( )

[quote="misan"][quote="pocaracas"]
Prove that $ I_{n \plus{} 1} \equal{} I_{n \minus{} 1}$
[/quote]

it is fairly easy, took me about half a page. :) but since you asserted i must have done something wrong previously to get at the right result, i don't think i want to bother typing it all again.[/quote]
Corrected! You're no longer wrong.  :D  Just a bit twisted. :wink:
Help, please! :blush:

we have

$ \frac { I_{n \plus{} 1}(r,z) }{ rz} \; \equal{} \; \int_z^r\frac {T_{n \plus{} 1}(\frac {p}{z})\cdot T_{n \plus{} 1}(\frac {p}{r})}{p\sqrt {(r^2 \minus{} p^2)(p^2 \minus{} z^2)}}\;\;\textbf dp \qquad \ldots \qquad \ldots (1)$

$ ( \;\; for \quad 0 < z < r < 1\;\; )$

looking at $ (i)$ and $ (ii)$ below, remember for $ (i)$ , you  need to use $ T_n(x) \equal{} \cos(n \cos^{ \minus{} 1} x)$ and for $ (ii)$, use  $ T_n(x) \equal{} \cosh(n \cosh^{ \minus{} 1} x)$

$ (i) \quad 0 < x < 1$
$ (ii) \quad 1\le x < \infty$

since we are doing  $ \int_z^r \ldots \;\textbf dp$,  it means $ p\ge z$, and remembering $ \cosh(x \plus{} y) \equal{} \cosh x \cosh y \plus{} \sinh x \sinh y$

$ T_{n \plus{} 1}\left(\frac {p}{z}\right) \equal{} \cosh\left( (n \plus{} 1) \cosh^{ \minus{} 1} \frac {p}{z} \right)$

$ \equal{} \frac {p}{z} \underbrace{\cosh\left( n \cosh^{ \minus{} 1} \frac {p}{z} \right) }_{call\quad it \quad T_n\left(\frac {p}{z}\right) }\; \plus{} \;\underbrace {\frac {\sqrt {p^2 \minus{} z^2}}{z} }_{\sinh \left( \cosh^{ \minus{} 1} \frac {p}{z} \right)} \; \underbrace{\sinh \left( n \cosh^{ \minus{} 1} \frac {p}{z} \right)}_{call\quad it \quad V_n\left(\frac {p}{z}\right) }$

similarly, because $ p\le r$, using $ \cos(x \plus{} y) \equal{} \cos x \cos y \minus{} \sin x \sin y$

$ T_{n \plus{} 1}\left(\frac {p}{r}\right) \equal{} \cos\left( (n \plus{} 1) \cos^{ \minus{} 1} \frac {p}{r} \right)$

$ \equal{} \frac {p}{r} \underbrace{\cos\left( n \cos^{ \minus{} 1} \frac {p}{r} \right)}_{call\quad it \quad T'_n\left(\frac {p}{r}\right) } \; \minus{} \; \underbrace{\frac {\sqrt {r^2 \minus{} p^2}}{r} }_{\sin \left( \cos^{ \minus{} 1} \frac {p}{r} \right) } \; \underbrace{\sin \left( n \cos^{ \minus{} 1} \frac {p}{r} \right)}_{call\quad it \quad V'_n\left(\frac {p}{r}\right) }$

put these in $ (1)$ to get

$ \frac { I_{n \plus{} 1}(r,z) }{ rz} \; \equal{} \; \int_z^r\frac {\left( \frac {p}{z} T_n\left(\frac {p}{z}\right) \plus{} \frac {\sqrt {p^2 \minus{} z^2}}{z} V_n\left(\frac {p}{z}\right) \right)\cdot \left( \frac {p}{r} T'_n\left(\frac {p}{r}\right) \minus{} \frac {\sqrt {r^2 \minus{} p^2}}{r} V'_n\left(\frac {p}{r}\right) \right) }{p\sqrt {(r^2 \minus{} p^2)(p^2 \minus{} z^2)}}\;\;\textbf dp$

similarly, we get

$ \frac { I_{n \minus{} 1}(r,z) }{ rz} \; \equal{} \; \int_z^r\frac {\left( \frac {p}{z} T_n\left(\frac {p}{z}\right) \minus{} \frac {\sqrt {p^2 \minus{} z^2}}{z} V_n\left(\frac {p}{z}\right) \right)\cdot \left( \frac {p}{r} T'_n\left(\frac {p}{r}\right) \plus{} \frac {\sqrt {r^2 \minus{} p^2}}{r} V'_n\left(\frac {p}{r}\right) \right) }{p\sqrt {(r^2 \minus{} p^2)(p^2 \minus{} z^2)}}\;\;\textbf dp$

subtracting,

$ \frac { I_{n \plus{} 1}(r,z) }{ rz} \; \minus{} \; \frac { I_{n \minus{} 1}(r,z) }{ rz} \; \equal{} \; \frac {2}{ rz} \int_z^r \frac { \minus{} p \sqrt {r^2 \minus{} p^2} T_n\left(\frac {p}{z}\right) V'_n\left(\frac {p}{r}\right) \plus{} p \sqrt {p^2 \minus{} z^2} T'_n\left(\frac {p}{r}\right) V_n\left(\frac {p}{z}\right)}{p \sqrt {(r^2 \minus{} p^2)(p^2 \minus{} z^2)} }\;\;\textbf dp$

$ \Rightarrow I_{n \plus{} 1}(r,z) \; \minus{} \; I_{n \minus{} 1}(r,z) \; \equal{} \;2 \int_z^r \left( \frac { \minus{} T_n\left(\frac {p}{z}\right) V'_n\left(\frac {p}{r}\right) } {\sqrt {p^2 \minus{} z^2}} \plus{} \frac { T'_n\left(\frac {p}{r}\right) V_n\left(\frac {p}{z}\right) } {\sqrt {r^2 \minus{} p^2}} \right) \;\textbf dp\qquad \ldots \qquad \ldots (2)$

i think i have done most of it for you ... can you do the rest ?  you just need to show

$ \int_z^r \frac {T_n\left(\frac {p}{z}\right) V'_n\left(\frac {p}{r}\right) } {\sqrt {p^2 \minus{} z^2}} \;\textbf dp \equal{} \int_z^r \frac { T'_n\left(\frac {p}{r}\right) V_n\left(\frac {p}{z}\right) } {\sqrt {r^2 \minus{} p^2}} \;\textbf dp$

i.e.

$ \int_z^r \frac {\cosh\left( n \cosh^{ \minus{} 1} \frac {p}{z} \right) \cdot \sin\left( n \cos^{ \minus{} 1} \frac {p}{r} \right) } {\sqrt {p^2 \minus{} z^2}} \;\textbf dp \equal{} \int_z^r \frac {\sinh\left( n \cosh^{ \minus{} 1} \frac {p}{z} \right) \cdot \cos\left( n \cos^{ \minus{} 1} \frac {p}{r} \right) } {\sqrt {r^2 \minus{} p^2}} \;\textbf dp$

once you show they are   [b]same[/b] ,  it will mean that the $ RHS$ of $ (2)$ is $ 0$, and  hence $ I_{n \plus{} 1}(r,z) \; \equal{} \; I_{n \minus{} 1}(r,z),$ which is what you wanted to show.

it is fairly easy, but  if you can't show it, i will post it later.  :|

[ hint: think about [i]differentiating[/i] the integrals with respect to some variable... ]

You want to know something funny?
I arrived at your equation (2) last Friday and got stuck exactly on the step that you say is "fairly easy".  :(
I've used your suggestion for differentiating with respect to something... I tried to 'n', but I don't think that's the way... I'm stuck again and I don't really understand why differentiating will help?

This what I got after differentiating with respect to 'n':
$ \int_z^r\sinh[n \cosh^{\minus{}1}(\frac{p}{z})]\sin[n \arccos(\frac{p}{r})]\left[\frac{\cosh^{\minus{}1}(\frac{p}{z})}{\sqrt{p^2\minus{}z^2}}\plus{}\frac{\arccos(\frac{p}{r})}{\sqrt{r^2\minus{}p^2}}\right]\,dp\equal{}$

$ \equal{}\int_z^r\cosh[n \cosh^{\minus{}1}(\frac{p}{z})]\cos[n \arccos(\frac{p}{r})]\left[\frac{\cosh^{\minus{}1}(\frac{p}{z})}{\sqrt{r^2\minus{}p^2}}\minus{}\frac{\arccos(\frac{p}{r})}{\sqrt{p^2\minus{}z^2}}\right]\,dp$

There's some kind of symmetry here, but I don't know what I can do next... help! :blush:

I think I got it. Derivation by parts!
I want to prove that
$ \int_z^r\frac {\cosh[n \cosh^{ \minus{} 1}(\frac {p}{z})]\sin[n \arccos(\frac {p}{r})]}{\sqrt {p^2 \minus{} z^2}}\,dp \equal{} \int_z^r\frac {\sinh[n \cosh^{ \minus{} 1}(\frac {p}{z})]\cos[n \arccos(\frac {p}{r})]}{\sqrt {r^2 \minus{} p^2}}\,dp$

Given that:
$ \frac{d}{dp}\sinh[n \cosh^{\minus{}1}(\frac{p}{z})] \equal{} n\frac{\cosh[n \cosh^{ \minus{} 1}(\frac {p}{z})]}{\sqrt {p^2 \minus{} z^2}}$
and
$ \frac{d}{dp}\sin[n \arccos(\frac{p}{r})]\equal{}\minus{}\frac{n}{\sqrt{r^2\minus{}p^2}}\cos[n \arccos(\frac{p}{r})]$
we can solve the LHS of the above equality using integration by parts:
$ \int_z^r\frac {\cosh[n \cosh^{ \minus{} 1}(\frac {p}{z})]\sin[n \arccos(\frac {p}{r})]}{\sqrt {p^2 \minus{} z^2}}\,dp \equal{} \left[\frac{1}{n}\sinh[n\cosh^{\minus{}1}(\frac{p}{z})]\sin[n \arccos(\frac{p}{r})]\right]_z^r\plus{}\int_z^r\frac{\sinh[n \cosh^{ \minus{} 1}(\frac {p}{z})]\cos[n \arccos(\frac {p}{r})]}{\sqrt {r^2 \minus{} p^2}}\,dp$
Making the substitutions:
$ \sinh[n\cosh^{\minus{}1}(\frac{r}{z})]\sin[n \arccos(\frac{r}{r})]\equal{}something*\sin[n\arccos(1)]\equal{}0$

$ \sinh[n\cosh^{\minus{}1}(\frac{z}{z})]\sin[n \arccos(\frac{z}{r})]\equal{}\sinh[n\cosh^{\minus{}1}(1)]*something\equal{}0$
and the remaining integral is the right hand side of the first equality!

And that's it!
Thank you very much for your suggestions misan.
I couldn't have done it without you!  :lol:


modular arithmetic
number theory unsolved
number theory

[quote="Tomekk"]Find all primes $ p$ and $ q$ such that $ pq$ divides $ 2^p \plus{} 2^q$.[/quote]

if $ p \equal{} q$ then it's easy to see that $ p \equal{} q \equal{} 2$ is a solution . and if $ p$ or $ q$ is equal to $ 2$ then we get $ 2p \mid 4 \plus{} 2^p$ or $ p \mid 2^{p \minus{} 1} \plus{} 2$ and Using Fermat little Theorem we get $ p\mid 3$ and so $ p \equal{} 3$ Thus $ (2,3)$ or $ (3,2)$ is a solution Now Assume that $ p$ and $ q$ are odd primes and $ p\neq q$ Hence $ pq \mid 2^p \plus{} 2^q \Rightarrow p\mid 2^p \plus{} 2^q$ and $ q\mid 2^p \plus{} 2^q$ and From Fermat little Theorem we have $ p \mid 2^p \minus{} 2$ and $ p\mid 2^p \plus{} 2^q$ Thus $ p \mid 2^q \plus{} 2$ or equivalently $ p\mid 2^{q \minus{} 1} \plus{} 1$ and Similarly we get $ q \mid 2^{p \minus{} 1} \plus{} 1$. Let $ k_1$ be the order of $ 2$ $ \pmod p$ and $ k_2$ The order of $ 2$ $ \pmod q$ Hence it's easy to Prove that  $ k_1 \not | q \minus{} 1$ and $ k_1 \mid 2(q \minus{} 1)$ so $ v_2(k_1) \equal{} v_2(q \minus{} 1) \plus{} 1$ and since $ k_1 \mid p \minus{} 1$ Then $ v_2(k_1) \le v_2(p \minus{} 1)$ or $ v_2(q \minus{} 1) \plus{} 1 \le v_2(p \minus{} 1)$ . On the other hand we Prove in a similar way that $ v_2(k_2) \equal{} v_2(p \minus{} 1) \plus{} 1$ since $ k_2 \not | p \minus{} 1$ and $ k_2 \mid 2(p \minus{} 1)$ and because $ k_2 \mid q \minus{} 1$ we get $ v_2(p \minus{} 1) \plus{} 1 \le v_2(q \minus{} 1)$ which is absurd and hence $ p \equal{} q \equal{} 2$ Conclusion The solution are $ \{(2,2);(2,3);(3,2)\}$  :P

[quote="phuonghong"]Dear Abdek, could you give me some information about "what is $ v_2(k_1)$ ?" I really haven't seen it before . Thank you so much.[/quote]
$ v_p(a) \equal{} d$  iff  $ p^d \parallel{} a$
and $ p^d \parallel{} a$ iff $ p^d | a$ but $ p^{d\plus{}1}$ not divides $ a$

[quote="Tomekk"]Find all primes $ p$ and $ q$ such that $ pq$ divides $ 2^p + 2^q$.[/quote]
I will note $ o_p(x)$ as order of $ x$ mod $ p$.

Assume that $ p$ and $ q$ are odd. Write $ p - 1 = 2^ln$, $ q - 1 = 2^km$, where $ n$ and $ m$ are odd positive integers. Because $ pq|2^p + 2^q$, using Fermat’s Little Theorem, we obtain $ 0\equiv 2^p + 2^q\equiv 2^p + 2 \pmod q$. It follows $ 2^{p - 1}\equiv - 1 \pmod q$. Denote $ x = 2^n$, we have $ x{}^{2{}^l}\equiv - 1 \pmod q$, hence $ o_q(x) = 2^{l + 1}$ (since $ x{}^{2{}^{l + 1}}\equiv 1 \pmod q$ and $ x{}^2{}^l\not\equiv 1\pmod q$). It follows $ 2^{l + 1} = o_q(x) | q - 1 = 2^km$, i.e. $ l + 1 \leq k$.
In similar way we can prove that $ k + 1\leq l$ and we get $ l \leq k - 1 \leq l - 2$, a contradiction. Therefore, it is necessary to have $ p = 2$ or $ q = 2$. If, for example, $ q = 2$, then $ p|2^p + 2^q = 2^p + 4$, $ 0 \equiv 2^p + 4 \equiv 6 \pmod p$, and we get $ p = 2$ or $ 3$

So solution are $ (2,2);(2,3);(3,2)$