[quote="cosinerburc"]can you please show that all positive integers can be written in the form x^2+y^2+z^2+t^2,where x,y,z,t are integers[/quote]

First fact :
if two integers $a,b$ are sum of four squares, then so is $ab$,
this follows from the identity :

$(x^2+y^2+z^2+t^2) \cdot (x'^2+y'^2+z'^2+t'^2) =
(xx' - yy' - zz' - tt')^2 +
(xy' + x'y +zt' - z't)^2 +
(xz' + zx' +ty' - yt')^2 +
(xt' + tx' + yz' - zy')^2 $

We just need to proove that a prime is sum of four squares.
If you don't find this, I'll give a hint later.

Fabrice

[quote="blang"]Try google with : [i]sum of four squares[/i] ;)[/quote]

And Lagrange's theorem.

Pierre.


I don't beleive that calculators should be allowed to be used on the amc because there is a good chance that a person can get a good score because of using them, by installing formulas. There was one problem with inscribtions of a circle and a quadrilateral I beleive on this year's amc and I could not solve it on the contest. Later on I looked up a formula or two in a book and quite easily solved the problem. ( I think the problem was number 12 or 13. I remember that the answer was 27/32 ). This problem can probably be solved without those formulas but by using ingenuity. So if a person has a calculator it is quite possible that because of a stored formula he/she will receive a higher score.

Maybe you should just write that under "AMC tactics?" thread instead of making a new thread...
You could make this into a poll, though. Then I think it's OK.

yeah, a poll of "do you think we should allow calculator use on <place test here>" that would be appropriate. or put in generaleeeee on the "place test here" part.

Using calculators to one's advantage like that won't give them that many extra points.   There are only a few problems on the AMC that require pure formula work only.  Most require other reasoning skills.

-interesting_move

way i see it, the only calculators you need on math contests are scientific calculators

[quote="mathfanatic"][quote="interesting_move"]Using calculators to one's advantage like that won't give them that many extra points.   There are only a few problems on the AMC that require pure formula work only.  Most require other reasoning skills.[/quote]

I concur.  Calculators aren't going to help someone out that much.  You can't use them on AIME or USAMO.  You can't use them in the Sprint or Countdown rounds of mathcounts.  In other words, you won't win just because you have a calculator with lots of programs.

And if you're allowed to use programs, then why not?  It's like preparing for a test.  Besides, by programming formulas, you end up memorizing them anyway, so it's almost just another way of remembering them.[/quote]
Hm.....maybe smart people like you who makes it to AIME a lot won't understand this, but to go to AIME, even if you know that you won't get past it, brings joy. And to have that hope broken just because someone had a better calculator, that's just evil. I know we already discussed this, but many people aren't as lucky as us, to have a graphing calculator and get good education. Those few points becomes important when your on the borderline between whether you make it or not. I lived in California so I know what I'm saying when I say kids in East Palo Alto can [b]not[/b] have graphing calculators, and I think it's unfare that the rich *censored* kids get to have all the glory of going to AIME (please don't laugh :) ) while the others look at him/her with envy and anger...
OK, maybe I got a leeeetle off course, but what I wanted to say is that those few points, maybe even 1, can make a difference, and we shouldn't exclude it from the discussion.

[quote="Fierytycoon"]True, a person having a T!-89 may have an advantage over a kid with a simple non-graphing calculator, but when we talk about the high number of perfect and close-to-perfect scorers on the AMC12, that high number would not decrease due to a banning of calculators. The issue is no big deal really.[/quote]
I want us to focus on the lower levels, level where people are on the borderline of passing or not passing (the AMC).
Maybe it doesn't matter for the top, but it becomes a big issue in the lower areas.

Well, if the AMC ppl want more students (who won't make USAMO anyways)to pass the AMC12 and feel happy, that's fine by me.

They want to keep the level of the AIME the same. Remember that you pay to take the AMC10 or AMC12, but after that, you pay nothing to take the AIME or the USAMO. That means that if many more people take the AIME, that just costs AMC a lot of extra money. Also, the AIME should (in my opinion) keep it's prestige. The idea of the AIME is for about 8000-10000 (I think) of the top students in the country to compete. If that number suddenly becomes 30000, the AIME loses some of its prestige.

[quote]The idea of the AIME is for about 8000-10000 (I think) of the top students in the country to compete. If that number suddenly becomes 30000, the AIME loses some of its prestige.[/quote]

Well...10000 students in the country (200 per state) wouldn't make it too prestigious anyways...

who said 200 per state. in okie-homa this year. i think only 1 or 2 made it to aime. very sad. very sad indeed

[quote="ComplexZeta"]That's not the point. The point is that it is fixed for a certain level of mathematical ability or above, and if people aren't at that level or above, they shouldn't be taking the AIME.[/quote]
I'm just saying that for the people [b]on the borderline[/b], calculators can make it happen.

[quote="mathfanatic"]Wait wait wait, first you want to ban calculators because it would allow people to "cheat", but you like the fact that calculators allow kids who are "borderline" to get into AIME?  I'm confused.

Well, it's true that a lot of people don't make it to AIME.  Are we to take pity on them and make the tests easier?  You have to remember that the AMC isn't a little kindergardner's game where everybody wins; the point is both to involve kids in a difficult competition, and to select the best high-schoolers in the USA to represent our nation at the IMO.

If you wanted to make the competition easier but still retain their lofty goals, it would become necessary to implement still another tier of competition, which would cost the already hard-pressed AMC even more.[/quote]
I'm trying to make just one point: People who doesn't have a graphing calculator shouldn't be excluded from the AIME if their points were extremely close to the passing mark.
I decided not to pursue the "cheating" line of the argument because technically it isn't.


algebra
polynomial
linear algebra
matrix
vector
linear algebra unsolved

Suppose $ a_0, a_1, ..., a_{n\minus{}1}$ are complex numbers. Find the minimal and characteristic polynomials of the operator on $ C^n$ whose matrix (with respect to the standard basis) is

0 0 0 ...... $ \minus{}a_0$
1 0 0 ...... $ \minus{}a_1$
0 1 0 ...... $ \minus{}a_2$
.........................
.........................
0 0 0..... 1 $ \minus{}a_{n\minus{}1}$

where the line below diagonal consists of all 1, the right most column consists of $ a_0$, $ a_1$, ..... and all other entries are 0.

We claim that both matrices are $ P(x) \equal{} x^n \plus{} a_{n \minus{} 1} x^{n \minus{} 1} \plus{} ... \plus{} a_0$.  Transpose the matrix and consider its action on the basis with column vectors of the form $ 1, \alpha_k, \alpha_k^2, ... \alpha_k^{n \minus{} 1}$ where $ \alpha_k$ are the roots of $ P(x)$.  This is the [url=http://en.wikipedia.org/wiki/Companion_matrix]companion matrix[/url] construction.  (Deal with the case that $ P$ has distinct eigenvalues; this case is dense in the general case, and the characteristic polynomial construction is continuous.  I'm not sure if this handles the minimal polynomial requirement, though.)


group theory
abstract algebra
superior algebra
superior algebra unsolved

Let  H  be  a  subgroup of  G.  Define  C(H) = all a in G  such  that ah=ha for all  h in H. Prove that  C(H) is a normal  subgroup  of G and that G/C(H) is a subgroup of Aut(H).

What is the kernel of $ a\mapsto (x\mapsto x^{\minus{}1}ax)$?


quadratics
linear algebra
linear algebra unsolved

Let X and Y be the nxn matrices. If we look at them as the elements  of $R^{n^2}$ then
1)Prove that Tr(XY) is symmetric  bilinear form.
2)Find its index of  inertion.
[hide]in russian: nayti eyo index inercii[/hide]

May be it is the positive and negative indexses of inertion  :?:

Rustam, can you write the definition the index of inertion?

The index of inertia of a quadratic form equals the number of negative eigenvalues. (See http://eom.springer.de/l/l057710.htm for the definition.)


EDIT: Can anyone solve these for me? I'm not sure of how to do them.  >__<;;

Determine each angle measures:
[img]http://img90.exs.cx/img90/8868/prob13lu.jpg[/img]
1. m<OJF
2. m<JFA
3. m<HCJ
4. m<COF
5. m<JHO
6. m<AFC
7. m<HOJ
8. m<JOF
9. m<AOC

I don't get this T_T

Use the definition of an inscribed angle.

Its measure is one-half of the arc it intercepts. In this case, the inscribed angle is $\angle HCJ$, which intercepts arc HJ.

For the other angle, the angle from the origin which intercepts an arc has the same measure as that arc. That should help a little.

Tell me if you need more hints.

Whoops meant that.  :blush:

[quote="white_horse_king88"]
Tell me if you need more hints.[/quote]

More hints please? heh ^^;;;

But $\angle HOJ$ is not an inscribed angle. It is a central angle, and therefore is equivalent to the arc measure.

On the other hand, $\angle HCJ$ [i]is[/i] an inscribed angle :D

If two angles intercept the same arc, they are congruent.


function
inequalities proposed
inequalities

There are long and short proofs for this classical song ! ...

the favorite one ( I like ) is to use convexity by fixing two of the 3 variables at a time and the LHS is a convex

function in the third variable so it must attend maximum at end points which are 0 or 1. A follow up calculation

at these end points lead to the max value = 1 and you're done.

 :rotfl:

It was posted before. Or see [url=http://www.kalva.demon.co.uk/usa/usoln/usol805.html]Kalva page[/url]


factorial
calculus
integration
floor function
number theory unsolved
number theory

Hi all,
Here is a problem I thought up of my own. I think it should be easy.

Find all 'n' such that n!, when expressed in scientific notation
n!=a*10^k, then k=n.

Sanjith

Is $a$ integral or $1\leq a<10$¿

1. one:
The number of zeros at the end of $n!$ is given by $\sum_{i=1}^\infty \left\lfloor \frac{n}{5^i} \right\rfloor$.
This is $\leq \sum_{i=1}^\infty \frac{n}{5^i} = \frac{n}{4}$.
Thus, there will be never be enough zeros.

2. one:
This means that $10^n \leq n! < 10^{n+1}$.
Since $n!$ grows clearly faster than any power $a^n$, this is only possible for finetely many cases, which I don't want to do.

a is not integral, 1 <= a < 10.

Also, a short calculator checking will show that 25,26 are the only possible solutions.

Sanjith.


AMC
USA(J)MO
USAMO
AMC 10
AMC 12
AMC 10 B
AIME

Hmm...DID YOU MAKE IT?

pS: Special thx to Zenith Xan~ You're right: Indicies of 197 (117/8) and 196.5 (106.5/9 or 136.5/6) do exist. So...If you got 197 or 196.5, I guess you fit into the "Don't talk about it" catogory ><

There should be an option for making it via floor.

1) Indicies of 197 (117/8) and 196.5 (106.5/9 or 136.5/6) do exist
2) You can make it by the floor if you're an underclassman.

Holy crap I MADE IT BY INDEX?

/joy

On the nose, by the way. 127.5 + 7 AIME.

I cleared the index by a lot :)

I chose not to take the AMC10 as a freshman, but I did really well on the AMC12 :)

144+7*10 = 214.

lol.. 198, lucky me, I thought I can't make it since I made so many mistakes..

$138+6*10=198$

Hmm...Looks like I just screwed up this poll >< Could the moderators please delete this post? I'll create a better one.

lol yes
seventh grade: amc10B (136.5) + aimeII (7)(10) = 206.5
and i thought i was hopeless cause everyone was saying on aops that the cutoff would be like 220 or something  :ninja:

amc10 doesn't count for qualifying by index, i don't think
however, u did make floor

wait i thought it did
isnt amc10 index like 180 something?

well, i was referring to the 197(?) index
but, er, yeah, index of 181 along with floor

yeah i thought so
cause i messed up on amc12 and aime and i wouldnt have made it if i did amc12
so amc10 worked for me! =D


analytic geometry
geometry
geometric transformation
rotation

hey.. i was able to get my hands on this.. there a few problems i was unsure about.. maybe we could use team work to figure it out.. please when you post your answer, post an explaination of why you think its right and why you think a different answer is wrong..

1st..
look at the attachment named 1.gif
the pullies and string are massless..
what is the mass of the question mark?
i think it should be somewhere between 1 and 1/2

2nd
look at attachment as well..
the first senairo is a ball hit a wall at velocity v, and bounces back at v. which means the collision is elastic. but the second senario, the wall is moving towards the ball at speed c. the collision is still elastic, what will be the speed of the ball as it bounces off the wall?
i think its v.. not sure tho.. still pondering on it..

3rd..
attachment..
the roll of string is pulled to the right. if it cannot roll without slipping.. then which direction would the string roll?
i said neither left or right, because the torque created by the tension from pulling it will only cause it to roll to the left, but the friction force would probably cancel it out. it cant roll to the left because in order for that to happened, the total force on the string would have to be to the left, which can only be caused by friction. and if friction is greater than the tension, then the torque created by friction would cause it to roll to the right.. which is contradictory.. so it must remain still..

1) 1kg is pulling down with a force of 9.8N, and since you have a frictionless, massless, unrealistic pulley, the forces on the two segments holding it up are clearly equal (T=4.9N), and the force over on the other end of the string is equal as well, T=4.9N, T=ma, 4.9=m9.8, and m=1/2 kg. Unless I'm wrong.

