linear algebra
matrix
quadratics
calculus
derivative
combinatorics proposed
combinatorics

Consider a matrix whose entries are integers. Adding a same integer to all entries on a same row, or on a same column, is called an [i]operation[/i]. It is given that, for infinitely many positive integers $ n,$ one can obtain, through a finite number of operations, a matrix having all entries divisible by $ n.$

Prove that, through a finite number of operations, one can obtain the null matrix.

[i]Marius Cavachi[/i]

Here's something I think works:

Let $ a_{ij}$ denote the entry of our matrix in row $ i$ and column $ j$.  Note that for any two rows $ (i, k)$ and  any two columns $ (j, l)$, the expression $ a_{ij}\plus{}a_{kl} \minus{} a_{il} \minus{} a_{kj}$ is left unchanged by any operation.  On the other hand, if all the entries are divisible by $ n$, this expression must also be divisible by $ n$.  It follows that for every pair of rows and columns this expression is in our original matrix already divisible by infinitely many $ n$...in other words, it must always be equal to $ 0$.

Applying this observation with $ k$ and $ l$ equal to $ 1$, we see that for every $ i>1$ and $ j>1$ we must have
\[ a_{ij}\equal{}a_{i1}\plus{}a_{1j}\minus{}a_{11} : \equal{}f(i)\plus{}g(j),\]
where $ f(i)$ is defined to equal $ a_{i1}\minus{}a_{11}$ and $ g(j)$ is defined to equal $ a_{1j}$.  By inspection, we see that this relation also holds when either $ i$ or $ j$ is equal to $ 1$.

We can therefore add $ \minus{}f(i)$ to each row and $ \minus{}g(j)$ to each column to obtain the null matrix.

Assume that after a finite number of operation, row i is added by r_i and column j is added by r_j, such that all entries are divisible by n. Consider everything in modulo n. Take note at the entries a_1,1, a_i,1, a_1,j, a_i,j. We have a_1,1+c_1+r_1=a_i,1+c_i+r_1=a_1,j+c_1+r_j=a_i,j+c_i+r_j in modulo n. From this, we get a_i,j=a_1,1-a_i,1-a_1,j mod n. Since this holds for infinitely many modulo, so the equation must hold. The conclusion follows easily.

As an interesting sidenote, suppose we were to try and apply the same argument to a three-dimensional array of integers, where the legal operations are adding an integer to all the entries along any hyperplanes where one of the variables is constant.  The analogue to the identity above is
\[ a_{i_1, j_1, k_1}\minus{}a_{i_2, j_1, k_1}\minus{}a_{i_1, j_2, k_1}\minus{}a_{i_1, j_1, k_2}\plus{}a_{i_2, j_2, k_1}\plus{}a_{i_2, j_1, k_2}\plus{}a_{i_1, j_2, k_2}\minus{}a_{i_2,  j_2, k_2}\equal{}0,\]
but this is no longer enough to establish the relation $ a_{i,j,k}\equal{}f(i)\plus{}g(j)\plus{}h(k)$ -- the entries could satisfy a quadratic relationship instead of a linear one (e.g. $ a_{i,j,k}\equal{}(i\plus{}j)^2\plus{}2k^2\minus{}3(i\plus{}k)^2$ ).  In a sense this is because by moving up a dimension we're looking at a discrete analogue of the third derivative instead of the second derivative, and quadratic forms have third derivative equal to zero.   So the arguments given above break down for this new problem.

Does the problem statement still hold in $ 3$ (or $ m$) dimensions?

Rather than

$ a_{i_1, j_1, k_1} \minus{} a_{i_2, j_1, k_1} \minus{} a_{i_1, j_2, k_1} \minus{} a_{i_1, j_1, k_2} \plus{} a_{i_2, j_2, k_1} \plus{} a_{i_2, j_1, k_2} \plus{} a_{i_1, j_2, k_2} \minus{} a_{i_2, j_2, k_2} \equal{} 0$,

you should use the stronger identities

$ a_{i, j_1, k_1} \minus{} a_{i, j_2, k_1} \minus{} a_{i, j_1, k_2} \plus{} a_{i, j_2, k_2} \equal{} 0$ for all $ i$, $ j_1$, $ j_2$, $ k_1$, $ k_2$,
$ a_{i_1, j, k_1} \minus{} a_{i_2, j, k_1} \minus{} a_{i_1, j, k_2} \plus{} a_{i_2, j, k_2} \equal{} 0$ for all $ i_1$, $ i_2$, $ j$, $ k_1$, $ k_2$,
$ a_{i_1, j_1, k} \minus{} a_{i_2, j_1, k} \minus{} a_{i_1, j_2, k} \plus{} a_{i_2, j_2, k} \equal{} 0$ for all $ i_1$, $ i_2$, $ j_1$, $ j_2$, $ k$.

These together are equivalent to saying that our three-dimensional array is given by a $ f\left(i\right)\plus{}g\left(j\right)\plus{}h\left(k\right)$ formula, so we are clearly done in three dimensions. Similarly in $ m$ dimensions.

  darij


modular arithmetic
number theory unsolved
number theory

$ p\in\mathbb{P},ord_{p}a=ord_{p^{\alpha}a}$ $ \implies$

Can we say anything about $ \alpha$  ?

What is \[ ord_{p^{\alpha}}a\]. I think you note minimal $ m$, suth that $ a^m\equal{}1\mod p^{\alpha}$.
Then usualy $ \alpha \equal{}1$, raretily $ \alpha\equal{}2$. I don't know suth a and $ m<p$, suth that $ p^3|a^m\minus{}1$.

yes $ ord_{p^{\alpha}}a$ is minimal $ m$,such that $ a^{m}\equiv 1\pmod{p^{\alpha}}$

Unknown $ 1<a<p,m<p$, suth that $ p^3|a^m\minus{}1$. But we can solve $ a^m\equal{}1\plus{}pN, \ p\not |m$ in p-adic $ Z_p$ and can find $ a, m<p$ suth that $ p^n|a^m\minus{}1$ for any n.


inequalities function logarithms calculus derivative

Να αποδειχθεί ότι για όλους τους πραγματικούς $ 0<x_1,.....,x_n\leq{\dfrac{1}{2}}$

$ {(\dfrac{n}{x_1+..+x_n}-1)}^n\leq{\displaystyle\prod_{i=1}^n(\dfrac{1}{x_i}-1)}$

Just Jensen for the function $ f(x)\equal{}\ln (\frac{1}{x}\minus{}1)$  . It has second derivative $ f''(x)\equal{}\frac{1\minus{}2x}{(x\minus{}1)^2x^2}$

which is positive for $ 0<x\leq\frac{1}{2}$ etc  :)


Hello, for a sphere of center $ (x_1, y_1, z_1)$ and radius r, will the equation for the volume of the sphere be $ (x_2\minus{}x_1)^2\plus{}(y_2\minus{}y_1)^2\plus{}(z_2\minus{}z_1)^2<\equal{}r^2$ or what? Actually my geometry is quite poor, so I was just curious...

The equation for the volume of the sphere will always be $ (4/3)(pi)(r)^{3}$

If you're looking for the equation of the sphere, what do you mean by x_2 and y_2, etc.?

The set of points $ (x, y, z)$ that satisfy $ (x \minus{} x_1)^2 \plus{} (y \minus{} y_1)^2 \plus{} (z \minus{} z_1)^2  \leq r^2$ is the solid sphere with center $ (x_1, y_1, z_1)$ and radius $ r$.  It has volume $ \frac{4\pi r^3}{3}$.

Yeah, by volume, I meant solid sphere. Thanks!

Just in case you're interested, [url=http://en.wikipedia.org/wiki/N-sphere#Volume_of_the_n-ball_and_n-sphere]here[/url] is some information regarding the volume of an $ n$-sphere, which is the higher dimensional counterpart.

You can think about this intuitively. The equation of a sphere was derived using the same method as deriving a circle. You use the distance formula in 3 dimensions to obtain:

$ \sqrt{(x\minus{}x_{1})^{2}\plus{}(y\minus{}y_{1})^{2}\plus{}(z\minus{}z_{1})^2} \equal{} r.$

This gives the set of all points whose distance from a fixed point $ (x_1,y_1,z_1)$ is $ r$. If we want to find the set of all points inside the sphere including the sphere itself, then we are looking for:

$ \sqrt{(x\minus{}x_{1})^{2}\plus{}(y\minus{}y_{1})^{2}\plus{}(z\minus{}z_{1})^2} \le r\implies (x\minus{}x_{1})^{2}\plus{}(y\minus{}y_{1})^{2}\plus{}(z\minus{}z_{1})^2 \le r^2.$

We were able to square both sides because the quantities under the square root and $ r$ are both positive.


$ A$ is a subspace of $ \mathbb{C}^{n}$.
To proof:
$ dim_{\mathbb{R}} A \cap \mathbb{R}^{n} \leq dim_{\mathbb{C}} A$

Show that any set in $ \mathbb{R}^n$ that is linearly independent over $ \mathbb{R}$ is also linearly independent over $ \mathbb{C}$.

This would work with any pair of fields, one contained in the other.


inequalities
algebra
polynomial
function
rational function
number theory
relatively prime

Can anyone give me a satisfying analysis-type proof of why R is unbounded above?

Thanks.

[quote="ComplexZeta"]By definition, every subset of $\mathbb{R}$ that is bounded above has a least upper bound. Suppose that $\mathbb{R}$ is bounded above, and let $m$ be the least upper bound. But $m\in\mathbb{R}$ (by completeness), and so $m+1\in\mathbb{R}$. But $m+1>m$, and so $m$ is not an upper bound.[/quote]

Thanks.  For some reason, in the contradiction, I didn't realize that sup R E R (which is, as you pointed out, part of completeness).

Really, any ordered field must be unbounded, without any need to cite completeness. In order for the statement "The field $F$ is bounded by $m$" to make any sence, $m$ must be a member of $F$. After all, the only inequalities defined in the axioms of an ordered field are between members of that field. Then you can look at $m+1$, which is greater than $m$. ($1$ is positive in any ordered field, and order cooperates with addition.)

But I can say that some subset of $\mathbb{Q}$, for example, is bounded above by some element of $\mathbb{R}\setminus\mathbb{Q}$.

Yes, that's right, up to a point. If $\mathbb{Q}$ is the entire universe of our discussion, then it is unbounded just because it is an ordered field. If you want to talk about elements of $\mathbb{R}\setminus\mathbb{Q}$ as possible bounds for $\mathbb{Q}$, then we've strayed quite a ways from the question that started this thread. To deal with that, you must deal with the properties of $\mathbb{R}$. In particular, this is equivalent to the Archimedean property of $\mathbb{R}$ - that is, "you can empty the ocean with a teaspoon." To prove that $\mathbb{R}$ is Archimedean, you must invoke completeness; ComplexZeta's first post is very close to that proof.

