AMC
USA(J)MO
USAMO
AIME
email
geometry
geometric transformation

On Saturday afternoon, I met with the Committee on the American Mathematics Competitions (CAMC) and the CAMC Advisory Board.  We had a long conversation about qualification for the 2006 USAMO.

The recommendation was to continue to invite the top (approximately) 240 students based on the index from the AMC 12 + 10*AIME score.  That continues to be a cut-off of 217.0 as before.  The lowest AIME score among those 237 students was 8, as before.  The "floor value" continues to be 8. The CAMC and Advisory Board recommended that, as in 2005 and 2004, we also invite all young students in 10th grade and below who had an AIME score of 8 or better, regardless of which previous AMC contest was used to qualify for the AIME.

This adds an additional 57 students to those invited to the USAMO.  I note that all but 7 of those students qualified for the AIME by virtue of a score on the AMC 12.  We will be notifiying those additional students by email and paper mail as soon as we can correlate names, scores, addressses, schools, and email addresses.  The addtional names will also be posted on our Website in  the USAMO qualifiers section, again as soon as we can correlate names, and scores.

Many of the CAMC also are graders for the USAMO.  They agreed to this additional group of invitees knowing full well that they would have an addtional burden of grading and administration.  They accepted this burden willingly, believing that this addition is for the benefit of mathematically motivated students and the state of mathematics more generally.

The CAMC was in agreement that
1.  The written procedures for USAMO selection were followed and applied correctly
2.  The written procedures for USAMO selection reflect the intentions of the CAMC as well as any simple set of rules can.
3.  Nevertheless, the inherent paradoxes that can result from trying to reduce two scores to a linear ordering will occasionally result in the selections as we had before. Using the floor attempts to rectify the situation.

Next year, we may attempt a slight rewrite of the selection rules to avoid this kind of adjustment after the first application of the rules.

Steve Dunbar
AMC Director

This is very generous!  I am sure everyone is most appreciative!

It is indeed very generous of you to take the additional burden upon yourselves (as the USAMO graders) to allow these extra students to qualify for USAMO.

Of course, this doesn't affect me as a sophomore who qualified on the strength of my index alone...

I'm sure you've had a lot to deal with over the past few days (actually, both Boy Soprano and I contributed to one little problem of yours  ;) ) and I'm sure those extra 57 and others are very grateful that you took the time to discuss this issue.

WOW! THANKYOU! So I did qualify for USAMO.... :lol:

That means that if I have no misbubblings, then I got to the USAMO!!! YAAAAAAAY!!!!

i applaud the board for making the decision to include for the usamo all students who scored an 8 or better on the aime.  this is a fair outcome for those students who chose to take the amc 12 rather than the amc 10.  great decision.

does this mean that if I got an 8 on AIME, I made USAMO no matter what score I got on the AMC 10, 12?

Yes. Even a 120/8 makes the USAMO

Unfortunately a 146.5/7 doesn't.  :(

Oh well, always next year.

Indeed, I think this was a great decision, even though there should probably be a revision in the rules to avoid a large number of qualifiers like 430 every year. I am not affected myself, but nonetheless I extend my gratitude to the CAMC board members who made this decision, especially those who agreed to put in more of their own time and effort for grading the additional tests.

Then there's a chance that the floor would be 7.

That would make me a very happy penguin.

Yea, but then there'd be like 600 people taking the USAMO.  Which sadly, is not possible.

No, there would be an index cutoff for floor qualifiers like there was with the floor of 8.

Wow....Extremely appreciative...Now I should/must/shall study again! :lol:

[quote="mna851"]Didn't Mr. Dunbar say that the floor would remain an 8.  Why are you getting so excited Xantos?[/quote]

I'm not.

*sigh* USAMO expansion #2

I've lost all faith in the USAMO qualification. It seems like the prestige this year has been seriously clipped.

I wish the AMC committee wouldn't give in so easily to those petitions. There will always be people who almost made it, and there will always be those who aren't happy because they were so close. If they keep expanding it, they might as well take those 600 with the 7's.

It's supposed to be difficult to get into the USAMO, and I doubt the quality of the students taking the AIME this year have improved so dramatically that the qualifiers should be doubled (almost). I know I'm going to get a lot of rebuttals on this post, but that's what I think.

[quote="xxazurewrathxx"]
I wish the AMC committee wouldn't give in so easily to those petitions. There will always be people who almost made it, and there will always be those who aren't happy because they were so close. If they keep expanding it, they might as well take those 600 with the 7's.[/quote]

This has nothing to do with people who came very close; I am perfectly aware that the expected value of people who came within 0.5 of the index is 9  ;) (see calculation in other post). The controversy over this year's USAMO qualification was that people who took the AMC 10 were favored over those who took the AMC 12.

This is a very generous and, in my opinion, justified decision. I applaud all at the AMC who work so hard to make these contests happen each year. :)

It certainly is generous. As far as the conflict between amc10 and amc12 goes: Why not just make higher on the 12? Why not just take the 10? Why not take [i]both[/i]?

Maybe I should've just kept my opinions to myself  :P

EDIT: Perhaps I was being a bit too harsh about it, but I don't know. I'm just getting a negative feeling from all the loosening of the qualifying scores. Nevertheless, the AMC is still the most prestigious math competition in the U.S. (followed by ARML), I am not hesitant to admit that. It's just that the prestige has been watered down a lot this year.

This is a very generous extension of USAMO qualification - thank you CAMC members for taking this burden upon yourselves and supporting many underclassmen in their quest for a deeper comprehension of mathematics.

I think the floor should be lowered so the ratio of regular qualifiers to index qualifier is 2:1 again. It's a lot fairer than inflating the number of index qualifiers. I encourage the CAMC board to consider this further expansion this year.

I want to take a moment to extend my deepest gratitude to Professor Dunbar and the CAMC.  I appreciate this kind decision.

Even though I'm graduated and out of the running for the AMC series now, I'd like to extend my thanks to Prof. Dunbar, the CAMC, and the USAMO graders who so generously agreed to grade the 57 extra tests.  You're going to make those 57 students very, very happy!  Good luck with the grading.

Actually, I'm surprised it was only 57 more.  I was expecting at least 100 or 150, or some other number that would probably render this solution unfeasible.\

Ooh, and another kid from MN got in!  :)

[quote="probability1.01"]Well, if you can prove that any even number greater than 2 can be written as the sum of two primes, we'll let you take the USAMO.[/quote]Actually, if you could do that they'd probably put you on the IMO team.

[quote="1234567890"]In my opinion, it's not fair that that the proportion of regular qualifiers to floor qualifiers is much less than before. I mean, it should be 2/1, but its more like 4/3. It cuts off a lot of juniors and seniors with more proof-writing experience who would do at least decent on the USAMO (Like me. I got a 216.5 for an index, but I'm pretty sure I'd progress significantly on at least any #1/4 Counting/Algebra/NT problem, and possibly even #2's/#5's.), versus a 8th/9th grader who barely got in with no proof-writing experience, and would goose egg the USAMO.

I don't know, it just doesn't seem right that there are even more underclassmen who've scraped by versus more experienced upperclassmen. :([/quote]

Proof-writing experience is the problem? I would that that's not too hard, as long as you understand what rigorous mathematics is about. I myself, a freshman who now qualified for USAMO, know how to write proofs. My problem is actually being able to solve the very difficult USAMO problems.

I've got several things to contribute to the topic.  The first point is in response to Chenyu's posts.

I've heard a few others express problems with the USAMO being "cheapened" or whatnot, but really, so what if there are 400 qualifiers?  The USAMO is still just as difficult and competitive as it was before, people are just getting closer and closer to each others' skill level.  With the rise of AoPS, so to speak, a very significant chunk of math students now have access to the exact same strong, "advanced," problem solving resources.  On top of that, keep in mind that the ultimate point of the International Math Olympiad isn't to flex muscle (I know you have a lot of Mathematical Muscle... I still remember You and Gaku trading 1st place finishes with perfect scores at FAMAT geometry regionals), but to keep interest in math high and advance everyone's ability.  In that spirit, I'm confident that, were the resources available, the USAMO would be open to significantly more than 375 people each year for the sole purpose of exposure to higher level proofs and whatnot.  Finally, there will still be a score on the USAMO.  You can still make anywhere between 0-42, let that distinguish you, if you're looking for distinction.

With regards to the Senior-Junior/Sophomores-and-below split, I think that's a product of improving math education (again, this site is a case in point) and the "training" aspect of the USAMO.  As the president of my school's math club, I try, first and foremost, to get our promising freshmen and sophomores to heighten their understanding and love for math, because by the time they're my age, they'll have surpassed me.  Improving myself is secondary.  The USAMO split is a similar idea.  No, the Freshmen and Sophomores don't have as much proof-writing experience as the Juniors and Seniors, but the USAMO is a good way to gain that experience (of course, so are other contests like the USAMTS, which I encourage everyone to join).

Regardless of either of the above arguments, the CAMC definitely did the right thing WRT advancing math education.  The rules of the contest this year stated that a floor would be in-effect, which lead many top 9th and 10th graders to take the AMC12 instead of the AMC10.  Dropping the floor value would have been unfair for the best students taking the AIME.  I applaud the CAMC for both reversing their original decision and for the extra time that will be spent grading the papers.  There are almost 200 additional USAMO qualifiers over last year, so such an undertaking is definitely laudable.  Of course, changing the rules to remove the floor value before the administration of the 2007 AMCs would be perfectly fair, but we'll see what the CAMC figures out.

Finally, I'd just like to remind everyone that math isn't about winning contests left and right, it's about the beauty of advancing from what seems like an unapproachable problem to a rigorous solution.  It's about finding friends who appreciate that same beauty, and appreciating their solutions in turn.  And finally, it's about advancing the world (Where would physicists be without Euler?).  None of these last three require you to qualify for a contest in order to pull off.  Keep that in mind.

~Youlian Simidjiyski

[quote="themonster"]Wow, now my name is on the list twice!

Maybe its because I'm in the unique position of getting a 16 on the AIME :D

 Actually I think it's because initially I qualified only because of the every state gets a qualifier rule, but now I make the normal floor.

Should I contact them about this (I might get registered twice or something)?

-Ben Dozier[/quote]

I'd keep quiet, your probably the first person to double qualify for the USAMO. Or you could contact them. Your choice.

[quote="1234567890"]In my opinion, it's not fair that that the proportion of regular qualifiers to floor qualifiers is much less than before. I mean, it should be 2/1, but its more like 4/3. It cuts off a lot of juniors and seniors with more proof-writing experience who would do at least decent on the USAMO (Like me. I got a 216.5 for an index, but I'm pretty sure I'd progress significantly on at least any #1/4 Counting/Algebra/NT problem, and possibly even #2's/#5's.), versus a 8th/9th grader who barely got in with no proof-writing experience, and would goose egg the USAMO.

I don't know, it just doesn't seem right that there are even more underclassmen who've scraped by versus more experienced upperclassmen. :([/quote]

If you got a really good index score that would have quallified even without the expansion, that still has the same honor as it did before so don't complain. Besides, I don't think letting more people take the USAMO would hurt you at all. It just gives some people more proofwriting experience.

[quote="1234567890"]In my opinion, it's not fair that that the proportion of regular qualifiers to floor qualifiers is much less than before. I mean, it should be 2/1, but its more like 4/3. It cuts off a lot of juniors and seniors with more proof-writing experience who would do at least decent on the USAMO (Like me. I got a 216.5 for an index, but I'm pretty sure I'd progress significantly on at least any #1/4 Counting/Algebra/NT problem, and possibly even #2's/#5's.), versus a 8th/9th grader who barely got in with no proof-writing experience, and would goose egg the USAMO.

I don't know, it just doesn't seem right that there are even more underclassmen who've scraped by versus more experienced upperclassmen. :([/quote]

I think this is AMC's philosophy to encourage younger students. You could make the same argument about MoSP- why not throw away the 25 slots reserved for freshman and give them to upperclassmen?

[quote="Phelpedo"]
I think this is AMC's philosophy to encourage younger students. You could make the same argument about MoSP- why not throw away the 25 slots reserved for freshman and give them to upperclassmen?[/quote]

I wouldn't complain. All Red MOP's ever done is given an unfair advantage to people who didn't screw up the AIME in 9th grade.

12...90 has a point though, and I have to say I agree with him. The upperclassmen/underclassmen ratio should be greater than 1:1, probably much greater. It'd be nice if CAMC tried to keep it  at a constant ratio, like 3:2 (including frosh/sophomores who qualified the regular way). That isn't to say that we should stop using a floor score, but if the ratio is going to drop to 4:3 or 5:4, the just take out the part about "favoring those students who take the more mathematically rigorous AMC 12 exams" and institute a floor index in future years. I mean, geez, it's almost to the point where Red MOP is as competitive as Blue MOP.

Regarding the supposed decrease in prestige of the USAMO:
Keep in mind, back before 2000, the USAMO only took 150 people (plus state qualifiers).  Then in 2000, they expanded it to roughly 250.  In 2002, due to a glitch in the floor (cutoff was 210 and someone got 150/6), 326 people made it.  This, and the expansion, is not a sudden increase in the number of students selected; it's a gradual process of expansion happening over time.  It seems to me that along with the increase in the number of people selected, there's an increase in how big a deal it is to take the USAMO.  If this is the case, then even if you think the prestige is diluted by more people qualifying (which I don't), then the total prestige is increasing, so the prestige per student remains constant.

Regarding the ratio of students in each selection group:
The AMC intended for this to be a 2:1 ratio.  In the past (except maybe 2002), this has been the case.  However, this year, maintaining a 2:1 ratio while inviting all the people the stated selection procedure obligated them to invite had undesirable results.  So the ratio was changed.  Prof. Dunbar mentioned in his post that the selection procedure might be rewritten slightly next year, so this might do something to fix the ratio more firmly.

Though I am a junior and this new development does not affect me personally, I would like to thank the CAMC and offer my opinion that they made the correct choice.  Given the situation, it would have been unfair to count the AMC 10 and the AMC 12 as equal in some way or to try to balance them.  Certainly, upping the floor and decreasing the qualifiers is not an option.  I think that, all things considered, the CAMC was correct in its choice.

I feel I need to respond to the multiple posts about "prestige" of the USAMO.  I hardly beleive it matters.  The USAMO exists for two purposes:

1). Get more children involved in difficult mathematics.
2). Act as a "try-out" for the IMO team.

