My friend found a bogus proof of 1=2 and showed it to me today.

[hide="Proof"]

If $ x\equal{}y$

$ x^2 \equal{} yx$ (Multiply both sides by x)

$ x^2 \minus{} y^2 \equal{} yx \minus{} y^2$

$ \frac{x^2\minus{}y^2}{x\minus{}y} \equal{} \frac{yx\minus{}y^2}{x\minus{}y}$

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

$ y\plus{}y\equal{}y$ (Due to substitution)

$ 2y \equal{} y$

$ 2\equal{}1$
[/hide]

How many things are incorrect with this proof? I found 2 in the 5 minutes we had in Spanish class today.

you divided by x-y but x=y so x-y=0 which is bad

you divided by y but 2y=y so y=0 which is bad

[quote="CatalystOfNostalgia"]you divided by y but 2y=y so y=0 which is bad[/quote]

My reasoning was a bit different for that one.

[hide="Reasoning"]
Because you have $ 2y \equal{} y$, then it follows that $ y \equal{} \frac{y}{2}$. Now since $ x\equal{}y$, we have $ x\equal{} \frac{y}{2}$, which contradicts our given statement.
[/hide]

x=y/2 isn't a direct contradiction of x=y...

Also if $ x \equal{} \frac{y}{2}$ then $ x\equal{}0$ and $ y\equal{}0$ which means that multiplying by $ x$ would result in $ 0\equal{}0$ (step 2 I think)

[quote="happyme"]Also if $ x \equal{} \frac {y}{2}$ then $ x \equal{} 0$ and $ y \equal{} 0$ which means that multiplying by $ x$ would result in $ 0 \equal{} 0$ (step 2 I think)[/quote]
Of course $ 0\equal{}0$. :huh:

But not $ 2 \equal{} 1$.

EDIT: I still don't get what was 9000+ (the views were nine HUNDRED something)

[quote="happyme"]But not $ 2 \equal{} 1$.[/quote]

Yeah, that was my initial observation. If we let $ x\equal{}y\equal{}0$, then that certainly does not prove that $ 2\equal{}1$. So therefore $ x$ and $ y$ must be nonzero rational numbers.

The main fallacy is that you divided by 0. (x-y)=0 since x=y.

See this link.

http://mathforum.org/dr.math/faq/faq.false.proof.html

you divided by x-y = 0, which is a undefined operation

The first division by $ 0$ (the division by $ x \minus{} y$) already invalidates the proof.  The errors beyond that point are meaningless.  In fact, it's possible to show that from a single invalid statement all false statements are provable.

Also, to solve the system $ 2y\equal{}y$, you must first isolate $ y$ to get $ y\equal{}0$.


probability
algebra
polynomial
MATHCOUNTS
expected value

You throw a coin multiple times. What's the average amount of throws required to obtain 2 heads in a row?

Maybe this is the answer.

[hide]Probability for getting 2 heads in a row is 1/4.

Expected counts = 1/probability (a formula from statistics)

So expected number of throws is 4.[/hide]

[hide]It's not four.  I think it is two but I don't have any hard proof.  Getting it in 2 throws has a prob.  of 1/4.  Three tries has a prob of 1/8 because the only way to do it in 3 is to get THH.  For four you can throw either TTHH or HTHH so the probability is 1/8.  The probability steadily goes down after 4 but I don't know how to show that 2 has the max.  probability.

[edit] By looking at the probabilities it appears that the probability of two heads coming up in n tosses is [tex]2^{(-n)}F_{n-1}[/tex]

[tex]F_n[/tex] is the nth Fibonnaci number.  I'll thing about why this is some more.[/hide]

[hide]But the question is asking for average number of throws.

Which is  :Sigma: (number of throws)(probability of success on that throw)

So i think the sum should converge to 4. [/hide]

A start.

Let a_n denote the number of ways to get 2 heads in a row for the first time after exactly n throws. We have already found a_2=1 and a_3=1. Now lets find a_n. If the sequence starts with a T, then the remaining (n-1) throws can be any of the a_(n-1) possible sequences with length (n-1), so there are a_(n-1) ways for the sequence of length n to start with a T. If it starts with a H, then the second throw must be a T, and then there are a_(n-2) ways to finish. So, we have

a_n = a_(n-1)+a_(n-2).

Does this recursion remind you of anything? Fibonacci. We get a_n=F_(n-1), which means that the PROBABILITY of needing n throws is a_n/2^n which equals F_(n-1)/2^n, which is what was guessed earlier.

With power series I was easily able to evaluate the required sum and I got an answer of [hide]6[/hide], but I don't think power series belong in intermediate, so I'll find another way.

You can't get F_n/2^n without power series?  That's a great series to solve, and it's not very difficult at all ... just as easy as (polynomial in n)/k^n, maybe even easier.

I can get the sum of f_n/2^n with power series, but the sum for the expected value is n*f_(n-1)/2^n. The extra n factor makes it more difficult. I did figure out how to get this more complicated sum, but it takes a little bit of work (i.e. more work than I plan to tex). But it relies heavily on the following method: [hide]Let S be the sum. Write 1/2 S, where all the terms are just moved over one with their denominators changed. Then subtract. Then try to manipulate this new sum to involve 2 sums that we can evaluate: the sum of f_n/2^n, and S itself. Then we can just solve for S as in a linear equation. Oh ya, you also have to figure out how to evalueate the sum of f_n/2^n. It uses pretty much the same method, but it is a bit simpler than that. Good luck![/hide]

Here's another approach.  Let a be the average value that was asked for.  Let b be the average value of the same quantity, except that there was one "pre-toss" of heads.  Now look at what happens after one real toss.  We get the linear equations a = 1 + a/2 + b/2 and b = 1 + a/2.  Do you see why?  Finally we can solve for a.

Ravi B is using the notion of "conditional expectation." This is an incredibly powerful idea, and I recommend that everyone study and understand his solution.