There is such a thing as a non-Archimedean ordered field. The standard example looks like this: Consider the set of all polynomials in the symbol $x$ that have real coefficients. (Don't think of $x$ as being anything other than a symbol to be manipulated.) This set of polynomials is a ring - you can add them and multiply them. Now form the field of quotients of this ring (just as $\mathbb{Q}$ is formed as the field of quotients of the ring $\mathbb{Z}$). Each member of this field - that is, each rational function - can be expressed in lowest terms as a quotient of two relatively prime polynomials, of which the denominator has a positive leading term. We then call this rational function positive if and only if the numerator has a postive leading (highest degree) term.

The result is an ordered field. Considered as its own universe, it is an unbounded set. Like any ordered field, it contains within it an isomorphic copy of the rationals - but that copy of the rationals [b]is[/b] bounded. For example, $x$ is an upper bound for $\mathbb{Q}$. This field is also not complete; it can't be, since completeness would imply the Archimedean property and it doesn't have that property.


[quote="ice_age"]find integer pairs (x,y) which follows x^y=y^(x-y)

thanks![/quote]
$x=y \to x=y=0 or x=y=1$
$y=1\to x=y=1$
$x>y\geq 2$
$x=yk, yeQ$
$y^{2}k=y^{k}$ $y^{k}$is rational. so $k=q/p , y=a^{p}$
$pa^{q}=qa^{2p}$one of $p,q = 1$  $x>y-\to q>p-\to p=1$
$q=a^{q-2}\geq 2^{q-2}q=3,a=3 and q=4, a=2$
so $y=a=3, x=yk=9$ and $y=a=2. x=yk=8$


Of the first 2004 Fibonacci numbers (1,1,2,3,...), how many have 2 as their last digit?

my idea was basically the same. we write the Fibonacci sequence $ \mod 10$: 1,1,2,3,5,8,3,1,4,5,9,4,3,7,0. and we have $ \text{ord}_{10}(7)=4\Rightarrow 7^{4}\equiv 1\pmod{10}$. Thus the sequence has period $ 15\times 4=60$. Let us write the first 60 terms: 1,1,2,3,5,8,3,1,4,5,9,4,3,7,0,7,7,4,1,5,6,1,7,8,5,3,8,1,9,0,9,9,8,7,5,2,7,9,6,5,1,6, 7,3,0,3,3,6,9,5,4,9,3,2,5,7,2,9,1,0. Since there are exactly four $ 2$'s among the first $ 60$ terms, we conclude that the number of two's in our sequence is $ 4\times \lfloor\frac{2004}{60}\rfloor+1=4\cdot 33+1=133$.(the "1" is for the two between the 1980th and 2004th term)

@Altheman: you missed the last 2. :P

How did you get from here:

[quote="nayel"]my idea was basically the same. we write the Fibonacci sequence $ \mod 10$: 1,1,2,3,5,8,3,1,4,5,9,4,3,7,0. and we have $ \text{ord}_{10}(7)=4\Rightarrow 7^{4}\equiv 1\pmod{10}$.[/quote]

to here:
[quote="nayel"]Thus the sequence has period $ 15\times 4=60$.[/quote]

What does $ \text{ord}_{10}(7)$ mean?

[quote="nayel"][b]Definition[/b] Let $ (a,m)=1$ and $ d$ be the smallest positive integer such that $ a^{d}\equiv 1\pmod m$. Then we define $ d$ as the order of $ a$ modulo $ m$ and denote by $ d=\text{ord}_{m}(a)$.

Now for your question, the first zero in the Fibonacci sequence $ \mod 10$ comes in the 15th term, and the 14th term is $ 7$. so since $ \text{ord}_{10}(7)=4$, the length of the period must be $ 15\times 4=60$. For more on this, have a look at [url=http://www.mathlinks.ro/Forum/weblog_entry.php?t=156030]here[/url].[/quote]

I'm afraid that I still don't get it. :(

Basically, we are looking for $ n$ such that
$ F_{n}= 0$
$ F_{n+1}= 1$

But why do we need the fact that $ 7^{4}\equiv 1\pmod{10}$?
How does this help us determine where the 0 and 1 are next to each other?

if you followed my link, you'd have possibly understood what i was trying to say. anyway, we have (congruences are taken mod 10)
$ F_{14}\equiv 7,F_{15}\equiv 0,F_{16}\equiv 7,$ $ F_{17}\equiv 7,$ $ F_{18}\equiv 2\cdot 7,F_{19}\equiv 3\cdot 7,$ $ F_{20}\equiv 5\cdot 7, F_{21}\equiv 8\cdot 7,\dots, F_{29}\equiv 7\cdot 7=7^{2}$, $ F_{30}\equiv 0,F_{31}\equiv 7^{2}, F_{32}\equiv 7^{2},F_{33}\equiv 2\cdot 7^{2},F_{34}\equiv 3\cdot 7^{2},$ $ F_{35}\equiv 5\cdot 7^{2},F_{36}\equiv 8\cdot 7^{2}\dots,F_{44}\equiv 7\cdot 7^{2}=7^{3}, F_{45}\equiv 0,F_{46}\equiv 7^{3},\dots,$ $ F_{59}\equiv 7^{4}\equiv 1$.
Thus $ F_{60}\equiv 0, F_{61}\equiv 1,F_{62}\equiv 1,\dots$. So the sequence has become periodic with period 60.

ps. my 500th post! :clap:

[quote="nayel"]if you followed my link, you'd have possibly understood what i was trying to say. anyway, we have (congruences are taken mod 10)
$ F_{14}\equiv 7,F_{15}\equiv 0,F_{16}\equiv 7,$ $ F_{17}\equiv 7,$ $ F_{18}\equiv 2\cdot 7,F_{19}\equiv 3\cdot 7,$ $ F_{20}\equiv 5\cdot 7, F_{21}\equiv 8\cdot 7,\dots, F_{29}\equiv 7\cdot 7=7^{2}$, $ F_{30}\equiv 0,F_{31}\equiv 7^{2}, F_{32}\equiv 7^{2},F_{33}\equiv 2\cdot 7^{2},F_{34}\equiv 3\cdot 7^{2},$ $ F_{35}\equiv 5\cdot 7^{2},F_{36}\equiv 8\cdot 7^{2}\dots,F_{44}\equiv 7\cdot 7^{2}=7^{3}, F_{45}\equiv 0,F_{46}\equiv 7^{3},\dots,$ $ F_{59}\equiv 7^{4}\equiv 1$.
Thus $ F_{60}\equiv 0, F_{61}\equiv 1,F_{62}\equiv 1,\dots$. So the sequence has become periodic with period 60.[/quote]

I get it now. Thank you very much! :)

Does your method generalize to other kinds of sequences?


write as many theorems or formulas on polynomials as possible please.they are really useful, binomial_4eva i think you know alot about polynomials.so write them here if u want, we can make a list of theorems on polynomials it will be very usefull for everyone.

Can you filter that list and just post the ones you feel you use the most/are the most important?

Polynomials (this in depth, at least), have never been covered too much in extent in my education, so I'm lost as to the solutions people post sometimes.

http://mathworld.wolfram.com/DescartesSignRule.html
http://mathworld.wolfram.com/EisensteinsIrreducibilityCriterion.html (a little college-level)
http://mathworld.wolfram.com/IrreduciblePolynomial.html (this too)
http://mathworld.wolfram.com/MonicPolynomial.html
http://mathworld.wolfram.com/Newton-GirardFormulas.html
http://mathworld.wolfram.com/PolynomialFactorTheorem.html ([b]important[/b])
http://mathworld.wolfram.com/RationalZeroTheorem.html ([b]important[/b])
http://mathworld.wolfram.com/SyntheticDivision.html
http://mathworld.wolfram.com/VietasFormulas.html ([b]important[/b])

I think everything in there, except for the two links regarding irreduceable polynomials, are covered in AoPS Vol. 2 (in a more understandable form in the case of the Newton-Gerard and Vieta formulas [speaking of which, I think I'll have to review the Newton-Gerard formula]).


I used the booklet package to produce a document, but it appears that the margin on the right side is larger than the margin on the left. Is there a way to fix this?

Booklet Test.pdf shows a sample document that shows the difference between the left and the right margins. This is the source code:
[code]\documentclass[12pt]{article}
\author{ThinkFlow}
\title{This is a Test}
\date{\today}

\usepackage[print,thirtytwo,twouparticle]{booklet}
\setpdftargetpages

\pagestyle{empty}
\begin{document}
\maketitle

Sample Text...Sample Text

\end{document}[/code]

The [url=http://tug.ctan.org/cgi-bin/ctanPackageInformation.py?id=booklet]Booklet documentation[/url] has a lot about margins eg \oddsidemargin. Or you may prefer to use the [url=http://tug.ctan.org/cgi-bin/ctanPackageInformation.py?id=geometry]geometry package[/url].


induction
modular arithmetic
combinatorics proposed
combinatorics

Given a triangle, divide it in smaller triangles, s.t. each two triangles either have no common points, or they have a common vertex, or they have a common side. If each vertex of a small triangle belongs to an even number of small triangles, show that we can assign the numbers $0,1,2$ to the small triangle vertices s.t. each small triangle has three vertices with different numebrs.

Pascual said that I should write my solution :P

I will write a sketch. ;)

1. We will prove prove that the small triangles can be colored in chessboard order. Indeed, consider corresponding planar graph (each triangle is a node and each side is an edge). We are to show that it has only even cycles. Suppose a contrary and choose the smallest odd cycle (which has the minimal area). It is clear it doesn't contains nodes inside yourself. But it follows that it contains exactly one vertex of the small triangle. And it immediately implies that chosen cycles consists of 'sides', which are incident to this vertex. And we know there are even number of such sides.

2. Let's prove statement for an arbitrary polygon divided into triangles which are colored in chessboard order. By induction on number of triangles. For 1 triangle it is true. Consider a common case. Choose an arbitrary polygon's vertex and remove it with all corresponding triangles. Then the initial polygon will break up into some polygons which can be properly colored (note: for each polygon there are 6 correct colorings! ). And it is clear how to co-ordinate colorings in order to obtain coloring of the initial polygon.

Hope it is correct.

I think it is. My first step was the first as yours (chessboard-style coloring).

jaja, I told Myth to write it because his solution is very smart, and dont uses anything stranfe, just nice observations, I think that that is what olypmpiads should try to motivate. Thanks Myth for this solution.

Anyway, there are lot of problems that are solved given numerical values to colors, Was your solution like that Grobber?

After coloring the board chessboard-style, I oriented the edges of all white triangles in a counter-clockwise direction (that's what I used the cehssboard coloring: it allowed me to orient the edges without them interfering with each other). After that, I colored a vertex with color $0$ and called it the origin. Then for a given path along the edges, add $1$ if you traverse the edge in the same direction as its orientation, and $2$ otherwise, and look at everything $\pmod 3$. Now just color each vertex $x$ according to the value of the path from the origin to $x$. It can be shown that no matter what path we follow, they all have the same value $\pmod 3$, by showing that each cycle has value $0\pmod 3$.

I hope it's clear and correct :). I never checked it properly, just thought about it during a bus trip, and it seemed to work.


Fredek runs a private hotel. He claims that whenever $ n \ge 3$ guests visit the hotel, it is possible to select two guests that have equally many acquaintances among the other guests, and that also have a common acquaintance or a common unknown among the guests. For which values of $ n$ is Fredek right? (Acquaintance is a symmetric relation.)

Suppose $n$ is odd. There are two guests with the same number of acquaintances. If they do not have a common acquaintance or a common unknown, then each of them knows exactly $\frac{n-2}2$ other people, which is not an integer, contradiction. Hence Fredek is right for odd $n$.

Suppose Fredek is wrong for some $n\ge6$ even. Take two people $A$ and $B$ with the same number of acquaintances. Each of them has either $\frac{n}2$ or $\frac{n-2}2$ acquaintances. Among guests other than $A$ and $B$, there exist $C$ and $D$ with the same number of acquaintances. Each of $C$ and $D$ knows exactly one of $A$ and $B$, thus they have either $\frac{n}2$ or $\frac{n-2}2$ acquaintances. Similarly, there exist $E$ and $F$ with either $\frac{n}2$ and $\frac{n-2}2$ acquaintances. Among $A,B,C,D,E,F$, there exist three with the same number of acquaintances. Among these three, one is a common acquaintance or a common unknown for the other two, so Fredek is right.

For $n=4$, Fredek is wrong: A only knows B, B only knows A and C, C only knows B and D.


Prove that among the numbers $50^{n}+(50n+1)^{50}$, where $n \in \mathbb{N}$, there are infinitely many composite numbers.


limit
real analysis
real analysis unsolved

Let $ n\geq 1$ be a natural number and let

$ x_{n}\equal{}\sqrt{1!\sqrt{2!\sqrt{3!\cdots\sqrt{n!}}}}$.

It can be proved that $ 1<x_{n}<3$ for all $ n\in N$, and hence, the sequence converges.

Let $ x\equal{}\lim_{n\rightarrow\infty}x_{n}$, and let $ \alpha>0$ be a positive  number.

Study the convergence of the following series:

$ \sum_{n\equal{}1}^{\infty}\left(x\minus{}x_{n}\right)^{\alpha}$.

Didilica, can you please post the solution?
Thanks.

[quote="didilica"]Let $ n\geq 1$ be a natural number and let

$ x_{n}\equal{}\sqrt{1!\sqrt{2!\sqrt{3!\cdots\sqrt{n!}}}}$.

It can be proved that $ 1 < x_{n}< 3$ for all $ n\in N$, and hence, the sequence converges.

Let $ x \equal{}\lim_{n\rightarrow\infty}x_{n}$, and let $ \alpha > 0$ be a positive  number.

Study the convergence of the following series:

$ \sum_{n \equal{} 1}^{\infty}\left(x\minus{}x_{n}\right)^{\alpha}$.[/quote]
Just a proof for $ x_{n}<3$
because :$ (n\minus{}1)!((n\plus{}1)!\plus{}1)<(n!\plus{}1)^{2}$
thus:
$ x_{n}\equal{}\sqrt{1!\sqrt{2!\sqrt{3!\cdots\sqrt{n!}}}}<\sqrt{1!\sqrt{2!\sqrt{3!\cdots\sqrt{((n\plus{}1)!\plus{}1)^{2}}}}}\equal{}\sqrt{1!\sqrt{2!\sqrt{3!\cdots\sqrt{(n\minus{}1)!((n\plus{}1)!\plus{}1)}}}}\leq\sqrt{1!\sqrt{2!\sqrt{3!\cdots\sqrt{(n!\plus{}1)^{2}}}}}\equal{}\sqrt{1!\sqrt{2!\sqrt{3!\cdots\sqrt{(n\minus{}2)!(n!\plus{}1)}}}}<\cdots<\sqrt{(2!\plus{}1)}^{2}\equal{}3$.

OK,for the author's problem.My answer is that for any positive number $ \alpha>0$ the series converges.
Just a skecth of the proof,because we have:$ x_{n+1}=x_{n}[(n+1)!]^{\frac{1}{2^{n+1}}}$
then use stolz's theorem(and associated with the Stirling's formula),we can prove:
$ \lim_{n\to\infty}\frac{x-x_{n}}{\frac{1}{n^{\beta}}}=0$,for $ \beta>0$
then the answer will be clear,hope it is right :P


I want 2005-2007 years all around the worlds national olimpiads geometry problem. :lol: please I very need this

Hey I think you should buy OLONLOG setguul xawsralt 13.
It has a lot of country's national or TST problems
I'm mongolian too


conics
ellipse
geometry
geometry unsolved

Let $E$ an elipse with center $O$,  $P\in E$ and $T$ the tangent line to $E$ at $P$. The line paralel to $T$ that pass through the center of $E$ is call diameter of $E$.
Well, this diameter have the property that if we draw any secant line $L$ to $E$ paralel to $OP$ then the this diameter cut the segment of $L$ inside $E$ in it's midpoint.

Does anybody know how to prove this fact ?
Well using analitic geometry is just  counts, but I was trying using simple geometry.

Yeah, $OP$ and the diameter parallel to $T$ are called conjugate diameters, and this is one of those properties which is easily proven if we take into account the fact that the ellipse is the projection of a circle in anohter plane.

I know, but I want to prove it using plane geometry (working with the elipse as the locus of the points that there sum of distants of the focus is constant),
such a prove will be interesting to see

If anybody knows how please let me know.....


geometry
algebra
polynomial
probability
number theory
complex numbers

Since there has been a recent surge in the number of marathons and stickying all of them wouldn't be a good idea, I'm going to link to all of them in this post.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=70276]The Intermediate Geometry Marathon (Intermediate)[/url]
[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=70338]Algebra, Number Theory, and Polynomials Marathon #2 (Intermediate)[/url]
[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=70337]Probability and Counting Marathon (Intermediate)[/url]
[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=70055]Algebra and Equations Marathon (Pre Olympiad)[/url]
[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=68754]Complex Numbers Marathon (Pre Olympiad)[/url]

And then there are more competitions in [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=37509]this[/url] post...maybe we'll consolidate our efforts as some point...

edit: eh I'm lazy...I agree with whatever 4everwise does (disclaimer: my 'agreeing' with 4everwise can be terminated at any time at my will...in case he does something radical :P )

I have been granted permission by Joml88 to resticky the geometry competition.  :)

Joml88, did you unsticky this?  :P

If so... [hide] :rotfl: It was just stickied :rotfl: [/hide]

Whoa huh????

Sticked again!

I disagree with whatever 4everwise does :lol:  :P

[quote="beta"]I disagree with whatever 4everwise does :lol:  :P[/quote]Response: :mad:

Just kidding.  :P


factor the polynomial
$x^6-2x^5+x^2-x-2$


ARML Practice- The following problems I have designed are intended to find a striking relationship between combinatorics and several sequences, such as the trigonal numbers and sum of first n squares sequence. This is intended as a semi-tutorial for students that have not been exposed to this topic. Some people may find it too easy but its still good review or practice.

We will start with combinatorics, then make the connection.

1. Hockey-Stick Identity

(a)Start with an entry on the extreme left side of Pascal's Triangle (any number 1) such as $\binom{3}{0}$. Now move downwards to the right in a daigonal fashion, adding numbers along the diagonal. For example, starting at $\binom{3}{0}$, the next numbers along the diagonal are 4, 10, 20, etc. Now stop at a given number, such as 10. Compare the numbers in the diagonal (from 1 to 10) to the number below and to the left of 10 (15). Do you see a relationship? Try starting with $\binom{3}{0}$ again, going down the diagonal, and then stopping at 20. Then compare the numbers in the diagonal (from 1 to 20) to the number below and to the left of 20 (35). The relationship should be clear. Once you have a firm understanding of the relationship, summarize the result with an equation involving a summation.

(b)Now try the same thing, but this time starting at the extreme right side of the triangle. Once again, formalize the result a bit by giving an equation. Notice that for this exact relationship to hold, we must start at the a 1.

The results of the investigation are given below. If this is your first exposure to the identity, please do not look until you have tried finding it yourself.

[hide]Left Hockey-Stick Identity: $\displaystyle\sum_{k=0}^{j}\binom{n+k}{k} = \binom{n+j+1}{j}$.
Right Hockey-Stick Identity: $\displaystyle\sum_{k=0}^{j}\binom{n+k}{n} = \binom{n+j+1}{n+1}$.[/hide]

2. Proof/Derivation
Proving the hockey-stick identity is not that difficult.

Let's start by deriving the left hockey-stick identity algebraically. First off, recall pascal's identity: $\binom{n}{k-1} + \binom{n}{k} = \binom {n+1}{k}$ (basically just a more formal way of writing that the sum of two adjacent terms in a row of Pascal's triangle gives the term centered below them).

(a)Starting with the expanded form of the left-hand side of the left hockey stick identity above, use Pascal's identity to "collapse" the terms, giving you the desired result.

(b) Now do the right hockey-stick identity. Start with the side with lots of terms, and "collapse" them to get the desired result.

(c) A combinatorial-based derivation can also provide insight. First make sure you understand a key concept that defines Pascal's Triangle: the number of paths from the top most entry to the $\binom{n}{k}$ entry is $\binom{n}{k}$. This is because every path from the top to $\binom{n}{k}$ has length $n$ and exactly $k$ of the $n$ moves are to the right. It follows that there are $\binom{n}{k}$ paths to the entry since all you need to do is choose exactly $k$ of the $n$ moves to be a right move. Make sure you understand this, and test it with concrete numbers if you need to.

Back to the hockey-stick identity. Look at a specific entry in Pascal's Triangle, such as one of the 15's. Give a detailed explanation of why the hockey-stick identity holds (left and right) by considering the number of paths from the top to the entry 15.

3.
Finally we can move on to the connection with sequences.
We first concern ourselves with the question of how to derive a formula for $\displaystyle\sum_{i=1}^{n} i$ in terms of $n$. Our general strategy will be to write $i$ as a combination, and then use the hockey-stick identities to simplify.

(a) Clearly, $\binom{i}{1}=i$. Use this fact and the hockey-stick identity to derive the familiar formula for $\displaystyle\sum_{i=1}^{n} i$.

(b) The nth triangular number $t_n$ is defined by $t_n=\displaystyle\sum_{i=1}^{n} i$. The nth tetrahedral number $s_n$ is defined by $s_n=\displaystyle\sum_{i=1}^{n} t_i$. Find a formula for $s_n$ in terms of $n$.

(c) Now we move on to a more difficult problem, deriving a formula for $\displaystyle\sum_{i=1}^{n} i^2$. Once again, our strategy is the same: try hard to apply the hockeystick identity by rewriting $i^2$ in terms of binomial coefficients. Before starting, note that the binomial coefficient $\binom{i}{k}$, where $k\leq{i}$ gives an expression with degree $k$ for $i$.

(d)Now try $\displaystyle\sum_{i=1}^{n} i^2+3i+2$

(e)Find an expression for $\displaystyle\sum_{i=1}^{n} i^3$

(f)One final extension. Its a lot of algebra (and practice with manipulation), but find an expression for $\displaystyle\sum_{i=1}^{n} i^4$

I won't give answers to number 3. Most formulas are familiar and you can get an idea if your formula works by plugging-in values.

Let me know what you think about the tutorial  :) Also tell me if you find any errors.

Mark

there might. depends on how much time i have.

i want to know how many people actually benefit from it.


factorial
function
integration
calculus
calculus computations

so i was reading a book and came across this interesting fact.

$(-.5)!=\sqrt{\pi}$

basically it works just like normal factoral except insead of $0!=1$ we have $(-.5)!=\sqrt{\pi}$.
so $(3.5)!=(3.5)(2.5)(1.5)(.5)(\sqrt{\pi})$

could someone please explain to me why this is soo. (i have pluged this into my TI-84 and have gotten the same result.)

That's the Gamma function: $\Gamma(s)=\int_0^\infty x^{s-1}e^{-x}\,dx$ (for $s>0$ or at least $\text{Re }s>0$). It is easy to show that $\Gamma(s+1)=s\Gamma(s)$ using integration by parts, and $\Gamma(1)=1$, so $\Gamma(n+1)=n!$.

We want to calculate $\Gamma(\frac12)=\int_0^\infty \frac{e^{-x}}{\sqrt{x}}\,dx$.
Substituting $t=\sqrt{x}$, we have $\Gamma(\frac12)=2\int_0^\infty e^{-t^2}\,dt=\int_\infty^\infty e^{-t^2}\,dt$. Integrating this by [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=63767]a classic trick[/url], we have $\Gamma(\frac12)=\sqrt{\pi}$.

o ok i follow somewhat.
it would probably help if i had more knowledge about calculus.
right now im in calc BC but i understood what u did for the most part.


So, exactly which setups are "balanced"?

Is a 4 townie, 2 cop, 2 doctor, 5 scum setup balanced?
Is a 10 vig, 10 townie, 1 sk setup balanced?

Game theoretic concepts don't apply well to a game like Mafia, which is highly psychological.  Optimal play in Mafia occurs when the mafia lie perfectly and the townspeople hang randomly, and real Mafia games are never optimal.  So whether a given setup is "balanced" (whatever that means) depends a lot on the strengths of the various players in question, how well they know each other, and so forth.

I created a program in TI-Basic at one point:

Prompt A
[Number of Town]
Prompt B
[Number of Scum]
While A>0 and B>0
rand*(A+B) -> R
If R>A
Then
B-1->B
Else
A-1->A
End
If A=0 or A=1
Disp "Scum Win"
If B=0
Disp "Town Win"
A-1->A
End

Assuming optimal gameplay what is the scum/town ratio to make a game have 50/50 probability of getting a town win versus a scum win?

As far as I can tell, your program ignores nightkills.
That's a problem. Also, it ignores power roles, though that might be necessary to make it simple enough.

Also, I believe the mafia win when B>=A (ignoring possible power roles that could change this).

Prompt A
Prompt B
While A>0 and B>0
rand*(A+B) -> R
If R>A
Then
B-1->B
Else
A-1->A
End
If A=0 or A=1
Disp "Scum Win"
If B=0
Disp "Town Win"
[b]A-1->A[/b]
End

Doesn't this make it such that mafia always kills?

Running a program with 2 mafia, 7 town, no power roles, and random lynch, town wins about 30% of the time.

Add in another town, and town wins about 20% of the time.

It is very important that town not random lynch. With random lynch, 19 town and 2 mafia wins 50% of the time.

Ah, it seems to have been a problem with my reading skills rather than with your program.

Not like I know how to read programs like that...
But there probably no truly balanced mafia game unless we could gather 100 people and try 100000000000000's of scenarios after another
even though we would be dead by then...

at least that's information for the future

balanced is such a relative term

Input "Townie:",A
Input "Scum:",B
Input "Vig:",V
Input "Doctor:",D
For(X,1,(A+B+V+D))
{0}->LKILL(X)
End
While (A+V+D)>0 and B>0
rand*(A+B+V+D) -> R
If R>(A+B+V)
D-1->D
If R>(A+B) and R<(A+B+V)
V-1->V
If R>A and R<(A+B)
B-1->B
If R<A
A-1->A
rand*(A+V+D) -> R
If R>A
R+B->R
1->LKILL(floor(R))
For(X,1,V)
rand*(A+B+V+D-1) -> R
If R>(A+B+X)
R+1->R
1->LKILL(floor(R))
End
For(X,1,D)
rand*(A+B+V+D-1) -> R
If R>(A+B+V+X)
R+1->R
0->LKILL(floor(R))
End
For(X,1,dim(LKILL))
If LKILL(X)=1
Then
2->LKILL(X)
...
End

Trying to make a program that accounts for vig+doctors. Next up: cops with sanity, SKers, inductors,roleblockers, etc...

[quote="chenhsi"]Me = no understand your program.

I actually started writing a mafia probablity program in java a couple of months ago. It works and runs, for just townie and goons. However, the probablity is a bit off then what I manually calculate :P

I have it almost working for doc (haven't tested it yet), and am too lazy to do cop.[/quote]
Inaccuracy probably due to double...
Man, I barely know computer science. :(

Umm...

3% difference for 5 town, 1 scum, 6% difference for 7 town, 1 scum

Oh, got it... your program estimates probability through running several iterations of the game? (I lost.)

[quote="james4l"]Well all the program proves is that random-lynching is bad. We all know that.[/quote]

Right. But not random-lynching is good. Random-Lynch makes me have to add 20 townies for 2 mafia. 7 townies, 2 mafia, with somewhat better lynching gives me 45% town win.


I was wondering if classes that worked through the books Aops 1&2 were being made?  If not, I'd really like to suggest it.

well they dont have it directly for the books but they are suggested for classes like aime problem solving

nice signature i think im the onyl person who cant find a nerdy signature on this site  :rotfl:  :(  :maybe:

I know they don't have it, i was suggesting it and asking if it's being planned...

It would be a great class for those not really preparing for competition, but just trying to get better at math in general.

I would definitely attend these classes, by the way :D

Well the introduction series are kinda like the AoPS volume 1 and the intermediate like volume 2 but I can see what you mean.

(P.S. can you post your pi proof in classroom math?)


Three beads, two white beads, and one bue bead are placed in a line in random order. What is the probability that no two neighoring beads are the same color?

the total number of outcomes is 3!=6

the number of outcomes where two neighboring beads are side by sides =4,
bww and wwb, where the 2 w's are interchangeable. the probability is the remaining over the total.

6-4/6=2/6=1/3

There are three posibilities,given by 3!/2!.  These are:
BBW
BWB
WBB.
The only one that works is the second.
THus, the probability is [u]1/3[/u]

There are only three positions the blue bead can be in: 1, 2, or 3.

If the blue bead is in position 1 or in position 3 then the two remaining white beads are adjacent to each other.

Therefore, only if the blue bead is in position 2 are there no neighboring beads of the same color.

Thus, the probability is   $ \frac13$.


Να βρεθουν οι συνεχεις συναρτησεις f:$ R\minus{}>R$ με $ f(f(x))\minus{}2f(x)\plus{}x\equal{}0$ για καθε χ ανηκει $ R$

Συνοπτικα,
θεωρω$ a_0\equal{}x, a_1\equal{}f(x), a_n\equal{}f(a_{n\minus{}1})$
τοτε απο την δοθεισα  $ a_{n\plus{}2}\minus{} a_{n\plus{}1}\equal{} a_n \minus{} a_{n\minus{}1}\equal{}c$, οπου c σταθερος πραγματικος,  για καθε n φυσικο.
αρα  $ a_1\minus{}a_0\equal{}c \leftrightarrow f(x)\equal{}x\plus{}c$,   ευκολα ολες αυτης της μορφης επαληθευουν.
Μηπως ειναι περιττη η συνεχεια;

Δες το συνημμένο εδώ http://www.artofproblemsolving.com/Forum/viewtopic.php?t=284247

[quote="Athinaios"]Συνοπτικα,
θεωρω$ a_0 \equal{} x, a_1 \equal{} f(x), a_n \equal{} f(a_{n \minus{} 1})$
τοτε απο την δοθεισα  $ a_{n \plus{} 2} \minus{} a_{n \plus{} 1} \equal{} a_n \minus{} a_{n \minus{} 1} \equal{} c$, οπου c σταθερος πραγματικος,  για καθε n φυσικο.
αρα  $ a_1 \minus{} a_0 \equal{} c \leftrightarrow f(x) \equal{} x \plus{} c$,   ευκολα ολες αυτης της μορφης επαληθευουν.
Μηπως ειναι περιττη η συνεχεια;[/quote]

Προσπαθώ να καταλάβω αυτή τη λύση και τη διαφορά της με το συνημμένο που έβαλε ο κ. Μπόρης! Θα μπορούσε να μου εξηγήσει κάποιος αν η παραπάνω λύση είναι σωστή (κι όταν λέω σωστή εννοώ να αρκούν τα παραπάνω για να βγάλουμε την $ f(x)\minus{}x$ σταθερή!).

Στην αρχή θέτουμε $ a_0\equal{}x$ και λοιπά και μετατρέπουμε το πρόβλημα σε "ανάλογο" με ακολουθίες... Ομως νομίζω ότι το συμπέρασμα που βγάζουμε ότι $ a_{n\plus{}1}\minus{}a_n\equal{}...\equal{}a_1\minus{}a_0\equal{}c$ ισχύει για κάθε $ x$ (ξεχωριστά). Δηλαδή ξεχωρίζω το [i]"για κάθε $ x$"[/i] απ' το "[i]για όλα τα $ x$"[/i] (το οποίο θα μας έδινε τη λύση...).
Aυτό που λέω λοιπόν είναι ότι με τη συγκεκριμένη λύση του Ηλία καταλήγουμε στο ότι $ ...\equal{}f(f(1))\minus{}f(1)\equal{}f(1)\minus{}1\equal{}c$ και $ ...\equal{}f(f(2))\minus{}f(2)\equal{}f(2)\minus{}2\equal{}c'$ και δεν έχουμε διασφαλίσει (αποδείξει) σε καμία περίπτωση ότι $ c\equal{}c'$!!!

Ελπίζω να έγινε σαφής η απορία μου :oops:

Μιm πιστευω πως η παρατηρηση σου ειναι ιδιαιτερα ευστοχη και η λυση μου λανθασμενη. Θα ηθελα και εγω απο καποιον αν μπορει να εξηγησει λιγο την τεχνικη αυτη με την καταλληλη χρηση ακολουθιων για την επιλυση συναρτησιακων εξισωσεων (που προφανως δεν πολυ γνωριζω).
Σαν αλλη λυση ειχα στο μυαλο μου το 1-1 της f(x) που οριζει οπως ειδα και ο Κ.Μπορης στο link και μετα αναγεται σε γνωστη.
(πχ APMO 1989 problem 5)

Ηλια αν καταλαβα καλα βγαζεις οτι η παρασταση a_(n+1) - a_n ειναι σταθερη, ειναι ομως σταθερη ως προς n και οχι ως προς x, πιο συγκεκριμενα η σταθερα που βγαζεις ειναι $ c_{x}$ και εξαρταται απο το x, ειναι δηλαδη μια νεα συναρτηση g(x)...

Νομιζω οτι εχω βρει μια γρηγορη λυση αλλα δεν την εχω κοιταξει και πολυ οποτε παιζει να χανει καπου. Βασιζεται παντος στο γεγονος οτι: f συνεχης και 1-1 => f γνησια μονοτονη, και στη συγκεκριμενη περιπτωση ειναι ευκολο να δεις οτι δεν μπορει να ειναι φθινουσα, αρα ειναι γνησιως αυξουσα.

Ακριβως εκει φαινεται να ειναι το προβλημα.
Η αλλη λυση ισως ειναι αυτη που εχει γραψει ο Κ. Μπορης στο link- η αυτη που περιεγραψα στο ποστ μου πιο πανω. αν οχι καλο ειναι να την βαλεις οταν βεβαια μπορεσεις!

Δεν ξέρω αν αυτό βοηθάει αλλά νομίζω ότι καταλαβαίνει κάποιος το πρόβλημα καλύτερα αν φανταστεί ότι μιλάμε για ακολουθίες συναρτήσεων $ a_n(x)$ οπότε για άλλο x έχουμε άλλη ακολουθία συνεπώς άλλη η μονοτονία της συνάρτησης (αφορά τα x) και άλλη της ακολουθίας (αφορά τα n). Γραφικά πρόκειται για ένα σύνολο καμπυλών...


superior algebra
superior algebra unsolved

Suppose $ I$ is an ideal in a commutative ring $ R$.
Prove that $ R/I$ is a field iff $ I$ is a maximal ideal of $ R$.

I recommend using the ideal correspondence between $ R/I$ and ones of $ R$ containing $ I$. What does this give you¿


Joml, move this if you think it is too hard.

Prove:

 can only, but not necessarily, be prime if  is a power of 2.

Hint:

[hide]First, try to use contradiction. Second, consider what k looks like when it is a power of 2 and when it isn't a power of 2.[/hide]

This looks like a good problem but I think it is a bit too hard for this forum.  I m going to move it to Intermediate.

If $n \neq 1$ is odd, then [tex]2^{2^mn} + 1 = \left(2^{2^m}\right)^n + 1 = \left(2^{2^m} + 1\right)\left[\left(2^{2^m}\right)^{n-1} - \left(2^{2^m}\right)^{n-2} + \left(2^{2^m}\right)^{n-3} \ldots\right][/tex]. Since the terms in the square brackets cannot sum to 1, the entire expression is necessarily composite. QED.

[hide]We note that a^k+1 can be factored for all odd x.

So if k is odd it isn't prime. If k has 1 or more factors of 2 we simply divide k by 2 (and double a) until k is odd and we can factor it. the only case where this procedure breaks down is for powers of two.[/hide]

Is this right?[/hide]

Another well known  result and not too hard to prove;

Prove that when k   is  a power of 2 then:
(if N= 2^k + 1) ; N is prime if and only if
 (3^(2^(k-1)) + 1) is divisible by N.


function algebra polynomial limit domain calculus derivative

Give an example of a differentiable function $ f(x,y)$ (a polynomial for instance) [b] defined over all [/b] $ {\bf R}^2$ having a single critical point $ P\equiv (x_0,y_0)$ and such that $ P$ is a relative, not absolute,  maximum.   For functions $ f(x)$ of one variable this is of course impossible.

1) Differentiable at $ (x_0,y_0)$ means:
$ \lim_{(h_1,h_2)\to(0,0)} {f(x_0 \plus{} h_1,y_0 \plus{} h_2) \minus{} f(x_0,y_0) \minus{} \underline \partial f(x_0,y_0)\cdot (h_1,h_2)\over \sqrt {h_1^2 \plus{} h_2^2}} \equal{} 0,$  $ \underline \partial f(x_0,y_0)\doteq (f_x(x_0,y_0),f_y(x_0,y_0)$

3) "Differentiable function $ f(x,y)$" means differentiable at any point of its domain

3)  critical point $ P\equiv (x_0,y_0)$ means $ \underline \partial f(x_0,y_0) \equal{} (0,0)$

4) relative means local and absolute means global

5) for functions of one variable, differentiability implies the ordinary derivative and viceversa.

I apologize if the original text has generated some misunderstandings.

A relative maximum is a local maximum?

Then why wouldn't this work?

$ f(x) \equal{} \begin{cases} \minus{} x & \text{ if } x < 0 \\
1 \minus{} (x \minus{} \frac12)^2 & \text{ if } x \in [0,1] \\
x \minus{} 1 & \text{ if } x > 1\end{cases}$

Unique relative maximum in $ x \equal{} \frac12$. (the function even is continuous and obviously tends to infinity at both ends, making $ \frac12$ not an absolute maximum).

And what are you taking to be critical points? How about the calculus-book definition that a critical point is a place where either the derivative is zero or the derivative does not exist? In that case, $ x\equal{}0$ and $ x\equal{}1$ count as critical points for your example, and I don't see it as a counterexample at all.

For those seeking Arrigo-Sacchi's counterexample, you should be able to find a smooth function that accomplishes the task.

Really? I'd say that there is no such counterexample, at least if we require global continuity.

First, that local maximum is a strict local maximum. If there were other points in arbitrarily small neighborhoods with the same value of $ f$, those would be local maxima as well. We may assume WLOG that $ f$ is differentiable everywhere except possibly $ P$; if it failed to be differentiable anywhere, that would be a critical point.
Let's translate this so that $ P$ is the origin and $ f(P)\equal{}0$; this is just convenience. Now, suppose there is some other point $ Q$ such that $ f(Q)\ge 0$. Consider all smooth curves $ \gamma$ from $ P$ to $ Q$, and look at the values of $ f$ on them. On any such $ \gamma$, we must start by dipping below zero near $ P$, since $ f$ has a strict local maximum at $ P$. Find the minimum of $ f$ on $ \gamma$, then find the maximum of those minima over all $ \gamma$. Let the point found this way be $ R$, and the associated curve be $ \Gamma$. What can we say about $ R$? Slicing in the tangent direction to $ \Gamma$, $ f$ has a local minimum (since $ R$ is a minimum on $ \Gamma$), and its derivative in that direction is zero. In the normal direction, note that shifting the curve slightly in either direction would decrease the minimum value; that's only possible if the derivative is zero, since shifting in whichever direction is positive would increase the values. Combine these two pieces, and $ f$ has a critical point at $ R$. If the second derivative is nondegenerate, this point is a saddle point.

Summary of all of that: no such continuous function exists, because in order to pass from a local maximum to another point with larger values, there must be a saddle point inbetween.

If we drop the continuity requirement, there are silly examples like $ f(x,y)\equal{}\begin{cases}1&(x,y)\equal{}(0,0)\\x&\text{otherwise}\end{cases}$

Since the examples exist, I have tried to follow your argument

[quote="jmerry"]Let the point found this way be $ R$, and the associated curve be $ \Gamma$[/quote]

I don't understand when you say <<and the associated curve be $ \Gamma$>> because the set $ R$ may be done by isolated points. Now, by definition, any curve on the graph of $ f$ is defined by a function $ \Gamma\colon [a,b]\to {\bf R}^n$ if
the graph of $ f$ "lives" in  $ {\bf R}^n$ so the curve "is a continuum"


trigonometry
geometry
geometric transformation
reflection
circumcircle
angle bisector
similar triangles

Let $ ABC$ be a non-obtuse triangle with $ CH$ and $ CM$ are the altitude and median, respectively. The angle bisector of $ \angle BAC$ intersects $ CH$ and $ CM$ at $ P$ and $ Q$, respectively. Assume that \[ \angle ABP\equal{}\angle PBQ\equal{}\angle QBC,\]
(a) prove that $ ABC$ is a right-angled triangle, and
(b) calculate $ \dfrac{BP}{CH}$.
[i]Soewono, Bandung[/i]

it is just [hide]trig ceva [/hide]to tackle this problem.

I don't know about this, but I have \[ \angle ABP=\angle PBQ=\angle QBC, \] = 8.948922449° (yes, that ugly angle) and $ \frac{BP}{CH} $ = 2.

Yes, the angle measurement of 8.948922449.....° is correct.

Hint: When the sum of two angles equals 90 degrees, the sum of the squares of the sine values of the angles equals 1.

by a simple trigonometric calculation we get
$\angle A=63.15323236...,\angle B=26.84676764...$
whose sum is 90.

I don't know how valid is this argument but its probably the same as trig ceva.

From $\angle PBA = \angle QBC$ and $\angle PAC = \angle QAB$ we have that $P$ and $Q$ are isogonal conjugates. Therefore , $CM$ is the reflection of $CH$ over the bisector of $\angle ACB$ and therefore we get that the circumcenter of $ABC$ lies in $CM$. Therefore we must have $\angle ACB = 90$. This concludes part (a).

Now let $\angle CAB = \alpha$. By easy angle chase we get $\angle ABP = 30 - \frac{\alpha}{3}$, $\angle PBC = \angle 60 - \frac{3\alpha}{2}$.

We have $BP = \frac {BP}{\sin (60 + \frac{\alpha}{3})} =\frac{BC \cdot \sin \alpha}{\sin (60 + \frac{\alpha}{3})}$ and $CH = BC \cdot \cos \alpha$ and therefore we obtain \[\frac{BP}{CH} = \frac{\sin \alpha}{\cos \alpha  \cdot \sin 60 + \frac{\alpha}{3}} (*)\]

From trig ceva for cevians $AP,CP,BP$ we get $\sin \alpha = \frac{ \cos \alpha \cdot \sin 60 - \frac{2\alpha}{3}}{\sin 30 - \frac{\alpha}{3}}$ so plugging this in $(*)$ gives us

\[ \frac{BP}{CH} = \frac{\sin 60 - \frac{2\alpha}{3}}{ \sin 30 - \frac{\alpha}{3} \cdot \sin 60 + \frac{\alpha}{3}} = \frac{\sin 60 - \frac{2\alpha}{3}}{ \sin 30 - \frac{\alpha}{3} \cdot \cos 30 - \frac{\alpha}{3}} = 2 \]

Here's a synthetic solution to (b).

Reflect $P$ about $AB$ to $P'$. Then $\angle CBP = 2 \angle PBH = \angle PBP'$, so by similar triangles and two applications of Angle Bisector Theorem we have \[\frac{CB}{CH} = \frac{AC}{AH} = \frac{CP}{PH} = 2\frac{CP}{PP'} = 2\frac{CB}{P'B} = 2\frac{CB}{PB},\]thus $\frac{BP}{CH} = 2$.

Anyone can proof a?
Since i dont know how to use isogonal conjaquates


complex analysis
complex analysis unsolved

Find a conformal mapping from $ A \equal{} \{ z: |z \minus{} i| > 1, Im(z) > 0\}$ to the upper half-plane $ \mathbb{H} \equal{} \{ z : Im(z) > 0\}$

I want to map $ A$ to unit circle $ \mathbb{D}$ or the first quadrant of the plane and then use some known-mappings but I am getting stuck. Any idea will be appreciated.  thanks

I would just translate the plane so that the circle $ |z\minus{}i|\equal{}1$ goes to $ |z|\equal{}1$, then invert ($ z\to 1/z$) so that you have the unit disk, then Cayley transform (maybe inverse Cayley, which way is which again?) to the upper half plane.

okie, after translating , the new region is $ B\equal{}\{z : |z|>1 , Im(z)>\minus{}i\}$
then you take the inversion $ z\to \frac{1}{z}$
I am not sure how this method works since our region is $ B\equal{}\{z : |z|>1 , Im(z)>\minus{}i\}$ [b]NOT[/b] $ C\equal{}\{z : |z|>1 \}$? if you think it works please explain why? thanks

Oops. I completely missed the $ Im(z)>0$ condition.

thanks  Yury
Could you show me how to find the map $ e^{ \minus{} 2\pi/z}$?

Hint:
\[ \{z: |z \minus{} i| > 1, \mathrm{Im}(z) > 0\} \stackrel{ \minus{} 2\pi/z}{\longrightarrow} \{z: \mathrm{Im}(z) \in (0,\pi)\} \stackrel{e^z}{\longrightarrow} \{z: \mathrm{Im}(z) > 0\}\]


inequalities
email
Support
inequalities theorems

(I don't know if this is the right forum to post this in, but I couldn't think of a better one.)

I'm just starting to work with inequalities, but I enjoy them a lot. Are there any books you would recommend for me to work through to improve my inequality techniques? Any suggestions would be appreciated!

For inequalities, I like "Problem-Solving Through Problems", Loren C. Larson, which is a great source for problem solving in general:
[url]http://www.amazon.com/exec/obidos/tg/detail/-/0387961712/002-1025705-4852018?v=glance[/url]

You should also consult Kiran Kedlaya's notes, which are very good, on-line, and free:
[url]http://simo20020.tripod.com/inequalitiesnotes.pdf[/url]

I would strongly recomend the following books:

1.Old and New Inequalities by Titu Andreescu, Vasile Cartoaje, Gabriel Dospinescu and Mircea Lascu; GIL Publishing House see http://www.gil.ro

in this book you will find classic inequalities and brand new problems... some of which are very hard. The classic results have new solutions which will show the diversity of ideas pertaining to inequalities.

2.360 Problems for Mathematical Contests, by T. Andreescu, D. Andrica, GIL publishing house

3. M.O. Drambe, Inegalitati idei si metode, GIL Publishing House

4. M. Lascu, Inegalitati, GIL  PUblishing House

5. L. Panaitopol, V. Bandila,M. Lascu, Inegalitati, GIL Publishing House

Lagrangia, is there a way to buy that first book without knowing romanian? :)

