A sequence of functions $\, \{f_{n}(x) \}\,$ is defined recursively as follows:
\[f_{1}(x) = \sqrt{x^{2}+48}, \quad \mbox{and}\\ f_{n+1}(x) = \sqrt{x^{2}+6f_{n}(x)}\quad \mbox{for }n \geq 1. \]
(Recall that $\sqrt{\makebox[5mm]{}}$ is understood to represent the positive square root.) For each positive integer $n$, find all real solutions of the equation $\, f_{n}(x) = 2x \,$.

[hide]
I claim that $ x\equal{}4$ is the only solution. I will first show it is a solution for all $ n$ by induction.

Base case: $ n\equal{}1$
$ 2x\equal{}8\equal{}\sqrt{4^2\plus{}48}\equal{}\sqrt{x^2\plus{}48}\equal{}f_{1}(x)$
so $ x\equal{}4$ works

Induction step: Assume $ x\equal{}4$ is a solution for $ n$; I will show it a solution for $ n\plus{}1$
$ 2x\equal{}8\equal{}\sqrt{4^2\plus{}6\cdot 8}\equal{}\sqrt{4^2\plus{}6\cdot 2x}\equal{}\sqrt{4^2\plus{}6f_{n}(x)}\equal{}f_{n\plus{}1}(x)$

Okay so now that I know $ x\equal{}4$ works for all values of $ n$, I will show that no other value of $ x$ works for any value of $ n$. I will do this by showing that

i) If $ x<4$ then $ 2x<f_{n}(x)$
ii) If $ x>4$ then $ 2x>f_{n}(x)$

I will use induction again to do this.

Base Case: $ n\equal{}1$
i) $ x<4$
$ x^2<16$
$ 3x^2<48$
$ 4x^2<x^2\plus{}48$
$ 2x<\sqrt{x^2\plus{}48}$
$ 2x<f_{1}(x)$

ii) $ x>4$
$ x^2>16$
$ 3x^2>48$
$ 4x^2>x^2\plus{}48$
$ 2x>\sqrt{x^2\plus{}48}$
$ 2x>f_{1}(x)$

Inductive step: Assume (i) and (ii) are true for $ n$; I will show they are true for $ n\plus{}1$.

i) $ x<4$
$ x^2<4x$

$ 2x<f_{n}(x)$
$ 4x<2f_{n}(x)$

$ x^2<2f_{n}(x)$
$ 3x^2<6_{n}(x)$
$ 4x^2<x^2\plus{}6_{n}(x)$
$ 2x<\sqrt{x^2\plus{}6_{n}(x)}$
$ 2x<f_{n\plus{}1}(x)$

ii) $ x>4$
$ x^2>4x$

$ 2x>f_{n}(x)$
$ 4x>2f_{n}(x)$

$ x^2>2f_{n}(x)$
$ 3x^2>6_{n}(x)$
$ 4x^2>x^2\plus{}6_{n}(x)$
$ 2x>\sqrt{x^2\plus{}6_{n}(x)}$
$ 2x>f_{n\plus{}1}(x)$

So now I have shown that $ x\equal{}4$ is the only solution.
[/hide]

Well it seems that's all of the practice problems  :)


articles
AMC
AIME
algebra
system of equations

This problem is in the wiki article for fibonacci, but the link to the solution is to the wrong place...

Find $ a$ if $ a$ and $ b$ are integers such that $ x^2 \minus{} x \minus{} 1$ is a factor of $ ax^{17} \plus{} bx^{16} \plus{} 1$.

How would you solve this?

I suppose you could perform long division and set the remainder equal to zero, but this would be quite an ugly solution.

You should read about how one proves Binet's formula.

Anyways, notice that whatever the roots of $ x^2 \minus{} x \minus{} 1$ are, they will be roots of the second expressions. So plug those in for $ x$ and set equal to zero, and you have a system of equations, two equations, two variables..
and solve.

Actually, look at Binet's formula, and see the similarities...

Yea, I just realized how much less ugly that would be..