2) The velocity of the ball [i]relative to what?[/i]
$V_{ball}$ relative to ball = 0 , but that's trivial.
If you measure everything relative to the wall, then your speed c makes no difference (inertial frame), and $V_{ball}$ after the collision is just -v. (Note: it can't hit the wall with velocity v and bounce off at velocity v, because a velocity indicates a direction as well, and if it continues in the same direction at the same speed, it never bounced.)
If you measure relative to something else, which sees the wall moving at speed c toward the ball (c being a negative number in the coordinate system I've chosen, in which -x is to the right), and the ball moving at speed v, then the ball strikes the wall at a speed of v-c (remember c is negative), as "felt" by the wall. It then bounces back off the wall with a velocity of -(v-c) (see reasoning from when we were measuring relative to the wall - it's the same thing, measured from a different inertial frame). So the ball is then moving at a speed of c-v relative to our observer, or a speed of -v relative to the wall, just as before.

3) It [b]cannot[/b] roll [b]without[/b] slipping? This wording seems rather confusing to me. Did you copy these problems verbatim?

hmm.. i agree with confuted for problem one? but i think its because there are two strings for the pulley so the force required x distance is like a constant, but i'm not sure.  the other two are too hard.

is there really a caltech freshman physics test, or is this just to attract veiws?

[quote="starrynightskies"]is there really a caltech freshman physics test, or is this just to attract veiws?[/quote]
He said it was a placement test. That makes sense.

for number 3, try it out with a spool of thread, it will roll to the right on that picture, and since the outer radius is larger than the inner, wind up toward your fingers. The torque caused by friction is greater than that caused by the applied force.

Now, I'm not exactly sure how to show this through equations... but here is a shot.  If we can show the spool moves toward the right, we know that it will accelerate faster than the string and wind up. If there is no slipping, suppose that the spool moves x*outer radius meters, x*inner radius meters of the string have been wound up, and thus the end of the string only moves the difference of the values, thus moving the the right an winding up.

... right and clockwise rotation being positive
F= applied force
f= frictional force
R=larger radius
r= smaller radius

ma = F-f
f=F-ma

I(a/R) = fR-Fr
I(a/R) = (F-ma)R-Fr

so consider a negative a, that means that
(F-ma)R<Fr
but since R>r and F-ma>F (for a negative a) this is impossible, thus the spool must accelerate to the right, and thus is will wind up toward the end of the string till all the string is wound.

edit: also notice if the spool would roll left, the when the spool moves x*outer radius, x*inner radius of the string is unwound, and thus the string must actually move to the left for this to happen. ;)

Try out the same thing with a spool of thread just pulling upward at an large angle, now the spool will roll backwards, you have decrease the force to the right while maintaining the same ctr-clockwise torque. Also, you can get it to roll left if the radius the string is wound on is larger than that touching the ground (itd have to touch on the sides)... u can try it out of u have a spool like that

confuted.. you are very wise..
for third problem.. it rolls without sliping..
and it is indeed the freshman placement exam..
i didnt copy verbatim, i just remembed the problems i had trouble with

for problem 1, notice that the string is not straight up, which means that the tension on the string might not be 4.9N, since 4.9 is only the up force, there is also a component of the force in the x direction

and for problem 2, shouldnt it be V+C? since the wall and the ball are moving towards each other? and the velocity is V+C from the perspective of the wall, the ball still travels a velocity of V from our perspective.. which takes me to the conclusion that the speed should be V+C after it hits the wall.. which was my original conclusion...

[quote="kentliu"]i didnt copy verbatim, i just remembed the problems i had trouble with

for problem 1, notice that the string is not straight up, which means that the tension on the string might not be 4.9N, since 4.9 is only the up force, there is also a component of the force in the x direction

and for problem 2, shouldnt it be V+C? since the wall and the ball are moving towards each other? and the velocity is V+C from the perspective of the wall, the ball still travels a velocity of V from our perspective.. which takes me to the conclusion that the speed should be V+C after it hits the wall.. which was my original conclusion...[/quote]
Would it be possible to obtain the questions verbatim, or even the whole test?

For 1 - you make a valid point. The horizontal components would cancel, though. So the reasoning in the middle was a bit shaky, but I think the answer is still correct (unless information was provided in the problem that you haven't relayed)

For 2 - note that the ball bounces off with the negative of the velocity that it hit the wall with. I defined c as a negative number, because I defined the positive direction to the left and the negative to the right. A strange convention, I know, but fundamentally it's valid to use any coordinate system (what an odd world it would be if that was not the case!)

So the ball is cruising along at speed v, and the wall is cruising along at c (a negative number!), so when the ball hits the wall, we subtract c from v (v-c) to get the speed the wall feels the ball hit. Intuitively, you're saying "but that should be v+c!" - note that is EXACTLY what I'm doing; c is negative. If c was positive, so it was moving away from the ball, well, clearly you would subtract; it's the same thing. We noticed before that it bounces off with negative the velocity it hit, so the new velocity is -(v-c). Let's distribute that out a bit. It equals -v+c, and c is negative, so that's the same as -v-|c|=-(v+|c|) ... |c| is just the speed of c (in the one dimensional case only!), or the c that you have written above. Remember, I kind of redefined it so I could have a consistent coordinate system.

For 3 - if it rolls without slipping, my intuition tells me that it HAS to roll to the left; it's turning CCW. I believe that it should be possible to construct a more "rigid" argument for this if you consider that the center of mass isn't going to want to move, but it's 3:15am, so that might be rather incorrect. I'll come back and ponder more tomorrow. For now, I'm off to get about five hours of sleep.

well, i read the problems really carefully.. and the thing with cal tech problems (i've done others before), is that they are really ambiguous.. probably to test if the student truely knows the material..

i still remember alot of the other problems.. i'll post some more up tomorow if u want them.. and well, its 2:18 am here, so i'll go get like few hours of sleep as well..

[Moderator:  Are we sure it's OK to post and discuss these questions?  If not, please delete this post!]  It's been a long time since I took physics, but I don't think the solutions posted to these 3 problems are completely satisfactory.  Hints in spoiler:

[hide]Problem 1.  Consider the pulley on which the 1kg mass is suspended.  If the tension in the two segments of rope/string are unequal, the pulley wheel will be accelerating.  If this is a static system, the tension in the two segments must be equal.  Likewise for each of the other pulleys.  So what mass is required on the RHS to give the proper tension?

Problem 2.  I don't think the posted answers are correct.  Think "slingshot".  Look up NASA's missions to the outer planets.

Problem 3.  No need to use force, mass, or acceleration.  Just draw 2 more pictures.  Draw one picture showing the spool one full revolution (without slippage) to the left of its starting point.  Draw another picture showing the spool one full revolution (without slippage) to the right of its starting point.  Where is the end of the string in each picture?[/hide]

no offense rcv.. but wut you said doesnt make any sense..

wuts ur suggestion to problem 2?

[quote="kentliu"]No offense rcv.. but what you said doesn't make any sense..
What is your suggestion to problem 2?[/quote]

More than a hint...  If you want a complete solution, visit this [url=http://www.mathpages.com/home/kmath114.htm]Gravitational Slingshot[/url] web site.

If anyone wants all of the questions (just 10): http://www.pma.caltech.edu/GSR/froshplacement.html

on that test, I would say in both cases, A and B, the spool rolls to the left. The only way to pull that string and make it move right is to slip to the right. The only way it can stay still is if it slips at the same rate that it unrolls.... without slipping, it cannot spin and go anywhere except left.

Also, this problem cannot be tested in real life, because I doubt very much that someone could find a spoll and surface with absolute 0 slippage or even anywhere close to it. This is an unrealistic problem.

anyone know where to get the answers for the physics exam?


In triangle $ABC,$ the angle $\angle A$ is equal to $60^\circ;\, O$ is the center of the circumscribed circle, $H$ is the orthocenter, $I$ is the center of the inscribed circle and $I_{a}$ is the center of the escribed circle tangent to side $BC.$ Prove that $IO = IH$ and $I_{a}O = I_{a}H.$

First $\measuredangle{BAH}=90-\measuredangle{ABC}=\measuredangle{OAC}$
so  $\measuredangle{HAI}=\measuredangle{OAI}$
also $HA=2R_{ABC}*cos{\measuredangle{BAC}}=R=OA$
so $\triangle{AOI}=\triangle{AHI}$ which gives $IH=IO$
and $\triangle{AOI_{a}}=\triangle{AHI_{a}}$ which gives $I_{a}H=I_{a}O$


To start off, here are two from me.  :)

1) Why do you rarely find mathematicians spending time at the beach?
Because they have sine and cosine to get a tan and don't need the sun!

2) In a speech to a gathering of mathematics professors from throughout the United States, George W. Bush warned the academics not to misuse their position to force their often extremist political views on young Americans. "It is my understanding", the president said, "that you are frequently teaching algebra classes in which your students learn how to solve equations with the help of radicals. I can't say that I approve of that..."

I'm so easily amused.  :rotfl:

Don't we have a topic [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=40460]here?[/url]

Sorry, didn't see that. I was thinking more along the lines of a joke thread though.


Deborah built a box by cutting 3-inch squares from the corners of a
rectangular sheet of cardboard, then folding the sides up. The volume of the box is 150 cubic
inches, and the longer side of the box is 5 inches more than the shorter
side. Find the number of inches in the shorter side of the original sheet
of cardboard.

[hide="hint"]apply variables and do some algetry[/hide]

[hide="solution"] Since the squares formed on each corner are 3 by 3, when we fold them up, the height of the box will be 3.  Since the volume of a box is height(area of base), we know that 3(area of base)=150, so area of base=50.  Now, we are also given that the length is 5 less than the width.  Guessing and checking gives us that the length of the prism is 10 and the width is 5.  Now, when we unfold the box, we have to add in the 3 on both sides of the rectangle.  Therefore, we must add 3(2)=6.  5+6=11, which is the shortest side.  [/hide]

[quote="Interval"]The tips are great for my collection of math notes for the upcoming state exam.

Thanks![/quote]
After this state exam are you going to stop bombarding aops with your problems?


geometry
inequalities
algebra unsolved
algebra

Find the minimum value of the expression
$ \sqrt{4x^2\plus{}4x\plus{}65}\plus{}\sqrt{4x^2\minus{}92x\plus{}1105}$

[quote="xxxxtt"]Find the minimum value of the expression
$ \sqrt {4x^2 \plus{} 4x \plus{} 65} \plus{} \sqrt {4x^2 \minus{} 92x \plus{} 1105}$[/quote]

Let $ f(x)\equal{}\sqrt {4x^2 \plus{} 4x \plus{} 65} \plus{} \sqrt {4x^2 \minus{} 92x \plus{} 1105}$ $ \equal{}\sqrt {(2x\plus{}1)^2\plus{}64} \plus{} \sqrt {(2x\minus{}23)^2\plus{}576}$

Then $ f'(x)\equal{}\frac{2x\plus{}1}{\sqrt {(2x\plus{}1)^2\plus{}64}}\plus{}\frac{2x\minus{}23}{ \sqrt {(2x\minus{}23)^2\plus{}576}}$ $ \equal{}\frac{(2x\plus{}1) \sqrt {(2x\minus{}23)^2\plus{}576}\plus{}(2x\minus{}23)\sqrt {(2x\plus{}1)^2\plus{}64}}{\sqrt {(2x\plus{}1)^2\plus{}64} \sqrt {(2x\minus{}23)^2\plus{}576}}$

So $ f'(x)\equal{}512\frac{(2x\plus{}13)(2x\minus{}5)}{\sqrt {(2x\plus{}1)^2\plus{}64} \sqrt {(2x\minus{}23)^2\plus{}576}((2x\plus{}1) \sqrt {(2x\minus{}23)^2\plus{}576}\minus{}(2x\minus{}23)\sqrt {(2x\plus{}1)^2\plus{}64})}$

And so $ f'(x)$ is negative for $ x< \frac 52$ and positive for $ x>\frac 52$ and minimum is $ f(\frac 52)\equal{}40$

[hide="I have a feeling this has a more elementary solution"]
Let $ y \equal{} 2x \plus{} 1$, and look at the following diagram:

[geogebra]56b6135d91c706f65ae14fdbff8a9f65a4759b2d[/geogebra]

Note that we want to minimize $ VP \plus{} ZP$. However, it is well known (since a line gives the shortest distance between two points) that the minimum of this distance is when $ WS \equal{} WZ$, if such a $ y$ exists such that this is true, of course (if not it is the $ y$ that makes $ WS$ closest to $ WZ$). Then, $ \triangle WSP \sim \triangle TVP$, so
\[ \frac {8} {24} \equal{} \frac {|y|} {|y \minus{} 24|}\implies 3|y| \equal{} |y \minus{} 24| \implies y \equal{} 6\]
Therefore, the minimum is $ \sqrt {6^2 \plus{} 8^2} \plus{} \sqrt {18^2 \plus{} 24^2} \equal{} 10 \plus{} 30 \equal{} 40$.
[/hide]

[quote="Duelist"]I have a feeling this has a more elementary solution[/quote]

As soon as there is a solution involving geometry, I'm sure to miss it :)

[hide="Algebraic solution"]

Minkowski inequality: $ \sqrt{(2x\plus{}1)^2 \plus{} 8^2} \plus{} \sqrt{(23\minus{}2x)^2 \plus{} 24^2} \ge \sqrt{24^2 \plus{} 32^2} \equal{} 40$

with equality when $ \frac{2x\plus{}1}{23\minus{}2x} \equal{} \frac{8}{24} \equal{} \frac{1}{3} \Rightarrow x \equal{} \frac{5}{2}$

[/hide]


calculus
integration
trigonometry
calculus computations

How to you solve $ \int \sqrt((1 \plus{} u^2))  du$

1. $ u \equal{} \tan x$
2. $ \int \sqrt {1 \plus{} u^2}\ du \equal{} u\sqrt {1 \plus{} u^2} \minus{} \int u\cdot \frac {u}{\sqrt {1 \plus{} u^2}}\ du\ \text {Integrall by parts}$
3. $ u \equal{} \frac {e^t \minus{} e^{ \minus{} t}}{2}$
4. $ u \equal{} \frac 12 \left(t \minus{} \frac {1}{t}\right)$

You can draw a right triangle with sides $ 1$, $ x$, and $ \sqrt{1\plus{}x^2}$, get $ \theta$ in terms of $ x$. If you draw it the way I did, $ \sec\theta$ is your integrand, and $ \tan\theta\equal{}x\implies \sec^2\theta\; d\theta\equal{}dx$.

Then the integral becomes $ \int \sec^3\theta\; d\theta$, which is done by integration by parts.


limit
induction
calculus
calculus computations

That one took some time; the solution is quite long so i'll post a plan. Let $y_{n}=x_{n}-n-\frac1 2$, hence $y_{n+1}=\frac1 2-n+\frac{y_{n}+n+\frac1 2}{n^{2}}+\frac{n^{2}}{y_{n}+n+\frac1 2}$. One can show by induction that $x_{n}\leq n^{2}$ when $n$ is big, so we shall get upper bound for $y_{n+1}$ by letting $y_{n}=0$: we shall have $y_{n+1}\le \frac1 n+\frac{1}{2n^{2}}+\frac{1}{4n+2}$.
Now we have to show that $y_{n}>0$, it can be done by simplifying the formula for $y_{n+1}$ and using the upper bound for $y_{n}$. When this is done, we see that $y_{n}\to 0$.


inequalities
search
inequalities unsolved

Given $ a,b,c > 0$. Prove that:
$ (ab \plus{} bc \plus{} ca)[ \frac {1}{(a \plus{} b)^2} \plus{} \frac {1}{(b \plus{} c)^2} \plus{} \frac {1}{(c \plus{} a)^2}] \ge \frac {9}{4}$

Searhing gives for example http://www.mathlinks.ro/Forum/viewtopic.php?search_id=58113521&t=249265 and a generalization in http://www.mathlinks.ro/Forum/viewtopic.php?search_id=203785920&t=292625


vector
induction
integration
number theory
greatest common divisor
algorithm
relatively prime

For $n = 1$ and $a_1 = 2$ you will only have even integers, so we must be at least  add the condition $n>1$. Is there any other missing condition?

Pierre.

[quote="pbornsztein"]For $n = 1$ and $a_1 = 2$ you will only have even integers,[/quote]

Hmm... if $a_1 = 2$, then the greatest common divisor is 2, not 1...

I think I have some steps towards the solution of the problem: At first, $0\in S$, and moreover, if $x\in S$ and $y\in S$ and $x+y\in S$, then for every integer m and n we have $mx+ny\in S$. Now, if we succeed to find two relatively prime elements in S, then we will be done.

  Darij

[quote="darij grinberg"]Now, if we succeed to find two relatively prime elements in S, then we will be done.
[/quote]

Just to comment on that, I think a lot of contestants made the mistake by claiming that there are two a_i, a_j, which are relatively prime. But this is not necessarily true, say for {6, 10, 15}.

Here's an outline of my solution.

I first showed that any integer s can be writen as $\sum a_i t_i$ for some integer vector $(t_1, \ldots, t_n)$. If n=2, then it's bezout's theorem. Otherwise we have by induction $s = \sum_{i=1}^{n-1} a_i t_i +\gcd(a_{n},a_{n+1}) t_n$. And then write $\gcd(a_{n},a_{n+1})$ as some $a_{n} p_n+a_{n+1} p_{n+1}$.

Then, by using some iteration/induction, we can show that $a \in S$ implies $ma \in S$ for each integer m. We can carry further by showing that $a, b \in S$ implies $pa+qb \in S$ for any integer p, q. And so on, so $\sum a_i t_i \in S$ for any vector (t). And we are done by the first claim.

Just a little variation: it is nown that for any set of integers, there is a linear combination of them equal to their biggest common divisor, so in our special case, there is a linear combination of the ai equal to 1, and result follows!

[quote="billzhao"]$a, b \in S$ implies $pa+qb \in S$ for any integer p, q.[/quote]

This is the only piece of the problem that I do not see how to do. Could you please post your proof of this lemma?

Why does this problem lie in Solved Section? I don't see solution. Moreover, I also don't believe some billzhao's arguments.

I will move it to Unsolved Section.

Ok. Let's do some steps.
1) $a\in S$ implies $ma\in S$. Indeed, $0\in S$, $a\in S$ and $0+a\in S$, so $-a=0-a\in S$. Suppose $ka\in S$ and $(k-1)a\in S$, then $ka+(-a)\in S$ implies $(k+1)a=ka-(-a)\in S$. So $ma\in S$ for all $m\in\mathbb{N}$. So $-ma=m(-a)\in S$.

