The length of a face diagonal of a cube is 3 cm. What is the number of square centimeters in the surface area of the cube?

We have that $ s\sqrt{2}\equal{}d$, where $ s$= the side length of the cube, and $ d$= the length of a face diagonal.
So,
           $ s\equal{}\frac{3}{\sqrt{2}}\equal{}\frac{3\sqrt{2}}{2}$.
Then, using that the surface area of a cube is $ 6s^2$,
$ 6s^2\equal{}6(\frac{3\sqrt{2}}{2})^2\equal{}\boxed{27}$.


algebra
polynomial
advanced fields
advanced fields unsolved

Let $ n\geqslant 2$, and $ z_{1},\ldots , z_{n}\in\mathbb{C}$.
Find out $ P\in\mathbb{C}[X]$, s.t $ P\bigl( (X\minus{}z_{1})(X\minus{}z_{2})\cdots (X\minus{}z_{n})\bigr)\equal{}P(X\minus{}z_{1})P(X\minus{}z_{2})\cdots P(X\minus{}z_{n})$.
P.S.: I only have a partial answer, and I post it here hoping that some bigger tools can be used to crack this nut.

every $ P\equal{}X^{k}$ satisfies the equation. maybe I've misunderstood something, or we want [i]all[/i] solutions?

And those are the only solutions that work for general $ z_{i}$. (There are no others when $ z_{1}\equal{}\dots\equal{}z_{n}\equal{}0$.)

-oo-, you are right, I should I've been clearer, instead of
[quote="JC_math"]... Find out $ P\in\mathbb{C}[X]$, s.t ...[/quote]
I should have written ""... Find out [b][i]all[/i][/b] $ P\in\mathbb{C}[X]$, s.t ...".
In fact $ P\equal{}aX^{k}$ are solutions if $ a^{n\minus{}1}\equal{}1$, and of course $ P\equal{}0$.
If $ n\equal{}2$ these are the only solutions, but also if $ z_{1}, z_{2},\ldots, z_{n}$ is a regular polygon as well.
But in general???

mlok,
To answer your comment, my question was not
Let $ n\geqslant 2$, Find out all $ P\in\mathbb{C}[X]$, s.t for all $ z_{1},\ldots , z_{n}\in\mathbb{C}$ $ P\bigl( (X\minus{}z_{1})(X\minus{}z_{2})\cdots (X\minus{}z_{n})\bigr) \equal{} P(X\minus{}z_{1})P(X\minus{}z_{2})\cdots P(X\minus{}z_{n})$.

P.S.: I tried to edit my previous message, but I got "Sorry, but you cannot edit this post anymore. Ask a moderator to do it if it is really necessary.", strange????


The quantity of heat liberated when $ 2.00$ moles of aluminum oxide is formed under standard conditions is closest to

$ \textbf{(1)} \ 419 \ \text{kJ} \qquad \textbf{(2)} \ 838 \ \text{kJ} \qquad \textbf{(3)} \ 1680 \ \text{kJ} \qquad \textbf{(4)} \ 3350 \ \text{kJ}$

[quote="i_thirst_for_knowledge"]The answer is (4)
Here's why:
For forming of the aluminum oxide, we have a reaction:
4Al(s) + 3 O2 = 2 Al2O3
Heat released= Q= 2* (-1676)= -3352 Kj.
the number -1676 is obtained from the standard delta H of alumnium oxide. This delta H for both alumnium and oxygen are zero because they are at standard state.
You can get this number from the index of a chemistry book.[/quote]

Thanks a lot!


I like doing these old Math League Contests because they're enjoyable: here's a good review problem for area:
[b]Let there be acute triangle ∆ABC, such that AE, BF, and CD intersect at point P (each of these are lines to the opposite side of ∆ABC from each angle). If the area of ∆AFP is 40, the area of ∆CFP is 30, and the area of ∆CEP is 35, what is the area of ∆BPD?[/b]

I don't think that's really clear...
You say that the other points are on the sides opposite the angle, but if that were true, then point P would be there too, meaning that the the other three lines couldn't intersect point P...

Yeah. I agree with ZhangPeijin. The directions aren't very clear. Can you please accompany this with a figure or diagram?

Huh? Guys, there is an acute triangle ABC, and points E,F, and D on BC,AC, and D on AB, respectively.The areas of triangle AFP,CEP, and CFP Z-Coli gave.
Argh, I'm really not sure in this problem.
[hide]Since triangles APC and CPE have the same height, and [APC]=70,[CPE]=35, the ratio of AP to EP=2:1, inother words, AE is a median. For triangles ABE and ACE, they have the same base and altitude, so equal area;thus, the total area is 210.[/hide].

Yeah, probably wrong.

No, it's good.  I think

It's actually pretty clear, and Peijin, I don't see why point P would have to be on a side.  Just draw 2 of the cevians from 2 different angles and draw the third from the last angle to hit that intersection point.

cevian=line from an angle to the opposite side

And I'm not sure if this actually belongs in Classroom Math or not, most people probably wouldn't consider the ratio to find that one of the cevians was a median.

Yeah, but he said each of these are on lines opposite to the angle.
Meaning that Point P is on a side of the triangle.

Hence why you fail English.  Read the question.  The lines [b]intersect[/b] at point P.

Ohh...
Anyways, I didn't fail english.
I just got a A-...
-worst grade ever-

Okay, there are a couple of things which should be addressed:
1) The original problem had a picture but I don't have a scanner so I had to word it.  I think it's pretty clear, but if you have specific questions about the problem, I'll answer it.
2) P IS NOT NECESSARILY THE CENTROID.  That is assuming that the lines drawn all have the same properties==>however, all I said was that they intersect at point P.  Every line has a point that divides it into a 2:1 ratio (so no, 210 is not correct)

yeah, that's why I thought it was wrong.
Too tired to do anything right now.

Obviously, this problem uses side ratios that correspond to area ratios.  Hint: Let [CEP]=k, and then find the remaining areas in terms of k.  Set up some equations to solve for k, and later, solve for the remaining unknown areas.

Are you sure this is solveable based on the information given?
Seeing as the lines could reach the opposite side at any point?
Or maybe it's just because I suck at Geometry.

Also, I don't think Math League problems go in Classroom Math

If it's the High school kind, then no. I don't think the middle school kind would be this hard though.

Yeah, this problem is from the high school Math League, but I didn't think that you guys would have trouble with it.  I guess I'll post the answer soon, then.  Seriously though, when I did it I though it wasn't too hard.  Sorry guys :(

Some of us are rather bad at geometry  :D

omg i got it!!!

I will include diagrams later

[hide="My Solution"]If the heights of two triangles are equal, then their areas are in the ratio of their bases.  In this case, $ \triangle AFP$ and $ \triangle CFP$ have the same height.  We know that the ratio of the bases must be $ 4: 3$.  $ AF: CF \equal{} 4: 3$.  So now that we have the ratio of the bases, we can assign weights to $ A$ and $ C$.  The weight of $ A$ is $ 3$ and the weight of $ C$ is $ 4$.  Now, let the weight of $ B$ be $ x$.  Therefore, $ BE: CE \equal{} 4: x$.  We know that the areas are in the ratio of the bases so the area of $ \triangle BEP \equal{} \dfrac{140}{x}$.  Since the weight of $ A$ is $ 3$ and the weight of $ B$ is $ x$, $ AD: BD \equal{} x: 3$.  Now, let us take the big triangles, $ \triangle ABE$ and $ \triangle ACE$.  We know that the area of $ \triangle ACE$ is $ 40 \plus{} 35 \plus{} 30 \equal{} 105$.  We also know that the areas are in the ratio $ 4: x$.  The area of $ \triangle ABE$ is $ 105\times\dfrac{4}{x} \equal{} \dfrac{420}{x}$.  Therefore, the area of $ \triangle ABP$ is $ \dfrac{280}{x}$.  The ratio of the area of $ \triangle ADP$ to the area of $ \triangle BDP$ is $ x: 3$.  We find that the area of $ \triangle ADP \equal{} \dfrac{280}{x(x \plus{} 3)}\times x \equal{} \dfrac{280}{x \plus{} 3} and the area of$\triangle BDP=\dfrac{280}{x(x+3)}\times3=\dfrac{840}{x(x+3)}.  Now, let us take $ \triangle ABF$ and $ \triangle CBF$.  The ratio of the areas of the triangles is $ 4: 3$.  Adding the areas of all the little triangles up, we get the areas of the big triangles.
\[ \dfrac{4}{3}(65 \plus{} \dfrac{140}{x}) \equal{} 40 \plus{} \dfrac{280}{x}
\]

\[ \dfrac{260}{3} \plus{} \dfrac{560}{3x} \equal{} \dfrac{40x}{x} \plus{} \dfrac{280}{x}
\]

\[ \dfrac{260x}{3x} \plus{} \dfrac{560}{3x} \equal{} \dfrac{40x \plus{} 280}{x}
\]

\[ \dfrac{260x \plus{} 560}{3x} \equal{} \dfrac{120x \plus{} 840}{3x}
\]

\[ 260x \plus{} 560 \equal{} 120x \plus{} 840
\]

\[ 140x \equal{} 280
\]

\[ x \equal{} 2
\]
The area of $ \triangle BPD$ is $ \dfrac{840}{x(x \plus{} 3)} \equal{} \dfrac{840}{2\times5} \equal{} \dfrac{840}{10} \equal{} \boxed{84}$[/hide]

The answer is correct, good.  The answer and solution was already up on the high school math section, but it looks like a different solution.  Excellent job.

[quote="Z-coli"]I like doing these old Math League Contests because they're enjoyable: [/quote]
where do you find these problems?

I go to a math team every Sunday where they have tons of old math books.  Our coach give me the book, it's pretty fun.


Find all positive integers $ x;y;z;n$ sauch that $ x!\plus{}y!\plus{}z!\equal{}5n!$ where $ k!\equal{}1*2*3*..*k$

Assume that $ x\geq y\geq z>0$ then we have: $ 5.n!\leq 3.x!<5.x!\Rightarrow n<x\Rightarrow n\plus{}1\leq x$
Now $ 5.n!>x!\geq (n\plus{}1)!\Rightarrow 5>n\plus{}1\Rightarrow n\equal{}1,2,3$
Consider $ 3$ cases we have result!

Interesting solution tdl!
my solution :

 Note that if we take the bigest  possible solution, we get: x=y=z=n : and then
3n!=5n!

impossible,so $ a\ne b$, and $ a\ne c$, but $ b$ can be equal to $ c$,.
Now,
For n=0

RHS=5,

LHS=$ x! \plus{} y! \plus{} z!$ So the only solutions are $ (x,y,z)\equal{}{(2,2,1);(2,2,0)}$
and  simmetricaly.

$ n\equal{}1$

$ RHS\equal{}5$,
Same solution

$ n\equal{}2$

$ RHS\equal{}10$ and $ 10 \equal{} 2\plus{}2\plus{}6$ the only possible partition,
so  $ (x,y,z)\equal{}{(2,2,3)}$  and permutations

$ n\equal{}3$

$ RHS\equal{}5\cdot 3!\equal{}30$
no solutions

$ n\equal{}4$

$ 5n!\equal{}120$,
$ x! \plus{}y!\plus{}z!\equal{} 5!$which is $ x! \plus{}y!\equal{}5! \minus{} z!$
so  $ LHS\equal{}5/( x!\plus{}y!)$       $ RHS\equal{}4! \minus{}5/z!$
but since $ 4 \geq z\geq 0$, the result found previously is absurd.
Besides if we take the bigest  possible solution, we get:$ x\equal{}y\equal{}n$ : and then $ 3n!\equal{}5n!$
impossible.

For $ n\geq 5$,  $ x! \plus{} y! \plus{} z!$=5n!
so $ \frac{(x!\plus{} y! \plus{}z!)}{5}\equal{}x! (x\plus{}1)\cdot...\cdot n$
 supposing that $ x> (z,y)$.