This is [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=458060#458060]1988 AIME Problem 13[/url].


algebra
polynomial
linear algebra
matrix
superior algebra
superior algebra unsolved

Hi,
I have a problem for which I can not find a solution, although it seems to be "easy".

Ultimative goal is to prove following: assume we have an infinite closed field $k$ of characteristic 0. Let $f_1,\ldots,f_n$ be polynomials in s variables over k. Prove the following: if $\text{tr deg}_k k(f_1,\ldots,f_n)=t$, then there exists $t$ polynomials $g_1,\ldots,g_t$ such that

\[
k(f_1,..., f_n) \subset k(g_1,...g_t), (\star)
\]
 where $\text{tr deg}$ means transcendence degree.

I think we can reduce the problem to the following: if $f_1,f_2$ are two algebraic dependent polynomials in $s$ variables (i.e. $h(f_1,f_2)=0$ for a non-trivial polynomial $h$), then there exist a polynomial $f$ and two polynomials$ h_1,h_2$ such that $f_1=h_1(f), f_2=h_2(f)$.

The case $s=1$ is trivial and what I think is that this is also an equivalence (the proof of the opposite direction needs to know how to compute the transcendence degree with the rank of the matrix built out with gradients of the polynomials and make use of the chain-rule, not that difficult).

Using theorem of primitive element, one can easily prove the first claim, if instead of $t$ polynomials, one admits $t+1$ polynomials (proof: $\text{tr deg} \ldots = t$ means that we can find a subset of size $t$ of the polymials $f_1,...,f_n$ such that $k(f_1,...,f_n)$ is algebraic over $k(f_1,...,f_t) $ (wlog). Since a field of characteristic 0 is always separable, one can apply the theorem of primitive elements and find a new polynomial such that the equality in $(\star)$ is fulfilled.)

I think this should be a known problem, but, as I said, I cannot find any solution and I don't even know if the claim is true... Any guess? Thx a lot...  :oops:

Really nobody has an idea? If you don't have a proof, what do you think about it? Is it possible that it is correct?

Is this too easy? Too stupid? :?  :?

Please... say something...


The Tournament of the Towns 2005 Spring problems may be discussed.

[hide="old message"]As some of you know, the 2005 spring season of [b]Tournament of the Towns[/b] is coming up.

I'm not well aware of how the contest is organized Internationally, but I do know that different cities are holding the contest on difference dates. It seems to me that two different cities may be writing the same contest several weeks apart.

Last fall season, we were not aware of this issue, so some problems were posted prematurely. We do not want this to happen again, for it would ruin the integrity of the contest as well as the forum.

So, first, if you know when your city is writing the contest, please post the dates here, so that we have an idea the time span of the competition.

Secondly, to all moderators, please try to prevent Tournament of Towns 2005 spring problems from being discussed before we are supposed to.

Now, students in [b]Toronto, Canada[/b] are writing the O-level contest on Feb 20 and A-level on Feb 27. If you are planning to write the contest there, you must register and confirm your participation on the [url=http://www.math.toronto.edu/oz/turgor/index.php]website[/url].[/hide]

Toronto always writes WAY before Calgary.  Haven't heard dates but we usually write it in March.

[quote="ln(dx/dy)"]What is this and how do you register for it?[/quote]

It's a math contest. You can only do it if your city participates in it.

[quote="sran"]What are the requirements for participation? What type of contest is it? Where should we go to find out more about it?[/quote]

If you want to see what the test papers are like, you may find them [url=http://www.math.toronto.edu/oz/turgor/archives.php]here[/url].

It's a contest for high school (or below) students. Contact your local university to see if your city is involved in the competition. If not, then it probably isn't worth the effort.

On the other hand, [b]when are your cities doing the T of Towns?[/b] I know that many Mathlinkers here have taken part in it.

Edmonton and Calgary are writing the O-level on April 9th.  Typically the next level is then written 2 weeks later.

[b]Edit:[/b]  Finally, official dates.  Calgary writes on April 10 and April 24.

Well, Sarah, we Vancouverians write even later!  :D

We just wrote the O-level on April 11th, and perhaps the A-level at the end of this month, or even May?  :lol:

p.s. Anyone thought the O-level was easy? I left after 90 minutes...

[quote="al.M.V."]=

p.s. Anyone thought the O-level was easy? I left after 90 minutes...[/quote]

One of the many times my mind has blanked out on me.  It took me an hour to finally let the problems sink in and at least another hour to solve them.

The A Level is so easy .... I got 16  :)

I could not write A level. I forgot to write it! :(
This year's problems are so beautiful like other year's. T of T has [b]the best [/b]math problems(in my perspective). I love T of T problems. :)

It wasn't so easy, A level I mean.........
How many points i must have to go on big TOT... and where is it

[quote="ali_ms2004"]please put the questions !!![/quote]

http://www.math.toronto.edu/oz/turgor/archives.php

[quote="jensen"]i thought that the tournament of towns is a competition in russia but now i understand that it is in many countries!
wowwwwww.. :o[/quote]

hmm is it in US too? I never heard of Tornament of towns

Depends on which city you're in. I'm not sure how the contest works outside Canada though  :|

Here in Colombia we participate too. And there are other southamerican countrys that also do so.

We used to have it here in Sweden aswell, but I think that they cancelled it in 2002.

[quote="billzhao"][quote="nirvanatear"]in canada it is on April 3[/quote]

Not necessarily. It depends on which city you're in.

In Toronto, we took the contest on Feb 19, 2006 (O-level) and Feb 26, 2006 (A-level)[/quote]

I was just wondering why is that the Tournament of Towns officials make it that so that the competition is done on various countries at various different dates, some even weeks or months apart.  :huh:  Wouldn't it be easier for them if they made it that everyone writes the contest around the same time. I know that people in some part of the world might be sleeping while some people in other parts of the world is writing the contest, but that does't mean that they have to schedule the contests weeks apart. :?:

Which canadian towns participate in this thing? What is the point of it?

Israel had it on 17th of March 2006 in three major towns: Jerusalem Tel Aviv Be'er Sheva


AMC USA(J)MO USAMO AIME trigonometry calculus inequalities

I see people with goals of like 150 AMC 10 and 10+ on AIME, and then their goal on USAMO is simply to score positive.  Is it really that difficult?  Is it close to IMO in terms of difficulty?

yes, some USAMO problems are harder than IMO problems. Although USAMO problems are hard, they're the most fun :)

The USAMO is really difficult. The scoring is brutal; you get a score from 0-7 on each of six problems. In order to get a 1, you must have made significant progress on the solution (or something like that, I'm not sure what the exact wording is).

The majority of participants get less than a 7. The median score for 2009 was a 4.

I don't know if the USAMO and the IMO are equal in difficulty. Someone else can give a better answer than me.  :wink:

Wow, that's tough.  So there are people that qualify for USAMO that score 0, and there are also people who score 42?  That's amazing.

People [i][u][b]RARELY[/b][/u][/i] get a 42 on USAMO. Has it even been done before? Anyways, yes the USAMO is that tough. If you look it up on AoPS wiki, it will tell you how large the jump from AIME to USAMO really is.

USAMO and IMO are comparable in difficulty, but in my opinion IMO favors people with training a LOT while usamo on average doesn't as much.

Training is pretty helpful on both though.

Usamo compared to aime/amc doesn't really work, because amc/aime is a rush to solve a list of easy-medium questions while usamo you have somewhat more time (though 4.5 hours usually isn't enough) but a lot less questions. So, someone's who is really fast and ok at problem solving but not really good at solving... somewhat hard problems might get 150 amc 12, like 13/14 aime, and then get < 5 points on usamo. Someone's who's really slow and amazing at problem solving might not even get past amc 12 but get like 21 points on usamo when they take it unofficially.

@poster above me: Brian Lawrence got a 42 one year. Both Brian Lawrence and Alex Zhai have gotten 41s.

No one is going to be slow to the point that they don't make AIME and get 21 when taking USAMO unofficially...

A complete list of the 9 distinct USAMO perfect scorers can be found [url=http://www.artofproblemsolving.com/Wiki/index.php/USAMO_historical_results#USAMO_Perfect_Scorers]here[/url].

Note that scores do not correlate perfectly between the USAMO and IMO. For example, Reid Barton and Gabriel Carroll earned perfect scores at the [url=http://imo-official.org/team_r.aspx?code=USA&year=2001&column=total&order=desc&gender=hide]2001 IMO[/url] yet did not earn perfect scores on the 2001 USAMO.

It should also be noted that a couple people every year usually (not always) earn perfect scores on the IMO, whereas the USAMO does not have such a consistent showing. (Then again, that would most likely be due to the rigorous training that happens between the TST (and its equivalents internationally) and the actual IMO).

[quote="darkdieuguerre"]It should also be noted that a couple people every year usually (not always) earn perfect scores on the IMO, whereas the USAMO does not have such a consistent showing. (Then again, that would most likely be due to the rigorous training that happens between the TST (and its equivalents internationally) and the actual IMO).[/quote]
I would say it has more to do with the caliber of the people taking it. The people in the US are a strong bunch, but they aren't as good as the best in the world.

[quote="not_trig"][quote="pythag011"]USAMO and IMO are comparable in difficulty, but in my opinion IMO favors people with training a LOT while usamo on average doesn't as much.
[/quote]

Yeah USAMO is pretty "special" in this way among national/international math Olympiads - it tries pretty hard to give 1/4s that don't require much knowledge, and 2/5s too even. Countries that favor training (tricky methods that can be learned) include China and Russia lolol[/quote]

I see in your signature that your goal on USAMO is 35.  Based on what I have seen from the thread, that's insanely difficult to achieve.  Am I right?

[quote="AdithyaGanesh"]I see people with goals of like 150 AMC 10 and 10+ on AIME, and then their goal on USAMO is simply to score positive.[/quote]
To get to the USAMO, you have to take the AMC 12, as of this year, unless you get 11+ on AIME.

The USAMO has to choose the best of the best in America, so it would have to be difficult enough to separate even the best. If it was too easy, it would be like MC or AMC 8 and it would be based more on accuracy (silly mistakes) than knowledge.

[quote="AdithyaGanesh"]I see in your signature that your goal on USAMO is 35.  Based on what I have seen from the thread, that's insanely difficult to achieve.  Am I right?[/quote]

 :yup:

[quote="AdithyaGanesh"]I see in your signature that your goal on USAMO is 35.  Based on what I have seen from the thread, that's insanely difficult to achieve.  Am I right?[/quote]

Yes, it is. But not_trig made blue MOP last year, so he probably could get that high of a score.  (I'm assuming he's aiming for black MOP this year.)

For anyone who is (or has) taken WOOT on AOPS, how do the practice olympiads that they give compare to the USAMO?  I can consistently get 7-9 on the intermediate questions.  What score would that roughly translate to on the USAMO?

For your first question, the answer is no, they only cover what you need for the easiest USAMO problems. You need to study other things for that. Also, afaik, calculus is never required in the USAMO and the IMO, but they can be useful.

[quote="pythag011"][quote="AdithyaGanesh"]Wow, not_trig must be a student of high calibre then; my kudos to him.

So do the Intermediate AoPS books cover all the concepts necessary for USAMO?  Also, can calculus ever be used in USAMO/IMO?  Is it ever required?

Thanks![/quote]

Calculus/Linear algebra/Combinatorial Nullstellensatz(which i guess sort of counts of olympiad, not really though imo) can be pretty helpful on usamo/imo. These techniques are very useful for solving some inequalities and certain #6s.

For the first question: Depends. Knowing basic stuff like being able to visualize dominoes and induct would have been enough to solve #3 usamo this year. (Though actually, I'm think induction isn't necessary, but the only solution i can recall right now to 3a uses induction.) This year, #2 probably could be solved without knowing anything beyond induction, #6 could be solved in a number of really elementary ways, #1 and #4 required some level of training though. (And #5 can be solved with pure angle chasing (no constructions.))

On IMO though, training.... is.... pretty.... useful.... (typically).[/quote]

Dude yeah listen to this guy. He knows what he's talking about (mostly, though maybe if he were slightly older ;) he'd be an EVEN MORE reliable source.)

also uhh combinatorial nullstellensatz. mr. pythag, you seem rather obsessed with that. It's useful only on a select number of IMO #6s and stuff. However, [i]no calculus or linear algebra[/i] is [b]necessary[/b] for Olympiads. It's "elementary math" - but it (obviously?) gets very tricky. (but it being useful for inequalities is pretty true.)

#4 was just AM-GM / Cauchy :( I suppose that counts as "training," but most people taking USAMO should know that? I think?

But yeah in conclusion USAMO still requires "not that much" training but lots of trickiness. IMO requires similar trickiness but more training.

Are you people (pythag011 and not_trig) suggesting that you don't need to know to much math to do well on the USAMO? You just need to be able to look at the problem correctly and handle the "trickiness"?

I don't think they're implying that. They're just talking about training. You can know lots of math but not have much training (I think).

ok hmm

we are treating "training" as knowledge that is pretty much only useful on Olympiads, but not anywhere else [though ok this is a sucky definition]

examples:

algebra:
dumbassing 3-var symmetric inequalities (and inequalities in general except maybe power mean / cauchy / jensen... like what, muirhead? minkowski? huh?)
solving functional equations (maybe; I suppose func eqs are actually legit topics)

NT:
VIETA JUMPING
lifting the exponent [maybe?]

geometry:
euclidean geometry in general :P (though yeah yeah it might be useful later in like projective geo or something)

combo:
erm... I suppose this stuff could be useful in combo later maybe (but ok some of it is still "Training")

another way to put it is "experience" (though this is slightly different). You have to know a lot of stuff, and then know when to apply it. which is hard.


The time shown here is 1 hour slower than the correct time, even though my time zone is correctly set(GMT). It doesn't seemed to know that daylight saving time is affective right now.

All local times are computed relative to GMT.  GMT doesn't change under daylight savings time.  So in order to show correct local times, you need to edit your profile to the correct time relative to GMT.

Example: US/Canada Eastern Time is GMT -5 during standard time, GMT -4 during daylight time.


The date of the second Thursday of a month is a square number.  The last Monday of the month is on the

A.26th 	 B.27th	C.  28th D.30th E.Cannot be determined

[hide=" click to reveal hidden content"]

The 2nd and 9th are Thursdays. The 13th, 20th and 27th are Mondays.

[/hide]

[hide]The 9th must be the second Thursday, which means that the 6th was a Monday. The Mondays of that month are on the 6th, 13th, 20th, and the 27th. The 27th is the last Monday because there is no 34th day in any month. The answer is [b]B. 27th[/b][/hide]


Just wondering: what exactly is Power of a Point?

It basically says that in a circle, if two chords $ AB$ and $ CD$ intersect at a point $ M$, then

$ AM \cdot MB \equal{} CM \cdot MD$.

Keep in mind that $ M$ can be outside the circle (we extend the chords until they intersect) and either or both of the chords can be replaced by tangents (in which case $ A \equal{} B$ or $ C \equal{} D$).  The numerical value of $ AM \cdot MB$ is called the [b]power[/b] of $ M$ with respect to the circle.  By the way, this would've been very easy to look up for yourself.

Oh, I see (I think). Thanks!
Oops. Posted in High School Math. Silly me.  :blush:

Also learn to use the Wiki: [url=http://www.artofproblemsolving.com/Wiki/index.php/Power_of_a_point]Power of a Point[/url].


algebra
polynomial
calculus
integration
number theory
relatively prime
number theory open

Do there exist monic polynomials $ P(x), Q(x) \in \mathbb{Z}$ such that

- $ P$ and $ Q$ are relatively prime, but

- For every integer $ n$ such that $ P(n), Q(n) \neq 0$, the prime factors of $ Q(n)$ include the prime factors of $ P(n)$?

We don't need monic here (and in both cases, constant $ P$ works fine).
There are integral polynomials $ a,b$ and an integer $ c \neq 0$ such that $ a(x)P(x) \plus{} b(x) Q(X) \equal{} c$ (for rational polynomials $ a,b$, we can get $ c \equal{} 1$; then multiply with a common denominator of the coefficients).
If now $ p$ is a prime dividing $ P(n)$, then $ p|Q(n)$, thus $ p|c$. Thus $ P(n)$ can only archieve finitely many prime divisors, giving that $ P(x)$ is constant (using the well known fact that nonconstant polynomials have infinitely many different prime divisors).

What about the general case $ gcd(P, Q) \not\equal{} 1$? What are the possible polynomials $ P$ and $ Q$?

If $ Q \equal{} q_1 \cdot ... \cdot q_r$ is it's factorisation into irreducible factors, then $ P \equal{} c \cdot q_1^{s_1} \cdot ... \cdot q_r^{s_r}$ for some $ s_i \in \mathbb N_0$ and some constant $ c \in \mathbb Z$ (and as before, $ c$ must be such that it divides all $ Q(n)$).
To see this, reduce to the case $ P$ irreducible, thus either $ \gcd(P,Q) \equal{} 1$ (which we settled already) or $ P|Q$ (in which case the problem is trivial).

Actually just the prime divisors of $ c$ need to divide $ Q(n)$ for all $ n$.

By the way, thanks!


algebra
polynomial
trigonometry
function
integration
real analysis
real analysis unsolved

Given that $\pi^{2}\left(x^{2}-x+1/6\right)=\sum_{n\in\mathbb{N}}\cos\left(2\pi nx\right)/n^{2}$ uniformly for $x\in\left[0,1\right]$, deduce that

\[\sum_{n\in\mathbb{N}}\frac{\sin\left(2\pi nx\right)}{n^{3}}\]
coincides with a polynomial for $x\in\left[0,1\right]$ and find the polynomial.

Since $\sin\left(2\pi nx\right)=\frac{1}{2i}\left(e^{2\pi inx}-e^{-2\pi inx}\right)$, and since $\sum_{n\in\mathbb{N}}n^{-3}\sin\left(2\pi nx\right)$ converges uniformly to a function $f\left(x\right)$ by the Weierstrass M-Test, I can write $f\left(x\right)$ as
\[f\left(x\right)=\sum_{n\in\mathbb{N}}\frac{\sin\left(2\pi nx\right)}{n^{3}}=\sum_{n\in\mathbb{Z}}\left(\frac{1}{2in^{3}}\right)e^{2\pi inx}. \]
Then
\[\widehat{f}\left(n\right)=\frac{1}{2in^{3}}=\int_{0}^{1}f\left(x\right)e^{-2\pi inx}\,dx. \]
Is this the correct process towards solving for $f\left(x\right)$?

I'm trying to use this to prove that

\[\sum_{n\geqslant 0}\frac{\left(-1\right)^{n}}{\left(2n+1\right)^{3}}=\frac{\pi^{3}}{32}.\]

Would be easier to integrate $\pi^{2}\left(x^{2}-x+1/6\right)=\sum_{n\in\mathbb{N}}\cos\left(2\pi nx\right)/n^{2}$ term by term, which you can do because the convergence is uniform.


A hiker carries a two-ounce package of concentrated fruit juice that is $ 10\%$ water. How many ounces of water does she have to add to make the mixture $ 50\%$ water?

The concentrated package is a 2 ounce package. 10% water means there is .2 ounces of water.

The amount which is water is $ \frac{0.2}{2}$

Since there is 1.8 oz juice, we want 50% water at $ \frac{1.8}{3.6}$

We need to add 1.8 - .2 = $ \boxed{1.6}$ ounces of water.


Let p be a prime such that 2 is a primitive root mod p , p^2 ,  and  p^ (p-2) .For which  natural k which satisfies 0 < k < p-1 do we have :
1^k + 2 ^k + + (p^k -1 )^k + ( p^k ) ^k = 2 ^ ( p-1 ) -1 ( mod p ^ k)

 :?  :?

Just a quick observation: if $a$ is a primitive root of $p^2$ then it's a primitive root of $p^n$ for all $n\ge 2$.

The summands on the left are just powers of $2$ to the exponent $k$, because we may eliminate those which are divisible with $p$, because when they're lifted to power $k$ they're divisible with $p^k$. So the sum on the left is congruent to $\displaystyle \sum_{i=1}^{\phi(p^k)}(2^i)^k=\sum_{i=1}^{\phi(p^k)}(2^k)^i=\frac {2^{k(p^k-p^{k-1}+1)}-1}{2^k-1}-1\ (\mod\ p^k)$.

We thus need $\frac {2^{k(p^k-p^{k-1}+1)}-1}{2^k-1}=2^{p-1}\ (\mod\ p^k)$.

I have pretty much no idea how to continue right now :).

hmm...that's pretty clear I think. first, we know that
$\phi(p^k)=p^k-p^(k-1)$. using fermat, we may forget about that term in the exponent and the left side is $\frac{2^k-1}{2^k-1}=1$. but 2^(p-1) is never one except in the case k=1 since 2 is primitive.

Peter

I can't believe I didn't see it, man :D.

I couldn't believe that, too...I thought my argument was false ;)


[quote="KMK00009"]3 circles of radii 1,2,3 respectively are tangent to each other externally. Another circle X is tangent to the three circles externally. What is the radius of circle X?[/quote]
This is an ambiguous question.

Circle X can be the even smaller circle that is externally tangent to all three
circles, *but* it lies in the enclosure of the three externally tangent circles.

*Or*, circle X can be the "great" circle that is externally tangent to all
three circles, and it lies on (is tangent to) the outer parts of the three
other circles.

EDIT:  "No, you just don't know what "externally tangent" means..."

I *did* know seconds before I saw the problem, but then I got
impulsive and lost what it meant.

[quote="Arrange your tan"]This is an ambiguous question.[/quote]  No, you just don't know what "externally tangent" means ;)  Two circles are [i]externally tangent[/i] if they are tangent and neither is inside the other.  (Two tangent circles may also be [i]internally tangent[/i], if one lies inside the other.)

[quote="Tiger100"]Use Descartes circle theorem http://mathworld.wolfram.com/DescartesCircleTheorem.html[/quote]
What's the proof of this theorem then?


Does mod only work for positive integers?
Can I use it on negative numbers?
How?

Thanks.

[quote="jli"]yes...it can be used with negative numbers.

for example:

1mod5==-4mod5

does that answer your question?[/u][/quote]

so... why -4 divide by 5 remainder 1? why not -1?

No, that isn't exactly how it works. Essentially, if you have a number $x$, then you can say $nx+1\equiv 1\bmod{x}$ for any integral $x$, including negatives. However, on top of this, you can always add or subtract any multiple of $x$ from $1$ and it'll still be equivalent to the same thing. So, in this case, $-4\equiv 1\bmod{5}$ because $-4=1-5$.

It can be used for all integers. If you have $a \equiv b \pmod {m}$, and $a$ is negative, then you can just add on $m$ to get a positive value. It won't change the remainder mod m. For example,

Find $x$ in the interval $(0,5)$ such that $-1 \equiv x \pmod {5}$

[hide="Solution"]
Then adding five to the LHS, we get $4 \equiv x \pmod {5}$. Thus $x=4$ in that interval.[/hide]


If $ x^4 \plus{} 4x^3 \plus{} 6px^2 \plus{} 4qx \plus{} r$ is exactly divisible by $ x^3 \plus{} 3x^2 \plus{} 9x \plus{} 3$, the value of $ (p \plus{} q)r$ is:

$ \textbf{(A)}\ \minus{} 18 \qquad \textbf{(B)}\ 12 \qquad \textbf{(C)}\ 15 \qquad \textbf{(D)}\ 27 \qquad \textbf{(E)}\ 45 \qquad$

What exactly is $ r$? Is it supposed to be the root obtained when you divide those two polynomials?

Sorry, the first polynomial should be $ x^4\plus{}4x^3\plus{}6px^2\plus{}4qx\plus{}r$.  Could a moderator please edit that post?

You should probably PM a mod in case they don't see your post.

[hide="Solution"]
Let the roots of the cubic be $ a,b,c$ such that they are roots of the quartic as well, and let $ d$ be the other root of the quartic.

By Vieta's, $ a\plus{}b\plus{}c\equal{}\minus{}3$ and $ a\plus{}b\plus{}c\plus{}d\equal{}\minus{}4\implies d\equal{}\minus{}1$.

Also, $ ab\plus{}bc\plus{}ca\equal{}9$, $ abc\equal{}\minus{}3$, $ 6p\equal{}ab\plus{}bc\plus{}ca\plus{}d(a\plus{}b\plus{}c)\equal{}9\plus{}3\equal{}12$

$ \implies p\equal{}2$, $ \minus{}4q\equal{}abc\plus{}d(ab\plus{}bc\plus{}ca)\equal{}\minus{}3\minus{}9\equal{}\minus{}12\implies q\equal{}3$, and $ r\equal{}abcd\equal{}3$, so $ (p\plus{}q)r\equal{}(2\plus{}3)3\equal{}\boxed{\textbf{(C)}\ 15}$.
[/hide]

[hide="alternate solution"]
Synthetic division immediately yields
$ 6p\minus{}9 \equal{} 3$
$ 4q\minus{}3 \equal{} 9$
$ r\equal{}3$

$ \Rightarrow (p\plus{}q)r \equal{} (2\plus{}3)3 \equal{} 15 \longrightarrow \boxed{C}$

[/hide]


vector
Gauss
linear algebra
linear algebra unsolved

Let U_1 and U_2 be 2 subspaces of a Vector Space V. If we have found individual bases for both U_1 and U_2 then how do we form a basis for the direct sum of U_1 and U_2?
I know if U_1 and U_2 are disjoint then the basis for the direct sum is the union of their individual bases, but how do you go about it if 2 subspaces are not independent? I can find the dimension of the basis, but am unsure how to obtain the basis vectors themselves. Does the basis of the intersection come in there somewhere?

Much help would be appreciated.
Thank you
[/hide]

p.s. the [/hide] is not supposed to be part of the message - I don't know how it got there, being an inexperienced user of the AOPS forum.

[quote]if 2 subspaces are not independent?[/quote]

What do you mean by that? By definition, the sum of two subspaces V,W is direct iff $ V \cap W \equal{} \{0\}$.

Sorry, in my original question I meant to ask how to find a basis for just the sum of the 2 subspaces i.e. U_1 + U_2. I believe the sum is only a direct sum if the 2 subspaces are independent.

Let $ V,W$ be two given subspaces. Select a basis $ U_1$ in $ V$ and a basis $ U_2$ in $ W$. Start by writting $ V \plus{} W \equal{} \langle U_1 \cup U_2\rangle$. Now, if necessary, eliminate vectors from this last set in order to obtain a linearly independent set, and so a basis for $ V \plus{} W$. Of course that you can use matrices and Gauss elimination so as to achieve that.


limit
calculus
derivative
function
AoPS Books
calculus computations

This is the problem from my student.

Find the limit $ \lim_{x\rightarrow 0} \frac{e^x\minus{}x\minus{}1}{x^2}$.

Please solve the problem without using l'Hopital's rule as he desires.

Thank you for your reply. My first solution was same as yours.
I wonder, aren't there solution without using University Mathematics?

Yes, I teach mathematics students those who will have Japanese University entrance exam.
That's why I usually make a comment with some restriction from the point of view of Japanese highschool students.

so ga, nihon jin desu ka?

anyway, it is odd that japanese knows english like you do

or are you foreign teacher in japan?

anyway can i have some mock exam or past paper of japanese university entrance exam?

Yes, I am a Japanese living in Tokyo.
Regrettably I can't help you, but you can see the problem in part. [url]http://www.mathlinks.ro/resources.php?c=87[/url]
By the way, what's mock exam?

[quote="kelvin911"]anyway can i have some mock exam or past paper of japanese university entrance exam?[/quote]  "Mock" means "imitation," so for example "mock turtle soup" is a soup that is meant to be like turtle soup but doesn't actually have turtle in it.  (There's also a verb "to mock," which means something quite different (though one can see how they could have come from the same root).)  Anyhow, kelvin, look through kunny's old posts -- there are hundreds of questions from past Japanese university entrance exams.

I wonder whether can we solve this problem by showing that it is a value of the derivative of the function $ g(x) \equal{} \frac {e^x \minus{} 1}{x}$ (with $ g(0) \equal{} 1$, for continuity) at $ x \equal{} 0$?  (This is more elementary than using L'Hosital's or power series, perhaps, but this problem "really" is about power series, so avoiding them is a little awkward.)

(Edited for typos.)

First, notice that $ \lim_{x \to 0} \frac {e^x - 1}{x} = \lim_{x \to 0} \frac {e^x - e^0}{x - 0} = \left( \frac {d}{dx} e^x \right) _{x = 0} = e^0 = 1$

For the desired limit:

\begin{eqnarray*} L & = & \color{blue}{\lim_{x \to 0} \frac {e^{x} - x - 1}{x^{2}}} \\
& = & \lim_{x \to 0} \frac {\left( \frac {e^x - 1}{x} \right) - 1}{x} \\
& = & \lim_{x \to 0} \frac {g(x) - g(0)}{x} \\
& = & g'(0) \\
& = & \color{blue}{\lim_{x \to 0} \frac {(x - 1) e^x + 1}{x^2}} \end{eqnarray*}

Adding the two blue expressions:

$ 2L = \lim_{x \to 0} \frac {x e^x - x}{x^2} = \lim_{x \to 0} \frac {e^x - 1}{x} = 1$

$ \implies \boxed{L = \frac {1}{2}}$

http://www.artofproblemsolving.com/Forum/resources.php?c=87&cid=79&year=2006 these are for highschool students to get into university in japan???  seriously?

Yes, Tokyo & Kyoto university are difficult to pass the entrance exam.

[quote="TZF"]
For the desired limit:

\begin{eqnarray*} L & = & \color{blue}{\lim_{x \to 0} \frac {e^{x} - x - 1}{x^{2}}} \\
& = & \lim_{x \to 0} \frac {\left( \frac {e^x - 1}{x} \right) - 1}{x} \\
& = & \lim_{x \to 0} \frac {g(x) - g(0)}{x} \\
& = & g'(0) \\
& = & \color{blue}{\lim_{x \to 0} \frac {(x - 1) e^x + 1}{x^2}} \end{eqnarray*}

[/quote]

how did you get the second blue equation?  :(

you have to know that stuffs even if you are going into psychology???  or is it only for math major students???

[quote="kunny"]Find the limit $ \lim_{x\rightarrow 0} \frac {e^x \minus{} x \minus{} 1}{x^2}$ [u]without using l'Hopital's rule[/u].[/quote]
Denote $ f(x)\equal{}\frac {e^x \minus{} x \minus{} 1}{x^2}$ and $ L\equal{}\lim_{x\to 0}f(x)$ . Prove easily that $ \boxed {4\cdot f(2x)\equal{}2\cdot f(x)\plus{}\left(\frac {e^x\minus{}1}{x}\right)^2}\ \ (*)$ .

In conclusion, since $ \lim_{x\rightarrow 0} \frac {e^x \minus{} 1}{x}\equal{}1$ , for $ x\to 0$ in the identity $ (*)$ obtain that $ 4L\equal{}2L\plus{}1$ , i.e. $ L\equal{}\frac 12$ .

[quote="earldbest"]how did you get the second blue equation?  :([/quote]

It is the derivative of $ g(x) \equal{} \frac{e^x\minus{}1}{x}$, where $ g(0)$ and all its derivatives are defined by limit. See the previous three lines.

For the approach I'd prefer that my own Calculus II students take: I really want people to be very, very familiar with the power series of the usual functions. For my own sake, my solution would be the same as kelvin911's in post #2 - except that I might not bother to write anything down. The power series perspective is that this is a very easy limit.

(It wouldn't surprise me if perhaps kelvin911 saw the problem and worked it in his head, knowing immediately that the answer was $ \frac12.$ But then, he had to write something out to explain himself when he made his post.)

Hey Kunny or anyone else who might know:

Do you think the AOPS Books (introductory series, intermediate series, problem solving series) would help a student pass the Tokyo or Kyoto math entrance exams?


I can solve this problem.
for any positive real $x,y,z$ where $xyz = 1$ prove that
$x^2 + y^2 + z^2 \geq \frac{1}{x}+\frac{1}{y}+\frac{1}{z}$

But if the problem become like this.
for any positive real $x,y,z$ where $xyz = 1$ prove that
$x^{x-1} + y^{y-1} + z^{z-1} \geq \frac{1}{x}+\frac{1}{y}+\frac{1}{z}$

I can't do it. Can someone help me. ! ?  :blush:

Um.. I'm not that smart to help on the proof but see that:

$\frac {1}{x} + \frac {1}{y} + \frac {1}{z} = x^{-1 }+ y^{-1} + z^{-1}$

This should help, I think...

Taking $\ln$'s, we want to prove:

$\sum (x-1)\ln x \geq \sum-\ln x$

or

$\sum x\ln x\geq 0$ with $\sum \ln x=0$ (the condition $xyz=1$)

But since $(x,y,z)$ and $(\ln x,\ln y,\ln z)$ are similarly sorted, we have that:

$\sum x\ln x\geq \frac {1}{3}(x+y+z)(\ln x+\ln y+\ln z)=0$ by Chebyshev, which is the desired result.

As for the first inequality, multiplying the $RHS$ by $xyz$ yields

$\sum x^2\geq \sum xy$, which follows immediately from AM-GM, factorization, Cauchy, Rearrangement, Jensen's, and just about every other inequality I know.

[quote="blahblahblah"]$\sum (x-1)\ln x \geq \sum-\ln x$
[/quote]

Try again.

[quote="blahblahblah"]What, doesn't $\ln {(x+y+z)}=\ln x +\ln y+\ln z$?  :?[/quote]

No. $\ln(xyz) = \ln x + \ln y + \ln z$.

I know that.  Do you have a solution to the original inequality?

It's seem too hard for pre-olympiad level.  :(

[quote="svrsk"]for any positive real $x,y,z$ where $xyz = 1$ prove that
$x^{x-1} + y^{y-1} + z^{z-1} \geq \frac{1}{x}+\frac{1}{y}+\frac{1}{z}$[/quote]

This problem is a bit too tricky for the pre-olympiad level, but not really hard either. Here is my solution:

Since the numbers x, y, z are positive, their natural logarithms ln x, ln y, ln z exist.

For any real number u, the inequality $e^u\geq u+1$ holds, with equality if and only if u = 0. Applying this inequality to the number $u=x\ln x$, we get $e^{x\ln x}\geq x\ln x+1$. Since $e^{x\ln x}=\left(e^{\ln x}\right)^x=x^x$, this becomes $x^x\geq x\ln x+1$. Hence, $x^{x-1}=\frac{x^x}{x}\geq\frac{x\ln x+1}{x}=\ln x+\frac{1}{x}$. Similarly, $y^{y-1}\geq\ln y+\frac{1}{y}$ and $z^{z-1}\geq\ln z+\frac{1}{z}$. Hence,

$x^{x-1}+y^{y-1}+z^{z-1}\geq\left(\ln x+\frac{1}{x}\right)+\left(\ln y+\frac{1}{y}\right)+\left(\ln z+\frac{1}{z}\right)$
$=\left(\ln x+\ln y+\ln z\right)+\left(\frac{1}{x}+\frac{1}{y}+\frac{1}{z}\right)$.

But $\ln x+\ln y+\ln z=\ln\left(xyz\right)=\ln 1=0$, and thus this becomes $x^{x-1} + y^{y-1} + z^{z-1} \geq \frac{1}{x}+\frac{1}{y}+\frac{1}{z}$. And the problem is solved.

  Darij

[quote="honglei"]Why "e^u≥u+1"[/quote]

Because it's true at 0 and then by comparing derivatives.  (Equivalently, the line $y = x + 1$ is a tangent of the curve $y = e^x$ at $x = 0$, and the curve has everywhere positive second derivative.)


When I enter:

\subjclass{11M06,11-02 (Primary) 30-02,44A10 (Secondary)}

in my asmart document, it prints out

1991 Mathematics Subject Classication. 11M06,11-02 (Primary) 30-02,44A10 (Secondary).

but these are 2001 classifications and I'd like it to print 2001 and not 1991.  And if I just use \footnotetext it gives a 0 footnote but I don't want a footnote number for this.

Also when I try to override \footnote with:

\def\unnumfootnote{\xdef\@thefnmark{}\@footnotetext}

and then use \unnumfootnote, it still prints a 0 for the footnote.

Could someone explain to me how to write in the footnotes without a footnote number:

2001 Mathematics Subject Classication. 11M06,11-02 (Primary) 30-02,44A10 (Secondary).

Thanks a lot guys :)

I think you mean 2000 rather than 2001 as amsart.cls only defines 1991 and 2000. To get 2000 you use:
[code]\subjclass[2000]{11M06,11-02 (Primary) 30-02,44A10 (Secondary)}[/code]If you insist on 2001 then you must define it yourself:
[code]\newcommand{\subjclassname@later}{\textup{2001} Mathematics Subject Classification}
\makeatother
\subjclass[later]{11M06,11-02 (Primary) 30-02,44A10 (Secondary)}
\maketitle[/code]You don't need to use the word [i]later[/i], any word will do but not numbers.

If you want a footnote elsewhere without a number use the [url=http://tug.ctan.org/cgi-bin/ctanPackageInformation.py?id=nccfoots]nccfoots package.[/url]
[code]\usepackage{nccfoots}
...
\Footnote{}{This is a footnote without a number}[/code]

. . . I'm sure you're right . . . thank you again. :)


You don't need that. You just need to notice that you just have to find a number divisible by $ 10, 9, 8, \dots 1$ and subtract 1.

I'll reword Yongyi's post so I can feel better about my own intelligence.  :maybe: I hope I don't get it wrong.

The number will be congruent to -1 mod x, where x is each of 2, 3, 4, 5, 6, 7, 8, 9, and 10. Therefore find the LCM of that list of numbers and subtract one. $ [2, 3, 4, 5, 6, 7, 8, 9, 10] \minus{} 1 \equal{} 2519$.

[quote="pascal_1623"]What is the smallest whole number such that, when divided by each of 10, 9, 8, 7, 6... 2 gives a remainder of 9, 8, 7, 6, 5, 4, 3, 2, 1 respectively?

I remember someone telling me there was something called the chinese remainder theorem that would help with this. Could anyone explain or give me a link?[/quote]

basically similar to what Yongyi said, the LCM of 10,9,8....2 is 2520

so one less than that is 2519, which is the answer.


geometry
conics
hyperbola
geometry proposed

The incircle $ (I)$ of $\triangle ABC$ is tangent to $ BC,BA$ at $ X_a,X_c.$ The $ A$-excircle $ (I_a)$ is tangent to $ BC$ at $ Y_a.$ Line $ X_aX_c$ meets $ I_aY_a$ at $ E$  and draw the circle with diameter $ EY_a.$ Tangents from $ B,C$ to the latter circle (different from BC) meet at $ D.$ Let $ F \equiv X_aX_c \cap AI$ and $ J \equiv (I) \cap AY_a,$ $ J$ is the closer point to $ BC.$ Show that $ AD,FJ$ and $ BC$ concur.

Let $ (K)$ be circle with diameter $ Y_aE,$ the incircle of $ \triangle DBC,$ and let $ (K_d)$ be its D-excircle, tangent to $ BC$ at $ X_a.$ As $ X_aB \minus{} X_aC \equal{} AB \minus{} AC \equal{} DC \minus{} DB \equal{} Y_aC \minus{} Y_aB \equal{} Y_aX_a,$ $ D, A$ are on hyperbola $ \mathcal H$ with foci $ B, C$ and vertices $ Y_a, X_a.$ Angle bisectors $ AII_a, DKK_d$ are hyperbola tangents at $ A, D$ and perpendiculars $ IX_aK_d, KY_aI_a$ to $ BC$ are hyperbola tangents at $ X_a, Y_a.$ Quadrilateral $ II_aKK_d$ (convex or reflex) is tangential to $ \mathcal H$ and $ AY_aDX_a$ is its contact quadrilateral; they have the same diagonal intersection $ S \equiv IK \cap I_aK_d \equiv AD \cap Y_aX_a \equiv AD \cap BC.$ This intersection is the common similarity center of the incircles $ (I), (K)$ and the excircles $ (I_a), (K_d),$ external when $ AB > AC$ and internal when $ AB < AC.$

Let $ M_a$ be the common midpoint of $ BC, Y_aX_a.$ Angle $ \angle AJX_a$ is right on account of $ A$ being the external similarity center of the circles $ (I), (I_a)$ $ \Longrightarrow$ angle $ \angle X_aJY_a$ is right $ \Longrightarrow$ $ M_aJ \equal{} M_aX_a$ $ \Longrightarrow$ $ M_aJ$ is tangent of $ (I)$ at $ J.$ On the other hand, $ M_aF \parallel AB$ is C-midline of $ \triangle ABC$ $ \Longrightarrow$ isosceles $ \triangle FM_aX_a \sim \triangle X_cBX_a$ are centrally similar with center $ X_a$ $ \Longrightarrow$ $ M_aF \equal{} M_aX_a \equal{} M_aY_a$ $ \Longrightarrow$ angle $ \angle X_aFY_a$ is right $ \Longrightarrow$ angle $ \angle Y_aFE$ is right and $ F \in (K)$ $ \Longrightarrow$ $ M_aF$ is tangent of $ (K)$ at $ F.$ From the isosceles $ \triangle M_aFJ,$ the line $ FJ$ forms angles of equal size with the incircles $ (I), (K),$ with the same signs when $ AB > AC$ and with the opposite signs when $ AB < AC$ $ \Longrightarrow$ $ FJ$ goes through their similarity center $ S.$


modular arithmetic
number theory unsolved
number theory

Let n = 4k+1 be a positive integer. Prove that there are positive integers x,y,u,v such that x^n + y^n can be written in the form u^2 + n*v^2 but x+y can't.

Anyone has any ideas or some nice way to approach it?

I don't really know in what set we must take $u$ and $v$, but what happens if they are positive integers?
Can we find such an example in that case?

[quote="maxal"]First of all, [i]"there are positive integers x,y,u,v such that x^n + y^n can be written in the form u^2 + n*v^2"[/i] does not make sense since as soon as u,v are fixed "u^2 + n*v^2" is not a form but a number. So I assume the statement is [i]"there are positive integers x,y such that ..."[/i].

Let $p$ be a prime such that $-n$ is not a square modulo $p$.
Let $x=(p-1)^n + 1$ and $y=(p-1)((p-1)^n + 1)$.
Then $x+y = p((p-1)^n + 1)$ cannot be represented as $u^2 + n*v^2$ (because $u^2 + n*v^2 \equiv 0\pmod p$ has no solutions)
while $x^n + y^n =  ((p-1)^n + 1)^{n+1} = \left(((p-1)^n + 1)^{2k+1}\right)^2 + n\cdot 0^2$.[/quote]

when $-n $ is not a square modulo $p$ we know that $p \mid a^2+nb^2 \Rightarrow p\mid a , p\mid b$
but $p^2 \mid x+y$ so how you use this lemma to prove that $x+y \notin A$

A particular case :
http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2500599&#p2500599

[quote="maxal"][quote="goldeneagle"]when $-n $ is not a square modulo $p$ we know that $p \mid a^2+nb^2 \Rightarrow p\mid a , p\mid b$
but $p^2 \mid x+y$ so how you use this lemma to prove that $x+y \notin A$[/quote]
Thanks for catching this. Actually my idea of playing on divisibility of $x+y$ and $x^n+y^n$ by $p$ does not work since $\nu_p(x^n+y^n)=\nu_p(x+y)$ by LTE theorem: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=721&t=393335

I now doubt that the problem has a simple solution. Moreover, an additional constraint $v\ne 0$ may be needed (as in the particular case).[/quote]

if we have $ v \in \mathbb{Z} $ (so $v=0$ is possible ), you can see a solution [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=518101&sid=c9c2a1a1e05829e6087d2c87da16b5f8#p518101]here[/url]...

But i think  solving this problme in general (for every $n$ such that $n \equiv 1 (mod 4)$with condition $v \neq 0$ is hard  :D
(Actually i wanted to use your idea at first but as you mentioned LTE lemma showed me it is not useful :wink: )

[quote="goldeneagle"]if we have $ v \in \mathbb{Z} $ (so $v=0$ is possible ), you can see a solution [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=518101&sid=c9c2a1a1e05829e6087d2c87da16b5f8#p518101]here[/url]... [/quote]
Basically, it is similar to my idea but relies on the special case of $p=2$ of LTE.


The value of a consonant is three more than the value of a vowel. Given that the sum of the values of the eleven letters in $ mathematics$ is 10, what is the sum of the values in the letters in $ math$?

Consonants: m,t,h,m,t,c,s
Vowels: a,e,a,i
Value: 25*vowel=10
vowel=0.4
consonant=1.2

math=(m+t+h)+a=3*consonant+vowel=1.6

Let the value of a vowel be $v,$ and the value of a consonant be $v+3.$

Therefore, since the value of $mathematics$ is 10, we have:

$7(v+3)+4v=10 \\ 11v+21 = 10 \\ 11v=-11 \\ v=-1 \\ v+3=2.$

$math$ has one vowel and three consonants. \[\therefore -1+3(2)=\boxed{5}.\]


There are three digits $ A$, $ B$, and $ C$ such that the product of two-digit numbers $ \underline{AB}$ and $ \underline{CA}$ is 1995. Find $ A\plus{}B\plus{}C$.

[quote="Bugi"]Shouldn't it be overline instead of underline?[/quote]
I don't understand.  Why should there be an overline?  :huh:

The basic meaning of this problem is that $AB$ and $CA$ are two separate two-digit integers which have a product of $1995$.  They underlined it so that the reader wouldn't mistake it for $A \cdot B$ and $C \cdot A$.


这是一个五一之前某日大家无聊在教室里玩的纸牌游戏。

我觉得这是一个没有明显必胜策略的多人博弈游戏，我们准备做一个活动。根据美国研究中心老师的说法，我们要做制定规则的人，我制定了这样的规则：记一局游戏是G(A,B,C,D,E)，其中A,B,C,D,E代表参与者。

游戏人数：5人。

游戏道具：1，2，3，4，5各四张。

一局游戏的流程：

   1. 五个参与者围座成一圈。
   2. 随机生成一个数n（范围是1000到10000之间的自然数），数n对参与者保密。
   3. 随机分配纸牌，每人四张。
   4. 大家同时抽出一张牌，然后给下一个人，并拿起上一个给自己的牌。
   5. 重复上一个步骤直到满足中止条件时执行下一个步骤。
   6. 在没有满足过胜利条件的参与者（或多个参与者）中，手上牌的数字种类最多的那个参与者（或多个参与者）得到一分。

终止条件：如果有至少四个人满足胜利条件或者重复第3个步骤的次数到达n。

整个游戏的流程：分别进行1000次G(A,B,C,D,E)，G(A,B,C,E,D)，……，G(A,E,D,C,B)，共24*1000次一局游戏。

游戏目标：使得自己的积分尽可能的少。

希望初期参与的同学请提供比较简单的策略，例如：Roy的随机策略：每次从手中选一张抽取一张给下一个人。

附加规则：如果某参与者在满足胜利条件之后，他的策略将被替换为Roy的随机策略。

欢迎感兴趣的同学积极参与，请在评论中留下你们的策略（是具体的，能用计算机实现的策略，注意，你是看不到别人手上的牌的），每人限参与三次，每集齐5个策略，就进行一次比赛（使用计算机模拟），比赛结果将于比赛后公布。

希望大家提出宝贵意见，谢谢，并希望大家报着娱乐的态度来参加比赛，因为我更期待的是结果的幽默性。

请将您的策略留在下面地址的评论中，谢谢。
http://libragold.spaces.live.com/blog/cns!2B791986893992CA!1019.entry?_c=BlogPart


AMC
AIME
probability
geometry
geometric transformation
dilation
Harvard

Hey guy, I have compiled a list of problems from various sources that serve as a practice AIME. Please don't go searching for the problems elsewhere, cause that takes the purpose out of the test. Without further adue, here we go:

1. Find the number of triangulations of a general convex 7-gon into 5 triangles by 4 diagonals that do not intersect in their interiors.

2. 12 points are placed around the circumference of a circle. How many ways are there to draw 6 non-intersecting chords joining these points in pairs?

3. Joe, Charles, and Bob each select a 2-digit number at random. What is the probability that all their numbers' tens' digits are different from each others' tens' digits and all of their numbers' ones digits are different from each others' ones' digits? Express the answer in the form m/n, where m and n are relatively prime positive integers. Find m+n.

4. Square ABCD has side length 1. A dilation is performed about point A, creating square AB'C'D'. If BC' = 29, compute the area of triangle BDC'.

5. What is the remainder when 100! is divided by 101?

6. A triangle has side lengths 888, 925, and x>0. Find the value of x that minimizes the area of the circle circumscribed about the triangle.

7. Note that 2002 = 22 * 91, and so 2002 is a multiple of the number obtained by removing its middle 2 digits. Generalizing this, how many 4-digit palindromes, xyyx, are divisible by the 2 digit palindrom, xx?

8. A bug is sitting on one corner of a 3' x 4' x 5' block of wood. What is the minimum distance it needs to travel along the block's surface to reach the opposite corner? Express the answer in the form m^(1/2). Where m is a positive integer. Find m.

9. Find the number of ordered quadruples (a, b, c, d) of positive odd integers that satisfy a+b+c+d =98. Let the answer be M. Find the sum of the digits of M.

10. Find the number of subsets of {1,..., 2000}, the sum of whose elements is divisible by 5. The answer can be expressed as (0.2)(2^x+2^y), where x and y are positive integers. Find y.

11. An 8 foot by 8 foot area has been tiled by one foot square tiles. Two of the tiles were defective. The probability that the two defective tiles share an edge can be expressed as m/n, (m, n) = 1. Find m+n.

12. How many possible values can there be for 3 coins selected from among pennies, nickels, dimes, and quarters?

13. The triangle ABC has AB and AC unequal. The angle bisector of A meets the perpendicular bisector of BC at X. The line joining the feet of the perpendiculars from X to AB and AC meets BC at D. Find BD/DC.

14. If J=2002^2001, find the last three digits of 2003^J.

15. The equations x^2 + ax + 1 = 0 and x^2 + bx + c = 0 have a common real root, and the equations x^2 + x + a = 0 and x^2 + cx + b = 0 have a common real root. Let a + b + c = m. Find the number of distinct squares in a m by m square grid.

THE END.
Just post your answers, I will post the correct answers in a few hours. Enjoy and have fun!

[i]Moderator's note: Capitalized the second 'm' in #9.  -mathfanatic[/i]

I guess you should change "hours" to "days" as there are probably people who haven't seen this yet who would like to and don't want to be tempted to cheat.

I'm quite surprised that no one has posted answers yet. Anyways, I will reveal answers later on when a substantial amount of users submit a least some answers. Also, for all people taking this challenge, do u think this is harder or easier than typical AIME? Also, I forgot to say that all answers are from 000-999, inclusive of course (but you all should know this) :cool:

Teddy, your score is: [hide]7[/hide]. The reason I will not reveal which ones you missed and got is because I wish for a bit more people to submit answers without the temptation to cheat. Good job!

Need help with 11.

[hide] I don't want others to cheat, but is the answer 10?  I didn't give my solution so people who give up quickly on problems wouldn't look at my solution.  Teddy got a different answer though[/hide]

Perhaps I should have posted this earlier, but in number 9, the second "m" should be captalized to match the first "M". I hope every figured this out before I added this, or otherwise the question would not make sense. Thanks

Here's a few solutions:

[hide]

1. Some diagonals that connect vertices separated by one vertex (we'll call these outside diagonals) and some connect vertices separated by two vertices (we'll call these inside diagonals).  I will divide all configurations into three categories.  In category 1, there are three outside diagonals.  If there are three outside diagonals - in heptagon ABCDEFG, between A and C, C and E, and E and G - then there are two ways to draw the last diagonal - either CG or AE.  (We can't involve points B, D, or F, since that would require an intersection with AC, CE, or EG, respectively.)  Since any of the sides may be the 'odd man out' (you'll see which one I mean when you draw it), there are 2 ways to connect the last diagonal times 7 configurations, for a total of 14.

Category 2 has 2 outside diagonals that share a common vertex.  Using our ABCDEFG example, these are AC and CE.  There is only one way to draw the other two diagonals - CF and CG - since any other configuration would be a category 1 configuration.  Since any vertex can be the one common to the two outside diagonals, we have 1*7 = 7 configurations.

Category 3 has 2 outside diagonals that do not share a common vertex.  There are 3 ways to place the other two diagonals without becoming category 1 or 2.  (If AC and DF are the outside vertices, then we could have CG and CF, CG and GD, or AD and GD).  Any of the 7 sides could be the one whose endpoints are both vertices of thet outside diagonals (e.g. CD), so there are 7 * 3 = 21 category 3 configurations.

In all, there are 14 + 7 + 21 = 042 configurations.

2. Pick two adjacent points and connect them, then pick the two points nearest to them and connect them.  Repeat.  You get 6 'parallel' (they would be parallel if the points were spaced evenly, but that isn't important - it's just for the mental picture) chords.  You could do this starting with any pair of adjacent points, of which there are 12, but this will overcount by a factor of 2, so there are really only 6.

3. The first guy can choose any of the 9 tens digits and 10 ones digits; the second guy can choose from 8 tens digits and 9 ones; and the third guy can choose from 7 tens digits and 8 ones.  So there are 9*10*8*9*7*8 good ways, out of a total of 90^3 combinations of 2-digit numbers.  10*9*9*8*8*7/(10^3*9^3) = 2*8*7/(5*5*9) = 112/225 --> m+n = 337.

4. Let B'C' = x, so that BB' = x-1.  Then we have a right triangle with side lengths of x-1, x, and 29.  Using the pythagorean theorem (or recognizing the 20-21-29 pythag triple), we have x = 21.

We now calculate the area of BDC' by subtracting [ABD], [BB'C'], and [DD'C'] from [AB'C'D'].  ABD = 1/2, BB'C' = 210, and DD'C' = 210, so BDC' = 441 - 420 - 1/2 = 20.5 = 41/2.  Are you sure this is AIME-style?  If you want m+n given m/n, it's 43...

5. By noticing patterns, 100.  It seems that every prime n, it is the case that (n-1)! :equiv: -1 mod n.  But I don't know why exactly.  More thinking involved.

7. xyyx = 1001x + 110y; xx = 11x.  We want to find how many (x,y) it is the case such that xyyx/xx = n for some integer n.  Thus, (1001x + 110y)/(11x) = 91 + 10y/x = n.  So 10y/x must be an integer.

If x = 1, y = anything -> 10 numbers

If x = 2, y = anything -> 10

If x = 3, y = 3, 6, 9 -> 3

If x = 4, y = 0, 2, 4, 6, 8 -> 5

If x = 5, y = anything -> 10

If x = 6, y = 3, 6, 9 -> 3

If x = 7, y = 7 -> 1

If x = 8, y = 4, 8  -> 2

If x = 9, y = 9 -> 1

In all, there are 45 numbers.

[/hide]

I might as well post the some solutions now. Starting with question #1:

1. 1. Find the number of triangulations of a general convex 7-gon into 5 triangles by 4 diagonals that do not intersect in their interiors.

Source: Harvard MIT Guts round 2001.

Answer: [b]042[/b]-> Using the catalan numbers: C(n)= (2n C n)/ (n+1). By substituting 5, we have C(5) = (10 C 5)/(6) = 042.

2. 12 points are placed around the circumference of a circle. How many ways are there to draw 6 non-intersecting chords joining these points in pairs?

Source: Harvard MIT Guts round 2001.

Answer: [b]132[/b] -> Again, we use catalan numbers-> C(# of chords)=C(6)= (12 C 6)/(7)= 132.

3. Joe, Charles, and Bob each select a 2-digit number at random. What is the probability that all their numbers' tens' digits are different from each others' tens' digits and all of their numbers' ones digits are different from each others' ones' digits? Express the answer in the form m/n, where m and n are relatively prime positive integers. Find m+n.

Source: Harvard MIT Guts Round 2001.

Answer: [b]337[/b] -> (9/10)(8/10)(8/9)(7/9)=112/225, so 112+225 = 337.

4. Square ABCD has side length 1. A dilation is performed about point A, creating square AB'C'D'. If BC' = 29, compute the area of triangle BDC'.

Source: Harvard MIT Guts 2001

Answer: [b]420[/b]-> 29^2-2(.5)(29)(29/2)-0.5=420.

5. What is the remainder when 100! is divided by 101?

Source: Harvard MIT guts 2001

Answer: [b]100[/b] -> By applying Wilson's theorem, we arrive at 100 as our remainder.

More to come. Thanks to all who participated. :cool:

Please explain #5 further.  I don't see how BC'D can be nearly the same area as AB'C'D' (which has, unless I misread the question, a side length of 21.)

Shouldn't you just apply the pythagorean theorem to traingle EBC' with E being the midpoint of BD?

C'E is then the height and sqrt2 is the base. I think this gets you 82.

0.5*2*sqrt2*sqrt (29^2- (sqrt2/2)^2)

keta, will you be posting the answers to the rest of the problems?

[quote="pkothari13"]I believe 9 is the same thing as doing $\displaystyle{97\choose 3} $

And that yields 147440;

So 1+4+7+4+4+0 = 20.[/quote]

I think you're close.  The problem stated [b]odd positive[/b] integers, so that means we should replace each of a,b,c,d with 2(some variable)+1.

After the substitution, we get
2w+1+2x+1+2y+1+2z+1 = 98
w+x+y+z=47
There are C(46,3) = 15180 ways to choose w,x,y,z and therefore a,b,c,d.
1+5+1+8+0=[b]15[/b]

Please correct me if I made a mistake. Thanks!

OHHHHHH. I guess I didn't read the question close enough. Yup, I believe you're right Optimosis.

Nah, it's ${50\choose 3}$ sets of odd positive integers not ${47\choose 3}$.


Let $ a,b$ be positive real numbers such that $ a\plus{}b\equal{}2$. Prove that

$ a^\frac 3{a}\plus{}b^\frac 3{b}\ge 2$.

[quote="Vasc"]Let $ a,b$ be positive real numbers such that $ a \plus{} b \equal{} 2$. Prove that

$ a^\frac 3{a} \plus{} b^\frac 3{b}\ge 2$.[/quote]
It is a very hard inequality, Vasc. Do you have a nice proof for it? By the way, my ugly proof is the following:

[Edit: I found some mistakes in my typing, so I have just uploaded the new file]

[quote="Vasc"]My proof is almost the same. It is not very nice. :oops:[/quote]
We got the same idea.  :lol:

This type's inequality deserves a whole book ,  can someone determin the best $ k$ such that :
$ a^{\frac{k}{a}} \plus{} b^{\frac{k}{b}} \geq 2$ wth the same condition :?:

[quote="can_hang2007"]I think the following inequality is harder:
$ a^{3b} \plus{} b^{3a} \le 2.$
My proof is so terrible.[/quote]

I posted this inequality on this forum in 2008, but it has remained unproved. It is the inequality (4.6) in my article
ON SOME INEQUALITIES WITH POWER-EXPONENTIAL FUNCTION. See
http://jipam.vu.edu.au/article.php?sid=1077
Ladislav Matejicka from Slovakia found a long proof for this inequality in an article for JIPAM, which will appear soon (in a week).

[quote="can_hang2007"]Yeah, I also saw this problem when you posted it in the forum in 2008. Now, I just repost it to see if someone gives us a nice solution. By the way, your article is really great![/quote]
Thank you for your appreciation. :lol:
Now I have a complete solution for my inequality

$ a^{ea}\plus{}b^{eb}\ge a^{eb}\plus{}b^{ea}$,

but I will wait a year a proof of someone for the unproved case $ 0<b<\frac 1{e}<a<1$.

[quote="anas"]This type's inequality deserves a whole book ,  can someone determin the best $ k$ such that :
$ a^{\frac {k}{a}} \plus{} b^{\frac {k}{b}} \geq 2$ wth the same condition :?:[/quote]
The best (smallest) $ k$ is 3. We can show that
$ a^{\frac {k}{a}} \plus{} b^{\frac {k}{b}} <2$

for $ k\equal{}3(2\minus{}x)$ and $ 1<x<2$, if we choose $ a\equal{}x$ and $ b\equal{}2\minus{}x$,

[quote="Vasc"]Now I have a complete solution for my inequality

$ a^{ea} \plus{} b^{eb}\ge a^{eb} \plus{} b^{ea}$,

but I will wait a year a proof of someone for the unproved case $ 0 < b < \frac 1{e} < a < 1$.
[/quote]
It's a great news. This one must be one of the hardest inequalities I have ever seen. I have tried too much but I can only prove it for $ k\equal{}2.$  :blush: I will wait for your article (hope it will appear soon).

We can extend the inequality
$ a^{3b}\plus{}b^{3a}\le 2 \ \  for \ \ a\plus{}b\equal{}2$,
to the following open inequalities:

$ a^{4b}\plus{}b^{4a}\le 2 \ \  for \ \ a^2\plus{}b^2\equal{}2$,
$ a^{5b}\plus{}b^{5a}\le 2 \ \  for \ \ a^3\plus{}b^3\equal{}2$,
$ a^{6b}\plus{}b^{6a}\le 2 \ \  for \ \ a^4\plus{}b^4\equal{}2$,
.....
$ a^{(k\plus{}2)b}\plus{}b^{(k\plus{}2)a}\le 2 \ \  for \ \ a^k\plus{}b^k\equal{}2$  and for any natural $ k$.

On the other hand, we have
$ a^{5b^2}\plus{}b^{5a^2}\le 2 \ \  for \ \ a\plus{}b\equal{}2$.


probability
geometry
geometric transformation
reflection

You are the sheriff of a small country with only two options for punishment for those charged with crimes:
(1) Executing them.
(2) Letting them go free without charges.

[b]Scenario 1:[/b]
After a horrible period in which $100n$ people were killed, you arrest $n+1$ people, knowing that $n$ are guilty of killing $100$ people each, but one's innocent. Despiting investigating the matter as thoroughly as you can, you can not find out the innocent one. You have no other options: tomorrow you must deliver a verdict to the suspects. You have two options:
-Let them all go, and release mass murderers into society.
-Execute them all, but send an innocent man to his death.

For what values of $n$ will you execute everyone? For what values of $n$ will you let everyone go without charging them? Is it more ethical to send an innocent man to his death than to release mass murderers in the society?
[b]
Scenario 2:[/b]
After a horrible period in which $n$ people were killed, you arrest $n+1$ people, knowing that one is guilty of killing $100$ people, but $n$ are innocent. Despiting investigating the matter as thoroughly as you can, you can not find out the guilty one. You have no other options: tomorrow you must deliver a verdict to the suspects. You have two options:
-Let them all go, and release a mass murderer into society.
-Execute them all, but send many innocent men to their deaths.

For what values of $n$ will you execute everyone? For what values of $n$ will you let everyone go without charging them? Why is this scenario any different from the above?

I have a problem with artificial ethical scenarios.  They're not useful for much more as thought experiments - suggestions for further questioning and discussion - and the way this problem is set up is presumptuously utilitarian and ignores real-life subtleties that would be associated with a corresponding ethical decision in the real world.

Mathematicians, especially, seem to be guilty of the (rather oversimplistic) notion that ethics can be axiomized, and that it is context-independent.

These type of problems are interesting, but kind of limited in their scope.
In each scenario, i would let everybody go free, but i might keep an eye on them if they were a manageable number.

Or i might quit my job. :D

[quote="t0rajir0u"]Mathematicians, especially, seem to be guilty of the (rather oversimplistic) notion that ethics can be axiomized, and that it is context-independent.[/quote]
Why shouldn't ethics be axiomizable?  What is your basis for rejecting the notion of an ethical system with simple, clear, easy to apply rules?  Is it the fact that you find some questions to be ethical dilemmas (suggesting that ethics is "hard"), or is there some deeper reason for it?  (None of these is meant as a rhetorical question.)

These scenarios seem odd to me: why shouldn't I be able to execute some arbitrary fraction $p < n$ of the prisoners, thereby providing a more reasonable balance (albeit a probabilistic balance) between insuring the guilty are punished and the innocent are left alone?

Also, for me at least, the most important piece of information is missing: what can I expect of those I let go?  I am more than willing to have dozens of murderers, sex criminals and pickpockets wandering town if I can be reasonably sure that none of them will continue in their nefarious ways.

And I think Captain Sugar's tongue-in-cheek answer is not a bad one, either.

[quote="JBL"]Why shouldn't ethics be axiomizable?  What is your basis for rejecting the notion of an ethical system with simple, clear, easy to apply rules?  Is it the fact that you find some questions to be ethical dilemmas (suggesting that ethics is "hard"), or is there some deeper reason for it? [/quote]

Before any other issue can be addressed we need to agree on a definition of what it means to be ethical.

A system of ethics is, broadly, a system of principles governing human behavior, splitting it up into "good" (perhaps "better") behavior and "bad" (perhaps "worse") behavior.

How you answer the ethical question depends a [b]lot[/b] on how you define "good" behavior.  [b]In other words, ethics is not (easily) axiomizable because no (easy) system exists for determining what its axioms should be.[/b]

Borrowing some ideas from evolutionary psychology, this is mine:

[b]Definition:[/b]  "Good" behavior for a human is behavior that best contributes to the survival and advancement of his group.

You can see that this definition makes a lot of sense evolutionarily; behaviors that contribute most to survival are passed on to the next generation, and in this way systems of ethics are acted upon by selection.

Note that I did not specify the group.  That is because the specification of the group is left up to an individual, and is one of the [b]several[/b] reasons why some ethical questions can be "hard."  Consider possible "groups" one might define:

- The world and all living things
- The human race
- A single country
- A single ethnic / religious group
- A single community
- A single family
- An individual

Shifting the meaning of one's "group" (one's tribe, as it were) around is enough, in my opinion, to accomodate the entire scope of ethical systems.  And then we have to ask ourselves, [b]on what basis do we define our group?[/b]

And that's not even my main pet peeve with the mathematician's view on ethics.

[b]My main pet peeve with the mathematician's view on ethics:[/b]  Many of you seem to treat ethical systems as the "software" of a society.  That is, you are acting under the assumption that it is easy to just "replace" the ethical system of a society with a "better" one that you dream up yourself, and that if this "software" runs better then it is fundamentally superior to the previous "software."

[b]It is not easy to replace the ethical system of a society.  The success of an ethical system in a society has as much to do with the current culture of the society as any kind of alleged inherent quality in the ethical system.[/b]

This is the fine point that I feel, for example, supporters of communism missed utterly.

[quote="t0rajir0u"]
Before any other issue can be addressed we need to agree on a definition of what it means to be ethical.
[/quote]

Somehow I feel that we wouldn't reach any sort of agreement in a hurry...

I believe that each individual defines his/her own ethics, and I find it hard to assume that anyone could write down his/her axioms. Don't you think that over the last 2500 years someone would've thought of at least one principle everyone would agree upon?

On topic: I think that the problem is too simple to exist in a real world, but there are two solutions I would find acceptable:
1) execute all of them -- you could easily convince yourself that this way you'd minimize the losses, as the murders will continue if you release the killer.
2) shift the burden of decision (this solution can arguably be dubbed 'coward's choice') -- present the problem to the citizens and let the society decide. This is good because it would eliminate your responsibility (if you're scared of it), but bad because the mass of people is unpredictable and may not reach a globally good decision.

Of course, letting them all go would result in murders continuing and the entire arrest business you've gone through proving to have been useless. Releasing a portion of people just lowers the probability that you'll release the killer, but doesn't elliminate it, and may require more arrests etc. I find this too cumbersome. Overall, I'd opt to be on the safe side -- I'd choose the first solution.

Oh, and what does the number $n$ have to do with the second problem? You later say that 100 people were killed -- shouldn't this be $n$ people?

[quote="1234567890"]My interest is in trying to find the "value" of life versus the safety for the general population.[/quote]

Again, this is a question that is not context-independent.  For example, is the community a community where people have a tradition of buying firearms for self-defense?  In that case, letting criminals go wouldn't do as much harm.

This particular question is basically the question of "risk assessment."  Actuaries do something like this.  Not ethicists.

[quote="Djole"][quote="t0rajir0u"]
Before any other issue can be addressed we need to agree on a definition of what it means to be ethical.
[/quote]

Somehow I feel that we wouldn't reach any sort of agreement in a hurry...[/quote]

Certainly not!  And that is one of my points.

Okay, sorry, let me begin again: certainly, you and I (or any other two individuals) are unlikely to agree on the appropriate response in every ethical dilemma.  In fact, it's probably the case that given any ethical dilemma (and, I suppose, given any situation where ethical thinking might come into play, regardless of whether [i]I[/i] consider it a dilemma) I can find two people to take opposite positions on what the ethical action would be.  That's fine.  "The ethics of everyone" is certainly not going to be sumarizable in a few short axioms because "the ethics of everyone" isn't well-defined.

[b]However[/b], "the ethics of t0rajir0u" [i]is[/i] (or could be) well-defined.  You have some ethical principles that you apply in your life.  Why shouldn't [i]those[/i] principles be simple axioms that you can apply to any ethical dilemma you face?  I, or Pope Ratzinger, or Albert Einstein, might not agree with your axioms or your conclusions, but it's not at all clear why you think the potential disagreement of others precludes you from having a nice ethical system.

A additional comment: I personally do strive for coherence in my ethical views.  That is, when I am from time to time confronted with what appears to be a conflict among my ethical views, I generally try to figure out what the underlying principles are and, if they lead to contradiction, adjust them accordingly.  That is, I believe an axiomatized ethical system can be robust to new information -- arguing from basic principles is not inherently inflexible.

So, in light of that long-winded explanation, I hope my previous questions now seem more piercing and insightful ;-)

[quote="1234567890"]JBL, assume that the murderers will continue murdering if released. And you can just execute the prisoners in the way you suggested. My interest is in trying to find the "value" of life versus the safety for the general population.[/quote]

Aha! Now we have figured out how to distinguish the muderers from the innocent :wink:. Just let them all go and keep people watching them - when they try to make a move, catch them in the act!

[quote="JBL"][b]However[/b], "the ethics of t0rajir0u" [i]is[/i] (or could be) well-defined.  You have some ethical principles that you apply in your life.  Why shouldn't [i]those[/i] principles be simple axioms that you can apply to any ethical dilemma you face?  I, or Pope Ratzinger, or Albert Einstein, might not agree with your axioms or your conclusions, but it's not at all clear why you think the potential disagreement of others precludes you from having a nice ethical system.[/quote]

The problem with principles is that they have necessarily been formed in some kind of context.  Once the context changes, principles can become [b]outdated[/b] or [b]irrelevant.[/b]  When following one's principles, from an earlier time, no longer actually produces the best outcome [b]now[/b], can you really be said to be behaving ethically?  Or are you just succumbing to [url=http://en.wikipedia.org/wiki/Belief_perseverance]belief perseverance[/url]?

Ethical principles themselves can be regarded as [b]heuristics[/b], and like any other heuristics, this implies a certain [b]incompleteness[/b].  There will be situations where any set of ethical principles will fail to come to consensus on a particular decision, and may in fact be at odds (the principles, for example, of freedom vs. equality, as applied to the government's role in the economy).  So what then?

[quote="JBL"]That is, when I am from time to time confronted with what appears to be a conflict among my ethical views, I generally try to figure out what the underlying principles are and, if they lead to contradiction, adjust them accordingly. That is, I believe an axiomatized ethical system can be robust to new information -- arguing from basic principles is not inherently inflexible. [/quote]

Ah, I see what you mean. Perhaps you're right; I can imagine such axioms, although I am not convinced that they are likely to make a complete and consisent set. I can think of extremistic examples where they are all you need to know -- for example, [i]Believe in the Big Brother and do what he tells you to do[/i].

But for a person who reflects on a number of his choices... Well, I'm not sure that this person can have such a set of axioms. I can think of several reasons why not: for instance, a person changes his views as he grows older. His axioms should change as well, right? Sometimes, they can change on a daily basis. You've already pointed out this phenomenon. How can you consider to have an axiomatized ethical system if it changes with time?

You may argue that you don't change your axioms but rather alter the way you comprehend new information and your actions so that it fits into your axioms (which are maybe somehow inherent to you). But this implies the possibility of self-deceit, at least. Do you agree?

Furthermore, doesn't the very existence of a set of axioms mean that when an ethical problem presents itself, you can decide how to act based on those axioms? But from your words, you seem to act first and axiomatize later. :huh:

[quote="Treething"]For example, in the second scenario, what if they were all Muslim? That'd probably influence one's decision. Nobody likes Muslims.[/quote]

Although I realize you meant to refute my point sarcastically, this is not a bad example of what I mean when I say that your definition of your "group" affects your moral judgment.  If your group doesn't include Muslims, then your decisions don't have to take the well-being of Muslims into account.  If your community agrees, this is a morally consistent judgment within the community.  Whether you agree or disagree is another matter.

#1
When n=0 I'd execute everybody.
When n>1 or =1 I'd execute everybody.

#2
When n=0 I'd execute everybody.
When 1<n<100 I'd execute everybody.
When n>100 I'd let everybody free.


[quote="13375P34K43V312"]A circle with center O has a diameter AB. A point C is chosen on the circle such that AC=6 and BC=8. Find the area of the circle.[/quote]
[hide="not that hard..."]AC+BC=AB
The radius of the circle is 7 so the area is
$49 \pi$[/hide]

[hide][img]http://i96.photobucket.com/albums/l167/adasarathy/circleproblem2.gif[/img]

So, teh radius is 5, and the area is $25\pi$

Where did I go wrong? :maybe: [/hide]

bpms you might want to try drawing the circle, it is harder than that.  If it was that simple though, then the diameter would be 7 and the area would not be 49$\pi$

Edit : Guess my suggestion wasn't fast enough

But that triangle's a right triangle, right?

Yeah, anirudh is right. It's good to know that any triangle inscribed in a circle that has one of its sides as the diameter is right. This is because, as mathgenius said, it interceps a semicircular arc.

Yup, that's how it works because the measure of an inscribed angle is exactly half the measure of the arc that it intercepts. [hide]Then, the measure of angle ACB is 90 degrees, because AB is a diameter which makes a 180 degree arc and inscribed angle ACB intercepts it. Then, by implementing the Pythagorean Theorem, $6^{2}+8^{2}=10^{2}$ so the diameter is 10, the radius is 5 and the area is $25\pi$[/hide]

[quote="anirudh"][quote="mathgeniuse^ln(x)"]Yes, since it intercepts a semicircular arc.[/quote]

yes. I didn't know though if that theorem was mathcounts level though.  :( But, you could still use pythagorean. :roll:[/quote]
That theorem is definitely mathcounts. Anyways, you can't use pythagorean unless you know it's true :roll:

If AC=x and BC=y, here is the area:

[hide="in here..."]$\frac{x^{2}+y^{2}}{4}pi$[/hide]


Prove $ \binom{n}{p} \equiv [\frac{n}{p}] \pmod{p}$ where $ p$ is a prime.

You can do it without the strength of the full argument, but you might as well just use [url=http://en.wikipedia.org/wiki/Lucas%27_theorem]Lucas' theorem[/url].


The teacher of our gifted program Honors Geometry is a pretty nice guy, the only problem is the curriculum, which is enough to make anyone except a teacher's pet fall asleep.
It sucks!
We learn all this stuff that we probably already know and whenever  I start complaining about it and the rest of the students too, he says that the NC board of education made him and if he had a choice he would choose AoPS "textbooks".  (he knows about AoPS)

So what do you think I should do?

Petition for a super-honors class. :roll:

switch to a higher level class? like, skip geometry...do higher math if this is too easy...then teh teacher will have some impact hopefully... :lol:

If “gifted” honors Geometry is so easy then request to take the final early and move on to another math course. However, it may be too late in the year to switch math classes. :ninja:

If you and everyone else already know the material, what's the point of even teaching it?

Maybe you could ask him to maybe test you guys on all the material, and only go over the parts where you need help?

You could ask your teacher if you could plair the course.(I hope I spelled it right :P !)

You could secretly use AoPS books with your teacher and then pass finals.

Suggest that he do one day of required lessons (cram a week's worth of stuff into one day), test the next day and spend the rest of the week doing fun stuff. Don't ask him to move to material for the next grade level, since you'll be in the same predicament next year. Ask him to do stuff not in the curriculum.

Try getting a bunch of students and parents together, and petition to the school board for better classes/ textbooks. Especially if they can find a donor for the textbooks. Or consider asking for a very accelerated course; where i go to school there are classes that teach geometry-precalc in 2 years

Skip classes, and get into other stuff like music and drama.
Or delcare a strike and get the class to sit outside the staff room (preferably at lunch or tea when everyone is inside), allowing no teacher to come out till you get a better course.

I opt to do a lot of other math stuff like AMC and past test junk during class instead of listening to the teacher. Honors Geometry is a Big Fat Joke! It's called easy 100, because stupid textbooks are used to teach. Waste of 50 minutes per day, and it accumulates to 2 semesters!  :o

[quote="Go Around the Tree"]yeah i secretly study real math at home.

Since school geometry honors is a joke, and most of it is known.[/quote]

Very reasonable, but why the secrecy?

my mom thinks I should spend more time on reading rofl

no lol i wish

as in stupid novels and science fiction books

[quote="asdf2345"]I would not pay attention in class and do real math. then ace all the tests.[/quote]

that's what I did in HonGeom
and it's what I'm doing in HonPre-Cal (after I skipped out of HonAlg2)

Algebra is always useful, and if it is not inequalities, it is interesting as well.
But I still don't get your objection to novels and science fictions. :maybe:

it's just aggravating to have your mom making you memorize vocab when you don't want to sometimes.

Do a perfect proof of a geometrical fact, like that if a trapeziod is isoscoles, the area of it is the average of the two bases times the height.  Sure fireway...

your mom make your read books to memorize vocabs?
yuck!

[quote="Xantos C. Guin"]Do what I would have done: learn by yourself, ace the tests, and do more worthwhile things during class.[/quote]

Nice. That's the classic way to do it.  :lol:

Do what I would do.  Don't do the homework, draw caricatures of the teacher on your tests, and in general be an all-around obnoxious idiot.

...this is middle school, right?  So the grades don't count?

In my school the difference between Honors Geometry and regular is the fact that Honors goes through and proves all the theorems, and regular "measures" and looks for patterns before declaring a theorem true. Honors should be regular, and regular is a joke.

[quote]Don't do the homework, draw caricatures of the teacher on your tests, and in general be an all-around obnoxious idiot.[/quote]
That reminds me of this one time the teacher was doing a problem in trig. She made a mistake and the one kid who did absolutely nothing except playing calculator games and screwing around with his girlfriend corrected her. The teacher never scolded him again, so he played games for the rest of the year (and aced all his tests).

But I guess since we're here at AoPS, we all think this way.

See [url]http://www.artofproblemsolving.com/Forum/viewtopic.php?t=122922[/url], if you haven't already.[/quote]


It's equivalent to:
[tex]\sum^n_{k=0} 2^{2k}\mathrm{C}^{2k}_{2n}\mathrm{C}^{n-k}_{2n-2k}=\mathrm{C}^{2n}_{4n} [/tex]
it's really hard!I have a solution but it's wrong!Can u post ur solution!

My solution:

Suppose that there are $2n$ boys and any of them wants job ,and there are 2 factories and one company which needs employees. but 2 factories must have equal number of employees. Now we count the ways of this work two times:

1:suppose the number of employees is $n-k$ where $1 \leq n-k \leq n $ now we choose them in \[(_{n-k\   n-k\   2k}^{\                    2n})=\frac{(2n)!}{(n-k)!^2(2k)!}\]
and now choose a subset from the other $2k$ boys in $2^{2k}$ ways.
so this is done in $\sum_{k=0}^{k=n}\frac{2^{2k}\times(2n)!}{(n-k)!^2(2k)!}$ ways :!:

2:we choose two subsets(some boys may be choosen in both of them) with equal number of boys from$2n$ boys to work for 2 factories but we will send those boys (which are in both subsets) to company.this is clearly done in
$\sum_{j=0}^{j=2n}(_{j}^{2n})^2$ which is equal  $(_{2n}^{4n})$.

so proof is complete. :D  :lol:

____
Good luck.

It's very nice equality. :D
Here is my approach:Using the directly consequen from Ukraina 1996:Let M be set of numbers of 2n digits with n digits 1 and n digits 2.Let N be set of numbers of n digits with digits 1,2,3,4 fulfilling :the number of digits 1 equals to the number of digits 2.Then |M|=|N|.Hence:
$\sum_{k=0}^{[\frac{n}2]}C^k_nC^k_{n-k}2^{n-2k}=C^n_{2n}$
Instead of n by 2n:$\sum_{k=0}^nC^k_{2n}C^k_{2n-i}2^{2n-2k}=C^{2n}_{4n}$
And finally instead of k by n-k$\sum_{k=0}^nC^{n-k}_{2n}C^{n-k}_{n+k}2^{2k}=C^{2n}_{4n}$
It's the desired thing(after conclusion)


probability
conditional probability
probability and stats

Hey all

This is an assignment question, so no outright solution please. I would like for someone to verify my answer for part a), and get me started on part b).

Problem Statement:
An inspector in a factory has a 95% of correctly identifying a defective part, and a 2% chance of incorrectly classfiying a good part as defective. 1% of all items are defective.

a) What is the probability that an item selected for inspection is classified as defective?
b)If an item is classified as good, what is the probability that it is actually good?

a) $ 0.95*0.01 \plus{} 0.02*0.99 \equal{} 0.0293$
breakdown: an item chosen at randome has a 1% chance of being defective, and  95% chance of being identified as such, plus it has a 99% chance of being good, with a 2% chance of being classified broken.

Can someone verify that answer?

b) let A be the event that the item is actually good
let B be the event that the item is classified as good
This is conditional probability: $ P(A|B) \equal{} \frac {P(A \cap B)}{P(B)}$