Just wondering cuz I can't answer the question they ask to send :P

These books are in English, right? Also, I have the same question as Peter.

I think you can tell by the titles that 3,4,5 are in Romanian. Or maybe you weren't referring to the books listed by Lagrangia?

I was referring to the first book on Lagrangia's list. I guess http://www.gil.ro sells it only in Romanian?

[quote="Peter VDD"]Lagrangia, is there a way to buy [b]that first book[/b] without knowing romanian? :)

Just wondering cuz I can't answer the question they ask to send :P[/quote]

Yeah we're talking about the first one... unless you say the others are worth studying romanian :D

The books 1. and 2. are in English indeed. I think you should ask Mircea Lascu ([url=http://www.mathlinks.ro/Forum/profile.php?mode=viewprofile&u=168]username "Gil" on MathLinks[/url]) about buying them from abroad. He says he regularly visits Germany (the GIL publishing house cooperates with Springer), and on such an occasion I have got the books, but I don't know whether such a method works in Belgium...

  Darij

well they can always ship them... I don't think shipping costs are really high inside europe, unless it's a very thick book of course. :)

First of all I would like to thank you all for the interest in our books. GIL Publishing House is publishing books in Romania (romanian language) and the main subject is mathematics. Any book could be bought from GIL, it doese not matter the language (romanian or english). If we have the book on stock, we can sell it to you without no problems. All we need is your postal addres, that to be sent to gil1993@zalau.astral.ro , our e-mail address. Hope that you questions are clarified now. Have a good day. :)