Dividing by x! we get $ (\frac {1}{5})\plus{} \frac {(y! \plus{}z!)}{5} \equal{}
 (x\plus{}1)\cdot...\cdot n$
So impossible since LHS is not an integer and RHS is.
So the only solutions are
$ (x,y,z,n)\equal{}{ (2,2,1,0) (2,2,0,0) (2,2,1,1)(2,2,0,1),(2,2,3,2)}$
and all the permutations of $ (x,y,z)$.


sorry  :(
Edit
[quote="AnhHungThamLang"][i]Let[/i] $\large a,b,c\ge0$ [i].prove that[/i]
...............
$\large(1+\sqrt{\frac{a}{a+b}})(1+\sqrt{\frac{b}{b+c}})(1+\sqrt{\frac{c}{c+a}})\leq \frac{10+7\sqrt{2}}{4}$
[b]Undefined Mixing Variables[/b]  :wink:
[b]@pvthuan:[/b]  Thầy thấy bài toán này thế nào ạ!  :rotfl: Thấy hãy nhắn lại cho em qua nick [b]silenthero_k09[/b] nhé. :D
Đề này mới đúng thầy ạ,em đánh nhầm dấu đẳng thức
 [/quote]

Please don't post repeat in future!
http://www.mathlinks.ro/Forum/viewtopic.php?t=138945
You can edit your post in that topic.


Ross Mathematics Program
summer program
PROMYS
AMC
USA(J)MO
USAMO
AwesomeMath

What is more prestigious, the Ross Program/ PROMYS or making USAMO??

Don't worry about prestige just try to do what you enjoy.  Regardless of that, USAMO is definitely far more prestigious than any summer program short of MOP/RSI.

Are the two mutually exclusive?

Seriously, if you're worried about anything other than college applications, there's not much relation between the two.  Ross and PROMYS are [b]not training camps.[/b]  They are designed to get you interested in, and better at, [b]mathematics[/b] - not contest mathematics, but the kind of mathematics you might want to spend the rest of your life doing and go to graduate school for.  The USAMO, on the other hand, is a high school competition.  It would be fair to say that PROMYS is the reason I became less interested in the USAMO.

For what it's worth, a good letter of recommendation from PROMYS is probably going to help your application more than making USAMO, but please don't think about either in such terms.

They are not mutually exclusive.

I enjoyed AwesomeMath and plan to apply to PROMYS, MathPath or Ross this year. Like many of AoPSers, I do math because I enjoy it. I am sure most of AoPSers also do other math competitions, such as Mandelbrot, ARML, USAMTS etc.

But, in my mind, USAMO always has a special place in our heart as this is the only way we can qualify for the USA IMO team someday. I will continue to practice math and continue to enjoy it. Once a math lover, forever a math lover, period.

yea i did well in all my other comps: mandelbrot, RIML, USAMTS
But FAILED the AMC's this year and did not make AIME. Very dissapointing....

[quote="mround"]They are not mutually exclusive. [/quote]
Rhetorical question!

[quote="mround"] plan to apply to PROMYS, MathPath or Ross this year.[/quote]
Isn't the PROMYS deadline in a few days?

[quote="mround"]USAMO always has a special place in our heart as this is the only way we can qualify for the USA IMO team someday. I will continue to practice math and continue to enjoy it. Once a math lover, forever a math lover, period.[/quote]
But that's exactly my point!  A love of math is lifelong, but the period in which you can qualify for the IMO team is 4 years (plus or minus).  What I'm trying to say is that I got much more out of going to PROMYS as a mathematician than I got out of qualifying for the USAMO.

[quote="simo14"]idk y ppl r always worrying abt prestige but i'd say usamo is harder to make[/quote]

Prestige makes you look good. It's like saying "I go to Stanford/Top University" and "I go to <insert something>"

Obviously it matters because society judges people based on their past. That said, it's obvious that the bragging rights aren't what matter, but the achievements themselves.

[quote="shelly32494"]errrr no
promys deadline is in like end of may.[/quote]

MAY 30th to be precise.t0rajir0u you should be a counselor ^^
I've finished 9 of the problems and typed them up though: 1-5, 7-10

I'm applying to be a counselor, but I'll be skimming the counselor deadline (which is what I was thinking of, my bad) pretty closely so that might be a problem.

[quote="james4l"]Let's just say that I do not know what PROMYS is but know what USAMO is. That must mean that USAMO is more prestigious.[/quote]
Horibble logic. Most students don't know what IMO is.

Well let's take a poll - mods, please make one.

I'm fairly certain that PROMYS is something that "most students" would not know.

That's completely irrelevant to the question being asked.  When people talk about prestige, it's usually with reference to college applications, so it's less important what students are aware of and more important what college admissions officers are aware of, but again, this is [b]still the wrong perspective[/b] to take with respect to how you decide to allot your time.

If you make IMO is it true that (almost) every college would accept you (or maybe even in other countries)? Just curious...

Not if they don't care about math!  This is both a college-specific decision and [b]still the wrong perspective.[/b]  If you're good enough to make IMO, especially from the United States, chances are you've got a lot of other good stuff on your application.

Also, if you are talented enough to make IMO, chances are you won't want to apply to, say, a liberal arts college, which probably won't care about math at all, but you'll probably have a better chance at an engineering/math college.  Still, torajirou has the right point: if you only want to get to IMO for college, then you should reset your priorities or just don't include math competitions in your priorities.  Furthermore, if all you care about is college, chances are you won't make IMO anyways because of stress over grades, extracurriculars, and focusing on those things that "look good" rather than math, which should be done because you want to.


AwesomeMath
summer program
AMC
USA(J)MO
USAMO
AMC 8
AMC 10
\/closed

In terms of AIME/USAMO preparation, which one would be more useful? Any suggestions would be greatly appreciated.

I think it depends on your level of math.

That question may be impossible to answer.  This is the first year of the AwesomeMath program and the WOOT program itself has evolved a lot over the past year.  You might be better off asking specific questions about each program or their instructors.

I have a question......Is USAMO Awesome Math Camp? I have been hearing many abbreviated tests and competitions lately. I am pretty confused.

USAMO=United States of America Mathematical Olympiad

AMC8, AMC10, and AMC12 have AMC=American Mathematics Competition.

AIME = American Invitational Mathematics Examination

USAMO= USA Math Olympiad

MOP/MOSP = Math Olympiad Summer Program.

Awesomemath, Mathpath, Mathcamp = No common abbreviation (I think).

W00t = Worldwide Online Olympiad Training.

I would think WOOT would be a better course, if only because of the quality of instruction.

But if it takes you a little while to see things (like me) then an online classroom might not be best.  However, during math jams, I can usually grasp a concept I missed by going back and reviewing transcripts.  So maybe the online classroom isn't a setback after all...

[quote="b-flat"]WOOT has a definite advantage in the fact that you can always look back at the transcripts if you need any help or want to review.  The transcripts are a very valuable resource that can help you a lot later, when the class is over.  Also, I think you get lots of good feedback from the instructor (if it is anything like the feedback you get in the other classes) that really helps.

Because the AwesomeMath program is new, the people who run it might not have had as much experience running it, so it could potentially have more problems.  However, you would have to look at the website of the people who run the AwesomeMath program to see what it is like.

Basically, there is not as information about the AwesomeMath program as there is for the WOOT program.[/quote]
I haven't taken WOOT yet, but I would say from what I saw in the Math Jam yesterday it looks like it will be a very helpful program.  :)

Actually, the AwesomeMath program (which is abbreviated as AMSP for AwesomeMath Summer Program) is very new, but the instructors are definitely not inexperienced; many of them are MOP instructors. Here's the faculty list if you're interested:
http://www.awesomemath.org/staff.html

However, WOOT is definitely less expensive than AwesomeMath, since you don't have to live there. (Or were you talking about just participating in the Year-Round program?)

I would say that if you can (if your budget allows and you have enough time), the best thing would be to do both.

From the title of this topic, I think he's talking about [url=http://www.awesomemath.org/amyhome.html]the AwesomeMath Year-round[/url], not the Awesome Math Summer Program.


geometry
ratio
analytic geometry
circumcircle
power of a point

Let an arc $AB=90^\circ$ of a circle . We produce chord $AB$ and take point $C$ , such that  $BC=AB$. Let  $CD$ the tangent segment to the arc  and $K$  the foot of the perpendiculer of  $A$  to  $BD$. Prove that  $KB=2KA$.

[u]babis[/u]

 [i]Have you ever seen this problem before ?[/i]

i think $C$ is on the line $\overline{AB}$, and $D$ is the point on the minor arc $\widehat{AB}$ of the given circle such that $\overline{CD}$ is tangent to the circle.

[hide]
Let $O$ be the center of the circle and $E$ be the point opposite $A$ on the circle. Then $AC=2AB$ and $AE=2AO$ so triangles $\triangle AOB$ and $\triangle AEC$ are similar by SAS.

Applying the side ratio to the third pair of sides, $CE=2OB=2OE$. Let $\alpha =\angle OCE$ and $\beta =\angle COE$. Then $\angle COD=\beta$ since triangles $\triangle COE$ and $\triangle COD$ are congruent.

Finally, $\angle AOD=180^\circ-2\beta =2\alpha$, which gives us $\angle ABD=\alpha$ since the inscribed angle is half of arc $\widehat{AD}$. Then $\triangle AKB$ is similar to $\triangle OEC$, so $KB=2KA$, as desired.
[/hide]

[quote="me@home"]A couple questions.
1. Produce chord AB (does this mean just connect the segment AB?)
2. Take point C (anywhere in the plane under the following constraint, or is it on line AB?)
3. CD the tangent segment to the arc (what does this mean?)

I tried to make I diagram but I coulldn't, at least not from my undestanding.[/quote]

 Really sorry! Probably I transleted the greek text in a direct way.
[color=red]a)[/color] We extend $AB$ and on ray $AB$ we take segment $BC= AB$
[color=red]b) [/color]From point $C$ we draw the tangent $CD$
[color=red]c) [/color]In (very nice !) solution by scorpius 119 , I hope you 'll clear the enounciation.
[color=red]d)[/color] Try for a new solution , if there is .
[u]babis[/u]

Alternative solution:

[hide]Clearly, $\angle ADB = \frac{3\pi}{4}$, so we conclude that $\left|KD\right|=\left|KA\right|$   (1)

By power of a point, we know that $\left|CD\right|^{2}= 2 \left|AB\right|^{2}$.

Now, in $\Delta ACD$, a median is $DB$. Therefore, it's length is given by $\left|BD\right|^{2}= \frac{1}{4}\left(2\left|AD\right|^{2}+2\left|CD\right|^{2}-\left|AC\right|^{2}\right)= AK^{2}$
Or $\left|BD\right|=\left|AK\right|$     (2)

Adding $(1)$ and $(2)$ together, we get what we wanted.[/hide]

Solution with coordinates[hide]Let $O$ be the center of the circle. We put $O(0,0), A(0,1)$ and $B(1,0)$. Then we found $C(2,-1), D(\frac{4}{5},\frac{3}{5})$ and $K(\frac{3}{5},\frac{6}{5})$. Then $AK= \frac{2}{\sqrt10}$ and $KB=\frac{4}{\sqrt{10}}$. So $KB=2KA$.[/hide]
It's ugly but mechanical ... :rotfl:

My solution uses only some concyclic points...This is the solution I found during the competition.

             [u][b]  SOLUTION[/b][/u]
