Combinatorial Number Theory
combinatorics
partition
Coloring
IMO Shortlist

A set of three nonnegative integers $\{x,y,z\}$ with $x < y < z$ is called [i]historic[/i] if $\{z-y,y-x\} = \{1776,2001\}$.  Show that the set of all nonnegative integers can be written as the union of pairwise disjoint historic sets.

Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=15623]introduction for the IMO ShortList/LongList project[/url] and regarding[url=http://www.mathlinks.ro/Forum/viewtopic.php?t=15623]solutions[/url]  :)

Just do it.

We partition the nonnegative integers into three sets X, Y and Z by taking disjoint historic triples {x,y,z} x<y<z and putting x into X, y into Y and z into Z according to a simple algorithm. We also keep track of a set S which is the set of nonnegative integers not yet in X,Y or Z. The algorithm is as follows:

i) Take the least element of S, x, and put it into X (so remove it from S). We also put x+1776+2001 into Z.
ii) If x+1776 is in S, we put it into Y. If x+1776 is no longer in S, we put x+2001 into Y instead.
iii) Return to step (i), having removed another historic triple from S.

Since we keep taking the least remaining element of S, it is clear that if such an algorithm succeeds, we have put every integer into precisely one of X,Y and Z once, which is equivalent to having partitioned the integers into historic triples.

Step (i) will clearly succeed, because x is in S by definition, and x+1776+2001 must be in S, as it cannot yet be in X (being bigger than x), or Y (being bigger than x+2001) and can only be put into Z by this value of x.

Step (ii) must also succeed. Suppose it doesn't (noting that for x<1776 it will obviously always work). Then x+2001 must be in Z. But this implies that x-1776 was placed into at some point X. At the time this happened, x should have been placed into Y, but by virtue of its being in S, it isn't already in Y, so this is a contradiction. Thus step (ii) succeeds also, and the algorithm works.

We use the following algorithm: Let $a$ be the smallest integer that has not been put in a set. If $a+1776$ has not been put in a set make the set $\{a,a+1776,a+3777\}$ and otherwise make the set $\{a,a+2001,a+3777\}$. Suppose that this fails at some point and we can make neither of those sets. This would mean that $a+2001$ was already in a set. It cannot be the least element of a set because otherwise we would have made a set with $a$ as the least element instead when we first put $a+2001$ in a set. If $a+2001$ is the middle element of a set then the least element has to be $a+225$ since $a$ is not in a set yet, but this would be the same contradiction as $a+2001$ being the least element. This means that $a+2001$ is the largest element of its set, so the least element would be $a-1776$. But then we would have made our middle element $a$, a contradiction. Hence, this algorithm works and we are done.

So obviously we are going to have two types of historic sets:
$$\{x,1776+x,3777+x\} \; (I)$$
$$\{x,2001+x,3777+x\} \; (II)$$
so obviously we don't want to end up in a situation such that all the points except one in the set of $\mathbb{Z}_{\geq 0}$ are covered at all.So we need to devise an algorithm such that we don't get into that position.