A simpler problem which can serve as practice for the notion: A certain thing (like a 1 showing up on the throw of one die) has a probability p of occuring on one trial. Repeat independent trials until it occurs until the first time. What is the average number of trials? (That is, we're asking for the expected value of the geometric distribution.) This can be done in many ways, but try to follow Ravi B's idea just for practice in that idea.

is there a place i could get more information on this method?  i'm not too sure i fully understand Ravi b's explanation

There's a cool little Dover book by Frederick Mosteller called [u]50 Challenging Problems in Probability with Solutions[/u] that has some problems with solutions using Ravi's method.

Try this one:

Suppose you are on a number line, and you start at 1. You repeatedly roll a die. If it lands on 1 or 2, go down one integer. If it isn't a 1 or a 2, go up one integer. What is the probability that you land at zero at some point?

Or this, which is a very close relative of Complex Zeta's problem: Two players, A and B, start with m and n coins, respectively. They flip a fair coin, and based on the results of each flip, one player pays the other one coin. The game ends when one player goes broke. What is each player's probability of winning, and how long, on average, does the game last? You can vary this problem by inserting an unfair coin.

You can think of the previous problem as being the m = 1, n =  :inf:  case of this, with a particular 1/3 : 2/3 unfair coin. These are all well-known problems, with names that we might as well not mention yet. A clear understanding of how to use conditional expectation (AKA "Ravi's method"), along with a little familiarity with difference equations, is what's needed.

Nosepuppy, here is a little more explanation of the method I described for the original problem.  Consider the first toss.  It's either tails or heads, with probability 1/2 for each.  If tails, then that doesn't help or hurt for HH, so we're back to the original situation.  If heads, then we are in the situation I described in the definition of b.

So now we can try to understand the equation a = 1 + (1/2)a + (1/2)b.  The "1" is because we are counting the first toss.  The (1/2)a is for the case when the first toss is tails.  The (1/2)b is for the case when the first toss is heads.

Did that make sense?

Following is a graphical interpretation of the problem.  [hide]I do not believe my method is beyond "Intermediate".  [But, please let me know if this is not the case, as I have used this method to solve MATHCOUNTS problems (see below).  The underlying mathematics is roughly equivalent to Ravi's solution.]

Figure 1 is a state diagram showing the process we are undertaking.  The graph shows four states.  In the "Start" state, the coin has not been flipped.  In the "H" state, there has been one consecutive head thrown.  In the "T" state, the last toss was a tail.  In the "HH" state, two consecutive heads have been tossed, and the process is finished.

Each time a coin is tossed, you follow a blue link (heads) or a red link (tails) to the next state.  The probability of flipping a heads is p=1/2 and the probability of flipping a tails is q=1/2.  [If you are very industrious, you might want to try this method with an unfair coin.]

The contents of each circle in the state diagram shows the expected number of times we will visit that node.  We visit the "Start" state exactly once (s=1), at the start of the process.  The expected number of times we visit the "H", "T", and "HH" states is given by the variables, h, t, and z.

Let's consider the "H" state.  You can get here from the "Start" state or you can get here from the "T" state.  The number of times you expect to reach this state is given by [tex]h=ps+pt[/tex].

Consider the "T" state.  You can get here from the "Start" state or from the "H" state or you can remain in the "T" state.  The number of times you expect to reach this state is given by [tex]t=qs+qh+qt[/tex].

Finally, consider the "HH" state.  The only way you can reach this state is from the "H" state.  The number of times you expect to reach state "HH" is given by [tex]z=ph[/tex].

Since p, q, and s are constants, the equations for h and t form a 2-variable linear system:

[tex]h=ps+pt=(\frac{1}{2})(1+t)[/tex]

[tex]2h=t+1\quad\quad\quad[/tex]

[tex]t=qs+qh+qt=(\frac{1}{2})(1+h+t)[/tex]

[tex]2t=h+t+1[/tex]

[tex]t=h+1\quad\quad\quad[/tex]

Solving equations (1) and (2) yields h=2, t=3.

Now we can solve [tex]z=ph=\frac{1}{2}h=\frac{1}{2}\times 2=1[/tex].

[It should come as no surprise that we reach the final stage of the process exactly once.  This is a good check that the rest of our work is correct.]

We now know we expect to reach the "H" state 2 times, we expect to reach the "T" state 3 times, and we expect to reach the "HH" state 1 time.

Each time we reach a state, we have flipped the coin.  If we add the total number of times we expect to reach each state (except "Start"), we should have the total number of expected flips.  (h+t+z=2+3+1=6)[/hide]

Problem 2 of the Team Round of the 2000 National MATHCOUNTS Competition was a slightly simpler problem, solvable by a similar method.  The problem involved three people who took turns flipping a coin.  If you matched your predecessor's flip, you won.  My solution, using a State Diagram, is on page 14 of this document.

That's pretty cool, rcv! I like that method alot.

BTW, if anyone's interested, here's the power series solution.

We will evaluate the sum [tex]\displaystyle \sum_{k=1}^\infty (k+1)F_k\cdot  x^{k+1}[/tex] and then plug in x=1/2. (Do you see why this is the required sum?) A (commonly?) known formula is that

[tex]\displaystyle \sum F_k\cdot x^k = \frac{x}{1-x-x^2}[/tex], which implies

[tex]\displaystyle \sum F_k \cdot x^{k+1} = \frac{x^2}{1-x-x^2}[/tex]. Then differentiating gives

[tex]\displaystyle \sum (k+1) F_k\cdot  x^k = \frac{x(2-x)}{(1-x-x^2)^2}[/tex], and so

[tex]\displaystyle \sum (k+1) F_k\cdot  x^{k+1} = \frac{x^2(2-x)}{(1-x-x^2)^2}[/tex].

Putting in x=1/2 we get an answer of 6.

zabelman wrote:BTW, if anyone's interested, here's the power series solution.

We will evaluate the sum [tex]\displaystyle \sum_{k=1}^\infty (k+1)F_k\cdot  x^{k+1}[/tex]

I agree with your original summation.  That's a very nice derivation and use of your power series.

[hide]I attempted to use the first few terms of the same summation to check my solution before I posted it.  But the summation converged quite slowly.  Up to [tex]F_8[/tex] (representing 8 tosses of the coin), the summation was barely more than 3.  I still wasn't convinced at [tex]F_{16}[/tex].  Up to [tex]F_{100}[/tex] convinced me.

[/hide]

Yes, rcv, I also drew a state diagram before writing down the two linear equations.  The one change was that I collapsed the "T" state into the start state, because for this problem those two states are equivalent.

Also, for variables, I chose to make them the expected time from each state to the final state, whereas you chose to make them the expected number of visits at each state.  Either way works.


[quote="surge"]I'm taking Pre-Calculus over the summer [freshman currently] at a local college and my math teacher recommended that I take BC next year. Is AB a needed pre-req for BC? If it is, is it possible to self-study the portion needed in about 4weeks? thanks.[/quote]
AB is in no way needed for BC... and ehere do you live that you can take precalc over the summer? I have to test out of precalc here....

Of course Calc AB isn't needed. I studied math like crazy over the summer last year and by the time I went back to school, I learned enough to test out of Algebra 2, Pre-Calculus, and got placed in Calc BC.  :P

Of course, I'll have to find something to do for the next three years of high school though.  :D

haha, good job. Go take some Multivar./Linear Alg./Diff eq. at a local college, or ask for indepedent study credit in "problem solving". :P

BC Calculus is AB calculus + Calculus II, so obviously, AB is not a prereq.

No you dont need it. The class im taking right now is AB, but its BC material, which is why im going directly to calc 2 next year.


For |X|=n≥5.Y is set of subsets of X and |Y|=n+2.For all T belongs to Y then |T|=3.
SHow that:THere exists two subsets A and B of Y such that:$|A\cap B|=1$


correct ans!!! can you give the mechanism?????? and the reason why there is a ring expansion??  :(  :(


inequalities
function
algebra
polynomial
inequalities proposed

Use Jensen for the convex function f(x) = 1 / (x^2 + 1) with the weigths a/3, b/3, c/3 (remember a/3 + b/3 + c/3 = 1) attached to the x-values b, c, a to get

  SUM (a / 3 * 1 / (b^2 + 1)) >= 1 / ((SUM (a/3 * b))^2 + 1) = 1 / (((bc + ca + ab)/3)^2 + 1),

and now it remains to use bc + ca + ab <= 3 and you are done.

Peter

Are you sure the function is convex? I found it is convex only on the interval [hide][/hide].

well,this inequality is a lot more difficult than it seems.coz using muirhead will actually kill u and i cant find a way out of it rite now

using my idea one can at least show 2 of the variables to be equal. you get an inequality in one variable. from that point it should be hard(it is even a polynomial inequality, those are quite easy to handle with some factorization).

Peter

I think we just need to expand it.Use this one:
[tex] (a^2+1)(c^2+1) \geq 2a(c^2+1) [/tex].So we need to prove that:
[tex] 2a^2(c^2+1)+2b^2(a^2+1)+2c^2(b^2+1) \geq \frac32 (a^2+1)(b^2+1)(c^2+1) [/tex]
[tex] \Leftrightarrow a^2+b^2+c^2 +a^2b^2+b^2c^2+c^2a^2 \geq 3a^2b^2c^2+3 [/tex].
This one comes from:
[tex] a^2+b^2+c^2 \geq 3 [/tex]
[tex] a^2b^2+b^2c^2+c^2a^2 \geq 3a^2b^2c^2 [/tex] :)

Here is sln of my student. It has the same idea of Anh Cuong's one, just some different realization.

We have $\frac{a}{b^2+1} = a - \frac{ab^2}{b^2+1} \ge a - \frac {ab^2}{2b} = a - \frac {ab}{2}$
Similarly for other terms. So we get
$LHS \ge a + b + c - \frac {ab+bc+ca}{2} \ge a+b+c - \frac {(a+b+c)^2}{6} = \frac {3}{2}$

Sorry for this pointless post, but Namdung, the solution you posted is so beautiful!The 'official' solution is essentially the same as Anh Cuong's soln.
BTW, can anyone prove/disprove this stronger (possibly wrong  :D) result:
f(a,b,c) >= f(a+b/2,a+b/2,c), where
a+b+c = 3 and f(x,y,z) = x/(y^2+1) + y/(z^2+1) + z/(x^2+1).

[quote=vinoth_90_2004]Prove, when a,b,c are positive and a+b+c=3, then
(a/b^2+1)+(b/c^2+1)+(c/a^2+1) >= 3/2[/quote]
[b]Australian team training:[/b]
Prove, when $a,b,c$ are positive and $a+b+c=3$, then
$$\frac{a}{b^2+1}+\frac{b}{c^2+1}+\frac{c}{a^2+1}\geq\frac{3}{2}.$$


Many of you are aware that MIT's Educational Studies Program (ESP) holds an event called Splash every November.  The courses at Splash are open to students in grades 6-12, and are taught by MIT students, faculty, and alumni.

For the first time ever, ESP is holding "Splash on Wheels," where the Splash program is held somewhere other than MIT.

The first Splash on Wheels is being held [b]Saturday, February 4, 2006, at Hudson High School[/b], with a snow date of February 11.

The cost is $\$7$, which entitles you to enroll in three 90-minute classes.  $\$2.33$ per class is pretty cheap.

Student enrollment opened January 18 and ends January 28, so if you are interested in participating, you should sign up soon.

* The main page for Splash on Wheels is at http://esp.mit.edu/web/takeaclass/Splash%20on%20Wheels.html.
* The course catalog is at http://esp.mit.edu/web/takeaclass/swcatalog.html.
* Online registration is at http://esp.mit.edu/web/takeaclass/swsignup.html.  (You need to make an account to register.)

I hope some of you find this interesting.  Hudson HS sent out announcements, but sometimes important information doesn't reach students.  If this is news to you, tell your friends.

Richard Yanco
Worcester Academy

P.S. I keep entering the subject properly and the system keeps changing to all lowercase, perhaps because "MIT" sets off some capitalization sensor.

i'm teaching for splash on wheels, if you have any questions you could contact me :) it should be lots of fun, see you all there!

Splash on wheels registration has been extended until February 2, so it's not too late to sign up.  There's going to be a lot of cool math, physics, and other topics as well, so you should all go.

(But I'm biased, since I'm directing the program.)

so, did anyone here go to splash on wheels? how did you guys like it? :D
i personally had a blast! it was great :wow:


inequalities
AMC
USA(J)MO
USAMO
inequalities unsolved

For $ n\geq 2$ let $ a_1,a_2,...,a_n$ be positive real numbers such that: $ (a_1\plus{}a_2\plus{}...\plus{}a_n)(\frac{1}{a_1}\plus{}\frac{1}{a_2}\plus{}...\plus{}\frac{1}{a_n})\leq(n\plus{}\frac12)^2$
Prove that: $ max(a_1,a_2,...,a_n)\leq 4.min(a_1,a_2,...,a_n)$

WLOG assume $ \max(a_1,\ldots,a_n)=a_1,\min(a_1,\ldots,a_n)=a_2$. Assume $ \frac{a_1}{a_2}=k^2>4$. So \begin{align*}(a_1+a_2+\ldots+a_n)\left(\frac1{a_2}+\frac1{a_1}+\cdots+\frac1{a_n}\right)&\ge\left(\sqrt{\frac{a_1}{a_2}}+\sqrt{\frac{a_2}{a_1}}+1+1+\ldots+1\right)^2\\&=\left(k+\frac1k+n-2\right)^2\\&\ge\left(\left(\frac{k}4+\frac1k\right) + \frac{3k}4 + n-2\right)^2 \\&>\left(1+\frac32+n-2\right)^2\\&=\left(n+\frac12\right)^2,\end{align*} contradiction

Surprising that such a simple problem has been given in an USAMO> NIce solution John Gunardi.

First, note that $ f(x) \equal{} x \plus{} \dfrac{1}{x}$ is increasing over $ x > 1$. I won't prove it here; this is pretty obvious by differentiating or considering $ a > b > 1$ and plugging everything in. Now, assume that $ a_{n}$ is the maximum and $ a_{1}$ is the minimum, and assume $ a_{n} > 4a_{1}$.

Expand the LHS; we get $ n^{2}$ fractions. We can group these in four classes:

(1) Those of the form $ \dfrac{a_{i}}{a_{i}}$. $ n$ of these.
(2) Those of the form $ \dfrac{a_{i}}{a_{j}}$, where $ 1 < i,j < n$. $ 2\dbinom{n \minus{} 2}{2}$ of these.
(3) $ \dfrac{a_{1}}{a_{n}}$ and $ \dfrac{a_{n}}{a_{1}}$. 2 of these.
(4) Those of the form $ \dfrac{a_{i}}{a_{j}}$, where exactly one of the $ i,j$ is 1 or n. $ 4(n \minus{} 2)$ of these.

We can double-check that we have covered all the fractions by counting the total number of fractions we have. Now, we consider the sum of each class of fractions separately.

(1) Clearly these have a sum of $ n$.
(2) Pair them in $ \dfrac{a_{i}}{a_{j}} \plus{} \dfrac{a_{j}}{a_{i}}$ pairs, which by AM-GM have sum at least 2. Thus the total sum is at least $ 2\dbinom{n \minus{} 2}{2} \equal{} (n \minus{} 2)(n \minus{} 3)$.
(3) Since $ x \plus{} \dfrac{1}{x}$ is increasing when $ x > 1$, the sum of these two fractions is more than $ 4 \plus{} \dfrac{1}{4} \equal{} \dfrac{17}{4}$, by the assumption.
(4) Put these in $ n \minus{} 2$ groups of 4, $ \dfrac{a_{1}}{a_{i}} \plus{} \dfrac{a_{i}}{a_{n}} \plus{} \dfrac{a_{i}}{a_{1}} \plus{} \dfrac{a_{n}}{a_{i}}$. By AM-GM, this is at least $ 2(\dfrac{\sqrt {a_{1}}}{\sqrt {a_{n}}} \plus{} \dfrac{\sqrt {a_{1}}}{\sqrt {a_{n}}})$. By the lemma, we can get that this is more than 5, since $ \sqrt {a_{n}} > 2\sqrt {a_{1}}$.

Now, adding, the sum of the fractions is more than $ n \plus{} (n \minus{} 2)(n \minus{} 3) \plus{} \dfrac{17}{4} \plus{} 5(n \minus{} 2) \equal{} (n \plus{} \dfrac{1}{2})^{2}$, contradiction.


How much time should you spend on an AMC 12 problem before looking at the solution?

If you spend more than twice as much time as you would allow yourself on the real thing, it's time to give up  :wink:

Well it depends on which problem you are doing. If it's something like the problem at the start, you should just look at the solution if you are not getting it, because you are then just wasting time on an easy problem. However, if it's something like the last problem, I would consider sitting at it for about $20$ minutes because it is a hard problem, and you need to learn how to solve the harder problems on your own. :)

I was going to ask a similar question... Instead of the AMC12 what about AIME problems?

Well, the first 5 on the AIME these days are quite similar in difficulty to the last 5 on the AMC 12's

the middle 5 on AIME's shouldn't take more than 20 minutes each either

[quote="mathgeniuse^ln(x)"]For AIME Problems, I believe you should just think about it, and if you are still stuck, look for a hint, and that will probably help.[/quote]

eh...i never look at solutions, i feel that i am wasting an opportunity when i just look at a solution, there are a limited number of aime problems to practice, there is no shame in not solving a problem, you just should go back to it later

although you do have to have some way of learning the methods that you use on the aime...i suggest reading a book on that topic and see if you can apply the idea, sometimes this is not obvious what topic to study, regardless, i feel that i can solve pretty much all the aime problems using this method and given enough time

In recent years... I've felt that the last 5 on AMC were actually more difficult than the first 5 on the AIME.  But regardless, I like spending about at least a solid 20 minutes or more looking at a problem you think you can do but you're just not getting it.  This means that you either are just approaching it wrong or are messing up somewhere, or aren't being very organized in your approach.

Some questions you'll of course be like.. I really can't think of even how to approach this problem.  This will usually mean that you don't know the concept behind the problem, however this is the best way to improve at your problem solving.  Playing around with things until you find something that may look promising.  Thats probably the best skill you can learn for long tests like the AIME and USAMO.  They give you plenty of time so you can just think about problems.  You may not always make actual progress, but creative thinking like that is probably the more useful skill in problem-solving.  So my suggestion is if you're working at it for 15 minutes and you're just getting absolutely nothing, check if you're reading the question correctly, what topic the problem is, and do some reading on that topic.  There are great resources in the AoPSWiki.  Then you should probably check the solution to see if you had a correct approach on your paper or to see if there was some really innovative way to do the problem, and really try to understand their reasoning on it.

On AMC Problems.. I agree with the "alott yourself twice as much time as you would during the actual test"  which basically means about... 20 minutes.


Let $n$ be an even positive integers. $S$ is the set of nonnegative integers $a$ so that $1<a<n$ and $a^{a-1} -1$ is divisible by $n$. Prove that is $S={n-1}$ then $n=2p$ where $p$ is a prime number.

I'm pretty sure it must have been discussed before. It's from a Romanian TST in $2002$.


logarithms
number theory
relatively prime
prime factorization
irrational number

Prove that  $\log_{10} 3$ isn't rational number.

[hide]Suppose it is, i.e. $\log_{10} 3 = \frac{a}{b}$, where $a$ and $b$ are relatively prime positive integers.  Then
\[10^{\frac{a}{b}} = 10^{\log_{10} 3} = 3\]
So
$10^a = 3^b.$

But this is clearly impossible, since $10^a$ is an integer that contains only 2s and 5s in its prime factorization, whereas $3^b$ is an integer that contains only 3s in its prime factorization.  Thus $\log_{10} 3$ cannot be rational.
[/hide]

[quote="blahblahblah"][quote="Gyan"]Okay a slightly different question.. but  related to above ...

Prove that there exist a natural number  $n$  such that $3^n$ starts with   $2005$
(extra credit find $n$)[/quote]

You need to stop being so dense.[/quote]

What exactly you mean by "dense"?

[quote="Gyan"]

What exactly you mean by "dense"?[/quote]

Dense like the decimal expansion of an irrational number in $\mathbb{R}$?


function
analytic geometry
calculus
derivative
real analysis
real analysis unsolved

Let $ A$ be an open subset of $ R^{k}$ which isn't necessarily convex. Give an example of function $ f: A \rightarrow R$ whose partial deriviates are bounded(all partial deriviates are smaller let say $ M$) and is not uniformly continous on A ? (You can choose set A)

Let $ A$ be the subset of $ \mathbb{R}^2$ of points whose polar coordinates $ (r,\theta)$ satisfy $ r>1,\,\minus{}\pi<\theta<\pi.$ Define $ f$ by $ f(r,\theta)\equal{}\theta.$ (We can write this in piecewise fashion in terms of $ x$ and $ y$ by using arctangents of quotients.) The gradient of $ f$ is $ \nabla f\equal{}\left\langle\frac{\minus{}y}{x^2\plus{}y^2},\frac{x}{x^2\plus{}y^2}\right\rangle$ and is bounded on $ A.$ The function $ f$ is not uniformly continuous, as it cannot be continuously extended to the closure of $ A.$

On second thought - did you want partial derivatives of all orders bounded by the same $ M?$ This example doesn't satisfy that.

[quote="Kent Merryfield"]

On second thought - did you want partial derivatives of all orders bounded by the same $ M?$ This example doesn't satisfy that.[/quote]

No, only "first orders", so it's correct

But can you elaborate this "as it cannot be continuously extended to the closure of $ A.$" ?

$ f$ cannot be continuously extended to the line $ \theta \equal{} \pi$.

Motivating force behind coming up with that example: the words "which isn't necessarily convex" in zibi's original post. If you deny convexity, just what can you do with a set? Several things, but this is one of them.


calculus
integration
probability and stats

What is the average squared distance between two randomly and uniformly selected points?
a) on the circumpherence $ x^2\plus{}y^2\equal{}1$
b) inside the circle $ x^2\plus{}y^2\le 1$.