It is enough to prove that $D$ is the midpoint of $KB$.Let us consider the midpoint $M$ of segment $AB$.I have to show that $\widehat{MDB}=90^{o}$.But $\widehat{ODB}=90^{o}$, so i have to prove that $\widehat{MDO}=\widehat{BDC}$, or $\widehat{DAC}=\widehat{MCO}$ $\Longleftrightarrow CO//AD$.
We now cosider the point $A'$, the symmetric point of $A$ with respect to $O$ and denote $Cx$ the ray $CD$.
Then we can easilly show that $\widehat{ADx}$ $=\widehat{AA'D}$ $=\widehat{OCD}$ , which is enough to prove that $AD//OC$ and we are Q.E.D.

[quote="me@home"]Nice solutions guys, Btw I understand the problem now :D
here is a diagram [img]6993[/img]

[quote="Nick Rapanos"]My solution uses only some concyclic points...This is the solution I found during the competition.

             [u][b]  SOLUTION[/b][/u]
It is enough to prove that $D$ is the midpoint of $KB$.Let us consider the midpoint $M$ of segment $AB$.I have to show that $\widehat{MDB}=90^{o}$.But $\boxed{\boxed{\widehat{ODB}}}=90^{o}$, so i have to prove that $\boxed{\boxed{\widehat{MDO}}}=\widehat{BDC}$, or $\widehat{DAC}=\boxed{\boxed{\widehat{MCO}}}$ $\Longleftrightarrow CO//AD$.
We now cosider the point $A'$, the symmetric point of $A$ with respect to $O$ and denote $Cx$ the ray $CD$.
Then we can easilly show that $\widehat{ADx}$ $=\widehat{AA'D}$ $=\widehat{OCD}$ , which is enough to prove that $AD//OC$ and we are Q.E.D.
[/quote]
Double box:
1. The double boxed angle should be ODC, right?
2. / 3. It appears like the first and second angles are equal, as you claim, but how is this trivial? I drew in the circumcircle just in case, but still, what am I missing... it seems non obvious to me.

That's all, thank you[/quote]

Yes you are right its not obvious...Firstly, i wanted to write $\widehat{ODC}$ as you understood!
Now I have to prove that $\widehat{MDO}=\widehat{BDC}$.

But $\widehat{BDC}=\widehat{BAD}$ (because $CD$ is tangent to the cicle) and $\widehat{MDO}=\widehat{MCO}$ because of the concyclic points you have drawn in your shape.

I think it is clear now!Ask me if you have any questions without any doubt!
Bye

Thanks for answering my questions, but I am still a little confused... I drew that circle in the diagram but I do not know [b]why[/b] they are concyclic, in your proof it kind of looks like you assumed it :maybe: but I am not sure, that is what I was really asking about (we know they are concyclic from the diagram but we haven't proven it yet or so it appears to me)

Sorry I didnt prove that these points are concyclic because it was too easy to prove...
Look $\widehat{ODC}=\widehat{OMC}=\widehat{OA'C}=90^{o}$

Sorry about that, I truly did not see that and t didn't seem "trivial" to me at least... thank you for pointing that out :oops:


Suppose there is a language similar to the English language, but any letter combination forms a word.  For example, "gdsf" is a word. How many four letter words can be formed from the word, "MISSISSIPPI"?.

How many three letter words can be formed from the word, KARAT?

Rezult of "MISSISSIPPI" is: $\frac{11!}{4!\cdot 4!\cdot 4!}$
Rezult of KARAT is $\frac{5!}{2!}$

Uh, the first one gives you a non-integer.  :wink:
I'm no good at these, but shouldn't it be:
$\frac{11!}{4!4!2!}$?

You guys are all counting the number of permutations when all the letters are used, but the questions ask when 4 letters and 3 letters are used.

Ah, well, isn't it:
$\frac{11!}{4!4!2!7!}$?
...But that isn't a whole number; never mind, I fail.

I actually do not have the answer. A teacher of mine messed up while making a question for a quiz, and I just posted it here because maybe there's some tricky counting technique you could use.

is it 176 for the first question (the one with MISSISSIPPI and 4 letter words)

If someone could post a solution to the MISSISSIPPI problem as well as a general method of doing problems like this, that would be great.
I admit; I'm curious.

I have a feeling that with the logic we've been using so far it would just be really ridiculous casework... But maybe somebody has a cool intermediate counting technique that could get it done quickly?


AMC
USA(J)MO
USAMO
AIME
geometry
inequalities
number theory

Does anyone know of a nice book with good USAMO-level practice problems? About the level of #1 and #4 USAMO problems.

Thanks! :)

I think Mathematical Olympiad Challenges is a good place to start - it groups problems by subject to give a more thorough grounding in a variety of Olympiad topics than simply selecting random Olympiad problems could provide.

The USSR Olympiad Problem Book has a lot of good problems, although they may be a little difficult for just #1 and #4 USAMO level.

Why not Engel? It has lots of problems at lots of different levels.

Hm, can I get the full title? On amazon engel seems to be a fiction book. :D thanks!

[url=http://www.amazon.com/exec/obidos/tg/detail/-/0387982191/qid=1125807069/sr=8-1/ref=pd_bbs_1/103-6210280-3474222?v=glance&s=books&n=507846][i]Problem Solving Strategies[/i] by Arthur Engel[/url]

Ah, thanks! :) I actually already have that book but I have never really looked at it before... I'll go check it out now!

[quote="xxreddevilzxx"]The Arbelos help quite a bit too, i heard.[/quote]

I've got those too, about 4 or 5 volumes or booklets or whatever. It seems kind of dense, I read them when I was preparing for the AMC 12 but I figured they wouldn't be of much use in problem solving. It probably is pretty good for the USAMO though.

Engel is great. If you only get one book, get that. Actually going through the WHOLE thing rigorously would put you at borderline top 12, honestly. (disclaimer: borderline top 12 depending on the strength of the year)

[quote="mathclass"]*sigh* I am going through Engel right now... it's soooo long! I'm a freshman trying to qualify for MOP. I don't know how I'm going to finish this book. x___x[/quote]

It's not about finishing. It's always going to be a continuous work in progress, which involves doing problems, GOING BACK AND DOING STUFF AGAIN, analyzing your strengths and weaknesses, etc. It's not a novel.

Oh by the way for USAMO 1's/4's, some AIME problems really aren't any easier than many 1's and 4's (sometimes significantly more time consuming), and doing stuff like Canadian, Irish, etc. Olympiads from http://www.kalva.demon.co.uk is good too.

Darktreb, I've gone through quite a bit of Engel but I was wondering if there are any things which are left out that would be good to look over for USAMO?

Also, I own Art and Craft of Problem Solving, Math Olympiad Challenges, USSR Olympiad Problem Book, and quite a bit of MOP notes. In our opinion do you think Engel is still best to look over when preparing for the USAMO?

In my opinion, Engel is a bit light on geometry and inequalities, but excellent otherwise.

There's no magic book ... I know a lot of people who have never used an olympiad book in their lives. Personally I had Engel as a reference but didn't really use it either.

In retrospect, I agree with Engel being slightly light on Inequalities, and shortchanging Geometry a bit, but those are both more "trainable" topics than some others (like hard hard Number Theory and Combinatorics). There are other places to learn those things. Inequalities have been relatively easy at the IMO lately, look at this year's #3. Or, if you look through last year's IMO shortlist, A6 was a two step Holder problem, and A6 is usually supposed to be significantly hard....

[quote="DPopov"]Also, I own Art and Craft of Problem Solving, Math Olympiad Challenges, USSR Olympiad Problem Book, and quite a bit of MOP notes. [/quote]

I have all that except MOP notes. Where did u get them? and can I get them?

A friend lent them to me. I don't think you could get them unless you can find someone to let you borrow them.

I did my whole IMO training with stuff I found on the internet (because of a lack of money and resources), and, guess what, it worked :D You can find a LOT of good things on the web if you know where to look.

what do you mean with
[quote="Arne"] and, guess what, it worked :D[/quote]
what did you get?

A honourable mention the first year, a comfortable silver in my second year.

So, you see, by working hard you will eventually get there - keep in mind that I had no "good resources" (no books, I mean) and only 2 training weekends a year. So, I had to do everything on my own, but I believed I could do it, so...

Wow!!! Arne amazing job.....

can you tell me the websites....


linear algebra
matrix
vector
induction
algorithm
pigeonhole principle
combinatorics solved

We consider graphs with vertices colored black or white. "Switching" a vertex means: coloring it black if it was formerly white, and coloring it white if it was formerly black.

Consider a finite graph with all vertices colored white. Now, we can do the following operation: Switch a vertex and simultaneously switch all of its neighbours (i. e. all vertices connected to this vertex by an edge). Can we, just by performing this operation several times, obtain a graph with all vertices colored black?

[It is assumed that our graph has no loops (a [i]loop[/i] means an edge connecting one vertex with itself) and no multiple edges (a [i]multiple edge[/i] means a pair of vertices connected by more than one edge).]

The answer is "yes". The goal is to find a subset of the set of vertices ($S$) of $G$ (the given graph) s.t. each vertex in $G$ is connected to an odd number of vertices in $S$ (assume a vertex is connected to itself). As Omid said here:

[url]http://www.mathlinks.ro/viewtopic.php?t=5656[/url] (the last message), this is a very famous problem. I don't know the exact solution, but I did try some things. If $A$ is the adjacency matrix of $G$ (assume $a_{ii}=1,\ \forall i\in \overline{1,n}$) then we must show that there is a $0,1$ column-vector $v$ s.t. $Av=\left (\begin{array}{c}1\\1\\\vdots\\1\end{array}\right )$. In conclusion, we must show that the system is compatible. I think (although I haven't proven it) that the compatibility is equivalent with the fact that no set of lines of $A$ with an odd number of elements adds up to the $0$ line (i.e. the line with $n$ elements which has $0$ everywhere). It's easy to show that this is indeed the case for $A$, but I haven't shown that it's equivalent to the compatibility of the system mentioned above.

I forgot to mention a crucial thing: I've been working with matrices which have elements in $F_2$, meaning that all integers are reduced $\mod 2$. That's why instead of a column vector having only odd entries we have a column-vector having only $1$'s as entries.

That is exactly what I was trying to prove....Keep searching....

Pierre.

Pfff....I'd rather look more often in my archives.... :maybe:
The result is du to Sutner (1989).

References :
K.Sutner, 'Linear cellular automata and the garden of eden', Math. Intelligencer, vol.11, n2, (1989), p.49-53.
K.Sutner, ' The sigma-game and cellular automata, A.M.M., 1990, p.24-34.

Pierre.

In another hand, I would be interested about the induction proof that Omid mentioned in the other topic.

Pierre.

I remember seeing quite a short, elementary and ingenious solution of the above TST problem by one of my friends (it used induction over the number of vertices in the graph), but I can't remember it...

  Darij

the inducthion proof is easy.assume that the hypothesis is valid for n-1 and $A$ is n*n matrice .suppress the i th row and ith column,we get n-1*n-1 matrice with same property,then according to the hypothesis there exist some column such that their sum mod 2 equal n-1 dimention vector (1,...,1),now if we add the similar columns of A we get n dimention vector s.t all its component equals 1 just maybe ith component is'nt,if there exists i such that the number of 1 in its row is odd we are done otherwise for any$1\leq i\leq n$ according to above we get $v(i)=(1,1,...,0,1,1,...,1)$ assume that n is even then we have $v(1)+...+v(n)\equiv (1,...,1) means that if we add the column which is in relation to v(i) we get (1,1,...) but in this summand maybe some column is used more than 1 ,so if some column is used even times we can omit it and or we can consider column in parityso we can get (1,1,..1) and for n=2k+1 the sol is same as above ( alittle diffrent)

Thus it is a linear algebra induction proof. I was expecting a graph theoretic proof (even not the ingenuous and elementary one that Darij cannot remember).

Pierre.

Here is the ingenious elementary solution I promised. It was found by Peter Scholze (thanks to Peter for reminding me of his induction argument, BTW):

The answer is "yes". We will prove this by induction over the number n of the vertices of the graph. For n = 1, there is nothing to prove. Now turn to the step n --> n+1:

Assume that the theorem holds for an n = k. Consider a graph G with k+1 vertices, all colored white. Choose an arbitrary vertex A of this graph, and let G' = G \ {A} be the graph consisting of the remaining k vertices. Call O the operation "switch a vertex and simultaneously switch all of its neighbours". Now, since the theorem is assumed true for n = k, there exists an algorithm T which consists of multiple applications of the operation O and which, applied to the graph G', colors all of its vertices black. If we apply this algorithm T to the graph G' regarded as a subgraph of G, then we know that all vertices of G' become black, but we don't know what happens to the vertex A.

(In the following, "applying the algorithm T to a vertex A of G" will mean "applying the algorithm T to the graph G' = G \ {A}".)

If after our algorithm T applied to A, the vertex A is colored black, too, then our graph G is completely black, and we are done. If the vertex A remains white after the algorithm, then start again with a white graph G and try applying the algorithm T to another vertex B of G instead of A. If this doesn't work, too, (i. e. if the vertex B remains white) then start again, choose another vertex C and apply T again, etc.. If our algorithm T doesn't work for any of our vertices, then we can draw the following conclusion: For any vertex V of the graph G, there exists an algorithm T(V) which switches all vertices of G apart from V, while V retains its initial color.

Now, we will distinguish between two cases: if k+1 is even, and if k+1 is odd.

If k+1 is even, then start with the white graph G, apply the algorithm T(V) to all vertices V of G one after the other, and finally each vertex gets switched k times, and, since k is odd (as k+1 is even), this means that all vertices become black. Proof complete.

Now consider the case when k+1 is odd. Then, there exists a vertex A of G with even valency (the "valency" of a vertex is the number of edges starting at the vertex). [This is because the sum of the valencies of all vertices is even.] Let $ B_1$, $ B_2$, ..., $ B_{n}$ be all vertices of G which are connected with A. Then, $ n$ is even (since A has even valency). Let $ C_1$, $ C_2$, ..., $ C_m$ be all vertices of G which neither coincide with A nor are connected to A; in other words, let $ C_1$, $ C_2$, ..., $ C_m$ be all vertices of G except of A and $ B_1$, $ B_2$, ..., $ B_n$. Then, $ m$ is even (since
$ m\equal{}\left(\text{number of vertices of }G\text{ except of }A,B_1,B_2,...,B_n\right)$
$ \equal{}\left(\text{number of vertices of }G\right)\minus{}\left(n\plus{}1\right)\equal{}\left(k\plus{}1\right)\minus{}\left(n\plus{}1\right)$,
and $ k\plus{}1$ is odd while $ n$ is even). Apply the algorithm T to each of these vertices $ C_1$, $ C_2$, ..., $ C_m$. Then, these vertices become black (since a vertex $ C_i$ gets switched each time when T is applied to a vertex $ C_j$ with $ j \neq i$, and there is an odd number of such vertices $ C_j$). On the other hand, each of the vertices A, $ B_1$, $ B_2$, ..., $ B_n$ was switched m times and hence remains white (since $ m$ is even). Now finally apply the operation O to the vertex A (i. e. switch A and all neighbours of A), and all of the vertices A, $ B_1$, $ B_2$, ..., $ B_n$ (and only they) become black. Again, we have colored G completely black. Proof complete.

Ingenious, isn't it? I believe Peter was the only one to solve the problem on the exam.

  Darij

You are right Darij, it is a very nice proof.

Pierre.

Here's how to prove the lemma:

The system $Av=u$ where $v,u$ are column-vectors and $u$ has only $1$'s is compatible iff there's no subset of lines of $A$ with an odd number of elements which add up to the $0$ line (call this property (P)).

Assume the system is compatible. Then it's clear that there's no such subset because we would have an odd number of $1$'s adding up to $0$, which is false.

Conversely, assume there's no subset with the mentioned property. Take a minor of $A$ of order $r$ (the rank of $A$). We have to show that if we add a column with only $1$'s and a line of the matrix getting a $r+1$ minor then it must be $0$ (the system is compatible iff adding $u$ to $A$, the new matrix doesn't have a rank different from that of $A$). Let's assume that this minor isn't $0$. If we look at its $r+1$ lines without the $1$ column, there must be some subset whose sum is $0$ because otherwise we would be able to find a non-zero minor of order $r+1$ within $A$, and that's false. If this subset has an odd number of elements, then it's ok, because the $1$'s at the end also add up to $0$, so we're done. We must thus assume that this set has an odd number of elements and get a contradiction. A very important fact is that because the $r$ minor isn't $0$, it means that the subset of lines with a null sum is unique.

If we add a column from $A$ to the $(r+1)\times r$ matrix we're currently looking at we must get a zero determinant, so there must be some subset of lines with a $0$ sum. Bu this subset must be the same as before because otherwise in our $(r+1)\times r$ matrix we would find more than one subset of lines with $0$ sum, and I've mentioned that this is impossible. This means that the mentioned subset of lines has a $0$ sum even when we add all the columns in $A$, and we thus get a subset of lines of $A$ with a $0$ sum and an odd number of elements, which is what we wanted. We've assumed there's no such subset, so we have a contradiction, which means that the system is compatible.

I think this proves the lemma. Here's how we use it to the problem: all we must show is that the adjacency matrix has property (P). This is easy to do because if we assume that lines $L_{a_1},L_{a_2},\cdots,L_{a_{2k+1}}$ add up to $0$ then the same happens in the minor matrix formed by these lines and the columns with the same indexes, so we have a symmetric matrix of odd order which has only $1$'s on the main diagonal  s.t. its lines add up to $0$. This is false because it implies that the matrix has an even number of $1$'s, but it has an odd number of $1$'s (an even number below and above the main diagonal and an odd number on the main diagonal).

I think we're done. Can you spot any mistakes? (hope it's not too unclear..)

Here is a solution by my friend Janos Kramar, and it is by far the most ingenious one i have seen so far.  Use induction. assume its true for n-1.

Now, there are 2^n possible states of color, and each point can be either "switched" or not, giving 2^n possible sequences of operations. Therefore, if we cannot get them all black, there must be a set S of k points such that switching every point in S causes no change. Now, each point in S is connected to an even number of points in S, so each point in S has an odd number of neighbours in S. So |S| is even. Now, as each point is connected to an even number of points in S, the number of white vertices in S never changes parity mod 2. Now, fix a vertex V in S. If we can get all points except for V black, then V must also be black due to our parity argument. But this is doable by induction. Hence,  result.

Sorry for the useless post, but this is just beautiful! :D

A wonderful solution, indeed! I didn't ever think it could be solved using the pigeonhole principle.

  dg

This is a similar (but easier) problem, taken from SNS admission exam, 2001. The official solution used a technique that's very similar to Lipnowski's one.

In a graph, every vertex has an on-off button, and every vertex can be white or black. If we switch a button, then the color of its vertex and all its neighbours switch, too (but the neighbours' buttons don't switch). Suppose that in our graph, all vertices are colored white, all buttons are off, and that the only way to have all vertices colored white is keeping all buttons switched off. Then, prove that we can reach every possible color configuration.

I think this problem was known earlier. Indeed, there was a problem at All-Russian Olympiad-1999:

[b]Problem 9.4.[/b] The numbers $1,\ldots,1000000$ are colored in two colors --- black and white. During the move we may choose a number and recolor it and all the numbers, that don't coprime with it, into opposite color. At the beginning all the numbers were black. Is there a finite sequence of moves that recolors all the numbers into white color?

Author of the problem 9.4: S Berlov.

Clearly, it is a particular case of the problem (about arbitrary graph). But there was a story concerning this problem. Only one participant solved this problem at the olympiad (ARO-1999). It was Ilya Megirov. He generalized the problem 9.4 to the arbitrary graph and suggested a solution by induction (this solution has already been posted here by darij). And the committee didn't belive that his solution was correct. And the correctness of his solution was revealed only at the appeal. So, the original problem posted by darij has already been known in 1999.

P.S. The story about I. Megirov and his solution I read in the journal "Kvant", 1999, № 5, page 50. It can be found here (in pdf format, and certainly in Russian):
http://kvant.mccme.ru/pdf/1999/05/50.pdf .

The solution of I. Megirov was also published in the same journal, see page 61. It can be found here:
http://kvant.mccme.ru/pdf/1999/05/61.pdf .

Of course the problem is Iran TST 1996, so it was know since 1996. As I know the problem is from Peled (name of person), 1992.

[hide = Slightly Different]
Suppose $G$ has $n$ vertices; then this becomes equivalent to choosing some subset of the $n$ vertices to mark so that every vertex is adjacent to an odd number of marked vertices, where a vertex is adjacent to itself. Call a vertex [i]lit[/i] if it is adjacent to an odd number of marked vertices, and call it [i]unlit[/i] otherwise.

We induct on $n$; clearly this is trivial for $n=1.$ Suppose that in $G$ with $n$ vertices, $2k$ of the vertices have odd degree. Consider one of these odd vertices, $V.$ If $V$ is unmarked, we can choose some subset, which we call $L(V),$ of $G\backslash V$ to mark so that all the vertices of $G,$ except possibly $V,$ are lit. If $V$ is lit by this process, we are done, so suppose $V$ is unlit. Repeat this for every one of the $2k$ odd vertices, each time making the assumption that the $V$ we chose is unlit by marking $L(V).$

Now take the sum set $S$ of $L(V)$ over all odd vertices $V$ using binary xor (so a vertex $W$ is in $S$ iff it appeared an odd number of times among all $L(V)$). Every odd vertex is now adjacent to an $\text{odd}\cdot (2k-1)+\text{even}=\text{odd}$ number of vertices in $S,$ and every even vertex is adjacent to an $\text{odd}\cdot 2k=\text{even}$ number of vertices in $S.$ (If there are no odd vertices, $S$ is simply the empty set.) So if we choose $S$ to be our marked subset, then all the odd vertices are lit and all the even vertices are unlit. Then if we take the complement of $S$ among the vertices of $G,$ every odd remains adjacent to an odd number of marked vertices and so remains lit, but every even becomes adjacent to an odd number of marked vertices as well. Therefore all the vertices of $G$ are lit, as desired.
[/hide]

Induction. Assume n-1. There’s two cases. For n is even, take all n combinations of n-1 vertices and apply the inductive hypothesis to each of those combinations. Every vertex is flipped an odd number of times.
For n is odd, there’s a vertex with even degree 2k, call it v_i. Take all 2k combinations of n-1 vertices consisting of all vertices but one of v_i neighbours. Apply hypothesis to all 2k combinations, then flip v_i. The only black vertex is v_i. Apply hypothesis to subgraph that excludes v_i (if this doesnt work, then making this move to the original graph gives the result)

Pure linear algebra:

We prove the following claim.

[u]Claim:[/u] Let $A\in\mathbb{F}_2^{n\times n}$ be symmetric, and let $d=\mathrm{diag}A\in\mathbb{F}_2^n$ be the diagonal of $A$. Then, $\mathrm{diag} A\in\mathrm{im} A$.

The result follows then by setting $A$ to be the adjacency matrix of $G$ plus the identity matrix.

[u]Proof of Claim:[/u] We show that $d\in(\mathrm{null}A)^\perp=\mathrm{im}A$. Suppose $Ax=0$. We want to show $d\cdot x=0$.

Let $I=\{i:x_i=1\}$, and let $B$ be the restriction of $A$ on to $I$. We have that $B1=0$ where $1$ us the all $1$s vector. Adding up all the rows of the equation $B1=0$, we see that the off diagonal terms cancel because $B$ is symmetric and we are working mod $2$, so we see that $d'\cdot 1=0$ where $d'$ is the restriction of $d$ on to $I$, so we have $d\cdot x=0$, as desired. Thus, the claim, and the problem are proven. $\blacksquare$

Sorry for bumping but (speaking to yayups) is there motivation for using linear algebra in this scenario?

Well for these kind of problems, the process can be modeled with a matrix similar to the adjacency matrix, so its natural to try to do something with that. You quickly see that the problem is then equivalent to the lemma. Proving the lemma is just some linear algebra tricks.

We will use induction on the number of vertices. The base case is trivial; now, suppose it holds for $n-1$, and I will prove it for $n$. By the inductive hypothesis, for every vertex $V$, there is a sequence of moves that keeps $V$ the same and toggles all the other vertices (we are supposing that each sequence that toggles $G\backslash V$ does not toggle $V$, or else we'll be immediately done). This means that for any two vertices $W, V$, after applying each of their respective sequences, $W, V$ each are toggled once while all the other vertices are toggled twice, meaning $W, V$ are toggled and everything else stays the same.\\

Thus it is possible to toggle vertices two at a time, which means that if $n$ is even then we are automatically done. If $n$ is odd, then choose vertex $V$ with even degree (there will be such a vertex because the sum of the degrees is even), and let $S$ be the subgraph of $G$ that excludes $V$ and its neighbors. Note that $S$ has an even number of vertices, so by toggling vertices two at a time, we can make everything in $S$ red while keeping $V$ and its neighbors black. Finally, just toggle $V$ and its neighbors, and we've made everything red.

We will induct on the number of vertices, with the base case $n = 1$ being trivial. Suppose that the result holds for $n - 1$ vertices, and consider adding another black vertex $v$ to the graph, and $V$ the set of $v$ and its neighbors. For brevity, let $G$ denote the original graph and $G'$ denote the union of $G$ and $v$. By the induction hypothesis, there exists a sequence of moves toggling all of the colors of $G$, meaning that it is possible to have a graph of $n - 1$ red vertices and $1$ black vertex. This likewise holds for all graphs on $i$ vertices, where $1 \le i \le n - 1$, by applying the induction hypothesis for $i - 1$. Hence, it is possible for $G$ to have $1$ red vertex and $n - 2$ black vertices. Let this black vertex neighbor $v$. Repeatedly applying this process to all subgraphs with $1$ vertex being a neighbor of $v$, it is possible to turn $G \backslash V$ into all red vertices and $V$ into a set of all black vertices. To finish, toggle $v$, which turns all of its neighbors black, completing the induction. $\blacksquare$

(I used red/black instead of white/black)

Let $n$ be the number of vertices. We will prove this via induction on $n$. Our base case is $n = 1$, where we just flip the lone vertex. We move on to the inductive step.

Assume we can make a sequence of moves for $n-1$; we prove we can do the same for $n$. For any vertex $A$, we can change the colour of all vertices except for $A$ via our inductive step, if $A$'s colour is also changed, then we're done, otherwise, $A$ must be black. Call this a supermove on $A$. If any supermove on any vertex leaves that vertex as red, we're finished with our inductive step, so assume all supermoves leaves the vertex as black. If $n$ was even, we do a supermove on each vertex. Then, each vertex will change it's colour $n-1$ times, which means each vertex will become red. Otherwise, if $n$ was odd, then let $S$ be the set of all vertices with even degree. Let $k$ be the size of $S$, we must have $k$ as odd (since the sum of all degrees is even). Then, let's do supermoves on each vertex in $S$. Each vertex in $S$ will change it's colour $k-1$ times, resulting in black, while each vertex outside of $S$ will change it's colour $k$ times, resulting in red. Finally, if we take the complement of all moves, such that for each vertex, if it was moved on, it will not be moved on, and vice versa, observe that all vertices with even degree will change their colour, while all vertices with odd degree wil not change their colour. Thus, we can take the complement of the supermoves of vertices in $S$, which will result in the vertices outside of $S$ to retain its redness, while the vertices in $S$ will become red. Thus, if $n$ is even or odd, we can turn all it's vertices red, so our inductive step is complete. We conclude that it is possible for all graphs.

[color=#00f][b]Remark:[/b][/color] Not my favorite problem :(

We will use strong induction. The base cases of $n = 1$ and $2$ are direct. Next we suppose that for some $k \geq 3$, it is possible to make all vertices red for graphs on $\leq k$ vertices. We wish to show that it is also always possible for graphs on $k+1$ vertices.

First let's consider a graph $G$ on $k+1$ vertices. By the inductive hypothesis, for all vertices $v \in G$, it is possible to toggle $G \symbol{92} v$ to all red. If in this toggling process, $v$ is toggled as well, then we are done, so suppose otherwise. We pick two vertices $u, w \in G$ to apply this toggling to. Note that all vertices in $G \symbol{92} \{u, w\}$ are toggled twice and $u, w$ are each toggled once, so this process actually turns both $u, v$ to red and keeps all other vertices black.

Thus, if we are not able to immediately finish, then we can toggle two vertices at a time, which completes the case when $k+1$ is even. Otherwise, we choose a vertex $v$ with even degree, which is known to exist since sum of degrees is even, and consider the set $S \subseteq G$ excluding it and its neighbors. $|S|$ must be even so we can apply the double toggling trick to turn all of $S$ red, and then we toggle $v$ to turn $v$ and its neighbors red, and we are done. $\blacksquare$

Quite nice!

WLOG, add self-loops to each vertex. To each vertex $v$, associate a binary string $N_v$, for which each coordinate is $0$ except for those vertices which are neighbors of $v$. Represent the state of the graph with a binary string, where the $i$'th coordinate is $0$ if the $i$'th color has black, and $1$ otherwise. A move then corresponds to replacing $T$ with the XOR of $T$ and one of the $N_v$. In particular, this implies that moves are commutative. We say a binary string $L$ of length $|G|$ is \textit{good} if there is some sequence of moves which results in $G$ having state $L$. We wish to show that the string $L$ of length $|G|$ with all entries $1$ is good.

Note that if two strings $L_1$ and $L_2$ are good, so is their XOR (perform the set of operations which results in $L_1$, then perform the set of operations which results in $L_2$).

We now proceed by induction on $n = |G|$, with base case $n = 1$ trivial (toggle the only vertex).

Consider a graph with $n > 1$. Consider the induced subgraph formed by removing vertex $1$. By induction, there is a sequence of moves which will cause each of the remaining vertices to be colored red. If this sequence of moves also colors vertex $1$ red in $G$, we are done. Otherwise, we find that $011\cdots 1$ is good, where there are $n - 1$ $1$'s. Repeating the argument for all vertices of $G$, we find that all binary strings with bitcount $n - 1$ are good.

In the case that $n$ is even, we are already done. Indeed, the XOR of all of these strings is also good, implying that the string $11\cdots 1$ is good, so we are done.

Now, suppose $n$ is odd. Note that an odd number of vertices have odd degree (since each vertex has a self-loop). WLOG, suppose the vertices with odd degree are $1, \ldots, k$. Let $X$ be the result of operating on each vertex. As $X$ is the XOR of all $T_v$,
it follows that the $i$'th coordinate of $X$ is $1$ iff the degree of the $i$'th vertex in $G$ is odd. Now, for each $1 \leq i \leq k$, let $S_i$ denote the string for which the only coordinate which is $1$ is the $i$'th coordinate. Then, for each $i$, let $Y_i$ be the complement of the XOR of $S_i$ and $X$. As $Y_i$ is equal to the XOR of the complement of $S_i$ and $X$, both of which are good, $Y_i$ is good as well. In $Y_i$, the $j$'th coordinate is $1$ iff the $j$'th vertex is even or $j = i$. Now, let $Y$ be the XOR of all of the $Y_i$'s; note that $Y$ is good. For each $1 \leq i \leq k$, the $i$'th coordinate is $1$ in exactly one of the $Y_j$'s (namely $j = i$). The coordinates corresponding to even vertices are $1$ in every $Y_i$. Thus, as there are an odd number of $Y_i$, it follows that $Y = 11\cdots 1$ is good. This completes the proof. $\Box$

Label the vertices with elements of $\mathbb{F}_2$, let black be 0 and red be 1. The [i]toggling[/i] operation adds 1 to a vertex and all its neighbors. We induct on $n$, the number of vertices of $G$.

[color=#00f][b]Claim:[/color][/b]  For any vertex $v$, there is a sequence of togglings that adds 1 to all but $v$, and keeps $v$ constant.

[color=#00f][i]Proof:[/i][/color]  By the inductive hypothesis, there is a sequence of togglings involving vertices not $v$ that adds 1 to all vertices not $v$, but not necessarily to $v$. If $v$ also increases by 1, then all vertices are red, so done. Else, $v$ stays constant, while all other vertices increase by 1.  $\blacksquare$

[color=#00f][b]Claim:[/color][/b]  For any two vertices $u,v$, we can add 1 to just $u$ and $v$.

[color=#00f][i]Proof:[/i][/color]  Add 1 to all but $u$, then add 1 to all but $v$.  $\blacksquare$

If all degrees are odd, then for each vertex $w$, toggling all but $w$ makes $w$ increase by $\deg w\equiv 1 \pmod2$, finishing. So now consider a vertex $v$ of even degree. Add 1 to all but $v$. Now, toggle $v$, so that $v$ is 1 while every vertex in the neighbor set $S$ of $v$ is 0. Since $|S|$ is even, arbitrarily pair up the vertices of $S$ and add 1 to each. Now all vertices are 1, finishing.

[hide=Remarks]For the first claim, it's actually pretty hard to see that you can not control what happens exactly to $v$, and instead realize simply that if it also adds by 1, then you're done. I was trying to use other global arguments to control what happens to $v$ for too long. After realizing that this second operation exists, there is a lot more room to get more power in terms of what you can do.[/hide]

Short and sweet linear algebra.

Work in $(\mathbb{F}_2)^n.$ Let $A$ be a $n \times n$ matrix representing this graph, where the $i$-th column contains $1$'s for all of $i$'s neighbors and $i,$ and $0$'s elsewhere. $A$ is symmetric and has $1$'s on the diagonal. Let $d = (1,\ldots,1)^T$ be the all ones vector. It is sufficient to show that there exists some $x \in \mathbb{F}_2^n$ such that $A x = d,$ ie. $d \in range(A) = ker(A^T)^{\perp} = ker(A)^{\perp}$ since $A$ is symmetric, ie. $ker(A) \subseteq \langle d \rangle^{\perp}$
It suffices to show that $A y = 0$ implies $d \cdot y = 0.$
But $Ay = 0$ means $y^T A y = \sum_{i,j} a_{i,j} y_i y_j = \sum_{i} a_{i,i} y_i^2 + 2 \sum_{i < j} a_{i,j} y_i y_j = \sum_{i} y_i = d \cdot y = 0,$ since we are in $\mathbb{F}_2.$


algebra
polynomial
inequalities
algebra proposed

Let $ P$ be a complex monic polynomial with $ |P(0)|\equal{}1$. prove there exists another complex monic polynomial $ Q$ of the same degree with $ |Q(0)|\equal{}1$ and all roots in the unit circle (if $ z$ is a root then $ |z|\equal{}1$)  such that for all $ x$ with $ |x|\equal{}1$ the following inequality holds
\[ |P(x)|\geq|Q(x)|.\]

BTW: Not related to this problem, but does someone know theorems involving inequalities and zeros of polynomials in complex disks?  or useful facts?

The idea is to extend or shorten the roots till they touch the unit circle and find a relation between the new and the old distance to some point of the unit circle.


AMC USA(J)MO USAMO AIME ARML trigonometry probability

I think this topic would be appropriate for all math competitions. But just in case there is a number I should randomly guess all the blanks with when I'm almost out of time, which one shall it be?

One USAMO qualifier suggested 0. My other classmates in the math team put in 5 for some reason.

What are your thhoughts?

Good guesses are 0, 1, and 2004. On the AIME, good guesses would be factors of 2004.

hmm.. what's wrong with  guessing the one which happens to be the  corrrect answer too.?

I mean, if you have time enough to write an answer,  why not write the correct answer? Answers do depend on well defined logic and  all you have to do is to just follow that logic  and  then you don't even have to guess. .. after all you, for crying out loud,  are not picking a number for lotto you know...

Just my thoughts... :cool:

Gyan, don't get smart.  Inevitably, there will be a time in your life when you have to guess; we're discussing what number would be best in such a situation.

I favor 501 this year.

[quote]Inevitably, there will be a time in your life when you have to guess;[/quote]

May be  some time in my life I have to guess in some situations,  but  I NEVER have to do that in a  AIME type, (or any otehr math test for that matter)  contest...and you know what, that principle works. I have gotten 100% in  every math tests in my school years. and believe me it was not because  of my knwoledge of "best number to guess with"

No I am not being smart,   I am serious, the point is trying to find a stretagy of "guessing"  the best answer, IMO, is pointless.  AIME type tests are not that hard  that  one would think that investing in "better guessing stretegy"  has better chance of return than just stuyding some serious stuff. Besides studing may help you in your life even after AIME type tests.

Okay, not everyone gets 100% in AIME but do you really think that trying to find the "best number to guess with" has any merit as far as your objectives are concerned?

Din't want to flame any one .. this is just my personal opinion..

Bottom line:   expected value of even the "best guess" is not going to make any significant difference in your.
Just my thoughts.

The only reasonable way to answer this question, of course, is to go collect thousands of math competitions and check out what answers are most frequent.  (On a random note, about four years ago a senior captain of Stuyvesant math team gave a test he had written to determine the junior teams in which every single answer was either 1 or 0.)  If this is for the AIME, though, the strategy is going to suck -- there is far too high a degree of randomness in the construction of answers to make it a significantly useful strategy.

You can bash guessing all you want, but if you can't solve a problem or you run out of time on the AIME or some other contest, and there isn't a penalty for wrong answers, it's not very smart to leave it blank. Therefore you might as well guess something that has what you believe to be a decent chance of being correct.

happy numbers like 144 or 288, with lots of factors of 2 and maybe 3. If you can narrow it down to a range of 10 numbers or so, pick the one in that range with the most factors of 2 or 3

There have been 27 AIME tests to date, which means 405 questions.

And the winner for most popular answer is (drum roll, please...) 025, which has appeared 6 times.  The runnerup is 840, which has appeared 5 times.  There is a five-way tie for third place: The answers 005, 012, 020, 061, and 400 have each appeared 4 times.

At that rate, if you choose 025, you have about a 1.5% chance of being right...

The answers 000 and 001 have appeared once each.

Enquiring minds want to know.

[quote="JBL"]I'm not bashing guessing -- I'm bashing the process of choosing a reasonable number to guess :).  It very much depends on the circumstances -- remember that ARML question with the heptagon?  Anyone who guessed 1001 was absurd, because it was obvious the asnwer was going to be of order 2.  They all should have guessed 1002001, but I don't see that on anyones list of numbers to guess :)[/quote]

Haha I guessed 1001 on that question, and it didn't take me long to realize that it was a really stupid guess. (I'm pretty sure I was certain it was wrong before they called out the answer.) Did you guess 1002001? Or did you solve it properly?

I did it trig-wise and got the angles in terms of 7ths.  Then I said, "Hey, these angles add to 90 degrees and aren't terribly far away from 30 and 60," so I plugged in 30 and 60 and it worked out to 1002001, and when I saw that, I knew I was set :)

[quote="Ravi B"]And the winner for most popular answer is (drum roll, please...) 025, which has appeared 6 times. The runnerup is 840, which has appeared 5 times. There is a five-way tie for third place: The answers 005, 012, 020, 061, and 400 have each appeared 4 times. [/quote]

Thanks for doing the scratch work. There is very much of a spy-counterspy aspect to making tests hard to guess correct answers for. I remember once, back when I was just finishing up law school, I took a bar exam review course that promised that topic X (a topic that was fair game, according to that state's bar examiners) would never be on the bar exam. Naturally, the day I sat for the bar exam, the very first question was on topic X, which I had had the foresight to learn even though I was promised it wouldn't be on the test.

Similarly, I am SURE that every year there are SAT I sentence completion or critical reading questions that involve the words kids memorize on SAT vocabulary lists being used with unusual meanings. Just memorizing vocabulary lists is not enough.

I note for the record that at least one staff member of the AMC program, namely the program's director, reads this site from time to time, so I think the AMC staff will figure out some way to make guessing unlikely to be successful on the next AIME.

I mainly favor 3, 5, 12, 20 and 144. But it depends on my mood and the problem. It also helps if you have to solve the measure for an angle and there's a diagram. Even though the diagram might not be to scale, if it's kind of close, it indicates a lot towards guessing.

Why Zero? Why not 1? or -1?

Also, be sure to guess numbers relatively prime to 2004 but less than 25...

[quote="Magnara"]On one math test, I only knew about half the answers, so I guessed on the other ones.  But I had some fun with it.  For example, one of my guesses was Abraham Lincoln (we could write in answers).  For another, I wrote a long thing out involving i, e, pi, square roots, and fractions.  Somehow....they missed it and marked it right.  Either that, or someone had a really really good sense of humor.[/quote]

you mean a baaaaaaaaad sense of humor...

Also, be sure to guess numbers relatively prime to 2004 but less than 25...

Why?

Ooohhh !!!  so many responses in this thread. This certainly looks like fun.
:D
I wonder if the authors of AoPs have seen this thread.  If some one writes a book about Art of guessing the best number -  Problem Solving the easy way, little doubt that it will become  a best-seller like  any other  get_rich_quick/cheat_the_system/get_something_for_nothing_type  book.

I can see it clearly now. A typical question in the contest:
[quote]
Find the number of zeros in the end of  1000! [/quote]

Let me see,   as clear as a drum roll (okay I cant see a drum roll but I can  imagine the amplitude of the  sound waves it will produce) rolling after 405 AIME problems, and I answer with  unheard of 1.5% confidence level 025. Now I dont see why this has more probability to get you a point  than  say, obvious and easily  calculable answer,  of  249.  . But hey! What do I know? I am just being two smart and am bashing  this wonderful art.  :D

One can always rush and buy Dr. Matrixs book on numerology. :D   ( may be better than  following old statistics..:D)

[size=125][b]But arent you selling yourselves short and aiming too low. I mean what an extra point in AIME will get you. Now  why not use the same logic i to pick the  numbers for super-lotto.[/b].[/size] :)

. Okay ducking for cover now!

P.S. Giving you best try (and that includes guessing) and entering  a number rather than leaving a  blank for an answer is one thing, but   investing energy in trying to find a best  number to guess  wont, IMVHO,   make  you a better problem solver, it may not even increase your score or even get a spot on your local TV news  How I added   the number of toes  on my cat  to the age  of my crazy uncle to guess the answer .
  :D  :D

[quote="Magnara"]For another, I wrote a long thing out involving i, e, pi, square roots, and fractions.  Somehow....they missed it and marked it right.  Either that, or someone had a really really good sense of humor.[/quote]

Maybe that was the correct answer  :D.

Really, your probablility of guessing an answer right on AIME is 1/1000, so I don't see the point of even trying to guess.  If you want to guess, just guess randomly.

On AMC, if you are pretty sure that you did really well, guess B for #25

Humans cannot generate random numbers. We always need some reason to put the answers we put down. So why not put down an answer you think might have a better chance?

[quote="tokenadult"]Guessing on AMC 10 or AMC 12 throws away points. Guessing on the AIME, after making an honest effort, is hoping that you'll win the lottery.[/quote]

I agree, that's why I said if you think you did REALLY well and losing 2.5 point is not really going to hurt you.

Being a Douglas Adams fan, when I have absolutely no idea whatsoever, I like to guess 42 or its variants (4,2) and 4 :sqrt: 2.

On a different note, at ARML practice last year, we did a team round problem involving a polynomial for which f(x)=1/x for all integral x between 1 and 1997.  We needed to find the value at x=1998.  I guessed zero (figuring the answer would be nice and simple); a coach pointed out afterwards that if it has nonzero rational values at 1997 points in a row, the next one is probably a nonzero rational as well.

[quote]a coach pointed out afterwards that if it has nonzero rational values at 1997 points in a row, the next one is probably a nonzero rational as well.[/quote]

Why stop at that? (you need not even browse in that direction), look at the  polynomial:
(x*f(x)) . Isn't its value 1 for 1 to 1997, and  isn't it is easy to guess the actual value?  (of say (x-1)*(x-2)*...(x-1997)+1)

Point is, more often than one would think, the answer is nice and  simple if you happen to see it, it may be even simpler than stopping at "art of guessing type reasoning"   in many cases,

Yes, that's how you solve it. But what if you don't see how to solve it?

[quote]But what if you don't see how to solve it?[/quote]Most likely it is not the end of the world (and if it is then who cares!), and you may miss a point  in the test.
But  then that is the point of the test, to see who can see how to solve it.  All is not wasted though becuase  one can use such  learnings  in the  future.


function
calculus
derivative
complex analysis
topology
real analysis
real analysis theorems

Is a function that is analytic always continuous and differentiable?

Is it possible to have a differentiable function that is not analytic?

The answer to the first question: yes, $ f$ analytic implies $ f\in C^{\infty}.$ (Asking for "continuous and differentiable" isn't going far enough.)

The argument goes like this: analytic means locally given by a power series with a positive radius of convergence. Any power series is differentiable in the interior of its interval of convergence, with derivative given by the term-by-term derivative of the series. (Proving that is a nice exercise). But then the derived series is still a power series with the same radius of convergence, so we can repeat the process arbitrarily many times.

The converse is false. A $ C^{\infty}$ function need not be analytic. There's a classic example which is given in several forms, slightly differing as to the details. I usually do it this way:
\[ f(x)\equal{}\begin{cases}e^{\minus{}1/x},&x>0\\0,&x\le 0\end{cases}\]
That function is $ C^{\infty}$ everywhere but fails to be analytic at $ x\equal{}0.$

In fact a function can be $ C^{\infty}$ everywhere and analytic nowhere. I know I've posted my example of that somewhere here.

Now, if you were thinking of the complex realm...

A function from $ \mathbb{C}$ to $ \mathbb{C}$ which is differentiable (holomorphic) in the complex sense on some open set $ U$ is in fact analytic on that set, and equal to its power series on each disk contained in $ U$. That's a theorem, and it defines how complex analysis is so different from real analysis. Just one derivative is good enough for infinite niceness.


geometry
geometric transformation
reflection
combinatorics unsolved
combinatorics

If you have m "a"s and n "b"s, where m>n>0, how many different strings of length m+n can you generate such that every non-empty prefix(substring starting at the beginning) of the string has more "a"s then "b"s? For example, the smallest case is 2 "a"s, and 1 "b", where the number of possible strings is only 1 - "aab". Is there a formula for the general case? I don't even know how to approach the problem.

the problem is equivalent to finding the number of paths (consisting of "right" and "up" moves) from (1, 0) to (m, n) that don't go above the line $ y = x - 1 $...  to compute this number, we find the number of paths that *do* go above the line $ y = x - 1 $, and then subtract from the total number of paths from (1, 0) to (m, n) (which is $ {m+n-1} \choose {n} $).

each path that *does* go above $ y = x - 1 $ must meet the line $ y = x $.  for such a path, consider the first time it meets the line $ y = x $ and *reflect* the part of the path up to that point in the line $ y = x $, leaving the rest of the path intact.  this results in a path from (0, 1) to (m, n).  conversely, for every path from (0, 1) to (m, n) there's a unique path from (1, 0) to (m, n) that goes above the line $ y = x - 1 $ (obtained by reversing the above procedure).  this determines a bijection between the set of (all) paths from (0, 1) to (m, n) and the set of paths from (1, 0) to (m, n) that go above $ y = x - 1 $.  thus, the number of such paths is $ {m+n - 1} \choose {n - 1} $.

so your answer is $ {m+n-1 \choose n} - {m+n -1 \choose n - 1}$

Thank you. Your solution works, and I understand why.   :)


email
AMC
AIME
induction
analytic geometry
trigonometry
geometry
\/closed

We have now listed all classes that we plan to have available for enrollment that start in 2004.  PreTests and PostTests will soon be available for classes that do not already have them.

If you have any questions about the courses you can ask here or email me at crawford@artofproblemsolving.com.

[quote="Rep123max"]Once the pre test comes up I'll check it, but what are the basic standars for Olympiad Problem Solving. Is it for people who are sure they will make USAMO, or also for people who think they can (but it's not a definite)?[/quote]

Students need to be able to score a 5 on the AIME or get a significant majority of the problems on the Pre Test.  The class will be challenging and will be good preparation for the Olympiads.

Students will be expected to have very good algebraic problem solving skills, know a fair amount of number theory, be able to handle most of the Intermediate Counting/Probability material, and have a basic understanding of contradiction and induction as problem solving tools.

is problem solving with polar coordinates in the trig and complex numbers class?

Polar coordinates are discussed in the complex numbers class.  One of the goals of the class is to teach students to understand the deep inter-relations between polar coordinates, complex numbers, exponential notation, and trig functions.  Many areas which are often understood as different in a standard mathematics curriculum are actually the same the thing.


abstract algebra
superior algebra
superior algebra unsolved

$ R$ is commutative ring with unity  $ T\equal{}\{y \in R: \exists t \in R$ so that $ yt \in S \}$  $ S$ is multiplicative closed .suppose M is a finite generated R-module so that $ \forall x \in M$ we have  $ T \cap (0 : _R  x)  \not\equal{} \phi$ show that exist $ s \in S$ so that $ \forall y \in M$   $ sy\equal{}0$

I try to use this: $ T\equal{}R\minus{} \cup$ $ p$  s.t.  p is prime and  $ p\cap S \equal{} \phi$

let $ M\equal{}x_1R\plus{}\cdots\plus{}x_nR$.
to  $ x_1$,  we have $ y\in T, t\in R$, $ s_1\equal{}yt\in S$ ,$ s_1x_1\equal{}0$.
let $ s\equal{}s_1s_2\cdots s_n\in S$

the struction of $ T$ you gave is also right..since $ T$ is also mutiplicative, and statured( if $ y_1y_2\in T\Rightarrow y_1\in T$ and $ y_2\in T$),......apply ex3.7 of atiyah'book .


How many sets of four consecutive positive integers are there such that the product of the four integers is less than $ 100,\!000$?

I asked this because I didn't really understand the solution.

let's experiment with some sets of four consecutive positive integers

$ 14\times15\times16\times17 \equal{} 57120$
$ 15\times16\times17\times18 \equal{} 73440$

each of those fit the restrictions set

however, we find that $ 17\times18\times19\times20 \equal{} 116280$, which is greater than $ 100000$

thus, the sets are $ (1,2,3,4), (2,3,4,5).....(16,17,18,19)$

we can immediately see that there are $ 16$ sets that work

So we want to approximate 100,000^1/4 and center our set around that.
100,000^1/4 = 10*10^1/4

10^1/4 is approx 3.16^1/2 which is approx 1.775

[hide]

So we end up with a center of about 17.7, so we consider the set (16,17,18,19). 16*17*18*19=93024<100,000, so we try (17,18,19,20)

17*18*19*20=116280>100,000, so the sets we want are bounded by (1,2,3,4) and (16,17,18,19), inclusive. This yields 16 sets.

[/hide]

[hide=solution]What I did was first note that product of the largest must be less than 316. So 17*18. 15*16*17*18, and there are 15 from 1*2*3*4. But since 16*17*18*19 also works, it's 17.[/hide]

Is there a better solution though? Because I got it correct on second try, since you had to notice that 16*17*18*19 also works.

[quote=Sippi]I don't understand and I don't think that yall are conting
1*1*1*999999
1*1*1*999998
1*1*1*999997
1*1*1*999996
and so on that is so much more!! than 16 !!! Help me!!![/quote]

these are not consecutive integers

It seems a little ridiculous to have to manually compute $16*17*18*19$.

Yes, there is nothing wrong with using a calculator, as far I know

~ :heli:


[quote="suweijie"]Let a,b,c be positive real numbers such that
a+b+c=3 Prove that
[img]http://www.artofproblemsolving.com/Forum/latexrender/pictures/b2f603d58bdfdfafa1feb3b4506ad7b7.gif[/img] ;)[/quote]
weighted jensen on $f(x)=\frac{1}{x^2+14x+1}$ and use $(a+b+c)^2 \ge 3(ab+bc+ca)$.

First I don't understand what you meant,but I have a much easier proof. :D

Just use the  fact:[img]http://www.artofproblemsolving.com/Forum/latexrender/pictures/d36e36d8f23b960b10352aa37430801e.gif[/img] :D


trigonometry
calculus
calculus computations

can any one please evaluate the inverse of this transform

(s+1)/(s^2+4s+6)

You just have to complete the square in that denominator.

$\frac{s+1}{s^{2}+4x+6}= \frac{(s+2)-1}{(s+2)^{2}+2}$

$=\frac{s+2}{(s+2)^{2}+2}-\frac1{\sqrt{2}}\cdot\frac{\sqrt{2}}{(s+2)^{2}+2}$

We can now read off the inverse Laplace transform as

$e^{-2t}\left(\cos(\sqrt{2}t)-\frac1{\sqrt{2}}\sin(\sqrt{2}t)\right)$

I debated whether to move your three topics to the "Calculus Computations and Tutorials" section but decided to do so for two reasons.

1. The questions seem to fit the spirit of "computations and tutorials."

2. I tend to say that differential equations (ODE's - not PDE's) are part of calculus, and then I suppose Laplace transforms are part of differential equations.

But it's a borderline case.


Prove, that for any natural $n\geq 2$ the equation:
$x_1+x_2+\cdots+x_n=x_1x_2\cdots x_n$ has solution is positive integers.

In fact, there are infinite solutions for each $n$.  For any given set of numbers $x_1, x_2, ...$ such that their product is greater than their sum, a solution can be found simply by adding $1$s to the sequence until the sum is equal to the product.  :)

That doesn't work, because you add additional terms and thus increase the size of $n$.  In fact, there are only finitely many solutions for each $n$.

Oops.  Righty-o.  Of course, as the $x_k \to \infty$ the product becomes much larger than the sum... silly me  :blush:

It remains that there are more nontrivial solutions than the ones given, though.  :P

[quote="Farenhajt"]For $n\geqslant 3$:

$\underbrace{1+1+...+1}_{n-2}+2+n=\underbrace{1\cdot 1\cdot...\cdot 1}_{n-2}\cdot 2\cdot n$

For $n=2$:

$2+2=2\cdot 2$[/quote]

Just nice!

[quote="dondigo"]How to find other non-trivial solutions :?:[/quote]

Take any collection of integers - say, $2, 6, 10, 17$.  Call $P = 2040$ their product and $S = 35$ their sum.  Now clearly $P > S$.  So we add $P-S = 2005$ $1$s to the collection; then the sum increases to $P$ but the product does not change.  :)

[quote="t0rajir0u"]Take any collection of integers - say, $2, 6, 10, 17$.  Call $P = 2040$ their product and $S = 35$ their sum.  Now clearly $P > S$.  So we add $P-S = 2005$ $1$s to the collection; then the sum increases to $P$ but the product does not change.  :)[/quote]

I might be missing something, but as far as I can see, after adding $P-S$ the sum will be $P$ and the product $P(P-S)$. How these two can be equal for $P-S\neq 1$?

Edit: $P-S$ [u]ones[/u]... Almost missed it :)

he means $P-S$ unique terms each of value one.

See also : http://www.mathlinks.ro/Forum/viewtopic.php?t=63671. :)


Hello,

This pretends to create a nice discussion, but it is not really a "Serius Discussion", hence, I believe it belongs more here (Games and Fun Factory) than to Round Table.

I had a collection of currency of different countries since at least 1987, and it has grown a lot (unfortunatelly the 95% of it is three thousand miles away) and I have noticed that regularly most of the currency denominations are of the form $2^n5^m$, where most of the time $|m-n|\leq2$, for example, the  currency denomiations in Costa Rica are 1, 5, 10, 25, 50, 100, 500, 1 000, 2 000, 5 000 and 10 000. In the US, besides the cents coins, those are 1, 2, 5, 10, 20, 50, 100, 500, 1 000, 5 000 and 10 000, but the last four are pretty difficoult to see and are not longer in print (I know that some people say that it is not true, but go to the page of the US Department of Theasury, and you will see that it is true, they exist)

Nevertheless, I have seen some denominations out of common. I remember some 13 pesos and other of 12 cents, from the 1920s or so, I do not remember the countries, but they exist. Does anyone knows about any other 'Odd' denominations, specially if they are currently in circulation?

Best regards,

I have some really old english coins that are 6 pence and 1/2 penny, but I am pretty sure that they are no longer circulated.

Sixpence made sense pre-1971; it was half a schilling. You see, back then it was:

1 pound = 20 schillings = 240 pence = 960 farthings.

[quote="miraculouspostmaster"]There's a cool picture in my economics book of these people on an island who use massive, circular stones as money.[/quote]

It would probably make quite difficoult to have a couple of bucks on your wallet  :D  :P

[quote="cardwacko9999"]way back in US history, there was a 1/2 cent coin, 3 cent coin, 3 dollar coin (gold) There were plans for a 4 dollar coin that was abandoned. These are all no longer in circulation, but...[/quote]

I don't know if you read the  [url=http://www.auburn.edu/~vestmon/Gift_of_the_Magi.html]Gift of the Magi[/url]  (O.Henry)  which starts:
[quote] One dollar and[b] eighty-seven[/b] cents. That was all. And [b]sixty cents[/b] of it was in pennies. Pennies saved one and two at a time by bulldozing the grocer and the vegetable man and the butcher until one's cheeks burned with the silent imputation of parsimony that such close dealing implied. Three times Della counted it. One dollar and eighty- seven cents. And the next day would be Christmas.[/quote]

Mathcounts students always wondered .. How to have  "One dollar and twenty-seven cents" without having pennies...????
[b]Mystry solved!![/b]
From googling: ..The US produced a 2-cent coin for general circulation up until 1872 and a 3-cent coin until 1889. (Either of these would allow the math to work) there were also half-cent pieces produced from 1794 until 1857,..  O. Henry lived from 1862 to 1910..

[quote="Danbert"][quote="cardwacko9999"]way back in US history, there was a 1/2 cent coin[/quote]

Really?  I was under the impression that the 'mill' was never produced.

It was proposed in the Great Depression.[/quote]

I believed it was called a pence

isnt that in europe?

along with the euros, etc

For some clarification... :)

