Prove that for any positive $ x_1,x_2,\ldots,x_n,y_1,y_2,\ldots,y_n$ the inequality
\[ \sum_{i\equal{}1}^n\frac1{x_iy_i}\ge\frac{4n^2}{\sum_{i\equal{}1}^n(x_i\plus{}y_i)^2}
\] holds.

Use the Adreescu inequality, and then the basic$ (x\plus{}y)^2\geq4xy$

[quote="gwen01"]Prove that for any positive $ x_1,x_2,\ldots,x_n,y_1,y_2,\ldots,y_n$ the inequality
\[ \sum_{i \equal{} 1}^n\frac1{x_iy_i}\ge\frac {4n^2}{\sum_{i \equal{} 1}^n(x_i \plus{} y_i)^2}
\]
holds.[/quote]
$ \sum_{i \equal{} 1}^n\frac1{x_iy_i}\ge\frac {4n^2}{\sum_{i \equal{} 1}^n4x_iy_i} \ge \frac {4n^2}{\sum_{i \equal{} 1}^n(x_i \plus{} y_i)^2}$
The first by AM-HM, and the second by $ (x_i \plus{} y_i)^2 \ge 4x_iy_i$ and using that $ x \to \frac{1}{x}$ is decreasing.

A bit of a revive, but here's a solution using Cauchy-Schwarz.

We'll rewrite the given inequality as \[ \sum_{i=1}^n \frac{1}{x_i y_i} \cdot  \sum_{i=1}^n (x_i+y_i)^2 \geq 4n^2. \]
Now we'll use Cauchy in the first and AM-GM in the second step and get \begin{align*} \sum_{i=1}^n \frac{1}{x_i y_i} \cdot  \sum_{i=1}^n (x_i+y_i)^2 &\stackrel{\text{CS}}{\geq} \left(\sum_{i=1}^n \frac{x_i+y_i}{\sqrt{x_iy_i}} \right)^2 \\ &\geq \left(\sum_{i=1}^n \frac{2\sqrt{x_iy_i}}{\sqrt{x_iy_i}} \right)^2 \\ &= (2n)^2 \\ &= 4n^2. \end{align*}
Hence, we're done. $\hfill\blacksquare$


For some reason, the permission list on the lower right hand corner of a thread is messed up.

I've seen that many times, it also occurs on polls.


complex analysis
integration
calculus
complex analysis unsolved

Suppose $ f$ is holomorphic on a region $ \Omega$, the closed ball $ \overline{D}(a, r)\subset \Omega$, and $ \gamma$ is the positively oriented circle with center $ a$ and radius $ r$.

Suppose $ f(z)\neq 0$ for any $ z\in \gamma$. What is the value of

$ \frac{1}{2\pi i}\int_\gamma \frac{f'(z)}{f(z)}z^pdz$ in terms of the number of zeros of $ f$. Of course for $ p\equal{}0$, this is just the argument principle, so it is the number of zeros of $ f$.

My guess would be that you multiply the number of zeros by $ p$, but I don't have justification for that. The inside of the integral doesn't look like $ \frac{g'(z)}{g(z)}$, at least in any obvious way.

It is the sum of $ p$-th powers of all zeroes of $ f$ inside the curve counted with multiplicity if $ p\ge 0$ (just use the residue theorem). If $ p<0$, you also need to take care of the pole at $ 0$. In any case, it is not expressible in terms of the [i]number[/i] of zeroes only.


USAMTS
geometry
parallelogram
geometric transformation
homothety
induction
AMC

Sweet ... I'm totally the first one to start talking about USAMTS round 4!

What did you guys think?  I personally thought this one was the hardest round of all, but I got answers to all of them.  In addition, I thought this round had the most interesting problems so far.

I guess use this thread to post solutions ... I won't because mine are in MS word and that might be a bit of a security risk.

JB

Yeah, I thought it was pretty hard. I think I barely got them all =)

Number 2 was difficult. I got the answer but had trouble writing it up so I bs-ed it.

I thought number 4 was the hardest. However, even though I know my methods are correct, I'm not sure about the answers I got. In my opinion, number 3 was the best problem.

I didn't bother doing the whole thing because I couldn't get a gold medal and only needed 6 points to get silver.  I ended up doing 3 of them.

1.  This problem was really really easy.
2.  This wasn't that hard IMO.  I got 15.  However, writing this one up was HARD.  I decided to write up #3 first.  Then I went back to this one, wrote up part of it, then looked at the clock and thought "OMG THIS IS DUE IN A FEW MINUTES" and just wrote a little note saying that I got 15 but didn't have time to finish writing it up.  (Turns out, by the way, that I still had one day left.  Oh well, I have the satisfaction that I got the problem right, and it was a fun problem.)

3.  This was my favorite.  I had this messy, complicated-looking drawing that pretty much solved the problem itself.  It basically involves drawing a whole bunch of parallelograms inscribing the quadralaterals in the problem, plus two other lines.  Then use basic similarities and congruences to finish it.

5 was a lot easier than 2,3,4 to actually get the answer, but I couldn't completely prove it. I needed 14 for bronze, but I'm guessing I got around 12.

I needed 4 for bronze, 20 for silver. I doubt I got 20.

I got 1
I completely failed at 2, ugh. Maybe a 2 on that one?
I made some kind of progress on 3, I made alot of assumptions that I think are correct but I supplied without proof. so maybe a 3.
I got several recursions for 4, which added up somehow, but I got about the twice the correct answer. Not sure what I did wrong, too lazy to read other people's solutions. Hoping for a 3.
For 5, I got 1004 and proved the pattern, but I didn't prove that it was the minimum, I was just like "we can apply the greedy algorithm." hoping for a 3.

So at most 52333, making 16, total 72.

grrr

hey that would make my scores palindromic for this year: 16, 20, 20, 16

OMG, i just realized that i only got half the solution for 1, i did c = 2007, d = even, but not c = even, d = 2007, i think i just missed the silver medal

number five took me days to finish until i realized i had read the problem wrong. i thought all the x's had to be distinct.(does anyone know the solution if we require all the x's to be distinct?)

but overall it was a hard round(1 was a joke)

Overall I'd certainly call it more difficult than the other rounds.  I mean, most rounds have at least one problem you can just sit down and do.  This round had only one, and the other problems were some of the trickiest in my two years of participation.

For #2 I didn't exactly use Chinese Remainder thm, but I did turn them into 2-variable, linear Diophantine EQ's with relatively prime coefficients, then showed that the solutions differed by however much.  It's pretty much the same idea.

JB

hmmmm probably a 22 :mad:

urrrrgh

missed #2... have stuff for it though, hope I can get 2 on that

this round was hard

1 was hilarious
2... i missed it
3 was so-so
4 was interesting
5 was so-so

1. easy
2. easy, but my solution was like really long
3. interesting, but I couldn't figure out other than analytical geometry
4. took me awhile
5. I got it, but I think there might be a slight flaw in my proof.

[quote="calc rulz"]Well here are my basic solutions:

1. jokey, just find an expression for S(even) and S(odd)

2. This was cool, because I used the CHINESE REMAINDER THEOREM

I thought it was neat because it was actually a counting problem, not a find the solutions problem  :wink:

3. I had a pretty nice solution for this. I showed that for any point on line MO, two of the four quadrilaterals had area 1/4 of the entire thing. I showed that their area doesn't change as the point moves along line MO, and then I showed that they have the correct area for M, thus they do for O, and similarly with line NO, so all four quadrilaterals have the right area

And when I showed the area connecting the midpoints to M...I had a really nice homothety =D

4. Well this was pretty cool, I basically had a recursion, but I also needed a 1-1 correspondence

5. Well I guessed it, but it took me ages to prove...I ended up using a lot of strong induction and a lot of contradiction  :yup:[/quote]