[b][color=#f00]Algorithm[/color][/b]
The algorithm, takes the smallest number now covered by any of the sets. Use type $I$ if possible, if not then use $II$.
To prove that this works we use contradiction.
Suppose this fails, so let $x_i$ be the $i$-th turn.We say that the algorithm has failed on the $(n+1)$-th turn. Where it failed must have been at $x_{n+1}+2001$ or $x_{n+1}+1776$, since $x_{n+1}+3777$ hasn't been covered at all.Furthermore $x_{n+1}+b$ must have been the largest members of their respected set.So by backtracking we have that:
$$x_{n+1}+2001-3777=x_{n+1}-1776 \; - \; \text{minimal element of set}$$
But notice how then $x_{n+1}$ would have been covered by our algorithm.Thus a contradiction is taking place here.
For the case of $x_{n+1}+1776$, we also get a contradiction.

Needless to say, the flavortext didn't age well.

Call an element [i]clogged[/i] if it's in a historic set and [i]unclogged[/i] otherwise. We use a greedy algorithm, where on the $i$th step, we construct a new historic set $H_i$ with $x$ as the smallest unclogged element, $y$ as $x+1776$ if it's unclogged and $x+2001$ otherwise, and $z=x+3777$. I claim that it will not terminate.

Suppose FTSOC that on some turn, both $x+1776$ and $x+2001$ are clogged. Note that $x+2001$ must be a $z$ element by size, which means that either $x$ or $x+2021-1776$ is clogged as an $y$ element. The former is obviously impossible, and in the latter case, $x$ must have been clogged in the first place.

Let $1776=a,2001=b$. Consider the following algorithm: consider a set $S$. Let $m$ be the smallest nonnegative integer not in $S$, then let $S$ be $S\cup \{m,m+a,m+a+b\}$ whenever possible, and let $S$ be $S\cup\{m,m+b,m+a+b\}$ if not possible, and we call $m$ an operator.

We claim that every point, one of the two historic sets above will be available. First, we take care of $m+a+b.$ Note that if $m+a+b$ is in the set, then there must've been an operator that is at least $m$. However, that raises a contradiction because if a number larger than $m$ is used as an operator, then by then $m$ must have been in $S$ already, but now that we are using $m$ as an operator, $m$ must not have been in $S$.

Now, if $m+a$ is unavailable, then either $m+a-b$ was an operator before or $m-b$ was an operator before. If $m+b$ is unavailable, then $m-a$ was an operator before. Since $m$ is currently being used as an operator, the historic set associated with $m-a$ is $\{m-a,m+b-a,m+b\}$, but the set with $m+b-a$ is only used when $m$ is unavailable! Obviously this cannot be the case, so we're done.

We provide an algorithm that generates sets that cover any nonnegative integer eventually. Call a historic set an $\alpha$ set if $y-x=1776$ and $z-y=2001$. Similarly, call a historic set a $\beta$ set if $y-x=2001$ and $z-y=1776$.

Our algorithm first covers $0$ with an $\alpha$ set, then repeatedly tries to cover the lowest uncovered number with the same type of set until the $x$ of the new set has to be more than one greater than the $x$ of the previous set, then it switches to the other type of set. If at one point, the lowest uncovered number is greater than any covered number, restart by covering the lowest uncovered number with an $\alpha$ set.

Now, we will prove that our algorithm works. When the first $1776$ $\alpha$ sets are made, there will be a gap between the largest $y$ and the smallest $z$. When we start to use the $\beta$ sets, note how the previously largest $y$ and the previously largest $z$ are now one-upped by the $x$ and $y$ in the new $\beta$ set. This continues until a new gap is formed between the largest $y$ and the smallest $z$, and the algorithm is continued. If at any point the gap doesn't exist anymore, we can simply restart the algorithm. Now, we note that the $x$ and $z$ cannot possibly clash($z$ is supposed to always be $1776+2001$ above $x$ which increases every time), and $y$ cannot clash because it one-ups the previous largest $z$. QED.

Note that a historic set is either in the form $\{x, x+1776, x+1776+2001\}$ (which we will call a 1776 set) or $\{x, x+2001, x+1776+2001\}$ (a 2001 set).

We can use the following algorithm to achieve this task:
We let $x$ be the smallest number not yet covered. If none of the numbers in the 1776 set have been covered already, then we use a 1776 set, otherwise we use a 2001 set.

Now we prove that this algorithm works. We prove that if the 1776 set does not work, then the 2001 set will always work.
Assume for the sake of contradiction that the 2001 set does not work.
Clearly the $x$ element can't have already been covered.
If the $x+1776+2001$ element has been covered, then that means that on some previous step, we either used the 1776 set on $x+2001$ or the 2001 set on $x+1776$. However, this is impossible as $x < x+1776 < x+2001$.
If the $x+2001$ has already been covered, then either we used the 1776 set on $x+2001-1776$, or we used any set on $x-1776$. Clearly the first one is impossible as $x+2001-1776>x$. Now we consider the second case. If we used the 1776 set on $x-1776$, then it would imply that we would have already covered $x$, a contradiction. If we used the 2001 set, then that means that some element in the 1776 set was already covered. If $x+2001$ was already covered, then this implies that $x$ was already covered, contradiction. Otherwise, this implies that $x$ was already covered, another contradiction.

Therefore, a situation where both sets don't work, and the algorithm always works. $\square$

We claim that using the following algorithm we can cover the postive integers:
-Find the lowest positive integer $x$ that hasn't already been covered.
-Let $y$ be the lowest if $x+1776$ and $x+2001$ that isn't covered.
-Let $z$ be $x+3777$.
-Then, add the triple $\{x, y, z\}$.

Assume towards a contradiction $x+2001$ is already covered. It can't be the 1st number in its triplet, since it's higher than $x$ and the triplets are added in strictly increasing order based on the 1st number. For the same reason, it can't be the 2nd number in its triplet. So, it is the third in its triplet. The first must be 1776. However, then, because $x$ has not yet been covered, when this triplet was created, $x$ would've been made the 2nd number, a contradiction. So, the 2nd step must be possible.

By similar logic, if $x+3777$ is already covered, then it must be the 3rd in its triplet. However, then $x$ would be the first, a contradiction.

So, we can continue this procedure indefinitely and cover the positive integers. We can flip it to cover the nonpositive integers. So, we can cover all integers.

dont like bashy stuff like this
silly from the aime

x,y,z=x (call it 1st element),x+{1776 or 2001} (second elements, where 1776 or 2001 is two options), x+1776+2001
Clearly the optimal strategy is to cover the smaller numbers (because why would you skip and go to larger? That just plugs your historic sets possible)
Now we show that the algorithm choosing the smallest number not used and use the set with smaller sum if possible, use the larger if not. We prove that this works. Suppose at x_n you cannot cover it. This means either both of the second elements are covered or the largest is. Clearly the largest is not by our algorithm of doing small first, so both x+1776 and x+2001 must be covered. x+2001 must be the largest number in its set (it can't be n+1776, and can't be n), hence the smallest number in this set must be x+2001-2001-1776. However, x_n is not covered, hence x_n-1776,x_n,x_n+2001 must have been used (smaller set). Hence, contradiction. $\blacksquare$


Let ABCD be a convexe quadrilateral inscribed in the circle with the diameter [AD]. I note the intersection I between the lines AC and BD. Construct the points M of [AB] and N of [CD] for which $I\in MN$ and the length of the segment [MN] is minimum.

[b]Where find I some information about it ?. [/b][u]Please, help me ![/u]
[I learn of it from sir Woulgar (Philo's line)].

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

This line is called Philo line.   It was done quite some time ago, and no wonder
     that you do not remember the solution.

     W.

I beg you pardon, Woulgar ! What is happened wrong ?


A stone is put on a vertex $ A_0$ of a regular triangle $ A_0A_1A_2$. When the stone is put on the vertex $ A_i\ (i \equal{} 0,\ 1,\ 2)$, thrown a dice, if the outcome of even appeares, the stone is moved to the vertex $ A_{i \plus{} 1}$, if odd, the stone is moved to the vertex $ A_{i \minus{} 1}$. Note that $ A_3 \equal{} A_0,\ A_{ \minus{} 1} \equal{} A_2$. After repeating this procedure $ n$ times, let denote the probabilty $ p_n$ such that the stone is on the vertex $ A_0$.

(1) Find the relation of $ p_{n \plus{} 1}$ and $ p_n$.

(2) Find $ p_n$.

If it does(sorry for double posting) then let [b]A1_n[/b]denote the probablity that the stone is on [b]A1[/b] after n dice throws and [b]A2_n[/b] denote the probablity that the stone is on [b]A2[/b].Then the stone can be put in [b]A0[/b] if the stone was on [b]A1[/b] or [b]A2[/b] in the previous step in exactly 3 ways.Using recursion thus and then using generating function or something else we can find [b]P_n[/b] in closed form.... :sleeping:

This question is addressed in [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=125811]this thread[/url]

Except it's a bug instead of a rock  :)

Techniques used in that thread:

[Post 04] Recursion
[Post 05] Direct combinatorics
[Post 10] "Roots of unity filter"

[quote="Cronus"]Does [b]P_n[/b] denote the probablity of the stone...after n dice throws?[/quote]

Sorry, I have just edited.

kunny

What is roots of unity filter??I know what roots of unity are but i am not comfortable at using them?Can anyone kindly help me?
Thanks in advance.

See here. You van find the topic in Page 3.

[url]http://reflections.awesomemath.org/2006_2/2006_2_zach.pdf[/url]

Regrettably, I can help you, because I did knew first roots of unit filter.  :(

[quote]Regrettably, I can help you, because I did knew first roots of unit filter.
[/quote]
Didn't understand what you meant.

I didn't know that so far. This is the first time.

[quote="Cronus"]Wow.that's sort of cool. :cool: Thanks again.Do you know a book that can help me learn more about this from the basics? :?:[/quote]

I don't know about a book, but see #17 and #18 [url=http://www.seansoni.com/solved.html]here[/url].  Those are two problems that also use roots of unity filtering.

In #17, if you don't know generating functions, it doesn't really matter.  The real problem starts after the generating function part is over... just start reading from the first line of the solution and you'll see.

#18 is a combinatorical application of the same concept, and it may actually be a bit easier to understand, and hence a better starting point.

Hmm... The link seems to have broken rather quickly.

For some reason I can't edit my post...

http://www.contestmath.com/solved.html


calculus search geometry perimeter rectangle

Prove, if $ax+by+cz=m$ for $x,y,z,a,b,c,m \geq 0$
then the maximum of

$\displaystyle P(x,y,z)=x^d y^e z^f$

is
$\displaystyle \frac{d^d e^e f^f m^{d+e+f}}{a^d b^e c^f (d+e+f)^{d+e+f}}$

Actually ill make it easier (as its extremely difficult): $d,e,f$ natural numbers.
Come on people, impress me!

Just realised i used $f$ twice! Whoops :blush:

Not sure if help is needed or it is an excercise .. anyway  solution is straight forward:
[hide]Try to maximize  $ln f$ and  equate zero to drivetivs wrt $x,y,z,\lambda $ in  (Langrange Multiplier etc..)

$d \ ln \ x + e \ ln  \ y + f \ ln \  z -\lambda (ax +by +cz -m) $
so $x = d/(a\lambda) , y = e/(b\lambda) , z = f / (c \lambda) $ where $ \lambda = (d+e+f)/m$
and you get your result when you substitute in $f = x^d y^e z^f$[/hide]

Could you kindley explian LeGrange Multipliers? I have  a non-calculus that can be used for all positive reals d,e,f.... But you seem to have half that in your second part, witht the lambda. Otherwise go on ye mad thing! It was an already solved problem, just hoping someone would find a different solution, and low and behold! :)  :)  :)

Hello - I have used calculus. For Langrange method  you can look at any standard text or  link say:
[url=http://mathworld.wolfram.com/LagrangeMultiplier.html]From mathword[/url]
or [url=http://en.wikipedia.org/wiki/Lagrange_multipliers]wikipedia[/url]
Or
 [url=http://www.google.com/search?hl=en&q=lagrange+multiplier&btnG=Google+Search]google can be used too ..[/url]
Hope that helps.

Ok thanks cool. Our lecturer said there was a standard way of doing it with calculus, just for a laugh (!) see if you can do it without calculus! (if you could be bothered!) This is already a generalisation, see if you can prove the ultra-generalisation for more than 3 numbers! And what if your given say $ax^2 + by +cz=m$? Millions of things to be doing!

Hi, yes with calculus it's just a few seconds work. Without  calculus it is still  intutivly obvious, if one is familiar with such  facts  as that given a fixed perimeter, the square is the rectangle with maximum   area. Or in general (for +ive real values) given
$x+y+z+\dots = constant$  maximum value of $xyz \dots $  occurs when $x=y=z \dots$ Here you have $ax+by+\dots $ instead of $x+y+\dots$ and you have powers of $x,y,z etc$ but that is just a scaling factor  and you can   guess the max value almost right away.

[hide]For example: if you use $(ax/d)$ with weight $d$, $(by/e)$ with weight $e$ and $(cz/f)$ with weight $f$ and apply
$GM \le AM$  we have:
$ ((\frac {ax}{d})^d \cdot (\frac {by}{e})^e \cdot (\frac {cz}{e})^f)^{\frac {1}{d+e+f}} \le \frac {d(ax/d)+e(by/e)+f(cz/e)}{d+e+f} = \frac {m} {d+e+f} $
So
$x^d y^e z^f \le  \frac { d^d e^e f^f  m^{d+e+f}}{a^d b^e c^f (d+e+f)^{d+e+f}}$
[hide]it is easy to expand it to more than three variables ..etc .. Neither the case like $ax^2+\dots $ wll make much difference .. just call $w=x^2$ and  form of $f$   will remain the same.....[/hide]
[/hide]

Yes... thats how i got it. BTW, what is the defination  of the AM-GM with weights? I dont actually know it... i solved this the hard(er) way.


Three cards from a standard deck are dealt. What is the probability that the first is a heart,
the second is a spade, and the third is another heart?

@Shkakthi S
I don't think you're supposed to post your own problems here...


Has anyone seen the AMC study guide and web study aid that is new this year?

Can you post a link to it? Or give directions on how to get a copy of it?

It has to be order through AMC, I was wondering if it was worth the $22 it cost.  It is suppose to be a study guide and have some web problems.

Can you provide a link so others can see what you are talking about? Where on the AMC site do you order from?

[url=http://www.math.unl.edu/~amc/registration/start12.php]Here[/url] is the web site, it is listed in the registration part but I think anyone can order it.

The document you are referring to is the AMC 10/12 Math Club Package.  It is a booklet aimed at teachers who want to start or sustain a school math club.  The contents are: tips for teachers about starting a club, an annotated bibliography of books with advanced and enrichment topics, a similar list of web sites, some pages of math formulas and theorems, and 50 worked problems from prior AMC contests, intended for club or classroom presentation uses.

I think that anyone reading the AoPS forum would already be familiar with this material.  To be honest, I think you would be better off purchasing past copies of the AMC contests, the Contest Problem Books from the MAA, or of course Art of Problem Solving.

Steve Dunbar
AMC Director


inequalities
search
inequalities unsolved

Let $ x, y, z$ be real numbers such that $ x\plus{}y\plus{}z\equal{}xy\plus{}yz\plus{}zx$. Find the minimum of :
$ \frac{x}{x^2\plus{}1}\plus{}\frac{y}{y^2\plus{}1}\plus{}\frac{z}{z^2\plus{}1}$

Sorry if it had already be posted, but I didn't find it.  :)

This is Brazilian Math Olympiad 2008, Problem 3
The answer is $ \frac{\minus{}1}{2}$

[quote="Thomas B"]Let $ x, y, z$ be real numbers such that $ x \plus{} y \plus{} z \equal{} xy \plus{} yz \plus{} zx$. Find the minimum of :
$ \frac {x}{x^2 \plus{} 1} \plus{} \frac {y}{y^2 \plus{} 1} \plus{} \frac {z}{z^2 \plus{} 1}$

Sorry if it had already be posted, but I didn't find it.  :)[/quote]

See here:http://www.mathlinks.ro/Forum/viewtopic.php?search_id=1189594937&t=235748


inequalities
function
symmetry
geometry
geometric transformation
calculus
derivative

I 'm sure that this one use Cauchy but I didn't figure out how to transform it properly.

a/(b+c+1) + b/(a+c+1) + c/(a+b+1) + (1-a)(1-b)(1-c) <= 1

With a,b,c belong to [0,1]

Hmmm... I think you can just be like hold a constant; fix b+c. Then show b = c.

$f(a,b,c)=\frac{a}{b+c+1}+\frac{b}{a+c+1}+\frac{c}{a+b+1}+(1-a)(1-b)(1-c)$
is convex is all variables, so the function is maximum at the extreme points only. By symmetry we only have to examine the following combinations: (0,0,0), (0,0,1), (0,1,1), (1,1,1).
$f(0,0,0)=1$
$f(0,0,1)=1$
$f(0,1,1)=1$
$f(1,1,1)=1$
For all other values of $a, b, c$, $f(a,b,c)<1$

Engel has the same or a very similar problem with this solution, but I forget whether it was also solved with Cauchy.

[quote="litoxe2718281828"]$f(a,b,c)=\frac{a}{b+c+1}+\frac{b}{a+c+1}+\frac{c}{a+b+1}+(1-a)(1-b)(1-c)$
is convex is all variables[/quote]

I've seen a similar argument used by Engel, and I was wondering what the easiest way to actually demonstrate this convexity is?  Both for this problem and in general.

If the function is easy, you often can determine the convexity without calculus. In this case, the function is symmetrical so you just have to investigate it for one variable, say a, and keep the other variables constant. The first and last term are lines, which don't affect the convexity. Second and third term are 1/a (after translation and multiplied by a constant, which again don't change the convexity), which are convex, so the entire function is also convex.

But for a formal proof, finding the sign of the second derivative is the easiest way.

Oh, I didn't think it was in a competition.  That's why it is hard.


Hello to all you new 2009 Jenks Mathletes! :lol:  :clap:


I thought this might be interesting.  I thought of it when looking at inequalities, but I don't know if there's a solution.  Though for all I know it might be easy (I can't do it).

Find all $ r$ such that for $ x, y, z \in \mathbb{R}^{+}$,

\[ xyz=1 \implies \sum_{\text{cyc}}\left(\frac{2}{1+x}\right)^{r}\le 3\]

Actually, this is not a new problem. We have the following general result

If $ a_{1}a_{2}...a_{n}=1$ (they are positive) then

\[ \frac{1}{(1+a_{1})^{k}}+\frac{1}{(1+a_{2})^{k}}+...+\frac{1}{(1+a_{n})^{k}}\ge \min(1,\frac{n}{2^{k}}).\]

[quote="K81o7"][quote="hungkhtn"]Actually, this is not a new problem. We have the following general result

If $ a_{1}a_{2}...a_{n}=1$ (they are positive) then
\[ \frac{1}{(1+a_{1})^{k}}+\frac{1}{(1+a_{2})^{k}}+...+\frac{1}{(1+a_{n})^{k}}\ge \min(1,\frac{n}{2^{k}}). \]
[/quote]

What about an upper bound?  Is the upper bound the maximum of those two?[/quote]

No, I think actually, it is

\[ \frac{1}{(1+a_{1})^{k}}+\frac{1}{(1+a_{2})^{k}}+...+\frac{1}{(1+a_{n})^{k}}\le \max(n-1,\frac{n}{2^{k}}). \]

Let consider problem of minimum, k8107  :blush: I think it is very nice.


modular arithmetic
number theory unsolved
number theory

assume that $p$ is a prime number
show that in any $p+1$ numbers like $a_1,...,a_p_+_1$:
$\exists i,j : \frac{a_i}{(a_i,a_j)}\geq p$ :?:

I assume they are meant to be distinct.

[hide]Let $p^n$ be the largest power of $p$ that divides all of the $a_i$s.  Then we define $b_i = \frac{a_i}{p^n}$.  Notice that $\frac{b_i}{(b_i,b_j)} = \frac{a_i}{(a_i,a_j)}$  Furthermore, we can conclude there must be some $b_i$ that is not divisible by $p$ in this case.  Now let us assume that another $b_j$ is divisible by $p$.  Then clearly $\frac{b_j}{(b_i,b_j)} \ge p$.  Now let us assume that there are no numbers divisble by $p$.  Since there are $p$ congruence classes in mod $p$ and there are $p+1$ numbers, we know that we have $b_i \equiv b_j \pmod p$. WLOG $b_i > b_j$. Thus, we know that $b_i-b_j = pk$.  Thus $gcd(b_i,b_j)|pk$, however $p$ doesn't divide $b_i$, so $gcd(b_i,b_j)|k$.  Since $b_i > pk$ and $gcd(b_i,b_j) \le k$, we can conclude that $\frac{b_i}{(b_i,b_j)} \ge p$[/hide]


A barn with a roof is rectangular in shape, 10 yd. wide, 13 yd. long and 5 yd. high.  It is to be painted inside and outside, and on the ceiling, but not on the roof or floor.  The total number of sq. yd. to be painted is:

(A) 360
(B) 460
(C) 490
(D) 590
(E) 720

[hide]
the area of the ceiling is $13 \times 10$, which is $130$.
Since the walls are painted both inside and outside, its going to be $4(13 \times 5) + 4(10 \times 5) = 260 + 200 = 460$.
Thus, the total area that is going to be painted is $130 + 460 = 590$, which is $d$.
[/hide]


[quote="mdk"]What is the largest cardinality of a set S of natural numbers between 2 and 120 such
that each pair of numbers in S are coprime, but [color=red]no element of S is coprime[/color]?[/quote]
Maybe you meant "no element of $ S$ is prime", didn't you?

I will use s.tringali's approach.

I didnt solve the problem, yet, but I got close (I think).

[b]Part 1:[/b] Let $ S$ be a set of integers between $ 2$ and $ 120$ which is the largest subset which can be chosen so that any two are coprime?

[b]Part 2:[/b] Let $ S$ be a ser of integers between $ 2$ and $ 120$ which is the largest subset which can be chosen so that any two are coprime with the condition that none are prime powers.

There are $ 30$ prime from $ 2$ to $ 120$, [url=http://www.research.att.com/~njas/sequences/A000040]see here[/url].

Now for every subset, say for example, $ \{ 4, 25, 36\}$ we will assign sets for each number in the set. The corresponding set will be the set of all prime divisors of that number. So,
$ 4\implies\{2\}$
$ 25\implies\{5\}$
$ 36\implies\{2,3\}$
Now if any of these sets have a non-trivial intersection then we found two numbers that arent relatively prime. In this example it occurs between $ 4$ and $ 36$.

From here we can answer [b]part 1[/b]. Let $ T$ be a subset of $ S$ of positive integers. For each $ t_{i}\in T$ we assing a set, the set of all prime divisors of $ t_{i}$. If any of the assigned sets intersect non-trivally (non-empty) then there are two numbers that have are common prime divisor, and so they arent coprime. So if we chose $ 31$ numbers by pigeonhole two sets must intersect for there are $ 30$ primes. Hence, the only possiblity is that $ 30$ is the [i]largest[/i] possible subset for [b]part 1[/b]. Indeed it is, if $ T$ is the set of those primes, then each two are coprime.

Now lets do [b]part 2[/b]. Since each element isnt a prime power it means it has [i]at least two divisors[/i]. So the assigned sets have at least two elements. By pigeonhole it means if we have $ 16$ sets then there are at least $ 32$ numbers which must be common to both sets. So they cant be coprime. It remains to find an example with $ 15$ non-prime non-prime power elements all of which are coprime, to show maximality. Anyone wanna try?

[quote="mdk"]What is the largest cardinality of a set S of natural numbers between 2 and 120 such
that each pair of numbers in S are coprime, but no element of S is coprime?[/quote]

[hide="A simple solution"]None is prime, so each has at least two prime divisors (maybe the same), and so at least a prime $ <11$ since $ 11*11>120$. But we have just 4 primes in $ [2,11)$ : $ 2,3,5,7$
Since each are coprime and so none may have the same prime divisor $ <11$, we have at most 4 such numbers. And we can have 4 : e.g.  $ \{4,9,25,49\}$

And so the answer is $ 4$.
[/hide]

I really like your solution Patrick, very elegant and nice.


geometry
parallelogram
circumcircle
perpendicular bisector

1. Prove that if a quadrilateral is orthodiagonal, then the midpoints of its sides are the vertices of a rectangle.

2. Let $ ABCD$ be a parallelogram of area $ 10$ with $ AB \equal{} 3$ and $ BC \equal{}5$.  Locate $ E$, $ F$, and $ G$ on segments $ AB$, $ BC$, and $ AD$, respectively, with $ AE \equal{} BF \equal{} AG \equal{} 2$.  Let the line through $ G$ parallel to $ EF$ intersect $ CD$ at $ H$.  Find the area of the quadrilateral $ EFHG$.

3. Let $ E$ be the point of intersection of the diagonals of convex quadrilateral $ ABCD$, and let $ P$, $ Q$, $ R$, and $ S$ be the centers of the circles circumscribing triangle $ ABE$, $ BCE$, $ CDE$, $ ADE$, respectively.  Prove that $ PQRS$ is a parallelogram.

[quote="TheHeinrich"][quote="314.math"]
2. Let $ ABCD$ be a parallelogram of area $ 10$ with $ AB \equal{} 3$ and $ BC \equal{}$.  Locate $ E$, $ F$, and $ G$ on segments $ AB$, $ BC$, and $ AD$, respectively, with $ AE \equal{} BF \equal{} AG \equal{} 2$.  Let the line through $ G$ parallel to $ EF$ intersect $ CD$ at $ H$.  Find the area of the quadrilateral $ EFHG$.[/quote]
what is BC?[/quote]

Oops - Edited.  Thanks.

[quote="azjps"][hide="2"]
[asy]size(150);
pointpen = black; pathpen=black; pen p = linewidth(0.7); pen f = fontsize(8);
pair A=(0,0),B=(5,0),C=(5+5^.5,2),D=(5^.5,2);
pair E=(2*D+A)/3, F=D+(2,0), G=(2,0);
D(A--B--C--D--cycle); D(E);D(F);D(G);
D(F--G,dashed);
pair J=G+2*(F-E), H=IP(F--J,B--C);
D(H); D(F--E--G--H--cycle);
MP("2",(A+G)/2);MP("2",(D+F)/2,N);
MP("A",A,f);
MP("B",B,f);
MP("C",C,f);
MP("D",D,f);
MP("E",E,W,f);
MP("F",F,N,f);
MP("G",G,f);
MP("H",H,f);[/asy]
Draw $ \overline{FG}$, and we see that $ [EFGH] \equal{} [EFG] \plus{} [FGH] \equal{} [ADFG]/2 \plus{} [GFCB]/2 \equal{} [ABCD]/2 \equal{} \boxed{5}$.
[/hide]
[hide="3"]
[asy]size(250);
pointpen = black; pathpen=black; pen p = linewidth(0.7); pen f = fontsize(10);
pair A=(0,0),B=(1,2),C=(2.5,2.3),D=(4,0);
pair E=IP(A--C,B--D);
D(A--B--C--D--cycle,p);D(A--C,p);D(B--D,p);D(E);
pair P=circumcenter(A,B,E), Q=circumcenter(C,B,E),R=circumcenter(C,D,E),S=circumcenter(A,D,E);
D(P--Q--R--S--cycle,p);
D(circumcircle(A,B,E));
D(circumcircle(C,B,E));
D(P--E--Q--E--R--E--S);
D(rightanglemark(P,foot(P,B,D),E,3));
MP("A",A,f);
MP("B",B,W,f);
MP("C",C,NE,f);
MP("D",D,f);
MP("P",P,W,f);
MP("Q",Q,N,f);
MP("R",R,SE,f);
MP("S",S,f);[/asy]
Let $ A'$ be the midpoint of $ \overline{AE}$ and so forth. Since a circumcenter of a triangle is the intersection of the perpendicular bisectors of that triangle, it follows that $ PB' \perp BD$ and $ QB' \perp BD$, so $ PQ \perp BD$. Also $ RS \perp BD$. Thus $ \overline{PQ} \parallel \overline{RS}$ and similarly $ \overline{PS} \parallel \overline{QR}$.
[/hide][/quote]

I'm confused with the solution for #3.  Could someone please explain it a bit more?  Thanks.

I'm still confused.  :(  I don't understand the diagram.  Thanks.

meh you've said that the last time. Could you clarify exactly what part of the solution you don't understand? This is a pretty straightforward problem..

[quote="azjps"][hide="For 3,"]
[asy]size(200);
pointpen = black; pathpen=black; pen p = linewidth(0.7); pen f = fontsize(10);
pair A=(0,0),B=(.8,1.1),C=(2.2,1),D=(3,0);
pair E=IP(A--C,B--D);
D(A--B--C--cycle,p);D(A--C,p);D(B--E,p);D(E);
pair P=circumcenter(A,B,E), Q=circumcenter(C,B,E) /* ,R=circumcenter(C,D,E),S=circumcenter(A,D,E) */ ;
/* D(P--Q--R--S--cycle,p); */
D(circumcircle(A,B,E));
D(circumcircle(C,B,E));
D(P--E--Q--cycle);
D(rightanglemark(P,foot(P,B,E),E,3));
MP("A",A,f);
MP("B",B,W,f);
MP("C",C,NE,f);
/* MP("D",D,f); */
MP("P",P,W,f);
MP("Q",Q,N,f);
/* MP("R",R,SE,f);
MP("S",S,f); */
MP("B'",(B+E)/2,SW,f);
MP("E",E,f);[/asy]
Denote $ B'$ the midpoint of $ \overline{BE}$. Now, it is known that the circumcenter of a triangle is the intersection of the perpendicular bisectors of each of the sides of the triangle. In other words, the perpendicular bisector of $ \overline{BE}$ goes through the circumcenter of $ \triangle ABE$, and it also goes through the circumcenter of $ \triangle CBE$. Thus $ P, Q, B'$ are collinear, with $ \overline{PQ} \perp \overline{BE}$.

Doing the same thing with $ R,S$ yields that $ \overline{RS} \perp \overline{DE}$. If two different lines are both perpendicular to another line (in this case $ BD$), then they must be parallel, so $ \overline{PQ} \parallel \overline{RS}$. Similarly, we have $ \overline{PS} \parallel \overline{QR}$. If follows that $ PQRS$ is a parallelogram.

[/hide][/quote]

I didn't get the diagram.  Points like $ R$ and $ S$ were not there.  Maybe I'm interpreting something incorrectly?

Thanks!

The second diagram azjips posted for #3 was just part of the first one. Erm needless to say, points $ R$ and $ S$ are present in his first figure :)

[quote="314.math"]
I didn't get the diagram.  Points like $ R$ and $ S$ were not there.  Maybe I'm interpreting something incorrectly?

Thanks![/quote]

I got rid of points $ D, R, S$ to reduce some of the clutter in the image (the first diagram had a lot of points etc, and I thought those might've added confusion). The key here is that no matter where I position point $ D$ on the line $ BE$, it does not affect the position of points $ P$ or $ Q$, so its presence isn't important at first.

However, the argument I used (to show that $ PQ \perp BE$) can be applied in the same method to these deleted points. The only time we need all of the points together is when we are concluding that $ PQ \parallel RS, PS \parallel QR$ and so that $ PQRS$ is a parallelogram.

By the way, undefined117, there's no "i" in my username.  :wink: But that's how I imagine it would be pronounced.

oops I think I accidentally cloned the "j" and thought it was an "i" :lol: sorry.


Again, I am unsure if this is all right, dear friend.... But I don't think it has any flaw this time. :(
Prove that $ \forall a, b, c\in\mathbb{R}^\plus{}$ we have:
$ \sum\frac{x^5}{x^3yz\plus{}yz^4}\geq \frac{3}{2}$.
 :blush:
MAN, I hope it is all right!! :o

[quote="Potla"]Again, I am unsure if this is all right, dear friend.... But I don't think it has any flaw this time. :(
Prove that $ \forall a, b, c\in\mathbb{R}^ \plus{}$ we have:
$ \sum\frac {x^5}{x^3yz \plus{} yz^4}\geq \frac {3}{2}$.
 :blush:
MAN, I hope it is all right!! :o[/quote]
This inequality is true,my friend :)
We have : $ LHS \ge \frac{(x^3\plus{}y^3\plus{}z^3)^2}{2xyz(x^3\plus{}y^3\plus{}z^3)} \ge \frac{x^3\plus{}y^3\plus{}z^3}{2xyz} \ge RHS$

[quote="quykhtn-qa1"][quote="Potla"]Again, I am unsure if this is all right, dear friend.... But I don't think it has any flaw this time. :(
Prove that $ \forall a, b, c\in\mathbb{R}^ \plus{}$ we have:
$ \sum\frac {x^5}{x^3yz \plus{} yz^4}\geq \frac {3}{2}$.
 :blush:
MAN, I hope it is all right!! :o[/quote]
This inequality is true,my friend :)
We have : $ LHS \ge \frac {(x^3 \plus{} y^3 \plus{} z^3)^2}{2xyz(x^3 \plus{} y^3 \plus{} z^3)} \ge \frac {x^3 \plus{} y^3 \plus{} z^3}{2xyz} \ge RHS$[/quote]
Nice solution, Quy!
[hide="My Solution/Method of finding this"]
We know the lemma of Titu(generalised to $ k$'th power and proven by Holder).
$ \sum \frac{x_i^k}{a_i}\geq \frac{(\sum x_i)^k}{n^{k\minus{}2}\sum a_i}$   where $ i\equal{}1,2,\cdots n$
Denote the required inequality as $ (*)$.
$ (*)\Leftrightarrow \frac{x^6y^3}{x^4y^4z\plus{}xy^4z^4}\geq \frac{3}{2}$
(Substituting $ a\equal{}x^2y, b\equal{}y^2z, c\equal{}z^2x$ we get )
$ \Leftrightarrow \sum\frac{a^3}{a^2b\plus{}b^2c}\geq \frac{3}{2}$.........$ (*_2)$
To prove this , we assume $ a\plus{}b\plus{}c\equal{}1$ as the inequaltiy is homogeneous.
Hence $ (*_2)\Leftrightarrow \frac{(a\plus{}b\plus{}c)^3}{3\sum(a^2b\plus{}ab^2)}\equal{}\frac{1}{\sum(a^2b\plus{}ab^2)}\geq \frac{3}{2}$(from The lemma)
Now, we know the famous IMO Problem [hide]
$ ab\plus{}bc\plus{}ca\minus{}abc\leq \frac{7}{27}\forall x, y, z>0; x\plus{}y\plus{}z\equal{}1$.[/hide]
Using this and $ AM\minus{}GM$ $ (abc\leq \frac{1}{27})\implies \sum(a^2b\plus{}ab^2)\leq \frac{2}{9}$.
Use this result in $ (*_2)$ and we obtain the result. :roll: [/hide]

Man, I had to do a lot of typing! Thanks for your NICE solution Quy. :)
[hide="@ all mathlinkers"]Good night, my friends! Its $ 23: 20$. Bye![/hide]

[quote="Stephen"][quote="quykhtn-qa1"][quote="Potla"]Again, I am unsure if this is all right, dear friend.... But I don't think it has any flaw this time. :(
Prove that $ \forall a, b, c\in\mathbb{R}^ \plus{}$ we have:
$ \sum\frac {x^5}{x^3yz \plus{} yz^4}\geq \frac {3}{2}$.
 :blush:
MAN, I hope it is all right!! :o[/quote]
This inequality is true,my friend :)
We have : $ LHS \ge \frac {(x^3 \plus{} y^3 \plus{} z^3)^2}{2xyz(x^3 \plus{} y^3 \plus{} z^3)} \ge \frac {x^3 \plus{} y^3 \plus{} z^3}{2xyz} \ge RHS$[/quote]

But why is $ LHS \ge \frac {(x^3 \plus{} y^3 \plus{} z^3)^2}{2xyz(x^3 \plus{} y^3 \plus{} z^3)}$ ?[/quote]
$ \sum \frac{x^5}{x^3yz\plus{}yz^4}\equal{}\sum\frac{x^6}{xyz(x^3\plus{}y^3)}\geq \frac {(x^3 \plus{} y^3 \plus{} z^3)^2}{2xyz(x^3 \plus{} y^3 \plus{} z^3)}$(from Titu's lemma)
 :D
I hope you understand now.

[quote="Potla"][quote="quykhtn-qa1"][quote="Potla"]Again, I am unsure if this is all right, dear friend.... But I don't think it has any flaw this time. :(
Prove that $ \forall a, b, c\in\mathbb{R}^ \plus{}$ we have:
$ \sum\frac {x^5}{x^3yz \plus{} yz^4}\geq \frac {3}{2}$.
 :blush:
MAN, I hope it is all right!! :o[/quote]
This inequality is true,my friend :)
We have : $ LHS \ge \frac {(x^3 \plus{} y^3 \plus{} z^3)^2}{2xyz(x^3 \plus{} y^3 \plus{} z^3)} \ge \frac {x^3 \plus{} y^3 \plus{} z^3}{2xyz} \ge RHS$[/quote]
Nice solution, Quy!

We know the lemma of Titu(generalised to $ k$'th power and proven by Holder).
$ \sum \frac {x_i^k}{a_i}\geq \frac {(\sum x_i)^k}{n^{k \minus{} 2}\sum a_i}$   where $ i \equal{} 1,2,\cdots n$
Denote the required inequality as $ (*)$.
$ (*)\Leftrightarrow \frac {x^6y^3}{x^4y^4z \plus{} xy^4z^4}\geq \frac {3}{2}$
(Substituting $ a \equal{} x^2y, b \equal{} y^2z, c \equal{} z^2x$ we get )
$ \Leftrightarrow \sum\frac {a^3}{a^2b \plus{} b^2c}\geq \frac {3}{2}$.........$ (*_2)$
To prove this , we assume $ a \plus{} b \plus{} c \equal{} 1$ as the inequaltiy is homogeneous.
Hence $ (*_2)\Leftrightarrow \frac {(a \plus{} b \plus{} c)^3}{3\sum(a^2b \plus{} ab^2)} \equal{} \frac {1}{\sum(a^2b \plus{} ab^2)}\geq \frac {3}{2}$(from The lemma)
Now, we know the famous IMO Problem
$ ab \plus{} bc \plus{} ca \minus{} abc\leq \frac {7}{27}\forall x, y, z > 0; x \plus{} y \plus{} z \equal{} 1$.
Using this and $ AM \minus{} GM$ $ (abc\leq \frac {1}{27})\implies \sum(a^2b \plus{} ab^2)\leq \frac {2}{9}$
[hide="@ all mathlinkers"]Good night, my friends! Its $ 23: 20$. Bye![/hide][/quote]
This step 's wrong,my friend :wink:

[quote="quykhtn-qa1"][/quote][quote="Potla"][quote="quykhtn-qa1"][quote="Potla"]Again, I am unsure if this is all right, dear friend.... But I don't think it has any flaw this time. :(
Prove that $ \forall a, b, c\in\mathbb{R}^ +$ we have:
$ \sum\frac {x^5}{x^3yz + yz^4}\geq \frac {3}{2}$.
 :blush:
MAN, I hope it is all right!! :o[/quote]
This inequality is true,my friend :)
We have : $ LHS \ge \frac {(x^3 + y^3 + z^3)^2}{2xyz(x^3 + y^3 + z^3)} \ge \frac {x^3 + y^3 + z^3}{2xyz} \ge RHS$[/quote]
Nice solution, Quy!

We know the lemma of Titu(generalised to $ k$'th power and proven by Holder).
$ \sum \frac {x_i^k}{a_i}\geq \frac {(\sum x_i)^k}{n^{k - 2}\sum a_i}$   where $ i = 1,2,\cdots n$
Denote the required inequality as $ (*)$.
$ (*)\Leftrightarrow \frac {x^6y^3}{x^4y^4z + xy^4z^4}\geq \frac {3}{2}$
(Substituting $ a = x^2y, b = y^2z, c = z^2x$ we get )
$ \Leftrightarrow \sum\frac {a^3}{a^2b + b^2c}\geq \frac {3}{2}$.........$ (*_2)$
To prove this , we assume $ a + b + c = 1$ as the inequaltiy is homogeneous.
Hence $ (*_2)\Leftrightarrow \frac {(a + b + c)^3}{3\sum(a^2b + ab^2)} = \frac {1}{\sum(a^2b + ab^2)}\geq \frac {3}{2}$(from The lemma)
Now, we know the famous IMO Problem
$ ab + bc + ca - abc\leq \frac {7}{27}\forall x, y, z > 0; x + y + z = 1$.
Using this and $ AM - GM$ $ (abc\leq \frac {1}{27})\implies \sum(a^2b + ab^2)\leq \frac {2}{9}$
[hide="@ all mathlinkers"]Good night, my friends! Its $ 23: 20$. Bye![/hide][/quote][quote="quykhtn-qa1"]
This step 's wrong,my friend :wink:[/quote]

Do you mean

$ ab + bc + ca - abc\leq \frac {7}{27}$?

I think it should be

$ ab + bc + ca - 2abc\leq \frac {7}{27}$.

[quote="Stephen"][/quote][quote="quykhtn-qa1"][/quote][quote="Potla"][quote="quykhtn-qa1"][quote="Potla"]Again, I am unsure if this is all right, dear friend.... But I don't think it has any flaw this time. :(
Prove that $ \forall a, b, c\in\mathbb{R}^ +$ we have:
$ \sum\frac {x^5}{x^3yz + yz^4}\geq \frac {3}{2}$.
 :blush:
MAN, I hope it is all right!! :o[/quote]
This inequality is true,my friend :)
We have : $ LHS \ge \frac {(x^3 + y^3 + z^3)^2}{2xyz(x^3 + y^3 + z^3)} \ge \frac {x^3 + y^3 + z^3}{2xyz} \ge RHS$[/quote]
Nice solution, Quy!

We know the lemma of Titu(generalised to $ k$'th power and proven by Holder).
$ \sum \frac {x_i^k}{a_i}\geq \frac {(\sum x_i)^k}{n^{k - 2}\sum a_i}$   where $ i = 1,2,\cdots n$
Denote the required inequality as $ (*)$.
$ (*)\Leftrightarrow \frac {x^6y^3}{x^4y^4z + xy^4z^4}\geq \frac {3}{2}$
(Substituting $ a = x^2y, b = y^2z, c = z^2x$ we get )
$ \Leftrightarrow \sum\frac {a^3}{a^2b + b^2c}\geq \frac {3}{2}$.........$ (*_2)$
To prove this , we assume $ a + b + c = 1$ as the inequaltiy is homogeneous.
Hence $ (*_2)\Leftrightarrow \frac {(a + b + c)^3}{3\sum(a^2b + ab^2)} = \frac {1}{\sum(a^2b + ab^2)}\geq \frac {3}{2}$(from The lemma)
Now, we know the famous IMO Problem
$ ab + bc + ca - abc\leq \frac {7}{27}\forall x, y, z > 0; x + y + z = 1$.
Using this and $ AM - GM$ $ (abc\leq \frac {1}{27})\implies \sum(a^2b + ab^2)\leq \frac {2}{9}$
[hide="@ all mathlinkers"]Good night, my friends! Its $ 23: 20$. Bye![/hide][/quote][quote="quykhtn-qa1"]
This step 's wrong,my friend :wink:[/quote][quote="Stephen"]

Do you mean

$ ab + bc + ca - 2abc\leq \frac {7}{27}$?

I think it should be

$ ab + bc + ca - 2abc\leq \frac {7}{27}$.[/quote]
I want to speak: $ \sum(a^2b + ab^2) \le \frac {2}{9}$ 's wrong

[quote="quykhtn-qa1"][/quote][quote="Stephen"][/quote][quote="quykhtn-qa1"][/quote][quote="Potla"][quote="quykhtn-qa1"][quote="Potla"]Again, I am unsure if this is all right, dear friend.... But I don't think it has any flaw this time. :(
Prove that $ \forall a, b, c\in\mathbb{R}^ +$ we have:
$ \sum\frac {x^5}{x^3yz + yz^4}\geq \frac {3}{2}$.
 :blush:
MAN, I hope it is all right!! :o[/quote]
This inequality is true,my friend :)
We have : $ LHS \ge \frac {(x^3 + y^3 + z^3)^2}{2xyz(x^3 + y^3 + z^3)} \ge \frac {x^3 + y^3 + z^3}{2xyz} \ge RHS$[/quote]
Nice solution, Quy!

We know the lemma of Titu(generalised to $ k$'th power and proven by Holder).
$ \sum \frac {x_i^k}{a_i}\geq \frac {(\sum x_i)^k}{n^{k - 2}\sum a_i}$   where $ i = 1,2,\cdots n$
Denote the required inequality as $ (*)$.
$ (*)\Leftrightarrow \frac {x^6y^3}{x^4y^4z + xy^4z^4}\geq \frac {3}{2}$
(Substituting $ a = x^2y, b = y^2z, c = z^2x$ we get )
$ \Leftrightarrow \sum\frac {a^3}{a^2b + b^2c}\geq \frac {3}{2}$.........$ (*_2)$
To prove this , we assume $ a + b + c = 1$ as the inequaltiy is homogeneous.
Hence $ (*_2)\Leftrightarrow \frac {(a + b + c)^3}{3\sum(a^2b + ab^2)} = \frac {1}{\sum(a^2b + ab^2)}\geq \frac {3}{2}$(from The lemma)
Now, we know the famous IMO Problem
$ ab + bc + ca - abc\leq \frac {7}{27}\forall x, y, z > 0; x + y + z = 1$.
Using this and $ AM - GM$ $ (abc\leq \frac {1}{27})\implies \sum(a^2b + ab^2)\leq \frac {2}{9}$
[hide="@ all mathlinkers"]Good night, my friends! Its $ 23: 20$. Bye![/hide][/quote][quote="quykhtn-qa1"]
This step 's wrong,my friend :wink:[/quote][quote="Stephen"]

Do you mean

$ ab + bc + ca - 2abc\leq \frac {7}{27}$?

I think it should be

$ ab + bc + ca - 2abc\leq \frac {7}{27}$.[/quote][quote="quykhtn-qa1"]
I want to speak: $ \sum(a^2b + ab^2) \le \frac {2}{9}$ 's wrong[/quote]
Yeah, I was wrong ..... but how come the inequality become all right??? I am awed! :o
Thanks for your notice, Quy.
By the way, @Stephens:
Well , I made  a typo: the IMO problem is
$ ab+bc+ca-2abc\leq \frac{2}{27}$ and I am extremely sorry for these frequent typos..... :(   :no:
I am really awed that my inequality came out to be right even if I used a famous problem,,,,,,   :roll: .


A given type of defibrillator consists on a capacitor which is charged to a given potential and is then discharged through the chest of the patient using two electrodes. The resistance of the chest is $ 150\,\, \Omega$ and the electric pulse have a typical duration of 20 ms, transferring a maximum of 360 J to the body of the patient. Estimate the capacity and potential with which the capacitor must be charged.

Thanks. Could you explain your reasoning a little bit?


How come all the problems in the diagnostic stage have to do with counting and probability? Is this always going to happen even once i pass the diagnostic stage?

As of now, all the problems in Alcumus are counting and probability :)

From FAQ:

There are currently over 1,100 problems in Alcumus. Problems are based on Art of Problem Solving's Introduction to Counting and Probability book.

Is AoPS gonna add more problems, like geometry, or number theory, amc 8, 10, 12 problems, etc.?

From Alcumus FAQ:

Will there be other subjects included in Alcumus?
Yes. We are developing material for Alcumus that supplements the rest of our texts, beginning with Introduction to Algebra. There is currently no available timeframe estimate as to when the Algebra problems will be ready.


eh I've always wondered what other math people listen to...

I listen mainly to metal and rock (60-40 split? idk), what about you guys?

I have kind of a weird taste in music.  I don't really stay in one genre.  A partial list:

- R&B
- Rap
- Acoustic
- Classical
- IDM
- Alt Rock
- (Edit) Classic Rock

... actually, that's pretty much a complete list.  :)

I would say that I primarily listen to rock, mainly oldies from the 60s and 70s, but some more recent stuff, also.

Mainly metal stuff, especially prog/power. Go Dragonforce wooooooooooooooooo!!!!!!!!! little bit of jazz and rock, too, but especially stuff like dforce, dream theater, TMV, ATDI, Vai, Malmsteen, etc. etc. also a little bit of a ska fan, you know, Reel Big Fish type stuff

Everything, my parents give me classical on the car and Chinese music, I get rap, R&B, hip hop on the bus and at school a lot too, I get Rock/Metal when I'm over my friends' house, etc.

I like classical, but mostly I listen to industrial music. Sadly not many ppl have heard of industrial usually. The bands that call themselves that and are most popular are usually heavily influenced by metal (like Rammstein) but that doesn't mean they're bad. But I'm a fan of bands like Covenant and Front Line Assembly and Cruciform Injection and Funker Vogt that not so many ppl have heard of.

dude, you need to add electronica. yeah, I know its a minority, but it definitely needs its own option. in fact, its not a minority throughout lots of parts of the world.

i've heard of industrial, but i'm not into it too much. its kind of in between electronica and heavy metal right?

You might say that. A lot of industrial bands will cite Kraftwerk as an influence. (btw, Kraftwerk = pwn.) Some are also pretty close to metal and would be well liked by metal fans (like Rammstein), but others are quite distant.

I think industrial is pretty popular in Europe, especially Germany. Sadly here (US) there's not much audience so the famous bands don't tour much.

NIN, Creed, Sum 41, Drowning Pool, Shattersphere, Red Hot Chili Peppers, Audioslave, MSI, Cake, Kamelot, Rammstein, Iron Maiden, and Trust Company are all great bands (in my opinion)...

[quote="t0rajir0u"][quote="Elemennop"]dforce, dream theater, TMV, ATDI, Vai, Malmsteen[/quote]

I love listening to that kind of stuff every once in awhile, but most of the time it doesn't suit the mood I'm in (especially Dragonforce, which gets repetitive after awhile).  You like Satriani?[/quote]

satriani is a guitar god
I wish I could play piano as well as he plays guitar .-.

[quote]
[quote="h_s_potter2002"]
I don't really like the term "alternative", since "alternative" can be so many things. Like according to iTunes, Bright Eyes and AFI are both considered "alternative". But they're like really different from each other.

But yea, I guess if you look at most of my music, it's "alternative".
[/quote]

[quote="drunner2007"]
dude, you need to add electronica.
[/quote]
[/quote]
Not enough poll options; I would've elaborated more if I could've.

Power metal almost makes me want to laugh and throw up at the same time, except some of it (mainly by Iron Maiden and Kamelot) isn't that bad, so yeah...

[quote="Treething"]Kamelot[/quote]

[b]Yes.[/b]

Some Rhapsody songs are pretty good, too.

Any of you metal fans heard of Mezarkabul (Pentagram in Turkey) or Skyclad?

Hmmmm......Death metal is a stand alone genre and Black Metal or Trash Metal,Doom metal,Dark and other ones are not? THAT IS DISCRIMINATION  :mad:  :P   :P

classic, pop, rock,...  everything that doesnt give me a headache

Mainly rock,not heavy metal n punk

The Rasmus,Evanescence,Creed,alter bridge,Metallica,Guns n roses,Linkin Park,Coheed and Cambria....

Lots of rap as well but 95% from Eminem only.

Some hip-hop as well

So i'll vote for ROCK

[quote="nutz_for2.718281828"]Foreign exitement, meditation, Calm music, somethings that are foreign that raise blood pressure...   "Menuma la fey xanaa ma woy la" "Bu newul di julli mangay durus lillaahi" "Pia         Pacifica" "Sundara, Sundara, Sundara Shaun" That kind of stuff. NO others![/quote]
0.o
 :o
 :huuh:

:huuh: [quote="nutz_for2.718281828"]grrr........  They are perfectly good types! They are just different!

Here is a whole song, titled Arrows, Fire and Flowers

"Your tears are the jewels decorating my heart
You capture my mind like the moon
Then broken we meet
You read my mind, I speak your words
Together we breathe
Thoughts unspoken like frost on the pane
My Dance
My light
My heart
Blinded by the darkness I stumble
Then shadows perforated
Bliss uncovered
Seperated by
Arrows fire and flowers
May your eyes,
Your wandering eyes
Rest upon me
Come hold my hand and lead me through
Spiral whispers and maddening sighs
Then fate unfolds
clutching my heart,
Stealing my thoughts,
Settles, repose
Painful lessons like fire within
My love
My hope
My heaven"[/quote]
Once again, I respond with:
0.o  :o  :huh: :huuh:
But I guess you are just weird like that.
Jk.  :P


geometry
vector
cyclic quadrilateral
geometry unsolved

Let $ ABDC$ be a square with $ AB \equal{} a$. Let $ G$ be the intersection of $ AD$ and $ BC$, $ E$ point on the side $ BD$ such that $ BE \equal{} \frac {a}{3}$ and $ F$ a point on the opposite ray $ DC$ such that $ DF \equal{} \frac {a}{2}$. Let $ H$ be the intersection of $ AE$ and $ BF$. Prove that $ BG \equal{} GH$
Only use the Thales's theorem! Help!!!!!!!!!!
[img]http://img22.imageshack.us/img22/8481/67171798.png[/img]

Let $ I$ be midpoint of $ BD$. $ K \equiv {AH}\cap{CD}$ .It's easy to count $ \dfrac {BH}{HF}$ then Applying menelaus's theorem we'll get $ H,I,C$ collinear => $ I$ is orthocenter of $ \triangle BCF$ (QED)

It is easy to prove, e.g. using vectors, that $ \angle{AHD}\equal{}90^{\circ}$. This implies that $ ABHD$ is a cyclic quadrilateral with circumcentre $ G$ and the result follows.  :P

Sorry, my English is very bad, so... :blush:
[img]http://c.upanh.com/uploads/07-Jan-2010/tv1cppfzyta44wayo6.png[/img]
Gọi K là giao điểm của AE và DC, Q là giao điểm của AB và CH. Two Triangles ABE and KCE are similar so:
$ \frac {AB}{CK} = \frac {BE}{CE}$
Or $ XK = \frac {AB.CE}{BE} = \frac {a.\frac {2a}{3}}{\frac {a}{3}} = 2a$
$ \rightarrow FK = \frac {3a}{2}$
We have :
$ \frac {AB}{FK} = \frac {BH}{BF} = \frac {BQ}{CF}$
$ %Error. "RightarwowBQ" is a bad command.
\frac {AB.CF}{FK}$
$ = \frac {a.\frac {a}{2}}{\frac {3a}{2}}$
$ = \frac {a}{3}$
$ = BE$
$ \rightarrow \delta ABE = \delta CBQ$
$ \rightarrow \widehat{AHC} = 90^{o}$
Derive ... :D

I haven't typed mathematic formula expertly :( . Some one can help me?

I have noticed the previous solutions, very nice, do not use Thales, except the third one.
Applying Menelaos in $ \triangle MEF$ with the transversal $ AHN$, we get $ \frac{MH}{FH}\equal{} \frac{4}{1}$, but $ \frac{MC}{CF}\equal{}\frac{2}{1}$, showing that $ \frac{MH}{FH}\equal{}\frac{MC^2}{CF^2} \equal{} \frac{4}{1}$, i.e. $ CH\perp MF$.
Next, take $ P$ the symmetrical of $ B$ about $ H$, hence $ BC \equal{} CP$ and $ GH \equal{} \frac{PC}{2}\equal{}BG$.

Best regards,
sunken rock


vector
linear algebra
matrix
invariant
linear algebra unsolved

Here is a quite difficult problem (although it seems obvious, I could not find an argument not involving complicated results) to which I would like very much to see a not too complicated solution:
   Let K a commutative field and a family of matrices that commute two by two. Supposing that there exists a common proper vector for all these matrices, prove that the same property holds for the transpose of each matrix.

Any idea, anybody?   Question: we know that a matrix is similar to its transpose ( not an easy task to prove for an arbitrary field!), but is it true that given a commutative family of matrices, we can find an inversible matrix P that realizes the similarity between each member of the family and its transpose?

[quote="harazi"]e know that a matrix is similar to its transpose ( not an easy task to prove for an arbitrary field!)[/quote]
do you have a sln without field extension ?

No, though I have so often heard that there is a solution based on "invariants de similitude". Probably Moubi will be so kind to post it.

Imagine all these things said in an oral examination! I don't want to imagine. This is the solution I've found based on complicated (at least for me and certainly for the french programme) results. I would like to know if there is a more tricky but easy solution. Did you find any?

[quote="alekk"]to prove that if A and B (coefficients in K)are similar in an extension of K then they are similar in K, i think we can use "invariant de similitude".
Then it suffices to prove the result in algebraicaly closed field, that is not hard with Jordan reduction.[/quote]

A serious student for ENS or X should know these result, and the proof

I know that, but don't forget that the exam is 1 hour and I seriously doubt that someone can prove all these results in one hour. Probably I am wrong...  :? or probably the problem is already so difficult that the examinator won't enter in great details.


topology
vector
inequalities
real analysis
real analysis unsolved

Dear friends,
I have just taken a final course exam about topology and I gave up this problem as follows:
“Let $A$ and $B$ be subsets of $X$. Put $\displaystyle \rho(x,A) = inf_{a \in A} \parallel x - a \parallel $ and $ \displaystyle d_{H} (A,B) = max  \{sup_{a \in A}  \rho(a,B) \} $
Prove that $\displaystyle \rho(x,A) $ and $\displaystyle  d_{H}(A,B)$ are metrics”.
I can’t solve this problem because I suppose it is not clear.
First, I wonder what a set $X$  is. Is it a usual set or a metric space?
Secondly, is $\displaystyle  d_{H}(A,B)$ a metric?
I would like to be given your ideas about this.
Thanks for your helps!

It's implied that X is a metric space with metric $\rho$.

You are given a definition of $d_H$, and need to prove that it is a metric.

That looks like a bad question all around. I would only use the $\|x-a\|$ notation in a normed vector space. It doesn't make sense to call $\rho$ a metric, since the definition is not symmetric in the objects we allow. The definition of $d_H$ is garbled; it should be made symmetric by including the other half of the maximum.
Finally, the whole thing doesn't work anyway; $d_H$ is not positive definite unless we restrict to closed sets.

Dear jmerry,

What is you say the other half of the maximum? Is it $ \displaystyle sup_{b \in B}  \rho(b,A) $? If so, is $\displaystyle d_ {H} $ the so called Hausdorff distance between $A$ and $B$? And then do we need all the subsets $A$ and $B$ of a metric space closed or bounded?

Suppose $\displaystyle d_{H} (A, B) = max \{sup_{a \in A}  \rho(a,B) , sup_{b \in B}  \rho(b,A) \} $.
Can you verify $d_{H} $ satisfying the desired inequality in the definition of a metric in X?

Yes, that's what I meant by the other half of the maximum. I forgot about boundedness, but you need that too if you want finite distances; the distance between a single point and an unbounded set is clearly infinite.
Why you need closed sets: the distance between a set and its closure is clearly zero.

What did the question actually say? How much of the confusion comes from you not writing it correctly here?


How do you solve problems like this?
A circle with diameter 12 units has a chord AB with length 8 units.  What is the distance between AB and a parallel diameter?

Look at the diagram and then solve it using the pythagoream theorem


Assume that $ X,Y$ are $ 2$ fixed points that lie in the interior of the circle $ (O)$.
$ H$ is a fixed point which lies on the line $ XY$.
A line $ d$ passes through $ H$ and cuts $ (O)$ at $ M,N(M\in HN)$.
$ MX,NY$ cut $ (O)$ at $ P,Q$ respectively.
Prove that $ PQ$ passes through a fixed point (when $ l$ varies and passes through $ H$).

we must prove that the point $ K\equal{}PQ \cap XY$ is the fixed point.
draw two lines from $ H$ and then use pascal theorem for
$ P'M'N'PMN$ and $ NP'Q'N'PQ$.then we r done since $ X,Y,H$ are collinear.
($ M'N'$ is the second line passing through $ H$ so that $ M' \in HN'$ and $ M'X,N'Y$ cut $ (O)$ at $ P',Q'$)


Construct the midpoint of two points using ONLY a compass.

no only a compass and a pencil
you cant use the pencil as a straitedge.
no stupid tricks or anything

Well, you actually don't ever need a straightedge, so... =)

Doubters can check out the Mohr–Mascheroni theorem.

I seem to recall the original problem statement saying "collapsible" compass, which does not allow for the transfer of lengths.


The answer to that integral is a MEAGRE zero:D..
Put x-1 = a sin y, and then basic solving will yield you a zero..

Nice :D You can be proud for solving a sum that was given by an MIT freshman Chappli :D

Oh thats nice piece of info... Tell that MIT freshman that CHAPPLI solved his problem, and that he had to be proud of that...:D.. Acting vetti scene??:P Seri, not the feel...

Dei, he wasnt requesting his problem to be solved. He just thought it was a nice problem and posted it :D He didnt need someone to solve it for him.. Lol.. No feel anyway


Hey Valentin,

I was trying to move

http://www.artofproblemsolving.com/Forum/viewtopic.php?t=38380

to Graphical Design and it gave me an "Invalid_Session" Error. Any idea why?

I had the same problem: http://www.artofproblemsolving.com/Forum/viewtopic.php?t=37321 but noone ever responded to me  :( .  That only happens to me when I'm using Firefox.  I recently tried out Opera and it seems to work fine...  I have yet to test IE.  Perhaps an admin will actually read this thread :!:  :help:

I have no idea what's going on. I tried Firefox now and I have no problems (moved the topic out also). Do you have the latest version of Firefox (1.0.4)? ...

Strange then ... does it happen all the time? Does it happen with IE? Or Opera?

It happens all the time.  It happens on IE and Firefox.  I can only move topics when I am using Opera.

Yes, I have Firefox and yes it is the latest version. It used to work just fine...until up to about 3 days ago. I don't believe I've changed any AoPS or browser options.


Hola a todos !!

solo para comunicar que en la seccion:

$RESOURCE$ $SECTION$ del menu superior :..

ya podran encontrar los examenes de la mayoria de
las Olimpiadas Iberoamericanas ...
que hemos ido traduciendo y posteando ....

Quisiera dar las gracias por el gran aporte de:
[color=blue]David Jimenez,
M4RIO,
Jose Carlos,
Jorge Tipe,
etc.
[/color]
Por su apoyo  en esta tarea,
que de seguro recien comienza,
pues el objetivo es mostrar el material con el que cuenta esta region.. Iberoamerica ;)

Saludos,

Carlos Bravo ;)
Lima - PERU

Para la gente que quiera ir directo

aki el link:

[url=http://www.artofproblemsolving.com/Forum/resources.php?c=1&cid=29]Resource Section[/url]

Saludos,

Carlos Bravo ;)
Lima -peru


inequalities
combinatorics unsolved
combinatorics

In a school tennis tournament with $ m \ge 2$ participants, each match consists of 4 sets. A player who wins more than half of all sets during a match gets 2 points for this match. A player who wins exactly half of all sets during the match gets 1 point, and a player who wins less than half of all sets gets 0 points. During the tournament, each participant plays exactly one match against each remaining player. Find the least number of participants m for which it is possible that some participant wins more sets than any other participant but obtains less points than any other participant.

The answer is 6.  First, we give a construction:

Players are A, B, C, D, E, F.  All matches are ties, except the following:
A4-B0
A4-C0
A1-D3
A1-E3
A1-F3
B3-C1
B3-D1
C3-E1
C3-F1
The resulting scores of the players in the form Player(points, sets) are A(4, 11), B(6,10), C(5, 9), D(5,10), E(5, 10), F(5, 10), so player A has the desired property.

Now, suppose player X has the desired property, that X loses to $ a$ players, defeats $ b$ players and ties $ t$ players.  In any such situation, we may adjust the final scores so that X wins 4 sets whenever he wins and wins 1 set whenever he loses without changing our desired properties, so we have that X wins $ a + 4b + 2t$ sets and $ 2b + t$ points.  Thus every other player wins fewer than this many sets but more than this many points.  It's easy to compute the total number of sets and points won by all other players, and doing so gives us the two inequalities \[ 4\binom{a+b+t}{2} + 3a + 2t < (a + 4b + 2t)(a + b + t)\] and \[ 2\binom{a + b + t}{2} + 2a + t > (2b + t)(a + b + t).\]  Expanding these out and combining like terms gives
\begin{align*} a^2 + at + a & < 2b^2 + ab + 2bt + 2b \\
a^2 + at + a & > b^2 + bt + b.\end{align*}  From the second inequality it follows immediately that $ a > b$, while plugging $ a = 2b + c$ in to the expression $ a^2 + at + a - ab$ gives that $ a < 2b$.  Since $ a, b$ are nonnegative integers, we must have $ b \geq 2$ and $ a \geq 3$ and so a total of at least $ 1 + 2 + 3 + 0 = 6$ participants.


On the application, when asking for math background, along with courses taken, would any information about contests taken be useful?  Especially good results?

i think they have different section for Contest listing and Course listing, at least on the online App.

Oh really?  Where?  I see Contact Listing, no Contest listing though

Yes, you can list contests in the math background section.


How did you guys do?

I'm in silver and I was hoping to qualify for gold, but it doesn't look like I will.

Results:
cleaning-6 of 14 cases (greedy solution that I knew was wrong)
cowtract-7 of 10 cases-mildly disappointing
treecut-5 of 8 cases-devastating, i was expecting close to full points, but it appears my program wa too slow.

Oh well.

i didnt get my results back, but i got murdered on the gold.
I am hoping that i got the first one correct, and 3 test cases on the third one (solution O(n^2)... definitely needs O(nlogn))  and i didnt even submit a solution for the second one...

i have not got the e-mail, but i tested w/ the test cases and think i got 4 0 4 for silver. its pretty bad, but now i have nowhere to go but up :). i too thought i had an alright solution for #3, but it was too slow for the last few cases.

I didn't do too good either.  I got 8 3 3 for the silver divison.  It felt like this contest was so much harder than the first one though.  I ended 1 1/2 hours early becuase I didn't have any idea of what to do.  I spent so much time trying to get what the problem was asking.  There's always next time though.

Just wondering, where are you guys on the training pages?  I'm on section 2.5, doing kimbits.

i ended the contests 3 hours early...  i just couldnt figure it out from there... i am on section 4.1

hehe, i was right on :)

obstacle    *  *  *  *  *  *  *  *  t  *  t  *
skiarea     *  x  x  *  *  x  x  t  t

[edit] oh wait... obstacle was the one that was suppose to time out, and skiarea was supposed to be the correct one :S [/edit]

I thought I did okay, but I guess not.

divide      *  *  *  *  *  t  t  *  t  s
obstacle    *  x  *  x  x  e  e  e  e  e  t  e
skiarea     *  *  x  *  *  x  x  s  t

I thought I had a clever solution for obstacle, but it looks like it used to much memory maybe.

[quote="h_s_potter2002"]Just wondering, where are you guys on the training pages?[/quote]
I'm on 4.1.  I want to get to new problems, but I can never get the programs I'm working on to go fast enough.

divide      *  *  *  *  *  *  *  *  *  *
obstacle    *  *  *  *  *  *  *  *  *  *  *  *

I am in section 5.3 of the training pages. Apparently, If I were slightly ahead of where I currently am, I would have already encountered a variant of skiarea.

I'm on section 3.4 on the training pages.

divide        *  *  *  *  *  *  *  t  t  t
obstacle    *  *  *  *  *  t   t   t *  t  *  t

I suppose I should get about 280

I'm on Camelot (Section 3.?)

[quote="cpu886"]Anyone care to discuss their solutions to the questions?[/quote]

Especially paradox ;)