US started minting its own coins in 1792. Of course, they made very few that year (mostly test coins). Regular circulation coins, more like 1794, 1796, dunno. At that time, there were minted half cent, one cent, "half dime", dime, quarter, half dollar, dollar, and in gold 2.50, 5, 10. People sometimes cut a quarter into 2 and used each piece as 12.5 cents. (It is the reason for the name "two bits" for a quarter. Actually, that comes from an earlier practice of cutting mexican 8 real coins into eighths ("pieces of eight").)

Later in the 1800s, there are some changes. Around 1857, they stop the 1/2 cent, and they change the one cent to a much smaller coin. Not long after, they start making the 3 cent coins (in copper-nickel and in silver) and change the silver half dime for the nickel. Around the same time (1850s), they also made some interesting endeavors with gold coins. They have a gold 1 dollar for a short time. The 3 dollar lasts for like 20 yrs at least (though not many are minted). They actually made a 4 dollar coin, "Stella", but there are VERY few (test coins, probably). Also, the 20 dollar coin started around then.

In the 1870s, for a short time there was a 20 cent coin.

Unfortunately I don't know the reasons for most of these "odd" denominations.

The UK used their English system for a long time. They had many weird denominations. There are 12 pence to a shilling, 20 shillings to a pound. Coins were usually from 1 farthing (1/4 penny) to a pound, but there were 1/4, 1/3, 1/2 farthing in the mid 1800s (circulated in the colonies, probably because money had more buying power there). They had farthing, half penny, penny, three pence, six pence, shilling, 2 shillings (florin), 2.5 shillings (half crown), 5 shillings (crown), pound, and guinea (21 shillings). For some reason, the guinea was more popular among rich people. I think it arose as a result of some tax which was 5%. In 1887-1889, there was a failed experiment where they minted a double florin (4 shillings). I have no idea why. There were also 4 pence (aka groat, hilarious name) which stopped circulating in 1800s, and there existed 2 pence and 2.5 pence that (as far as I know) were only in Maundy sets (for collectors) in recent times (i.e. since late 1700s).