Warning: the explicit use of densities is NOT allowed.

For the moment i have an allowed solution for a) and a non-allowed solution for b)

a) Let $ u$ and $ v$ be two random points independently and uniformly distributed on the unit circle. Note that random points $ u$ and $ \minus{}v$ are also independent. Thus
\[ \mathbf{E}[|u\minus{}v|^2] \equal{} \mathbf{E}[|u\minus{}(\minus{}v)|^2] \equal{} \mathbf{E}[|u\plus{}v|^2].\]
We get,
\[ \mathbf{E}[|u\minus{}v|^2] \equal{} \frac{1}{2}\left(\mathbf{E}[|u\minus{}v|^2] \plus{} \mathbf{E}[|u\plus{}v|^2]\right) \equal{} \mathbf{E}[|u|^2 \plus{} |v|^2] \equal{} \mathbf{E}[1 \plus{} 1] \equal{} 2.\]
b) Let $ u$ and $ v$ be two random points independently and uniformly distributed in the unit disk. Then similarly, $ \mathbf{E}[|u\minus{}v|^2] \equal{}  \mathbf{E}[|u|^2 \plus{} |v|^2] \equal{} 2 \mathbf{E}[|u|^2]$.
This expectation can be easily computed by integration  :roll: - does that count as "explicit use of densities"?

We can also compute it less explicitly  :D. Note that $ \mathbf{Pr}[|v| < r] \equal{} r^2$. Therefore, $ \mathbf{Pr}[|v| < |u|] \equal{} \mathbf{E}[|u|^2]$. We get,
\[ \mathbf{E}[|u\minus{}v|^2] \equal{} 2\mathbf{E}[|u|^2] \equal{} 2 \mathbf{Pr}[|v| < |u|] \equal{} \mathbf{Pr}[|v| < |u|] \plus{} \mathbf{Pr}[|u| < |v|] \equal{} 1.\]

Yury, could you comment on "Therefore" in point b?

I can make this "Therefore" rigorous only using conditional expectation, but i would like to explain this example for beginners...

Yes, we need to use conditional probabilities.
\[ \mathbf{Pr}(|v| < |u|) \equal{} \mathbf{E}_u[\mathbf{Pr}(|v|<|u| \,|\, u) ] \equal{} \mathbf{E}[|u|^2].\]

However, I think that it's much better to show the direct computation than this trick: Consider the distribution of $ |u|$. Its density is $ 2r$ on $ [0,1]$. Therefore,
\[ \mathbf{E}[|u|^2] \equal{} \int_0^1 r^2 \cdot 2r\, dr \equal{} 2\int_0^1 r^3 dr \equal{} 1/2.\]

Спасибо, Юрий. Хотя идеал для б) так и не получился ;)  /thanks/


conics hyperbola geometry incenter circumcircle trigonometry ratio

Here's a hint (it doesn't look helpful, but it is ;) ): try to show that the locus of those $C$ for which $\angle CAB=2\angle CMA$ is the branch of the hyperbola $CB-CA=\frac{AB}2$. In order to do this, think about the other definition of a hyperbola (or any other conic for that matter), the one involving the directrice.

I'll post the solution if it still doesn't ring a bell :).

Hi grobber!
Can you post your solution?Thanks

[quote="pigfly"]Let a triagle $ABC:AB=c,AC=b,BC=a $ such that: $a= b+\frac{c}{2}$ and $M $ be a point in $[AB]:MA=3MB$.
Prove that: <BAC=2<CMA[/quote]
Let D lies on BC such that CD = BC => NB = BD. With N is the midpoint of AB.
We can prove that the incenter of ABC is the circumcenter of AND.
=> $\angle ANO = \frac{1}{2} \angle BAC$
We prove that NO // MC by proving $\frac{KO}{OC} =\frac{KN}{NM} = \frac{2c}{4b +c}$ K is the intersection of OC and AB.