i thought skiarea was the most straightfoward one and divide was pretty impossible to do!!  guess i was wrong...

I had an O(nlogn+kn) algo for skiarea... where k might be potentially big (n being the size of the entire map)
nlogn comes from sorting and kn is a DFS.  either there is a bug in my code or that this implementation is completely wrong
and O(n^2) algo for obstacles...  (DP+mushing around)
I was twisting my brains for a nlogn solution for obstacles, and to tell you the truth, i dont think there is a way (unless you dont stick to my implementation... but... O(n^2) is just too big!  50000^2 wont run in less than 1 sec).  but obviously, i am not math inclined enough to prove to disprove nlogn works or not.
I am way to use to ACM, where you submit a program and they tell you if you are right or wrong.  so now i never bother testing my programs :(
if anyone can discuss there solution they used for divide that be great, regardless if its correct or not.

1  2  3  4  5  6  7  8  9 10 11 12 13 14
divide      *  *  *  *  *  *  *  *  t  t
obstacle    *  *  *  *  *  *  *  *  *  *  *  *
skiarea     *  *  *  *  *  *  *  *  t

For divide, all I did was Dynamic Programming. I went through each endpoint (from 1...L <= 1,000,000) and checked all possible start points 2A to 2B places behind. This could be done with a heap but I just did a plain linear search. It'd be great if someone who got perfect on this question posts their method.

For obstacle, I again used DP. However, I first calculated the length of taking only left turns or only right turns and pruned based on this "maximum" value.

Skiarea is very similar to Network of Schools in Section 5.4 (which is from IOI '96). Basically, you use flood-fill to find the # of "tops" that have to be visited in order for all locations to be accessible. You do the same thing for the "bottoms" and the answer is max(# of tops, # of bottoms).

ahh i just took the # of tops for skiarea, no wonder it was wrong!
pruning for obstacle... yep thats what i was missing.  i like that... good job aiden
for

[quote="paradox"]divide      *  *  *  *  *  *  *  *  *  *
obstacle    *  *  *  *  *  *  *  *  *  *  *  *
[/quote]

Paradox, can you describe how you solved divide.

Congrats Aidin, you did well and you may just have beaten most of the top American participants.

Divide:
I did a DP solution which used an array that kept track of the minimum number of sprinklers needed to cover all the ground legally up to a point (if possible). The value at 0 is set to be 0. Then I go through all even numbers (call them x) up to L and check values in the array for x-2*B ... x-2*A, in that order. The moment I come across a point x-2*k that has a possible legal arrangement of sprinklers ending there, I call  that value+1 the minimum number of sprinklers that are needed to cover everything up to x. (*) Of course, I never look at points that are inside the range of some cow (this is stored in a separate array determined at the beginning).

(*) This seemed right at the time and I knew that I needed to do something like this to make the program run in time. Though I did get all the test cases, I have not proven that this algorithm is correct; feel free to do so or to find a counterexample (just not both).

Obstacle:
I did DP here as well, keeping track of the minimum number of moves needed to get to a fence endpoint (or the barn).  After setting the initial Nth fence values (pretty simple), I loop through the fences from the Nth to the 1st. If an endpoint of that fence already has a value assigned, I follow the steps outlined in the problem and see what the first fence I hit is. Accordingly, I update, if necessary, the current best number of moves to get to the endpoints of this new fence.

This actually is not really a fast enough algorithm, since it is O(N2). Rob Kolstad, though, has apparently intentionally omitted the really difficult test data. I can easily construct a test case that takes this program 5 seconds to run.

hmm paradox... wow... i did the exactly the same thing except i didnt check if a value is assigned or not and found where it is suppose to go anyways, so that timed me out :(.

of cuz, aidin is a genious... he got bronze on IOI last year!

In fact, the algorithm that I posted previously for Divide has been proven to work and has been improved into a form that runs in O(L). Instead of posting details, I prefer to leave this as an exercise to the reader.

Does anyone know why the results always take a long time to come?  Just like the last contest, the results will probably come up a day late.

For the first one, you can just sort the intervals in increasing order by start time and decreasing order by end time.  Then find the interval with the greatest end time, that has a start time that is less than one more the last interval's end time.

I haven't really looked at this problem, but the first thing that came to mind glancing at it was use a minimum spanning tree algorithm and then remove those edges that in the spanning tree.  Repeat this until you are only left with a tree.  That tree is your max tree.

[quote="jeffrey"]Well, they're volunteers I think...

Could someone post solutions for the Silver division problems?

My attempts:
cleaning-I wrote a greedy solution that got about half the cases. It didn't seem to fit into any of the algorithms I've done on the site so far, brute force seemed slow, and I couldn't spot a DP recurrence (though my suspicion is a DP solution).

cowtract- I'd guess you'd call what I did a "maximal spanning tree" instead of finding the points closest to the tree, i did the points furthest away. I might have messed the execution, but I think the algorithm is wrong.

treecut- Flood-fill with part of the tree after removing a node. There must be a faster way.

Thanks[/quote]

I did Gold Division so I didn't look at the Silver problems much, but here are my thoughts:

Cleaning-This is a DP problem. Let best[i] be an array so that best[i] is the maximum number K such that shifts 1, 2, ...., K can be covered with i cows.  Knowing best[i], you can compute best[i+1] by adding the cow whose ending shift is largest, but with starting shift no more than best[i] + 1.

Cowtract-Let M be the maximum weight for any edge in the tree replace each edge weight w with M-w. Now, you can simply use the minimal spanning tree algorithm and then subtract the result from (M*number of edges).

Treecut-First, pick a node as your source, or root. Then, do a BFS search to compute distances from the source. For each node, maintain the number of children nodes as well as the size of the maximal subtree that is a child.

Results are up, [url]http://ace.delos.com/DEC04results[/url]


linear algebra
matrix
function
linear algebra unsolved

In my ergodic theory class we discussed transformations on $R^{n}$ by $n\times n$ matrices. The professor stated (and challenged us to prove) that if $A$ is such a matrix with integer entries and nonzero determinant, then the following are equivalent:

(1) The transformation $T$ associated with $A$ (i.e., $Tf(x) = f(A^{-1}x)$) is ergodic.
(2) $T$ is mixing.
(3) $A$ has no eigenvalue that is a root of unity.

But as far as we (that is, I and another student in the class) can tell, we don't actually use the fact that $A$ has integer entries anywhere, except maybe in that $A$ doesn't have determinant in $(0, 1)$, which it seems like we could just state as the condition on $A$, as that would be more general. Does anyone have any idea why it's important? We are sure that (2) -> (1) and (1) -> (3) do not require it (but we didn't yet prove (3) -> (2)).

(Also if anyone has ideas for proving (3) -> (2) they are welcome!)

I am happy to explain notation or definitions if anything I wrote is confusing. Just post here or pm me.

[quote="Xevarion"]I am happy to explain notation or definitions[/quote]
Yes, please. I've never heard the language of ergodic theory before, and I don't imagine many other regular posters have heard it either.
What are "ergodic" and "mixing"? The transformations act on functions $f$; what sort of functions are considered? I can see why we use inverse matrices; that makes $T_{A}\circ T_{B}=T_{AB}$.

I'm sorry, but (a) I stated my question wrong; (b) the answer to what I wanted to ask is actually obvious. I'll just edit and rewrite my post this evening to ask an interesting question and to explain it properly, and then hopefully a moderator will delete these two extra posts.


Setting $ g(x)=f(x)-x^{2}$ then that equation is equivalent to $ g(x+y)=g(x)+g(y)\forall x,y\in\mathbb R$. Hypothesis isn't enough!

[quote="The soul of rock"]Find all function $ f: %Error. "mathBB" is a bad command.
{R}\rightarrow R$ such that
$ f(x+y)=f(x)+f(y)+2xy$[/quote]

Let $ g(x)=f(x)-x^{2}$. Then $ g(x+y)=g(x)+g(y)$ and so the solutions are $ f(x)=x^{2}+$any solution of Cauchy equation.

For example (for continuous solutions) : $ f(x)=x^{2}+ax$


[quote="ductrung"]Prove that for all positive real numbers $ a,b$ and $ c$,
\[ \frac {ab^{2}}{c^{2}} \plus{} \frac {bc^{2}}{a^{2}} \plus{} \frac {ca^{2}}{b^{2}} \plus{} a \plus{} b \plus{} c \ge \frac {6(a^{2} \plus{} b^{2} \plus{} c^{2})}{a \plus{} b \plus{} c}
\]
[/quote]
I can rewrite the inequality :
$ \sum_{cyc} (a\minus{}b)^2(\frac{c}{a}\minus{}\frac{2}{a\plus{}b\plus{}c}) \geq 0$
But I don't know how to continue :blush:

[quote="chien than"]
I can rewrite the inequality :
$ \sum_{cyc} (a \minus{} b)^2(\frac {c}{a} \minus{} \frac {2}{a \plus{} b \plus{} c}) \geq 0$
But I don't know how to continue :blush:[/quote]
I think, you are wrong, chien than, because your inequality is not homogeneous. :wink:


Can anybody explain why the url tags in [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1060730#1060730]this thread[/url] do not work? When I post the same code anywhere else, say here, it results in [url]http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=471537135&t=114775[/url], just as it should be but not in that particular thread :?.

Edit: Nevermind; I figured it out: the BBCode was disabled there. So, just ignore this post.

I also noted something interesting. You can just post the URL without the tags, and it'll still generate the link.

Also, URLs with spaces makes posts blank like this one:
[url]http://www.example.com/one[/url]


Well, the 2 obvious solutions are (-2,0) and (0,0)

- Nawahd Werdna


Hi. I'm currently a junior in high school and was wondering:

How do you join an ARML team in NJ? Who should I ask?

Thanks in advance.

Going down the ARML team list for New Jersey, the only teams that exist according to the 2005 roster are the AAST teams, Bergen County, and Central Jersey teams.  I guess the team you can join is dependent on where you live in NJ.

I'm going to ARML as part of Central Jersey, which was based on taking a series of monthly tests and then selecting potential people.

I guess you should try consulting with your math coach or someone like that to see what you can do.  Or you can get 14 other people from your area and make up your own team.

As far as AAST goes, you can call up Joe Holbrook, the team coach over there, and ask if he'd be willing to take you along. He'd probably expect you to come to a few of the practices, which are on the weekends. It's doable if you live close enough to Bergen County.

[quote="neelnal"]can we go as a school?[/quote]

If your school can get enough people (as close to 15 as possible but not over) and your whole school team signs up and stuff then certainly. Any team can go, whether it be school, city, state, or just random people together.


Euler geometry trigonometry circumcircle

We are given a triangle ABC, whose Euler line's length is x. Find the side length of the triangle (in terms of x).

what is the Euler line? I saw it on a practice mu alpha theta thing before, but I never quite figured out its definition.

It's the line that passes through the centroid, orthocenter and circuncenter.

[quote="M4RI0"]Does the Euler line have a finite length :?:[/quote]
Yes, at least for this triangle it is completely inside the triangle. WE can make cases for this too.

I assume you mean the length OH (the line [i]segment[/i] of the Euler line which is actually of interest).

I believe there is no fixed answer for the sides.

However $x^{2}= OH^{2}= R^{2}(1-8\cos A \cos B \cos C)$ is well known (where R is the circumradius), from which, given other information, you might be able to work out individual side lengths.


vector
calculus
quadratics
algebra
polynomial
derivative
linear algebra

Let V be the vector space of real 2 x 2 matrices, and define \[f: V \to V \] by setting
\[f(A) = A^{2}\] for all \[A \in V \]

(i) Show that f is differentiable at each \[A \in V \] and find the rank of the linear map
\[f'(A): V \to V \] (This will depend upon A)

(ii) Find the image of f. At what points
\[S \in f(V) \] does the preimage
\[f^{-1}(\{ S\}) \]
include a point A with rank(f ' (A)) < 4 ?

An interesting problem. Of course $f$ is differentiable, being a quadratic polynomial in the entries of $A$. One can also see this from the expansion $f(A+B)-f(A)=AB+BA+B^{2}$, where $Df(A)\colon B\mapsto AB+BA$ is the derivative of $f$ at $A$, and $B^{2}$ is a negligible term, $o(\parallel B\parallel )$ as $B\to 0$.
The derivative $Df(A)$ can be represented by this $4\times 4$ matrix: \[Df(A)=\begin{pmatrix}2a_{11}& a_{21}&a_{12}&0\\ a_{21}&0&a_{11}+a_{22}&a_{21}\\ a_{12}&a_{11}+a_{22}&0&a_{12}\\0&a_{21}&a_{12}&2a_{22}\end{pmatrix}\]
Having computed its determinant, I found that $Df(A)$ is degenerate if and only if either of the following happens:
(1) $A$ has trace zero
(2) $A$ has determinant zero
I don't have a clean proof of this. And I don't know how to compute the rank of $Df(A)$.  :maybe:

[quote="Cezanne123"]it is a real analysis proof, if you haven't had the course, it probably isn't that obvious to you.[/quote]
Sorry, I didnt see the wor differentiable and derivative there. It just looked like linear algebra to me.

[quote="Cezanne123"]Let V be the vector space of real 2 x 2 matrices, and define $f: V \to V$ by setting $f(A) = A^{2}$ for all $A \in V$

(i) Show that f is differentiable at each $A \in V$ and find the rank of the linear map $f'(A): V \to V$

(This will depend upon A)[/quote]
This is indeed just Linear Algebra. As [i]mlok [/i] showed, the derivative of $f$ at $A$ is the linear map $Df(A)[B] = AB+BA$.

To characterize $Df(A)$, we can assume that $A$ has Jordan form.

(i) If (in Jordan form) $A = \begin{pmatrix}\lambda_{1}& 0 \\ 0 &\lambda_{2}\end{pmatrix}$, we set $C = \begin{pmatrix}2 \lambda_{1}& \lambda_{1}+\lambda_{2}\\ \lambda_{1}+\lambda_{2}&2 \lambda_{2}\end{pmatrix}$.  Then $Df(A)[B] = C \circ B$, where $\circ$ denotes the Hadamard product, $(C\circ B)_{ij}= C_{ij}B_{ij}$. So ...

a) If $\lambda_{1}\neq 0 \neq \lambda_{2}$, then $Df(A)$ has full rank unless $trace(A) = \lambda_{1}+\lambda_{2}= 0$ (in which case $Df(A)$ has rank 2).
b) If $\lambda_{1}\neq 0 = \lambda_{2}$, then $Df(A)$ has rank 3.
c) If $\lambda_{1}= \lambda_{2}=0$, then $Df(A) = 0$.

(ii) If (in Jordan form) $A = \begin{pmatrix}\lambda & 1 \\ 0 &\lambda \end{pmatrix}$, then
\[Df(A)[B] = 2 \lambda B+\begin{pmatrix}b_{21}& b_{11}+b_{22}\\ 0 & b_{21}\end{pmatrix}\, . \]
It is clear that $Df(A)$ has rank = 2 if $\lambda = 0$ and full rank = 4 otherwise.


geometry
3D geometry
function
algebra
domain
Support

Any help at all will be greatly appreciated =(

Scott (a part-time mathematics professor) has decided that he wants to open an ice cream stand and therefore design a large plywood ice cream cone to go on top of his new building. Being a math professor, Scott has decided to model the ice cream scoop part of the design (the top part) with the relationship s(x) = square root of (64 - x2) and the ice cream cone part of the design (the bottom part) with the relationship c(x) = |x| - 8.  x will be measured in feet.

3.	a.	Graph the ice cream scoop on a graphing calculator and submit your best reproduction of the graph with you project.
	b.	Graph the ice cream cone on a graphing calculator and submit your best reproduction of the graph with your project.
	c.	Is the ice cream scoop relationship s(x) = square root of (64 - x2) a function? What is the domain of s(x)?
	d.	Is the ice cream cone relationship c(x) = |x| - 8 a function? What is the domain of c(x)?
	e.	Graph the scoop and the cone together on the same set of axes (make this a very large graph as you will be adding to it).
	f. 	Scott wants to put crossed support beams behind the plywood ice cream cone at the x = -3 and x = 3 lines. In order to do this, he needs to know s(x) and c(x) at those points. What are s(-3), s(3), c(-3) and c(3) (be accurate to at least 4 decimal places)?
	g. 	To build his crossed support beams, Scott needs to know how long to make his beams. What is the distance from the point (-3, s(-3)) across to the point (3, c(3))? What about from (-3, c(-3)) to (3, s(3))? Be accurate to at least 2 decimal places.
	h.	Show what his crossed support beams will look like on your graph from part (e). Label all four points mentioned in part (g).
	i.	What are the x- and y- intercepts of s(x) and c(x)? Include those on your graph from part (e).
	j. 	At what values of x will the scoop be 6 feet high? Be accurate to 2 decimal places.
	k. 	Design a grid pattern of your choice with at least 8 lines for the cone (horizontal, vertical and slanted lines are okay). What are the equations of the grid lines? How long are the grid lines? Sketch the grid pattern on a graph of the cone including all points of intersection with c(x).

I think this is a little bit too difficult for the Classroom Math section...


What is the sum of the distinct prime factors of $ 3,780$?

3780 = 189*20 = 21*9*4*5=3*7*3*3*2*2*5, so 2+3+5+7=17.

It should be fairly obvious that it's divisible by 2,3, and 5, but to get divisibility of 7 is somewhat harder (and an intuitive jump)

First note that $ 3780\equal{}10\cdot378$. Since 378 is even, it is divisible by 2, which gives $ 3780\equal{}10\cdot2\cdot189$. Finally $ 189\equal{}9\cdot21\equal{}3^3\cdot7$. Thus, $ 3780\equal{}2^2\cdot3^3\cdot5\cdot7\implies2\plus{}3\plus{}5\plus{}7\equal{}\boxed{17}$.


group theory
superior algebra
superior algebra theorems

Hi this is my first post in College Algebra. I'm about to take the course this semester and I've study it a little by my self. I want to ask something about cyclic group.

Let $n$ be any integer. We construct a group of order $n$ as follow: $G$ will consist of all symbols \[ a^i \qquad i=0,1, \cdots n-1 \] where we insist that $a^0=a^n=e$, where $e$ is the identity elemen in $G$. and \[ a^i . a^j = \begin{cases}a^{i+j}&i+j\leq n \\ a^{i+j-n}&i+j>n \end{cases} \]
This is called cyclic group of order $n$.

I understand the definition if n is positive integer. for example $n=3$ we have $a^0=e$ and $a^n=e$. and the element are $a^0$,$a^1$ and $a^2$.
What about if $n$ is negative.

Another question, why we must state $a^0=a^n=e$, why not just write \[ a^i . a^j = \begin{cases}a^{i+j}&i+j <n \\ a^{i+j-n}&i+j\geq n \end{cases}  \]

So we just need to state that $a^0=e$.

Thanks in Advance. :)

Don't worry about redundant definitions; they happen all the time.

$n$ must be positive here; since the order of a group is the number of elements, we only consider groups of positive order.

Of course, you're probably familiar with this structure already- it's the additive structure of the integers mod $n$, and we should let each element have multiple names when convenient.

Thanks Jmerry.
Yes I'm already familiar with that structure.


Let $ ABCD$ be a trapezium($ BC\| AD$).Denote $ O\in AC\cap BD$.Let $ l$ be a line through $ O$ and parallel to $ BC$ and $ AD$.Denote $ K\in CD\cap l$.Suppose that there exist circle $ \zeta$, which passes through vertexes $ A$ and $ B$ and tangent to $ CD$ at $ K$.Denote $ X\in \zeta\cap BC$,$ Y\in\zeta\cap AD$,$ Z\in AB\cap CD$.Prove that $ Z$,$ X$,$ Y$ are collinear.

An image to this problem:
[img]http://img513.imageshack.us/img513/1276/spotborsg9.png[/img]

Nice problem . Here is a sketch of a solution .We have $ DK^2\equal{}DX\cdot DA$ and $ KC^2\equal{}CY\cdot CB$

So $ (\frac{DK}{KC})^2\equal{}\frac{DX\cdot DA}{CY\cdot CB}$ so $ (\frac{OD}{OB})^2\equal{}\frac{DX\cdot DA}{CY\cdot CB}$

or $ (\frac{AD}{BC})^2\equal{}\frac{DX\cdot DA}{CY\cdot CB}$  so $ \frac{AD}{BC}\equal{}\frac{DX}{CY}$ from which we get the derised.


Please post here with your name, class, school, city and the competitions you are giving in the near future. This is not an introduction thread. Basically meant to keep track of who's doing what. It can get confusing at times lol. You may mention your past achievements as well.

Here's me-
Gaurav Shukla
11
City Montessori School, Aliganj Sector 'O'
Lucknow
A lil long coz I copied it from my kvpy interview form document :p-
[hide]Accolades pertaining to Science related competetions-
i.	Selected for final award of scholarship in  the National Talent Search Scheme
ii.	Qualified for Indian National Maths Olympiad through the Regional Maths Olympiad
iii.	Qualified for the Indian National Astronomy Olympiad Jr. conducted by Homi Bhabha Centre for Science and Education through the National Standard Examination in Physics and was placed among top 10% of 35 students enrolled at the centre.
iv.	Qualified for 2nd Round of National Science Olympiad and attained all India rank of 126
v.	Achieved all India ranks 60, 67 and 163 in different years in National Level Science Talent Search Examination conducted by Unified Council.
vi.	Qualified for 2nd round of National Cyber Olympiad and attained All-India Rank of 172
vii.	Won 1st prizes in Inter-Branch Olympiads for Physics(twice) and mock NTSE conducted by Inspection Department, City Montessori School
viii.	1st prize in Elocution and Quiz competitions conducted by Regional Science Centre.
ix.	1st position in Science Talent Search Exam in West Bengal
x.	Came in top 3 in the written round of Birla Scholarship exam and won the interview round.
xi.	Came third in the regional round Discovery Kids Quiz[/hide]
Giving this month-
(INMO, SAT, NSTSE)

Arnav Mittal
Class 11th
School-Brigthlands (have u evr herd the name....??? :rotfl: )
Dehradun
NSTSE,...i dont think any more....... :rotfl:

NAME: ROMIL TALWAR

CLASS: XI C

SCHOOL: LA MARTINIERE COLLEGE,LUCKNOW

COMPETITIONS:

INTEL IRIS

ARIZONA STATE SCIENCE FAIR

TECHKRITI (IIT KANPUR)

NATIONAL GEOGRAPHIC YOUNG SCIENTIST CHALLENGE

EXAMS: SAT,ACT AND AP CREDITS EXAMS

FEW OTHER INTERNATIONAL CHALLENGES.............

Name ---Pulkit Mittal
Class---- XI
School----SJA
City----Dehradun

Past acheivements-----
Karate Black Belt(seems a very loooooonnng time back) :starwars:
Ntse

Competition
nstse

@ Arnav... i've heard of brightlands.....the best in dehradun..

i studied there till 5th....... i wonder if you some of ur seniors like Nandish Malhotra, etc..

HEY alsk/.........
u r in which clas?????? :maybe:
well where r u now????
and pls tell why did u leave it......???

[quote="rituraj007"]see this ...evrything's denovo
 :blush:
http://www.mathlinks.ro/viewtopic.php?t=192260[/quote]
Thats funny. You seriously seem to have been misunderstood there. Nearly everyone here is a part of the cream of the country. There's no point trying to prove yourself superior. From what I've seen here, people always tend to be soooo happy whenever they see a fellow Aopsian get selected somewhere or win a prize. Its almost this is like our 3rd school(including coaching lol). I hope the team spirit never fades.

it is in my opinion very much natural to be happy on 'someone you know's success  :D

if you can't win,you would want your friends to win  :)

[quote="ALSK*"]im in 12

i shiftd 2 delhi aftr 5th

well i still miss it n frends

i loved the skul.......

don kno abt senior sec...but till 5th toh it was good
where d u live .....i lived in FRI[/quote]

Finally Adarsh u hav made it here..
Congrats 4 the 4 olymps

and also ,did anchit direct u here??

betw,i hope u remember me,i wasn't that bad GK till the tournament began :rotfl:  :rotfl:

omg,this forum is really overflowed wid genii :D

similarily we can say who don't know NSTSE topper  :)

[quote="skand"]omg,this forum is really overflowed wid genii :D
[/quote]
Your wish is my command.  :P

[quote="rt_08"]AP CREDITS EXAMS

FEW OTHER INTERNATIONAL CHALLENGES.............[/quote]
Can you elaborate which APs you are taking and have you contacted ETS about the regional participants in the AP courses where we can get ourselves examined?  :huh:


[quote="socrates"][quote="Maverick"]ABC is a triangle which is not echilateral and it also isn't isosceles. Prove that:

|a/(a-b)+b/(b-c)+c/(c-a)|> \sqrt 6 - 1[/quote]

 :)  :)[/quote]
 :mad:  :spam:

[quote="Tiks"] :mad:  :spam:[/quote]

He is just trying to draw attention to these old, forgotten threads. However, I fear this is not really efficient, because a thread on page 9 of the respective section which has 0 replies still attracts more attention than a thread with 2 replies on page 1, as the existence of replies suggests that the problem is actually solved.

Anyway, this problem has been discussed on http://www.mathlinks.ro/Forum/viewtopic.php?t=20869 . Not that I would really like the solutions presented there, but I don't like mine either...

  Darij

:o  I didn't see that this problem was be posted in 2003 :blush: .
But I think hi can writed same words.


function
integration
calculus
derivative
probability and stats

Sorry I haven't figured out how to put formulae in the text box so have put my question in the attachment...

THanks

i think you  should  use Moment Generating Functions .

why are you stuck ?
$ E(W_t^k) \equal{} \int_{\mathbb{R}} x^k \frac{e^{\minus{}\frac{x^2}{2t}}}{\sqrt{2 \pi t}} dx$, which is easily computable by integtation part. That is really all you need to know to finish the exercice.

I would not use integration by parts, it is easier to compute the derivative of characteristic function at 0 and use the relation between the moments and the derivatives.


trigonometry
algebra
polynomial
number theory
relatively prime
AMC

Let $ s_{k}=\sin\frac{2\pi(4k+1)}{4n}$, and $ c_{k}=\cos\frac{2\pi(4k+1)}{4n}$ for some positive integer, $ n$. If $ n=2007$, $ x=3$, and  $ \tan\left[\sum_{k=0}^{n-1}\tan^{-1}\frac{s_{k}}{x-c_{k}}\right]=\frac{p}{q}$ where $ p$ and $ q$ are relatively prime positive integers, find the remainder when $ p+q$ is divided by $ 1000$.