I am less knowledgeable about other countries. I think I have a 9 kreuzer coin from some central European country, though. Austria, maybe? It was from the 19th century.


function
calculus
integration
geometry
rectangle
real analysis
real analysis unsolved

Hello: I need a hint for showing the following
Given f_n:A->R a sequence of continous and integrable (in the extended sense) functions who uniformly converge in compact sets
to f:A->R, show that
lim_n integral over A (f_n) = integral over A (f)   [/code]

This is not true with $A=\mathbb R$ and $f_{n}(x)=\frac{1}{(x-n)^{2}+1}$. The sequence converges to $0$ uniformly on compact sets, yet the integral of $f_{n}$ is $\pi$ for any $n$.

The conclusion is true if the sequence is [i]uniformly integrable[/i], that is, for every $\epsilon>0$ there exists $M$ such that $\sup_{n}\int_{-M}^{M}|f_{n}(x)|dx<\epsilon$

If the sequence were uniformly integrable how would the proof go?

If $A$ $\subseteq$ $\mathbb R^{n}$ for $n>1$ what would be the condition of uniformly integrable for the sequence? Perhaps:
$\forall$$\epsilon>0$,$\exists Q$, rectangle, such that
$\sup_{n}\int^{}_{Q}\left|f_{n}\right|<\epsilon$  ?