EDIT: figured it out. Using Baye's theorem, I get that b) $ P(A|B) \equal{} 0.99948$

Can someone verfiy?

Your way of computation is perfectly fine. I'm too lazy to verify the arithmetic without a calculator though :).


function
modular arithmetic
algebra unsolved
algebra

1) Find the close form of
\[ T(x) \equal{} 3 \sum_{k \equal{} 0}^{n} \binom{3n}{3k}.
\]
Please, I need algebric solution & put it step by step (Anyone have books of generating functions ?).

2) Let $ f: \mathbb{R} \to \mathbb{R}$ (decreasing function), and $ a,b,c \in \mathbb{R}^ \plus{}$ satisfy
\[ a \plus{} \sqrt 2 \equal{} b \plus{} \sqrt 3 \equal{} c \plus{} \sqrt 5 \equal{} k.
\]
Prove that
\[ f\left(a\sqrt 3 \plus{} b\sqrt 5 \plus{} c\sqrt 2 \right) \ge f(k^2).
\]

[quote="mathson"] 2) Let $ f: \mathbb{R} \to \mathbb{R}$, and $ a,b,c \in \mathbb{R}^ \plus{}$ satisfy
\[ a \plus{} \sqrt 2 \equal{} b \plus{} \sqrt 3 \equal{} c \plus{} \sqrt 5 \equal{} k.
\]
Prove that
\[ f\left(a\sqrt 3 \plus{} b\sqrt 5 \plus{} c\sqrt 2 \right) \ge f(k^2).
\]
[/quote]