Certainly, an expansions works to further the first goal.  Secondly, the increase in USAMO takers makes it more likely that a future IMO gold medalist hiding in the rough will be found.  Though a future IMO gold medallist not qualifying for USAMO sounds preposterous, we must remember that on "Any given Sunday" anything can happen.  A USAMO expansions furthers both these goals.

I understand that personal prestige is important.  However, I think we can put aside our personal aspirations for glory in order to support the CAMC's decision, which will ulitmately help other students and the IMO team.

JB

[quote="DPopov"]I guess we can all expect a difficult USAMO after the higher admission rates this year. ;)[/quote]

EH except USAMO was written a year ago and the expansion happened after USAMO was written, so it's hard to predict the difficulty of USAMO.

Unfortunately, I'm in 11th grade and got a 112.5 on the AMC 12 and an 8 on the AIME :(
If only they took the top [u][b]2[/b][/u] scorers in each state (Kyle S beat me with a 118.5/8).  But I guess there's always next year.  Ironically, I need to work on my AMC 12 score more than my AIME score.

2005 USAMO Qualifier Grade Distribution:

13th Grade - 1    (0.39%)
12th Grade - 78  (30.12%)
11th Grade - 63  (24.32%)
10th Grade - 72  (27.80%)
9th Grade - 38    (14.67%)
8th Grade - 6      (2.32%)
7th Grade - 1      (0.39%)

Total = 259
Average Grade = 10.65

2006 USAMO Qualifier Grade Distribution:

12th Grade - 119  (27.67%)
11th Grade - 90    (20.93%)
10th Grade - 134  (31.16%)
9th Grade - 63      (14.65%)
8th Grade - 19      (4.42%)
7th Grade - 4        (0.93%)
Unknown - 1         (0.23%)

Total = 430
Average Grade Level = 10.50

[quote="qvc122"]When I checked the AIME (I+II) stats from AMC site, my counts for 9th graders with score above 8 is 96 people. How come there are only 63 qualifiers from the freshman group?[/quote]

Taiwan?

i think i was one of those 57
sophomore, 124/8

yay

So this means that I also qualified for the USAMO.  Awesome!

Thank you very much for your generosity, all the CAMC members!

[quote="themonster"]Wow, now my name is on the list twice!

Maybe its because I'm in the unique position of getting a 16 on the AIME :D

 Actually I think it's because initially I qualified only because of the every state gets a qualifier rule, but now I make the normal floor.

Should I contact them about this (I might get registered twice or something)?

-Ben Dozier[/quote]

I also noticed it right now. They don't seem to be changing it. Sorry but you have to hand in your exam papers twice. Be careful to start on them early as the scores of both papers are averaged.  ;)


Let $ a,b,c\in[\minus{}1,1]$ such that $ a^{3}\plus{}b^{3}\plus{}c^{3}\equal{} 0$ and $ abc >\frac{1}{8}$. Show that $ abc> (a\plus{}b\plus{}c)(ab\plus{}bc\plus{}ca).$

Write the inequality as $ 3abc > 3(a\plus{}b\plus{}c)(ab\plus{}bc\plus{}ca)$
Since $ \minus{}3abc \equal{} a^{3}\plus{}b^{3}\plus{}c^{3}\minus{}3abc \equal{} (a\plus{}b\plus{}c)(\sum a^{2}\minus{}\sum ab)$
we have $ a\plus{}b\plus{}c < 0$
By substituting the above expression for $ 3abc$, it suffices to show
$ (a\plus{}b\plus{}c)(\sum ab\minus{}\sum a^{2}) > 3(a\plus{}b\plus{}c)(ab\plus{}bc\plus{}ca)$
$ \Leftrightarrow\sum ab\minus{}\sum a^{2}< 3(\sum ab)$
$ \Leftrightarrow (a\plus{}b\plus{}c)^{2}> 0$
which is true.


adade tabeii $n$ dade shode ast..donbaleyee $a_{1},a_{2},\dots,a_{2n}$ yek donbaleye martabe $n$ namide mishavaad agar har yek az adadhaye $1$ ta $n$ , daghighan dobar dar in donbale amade bashand. va agar $a_{i}=a_{j}=k$ , dashte bashim $|i-j|=k$. baraye mesal donbaleye
                                         $3,5,2,3,2,4,5,1,1,4$
yek donbaleye martabe $5$ ast.. sabet konid agar donbaleye az martabe $n$ vojood dashte bashad. angaah $n=4k+1 n=4k$

majmooe andis ha ra hesab mikonim(farz konid k dar jaygahe b(k) va
b(k)+k amadeh bashad)
n(2n+1)=1+2+3+...+2n=majmooe andis ha=(b(1)+(b(1)+1))+
(b(2)+(b(2)+2))+...+(b(n)+(b(n)+n))=2(b(1)+...+b(n))+n(n+1)/2

pas agar do tarafe tasavi ra be hange 2 begerid:

  n=n(n+1)/2 (mod 2) pas  2n=n^2+n (mod 4) pas n(n-1)=0 (mod 4)
 pas n=4k+1 ya n=4k


quadratics
number theory proposed
number theory

If there exists number $ x $ satisfying [tex] \lbrace{x^2}\rbrace+\lbrace{x}\rbrace = r [/tex],then we have infinitely many numbers satisfying that condition too.
Let [tex] x=\frac{p}{q} [/tex] then $ x+nq $is a example for the formula.

Yes, that's one obvious result.  The other two obvious ones are $r < 2$ and $r \not= 1$.  Other than that, everything else remains, and it's still interesting.

Further, if $q$ is even then we can have $x+nq/2$.

[quote="Michael Lipnowski"]For which $r \in Q^+$ do there exist infinitely many $x \in Q^+$ such that $\{x^2\} + \{x\} = r$ ?
Note: $Q^+$ denotes the set positive rationals while $\{x\} = x - [x]$[/quote]

As said before, one solutions means infinite solutions. I will look here only for 1 solution every time!! very important!!!

let $x$ be $\displaystyle\frac ab$, then we have $\displaystyle r=\{\frac{a^2}{b^2}\}+\{\frac{ab}{b^2}\}$ so $\displaystyle r = \frac{(a+b)a}{b^2} \bmod 1$