2) For all $a_i$ and $a_j$ numbers $pa_i+qa_j\in S$. By induction, for example: $a_i-a_j\in S$ implies $a_i+a_j\in S$, $(a_i+a_j)-a_j\in S$ implies $a_i+2a_j\in S$ and so on (induction on $|p|+|q|$).

Here is the rest of solution:
Let 2^e_i||a_i and wlog assume $e_1\geq\ e_2...\geq\e_n$
Let $d_i =gcd(a_1;...a_i)$ we will prove by induction that S contain all multiple of d_i,case i=n is the desired result
Assume that S contains all multiple of d_i for some $2\leq\i<n$.Let T be the set of integers m such that m is divisible by d_i and $m+ra_{i+1}\in S$for all integers r.Then T contains nonzero positive and negative numbears,namely any multiple of a_i.If $t\in T$ and s is divisible by d_i s.t $t-s\in T$ and $t+s\in T$.By taking t=s=d_i we deduce that $2d_i\in T$;by induction we have $2md_i\in T$ for any integer m
It's easy to see that we can find integer f,g with f even s.t fd_i+ga_{i+1}=d_{i+1}.Then for any integer r we have $rfd_i\in T$ and so $rd_{i+1}\in S$.We are done

Okay, now looking back at my old "solution" (TWO YEARS AGO!!!!), I probably made the incorrect assumption that clause (b) read "if $x, y \in S$ then $x - y \in S$", which simplifies the problem dramatically.

Sorry guys ... (still, it was two years ago)  :blush:

Wow, this is such a cruel realization. I always thought that I had solved this problem.

Well, I guess it would feel better to realize it now than it would have been two years ago ...

wait....

how do we know that d_i is in set T?

0 = a_i - a_i for any i={1,2,...,n}  (prop 2 ).Hence 0 belongs to S.

There exist integers k_1, k_2,...k_n such that
k_1a_1 +k_2a_2 + ...+ k_na_n = 1        ->bezout's theorem

Suppose a  k_i, where i={1,2,...n} is positive, it can be obtained by adding a_i to itself.( n-1 operations required)( again prop 2, this is trivial,go for induction for rigour)

Since 0- k_i belongs to S(prop 3), any negative co efficient may be obtained.
=>1 belongs to S.
Any +ve or negative integer can be obtained by prop 2 and prop 3.

This problem can perhaps be solved with this in mind.

Obviously "zero" lies in the set. SO negative numbers of same absolute values as positives can be generated.

That is, if

                 a is +ve ; a belongs to s            and                0 belongs to S

                  So does -a....

So we will prove that we can generate all the positives only...

Consider 2 +ve integers to each other on a board. U can  place any positive difference of the numbers on the board if it does not exist already. clearly the smallest number u place is the gcd "d" of the numbers say "a' and "b".

And the numbers b-d, b-2d, b-3d..d all appear on the board. If gcd (a,b)=1, all numbers less than or equal to b appear.

Now u can create all numbers larger than b too which settles the case for n=2.

All numbers larger thn b are created by noticng that 1 and 0 lies on the board. there sum is on board. So -1 will can be kept on the board. Do it...

b is on board; -1 is on board...there sum b-1 is on board...So b+1 "their diff is on board"...
Similarly b+2, b+3 and all bigger numbers can be put on board (or the set S)..

For n > 2, take a & b with a gcd d > 1 (possibly)....generate d....

Consider d and a number "c" with gcd(c,d) = e....

Since gcd of all n numbers is 1, sooner or later two number with gcd 1 appear....at which stage the game is over

Here's a weird proof that you can get any linear combination of $ a_{1},a_{2},\ldots,a_{n}$, after which we can prove using the extension of Bezout's Theorem (which is not hard with induction) that we have to have 1 on the board.

So we induct on $ n$, showing that we can get linear combinations of any subset of our starting integers. For $ n\equal{}2$ (because for $ n\equal{}1$ the whole problem is trivial), we can use the Euclidean Algorithm to get down to $ \gcd(a_{1},a_{2})$. Like, we have $ a_{1},a_{2}$, and also $ a_{1}\minus{}a_{2}$, and now we have $ a_{1}\minus{}a_{2}\plus{}a_{2}\equal{}a_{1}$, etc. This means we can get any multiple of the gcd, and thus any linear combination of $ a_{1}$ and $ a_{2}$ (by Bezout).

Now assume it's proven for n-1 (ok this really should be k instead of n here, but you get my drift). We claim that we can get any $ x_{1}a_{1}\plus{}x_{2}a_{2}\plus{}\cdots\plus{}x_{n}a_{n}$. Say one of the $ x_{i}$ is even. Then, $ x_{1}a_{1}\plus{}x_{2}a_{2}\plus{}\cdots\plus{}\dfrac{x_{1}}{2}a_{i}$ and $ \minus{}\dfrac{x_{1}}{2}a_{i}\minus{}x_{i\plus{}1}a_{i\plus{}1}\minus{}\cdots\minus{}x_{n}a_{n}$ are both attainable, as is their sum, because the $ a_{i}$ term vanishes and it's a linear combination of $ n\minus{}1$ of the starting values. Thus, their difference is attainable, which is what we want (of course, we have to modify this argument if i=1 or i=n, but this is easy; apply a "frame shift"). Now it suffices to consider the case when all the $ x_{i}$ are odd. We claim that it will be equal to some other linear combination in which one of the $ x_{i}$ are odd. Take any two of the $ a_{i}$, say $ a_{i}$ and $ a_{j}$. Then we can find integers $ c$ and $ d$ such that $ ca_{i}\plus{}da_{j}\equal{}0$ and at least one of $ c$ or $ d$ is odd (if they are both even, keep dividing out factors of 2). Then, just add this to our linear combination where all the $ x_{i}$'s are odd, and we'll have an even coefficient somewhere. So we're done.