This is obviously wrong.

As soon as $ k>\sqrt 5$ is such that $ k^2\neq (k\minus{}\sqrt 2)\sqrt 3 \plus{} (k\minus{}\sqrt 3)\sqrt 5 \plus{} (k\minus{}\sqrt 5)\sqrt 2$ you can choose a $ f(x)$ such that  $ f(k^2)< f(a\sqrt 3 \plus{} b\sqrt 5 \plus{} c\sqrt 2)$

[quote="mathson"]1) Find the close form of
\[ T(x) \equal{} 3 \sum_{k \equal{} 0}^{n} \binom{3n}{3k}.
\]
Please, I need algebric solution & put it step by step (Anyone have books of generating functions ?).
[/quote]

Sorry, but I dont know what is an "algebraic" solution. Hope this will fit your requirements :

Let $ S(x) \equal{} (1 \plus{} x)^{3n} \equal{} \sum_{k \equal{} 0}^{3n}\binom{3n}{k}x^{k}$

$ S(x) \equal{} \sum_{k \equal{} 0,k \equal{} 0\pmod 3}^{3n}\binom{3n}{k}x^{k}$ $ \plus{} \sum_{k \equal{} 0,k \equal{} 1\pmod 3}^{3n}\binom{3n}{k}x^{k}$ $ \plus{} \sum_{k \equal{} 0,k \equal{} 2\pmod 3}^{3n}\binom{3n}{k}x^{k}$