Wow, my solutions were pretty much the same (though my #5 wasn't too messy).
Actually, for #4, I defined a parallel sequence of what i called "close" connections: those which are invalid but would be valid if you connected the two rightmost edges.

Wow all of my solutions are good... except for #1.  No joke.  I had the closed forms and everything, I just forgot which one was the even one and which was the odd.  Grrr... goodbye gold.

For number 4, I used a computer program, and somehow made a mistake and got $T_{11}$ instead of $T_{10}$.

DO you think the graders will recognize that at all?

I didn't really have much motivation this round.  I solved 1, 4, and 5 but never made much of an effort on 2 or 3 and didn't put anything down.  I'll probably end up with a 90 overall.

wow i just realized that i could reduce my #2 proof by about 2 pages really easily... I did all this weird stuff when I should have just factored the whole thing instead of factoring in one case. :wallbash:

Yeah and instead of having a shot at commended you only get a 5.

lol. First time doing USAMTS, only really got #1, partial solution on #4. I didn't really try very hard, did I? [/end self-examination]

[quote="K81o7"][quote="bpms"][quote="azjps"]#1 Almost panicked when I saw -1 being raised to an imaginary number … needless to say, it turned out to be a lot easier
#2 I barely had a clue about what to do with this, and ended up doing the linear diophantine thing that jackb1115 mentioned
#3 Thought this was interesting, didn’t know how to use the location of O at first
#4 I finished this problem second, didn’t think it was so bad
#5 I got 1004 and thought it was too easy to be #5, then I realized that I still had to prove it was the minimum

Hopefully I’ll get a 27 and make gold (if only I knew what I was doing in round 1)  :([/quote]
It's only out of 25 points[/quote]

That was sarcasm if you didn't notice.[/quote]
Oh, sorry, I guess I'm just slow :oops:

[quote="h_s_potter2002"][quote="ehehheehee"]If you got the recursion right then I think they would.[/quote]

Well, I used a computer program, so I'm not sure how well my description of it would show that I just made a stupid mistake when writing it, but everything else was okay.

Aaah, I should have just used the recursion I found.  But I decided it would be too hard to do, and used a computer program instead.[/quote]

I would think a recursion would have a better chance of a commended than a computer program would.

I got $14$ for #2...  :maybe:

calc rulz, how can you use the CRT?!!?

I might get silver... (Hoping for an 81, I have a 64 so far)

That's pretty bad, considering that I'm in 8th grade.

Prob #1: simple
Prob #2: I just found a pattern, and I thought it was 14.
Prob #3: simple
Prob #4: took me a while for rigorousness
Prob #5: simple, but hard to prove (even though I was able to do it)

Expecting 45532 = 19.

1. Forgot the reversed solution.

2. Horrible, almost unintelligible, but hopefully correct solution.

3. Analytical solution. :wallbash:

4. Used an equation that I didn't prove.

5. Assumed minimizing each $A_{n}$ minimizes $A_{2007}$. I hoped they wouldn't notice it, but they will.

[quote="lotrgreengrapes7926"]Expecting 45532 = 19.

5. Assumed minimizing each $A_{n}$ minimizes $A_{2007}$. I hoped they wouldn't notice it, but they will.[/quote]

This is close to being correct. I think you just have to take into account the fact that the mean can decrease for certain values. I don't think you will lose more than two points for that detail.

[quote="vishalarul"]...

calc rulz, how can you use the CRT?!!?

...[/quote]

See the solutions I posted in the other thread.

[quote="bpms"]Hah, I soooo tanked this round.
Where do you guys think questions like number 1/2/4/5 would show up on the AIME?[/quote]

#1 - Though warping it into a question with integral answers might be slightly hard (since there are an infinite # of answers), wouldn’t be surprised if a related question would pop up from #2-5
#2 - Perhaps somewhere in #12+? It’s not too bad if you have a computer sitting right in front of you…
#4 - Perhaps $T_{5}$, since calculating $4(4(4(4( \ldots 1)+1))-4(4(((( \ldots 1)+1)))-4((( \ldots 1)+1)))$ (and that’s not even the full expansion) is pretty bad by hand. I thot this was easier than question 2 tho, so maybe #10+?
#5 - Doubt this would appear, it’s more a proof question then a number question.

How hard are these questions in comparison to USAMO questions (I'm supposing that the USAMTS is easier)?

Uh, for #1 it wouldn't be that hard to make it have an integral answer.  Something like:

Let $(a_{1}, b_{a}), (a_{2}, b_{2}),...,(a_{n}, b_{n})$ be all solutions to (question #1) such that $0\leq a_{i}, b_{i}\leq 10000$ for all $i$ such that $0\leq i\leq n$.  Let $S=a_{1}+b_{1}+a_{2}+b_{2}...+a_{n}+b_{n}$.  Find the remainder when $S$ is divided by 1000.

I really doubt something as messy as #4 would show up on the AIME and if it was it would be one of the last ones that I don't worry about.

oh man that's painful

#5 is way too easily guessable, anyone could just say ok, 1 is the lowest number, what's the lowest number that works after that, 3, etc., then eventually they'd see 1, 3, 2, 6, etc., and be like HEY that's a pattern so 004

I wouldn't be surprised to see #4, in it's exact statement, as like a #12 or #13, because the calculations aren't THAT bad. If you got a simple recursion that is.

When will round 1 year 19 be released?
Hah, for number 5 I put down $2007*1004$ becuase I thought it was asking for $ \sum^{2007}_{n=1}x_{n}$ instead of $\frac{\sum^{2007}_{n=1}x_{n}}{2007}$

[quote="tjhance"]hm I accidentally used a and b for part B instead of c and d. Do you think this will be taken off for?[/quote]

no.  The USAMTS people are rational people and won't dock you for typos.

jB

I probably got 25:
1- super easy
2- I really liked my solution, I sort of proved it by induction.  I thought it was really pretty.  But the solution with the Chinese Remainder theorem would have been shorter.
3- Solved for almost every length, did some stuff with similar triangles, and ended up with a brute-force proof about 6 pages long.
4- solved using recursion, but was worried because what kind of problem has 151316 as an answer?
5- my proof may have been a little vague but hopefully it's good enough.

i tested my recursion for $T_{4}$ and $T_{5}$ to make sure it worked.

It took forever to calculate those without the recursion.

[quote="tjhance"][quote="diophantient"][hide="one liner for number 5"]Fibonacci's Lemma[/hide][/quote]

Could you please explain what that is? I couldn't find it on Mathworld.[/quote]
Never mind, it turns out that I misinterpreted the question :(


LaTeX
geometry
parallelogram
circumcircle
analytic geometry
function
IMO Shortlist

It´s a easy problem from IMO Shortlist 1996, and I wish that someone could solve with complex numbers, to confirm my solution. Thanks!

(sorry if I don´t have Latex)

Let triangle ABC have orthocenter H, and let P be a point on its circuncircle. Let E be the foot of altitude BH, let PAQB and PARC be parallelograms, and AQ meet HR in X. Prove that EXis parallel to AP.

Look Rafael, I think that if you have the technice of solving problems by complex numbers then it is rather unlakely that you found a wrong solution.
Anyway,I will post here my way with complexs.I will not enter to the detale but I hope it will be clear.

Let the circumcircle of the triangle to be a unit circle and the circumcentre to be the centere of the complex plane.

I will note the complex coordinate of a point $T$ by $t$.

So,we can easily get that $r=a+c-p$ and $q=a+b-p$.
Now,the equation of the line $AQ$ is
\[\frac{x-a}{\overline{x}-\overline{a}}=\frac{x-q}{\overline{x}-\overline{q}}\]
and the equation of the line $HR$ is
\[\frac{x-h}{\overline{x}-\overline{h}}=\frac{x-r}{\overline{x}-\overline{r}}\]
in fact $h=a+b+c$
so solving the sistem of equation we can get the complex coordinate $x$ of the point $X$ as a function of $a,b,c$.
We also know that $e=\frac{1}{2}(a+b+c-\frac{ac}{b})$
Therefore we only need to check that
\[\frac{x-e}{\overline{x}-\overline{e}}=\frac{a-p}{\overline{a}-\overline{p}}\]
 :wink:

Thank you, Tiks! :)
This was just what I need, thanks


let X={set of all bijective functions from [1,2,...n] to [1,2,..n]}
we define t{f(a)}=1 if f(f(f(f(f(f(f(f(f(f(f(f(a)))))))))))))=a {f 12 times } else 0
find summation{f belonging to X}[summation{i = 1 to n}[t{f(i)}] :D  :rotfl:   :huh:

[quote="gauravpatil"]let X={set of all bijective functions from [1,2,...n] to [1,2,..n]}
we define t{f(a)}=1 if f(f(f(f(f(f(f(f(f(f(f(f(a)))))))))))))=a else 0
find summation{f belonging to X}[summation{i = 1 to n}[t{f(i)}] :D  :rotfl:   :huh:[/quote]

Please learn to use $ LaTeX$, it makes your question readable to others and gives them enthusiasm to answer. ;)
You can use this link for the basic codes: http://www.mathlinks.ro/viewtopic.php?t=188533

@rituraj: What was the purpose of that comment? The whole world knows that IMOTC questions are very easy for you.

@Rituraj please no spamming on serious topics :)

can i get an answer please :

 :?:latex seems qute difficult to learn  :!:


ahh,...

i know this has been asked about fifty times in the forum, but it didn't want to revive old topics...

1. how do i study for them??

2. where should i take them?? (i'm in 8th grade, but i want to take AMC10 because my teachers say that i have a decent chance of gettin in AIME, but my teachers don't know where i should take the AMC10)

3. Any good or decent books to help study??

4. Are there old AMC10's on the AMC website or is there another website??

i hope i'm not overburdening you with questions, but PLEASE HELP!!!!

AND on top of that i have AMC8, which i bombed last year (prob. cuz of lack of calculator, but oh well...)

i'm really nervous.... everything depends on twenty-five math problems...

thanks!!!

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

This isn't really an old topic. Probably best to have used this one.

1. See that topic
2. Someone else will have to answer this one. Usually the answer is a local college or high school.
3. Maybe AOPS volume 1 from this site.
4. This website has past AMC 10s. Click on the Contests link above these forums, then USA, then AMC 10. For practice, I would also advise trying difficult AMC12 problems. It's always a good idea to practice with problems harder than those on the actual test.

1.
2.  Frequently Asked Question #4
3.  Contest Problem Books I-VI, availalbe at the AoPS Bookstore.

4.  Frequently Asked Question #6

See the AMC FAQ page.
http://www.unl.edu/amc/f-miscellaneous/faq.shtml

Steve Dunbar
MAA Director, American Mathematics Competitions

See the topic, "Best Way to Prepare for AMC 10."


function
limit
calculus
calculus computations

Im having trouble w/ problems that require you to find specific values such as this one:

for what value of a and b is the function f differentiable on (-infinity,infinity)

f(x)=        ax+b        if x[u]<[/u]0
               x^2+1      if x >0

if we differentiate, $f'(x)$ will not defined when $x=0$.
so all we need is to find $a$ and $b$ so that it is defined.
$f'(x)= a$ for $x < 0$  and $f'(x)=2x$ for $x>0$, now we want the continous function
\[ \lim_{x \rightarrow 0+} f'(x) = \lim_{x \rightarrow 0-} f'(x) \]
on $x=0$. $\lim_{x \rightarrow 0-} a = \lim_{x \rightarrow 0+} 2x=0$
so $a=0$.
and also $\lim_{x \rightarrow 0-} ax+b = \lim_{x \rightarrow 0+} x^2+1=1$
so $b=1$.


A plan takes off from Chicago's O'Hare Airport on runway 2 LEFT, which has a bearing of N20degreesE. After flying for 1 mile, the pilot of the plane requests permission to turn 90 degrees and head toward the northwest. The request is granted. After the plane goes 2 miles in this direction, what bearing should the control tower use to locate the plane?

ALSO: What does the word bearing mean in terms of math?

Bearing in this problem would mean direction as in north, south, etc.
[hide]Firstly, draw the flight plan. It forms a right triangle, leg lengths of 1 mile and 2 miles. Using Pythagoreans therom, the hypotenuse is $ \sqrt{5}$. Since we don't know any angle increments beside the right angle, we have to use trigonometry to find the other 2.
Supposing the angle across from the 1 mile line is $ x$, then
$ tan x=\frac{1}{2}$
$ x\approx26^{o}$

The other angle is about $ 64^{o}$, subtract the $ 20^{o}$ angle positioning from the beginning giving us co-ordinates of about [b]north 44 degrees west[/b][/hide]

[hide="Vectors EDIT Put Wrong Numbers in Calculator"]
$ \vec{w}=$Intial displacement of one mile at $ N20^{\circ}E = 70^{\circ}$.
$ \vec{z}=$Second displacement of two miles at $ W20^{\circ}N = 160^{\circ}$.
$ \vec{r}=$Resultant vector.
$ \vec{r}= \vec{w}+\vec{z}= \left( \cos 70^{\circ}+2 \cos 160^{\circ}\right) \hat{i}+\left( \sin 70^{\circ}+2 \sin 160^{\circ}\right) \hat{j}\approx-1.5373651 \hat{i}+1.62373291 \hat{j}$
The direction of $ \vec{r}$ is $ \boxed{\approx \arctan \frac{1.62373291}{-1.5373651}\approx 133.434949^{\circ}\ \text{or W}46.565051^{\circ}\text{N}}$.
[/hide]

[quote]$ \vec{r}= \vec{w}+\vec{z}= \left( \cos 70^{\circ}+2 \cos 160^{\circ}\right) \hat{i}+\left( \sin 70^{\circ}+2 \sin 160^{\circ}\right) \hat{j}\approx-1.5373651 \hat{i}+1.62373291 \hat{j}$[/quote]

The above $ \vec{z}$ is incorrect. $ (2cos 160^{\circ}, 2sin160^{\circ})$ is not at $ \vec{z}$.

Can you please explain what is incorrect?  :|

[hide="Trigonometry"]
$ \tan \theta = \frac{2}{1}\Rightarrow \theta \approx 63.4349489^{\circ}$.
$ \boxed{180^{\circ}-\left( 63.4349489+70 \right)^{\circ}= 46.5650511^{\circ}\Rightarrow W46.5650511^{\circ}N \equiv N43.434949^{\circ}W}$.
[/hide]


The first two weeks of assignments will be posted on the first day of the independent study - September 3.

That is weird - the independent study forum appeared and then disappeared under My Classes. :?

You probably just happened to look at the board between when we built the forum and set the permissions on it.


[quote="Valentin Vornicu"][quote="zmli"]Will it nice to be able to add a forum to the Favorites.  I find myself mostly work in 3-4 forums across several sections (e.g., MATHCOUNT COACHES in middle school, SDMC in Communities and Parents, etc.)  Using favorites, I can cut down significantly the number of clicks for me to get to my forums.[/quote]Have a little patience, you not the first to request this :D ...[/quote]

Well, if you have this function, it cut my clicks by at least 10.

Now, I usually check the forums three times a day, that's 30 clicks per day and >1000 clicks per year. :(
How many users you have?

A click here and a click there, you add up to a lot of clicks! ;)


trigonometry
inequalities proposed
inequalities

$a,b,c\leq \frac{\pi}{2}$, $cos^{2}a+cos^{2}b+cos^{2}c=1$
Prove that $1+cosa+cosb+cosc\geq sina+sinb+sinc$


For every n natural <>0 we denote x_n the real solution of the equation: 2^x+x=n. Compute, showing that there exists and it is finite: lim n-->oo  n(x_n/logn -1) . the base of the log is 2.

thank you!!

Using calculus (or better) some Taylor development of ln(2^x + x) :

2^x * e^(x/2^x - 1/2*x^2/((2^x)^2) <= 2^x + x <= 2^x * e^(x/2^x)

I think it's enough to prove that x_n/ln[2](n) - 1 -> 0.


Let $n\geq 2$ is positive integer. Find the best constant $C(n)$ such that \[\sum_{i=1}^{n}x_{i}\geq C(n)\sum_{1\leq j<i\leq n}(2x_{i}x_{j}+\sqrt{x_{i}x_{j}})\] is true for all real numbers $x_{i}\in(0,1),i=1,...,n$ for which $(1-x_{i})(1-x_{j})\geq\frac{1}{4},1\leq j<i \leq n.$

$C(n)=\frac{1}{n-1}$ with equality when all $x_{i}=\frac{1}{2}$
Observe that changing $x-e$,$x+e$ into $x$, $x$ doesn't change LHS while it increases RHS. Now if for all $i$: $x_{i}\leq \frac{1}{2}$, we're done (. So assume that $x_{1}=x_{2}=...=x_{n-1}\leq \frac{1}{2}\leq x_{n}$ (there is at most one number greater than $\frac{1}{2}$, because of the condition on $x_{i},x_{j}$). Using $(1-x_{n})(1-x_{1})\geq \frac{1}{4}$ we conclude that $\sum x_{i}\leq \frac{n}{2}$ and so we can assume all variables are equal because $(1-\frac{\sum x_{i}}{n})^{2}\geq \frac{1}{4}$ and hence the maximum is attained with all $x_{i}$ being equal to $\frac{1}{2}$.

Well, I don't understand why you had to go through all that. You've proved that, for a fixed value of $\sum x_{i}$, if there are still unequal terms, you can change it so that the right side gets bigger and everything still satisfies the condition. So the maximum of the right side occurs when all $x_{i}$ are equal...

Because we want $(1-x_{i})(1-x_{j})\geq \frac{1}{4}$ to hold for new variables as well and my later considerations were just to check that.

Well，I think that this prove has a few drawbacks. The adjustment is about two variables x_i and x_j.  So you need to confirm that to any i and j，(x_i+x_j)/2 <1/2. Even though you get that the sum of all x_i <n/2, you cannot do such an adjustment for x_n and x_i (consider the instance of (0.0001,0.0001,...,0.0001,1). Meanwhile, l cannot come across how you get the sum of all x_i <n/2, and with all x_i equaling to one value, assumed as x, you need to confirm that when x equals to 1/2, the maximum of C(n) occurs（while this step is easy）．


algebra
polynomial
inequalities
inequalities proposed

let $ a,b,c$be non-negative real number
prove that:
$ {\left( {\frac{a}{{b \plus{} c}}} \right)^3} \plus{} {\left( {\frac{b}{{c \plus{} a}}} \right)^3} \plus{} {\left( {\frac{c}{{a \plus{} b}}} \right)^3} \plus{} \frac{{13abc}}{{(a \plus{} b)(b \plus{} c)(c \plus{} a)}} \ge 2$
 :(

[quote="Toan_VN_LC"]let $ a,b,c$be non-negative real number
prove that:
$ {\left( {\frac {a}{{b \plus{} c}}} \right)^3} \plus{} {\left( {\frac {b}{{c \plus{} a}}} \right)^3} \plus{} {\left( {\frac {c}{{a \plus{} b}}} \right)^3} \plus{} \frac {{13abc}}{{(a \plus{} b)(b \plus{} c)(c \plus{} a)}} \ge 2$
 :([/quote]

check  $ a, b, c \equal{} 0$

so its not possible my dear

[quote="phymax"][quote="Toan_VN_LC"]let $ a,b,c$be non-negative real number
prove that:
$ {\left( {\frac {a}{{b \plus{} c}}} \right)^3} \plus{} {\left( {\frac {b}{{c \plus{} a}}} \right)^3} \plus{} {\left( {\frac {c}{{a \plus{} b}}} \right)^3} \plus{} \frac {{13abc}}{{(a \plus{} b)(b \plus{} c)(c \plus{} a)}} \ge 2$
 :([/quote]

check  $ a, b, c \equal{} 0$[/quote]
I don't think so :rotfl: $ a\equal{}b\equal{}0$ then $ a\plus{}b\equal{}0$ :rotfl:

hello, i think ist must be $ a,b,c$ positive.
Sonnhard.

[quote="Toan_VN_LC"][quote="phymax"][quote="Toan_VN_LC"]let $ a,b,c$be non-negative real number
prove that:
$ {\left( {\frac {a}{{b \plus{} c}}} \right)^3} \plus{} {\left( {\frac {b}{{c \plus{} a}}} \right)^3} \plus{} {\left( {\frac {c}{{a \plus{} b}}} \right)^3} \plus{} \frac {{13abc}}{{(a \plus{} b)(b \plus{} c)(c \plus{} a)}} \ge 2$
 :([/quote]

check  $ a, b, c \equal{} 0$[/quote]
I don't think so :rotfl: $ a \equal{} b \equal{} 0$ then $ a \plus{} b \equal{} 0$ :rotfl:[/quote]

If $ a \plus{} b \equal{} 0$, it can't because it's the denominator.

We can transform the ineq to a polynomial ineq and then we can apply ABC Method by considering two cases:
-abc=0
-(a-b)(a-c)(b-c)=0.

We have a stronger result is:
If $ a,b,c$ are nonnegative real numbers, no two of which are zero, then
$ \sum \left( \frac{a}{b\plus{}c}\right)^3 \plus{}\frac{9abc}{(a\plus{}b)(b\plus{}c)(c\plus{}a)} \ge \sum \frac{a}{b\plus{}c}.$
Using this inequality, we can reduce the original inequality to
$ \sum \frac{a}{b\plus{}c} \plus{}\frac{4abc}{(a\plus{}b)(b\plus{}c)(c\plus{}a)} \ge 2,$
which is just Schur's Inequality in fractional form. ;) :)


algebra
polynomial
Galois Theory
algebra unsolved

[quote="derezin"]Firstly, using Descartes' rule of sings, we observe that this polynomial has at most 1 positive root and any negative...[/quote]

What is Descartes' rule of sings ?
My progress :
$f'(x) = 5x^{4}+30x^{2}+20 = 5(x^{2}+3)^{2}-25 \geq 5 \cdot 9-25 > 0$
So, $f(x)$ is increasing, and since $f(0) < 0 < f(1)$, then the root must be unique and located between $0$ and $1$.

Let $p=x^{5}+10x^{3}+20x-18$. The $p$'s Galois group, $F_{20}$ as for $x^{5}-2$, is solvable; then we can compute the $p$'s roots with radicals. Here we compute only the real root.
With Maple: we use the var.-change: $x=\frac{y}{5}-\frac{10}{y}$.
Then $y^{10}-56250y^{5}-312500000=0$ and we obtain easily 2 real values for $y$; for example $y=(28125+3125\sqrt{113})^\frac{1}{5}$

[quote="RDeepMath91"]
What is Descartes' rule of sings ?
[/quote]

The number of changes in sign in a polynomial is the maximum value of number of positive roots, which can differ from only by even numbers.  :idea:


What is the sum of the two largest prime numbers less than 100?

The two largest prime numbers less than $ 100$ are $ 97$ and $ 89$.  Thus, their sum is $ 97 \plus{} 89 \equal{} \boxed{186}$.


algebra
polynomial
geometry
3D geometry
induction
complex numbers
complex analysis

Let $\alpha,\beta,\gamma$ be complex numbers such that $\alpha+\beta+\gamma={\alpha}^2+{\beta}^2+{\gamma}^2=0$.
Determine the shape of $\triangle \alpha\beta\gamma$ in a complex plane.

Equlateral, centered at the origin.

Note upon squaring that $\alpha\beta+\alpha\gamma+\beta\gamma=0.$

$\alpha,\beta,$ and $\gamma$ are roots of the polynomal

$z^3-(\alpha+\beta+\gamma)z^2+(\alpha\beta+\alpha\gamma+\beta\gamma)z -\alpha\beta\gamma=0$

This equation becomes $z^3=c.$ The three cube roots of a complex number always form an equilateral triangle centered at 0.

How about this:

$\alpha_1,\alpha_2,\dots,\alpha_k$ are complex numbers such that

$\sum_{j=1}^k\alpha_j^m=0$ for $m=1,2,\dots,k-1.$

Prove that these complex numbers lie at the vertices of a regular $k$-gon centered at the origin. (Note that the vertices don't have to be in order.)

I think I have a solution after some ugly bashing of newton's sums - is there a nicer way?

Suppose we have $ \alpha_{1},\alpha_{2}, \ldots , \alpha_{n} \in \mathbb{C} $, such that
$ \sum_{j=1}^{n} \alpha_{j}^{m} = 0 $ for $ m=1,2,\ldots,n-1 $.
Denote $ C = \sum_{j=1}^{n} \alpha_{j}^{n} $.
The key observation is that if $ p(x)\in \mathbb{C}[x] $ is a polynomial of degree less or equal
to $ n $, such that $ p(0) = 0 $, and with leading coefficient $ a $, then
$ p(\alpha_{1}) + p(\alpha_{2}) + \ldots + p(\alpha_{n}) = aC $.
Now, first of all let us prove the following:
or all $ \alpha_{i} $'s are distinct pairwise, either all of them are equal, and hence equal to
$ 0 $. Indeed, suppose that they are not distinct pairwise, and suppose that we already know
that $ k $ of them are equal one to another, so without loss of generality, we can assume that
those are $ \alpha :=\alpha_{1}=\alpha_{2}= \ldots =\alpha_{k} $ , $ 2 \leqslant k \leqslant n-1 $.
Denote $ q(x) = x\prod_{j=k+1}^{n} (x- \alpha_{j}) $. Then degree of $ q(x) $ is less that $ n $,
so $ \sum_{j=1}^{n} q(\alpha_{j}) = 0 $, but clearly $ q(\alpha_{1}) = q(\alpha_{2}) = \ldots =
q(\alpha_{k}) = q(\alpha) $, and $ q(\alpha_{j}) = 0 $ for $ j = k+1, \ldots ,n $. So
$ q(\alpha) = 0 $, so there exists $ \alpha_{j} $ for some $ k+1 \leqslant j \leqslant n $,
which is equal to $ \alpha :=\alpha_{1}=\alpha_{2}= \ldots =\alpha_{k} $. So, by induction we get
that all $ \alpha_{j} $ are equal, and hence are equal to $ 0 $.
Now suppose that they are all distinct pairwise.
Define a polynomial $ p_{i}(x) = x \prod_{j \neq i} (x - \alpha_{j}) $. Then it has a leading
coefficient equal to $ 1 $, so $ \sum_{j=1}^{n} p_{i}(\alpha_{j}) = C $.
But clearly $ p_{i}(\alpha_{j}) = 0 $ when $ j \neq i $, so we get that
$ p_{i}(\alpha_{i}) = C $. Now if we define $ p(x) = \prod_{i=1}^{n} (x-\alpha_{i}) $,
and $ r(x) = xp'(x) $, then we see that $ p_{i}(\alpha_{i}) = r(\alpha_{i}) $ so
$ r(\alpha_{i}) = C $ for every $ 1 \leqslant i \leqslant n $. So we get that
the polynomial $ r(x) - C $ has as roots all roots of the polynomial $ p(x) $, and
with degree equal to $ n $, which is the degree of $ p(x) $, and with leading coefficient
equal to $ n $. Therefore $ r(x) - C \equiv np(x)$, so we get that $ p(x) $ satisfies
$ xp'(x) - C = np(x) $. From now the solution is simple. Indeed, if we have
$ p(x) = x^{n} + a_{n-1}x^{n-1} + \ldots + a_{1}x + a_{0} $ then
$ xp'(x) = nx^{n} + (n-1)a_{n-1}x^{n-1} + \ldots + a_{1}x $, and comparing both sides
in the equation $ xp'(x) - C = np(x) $ , we get that $ a_{n-1} = a_{n-2} = \ldots = a_{1} = 0 $,
so $ p(x) = x^{n} + a_{0} $, and we are done.


how many ways can $13 be made using only quarters and/or dimes? they always ask these questions and it always takes me a while to solve em. is there a really quick and accurate way of doin these?
thanks

Well, before you do anything, think this:

What if I have 1 quarter?  How many dimes do I have?

For 1 quarter, you have $12.75 in dimes, which is impossible.  You have to have an even number of quarters.
That said, you can have 0 quarters, 2 quarters, 4 quarters, ... all the way up through the whole $13 in quarters (that's 52 quarters).

Then, to find the number of terms in this sequence (0,2,4,...52), do:
52-0=52 (this is the difference between least and most)
52/2 = 26 (you have to divide by 2 because it's only every other term)
26 + 1 = 27 (because you forgot to count either the 0 or the 52)

So there are 27 ways.

Here's another problem.  I want you to try it using the "shortcut" explained above.

How many combinations are possible using pennies and quarters to make $10.00?

Hint below:

[hide]Forget the pennies.  They will just make up the remainder.  Focus on how many quarters you could have, i.e. 0,1,2,...[/hide]

And then to make things quite a bit harder.. how many ways to make up that $10.00 with pennies, quarters AND dimes (to use american money words..)

I make the answer [hide]2040[/hide], by the way. I wonder if theres any more general method if you have more types of coins? I doubt it.. but you never know...

The standard way to do this is with generating functions. Suppose you want to find out how many ways you can make $14.77 with pennies, dimes, and quarters. You consider the following product:

(x + x^2 + x^3 ... ) * (x^10+x^20+x^30 + ...) * (x^25 + x^50 + x^75 +  ...).

The answer you want is the coefficient of x^1477. And ordinary manipulation of polynomial sums suffices to find the answer: 4263.

Here's a tricky question: suppose you want to make change for K cents live on an island where the coins come in 1, 2, 3, 5, 8, ... more Fibonnaci numbers up the greatest one less than or equal to K. Find an asymptoptic expression for the number of ways you can make change for large K.


inequalities
geometry
inradius
circumcircle
trigonometry
geometry unsolved

Given are $\triangle ABC$ inradius $r$ and circumradius $R$ with any $M$ on plane prove that
$\sin\frac{A}{2}MA+\sin\frac{B}{2}MB+\sin\frac{C}{2}MC\ge \frac{6r^{2}}{R}$


By AM-GM:

\begin{eqnarray*}x_k(x_1 + \ldots + x_{k - 1} + x_{k + 1} + \ldots + x_n) = x_k(2 - x_k)\leq \frac {\left(x_k + \left(2 - x_k\right)\right)^2}4 = 1\end{eqnarray*}

I am very sorry for wasting your time, iptgut. Please read here and check again my new proof, thank you very much: http://www.mathlinks.ro/viewtopic.php?p=1485596#1485596


:rotfl:

When did this happen? And I think the answer is no, unless you wrote on the back with like sharpie or pen.

I think you will be fine.  You can write on your scantron on the front, as long as you don't do it near the bubbles.  So the back should be fine too.  I would say don't worry about it; it should be fine, and if not, there's nothing we can do.

In fact, I remember writing a history essay on the back of a Scantron one year when I had no paper!  So I'm 99.999 percent sure you'll be fine.

In Spanish class, we sometimes have tests that have a multiple choice and vocabulary section (the vocabulary section involves translating words back and forth between English and Spanish).

On the tests, we get a scantron, and on the front we do the multiple choice, on the back we do the free response and write the honor pledge. 80 or so students do this each time we have a test, and there has yet to be any problems.

So, I think you should be fine.

[quote="calc rulz"]Nope, if you're talking about the MAML Olympiad, our math department leader told us all about the new scantron answer sheets, and it's fine.[/quote]

No, it was the AMC 8, but whatever.

[quote="indianamath"]one time, this kid in my class took his midterm all in pen on a Scantron!!!! :rotfl:  :rotfl: Don't feel bad because there are always people worse off than you.[/quote]

This should make us not feel bad?

[quote="13375P34K43V312"]Will my scantrom register if I accidentally wrote a bunch of stuff on the back? I erased it, but it's still visible.  :huh:[/quote]
Actually, they make scantrons with 200 answer places; 100 on the front, 100 on the back. The ones on front and back both work fine.

[quote="funcia"][quote="Karth"][quote="MysticTerminator"]dude this reminds me of a funny story

so it turns out I did my ap french language exam with like a 2 and a HALF type pencil

I was pretty pissed when I realized

I was all like

dude who even makes 2 and a HALF type pencils

wtf

but then I scored pretty ok

so I was like huh ok

that's cool[/quote]

Heheh... what a coincidence...  :lol:

Except it wasn't AP French.. it was AP World.[/quote]
umm JW i just did my IOWA test and didn't check my pencils(they were free ones i got at the library that say over the hedge all over) i guess i should get it hand scored right?
*cough cough* who does make 2 1/2 pencils?[/quote]

Well, I used my drawing pencil, so apparently companies such as Crayola, RoseArt, etc. do...  :wink:

ok i will never use art pencils  :lol:
yeah i'm still going to get hand scoring because i can't fully erase some marks i mad aww 25 dollars  :o


function
geometry
advanced fields
advanced fields unsolved

Construct a sequence of continuous function f_n on [0,1] so that 0<=f_n<=1 and such that  lim int_0^1(lower and upper limits of the integral)f_n(x)dx=0 as n--->infty, but such that {f_n(x)} converges for no x in [0,1]

Informally, use functions whose graphs are a triangle (moving back and forth along the $x$-axis as $n \rightarrow +\infty$ and with area tending to $0$, but whose height is constant).


[quote="Albanian Eagle"]how do you prove 1) with AM-GM  zhaobin ?[/quote]

for example
$\frac{a^{3}}{cd}+c+d \ge 3a$
then sum up.

Do the same for n variables


AoPSwiki
LaTeX
modular arithmetic
number theory
greatest common divisor
algorithm
relatively prime

Let  be an integer such that $ \frac{1}{1}\plus{}\frac{1}{2}\plus{}\frac{1}{3}\plus{}\cdots\plus{}\frac{1}{23}\equal{}\frac{a}{23!}$. Find the remainder when  is divided by .

...There wasn't a solution on the Wiki, and I'm not sure I understand Wilson's Theorem. Also, why is this true? :
$ ab\equiv1mod p$ for relatively prime integers a and p?

Fixed question (some $ \text{\LaTeX}$ formulas were missing):

Let $ a$ be an integer such that $ \frac {1}{1} + \frac {1}{2} + \frac {1}{3} + \ldots + \frac {1}{23} = \frac {a}{23!}$. Find the remainder when $ a$ is divided by $ 13$.

[quote="erdogankerem123"]Let $ a$ be an integer such that $ \frac {1}{1} + \frac {1}{2} + \frac {1}{3} + \cdots + \frac {1}{23} = \frac {a}{23!}$. Find the remainder when $ a$ is divided by $ 13$.
[/quote]

Multiplying through by $ 23!$, we find that all of the terms on the left-hand side are divisible by $ 13$ except $ \frac {23!}{13} = 12! \times (14 \cdot 15 \cdots 23)$. Thus,
\begin{align*}a & \equiv [12!] \cdot [14 \cdot 15 \cdots 23] \equiv [ - 1] \times [1 \cdot 2 \cdot 3 \cdots 10] \\
& \equiv - \frac {12!}{12 \cdot 11} \equiv \frac {1}{ - 1 \cdot - 2} \equiv \frac {1}{2} \equiv \boxed{7} \pmod{13}\end{align*}
[quote="erdogankerem123"]
...There wasn't a solution on the Wiki, and I'm not sure I understand Wilson's Theorem. Also, why is this true? :
$ ab\equiv1mod p$ for relatively prime integers a and p?[/quote]

It is not; the correct statement is, there exists $ b$ such that $ ab \equiv 1 \pmod{p}$ for relatively prime $ a$ and $ p$. Rewrite this condition as $ ab + cp = 1$ for $ \text{gcd}(a,p) = 1$, which has solutions for $ b$ as given by the [[Euclidean algorithm]].

Edit:case-sensitive

Thanks for the solutions (and the corrections to the problem  :blush: )!

... and what happened to the Euclidean Algorithm page on AopsWiki; It says it's blank?!

It's a capitalization problem: [url=http://www.mathlinks.ro/Wiki/index.php/Euclidean%20algorithm]Euclidean algorithm[/url].


This is the first of a series of attempts I have planned to revive the old Games and Fun Factory spirit.

This is the link to the original Never Ending Story:
[url]http://www.mathlinks.ro/Forum/viewtopic.php?t=34951[/url]

Do NOT bump it up. I am repeating the rules.

[u]Rules:[/u]
Each person posts five to twenty five words.
No one posts twice in a row.
The story MUST be G-rated.

Okay have fun! Make it a wonderful story!

One day, in the lush forests of the Free Land of Geniusses, a gewno was whirling about. It was trying to find somebody who knew...

... how to use a toothpick, as the packet he had recently got as a gift had no "Instructions" label. However, none of the Geniusses seemed to ...

...KNOW HOW IT WORKED. SO THEY WERE CONFUSED. SO THEY THOUGHT IT WAS

the end

BUT HOWEVER...

... the puzzled gewno tried using it to scratch its back. Now, you have to know, a gewno's skin is very...

...thick and the itching sensation under the thick outer skin was not relieved.  Something else was needed...

So the gewno decided to go find that person who wore a blue shirt. However that person lived far far away in another dimension(2D).

so it stopped by at pizza hut

it ordered a pepporoni pizza, but when he recieved the pizza, a huge fat

Walrus snuck up from behind and mugged him, stealing his pizza and all of his money

It was only then that he noticed the Walrus wore a blue shirt, but it was too late by then. The walrus ambled along and met a carpenter at the next crossing ...

... who gave him a choice to either eat the pizza with a toothpick or...

... or eat a toothpick with the pizza. He fell into musings, and ...

... finally came up with the excuse that he had a toothache. The carpenter, being a carpenter, could not help him, but instead...

... offered to make him a wooden tooth, which was refused with thanks, much to the disappointment of the carpenter. So he ...

committing suicide! Of course we all know that the next victim will be...

a little girl hosting a tea party! the tea splashes and then...

everybody dies
except for the pokemon
and the tea
the tea take over the world and make the pokemon their slaves

ash ketchup suddenly realizes that his pokemon r rong and he fixes the problem...

[quote="daermon"]consume vast amounts of cheese without blowing up.  unfortunately, many tried to imitate this pikachu and ended up...[/quote]

That was me.  :D

Then, a strange person wearing a mask comes and asks...

where did all the cheese go?  then cheeseisgood answered, "...

"I ate it."  Suddenly, the man took off his mask, and revealed that he was the owner of a cheese factory, and gave all his cheese to CheeseIsGood.  Suddenly,...

All cheese disintegrated, all pokemon disintegrated, all digimon disintegrated, and all non-reality disintegrated. I milked a cow, and made cheese. But suddenly,

All people,animals and flutes of the universe, the pseudo-one, were transformed in orange juice

the MC Donalds

turned all the orange juice into an unspeakably disgusting goo, which they drank till they became ...

yes, they become, very much!

since, one day, when i've been loving you, a big orange juice come to the sky

with everybody dead!!

sundely monday, i wake up in my bed without one hand


inequalities
function
induction
integration
calculus
limit
inequalities theorems

[b]The generalisation of Jensen inequality[/b]
Let $t$ be a nonzero real number and $f$ be a function defined on the finite interval $I \subset R^{+}$ satisfying $f(x)>0$ for any $x\in I$ (for $t>0$ the interval $I$ and the set of values of $f$ can contain zero as element). We will name function $f$ [i] $t$-convex [/i] if for any $x,y\in I$ and $p,q\geq 0$, $p+q=1$:
\[ f(\sqrt[t]{px^{t}+qy^{t}})\leq\sqrt[t]{pf(x)^{t}+qf(y)^{t}}  \] and [i] $t$-concave [/i] if
\[ f(\sqrt[t]{px^{t}+qy^{t}})\geq\sqrt[t]{pf(x)^{t}+qf(y)^{t}}.  \]
[b]Lemma[/b]
[i] Let $p_{1},...,p_{n}$, $\sum_{i=1}^{n}p_{i}=1$ be $n\geq 2$ nonnegative reals and $x_{1},...,x_{n}\in I$. Then if $f$ is  $t$-convex,
\[ f(\sqrt[t]{\sum_{i=1}^{n}p_{i}x_{i}^{t}})\leq\sqrt[t]{\sum_{i=1}^{n}p_{i}f(x_{i})^{t}}  \] and if $f$ is $t$-concave,
\[ f(\sqrt[t]{\sum_{i=1}^{n}p_{i}x_{i}^{t}})\geq\sqrt[t]{\sum_{i=1}^{n}p_{i}f(x_{i})^{t}}.  \][/i]
[b]Proof[/b]
We will prove the lemma only for a $t$-convex function $f$; the proof in the second case is analogous.
We will use induction on $n$.
Case $n=2$ is obvious - it's just the definition of a $t$-convex function. Let's assume that the lemma works for $n$ numbers $p_{i}$ and $x_{i}$. Let $x_{1},...,x_{n+1}$ and $p_{1},...,p_{n+1}$ be reals satisfying: $x_{1},...,x_{n+1}\in I$, $p_{1},...,p_{n+1}\geq 0$ and $\sum_{i=1}^{n+1}p_{i}=1$. For $p_{n+1}=1$ we have $p_{1}=...=p_{n}=0$ and the inequality holds. Let's assume that $p_{n+1}>0$. Then we have:
\[ f(\sqrt[t]{\sum_{i=1}^{n+1}p_{i}x_{i}^{t}})=f(\sqrt[t]{(1-p_{n+1})(\sqrt[t]{\sum_{i=1}^{n}\frac{p_{i}}{1-p_{n+1}}x_{i}^{t}})^{t}+p_{n+1}x_{n+1}^{t}})\leq  \]
\[ \leq \sqrt[t]{(1-p_{n+1})f(\sqrt[t]{\sum_{i=1}^{n}\frac{p_{i}}{1-p_{n+1}}x_{i}^{t}})^{t}+p_{n+1}f(x_{n+1})^{t}}.  \]
Let's consider two functions $x\mapsto x^{t}$ and $x\mapsto\sqrt[t]{(1-p_{n+1})x+p_{n+1}f(x_{n+1})^{t}}$. For $t>0$ they are both ascending and for $t<0$ they are both descending, so in both cases their superposition is ascending which means that the function $x\mapsto\sqrt[t]{(1-p_{n+1})x^{t}+p_{n+1}f(x_{n+1})^{t}}$ is ascending.
From the assumption
\[ f(\sqrt[t]{\sum_{i=1}^{n}\frac{p_{i}}{1-p_{n+1}}x_{i}^{t}})\leq \sqrt[t]{\sum_{i=1}^{n}\frac{p_{i}}{1-p_{n+1}}f(x_{i})^{t}},  \] so
\[ \sqrt[t]{(1-p_{n+1})f(\sqrt[t]{\sum_{i=1}^{n}\frac{p_{i}}{1-p_{n+1}}x_{i}^{t}})^{t}+p_{n+1}f(x_{n+1})^{t}}\leq  \]\[ \leq\sqrt[t]{(1-p_{n+1}) \sum_{i=1}^{n}\frac{p_{i}}{1-p_{n+1}}f(x_{i})^{t} +p_{n+1}f(x_{n+1})^{t}}=  \]\[ =\sqrt[t]{\sum_{i=1}^{n+1}p_{i}f(x_{i})^{t}}.  \]
Finally we got
\[ f(\sqrt[t]{\sum_{i=1}^{n}p_{i}x_{i}^{t}})\leq\sqrt[t]{\sum_{i=1}^{n}p_{i}f(x_{i})^{t}}  \] wich ends the proof.
[b]Theorem[/b]
[i] Let $p$ be a function defined on the interval $I$ and satisfying $p(x)\geq 0$ for any $x\in I$ and $\int\limits_{I}p(x)dx=1$ (all integrals are evaluated on the interval $I$). Then if function $f$ defined above is continuous on $I$ and $t$-convex,
\[ f(\sqrt[t]{\int p(x)x^{t}dx})\leq\sqrt[t]{\int p(x)f(x)^{t}dx}  \]
and if $f$ is $t$-concave,
\[ f(\sqrt[t]{\int p(x)x^{t}dx})\geq\sqrt[t]{\int p(x)f(x)^{t}dx}.  \][/i]
[b]Proof[/b]
As in the lemma, we will prove the theorem only for a $t$-convex function; the proof in the second case is analogous.
Let $a$ be the lower bound of $I$ and $b$ be the upper bound of this interval. Let's mark $a+(b-a)\cdot\frac{i}{n}=x_{i,n}$. Then we can rewrite the inequality from the definition of the integal:
\[ f(\sqrt[t]{\lim_{n\to\infty}\sum_{i=0}^{n}\frac{1}{n}\cdot p(x_{i,n})x_{i,n}^{t}}) \leq \sqrt[t]{\lim_{n\to\infty}\sum_{i=0}^{n}\frac{1}{n}\cdot p(x_{i,n})f(x_{i,n})^{t}}.  \]
From the condition $\int p(x)dx=1$ we get $\lim_{n\to\infty}\sum_{i=0}^{n}\frac{1}{n}\cdot p(x_{i,n})=1$, so the inequality is equivalent to
\[ f(\sqrt[t]{\frac{\lim_{n\to\infty}\sum_{i=0}^{n}\frac{1}{n}\cdot p(x_{i,n})x_{i,n}^{t}}{\lim_{n\to\infty}\sum_{j=0}^{n}\frac{1}{n}\cdot p(x_{j,n})}}) \leq \sqrt[t]{\frac{\lim_{n\to\infty}\sum_{i=0}^{n}\frac{1}{n}\cdot p(x_{i,n})f(x_{i,n})^{t}}{\lim_{n\to\infty}\sum_{j=0}^{n}\frac{1}{n}\cdot p(x_{j,n})}}.  \]
Functions $x\mapsto f(x)$ and $x\mapsto\sqrt[t]{x}$ are continuous, so we can extract signs of limit:
\[ \lim_{n\to\infty}f(\sqrt[t]{\frac{\sum_{i=0}^{n}\cdot p(x_{i,n})x_{i,n}^{t}}{\sum_{j=0}^{n}\cdot p(x_{j,n})}}) \leq \lim_{n\to\infty} \sqrt[t]{\frac{\sum_{i=0}^{n}\cdot p(x_{i,n})f(x_{i,n})^{t}}{\sum_{j=0}^{n}\cdot p(x_{j,n})}}.  \]
We only have to prove that expressions under limits are in relation $\leq$. Let's mark $q_{i,n}=\frac{p(x_{i,n})}{\sum_{j=0}^{n}p(x_{j,n})}$, of course $\sum_{i=0}^{n}q_{i,n}=1$. Then the inequality simplifies to:
\[ f(\sqrt[t]{\sum_{i=0}^{n}q_{i,n}x_{i,n}^{t}})\leq \sqrt[t]{\sum_{i=0}^{n}q_{i,n}f(x_{i,n})^{t}}  \] wich is true by lemma which ends the proof.

It's just normal Jensen for function $g(x)=f^t(x^{\frac{1}{t}})$ -  substitute $x^t=a$, and $y^t=b$ and then your condition for $t-convex$ rewrites as:

$g(pa+qb) \leq pg(a)+qg(b)$ what is just a common definition of convexity


Let $ a_1, a_2, ... a_n$ be $ n$ positive numbers greater than $ 1$.Define $ A \equal{} 1 \plus{} a_1 \plus{} a_2 \plus{} .. a_n$. Prove that:
\[ 1 \plus{} \frac {1}{a_1a_2 \plus{} 1} \plus{} \frac {1}{a_2a_3 \plus{} 1} \plus{} ... \plus{} \frac{1}{a_{n \minus{} 1}a_n \plus{} 1}\ge \frac {n^2A}{n^2 \plus{} A^2}\]

may be a good idea to begin :  let  $ a_i \equal{} \frac {x_i}{d}$   where : $ d\leq min(x_i)$  :maybe:


modular arithmetic
Diophantine equation
number theory proposed
number theory

We consider the proposition $ p(n): n^2\plus{}1$  divides $ n!$ , for positive integers . Prove that there are infinite values of $ n$ for which $ p(n)$ is true, and infinite values of $ n$ for which $ p(n)$ is false.

False part follows directly after http://www.mathlinks.ro/Forum/viewtopic.php?p=1190546#1190546
For true part, consider Pell Equation $ 5x^2\minus{}n^2\equal{}1$, obviously this type of equations have infinitely many solutions. On the other hand, we see that n is at least 2x, so for x larger than 5 the corresponding n works.

second part:
If $ p\equiv1\pmod 4$ by Wilson if $ n \equal{} (\frac {p \minus{} 1}{2})!$ then $ n^2\equiv \minus{} 1\pmod p$, and $ p > n$
first part: $ n^2 \plus{} 1 \equal{} (2a^2 \plus{} 2a \plus{} 1)(2a^2 \minus{} 2a \plus{} 1)$, $ MCD(2a^2 \plus{} 2a \plus{} 1 ; 2a^2 \minus{} 2a \plus{} 1) \equal{} 1$ and $ 2a^2 \minus{} 2a \plus{} 1 < (2a^2)!$ and $ 2a^2 \plus{} 2a \plus{} 1\mid(2a^2)!$ if $ a \equal{} 25\beta \plus{} 1$


Solve:

sin x = 6n

(hint: trick question)

Trig should not be in classroom forum. Sorry  :(  but that's the rule  :D

sin x = 6n

Divide both sides by n

six = 6

So, all real values of n.

Haha  :oops: I was tricked...

Good one, but someone should move it!
 :rotfl:

i think i have seen that somewhere before....

It's in the puzzles and brainteasers math jokes thread. Here's a link: [url]http://www.artofproblemsolving.com/Forum/viewtopic.php?t=74007[/url]

I heard it as sin x / n.
I also heard this:

1 / (1 - (sin c)^2)^0.5 ;)

[quote="furious"]i've seen that as a limit problem:
limit of sin(x) / n as n :arrow: infinity
(but the n :arrow: infinity really doesn't mean anything)[/quote]
Hmm that would be 6n/n, L'Hospital rule for indeterminate form infty/infty.

What n tends to is immaterial.
Just see that n is not zero.


quadratics
LaTeX
algebra
quadratic formula
polynomial
sum of roots

what is the discriminant?

something to do with the quadratic formula...

in the quadratic formula it is $ b^2 \minus{} 4ac$
it tells you if the # of real solutions is 0, 1, or 2
it also can tell you if you have rational solutions or irrational

the reasoning behind this lies in the original quadratic formula... *yeesh here comes LaTeX challenge*
$ \frac { \minus{} b\pm\sqrt {b^2 \minus{} 4ac}}{2a}$*YAY!*
ok so the $ b^2 \minus{} 4ac$ is under a square root so if the discriminant is negative, the simplified value of the radicand is complex and the whole solutions are complex
is it is 0, the simplified value of the radicand will be 0 and the $ \pm 0$ will mean nothing and therefore the solution is $ \minus{} \frac {b}{2a}$
if it is positive, the simplified value of the radicand will be real and positive and therefore the $ \pm$ will give 2 solutions
is the discriminant is the square of a real number, the simplified value of the radicand will be real and rational and positive and there fore the solutions will be rational
note that in the preceding, it was assumed that all coefficients are real and rational

if a coefficient is rational, then by definition it is also real :wink:

its $ b^2\minus{}4ac$ and it helps a lot!! If you have a graphing calculator I suggest you make a discriminant program.

Also if $ b^2 \minus{} 4ac \equal{} 0$ then the quadratic equation can be factored into $ (x \minus{} y)^2$ where $ y \equal{} \frac {b}{2}$

Edit: OF ALL PEOPLE TO CORRECT ME...

[quote="hunter34"]Also if $ b^2 \minus{} 4ac \equal{} 0$ then the quadratic equation can be factored into $ (x \minus{} y)$ where $ y \equal{} \frac {b}{2}$[/quote]
Don't you mean $ (x\minus{}y)^{2}$?

yes, he probably does mean that

also, as a note, in quadratic equations with rational coefficients, there can never be exactly one real root.  Why?  If this was the case, then the equation factors into the form $ (x\minus{}r)(x\minus{}z)$ for some real number $ r$ and complex number $ z$.  The sum of the roots is $ r\plus{}z$, which will be a complex number, but this is the negative of the coefficient of the linear term, and thus the coefficients aren't rational.

that might have been too complicated for classroom math

Eh, I got it after I read the whole thing, but when I read the first sentence I was just like.
"No real roots for all quadratics with rational coefficients? Alan's lost his mind!"

wait, how come when you have the quadratic equation :
$ x^2\minus{}4x\plus{}4\equal{}0$
the sum of the roots is supposed to be 4, does it count two twice or something?

[quote="TheHeinrich"][quote="ZhangPeijin"][quote="hunter34"]Also if $ b^2 \minus{} 4ac \equal{} 0$ then the quadratic equation can be factored into $ (x \minus{} y)$ where $ y \equal{} \frac {b}{2}$[/quote]
Don't you mean $ (x \minus{} y)^{2}$?[/quote]

this is the case when a=1,[/quote]
When a is not one $ x$ is simply not the $ x$ in the quadratic.

If $ b^2\minus{}4ac\equal{}0$, then the quadratic is factored into the form $ (\sqrt{a}x\pm\sqrt{c})^2$, depending on the coefficient of $ x$.

@ZhangPeijin - um, what?

[quote="levans"]Hmmm, good question.  I guess the sum of roots formula doesn't really work if the discriminant is zero.[/quote]
[quote="alanchou"]this assumes multiple roots are counted seperately[/quote]
Multiplicity of the roots ;)

For example, $ x^2\minus{}6x\plus{}9\equal{}0$ has double root $ x\equal{}3$ with discriminant zero. The sum of roots is $ 3\plus{}3\equal{}6$, as expected.

[quote="Nerd_of_the_Ages"]Also, if the discriminant is a perfect square, then the problem is factorable.[/quote]

I believe you meant to say "factorable into terms involving only rational numbers," no?


modular arithmetic
induction
number theory
relatively prime
algebra
binomial theorem
number theory unsolved

Prove that there exists infinite composite numbers $ n$ such that $ n|3^{n\minus{}1}\minus{}2^{n\minus{}1}$.

[quote="The QuattoMaster 6000"]I am not quite sure if this is allowable on a competition, but we could always consider the Carmichael Numbers.[/quote]

A Carmichael number $ n$ satisfies $ a^{n \minus{} 1} \equiv 1 \pmod{n}$ for all $ a$ that are relatively prime to $ n$. It doesn't satisfy that for all $ a$, and in particular it may not satisfy this for $ a \equal{} 2$ or $ a \equal{} 3$. For instance, the first Carmichael number $ 561 \equal{} 3 \times 11 \times 17$ fails the condition of the problem. Therefore, just citing the theorem on infinitely many Carmichael numbers is not enough even assuming that such a recent, difficult result would be acceptable in competition. You would have to assume there are infinitely many Carmichael number relatively prime to 6, and I've no idea if this is true.

Of course, you need much less than actual Carmichael-ness for this problem.

I think randomgraph is right. The $ 2^{nd}$ Carmichael number, which is $ 41041$ does not satisfy the conditon either. It seems to be a hard problem :maybe:

@The QuattoMaster 6000: In my school, difficult results are not acceptable in competitions.

Not that hard, actually  :roll:  I think you put yourself in a tough position when you decided to look at the problem from the point of view of pseudoprimes. It's true that if $ n$ is a pseudoprime for the bases $ 2$ and $ 3$ then $ n$ satisfies the requirement, but this is an overkill, and would be very hard to prove.

Let $ k \geq 2$ be an integer, and let $ n = 3^{2^k}-2^{2^k}$.

1. $ n$ is not prime: Since $ 4 | 2^k$ we have $ 3^{2^k} \equiv 2^{2^k} \equiv 1 \pmod{5}$ so $ 5|n$ and $ n>5$.

2. $ n \equiv 1 \pmod{2^k}$: Obviously $ 2^{2^k} \equiv 0 \pmod{2^k}$, so we need to verify that $ 3^{2^k} \equiv 1 \pmod {2^k}$. This is easy to see using the binomial theorem, but it's even easier via induction on $ k$: let $ a_k = 3^{2^k}$, then $ a_1 \equiv 1 \pmod{2}$. Assuming $ a_k = 1 + m2^k$, we have ${ a_{k+1} = a_k^2 = (1+m2^k)^2 = 1+2m2^k+2^{2k} \equiv 1 \pmod{2^{k+1}}}$.

3. It follows that $ n = N2^k + 1$ for some natural number $ N$. Thus

$ Z = 3^{n-1}-2^{n-1} = 3^{N2^k} - 2^{N2^k} = (3^{2^k})^N - (2^{2^k})^N$.

So, if we let $ x=3^{2^k}$ and $ y=2^{2^k}$ we see that $ Z = x^N-y^N$ which is divisible by $ x-y$, and $ x-y$ is exactly $ n$, so $ n | 3^{n-1}-2^{n-1}$ as desired.

[quote="randomgraph"]Not that hard, actually  :roll:  I think you put yourself in a tough position when you decided to look at the problem from the point of view of pseudoprimes. It's true that if $ n$ is a pseudoprime for the bases $ 2$ and $ 3$ then $ n$ satisfies the requirement, but this is an overkill, and would be very hard to prove.

Let $ k \geq 2$ be an integer, and let $ n = 3^{2^k} - 2^{2^k}$.

1. $ n$ is not prime: Since $ 4 | 2^k$ we have $ 3^{2^k} \equiv 2^{2^k} \equiv 1 \pmod{5}$ so $ 5|n$ and $ n > 5$.

2. $ n \equiv 1 \pmod{2^k}$: Obviously $ 2^{2^k} \equiv 0 \pmod{2^k}$, so we need to verify that $ 3^{2^k} \equiv 1 \pmod {2^k}$. This is easy to see using the binomial theorem, but it's even easier via induction on $ k$: let $ a_k = 3^{2^k}$, then $ a_1 \equiv 1 \pmod{2}$. Assuming $ a_k = 1 + m2^k$, we have ${ a_{k + 1} = a_k^2 = (1 + m2^k)^2 = 1 + 2m2^k + 2^{2k} \equiv 1 \pmod{2^{k + 1}}}$.

3. It follows that $ n = N2^k + 1$ for some natural number $ N$. Thus

$ Z = 3^{n - 1} - 2^{n - 1} = 3^{N2^k} - 2^{N2^k} = (3^{2^k})^N - (2^{2^k})^N$.

So, if we let $ x = 3^{2^k}$ and $ y = 2^{2^k}$ we see that $ Z = x^N - y^N$ which is divisible by $ x - y$, and $ x - y$ is exactly $ n$, so $ n | 3^{n - 1} - 2^{n - 1}$ as desired.[/quote]

I think yours is an amazing solution. Could you explain how can you think of $ n=3^{2^k}-2^{2^k}$???

Of course - sorry, I didn't mean for this to look like magic. First, I had a clue by using a computer to find some examples. The first solution is $ n \equal{} 65$ so I tried to investigate what makes it work. It is divisible by $ 5$ and $ 13$. The $ 5$ is easy to understand: both $ 2$ and $ 3$ are generators mod $ 5$, and luckily $ 65 \minus{} 1$ is divisible by $ \varphi(5) \equal{} 4$.

The $ 13$ is more mysterious: $ 3$ happens to have very low order mod $ 13$, since $ 3^3 \equiv 1 \pmod{13}$. Fortunately, $ 2^4$ just happens to be $ 3 \equal{} 3^4 \equal{} 3^1$ mod $ 13$. This is the "miracle" that makes this problem much easier than dealing with pseudoprimes. But how can I make sure this miracle occurs? Well, if you want to have $ 3^m \equiv 2^m \pmod{p}$, you just need to make sure $ p$ is a divisor of $ 3^m \minus{} 2^m$. This is where I noticed that $ 65 \equal{} 3^4 \minus{} 2^4$. My original plan was to look for divisors of the form $ 5p$ of such numbers, but then I realized it'll be simpler to just take $ n$ itself to be $ 3^m \minus{} 2^m$.

A few more numerical checks revealed that not just any $ m$ works. This isn't surprising: If $ m$ does not divide $ n \minus{} 1$, there's very little you can say about $ 3^{n \minus{} 1}$ where all you have is something about $ 3^m$. So I wanted to make $ n \minus{} 1$ a multiple of $ m$. It's easiest to control the residue of $ n$ mod $ m$ when one of $ 3^m$ or $ 2^m$ is just $ 0$, so I gambled on $ m \equal{} 2^k$, and it worked  :)

BTW, Mashimaru: can you mention the source of this problem?

Sorry to everyone for my carelessness on Carmichael numbers.  I don't know what I was thinking  :(

This problem was, in fact, a PEN problem:
http://www.artofproblemsolving.com/Forum/viewtopic.php?p=849273#849273


let $f$ be a real-valued function defined on I=$(0,\infty)$ and having no zeros on I.suppose that $\lim_{x\to+\infty}\frac{f'(x)}{f(x)}=+\infty$. for the sequence $u_{n}=\ln|\frac{f(n+1)}{f(n)}|$,prove that $\lim_{n\to\infty}u_{n}=+\infty$.
thanks.


inequalities
trigonometry
inequalities proposed

Easy.
Use General ineq ,we have:
[tex]L.H.S\leq\sqrt{(\sum sinAsinB)(\sum cosA)}\leq\sqrt{(\sum sinA^2)(\sum cosA)}\leq\sqrt{\frac{9}{4}.\frac{3}{2}}=\frac{3\sqrt{6}}{4}[/tex]

[quote="keira_khtn"]Easy.
Use General ineq ,we have:
$L.H.S\leq\sqrt{(\sum sinAsinB)(\sum cosA)}\leq\sqrt{(\sum sinA^{2})(\sum cosA)}\leq\sqrt{\frac{9}{4}.\frac{3}{2}}=\frac{3\sqrt{6}}{4}$[/quote]

This is wrong: $L.H.S\leq\sqrt{(\sum sinAsinB)(\sum cosA)}$ is a wrong application of Chebyshev.

[color=red][[b]EDIT:[/b] As Sbos kindly pointed out, this is wrong. Keira_khtn's solution is correct.][/color]

Anyway, the problem is rather easy: We have to prove the inequality

$\sqrt{\sin B\sin C\cos A}+\sqrt{\sin C\sin A\cos B}+\sqrt{\sin A\sin B\cos C}\leq\frac{3\sqrt6}{4}$

for any acute-angled triangle ABC.

Rewrite this inequality in the form

$\frac{\sqrt{\sin B\sin C\cos A}+\sqrt{\sin C\sin A\cos B}+\sqrt{\sin A\sin B\cos C}}{3}\leq\frac{\sqrt6}{4}$.

After squaring, this becomes

$\left(\frac{\sqrt{\sin B\sin C\cos A}+\sqrt{\sin C\sin A\cos B}+\sqrt{\sin A\sin B\cos C}}{3}\right)^{2}\leq\left(\frac{\sqrt6}{4}\right)^{2}$.

But since

$\left(\frac{\sqrt{\sin B\sin C\cos A}+\sqrt{\sin C\sin A\cos B}+\sqrt{\sin A\sin B\cos C}}{3}\right)^{2}$
$\leq\frac{\sin B\sin C\cos A+\sin C\sin A\cos B+\sin A\sin B\cos C}{3}$

by the inequality between the $\frac12$-power mean and the arithmetic mean, in order to prove this inequality, it will be enough to show the stronger inequality

$\frac{\sin B\sin C\cos A+\sin C\sin A\cos B+\sin A\sin B\cos C}{3}\leq\left(\frac{\sqrt6}{4}\right)^{2}$.

Upon multiplication with 6, this becomes

$2\left(\sin B\sin C\cos A+\sin C\sin A\cos B+\sin A\sin B\cos C\right)\leq 6\cdot\left(\frac{\sqrt6}{4}\right)^{2}$.

This rewrites as

$\left(\sin C\sin A\cos B+\sin A\sin B\cos C\right)+\left(\sin A\sin B\cos C+\sin B\sin C\cos A\right)$
$+\left(\sin B\sin C\cos A+\sin C\sin A\cos B\right)\leq\frac94$.

But by the sum of the angles in a triangle, A + B + C = 180°, so that B + C = 180° - A, and thus sin (B + C) = sin A. In other words, cos B sin C + sin B cos C = sin A. Thus,

$\sin C\sin A\cos B+\sin A\sin B\cos C=\sin A\left(\cos B\sin C+\sin B\cos C\right)$
$=\sin A\sin A=\sin^{2}A$,

and similarly $\sin A\sin B\cos C+\sin B\sin C\cos A=\sin^{2}B$ and $\sin B\sin C\cos A+\sin C\sin A\cos B=\sin^{2}C$. Hence, the inequality in question becomes

$\sin^{2}A+\sin^{2}B+\sin^{2}C\leq\frac94$.

But this is a famous inequality. So the proof is complete.

  Darij

Darij, I think keira_khtn didn't use Chebyshev, but Cauchy-Schwarz.

[quote="zhaobin"]yes,but keira_khtn also have something wrong.
for $\sum \cos A \leq \frac{3}{2}$[/quote]

what mistake?

Daiji!!
I think our solution is  so long.This ineq is really easy.

Using the usual notation, the inequality can be rewritten as:
$ \sum\sqrt{sinAsinBcosC}\le\frac{3\sqrt{6}}{4} $
With the notation $ a=2cosA,b=2cosB,c=2cosC $ the problem lies in:
$ a,b,c>0,a^2+b^2+c^2+abc=4\Rightarrow\sum\sqrt{c\sqrt{(4-a^2)(4-b^2)}\le 3\sqrt{3} }$
Since $ a^2+b^2+c^2+abc=4\Leftrightarrow (2c+ab)=\sqrt{(4-a^2)(4-b^2)} $
we have shown that:
$ \sum\sqrt{c(2c+ab)}\le 3\sqrt{3} $
Apply Cachy-Schwarz and keep in mind that $ a+b+c\le 3 $ and $ ab+bc+ca\le 3 $,obtain:
$ \sum\sqrt{c(2c+ab)}\le\sqrt{a+b+c}\sqrt{2(a+b+c)+bc+ca+ab}\le 3\sqrt{3}\Leftrightarrow QED $
__________
Sandu Marin

Let  $a=2sin\frac{A}{2},b=2sin\frac{B}{2},c=2sin\frac{C}{2}  $,then we have :
  $4\sum sin^{2}\frac{A}{2}+8\prod sin\frac{A}{2}=4  $
[b]proof:[/b]
From the well-known identity Napier   $:\sum sin^{2}\frac{A}{2}=\frac{2R-r}{2R},\prod sin\frac{A}{2}=\frac{r}{4R}  $  , then we have :
  $ \sum sin^{2}\frac{A}{2}+2\prod sin\frac{A}{2}=\frac{2R-r}{2R}+\frac{r}{2R}=1  $ .
we have :

$ I=\sum \sqrt{2sin\frac{C}{2}\sqrt{16(1-sin^{2}\frac{A}{2})(1-sin^{2}\frac{B}{2})}}=\sum \sqrt{8sin\frac{C}{2}cos\frac{A}{2}cos\frac{B}{2}}=\sum \frac{\sqrt{8sin\frac{C}{2}\prod cos\frac{A}{2}}}{cos\frac{C}{2}}=\sqrt{\frac{8s}{4R}}\sum \sqrt{tan\frac{A}{2}}\leq \sqrt{\frac{2s}{R}}\sqrt{3\sum tan\frac{A}{2}}\leq 3\sqrt{3}\Rightarrow R\geq 2r  $ , because,  $ \sum tan\frac{A}{2}=\frac{4R+r}{s}  $

but
\[LHS \le 3\sqrt{\frac{\sum{\sin \alpha \sin \beta \cos \gamma }}{3}}=3\sqrt{\frac{1+\cos \alpha \cos \beta \cos \gamma }{3}}\le \frac{3\sqrt{6}}{4}\]
 :maybe:

[quote="xzlbq"][quote="sbos"]Prove that in an acute triangle the following inequality holds:
\[\sqrt{\sin\alpha\sin\beta\cos\gamma}+\sqrt{\sin\beta\sin\gamma\cos\alpha}+
\sqrt{\sin\gamma\sin\alpha\cos\beta}\leq\frac{3\sqrt6}{4}.\][/quote]

Prove that in an acute $\triangle ABC$ the following inequality holds:
\[\sqrt{\sin{A}\sin{B}\cos{C}}+\sqrt{\sin{B}\sin{C}\cos{A}}+\sqrt{\sin{C}\sin{A}\cos{B}}\leq\frac{3\sqrt6}{4}.\][/quote]

First,any triangle,have:

$\frac{27}{32}(\frac{\sin{C}}{\sin{A}+\sin{B}+\sin{C}}+\frac{\cos{A}\sin{B}}{\cos{A}\sin{B}+\cos{B}\sin{C}+\sin{A}\cos{C}})^2$

$\geq \cos{A}\sin{B}\sin{C}-----(1)$

from it is an acute triangle,
(1)=>

$\frac{3\sqrt{3}}{4\sqrt{2}}(\frac{\sin{C}}{\sin{A}+\sin{B}+\sin{C}}+\frac{\cos{A}\sin{B}}{\cos{A}\sin{B}+\cos{B}\sin{C}+\sin{A}\cos{C}})$

$\geq \sqrt{\cos{A}\sin{B}\sin{C}}-----(2)$

give a sum to (2),get result.

BQ


Hi guys

what's the best approach to the type of problems where one is given rates.
for example: bob cleans his house in 3 hours and jenny in 9 hours. How long will it take them to clean it together?

I am not worried about the solution, I am looking for the approach  :lol:

Uh igiul that [i]is[/i] a rate problem but from the example the OP gave it seems as though he's looking for a way to do [i]work[/i] problems. To the OP, when I do work problems I compare the total job to the time it takes to complete the job. So to complete one job in 3 hours is $ \frac{1}{3}$ and to complete one job in 9 hours is $\displaystyle \frac{1}{9}.$To find the amount of time it takes them collectively to complete one job all you need to do is add the fractions and put the result under a numerator of 1.

\[\frac{1}{3}\:+\frac{1}{9}\; = \; \frac{4}{9}\] then it has to be relative to [i]one[/i] job so $ \frac{1}{{4}/{9}}\; = \; \frac{9}{4}$ hours

[quote="igiul"][hide="SAT Question:"]
A woman drove to work at an average speed of 40 miles per hour and returned along the same route at 30 miles per hour. If her total traveling time was 1 hour, what was the total number of miles in the round trip?[/hide]

[hide="Solution:"]
$V_{1}= 40$; $V_{2}= 30$
$\frac{d}{V_{1}}= t_{1}$; $\frac{d}{V_{2}}= t_{2}$
$t_{1}+t_{2}= 1 = \frac{d}{V_{1}}+\frac{d}{V_{2}}= \frac{d(V_{1}+V_{2})}{V_{1}V_{2}}= 1$
$d(V_{1}+V_{2}) = V_{1}V_{2}$

$d = \frac{V_{1}V_{2}}{V_{1}+V_{2}}= \frac{1200}{70}= \frac{120}{7}$ miles.

But that's $\frac{1}{2}$ the trip, since she traveled $2d$, so the answer is 34 and 2/7 miles

[/hide]

EDIT: I think the Time equations are generally the key. That, or distance depending on the problem. Try to factor. Many of these problems are BUILT to cancel. here are a few rules of the thumb;

$\frac{operation}{time}= speed$
$\frac{operation}{speed}= time$
$speed$X $time = operation$[/quote]

Or we  could just use harmonic mean, which for two terms can be simplified to $\frac{2AB}{A+B}$.

So 2*30*40/70=240/7=$34\frac{2}{7}$ mph, and since she traveled for 1 hour, that would be the total distance.

[quote="#H34N1"][hide="approach"]
In 1 hour, Bob clens $\frac{1}{3}$ of the house. In 1 hr, Jenny cleans $\frac{1}{9}$ of the house. Add them up: $\frac{1}{3}+\frac{1}{9}=\frac{4}{9}$. Now, take the reciprocal. Total, they will take $\frac{9}{4}$ hours or 2 hrs and 15 min.[/hide][/quote]

Yes, that approach is the same i was trying to imply.

Lets say we had x different people/rates, we just use harmonic mean (reciprocal of the average of the sum of the reciprocals).  And that gives the average rate.  Then, since that is average, and x people are working, we multiply by x again, which cancels out the average, and just leaves us with the reciprocal of the sum of the reciprocals.

sorry if that was hard to follow.

Thank you very much

that was very useful. So was the first car travel question.  :)

this model might lend itself well to explaining this question:

When you have two times, like the ones in your house problem, you can't just add them. You have to add rates, because when they work together, they combine their rates.

So make rates out of the information given.

$\frac{1 house}{3hours}$ and $\frac{1house}{9hours}$

add them up and you get

$\frac{\frac49 house}{hour}$

which translates to

$\frac{1house}{\frac94 hours}$

I understand it's the same method, but I feel like this explanation shows why better.


linear algebra
matrix
integration
vector
function
probability
linear algebra solved

${(a_i})_{i=1}^{n}$-different positive real numbers , matrix $A$ defined as follows: $A=||\frac{1}{a_i+a_j}||_{1\leq i,j \leq n}$. Prove that matrix A is positively defined.

You should prove that $X^t.A.X\geq 0$ for any $X\in R^n$
and $X^t.AX=0 \Rightarrow X=0$

Use $\frac{1}{a_i+a_j}=\int_{0}^{1}t^{a_i+a_j-1}dt$

Let $B={u_1, u_2, \dots u_k}$ be a set of vectors in an inner product space. Define the "Grammian" matrix $G$ by setting the $(i,j)$ element of $G$ equal to the inner product of $u_i$ with $u_j.$ Then $G$ is always positive semidefinite and is positive definite if and only if $B$ is an independent set.

The proof is trivial: If $x$ is the column vector with entries $x_i$, then we can show that $||\sum_ix_iu_i||^2=x^TGx.$ (That's in a real inner product space. In a complex inner product space, you would write $x^*Gx$.) This is obviously nonnegative, and would be zero for some nonzero $x$ if and only if some nontrivial linear combination of the $u_i$ were the zero vector - in other words, if $B$ were dependent.

All Moubinool did was suggest an independent set (the set of functions $\{1,t,t^2,\dots,t^{n-1}\}$) on a particular inner product space (continuous functions on $[0,1]$ with the inner product of $f$ and $g$ given by $\int_0^1xf(x)g(x)dx$.) Since the set of functions is clearly linearly independent, the Grammian matrix is positive definite. (Albeit notoriously ill-conditioned.)

[quote="eugene"]really pretty nice solution, maybe you could say where you read about "Grammian" matrix and other results[/quote]
Grammian matrix is a well known object in funtional analysis, for example. So you can read appropriate analysis books.

I would add that if you've seen the Gram-Schmidt orthogonalization process (often taught in a first linear algebra course), then this is the same "Gram" and the matrix of inner products contains all the information ever needed for the whole orthogonalization process.

There's an extremely close relative of this matrix in probability theory: the covariance matrix. If $(X_i), 1\le i\le n$ are random variables, we define $Cov(X_i,X_j)=E(X_i,X_j)-E(X_i)E(X_j)$ with the note that that makes $Cov(X_i,X_i)=Var(X_i).$ The the covariance matrix is the matrix $C$ whose $(i,j)$ entry is $Cov(X_i,X_j).$

Another way to write this is to consider $X$ to be a random column vector with components $X_i$. Then $C=E(XX^T)-E(X)E(X)^T.$

The covariance matrix is always postive semidefinite, and is positive definite whenever the $X_i$ are [i]linearly[/i] independent (a far, far weaker condition than probabilistic independence.) In fact, considering $a_i$ to be the constant components of the column vector $a$, we have

\[Var\left(\sum_ia_iX_i\right)=Var(a^TX)=a^TCa.\]


number theory
Divisibility
polynomial
IMO
Hi
IMO 2003
IMO Shortlist

Let $p$ be a prime number. Prove that there exists a prime number $q$ such that for every integer $n$, the number $n^p-p$ is not divisible by $q$.

For p=2 take n=5. Let now p be odd. We have
p^p-1=(p-1)(1+p+..+p^{p-1}}. The second bracket is odd and is not equal 1 modulo p^2. Then there exists its prime divisor q, which is odd and not of form k*p^2+1. Lets prove that q satisfies condition. If n^p=p (mod q), then (n^p)^p=p^p=1 (mod q), so n^{p^2}=1 (mod q). Since n^{q-1}=1 (mod q), we have n^gcd(q-1,p^2)=1 (mod q). But q-1 is not divisible by q^2, then gcd(q-1,p^2) is p or 1. so, n^p=1 (mod q) -- a contradiction, unless p-1 is divisible by q. But the 1+p+..+p^{p-1}=p (mod p-1), so coprime with p-1.

What follows is just the construction Fedor Petrov provided. Our excuse for this post is that it'll attempt to show that this choice of q is in fact quite 'natural'.
Thus we are just trying to solve the congruence x^p = p (mod q). When does this have no solution? By Euler's criterion, or much more cutely by summing up (n^p -p)^(q-1) over n lying in Z/qZ, we observe that the above congruence has no solution [i]if and only if [/i] the following conditions are met:
1) q = 1(mod p)
2)p^ ((q-1)/p) not equal to 1 (mod q)

Thus the problem is equivalent to proving the existence of a prime q satisfying 1) and 2).
So it almost seems like a special case of the decidedly non-elementary Dirichlet's theorem for primes in Arithmetic progression! But there is an elementary proof of this theorem for the mk+1 case and this falls in that case...more exactly one can (easily)prove that for any c,d integers,(c,d) not equal to (3,2), c^d - 1 has a prime divisor of the form kd+1. The proof begins with the observation that any prime dividing c^d -1 and [u]not dividing[/u] c^h - 1 for all h properly dividing d must be of the form kd+1;to complete the proof one has to show that such a prime exists.The existence of such a prime is a matter of simple inequalities. In our problem d = p, and h can only be 1.
So, there are not many other ways to proceed except to choose c, and then choose any prime q that divides c^p -1, does not divide c-1 and hope(here's where the 'suitability' of the c comes in) that p^((q-1)/p) is not 1 mod q. Since we dont have many numbers to play with, the first guess would be c=p, which works.
Finally, since a bit of generalization can't hurt, the same constuction, with a^p-1 instead of p^p -1, proves the following result:
Let p be an odd prime and a be an integer such that p^2 does not divide a^p - a. Then there exists a prime q such that n^p - a is not divisible by q for any integer n.

-Abhishek Saha

[quote]
n^{p^2}=1 (mod q). Since n^{q-1}=1 (mod q), we have n^gcd(q-1,p^2)=1 (mod q). [/quote]

why n^gcd(q-1,p^2) = 1 (mod q)?
i cannot see it clearly.

To the last guest: gcd of two positive integers is their linear combination with integer coefficients. So, if n^A=1 (mod p) and n^B=1 (mod p), then n^gcd(A,B)=n^(k*A+l*B)=1^k*1^l=1 (mod p). Never mind that l or k may be negative.

[quote="Jayanta"]Let K be the splitting field over Q of x^p-p . This is Galois of order p(p-1).  Chebotarev density gives  Frobenius elements of order p. Not elementary, but at the heart of the question :)[/quote]

That sounds intriguing, but since I have no idea what "Chebotarev density" or "Frobenius elements" are, it's completely lost on me.  Do you think you could possibly give me some idea of what that is?  I do know some Galois theory.

I started writing out something on the Chebotarev stuff.... and decided at the end that the best way is to give some references. Two books that come to mind are Local Fields by Jean-Pierre Serre and Algebraic Number Theory by Serge Lang.
Here is a naive/simplistic way of looking at it: lets suppose K / Q finite Galois with Galois group G, and suppose that K splits the irreducible polynomial $f$ (with Q coeffs). We can look at the reduction mod p of f and look at its Galois group over F_p --- this will work for primes outside a finite set (called ramified primes). And over F_p, we know that the Galois group is cyclic with a canonical generator---the Frobenius map which raises elements to the p-th power. It turns out that these infact lift to elements in the Galois group G, and these are the Frobenius elements. Chebotarev density then says that each conjugacy class in G contains lots of Frobenius elements.
So what does this have to do with the original problem? There, we had G a non-abelian group of order p(p-1). Look at the conjugacy class given by an element of order of p. Unravelling what Chebotarev says gives us lots of primes q such that the splitting field of $X^p-p$ over F_q is of degree p. Which is precisely what we want!
The same method also deals with any irreducible polynomial f of prime degree... there is a prime q which does not divide f(n) for any integral n.
Jayanta

Thank you very much!  You've certainly given me food for thought.

[quote="Anonymous"]Never mind that l or k may be negative.[/quote]

why does it hold when l or k is negative?
i just confused with this.

Because the division is possible modulo p, aswell as multyplication, if we divide to the number which is not a factor of p (or consider all calculations in the field of residues modulo p).

A circle has p congruent sectors where p is a prime. In how many ways these p sectors can be coloured with n colours if for several (maybe even all) sectors the same colouring is valid. Two colourings are considered as different if they don't cover each other by means of a rotation of the circle. Prove the theorem by Fermat: If p is a prime then n^p-n is divisible for each n by p !

Is this problem anyhow related to IMO2003/6 ?

[quote="supercomputer"][quote="abhisaha"]
Thus we are just trying to solve the congruence $x^p = p \pmod{q}$. When does this have no solution? By Euler's criterion, or much more cutely by summing up $(n^p -p)^{(q-1)}$ over $n$ lying in $\mathbb{Z}/q\mathbb{Z}$, we observe that the above congruence has no solution [i]if and only if [/i] the following conditions are met:

1) $q = 1\pmod{p}$
2) $p^{(\frac{q-1}{p})} \not\equiv 1 \pmod{q}$
[/quote]

How does this conclusion follow from either of the two methods (Euler's Criterion and/or the sum) that the quoted poster mentioned?[/quote]

I assume that you looked up what Euler's Criterion is, and found something relating to quadratic residues. Well, what we're using here is a generalization of that: how can we tell if something has a $p$-th root modulo $q$. Let us first get the first condition, that $q \equiv 1 \pmod{p}$. Well, let's assume that $q \not\equiv 1 \pmod{p}$. We'll now show that every single number has a $p$-th root modulo $q$. Suppose we had two $x \not\equiv y \pmod{q}$ such that $x^p \equiv y^p \pmod{q}$. Multiply both sides by $y^{-p}$ to get $(xy^{-1})^p \equiv 1 \pmod{q}$, which means that $\text{ord}_q(xy^{-1}) | \gcd{(p, q-1)}$, but because $q-1$ and $p$ are relatively prime, we have $x \equiv y \pmod{q}$, contradiction. So that means, if we consider the set numbers $1^p, 2^p, 3^p, ..., (q-1)^p$, no two of them are the same, which means that every residue has a $p$-th root...which of course would imply that $n^p \equiv p \pmod{q}$ has a solution.

Okay so now we know that $q \equiv 1 \pmod{p}$. The second one is now very similar to Euler's Criterion for quadratic residues. Suppose there exists some integer $r$ such that $r^p \equiv p \pmod{q}$. Then, raising both sides to the $\frac{q-1}{p}$ -th power, we get $r^{q-1} \equiv 1 \equiv p^{\frac{q-1}{p}} \pmod{q}$, so if $p^{\frac{q-1}{p}} \not\equiv 1 \pmod{q}$, then $n^p \equiv p \pmod{q}$ cannot have a solution. Now to prove it the other way, that if $x^p \equiv p \pmod{q}$ doesn't have a solution, then $p^{\frac{q-1}{p}} \not\equiv 1 \pmod{q}$. Well, the number of solutions to $n^{\frac{q-1}{p}} \equiv 1 \pmod{q}$ is at most $\frac{q-1}{p}$ since $q$ is prime. Suppose again we have $x^p \equiv y^p \pmod{q}$ so that $(xy^{-1})^p \equiv 1 \pmod{q}$. The order of $xy^{-1}$ is either $1$ in which case $x \equiv y$ or $p$. Hence, there are $p$ values that $xy^{-1}$ can take on, which means that given a certain $x$ such that $x^p \equiv \text{something} \pmod{q}$, we have $p-1$ other numbers $y$ such that $y^p \equiv x^p \pmod{q}$. Suppose $r_1, r_2, ..., r_m$ are integers that have a $p$-th root. Furthermore, we know that each one has exactly $p$ roots. Therefore, $mp = q-1$, so $m = \frac{q-1}{p}$, so there are $\frac{q-1}{p}$ numbers that are perfect $p$-th powers modulo $q$. Therefore, the congruence $x^{\frac{q-1}{p}} \equiv 1 \pmod{p}$ is satisfied if and only if $x$ is a perfect $p$-th power. And, of course, letting $x = p$, we see that there exists an integer $n^p \equiv p \pmod{p}$ if and only if $p^{\frac{q-1}{p}} \equiv 1 \pmod{q}$.

Hope that answers your question about Euler's Criterion.

As for the summing $(n^p - p)^{q-1}$: from FLT, we know that $x^{q-1} \equiv 1 \pmod{q}$ UNLESS $q|x$. So if we assume that for all $n$, $n^p - p$ is not divisible by $q$, then $(n^p - p)^{q-1} \equiv 1 \pmod{q}$, so when we sum over $n$ from $1$ to $q-1$, we should get $q-1$ modulo $q$. By expanding $(n^p - p)^{q-1}$ and reducing everything, we get the same conditions as mentioned above. Try it yourself!

Surprisingly easy

just take a prime divisor of $ \frac{p^p-1}{p-1} $ that is not 1 mod $p^2$

There were some little details

If n<0, then n^(q-1) = -(-n)^(q-1) = -1 (mod q). So n^(q-1) = 1 (mod q) failed. But no matter, raising both sides to 2, we can get the same contradiction.

We attempt to present a complete proof as tersely as possible.

Note that any prime $q\mid p^{p-1}+\cdots + p+1=\frac{p^p-1}{p-1}$ must satisfy $q\mid p^p-1$, hence $\mbox{ord}_q(p) \in \{1,p\}$, but $q\nmid p-1$ because $\gcd (p-1,p^{p-1}+\cdots + 1) = \gcd (p-1,p) = 1$, so $p\mid q-1$. However, there must exist some such prime $q\mid \frac{p^p-1}{p-1}$ such that $q\not\equiv 1\pmod{p^2}$, as that expression is $p+1\pmod{p^2}$. Take such a prime $q=pk+1$. We claim this prime works. Otherwise, there exists some $n$ such that $n^p\equiv p\not\equiv 1\pmod{q}$, $n^{p^2}\equiv p^p\equiv 1\pmod{q}$, implying $n$ has order $p^2$ and $p^2\mid q-1$. But this is false, hence $q$ works.

[hide = Solution]
[color=#0B5394][b]Claim:[/b][/color] There exists $q \not\equiv 1 \pmod{p^2}$ such that $\operatorname{ord}_q p = p$.

[i]Proof[/i]. Consider $\tfrac{p^p - 1}{p - 1}$. This is greater than $1$, and is relatively prime to $p - 1$ by LTE. So if $q$ divides it, then $\operatorname{ord}_q p = p$. However, we can't have all primes dividing it be $1$ mod $p^2$, since \[\frac{p^p - 1}{p - 1} \equiv -\frac{1}{p - 1} \not\equiv 1 \pmod{p^2}.\] So at least one of its prime factors works.  $\blacksquare$

Note that $q \equiv 1 \pmod{p}$, since the order must divide $q - 1$. So \[n^p \equiv p \mod{q} \implies 1 \equiv n^{q - 1} \equiv p^{\frac{q - 1}{p}} \pmod{q}\] (since $q \neq p$, clearly $q \nmid n$). However, this means $p$ must divide $\tfrac{q - 1}{p}$ by orders, contradiction.

[color=#0B5394][b]Remark:[/b][/color] The motivation for this is that we want $q$ mod which $p$ is not a $p$th power. First we want $q \equiv 1 \pmod{p}$, or else everything is a $p$th power. Then $p$ is not a $p$th power iff $\nu_p(d) = \nu_p(q - 1)$, where $d$ is the order of $p$ mod $q$, so we can try setting both to 1, which works.
[/hide]

I'll try to illustrate the thought process leading to the choice of $q.$ It seems unnatural at first glance, but, in fact, it's rather easy to think of this.
[rule]
Fix some $q,$ and let $g_q$ be a primitive root modulo $q.$ We will proceed to work in $\mathbb{Z}_q$ only. Let $p=g_q^c$ and $n=q_q^m.$

Then, $n^p\equiv p\bmod{q}$ rewrites as $g_q^{p m}\equiv g_p^{c}\bmod{q}$ or, $g_q^{pm-c}\equiv 1\bmod{q}$ so $q-1\mid pm-c.$ Rewrite this as $pm\equiv c\bmod{q-1}.$

Here's the catch: for a fixed $q,$ since $p$ is fixed, then so is $c$ (recall that $p=g_q^c$) Hence, the only thing that varies is $m$ and since $n$ ca take any value of $\mathbb{Z}_q$ then $m$ can take any value from $\mathbb{Z}_{q-1}.$ So, for the congruence $pm\equiv c\bmod{q-1}$ to have no solution, $p$ must not have a multiplicative inverse modulo $q-1$ or, in other words $\gcd(p,q-1)\neq 1.$ Since $q$ is a prime, this forces us to have $q\equiv 1\pmod{p}.$ Let $q=kp+1.$

Coming back to our congruence, we have $pm\equiv c\pmod{kp}.$ Observe that this congruence has a solution if and only if $p\mid c.$ But what was $c?$ We defined $c$ as $p=g_q^c$ so, in other words, the order of $p$ modulo $q$ is $(q-1)/\gcd(c,q-1).$

Now we know what kind of $q$ we want to find. We want $q\equiv 1\bmod{p}$ and $p\nmid c$ where $\text{ord}_q(p)=(q-1)/\gcd(c,q-1).$ However, teh interesting part is that all those properties are [i]forced[/i]. All $q$ that satify the problem's condition [i]must[/i] satisfy $q\equiv 1\bmod{p}$ and $p\nmid c$ where $\text{ord}_q(p)=(q-1)/\gcd(c,q-1).$ This is why, a natural primitive root approach leads you to the seemingly random choice of $q.$

Now, to finish off, indeed, if $\nu_p(q-1)=1$ and $p\mid \text{ord}_q(p)$ it follows that $p\nmid \gcd(c, q-1)$ so, because $q\equiv 1\bmod{p}$ then $p\nmid c.$ Hence, if some $q$ satisfies the following three conditions, it also satisfies the problem's requirements: \[\begin{cases}q\equiv 1\pmod{p}, \\ p\mid\text{ord}_q(p)\text{ and,}\\ \nu_p(q-1)=1\end{cases}\]It now naturally follows to consider some $q$ dividing $\Phi_p(p),$ which assures the first two conditions and then to show that not all $q$ dividing $\Phi_p(p)$ are congruent to $1\bmod{p^2},$ which yields the existance of a prime $q$ with the three desired properties, finishing the proof.     $\square$

We are basicaly studying the congruence $n^p \equiv p \pmod q$
[b][color=#f00]Claim 1:[/color][/b] $v_p(q-1)=1$ must hold.
[b][color=#f00]Proof:[/color][/b] We will make an attempt (u will know why i use this word later) to rid out the injectivity of $x^p$ in $\mathbb Z_q$ for $x$ coprime with $q$. So consider $a^p \equiv b^p \pmod q$ so that $a,b$ are coprime with $q$ and $a \not\equiv b \pmod q$ which means that $a,b$ have an inverse in $\mathbb Z_q$ which means that $(a \cdot b^{-1})^p \equiv 1 \pmod q$ so it means that $\text{ord}_q(a \cdot b^{-1}) \mid \gcd(q-1,p)$ and since we dont want the order to be one we need $p \mid q-1$ so now lets continue. Setting $n=p$ we have that $p^{p-1} \equiv 1 \pmod q$ as $p \ne q$ ofc lol, now if there is such $n$ then we have that $p^{\frac{q-1}{p}} \equiv 1 \pmod q$ so we will have that $\frac{q-1}{p} \mid p-1$ hence for some constant $c$ we will have $p-1=\frac{c(q-1)}{p}$ so $p(p-1)=c(q-1)$ which clearly says that $v_p(q-1)=1$ needs to hold here.
[b][color=#f00]Claim 2:[/color][/b] If there exists 2 positive integers $x,y$ such that $x^p \equiv y^p \pmod q$ then either $x \equiv y \pmod q$ or $x \equiv y \equiv 0 \pmod q$ hold.
[b][color=#f00]Proof:[/color][/b] The case when one of the $x,y$ is $0$ on $\mathbb Z_q$ is clear so lets take $x,y$ coprime with $q$. Then its inverse exists so we have that $(x \cdot y^{-1})^p-1 \equiv 0 \pmod q$ and now if $x \not\equiv y \pmod q$ then $\Phi_p(x \cdot y^{-1}) \equiv 0 \pmod q$ which means that either $p=q$ or $q \mid p-1$ and both are imposible so we got a contradiction.
[b][color=#f00]Finishing:[/color][/b] The idea here is the use of primitive roots on $\mathbb Z_q$ hence let $g$ the primitive root on $\mathbb Z_q$ hence we can let $n \equiv g^k \pmod q$ and $p \equiv g^l \pmod q$ for $1 \le k,l \le q-1$ and now this means that $g^{k \cdot p-l} \equiv 1 \pmod q$ so we have $p \mid q-1 \mid k \cdot p-l$ so $p \mid l$ meaning that if we let $l=p \cdot m$ then $(g^k)^p \equiv (g^m)^p \pmod q$ but note that if $g^{k-m} \equiv 1 \pmod q$ then $q-1 \mid k-m$ which is imposible unless $k=m$ due to size reasons (skipping the other case becuase the other case implies that $g$ is $0$ on $\mathbb Z_q$ which is clearly not possible) now we consider our last condition of $q$ which is $q \mid p^p-1$ to get a contradiction with $n=p$ and now note that $n^{p^2} \equiv p^p \equiv 1 \pmod q$ meaning that $\text{ord}_q(n) \mid \gcd(q-1,p^2)=p$ hence $n \equiv 1 \pmod q$ or $n^p \equiv 1 \pmod q$ and both yeld contradictions hence we are done :D

[b]Existence of such prime:[/b] Since $$p+1\equiv 1+p+p^2+p^3+\dots+p^{p-1}=\tfrac{p^{p}-1}{p-1} \pmod{p^2}$$ we must have a prime $r$ such that $\tfrac{p^{p}-1}{p-1}\equiv 0\pmod r$ and $p^2\nmid r-1.$ $\blacksquare$

[b]This prime works:[/b] Assume the contrary then $$n^p\equiv p\pmod r \iff 1\equiv p^{\tfrac{r-1}{p}}\pmod r.$$ This forces $r\equiv 1\pmod{p^2}$ due to order reasons, impossible. $\blacksquare$

[hide=Sketch my sol]
[color=#f00][b]Theorem:[/b][/color] $\exists \, n: n^p-p \, \vdots \,q \, \Leftrightarrow \, p^{\frac{q-1}{p}}-1 \, \vdots \, q$
[color=#00f]Proof:[/color] Easy.
If we let $k=ord_q(p)$ then $\frac{q-1}{p} \, \vdots \, k \Leftrightarrow q-1 \, \vdots \, pk$
From here i take $q \, | \, p^p-1$, $k=p$ [/hide]

If $p=2$, then take $q=3$. Otherwise, consider prime divisors of $p^{p-1}+p^{p-2}+\cdots+1$. If all of them are congruent to $1 \pmod{p^2}$, then $p^{p-1}+p^{p-2}+\cdots+1 \equiv 1 \pmod{p^2}$, a contradiction. Thus, there must be a prime divisor not congruent to $1 \pmod{p^2}$. Take $q$ to be that prime.

We have $q \mid (p-1)(p^{p-1}+p^{p-2}+\cdots+1)=p^p-1$, so $\operatorname{ord}_q(p) \mid p$. If $\operatorname{ord}_q(p)=1$, then $p \equiv 1 \pmod{q}$, but that means $p^{p-1}+p^{p-2}+\cdots+1 \equiv p \not\equiv 0 \pmod{q}$, a contradiction. Therefore, we have $\operatorname{ord}_q(p)=p$. Notice that $p$ not being a $p$th power $\!\!\!\mod{q}$ is equivalent to $p^\frac{q-1}{p} \not\equiv 1 \pmod{q}$. But notice by assumption that $\operatorname{ord}_q(p)=p \nmid \tfrac{q-1}{p}$, so we're done.

for some prime $q$ let $g$ be a primitive root modulo $q$ and $n \equiv g^\alpha$ , $p\equiv g^\beta$
so $n^p \equiv p \pmod{q}$ or $g^{\alpha p} \equiv g^\beta \pmod{q}$ and it means $\alpha p \equiv \beta \pmod{q-1}$
now let $q = pk+1$ then  $\alpha p \equiv \beta \pmod{pk}$ so $p | c$
it's enough find $q$ such that $p \nmid c$. note that $ord_q(p) = \frac{q-1}{gcd(c,q-1)}$ if $v_p(q-1)=1,p|ord_q(p)$ then $p\nmid c$
we will show that one of prime factors of $\Phi_p(p)$ has this properties ($\Phi_p(x) = \frac{x^p-1}{x-1}$)
- $\color{blue} q\equiv 1 \pmod{p} : $ we know that all prime factors of $\Phi_p(x)$ are $pk+1$ or $p$ but $p\nmid \Phi_p(p)$
- $\color{blue} p \mid ord_q(p) : $ so $q\nmid p-1$ ( because isn't possible $p\equiv 1 \pmod{q},q\equiv 1 \pmod{p}$) so $p^p \equiv 1 \pmod{q}$ and $ord_q(p) \mid p$ but $ord_q(p) \not =1$ so $ord_q(p) = p$
- $\color{blue} v_p(q-1) = 1 : $ let all prime factors of $\Phi_p(x)$ be on form $p^2k+1$ so $\Phi_p(x)$ is $P^2k'+1$ but $\Phi_p(x)=1+p+p^2+...+p^{p-1} \equiv p+1 \pmod{p^2}$ so exist $q$ such that $q\mid \Phi_p(x),v_p(q-1)=1$

Pick a prime $q$ such that $q\mid p^p-1$ but $q\nmid p-1$, and $q\not\equiv 1\pmod p^2$. Such a $q$ must exist because \[p^{p-1}+\dots + p+1\equiv p+1\pmod p^2\]
Now, suppose $n^p\equiv p \pmod q$ then $n^{p^2}\equiv p^p\equiv 1\pmod q$ so $\text{ord}_q(n)\mid \text{gcd}(p^2,q-1)$ but $p^2\nmid q-1$ so $n^p\equiv 1\pmod q$, contradiction.

This is quite a funny problem. The key is to pick some prime $q \mid \frac{p^p - 1}{p-1}$ but $q \not \equiv 1 \pmod p^2$. Now everything miraculously falls apart as we can write the congruence $$n^{p^2} \equiv p^p \equiv 1 \pmod q,$$ hence $p^2 \mid q-1$ or $n^p \equiv 1 \pmod q$. Both cases are impossible, so we're done.

huh

Pick a prime $q \mid p^{p-1} + p^{p-2} + \dots + 1 = \frac{p^p - 1}{p-1}$ such that $p^2 \nmid q - 1$, which clearly must exist (else $p^{p-1} + p^{p-2} + \dots + 1 \equiv 1 \pmod{p^2}$, contradiction.)

Now if $n^p \equiv p \pmod{p}$ then $n^{p^2} \equiv p^p \equiv 1 \pmod{q}$, but this implies due to orders that either $p \equiv 1 \pmod{q}$ or that $p^2 \mid q -1$, both contradictions - hence we are done.

welp I hope I didn't mess anything up
[hide = solution]
For $p = 2$ things are trivial.

Define $P = x^p-p$. We are trying to look at primes $q$ for which $P$ has no solution. Let $K$ denote the field $\mathbb{Q}(\zeta_p, p^{1/p})$. The minimal polynomial of $\zeta_p$ is $x^{p-1}+\dots + 1$ and so $p-1$ divides the degree of $K$. Similarily, $p$ divides the degree of $K$. One also sees easily that the degree of $K$ is at most $p(p-1)$; it follows that $K$ has degree $p^2-p$. This means that for all $0 \leq m < p$ and $1 \leq n < p$ there is a isomorphism of $K$ mapping $p^{1/p} \mapsto p^{1/p} \zeta_p^m$ and $\zeta_p \mapsto \zeta_p^n$. Thus there are isomorphims of $K$ not fixing any element. In particular, by the Chebotarev Density theorem, the set of primes $q$ for which $P(x) \equiv 0 \pmod q$ is NOT solvable has positive density, in particular there is at least one element and we're done.
[/hide]

Take any $q|\frac{p^p-1}{p-1}$ with $q\not\equiv 1\pmod{p^2}$.

[b][color=#00f]Claim:[/color][/b] $x^p-p$ is irreducible over $\mathbb{Z}[x]$.
[color=#00f]Proof:[/color] If it factored, it would be into two monic polynomials. Its roots all have magnitude $\sqrt[p]{p}$, so the product of any $k$ of them where $0<k<p$ is not an integer; contradiction from Vieta's. $\blacksquare$

Now go to section 2.3 [url=https://cjquines.com/files/sledgehammers.pdf]here[/url]. We are done. $\blacksquare$


I have sent the solution by email to solutions@usamts.org with subject Chao Xu, 10222, Round 3. in 12/21 last year. and it's already 14 days, the green check mark still haven't show up. Did I send the email in the wrong format? or no one have received it at all?
should I send it again?

Well, you've got to consider that AoPS was on break around Christmastime, and since it's around the new year, they could still be on break.  If you sent it as a PDF it should be fine.  Don't freak out until an administrator posts something in this forum saying that all green checks have been posted.  Then you should freak out.  But definitely don't resend until then because it can get annoying and they've been telling everyone not to resend unless they're confident it wasn't received.  I haven't received my check either.

ok. thx. guess I can still wait a few more days.
this is the first time I send in answers.. so I freak out xD


number theory
prime factorization
combinatorics unsolved
combinatorics

find $n$ is smallest such that every partition set ${1,2,...n}$ into two subsets then there exist a subset include three elements $a,b,c$ st $a.b=c$

it has been discused before, thats why noone post solutions here...

It's not hard, but it involves some busy work.

First, let's prove that for $n=96$ there is no partition that satisfies the problem condition.

Suppose that $2$ and $3$ belong to different sets, say, $2 \in A$ and $3 \in B$.  Suppose that $6 \in A$.  Then let $k$ be the smallest element of $A$ other than $2$ and $6$.  Since $B$ cannot contain both $4$ and $12$, $k \leq 12$.  Then $B$ contains $2k$ and $6k$, a contradiction.  If $6 \in B$, then let $k$ be the smallest element of $B$ other than $3$ and $6$.  $k \leq 8$, and $A$ contains both $3k$ and $6k$, a contradiction again.

Now suppose $2,3$ and $5$ belong to different sets, say $2,3 \in A$ and $5 \in B$.  The same reasoning leads to a contradiction again.

So we may assume that $2,3,5$ are in the same set, say set $A$.  Then we have the following implications:

$6,10,15 \in B$
$60 \in A$
$12 \in B$
$72 \in A$
$24 \in B$
$4 \in A$
$8 \in B$
$48 \in A$
$96 \in A$

which is a contradiction again.

For $n = 95$, we will distribute the numbers $1,2,\ldots, 95$ based on the prime factorization type:  we say the $n$ has type $abc$, say, if $n = p^{a}q^{b}r^{c}$ for primes $a,b,c$.  Let $A$ have numbers of type $1,2,5,6,41,32,211,$ and $1111$.  Let $B$ have numbers of type $3,4,11,21,22,31,111$.  This contains all numbers less than or equal to $95$, and it's not hard to see that no number is the product of two other numbers in the same set.