quadratics
algebra
polynomial
algebra proposed

Suppose that $ a$ and $ b$ are real numbers such that the quadratic polynomial $ f(x)\equal{}x^2\plus{}ax\plus{}b$ has no nonnegative real roots. Prove that there exist two polynomials $ g,h$ whose coefficients are nonnegative real numbers such that: $ f(x)\equal{}\frac{g(x)}{h(x)}$ for all real numbers $ x$.

Even more is true actually.
Take a look at http://www.mathlinks.ro/viewtopic.php?p=1219057#1219057


I think that's wrong.
Try $ a=1, b=3, c=2$

Now it is correct. Thank you very much Yulia for pointing out the mistake! :lol:

[quote="nayel"]Let $ a,b,c>0$. Prove that
\[ \left(\frac{a+b+c}{3\sqrt[3]{abc}}\right)^{3}\le \left(\frac{a^{2}b+b^{2}c+c^{2}a}{3abc}\right)^{4}\]
[/quote]

\[ \left(\frac{b}{a}+\frac{c}{b}+\frac{a}{c}\right)^{4}\ge \left(\frac{a+b+c}{\sqrt[3]{abc}}\right)^{4}\ge 3\left(\frac{a+b+c}{\sqrt[3]{abc}}\right)^{3}\]


Let  f(x),  xε[0,1] with f'(x)>=M>0
Show that there is a space I, in the [0,1] , with length  1/4 : |f(x)|>=M/4 for all x whose belongs to I