[hide="hint"]Use $ \tan^{-1}\frac{b}{a}=\arg(a+bi)$ and $ \arg(z)+\arg(w)=\arg(zw)$.[/hide]

[quote="Altheman"][hide="hint"]Use $ \tan^{ \minus{} 1}\frac {b}{a} \equal{} \arg(a \plus{} bi)$ and $ \arg(z) \plus{} \arg(w) \equal{} \arg(zw)$.[/hide][/quote]

OK, so we need to calculate $ \tan(\arg((3\minus{}\cos{\frac{\pi}{4014}}\plus{}i\sin{\frac{\pi}{4014}})(3\minus{}\cos{\frac{5\pi}{4014}}\plus{}i\sin{\frac{5\pi}{4014}})...(3\minus{}\cos{\frac{8025\pi}{4014}}\plus{}i\sin{\frac{8025\pi}{4014}})))$

What next?

Plugging in numbers isn't going to help you much...you have a polynomial in x now...can you find a more simple form?

Umm... don't really see how. Please give a hint  :)

Multiply the sum in question by negative one. After applying the first hint, you get something like:

$ \prod (x\minus{}\text{cis }\, 2\pi \frac{4k\plus{}1}{4n})$.

...

What are the roots of $ x^{4n}\minus{}1$?

[quote="Altheman"]Multiply the sum in question by negative one. After applying the first hint, you get something like:

$ \prod (x \minus{} \text{cis }\, 2\pi \frac {4k \plus{} 1}{4n})$.

...

What are the roots of $ x^{4n} \minus{} 1$?[/quote]

OK, so you get something like $ \prod (x \minus{} \text{cis }\, 2\pi \frac {4k \plus{} 1}{4n})\prod (x \minus{} \text{cis }\, 2\pi \frac {4k \plus{} 3}{4n}) \equal{} x^{2n} \plus{} 1$.
But we just want one of the two products. If we get it we'll be done.

But how?  :maybe:

Edit: Got it. Very nice. $ x^{2n}\plus{}1\equal{}(x^n\minus{}i)(x^n\plus{}i)$  :lol:  :D


In a nxn matrix, if you have n linearly independent vectors, then they MUST form a basis?

We know that they are linearly independent. So thus, we only need to show that they span the space.

We know that the set $S =(e_{1},e_{2},...,e_{n})$, which consists of the unit vectors of $R^{n}$ spans $R^{n}$. We also know that n linearly independent vectors in a nxn matrix can be reduced to S. Does this then constitute an adequate proof?

Yes, your proof is OK.
Another possibility: if there is a vector not in the span of $x_{1},\dots,x_{n}$, then adding it to the collection, we get linearly independent vectors $x_{1},\dots,x_{n+1}$, which can be shown to be impossible.