Let then complex number (cubic root of 1) $ j \equal{} e^{\frac {2i\pi}{3}}$. Since $ j^3 \equal{} 1$, we can write : $ j^{k} \equal{} j^{k\pmod 3}$

Let then complex number (another cubic root of 1) $ j^2 \equal{} e^{\frac {4i\pi}{3}}$. Since $ (j^2)^3 \equal{} 1$, we can also write : $ (j^2)^{k} \equal{} (j^2)^{k\pmod 3}$

$ (1 \plus{} 1)^{3n} \equal{} S(1) \equal{} \sum_{k \equal{} 0,k \equal{} 0\pmod 3}^{3n}\binom{3n}{k}$ $ \plus{} \sum_{k \equal{} 0,k \equal{} 1\pmod 3}^{3n}\binom{3n}{k}$ $ \plus{} \sum_{k \equal{} 0,k \equal{} 2\pmod 3}^{3n}\binom{3n}{k}$

$ (1 \plus{} j)^{3n} \equal{} S(j) \equal{} \sum_{k \equal{} 0,k \equal{} 0\pmod 3}^{3n}\binom{3n}{k}$ $ \plus{} \sum_{k \equal{} 0,k \equal{} 1\pmod 3}^{3n}\binom{3n}{k}j$ $ \plus{} \sum_{k \equal{} 0,k \equal{} 2\pmod 3}^{3n}\binom{3n}{k}j^2$