Actually, it's not necessary to prove that all linear combinations of $ a_i$ are attainable.  We can alternatively induct on $ k$ to prove that all linear combinations $ \sum_{i\equal{}1}^{k} x_ia_i$ such that all but 2 of the $ x_i$ are even are attainable (this is easily proved by just halving even $ x_i$; actually "all but 1" is sufficient but it's easier to prove "all but 2").  Pick $ a_n$ to be odd, WLOG (obviously they can't be all even).  By the condition of the problem $ ((a_1,a_2,\ldots,a_{n\minus{}2}, a_{n\minus{}1}),a_n)\equal{}1$.  Let $ G\equal{}(a_1,a_2,\ldots,a_{n\minus{}2}, a_{n\minus{}1})$.  Bezout gives $ \sum_{i\equal{}1}^{n\minus{}1} y_ia_i\equal{}G$ for certain $ y_i$.  Then $ \sum_{i\equal{}1}^{n\minus{}1} (2y_i)a_i\equal{}2G$ which is still coprime to $ a_n$.  Then apply bezout's again and we'll get for some $ p$ and $ q$, $ \sum_{i\equal{}1}^{n\minus{}1} (2y_ip)a_i\plus{}qa_n\equal{}1$, and this linear combination is achievable by induction above.

The idea is to show any linear combination of the $a_i$ are in $S$, which implies (by Bezout) that $S = {\mathbb Z}$. This is pretty intuitive, but the details require some care (in particular there is a parity obstruction at the second lemma).

First, we make the following simple observations: [list] 	[*]$0 \in S$, by putting $i=j=1$ in (b). 	[*]$s \in S \iff -s \in S$, by putting $x=0$ in (c). [/list]

Now, we prove that:

[b]Lemma[/b]:  	For any integers $c$, $d$, and indices $i$, $j$, 	we have $ca_i + da_j \in S$.

[i]Proof.[/i]  	We will assume $c,d > 0$ since the other cases are anologous. 	In that case it follows by induction on $c+d$ 	for example $ca_i + (d-1)a_j$, $a_j$, $ca_i + da_j$ in $S$ 	implies $ca_i + (d+1)a_j \in S$. $\blacksquare$

[b]Lemma[/b]:  	For any nonzero integers $c_1$, $c_2$, \dots, $c_m$, 	at least one of which is even, 	and any indices $i_1 < i_2 < \dots < i_m$, we have 	\[ \sum_k c_k a_{i_k} \in S. \]

[i]Proof.[/i]  	By induction on $m$, with base case $m \le 2$ already done. 	Assume WLOG $c_1 \neq 0$ is even and note that 	\begin{align*} 		x &\overset{\text{def}}{=} \frac{1}{2} c_1 a_{i_1} + \sum_{k \ge 2} c_k a_{i_k} \in S \\ 		y &\overset{\text{def}}{=} -\frac{1}{2} c_1 a_{i_1} \in S \\ 		x+y &= \sum_{k \ge 2} c_k a_{i_k} \in S \\ 		\implies x-y &= \sum_{k \ge 1} c_k a_{i_k} \in S. 	\end{align*} 	This implies the result. $\blacksquare$

Now by taking $m = n$ in the above, any nontrivial linear combination of the $a_i$ with at least one even coefficient are attainable. So suppose that  \[ 1 = \sum_{i=1}^n c_i a_i \] is given by Bezout. The only obstruction possible is if all $c_i$ are either zero or odd, so WLOG the first $k \ge 2$ are odd and the rest are zero (if $k = 1$, then $1 = |a_1| \in S$ already). WLOG again $a_1$ is odd. Then we also have \[ 1 = (c_1 + a_2) a_1 + (c_2 - a_1) a_2 + 	c_3a_3 + \dots \] which has at least one even coefficient, namely $c_2-a_1 \equiv 0 \pmod 2$.

@v_Enhance sorry I'm a bit confused. In the proof for your second lemma, how do we know that $x$ and $x+y$ are in $S$? Doesn't $x$ include $m$ $a_{i_j}$s instead of less than $m$ for the induction? (Is there an underlying additional induction on $\sum_i |c_i|$ or something like that?) Also, why couldn't all of $c_2, \ldots, c_m$ be odd (against the induction for $x+y \in S$)?

You're correct on both counts, sorry. I'll try to patch it.

Darn. Your finish with the $c_1 a_1 + c_2 a_2 + c_3 a_3 + \cdots \Longrightarrow (c_1 + a_2)a_1 + (c_2 - a_1)a_2 + c_3 a_3 + \cdots$ seemed really cool and clever regardless!

I guess something like CatalystOfNostalgia's approach is the same in principle: first get length $m$ sequences with at least one even coefficient $x_{i_r}$ with $x_{i_1} a_{i_1} + x_{i_2} a_{i_2} + \cdots +\frac{x_{i_r}}{2} a_{i_r}$ and $-\frac{x_{i_1}}{2}a_{i_r} - x_{i_{r+1}} a_{i_{r+1}} - \cdots - x_{i_m} a_{i_m}$, both in $S$ by induction (relabeling indices to "cut" at a middle term if $r = 1$ or $r = m$), as well as their sum. For all odd coefficients, realize that such an expression can be expressed in an equivalent form using at least one even coefficient by taking $y_{i_1}, y_{i_2}$ such that $y_{i_1} a_{i_1} = y_{i_2} a_{i_2}$ where $y_{i_1}$ and $y_{i_2}$ are not both even (by canceling factors of $2$ as necessary) and then adding this expression to the all-odd-coefficients expression. (Again, credit to CatalystOfNostalgia above.)

$i=j$ on condition $b$ implies $0\in S$, and condition c implies $y\in S\implies -y\in S$

Use the Euclidean Algorithm (which works because condition b) on $a_1, a_2$ to get that $\gcd(a_1,a_2)\in S$, and then use Euclidean Algorithm on $\gcd(a_1, a_2)$ and $a_3$ to get $\gcd(a_1, a_2, a_3)\in S$, and continue this until we run through all of $a_i$, and get that $\gcd(a_1, a_2, a_3,\dots, a_n)=1\in S$. This means $-1\in S$.

Now, we prove inductively (on absolute value) that all integers are in the set. The base case is true, because we proved 0, 1, -1 are in the set.

Assume for some $n$, all integers with absolute value less than $n$ are in $S$. Then, $n\in S$ because $-1, n-1, n-2\in S$ and we just plug in $x=n-1$, $y=-1$ into condition c. This also implies $-n\in S$, which means the induction is complete and $S=\mathbb{Z}$

i have a solution using strong induction but i cant write it properly in here bc i dont know latex :( but i can give hints if anyone is interested :)

ok i kinda learned latex and im writing my solution , first we induct on n for base $n=2$ is trivial so lest just say we want to solve it with $n$ knowing that $n-1$ is correct since at least 1 of $a_i$ is not even we say like $a_n$ is odd now by induction if we say $GCD(a_2 , a_3 , ... , a_n) = d$ we know that we have every number $x$ in $S$ such that $d|x$ now we have that $a_1 - a_i$ is in $S$ and we have that  $m a_1 - n a_i$ is in $S$ for for integer $m,n$ now we know that $m a_1 - n a_2$ and $(d-m)a_1 - t a_3 $ is in $S$ and since the difference is devided by $d$ we have that $(2m-d)a_1 - na_2 - ta_3$ is in $S$ we can say with induct that $[2^i m - (2^i -1)d]a_1 -(W)$ such that $i=n-2$ and $W$ is a linear combination of $a_2 , a_3 , ... , a_n$ hence we can just say $W=dk$ for an integer $k$ so we have $ 2^i a_1 - dk$ is in $S$  and since $a_n$ was odd so $d$ cant be even so we have $ GCD(2^i a_1,d)=1$ so there exists a linear combination of these 2 such that $2^i a_1 x + dy =1$ so we have that $T 2^i a_1 x + Tdy = T$ is in $S$ for any integer $T$ so we have that all integers are in $S$
so we  are done :)

Call the sequence $\{a_1,a_2,\dots a_n \}$ an "[i]ancestral sequence[/i]" of $S$
Let $Q(a_i,a_j)$ and  $P(x,y)$ denote the second and the third conditions respectively

First, some basic remarks :-
1. $Q(a_i,a_i) \implies 0 \in S$
2.$P(0,x) \implies x\in S \implies -x \in S $
3.$P(x,y),P(x,-y) \implies x+y \in S   \iff   x-y \in S $