Note that f is increasing, so that it suffices to find x >= 1/4 s.t. f(x) <= -M/4 or x <= 3/4 s.t. f(x) >= M/4. Suppose that is not true... then in [1/4, 3/4] f is between -M/4 and M/4. This is contradicted by the mean value theorem, as |f(3/4) - f(1/4)|/(3/4 - 1/4) < |M/4 + M/4|/(1/2) = M, so that some value t in [1/4, 3/4] has f'(t) < M.


Hi,

I wish to type up my solutions using LaTeX this year.

In order to do so, I learned that I must download fancyhdr.sty.

However, when I click the the link 'Click here to download fancyhdr.sty', I see a [url=http://www.artofproblemsolving.com/LaTeX/Images/fancyhdr.sty]text page[/url] instead of a file download window. (In [url=http://usamts.org/Forms/U_Forms.php]this[/url] page)

Could AoPS fix this?

Thanks. :)

Well your browser must be interpreting it as text.

Simply right-click on the link to fancyhdr.sty and choose "Save Link" or "Save Link As" to save it.

Thanks a lot. :)

EDIT: Um, am I supposed to download the file the way dysfunctionalequations mentioned?

I did what he said and when I compiled it, it came out as attached... :|

Yes. I downloaded both solutions.tex and usamts.tex.