superior algebra
superior algebra unsolved

If a group has an element with infinite order, is the group to which that element belongs to of infinite order?
That is if $ g \in G$ and $ |g| \equal{} \infty$ then is $ |G| \equal{} \infty$ or is it possible that $ |G| < \infty$?
I don't think so because then it is not closed...

Can a set with a [b]infinite[/b] subset be finite?  :wink:


Please observe the following guidelines while starting threads and making posts in the Round Table:

The Round Table is a forum for [i]discussion[/i].  As such, the following activities/behaviors are strongly discouraged:

1) Creating "polls as subject of discussion" or "poll only" topics.

2) Using chat-speak or other forms of communication that vary wildly from standard written English.  In particular, the use of "u" for "you," "r" for "are," etc. is annoying and distracting.

3) Making posts that do not add to a discussion.  This can take many forms including personal anecdotes of no interest to anyone other than yourself, posts of the form "I disagree!" or "Right on!", posts that consist almost entirely of links or embedded content, etc.

4) The use of profanity.

5) Quoting the entire post immediately preceding yours.  (This makes threads longer and makes reading them more difficult; it is always assumed that you are responding to the post directly preceding yours.)

6) The use of fonts that make your post difficult to read.

7) Reviving old threads on which discussion has long since ended, especially when in violation of other guidelines (e.g. (3) and (4)).