Nice solution [b]Huynh Anh Hao[/b].
My solution is calculative. I'll post only the way how to solve.It can be easily proved
that in this conditions of the problem$ \angle{BAC}=2\cdot\angle{AMC}$ iff
$\frac{\sin{\alpha}}{\sin{\varphi}}=2\cos{\frac{\alpha}{2}}.$
$\frac{\sin{\alpha}}{\sin{\varphi}}=\frac{b}{CM}$ using sine rule in the triangle $AMC$ where$ \alpha= \angle{BAC}$ and $\varphi=\angle{AMC}.$
We can find $CM$ in terms of$ b$ and $c$ (by Stewart's theorem).
On the other hand$ \cos{\frac{\alpha}{2}}=\sqrt{\frac{1+\cos{\alpha}}{2}}$ and
$1+\cos{\alpha}=\frac{(b+c)^{2}-(b+\frac{c}{2})^{2}}{2bc}$.
After this you have only to check  that the  ratios are equal.


Prove that every nonnegative integer can be expressed in the form $a^2+b^2-c^2$, where $a$,$b$, and $c$ are positive integers with $a<b<c$

[hide]For any given non-negative integer k, (k+3=a, $\frac{k^2+5k+8}{2}$=b, $\frac{k^2+5k+10}{2}$=c) will satisfy $a^2+b^2=c^2+k$.
Let's inductively show this.
Base case k=0 is true.  $3^2+4^2=5^2+0$.
Now, let's assume this true for a given k.
Proof is needed for k+1.
$(k+4)^2+{(\frac{(k+1)^2+5(k+1)+8}{2})}^2-{(\frac{(k+1)^2+5(k+1)+10}{2})}^2=k+1$
Set x=$(k+1)^2+5(k+1)=k^2+7k+6$.  Now, (16x+64-20x-100)/4=-x-9=$-k^2-7k-15$.  When one factors the $(k+4)^2$ and subtracts, one gets k+1.  Now, one just needs to show that k+3<$\frac{k^2+5k+8}{2}$ so $k^2+3k+2=(k+2)(k+1)>0$, which is true unless k is between (-2, -1) which isn't the case here.[/hide]

Nice.  I was wondering how to work with the second condition... the problem is almost trivial without it.

By the way, out of curiosity, someone solve this related problem:

Show that every $n \in \mathbb{Z}$ can be written in the form $a^2 + b^2 + c^3$ for $a, b, c \in \mathbb{Z}$.


AMC
AIME
geometry
ARML
USAMTS
AMC 10
AoPS Books

As a rising senior, next year will be my last shot at the AMC 12 and at the AIME. It was after being introduced to the AMC 10 in 10th grade and failing to make it into the AIME that I became determined to do well on the AMC. After some problem-solving practice, I managed to make it into the AIME this year, but with the bare minimum (101). I scored a 2 on the AIME.

Now...is it feasible for me to get a 7 on the AIME if I work hard this year? It's just that 6 is our high school's record, and I want to break it so badly. What I'm doing this summer, basically, is running through a stack of old AMC 12's and AIME's making sure I know how to do every problem.

At the same time, I'm doing practice problems from past NY Mathletes exams. They're 30 minute contests with 6 problems. I've been averaging 3/4 this year and I'm aiming for 5's and 6's next year.

Should I be doing more than just running through practice problems? Are my goals attainable?

Thanks!

What's up with everyone asking if they can reach their goals?  Of course you can.  Will you?  I don't know.  It depends on a ton of things.  If you are going through the problems without giving the solutions much thought then you need to do more.  Practicing problems is good but if you never go back and learn the concepts behind the problems that you missed then you aren't getting the most of those problems.

The best way to learn those concepts is probably to work through the Art of Problem Solving books (both volumes!). Make sure you get the solution packets too, because the solution you come up with to a problem may not be the only one.

Phantom,

Here is a suggestion: Keep track of the kinds of problems you get and miss over the course of taking several AMCs and AIMEs.  Identify your strong points and your weak points.  Focus on developing your weak points.  Going through the AoPS books would certainly give you an idea of the categorization of problem stypes (algebra, geometry, combinatorics, number theory, etc.).

At AoPS we offer courses in most of the material covered on those exams as well as problem series classes that covered hundreds of the most instructive problems from those exams.  If you feel the need for instruction in the areas that you need preparation in most, our goal is to provide that instruction.

Additionally, solving problems is the absolute best way to prepare.  There is a world of problem books out there that are fantastic for developing problem solving skills.  In addition to the old AHSME books the AMC sells pamphlets of all their exams (which you probably know about already), Paul Zeitz wrote a good book called the Art and Craft of Problem Solving that is good when you hit that 120+/5+ area of AMC/AIME scores.  ARML problems are great for that level.  Five Hundred Problems is a great problem book that covers problems from AMC level up to Olympiad level, but it doesn't tell you which is which.  I think it's a great book for students interested in mathematical exploration.

The USAMTS is also a good way to develop the depth of thinking required to solve mid to hard level AIME problems.  USAMTS problems require more exploration, but over a longer period of time and help students form insights to cracking open harder AMC and mid to hard AIME problems.

There are some AMC/AIME Math Jam transcripts, which have problems and discussions of them.  All of the transcripts are [url=http://www.artofproblemsolving.com/Community/AoPS_Y_MJ_Transcripts.php]here.[/url]

By default, I have the highest score on the AIME at my school-- that's because I am the first and only one to take it at my school : ) I actually only got a 4 because I got two wrong that I should have gotten right. Can you believe that I got #1 wrong!!! All that studying and learning number theory and combinatorics-- its a shame when you get tripped up because you don't know how to do long division.


[quote="pvthuan"][quote="barra"][quote="pvthuan"]Prove that if $x,y,z\geq0$, then
\[ \frac{(x^3+y^3+z^3)^2}3\geq x^4yz+y^4zx+z^4xy.  \][/quote]

Obvious?? By AM-GM
$(x^3+y^3+z^3)^2\geq (x^3+y^3+z^3)(3xyz)=3(x^4yz+y^4xz+z^4xy$[/quote]
Yes, that is right. And what about the following
\[ \frac{(x^3+y^3+z^3)^2}3\geq x^5\sqrt{yz}+y^5\sqrt{zx}+z^5\sqrt{xy}.  \][/quote]

The inequality is not correct
For $x=2,y=1,z=1$ we have $LHS=100/3$ meanwhile $RHS=34.$

[quote="barra"][/quote][quote="pvthuan"][quote="barra"][quote="pvthuan"]Prove that if $x,y,z\geq0$, then
\[ \frac{(x^3+y^3+z^3)^2}3\geq x^4yz+y^4zx+z^4xy.  \][/quote]

Obvious?? By AM-GM
$(x^3+y^3+z^3)^2\geq (x^3+y^3+z^3)(3xyz)=3(x^4yz+y^4xz+z^4xy$[/quote]
Yes, that is right. And what about the following
\[ \frac{(x^3+y^3+z^3)^2}3\geq x^5\sqrt{yz}+y^5\sqrt{zx}+z^5\sqrt{xy}.  \][/quote][quote="barra"]

The inequality is not correct
For $x=2,y=1,z=1$ we have $LHS=100/3$ meanwhile $RHS=34.$[/quote]
I think $R.H.S.=32+2\sqrt{2}\geq\frac{100}{3}=L.H.S.$


probability
Ross Mathematics Program
calculus
integration

[img]http://i30.tinypic.com/10mjzuh.jpg[/img]

The books in my collection:

A Course In Probability Theory - Chung K L
An Introduction to Probability Theory - Geiss
An Introduction to Probability Theory and its Applications Vol I - Feller W.
Applied Bayesian Modelling - P. Congdon
Applied Probability - Lange K.
Applied Probability and Stochastic Processes - Bryc
Applied Statistics And Probability For Engineers - Montgomery && Runger
Applied Statistics And Probability For Engineers solution - Montgomery && Runger
CRC - standard probability and Statistics tables and formulae - DANIEL ZWILLINGER
Foundations of Modern Probability - Olav Kallenberg
Foundations of the Theory of Probability - A.N. KOLMOGOROV
Fundamentals of Probability and Statistics for Engineers - T T Soong
Introduction to Mathematical Statistics 6th ed. - P. Hoel
Introduction To Probability - Dimitri Bertsekas And John N Tsitsiklis
Introduction to Probability - Grinstead & Snell
Introduction to Probability 2nd Ed - C M Grinstead & J L Snell
Introduction To Probability Models Sixth Ed -Sheldon M ross
Introduction to Statistical Pattern Recognition 2nd ed. - K. ~censored~
Lectures on Probability Theory and Statistics - Jean Picard
Markov Random Fields And Their Applications - kinderman & snell
Mathematics, Pre-Calculus and Introduction to Probability
Measure Integral & Probability - Capinski & Kopp
Multivariable Bayesian Statistics - D. Rowe.djv
Probability and Finance It's only a game
Probability and its applications - Ollav Kallenberg
Probability and measurements - Tarantola A.
Probability And Statistical Inference - NITIS MUKHOPADHYAY
Probability Demystified - bluman
Probability Theory and Examples second edition - Durrett R
Probability Theory The Logic Of Science - E. T. Jaynes
Probability, random processes and ergodic properties - Gray
Probability, Random Processes, and Ergodic Properties - R. Gray
Probability, Random Variables and Random Signal Principles 2nd ed. - P. Peebles
Probability, Random Variables and Stochastic Processes 3rd ed- Papoulis
Radically Elementary Probability Theory - edward Nelson
Recent Advances in Applied Probability - Springer
Schaum's Outlines - Theory and Problems of Statistics 3rd ed. - M. Spiegel, L. Stephens
Six Sigma and Beyond Statistics and Probability, Volume III - satamtis.chm
Statistics and Probability for Engineering Applications With Microsoft? Excel - W.J. DeCoursey
Statistics for Dummies - D. Rumsey.chm
Statistics Hacks - B. Frey.chm
The Basic Practice of Statistics 3rd ed. - D. S. Moore
Theory and problems of probability - Lipschutz, Seymour
Theory and Problems of Probability, Random Variables, and Random Processes - Hwei P. Hsu
Tutorials in Probability

[url=http://muebook.blogspot.com/2008/10/probability-and-statistics-45-books.html]Download(4 parts)[/url]

How come you have a lot of Probability and Statistic books? How about the other topics like Algebra, Combinatorics, ...?

[quote="mathangel"] How about the other topics like Algebra, Combinatorics, ...?[/quote]

[url=http://muebook.blogspot.com/search/label/mathematics?max-results=20]Find those kind of books here[/url]

Wow!! :omighty:
What a superb collection.
Thanks for sharing ^^


factorial
number theory
prime factorization

The number $10!$, when written in the base 12 system, ends with exactly how many zeroes?
\[ \text{(A)}\ 1 \qquad \text{(B)}\ 2 \qquad \text{(C)}\ 3 \qquad \text{(D)}\ 4 \qquad \text{(E)}\ 5 \]

[hide]A 0 in base 12 is made by a factor of 12, so we just need to see how many pairs of 4's and 3's are in 10. Looking at its prime factorization there are $4$ such pairs.[/hide]


100 boxes contian apples,oranges and bananas.prove that we can choose 51 boxes in such way taht they contain at lease half all appples,and half all orange and half all bananas.


If e(1), e(2), ..., e(n-1) are the nth root of unity (they are not equal to 1) and r(x) is a polynomial of Z[x] is that true that   r(e(1)).r(e(2)).(...).r(e(n-1)) is a integer? How can I show this?

I forgot to say that e(1), e(2), ... , e(n-1) are not roots of r(x).

Just a hint: let $f(x)=a_{0}+a_{1}x+\ldots+a_{n-1}x^{n-1}$ and let $\zeta_{k},$ $k=0,1,\ldots,n-1$ be the $n-$th roots of the unity. Then
\[ \left\vert \begin{array} [c]{ccccc} a_{0} & a_{1} & a_{2} & \ldots & a_{n-1}\\ a_{n-1} & a_{0} & a_{1} & \ldots & a_{n-2}\\ a_{n-2} & a_{n-1} & a_{0} & \ldots & a_{n-3}\\ \vdots & & & & \vdots\\ a_{1} & a_{2} & a_{3} & \ldots & a_{0} \end{array} \right\vert =f\left( \zeta_{0}\right) f\left( \zeta_{1}\right) \ldots f\left( \zeta_{n-1}\right) .  \]
You can easily derive your conclusion from this.


Can you please post your solution, Harazi?

Thank you very much.

Actually, this inequality is not that hard, and we don't need harazi's help to solve problem. It is just a fortuity that noone write solution. ;)

We will prove general inequality [b](*)[/b]:
\[(1+a_1^2+...+a_1^{2k})...(1+a_n^2+...+a_n^{2k})\geq (k+1)^{n}.\]

And now

[b]Lemma[/b]
Let $a,b>0$, $k\in\mathbb{N}$. Then following inequality holds
\[a^k+a^{k-1}b+a^{k-2}b^2+...+ab^{k-1}+b^k\geq \frac{k+1}{2^k}(a+b)^k.\]

It is quite easy, but if you need, I will write a proof later ;)

The rest is simple.
Consider $n-1$-th power of each side of [b](*)[/b], then
\[LHS^{n-1}=\prod_{i<j} \big((1+a_i^2+...+a_i^{2k})(1+a_j^2+...+a_j^{2k})\big)=\]
\[=\prod_{i<j} \big((1+a_i^2+...+a_i^{2k})(a_j^{2k}+...+a_j^2+1)\big)\geq\]
\[\prod_{i<j}(a_j^k+a_j^{k-1}a_i+...+a_ja_i^{k-1}+a_i^k)^2\]
by Cauchy-Bunyakowski.
Apply lemma to each multiplier and get result!!! :D  :D  :D

Yes, this is simple and it is just because it is ugly the reason for which noone posted a solution. But there are some other inequalities just a little bit more difficult :D  :D  :D

Definitely, it is not a simple inequality.  ;)  :D
I just said that it is not so hard for asking your help :)


[quote="aidan"]Evaluate $ \prod^{n}_{r = 0}\tan^{2}\frac{{2^{r}}\pi}{2^{r}+1}$[/quote]
Are you sure its $ r=0$ because then at $ r=0$ we have:
$ \tan^{2}\frac{2^{0}\pi}{2^{0}+1}= \tan^{2}\frac{\pi}{1}= 0$ and the entire thing is zero.

Maybe $ r=1$.  :maybe:

:blush: Yes thanks for noticing the mistake, it's indeed $ r = 1$


Determine, with proof, all values of $ k$ such that the positive integers $ 1, 2, ... 2k$ can be partitioned into pairs $ (a, b)$ such that $ a \plus{} b$ is a square.

[hide="Motivation"] The AMATYC problem was the case $ k \equal{} 8$.  In this case, the unique partition was given by $ (8, 1), (16, 9), (15, 10), (7, 2), (14, 11), (5, 4), (13, 12), (6, 3)$. [/hide]
[b]Follow-up:[/b]  For what values of $ k$ is the partition unique?

For all $ k>90$, this holds. Although, of course, there are still many $ k\leq90$ that has the given property such as $ k\equal{}8$(also if $ k$ is divisible by 4 it works), I wasn't able to find all of them. Also, for the proof of my first statement is very long, I will no post it. Hopefully somebody will find a better solution.

Interesting.  Can you provide at least a sketch of your proof?  (Or perhaps the proof for $ 4 | k$.  So far, all I've got is the rather easy case $ k \equal{} 2n^2 \plus{} 2n$.)

Instead of saying that $ k$ works, I will denote $ a\equal{}2k$ and say $ a$ works if $ k$ works.(I think its easier this way)
The proof relies on the basic concept that if $ a$ works, then for all odd $ t^2\geq2a\plus{}1$,
$ a'\equal{}t^2\minus{}a\minus{}1$
also works. You can see this by pairing the extra $ a\plus{}1,...,t^2\minus{}a\minus{}1$ in your new list of $ a'$ numbers into $ (a\plus{}1,t^2\minus{}a\minus{}1)(a\plus{}2,t^2\minus{}a\minus{}2)...$ and the rest $ 1,..,a$ the same way you did.
Now to see that $ 8$ divides $ a$ implies $ a$ works(same as $ k$ being divisible by 4), we proceed using induction. Note that 0 works(easy) and now assume that all multiples of 8 work up to $ 8n$ for some $ n\geq0$.
Now I use a lemma that I state without proof,
For all integers $ s>0$, there is an integer $ 0\leq t<s$ such that $ s\plus{}t$ is a triangular number.
So for $ n\plus{}1>0$, there must be an integer $ 0\leq m<n\plus{}1$ such that $ m\plus{}n\plus{}1$ is a triangular number. Then,
$ 8(m\plus{}n\plus{}1)\plus{}1$
must be an odd square, say $ t^2$. Rearranging,
$ 8(n\plus{}1)\equal{}t^2\minus{}8m\minus{}1$
This looks very similar to the basic concept. Note that since $ t^2\equal{}8(m\plus{}n\plus{}1)\geq16m\plus{}1$ and $ 8m$ must work as stated in the induction hypothesis, $ 8(n\plus{}1)$ must also work. Thus all multiples of 8 must work.
The rest of the numbers mod 8 can be done in a similar manner, note that 14,18, and 28 all work.


probability
MATHCOUNTS
LaTeX
complementary counting

A sales representative makes sales at about one fourth of all calls. If, on a given day, the representative contacts 5 potential clients, what's the probability that a sale will be made with at least one contact.

[quote="Prime factorization"]It would seem that the probability is:

$ 5 \times \frac{1}{4}> 100 \%$

Therefore, it is guaranteed that the sales representative will make a sale....?

I guess if you want to get technical, the probability is $ 99.\overline{9}$ %. Perhaps I'm completely wrong, seems too simple  :huh:[/quote]

That's incorrect.

[hide="Solution"]Find the probability that he won't make any contacts. That is $ \left( \frac{3}{4}\right)^{5}= \frac{243}{1024}$.

So the probability that he will make a contact is $ 1-\frac{243}{1024}= \boxed{\frac{781}{1024}}$[/hide]

EDIT: So what if I can't subtract in my head? It's not like I have to do MathCounts again... I already messed up on my last chance.

[hide]use complementary counting, just find the probability he wont get any sales, which is $ (\frac{3}{4})^{5}=\frac{243}{1024}$, and subtract that from one the answer is $ \frac{781}{1024}$[/hide]

$ \text{\LaTeX}$ tip: hover your mouse over the latex to see the code, that way you can make better latex strings. aka. parenthess's for fractions (ehmmmmm).

[quote="vishalarul"][quote="Prime factorization"]It would seem that the probability is:

$ 5 \times \frac{1}{4}> 100 \%$

Therefore, it is guaranteed that the sales representative will make a sale....?

I guess if you want to get technical, the probability is $ 99.\overline{9}$ %. Perhaps I'm completely wrong, seems too simple  :huh:[/quote]

That's incorrect.

[hide="Solution"]Find the probability that he won't make any contacts. That is $ \left( \frac{3}{4}\right)^{5}= \frac{243}{1024}$.

So the probability that he will make a contact is $ 1-\frac{243}{1024}= \boxed{\frac{759}{1024}}$[/hide][/quote]
well your answer is incorrect too..

I know that, I'm just saying he was probably just rushing, and if it really mattered, I'm sure he would have put more time in to make sure the answer was right.

[quote="vikas"][quote="xpmath"]He just subtracted wrong, but still had everything right[/quote]

Hello, that still means he got the answer wrong...In mathcounts they care nothing about your work, so i was right in saying the answer is wrong, not the solution, but the answer[/quote]

jeezes

[hide]
$ (\frac{3}{4})^{5}= \frac{243}{1024}$
1- that is:: $ \frac{781}{1024}$
[/hide][/hide]


Suppose that $a$ and $b$ are two distinct positive integers such that $ab(a+b)$ is a multiple of $a^2 + ab + b^2$.
Prove that $|a - b| > \sqrt[3]{ab}$.

[i]Solution:[/i]

Suppse that $gcd(a,b)=d$ then $a=a_1d, b=b_1d$ where $gcd(a_1,b_1)=1$ and we know that $gcd(a_1^2+a_1b_1+b_1^2 , a_1)=gcd(a_1^2+a_1b_1+b_1^2 ,b_1)=gcd(a_1^2+a_1b_1+b_1^2 ,a_1+b_1)=1$ thus $a_1^2+a_1b_1+b_1^2 \mid d$ so that \[ d\geq a_1^2+a_1b_1+b_1^2 >a_1b_1 \Longrightarrow d^3\geq ab \Longrightarrow \mid a-b\mid \geq d >\sqrt[3]{ab} \]


Determine, with proof, the number of ordered triples $ \left(A_{1},A_{2},A_{3}\right)$ of sets which have the property that

$ A_{1}\cup A_{2}\cup A_{3} \equal{} \left\{1,2,3,4,5,6,7,8,9,10\right\},$

and

$ A_{1}\cap A_{2}\cap A_{3} \equal{} \left\{\right\}$.

Each element $ i$ from $ \{1,2,...,10\}$ can belong to only $ A_1$ or belong to only $ A_2$ or belong to only $ A_3$ or belong to $ A_3$ and $ A_1$ or belong to $ A_1$ and $ A_2$ or belong to $ A_2$ and $ A_3$ -- $ 6$ possibilities in total (the cases when the element does not belong to $ A_1$, $ A_2$, or $ A_3$ is impossible as $ A_{1}\cup A_{2}\cup A_{3} \equal{} \left\{1,2,3,4,5,6,7,8,9,10\right\}$ and the case when it belongs to $ A_1$, $ A_2$, and $ A_3$ is impossible as $ A_{1}\cap A_{2}\cap A_{3} \equal{} \left\{\right\}$). There are $ 10$ elements in total hence the number of ordered triples $ \left(A_{1},A_{2},A_{3}\right)$ is $ 6^{10}$.
[b]Answer:[/b] $ 6^{10}$

Hi, just wondering why the following argument doesn't hold:
([color=#FF0000]EDIT: figured it out[/color])

Let each number be represented by a "o", where a hollow "o" means it is within the set and a filled-in "o" (represented by ".") means it is within both of the other two sets [example: if "." with value 3 is in A1, we can simplify by adding "o" with value 3 in A2 and A3]. The sets A1, A2, and A3 can be determined by partitioning the hollow "o"s and filled-in "o"s between 2 dividers, and then assigning numbers 1 thru 10 to the "o"s and "."s without discrimination as to whether it is hollow or filled.

It then becomes a matter of counting the arrangements possible. For simplicity and to avoid overcounting, I took the sets as they appeared in order: A1|A2|A3.

oooooooooo||   becomes (12!/10!2!)*10!=12!/2*(10C0)
.ooooooooo||   becomes (12!/9!2!1!)*10!=12!/2*(10C1)
..oooooooo||   becomes (12!/8!2!2!)*10!=12!/2*(10C2)
...ooooooo||   becomes (12!/7!2!3!)*10!=12!/2*(10C3)
....oooooo||   becomes (12!/6!2!4!)*10!=12!/2*(10C4)
.....ooooo||   becomes (12!/5!2!5!)*10!=12!/2*(10C5)
......oooo||   becomes (12!/4!2!6!)*10!=12!/2*(10C6)
.......ooo||   becomes (12!/3!2!7!)*10!=12!/2*(10C7)
........oo||   becomes (12!/2!2!8!)*10!=12!/2*(10C8)
.........o||   becomes (12!/1!2!9!)*10!=12!/2*(10C9)
..........||   becomes (12!/0!2!10!)*10!=12!/2*(10C10)

Summation gets me to 12!/2*2^10=2^9*12!, which is FAR more than the correct answer of 6^10.

owait i found my mistake now
[hide="oops"] I think the "o"s are ordered when they appear within the sets A1, A2, A3, causing massive overcounting. [/hide]

Anybody who can tell me what is the meaning of A1∩A2∩A3={}?Please?

@Skyletter $A_1 \cap A_2 \cap A_3=\{\}$ means that the intersection of the sets $A_1$, $A_2$ and $A_3$ is empty, that is that those sets have no common elements.

Thanks to rea306 :blush: With your help,I have worked out it.


calculus
integration
parameterization
trigonometry
calculus computations

Let $\vec{F}: xz^{2}\vec{i}+x^{3}\vec{j}+\cos(xz) \vec{k}$ and $\delta$ is a part of elipsoida $x^{2}+y^{2}+3z^{2}=1$ under the  $xy$-plane and $\vec{n}$ denote the normal which is the downest surface. Using Stoke's Theorem Calculate \[\iint_{\delta}\text{Curl}(\vec{F}) \cdot \vec{n}ds\]

The theorem tells you that the surface integral is equal to the line integral of $\vec F$ over the edge of $S$, which is the circle $x^{2}+y^{2}=1$ in the $xy$-plane, oriented clockwise. Parametrize the circle and integrate (or, use Green's theorem).

What i've learned about Stoke's theorem is that it state about calculating \[\iint_{s}\text{Curl}(\vec{F}) . dS\] I dunno about an extra $\vec{n}$ ..... or perhaps they are the same?

[hide="maybe this what you meant"] Since $z=0$ ($xy$-plane) then the boundary curve is $C: x^{2}+y^{2}=1$ that is a unit radius circle the parameterization (clockwise) give us \[\vec{r}(t) = \cos t \, \vec{i}+\sin t \, \vec{j}+0 \vec{k}\qquad 0\leq t\leq 2t\] and \[F(\vec{r}(t))= \cos^{3}t \, \vec{j}+\vec{k}\] with \[\vec{r'}(t) =-\sin t \, \vec{i}+\cos t \, \vec{j}\] By Stoke's theorem \[\iint_{\delta}\text{Curl}(\vec{F}) dS = \int_{2\pi}^{0}F(\vec{r}(t)) \cdot \vec{r'}(t) \, dt = \int_{2 \pi}^{0}\cos^{4}t dt =-\frac{3 \pi}{4}\] [/hide]


geometry
geometric transformation
reflection
homothety
angle bisector
geometry solved

Let K be the Lemoine point of a triangle $\triangle ABC$. If any circle be drawn through B and C cutting the sides AC, AB in the points M and N, show that AK bisect MN.

Since $ABC,AMN$ are similar (in this order of the vertices), $AK$, being the reflection of the $A$-median of $ABC$ in the angle bisector of $\angle BAC$, it must be the $A$-median of $AMN$, because $AMN$ is obtained from $ABC$ through a homothety of center $A$ and then a reflection in the angle bisector of $\angle BAC$.
Actually, it's easier to see than it is to explain, if you ask me :).


topology
function
algebra
domain
advanced fields
advanced fields theorems

I am trying to figure out if the statement in the topic is true for maps $ f: R^n \rightarrow R^n.$

When $ n \equal{} 1$, we can use the fact that every bijective function is either increasing or decreasing, and by using the Intermediate Value Theorem, the map can be proven to be an open map.

However, I don't know how to generalize this result for any $ n$.   I think it is true.

Furthermore, these are some more conjectures about it:

[b](1)[/b] There is a theorem saying that if $ X$ is compact, $ Y$ is Hausdorff, and $ f: X \rightarrow Y$ is continuous and bijective, then $ f$ is a homeomorphism.  Does this theorem remain valid when $ X$ is locally compact?
[b](2)[/b] If $ U$ is any topological space and $ f: U \rightarrow U$ is a bijective and continuous map, then $ f$ is a homeomorphism.

P.S.: I am so sorry, this have been posted in OPEN QUESTIONS.

The statement is true; in fact, it is a special case of Brouwer's [url=http://en.wikipedia.org/wiki/Invariance_of_domain]invariance of domain[/url] theorem. A natural approach is to extend $ f$ to the one-point compactification of $ \mathbb R^n$, which is $ \mathbb R^n\cup\{\infty\} \equal{} S^n$. Since $ S^n$ is both Hausdorff and compact, the result follows. However, for the extension map to be continuous, you must show that $ |f(x)|\to\infty$ as $ |x|\to\infty$. (That is, $ f$ is [url=http://en.wikipedia.org/wiki/Proper_map]proper[/url].) I'm not sure if this statement is much easier to prove than the invariance of domain itself.

(1) is false: let $ X \equal{} [0,1)$ and $ Y \equal{} S^1$, with a natural map from $ X$ onto $ Y$.

(2) is false as well. Let $ U \equal{} \mathbb R^2\setminus (( \minus{} \infty,0)\cup(0,\infty))$, i.e. the plane with a line removed and a point added back in. The map $ f(x,y) \equal{} (xy,y)$ is continuous, but its inverse $ f^{ \minus{} 1}(x,y) \equal{} (x/y,y)$ is not.

[quote="mlok"]The statement is true; in fact, it is a special case of Brouwer's [url=http://en.wikipedia.org/wiki/Invariance_of_domain]invariance of domain[/url] theorem. A natural approach is to extend $ f$ to the one-point compactification of $ \mathbb R^n$, which is $ \mathbb R^n\cup\{\infty\} \equal{} S^n$. Since $ S^n$ is both Hausdorff and compact, the result follows. However, for the extension map to be continuous, you must show that $ |f(x)|\to\infty$ as $ |x|\to\infty$. I'm not sure if this statement is much easier to prove than the invariance of domain itself.

(1) is false: let $ X \equal{} [0,1)$ and $ Y \equal{} S^1$, with a natural map from $ X$ onto $ Y$.

(2) is false as well. Let $ U \equal{} \mathbb R^2\setminus (( \minus{} \infty,0)\cup(0,\infty))$, i.e. the plane with a line removed and a point added back in. The map $ f(x,y) \equal{} (xy,y)$ is continuous, but its inverse $ f^{ \minus{} 1}(x,y) \equal{} (x/y,y)$ is not.[/quote]

Thank you.  I can see my conjectures were all wrong :( .

Just let me add another question: if $ f: X \rightarrow X$ is bijective and continuous, what kind of hypothesis I should have to assure that $ f$ would be a homeomorphism?    What about a more general result when $ f: X \rightarrow Y$ ?

I don't know how to characterize the topological spaces $ X$ such that any continuous bijection $ X\to X$ is a homeomorphism.

If $ f\colon X\to Y$ can be extended to a continuous bijection $ \tilde f\colon \tilde X\to\tilde Y$ where $ \tilde X$ is compact and $ \tilde Y$ is Hausdorff, then $ \tilde f^{\minus{}1}$ is continuous and so is $ f^{\minus{}1}$...


geometry
search
function
geometry unsolved

Let $AA_{1}$,$BB_{1}$,$CC_{1}$ be altitudes in any acute-angled triangle $ABC$. $K$ and $M$ are points on the line segments $A_{1}C_{1}$ and $B_{1}C_{1}$ respectively. Prove that if the angles $MAK$ and $CAA_{1}$ are equali,then the angle $C_{1}KM$ is bisected by $AK$

I am sure that this was posted before, maybe you shoud try search function
[edit] I found it: http://www.mathlinks.ro/Forum/viewtopic.php?t=51165

Bye

What should I type in search box if I want to search??
I don't know what the key word..

Sorry n thx..

I have the same problem, I didn't found this page with search function but in some other way, and always when I want to find some problem, I can't. Get used to it that admins will often bother you about that, just ignore them :D

Bye

Or
http://www.mathlinks.ro/Forum/viewtopic.php?t=6229
There is nothing difficult in typing "MAK bisect*" into the search field, and no reason you should ignore mods (not admins, in most cases). You may need a few tries before finding the right keywords, but this all takes less time than posting a new topic and waiting until someone replies.

  darij


Find all functions $ f: \mathbb R\rightarrow \mathbb R$ satisfying $ f(xf(y)\plus{}f(x))\equal{}2f(x)\plus{}xy$ for every $ x,y\in\mathbb R$

If we fix a nonzero $ x$, we know $ f(x)$ is surjective.
If there is $ f(y_1)\equal{}f(y_2)$ for some $ y_1\neq y_2$, We can get contradiction $ xy_1\equal{}xy_2$ by compare $ P(x,y_1)$ and $ P(x,y_2)$. Hence, $ f(x)$ is bijective.

$ P(x,\minus{}\frac{f(x)}x): f(xf(\minus{}\frac{f(x)}x)\plus{}f(x))\equal{}f(x)$. Since $ f(x)$ is injective, we have, for nonzero $ x$

$ xf(\minus{}\frac{f(x)}x)\plus{}f(x)\equal{}x$, or $ f(\minus{}\frac{f(x)}x)\equal{}1\minus{}\frac{f(x)}x$ --------------- (1)

Now we prove we can always find $ a$ such that $ b\equal{}f(a)\neq 2a$. If $ f(1)\neq 2$, let $ a\equal{}1$. Otherwise, let $ a\equal{}\minus{}f(1)\equal{}\minus{}2$ since (1) implies $ f(\minus{}2)\equal{}\minus{}1$.

$ P(x,\frac{b\minus{}2f(x)}x): f(xf(\frac{b\minus{}2f(x)}x)\plus{}f(x))\equal{}b\equal{}f(a)$. Again, we have, for nonzero $ x$

$ xf(\frac{b\minus{}2f(x)}x)\equal{}a\minus{}f(x)$.

Let $ u\equal{}\frac{b\minus{}2f(x)}x$ for any $ x\neq0$ such that $ f(x)\neq\frac b2$.

$ \frac{f(u)}u\equal{}\frac{a\minus{}f(x)}{b\minus{}2f(x)}\equal{}\frac12\plus{}\frac{a\minus{}\frac b2}{b\minus{}2f(x)}$.

Since $ f(x)$ is surjective, we notice that the only values that RHS, or $ \frac{f(u)}u$ may not take are $ c_1\equal{}\frac12$ and $ c_2\equal{}\frac12\plus{}\frac{a\minus{}\frac b2}{b\minus{}2f(0)}$.

Looking back (1), this implies $ f(x)\equal{}x\plus{}1$ for all but two values $ \minus{}c_1$ and $ \minus{}c_2$.

For any $ x\neq0$, we can always find $ y$  such that $ y\neq \minus{}c_1$, $ y\neq \minus{}c_2$ and $ xy\plus{}x\plus{}f(x)\plus{}1\neq \minus{}c_1$ and $ xy\plus{}x\plus{}f(x)\plus{}1\neq \minus{}c_2$.
Then we have,

$ f(xf(y)\plus{}f(x))\equal{}xf(y)\plus{}f(x)\plus{}1\equal{}xy\plus{}x\plus{}f(x)\plus{}1\equal{}2f(x)\plus{}xy$, or $ f(x)\equal{}x\plus{}1$.

If $ c_2\equal{}0$, we are left to show $ a\equal{}f(0)\equal{}1$.

$ P(0,0): f(a)\equal{}2a$ and $ f(\minus{}1)\equal{}0$ implies $ a\neq0$ and $ f(a)\equal{}a\plus{}1\equal{}2a$. Hence $ a\equal{}1$.


there are $ mn$ coins which have to be distributed into $ m$ purses with $ n$ coins in each purse. (i) find the probability that two specified coins will be in the same purse (ii) r purses have been opened and checked and it has been found that they do not contain either of the coins. find the probability that the two coins will be in the same purse.

I got the first one right and the answer is $ \frac {n\minus{}1}{mn\minus{}1}$. but I'm unable to get the second one whose answer is $ \frac {n\minus{}1}{mn \minus{} rn \minus{} 1}$

The second one is exactly the same as the first one, but with $ m \minus{} r$ purses.   :|


[quote="little boy"]we have \[a,b,c>0,\] proof: \[\sqrt{a^{2}+b^{2}}+\sqrt{c^{2}-\sqrt{3}bc+c^{2}}\geq\sqrt{a^{2}+ac+c^{2}}\] [/quote]

I think you intended $\sqrt{b^{2}-\sqrt{3}bc+c^{2}}$, not $\sqrt{c^{2}-\sqrt{3}bc+c^{2}}$.

Let's construct points $O,A,B,C$ such that $OA=a,OB=b,OC=c$,
and $\angle AOB=\frac{\pi}{2}, \angle BOC=\frac{\pi}{6}, \angle COA=\frac{\pi}{3}$.
Now $LHS$ is equal to $AB+BC$, and $RHS$ is equal to $AC$,
so it is equivalent to $AB+BC\geq AC$, which is trivial by triangle inequality.

I have another solution to yoour problem:
c^2-square root3 *bc +c^2=(c*square root3/2-b)^2+1/4c^2
Then you only use Micopxki and i thinks it's easy for you!


When using mass points how do you distribute the masses when whole sides of triangles are given and you are told to find some internal ratio?


articles search algebra polynomial function domain quadratics

I think the problem is irrelevant, as every number is rational or irrational, by definition, independent of your logics... [and all those alternative logics rather belong to philosophy than mathematics ;)]

[quote="Peter VDD"]I think the problem is irrelevant, as every number is rational or irrational, by definition, independent of your logics... [/quote]
Alright that's something but what I mean is whether you can say for each number to what set it belongs is dependent of your logic and in what way it is. It is a strange question but I'm sure someone will have wondered before and maybe found an answer.

[quote="Peter VDD"]
[and all those alternative logics rather belong to philosophy than mathematics ;)][/quote]
I think I know what you're talking about :D (the Beardman...) but wouldn't it be interesting for mathematicians to know in what way mathematics would change in alternative logics. Isn't that what 'foundations of mathematics' is all about?

Smth related to logic: In an article I read about Bertrand Russel's Paradox, it said that it isn't actually a paradox if we define sets and operation on sets like they said it is now done... can anyone who knows a little about the subject clear this things up for me?

PS: If you want, I'll search that article, but it's gonna take a while, since my files/folders are arranged in a very messy way

Consider $x^2-2=0$

All rationsl roots of this must be integers.....

[quote="seamusoboyle"]All rational roots of this must be integers.....[/quote] :?:

since it's an integer polynomial, if it's factorizable on $\mathbb{Q}$, then it's factorizable on $\mathbb{Z}$. and the leading coefficient is one, so all of its factors (of degree 1) are monic, and then all its roots should be integer..

[quote="mathmanman"]Yeah, well, basically, Russell's paradox (the barber's one, right? :)) is not a paradox anymore if you add something like : the barber is an extraterrestrial, or, he is from another village, etc..[/quote]... wasn't it with a set containg all sets? :?

[quote="K.W.M.A.N"]really nice indeed

btw answering to the set-related question: the paradox cannot be true if you think the axioms of set theory are. Using them, it can be shown that there is no set X containing all x for which a formula $\Phi(x)$ holds. The notation $X=\{x : \Phi(x)\}$ signifies $X=\{x\in A : \Phi(x)\}$, where A is the domain of $\Phi$. This implies many things but also it implies that a set as Russel defines it cannot exist and there is no set containing all sets and many more things.[/quote]

OK, so $S = \{ X : X \not \in X \}$ does not exist.

first of all, is there a set $X$ s.t. $X \in X$? it is correct to take $\{0,\{0,\{0,\ldots\}\} \}$?

second of all, why is the barber's paradox the same with considering $S$?

[quote="perfect_radio"]

first of all, is there a set $X$ s.t. $X \in X$? it is correct to take $\{0,\{0,\{0,\ldots\}\} \}$?

second of all, why is the barber's paradox the same with considering $S$?[/quote]

If you accept the axioms of regularity (foundation) and choice, like in the ZFsystem , it can be shown there isn't. (It might be possible to show without the axiom of choice but I'd rather think it isn't)
Accepting those one can show that $A \in B \in C \ldots \in A$ for no $A,B,C,\ldots$.
However about the 'thing' you take, it is an object from naive set theory but it isn't proven that it actually is a set...  That's where set theory gets a little tricky, whenever you talk about a set you have to proof it actually exists. Oftenly that requires the axiom of choice. (That's why it is so important,I think)

(BTW the proof I mentioned uses the fact that Russells paradox isn't supposed to exist in mathematics to make everthing even more confusing)

Well, as far as I understood the barbers paradox myself:
The barbers paradox talks about a set containing all men in town that do satify the condition 'not shaving themselves'.  The answer of axiomatic set theory is as simple as affective: such a set cannot exist if there are men in town (the domain of the function)about who you don't know whether they satify the condition or not. When you first hear it, it might sound like a stupid solution but it really helps...

[quote="K.W.M.A.N"]However about the 'thing' you take, it is an object from naive set theory but it isn't proven that it actually is a set... [/quote]

Can you prove that it doesn't exist? I'm really interested in this...

As for the connection between $S$ and the "barber", who are the $X$ in the "barber" case? (perhaps I should have formulated my misunderstanding in my previous post)

Such a proof would be very trivial. First of all you'll have to find an expression for your set, this means that you should explain what the three dots mean. Like the set $\{0,2,4,6,8\dots\}$ can be explained as the union of the sets $\{0,2,...,2n\}$ over all natural $n$. (These are all finite sets, there existence can be proven. Theorems states that their union will exist to, so the original set exist.). The only way I can think of to define this set is like $X=\{0,X\}$. But from this definition $X \in X$, a contradiction.

For the paradoxes, when you are looking for thing that both of them have in common don't look too close. What they have in common are these thing: a set is defined in a special (wrong) way, and about there's one element you cannot decide whether it's in the set or not. The way to achieve this are quite different however at first sight. Russel uses self-referring properties for all sets, but this gives problems in only one case. In the barbers paradox you use the relation between the considered element and a special element (the barber) to decide whether is't in the set or not. But when you try this out for the barber, you get another self-referring property giving problems again.

There are different possibilities to define 'sets', one of them being the Zermelo-Fraenkel-Axioms ( I used the german shortcuts for the axioms):
[b]Ex[/b]: it exists a set.
[b]Ext[/b]: two sets with the same elements are identical
[b]Aus[/b]: for every property $\Phi$ of sets and a set $A$, there exists a/the set $\{ x\in A | \Phi (x) \}$ (what exactly is alowed as a 'property' is something more logic based...)
[b]Paar[/b]: for all sets $A,B$ there exists the set $\{ A,B\}$
$\bigcup$[b]-Ax[/b]: for every set $A$ there exists the set $\bigcup_{x \in X} x$ of the elements of the elements of $X$
[b]Pot[/b]: for all sets $A$ there exists the the set $Pot(A)$ of all subsets of $A$
[b]Inf[/b]: there exists a set that contains $\emptyset$ and with every set $A$ also the set $A \cup \{ A\}$
[b]Fund[/b]: for every nontrivial set $A$ there exists a set $B \in A$ that has no element in common with $A$
last but not least:
[b]AC[/b]: for every set $A$ there exists a 'function of choosing', meaning a function $f$ with $f(B) \in B$ for all $\in A$

Note:
$\emptyset$ exists because of Ex and Aus.
$A \cap B$ can be defined as $\{x \in A | x \in B\}$ by Aus.
the axiom of choice (AC) has nothing to do with $x \not\in x$, this follows from Fund (and some of the earlier axioms), try to prove yourself.

[quote="perfect_radio"] Can we accept it, even though its use leads to things totally contrary to any intuition?[/quote]If that was a problem, there would be no quantummechanics. ;)

But I will move this to other problem solving topics, as that's the place for this sort of dicussions.

[quote="perfect_radio"]So a set $X$ s.t. $X \in X$ does not exist. Right?

And what about Tarsky-Banach "paradox" based on AC? To me that's the weirdest theorem I've ever seen in mathematics 'til now. Can we accept it, even though its use leads to things totally contrary to any intuition?[/quote]

Analysis has all sorts of weird creatures in it.  The fact that the Banach-Tarski paradox requires the use of non-measurable sets makes it really not too surprising.

And, just as a side note: "The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?" -Jerry Bona

[quote="K.W.M.A.N"]We all know that $\sqrt{2}$ is not a rational number. We all can proof it using a 'technique' of which I don't know the english name, but let's call it "ex absurdo", I hope you'll understand.
I *think*  there is no straightforward proof or any proof not using such a logical rule, but just saying $x=\sqrt{2}\Rightarrow\ldots\Rightarrow x$ is not rational.

but I was wondering, can facts like this be proven? Does anyone happen to know a proof of this?

I think such question is equal to ask what would be left of mathematics if in you're kind of logic it is not sure that not(not(p)) equals p, but I don't know much on this subject, that's why I posted it here  :)

(I wasn't sure in which topic I should post this, hope it is in the correct one)[/quote]

Your question is actually a really good one!! The method of proof you talk about is called Reductio Absurdum (or proof by contradiction). It is generally accepted as a valid form of proof.

There is a school of mathematics, called Mathematical Constructivism, however, that rejects the Law of the Excluded Middle. This is the law that says that a statement is either true, or its not true. Mathematical constructists hence reject all proofs by contradiction (since all such proofs are based on the Law of Excluded Middle).

The school of Mathematical Constructivism was first kicked off by Kronecker in the late 1800s (although hinted at by Pythagoras thousands of years earlier). Constructivists believe that the only proofs which are valid are "Constructive Proofs" -- sort of like the one you seek for proving that the $\sqrt{2}$ is irrational.

Constructivism is "weird", and certainly out of the mainstream, but not totally ludicris. There is "some" reasonable basis to reject the Law of Excluded Middle, and in fact Mr. Rusczyk himself has said that he doesn't particularly "like" proofs by contradiction.

The study of what kind of statements can and can't be proven without the Law of Excluded Middle has been studied. I believe irrationality of $\sqrt{2}$ can be proven constructively, but it relies on slightly revamped "definitions" of rationality and irrationality and is rather circuitous.

Kronecker, by the way, was the nemesis of Cantor, who used proof by contradiction willingly and often to prove lots of interesting things about infinite sets. Kronecker even went so far as to reject the [i]existence[/i] of several types of infinite sets because they couldn't be constructed explicitly.

Here are three interesting websites about the law of the excluded middle, constructionism, and various schools of philosophy in mathematics:

http://www.chaos.org.uk/~eddy/math/found/reductio.html
http://en.wikipedia.org/wiki/Constructive_mathematics
http://en.wikipedia.org/wiki/Philosophy_of_mathematics

Feel free to do your own search for these topics. There is lots of information about them. A very good book that touches on these things by the way is called [u]Everything and More: A Compact History of Infinity[/u] by David Foster Wallace.

A proof by contradiction of the irrationality of $\sqrt{2}$:

$\sqrt 2 = \frac{m}{n} \Rightarrow m^2 = 2n^2$
Let
$m = 2^{a_2 } \cdot 3^{a_3 } \cdot 5^{a_5 } \cdot ...\; \Rightarrow \;m^2 = 2^{2a_2 } \cdot 3^{2a_3 } \cdot 5^{2a_5 } \cdot ...\; \\$
$n = 2^{b_2 } \cdot 3^{b_3 } \cdot 5^{b_5 } \cdot ...\; \Rightarrow \;2n^2 = 2^{2b_2 + 1} \cdot 3^{2b_3 } \cdot 5^{2b_5 } \cdot ...\; \\$

Since the exponent of 2 in $m^2$ is even whereas the exponent of $2n^2$ is odd,

$m^2 \ne 2n^2$, a contradiction
$\therefore \sqrt 2$ irrational

here is a better proof,

let $f(x)=x^2-2$

by the rational root theorem, if the roots are rational, then $r \in \{\pm1,\pm2\}$, obviously that is not the case, so the roots are irrational, and since $\sqrt{2}$ is a root, it is irrational

But the Rational Root Theorem is usually based on a proof by contradiction.

here is another proof using quadratic reciprocity.
ok this is again a proof by contradiction though.

Suppose $\sqrt2$ is rational i.e. that there are positive natural numbers $a, b$ such that $a^2 = 2 b^2$.

Let $p$ be a prime number satisfying both of:
(1) $p$ > $b$
(2) $p \equiv 3 \text{ mod } 16$
(Dirichlet's theorem guarantees the existence of p)

Then, by (1), $b$ is relatively prime to $p$. So there exist integers $s, t$ with $bs+pt = 1$.
Then $(as)^2 \equiv 2 \text{ mod } p$
But this contradicts (2) according to the law of quadratic reciprocity.

_________________
One minute pray for peace in korea.

Proving the irrationality of $\sqrt{2}$ isn't a constructive goal.  The problem itself is phrased in a way that implies the Law of the Excluded Middle - "Show that there is no expression $\displaystyle\frac{m}{n}$, for $m, n \in \mathbb{N}$, such that $\frac{m}{n} = \sqrt{2}$.  Excluded Middle is part of the definition of irrationality - either it can be expressed as a ratio of integers, or it cannot be expressed as a ratio of integers.

The proof by contradiction shows that no such expression exists (because there must be a smallest such expression in lowest terms, and unless you're implying that an infinite number of [i]different[/i] fractions in lowest terms can express $\sqrt{2}$, then there is no expression, by the proof).  Hence, the proof is entirely valid given an acceptance of the axioms of arithmetic.  If you want a constructive proof, you'll have to re-formulate your axioms and your definitions.

$ \sqrt 2$ being irrational is a constructive property:

At first one needs to define [i]irrational[/i]. As we have a notion or rational (being in $ \mathbb Q$), it's quite standard to define it the following way:
$ a \in \mathbb R$ is called [i]irrational[/i]   $ : \iff$    $ \lnot ( a \in \mathbb Q)$.

Even if this seems a trivial definition, it will be essential later. But we must not forget one thing: what does $ \lnot$ even mean¿
One rather common definition of $ \lnot A$ for some property $ A$ is: $ A$ implies "something wrong". For this, one defines the [i]falsum[/i] $ \bot$ to be some symbolmeant to represent "falsiness". Thus $ \lnot A$ stands for $ A \implies \bot$
This symbol $ \bot$ is what diverses different types of logic:
- minimalistic: no property on $ \bot$.
- intuitionistic: for all $ A$ we have $ \bot \implies A$ (EFQ = Ex Falso Quodlibet: a wrong statement implies everything).
- classical: for all $ A$ we have $ \lnot \lnot A \implies A$ (TND = Tertium Non Datur: at least one of $ A$ and $ \lnot A$ must be true).

Note that the classical one implies the intuitionistic one. But still, we can prove the following using intuitionistic logic only:
If $ a \in \mathbb R$ and $ a^2\equal{}2$, then $ a$ is irrational.
Proof (sketch):
In intuitionistic logic, we can prove that $ 2$ is prime (meaning that $ 2|xy \implies 2|x \vee 2|y$).
Then we can use the standard proof again to show that $ \exists a \in \mathbb Q: a^2\equal{}2$ leads to a contradiction:
If $ (m,n)$ is a minimal pair in respect to $ m^2$ with the property $ P(m,n) : \equal{} (m^2\equal{}2n^2)$, then we get a smaller pair, thus it is not minimal.
Essentially, we proved: $ \left( \exists a \in \mathbb Q: a^2\equal{}2 \right) \implies \bot$, meaning that $ \lnot \left( \exists a \in \mathbb Q: a^2\equal{}2 \right)$ meaning that $ \sqrt 2$ is irrational.


AMC USA(J)MO USAMO inequalities geometry induction circumcircle

what do you think the cutoff will be ? :idea:  :?:

lol I bet winner is more like 29 = 7+7+7+7+1 :O

mop ... blue probably 21-22? red I have no idea. 9-10? but partial credit may have been hard

[quote="not_trig"]mop ... blue probably 21-22? [/quote]

Dang, then I probably missed by 1-2 points. Oh well.

Actually I think red might be as low as 7 because (a) a lot of people will lose points on 1, (b) 1 and 4 were harder than usual, in my opinion, or at least much harder for people who didn't prepare as much. I think last year's 1 and 4 weren't necessarily a whole lot easier but they required less experience.

[quote="JSteinhardt"]Blue: 16[/quote]

:O

I sure hope this won't happen for my own selfish sake because then I would have missed MOP because I didn't solve #1.

[quote="JSteinhardt"]I doubt many 9th graders can solve either 1 or 4. My prediction:

Red: 7
Blue: 16
HM: 21
Black: 28

Based around solving just 1 or 4, two of 1,2,4 and also 3a, all three of 1,2,4, or any four of six.[/quote]

Yay I may actually qualify if I get no partial credit! :lol:

[quote="dnkywin"][quote="JSteinhardt"]I doubt many 9th graders can solve either 1 or 4. My prediction:

Red: 7
Blue: 16
HM: 21
Black: 28

Based around solving just 1 or 4, two of 1,2,4 and also 3a, all three of 1,2,4, or any four of six.[/quote]

Dude if blue is 16 then there must be a god.  :wink:

Yeah, since my prediction is 710710[/quote]

what 1 point may be unlikely

[quote="JSteinhardt"]I doubt many 9th graders can solve either 1 or 4. My prediction:

Red: 7
Blue: 16
HM: 21
Black: 28

Based around solving just 1 or 4, two of 1,2,4 and also 3a, all three of 1,2,4, or any four of six.[/quote]

Wow, are you implying this is the hardest usamo in the recent four years (I only had information about the cutoff for the last three years).

EDIT: this is based on the blue mop cutoff.

I did embarassingly poorly on this USAMO, but I'll toss in some ideas.
Last year's number 1 was harder than this year's in that it took more thinking, even if you knew number theory. This year's number 1 was pretty much a question of whether you were aware of the concept of a radical axis. I didn't solve number 1 because I only had a vague idea of radical axes, and gave up. When I went home I looked it up and got the result as soon as I wrote the theorem out on paper.

On the other hand, another person at our school spent over 4 hours working out the theorem without any idea of it, and eventually got it. Last year's number 1 required very little previous number theory experience, and could be done if one really persisted at it.

Number 4 was somewhat more knowledge intensive as well, in that you needed some sort of inequalities knowledge to deduce some helpful information.

So perhaps the red MOP cutoff will be lower like people have already said?

[quote="JSteinhardt"]I doubt many 9th graders can solve either 1 or 4. My prediction:

Red: 7
Blue: 16
HM: 21
Black: 28

Based around solving just 1 or 4, two of 1,2,4 and also 3a, all three of 1,2,4, or any four of six.[/quote]

Wait, a blue MOP cutoff that's [i]5[/i] points below the HM cutoff  :huh: . To the best of my knowledge that's only ever happened once, in 2006, when ridiculously many people were seniors/were Canadian/went to RSI etc., and there were like, only 2 HMs in blue MOP. I don't see that happening again anytime soon.

I'd personally predict something like HM:21, Blue: 19, or something more like that.

Hopes:

Red:6

Predictions:

Red: 9 (there are probably at least 20 freshmen that are beasts at inequalities or geometry)
Blue: 20
HM: 24
Black: 27

For me,
4<2<1<5<6<3

actually, 1,5, and 6 can be permuted in any order; i didn't solve any of them, just wrote down a bunch of bs. For 3 i couldn't even think of bs to write down, so i drew a smiley face.

hmm... it's interesting how so many people think 3 was very hard
my proof for it sucked and wasn't rigorous at all, but i definitely came up with a lot of stuff to write down - not complete bs, but that actually made some sense.

i'd say

4<2<6<3<1<5 for me personally
(i'm horrible at geometry, especially cyclic quads)

as a geometry person (though I also spend an disproportionate amount of time solving inequalities...)

1<5<4<2<6<3

lol... well maybe 4<5, but 5 took me less time

[quote="matheoteque"]hmm... it's interesting how so many people think 3 was very hard
my proof for it sucked and wasn't rigorous at all, but i definitely came up with a lot of stuff to write down - not complete bs, but that actually made some sense.[/quote]
There's a big difference between that and solving the problem, unfortunately.

hmm...

1<4<2<5<3<6

dang, it is actually in order for me =-O

Hmm... actually for me it was

4<3a<2<6<1<5<3b

Since I'm pretty bad at geometry....

Dude, I hope that JSteinhardt is right, because if my potentially bogus solution to 3a is correct I have a chance of being on the bottomof blue.

Anyway, this test makes me realize that I would be pretty good if I knew geometry...

2(solved, but took too long on)<4(9 pages...don't ask, but got it)<3a(only if I got it, lol)<1(blah, geometry)<5(knew it would be geo)<3b(wrote nothing)<6(eh, I think I proved that it is sufficient to prove only one of the two, is that a point?)

So my prediction is something like 0-6-0-7-0-1, but if 3a is right, it gives me 17.

Knowing that I am weak on geo, I practiced a lot of it before USAMO. I thought that I would be fine with #1 or #4 algebra, but I think I am going to get 2 on #4... What's even worse is that many people are saying that #4 was easier than #1. Maybe I should have focused more on #4 than #5.

For #5, I did a whole bunch of angle chasing to no avail. #6, I had no idea how to start. #3, I thought I had a solution for chessboard rectangles, only to realize soon later that they wanted chessboard polygons.

This was a terrible USAMO for me. As a 3-time USAMO qualifier, I expected my score to jump high this year, but I got owned by the problems. 1<4<2<3<5<6

[quote="greentreeroad"]Based on posts since the exam, I think it's reasonable that 4<2<1<3a<5=6<3b[/quote]
hmm, i agree with this

I disagree with 2 < 1, but it's personal preference. 2 was definitely a lot more classic than 1, with problems like that being relatively common, but 1 was easier if you haven't done many problems, as long as you know about radical axes.

I thought 2 was easier than 1 but I would assume that this is because I like combo a lot and I am not a very big fan of geometry. Actually I think I got 2 faster than I got 4 but I used more trickiness on 2 so I would still call it harder. So yeah I would probably have the same ranking except maybe with 6 easier than 5 because 5 was geometry. Although I guess I can't really make a very informed decision on those two because I can't do either?

My best subject is geo (so when I turned around the day 1 problems, I was very happy).  However, at the end, I managed to get nothing done for 1, but got the answer, and most of the proof for 2 (although its sketchy, might be as low as 2 or as high as 6).  So I have to say that it is something like 4<2<1<5<3<6.

4 actually wasnt that bad, but I was pressed for time (spent 3 hours on number 5) so I didnt finish my proof.

I hope the MOSP blue cutoff is like 18 or so because one of my friends probably got somewhere around there.  I am pretty sure someone from my school made red (we've only had 4 people ever qualify) unless something goes horribly wrong.

Putting the USAMO problems in order of difficulty seems very subjective... besides the fact that everyone has their own preferences, some problems have more than one part, most of which might be "easy" but one of which might be very difficult.  Like #1 this year, applying radical axes might be "hard," but after that the problem is "easy."  So really it might be interesting to put in order the relevant observations of each question.

But I'm too lazy to do that  :lol:

For me, 4<1<2<6<5<3, since I'm no good at geometry; but I also think an elegant solution to 2 is rarer than a neat solution for #1.


tom is walking a cross a bridge on the train track
 when he is 5/12 of the way across the bride he notices a train bearing down on hem at 90 k/h if he can just escape death by running in either direction how fast can tom run

Which way is the train coming, from behind him or in front of him?

I dont think it matters.. it says he can run either direction, which seems to indicate that the train would be coming from any direction..

So, the fastest he can run is when he just escapes death running over the last 7/12ths of the bridge?

[hide=" If the distance he must travel is"] $\frac{7}{12}$
His speed $x$ is
$\frac{\frac{7}{12}}{x}= \frac{1}{90}$
$x=52 \frac{1}{2}$
Which seems impossible.
[/hide]
[hide=" If the distance he must travel is"] $\frac{5}{12}$
$\frac{\frac{5}{12}}{x}= \frac{1}{90}$
$x=37 \frac{1}{2}$
Which still seems impossible.
[/hide]

Notice Tom can [i]just[/i] escape death, implying that at the moment that he leaves the track, the train has either just entered the bridge or just crossed it (so it's right next to him). Since Tom runs more if he runs forward, the train should be coming from behind to take longer to get to that side of the bridge (that sentence must be so confusing).
[hide]
If Tom runs backwards 5/12 of the bridge length, the train reaches the beginning of the bridge. So, if Tom runs forwards 5/12, then the train will also reach the beginning of the bridge. Then, Tom runs the remaining 1/6 of the bridge, and the train goes over the entire bridge in the same time period, so Tom is running 1/6 as fast as the train, and so his speed is 15k/h.
[/hide]

That solution makes more sense, I did not understand the problem correctly.
$15 \frac{km}{hr}$ is the right answer.


I am ur new mod please pour in ur suggestions ....about every possible thing including the marathon :)

We should regenerate the marathon after 13th. :)

yes sure that's a great idea probably we can rope in people from goiit and elsewhere and start a nice marathon :)

could you revive this forum seems like the weekly problems are not going to start any time in the near future at least so could you at least start one.Please.
Thanks in advance thala..................

i am ok with the weekly probs if we can atleast have 10-15 people or so to start with

i sure am goin to join so pardesi please start that weekly quiz..........

I'm now one of your mods; we should do more probs.

Oh! Good Congrats! and yes we should post more problems :D


Hello all,

This is my first post here. My problem is with this matrix, I can't remember how to come up with the second step, and therefore I can't find out how to do the rest of it.

The problem is:

6x     - 5z = 17
5x - y - 3z = -1
2x + y      = -41

| 1 0 0 ? |
| 0 1 0 ? |
| 0 0 1 ? |

So far all I've been able to come up with was:

| 6  0  -5  17 |
| 5 -1 -3   -1 |
| 2  1  0  -41 |

| 1  0  -5/6  17/6 |
|                        |
|                        |

I know that next I need to find the "0" in the second row, but I don't understand how to do that.

Remember that in an equation, there needs to be an equality, so a single matrix won't do.  Your matrix would have to be square anyway to be invertible.  You have the correct values, but the right side of the equation is a vector.  So you have:

$\displaystyle A\widehat{x}= \widehat{b}\implies \left| \begin{matrix}6 & 0 &-5 \\ 5 &-1 &-3 \\ 2 & 1 & 0 \end{matrix}\right| \widehat{x}= \left| \begin{matrix}17 \\-1 \\-41 \end{matrix}\right|$

The solution $\widehat{x}$ is then:

$\displaystyle \widehat{x}= \left| \begin{matrix}6 & 0 &-5 \\ 5 &-1 &-3 \\ 2 & 1 & 0 \end{matrix}\right|^{-1}\left| \begin{matrix}17 \\-1 \\-41 \end{matrix}\right|$

The first thing you have to ask yourself is if the matrix is invertible, which you can determine easily by checking $\det{A}\neq 0$.  Then invert it, and multiply by $\widehat{b}$.  In the case that the determinant [i]is[/i] 0 you still have a set of solutions in some cases but that involves null-spaces and a whole lot of stuff you don't want to jump into just yet :)

If you're not that familiar with Gaussian elimination for matrix inversion, then start out using Cramer's rule for small matrices.  You can search online for either of those processes and get some good instructions on how to use them, much better than I could explain in a single post.

Gaussian elimination is more fundamental than determinants, than inverses, than Cramer's rule. Gaussian elimination can cope with non-square systems and with non-invertible matrices. Our original poster needs to learn Gaussian elimination.

Back to the original post: dividing the first row by 6 might not have been the most effective thing to have done, assuming you are a human using pencil and paper - but you did it. Just leave yourself a large scratch area for adding fractions, and be careful with the fractions.

General idea: operate on rows but plan by columns. You would like to create zeros in the first column in all but the first row. You have a new version of that first row - the one that starts with a 1. Use this new row as a tool. Subtract 5 times the (new) first row from the second row. Then subtract 2 times the same new first row from the third row.

Once you've done these, what does what you have now look like?


Let $ a,$ $ b$ and $ c$ are non-negative numbers such that $ ab \plus{} ac \plus{} bc\neq0.$  Prove that:
\[ \frac {a^3 \plus{} b^3 \plus{} c^3}{ab \plus{} ac \plus{} bc}\leq
\frac {a^3}{b^2 \plus{} bc \plus{} c^2} \plus{} \frac {b^3}{a^2 \plus{} ac \plus{} c^2} \plus{} \frac {c^3}{a^2 \plus{} ab \plus{} b^2}\leq\frac {a^5 \plus{} b^5 \plus{} c^5}{a^2b^2 \plus{} a^2c^2 \plus{} b^2c^2}
\]

It's quite difficult. Anyway I'll try it.

The inequality is very nice arqady  :)
Here is my solution
By Cauchy-Swartz inequality we have that

$ \sum\frac{a^3}{b^2\plus{}bc\plus{}c^2}\geq\frac{(a^3\plus{}b^3\plus{}c^3)^2}{\sum (a^3b^2\plus{}a^3bc\plus{}a^3c^2)}$

So it remains to prove that $ \frac{(a^3\plus{}b^3\plus{}c^3)^2}{\sum (a^3b^2\plus{}a^3bc\plus{}a^3c^2)}\geq\frac{a^3\plus{}b^3\plus{}c^3}{ab\plus{}bc\plus{}ca}$

which is equivalent to $ \sum_{sym} a^4b\geq \sum_{sym} a^3b^2$ which is true by Muirhead or AM-GM

For the other side now .
By the Cauchy-Swartz inequality we have that

$ (b^2\plus{}bc\plus{}c^2)(a^4b^2\plus{}b^3c^3\plus{}a^4c^2)\geq (a^2b^2\plus{}b^2c^2\plus{}c^2a^2)^2$

so $ \sum\frac{a^3}{b^2\plus{}bc\plus{}c^2}\leq\frac{\sum a^3(a^4b^2\plus{}b^3c^3\plus{}a^4c^2)}{(a^2b^2\plus{}b^2c^2\plus{}c^2a^2)^2}$

So it remains to prove that
$ \frac{\sum a^3(a^4b^2\plus{}b^3c^3\plus{}a^4c^2)}{(a^2b^2\plus{}b^2c^2\plus{}c^2a^2)^2}\leq\frac{a^5\plus{}b^5\plus{}c^5}{a^2b^2\plus{}b^2c^2\plus{}c^2a^2}$

or equivalently $ a^3\plus{}b^3\plus{}c^3\geq 3abc$ which is clearly true and we are done .

Beautiful!
My solution for the left inequality is the same. But your proof for the right inequality is more better.


calculus
analytic geometry
graphing lines
slope
ratio
function
calculus computations

An exercise from James Stewart's "Calculus Early Transcendentals" asks for the points on the lemniscate $2(x^{2}+y^{2})^{2}=25(x^{2}-y^{2})$ at which the tangent line is horizontal. I was able to solve the problem, but I had difficulty excluding the possibility of a horizontal tangent line at the origin, since my expression for dy/dx is undefined at the origin. I finally resorted to polar coordinates, but this technique appears seven chapters later in the book. Is there a reasonable way to show, using Calculus I methods, that the curve does not have a horizontal tangent line at the origin?

I assume you have $\frac{dy}{dx}= \frac{x(25-4(x^{2}+y^{2}))}{y(4(x^{2}+y^{2})+25)}.$

Suppose $(x,y)$ is very close to the origin, but not the origin itself. The chord line connecting the origin to $(x,y)$ has slope $\frac{y}{x}.$ At the same time, try evaluating the expression above; very near the origin, $4(x^{2}+y^{2})$ is much smaller than $25.$ Hence we have $\frac{dy}{dx}\approx\frac{x}{y}.$

If the curve truly has a tangent line, then the slope of the chord and the slope of the tangent should tend to each other in the limit. Our two estimates of that slope are reciprocals of each other, and the only way that reciprocals can be equal is for the ratio in question to be either $1$ or $-1.$ Hence our candidates for possible slope of tangent lines at the origin are $+1$ and $-1.$ Of course, once you see the graph, you see that in a sense, these are both right.

That's not a particularly rigorous argument. In fact, the theorem of multivariable analysis known as the Implicit Function Theorem has the hypothesis that the gradient of $F(x,y)$ be nonzero in order for $F(x,y)=0$ to define a smooth curve at a certain point. That hypothesis is violated here at $(0,0),$ and in fact we don't have a curve at all at the origin - we have a pair of crossing curves, which is a different thing.


Let $A$ be a set of $n$ non-negative integers. We say it has property $\mathcal P$ if the set $\{x + y \mid x, y \in A\}$ has $\binom{n}{2}$ elements. We call the largest element of $A$ minus the smallest element, the diameter of $A$. Let $f(n)$ be the smallest diameter of any set $A$ with property $\mathcal P$. Show that $n^2 \leq 4 f(n) < 4 n^3$.

[hide="Comment"](If you have some amount of time, try a best estimative for $f(n)$, such that $f(p)<2p^2$ for prime $p$).[/hide]

From the appearance of the expression $\binom{n}{2}$ I think it's safe to suppose that we take $x$, $y$ distinct.