I too am interested in buying Old and New Inequalities, but as I am in the US it is hard for me to get this book. I have sent two e-mails to the address you mentioned but I haven't gotten any response yet :?

I had commanded the book, but after some emails the replies stopped, and no matter how much I kept asking, no reply.

I'm still interested in this book, but I'm afraid I'll need to look for alternative distributors? Or is gil publishing back?

I sent a PM to Gil on the forum as well, and according to my PM window or whatever, it seems that he read the message (since the message only shows up under sentbox as opposed to outbox). However, there is no response as of yet. Anyone know of any other place where I can buy this book?

ebay, 2nd hand.

that's the only place I know and probably the one I'm going to use...

I just checked -- Ebay doesn't seem to have it...

not permanently. sometimes it does (I think I've seen at least 2 of them pass in total...)

But of course it would be more handy if Gil Publishing would answer messages instead of ignoring them :)

GIL Publishing House does only intern shipping for now. Our sales departmend for foreign countries will be available after 25 may. Please input your orders by mail to gil1993@zalau.astral.ro or gil@gil.ro. You can order from our 4 english books, or of course, from our romanian books (120 :) ). Please quit joking around with things like "finding the book on e-bay" or other things. I belive you all have heard about Springer. Do you think Springer has books on e-bay ? Well, we can`t compare to them at all, but what I mean is that each publishing house has its orders and deals them privatly. As for the shipping costs... the client supports the taxes. Input your orders on mail and we will talk more.

Hope to be helpful !

Does this mean we should send our orders via e-mail after May 25th if we are from a country other than Romania? In any case, I sent my order to both e-mail address just now...

[quote="Gil"]GIL Publishing House does only intern shipping for now.[/quote]Does that mean you only ship inside romania? If so, I don't see why it would be a 'joke' buying it on ebay or something?

Amazon doesn't have it, you don't ship international, so buying it second hand from e-bay is the only way left I have experience with, so the only way to get it... ? Or did I misunderstand somehow?

You are foreign (meaning that you are not from Romania), right ? If so, please state your orders on mail at gil1993@zalau.astral.ro or at gil@gil.ro. You will get an answer as soon as possible. Thank you for your interests !

The book of Sedrak'an and Avoyan is very excelent.

I recommend [i]The Cauchy-Schwarz Master Class[/i], by J. Michael Steele.  It is published by the [url=http://www.maa.org]MAA[/url].

i'm very like old and new inequalities . But i am in vietnam !!!!!!!!!!
do you have  old and new ineq in acrobat reader?

Isnt there any other pdf file to learn them.


solving the system of equation:
$ (i): \frac{3x}{x\plus{}1}\plus{}\frac{4x}{x\plus{}1}\plus{}\frac{2z}{z\plus{}1}\equal{}1$
$ (ii): x^3y^4z^2\equal{}\frac{1}{8^9}$
$ (iii): \sqrt{x}\plus{}\sqrt{y}\plus{}\sqrt{z}\equal{}\frac{3}{2\sqrt{2}}$
I have the proof but i need another please!

In (i) is it supposed to be $ \frac{4y}{y\plus{}1}$?

yes, i'm sorry.It's must be $ \frac{4y}{y\plus{}1}$

[quote="toanIneq"]solving the system of equation:
$ (i): \frac {3x}{x \plus{} 1} \plus{} \frac {4x}{x \plus{} 1} \plus{} \frac {2z}{z \plus{} 1} \equal{} 1$
$ (ii): x^3y^4z^2 \equal{} \frac {1}{8^9}$
$ (iii): \sqrt {x} \plus{} \sqrt {y} \plus{} \sqrt {z} \equal{} \frac {3}{2\sqrt {2}}$
I have the proof but i need another please![/quote]
 cauchy  9 numbers and use condition ii and iii
$ \sqrt[9]{(x\plus{}1)^3(y\plus{}1)^4(z\plus{}1)^2} \geq 9/8$
 last , Use Hoder's

Just looking at it one can see $ x\equal{}y\equal{}z\equal{}\frac{1}{8}$...

You know, just saying...  :ninja:


[quote="burberri4"][quote="makar"][quote="GameBot"]Two positive integers have a sum of 365. What is the smallest possible product they could have?[/quote]

As $ \ n\plus{}m\equal{} 365\implies 1\times 364\le nm\le182\times 183$

$ \implies$ smallest possible product $ \ 364$[/quote]

ACTUALLY i just had this question and came on forum to see how you would get the answer which is 264 and i dont understand it. I put 364 as well and it was incorrect. Anyone understand how you get 264?[/quote]

I think the answer in the system is wrong. To get the least product, you need the numbers to be the farthest away, and that is 1 and 364.


calculus
derivative
calculus computations

hey need help with this one.. thanks

Find the Millionth derivative of f(x)= xe^-x

Calculus is not really suppose to be in this forum.


geometry
parallelogram
trigonometry
ARML
rectangle
rhombus
similar triangles

This... is... slightly evil... I finally figured it out ~_-...

In $ \bigtriangleup ABC, AC\equal{}18,$ and D is the point on $ AC$ such that $ AD\equal{}5$.  Perpendiculars drawn from D to $ AB$ and $ CD$ have lengths of 4 and 5 respectively.  What is the area of triangle ABC?

[hide]Answer: $ \frac{360}{7}$.... [/hide]I think...

In parallelogram ABCD, the bisector of $ \angle ABC$ intersects $ AD$ at $ P$.  If $ PD\equal{}5,BP\equal{}6,$ and $ CP\equal{}6,$ what is the value of $ AB$?

[hide]Answer: 4[/hide] I cheated... using trig ~_-.

Here's an easy one for boosting self-confidence :)

The lengths of the sides of a triangle are 25, 29, and 36.  There is a point on the longest side of the triangle whose distance from the opposite vertex is 20.  What is the distance from this point to the midpoint of the shortest side?

[hide]Answer: $ \frac{25}{2}$[/hide]

wasn't the answer to #8 on ARML indiv. last year $ \frac{360}{7}$??

This problem was made... a long time before that

[quote="mathcrazed"]This... is... slightly evil... I finally figured it out ~_-...

In $ \bigtriangleup ABC, AC \equal{} 18,$ and D is the point on $ AC$ such that $ AD \equal{} 5$.  Perpendiculars drawn from D to $ AB$ and $ CD$ have lengths of 4 and 5 respectively.  What is the area of triangle ABC?

[hide]Answer: $ \frac {360}{7}$.... [/hide]I think...

In parallelogram ABCD, the bisector of $ \angle ABC$ intersects $ AD$ at $ P$.  If $ PD \equal{} 5,BP \equal{} 6,$ and $ CP \equal{} 6,$ what is the value of $ AB$?

[hide]Answer: 4[/hide] I cheated... using trig ~_-.

Here's an easy one for boosting self-confidence :)

The lengths of the sides of a triangle are 25, 29, and 36.  There is a point on the longest side of the triangle whose distance from the opposite vertex is 20.  What is the distance from this point to the midpoint of the shortest side?

[hide]Answer: $ \frac {25}{2}$[/hide][/quote]

[hide="1"]
That part above the upper left corner of the rectangle is 3
The part to the right of the lower right corner is 12
Then because it's a rectangle, the left side is 5 and the bottom side is 4
So the sides are 8 and 16.  The area is 64.

[/hide]

[hide]
Do a bit of angle chasing, call BC s, and you get $ AP\equal{}\frac{36}{s}$ so $ 5s\plus{}36\equal{}s^2$.

[/hide]

[quote="mathcrazed"]number 1 is wrong... and you should explain your solutions.[/quote]

I double checked them, and they're correct with my diagram.  Maybe you could post a diagram of your solution?

edit: oh dangit, i assumed ABC was right.  *goes back to fix*

Kind of hard to explain without a diagram...
[hide="1."]
Drop an altitude from B to AC.
On the left side is the 3-4-5 triangle with vertices A and D, and on the right side is the 5-12-13 triangle with vertices C and D.
Draw altitudes from both of these triangles to AC; find their lengths and the lengths from their feet to A and C.

Then, system of equations with the two sets of similar triangles formed from these altitudes; label the altitude of ABC as h and some random length that you don't know as x.
Solve to find the altitude to AC is $ \frac{40}{7}$ and the area of the triangle is thus $ \frac{360}{7}$
[/hide]

[hide="2."]
Firstly, $ APB$ and $ PBC$ are similar isosceles triangles.
Let $ x$ be the length of AB and $ y$ be the length of BC.
Then $ \frac {y}{6} \equal{} \frac {6}{x}$.

Also, if you draw a line through P parallel to AB, it splits the parallelogram into a rhombus and a smaller parallelogram.
It is clear that $ y \equal{} x \plus{} 5$ from this.

Substituting into the equation, we have $ \frac {x \plus{} 5}{6} \equal{} \frac {6}{x}$
Solving for $ x$, we have $ x \equal{} \boxed{4}$.[/hide]

[hide="3."]
The area of the triangle is $ 360$ by Heron's formula, which means that the desired point is the foot of the altitude from the opposite vertex.
Thus, it makes a right triangle with the shortest side with length 25, so the distance from it to the midpoint of the hypotenuse = $ \boxed{\frac{25}{2}}$.[/hide]


A certain piece of elastic breaks when it is streched to twice its unstretched length. At time $ t \equal{} 0$, all points are accelerated longitudinally with constant proper acceleration "$ a$" from rest in the unstretched state. Prove that the elastic breaks at $ t \equal{} \frac{\sqrt{3}c}{a}$.

could you be a bit more specific with the problem.
What do you mean by "proper acceleration"?
Is one of the ends of the elastic material fixed somewhere, is the fixing moving, or its stationary etc.etc....

Well this is a direct "lift" from the my book. Proper acceleration is constant aceeleration with respect to it's instantaneaous rest frame. I really don't understand why it would snap, if all points on the elastic are given equal accelerations. Surely every point follows the same path, and elastic stresses won't arise.

I thought then it was perhaps talking about the "observed" length. But that didn't help, because an inertial observor will see the thing contract...

all the distances remain the same with respect to the rest frame S of someone who's initially at rest with both dudes

in the instantaneous rest frames of both dudes, though, the observed length in S (which is remaining constant) is way too short and the length they perceive is totally longer

the rope is being strained pretty hard

then it snaps

draw a minkowski diagram

I don't understand MysticTerminator. I feel stupid.

The acceleration is with respect to it's [b]instantaneous rest frame[/b]. It is not constant acceleration as viewed by an inertial observor. i.e if it has at one velocity, an instantaneous rest frame $ S(x,t)$ and at another velocity rest frame $ S'(x',t')$ then:

$ \frac{d^2x}{dt^2}\equal{}\frac{d^2x'}{dt'^2}$

I assume, by the two dudes that you mean "world observors moving with each end of the elastic".

I think I understand your reasoning however, if the acceleration were constant as viewed by an inertial observor. I know that if this condition holds, then a rigid body should appear to get shorter (as measured in S), but the inertial observor in S notes that this is not happening - the apparent length appears the same. So of course the elastic must be getting longer...

Actually I will try the calculations using this assumption...

with respect to the initial observer the acceleration isn't constant but the point is the two dudes still seem to have the *same* acceleration at every time, so it looks like they have the exact same motion, just translated a certain length away from each other

I finally understand this problem! The reason I was getting confused was for a completely different reason.

I seemed to have convinced myself - before tackling this problem - that all points on a rigid body can be accelerated with constant acceleration with respect to it's instantaneous rest frame, and remain rigid. I realise now that this is not true, and that for a body to remain "rigid" under an acceleration, different points must undergo different accelerations. So I was confused why anything should change when elastic was inserted into the problem.

I only realised my mistake, when I read that last post, and understood it perfectly. And then tried to apply it equally to a rigid body, then realised that there was a contradiction.

Thanks very much!

Solution:

Let the instantaneous rest frame of the elastic be $ S'$ at any point in time. Let frame $ S$ be the inertial frame in which the elastic is initially at rest, and is moving along the $ x$-axis. Let $ u$ and $ t$ measure the velocity of the elastic, and the time elapsed in $ S$.

Using the acceleration transform:

$ \frac{d}{dt} (\gamma (u)u) \equal{} a$
$ \Rightarrow \gamma (u) u \equal{} at \plus{} c$

When $ t \equal{} 0,\,u\equal{}0 \Rightarrow c\equal{}0$

$ \Rightarrow \gamma(u) u \equal{} at \,\,\,\, (*)$

Let $ L$ and $ L_0$ be the respective lengths of the elastic, measured in $ S$ and $ S'$ respectively. We note, that $ L$ is constant.

$ L \equal{} \frac{L_0}{\gamma(u)} \Rightarrow L_0 \equal{} \gamma(u) L$

The elastic snaps when $ L_0 \equal{} 2L$ so $ \gamma (u) \equal{} 2$

$ \Rightarrow \frac{1}{\sqrt{1 \minus{} \frac{u^2}{c^2}}} \equal{} 2$
$ \Rightarrow \frac{u^2}{c^2} \equal{} \frac{3}{4}$
$ \Rightarrow u \equal{} \frac{\sqrt3}{2} c$

Substituting into $ (*)$:

$ 2 \cdot \frac{\sqrt{3}}{2} c \equal{} at$
$ \Rightarrow t \equal{} \frac{\sqrt{3} c}{a}$

yup that looks correct

minor point -- don't use c for constants of integration in relativistic physics :wink:


Over the past two months, Klebian and I were forced to lock many popular marathon threads because they disintegrated into spam. Here are some general rules you should follow when posting/creating in non-Mafia marathon threads.

[b]1. Read the rules.[/b] Without reading the rules in the original post, any new user can change the rules ever so slightly with his/her posts. There was actually one incidence where a marathon changed into another [locked] because the original rules weren't followed.

[b]2. Don't change the rules.[/b] Obviously, don't change the rules of the original post. Changing discredits the original rules and you're better off making a new thread.

[b]3. Don't revive old threads.[/b] If you want to continue a pre-existing game, just make a new thread, saying it's a revival in the subject description, as well as a link of the original thread and credit to the original poster in the post.

Finally, now spammers can not say they were not spamming.  :lol:

[quote="1=2"]I just realized that most of the marathons were/are pointless...[/quote]

They usually start off as good ideas, but then over months they spiral down to pointlessness and spam.

For example, "What is the avatar above you thinking?" started as a good idea to get opinions on one's avatar but then people started abusing what they could say to each other (sometimes reflecting what they thought of another user).

Without some degree of pointlessness in marathon threads, G&FF would cease to exist if not slow to a crawl.

Hah, most of  the forums by me get locked because i simply don't post anything good.I am offtrack i guess.

then post somethin useful once in a while at least =]

Same here, no spam
Guide:
If a post is spam, rate it 1
If a post is poor, rate it 2
If a post is average or good, rate it 3-4
If a post is really good, sticking to the topic, rate it 5-6.

[quote="rituraj007"]and how to decide wat is good???[/quote]

Well usually that is decided by my [biased] state of mind, whether or not I'm having a good day, and pretty much for the purpose of not completely throwing this forum into the bin.

Like, I banned all Hurt and Heals because people started mass-making them, which makes them annoying. Generally, they're decent topics to have in the Fun Forum, but the mass amounts of them were just plain annoying.

To build on the last post, this was turning into the Hurt & Heal Factory, to coin the phrase "spam and fun factory" used yesteryear.

And rating is even less popular than AoPSWiki. I don't think it even works in G&FF... And of course there are rating hounds, which suck your rating away. I think I've been a victim quite a few times.

i think that if a thread has to be locked or deleted than whoever was the reason it had to be locked or deleted should be suspended for a period of time that way if a thread deleted the reason it deleted will be less likely to spam again

I would like to point something out that people need to pay more attention to.

[quote="n0vad3m0n"][b]3. Don't revive old threads.[/b] If you want to continue a pre-existing game, just make a new thread, [u]saying it's a revival in the subject description[/u], as well as a link of the original thread and credit to the original poster in the post.[/quote]

I'm starting to have to edit in the word "revival" a lot. Please pay attention to this piece of instruction. Also, notice the last clause and credit the original maker of the thread.

A marathon is a thread in which a poster responds to a stimulus from the previous poster and provides a new stimulus for the next poster, or, in simpler talk, a thread where you answer something from the person before you and give something for the next person which happens to get on the thread to answer. Nearly all non-mathematical marathons belong here in the Fun Factory, as they serve no purpose beyond entertainment.

[quote="mathelete"]What is a marathon?[/quote]
A marathon is where you run 26 miles and try to get first place... oh wait you mean the other kind?
examples are the game of 2+2=5, All of the "rates", and The factory Medley.

[quote="Richard_Min"]Letti, you know better than to revive dead threads.[/quote]
[b]STICKIES CAN BE REVIVED. THAT IS THE EXCEPTION.[/b]

You should never yell like that, however.

Dude, your answering a 2 month old question, that was already answered.

[quote="n0vad3m0n"]Like, I banned all Hurt and Heals because people started mass-making them, which makes them annoying. Generally, they're decent topics to have in the Fun Forum, but the mass amounts of them were just plain annoying.[/quote]
[quote="1=2"]To build on the last post, this was turning into the Hurt & Heal Factory, to coin the phrase "spam and fun factory" used yesteryear.[/quote]
We don't need another one. I'm starting to see more Hurt and Heal threads come up.

Asian vs. Nonasian
Boy vs. Girl
Mac vs. Windows...

Eh, actually they're Tug of War threads.

Are Hurt/Heal threads allowed, as long as there is only one at a time?

Well, as long as the number of threads is controllable, it's okay.

[quote="bestmath"]This topic is kind of getting off topic.[/quote]

Indeed, your post existed.

Is there a limit to the munber of threads you can make? On both the Games and Fun Factory?


inequalities
trigonometry
inequalities proposed

Let triangle $ ABC$. Prove that

$ \sin\left(\frac{\pi-A}{4}\right).\sin\left(\frac{\pi-B}{4}\right).\sin\left(\frac{\pi-C}{4}\right) \ge\sin \frac{A}{2}.\sin \frac{B}{2}.\sin \frac{C}{2}$.

Thank.

hello, i will prove this inequality after a hint from Darij,
let $ x,y,z$ the angles of the given triangle then we have
$ \sin(\frac{\pi\minus{}x}{4})\equal{}\sin(\frac{y\plus{}z}{4})\geq\sqrt{\sin(y/2)\sin(z/2)}$
$ \sin(\frac{\pi\minus{}y}{4})\equal{}\sin(\frac{x\plus{}z}{4})\geq\sqrt{\sin(x/2)\sin(z/2)}$
$ \sin(\frac{\pi\minus{}z}{4})\equal{}\sin(\frac{x\plus{}y}{4})\geq\sqrt{\sin(x/2)\sin(y/2)}$
multiplying these inequalities we get the desired.
Because we have e.g. $ \sin(\frac{y\plus{}z}{4})^2\minus{}\sin(y/2)\sin(z/2)\equal{}\sin(\frac{y\minus{}z}{4})^2\geq0.$
Sonnhard.


i have a question about an ahmse problem
the problem is AHSME 1954 #33
A bank charges $6 for a loan of $120. The borrower receives $114 and repays the laon in 12 installments of $10 a month. The interest rate is approximately:
The Solution says the exact interest formula is complex. Approximately, he has the use of $59 for 1 year. 6*100/59=10+.
My question is how and where do you get $59.

No idea: I came up with 0.428% by soving for r in 114*(r+1)^12=120 but I have no idea what that solution means...

I believe they get the 59 by averaging how much the loan got him at any particular time through the year.  He has 114 to use in the first month, 104 in the second month, etc. to 4 in the final month.  Adding them up gives 12*(114+4)/2 = 6*118.  Averaging over 12 months gives 118/2 = 59.  I haven't seen interest problems worked this way before and am not immediately sure how significant this number is.

I think it's meaningful -- in general, when banks calculate interest on a savings account, say, they do it for the average amount of money in the account over the period of time.  So, my bank statement tells me money at the beginning of the month, money at the end, average amount of money over the month, and how much interest I've earned due to that average amount.

So how can we do the original problem and get an exact answer?

[quote="Fierytycoon"]Oh, right, I see.

By the way, where did the solution get 6*100/59=10+ from after the quantity $59 was derived?[/quote]
So I think the point is simply that $6 (the cost of the loan) is a little more than 10% of $59 (the average amount loaned over the whole year), so they are interpreting that to mean that you are being charged a little more than 10% interest on the loan of
$59.  Not a very well written question in my opinion.

--Dan

I know that we are not supposed to solve the question exactly, but if you wanted to, here is how you could.  Let r be the interest rate.  After k months (for each integer k from 1 to 12), we make a payment of 10 dollars.  The present value of that payment is 10(1 + r)<sup>-k/12</sup>.  The sum of those present values must equal 114.  Unfortunately, solving that equation means finding the root of a 12th degree polynomial.  Fortunately, we can find a solution numerically.  By using an iterative method, I found r was about 10.0088187%.  Alternatively, there are financial functions on many calculators and spreadsheets that will solve this interest equation for you.


Here's how to play...
Type a few lines (max is 5) of a song and everyone guesses. There will be four judges who come on AoPS often enough to see whether the answers are correct. One judge will announce the winner of each round.

RULES:
NO SWEAR WORDS!!!!

I'll be the judge for now (post if u want to be one)...here's the lyrics!

i dont mind spending every day
out on your porch in the pouring rain
look for the girl w/ the broken smile....

"She Will Be Loved"-Maroon5

"No foreign languages" is somewhat subjective since a good deal of people on this site aren't from the US or an english-speaking country.

Here we go:

"Hold my breath as I wish for death
Oh please God help me!"

oh i thought i erased that i'll edit it...

I'll judge. I'm on almost evey day.

Every Saturday Night,
I felt the fever go

i will judge

First song:

(It starts with) One thing
I dont know why
It doesnt eeven matter how hard you try
Keep that in mind I designed this rhyme
TO explain a due time

Anotehr one:

I walk a lonely road
the only one that i have ever known
dont knw where it goes
but its home t me and i walk alone

pretty simple...

@ mz94: 1st one: In the End by Linkin Park
2nd one: Boulevard of Broken Dreams by Green Day

[quote="alexhhmun"]"One" ---Metallica

Here's an easy one:
"For ten years we've been on our own
And moss grows fast on a rolling stone
But that's not how it used to be..."

Another different song:
"Remember Charlie,
Remember Baker
They left their childhood on every acre
And who was wrong? And who was right?
It didn't matter in the thick of the fight"[/quote]

Nobody's got mine yet.   :)

First one is American Pie. Everyone who's been to CTY knows that.  :P

That's why I said it was easy.   :)

Hint for the second one:  Vietnam.

"Good Night, Saigon"-Billy Joel

My next one:

"Screams break the silence
Waking from the dead of night..."

Ozzy Osbourne--Barking at the Moon

I tried to be perfect
It just wasnt worth it
I dont believe it makes me real

pieces- Sum41

[b]No more will my green sea go turn a deeper blue
I could not foresee this thing happening to you.
If I look hard enough into the settin sun
My love will laugh with me before the mornin comes.[/b]

One Step at a Time--Jordin Sparks

SnipedYou's is Highway Star--Deep Purple (?)

And do you ever lay awake at night?
And do you ever tell yourself don't try?
Don't try to let yourself down
And do you ever see yourself in love?
And do you ever take a chance, my love?

[quote="ernie"]the wheels of the bus go round and round! (easy)

AND BIG GIRLS DONT CRY!  :maybe:  (easier)

rubber ducky, ur the one! u make my bathtime, so much fun! rubber ducky, im awfully fond of u! (hmmm... :ewpu:)[/quote]

you serious?

wheels on the bus--idk
big girls dont cry--Fergie
rubber ducky song--Ernie from sesame street

do mine!

And do you ever lay awake at night?
And do you ever tell yourself don't try?
Don't try to let yourself down
And do you ever see yourself in love?
And do you ever take a chance, my love?

Everything's Magic? by Angels & Airwaves

Sat on the parkbench like bookends
A newspaper blown through the grass
Fall on the round toes
Of the high shoes

Old Friends (2:35) P. Simon

Three fingers on a swollen hand
beside a dented garbage can
a blind man staring
at something only he can see

idk

chinese song for chinese ppl:

(done in pin yin b/c i cant really type chinese here)
hao yi duo muo li hua...
(its really ezpz :blush: )

english song for english ppl:

There's someone in the world who I love,
There's someone there who I'll give up everything for,
But I can't find her,
Anywhere out,
So please show yourself and be happy...
(youll never guess this one, although youll probably guess why i did it)

4 the chinese one, it is called jasmine flower or somethin like that

[quote="crazychinesemaniac"]Buckethead-Three Fingers

Hehe...I feel like being evil, no one will guess this one.
Hint: NSYNC recorded the song under a different band name, SONG HAS NO NAME. Just give name of the "fake" band name.

I saw you last night at the spelling bee,
I knew right then that it was L U V,
I gotta spell out what u mean to me...[/quote]

still havent gotten this one yet :)

new song even though those aren't finished

I am a little bit insecure
A little unconfident
Cause you don't understand
I do what I can
But sometimes I don't make sense

Another one...
We're no strangers to love
You know the rules, and so do I...

You should know this one, especially if you have visited youtube and got annoyed.

Here's another (because I have no idea)

This was a triumph.
I'm making a note here-HUGE SUCCESS.
It's hard to overstate my satisfaction.
Aperture Science
We do what we must because we can.
For the good of all of us except the ones who are dead.

err no more new songs till we get previous like 4...

TheProdigy's is Linkin Park - Faint
MatthewL's is Rick Astley - Never Gonna Give You Up
herefishyfishy1's is Portal - Still Alive

New one:
"Sing once again with me
Our strange duet
My power over you
Grows stronger yet
And though you turn from me
To glance behind"

We're playing a medley from this musical (hint) in band, so I feel like I should post it here.

IRT sniped: Phantom of the Opera

New one:
"how He picked me up
and turned me around,
and set my feet on solid ground"


when the China TST was held, Hawk Tiger told us an inequality produced by himself: forall $x_{1},x_{2},\ldots,x_{n}$ such that $x_{1}+x_{2}+\cdots+x_{n}=1$ there is
$\sum_{i=1}^{n}\sqrt{x_{i}^{2}+x_{i+1}^{2}}\leqslant2-\frac{1}{2\sum_{i=1}^{n}\frac{x_{i}^{2}}{x_{i+1}}}$
And I found a stronger one
$\sum_{i=1}^{n}\sqrt{x_{i}^{2}+x_{i+1}^{2}}\leqslant2-\frac{1}{\frac{\sqrt{2}}{2}+\sum_{i=1}^{n}\frac{x_{i}^{2}}{x_{i+1}}}$
Both have beautiful solutions I think.

I have posted here.http://www.mathlinks.ro/Forum/viewtopic.php?t=133594
And I remmeber that which I give you  is
$\sum_{i=1}^{n}\sqrt{x_{i}^{2}+x_{i+1}^{2}}\leqslant2-\frac{1}{\frac{3}{4}+\sum_{i=1}^{n}\frac{x_{i}^{2}}{x_{i+1}}}$
Maybe the first one is too easy for Mathlinkers

You're right, and your inequality is pretty good!
OK, now I would post my solution in what you've posted.


Is there any way to get the root's of a polynomial using Newton's method if some or all of them are complex? Or is there some other, more appropriate method for finding root's of a polynomial?


modular arithmetic
combinatorics proposed
combinatorics

A horse chess are lay at a cell at edge of a chess board $ 4*50$. Prove that: it can't move over all cells of chessboard exactly $ 1$ time for each cell!

[asy]size(40);
draw((0,0)--(0,1)--(1,1)--(1,0)--cycle);
draw((0,1)--(1,1)--(1,2)--(0,2)--cycle);
draw((1,0)--(2,0)--(2,1)--(1,1)--cycle);
draw((0,2)--(1,2)--(1,3)--(0,3)--cycle);
label("1",(0,2),NE);
label("2",(1,0),NE);[/asy]

If the knight starts from $ \boxed{1}$ then it travels $ 3$ squares to get to $ \boxed{2}$, covering $ 3\plus{}1$ squares. After that in every move it will cover $ 3$ additional squares. Thus if we want the knight to move all over the chessboard with exactly once on each square then the number of squares must be $ 3n\plus{}1$ for some $ n$. But $ 4\times 50\equiv 1\times 2\equiv 2\pmod 3$. Hence such a configuration isn't possible.

That's not what one traditionally means when asking for a knight to visit every square.

[quote="nayel"][asy]size(40);
draw((0,0)--(0,1)--(1,1)--(1,0)--cycle);
draw((0,1)--(1,1)--(1,2)--(0,2)--cycle);
draw((1,0)--(2,0)--(2,1)--(1,1)--cycle);
draw((0,2)--(1,2)--(1,3)--(0,3)--cycle);
label("1",(0,2),NE);
label("2",(1,0),NE);[/asy]

If the knight starts from $ \boxed{1}$ then it travels $ 3$ squares to get to $ \boxed{2}$, covering $ 3 \plus{} 1$ squares. After that in every move it will cover $ 3$ additional squares. Thus if we want the knight to move all over the chessboard with exactly once on each square then the number of squares must be $ 3n \plus{} 1$ for some $ n$. But $ 4\times 50\equiv 1\times 2\equiv 2\pmod 3$. Hence such a configuration isn't possible.[/quote]

But I think if $ n$ odd then it is posible! Look at my picture with $ n\equal{}5$ it mean $ 4\times 5\equiv 2\pmod 3$
[img]http://i227.photobucket.com/albums/dd72/TPFC/chessboard.png[/img]

Yes I see my mistake, I'm sorry. Thank you.


What is the sum of the next three terms in the geometric sequence
1, -2, 4,...?

[hide]-8, 16, -32

I got those number from y = -2^(x-1) for every xth term.[/hide]

Yes, HSPotter just wrote a function for it.

huh? um...thats kinda confusing for me.  but yea i gess it works.


Let $<h_n>_{n\in N}$ be a sequence of positive rational numbers so that for all $n\in N$
\[ h_n = \frac{2h_{n-1}h_{n+1}}{h_{n-1}+h_{n+1}} \]
holds.
Prove that if the sequence has a member which is the square of a rational number, then it has infinitely many members which are the square of a rational number.

Denote $r_n = \frac{1}{h_n}$.  We have $r_n = \frac{ r_{n+1} + r_{n-1} }{2}$ so $r_n$ is an arithmetic progression.  Moreover, if $h_i$ is the square of some rational, then $r_i$ is also the square of some rational.

Suppose it has a common difference $d = \frac{n}{m}, (n, m) = 1$ and we have some $r_i = \frac{p^2 m}{q^2 m}, (p, q) = 1$, then the terms after $r_k$ are of the form

$r_{i + k} = \frac{p^2 m + kn }{q^2 m}$

We wish to show that infinite such numbers are the square of a rational.  Choose $k = am$ for some integer $a$.

$r_{i + k} = \frac{p^2 + an}{q^2}$

And we now only need to show $p^2 + an$ is square for infinite values of $a$ for a given $n$.  Suppose

$p^2 + an = s^2$

For some integer $s$.  Then

$an = (s + p)(s - p)$

For simplicity, let $n | (s-p)$ and let $\frac{s-p}{n} = d$ for integer $d$.  Then

$a = d(s + p) = d(nd + 2p)$

Now simply choose an arbitrary value of $d$ and it produces a square value of $p^2 + an$.

Hence, the sequence $r_k$ contains infinite squares if it contains at least one.  QED.


given $n>2$ points in the plane, not all on the same line, prove that exists one line that contains [b]exactly[/b] 2 of them

It's a famous problem. If no one solves it for a while i'll post the solution.

[hide]clearly there are lines containing at least two points. connect every pair of points, extened either side (i.e draw all lines with at least two points on them) and to prove that  there exists a line that does not have three points on it consider the point [u]closest[/u] to but [u]not on[/u] a line...[/hide]


algebra
polynomial
number theory solved
number theory

:D Has it been already solved  ?! :D
 :cool:

Using the binomial expansion, it is clear that $(k+1)^n = 1 + nk \mod [k^2]$, which reduces the writing  ;) .
Anyway, nice proof.

Pierre.

Thank you for your reply,everybody.
Here is my solution.

Since $x^n-n(x-1)-1=(x-1)^2Q(x)$,where $Q(x)$ is polynominal,

thus $\prod_{k=2}^{2005}\left[ k^n-n(k-1)-1\right]=(2004!)^2\prod_{k=2}^{2005}Q(k)$.    Q.E.D.

kunny


rotation
geometry
geometric transformation

A rod of mass $ 4m$ and length $ l$ is placed on a smooth floor as shown in the figure below. The lower end of the rod is given a negligible slight push towards left due to which the lower end of the rod moves towards left and collides perfectly inelastically with a step at point $ P$ and then the rod rotates about $ P$.
$ [l \equal{} (2\minus{}\sqrt{3})m]$

Now, answer the following questions:
$ \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{}$

$ \color{red} 1)$ The angular velocity of rod just before its lowest point collides with $ P$ is:

$ A)$ $ \sqrt{g\frac{48}{13}}$

$ B)$ $ \sqrt{g\frac{24}{7}}$

$ C)$ $ \sqrt{g\frac{21}{7}}$

$ D)$ $ \sqrt{g\frac{20}{13}}$

$ \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{}$

$ \color{red} 2)$ The angular velocity of the rod just after its lowest point collides with $ P$ is:

$ A)$ $ \frac{g}{4}$

$ B)$ $ \frac{g}{2}$

$ C)$ $ \sqrt{g\frac{21}{8}}$

$ D)$ $ \sqrt{g\frac{21}{32}}$

$ \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{} \minus{}$

$ \color{red} 2)$ The veocity of the top most point of the rod immediately after collision is:

$ A)$ $ \frac{g(2\minus{}\sqrt3)}{2}$

$ B)$ $ \frac{g(2\minus{}\sqrt3)}{4}$

$ C)$ $ \sqrt{g\frac{21}{8}}(2\minus{}\sqrt3)$

$ D)$ $ \sqrt{g\frac{21}{32}}(2\minus{}\sqrt3)$

[hide="My Approach:"]
I won't elaborate, I'm sure you'll all understand what I'm doing:

$ mgh \equal{} 0.5I\omega ^2
\\
\\
h \equal{} \frac{(2\minus{}\sqrt3)}{4}
\\
\\
\therefore \frac{l(2\minus{}\sqrt3)mg}{4} \equal{} \frac{1}{24}ml^2\omega ^2
\\
\\
\therefore \omega \equal{} \sqrt {\frac{6(2\minus{}\sqrt3)}{l}} \equal{} \sqrt{6g}$
[b]
Caution:[/b] Don't go by dimensional analysis.
[/hide]

I wrote this test and i made the same mistake,[hide="but ..."] $ mgh \equal{} 1/2Iw^2 \plus{} 1/2mv^2$[/hide]

[quote="Immanuel Bonfils"]
B

[/quote]

Yes, that answer is correct.

How did you proceed?

Find $ v$ in terms of $ w$ and apply energy conservation

Angular velocity relative to which origin? CoM?

Rajiv,vivek_n or someone else;
could you post the answer to 2)?
Cause I'm getting to a strange conclusion...

[quote="Immanuel Bonfils"]Angular velocity doesn't depend on the "pole'.[/quote]

Why does it not?

If A and B are points of the same rigid body, the angular rotation of A wrpt to B is the same as that of B wrpt A.

I think I've  got the two last questions, but I'll wait Dr. No's solutions...


A finite family $ F$ of intervals covering the interval $ [0, 1]$ is given. Show that there exists a subfamily of disjoint intervals of $ F$ such that the sum of their intervals is at least $ \frac12$.

First, prove a lemma: if three intervals share a common point, one is completely contained in the union of the two others.  Then, discard redundant sets.  Then split what's left into two subfamilies, $ F_{odd}$ and $ F_{even}$, of disjoint intervals that together cover $ [0, 1]$ and claim your prize.


Subject line says it all.

A reminder: please do [b]not[/b] ask when the scores will be available, when the USAMO qualifiers will be announced, etc.  We don't know (though see the AMC Director's announcement in this forum for some guidance), and repeatedly asking is just annoying.

Does this not conflict with the delay of the offical release of the answers (due to other country taking test)?

Not unless we get requested otherwise from the AMC.

All they said is that they're not going to post the official answers on their website.  They didn't say anything about us not discussing the problems and solutions.

To be perfectly honest, one (unnamed) non-US country cannot reasonably expect the entire World Wide Web (or even a significant subset of it) not to discuss a US-based contest after the period in which the contest is officially given has concluded.  We always wait an extra day (in this case, the Math Jam is Friday for a Wednesday contest) primarily as a courtesy in case something goes disastrously wrong with the official administration of the test, but we've already publicized the Math Jam for Friday, and we'd be very disinclined to change it at the last minute.

[quote="roadnottaken"]Can anyone post all of the AIME 2 questions?  I would like to take it as a practice test (for next year).[/quote]All of the questions are posted in their individual threads.  We are not permitted to post it all at once in a single document.

[quote="mysmartmouth"]You can go to the [url=http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=45&year=2007]Resources[/url] section, and view the problems there.[/quote]

But how can we do this if we aren't allowed to post the questions in a single document?

Yeah, it's impossible to keep the answers from spreading after the exam has already been taken. I was simply wondering if this was an overlooked conflict.

Let me clarify: we do have permission to set up the resources section.  We do not have permission to post the full test as a post on the forum.

Sorry for the poorly worded response. I was wondering about an overlooked conflict in my first post. My second post was just a confirmation of the impossibility of not spreading the answers. Sorry if I came off as argumentative. :wink:

[quote="DPatrick"]By the way -- don't forget our [url=http://www.artofproblemsolving.com/Community/AoPS_Y_Math_Jams.php]Math Jam[/url] tomorrow (Friday) at 7 PM Eastern / 4 PM Pacific, where we'll be discussing all 15 problems and solutions.[/quote]

When will you posting the transcript?


Post anytime you want.

I'll have to find one of myself.

I tried to do the same thing here:
http://www.mathlinks.ro/Forum/viewtopic.php?t=139835
but it failed.  :D

[img]http://www.pokemonelite2000.com/pictures/anime/anime197.jpg[/img]

Seriously ... figure out my anagram and then look for me in the AMC 10 perfect scores section from last year :D

lol, u are [hide]taken out by mod[/hide]

Yeah ... could you not post the answer online please?

[img]http://extreme.atheist.googlepages.com/5293099.jpg[/img]

Stumbled across this one after a long time. MAybe this is a funny. This was on one of the last days in school. The middle one is me! :rotfl:


algorithm
induction
probability
graph theory
expected value
combinatorics proposed
combinatorics

Given a graph G and positive integer n prove that we can remove at most 1/n of all edges of
G so that the resulting graph does not contain a complete subgraph of n+1 vertices.

Okay, so consider that the original graph is the complete graph on $ N$ vertices. What you want to do is pick at least one edge of each complete subgraph on $ n\plus{}1$ vertices , so this is a problem of transversal in hypergraphs. I don't know how to do it, but what I know is that since an edge is on $ N\minus{}2 \choose n\minus{}1$ complete $ K_{n\plus{}1}$ subgraphs, and there are $ N \choose n\plus{}1$ such subgraphs, you need at least $ {N \choose n\plus{}1}  / {N\minus{}2 \choose n\minus{}1}$ edges to do it. One can compute that
$ {N \choose n\plus{}1}  / {N\minus{}2 \choose n\minus{}1}\equal{}\frac{2}{n(n\plus{}1)} {N \choose 2}$, so at least there is no contradiction !

I wonder if a simple greedy algorithm wouldn't work. Or maybe someone could provide a theoretical existence result ?

Here's a solution:

Let e be the number of edges in the graph. We now have the following:

[b]Lemma 1[/b]
Given any graph G, there exists an n-coloring of the vertices of the graph such that the number of edges between vertices of the same color is at most e/n.

[b]Proof:[/b]
We proceed by induction on the number of vertices. In the base case of only one vertex the result obviously holds. Assume our graph G has k+1 vertices, and the result is true for any graph with k vertices. We let e be the number of edges in G. We create a new graph G' by removing one of the vertices, and let e' be the number of edges in G'. We now color the vertices of G' with n colors such the number of edges between vertices of the same color is at most e'/n. Now, let f be the number of edges connected to the vertex which we removed from G, so that f = e - e'. Letting f(i) denote the number of edges from the removed vertex to vertices with color i, we have f = f(1) + ... + f(n). It is then clear that $ \min (f(i)) \le f/n$. If we color the removed vertex with the color i for which f(i) is minimal, we see that the number of edges between vertices of the same color in G is $ \le e'/n \plus{} f(i) \le e'/n \plus{} f/n \equal{} e'/n \plus{} (e\minus{}e')/n \equal{} e/n$, which is what we wanted. Hence the induction step is done, and the result holds.

Given any graph G, we n-color it in the manner given in the lemma. We then remove all the edges between vertices of the same color. Now there cannot be any complete graph of n+1 vertices left, because by PHP any set of n+1 vertices must contain two vertices of the same color, and so cannot be complete.

[quote="Jorgen_VR"]Let e be the number of edges in the graph. We now have the following:

[b]Lemma 1[/b]
Given any graph G, there exists an n-coloring of the vertices of the graph such that the number of edges between vertices of the same color is at most e/n.
[/quote]

Here is a quick probabilistic proof for this lemma:
Color every vertex randomly (uniformly, and independently of each other) with one of the colors $ 1,\ldots,n$.
The probability that some fixed edge connects two vertices of the same color is $ 1/n$.
Hence the expected number of such edges is $ e/n$.
There exists a point in the probability space for which the number is at most  the expected number $ e/n$.
Done.

[quote="test20"][quote="Jorgen_VR"]Let e be the number of edges in the graph. We now have the following:

[b]Lemma 1[/b]
Given any graph G, there exists an n-coloring of the vertices of the graph such that the number of edges between vertices of the same color is at most e/n.
[/quote]

Here is a quick probabilistic proof for this lemma:
Color every vertex randomly (uniformly, and independently of each other) with one of the colors $ 1,\ldots,n$.
The probability that some fixed edge $ e$ connects two vertices of the same color is $ 1/n$.
Hence the expected number of such edges is $ e/n$.
There exists a point in the probability space for which the number is at most  the expected number $ e/n$.
Done.[/quote]

 :coolspeak:  :coolspeak:  :coolspeak:


geometry
circumcircle
power of a point
radical axis
geometry proposed

Let $ABC$ be a triangle with $AB\neq CB$. Let $C^{\prime}$ be a point on the ray $[AB$ such that $AC^{\prime}=CB$. Let $A^{\prime}$ be a point on the ray $[CB$ such that $CA^{\prime}=AB$. Let the circumcircles of triangles $ABA^{\prime}$ and $CBC^{\prime}$ intersect at a point $Q$ (apart from $B$). Prove that the line $BQ$ bisects the segment $CA$.

  Darij

$w =$ The circumcircle of $\triangle ABA'$
$z =$ The circumcircle of $\triangle CBC'$

$w \cap z =\{B,Q\}$

The point $A$ is out of the circle $z$, so the ray $AC$ intersects $z$ at a point $E$.

Similarly, the ray $CA$ intersects the circle $w$ at a point, $F$.

From the power of $A$ w.r.t. $z$ we have $AE \cdot AC = AB \cdot AC' = AB \cdot BC \ \ (1)$

From the power of $C$ w.r.t. $w$ we have $FC \cdot AC = A'C \cdot BC = AB \cdot AC \ \ (2)$

From $(1),(2)$ we get $AE=FC$

So, if $M$ is the midpoint of $AC$ then also $ME=MF$[hide="(simple)"]

If $AE\leq AM$ then $ME=AM-ME, MF=MC-FC$
If $AE>AM$ then $ME=AM+ME, MF=MC+FC$

In both cases we have $ME=MF$[/hide]

Now, the line $BQ$ is the radical axis of $w$ and $z$.

Also $M$ is on the radical axis, since $MA \cdot MF$ = $MC \cdot ME$  and we are done

Darij , could you please tell me what QEDMO means ?


I wonder if there is any "KUMON" like math software that students can practice with at home to improve speed in math. I wonder if any of you know about any such software.

For those of you, if any, who are not familiar with KUMON, it is a Japanese program, available in every major city, that trains students to increase their speed. You will usually see that majority of the students in those programs are of Chinese and Indian origin. I have seen several of these kids achieving perfect score in SAT math section long before their junior year! But it is quite an expensive program. A good software could achieve, I think, the same results.
Thanks.
Wazir

[quote="wazir"]You will usually see that majority of the students in those programs are of Chinese and Indian origin. I have seen several of these kids achieving perfect score in SAT math section long before their junior year![/quote]
Haha. That's me twice. Chinese and perfect score (only in math though). I don't know about KUMON software, but you can always practice with Countdown problems and stuff. :D