As a rule of thumb, before making a post, one should ask oneself the following questions:

[quote][u][b]1.[/b] Does my post contain informative value?[/u]
This needs not be mathematical (and indeed, in the Round Table it should not be!), as there are informative things to be said about World Cup 2006, too. On the other hand, few informative things can be said about problem 5 of the IMO 2006 before the IMO has started.
[u][b]2.[/b] Could my post interest or be useful to anyone?[/u]
This is closely related to the question before. If a post doesn't interest anyone, why should it be posted?
It is probably safe to assume that a good joke will interest people if it pertains to the subject at hand. On the other hand, a statement of the kind "I think so too" is less likely to do that.
[u][b]3.[/b] Will anyone understand this post?[/u]
Yes, this is something many people just don't think about. For example, if you know that your English sucks, try to be as clear as possible -- others will seek clarification as needed.[/quote]

If statement [b]3.[/b] is not fulfilled, or neither [b]1.[/b] nor [b]2.[/b] is fulfilled, then the post is spam.

The moderators will do our best to remove spam, trolling, and other posts that fail to meet the guidelines above, derail conversations, or otherwise interfere with normal usage of the forum.  Please help us by [i]not responding to spam and trolling[/i].

[quote="JBL"]
1) Creating "polls as subject of discussion" or "poll only" topics.
[/quote]

Er... what does that mean?
If I added a poll to a discussion topic, would that violate that?
Can I even post a response to this announcement?

[quote="username42"]If I added a poll to a discussion topic, would that violate that?[/quote]

I don't think so. I think that JBL meant that these topics are meant to be discussion topics, and not only "poll only" topics. So as long as it is a topic where meaningful discussion is occurring, it should be fine.

[quote=OlympusHero]Bump, these guidelines are very important! :)[/quote]

uh
I think this is already linked in the rules
but yeah remember to read this also

[quote=Kmath1234][quote=OlympusHero]Bump, these guidelines are very important! :)[/quote]

They are linked to the announcement and are in the announcement. This was highly unnecessary.[/quote]

False. Not many people actually click that link anyways, and more people view the first few threads than actually viewing the announcement and then clicking another link after it.

Ok, so are you going to bump this every month? This will inevitably go back to the depths of the forum.

[hide=@Wukong #10:][quote name="Wukong" url="/community/p16639799"]
why not just make it announcement?
[/quote][/hide]

because it's already linked in the rules announcement

[quote=shark449]So they are just reinforcing these rules!!![/quote]

There's no point in bumping this if it's linked in the rules announcement anyway