Did you put your solutions and the fancyhdr file in the same folder?

Yes...

Huh, when I put all three files in my folder, it says it has 16 errors, and when I put it on the desktop, it says it has 0 errors... (although it says the file does not exist)

EDIT: Okay, now it just says the file does not exist when I compile it and see it...

This depends on what broswer your using, but when you right click and save fancyhdr, make sure you have the filename as "fancyhdr.sty".  For example, in google chrome it will save the file as "fancyhdr", and you won't get what you want without the .sty.

Ugh, still the same...

I downloaded solution.tex, usamts.tex, and fancyhdr.sty, and it says it has 16 errors :stink:

Mine has errors to (about 10, but there is only 1 problem complete), but it turns out fine.  YOu could take the template for handwritten solutions and make it a word doc. and type everything up there.

Don't do that... that is a very bad idea. First of all, word docs are not accepted. Secondly, even if you print them out and submit them by mail, the typesetting looks... very bad. Also, submitting by mail is a pain. I guess you could possibly write the document to a PDF file, but the typesetting would still look... very bad.

I would suggest that you redownload the solutions.tex file and try compiling it again. If it doesn't work, try redownloading all three files. If that doesn't work, reinstall LaTeX.

Reinstalled LaTex.

Still doesn't work...

EDIT: Phew, I got it now.

Thanks for the help!  :)

[quote="dysfunctionalequations"]Don't do that... that is a very bad idea. First of all, word docs are not accepted. Secondly, even if you print them out and submit them by mail, the typesetting looks... very bad. Also, submitting by mail is a pain. I guess you could possibly write the document to a PDF file, but the typesetting would still look... very bad.[/quote]
You don't [i]have[/i] to use LaTeX. I have it, but I prefer Word. You can just use the equation editor in word, if it has one. You don't need LaTeX at all. Also, you can print it as a PDF file, and it will come out fine (the Word equations, not the LaTeX). Then you have what you need, and don't need to mail.

[quote="Math Champion"]Yeah...Word's equations are much easier to type, and you can easily convert a word document to pdf and then upload it.[/quote]

It's up to the user, but in terms of a document dominated by equations, I find LaTeX a lot easier to use because the keyboard is so much quicker than clicking the mathematical symbols and typing, and then pressing the mouse, and then typing, etc. Also, Word's equation-rendering IMO is a bit ugly.

What's an IMO? I don't think you mean the math competition.


1) A traveling salesman has to visit six of the ten cities in his territoriy. Cities A and B are two cities among the ten. If A and B are to be included in the itinerary what is the number of ways? In how many of these will A come before B?

2) A delegation of 4 students is to be chosen from among 12 for a conference. How many ways if 2 particular students refuse to attend the meeting together? How many ways if 2 students who are married to each other will attend on if they both can go? (Note: Are these the same question??? I was thinking of 10 choose 2 = 45 ways for these two questions...)

1.
[hide] 8C4*6! (take 4 from the remaining 8, and permute them). Half of them.[/hide]

2.
[hide] 11C4 (with one student) + 11C4 (the other student) - 10C4 (those without either is double counted)
10C2 (if we choose the pair) + 10C4 (if we don't)[/hide]

[quote] 1) A traveling salesman has to visit six of the ten cities in his territoriy.
Cities A and B are two cities among the ten.
(a) If A and B are to be included in the itinerary, what is the number of ways?
(b)In how many of these will A come before B?[/quote][hide]
(a) Since A and B are already selected, we must choose 4 more from the other 8 cities.
[color=yellow]. . . [/color]There are $C(8,4) = 70$ choices for cities W,X,Y,Z.
[color=yellow]. . . [/color]Then these six cities can be ordered in $6!= 720$ ways.
Therefore, there are $70 \times 720 = 50,400$ ways.

(b) Half of them: $25,200$ ways.
[color=yellow]. . . [/color][I have also worked this out "the long way".][/hide]
[quote]2) A delegation of 4 students is to be chosen from among 12 for a conference.
(a) How many ways if 2 particular students refuse to attend the meeting together?
(b) How many ways if 2 students who are married to each other will attend only if they both can go?[/quote][hide]
There are $C(12,4) = 495$ possible delegations.

[b](b)[/b] There are two cases:
[color=yellow]. . . [/color][1] A and B are both selected.
[color=yellow]. . . . . .[/color]We must select the other 2 delegates from the remaining 10 students.
[color=yellow]. . . [/color]Hence, there are $C(10,2) = 45$ ways for both A and B to be in the delegation.

[color=yellow]. . . [/color][2] Neither is selected.
[color=yellow]. . . . . . [/color]We must select 4 delegates from the remaining 10 students.
[color=yellow]. . . [/color]Hence, there are $C(10,4) = 210$ ways in which neither A and B is selected.

Therefore, there are $45 + 210 = 255$ ways for A and B to be "together".

[b](a)[/b] And therefore, there are $495 - 255 = 240$ ways for A and B to be separated.[/hide]

Edit: I [b]love[/b] your one- and two-line solutions, kueh!


vector
linear algebra
linear algebra theorems

Let $V$ and $W$ be finite dimensional vector spaces over $F$ which are dual with respect to a bilinear form $B$.
If $V_{1}$ be a subspace of $V$ and $V^{\bot}_{1}$ be the [u]annihilator[/u] of $V_{1}$ with respect to $B$.

I want to show the following result:

$\boxed{dim\, V_{1} \,+dim\, V^{\bot}_{1} \, = dim \, V }$

In my book we take a base for $V_{1}$, extend it to a base for $V$ and  since $W \cong V^{*}$ we find a base of $W$
corresponding to the dual base of $V^{*}$ relative to the base of $V$ etc.

I tried the the following:

The vector spaces $V_{1}$ and $W/V^{\bot}_{1}$ are dual with respect to the bilinear form $B_{1}$ defined by

$B_{1}(v_{1},[w])=B(v_{1},w) \, ,v_{1} \in V_{1} \, ,[w] \in W/V^{\bot}_{1}$  therefore  $dim\, W/V^{\bot}_{1} = dim\,V_{1}$.

But $dim\, W/V^{\bot}_{1} = dim\, W - dim\, V^{\bot}_{1}$ and $dim\, W = dim\, V$ so $dim\, V -dim\, V^{\bot}_{1} = dim\,V_{1}$.

It is wrong ?? Because i told that to my teacher and he didnt liked it  :?

Well i am almost sure it is correct and maybe it's trivial but i need a verification from someone who knows the subject  :)

And if it is not correct please explain me why  :)


سلام . از همگی خواهش می کنم هر کی سوالات مرحله سوم امسال 88 را داره بذاره. خواهش مندم و شدید شدید نیاز دارم . سوالات خلاقیت و ترکیبیات و هندسه و جبر و توپولوژی. با تشکر

hendese ro khodam post kardam ([url=http://www.mathlinks.ro/viewtopic.php?t=299851]inja[/url]).
nazariye adad ham ghablan post shode ([url=http://www.mathlinks.ro/viewtopic.php?t=295800]inja[/url]).
jabr ro ham type kardam [url=http://www.irysc.com/ftopict-1587.html]inja[/url] (bazam mazerat mikham chon behtar nashode).
mimune tarkibiat ke type shode hast va baz ham sharmande ke behtar az in nashod...
be tartibe safahat:
untitled , untitled 1 , untitled 2, untitled 3...

khahesh mikonam, inam akharin safhe ke forsat nashode bud bezaram...