$ (1 \plus{} j^2)^{3n} \equal{} S(j^2) \equal{} \sum_{k \equal{} 0,k \equal{} 0\pmod 3}^{3n}\binom{3n}{k}$ $ \plus{} \sum_{k \equal{} 0,k \equal{} 1\pmod 3}^{3n}\binom{3n}{k}j^2$ $ \plus{} \sum_{k \equal{} 0,k \equal{} 2\pmod 3}^{3n}\binom{3n}{k}j$

Notice that $ (1 \plus{} j)^3 \equal{} ( \minus{} j^2)^3 \equal{} \minus{} 1$ and $ (1 \plus{} j^2)^3 \equal{} ( \minus{} j)^3 \equal{} \minus{} 1$ and add these 3 equalities and remember $ 1 \plus{} j \plus{} j^2 \equal{} 0$ and you get :

$ 2^{3n} \plus{} 2( \minus{} 1)^n$ $ \equal{} 3\sum_{k \equal{} 0,k \equal{} 0\pmod 3}^{3n}\binom{3n}{k}$ $ \equal{} 3\sum_{k \equal{} 0}^{n}\binom{3n}{3k}$

Hence the result : $ 3\sum_{k \equal{} 0}^{n}\binom{3n}{3k}$ $ \equal{} 2^{3n} \plus{} 2( \minus{} 1)^n$