now r is either in [$0,1$[ or in ]$1;2$[

suppose $r$ is in [$0;1$[: the answer is: any $r$ of the form $\displaystyle\frac{(a+b)a}{b^2}$ with $a,b$ naturals and $b>\frac{1\pm\sqrt5}{2}a$.

suppose $r$ in ]$1;2$[: we get a<b (fulfills both below 1) so the answer is: any $r$ of the form $\displaystyle\frac{(a+b)a}{b^2}$ with $a<b$ naturals and $b<\frac{1\pm\sqrt5}{2}a$.

Peter VDD: I think the question is more complicated.  First, $\frac{a(a+b)}{b^2} = r (mod 1) \rightarrow \frac{a(a+b)}{b^2} = r + n$ for some non-negative integer $n$.  Second, you give some form for the $r$'s which work (actually, since you gave two roots to a quadratic, your form contradicts itself).  We can obviously say that $r$ works iff $r = \frac{a(a+b)}{b^2} - n$ for some non-negative integers $a,b$, and $n$.  Sorry for not being more specific to begin with, but I'm looking for a form which is as explicit as possible.


Does anyone know of any freeware that operates like GarageBand that can work on PCs? Thanks!

(I don't know exactly which forum this belongs in, sorry.)

There's not much freeware like GarageBand; even GarageBand isn't free.

Audacity is an audio editor, but it doesn't have sound clips built in.
Adobe Soundbooth CS4 is similar, but costs money.
Same with Acoustica Mixcraft 4.

Thanks for your reply. I have been using Audacity and I find it sufficient for my needs. (currently, at least)


$n$ real numbers was given around the circle.One of them equals to $1$ and sum of them is zero.Show that:
i/There exists 2 adjacent number which differs at least $\frac{n}{4}$
ii/There exists one number differs two adjacent number's a.m. at least $\frac{8}{n^{2}}$
Improve for $\frac{k}{n^{2}}$ when $k\geq 8$
Point a exam for case $n=30, k=\frac{1800}{133}$

I have edited it!As I think this problem belongs the hardest issue of All Soviet Union Olypiad.Who has any idea? :o

$n/4?$ i think it would be $4/n$. The solution for above problem is very simple.
Suppose for the shake of contraction that: for any $2$ adjacent numbers, they differ $<4/n$. Let $a_{1},a_{2},..,a_{n}$ be the numbers in order and $a_{1}=1$. We have $a_{1}-a_{2}<4/n, a_{2}-a_{3}<4/n$, then $a_{3}>a_{1}-8/n$, similary, $a_{k}>a_{1}-4(k-1)/8$ for all $k=2,3,...,[\frac{n}{2}]$.
In the same way, we have $a_{n}<a_{1}-4/n, a_{n-1}>a_{n}-4/n>a_{1}-8/n$. Similary, $a_{n-k}>a_{1}-4k/n \forall k=0,1,...,[n/2]$.
Thus, we have $a_{1}+a_{2}+...+a_{n}>na_{1}-2(4+8+...+4[n/2])4/n>0$ (a contraction).
b/ between two adjacent numbers $a, b$ in order, we write the number $a-b$. Considering the set of $n$ new numbers. Using i/, we have $max|a-b|\ge 4/n$. and the are two adjacent numbers $a-b$ and $b-c$ which  differ at least $4/n.4/n=16/n^{2}$. Thus, $\frac{a+c}{2}-2b\ge 8/n^{2}$.

If $k>8$. We can take  $...1-8/n,1-4/n,1,1-4/n,1-8/n....$

I think my post is not absolutely correct, but i believe the access is right


If for positive real numbers $ a, b, c, d$ :
$ c^2\plus{}d^2\equal{}(a^2\plus{}b^2)^3$

Prove:
$ \frac{a^3b^3}{cd} \ge 1/3$

[quote="gorrina"]If for positive real numbers $ a, b, c, d$ :
$ c^2 \plus{} d^2 \equal{} (a^2 \plus{} b^2)^3$

Prove:
$ \frac {a^3b^3}{cd} \ge 1/3$[/quote]
Try $ a\rightarrow0^\plus{}.$


let M be a finite subset of real numbers, such that given any 3 elements distint of M, we can choose two of them whose sum belongs to M too. ¿Which is the maximum number of elements that M can have?

sorry for my english

the answer is 7.assume that M has more than 3 positive real numbers and take 4 of them which are the largest such as a>b>c>d.it is easy to recognize that a=b+c if we take a,b and d we cah achieve that none of the numbers a+b,a+d and b+d belong to the set M.It is also valid for M which has more than 3 negative real numbers.thus,M can have at most 3 positive and 3 negative real numbers and zero,leading to M has at most 7 elements.as an example M has elements 3,2,1,0,-1,-2,-3 .


Find all functions $f: \mathbb{Z} \rightarrow \mathbb{Z}$ (where $\mathbb{Z}$ is the set of all integers) such that \[ 2000f(f(x)) - 3999f(x) + 1999x = 0\textrm{ for all }x \in \mathbb{Z}. \]

I assume the answer is $f(x)\equiv x$.  Treat it as a recursion...

Rewritting  $2000(f(f(x)) - 2f(x) + x) = x - f(x)$ this gives $f(x) = x + 2000*g(x)$ with $g(x) \in \mathbb{Z}$

This gives $1999 g(x) = 2000 g(x+ 2000g(x))$ with $g(x) = 2000 h(x)$ with $g(x) \in \mathbb{Z}$ since $gcd(1999,2000) = 1$

Again $1999*h(x) = 2000*h(x+4000000*h(x))$

And so on. The only possiblity is $g(x) = 0$.

$f(x) = x$ works and is the only solution.

Correct ?

[hide=a little late to the party]Observe that $f(f(x))-f(x)\equiv\tfrac{1999}{2000}\left(f(x)-x\right)$, so for any $x$ and all $n\ge 0$\[
f^{n+1}(x)-f^n(x)=\left(\frac{1999}{2000}\right)^{\!n}\left(f(x)-x\right),
\]which, if $f(x)-x\ne 0$, is not an integer when $n$ is large (contradiction).

So $f(x)\equiv x$.[/hide]


Can we recover the plan IR² whit discs ?  ( I think that is not possible , we will have some points even if we use discs with arbitray small radios )

I take it that you want to to write $ \mathbb{R}^2$ as the union of a pairwise disjoint collection of discs of arbitrarily varying radius.

Now: do you mean open discs or closed discs?

yes, that what I meant , is it possible to whrite IR² as disjoint uninon of closed discs ( and what about open disc too ? )

Closed disks? Choose them all of radius zero.

Open disks? $ \mathbb{R}^2$ is connected, and can't be partitioned into a disjoint union of nonempty open sets.

How about if we disallow taking all the disks to be points, either by specifying positive radius or by requiring a countable collection?

Pick a one-dimensional slice, and apply the Baire category theorem. See [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?&t=113888]here[/url].

I didn't mention that the union must be countable , the radios must be strictly positives ! but I didn't understand the relation with the post that gives jemrry ! can you give more explanations ?

A measure argument together with the positive radii implies that the union is countable.

The intersection of a closed disk and a line is a closed interval. The real line cannot be written as the disjoint union of countably many closed intervals unless one is the whole thing.

please , i can't see how you deduce that the union must be countable !! I can't imagine that , could you please prouve that rigorously , of course the deduction will be immediat ! dont forget that some discs can be tangent , so any point  can be in at most two discs ( when it's a tengent point of two discs )

so if i understand , we can't write IR as a uninon of disjoint closed intervals , that way we can't recover the plan  ! and a union of closed se that recover IR if it exist must be countable !!? can any one clarify with proof  :?:

[quote="yassinus"]dont forget that some discs can be tangent , so any point can be in at most two discs[/quote]OK, now you're changing the rules.
That just means you have to choose the line to avoid the countably many bad points.

so recovering is not possible ? how to prove it !


LaTeX
inequalities
inequalities unsolved

Let $x_1,x_2,..x_n \leq -1$.Prove that:
   $x_1x_2..x_n+ \frac{1}{x_1}+...+\frac{1}{x_n}\geq \frac{1}{x_1x_2..x_n}+x_1+x_2+...+x_n$

[color=red]Edit by Megus: Please write in LaTeX whole expression not just a part of it - it'll be more readable this way[/color]

by letting $x_i=-a_i$ , $a_i >0$ it is easy to see that above inequality is trivially true for $n$ even and false for $n$ odd.

I don't know what do you mean,Megus??
Can you post your solution more detail?????


Given any odd integer m, prove that there exists an odd integer n and an integer r such that

mn + 1 = 2^r

Hint:

[hide]This is just that some 2^r  :equiv: 1 mod m. [/hide]

Solution:

[hide] 2^r :equiv: 1 mod m.

We know that 2 :equiv: 2 mod m. Since the modular pattern will repeat, we also know that if the power of 2 has order k modulo m, 2^k  :equiv: 2 mod m. Thus, 2^(k-1)  :equiv: 1 mod m, and we have found a solution r = k-1.

[/hide]


A set of integers $A$ is [i]fat[/i] if each of its elements is greater than or equal to the number of elements in $A$. Let $g_n$ denote the number of fat subsets of ${1,2,\ldots,n}$. The empty set is considered fat.

Define $g_n$ recursively
Find an explicit formula for $g_n$

just an idea, but I can't continue

[hide]

in the set $\{ 1,2,3...n \}$ we can find $\binom {n+1}{0}$ fat subsets with no elements, the empty set.
If we take all subsets containing one elements, they're all fat, and they are $\binom n1$.
fat subsets containing two elements can't contain the number 1, so we have $\binom {n-1}{2}$ fat subsets containing 2 elements, and so on.
the problem I found in this way is to distinguish even and odd n, cause

for n odd, $g_n=\sum_{k=0}^{\frac{n+1}{2}}\binom {n+1-k}{k}$
for n even, $g_n=\sum_{k=0}^{\frac{n}{2}}\binom {n+1-k}{k}$
how to unificate upper bounds of $k$????
[/hide]

[hide]
Let $S_n = \{1,2,\ldots,n\}$. If $T$ is a fat subset of $S_n$ then it is clearly a fat subset of $S_{n+1}$. Also, if $T$ contains only elements that are $|T|+1$ or greater, $T \cup \{n+1\}$ is also a fat subset of $S_{n+1}$.

If $|T| = 0$, $T$ can be $\emptyset$.

If $|T| = 1$, $T$ can be $\{2\}, \{3\}, \ldots, \{n\}$, but not $\{1\}$.

If $|T| = 2$, $T$ can be any two elements from $\{3,4,\ldots,n\}$, but cannot have $\{2\}$.

So if $|T| = k$, we have $\binom{n-k}{k}$ fat subsets of $S_n$ such that $T \cup \{n+1\}$ is a fat subset of $S_{n+1}$. Summing over all possible $k$, this becomes $F_n$, the $n$th Fibonnaci number, where $F_0 = F_1 = 1$. The result can be intuitively proved by looking at the diagonal lines created on Pascal's Triangle (pretty cool if you can see it).

So we have $g_{n+1} = g_n+F_n$. Consequently, $g_n = F_{n+1}$ by looking at the first few cases and noting that it satisfies the Fibonnaci recurrence. [/hide]


Let $ \displaystyle(x_{n})$be a sequence of strictly positive real numbers such that $ \lim(\frac{x_{n\plus{}1}}{x_{n}})< 1$. Show that for some $ r$ with $ 0 <r<1$ and some$ C > 0$, then we have $ 0<x_{n}<Cr^{n}$ for all large $ n\in\mathbb{N}$. use this to show that $ \lim(x_{n})\equal{}0$.

How do I start this, and then show $ 0<x_{n}<Cr^{n}$?

First step: let $ s\equal{}\lim\frac{x_{n\plus{}1}}{x_n}.$ Now choose $ r$ such that $ s<r<1.$

Second step: note that by the definition of limit, given $ \epsilon>0,$ there exists $ N$ such that for all $ n>N,$ $ s\minus{}\epsilon<\frac{x_{n\plus{}1}}{x_n}<s\plus{}\epsilon.$ Do that for $ \epsilon\equal{}r\minus{}s,$ so that for $ n>N,$ $ \frac{x_{n\plus{}1}}{x_n}<r,$ which we rewrite as $ x_{n\plus{}1}<rx_n.$

I'll let you supply the remaining steps.


inequalities
geometry
geometric transformation
reflection
trigonometry
circumcircle
geometry proposed

Let $ABC$ be a triangle right at $A$.Let $E$,$F$ be the points resprctively on the rays $AB$,$AC$ such that $BE=CF=BC$.$M$ is a point on the circle with diameter  $BC$.Prove that $MA+MB+MC\le EF$

A nice and easy geometrical inequality ! [hide="Here is a short proof."]I suppose w.l.o.g. $[MA]\cap BC\ne \emptyset\ ([MA]\cap BC=\emptyset\Longrightarrow M: =M'$, where
the point $M'$ is the reflection of the point $M$ w.r.t. the line $BC)$ . Let $A\ge 90^{\circ}$,
i.e. $\boxed {\ \sqrt{(a+b)^2+(a+c)^2}\le EF\ }$ and denote $m(\widehat {MBC})=\phi\in \left[0,\frac{\pi}{2} \right]$.
Therefore, $MB=a\cos \phi$ and $MC=a\sin \phi$. From the [b]Ptolemeu's inequality
[/b] $MA\cdot BC\le MB\cdot AC+MC\cdot AB$ results $MA\le b\cos \phi+c\sin \phi$. Thus,
$\boxed {\ MB+MC+MA\ }\le a\cos \phi +a\sin \phi +(b\cos \phi +c\sin \phi) =$ $(a+b)\cos \phi +(a+b)\sin \phi\le \sqrt{(a+b)^2+(a+c)^2}=\boxed {\ EF\ }\ .$[/hide]

Using most part of the work made by Nicula, one can prove that MA+MB+MC = AN where N is the point of intersection beteween AM and c(AEF).  This prove the claim.

Edit

Now I have got a purely geometric proof of this fact:

MA+MB+MC = AN

[quote="Virgil Nicula"]What is c(AEF) ?[/quote]

c(AEF) is the circumcircle of triangle AEF.
Here is the picture that illustartes the idea. I wiil complete later the post with the necessary comments

Let c(AEF) be the circumcircle of AEF, let P be the intersection of EC with c(AEF), let N be the intersection of AM with c(AEF),  and let R the point of intersection between PN and c(PCF). By angle chasing one can see that CRF is congruent with BMC. If T is the inetersection of AN with the parallel to CM trhough R then MT = CR = MB furthermore, as <ABC =  2<AEC, then TN= TR = MC.  Then AN = MA+MB+MC as claimed.


do there exist k such that for real a,b
(a^2+b^2)/2<=kab?

No.

As $a$ increases without bound and $b=\frac{1}{a}$, $ab=1$ but $\frac{a^{2}+b^{2}}{2}$ increases without bound.


The digits 2, 3, 4, 7 and 8 are each used once to form a five-digit number. what is the probability that the tens digit is odd and the number is divisible by 4? Express your answer as a common fraction.

There are a total of $ 5 \cdot 4 \equal{} 20$ ways to put the last two digits in the number. Only regarding the last two digits in the number is okay. Divisibility rule for $ 4$ is if the last two digits are divisible by $ 4$. The possible last two digits that work are $ 32$ and $ 72$. This is $ 2$ out of the $ 20$ possible last two digits, so our probability is $ \frac{2}{20} \equal{} \boxed{\frac{1}{10}}$


Hello everybody, long time no see  :D I am really busy at many things in my school and my vacation. Now, I came back and I want to share with you a very nice problem and some very nice solutions for this. I have known that it can be solved easily by canhang_2007's method (You can find it somewhere in Mathlink Forum) but I am interested in finding out another solution for this and I found something. Here is it:
[b]Problem: [/b]Let $ a,b,c\in \mathbb{R}$ such that $ a \plus{} b \plus{} c \equal{} 3$. Prove that:
\[ a^3b \plus{} b^3c \plus{} c^3a \plus{} 6abc\le 9
\]
Enjoy !! Let try solve it  :wink:

[quote="zaizai-hoang"]
[b]Problem: [/b]Let $ a,b,c\in \mathbb{R}$ such that $ a \plus{} b \plus{} c \equal{} 3$. Prove that:
\[ a^3b \plus{} b^3c \plus{} c^3a \plus{} 6abc\le 9
\]
[/quote]
Maybe $ a,$ $ b$ and $ c$ are non-negative? If so then it follows from my inequality:
http://www.artofproblemsolving.com/Forum/viewtopic.php?t=175936

I proved that:
\[ 9(a^3b \plus{} b^3c \plus{} c^3a) \plus{} 18abc(a \plus{} b \plus{} c) \le (a \plus{} b \plus{} c)^4, \forall a,b,c\in \mathbb{R}
\]
When $ a \plus{} b \plus{} c \equal{} 3$ so we have above inequality  :roll:

[hide]to arqady: your post is really special. It is equal to 3333. I think you shouldn't post more (I am kidding)  :D [/hide]

Let $ a,b,c$ be real numbers such that $ a \plus{} b \plus{} c \equal{} 3.$Prove that:
\[ a^{3}b \plus{} b^{3}c \plus{} c^{3}a \plus{} 6abc\leq 9
\]
What do you think about the following solution  :wink:

The inequality is equivalent to:
\[ (a \plus{} b \plus{} c)^{4}\geq 18abc(a \plus{} b \plus{} c) \plus{} 9(a^{3}b \plus{} b^{3}c \plus{} c^{3}a)
\]

\[ \sum a^4 \plus{} 6\sum a^2b^2 \minus{} 5\sum a^3b \plus{} 4\sum ab^3 \minus{} 6abc \sum a \ge 0
\]

\[ \Leftrightarrow \frac {3\left( \sum a^{3} \minus{} 3 \sum a^{2}b \plus{} 6abc\right) ^{2} \plus{} \left( \sum a^{3} \plus{} 6\sum a^{2}c \minus{} 3\sum a^{2}b \minus{} 12abc\right) ^{2}}{ 18[(a \minus{} b)^{2} \plus{} (b \minus{} c)^{2} \plus{} (c \minus{} a)^{2}]}\geq 0
\]
The inequality was proved. The equality holds on $ a \equal{} b \equal{} c \equal{} 1$
[b]
I have made mistake in typing...now it is ok[/b]  :D

Of cause ( wihtout litle mistake ), zaizai-hoang!
The $ b \equal{} a \plus{} x,$ $ c \equal{} a \plus{} y$'s way gives it. :)
Nice inequality, zaizai-hoang!

Thank you, I have made mistake in typing. I have edited it. Have any nice solution for this? I have another one  :D

It seem to be solve easily by theorem of Võ Quốc Bá Cẩn, isn't it ?
PS: Hello, zaizai. I think you don't remember me :D

Yes, I have known about this. As I said above, it can be solved by Canhang_2007"s method :wink: It is just a consequence of his theorem. But in this topic, I want to find out some different from what we have known before. I have posted the first solution what I want to share with everyone.

@nguoivn: I think I have known you before  :wink:

[quote="zaizai-hoang"]

\[ (a \plus{} b \plus{} c)^{4}\geq 18abc(a \plus{} b \plus{} c) \plus{} 9(a^{3}b \plus{} b^{3}c \plus{} c^{3}a)
\]

\[ \Leftrightarrow a^{4} \plus{} b^{4} \plus{} c^{4} \plus{} 6\sum a^{2}b^{2}\geq 5(a^{3}b \plus{} b^{3}c \plus{} c^{3}a) \plus{} 4(a^{3}c \plus{} c^{3}b \plus{} b^{3}a)
\]
[/quote]
I don't think so. :wink:

You're right, arqady. It should be \[ \sum a^4 \plus{}6\sum a^2b^2 \minus{}5\sum a^3b \plus{}4\sum ab^3 \minus{}6abc \sum a \ge 0\] and my theorem works here:)


limit
integration
real analysis
real analysis unsolved

Let $f: [0,1]\to\Re$ continous and $k\in N$. Compute:
   $\lim_{n\to\infty}\frac{1}{n^{k}}\sum_{1\leq i_{1}< i_{2}<...<i_{k}\leq n}f(\frac{i_{1}}{n})\cdot f(\frac{i_{2}}{n})\cdot ... \cdot f(\frac{i_{k}}{n})$

let's consider the case when $k=2$. Then

$f(1/n)+\cdots+f(n/n))^{2}=\sum_{k=1}^{n}f^{2}(k/n)+2\sum_{1\leq i<j\leq n}f(i/n)f(j/n)$.
Devide by $n^{2}$ and take the limit as n converges to $\infty$ and you get that your limit is

$\frac{1}{2}\left(\int_{0}^{1}f(x)dx\right)^{2}$.

If $k\geq 3$ I think that you should use the multinomial formula for calculating this limit.


It is not unlikely that this has been posted before. Sorry if it has.

If $\log_{3n}45=\log_{4n}40\sqrt3$, find $n^3$.

Give a hint first if you wouldn't mind. :D

[quote="riddler"][quote="AntonioMainenti"]
Give a hint first if you wouldn't mind. Mr. Green
[/quote]
Sorry I didnt see. :blush:[/quote]No problem. How did you get it though?

[quote="riddler"][hide="Solution"]
$(3n)^x=45$
and
$(4n)^x=40\sqrt3$
Dividing these $2$ equations we get,
$[\frac{3}{4}]^2=\frac{3\sqrt3}{8}$
From this $x=\frac{3}{2}$
Put it in the $1$st equation and we get my answer
[/hide][/quote][hide]Of course you mean $\left(\frac34\right)^x=\frac{3\sqrt3}8$. But when you put in $x=\frac32$ you get $n^3=75$, which I checked is right.

I wasted so much time on this problem never thinking to rationalize the denominator. Thanks.[/hide]


The negation of the statement "No slow learners attend this school" is:

$ \textbf{(A)}\ \text{All slow learners attend this school} \\
\textbf{(B)}\ \text{All slow learners do not attend this school} \\
\textbf{(C)}\ \text{Some slow learners attend this school} \\
\textbf{(D)}\ \text{Some slow learners do not attend this school} \\
\textbf{(E)}\ \text{No slow learners do not attend this school}$

[hide="I am frequently wrong with these problems"]The statement is false when at least one slow learner attends the school, so $ \boxed{\textbf{(C)}}$.[/hide]

by eleminating it is easy to find $ \boxed C$


$A\equiv\{1,2,\cdots,n\}$,Find The Min Number Of K,If There Exist K
$B_{1},B_{2},\cdots,B_{K}$ Which Have Proper s Elements.Such That For
Any C$\subseteq$A,and C Have Proper t Elements.$0\leq s \leq t \leq n$
there exist $B_{i}\subseteq$C

It is ok now。and it's time to solve the problem.
I have to explain it.
if s=1,t=2  then we can get K=n-1
because if K <= n-2  we can get
$\{a\},\{b\}\neq B_{i}$ then $\{a,b\}$  is not satisfy


Prove that there are no positive integers a,b,n > 1
such that a^n - b^n divides a^n + b^n

we may easily take $(a,b)=1$ then it is esily seen that $a^{n}-b^{n}| a^{n}+b^{n}$ implies $a^{n}-b^{n}| xa^{n}-yb^{n}$ so by bezout theorem
$a^{n}-b^{n}=1$ but this is imposible for $n>1$ and $a,b$ natural :wink:

[quote="Albanian Eagle"] it is esily seen that $a^{n}-b^{n}| a^{n}+b^{n}$ implies $a^{n}-b^{n}| xa^{n}-yb^{n}$ [/quote]
I think that from $a^{n}-b^{n}|a^{n}+b^{n}$ follows only $a^{n}-b^{n}|xa^{n}-y^{n}$ for $x,y$ which both even or odd. Hence we get only that $a^{n}-b^{n}|2$, but it is also enough.


Because my previous post has been lost due to server problems, I'll now post the problems of the Chinese TST 2004 again.

[Edit: corrected a bug in problem 3.]

Hi wpolly

"The camp lasted two weeks from 16 March to 2 April. Eight tests with 24 problems are held during that time."

Can post the other problems too, please ? It would be very nice.  :)

you might also change the fact that "each problem is worth 21p" :D

No, it's correct, that's the way China TST is marked.

Well, I'll post them along with the Chinese TST 2003 before the IMO.

Can you please explain me problem 3?
I don't understand it, it seemes I can find a counter-example!

Yes, I also noticed it is wrong. But it seems very interesting, so please someone post the correct version.

Yeah, we need to inform wpolly about this problem, problem #3. It is not always true, as others have pointed out.
The problem from [b]tst04.pdf[/b] states as follows:
Let integer $k\geq2$, $n_1,n_2,...,n_k$ are positive integers, $a,b\in Z^{+}$ satisfy
\[ \left(1-\frac{1}{n_1}\right)\left(1-\frac{1}{n_2}\right)...\left(1-\frac{1}{n_k}\right)\leq\frac{a}{b}<\left(1-\frac{1}{n_1}\right)\left(1-\frac{1}{n_2}\right)...\left(1-\frac{1}{n_{k-1}}\right). \]
Prove that $n_1n_2...n_k\geq(4a)^{2^k-1}$
Simple counterexample: let $k=2,n_1=n_2=2,a=1,b=3$. Clearly all conditions are satisfied with $(1-\frac 12)(1-\frac 12)\leq\frac 13<\frac 12$. But, $2\cdot2<(4\cdot1)^{2^2-1}=64$. Contradiction.
Also, what's the role of $b$? Is $b$ important in this problem?
[b]This message for wpolly:[/b]
Can you please post the other problems too, wpolly? We want to solve those hard Chinese problems too!!! :D  :blush:  :D

I've overlooked the fact that in the original problem we have [tex]1<n_1<n_2<\ldots<n_k[/tex].[/tex]

I still understand wrong the problem. What if we put a/b=/product(1-1/n[i])?
If (n[i]-1,n[j])=1 we have a=(n[1]-1)*(n[2]-1)*.. so we also get a contradiction?
Maybe I got something wrong please smb explain me the condition!

Finally I see what's wrong.
the conclusion in problem 3 should be [tex]n_1n_2\ldots n_k\leq(4a)^{2^k-1}[/tex].

hi! Can somebody post the Chinese olympiad problems 2004, they used to be at kalva but they aren't anymore... i would very much appreciate someone sending the problems

thx,

psykyk

[quote="ThAzN1"]Hmm... If anyone's interested, I found the China olympiad problems (1986-2002) copied from kalva (before they were taken down) in pdf format [url=http://olympiad.mathnet.or.kr/olympiad/list.php?mode=title&title=Chinese%20Mathematical%20Olympiads]here[/url].[/quote]

Thanks for the link.  It looks like they were virtually-printed (with virtual PDF printer or CutePDF Writer, say).

[quote="Peter VDD"]what do you mean by virtual? :?[/quote]A virtual printer is usually a program that is used to "print" (produce) other types of files (usually these are used to produce .pdf, or .ps files from other formats, like .doc), while the printer physically does not exist (it's a set of drivers ;) ).

Computer Nuke, I've moved your post [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=19941]HERE[/url] because it didn't have anything to do with the Chinese TST 2004 :)

[quote="MysticTerminator"][quote="ThAzN1"]Hmm... If anyone's interested, I found the China olympiad problems (1986-2002) copied from kalva (before they were taken down) in pdf format [url=http://olympiad.mathnet.or.kr/olympiad/list.php?mode=title&title=Chinese%20Mathematical%20Olympiads]here[/url].[/quote]

I can't access it?[/quote]

That's wierd; most of 'em work for me.

orl said
[quote]
"The camp lasted two weeks from 16 March to 2 April. Eight tests with 24 problems are held during that time."

Can post the other problems too, please ? It would be very nice.[/quote]

After more than 3 hours' hard work, I have translated the other 18 problems. It is sure I might make some mistake in it, maybe lots of.[/quote]

[quote="zhaoli"]

After more than 3 hours' hard work, I have translated the other 18 problems. It is sure I might make some mistake in it, maybe lots of.[/quote]

Thanks. We appreciate your efforts. But next time please also post the .tex file or at least make an own post for each of the problems.  :)

Sorry, my computer does not support .TEX or LATEX file form.

Quiz 1
Problem 1: http://www.mathlinks.ro/viewtopic.php?p=1393042#1393042
Problem 2: http://www.mathlinks.ro/viewtopic.php?p=1393045#1393045
Problem 3: http://www.mathlinks.ro/viewtopic.php?p=1393047#1393047

Quiz 2
Problem 1: http://www.mathlinks.ro/viewtopic.php?p=1393051#1393051
Problem 2: http://www.mathlinks.ro/viewtopic.php?p=1393053#1393053
Problem 3: http://www.mathlinks.ro/viewtopic.php?p=1393055#1393055

Quiz 3
Problem 1: http://www.mathlinks.ro/viewtopic.php?p=1393060#1393060
Problem 2: http://www.mathlinks.ro/viewtopic.php?p=1393066#1393066
Problem 3: http://www.mathlinks.ro/viewtopic.php?p=1393068#1393068

Quiz 4
Problem 1: http://www.mathlinks.ro/viewtopic.php?p=1393073#1393073
Problem 2: http://www.mathlinks.ro/viewtopic.php?p=1393075#1393075
Problem 3: http://www.mathlinks.ro/viewtopic.php?p=1393077#1393077

Quiz 5
Problem 1: http://www.mathlinks.ro/viewtopic.php?p=1393079#1393079
Problem 2: http://www.mathlinks.ro/viewtopic.php?p=1393083#1393083
Problem 3: http://www.mathlinks.ro/viewtopic.php?p=1393084#1393084

Quiz 6
Problem 1: http://www.mathlinks.ro/viewtopic.php?p=1393087#1393087
Problem 2: http://www.mathlinks.ro/viewtopic.php?p=1393090#1393090
Problem 3: http://www.mathlinks.ro/viewtopic.php?p=1393094#1393094


I'm new here I know, but I'm hoping somebody else here might know something about this.  I read back a few pages through the history and didn't see anything on this posted already, so I thought I would ask.

The way latex handles images has always bugged me and recently I'm having to include more and more of them in my tex files.  At the moment the most convenient way to check my code is to compile to dvi in winshell until I am finished with the document and then compile to pdf for the final presentation.  However whenever I want to include graphics files, I have to see how they format in the pdf version and then comment them out while I finish with the rest of the document, and then uncomment them at the end when I am ready to check the final product.  If I have more than a few images that I want to include, going through every time to uncomment/recomment the image commands gets to be painfully annoying.

I am thinking there must be a way that I can put some scripting up in the header to dynamically determine whether the document is being compiled to dvi or pdf, so that I could then modify the graphics commands as necessary to automatically appear or not by editing a single line in the header, rather than 10 scattered comments throughout the document.  If I just knew the name of the variable (or where to find that sort of information) I can probably work my way through the rest of it, but I don't have the slightest clue where to begin on this one.

Thanks, and it looks like you guys have got a neat place here :)

There's a command that won't load pictures.  You'll just see a box of the size of the picture.  The problem is that I don't remember it and I can't find it.  So here's some less efficient solutions.

To check syntax only, you can use the package syntonly and put the command syntaxonly in the preambule.

If you create a large file, split it in several smaller files and create one master file with the preambule and all.  Add the other files with the command include.

\documentclass{article}
...
\begin{document}
\include{file.tex}
\include{otherfile.tex}
\end{document}

This way, when you work on a specific part, you comment the rest.  In texnic center, you can comment several lines by selecting them and then pressing ctrl  q  and uncomment with ctrl  w.

I'll try to find the right command though...

ledurt

Sweet, that command is probably just what I'm looking for, and the syntonly will certainly work for the time being.  Thanks!

ok, I found it!

use:

\documentclass[12pt,titlepage,[b]draft[/b]]{article}

you'll get boxes instead of pictures with the name of the file.

ledurt

Sweet :)

It's still giving me some problems about unexpected picture filetypes and things when I compile to dvi, but I think I probably figure out what to do with that part of it.  In any case thanks a ton for your help :)

Nice solution, but still compiles with errors on my computer. I have a simple png file included, however when I texify it the dvi is produced, but also an error about the picture not having a bounding box :? , which keeps the dvi viewer from popping up, thus annyoing me :mad: :(

Any solutions? .. (I've tried a lot, but nothing seems to work ...)

A friend of mine had a similar problem, I think.  The tex file would compile perfectly on my computer but on his, it had the same error as you, Valentin.  The "solution" is to define a bounding box for each pictures, but we shouldn't have to do that.  May be you can try to convert your picture in jpg or something else and maybe compile in pdf, I don't know.... :?

ledurt

I can compile in PDF even without your little trick. The trick would be usefull if we can compile in DVI and without commenting, just removing the added key-word in the header of the $\LaTeX$ source file, to have a perfectly nice .pdf file ...

ok, at this point I'm really confuse... may be because I never compile in DVI.  Any way, i'm lost now, how do you use [b]draft[/b] and what doesn't work when you do so... And what is the advantage to compile in DVI?

ledurt

The advantaje is that it's a little faster :P than compiling into .pdf (and even faster is the loading of the document in the viewer) and in the new versions of Yap, you can actually double click on the formulaes on the .dvi file and it will lead you to that point in the .tex document. Very usefull :)

Speed mostly for me as well.  I tend to check my work a lot while I type rather than writing up big sections and checking all at once, and compiling to pdf takes time, where as dvi is almost instantaneous.


Find linear approximation of the function (2-x)^1/2  at a=1

Use the linear approximation obtained in the previous part to obtain an approximate value of (1.99)^1/2


modular arithmetic
IMO 2001
factorial
IMO
combinatorics

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

Ah...at last I solved an IMO-Combinatorics problem.

We consider all $n!$ Permutations $a$ of ${1,\ldots,n}$ and the corresponding $S(a)$ modulo $n!$. If two of them are congruent $\mod{ n!}$, then we are done.
So let's suppose that all $n!$ permutations are in different residues. Sum up over $S(a)$ and we have
\[ \sum_{a}S(a)\equiv 0+1+\ldots+n!-1 \equiv \frac{(n!-1)n!}2\mod {n!} \]
But on the other hand, we have
\[ \sum_{a}S(a)=\sum_{i=1}^nc_i( (n-1)!\cdot (1+2+\ldots+n)) = \sum_{i=1}^nc_i( n! \cdot \frac{n+1}2) \]
Since $n$ is odd, we have $2\mid n+1$, thus $\sum_a S(a)\equiv 0 \mod{n!}$,
so we have
\[ \frac{(n!-1)n!}2\equiv 0\mod{n!} \]
which is a contradiction since $n!$ is even.

Suppose for the sake of contradiction that for all permutations $a$ and $b$ of $\{1,2, \ldots, n\}$, we have that $S(a) \neq S(b) \pmod{n!}$. There are $n!$ permutations of $\{1,2, \ldots, n\}$ and $n!$ residue classes modulo $n!$, so for every integer $m$ with $0 \leq m < n!$, there is a unique permutation $a$ of $\{1,2,\ldots,n\}$ such that $S(a) \equiv m \pmod{n!}$.

Let $k = \frac{(n+1)(c_1 + c_2 + \cdots + c_n)}{2}$. We can find some permutation $a = (a_1, a_2, \ldots, a_n)$ such that $S(a) \equiv c_1 a_1 + c_2 a_2 + \cdots + c_n a_n \equiv k \pmod{n!}$. But the permutation $a' = (n+1-a_1, n+1-a_2, \ldots, n+1-a_n)$ also satisfies $S(a) \equiv (n+1)(c_1 + c_2 + \cdots + c_n) - (c_1 a_1 + c_2 a_2 + \cdots + c_n a_n) \equiv 2k - k \equiv k \pmod{n!}$.
Hence, $a'$ and $a$ must be the same permutation, which is absurd.

Let $\mathcal{P}_1, \mathcal{P}_2, \cdots , \mathcal{P}_{n!}$ denote the $n!$ permutations of $(1, 2, \cdots , n).$ We shall take the indices modulo $n!,$ meaning that $\mathcal{P}_x = \mathcal{P}_{x \pmod{n!}}.$ Also, let $\mathcal{D}_{n,x}$ denote the $x$th digit of $\mathcal{P}_n.$ Suppose the problem statement isn't true. Then,
\[S(\mathcal{P}_x) \equiv S(\mathcal{P}_y) \pmod{n!} \iff x \equiv y \pmod{n!},\]
implying that $\mathcal{P}_i$ is bijective modulo $n!,$ or in other words, $(S(\mathcal{P}_1), S(\mathcal{P}_2), \cdots , S(\mathcal{P}_{n!}))$ is equivalent to $(1, 2, \cdots , n!)$ modulo $n!$ in some order. We then have
\[\displaystyle \sum_{i=1}^{n!} S(\mathcal{P}_i) \equiv \displaystyle \sum_{i=1}^{n!} i \equiv \dfrac{n!(n!+1)}{2} \pmod{n!}.\]
But we also have
\begin{align*}
\displaystyle \sum_{i=1}^{n} S(\mathcal{P}_i) & \equiv \displaystyle \sum_{i=1}^{n} \left( \displaystyle \sum_{j=1}^{n} c_j \mathcal{D}_{i,j} \right) \\
& \equiv (n-1)! \displaystyle \sum_{j=1}^{n} c_j \left( \displaystyle \sum_{k=1}^{n} \mathcal{D}_{j,k} \right) \\
& \equiv \dfrac{n(n+1)}{2} (n-1)! \cdot \left( \displaystyle \sum_{j=1}^{n} c_i \right) \\
& \equiv 0 \pmod{n!},\end{align*}
implying $\dfrac{n!(n!+1)}{2} \equiv 0 \pmod{n!} \implies 2 \mid n!+1,$ contradiction. $\blacksquare$

Wow, this problem is really nice. Unfortunately my solution seems to be pretty similar compared to previous ones in the thread  :(

FTSOC $S(1), S(2), \cdots, S(n!)$ are all distinct residues $\pmod{n!}$. Let's consider $S=\sum_{j=1}^{n!} \sum_{i=1}^{n} c_ia_i$ in two different ways. First, summing over $S(1), \cdots, S(n!)$ we have $S=1!+2!+\cdots+(n!-1) \equiv \frac{n!(n!-1)}{2} \pmod{n!}$, which isn't $0 \pmod{n!}$. Considering $S$ a different way, observe that there are $(n-1)!$ times where $c_i$ has coefficient $1, 2, \cdots, n$, $1 \le i \le n$. Summing up over the $c$'s, we have $S=(n-1)! \frac{n(n+1)}{2} \sum_{i=1}^{n} c_i \equiv 0 \pmod{n!}$. This is our contradiction and we are done.

I apologize to everyone for my solution being similar to above solution.

Let $S_{n}$ be set of all permutation of $(1,\dots ,n)$.We suppose that there is no $a\neq b$ which satisfy $S(a)\equiv S(b)\mod{n!}$.Then $\{S(a)\}_{a\in S_{n}}{}$ is $\{0,1,\dots ,n!-1\}$ in$\mod{n!}$.We calculate $\sum_{a\in S_{n}}{}S(a)$ in $2$ ways.

[u]First[/u]
$\sum_{a\in S_{n}}{}S(a)\equiv \sum_{k=0}^{n!-1}k\equiv \frac{(n!-1)(n!)}{2}\mod{n!}$.

[u]Second[/u]
The number of permutations which $a_i=k(1\le i,k\le n)$ is $(n-1)!$.Thus
$\sum_{a\in S_{n}}{}S(a)\equiv \sum_{i=1}^{n}c_{i}\cdot (n-1)!\cdot (1+\dots +n)$
$\equiv n!\frac{n+1}{2}\sum_{i=1}^{n}c_{i}\equiv 0\mod{n!}$.

From [u]First[/u] and [u]Second[/u],
$\frac{(n!-1)(n!)}{2}\equiv 0\mod{n!}\Leftrightarrow \frac{n!}{2}\equiv 0\mod{n!}$ which is absurd.Therefore ∃$a\neq b$ s.t. $n! | S(a)-S(b)$.$\blacksquare$

:coolspeak:

[quote=ISL 2001 C2]Let $n$ be an odd integer greater than 1 and let $c_1, c_2, \ldots, c_n$ be integers. For each permutation $a = (a_1, a_2, \ldots, a_n)$ of $\{1,2,\ldots,n\}$, define $S(a) = \sum_{i=1}^n c_i a_i$. Prove that there exist permutations $a \neq b$ of $\{1,2,\ldots,n\}$ such that $n!$ is a divisor of $S(a)-S(b)$.[/quote]

[b]Solution.[/b]

Let $\mathcal{P}$ be the set of all permutations of $\{1,2,3,\ldots,n\}.$ Assume for the sake of contradiction that there doesn't exist such $a\ne b.$ Consider the multiset $T=\{S(\pi)\mid \pi\in\mathcal P\},$ because of our assumption and $|T|=n!$ , when we take $T$ modulo $n!$ we get the complete set of residues modulo $n!~.$ Let $X=(x_1,x_2,x_3,\ldots,x_n)$ be the permutation such that
\[S(X)\equiv \left(\frac{n+1}{2}\right)\left(\sum_{i=1}^{n}c_i\right)\pmod{n!}\]
Define $\overline{X}=(n+1-x_1,n+1-x_2,\ldots,n+1-x_n),$ note that $X\ne \overline{X}$ and that $\overline{X}$ is a valid permutation.
Now,
\[S(\overline{X})=\sum_{i=1}^n c_i(n+1-x_i)=(n+1)\sum_{i=1}^n c_i-S(X)\equiv (n+1)\sum_{i=1}^n c_i- \left(\frac{n+1}{2}\right)\left(\sum_{i=1}^{n}c_i\right)\pmod{n!}\equiv S(X)\pmod{n!}\]
Which is a contradiction to our assumption. And we are done. $\blacksquare$

Suppose for sake of contradiction that this didn't happen. Then, all the $S(\sigma)\pmod{n!}$ are different for all $\sigma\in S_n$. Choose $\sigma$ uniformly at random. By linearity of expectation, we have
\[\mathbb{E} S(\sigma)=c_i\frac{n+1}{2},\]
so
\[\sum_{\sigma\in S_n}S(\sigma)=\frac{(n+1)!}{2}\sum_{i=1}^n c_i\equiv 0\pmod{n!}\]
since $\frac{n+1}{2}\in\mathbb{Z}$. By the hypothesis, we have
\[\sum_{\sigma\in S_n}S(\sigma)\equiv\sum_{k=0}^{n!-1}k\equiv\frac{n!(n!-1)}{2}\pmod{n!},\]
which isn't divisible by $n!$ since $n!-1$ is odd (this is why we need $n>1$), This is a contradiction, as desired. $\blacksquare$

Assume FTSOC that all the $S(\pi)$'s are distinct mod $n!$ for all $\pi \in S_n$. Then
\[ \sum_{\pi \in S_n} S(\pi) \equiv 0+\cdots+(n!-1) = \frac{(n!-1)(n!)}{2} \not \equiv 0 \pmod{n!} \]
since $n!$ is even for $n>1$.

Treat the permutations and $\{c_i\}$ as vectors in $\mathbb{F}_{n!}^n$. Note that the vector sum of all the permutations is
\[ ((n-1)!\cdot (1+\cdots+n))(1,\ldots,1) = \frac{n!(n+1)}{2}(1,\ldots,1).\]
Then
\begin{align*}
    \sum_{\pi \in S_n} S(\pi) &= \sum_{\pi \in S_n} \vec{c}\cdot \pi \\
    &= \vec{c} \cdot \sum_{\pi \in S_n} \pi \\
    &= \vec{c} \cdot \frac{n!(n+1)}{2} (1,\ldots,1) \\
    &= \frac{n!(n+1)}{2} \left(\sum c_i \right) \equiv 0 \pmod{n!}
\end{align*}
since $n$ is odd. Contradiction!

[hide=Solution]
Suppose \(D_{n!} (S(\pi))\) takes distinct values as \(\pi\) ranges over all permutations of \([n]\). Then summing over all permutations, we get that

\begin{align*}
\frac{n!(n! - 1)}{2} &\equiv (n-1)! \cdot \frac{n(n+1)}{2} \sum c_i \pmod{n!} \\
\frac{n!(n!-1)}{2} &\equiv n! \cdot \frac{n+1}{2}\sum c_i \pmod{n!} \\
\end{align*}
But that would mean
\[\frac{n!}{2} \equiv 0 \pmod{n!}\]
which is a contradiction.
[/hide]

[hide=Solution][quote=ISL 2001 C2]Let $n$ be an odd integer greater than 1 and let $c_1, c_2, \ldots, c_n$ be integers. For each permutation $a = (a_1, a_2, \ldots, a_n)$ of $\{1,2,\ldots,n\}$, define $S(a) = \sum_{i=1}^n c_i a_i$. Prove that there exist permutations $a \neq b$ of $\{1,2,\ldots,n\}$ such that $n!$ is a divisor of $S(a)-S(b)$.[/quote]
[b][color=#000]Solution:[/color][/b] For the sake of contradiction, assume the contrary. As a result, we must have distinct remainders for $S(a_i)$ $\pmod{n!}$. Using this fact
\begin{align*} \sum S(a_i) \equiv \frac{n!(n!-1)}{2} \not \equiv 0 \pmod{n!} \end{align*}
Counting $\sum S(a_i)$ fixing $c_i$ results,
\begin{align*} \sum S(a_i)= n! \left( \frac{n+1}{2} \right) \sum c_i \equiv 0 \pmod{n!} \end{align*}
Which is a contradiction $\qquad \blacksquare$
[/hide]

For storage.
---------
Suppose not. Then let $\mathcal{P}$ be the set of all permutations $a$. Now for all permutations, their residues are distinct modulo $n!$. Hence
    \begin{align*}
        0 + 1 + \dots + (n! - 1) &\equiv \sum_{a\in\mathcal{P}} S(a) \\
        &\equiv \frac{n(n+1)}{2}\cdot(n-1)!\cdot\sum_{i=1}^n c_i
    \end{align*}
    by looking at the amount of times $1$, $2$, $\dots$, $n$ appears in the $i$th slot. But \[\frac{n(n+1)}{2}\cdot(n-1)!\cdot\sum_{i=1}^n c_i = \frac{n+1}{2}\cdot n!\cdot \sum_{i=1}^n c_i\] and $n$ is odd, so the RHS is congruent to $0$ modulo $n!$. Hence we have $\frac{(n!-1)(n!)}{2} \equiv 0 \mod{n!}$. But $n!$ is even, so this is equivalent to $-\frac{n!}{2}$, which is clearly nonzero modulo $n!$, contradiction.

For the sake of contradiction assume this is not the case, which implies that $S(a)$ takes on every residue modulo $n!$ as it ranges over all permutations. Letting $P$ be the set of all permutations, we have that
\begin{align*}
\sum_{k \in P} S(k) &\equiv 0+1+2+\cdots + (n!-1)\\
&\equiv \frac{(n!-1)(n!)}{2} \pmod{n!}.
\end{align*}

If we compute
\begin{align*}
\sum_k S(k) &= \sum^n_{j=1} c_j \times (n-1)! \times (1+2+3+\cdots+n)\\
&= \sum_{j=1}^n c_j\left[(n!)\left(\frac{n+1}{2}\right)\right].
\end{align*}
So, $\sum_k S(k) \equiv 0 \mod{n!}.$ Thus we can deduce that
$$\frac{(n!-1)(n!)}{2} \equiv 0 \pmod{n!},$$
which is a contradiction since $n!$ is even. $\blacksquare$

AFTSOC that all $S(a)\neq S(b)$, then the set of $S(p)$ is the residues from $0,1,\ldots, n!-1$. Let $P$ be the set of all permutations, then
\[\sum_{p\in P} S(p) \equiv \frac{(n!-1)(n!)}{2} \not\equiv 0 \pmod{n!}\]
however,
\[\sum_{p\in P} S(p) = n!\cdot \frac{1+2+\cdots n}{n}\cdot \sum c_i = n!\cdot \frac{n+1}{2}\sum c_i \equiv 0 \pmod{n!}\]
a contradiction, so we are done. $\blacksquare$

Probably similar to the above solutions, posting just for storage
[hide=solution]
FTSOC assume $S(a) \ne S(b) \forall a \ne b$. Notice that $\sum{S(a)}= \frac{(n+1)!}{2}\sum{c_i}$, so $\sum{S(a)} \equiv{\frac{n!(n!-1)}{2}} \equiv{0} \pmod{n!}$, which is clearly a contradiction

[hide=Wut]Combinatorics problem? Apparently Evan considered this as a 5-MOHS Algebra problem, don't know what was that for.[/hide] Assume for the sake of contradiction that $n!$ does not divide $S(a)-S(b)$, this means all the $S(i)$ give distinct remainder upon division by $n!$.
$$\implies \sum_{\text{over all permutations}} S(a) \equiv 0 + 1 + \cdots + n!-1 \equiv \dfrac{n!(n! - 1)}{2} \equiv \frac{n!}{2} \pmod{n!}$$
On the other hand $$\sum_{\text{over all permutations}} S(a) = \sum_{i=1}^n c_i \cdot (n-1)! \cdot (1 + 2 + \cdots n) = \dfrac{n!(n+1)}{2} \sum_{i=1}^n c_i \equiv 0 \pmod{n!}$$
because $\dfrac{n+1}{2} \in \mathbb Z$. So $\dfrac{n!}{2} \equiv 0 \pmod{n!}$ which is a contradiction.

The statement clearly is not true for $n = 1$ or $n = 2$, but one may check (with a computer) that it does hold for $n = 4$. I wonder whether the result is true for all even $n \ge 4$. Of course, the above proofs fail in this case, so one needs something more sophisticated.

Let $P$ denote the set of permutations of $\{1,2,\ldots,n\}$. Since $|P|=n!$, we only have to show that we cannot have $\{S(\sigma)\}_{\sigma \in P}\equiv \{1,\ldots,n!\} \pmod{n!}$. Suppose otherwise. Then summing over $1,\ldots,n!$ we find that
$$\sum_{\sigma \in P} S(\sigma)\equiv \frac{n!(n!+1)}{2}\equiv \frac{n!}{2} \pmod{n!},$$
but summing over $P$ directly, we obtain
$$\sum_{\sigma \in P} S(\sigma)=\sum_{\sigma \in P}\sum_{i=1}^n c_i\sigma(i)=\sum_{i=1}^n c_i\left(\sum_{\sigma \in P}\sigma(i)\right)=\frac{n(n+1)(n-1)!}{2}\sum_{i=1}^nc_i\equiv 0 \pmod{n!},$$
as $n$ is odd. Since $\tfrac{n!}{2} \not \equiv 0 \pmod{n!}$, we have a contradiction. $\blacksquare$

[hide = Solution]
Consider the sum of all the possible values of $S(a)$. We get:
\[\mathcal{S} = \sum_{a} S(a) =  (n - 1)!\frac{n(n + 1)}{2}\left( \sum_{i = 1}^{n} c_i \right).\]
Observe that $n! \mid \mathcal{S}$ since $n + 1$ is even.
Now assume for the sake of contradiction all the values $S(a)$ takes modulo $n!$ are distinct. We see that:
\[\mathcal{S} \equiv 1 + 2 + \cdots n! \equiv \frac{n!}{2} \pmod{n!}\]
as  $n!$ is even and $\frac{n!}{2}$ does not have an inverse. But this contradicts what we had earlier, and therefore our assumtion was wrong, and there exists two permutation $a$ and $b$ such that $n! \mid S(a) - S(b)$.
[/hide]

[quote=MrOreoJuice][hide=Wut]Combinatorics problem? Apparently Evan considered this as a 5-MOHS Algebra problem, don't know what was that for.[/hide] [hide = my hypothesis]I assume this is because it's not very combi heavy ? not sure maybe we can ask him [/hide]

Let $A_i$ denote a permutation of $\{1,2\dots,n\}$ for $1\le i\le n!.$ Notice that $$\sum_{i=1}^{n!}{S(A_i)}\equiv\frac{(n-1)!n(n+1)}{2}\sum_{i=1}^{n}{c_i}\equiv 0\pmod{n!}$$ as $2\nmid n.$ Suppose FTSOC that $A_i\not\equiv A_j\pmod{n!}.$ Then, $$0\equiv\sum_{i=1}^{n!}{S(A_i)}\equiv\sum_{i=0}^{n!-1}{i}\equiv\frac{(n!-1)n!}{2}\pmod{n!},$$ a contradiction as $2\mid n!.$ $\square$

Proudly wasting my 200th HSO post on my 1st ISL combo.
[quote=ISL 2001 C2]Let $n$ be an odd integer greater than 1 and let $c_1, c_2, \ldots, c_n$ be integers. For each permutation $a = (a_1, a_2, \ldots, a_n)$ of $\{1,2,\ldots,n\}$, define $S(a) = \sum_{i=1}^n c_i a_i$. Prove that there exist permutations $a \neq b$ of $\{1,2,\ldots,n\}$ such that $n!$ is a divisor of $S(a)-S(b)$.[/quote]

FTSOC there doesn't exist $a,b$ such that $n \not | S(a)-S(b)$.If we consider the permutation $S(a_1),S(a_2),......S(a_{n!})$,it clearly formed a residue class modulo $n$ and all the combinatorics is gone.

We now evaluate $\sum S(a_i)$ in 2 ways.
Since  $\{S(a_i)\}$ forms a whole residue class $\pmod n$ we get that,
$$\sum S(a_i) \equiv \frac{n!(n!-1)}{2} \ne 0 \pmod{n!}$$
Again,
$$\sum S(a_i) \equiv (n-1)!\sum_{i=1}^{n} \sum_{i=1}^{n} c_ia_i \equiv (n-1)!\frac{n(n+1)}{2}\sum_{i=1}^{n}c_i
 \stackrel{\text{n is odd}}\equiv 0 \pmod{n!}$$
The above 2 equations contradict each other,so our assumption was wrong . The End $\blacksquare$

ISL marabot solve

AFTSOC there doesn't exist such $a$ and $b$. Call the permutations of $\{1,2,3,\ldots,n\}$ as $b_1,b_2\ldots,b_{n!}$. Note that $S(b_i)$ forms a complete residue class $\pmod{n!}$.

Now we compute $\sum S(b_i)\pmod{n!}$ in two ways.

Way 1: We have $\sum S(b_i)\equiv 0+1+2+\ldots+n!-1=\frac{n!(n!-1)}{2}\not \equiv 0\pmod{n!}$ as $n!-1$ is odd.

Way 2: We have $\sum S(b_i)=(n-1)!\sum c_i \cdot \frac{n(n+1)}{2}$. Since $n$ is odd, this is $0\pmod{n}$, so $0\pmod{n!}$.

These two ways contradict each other, so such permutations $a$ and $b$ exist.

Algenatorical NT!?!?!?

Assume for the sake of contradiction that there does not exist such permutations. Since each $S(a)$ has a different remainder when divided by $n!$ and there are $n!$ total permutations, each permutation must have a different remainder.

We sum the $S(a)$ for all permutations $a.$

Let $i$ be a number $1\le i \le n$ To calculate this sum, we first find the number of times that the term $ic_j$ appears. The terms of each permutation and list are symmetric, so the number of times $ic_j$ appears sn an invariant across $i,j$.

Thus, we only need to count this for $1c_1$. This number is $(n-1)!$ since we have assigned a number $i$ to $a_1$, and we only need to assign now for $a_2, a_3, \dots a_n$. This implies that the sum is \[(n-1)!(c_1+c_2+c_3+\dots+c_n)(1+2+\dots+n)=\frac{1}{2}(c_1+c_2+\dots+c_n)(n+1)!\]
Since $n$ is odd, $\frac{n+1}{2}$ is an integer. Thus, the sum of $S(a)$ across all permutations $a$ is divisible by $n!$.

Looking back at our assumption that each permutation must have a different remainder, we see that the sum must have a remainder $1+2+\dots+n!-1$ mod $n!$. If this were to comply with our above result, then \[n!|\frac{1}{2}n!(n!-1)\]
This implies that $n!-1$ is even, which is clearly false because $n>1.$

The problem feels somewhat awkwardly constructed and the existence of the $c_i$ makes the summing idea pretty obvious.

It suffices to show that the residues $S(a) \pmod {n!}$ cannot be all distinct. Assume for the sake of contradiction otherwise; then, double count $S(n)$; on one hand, it equals $$(n-1)! \left(\sum c_i \right) \frac{n(n+1)}2 = \frac{n+1}2 \cdot n! \cdot \left(\sum c_i\right).$$ This expression is a multiple of $n!$ as $n$ is odd. On the other hand, it equals $$1+2+3+\cdots+n! = \frac{n!(n!+1)}2$$ modulo $n!$. Yet $n!$ is even, so this cannot be possible.

As a result, the residues are not all distinct, and we can choose $S(a) \equiv S(b) \pmod {n!}$, which solves the problem.

Assume not. Then the residues $S(a) \pmod{n!}$ form a complete residue set. The sum of the terms in a complete residue set is $$0+1+ \cdots + (n!-1) \equiv \frac{n!(n!+1)}{2} \equiv \frac{n!}{2} \pmod{n!},$$ since $n!$ is even. We also have the sum of the residues of $S(a)$ is $$\sum_{i=1}^{n}(n-1)!i\left(\sum c_i \right) = \frac{n+1}{2} \cdot n! \cdot \left(\sum c_i \right) \equiv 0 \pmod{n!},$$ a contradiction to the above so we are done.

[hide="Solution"]
For the sake of contradiction assume that all $S(a)$'s are different modulo $n!$. Because $n>1$ there are exactly $\frac{n!}{2}$ permutations like $a$ such that $2\nmid S(a)$. So, the problem is solved if I show that $\left\lvert\{a\mid S(a)\overset{2}{\equiv}0\}\right\rvert\neq\left\lvert\{a\mid S(a)\overset{2}{\equiv}1\}\right\rvert$.
I want to make an injection from one of the above sets to the other one. We know that there exists a parity $X\in \text{GF}(2)$ such that odd numbers among $c_1,c_2,\ldots,c_n$ have parity $X$. Define $b=(b_1,b_2,\ldots,b_n)$ such that $\forall i: b_{a_i}=c_i$ that implies $S(a)=\sum_{i=1}^{n} ib_i\eqqcolon T(b)$. If we choose $b_n$ with parity $\neg X$, then we have a bijection with permutations with $T(b)\overset{2}{\equiv}0$ and $T(b)\overset{2}{\equiv}1$. And for some of permutations that $b_n$ has parity $X$, consider $f(b)=t$ such that $b_{2t-1}\overset{2}{\not\equiv}b_{2t}\,\wedge\,b_{2t+1}\overset{2}{\equiv}b_{2t+2}\,\wedge\,\cdots\,\wedge\,b_{n-2}\overset{2}{\equiv}b_{n-1}$ if possible. If we swap $b_{2t-1}$ and $b_{2t}$ and define it $b'$, then $f(b')=f(b)$ but $T(b')\overset{2}{\not\equiv}T(b)$ and I claim that the correspondence I created between $b$'s and $b'$'s it's a non-surjective injection.
Some permutations like $b$ of $c$ remain that aren't in the domain of $f$. Their property is that $b_{1}\overset{2}{\equiv}b_{2}\,\wedge\,b_{3}\overset{2}{\equiv}b_{4}\,\wedge\,\cdots\,\wedge\,b_{n-2}\overset{2}{\equiv}b_{n-1}$. So, there exists a whole number $m$ that for all of them there's exactly $m$ odd numbers among $b_1,b_3,\ldots,b_{n-2}$. So, for all of them $T(b)$ has the same parity and my claim was proved.[/hide]

Assume that there aren't at least two permutations or which $S(a) \equiv S(B) \pmod{n!}$. Then we have that by the pigeonhole principle that the $S(a)$ form a distinct set of residues modulo $n!$.

Hence $$\sum_{a \in \pi} S(a) = \frac{n!(n! - 1)}{2} \pmod{n!}.$$ Also we have that $$\sum_{a \in \pi} S(a) = \sum_{i = 1}^{n} c_i \frac{n!(n + 1)}{2}.$$ As $n$ is odd by hypothesis, we have that $2 \mid n + 1$. Hence we have that $\sum_{a \in \pi} S(a) = \sum_{i = 1}^{n} c_i \frac{n!(n + 1)}{2} \equiv 0 \pmod{n!}$. Thus $\frac{n!(n! - 1)}{2} \equiv 0 \pmod{n!}$, which is impossible as $n!$ is even and $n! - 1$ is odd. $\blacksquare$

[hide=Actually a constructive solution]
Lemma: Problem is trivial if there exist $c_i = c_j$
Just take arbitrary (a), let $(b)$ be $(a)$ but swap $a_i$ and $a_j$. $_\blacksquare$

Wlog assume that $(c)$ is a permutation of $\{ 1, 2, \cdots, n \}$.
Then there are triples $(a), (b)$ for $n=3$ with $S(a) = S(b)$. (This actual equality is the main idea)
For example, take $(3, 1, 2), (2, 3, 1)$.
For induction $n \rightarrow n+2$, just append $n+1, n+2$ to the ends of the existing tupels for $n$, and trivially, $S(a), S(b)$ will be equal again.
[/hide]

[quote=Kugelmonster][hide=Actually a constructive solution]
Lemma: Problem is trivial if there exist c_i = c_j
Just take arbitrary (a), let (b) be (a) but swap a_i and a_j.

Wlog assume that (c) is a permutation of {1,2,...,n}.
Then there are triples (a), (b) for n=3 with S(a) = S(b). (This actual equality is the main idea)
For example, take (3, 1, 2), (2, 3, 1).
For induction n --> n+2, just append n+1, n+2 to the ends of the existing tupels for n, and trivially, S(a), S(b) will be equal again.
[/hide][/quote]

Sadly, we found out that this solution is false, as we cannot assume that (c) is a permutation of {1,2,...,n}.

Suppose not. Then every remainder mod $n!$ can be attained by $S$. Now, double count the remainder when the sum of all possible $S(a)$ is divided by $n!$. We have that $$0+1+\dots+(n!-1)\equiv\sum_{i=1}^n c_i((1+2+3+\dots+n)(n-1)!)\pmod{n!}.$$ Simplifying, $$\frac{(n!-1)(n!)}{2}\equiv\left(\sum_{i=1}^n c_i\right)\left(\frac{n(n+1)}{2}(n-1)!\right)\equiv\left(\sum_{i=1}^n c_i\right)\left(\frac{n+1}{2}\right)(n!)\equiv 0\pmod{n!}.$$ Since $n!-1$ is odd, the LHS cannot be divisible by $n!$, contradiction, QED.

Claim: The sum of $S(a)$ over all permutations $a$ is a multiple of $n!$. Note that the expected $S$ of a random permutation is $$(c_1+c_2\cdots +c_n)(\frac{n+1}{2}),$$ and since $n$ is odd, this is an integer. Therefore, the total sum is a multiple of $n!$.\\

Suppose FTSOC that the problem statement does not hold. Then, the $S$ values of the permutations modulo $n!$ must be $0,1,2\cdots n!-1$ in some order. However, this would mean that their sum would be congruent to $$\frac{(n!-1)(n!)}{2}$$ modulo $n!$, but since $n!-1$ is odd, this is not a multiple of $n!$, contradiction.\\

Suppose otherwise. Then the values of $S(a) \mod n!$ over all permutations $a$ must be precisely $0,1,2,\ldots,n!-1$ in some order (else, we would be done by Pigeonhole). Summing, we get that \[0+1+2+\cdots+(n!-1) \equiv \sum_{i=1}^n c_i \cdot (n-1)! \cdot [1+2+3+\cdots+n] \mod n! \implies \frac{n!(n!-1)}{2} \equiv \sum_{i=1}^n c_i \cdot n! \cdot \frac{n+1}{2} \equiv 0 \mod n! \] This is a contradiction as the left hand side of the last equation is clearly equal to $\frac{n!}2$ modulo $n!$

If the problem statement is not true, then all $S(a)$ must be different modulo $n$. First off, we can see that the permutations of $a$ give a total of $n!$ total $a$ sets. We can take these remainders as $0,1,\cdots ,n!-1$ so that all $S(a)$ are different mod $n$. We can take the sum of all $S(a)$ mod $n!$ and get $\frac{(n!)(n!-1)}{2} \mod{n!} \equiv \frac{n!}{2} \mod{n}$ via the arithimetic sequence summation identity. However, we also get that $\frac{(n!)(n!-1)}{2} \mod{n!} \equiv \sum_{i=1}^n c_i \cdot n! \cdot \frac{n+1}{2} \equiv 0 \mod n!$. This means that in order for the problem statment be false, we must have $\frac{n!}{2}=0$. However, because $n \ge 1$, the problem statement is true

For the sake of contradiction suppose not. Then, it follows that $\{S(\pi)\}$ where $\pi$ ranges over $S_n$ is the same as the residues $\pmod{n!}$.

However, while \[\sum_{\pi \in S_n} S(\pi) = \frac{n!}{2} \cdot (n+1) \cdot (c_1 + c_2 + \dots + c_n)\] is divisible by $n!$
\[\sum_{i=0}^{n! - 1} = \frac{n!}{2} \cdot (n! - 1)\] is not, contradiction.

Assume no two $S(a) \equiv S(b) \pmod{n!}$. Then the sum over all such $S(a)$ is \[\sum_{a \in \sigma} S(a) \equiv \frac{n!(n! + 1)}{2} \pmod{n!}.\] However we also have \[\sum_{a \in \sigma} S(a) = \sum_{i = 1}^{n} c_i \left(\frac{n!(n+1)}{2}\right) \equiv 0 \pmod{n!}.\] Thus we have the congruence \[\frac{n!(n! + 1)}{2} \equiv 0 \pmod{n!},\] which is a contradiction. $\blacksquare$

For the sake of contradiction, assume the given statement is false. Then, all of the $S(a)$ must have it's own unique residue mod $n!$. Then,

\[\sum_a S(a) \equiv \frac{(n!-1)(n!)}{2} \not\equiv 0 \pmod{n!}\]

however,

\[\sum_{a} S(a) = n!\cdot \frac{1+2+\cdots n}{n}\cdot \sum c_i = n!\cdot \frac{n+1}{2}\sum c_i \equiv 0 \pmod{n!}\]

a contradiction. $\square$

FTSOC, assume that there are not two permutations $a\neq b$ such that
\[n\mid S(a)-S(b) \iff S(a)\equiv S(b) \mod n!,\]
and since there are $n!$ permutations and only $n!$ modulos mod $n$, this means that every permutation $k$ of $\{1,2,\dots,n\}$ has a value of $S(k)$ such that $S(k)$ has a unique remainder when divided by $n!$. This implies that
\[\sum_{k} r(S(k)) \equiv 1+2+\dots+n! \equiv \frac{n!(n!+1)}{2} \equiv \frac{n!}{2} \mod n!,\]
where $r(x)$ is the remainder function mod $n!$, and since $n>1$, implying that $n!+1$ is odd, meaning that $\frac{n!(n!+1)}{2} \equiv \frac{n!}{2} \mod n!$. \\\\
However, if we try to sum up $S(k)$ over all permutations $k$ another way by using the definition of $S(k)$, we have that
\[\sum_{k} r(S(k))=(c_1+c_2+\dots+c_n)(1+2+\dots+n)((n-1)!)=\frac{(n+1)! \sum c_i}{2} \equiv 0 \mod n!,\]
This is because for each number occupies each position $(n-1)!$, so if we sum these together for all numbers in all positions, we get that the total sum is $(c_1+c_2+\dots+c_n)(1+2+\dots+n)((n-1)!)$. We can combine terms to get $\frac{(n+1)! \sum c_i}{2}$, which is $0$ mod $n!$ because $\frac{n+1}{2}$ is an integer since $n$ is odd. This is a contradiction to our previous way of summing, which gave that the total sum should be $\frac{n!}{2}$ mod $n!$. Therefore, there must exist two distinct permutations $a$ and $b$ of $\{1,2,\dots,n\}$ such that $n\mid S(a)-S(b)$, finishing the problem.

Assume ftsoc that $n! \nmid S(a) - S(b)$ for all choices of $a$ and $b$, or that $S(a)$ leaves a distinct remainder modulo $n!$ over all choices of the permutation $a$. Then we find that the sum of these remainders modulo $n!$ is
$$1 + 2 + \cdots + n! = \frac{n!(n! + 1)}{2} \not\equiv 0 \pmod{n!},$$
the incongruence coming from the fact that $n! + 1$ is odd, and $\nu_2(n!/2) = \nu_2(n!) - 1 = -1$. However, if we consider how many times each of $1, 2, \ldots, n$ appear as each of the $a_i$ across all permutations, we find that the sum of all permutations modulo $n$ is also
$$\sum_{i = 1}^n [c_i(1 + 2 + \cdots + n)(n - 1)!] = \frac{(n+1)!}{2} \cdot \sum_{i = 1}^n c_i \equiv 0 \pmod n!,$$
as $n$ is odd (so $\nu_2((n + 1)/2) \ge 0$), contradiction.

With $n!$ possible permutations, the only possible way to violate the statement is that all $S(a)$ have different residues modulo $n!$. Then
\begin{align*}
&\hspace{1cm} \sum S(A) \equiv 0+1+\ldots+(n!-1) \\
&\implies (n-1)! \cdot (1+2+\ldots+n) \cdot (c_1 + \ldots + c_n) \equiv n! \left(\frac{n!-1}{2}\right) \\
&\implies n! \cdot \left(\frac{n+1}{2}\right) \cdot (c_1 + \ldots + c_n) \equiv n! \left(\frac{n!-1}{2}\right) \quad \pmod{n!}
\end{align*}

The LHS is a multiple of $n!$ while the RHS isn't, contradiction. $\blacksquare$

Suppose by way of contradiction that there exist no two permutations $a$ and $b$ such that $S(a) \equiv S(b) \mod{n!}$ This means that all permutations have a unique residue modulo $n!$ Thus, if we compute the sum of $S(p)$ modulo $n!$ where $p$ ranges over all permutations of $[1, 2, 3, 4, \dots n]$, we will obtain $\sum_{i = 0}^{n!-1}i \equiv \frac{(n!-1)n!}{2} \equiv \frac{-n!}{2} \equiv \frac{n!}{2}  \pmod{n!}$

Now let us compute this exact sum modulo $n!$ in another way. We can think about how each of $c_1, c_2, c_3 \dots c_n$ contribute to the sum. Observe that each of the $c_i's$ have a "contribution" of $(n-1)!(1+2+3+4+\dots+n) = (n-1)!\frac{n(n+1)}{2}c_i$. So the sum we desire modulo $n!$ is $\sum_{i = 1}^{n}((n-1)!\frac{n(n+1)}{2}c_i) \equiv (n-1)!\frac{n(n+1)}{2}\sum_{i=1}^{n}c_i \equiv 0 \equiv \frac{n+1}{2}n!\sum_{i=1}^{n}c_i \pmod{n!}$. Since $n$ is odd, we know that $\frac{n+1}{2} = k$ where $k$ is some integer. So, we have effectively deduced that the sum of $S(p)$ where $p$ iterates over the permutations of $[1, 2, 3, \dots n]$ is $0 \pmod{n!}$.

But note that we claimed earlier that the sum was actually $\frac{n!}{2}  \pmod{n!}$, therefore creating a contradiction.

Seriously, this was an IMO problem?

Assume for the sake of contradiction that all values of $S(a)$ are distinct mod $n!.$ The main idea is to add everything together. On one hand, we are adding all of the distinct residues mod $n!,$ which gives $1 + 2 + \dots + n! = \frac{n! (n! + 1)}{2}.$ Noting that $n! + 1$ is odd and $n!$ is even, this is equivalent to $\frac{n!}{2} \pmod{n!}.$

On the other hand, for each $c_i,$ each possible value of $a_i$ from $1$ to $n$ inclusive is covered $(n-1)!$ times, so the sum is equivalent to $$(c_1 + c_2 + \dots + c_n)(n-1)!(1+2+\dots + n) = (c_1 + c_2 + \dots + c_n)(n-1)! \cdot \frac{n(n+1)}{2} = \frac{(c_1 + c_2 + \dots + c_n)(n+1)!}{2}.$$ Note that $\frac{(n+1)!}{2} = \frac{n!}{2} \cdot (n+1).$ Since $n$ is odd, $n + 1$ is even, which makes this equivalent to $0 \pmod{n!}.$ Therefore, the entire thing is equivalent to $0 \pmod{n!},$ which is a clear contradiction.

Therefore, by Pigeonhole, at least one residue class is covered by $S$ at least twice.

Otherwise $S(a)$ are distinct and the sum of $S(a)$ over all $a$ will be $\equiv \frac{n!}2\pmod{n!}.$ However it is not hard to show that this sum is $n!\left(\frac{n+1}2\right)\sum_{i=1}^n c_i\equiv 0\pmod{n!}.$


Can any one help with this tough graph theoritic problem?

Pollutant Control

It's your first day in Quality Control at Merry Milk Makers, and already there's been a catastrophe. You've discovered that a shipment of bad milk has been sent out. Unfortunately, you didn't discover this until the milk was already into your delivery system, a rather large and complex affair. You do, however, know which grocer that milk was destined for, but there may be multiple ways for the milk to get to that store.

The delivery system is made up of a several warehouses, with trucks running from warehouse to warehouse moving milk. While the milk will be found quickly, it is important that it does not make it to the grocer, so you must shut down enough trucks to ensure that it is impossible for the milk to get to the grocer in question. Every route costs a certain amount to shut down. Find the minimum amount that must be spent to ensure the milk does not reach its destination, along with a set of trucks to shut down that achieves this goal at that cost.

INPUT
Two space separated integers, N and M. N (2 <= N <= 32) is the number of warehouses that Merry Milk Makers has, and M (0 <= M <= 1000) is the number of trucks routes run. Warehouse 1 is actually the productional facility, while warehouse N is the grocer to which which the bad milk was destined.

Truck routes: three space-separated integers, Si, Ei, and Ci. Si and Ei (1 <= Si,Ei <= N) correspond to the pickup warehouse and dropoff warehouse for the truck route. Ci (0 <= Ci <= 2,000,000) is the cost of shutting down the truck route.

4 5
1 3 100
3 2 50
2 4 60
1 2 40
2 3 80

OUTPUT

The first line of the output should be two integers, C and T. C is the minimum amount which must be spent in order to ensure the our milk never reaches its destination. T is the minimum number of truck routes that you plan to shut down in order to achive this goal. The next T lines sould contain a sorted list of the indexes of the truck routes that you suggest shutting down. If there are multiple sets of truck routes that achieve the goal at minimum cost, choose one that shuts down the minimum number of routes. If there are still multiple sets, choose the one whose initial routes have the smallest index.

60 1
3

not quite sure, but i think that this was a min-cut problem

Yup... Straitforward minimum-cut problem... You can read about it in the "network flow" section in USACO.

The part with "If there are still multiple sets, choose the one whose initial routes have the smallest index. " can be done by multiplying the distance by 1000 and add the index of the route (i.e. the first route with C1 as cost has "new edge cost" = C1 * 1000 + 0, the second route with C2 as cost has "new edge cost" = C2 * 1000 + 1, etc...).

Thanks a lot webbie. I did not read that tutorial well. So I missed this!

Anyhow thanks again.

Well, I think I will try to code this tomorrow. After that I want to try the shuttle puzzle at the same section. (www bbb) remember? Well, in worst case (n=12) the different state can be 67603900. HUGE! How to keep track of these? Isn’t it backtracking(BFS)? One told me it may be solved in constant time I mean no backtracking just printing soln. Is this true? I don’t know. Can you plz clarify me which method should be used?

Btw, in which section you r now?

I've finished USACO... ;)

Hm... That's one of the stupidiest tasks in USACO... You have to analyze the solution...

If you write out the example solution on a paper (i.e. write the marbles on a paper, where first "line" on paper is the "pre-move", second "line" is the "first move", third "line" is the "second move", etc).

Do you see a "choose marble" pattern? :D

If not... Just ask again. ;)

I can't say anything except WOW!!! for ur performance!

Btw, have u passed ur IOI years? or going to participate this IOI? :roll:

Well, took silver in 2004...

Going there this year too... :D

And... Got 2 more years left (not counting with this year). ;)

USACO isn't really all that hard, but takes a lot of time to complete (especially if you get stuck :( ).

Btw, hope to meet you there. ;)

WOW! But unfortunately this will be my last year. my country is going for the first time. and i am this year in july 19. And next year i will be in university according to the education system of our country :(

So haha..

Hey webbie! I solved the spin problem in the first attempt. taking highest time limit to 10000. but the official soln says it is enough to assume that only 360. :(

Anyhow, It was ez anyway ;)

Oh! i forgot to ask: can u tell me why the highest limit is 360?

Assume a wheel's speed is x degrees per second. (x is a integer, according to the task)

So... what happens after 360 seconds? Well... 360 degrees = "back to original position", so, after 360 seconds, the wheel has rotated x * 360 = 0 degrees! :D


A line contains the points $ (\minus{}1, 6)$, $ (6, k)$ and $ (20, 3)$. What is
the value of $ k$?

hello, setting $ y\equal{}mx\plus{}n$ and put the coordinates of the points $ (\minus{}1;6)$ and $ (20;3)$ in this equation
we get the system
$ 6\equal{}\minus{}m\plus{}n$
$ 3\equal{}20m\plus{}n$
solving this we get
$ m\equal{}\minus{}1/7$ and $ n\equal{}41/7$
and from here we get $ k\equal{}5$.
Sonnhard.

Hiya folks!

Here's how I do it:

There's a horizontal distance of 21 (20-(-1)) between the two x points   -1, and 20.
There's a vertical distance of 3 (6-3) between the two y co-ordinates of said points.

Therefore: for every 1 unit the line goes down, it goes over -3/21 units, or -1/7 units.

If we want to go over by 7 points (From -1, to 6) we move down by (-1/7)*(5) units, or, down -1 units.
If we're ngoing down 1 unit from 6, we will end up at 5.

And that's your answer: 5


proof that: a majorate convex function with real variable is constant

You mean "[i]a bounded from above convex function defined on the entire real line is constant[/i]"?

yes that what i mean,and i think i have just found a solution,i wish you'll find better solutions  :D

It is next to obvious: if $ (x,f(x))$ and $ (y,f(y))$ with $ x<y$ are two points on the graph, then the parts of the graph to the left of $ x$ and to the right of $ y$ lie above the line joining the points. If this line is not horizontal, this implies unboundedness of $ f$ from above.


Hi!
$x^{n}+y^{n}=z^{n}$

I need the proof of some special cases of FLT: n=3,4,5,7. I'm asking this proofs because I was told that this were the simplest cases to prove. Any proof, link or help of how to prove it will be thanked. Bye for now guys!

EDIT: What about the proof of n=2k (n=4,6,8,10...)

I think that here's the n=4 case (look E98), but it is in Latin, so I can't reading... any help for any case asked in english? http://www.math.dartmouth.edu/~euler/

Fermat solved the case where n=4 using infinite descent. The proof is very straight forward but fairly long. (For the cases where n=2k it suffices to prove the theorem for n=k)


MATHCOUNTS
modular arithmetic
calculus
integration

Prove that the sum of three consecutive perfect squares can never give a perfect square.(Hope this isn't transferred to mathcount :lol: )

[hide="General hint"]Whenever in a problem we have ODD number of consecutive numbers, write them as going both ways from the middle one - i.e. three numbers are $x-1,x,x+1$, five numbers are $x-2,x-1,x,x+1,x+2$ etc. That simplifies the expressions greatly.

And yes, mod 3 is a key hint :)[/hide]

[hide]

Now since we have three consecutive integers, $x-1, x, x+1$

One has to be a multiply of 3, one has to leave a remainder of 1 when divided by 3 and one has to leave a remainder of 2 when divided by 3.

w.l.o.g

$x-1\equiv 1\pmod{3}$

$x\equiv 2\pmod{3}$

$x+1\equiv 0 \pmod{3}$

$\implies (x-1)^2 + x^2 + (x+1)^2 \equiv 1^2 + 2^2 + 0^2 \pmod{3}$

$\therefore (x-1)^2 + x^2 + (x+1)^2 \equiv 2 \pmod{3}$

however, a square number can only be $\equiv 1$ or $0 \pmod{3}$

$\therefore$ the sum of three consecutive squares will never be a square also.

[/hide]

[quote="shyong"][quote="eminem"]this is a dumb method i guess,  :? but...

let the squares be $x^2 ,(x+1)^2 , (x+2)^2$

summing  them will give us  $3x^2+6x+5$

for this to be a perfect square , D=0

but D will come = -24

hence it cant be a perfect square.[/quote]

it cannot be done in such way ... since $3x^2+6x+5=k^2$ for integer $k$ . So you cannot directly take discriminant of LHS .

[hide="hint"]
Consider mod 3 ...
[/hide][/quote]

hey shyong , does that mean that $3x^2+6x+5$  is not a square for x being integral , but may be a square for x being non-integral?

I think you can do the $D=0$ thing only when the R.H.S is 0 eminem.

Well, for a solution showing that $3x^2+6x+5=k^2$ has no integer solutions just see this [url]http://www.artofproblemsolving.com/Forum/viewtopic.php?highlight=3n%2B2&t=66213[/url]. (LHS is 2 more than a multiple of 3.) Prov'n.

[quote="riddler"][hide=" is this right?"]
Say the consecutive no.s were $(x-1)^2$, $x^2$, $(x+1)^2$
So, adding them gives
$3x^2+2=k^2$
We have to prove that this does not hold true if $x$ and $k$ are integers
So,
$2x^2+2=(k-x)(k+x)$
$2(x^2+1)=(k-x)(k+x)$
So,
$(k-x)=2$ then $(k+x)=x^2+1$
This implies that:
$2+x=x^2-x+1$
$2=(x-1)^2$
which shows $x$ is not an integer

Then the other possibility is that:
$(k-x)=1$ then $k+x=2(x^2+1)$
adding the 2
we get
$2k=2x^2+3$
which shows $k$ can never be a whole number.
similarily we can also show that the equations:
$(k-x)=x^2+1$ and $(k+x)=2$ dont hold for integral values of $k$ and $x$

PROVED?
[/hide][/quote]
$(k-x)=2$ then $(k+x)=x^2+1$
Can you equate it?

[quote="riddler"][hide=" is this right?"]
Say the consecutive no.s were $(x-1)^2$, $x^2$, $(x+1)^2$
So, adding them gives
$3x^2+2=k^2$
We have to prove that this does not hold true if $x$ and $k$ are integers
So,
$2x^2+2=(k-x)(k+x)$
$2(x^2+1)=(k-x)(k+x)$
So,
$(k-x)=2$ then $(k+x)=x^2+1$
This implies that:
$2+x=x^2-x+1$
$2=(x-1)^2$
which shows $x$ is not an integer

Then the other possibility is that:
$(k-x)=1$ then $k+x=2(x^2+1)$
adding the 2
we get
$2k=2x^2+3$
which shows $k$ can never be a whole number.
similarily we can also show that the equations:
$(k-x)=x^2+1$ and $(k+x)=2$ dont hold for integral values of $k$ and $x$

PROVED?
[/hide][/quote]

not nessecary . What if $x^2+1=10$ ? Then you can also break $x^2+1$ into a composite number .... ie 5x2

[quote="riddler"][quote="shyong"]

not nessecary . What if $x^2+1=10$ ? Then you can also break $x^2+1$ into a composite number .... ie 5x2[/quote]

$x^2+1=k-x$
$2=k+x$
Then,

$2-x=x^2+1+x$
$2=(x+1)^2$
 :huh:[/quote]

How can you eqwuate it?Not necessary that one of them has to be 2.Wait,Are $k-x$ and $k+x$ in simplest form(Prime nos.?)

[quote="pianoforte"][hide]$n^2\equiv 0,1 (\mod3)$ because $n\equiv 0,1,2 (\mod 3)$ so $n^2\equiv 0^2,1^2,2^2\equiv 0,1,4\equiv 0,1 (\mod 3)$

adding $(x-1)^2,x^2,(x+1)^2$ we get $3x^2+2$

$3x^2+2 \equiv 2 \mod 3$ but since a square is only congruent to 0,1 mod 3, the sum of three consecutive perfect squares can never give a perfect square.[/hide][/quote]

That's what I did, and not only does my chinese book agree, but the AoPS book does too. Thus it's probably correct  :D


geometry
circumcircle
search
geometry proposed

Let $ L$ be the Lemoine point of triangle $ ABC$, i.e. - $ L$ is the isogonal conjugate of the centroid of triangle $ ABC$ . $ A$ point $ A_1$ is chosen inside triangle $ ABC$ so that $ \hat{A_1AB} \equal{} \hat{A_1CA}$ and $ \hat{A_1AC} \equal{} \hat{A_1BA}$ . Points $ B_1,C_1$ are defined similarly . Prove that $ A_1,B_1,C_1$ , and $ L$ are concyclic. :P  :)

Clever problem.

[u][b]Proof:[/b][/u] First, notice that by adding up these equalities and doing some manipulations, we obtain that $ \angle BA_1C \equal{} 2 \angle BAC$. Hence, $ B, C, O, A_1$ are concylic. Now, by adding up the equalities in reversed order, we obtain that $ \angle BA_1A \equal{} \angle CA_1A$, implying that $ AA_1$ is the bisector of $ \angle BA_1C$. This shows that $ AA_1$ must cut the circumcircle of $ BOC$ again in the midpoint of the large arc $ BC$ in the circumcircle of $ \Delta BOC$. Of course, this is also the intersection point of the tangent lines to the circumcircle of $ \Delta ABC$ in points $ B$ and $ C$, hence a point on the symmedian $ AL$.

We can now easiley see that $ A_1$ has to be the projection of $ O$ onto $ AL$, and we can easiley verify that this point indeed does the trick. Similarly for $ B_1$ and $ C_1$. It follows that $ A_1,A_2,A_3$ all lie on the circle with diameter $ OL$.

[u][b]Remarks:[/b][/u] In the proof, $ O$ denotes the circumcenter of $ \Delta ABC$. I never heard of the circle with diameter $ OL$ before, but maybe this circle has been investigated in the past, and maybe some other ETC centers lie on it. Any references?

You will find more than enough references if you search for "second Brocard triangle" - this is how triangle $ A_1B_1C_1$ is called.

  darij

Of course, thank you Darij. I don't know how I missed that...


$ABC$  is  a triangle , and  $ x , y , z >0 $. Show that
$x^2+y^2+z^2 \geq (3-\frac{a+b}{c})\cdot xy + (3-\frac{a+c}{b})\cdot xz + (3-\frac{b+c}{a})\cdot yz $

Thanks!

hello, so it looks better
$x^2+y^2+z^2 \geq (3-\frac{a+b}{c})\cdot xy + (3-\frac{a+c}{b})\cdot xz + (3-\frac{b+c}{a})\cdot yz $
Sonnhard.


calculus
integration
function
trigonometry
calculus computations

Your answer is correct. :)
This problem was posted in 1979.

$f(a) \rightarrow f(x)$ in the first line ?, but which is trivial.

Sorry :(

[b]Mistake[/b]
$f(a)=\left \{ \begin{array}{ll}a \cos x+b \sin x & (0 \le x \le \frac{\pi}{2}) \\ a \cos x-b \sin x & (-\frac{\pi}{2}\le x \le 0) \\ \end{array}\right.$

[b]Right[/b]
$f(x)=\left \{ \begin{array}{ll}a \cos x+b \sin x & (0 \le x \le \frac{\pi}{2}) \\ a \cos x-b \sin x & (-\frac{\pi}{2}\le x \le 0) \\ \end{array}\right.$

[quote="kunny"]Find the values of real numbers $a,\ b$ for which the function $f(x)=a|\cos x|+b|\sin x|$ has local minimum at $x=-\frac{\pi}{3}$ and satisfies $\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}}\{f(x)\}^{2}dx=2$.[/quote]

$\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}}\{f(x)\}^{2}dx=2$

$\implies \int_{0}^{\frac{\pi}{2}}\{f(x)\}^{2}+\{f(-x)\}^{2}dx=2$

$\implies 2\int_{0}^{\frac{\pi}{2}}\{f(x)\}^{2}dx=2$

$\implies \int_{0}^{\frac{\pi}{4}}\{f(x)\}^{2}+\biggl\{f\biggl(\frac{\pi}{2}-x\biggr)\biggr\}^{2}dx=1$

or

$\int_{0}^{\frac{\pi}{4}}\{a\cos x+b\sin x\}^{2}+\{a\sin x+b\cos x\}^{2}dx=1$

$\implies\int_{0}^{\frac{\pi}{4}}(a^2+b^2)+4ab\sin x\cos x\,dx=1$

$\implies\biggl((a^2+b^2)x+2ab\sin^2 x\biggr)_{0}^{\frac{\pi}{4}}=1$

$\implies\frac{\pi}{4}\biggl(a^2+b^2\biggr)+ab=1$

Since $f(-x)=f(x)\ ,\  f(x)=a|\cos x|+b|\sin x|$ has local minimum at $x=-\frac{\pi}{3}\implies f(x)=a|\cos x|+b|\sin x|$ has local minimum at $x=\frac{\pi}{3}$

Consider $f(x)$ for $x\in\biggl(0,\frac{\pi}{2}\biggr)$

$\implies f(x)=a\cos x+b\sin x\ ,\ x\in\biggl(0,\frac{\pi}{2}\biggr)$

$\implies f'\biggl(\frac{\pi}{3}\biggr)=-a\sin \biggl(\frac{\pi}{3}\biggr)+b\cos \biggl(\frac{\pi}{3}\biggr)=0\implies b=a\sqrt3$

and

$f''\biggl(\frac{\pi}{3}\biggr)=-a\cos \biggl(\frac{\pi}{3}\biggr)-b\sin \biggl(\frac{\pi}{3}\biggr)>0\implies a+b\sqrt3<0\implies a<0$

$\implies\boxed{ a=-\frac{1}{\sqrt{\pi+\sqrt{3}}},\ b=-\frac{\sqrt{3}}{\sqrt{\pi+\sqrt{3}}} }$


[quote="Faressco"]Hiya

i need ur help plz

find the equation of the line passes through the point $Q=(3,2)$ and with slop is $m=1$.

cheers  :roll:[/quote]

[hide]y=mx+b
$2=3\cdot1+b$
$b=-1$
$y=x-1$[/hide]

[quote="Faressco"]Hiya

i need ur help plz

find the equation of the line passes through the point $Q=(3,2)$ and with slop is $m=1$.

cheers  :roll:[/quote]
what form..... ;)  :?
[hide="my answer"] this is a pretty easy problem and you can do it with a graph or without it. Ok, so since the slope is 1, you just have to subtract (1,1) from (3,2) until you get (0,x). In this case, it is (0,-1) so the y-intercept is -1. Then, following the equation y=mx+b, you get [b]y=x-1[/b] as your answer [/hide]

Or...

[hide]You can use the point-slope formula: $y-y_1=m(x-x_1)$ where $x_1$ and $y_1$ are one pair of points and $m$ is the slope.

$y-2=1(x-3)$
$y-2=x-3$
$y=x-1$  :P [/hide]

[quote="Faressco"]Hiya

i need ur help plz

find the equation of the line passes through the point $Q=(3,2)$ and with slop is $m=1$.

cheers  :roll:[/quote]

umm...

[hide="answer here"]u can use slope form which is $y=mx+b$.
plug in the $y$ and $x$ and $m$ with the points and slope given, so...

$2=(1)(3)+b$
$2=3+b$
$-1=b$

thus...

$y=x-1$

if u want it in the standard form, move the $y$ and $-1$ so that...

$x-y=1$[/hide]

[hide]this would be easiest to write in point-slope form...so it'd be y-2=1(x-3).[/hide]