[color=#f00][b][u]CLAIM[/u][/b][/color] : $2a_i-a_j \in S$
[color=#222][b][i]Proof[/i][/b][/color] : $P(a_j-a_i,a_i) \implies a_j-2a_i \in S \implies 2a_i-a_j \in S$

[color=#f00][u][b]CLAIM[/b][/u][/color]: If $\{x_1,x_2, \dots ,x_n \} $  is an ancestral sequence of $S$  , then so is the sequence $\{x_1,x_2-x_1, \dots ,x_n-x_1\}$

[b][color=#000][u][i]Proof[/i][/color][/b]: This follows from the previous claim due to the fact that gcd of the numbers remains unchanged in the algorithm (say , by the Euclidean algorithm)

Now assuming WLOG that $|a_1|$ is minimal , if we repeat the algorithm,  we will eventually reach a stage when $a_1=0$ . We can then repeat the algorithm for the next $n-1$ numbers.  Hence we will eventually reach the sequence
$$\{ \underbrace{0,0,\dots,0}_{n-1 \text{ zeroes}},1 \}$$

So $1,-1 \in S$ . Now we can use strong induction based on the fact that
$n-1 \in S \implies n+1 \in S$ (this is the 3rd basic remark) and also the second basic remark ensures that we can focus on only naturals

Hence , done

This is a pretty cool problem and definitely one that requires great care.
[hide=Solution]We shall prove that for all $b_1,..,b_n \in \mathbb{Z}$, $b_1a_1+...+b_na_n \in S$. \\
We shall prove this for one and two $a_i,a_j$ and then induct. \\
$\textbf{Lemma 1:}$ If $a \in S$ then $ka \in S$ for all $k \in \mathbb{Z}$ \\
$\textbf{Proof)}$ \\
Firstly, notice that $a_i-a_i = 0 \in S$. Then if $a \in S$, $a+0 \in S$ gives us that $-a \in S$ as well. \\
We shall therefore prove that $ka \in S$ for all $k \in \mathbb{N}$. \\
Assume this is the case for all $k \geq t \geq 1$, then $ka \in S$, $-a \in S$, $ka-a = (k-1)a \in S$ means that $ka-(-a) = (k+1)a \in S$ and we get the desired result by induction. $\square$ \\
Even though the following argument is unnecessary, it is slightly different from a "normal inductive step" and I will consequently present it. \\
$\textbf{Lemma 2:}$ $ka_i+la_j \in S$ for all $k,l \in \mathbb{Z}$ \\
$\textbf{Proof)}$ \\
We shall firstly prove that $a_i-ka_j \in S$ for each $k \in \mathbb{N}$. \\
Notice that $a_i - a_j \in S$ and assume that $a_i-a_j \in S$ for all $k \geq t \geq 1$. \\
Then $a_i-ka_j \in S$, $a_j \in S$, $a_i-ka_j+a_j =a_i-(k-1)a_j \in S$ means that $a_i-(k+1)a_j \in S$. Then by Bezout's Theorem $gcd(a_i,a_j) \in S$ and we get by $\textbf{Lemma 1}$ that $ka_i+la_j \in S$ for all $k,l \in \mathbb{Z}$. $\square$ \\
$\textbf{Lemma 3:}$ For all $b_1,..,b_n \in \mathbb{Z}$, $b_1a_1+...+b_na_n \in S$ \\
$\textbf{Proof)}$ \\
Notice that the claim holds for any single or pair of $a_i$'s (this is by $\textbf{Lemma 2}$) \\
We shall induct assuming that the claim is true for any $t$-tuple of them where $t \in \{1,..,k\}$ and $a_1$ is contained in these $t$-tuples where without loss of generality we assume $2 \nmid a_1$. \\
$\textbf{Inductive Step:}$ \\
We shall reindex if necessary in the following argument. \\
We know that $$A=b_1a_1+2b_2a_2+...+2b_{k-1}a_{k-1}+b_ka_k \in S$$ $$B= b_2a_2+...+b_{k-1}a_{k-1}+b_{k+1}a_{k+1}-b_ka_k \in S$$
$$A+B = b_1a_1+3b_2a_2+...+3b_{k-1}a_{k-1}-b_{k+1}a_{k+1} \in S$$
Therefore $$A-B = b_1a_1+b_2a_2+...+b_{k-1}a_{k-1}+2b_ka_k-b_{k+1}a_{k+1}$$
Once again using Bezout's Theorem we have that $b_k2a_k+kgcd(a_1,..,a_{k-1},a_{k+1} \in S$ and therefore $gcd(2a_k,gcd(a_1,..,a_{k+1})) = gcd(a_1,..,a_{k+1}) \in S$ as $gcd(2,gcd(a_1,..,a_k)) = 1$ because we made sure that $2 \nmid a_1$. \\
We are thus done with the inductive step as long as we ensure that $a_1$ is in the set of integers on which we induct and ultimately means that if we apply the conclusion following the induction for all of the $n$ integers, we have that $kgcd(a_1,a_2,...,a_n) \in S$ by Bezout which means that $S$ must contain all integers as $gcd(a_1,...,a_n) = 1$. $\blacksquare$
[/hide]
[hide=Motivational Remarks]
So routinely, one figures out that all multiplies of any element in $S$ is also in $S$, moreover, using $a_i-a_j \in S$ one can also figure out that for any $i,j \in \{1,..,n\}$, one can prove that any linear combination of $a_i,a_j$ is also in $S$. After these two steps, it is natural to try and prove that the linear combination of any three is in the set, one can easily prove that $b_1a_1+b_2a_2+2b_3a_3$ is in the set for any $b_1,b_2,b_3 \in \mathbb{Z}$ and consequently, imposing the condition that $2 \nmid a_1$ ensures that we get any linear combination of $a_1,a_2,a_3$ lying in $S$. The rest is once again routine induction to finish off the problem using Bezout.[/hide]

[hide]First note that we have $0$. Let the assertion in (c) be denoted as $P(x,y)$.

[b]Claim 1:[/b] If $x$ is in the set, we have $-x$.

[b]Proof:[/b] $P(0,x)$.

[b]Claim 2:[/b] If $x$ is in the set, we can form any multiple of $x$.

[b]Proof:[/b] By Claim 1, we can form $-x$, and note that we already have $0$. Now we proceed by induction and show that if we have $ix$ and $-ix$ ($i$ is a positive integer), we can form $(i+1)x$ and $-(i+1)x$ (we have proved the base case $i=1$): $P(-ix,x)$ allows us to form $-(i+1)x$ and by Claim 1, we can form $(i+1)x$.

[b]Claim 3:[/b] We can form any number in the form $b_1a_{i}+b_2a_{j}$ if we have a number in the form $b_1a_i-a_j$ for integers $b_i$.

[b]Proof:[/b]: Note that we have $b_1a_i-a_j$. Then we proceed with induction to prove we can form $b_1a_i-ka_j$ with the base case $k=1$ being proven: We have $P(b_1a_i-(k-1)a_j,a_j)$ gives $b_1a_i-ka_j$ for $k \geq 2$. Now by Claim 1, we can form $ka_j-b_1a_i$, so for $k \leq 1$, we have $P(a_j,ka_j-b_1a_i)$ gives $b_1a_i-(k-1)a_j$.

[b]Claim 4:[/b] We can form any number in the form $b_1a_{i}+b_2a_{j}$ for integers $b_i$.

[b]Proof:[/b] Note that we have $a_i-a_j$. Apply Claim 3 here, and we get we can form any number in the form $a_i-b_2a_j$. Now we can form $b_2a_j-a_i$ by Claim 1. Then reapplying Claim 3 gives that we can form $b_2a_j+b_1a_i$.

[b]Claim 5:[/b] We can form any number that can be written as $b_1a_{i_1}+b_2a_{i_2} \dots +b_ka_{i_k}$ where at least one of the $b_i$ is even.

[b]Proof:[/b] We proceed with induction on $k$, with the base cases $k=1,2$ already having been proven. Now WLOG let $b_i \neq 0$ and $b_1=2x$. Then if some $b_i,i>1$ is even, WLOG $b_2$, doing $P(xa_{i_1} +(b_2-2)a_{i_2} \dots +b_{k-1}a_{i_{k-1}},-xa_{i_1}-2a_{i_2}-b_ka_{i_k})$ finishes as we have those two values, and their sum, is in $S$ because of induction (all three have fewer than $k$ terms).
Now if all $b_i,i>1$ is odd, then we can do $P(xa_{i_1} +(b_2-1)a_{i_2} +(b_3-2)a_{i_3}\dots +b_{k-1}a_{i_{k-1}},-xa_{i_1}-a_{i_2}-2a_{i_3}-b_ka_{i_k})$ which works for the same reason.

[b]Claim 6:[/b] We can always form $1$.

[b]Proof: [/b]Now consider some set of values $b_1,b_2...b_n$ that satisfy $\sum_{i=1}^{n} b_ia_i=1$. Now if one of $b_i$ is even, we can form $1$. Otherwise, all $b_i$ are odd. Now there must exist some odd $a_i$ as the sum is not even, and WLOG let it be $a_1$. Then $(b_1+a_2)a_1+(b_2-a_1)a_2+\sum_{i=3}^{n}b_ia_i=1$ and since $b_2-a_1$ is even, we can form this expression. Thus, we can always form $1$.

By Claim 6, we can form $1$, and by Claim 2, we are done. [/hide]

[hide=Solution]
We claim that if $x\in S$, then $kx\in S$ for all integers $k$. We will prove this using induction.

Base Cases: $k=0$, $k=1$
We have $a_1-a_1=0\in S$ and $x\in S$.

Inductive Step:
Suppose that $(k-1)x\in S$ and $(k-2)x\in S$. Since $0,x\in S$, we get $-x\in S$. Therefore, we get $kx\in S$.

Now, $kx\in S$ for all positive integers $k$, so $-kx\in S$ for all positive integers $k$, which means $kx\in S$ for all integers $k$.

We will show by induction that any linear combination of $i$ of the $a_j$ is in $S$.

Base Cases: $i=1$, $i=2$
We have already proven the case $i=1$. Since $a_1-a_2\in S$ and $a_1\in S$, this means that $a_1+b_2a_2\in S$. Similarly, since $ka_2\in S$, we get $b_1a_1+b_2a_2\in S$.

Inductive Step:
By dividing each $a_j$ by $\gcd(a_1,a_2,\ldots,a_i)$, it suffices to prove this when $\gcd(a_1,a_2,\ldots,a_i)=1$. Assume without loss of generality $a_1$ is odd. By the inductive hypothesis, we have $b_2a_2+\ldots+b_{i-1}a_{i-1}+b_ia_i\in S$. Since $-b_1a_1-b_ia_i\in S$, we get $b_1a_1+b_2a_2+\ldots+b_{i-1}a_{i-1}+2b_ia_i\in S$. Then, we have $b_1a_1+\ldots+b_{i-1}a_{i-1}+2b_ia_i=(b_1+b_i)a_1+b_2a_2+\ldots+b_{i-1}a_{i-1}+(2b_i-a_1)a_i\in S$. Therefore, this means that every linear combination of $i$ numbers is in $S$.

Therefore, since $\gcd(a_1,a_2,\ldots,a_n)=1$, this means that $1\in S$, so every integer is in $S$.

Fix $n$. We use strong induction on $\mu = |a_1| + |a_2| + \cdots + |a_n|$. $i=j$ in (b) gives $0 \in S$ and $x=0$ in (c) gives $-y \in S$ whenever $y \in S$. In general, if $y \in S$, then an easy induction (on $k$) gives $ky \in S ~ \forall ~ k \in \mathbb Z$. This resolves all the cases when some $a_i$ equals $1$. In particular, this resolves all base cases of $\mu \le n$. Now we do the inductive step. Assume $\mu > n$. Note $a_i,-a_j \in S$ and $a_i - a_j \in S$ implies $a_i + a_j \in S$. So we may change negative $a_i$'s to $-a_i$, so that all $a_i$'s are non-negative (this preserves all conditions and doesn't increase $\mu$). WLOG $a_1$ be the smallest [b]non-zero[/b] $a_i$ and $a_n = \max(a_1,\ldots,a_n)$. Note $a_1 \ne a_n$, as otherwise all positive $a_i$'s are equal, and $\gcd$ condition would force all of them to equal $1$, contradicting $\mu > n$. Now change $a_n \to a_n - 2a_1$. This easily preserves $\gcd$ condition. Also, $x=-a_1,y=a_1 - a_n$ gives $a_n - 2a_1 \in S$. So (a) is also preserved. (c) is preserved by definition. It suffices to show $(b)$ is preserved. So we want to show $a_n - 2a_1 - a_j \in S$. Just take $x=a_n - a_1, y = a_i + a_j$. Lastly, as this decreases $\mu$, so we are done by induction hypothesis. $\blacksquare$

We will show that any linear combination of the $a_i$ is in $S$, so $S=\mathbb{Z}$ by Bezout's Lemma.
First note that $a_1-a_1=0 \in S$, so for any $x \in S$, we have $0,x,0+x \in S \implies -x \in S$. I will now prove the following preliminary claim:

[b][color=#00f]Claim:[/color][/b] $ca_i+da_j \in S$ for all $c,d \in \mathbb{Z}$.
[color=#00f]Proof:[/color] This follows by strong induction. I don't feel like writing out the details.

To extend this to any number of elements, we will use strong induction again. I will first prove that for $m \geq 3$ indices $i_1,\ldots,i_m$, $c_1a_{i_1}+\cdots+c_ma_{i_m} \in S$ by strong induction (the base case has already been proven). I will first prove it in the case that one of $c_1,\ldots,c_m$ is even. WLOG let $i_1=1,\ldots,i_m=m$, and $c_1$ even. Then,
\begin{align*}
\frac{1}{2}c_1a_1+\sum_{i=3}^m c_ia_i &\in S\\
-\frac{1}{2}c_1a_1-c_2a_2 &\in S\\
-c_2a_2+\sum_{i=3}^m c_ia_i &\in S\\
\implies c_1a_1+\sum_{i=3}^m c_ia_i+c_2a_2=\sum_{i=1}^m c_ia_i &\in S.
\end{align*}
Note that the first expression has $m-1$ terms, the second $2$, and the third $m-1$.
To extend to all odd indices, "un-WLOG" everything and pick $1 \leq x<y \leq m$ such that $x \neq y$. Let $p,q$ be the minimal positive integers such that $pc_x=qc_y$, so $p,q$ are not both even. Then if $p,q$ are both odd let $c_x,c_y$ be arbitrary evens and the rest odds, so
$$c_1a_{i_1}+\cdots+c_xa_{i_x}+\cdots+c_ya_{i_y}+\cdots+c_ma_{i_m}=c_1a_{i-1}+\cdots+(c_x-p)a_{i_x}+\cdots+(c_y+q)a_{i_y}+\cdots+c_ma_{i_m} \in S$$
and since we can pick everything arbitrarily it follows that all choices of $c_i$ all odd work as well. The case where one is even (WLOG $p$) and the other odd is similar, where we let $c_y$ be even and $c_x$ odd. This completes the induction, so we're done. $\blacksquare$

I'm a bit surprised that no one has pointed out the similarity between this and 2012 N1 yet.  :)

Sketches are sketchy:

Note that picking $i=j$ for criteria $(b)$ shows that $0\in S$. Now, if $i\in S$ then set $x=0,y=i$ for criteria $(c)$ to get that $-i\in S$. If $y\in S$ then $-y\in S$, so $x+(-y)\in S\implies x-(-y)=x+y\in S.$
\\$~$\\
Now, since $x-x\in S$, $x+x\in S$ and by induction $kx\in S$ for all $x\in S$ and $k\in \mathbb Z$. Now, if $x-y\in S$ then from similar logic $kx-y\in S$ and so $kx+ly\in S$ by induction.
\\$~$\\
Since $a_1,a_2,\dots, a_n$ are coprime, there exist numbers $b_1,\dots, b_n$ such that $b_1a_1+b_2a_2+\dots + b_na_n=x$ for each $x\in \mathbb Z.$ From similar logic as above, we can get $b_1a_1+b_2a_2+\dots + b_na_n=x.$ Thus, we are done.

First, get some easy stuff out of the way. Part (b) with $i = j$ tells us $0 \in S$. Setting $y = 0$ in part (c) tells us that $x \in S \Longrightarrow -x \in S$.

The central claim of this problem is

[b]Claim:[/b] Linear combinations of the form
$$c_1a_1 + c_2a_2 + \cdots + c_na_n$$
can be achieved [b]if at least $n - 2$ of the $c_i$'s are even.[/b]

[i]Proof:[/i] We can induct on $n$.

The base case is showing that $c_1a_1 + c_2a_2$ can be achieved for any $c_1, c_2$. We will now do an inner induction on $M = |c_1| + |c_2|$. The base case of $M = 0$ and $M = 1$ were handled earlier. Consider targeting $(c_1, c_2)$ where $|c_1| + |c_2| = M$, with $c_1 \ge 1$. Then, we know
$$(c_1 - 1)a_1 + c_2 a_2 \in S \qquad a_1 \in S \qquad (c_1 - 2)a_1 + c_2a_2 \in S$$
because $|c_1 - 2| < |c_1|$ due to $c_1 \ge 1$ assumption. So, using (c), we get $c_1a_1 + c_2a_2 \in S$, for $c_1 \ge 1$.

We can cover the $c_1 \le -1$ case by using the fact $x \in S \Longrightarrow -x \in S$. And, if $c_1 = 0$, replicate the proof but replace $c_1$ with $c_2$.

Note that while we proved $c_1a_1 + c_2a_2 \in S$, we can generalize this proof to show $c_ia_i + c_ja_j \in S$ for any $i, j$.

So the base case for the induction on $n$ is handled. Let's now suppose $c_{i_1}a_{i_1} + \cdots + c_{i_{k-1}}a_{i_{k-1}}$ can be achieved at least $k - 3$ of the $c$'s are even. Let us try to achieve $c_1a_1 + c_2a_2 + \cdots + c_ka_k$ where $c_3$ through $c_k$ are even. We can get the following
\begin{align*}
x &= c_2a_2 + \cdots + c_{k-1}a_{k-1} + \frac{c_k}{2}a_k \\
y &= c_1a_1 + \frac{c_k}{2} a_k \\
x - y &= -c_1a_1 + c_2a_2 + \cdots + c_{k-1}a_{k-1}
\end{align*}
we know that $x \in S$ by induction, because $c_3$ through $c_{k-1}$ are even. We know $y \in S$ by our base case earlier for $n = 2$. And, we know $x - y \in S$ again by induction. Therefore, $x + y \in S$, meaning $c_1a_1 + \cdots + c_ka_k \in S$, as desired. $\Box$

Now it remains to show a generalized version of Bezout's, where if $a_1$ through $a_n$ are relatively prime, $c_1a_1 + \cdots  + c_na_n$ can hit all positive integers $n$ with at least $n - 2$ of the $c_i$'s even.

Let $z$ be any positive integer. By Bezout's we know that there exists some $d_1$ through $d_n$ such that
$$d_1a_1 + d_2a_2 + \cdots + d_na_n = z$$
where some of these $d_i$ might be odd. Let's say $a_1$ is odd, WLOG. For each odd $d_i$, we can replace $d_i$ with
$$(d_1 + a_i)a_1 + d_2a_2 + \cdots + (d_i - a_1)a_i + \cdots + d_na_n$$
which means for any $i \neq 1$, we can make $d_i$ even. So there exists a linear combination of $a_i$ that achieves $z$ with at least $n - 1$ even coefficients. This is certainly better than $n - 2$.

[i]Remark:[/i] If we think about just the coefficients $c_1$ through $c_n$ without semantically considering that $a_1$ through $a_n$ are numbers (i.e., just treating $a_1,\ldots, a_n$ as "symbols"), then we can actually show that the coefficients that are achievable [b]must[/b] have at least $n - 2$ evens. The reasoning is simple. By rules (a) and (b), everything there has at least $n - 2$ even coefficients, namely $0$. In part (c), if you were somehow able to get $x - y$ to be some expression with less than $n - 2$ evens, then $x + y$ itself must have already had less than $n - 2$ evens. A classic infinite descent.

This means that solutions that claim to be able to generate all linear combinations of $a_1$ through $a_n$ wouldn't be correct [i]unless[/i] they take into account the semantic information that $a_i$ themselves are actually integers with some value.

Proceed by induction.

I claim that for any $x, y \in {a_i}$ we can obtain the multiples of $\gcd(x,y)$. However this might require rewriting some of the rules here.

Observe that $0$ is always in $S$. Therefore if $x$ is in $S$, so is $-x$. Henceforth focus on positive integers only, so condition (c) rewrites to two conditions:

(c1) For any integers $x, y \in S$, if $x+y \in S$ then $|x-y| \in S$.
(c2) For any integers $x, y \in S$, if $|x-y| \in S$ then $x+y \in S$.

Now condition $b$ gives us a starting point to work with; consider the starting integers $x$ and $y$, and assume WLOG $x > y$. Observe that $x-y \in S$ and that $x-y + y \in S$. Therefore we can just take their non-negative difference and then the process repeats again. However this is precisely the Euclidean Algorithm so we end up with $\gcd(x,y) \in S$.

From here it is not hard to show that if $K$ is in $S$, then $nK$ is as well. Simply note that $K - K \in S$ and induct. Thus the claim is proven.

Bring back negative integers to make things easy again. Now suppose that for any $n \ge 2$ integers $a_1, a_2, \cdots a_n$ we can obtain their GCD. I claim that for $n+1$ we can do the same.

WLOG we can assume that the GCD of the $n+1$ integers is $1$ (but not the $n$ integers.) Now, for every subset of $n$ integers of the set of $n+1$ integers, we can obtain the multiples of their GCDs. Now observe that pairwise these GCDs must be relatively prime, as otherwise the whole set would have a GCD greater than one. Therefore pick three of these, say $A$, $B$, and $C$.

Now observe that $A+Bx=Cy$ has a solution in integers with $\gcd(Bx,A)=1$ by simply taking $\pmod{A}$. Thus we find two integers where the Euclidean Algorithm can be performed (a la proof of $n=2$) to get $1 \in S$, and from there the rest is trivial.

Does this work? I wrote it up sloppily; took me 10 minutes so im not sure why this would be 20 mohs if i solved it that quickly

    Use an algorithm as follows:
    From c) we have $a_i-a_j,a_j,a_i\in S\rightarrow a_i-2a_j\rightarrow a_i-ka_j,a_j;a_i-{k-1}a_j\in S\rightarrow a_i-(k+1)a_j\in S;a_i-ka_j,a_i-(k+m)a_j,a_i-(2k+2)a_j\in S\rightarrow ma_j\in S;a_i-a_j,a_k-a_i,a_k-a_j\in S\rightarrow 2a_i-a_j-a_k\in S$ and this easily generalizes to any linear combination of the variables; by Bezout's, we're done.

Its easy to see that $a_i + ka_j \in S$ and then $k_1a_i + k_2a_j \in S$. We use induction.

Assume $$k_2a_2 + k_3a_3\dots k_{c}a_{c}, k_1a_{1} + k_2a_{2}\dots +k_{c-1}a_{c-1} \in S$$ Then since $k_1a_1 - k_ca_c\in S$, we have $$-k_1a_1 + k_2a_2 + k_3a_3+\dots +2k_{c}a_{c} \in S.$$

This induction can reach all sums such that at most $n-1$ summands have even coefficents. Since there must exist an odd element, we should chose the sum so the $n-1$ other elements are all even coefficents. Then we can write this as $$k_1a_1 + \frac{k_2}{2^{d_2}} (a_2 \cdot 2^{d_2}) + \frac{k_3}{2^{d_3}} (a_3 \cdot 2^{d_3})\dots,$$ where $k_1$ is odd and $d_i \leq v_2(k_i)$. Now by bezout, since $\frac{k_i}{2^{d_i}}$ can range over $\mathbb{Z}$ and since $\gcd(a_1, a_2 \cdot 2^{d_2}, a_3 \cdot 2^{d_3} \dots) = 1$ we have $S=\mathbb{Z}$.

[b][color=pink]Claim:[/color][/b] $0 \in S$, and $a \in S \iff -a \in S$.
[i]Proof.[/i] The first result follows by setting $i = j$. Then taking $x = 0$, $y = a$ for (c) gives the second result. $\blacksquare$
It follows that $a_i + a_j \in S$.

[b][color=pink]Claim:[/color][/b] We can inductively get $c_1 a_{i_1} + c_2 a_{i_2} + \dots + c_n a_{i_n} \in S$
[i]Proof.[/i] This follows immediately for $n = 1$ as since if $ka, (k+1)a \in S$ then $(k+2)a \in S$.
Then since $a_i + a_j \in S$, taking $x = c_1 a_i + c_2 a_j \in S$ for $c_1, c_2 \ge 1$ and $y = a_i$ gives $(c_1+1) a_i + c_2 a_j \in S$.
Repeating this gives that $c_1 a_i + c_2 a_j \in S$ for all nonnegative $c_1, c_2$. To construct general $c_1, c_2$, we can subtract $x = (N + c_i)a_i + (N + c_j)a_j$ and $y = Na_i + Na_j$ for $N \ge |\max\{c_i, c_j\}|$.
Now, suppose that this holds for $n \ge 2$. Then $((c_1+1) a_{i_1} + c_2 a_{i_2} + \dots + c_n a_{i_n}) - (c_1 a_{i_1} - c_{n+1} a_{i_{n+1}}) \in S$. $\blacksquare$
Since $\gcd(a_1, a_2, \dots, a_n) = 1$, any integer can be expressed as a linear combination as desired.

A solution without using induction and without using bezout :blush:
[hide]Let's assume the problem is not true for ($a_1, ..., a_n$) = ($x_1, x_2, ..., x_n$) $\rightarrow gcd(|x_1|, |x_2|, ..., |x_n|)=1$
By (b): $0 \in S \rightarrow \forall x \in S$ we have $0+x = x \in S$, so by (c): $0-x=-x \in S$
$\forall x_i, x_j \in S, x_i + (-x_j) = x_i - x_j \in S$, so by (c): $x_i + x_j \in S$, so we cloncude that $\pm x_i \pm x_j \in S$
Then, the condictions $gcd(a_1, ..., a_n)=1$, (a), (b), and (c) are true for ($a_1, ..., a_n$) = ($|x_1|, |x_2|, ..., |x_n|$), so if the problem would be true for ($a_1, ..., a_n$) = ($|x_1|, |x_2|, ..., |x_n|$), the problem would be true for ($a_1, ..., a_n$) = ($x_1, x_2, ..., x_n$), which is not true
If $|x_1| = |x_2| = ... = |x_n| = 0$ then $gcd(|x_1|, |x_2|, ..., |x_n|)$ isn't equal to $1$, which is not true ... (d)
WLOG asumme that ($|x_1|, |x_2|, ..., |x_n|$) is the set of non-negative numbers for which the problem isn't true with the minimun sum ...(e)
WLOG $|x_1| \geq |x_2| \geq  ... \geq |x_k| > 0 = |x_{k+1}| = |x_{k+2}| = ...= |x_n|$, $k$ could be equal to $n$, but anyways k exist by (d)
Then, since the problem isn't true for ($a_1, ..., a_n$) = ($|x_1|, |x_2|, ..., |x_n|$), the problem isn't true for ($a_1, ..., a_n$) = ($|x_1|, |x_2|, ..., |x_k|$)
Also, by (b): $|x_k|, |x_1| - |x_k|, |x_2| - |x_k|, ..., |x_{k-1}| - |x_k| \in S$ and we have:
$(|x_i| - |x_k|) - (|x_j| - |x_k|) =|x_i| - |x_j| \in S$, and $|x_i| - |x_k| + |x_k| = |x_i| \in S$, so by (c): $|x_i| - |x_k| - |x_k| \in S$, so they satisfy (b)
Also, since $gcd(|x_1|, |x_2|, ..., |x_k|)=1 \rightarrow gcd(|x_k|, |x_1| - |x_k|, |x_2| - |x_k|, ..., |x_{k-1} - |x_k||)=1$
Finally, the conditions $gcd(a_1, ..., a_n)=1$, (a), (b), and (c) works for $(|x_k|, |x_1| - |x_k|, |x_2| - |x_k|, ..., |x_{k-1}| - |x_k|)$, so if the problem would be true for ($a_1, ..., a_n$) = $(|x_k|, |x_1| - |x_k|, |x_2| - |x_k|, ..., |x_{k-1}| - |x_k|)$, the problem would be true for ($a_1, ..., a_n$) = ($|x_1|, |x_2|, ..., |x_k|$), which is not true
So, by (e): $|x_k| + |x_1| - |x_k| + |x_2| - |x_k| + ...+ |x_{k-1}| - |x_k| = |x_1| + |x_2| + ... + |x_k| - (k-1)|x_k| \geq |x_1| + |x_2| + ... + |x_k| \rightarrow 0 \geq (k-1)|x_k|$
Since $|x_k| > 0 \rightarrow 0 \geq k-1 \rightarrow 1 \geq k \rightarrow k=1$
Then $1=gcd(|x_k|, |x_1| - |x_k|, |x_2| - |x_k|, ..., |x_{k-1} - |x_k||)=x_k$, but the problem is actually true for ($a_1, ..., a_n$) = {1}, contradiction $\blacksquare$[/hide]

Notice that $0 \in S$, so inductively $na_i \in S$ for any $n \in \mathbb Z$.

Now I show inductively that any linear combination of $k \leq n$ of the $a_i$ [i]with at least one coefficient even[/i] is in $S$. For the base case $k = 2$, note that $a_i + a_j \in S$, which implies that $d_1a_i + a_j$ and $d_1a_i$ are both in $S$ for any $d_1$. These two conditions imply $d_1 a_i + d_2a_j \in S$ for any $d_1, d_2$.

For the inductive step, WLOG the coefficient of $a_k$ is guaranteed to be even. Write $d_1a_1 + d_2a_2+ \cdots + d_ka_k \in S$, where $d_k$ is our even coefficient forced in the $k$-sum, and $d_ka_k + d_{k+1}a_{k+1} \in S$. So $$d_1a_1+d_2a_2+\cdots+d_{k-1}a_{k-1}+2d_ka_k + d_{k+1}a_{k+1} \in S,$$ where the sum still covers all possible linear combinations. $\blacksquare$

Now, I claim that there exists a valid linear combination as described above that sums to $1$. There exists a term $a_i$ that is odd by the GCD condition; thus, fix some $j \neq i$ and consider all possible linear combinations with the coefficient of $a_j$ even. There exists an $n$-tuple $(c_1, c_2, \dots, c_n)$ such that $$c_1a_1+c_2a_2+\cdots+c_na_n = 1$$ by Bezout. If $c_j$ is even, we're done; if $c_j$ is odd, replace $c_j$ with $c_j + a_i$ and $c_i$ with $c_i - a_j$.

Thus, taking multiples of this $1 \in S$ yields $S = \mathbb Z$.

[quote=HoRI_DA_GRe8][quote=HamstPan] If $c_j$ is even, we're done; if $c_j$ is odd, replace $c_j$ with $c_j + a_i$ and $c_i$ with $c_i - a_j$.[/quote]

Can this argument be replaced by this argument ?
If $a_i$ is odd then consider $j \not = i$ So $\text{gcd}(a_1,a_2,\cdots 2a_j,\cdots,a_i,\cdots ,a_n)$ remains $1$ so by bezout we can find a linear combination $(c_1,c_2,\cdots,c_n)$ such that $c_1a_1+\cdots c_j2a_j+\cdots+c_ia_i+\cdots+c_na_n=1$ and we can easily reach it by your algorithm .[/quote]

Yes this makes it super simple, and it works too.

@HamstPan38825 It is my request to add this modification into your solution. Your solution is by far the best among the ones I have read but this modification makes it super simple to understand. I felt that the final line was a bit unmotivated but this addition makes it very instructive.

[quote=billzhao]Suppose $a_1, \dots, a_n$ are integers whose greatest common divisor is 1. Let $S$ be a set of integers with the following properties:

(a) For $i=1, \dots, n$, $a_i \in S$.
(b) For $i,j = 1, \dots, n$ (not necessarily distinct), $a_i - a_j \in S$.
(c) For any integers $x,y \in S$, if $x+y \in S$, then $x-y \in S$.

Prove that $S$ must be equal to the set of all integers.[/quote]

First of all we start of with an observation that $0 \in S$ which means that.\\

Claim 1: For all $a \in S $ we have that $-a \in S $.

    Since $0 \in S$ then by (c) as $0+a=a \in S$
    then $0-a=-a \in S$.

Claim 2: For any $a \in S $, then all of the multiples of $a$ are in $S$ as well.

    Suppose that $(k-1)a\in S$ and $(k-2)a\in S$. Since $0,a\in S$, we get $-a\in S$. Therefore, we get $ka\in S$

Claim 3: For any integers $d_1,d_2$ and $i,j$ we have that $d_1a_i+d_2a_j \in S$.

    Assume that $d_1,d_2$ are positive as it's similar if they are negative. Inductively if we have $d_1a_i+d_2a_j, a_j, d_1a_i+d_2a_j \in S$ then $d_1a_i+d_2a_j \in S$.

Now let's generalize Claim 3.\\

Claim 4: For any $d_1,d_2, \dots , d_n$ we have that $d_1a_1 + d_2a_2 + \dots + d_na_n \in S$

    We will proceed with induction, we proved the base case in Claim 2, Now assume for some $m$ our claim is true, namely.
    \[d_2a_2+ \dots + d_ma_m \in S\]
    Now assume WLOG $d_1 \neq 0$ is even then we have

   $$ x = \frac{1}{2} d_1 a_{1} + \sum_{k \ge 2} d_k a_{k} \in S.$$
  $$  y = -\frac{1}{2} d_1 a_{1} \in S $$
 $$   \implies x+y = \sum_{k \ge 2} d_k a_{k} \in S $$
   $$ \implies x-y = \sum_{k \ge 1} d_k a_{k} \in S.$$
But Now assume that all $d_i$ are either zero or odd then replace $d_1$,$d_2$ with the following.
\[(d_1+a_i)a_1+a_2+ \dots + (d_i-a_1)a_i+ \dots + a_n \]
Making at least one of them being even.

Now by Bezout lemma we have some linear coefficients such that.
\[d_1a_1+ \dots d_na_n=1\]
Since $gcd(a_1,a_2, \dots, a_n)=1$.
So this means that $1 \in S$, by \textbf{Claim 2} we have that all the multiples of $1$ are in $S$ as desired


quadratics
number theory
number theory unsolved

Please, prove

if $p\equiv 7 \mod (8)$ and prime number then
$\sum \limits_{j=1}^{\frac{p-1}{2}}\{\frac{j^{2}}{p}+\frac{1}{2}\}=\frac{p-1}{4}$

there, $\{x\}=x-[x]$.

hey!  Rust!
please tell me ,
how do you solve it ?

Let p is odd prime, V is number of quadratic residues $V=\# \{1\le x\le p/2 |x=y^{2}(mod p)\}$ and $N= \# \{p/2<x<p |x=y^{2}(mod p)\}$. We have $V+N=(p-1)/2$.
Then \[S=\sum_{j=1}^{(p-1)/2}\{\frac{x_{j}}{p}+\frac{1}{2}\}=\frac{1}{p}\sum_{j}x_{j}+\frac{V-N}{2},\]
were $x_{j}=j^{2}(mod p)$. If $p=1(mod 4)$ it is easy to get $V=N=\frac{p-1}{4}, \sum_{j}x_{j}=\frac{p(p-1)}{4}$, because for all $x_{j}$ exist $x_{l}$, suth that $x_{j}+x_{l}=p$.
Let $p=3(mod 4)$, then $A=\frac{1}{p}\sum_{1\le j<p/2}x_{j}=\frac{p-1}{4}-\frac{h}{2}$, were $h$ is number of classes (See Borevish, Shafarevich. Number theory ). Therefore $S=\frac{p-1}{4}+\frac{V-N-h}{2}$. But $V-N=h$ if $p=7(mod 8)$ and $V-N=3h$ if $p=3(mod 8 )$.
Therefore $S=\frac{p-1}{4}, p=1,5,7 (mod 8)$ and $S=\frac{p-1}{4}+h$ if $p=3(mod 8)$.

Thanks! Rust
but ,I don't understand;
have you better easy method?

rust, what do you mean by number of classes?

[url=http://www.mathlinks.ro/Forum/viewtopic.php?p=214544#p214544]here[/url] is a similar problem.


[quote="Jutaro"]How many positive integers not exceeding 1000 can be expressed as the sum of a positive multiple of 7 and a positive multiple of 4?[/quote]

We can see that every integer $n\ge 4*7+1=29$ can be expressed as $4a+7b ,\mbox{ integer } a>0, b>0$
(because every integer of $n-7, n-14, n-21, n-28$ is $>0$ end one of them is divisible by 4)

From 1 to 28 we have $\left( \left[\frac{28-7}{4}\right]+\left[\frac{28-14}{4}\right]+\left[\frac{28-21}{4}\right]\right)=$
$5+3+1=9 \Rightarrow$
Finally we have $1000-28+9=981$ such integers.

V:)

If $n\geq 21$, then one of numbers $n,n-7,n-14,n-21$ is divisible by 4 :arrow: $n$ can be expressed as the sum of a positive multiple of 7 and a positive multiple of 4.
It's easily to see, that from positive integer numbers, not exceeded $20$ only $4,7,8,11,12,14,15,16,18,19,20$ "is good".
Also we get $991$ "good" numbers.

Generally, there is the more common well-known and easily proved fact:
If $gcd(a,b)=1$, then equation $ax+by=ab-a-b$ hasn't solutions in nonnegative integers, bu if $c>ab-a-b$, then equation $ax+by=c$ always has solution in nonnegative integers $x,y$.

[quote="pavel kozlov"]Just a few minuts later.
And I don't find the word positive in condition  :arrow: I got wrong answer.[/quote]

What do you mean?


Do you know how I could do any of the following contests?

#  Fairfax County Math League (FCML)
# James Madison University Mathematics and Science Contest

And how I could get my younger siblings signed up for this contest?

"Intermediate Math Open -- Middle school competition hosted by TJHSST"

Also, are there any other math competitions that you recommend?

This is what I could find about the JMU contests:

http://www.jmu.edu/catalog/07/colleges/csm.html

See the end of the page.

Participation in TJ's Intermediate Math Open is via the middle schools in the TJ attendance area. A invitation is sent to each of these schools.  See:

http://activities.tjhsst.edu/vmt/pages/imo.phtml

The "IMO" is coming soon. It is usually in October.

FCML seems to be run by the Fairfax Co. Public Schools. I could not find a website.  I know that TJ students take it at TJHSST.

What age group(s) are you interested in?

"What age group(s) are you interested in?"
My younger siblings are in middle school.
I'm in ninth grade.

For your siblings:

MathCounts

TJ IMO if they are in Northern VA

Virginia Math League

AMC 8 or 10

To participate in the contests you mentioned, here are the general steps and information you'll need:

### Fairfax County Math League (FCML)

1. **Eligibility**: Typically, this contest is for high school students attending schools in Fairfax County.
2. **Registration**: Schools usually register their teams. Check with the math department at your school or the school's math club.
3. **Preparation**: Engage in regular practice sessions, often organized by math teachers or club advisors.

### James Madison University Mathematics and Science Contest

1. **Eligibility**: Open to high school students. The contest includes both individual and team competitions.
2. **Registration**: Similar to FCML, registration is generally done through schools. Contact your school’s math department.
3. **Preparation**: Review past contest problems and participate in mock contests if available.

### Intermediate Math Open – Middle School Competition Hosted by TJHSST

1. **Eligibility**: Aimed at middle school students.
2. **Registration**: This might involve individual registration. Check the Thomas Jefferson High School for Science and Technology (TJHSST) website or contact them for the most accurate and current information.
3. **Preparation**: Focus on foundational math concepts and problem-solving skills.

### Other Math Competitions to Consider

1. **MathCounts**: A popular middle school competition with both individual and team rounds.
2. **AMC 8/10/12 (American Mathematics Competitions)**: Suitable for middle and high school students, these contests lead to further competitions like the AIME and USAMO.
3. **Math Kangaroo**: An international competition for students from grades 1 to 12.
4. **International Mathematical Olympiad (IMO)**: For high school students, but requires progression through national qualifying rounds.

### Steps for Registration and Preparation

- **Contact School**: For most competitions, the first step is to contact your or your siblings' school. Teachers or club advisors can provide information on registration and preparation.
- **Official Websites**: Visit the competition websites for the most accurate information regarding registration deadlines, fees, and preparation resources.
- **Preparation Resources**: Utilize past problems, online resources, and math clubs for practice. Many competitions also offer study materials and practice tests.

Remember, participation in these contests is not only about winning but also about developing problem-solving skills, fostering a love for mathematics, and gaining valuable experience.


function
limit
calculus
derivative
calculus computations

consider a function $ f$ defined from $ R$ to $ R$ by $ f(x)\equal{}x^n\plus{}c_{n\minus{}1}x^{n\minus{}1}\plus{}....c_1x\plus{}c_0$, where $ c_0,....c_{n\minus{}1}$ are reals numbers.
prove there exist $ A>0$ such that $ f$ is incresing in $ [A,\plus{}00)$

Assume that no such A exists.
Since the $ \lim_{x\to\infty}f(x) \equal{} \infty$, for any value f(N), there exists another extrema for x>N.
Therefore, f(x) must have an infinite amount of relative extrema

By the first derivative test and the fundamental theorem of algebra, $ f(x)$ has at the most $ n\minus{}1$ relative extrema.
We reach a contradiction, since $ n\minus{}1$ is finite, so such an A exists.


Is sqrt(2) the limit of a sequence of numbers of the form n^(1/3)-m^(1/3) (n,m = 0,1,2,...)?


Write $ 39$ as sum of $ 6$ odd numbers!  :D

What?

$ 6 \cdot 1 \equiv 0 \not \equiv 1 \bmod 2$.

Yes thats it!:D thats why its a mystery:D think more...
actually the problem is this:
A wolf wants to kill $ 40$ sheep of a farm in $ 6$ days with this condition that it has to remain $ 1$ sheep in last day and he has to kill odd number of sheep in each day...! how can he do it?! :D

[hide="Possibly?"]
Since on the $ 6^{th}$ day he must kill $ 1$ sheep.
That leaves $ 5$ days to kill an odd number of sheep summing to $ 39$, one solution is $ 5 \ , \ 5 \ , \ 9 \ , \ 9 \ , \ 11$ or even distinct odd numbers $ 3 \ , \ 5 \ , \ 7 \ , \ 9 \ , \ 15$.[/hide]

actually if the problem was like this it would be really easy...! :wink:
It seems i've explained the problem not good enough... $ 1$ ship must remain alive in the $ 6^{th}$ day! and the wolf has to kill atleast $ 1$ ship each day...
How can he do it?!


Mafia
probability
conditional probability

I am a participant in a 13 player mafia game. There are 3 people on the town's side: me, and 2 other vigilantes. A vigilante is a player who is on the side of the town who can kill at night. The other 10 players are in mafia groups of 5 players each. A mafia group is evil, and each group can kill one person each night.

Last night, I died. I was only killed by one person or group. I was the only person who died last night. What is the probability that I was killed by a vigilante?

This problem might not be clear, so go ahead and ask questions if you want. I don't know the answer.

lol wut?

[hide]If each of the other 2 vigilantes can kill 1 person each night, and each of the mafia groups can kill 1, then the chance of being killed by a vigilante is $\frac12$[/hide]

If they are all Waldos,

[hide="answer:"]1/5[/hide]

The problem contradicts itself, you cannot have been the only one killed if you were only killed by one group last night.

[quote="t0rajir0u"]What assumptions are being made here?  We can't just assume that all players are playing perfect strategies since the players don't know a lot of information.  Are we assuming that vigilantes kill randomly, and mafia kill everyone except themselves?[/quote]
Vigilantes kill randomly, anyone but themself. Mafia can kill everyone except their own group. It doesn't contradict itself, it just means some groups didn't kill last night.

What's the probability that a group doesn't kill on a given night?

There's no probability that a group doesn't kill, we just know that 1 group killed, which means that 3 other groups/individuals chose not to kill.

[hide="What is the probability that you are trying to make this into a math question when it should not be one?"]1  :rotfl: [/hide]

All jokes aside

[hide="i think"]2/3 since 2 out of the 3 killers are vigilantes[/hide]

[hide]$\frac{1}{3}$. Extremely easy problem, should be in Classroom Math[/hide]

[quote="Ignite168"][quote="Klebian"][quote="Klebian"]So you're saying the size of a mafia group doesn't affect the probability of them killing me?[/quote]
And, I don't see how you're getting that answer.[/quote]

Nope, it doesn't. Equal probability of killing. Three groups = 1 out of 3.[/quote]

The mafia groups each have $8$ potential targets, but the vigilantes have $12$.  This means that the probability of a vigilante killing any particular person is lower, given an equal probability of mafia or vigilante killing.

So you did not kill yourself?

There are 5 groups, 3 vigilanties and 2 mafias. Without more informations it seems impossible to figure it out correctly.

[quote="t0rajir0u"][/quote][quote="Ignite168"][quote="Klebian"][quote="Klebian"]So you're saying the size of a mafia group doesn't affect the probability of them killing me?[/quote]
And, I don't see how you're getting that answer.[/quote]

Nope, it doesn't. Equal probability of killing. Three groups = 1 out of 3.[/quote][quote="t0rajir0u"]

The mafia groups each have $8$ potential targets, but the vigilantes have $12$.  This means that the probability of a vigilante killing any particular person is lower, given an equal probability of mafia or vigilante killing.[/quote]

[quote="Klebian"][quote="Ignite168"]Is there a equal probability they killed?[/quote]
yes[/quote]

And I meant $\frac{1}{2}$ because 2 groups out of 4.

However, we know from the problem that on this night, only one person/group did kill, and only one person was killed.

[quote="mathstudent1"][quote="Hamster1800"]Ok here goes

Each mafia group has 5 members and there are 2 vigilantes that might have killed. All 13 players are alive.

A vigilante has 12 targets while a mafia group has 8. Suppose that a mafia group killed. There is a probability of 1/8 that they chose you. Suppose a vigilante killed. There is a probabillity of 1/12 that they chose you. Therefore, there are $\frac 1{12}: \frac{1}{8}$ odds that a vigilante killed you meaning a probability of $\frac{\frac{1}{12}}{\frac1{12}+\frac18}$, which can (obviously) be simplified but I don't feel like it.[/quote]
but that assumes that only one person is killed per night and that only one group/person can kill per night.
somebody said before that many people can be killed in one night[/quote]

This is what makes conditional probability confusing. Each group has the same probability of killing, so we can assume there is a 1/4th probabilty that each group killed. However, each group has a different number of targets, so we have to account for those too. Assuming that my answer actually does simplify to $\frac25$, that should be the right answer.

[quote="Ihatepie"]the chance is 0 the problem says other vigilants so that means u r part of their group[/quote]
vigilantes kill anyone but themselves (so each vigilante is a different group of 1)

[quote="roadnottaken"][hide="tongue-in-cheek probability"]Either a vigilante killed you or a mafia member killed you.  Since one of these events already happened, the probability that a vigilante killed you is technically either $0$ or $1$. :P  :huh:  :roll:  :yankchain: [/hide]
Sorry, I thought something needed to be done to break the tension.[/quote]

Yes, that's true. Now what's the probability of the probability of being killed by a vigilante being $1$? :P

[hide="redundancy:  read at your own risk"]It is either $0$ or $1$. :yankchain: [/hide]
On a more serious note:  [quote][i]Hamster1800:[/i]  Ok here goes

Each mafia group has $5$ members and there are $2$ vigilantes that might have killed. All $13$ players are alive.

A vigilante has $12$ targets while a mafia group has $8$. Suppose that a mafia group killed. There is a probability of $\frac{1}{8}$ that they chose you. Suppose a vigilante killed. There is a probabillity of $\frac{1}{12}$ that they chose you. Therefore, there are $\frac{1}{12}: \frac{1}{8}$ odds that a vigilante killed you meaning a probability of $\frac{\frac{1}{12}}{\frac{1}{12}+\frac{1}{8}}$, which can (obviously) be simplified but I don't feel like it.[/quote]
[quote][i]roadnottaken:[/i]  It symplifies to $\frac{2}{5}$.[/quote]
More specifically, multiply the top and bottom of the fraction by $24$, and you end up with $\frac{2}{{2+3}}= \frac{2}{5}$.  Also, there are two mafia groups and two vigilante groups, but the twos cancel out, so we can treat the problem as if there is one group of each, not including the vigilante who was just killed.


Hockey Stick Identity Part 3

We investigate the number of ways to distribute dollar bills among four people.

If the people are p, and the money is m, wouldn't the number of ways be like we choose m things out of p+m-1 ? Sorry, I don't know LaTex, so I can't write it as a combination.


modular arithmetic
function
number theory

You obviously know what it means for "$ a$ to divide $ b$."  We write $ a\mid b$.  This is the same thing as saying that there is no remainder when $ b$ is divided by $ a$.

Now this is what you're probably used to seeing: $ a\equiv b \pmod c$.  This is really all just notation.  This means that $ c\mid (a\minus{}b)$, or that "$ c$ divides $ a\minus{}b$."  Alternatively, you can think of it as meaning that $ a/b$ yields remainder $ c$.

For an example, we can say that $ 7\equiv 5\pmod 2$.  Why?  Because $ 7\minus{}5\equal{}2$, which is divisible by 2.  Also $ 7/5\equal{}1$ with remainder 2.

This is just really basic stuff, as mods can be quite powerful for solving problems.

Thanks for you but in fact I also what "$ a$ to divide $ b$" mean or $ a\mid b$. Is it mean that there is no remainder for it? Please explain it a little bit. Thanks

$ a$ and $ b$ are completely arbitrary numbers.  However, it is not true that just because $ a$ divides $ b$, then $ b$ divides $ a$.  But if there is an even division, then there is no remainder.

If $ a\mid b$, then $ a\equiv 0\pmod b$, and $ b$ is an integer multiple of $ a$.

First of all I think my problem is that I didn't understand this $ a\mid b$ give a brief description for its function please  :( .

It's not a function, it's a notation.
$ a\mid b$ means that $ \frac{b}{a}$ has no remainder.

$ b\equiv 0\pmod a$ iff $ a\mid b$.

I see. Thanks a lot. Can you give me an example please just to make sure that I understand  :D .
And by the way what $ \equiv$ mean?

I just googled this page with modular arithmetic. It seems pretty fundamental (I don't think I saw the notation $ a|b|$ though) so this'll be a good site to read and do problems.

http://www.math.rutgers.edu/~erowland/modulararithmetic.html

Thanks a lot "JRav", "grn_trtle" and "Silverfalcon".  :)
I see the site its good and I understand a lot so far but I have a problem here in this example: $ 1a \plus{} 1 \equiv 0 \pmod 2$ it say it reduced to $ 0 \cdot  a \plus{} 1 \equiv 0 \pmod 2$ how this comes? how its reduced and why $ \pmod 2$ is it because we are looking for integers  :?:

Actually, it says $ a\plus{}1\equiv 0\pmod 2\implies a\equiv \minus{}1\equiv 1\pmod 2$.
In $ \bmod 2$, numbers "wrap around" so that $ \minus{}1$ is the same as $ 1$.
Another example would be $ \minus{}3\equiv 7\pmod {10}$ because you move $ 3$ backwards from $ 10$.
Think of a clock...

[quote="hasan4444"]I always see people write $ mod$ and I think its a part of the number theory but can someone explain it to me as easy as he can?

Thanks in advance[/quote]

Hasan,

I see a lot of people here have already given you good advice, so I'll just add a few things.

The concept of $ mod$ is part of number theory -- perhaps the most important part of number theory. The expression $ a\equiv b\pmod{m}$ is read, in English, as "$ a$ is congruent to $ b$, modulo $ m$."

That sentence means $ m|(a \minus{}b)$. (Further, that expression, $ m|(a \minus{}b)$, means $ m$ divides the difference between $ a$ and $ b$ exactly; that is with remainder zero.) The numbers $ a$, $ b$ and $ m$ are each integers. The number $ m$ is called the modulus of $ a$ and $ b$.

The theorem to remember in doing modular arithmetic is: $ a\equiv b\pmod{m}$ if and only if $ a$ and $ b$ have the same remainder upon division by $ m$.

For your example problem $ a \plus{} 1\equiv 0\pmod{2}$ means that $ a \plus{} 1$ is an even number.

This is because $ 2|(a \plus{} 1 \minus{} 0)$, meaning that $ 2$ divides the difference of $ a \plus{} 1$ and $ 0$ exactly. In this case the difference is equal to $ a \plus{} 1$ itself. Therefore, $ 2|(a \plus{} 1)$.

@hasan444 - Modular arithmetic is very important because it allows people to find the remainder of things like 3^1234  and 2^456 when divided by other numbers. It can also be used to prove divisibility formulas. For example, this is the proof that any number is divisible by three if and only if the sum of its digits are divisible by three.

Let's say we have a number $ xyzw$ where $ x$, $ y$, $ z$, and $ w$ are the digits. We can also write this as;

$ 1000x \plus{} 100y \plus{} 10z \plus{} w$
We can factor $ 1000$ into $ 10 X 10 X 10$, and $ 100$ into $ 10 X 10$ to get;
$ (10 X 10 X 10) X x  \plus{} (10 X 10) X y  \plus{} 10z \plus{} w$
When ten is divided by three you get a remainder of one, so;
$ (1 X 1 X 1) X x  \plus{} (1 X 1) X y \plus{} 1z \plus{} w$
The ones don't change anything about the product, so we get;
$ x \plus{} y \plus{} z \plus{} w$
So all that matters is if the sum of the digits is divisible by three.

The proofs for divisibility of $ 9$ and $ 11$ are very similar, but you should see if you can figure them out.

In fact I learn a lot from that site but I understand most of your example "Wickedestjr". Thanks for the very good explanation"Dr. No"  :) . I want to buy some AoPS textbooks but the hard thing here that the shipping money is even more expensive than the book  :rotfl: . I will try to buy some books in one time. Does anybody know if AoPS Introduction to Number Theory have some Modular Arithmetic also :?:

[url=http://www.artofproblemsolving.com/Books/AoPS_B_Item.php?item_id=206#excerpt]This[/url] is the page for that book.  If you look in the table of contents, you'll see that an introduction to modular arithmetic is covered starting in chapter 12.

You might also try Introduction to Number Theory.

@Wickedestjr: try \cdot or \times for a multiplication symbol instead of typing X, it's a lot prettier that way  :wink:

Oh yeah sorry hasan. The big $ X$ is supposed to be multiplication.


Does anyone know what I can do if I have a conflict (in this instance, State Solo/Ensemble Contest) with the USAMO? Is there an "alternate" date allowed?

Sorry to say this, but I doubt there is an alternate date allowed.  I would just skip whatever it is that's conflicting with USAMO  :blush: .

yea... it is a set date, set time i believe. I was scheduled to take the reading part of WASL (Washington Assessment of Student Learning - something like ITBS), but i have to skip that to later of the week... ;)

DEFINITELY no alternate date. The USAMO isn't exactly a normal math competition.

From the AMC website:
[quote]The USAMO must be taken on the official days under the supervision of a certified professional educator--absolutely no exceptions.[/quote]In fact it is even more restrictive: the test must be taken at 12:30 PM Eastern time.

There may be a glimmer of hope for you, if this option is practical:
[quote] It is possible, however, for a student to take the test under the supervision of a teacher at a site other than the student’s school for valid reasons. The student’s teacher must call the AMC national office for permission.[/quote]
So if you're going to be at your state music competition, and you have the block of time from 12:30-5:00 Eastern free on the appropriate days (April 19 and 20), and you have a teacher that can proctor, AND you get the AMC's permission, you might be OK.


algebra
polynomial
calculus
integration
superior algebra
superior algebra unsolved

Let $ r \in \mathbb{Z}[x]$ be a polynomial with integer coefficients and $ \epsilon_q$ be the $ q$-th primitive root of unity where $ q$ is a prime number. Is it true that
\[ \Pi_{i\equal{}1}^{q\minus{}1}r(\epsilon_q^i) \in \mathbb{Z},\]
or at least
\[ |\Pi_{i\equal{}1}^{q\minus{}1}r(\epsilon_q^i)| \in \mathbb{Z} \ ?\]

I am not experienced much with primitive roots.

For $ q = 2$, it should be clear that it is true.

For other larger prime $ q$, it should be able to group the non-real roots of unity into pairs, in which each of them are conjugates. And as the polynomial is with integer coefficent, and the respective pair would give a conjugate upon substitution into the polynomial. The expression now mean multiple of a integer, with $ \fac{q-1}{2}$ pairs of conjugates of integer modulus, hence I think the first one is true.

[quote="ssheep"]Let $ r \in \mathbb{Z}[x]$ be a polynomial with integer coefficients and $ \epsilon_q$ be the $ q$-th primitive root of unity where $ q$ is a prime number. Is it true that
\[ \Pi_{i \equal{} 1}^{q \minus{} 1}r(\epsilon_q^i) \in \mathbb{Z},
\][/quote]

Yes, this is true.
More generally, for every integral symmetric polynomial $ P$ of $ q\minus{}1$ variables, we have
$ P\left(\epsilon_q^1, \epsilon_q^2, ..., \epsilon_q^{q\minus{}1}\right)\in\mathbb{Z}$.
(An [i]integral polynomial[/i] means a polynomial with integer coefficients here.)
For the proof, recall that every symmetric polynomial $ P$ can be written as an integral polynomial in the elementary symmetric polynomials of the same variables, so it only remains to show that
$ \sigma_i\left(\epsilon_q^1, \epsilon_q^2, ..., \epsilon_q^{q\minus{}1}\right)\in\mathbb{Z}$ for every integer $ i\geq 0$.
But this is clear since $ \sigma_i\left(\epsilon_q^1, \epsilon_q^2, ..., \epsilon_q^{q\minus{}1}\right)$ equals $ 1$ if $ i\in\left\{0,q\minus{}1\right\}$ and $ 0$ otherwise.

Alternative proof:
On one hand, $ P\left(\epsilon_q^1, \epsilon_q^2, ..., \epsilon_q^{q\minus{}1}\right)$ is a polynomial of $ \epsilon_q$ with integer coefficients, and thus an algebraic integer over $ \mathbb{Z}$ (because $ \epsilon_q$ itself is an algebraic integer over $ \mathbb{Z}$).
On the other hand, $ P\left(\epsilon_q^1, \epsilon_q^2, ..., \epsilon_q^{q\minus{}1}\right)\in\mathbb{Q}\left(\epsilon_q\right)$ is fixed under every $ \mathbb{Q}$-automorphism of the field $ \mathbb{Q}\left(\epsilon_q\right)$ (because any such automorphism just permutes the $ \epsilon_q^i$'s and thus doesn't change the value of $ P\left(\epsilon_q^1, \epsilon_q^2, ..., \epsilon_q^{q\minus{}1}\right)$ since $ P$ is symmetric). Since the field extension $ \mathbb{Q}\left(\epsilon_q\right)\slash\mathbb{Q}$ is Galois, this yields that $ P\left(\epsilon_q^1, \epsilon_q^2, ..., \epsilon_q^{q\minus{}1}\right)\in\mathbb{Q}$.
Thus, $ P\left(\epsilon_q^1, \epsilon_q^2, ..., \epsilon_q^{q\minus{}1}\right)\in\mathbb{Q}$ is an algebraic integer over $ \mathbb{Z}$. Since $ \mathbb{Z}$ is integrally closed, this yields $ P\left(\epsilon_q^1, \epsilon_q^2, ..., \epsilon_q^{q\minus{}1}\right)\in\mathbb{Z}$.

I am rather sure there are simpler proofs.

  darij


inequalities
trigonometry
geometry
cyclic quadrilateral

Let $P$ be a point inside triangle $ABC$, and $D,E,F$ be the feet of perpendiculars from $P$ to the lines $BC,CA,AB$ respectively.
Prove that :
(i)  $EF=AP. \sin{A}$
(ii) $PA+PB+PC\geq2(PE+PD+PF)$

denote $\angle FAP=\alpha$ and $\angle EAP=\beta$
then $\alpha+\beta=A$
$EF^2 = PF^2+PE^2-2PE\cdot PF\cos FPE = PF^2+PE^2+2PE\cdot PF\cos A$
And $PF=AP\sin\alpha, PE=AP\sin\beta$
Thus we obtain
$EF^2 = AP^2(\sin^2\alpha+\sin^2\beta+2\sin\alpha\sin\beta\cos A)$

In fact,
$\sin^2\alpha+\sin^2\beta+2\sin\alpha\sin\beta\cos A = \frac{1-\cos 2\alpha}{2}+\frac{1-\cos 2\beta}{2}+(\cos(\alpha-\beta)-\cos(\alpha+\beta))\cos A = 1 - \cos(\alpha-\beta)\cos(\alpha+\beta) + \cos(\alpha-\beta)\cos A  -\cos^2 A = \sin^2 A$

This is Well-known inequality which named "Erdos-Mordell Theorem".

The proof I gave above is too complicated.
I suddenly realise the following one:

AFPE is a cyclic quadrilateral and $AP$ is the diameter. Hence by Law of Sine, $\frac{EF}{\sin A}=2r=AP$

for (ii)

Let $E'$ and $F'$ be the projection of $E$ and $F$ on $BC$, respectively.
We have $EF\geq E'F'$, $DE'=PE\cos (\frac{\pi}{2}-C)=PE\sin C$ and similarly $DF'=PF\sin B$

hence $AP\sin A = EF\geq DE'+DF'= PE\sin C+PF\sin B$
and $AP \geq PE\frac{\sin C}{\sin A}+PF\frac{\sin B}{\sin A}$

Similarly, we have another two inequalities. Sum them up and we obtain that

$PA+PB+PC\geq PD\left(\frac{\sin C}{\sin B} + \frac{\sin B}{\sin C}\right)+PE\left(\frac{\sin C}{\sin A} + \frac{\sin A}{\sin C}\right)+PF\left(\frac{\sin B}{\sin A} + \frac{\sin A}{\sin B}\right) \geq 2(PD+PE+PF)$