[quote="pco"][quote="mathson"] 2) Let $ f: \mathbb{R} \to \mathbb{R}$, and $ a,b,c \in \mathbb{R}^ \plus{}$ satisfy
\[ a \plus{} \sqrt 2 \equal{} b \plus{} \sqrt 3 \equal{} c \plus{} \sqrt 5 \equal{} k.
\]
Prove that
\[ f\left(a\sqrt 3 \plus{} b\sqrt 5 \plus{} c\sqrt 2 \right) \ge f(k^2).
\]
[/quote]

This is obviously wrong.

As soon as $ k > \sqrt 5$ is such that $ k^2\neq (k \minus{} \sqrt 2)\sqrt 3 \plus{} (k \minus{} \sqrt 3)\sqrt 5 \plus{} (k \minus{} \sqrt 5)\sqrt 2$ you can choose a $ f(x)$ such that  $ f(k^2) < f(a\sqrt 3 \plus{} b\sqrt 5 \plus{} c\sqrt 2)$[/quote]

Sorry, I forgot to write : $ f$ is decreasing function.

By the way, Your solution for the second one is elegant.

[quote="mathson"] 2) Let $ f: \mathbb{R} \to \mathbb{R}$ (decreasing function), and $ a,b,c \in \mathbb{R}^ \plus{}$ satisfy
\[ a \plus{} \sqrt 2 \equal{} b \plus{} \sqrt 3 \equal{} c \plus{} \sqrt 5 \equal{} k.
\]
Prove that
\[ f\left(a\sqrt 3 \plus{} b\sqrt 5 \plus{} c\sqrt 2 \right) \ge f(k^2).
\]
[/quote]

You have $ a\equal{}k\minus{}\sqrt 2$, $ b\equal{} k\minus{} \sqrt 3$ and $ c \equal{} k \minus{} \sqrt 5$

Since $ f(x)$ is a decreasing function, your requirement is to show that $ a\sqrt3 \plus{} b\sqrt 5 \plus{} c\sqrt 2\leq k^2$ $ \forall k>\sqrt 5$ (in order $ a,b,c\in\mathbb R^\plus{}$) so that :

$ (k \minus{} \sqrt 2)\sqrt 3 \plus{} (k \minus{} \sqrt 3)\sqrt 5 \plus{} (k \minus{} \sqrt 5)\sqrt 2 \leq k^2$

$ k^2 \minus{} k(\sqrt 3 \plus{} \sqrt 5 \plus{} \sqrt 2) \plus{} \sqrt 6 \plus{} \sqrt{15} \plus{} \sqrt{10} \geq 0$

The  minimum value of LHS is reached for $ k\equal{}\frac{\sqrt 3 \plus{} \sqrt 5 \plus{} \sqrt 2}{2}$ and its value is :

$ m\equal{}\sqrt 6 \plus{} \sqrt{15} \plus{} \sqrt{10} \minus{} \frac{(\sqrt 3 \plus{} \sqrt 5 \plus{} \sqrt 2)^2}{4}$

$ 4m\equal{}4\sqrt 6 \plus{} 4\sqrt{15} \plus{} 4\sqrt{10} \minus{}$ $ (3 \plus{} 5 \plus{} 2 \plus{} 2\sqrt 6 \plus{} 2\sqrt {10} \plus{} 2\sqrt {15})$

$ 4m\equal{}2\sqrt 6 \plus{} 2\sqrt{15} \plus{} 2\sqrt{10} \minus{} 10$

And, since $ 2\sqrt{15} > 6$ and $ 2\sqrt{10} > 6$, we obviously have $ 2m > 12 \minus{} 10 > 0$

Q.E.D.

(but it's not an olympiad problem) :(


Let $a,b,c>0$. Prove that :
$\frac{\left( b+c-a\right) ^{2}}{(b+c)^{2}+a^{2}}+\frac{\left( c+a-b\right) ^{2}}{(c+a)^{2}+b^{2}}+\frac{\left( a+b-c\right) ^{2}}{(a+b)^{2}+c^{2}}\geq \frac{3}{5}$
Sorry if it was posted before  :D


induction function algebra polynomial AMC USA(J)MO USAMO

Let $n\geq 1$ be an integer. Let $S_{n}$ be the number of permutations $\left(a_{1},a_{2},...,a_{n}\right)$ of $\left(1,2,...,n\right)$ such that $1\leq\left|a_{k}-k\right|\leq 2$ for all $k\in\left\{1,2,...,n\right\}$.

Show that $7S_{n-1}<4S_{n}<8S_{n-1}$ for all $n > 6$.

Oh,It is very hard problem!!
Hint :
  S_(n+1)=2S_n-2S_(n-4)+S_(n-5)

This is an interesting problem but it is not a difficult one.
I think that the hint may make the other people confused because I think that this problem can't be solve by induction.

not to solve it with induction, that would be too easy of course :D

but seeing this may be useful in some problems (however I don't think it's very useful in here...)

Why are all Vietnamese problems this complicated?

Let $L_n$ be the number of invertible functions $f(k)$ from {1,2,...,n-1,n} to {1,2,...,n-1,n+1} satisfying $|f(k)-k|=$ 1 or 2.
We can classify the permutations that define $S_n$ by:
Case 1: $f(n)=n-1$
This gives $L_{n-1}$ possibilities.
Case 2: $f(n)=n-2$, and $f(n-1)=n$
This gives $L_{n-2}$ possibilities.
Case 3: $f(n)=n-2$, and $f(n-1)=n-3$
This forces $f(n-2)=n$, and $f(n-3)=n-1$, giving $S_{n-4}$ possibilities.
We have $S_n=L_{n-1}+L_{n-2}+S_{n-4}$

Now for $L_n$
Case 1: $f(n)=n+1$
This gives $S_{n-1}$ possibilities.
Case 2: $f(n-1)=n+1$ and $f(n)=n-1$
This gives $S_{n-2}$ possibilities.
Case 3: $f(n-1)=n+1$ and $f(n)=n-2$
This gives $L_{n-2}$ possibilities.
We have $L_n=S_{n-1}+S_{n-2}+L_{n-2}$

By the first equation, $S_{n+1}-S_n=L_n-L_{n-2}+S_{n-3}-S_{n-4}$
The second lets us substitute for $L_n-L_{n-2}$, so  $S_{n+1}-S_n=S_{n-1}+S_{n-2}+S_{n-3}-S_{n-4}$

Assume that $\frac{7}{4}S_k < S_{k+1} < 2S_k$ for $k=n-1,n-2,n-3,n-4$
Then $S_{n-3}-S_{n-4}>\frac{3}{7}S_{n-3}$ and $S_{n-i}>2^{-i}S_n$, so
$S_{n+1} = S_n+S_{n-1}+S_{n-2}+S_{n-3}-S_{n-4} > S_n+\frac{1}{2}S_n+\frac{1}{4}S_n+\frac{3}{56}S_n= (\frac{7}{4}+\frac{3}{56})S_n > \frac{7}{4}S_n$

Also, $S_{n-3}-S_{n-4}<\frac{1}{2}S_{n-3}$ and $S_{n-i}<(\frac{4}{7})^iS_n$, so
$S_{n+1} = S_n+S_{n-1}+S_{n-2}+S_{n-3}-S_{n-4} < S_n+\frac{4}{7}S_n+\frac{16}{49}S_n+\frac{32}{343}S_n= (2-\frac{3}{343})S_n < 2S_n$

Based on these two results, we will have the desired result by induction if we can establish the base cases  $\frac{7}{4}S_k < S_{k+1} < 2S_k$ for $k=6,7,8,9$

By formula logic, $S_0=1$ and $L_0=0$ By inspection, $S_1=0$, $L_1=1$, and $S_2=1$ The recursion gives us $L_2=1$ (easily verified directly) and $L_3=2$. We have $S_3=2$ (the two three-cycles) and $S_4=4$ by formula. (Verification: $1 \to 2 \to 1, 3 \to 4 \to 3$ or $1 \to 2 \to 4 \to 3 \to 1$ or $1 \to 3 \to 4 \to 2 \to 1$ or $1 \to 3 \to 1, 2 \to 4 \to 2$) Also, $L_4=4$ by formula. The recursive formulas now give us $S_5=6$, $L_5=8$, and $S_6=13$. We no longer need to calculate $L_n$, and $S_7=24$, $S_8=45$, $S_9=84$, $S_{10}=160$.
Since $\frac{24}{13}, \frac{45}{24}, \frac{84}{45}$, and $\frac{160}{84}$ are all between $\frac{7}{4}$ and 2, we are done.

By the recursion, $S_n$ can be written as $a_1 \cdot r_1^n + a_2 \cdot r_2^n + a_3 \cdot r_3^n + a_4 \cdot r_4^n + a_5 \cdot r_5^n$ where $r_1,r_2,r_3,r_4,r_5$ are the roots of $x^5-x^4-x^3-x^2-x+1=0$. The polynomial factors as $(x+1)(x^4-2x^3+x^2-2x+1)$, and we can solve by the substitution $y = x+\frac{1}{x}$; this gives $x=-1$ or $y^2-2y-1=0$, so $y=1 \pm \sqrt{2}$. The case $y=1-\sqrt{2}$ gives two complex numbers on the unit circle for $x$, and the case $y=1+\sqrt{2}$ gives two real values of $x$ which are reciprocals of each other. The larger, which dominates the behavior of $S_n$ for large $n$, is about 1.883.

[quote="jmerry"]Why are all Vietnamese problems this complicated?
[/quote] Really ? I think it is not as difficult as USAMO tests  :D
I think i have another solution I will post it later
- Thanks Jmerry for a beauty solution above !

The sequence $S_{n}$ is given by [url=http://oeis.org/A033305]A033305[/url] and satisfies the following recurrence of the 5-th order: \[S_{n}= S_{n-1}+S_{n-2}+S_{n-3}+S_{n-4}-S_{n-5}.\]

It can be shown that \[S_{n}=S_{n-2}+S_{n-4}+2\bigl(S_{n-3}+\cdots+S_{0}\bigr)\] Then $S_{n}-S_{n-1}$ gives $S_{n}=S_{n-1}+S_{n-2}+S_{n-3}+S_{n-4}-S_{n-5}$ as mentioned above.  Repeating $S_{n}-S_{n-1}$ gives $S_{n}=2S_{n-1}-2S_{n-5}+S_{n-6}$ which is also mentioned above.

My question is this:  Does anyone know how to  directly derive the simple recurrences?  Or do you have to start with the long recurrence?

[quote="Negative_3"]Does anyone know how to  directly derive the simple recurrences?  Or do you have to start with the long recurrence?[/quote]

The most straightforward way would be to find all factors of a characteristic polynomial and check if initial terms of the sequence satisfy any of them.

For example, a recurrence $S_{n}=2S_{n-1}-2S_{n-5}+S_{n-6}$ correspond to a characteristic polynomial $x^{6}-2x^{5}+2x^{4}-1.$ This polynomial is factored as $x^{6}-2x^{5}+2x^{4}-1 = (x-1)(x^{5}-x^{4}+x^{3}+x^{2}+x+1).$ The latter factor here happens to deliver another recurrence: $S_{n}=S_{n-1}+S_{n-2}+S_{n-3}+S_{n-4}-S_{n-5}.$

it CAN be solved by induction. I've done it that way year ago ;)

Yes it can.  From $S_{n}=2S_{n-1}-2S_{n-5}+S_{n-6}$ we have immediately that $S_{n}<2S_{n-1}$ (since $S_{n-5}>S_{n-6}$) which is one of the desired inequalities.

For the other bound, repeatedly using the inital inequality (which we can do since we are inducting) gives

$S_{n}=2S_{n-1}-2S_{n-5}+S_{n-6}>2S_{n-1}-2S_{n-5}>2S_{n-1}-2\left(\frac{4}{7}\right)^{4}S_{n-1}>\frac{7}{4}S_{n-1}$

BTW - What is the non-inductive solution?

From the contest this year, there was another problem a bit long, and this one was very long (not only on the solution, it was complicated to think). That explained why no one (maybe 1 or 2) solved completely this one in the contest.

[quote]It can be shown that
                                $S_{n}=S_{n-2}+S_{n-4}+2(S_{n-3}+\ldots+S_{0})$[/quote]
can you show ? i cannot prove it.

Let's call the permutations that meet the condition of the problem [i]good[/i].  Call a permutation $w = w_1 \cdots w_n$ [i]decomposable[/i] if there is some $k$ such that for all $i \leq k < j$, $w_i < w_j$, and call a permutation [i]indecomposable[/i] otherwise.  To get the version of the recursion mentioned above, show that for each $n > 4$, there are exactly two good indecomposable permutations of length $n$.  For example, for $n = 7$ these permutations are 2416375 and 3152746; for $n = 8$ they are 24163857 and 31527486.  Now observe that every good permutation can be written uniquely as a [url=https://en.wikipedia.org/wiki/Direct_sum_of_permutations]direct sum[/url] of good indecomposable permutations.  Finally, note that there are zero good indecomposable permutations of length 1, one of length 2, two of length 3 and three of length 4.  It follows that $S_n = S_{n - 2} + 2S_{n - 3} + 3S_{n - 4} + 2(S_{n -5} + \ldots + S_0)$.


Hello,

Prove that :  $ S\equal{}\cos\frac{\pi}{17}\plus{}\cos\frac{3\pi}{17}\plus{}\cdots\plus{}\cos\frac{15\pi}{17}
 \in \mathbb{Q}$.

[hide]Applying $ \cos{k\pi\over 17}+\cos{(16-k)\pi\over 17}=2\cos{8\pi\over 17}\cos{(8-k)\pi\over 17}$ for $ k\in\{1,3,5,7\}$, we get

$ S=2\cos{8\pi\over 17}\left(\cos{\pi\over 17}+\cos{3\pi\over 17}+\cos{5\pi\over 17}+\cos{7\pi\over 17}\right)$

Repeating the process, we eventually get

$ S=8\cos{8\pi\over 17}\cos{4\pi\over 17}\cos{2\pi\over 17}\cos{\pi\over 17}$

Now

\begin{eqnarray*}S\sin{\pi\over 17} &=& 4\cos{8\pi\over 17}\cos{4\pi\over 17}\cos{2\pi\over 17}\sin{2\pi\over 17}\\ &=& 2\cos{8\pi\over 17}\cos{4\pi\over 17}\sin{4\pi\over 17}\\ &=& \cos{8\pi\over 17}\sin{8\pi\over 17}\\ &=& {1\over 2}\sin{16\pi\over 17}\\ &=& {1\over 2}\sin{\pi\over 17}\end{eqnarray*}

Therefore $ S={1\over 2}$[/hide]

[hide="to above"]$ \sin \frac {\pi}{17} \equal{} \minus{} \sin \frac {16\pi}{17}$, so you're off by a sign. :( [/hide]

[hide="Less trig"]Since $ \cos \frac {k \pi}{17} \equal{} \cos \frac {(17 \minus{} k)\pi}{17}$,
\[ 2S \equal{} \sum_{k \equal{} 1}^{16} \cos \frac {k \pi}{17},
\]

\[ 2S \plus{} 1 \equal{} \sum_{k \equal{} 1}^{16} \cos \frac {k \pi}{17}.
\]
But the RHS of that is the sum of the real parts of the 17th roots of unity which is $ 0$. Therefore $ 2S \plus{} 1 \equal{} 0$ and $ S \equal{} \minus{} 1/2$.[/hide]\

EDIT: DER! What happened is I got my $ \pi$ and $ 2\pi$ mixed up.

[quote="MellowMelon"]Since $ \cos \frac {k \pi}{17} \equal{} \cos \frac {(17 \minus{} k)\pi}{17}$,...[/quote]

So uh... off by two signs?
\[ \cos\frac {k\pi}{17} \equal{} \minus{} \cos\frac {(17 \minus{} k)\pi}{17}
\]
:(

Edit: Plus, Farenhajt was right that $ \sin \frac{\pi}{17}\equal{}\sin\frac{16\pi}{17}$. Oh dear, have you gotten your $ \sin$ and $ \cos$ mixed up?

[quote="MellowMelon"][hide="to above"]$ \sin \frac {\pi}{17} \equal{} \minus{} \sin \frac {16\pi}{17}$, so you're off by a sign. :( [/hide]

[hide="Less trig"]Since $ \cos \frac {k \pi}{17} \equal{} \cos \frac {(17 \minus{} k)\pi}{17}$,
\[ 2S \equal{} \sum_{k \equal{} 1}^{16} \cos \frac {k \pi}{17},
\]

\[ 2S \plus{} 1 \equal{} \sum_{k \equal{} 1}^{16} \cos \frac {k \pi}{17}.
\]
But the RHS of that is the sum of the real parts of the 17th roots of unity which is $ 0$. Therefore $ 2S \plus{} 1 \equal{} 0$ and $ S \equal{} \minus{} 1/2$.[/hide][/quote]

 :huh: $ \sin{\pi\over 17} \equal{} \sin\left({\pi \minus{} {\pi\over 17}}\right) \equal{} \sin{16\pi\over 17}$

Well, if you don't want to actually evaluate it, [hide="then..."] as an element of $ \mathbb{Q}[\zeta_{17}]$ it is obviously fixed by every element of the Galois group since, as MellowMelon noted , $ \cos \frac{k \pi}{17} \equal{} \cos \frac{(17 \minus{} k)\pi}{17}$. [/hide]