The following is a thread devoted to the discussion of COMC 2007, which will be held on November 21, 2007.  Feel free to discuss or give conjectures regarding this coming competition.

I conjecture that Problem 7 will be too easy, 3 of the problems will have bad puns, all written questions will have multiple parts, 6 people will solve the last question, and Alphonse and Beryl will play a game.

COMC is going to be held tomorrow, so good luck to all individuals writing it.  May I post the problems tomorrow, or should I wait a few days?

You should maybe wait until Friday, just in case.

Good Luck to everyone on COMC tomorrow!  :thumbup:

Good Luck to all writers! :D  :D

EDIT: What do you think the cutoff for CMO will be this year??

Yeah, I think so too.

It seemed way easier than last year's.

What if I get a 70.... how well do I need to get on Olymon to make CMO???

I hope it's around 70, maybe 68-70...because that's what is the max I can get.

it really depends on how other ppl do .....
70 maybe but i won't believe if it's lower than 70

this yr's paper is pointless, there is no question that can really seperate kids can do olympiad from kids who just good at school work    (maybe 3c can be?)

if a smart guy made a silly mistake then he will lose the chance to write CMO? well i hope it won't happen

I agree. I think it was easier than usual, especially easier than last year.

[quote="Nawahd Werdna"]How many people make CMO... the website says that aroudn 50 make but, in reality... isn't it like 65?
 :maybe:  :maybe:[/quote]

they will select some ppl they know and some guys do well on olymons
so there will be 70 ppl

By what time are invitations for CMO sent out???

Usually after the COMC results are out. So in mid or late December or January.

Yes, this year's COMC was almost trivial.  (Though 3c was quite interesting.)

Too bad during the 30 minutes I had to check over my work I did not realize part A question 4 asked for the number of students in June (not September) and that my factorization of the quadratic in part B 4a was wrong.

I wonder how many 80s there will be...

wow
this year's competition was really .. pointless like someone mentioned above.
i was hoping that my math level was upgraded but i guess not. it was just that contest was too easy.
it's so sad that even ppl who got around 70 is unsure about their ticket to CMO!

Congratulations everyone!
there is one year left till next COMC! :P

dude, the COMC owned me.  i couldn't even get the last question. totally not easy for me.

i don't think there are many 80s
writing solution for 3c is annoying, i know some people can't finish their solution due to the time limit

however, there will be a lot of ppl get 75-78

Yeah, I believe that too.  In fact, 3(c) was a pain, so hard to explain properly, so I tried using analogies.

But everything else I am pretty sure I got though.

I solved Part B 3c) completely by intronducing a Lemma, using Inequalities and Number Theories, but I ran out of time so I did not attempt 4b) c).

It was pretty sad because I solved both part under 10min after the contest.......

I also got some Part As wrong...............DOUH!

Does CMS membership help in getting in CMO?  I've recieved my membership card last night (on the same day as COMC)

In my opinion, writing up 3c in a rigorous and a concise way is quite hard for a person with little olympiad experience.
Problem 4 was really standard and involved just basic equation manipulating and a bit of tricks but nothing too complicated.
Problems 1 and 2 were much easier than last year, and part A was also much easier than usual, especially compared to previous year.
But it was a fun contest, and I really liked it, especially number 3, it was a very nice problem. Number 4 has some nice results, but they can be derived quite easily.
Hopefully I didn't do any stupid mistakes.

I hate it when the people remove marks without us knowing why we lost it.

Do they actually tell us.

Again, How many Olymon problems should I solve (for Nov. ) to be at least considered for CMO if I might only get around 68 - 70 on COMC???

ya~~i think its too easy, too
especially compared to last year's...
so...maybe the cutoff will be 65 this year...
we'll see........

I worked so hard this time
who knows.....

anywayz~good luck to everyone who wrote it

um...if you are saying it was easier this year

how come the cutoff you predict is 65.

Last year was 66.

the cutoff for certificate...
last yr was 40??
the one on the website

By cutoff, most of us assume CMO cutoff... not certificate cutoff... :lol:

but...I'm surprised to see the cut-off for certificate is 53 though...

[quote="longwan"]so what is the exact CMO cut off this year?[/quote]

Nobody knows as of now.

I got a  81 in this COMC..

I found a fatal error on the 3c, and then they had to give me a bonus mark for that

because i gave them the alternative solution.

The known solution only works only up to the prime number smaller than 2^2000. but after that, you need a different

strategy to attack it.

The markers admitted their mistakes, and then adjusted my mark so that my great work would not be depicted

as same as other 'ordinary works'


I hope this question hasn't been asked before, but does anyone know when national/state statistics for this year's AMCs will be posted on their website? I believe last year stats were up like mid-March (if you do the last modified thingey in the address bar). I'm sort of curious to know how other people in my state did.

I believe Mr. Dunbar said they'd be up when they finished all the more important stuff (scoring the AIME).

He said after about a month, since he had more important things to do (idk what, maybe AIME scoring/etc)


trigonometry
geometry
geometric transformation
reflection
trig identities
Law of Cosines
angle bisector

[quote="stergiu"]Let  $BD$   the   bisector of  angle  $B$  in an isosceles triangle  $ABC (AB = AC)$ .
  If  $BC = AB + 2AD$ , find the angles of the triangle $\triangle ABC$ .

 [u]Babis[/u][/quote]

[hide]
Label $AB = a$, $AD = x$, $DC = y$, $BC = b$.

$x + y = a$
$\frac{x}{a} = \frac{y}{b}$
$b = a + 2x$

so:
$\frac{a - x}{a + 2x} = \frac{x}{a}$
$a^2 - ax = ax + 2x^2$
$a^2-2ax - 2x^2 = 0 \implies (a-x)^2 - 3x^2 = 0 \implies (a - x - \sqrt{3}x)(a - x + \sqrt{3}x)$

WLOG we can let $x = 1$ and then $a = 1 + \sqrt{3}$ because it must be positive.
Then, $B = 3 + \sqrt{3}$ and $y = \sqrt{3}$

Then from the law of cosines, we get that $A = 120^{\circ}$ so $B = 30^{\circ}$ and $C = 30^{\circ}$.

Meh, that was probaly much more contrived it needed to be.
[/hide]

Reflect $A$ through $BD$ to $A'$. Since $BD$ is the angle bisector of $\angle{ABC}$, so $A'$ is on $BC$. Since $BC=AB+2AD$, $AB=A'B$, so $CA'=2AD$. Because $\angle{A}+2\angle{C}=180^o$, $\angle{BA'D}+\angle{CA'D}=180^o$ and $\angle{BA'D}=\angle{A}$, so $\angle{CA'D}=2\angle{C}$, which means $\triangle{CA'D}$ is a double angle triangle. Thus we must have:
\[ CD^2=A'D^2+ A'D \cdot A'C \]
Simplyfy:
\[ CD^2=3A'D^2=3AD^2 \]
Therefore:
\[ \frac{AB}{BC}=\frac{AD}{CD}=\frac{1}{\sqrt{3}} \]
Which gives $\angle{ABC}=30^o$.

Maybe you are confused about the double angle theorem:

http://www.mathlinks.ro/Forum/viewtopic.php?p=288310#p288310


Dwanye's choices may be crazy, but they have some sense of logic.

Dwanye is a picky eater. He will eat corn, carrots, meat, cheese, and will drink water but Dwanye won't eat tuna, lettuce, cabbage, cake(or cupcakes), and will not drink Coke. What is the logical explination?

Another easy one would be:

Dwanye has favorite cities to live in. He would live in Boston, Indiananapolis, or Sacramento, but wouldn't live in Miami, Houston, or Baltimore.

[hide="hint"] These problem has more to do with the words and spelling than math :) [/hide]

[hide="first one"]
he will only eat things that end in a consanant.[/hide]

[hide="second one"]
he will only live in capital cities.[/hide]

[quote="math92"][hide="first one"]
he will only eat things that end in a consanant.[/hide][/quote]
After doing intensive research, I have concluded that "cheese" does not end in a consonant.

The word "cupcakes" ends in a consonant, according to my research.

sorry guys :blush:, I meant cheese to be on the side he doesn't like and cupcakes is cupcakE

be careful next time...now this topic is dead


$p(x)$ is a real polynomial that for each $x\geq 0$, $p(x)\geq 0$. Prove that there are real polynomials $A(x),B(x)$ that $p(x)=A(x)^{2}+xB(x)^{2}$

Take all polynomials we're working with to be monic. Clearly, there is no loss of generality.

A product of polynomials of the form $A^{2}+xB^{2}\ (*)$ is again of this form, so it suffices to write $f$ as a product of first or second degree such polynomials. Its second degree irreducible factors are of this form, its first degree factors of the type $x+t, t\ge 0$ are again of this form, and the factors of the type $x-t, t\ge 0$ appear with even exponents, as can easily be seen, so we can pair them up into factors of the type $(x-t)^{2}$, which are also of the type $(*)$.

First we prove the statement for polynomials of degree 1 and 2.
Consider p(x)=ax+b of degree 1 such that p(x)>=0 for all x>=0.
Then a>=0 and b>=0 because of this. So we can write p(x) to this
form :     p(x) = (b^.5)^2 + x(a^.5)^2

Now consider p(x) = ax^2 + bx + c , and p(x)>=0 for all x>=0.
Then c>=0 and a>=0 and b^2-4ac >=0. So we can divide all coefficients
by positive real number a!=0 , and consider p(x) = x^2 + bx + c . If p(x)
have real roots we can write it to form (x-r1)(x-r2) and using previous
expression. So we can consider that p(x) has complex (unreal) roots
a+bi and a-bi (because p(x) is real polynomial) , so the polynomial p(x)
is to the form p(x) = x^2 - 2ax + (a^2+b^2). So we can write it to the
form:      p(x) = (x - (a^2+b^2)^.5)^2 + x((2(a^2+b^2)^.5 - 2a)^.5)^2
(notice: we used that (a^2+b^2)^.5-a>=0 )

Now we claim that if p(x) and q(x) be real polynomials and we can write
them to this form, then we can write p(x)q(x) to this form.
Proof. p(x)=A(x)^2 + xB(x)^2      q(x)=C(x)^2 + xD(x)^2

so p(x)q(x) = (AC)^2 + x(AD)^2 + x(BC)^2 + (xBD)^2
                 = (xBD-AC)^2 + x(AD+BC)^2
this completes the proof of claim.

Finaly, Consider the real polynomial p(x) be reduced in R[x], by
multiplication of some degree 1 and degree 2 (for complex unreal roots)
polynomials.

p(x)=a(x^2-2a1.x+(a1^2+b1^2))^l1...(x^2-2ar.x+(ar^2+br^2))^lr(x-c1)^k1...(x-cs)^ks
where r,s are index of ai 's and bi 's and ci 's.and li and ki are occurence
of roots.

The coefficent a is don't care because we can enter it to the expression.
(a is possitive)
                          ap(x)=(a^.5 A)^2 + x(a^.5 B)^2
and ci>=0 or li=0(mod 2) else we have sign variance in x=ci.
and square polynomial can be written to this form:
A^2 = (A)^2+x(0)

So we can write p(x) to this form, because each of it factors can be
written to this form.  :D


vector
calculus
integration
analytic geometry
trigonometry

I love to do all the excercises I can vectorially as possible (I find it the safest way to go for me: Helps you to understand the whole proccess). The problem is: I CAN'T GET IT TO WORK HERE!

I want to calculate the magnetic field a distance $ z$ above the center of a circular loop of radius $ R$, wich carries a steady current $ I$.

So, Biot-Savart law tell us that an infinitesimal vector $ d\vec{B}$ it's proportional to the permeability of space, divided by $ 4\pi r^2$. It has to be also proportional to the cross product of an element of length $ d\vec{l}$ and the position vector $ \hat{r}$ multiplied by the current $ I$. In other words:

$ d\vec{B} \equal{} \frac {u_0}{4\pi}\frac {I(d\vec{l} \times \hat{r})}{r^2}$

So, if we want the whole magnetic field, we simply sum all the contributions, giving us a line integral (in the case of a wire):

$ \vec{B} \equal{} \frac {u_0}{4\pi}\int \frac {I(d\vec{l} \times \hat{r})}{r^2}$

So, in our case, in cartesian coordinates the vector $ \vec{r}$ that goes from an element on the wire $ \vec{r_1} \equal{} (x,y,0)$ to our distance z above the xy plane $ \vec{r_2} \equal{} (0,0,z)$ is:

$ \vec{r} \equal{} \vec{r_2} \minus{} \vec{r_1} \equal{} (0,0,z) \minus{} (x,y,0) \equal{} ( \minus{} x, \minus{} y,z)$

Wich give us the normalized position vector:

$ \hat{r} \equal{} \frac {\vec{r}}{\sqrt {x^2 \plus{} y^2 \plus{} z^2}}$

Finally, our element of length is $ d\vec{l} \equal{} ( \minus{} dx,dy,0)$ (this last part is crucial in the final result. Why did I choose $ \minus{} dx$ instead of $ dx$? Well, i want the current to flow counter-clock wise so the magnetic field goes upwards).

Now we take the cross product:

$ d\vec{l} \times \hat{r} \equal{} \frac {(zdy,zdx,xdy \plus{} ydx)}{\sqrt {x^2 \plus{} y^2 \plus{} z^2}}$

Now we can integrate each cartesian coordinate separately. We then use polar coordinates and write down $ x \equal{} Rcos(\theta)$,$ y \equal{} Rsin(\theta)$, $ z \equal{} z$ and $ dx \equal{} \minus{} Rsin(\theta)d\theta$, $ dy \equal{} Rcos(\theta)d\theta$. So, our original integral:

$ \vec{B} \equal{} \frac {u_0}{4\pi}\int \frac {I(zdy,zdx,xdy \plus{} ydx)}{(x^2 \plus{} y^2 \plus{} z^2)^{3/2}}$

Changes to:

$ \vec{B} \equal{} \frac {u_0}{4\pi}\int^{2\pi}_{0} \frac {I(Rzcos(\theta)d\theta, \minus{} Rzsin(\theta)d\theta,(Rcos(\theta))^2d\theta \minus{} (Rsin(\theta))^2d\theta)}{(R^2 \plus{} z^2)^{3/2}}$

We can see here that the $ \hat{x}$ component and the $ \hat{y}$ component vanishes. And we finally get:

$ \vec{B} \equal{} \frac {Iu_{0}}{4\pi}\int^{2\pi}_{0} \frac {R^2(cos(\theta)^2 \minus{} sin(\theta)^2)}{(R^2 \plus{} z^2)^{3/2}} d\theta\hat{z} \equal{} \frac {Iu_{0}}{4\pi}\int^{2\pi}_{0} \frac {R^2(1 \minus{} 2sin(\theta)^2)}{(R^2 \plus{} z^2)^{3/2}} d\theta\hat{z}$

Wich gives, recalling $ cos(2\theta) \equal{} 1 \minus{} 2(sin(\theta))^2$:

$ \vec{B} \equal{} \frac {Iu_{0}}{4\pi}\int^{2\pi}_{0} \frac {R^2cos(2\theta)}{(R^2 \plus{} z^2)^{3/2}} d\theta\hat{z} \equal{} 0$

I know the result has to be:

$ \vec{B} \equal{} \frac {Iu_{0}R^2}{2(R^2 \plus{} z^2)^{3/2}} \hat{z}$

Wich actually gives if you replace $ d\vec{l} \equal{} ( \minus{} dx,dy,0)$ for $ d\vec{l} \equal{} (dx,dy,0)$ (current going clock-wise). What's wrong?

Thinking about this i came up with the solution.

The thing is that you don't have to take the vector $ d\vec{l}\equal{}(\minus{}dx,dy,0)$, because the very definition of the integral in polar coordinates sums the contributions counter clock-wise alone (recall that the integral goes from $ 0$ to $ 2\pi$).

In that case, just letting $ d\vec{l}\equal{}(dx,dy,0)$, you get the result you are suposed to.

Your mistake is the following:

so basically what you wrote, but let me highlight it a little:

when you set $ d\vec l \equal{} ( \minus{}dx, dy, 0)$, here you set that $ dx > 0$. But later when you switch to polar coordinates, you say $ dx\equal{}\minus{}R\sin\theta d\theta$ so you reverse the sign of the element..
so since you chose your element already by the signs, you should change the orientation of the polar coordinates you introduce.

Thanks for put in it that way [i]yeahnigga[/i], it's a lot more helpfull !!


Euler
function
modular arithmetic
algebra
polynomial
calculus
integration

This may look very stupid, but I nedd help with the following fact:
For any prime p, there exists a residue r, so that ord(r) = p-1.
This means that r^k generates all the numbers in Zp.
I am not so good in NTH so please help.

Try this (just an outline):

(1) Show that the number of elements in $Z_p$ with order $p_i$ is $p_i-1=\phi(p_i)$, for all primes $p_i|p-1$.

(2) Show that the number of elements in $Zp$ with order $p_i^k$ is $\phi(p_i^k)$, where $p_i$ is prime and $p_i^k|p-1$.

(3) Show that the number of elements in $Z_p$ with order $d|p-1$ is exactly $\phi(d)$.

($\phi$ is the Euler function)

You apply (3) to $d=p-1$ and we get even more than we wanted: we get $\phi(p-1)$ primitive roots instead of just one. Throughot the proof, a crucial property of the Euler function, which is used all the time, is that $\displaystyle \sum_{d|n}\phi(d)=n,\ \forall n\in N^*$. We also use the fact that $Z_p$ is a field, so $(Z_p^*,\cdot)$ is a group. Try it; it's really not that hard from here.

Yea, sure, thanks.
But I think the same problem was somewhere in the forum, I mean that of the number of primitive roots is phi(x), and it used the fact that there existed such a primitive root :) :D.
Also, this fact is used in a lot of many other theorems, so I guess it must have a much easier proof.
Also, I think it is not true for any ring or even group. :)

No, it's not true for any ring or group, but, on the other hand, I didn't say that, did I? :D. We have additional properties due to the fact that $p$ is prime. One such property is that $x^d-1=0$ has exactly $d$ roots in $Z_p$ for all divisors $d$ of $p-1$. I didn't write the solution in detail, so that's why I forgot to mention some of the properties we use.

After this, you directly get $\phi(p-1)$ primitive roots, so it's kind of pointless to show that there is one, and then to show that there are $\phi(p-1)$, right? :)

But how to prove that all numbegrs p^a and 2*p^a (p>2) have a primitive root? (maybe solution is similar to case a=1, but I can't find it :( )
And how to prove that other numbers (except 2 and 4) don't have?
Please help!

I took a small step :):

If $4|n$ and $n$ has a primitive root then $n=4$: In order to show this we must observe that the equation $x^2-1=0$ has $4$ solutions in $F_n$: $n-1,n+1,\frac n2 -1, \frac n2+1$, but this would be impossible if $U(F_n)$ was cyclic (there would be only $2$ roots).

Come to think of it, I think I can show that there are no primitive roots for $n$ other than $p^t,2p^t,2,4$. Assume there is $n=ab,\ a,b\ge 3,\ (a,b)=1$. It's not hard to check, in this case, that $Z_n^{\times}\simeq Z_a^{\times}\cdot Z_b^{\times}$, where $A^{\times}$ is the usual notation for the group of invertible elements of the ring $A$, and $\simeq$ means isomorphic. The isomrphism is $x \mod n\leftrightarrow (x\mod a,\ x\mod b)$.

Assume $x$ is a primitive root of $n$. In this case the smallest $k$ for which $x^k=1$ must be $\phi(n)$, but $x^{\phi(a)}=1\ (\mod\ a),\ x^{\phi(b)}=1\  (\mod\ b)$, and both $\phi(a),\phi(b)$ are even, so they're not coprime, so $[\phi(a),\phi(b)]<\phi(a)\phi(b)=\phi(ab)=\phi(n)$, and since $x^{[\phi(a),\phi(b)]}=1\ (\mod\ n)$, it means that $\phi(n)$ isn't the smallest $k$ s.t. $x^k=1\ (\mod\ n)$, contradiction.

So it turns out that the problem was not as easy as I thought.
Anyway, maybe somebody knows how to prove this not by counting the number of roots.

I do!

Alternative proof of the existence of a primitive root modulo a prime $p$:

Let $k_1,\ldots,k_m$ be all different orders modulo $p$ of the numbers $1,2,\ldots,p-1$. Let $n = [k_1,\ldots,k_m]$ be their least common multiple. If $n=q_1^{\alpha_1}\cdots q_s^{\alpha_s}$ is the prime factorization of $n$, then each factor $q_i^{\alpha_i}$ divides at least one of the numbers $k_j$, and this $k_j$ may be written as $k_j = a_{ij}q_i^{\alpha_i}$. Let $l_j$ be one of the numbers $1,\ldots,p-1$ which has order $k_j$ modulo $p$ (such exists, by the definition of the $k_j$). Then, the number $t_j:= l_j^{a_{ij}}$ has order $q_i^{\alpha_i}$. It follows that the product $g:=t_1 \cdots t_s$ has order $q_1^{\alpha_1} \cdots q_s^{\alpha_s} = n$ modulo $p$. To complete the proof, it suffices to show that $n=p-1$.

Suppose to the contrary that $n<p-1$. For each $c \in \{1,\ldots,p-1\}$, we have, by the definition of $n$, $c^n \equiv 1 \pmod{p}$. Let $c_i=i$ for $1 \leq i \leq n+1$ (by assumption, $n+1<p$, so the chosen numbers are non-zero pairwise distinct modulo $p$.) Consider the polynomial $f(x)=x^n-1$. It can be written in the form
\[
f(x) = x^n-1 = \sum_{0 \leq i \leq n} t_i(x-c_1)\cdots (x-c_i),
\]
where $t_n=1,t_{n-1}, \ldots,t_0$ are integers. Indeed, $t_n=1$, then  $t_{n-1}$ is chosen so that the coefficient of $x^{n-1}$ in the resulting polynomial is zero, then $t_{n-1}$ is chosen so that the coefficient of $x^{n-2}$ becomes zero, and so forth (the integral coefficients $t_n, t_{n-1}, \ldots$ are defined successively). Now, by plugging in $x=c_0$, we get that $p\, | \, t_0$. By plugging in $x=c_1$, we now find that $p \, | \, t_1$. By induction, we get that all coefficients $t_0,t_1,\ldots,t_{n-1}$ are divisible by $p$. Thus,
\[
0 \equiv f(c_{n+1}) \equiv (c_{n+1}-c_1) \cdots (c_{n+1} -c_n) \pmod{p},
\]
which is clearly a contradiction because the numbers $c_1,\ldots,c_{n+1}$ are pairwise distinct modulo $p$. This contradiction shows that $n=p-1$. This completes the proof, because $g$ has order $n$.

For an elementary proof of the existence of a primitive root modulo $p^k$, I suggest to try the following. Let $g$ be a primitive root modulo $p$. Then, show that at most one of the numbers $g^{p-1}$ and $(g+p)^{p-1}$ is congruent to $1 \pmod{p^2}$. In this way, we may assume that $g$ is a primitive root $\pmod{p}$ and $g^{p-1} \neq 1 \pmod{p^2}$. Then, show that this same $g$ (!!!) is a primitive root modulo $p^k$ for each $k \geq 2$.

For the existence of a primitive root $\pmod{2p^k}$, use the existence of a primitive root $g$ modulo $p^k$. One of the numbers $g$ and $g+p^k$ is odd; prove that this number is a primitive root $\pmod{p^k}$.

Hope this helps.  :)


Prove that in any $ \triangle\ ABC$ we have $ \sum\frac{a^3}{(r_a\minus{}r)^2}\ \ge\ \frac{4}{a\plus{}b\plus{}c}\cdot\left(\sum r_a\right)^2$ with equality iff $ a\equal{}b\equal{}c\ .$

hello, are $ r_a,r_b$ and $ r_c$  the exradii of the given triangle? and is $ r$ the radius of the incircle?
Sonnhard.

I think it can be proved by the indentity

$ \sum\frac {a^3}{(r_a \minus{} r)^2} \equal{} \frac {2p(2R \minus{} r)}{r}$ and $ \frac {4}{a \plus{} b \plus{} c}\cdot\left(\sum r_a\right)^2 \equal{} \frac {2(16R^2 \plus{} 8Rr \plus{} r^2)}{p}$ when $ p \equal{} \frac {a \plus{} b \plus{} c}{2}$ so we must prove
\[ \frac {2p(2R \minus{} r)}{r}\geq\frac {2(16R^2 \plus{} 8Rr \plus{} r^2)}{p}\Leftrightarrow p^2\geq \frac {r(16R^2 \plus{} 8Rr \plus{} r^2)}{2R \minus{} r}
\]
If using $ p^2\ge 16Rr \minus{} 5r^2$ we must prove $ 16Rr \minus{} 5r^2\ge \frac {r(16R^2 \plus{} 8Rr \plus{} r^2)}{2R \minus{} r}\Leftrightarrow \frac {(2r(8R \minus{} r)(R \minus{} 2r)}{2R \minus{} r}$ which is true.

[quote="Virgil Nicula"] [color=darkred]Prove that in any $ \triangle\ ABC$ we have $ \sum\frac {a^3}{(r_a \minus{} r)^2}\ \ge\ \frac {4}{a \plus{} b \plus{} c}\cdot\left(\sum r_a\right)^2$ with equality iff $ a \equal{} b \equal{} c\ .$[/color] [/quote]

[color=darkblue][b][u]Proof[/u].[/b] $ \left\|\ \begin{array}{c}
 \sum r_a\equal{}4R\plus{}r\\\
S\equal{}pr\equal{}(p\minus{}a)r_a\end{array}\ \right\|\ \Longrightarrow\ r_a\minus{}r\equal{}\frac {ar_a}{p}\equal{}\frac {ar}{p\minus{}a}$ $ \Longrightarrow$ $ \sum\frac {a^3}{\left(r_a\minus{}r\right)^2}\equal{} \frac {1}{r^2}\cdot\sum a(p\minus{}a)^2\ .$

$ \sum\frac {a^3}{(r_a \minus{} r)^2}\ \ge\ \frac {4}{a \plus{} b \plus{} c}\cdot\left(\sum r_a\right)^2\ \Longleftrightarrow\ p\cdot\sum a(p\minus{}a)^2\ge 2r^2\cdot(4R\plus{}r)^2$ $ \Longleftrightarrow$

$ p^2(2R\minus{}r)\ge r(4R\plus{}r)^2$ . In conclusion, $ \left\|\ \begin{array}{c}
 p^2\ge 3r(4R\plus{}r)\\\\\\\
 2R\minus{}r\ge \frac {4R\plus{}r}{3}\end{array}\ \right\|\ \odot\ \Longrightarrow$ $ p^2(2R\minus{}r)\ge r(4R\plus{}r)^2$ . [/color]


[quote="arqady"]Let $ a,$ $ b$ and $ c$ are positive numbers. Prove that:
\[ \frac{a^2}{b}\plus{}\frac{b^2}{c}\plus{}\frac{c^2}{a}\geq\frac{37(a^2\plus{}b^2\plus{}c^2)\minus{}19(ab\plus{}ac\plus{}bc)}{6(a\plus{}b\plus{}c)}\][/quote]
Hi, arqady. When equality holds?

[quote="arqady"]For $a=b=c$.[/quote]

 Sorry for my lack of, thank you.
The following inequality is also true.
For $a, b, c>0$ prove that
\[\frac{a^2}{b}+\frac{b^2}{c}+\frac{c^2}{a}\ge\frac{2999(a^2+b^2+c^2)-1541(ab+bc+ca)}{486(a+b+c)}\]

[quote="arqady"]By the same way we can prove a stronger inequality.
Let $a$, $b$ and $c$ be positive numbers. Prove that:
\[ \frac{a^2}{b}+\frac{b^2}{c}+\frac{c^2}{a}\ge\frac{469(a^2+b^2+c^2)-241(ab+bc+ca)}{76(a+b+c)} \][/quote]
Try please $a=\frac{71}{132}, b=\frac{1}{3}, c=1$

Thank you, oldbeginner! I have fixed my post.

[quote=arqady]By the same way we can get a best estimation.
Let $a$, $b$ and $c$ be positive numbers. Prove that:
\[ \frac{a^2}{b}+\frac{b^2}{c}+\frac{c^2}{a}\ge\frac{k(a^2+b^2+c^2)-(k-3)(ab+bc+ca)}{a+b+c} \]
where $k$ is a maximal real root of the following equation.
$x^4-11x^3+72x^2-304x+269=0$.
$k_{best}=6.1708001...$.[/quote]

Can you show a proof?

[quote=arqady]See here: https://artofproblemsolving.com/community/c6h296853p3520148
It's the same.[/quote]

I want to see that it the best constant

[quote=janitor]
I want to see that it the best constant[/quote]
If you so want, why you can not do it by yourself?
Rewrite this inequality in the following form:
$$u(9u^2v^2-6v^4-uw^3)-2(ku^2-(k-1)v^2)w^3\geq u^2(a-b)(a-c)(b-c).$$
Now, prove that $$u(9u^2v^2-6v^4-uw^3)-2(ku^2-(k-1)v^2)w^3\geq0,$$
for which it's enough to prove the last inequality for $b=c=1$.

After squaring of the both sides we need to prove that
$$\left(u(9u^2v^2-6v^4-uw^3)-2(ku^2-(k-1)v^2)w^3\right)^2\geq27u^4(3u^2v^4-4v^6-4u^3w^3+6uv^2w^3-w^6),$$
which is a quadratic inequality of $w^3$.
Good luck!


modular arithmetic
Putnam
number theory solved
number theory

Here is a beautiful easy problem. The solution I gave is very ugly, but the theacher showed be a super-cool solution. I will let you the pleasure of finding it.
  It says that if n+1 is a multiple of 24, then the sum of the divisors of n is also divisible by 24.

Indeed a relatively easy problem: We know that if d is a divisor of n, then so is $ \frac nd$. And because $ n + 1 \equiv 0 \pmod{24}$, we have that $ n \equiv 3 \pmod 4$, so $n$ cannot be a perfect square, thus it has an even number of divisors. We can therefore group them into pairs as above, so it's we just need to check that $24 \mid d+\frac nd$, or $ 24 \mid \frac {d^2+n}d $. Since $\gcd (n,24)=1$ it follows that $\gcd (d,24)=1$, so we need $ 24 \mid d^2+n$, or $ d^2 \equiv 1 \pmod{24}$.

This is easy, as if $\gcd (3,d)=1$, then $d^2 \equiv 1 \pmod 3$ and if $\gcd (d,8)=1$, then $d^2 \equiv 1 \pmod 8$, and as $24 = 3 \cdot 8$ we are done.

What is your solution Harazi?

Wow, you found this solution in 10 minutes... Boy, you are really magnificient! Well, my solution just uses formulas and lots of congruences that made mad our coller ( among other things, such as mixing romanian with english and french!). It is not interesting, this is the solution he showed to me.

I knew the problem ahead, since I got it at a test at the university (the one which you didn't take :P). But I solved it then like this in 10 minutes then also :)

Ok, Valentin, here is one that cannot be solved in 10 minutes ( in fact, who knows?): find all natural numbers a such that if n+1 is a multiple of a, so is the sum of the divisors of n.

We shall prove that the numbers we are looking for are of the form
\[ a \equal{} 2^k \cdot p_1 p_2 \cdots p_m
\]
where $ p_i$ is a Mersenne prime (ie $ p_i \minus{} 1$ is a power of 2).

We first prove that these numbers satisfy the hypothesis. Indeed, since $ \varphi (a) \equal{} 2^s$, for a certain $ s$, and since the multiplicative group units in the ring $ \mathbb{Z} / a\mathbb{Z}$ has exactly $ \varphi(a)$ elements, it follows that this group has the property that each element is its own inverse, ie $ x^2\equiv 1 \pmod a$.

And since each $ d \mid n$ divisor of n, is obviously a member of this units group, it follows that $ d^2 \plus{} n \equiv 0 \pmod a$, and as in the case $ a \equal{} 24$ the sum of the divisors of $ n$ is obviously $ \equiv 0 \pmod a$.

Now, for the converse. Since all the numbers with $ \varphi(a)$ being a power of two are described above (I hope this is an obvious statement for everyone), we know that $ \varphi (a)$ has at least an odd prime divisor $ p \geq 3$. By Cauchy's theorem (for groups) it follows that we have an element $ r$ of order $ p$, ie
\[ r^p \equiv 1 \pmod a
\]
Now this implies that $ ( \minus{} r)^p \equiv \minus{} 1 \pmod a$, and that $ p$ is the smallest number with that property (since p is odd). Now, let $ q$ be prime number such that $ q\equiv \minus{} r \pmod a$. This prime number exists because of Dirichlet's theorem ($ r$ and $ a$ are coprime).

Consider $ n \equal{} q^p$. From the choosing of $ q$, $ n \plus{} 1$ is divisible by $ a$. However, the sum of divisors of $ n$ is
\[ \sigma(n) \equal{} \frac { q^{p \plus{} 1} \minus{} 1}{q \minus{} 1}
\]
If the latter would be divisible by $ a$, then $ q^{p \plus{} 1} \minus{} 1$ would be also divisible by $ a$, that is $ q^p \cdot q \equiv 1 \pmod a$ or $ q\equiv \minus{} 1 \pmod a$, which contradicts the fact that $ r$ had order $ p$ modulo $ a$.

We need to have all the elements in the group of units of $ \mathbb{Z}/a\mathbb{Z}$ of order 2, thus if $ \gcd(x,a) \equal{} 1$ then $ x^2 \equiv 1 \pmod a$. Let $ p \mid a$ be a prime. Then $ x^2\equiv 1 \pmod p$ for all $ x\in \mathbb{Z}/p\mathbb{Z}$. But this of course cannot happen for $ p > 3$, because $ (x \plus{} 1)(x \minus{} 1) \equiv 0 \pmod p$ cannot have more than 2 solutions in the field $ \mathbb{Z}/p\mathbb{Z}$. Thus $ a \equal{} 2^k\cdot 3^r$.

But if $ r\geq 2$, then $ x^2 \equiv 1 \pmod 9$ for all $ x$ which are coprime with 3. For $ x \equal{} 5$ this does not happen. So $ a \equal{} 2^k\cdot 3$.

Similarly, if $ k\geq 4$, then because $ 3^2 \equiv 9 \pmod {16}$ we obtain a contradiction. Thus $ k\leq 3$, so, indeed all $ a$-s are divisors of 24.  :blush:

Also, we need to straight something. In my second part of my (partially) wrong proof, I used that the order of $ r$ is odd, and thus so is the order of $ \minus{} r$. If the order of $ r$ is a power of 2, (in the case that $ a$ is not a divisor of 24, but still $ \varphi (a)$ is a power of 2), the argument is still valid but it's trickier.

Consider a prime divisor of $ q\mid a$, $ q > 3$ (if such a prime exists). Since the multiplicative units group in the field $ \mathbb{Z}/q\mathbb{Z}$ is cyclic (well known algebra theorem), and because obviously (-1) cannot be a generator for this group, it follows that there exist positive integers $ r < q$ and $ k > 1$ such that $ r^{k} \equiv \minus{} 1 \pmod q$.

First suppose that $ k$ is not a power of 2. We can consider then that $ k$ is actually and odd number (we re-consider $ r$). Further on, considering a prime $ z$ (running out of letters soon :)) such that $ z \equiv r \pmod q$ and $ z \equiv \minus{} 1 \pmod {\frac aq}$ (such a prime exists in the basis of the Chinese Remainder theorem and Dirichlet's theorem) so $ z^k \plus{} 1 \equiv 0 \pmod a$. But then, $ z^{k \plus{} 1} \equiv \minus{} z \equiv 1 \pmod a$, so $ z \equiv 1 \pmod a$, and also $ z\equiv 1 \pmod q$ which is obviously a contradiction.

Now, if $ k$ is a power of 2 for all $ q$-s. This means that $ q \equiv 1 \pmod 4$ by Fermat's theorem (a little extra :)), so we can find an $ r^2 \equiv \minus{} 1 \pmod q$, $ r \neq \minus{} 1 \pmod q$. Let $ p$ be a prime such that $ p \equiv r \pmod q$, and $ \hat p$ is a unit in $ \mathbb{Z}/a\mathbb{Z}$. Let $ \widehat{ \minus{} p'}$ be its inverse element, and let $ p'$ be a prime also. Then $ pp' \plus{} 1 \equiv 0 \pmod a$, and the sum of divisors is $ pp' \plus{} 1 \plus{} p \plus{} p' \equiv 0 \pmod a$, therefore $ p \equiv \minus{} p' \pmod a$. But then $ p\cdot { \minus{} p'} \equiv 1 \pmod a \ \Leftrightarrow p^2 \equiv 1 \pmod a$, that is $ p^2 \equiv 1 \pmod q$ which is a contradiction.

The final case is when we have no such $ q > 3$, so $ a \equal{} 2^s\cdot 3$. But then we consider two primes $ p,q$ such that $ p \equiv 2^{s \minus{} 2} \minus{} 1 \pmod {2^s}$ and $ q \equiv p \plus{} 2 \pmod {2^s}$, and also such that $ p \neq q \pmod 3$. Such primes obviously exist in the basis of the same theorems stated above. Then $ pq \plus{} 1 \equiv 0 \pmod a$, for $ 2(s \minus{} 2) \geq s \ \Leftrightarrow \ s\geq 4$, but $ p \plus{} q \equiv 2^{s \minus{} 1} \pmod 2^s$ which is a contradiction, so $ s\leq 3$ so $ a \mid 24$.

Dear Valentin, I must admit that the solution is very nice and elaborated, but I think it is wrong. I must be idiot, but I knew that the only numbers a for which ech element in the ring of invertibles of Z /aZ is equal to its invrse are the divisors of 24. Of course, I must be wrong, or probably by Z/aZ you refer toother things, unknown to me.

Ah harazi, you are right. I hurried to write down, but it was obvious that the order of elements in such rings (with $\varphi(a)=2^s$) is not 2, but a power of 2  :blush:

Still my argument can be adapted. We need to have all the elements in the group of units of $\mathbb{Z}/a\mathbb{Z}$ of order 2, thus if $\gcd(x,a)=1$ then $x^2 \equiv 1 \pmod a$. Let $p \mid a$ be a prime. Then $x^2\equiv 1 \pmod p$ for all $x\in \mathbb{Z}/p\mathbb{Z}$. But this of course cannot happen for $p>3$, because $(x+1)(x-1) \equiv 0 \pmod p$ cannot have more than 2 solutions in the field $\mathbb{Z}/p\mathbb{Z}$. Thus $a=2^k\cdot 3^r$.

But if $r\geq 2$, then $x^2 \equiv 1 \pmod 9$ for all $x$ which are coprime with 3. For $x=5$ this does not happen. So $a=2^k\cdot 3$.

Similarly, if $k\geq 4$, then because $3^2 \equiv 9 \pmod {16}$ we obtain a contradiction. Thus $k\leq 3$, so, indeed all $a$-s are divisors of 24.  :blush:

Also, we need to straight something. In my second part of my (partially) wrong proof, I used that the order of $r$ is odd, and thus so is the order of $-r$. If the order of $r$ is a power of 2, (in the case that $a$ is not a divisor of 24, but still $\varphi (a)$ is a power of 2), the argument is still valid but it's trickier.

Consider a prime divisor of $q\mid a$, $q>3$ (if such a prime exists). Since the multiplicative units group in the field $\mathbb{Z}/q\mathbb{Z}$ is cyclic (well known algebra theorem), and because obviously (-1) cannot be a generator for this group, it follows that there exist positive integers $r<q$ and $k>1$ such that $r^{k} \equiv -1 \pmod q$.

First suppose that $k$ is not a power of 2. We can consider then that $k$ is actually and odd number (we re-consider $r$). Further on, considering a prime $z$ (running out of letters soon :)) such that $z \equiv r \pmod q$ and $z \equiv -1 \pmod {\frac aq}$ (such a prime exists in the basis of the Chinese Remainder theorem and Dirichlet's theorem) so $z^k + 1 \equiv 0 \pmod a$. But then, $z^{k+1} \equiv - z \equiv 1 \pmod a$, so $z \equiv 1 \pmod a$, and also $z\equiv 1 \pmod q$ which is obviously a contradiction.

Now, if $k$ is a power of 2 for all $q$-s. This means that $q \equiv 1 \pmod 4$ by Fermat's theorem (a little extra :)), so we can find an $r^2 \equiv -1 \pmod q$, $r \neq -1 \pmod q$. Let $p$ be a prime such that $p \equiv r \pmod q$, and $\hat p$ is a unit in $\mathbb{Z}/a\mathbb{Z}$. Let $\widehat{-p'}$ be its inverse element, and let $p'$ be a prime also. Then $pp'+1 \equiv 0 \pmod a$, and the sum of divisors is $pp'+1+p+p' \equiv 0 \pmod a$, therefore $p \equiv -p' \pmod a$. But then $p\cdot {-p'} \equiv 1 \pmod a \ \Leftrightarrow p^2 \equiv 1 \pmod a$, that is $ p^2 \equiv 1 \pmod q$ which is a contradiction.

The final case is when we have no such $q>3$, so $a=2^s\cdot 3$. But then we consider two primes $p,q$ such that $p \equiv 2^{s-2}-1 \pmod {2^s}$ and $q \equiv p+2 \pmod {2^s}$, and also such that $p \neq q \pmod 3$. Such primes obviously exist in the basis of the same theorems stated above. Then $pq+1 \equiv 0 \pmod a$, for $2(s-2) \geq s \ \Leftrightarrow \ s\geq 4$, but $p+q \equiv 2^{s-1} \pmod 2^s$ which is a contradiction, so $s\leq 3$ so $a \mid 24$.

If I have not made other (foolish) mistakes I think that now the problem is solved. And indeed it took more than 10 minutes :P

Beautiful! Congratulations, a very nice solution indeed. Here is another, shorter solution. First of all, it is not difficult to prove that if a does not divide 24 then there exists a prime number p such that a does not divide $ p^2-1$ and p does not divide a. Then, consider a prime number q such that qp+1 is a multiple of a. It exists by Dirichlet theorem. It follows that p+q is also divisible by a and so a divides $p^2-1$, false.

I saw something similar to initial problem in Russian Olimpiad 2001. At least it uesd an idea close to Valentine's one.

[quote="Valentin Vornicu"]Ok, I must admit that this took more than 10 minutes to write, but less to solve :D So, here goes nothing:

We shall prove that the numbers we are looking for are of the form \[ a= 2^k \cdot p_1 p_2 \cdots p_m \] where $p_i$ is a Mersenne prime (ie $p_i-1$ is a power of 2).
[/quote]

Something is totally wrong here.  First, there is a confusion of Fermat-primes (powers of two plus one) and Mersenne-primes (powers of two minus one) , The proof only makes sense for Fermat-primes.

However: Take a=17. This satisfies the conditions of Valentin.  But for n=16, we have n+1 divisible by 17, whereas the sum of divisors of n is 1+2+4+8+16=31, which is not divisible by 17.

Actually, the correct answer seems to be: All divisors of 24 except 2.

My dear friend, have you read the posts after that mistake?


quadratics
number theory
greatest common divisor
Vieta
induction
algorithm
algebra

The quadratic equation $x^{2}+mx-1=0$ has roots $\alpha$ and $\beta$ such that $m$ is an odd integer. Let $\lambda_{n}= \alpha^{n}+\beta^{n},$ for $n \geq 0.$ Prove that for $n \geq 0,$

$(a)$ $\lambda_{n}$ is an integer, and

$(b)$ $\gcd(\lambda_{n}, \lambda_{n+1}) = 1.$

[quote="Hokkage"][hide]Idea for a: apply Vieta's relations and show that there is a way of getting $a^{n}+b^{n}$ in terms of $m$ and $-1$ (hence an integer).[/hide][/quote]
Using this idea we get $\lambda_{n-1}(\alpha+\beta)=\lambda_{n}+\alpha\beta\lambda_{n-2}$. Applying Vieta's theorem ($\alpha+\beta=-m$, $\alpha\beta=-1$) we transform it to form $\lambda_{0}=2, \lambda_{1}=-m, \lambda_{n}=-m\lambda_{n-1}+\lambda_{n-2}$. It's obvious that for any $n\geq 0$ the number $\lambda_{n}$ is an integer.
Induction for $\gcd(\lambda_{n},\lambda_{n+1})=1$:
1. $n=0$
Obvious because $2\bot-m$ ($m$ is odd).
2. We know that $\gcd(\lambda_{n-1},\lambda_{n})=1$ and have to prove that $\gcd(\lambda_{n},\lambda_{n+1})=1 \iff \gcd(\lambda_{n},-m\lambda_{n}+\lambda_{n-1})=1$. Using Euclid's algorithm we get $\gcd(\lambda_{n},-m\lambda_{n}+\lambda_{n-1})=\gcd(\lambda_{n},-(m-1)\lambda_{n}+\lambda_{n-1}) =...=$ $\gcd(\lambda_{n},\lambda_{n-1})=1$ which ends the proof.

Posted at
[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?p=442328#p442328[/url]
the Indian RMO from the past 10 years is also available in resources section. :wink:


What are some book that you would recommend for someone who is about to take the Putnam for the first time.

I alredy have The Art and Craf of Problem Solving.

Get a collection of past problems.  The newest is pretty good.

For past problems, AMC's website has the exams back to 1985 on there with solutions back to 1995: http://www.unl.edu/amc/a-activities/a7-problems/putnam/-pindex.html .

Yup, but the 'official book' has more detailed solutions and goes back further.  I don't personally own a copy, but I've looked through it several times and can say it's well worth owning.

In addition, I think it is a very good idea to refer to notes/ handouts posted by math teams from other colleges/universities. This was of tremendous help to me last year when I created a homepage just for this very purpose here: http://www.student.suu.edu/~vishallama

Of course, the following books are a must (in my opinion):

1. "The William Lowell Putnam Mathematical Competition 1985-2000 : problems, solutions, and commentary" by Kedlaya, Poonen and Vakil.
2.  "The William Lowell Putnam Mathematical Competition : problems and solutions, 1965-1984" by Alexanderson, Klosinski and Larson.
3.  "The William Lowell Putnam mathematical competition : problems and solutions :1938-1964" by Gleason, Greenwood and Kelly.
4. "Problem-Solving Through Problems" by Loren Larson.
5. "Problem-Solving Strategies" by Arthur Engel.

There are, of course, other good books for the Putnam. Above all, the Putnam forum as well as other related forums on this site are awesome!

Cheers!


Prove that in any triangle the two Brocard points, the circumcenter, and the Lemoine point are concyclic. :roll:  :P

Dear Mathlinkers,
this circle is known as the Brocard's circle and has for diameter the segment havinf for extremity the circumcenter and the Lemoine's point.
Brocard itself give the name of the five points circle.
Find the fifth point and you will found the solution.
Sincerely
Jean-Louis


An ant walks on the plane as follows: initially, it walks 1 cm in any direction. After, each step, it changes the direction of the path at 60º to the left or right and walk 1 cm in that direction.
It may return to the point where they broke into
(a) 2008 steps?
(b) 2009 steps?

It is simple to get that the ant is moving at the hexagon lattice. His movement trajectory is a (not necessary convex) polygon with angles of two possible values: $ \frac{2\pi}{3}$ and $ \frac{4\pi}{3}$. Denote by $ a$ the number of $ \frac{2\pi}{3}$ angles and by $ b$ the number of $ \frac{4\pi}{3}$ angles. Then
\[ a\frac{2\pi}{3}\plus{}b\frac{4\pi}{3}\equal{}\pi(a\plus{}b\minus{}2),\]
whence $ a\minus{}b\equal{}6$, and we obtain $ a\plus{}b\vdots 2$. So the answer in (b) is negative. Also it's easy to find a closed movement trajectory with lengthes $ 6$ and $ 10$, so walking at the first way $ 3$ times and at the second way $ 199$ times we get the ant trajectory needed in (a).  :roll:

[geogebra]132b866c88bf9917a3f4de293ce3ce3b081d460d[/geogebra]


Hello, To all mathlinkers!
Is there any link that has information, about students solving the problems?
Abdurashid

hmm... wrong place  [url=http://www.mathlinks.ro/index.php?f=452]here[/url] are some discussions


number theory
least common multiple
modular arithmetic
articles

Find the largest number that cannot be obtained while adding the numbers $ 4$,$ 5$ and $ 7$ infinitely for each (nope not the get fat theorm)

are you supposed to find the lcm of the three sums of the two numbers and subtract one? i get $ lcm(9,11,12)-1$ which equals $ 91111$. (please dont ask where i got that)

[quote="abacadaea"]are you supposed to find the lcm of the three sums of the two numbers and subtract one? i get $ \text{lcm}{9}{11}{12}-1$[/quote]
 :huh:
How in the world did you come up with that?  I mean, it's good to make conjectures and find patterns, but this has no basis at all.  You should at least test your new ideas a little before using them to solve a problem.

well, i have no idea what the chicken Mcnuggets theroem is and i cant relate to it in any way. so on a problem like this, im basically stuck, but its worth a try :)

You're not stuck.  Try making a table and finding patterns. :)

[quote="nhansen"]By "adding...infinitely" do you mean adding a non-negative integer multiple of each?  I've never heard the phrase before.
                                                     Thanks![/quote]
Yes, I believe that was the intended meaning.

[quote="i_like_pie"]Question re-phrased mathematically: Find the largest integer $ n$ such that there are no non-negative $ (a,b,c)$ such that $ 4a+5b+7c=n$.

[hide="Solution"]The numbers 10 through 20 can all be made; therefore any number greater than 20 can also be made (by adding a multiple of 10 to one of the numbers 10-20). 9, 8, and 7 can all be made. Therefore, the largest number than cannot be made is $ 6$.[/hide][/quote]

It's easier just to consider $ \pmod{4}$.

[hide="Simpler solution"]$ 7 = 7$
$ 8=2\cdot 4$
$ 9=4+5$
$ 10=5+5$

Now, to get anything bigger than $ 10$, just add a multiple of $ 4$ to one of these. For example, to get $ 91111$, you just do:
$ 91111 = 7+91104 = 7+4\cdot 22776$

So, every number bigger than $ 6$ can be attained. But $ 6$ is impossible, so that must be the answer.

In general, there is no formula, but if I had to do something like this, I would just pick the smallest coefficient in that modulo.[/hide]

That works also, and (manages to admit) is faster. :)

How about: Same question, but now the numbers are $ 6$, $ 7$, and $ 9$.

Similar, but a bit harder.

[quote="mihail911"]im not really understanding vishalarul's answer..can someone explain it a little more indepth?

thanks![/quote]
Basically he did the same thing as I did (if you understand my solution), but his solution is a bit faster.

I found ten consecutive integers than can be made, the first one being 10, which makes every other integer possible to make.

His solution only required four consecutive integers, because you can then add a multiple of four to them and make every other integer.

[quote="erdogankerem123"][quote="t0rajir0u"]As far as the Chicken McNugget Theorem goes, there is an analogue for three numbers, but it's complicated.  I believe it wasn't discovered until 1978.  And for those of you who really want to sound smart discussing this problem, the general case is called the [url=http://mathworld.wolfram.com/CoinProblem.html]coin problem[/url].[/quote]
In the above link to "coin problem", I didn't really understand what it meant when it says "where the $ x_{i}$ are nonnegative integers giving the numbers of each coin used." What does that mean?[/quote]
The $ x_{i}$ are coefficients of $ a_{i}$. They represent how many times each coin is added. They are non-negative integers because you can't add a coin a negative amount of times.

...so you don't know what $ x_{i}$ is, do you ?

Nope.  The $ x_{i}$ just represent how many of each "coin" (or, equivalently, how many boxes of each different partition of chicken nuggets) you have.

ok, so did the article ever describe how to do it for n=3?
I also didn't get the part about the total number of such unrepresentable amounts. What is "N" ?
(I really suck at interpreting this article, and math terminology in general :( )

[quote="erdogankerem123"]I also didn't get the part about the total number of such unrepresentable amounts. What is "N" ?
(I really suck at interpreting this article, and math terminology in general :( )[/quote]

In that paragraph, $ N$ was the largest amount that couldn't be represented.  And don't sweat it.  MathWorld wasn't designed to be that easy to read :)

[quote="erdogankerem123"]ok, so did the article ever describe how to do it for n=3?[/quote]
No, it just says that there is a solution, which was found in 1978.

[quote="erdogankerem123"]I also didn't get the part about the total number of such unrepresentable amounts.[/quote]
For two coins with values $ a_{1}$ and $ a_{2}$, the total number of unrepresentable amounts is given by $ \frac{\left(a_{1}-1\right)\left(a_{2}-1\right)}2$.


[quote="Philip_Leszczynski"]I think I got a cool solution to number 5 using 3D vectors...

On another note, my solution to #4 is 3^r-2, 2*3^r-2 for r>=1. (So this includes r=1). Do you think they'll knock off a point for that?[/quote]
including $r = 1$ is trivial, and isn't strictly speaking a mistake (though it's unnecessary as the problem says you can exclude it), so only the grumpiest grader in the world (and one who doesn't really understand the point of grading these things) would take a point off just for that.

It's not a mistake for the formula to include $n=1$. The problem states that $n>2$, so stating in your solution that $n\not=1$ is redundant.


algebra
polynomial
function
number theory
greatest common divisor
modular arithmetic

Prove that for all positive integers $ n$ and all odd positive integers $ k$,

$ 1\plus{}2\plus{}\cdots \plus{} n | 1^k \plus{} 2^k \plus{} \cdots \plus{} n^k$.

 :)

First off, $ 1\plus{}2\plus{}\cdots \plus{} n \equal{} \frac{n(n\plus{}1)}{2}$.
The wikipedia page for Faulhaber's formula [url]http://en.wikipedia.org/wiki/Faulhaber%27s_Formula[/url] mentions this fact, but does not prove it: "[Faulhaber] did know at least the first 17 cases and the fact that when the exponent is odd, then the sum is a polynomial function of the sum in the special case that the exponent is 1".  A few cases of this theorem are then given: [url]http://en.wikipedia.org/wiki/Faulhaber%27s_Formula#Faulhaber_polynomials[/url].

[hide="solution"]I show that if $ n$ is even, it is true. The case $ n$ odd is similar.
Let $ s_k(n) \equal{} 1^k \plus{} \ldots \plus{} n^k$.
Clearly $ \text{gcd}(n/2,n \plus{} 1) \equal{} 1$, so that if $ n/2\mid s_k(n)$ and $ n \plus{} 1\mid s_k(n)$ then $ n(n \plus{} 1)/2\mid s_k(n)$

Consider $ s_k(n)\pmod{n \plus{} 1}$: it looks like $ 1^k \plus{} 2^k\ldots \plus{} \left(\frac {n}2\right)^k \plus{} \left(\frac { \minus{} n}2\right)^k \plus{} \ldots \plus{} ( \minus{} 2)^k \plus{} ( \minus{} 1)^k$ which is 0 since $ k$ is odd.
Also consider $ s_k(n)\pmod{n}$. Things cancel similarly but we are left with a $ (n/2)^k$ in the middle, so $ s_k(n)\equiv (n/2)^k\pmod n$ so $ s_k(n) \equal{} mn \plus{} (n/2)^k$ for some integer $ m$ and $ n/2$ clearly divides that.[/hide]

EDIT: Fixed typo

[quote="caffeineboy"][hide="solution"]I show that if $ n$ is even, it is true. The case $ n$ odd is similar.
Let $ s_k(n) \equal{} 1^k \plus{} \ldots \plus{} n^k$.
Clearly $ \text{gcd}(n/2,n \plus{} 1) \equal{} 1$, so that if $ n/2\mid s_k(n)$ and $ n \plus{} 1\mid s_k(n)$ then $ n(n \plus{} 1)/2\mid s_k(n)$

Consider $ s_k(n)\pmod{n \plus{} 1}$: it looks like $ 1^k \plus{} 2^k\ldots \plus{} \left(\frac {n \plus{} 1}2\right)^k \plus{} \left(\frac { \minus{} n \minus{} 1}2\right)^k \plus{} \ldots \plus{} ( \minus{} 2)^k \plus{} ( \minus{} 1)^k$ which is 0 since $ k$ is odd.
Also consider $ s_k(n)\pmod{n}$. Things cancel similarly but we are left with a $ (n/2)^k$ in the middle, so $ s_k(n)\equiv (n/2)^k\pmod n$ so $ s_k(n) \equal{} mn \plus{} (n/2)^k$ for some integer $ m$ and $ n/2$ clearly divides that.[/hide][/quote]

I like your train of thought but $ \frac {n \plus{} 1}{2}$ is NOT an integer for $ n$ even.  Instead we should sum up to $ (n/2)^k$ and then note that $ (n/2 \plus{} 1)^k \equiv ( \minus{} n/2)^k \pmod{n \plus{} 1}$ so we have $ s_k(n) \equiv 1^k \plus{} 2^k \plus{} \cdots \plus{} \bigg(\frac {n}{2}\bigg)^k \plus{} \bigg( \minus{} \frac {n}{2}\bigg)^k \plus{} \cdots \plus{} ( \minus{} 2)^k \plus{} ( \minus{} 1)^k \equiv 0 \pmod{n \plus{} 1}$.

Similarly, $ n/2 \plus{} 1 \equiv \minus{} n/2 \plus{} 1 \pmod{n}$ so $ s_k(n) \equiv 1^k \plus{} 2^k \plus{} \cdots \plus{} \bigg(\frac {n}{2}\bigg)^k \plus{} \bigg( \minus{} \Big(\frac {n}{2} \minus{} 1\Big)\bigg)^k \plus{} \cdots \plus{} ( \minus{} 2)^k \plus{} ( \minus{} 1)^k \plus{} 0^k \equiv \frac {n^2}{4} \equiv 0 \pmod{n}$

And then we can consider $ n$ odd, which should work out similarly.

I just realized that I wrote $ (n/2)^k \equal{} n^2/4$ (stupid!).  And then I said that this is equivalent to $ 0$ in mod $ n$.  Is that necessarily true?

Now I'm being stupid again... it is not necessarily true, but we can use mod $ n/2$ instead!  :)

Advice: do math while awake!


number theory
greatest common divisor
number theory proposed

let x,y,z be positive integers such that
\[ \frac{1}{x}\minus{}\frac{1}{y}\equal{}\frac{1}{z}\]
let h be the greatest common divisor of x,y,z.Prove that $ hxyz$ and $ h(y\minus{}x)$ are perfect squares.
it can be easy for this section i took it from 104 number theory introductory section but i couldnt understand the solution of it

[quote="mehmetcantu"]let x,y,z be positive integers such that
\[ \frac {1}{x} \minus{} \frac {1}{y} \equal{} \frac {1}{z}
\]
let h be the greatest common divisor of x,y,z.Prove that $ hxyz$ and $ h(y \minus{} x)$ are perfect squares.
it can be easy for this section i took it from 104 number theory introductory section but i couldnt understand the solution of it[/quote]

Let $ x\equal{}hx_1, y\equal{}hy_1,z\equal{}hz_1$, where $ h\equal{}gcd(x,y,z)$
So what we need to prove becomes $ x_1 y_1 z_1$ and $ y_1\minus{}x_1$ are perfect squares such that $ \frac{1}{x_1}\minus{}\frac{1}{y_1}\equal{}\frac{1}{z_1}$.
Rewrite it as $ z_1\equal{}\frac{x_1 y_1}{y_1\minus{}x_1}$ and let $ x_1\equal{}kx_2, y_1\equal{}ky_2$, where $ k\equal{}gcd(x_1,y_1)$
Then we get $ z_1\equal{}\frac{k(x_2 y_2)}{y_2\minus{}x_2}$, so $ k\equal{}1,y_2\minus{}x_2\equal{}1$(thus $ x_1 y_1 z_1\equal{}z_1 ^2, y_1\minus{}x_1\equal{}1^2$) or $ k\equal{}y_2\minus{}x_2$(thus $ x_1 y_1 z_1\equal{}k^2 z_1 ^2, y_1\minus{}x_1\equal{}k^2$ ) to make $ z_1$ an integer as $ y_2\minus{}x_2 \nmid x_2 y_2$ or $ x_2$ and $ y_2$ has a common divisor.

I think this should be detailed enough. If you still don't understand, please tell me which part you don't understand.


Let $ a,b,c,d>0$,prove that
$ {\frac {c\minus{}a}{a\plus{}d}}\plus{}{\frac {d\minus{}a}{a\plus{}b}}\plus{}{\frac {d\minus{}b}{a\plus{}b}}\plus{}{\frac
{a\minus{}b}{c\plus{}b}}\plus{}{\frac {a\minus{}c}{c\plus{}b}}\plus{}{\frac {b\minus{}c}{d\plus{}c}}\plus{}{\frac {b\minus{}d}{d\plus{}c}}\plus{}{
\frac {c\minus{}d}{a\plus{}d}}\geq 0.$

[quote="xzlbq"]Let $ a,b,c,d > 0$,prove that
$ {\frac {c \minus{} a}{a \plus{} d}} \plus{} {\frac {d \minus{} a}{a \plus{} b}} \plus{} {\frac {d \minus{} b}{a \plus{} b}} \plus{} {\frac {a \minus{} b}{c \plus{} b}} \plus{} {\frac {a \minus{} c}{c \plus{} b}} \plus{} {\frac {b \minus{} c}{d \plus{} c}} \plus{} {\frac {b \minus{} d}{d \plus{} c}} \plus{} { \frac {c \minus{} d}{a \plus{} d}}\geq 0.$[/quote]
This is the nesobit ineq for 4 numbers!
$ \frac{a}{b\plus{}c}\plus{}\frac{b}{c\plus{}d}\plus{}\frac{c}{d\plus{}a}\plus{}\frac{d}{a\plus{}b} \ge 2$

Let $ a,b,c,d,e > 0$,prove that

$ {\frac {a \minus{} b}{b \plus{} c}} \plus{} {\frac {b \minus{} c}{c \plus{} d}} \plus{} {\frac {c \minus{} d}{d \plus{} e}} \plus{} {\frac {d \minus{} e}{a \plus{} e}} \plus{} {\frac {e \minus{} a}{a \plus{} b}}\geq 0.$

n-variable:

Let $ x_1,x_2,...,x_n > 0,n\geq 3$,prove that:
$ \frac {x_1 \minus{} x_2}{x_2 \plus{} x_3} \plus{} \frac {x_2 \minus{} x_3}{x_3 \plus{} x_4} \plus{} .... \plus{} \frac {x_{n \minus{} 1} \minus{} x_n}{x_n \minus{} x_1} \plus{} \frac {x_n \minus{} x_1}{x_1 \plus{} x_2} \geq 0.$

Let $ a,b,c,d,e>0$,prove that:
$ {\frac {a\plus{}b}{c\plus{}d\plus{}e}}\plus{}{\frac {b\plus{}c}{d\plus{}e\plus{}a}}\plus{}{\frac {c\plus{}d}{e\plus{}a\plus{}b}}\plus{}{
\frac {d\plus{}e}{a\plus{}b\plus{}c}}\plus{}{\frac {e\plus{}a}{b\plus{}c\plus{}d}}\minus{}\frac{10}{3} \geq 0.$

Let $ x_1,x_2,...,x_n > 0,n\geq3$,prove that:
$ \sum_{cyc}{\frac {\sum_{i \equal{} 1}^r{x_i}}{\sum_{i \equal{} r \plus{} 1}^s{x_i}}}\geq \frac {nr}{s \minus{} r}(n \geq s > 2r).$


algebra polynomial function induction quadratics limit integration

Prove that for any positive integer $ n$, there exists only $ n$ degree polynomial $ f(x),$ satisfying $ f(0) \equal{} 1$ and $ (x \plus{} 1)[f(x)]^2 \minus{} 1$ is an odd function.

This method might not be efficient enough.

Denote $ f_n(x)$ as the function with degree $ n$, we can have $ f_n(x)\equal{}g_n(x)\plus{}h_n(x)$, where $ g_n$ is even and $ h_n$ is odd.

$ (x\plus{}1)f(x)^2\minus{}1$ being odd implies
$ (1\plus{}x)f(x)^2\plus{}(1\minus{}x)f(\minus{}x)^2\equal{}2\Rightarrow g(x)^2\plus{}h(x)^2\plus{}2xg(x)h(x)\equal{}1$ (*)
Now we define $ g_n,h_n$ as follows:
$ g_0(x)\equal{}1$,$ h_0(x)\equal{}0$.
$ g_{2n\plus{}1}(x)\equal{}g_{2n}(x)$, $ h_{2n\plus{}1}(x)\equal{}\minus{}2xg_{2n}(x)\minus{}h_{2n}(x)$;
$ g_{2n}(x)\equal{}g_{2n\minus{}1}(x)\plus{}2xh_{2n\minus{}1}(x)$, $ h_{2n}(x)\equal{}\minus{}h_{2n\minus{}1}(x)$.

It is not hard to verify (*), $ g_n(0)\equal{}1$, $ g_n$ being even, and $ h_n$ being odd.
We proved existence.

Now we prove uniqueness by induction.
Uniqueness of $ f_0(x)$ is trivial.
Suppose $ f_{n\minus{}1}(x)$ is unique and we look at $ f_n(x)\equal{}g_n(x)\plus{}h_n(x)$.
Assume $ n$ is even. $ (g_n,h_n)$ is any pair which meets the requirement.
Then we see $ g_n$ has degree $ n$.
We also have
$ g_n^2\plus{}h_n^2\plus{}2xg_nh_n\equal{}1$.
If we look at the coefficient of $ x^{2n}$ of the above equation, we can show
$ h_n$ has degree $ n\minus{}1$ and $ g_n\plus{}2xh_n$ has degree no greater than $ n\minus{}2$.
Now we find out $ g\equal{}g_n\plus{}2xh_n$, $ h\equal{}\minus{}h_n$ also solves (*).
But we notice $ g\plus{}h$ has degree $ n\minus{}1$. Then by induction assumption, we have
$ g_n\plus{}2xh_n\equal{}g_{n\minus{}1}$ and $ \minus{}h_n\equal{}h_{n\minus{}1}$.
This shows uniqueness of $ f_n$
Similarly we can handle the case when $ n$ is odd.

Q.E.D.

All I want to say is:a perfect solution! :lol:
Siince the official solution is based on Pell Equation(defined in polynomial not integer) which is not elementary at all

Could you post the official solution of this problem,dear hxy09? :)

We will show that up to sign, there is in fact a unique polynomial in $\mathbb{R}[x]$. Let $f(x)=p(x^2)+xq(x^2)$, so $(x+1)f(x)^2-1=-[(-x+1)f(-x)^2-1]$ rewrites as $x[p(x)+q(x)]^2+(1-x)p(x)^2=1$. (*)

Let $r(x)=p(x)+q(x)$. Differentiating both sides, we have
\[r(x)[r(x)+2xr'(x)]=p(x)[p(x)+2(x-1)p'(x)].\]Clearly $\deg{p}=\deg{r}$ or else (*) can't hold (the leading coefficients must be the same up to sign), so because $\gcd(p(x),r(x))=1$, $p(x)$ must divide $r(x)+2xr'(x)$ and so there exists a constant $c$ such that $p(x)=c[r(x)+2xr'(x)]$. Plugging this into (*), we get the differential equation
\[1=[x+c^2(1-x)]r(x)^2+4c^2x(1-x)r'(x)r(x)+4c^2x^2(1-x)r'(x)^2.\]From the quadratic formula, we find
\[r'(x)=-\frac{c(x-1)r(x)\pm\sqrt{(x-1)[xr(x)^2-1]}}{2cx(x-1)},\]or letting $s(x)=r(x)\sqrt{x}$ so that $2xr'(x)\sqrt{x}=2xs'(x)-s(x)$ and simplifying,
\[\frac{2cs'(x)}{\sqrt{s(x)^2-1}}=\sqrt{\frac{1}{(2x-1)^2-1}},\]where WLOG $\lim_{x\to\infty}s(x)=\infty$. Anyway, it's easy to find that
\[\int\frac{1}{\sqrt{x^2-1}}\;dx=\ln(x+\sqrt{x^2-1})+C,\]so for some constant $C_0$ we have
\[c\ln(s(x)+\sqrt{s(x)^2-1})=\ln(\sqrt{x}+\sqrt{x-1})+C_0,\]i.e.
\[\frac{1}{s(x)-\sqrt{s(x)^2-1}}=s(x)+\sqrt{s(x)^2-1}=e^{C_0/c}(\sqrt{x}+\sqrt{x-1})^{1/c},\]so there exist constants $C_1,C_2$ such that
\[r(x)=\frac{e^{C_1}(\sqrt{x}+\sqrt{x-1})^{C_2}+e^{-C_1}(\sqrt{x}-\sqrt{x-1})^{C_2}}{2\sqrt{x}}.\]Since $r$ is a polynomial, we clearly have $C_2\in\mathbb{Z}$ and thus $C_1=0$. Now we can easily compute $f(x)=(1-x)p(x^2)+xr(x^2)=T_{n+1}(x)-(x-1)U_n(x)$ (up to sign of course).

Note that (*) rearranges to the Pell equation $u(x)^2-(x^2-1)v(x)^2=1$ upon the substitutions $u(x)=xr(x^2)$, $v(x)=p(x^2)$, which is a bit cleaner to do with differentiation.

Solution from [i]Twitch Solves ISL[/i]:

Suppose the polynomial $P$ obeys \[ 2 = (x+1)P(x)^2 + (-x+1)P(-x)^2. \] Work in ${\mathbb R}[y, y^{-1}]$ and substitute \[ x = \frac{1}{2}\left( y + \frac 1y \right). \] Then the above equation can be rewritten as \begin{align*} 4 &= \left( y + \frac 1y + 2 \right) P(x)^2 - \left( y + \frac 1y - 2  \right) P(-x)^2 \\ \iff 4y &= \left( (y+1) P(x) \right)^2 - \left( (y-1) P(-x) \right)^2 \\ \iff 4y &= \Big( (y+1) P(x) + (y-1) P(-x) \Big) \Big( (y+1) P(x) - (y-1) P(-x) \Big). \end{align*} Using factorization in ${\mathbb R}[y, y^{-1}]$, we see there must exist an integer $d \ge 0$ and a nonzero real number $\varepsilon$ such that we have identities \begin{align*} 2\varepsilon \cdot y^{d+1} &= (y+1) P(x) \pm (y-1) P(-x) \\ \frac 2\varepsilon \cdot y^{-d} &= (y+1) P(x) \mp (y-1) P(-x) \end{align*} for some opposite choice of signs $\pm$. Replacing $y$ with $1/y$, it follows $\varepsilon = \varepsilon^{-1} \implies \varepsilon = \pm 1$. So the system of equations is equivalent to \begin{align*} y^{d+1} + y^{-d} &= \varepsilon (y+1) P(x) \\ y^{d+1} - y^{-d} &= \pm \varepsilon (y-1) P(-x) \end{align*} Now, the first equation implies that \begin{align*} \varepsilon P(x) &= \frac{y^{d+1}+y^{-d}}{y+1} \\ &= \left( y^d + \frac{1}{y^d} \right) - \left( y^{d-1} + \frac{1}{y^{d-1}} \right) + \dots + (-1)^{d-1} \left( y + \frac 1y \right) + (-1)^d. \end{align*} The theory of Chebyshev polynomials guarantees that $y^k + \frac{1}{y^k}$ is a degree-$k$ polynomial in $x$ for each $k \ge 0$. Hence we see there is a unique choice of polynomial $P$ of degree $n$ (corresponding to $d=n$) which makes the identity $P(x) = \varepsilon \frac{y^{d+1}+y^{-d}}{y+1}$ true, for each $\varepsilon \in \{\pm1\}$. When we add the condition $P(0) = 1$ (set $y=i$ so $x=0$), we find only one $\varepsilon \in \{\pm1\}$ is valid.
Conversely, we have the implication \[ \varepsilon (y+1)P(x) = y^{d+1} + y^{-d} \implies \varepsilon (y-1)P(-x) = \pm (y^{d+1} - y^{-d}) \] which follows readily by making the substitution $y \mapsto iy$. So the choice of polynomial $P$ we just mentioned will satisfy the entire system, ergo (reversing the logic above) will satisfy the desired condition. In other words, the unique possibility for $P$ does indeed work.

[b][color=red]Remark:[/color][/b] The first few actual polynomials $P$ are: \begin{align*} P(x) &= 1 \\ P(x) &= 1 - 2x \\ P(x) &= 1 + 2x - 4x^2 \\ P(x) &= 1 - 4x - 4x^2 + 8x^3 \\ P(x) &= 1 + 4x - 12x^2 - 8x^3 + 16x^4. \end{align*}


geometry
3D geometry
number theory proposed
number theory

[quote="Fermat -Euler"]Find the smallest positive integer $n$ such that for every integer $m \geq n$, it is possible to partition a given square into $m$ squares, not necessarily of the same size.[/quote]

$n = 6$
There is no such partition only for $m = 2$, $3$, $5$.
Easily if it exists for $m$ then we have one for $m+3$ - just divide an existing square in $4$ half-sided squares.
Check such partitions for $m = 6$, $7$, $8$.

The problem is quite trivial, but what I want to point here is the same problem, but with cubes instead of squares, which still gave headeaches to the mathematicians - it is supposed to be $n=48$ if I remember well, but not all of them agree with... ;)
Of course the problem can be extended in $k$-th dimensional case wit h hyper-cubes... does anybody want to try it... ?!?  :o


calculus
integration
real analysis
real analysis unsolved

[quote="didilica"]Hi,
Can this integral be evaluated in terms of well-known constants?

$\int_{0}^{1}\ln(1-x) \ln(x) \ln(1+x) \,dx=$

Didi[/quote]

Yep! I used [url=http://www.hostsrv.com/webmab/app1/MSP/quickmath/02/pageGenerate?site=quickmath&s1=calculus&s2=integrate&s3=advanced]www.quickmath.com[/url] to get this:

[url=http://ezimagecenter.com/out.php/i142_aLogarithmicIntegral.jpeg][img]http://ezimagecenter.com/out.php/t142_aLogarithmicIntegral.jpeg[/img][/url]


modular arithmetic
algorithm
LaTeX
function
Gauss
number theory

$ (a \plus{} b) \pmod{m} \equiv a \pmod{m} \plus{} b \pmod{m}$
$ ab \pmod{m} \equiv (a \pmod{m} )( b \pmod{m})$

[b]How do you prove these properties????????[/b]

[hide="Click here to see my work"] Can these properties be true based on the definition - two numbers are congruent mod m iff the two numbers in question have the same last digit in base m? I can't prove it with the definition, but I feel that it may play a huge role in the proof.[/hide]

I don't quite understand either: the only correct way to express the first one is $ (a \plus{} b)\equiv a \plus{} b\pmod m$ or something, which I think is just a bit trivial... :wink:

I didn't understand how can he have 2 (mod m) on one side of the equality.

What he meant was, for example:

$ 72 \equiv 2 \pmod{5}$
$ 34 \equiv 4 \pmod{5}$

$ 72 \cdot 34 \equiv 2 \cdot 4 \pmod{5}$

Oh. Then if we have $ a\equiv b\pmod m\implies a\equal{} jm\plus{}b$ and $ c\equiv d\pmod m\implies c\equal{} km\plus{}d$ for some integers $ j$ and $ k$, we can add these two relations to get

$ a \plus{} c  \equal{} (j\plus{}k)m\plus{}b\plus{}d\implies a \plus{} c \equal{} b \plus{} d\pmod m$, or multiply to get

$ ac \equal{} jkm^2 \plus{} djm \plus{} bkm \plus{} bd\implies ac\equiv bd\pmod m$.

Thanks for everyone who answered!  :lol:

I'm sorry I did not formulate my question more clearly...  :blush:

Anyway, math154, I was not actually looking for that proof (thanks for posting it anyway  :) ) as it is on http://www.artofproblemsolving.com/Forum/viewtopic.php?t=246593

And for the people who had questions - my real question was this: please refer to page 6 of this link - http://www.artofproblemsolving.com/Books/Vol1/exc1.pdf - and my question was: how do you prove properties 5 and 6??????????

Sorry again for not making my question more clear. But thanks, once again, to everyone who answered.  :D

This is a strange usage of notation, though I don't know of a better way of getting the point across. Still, I'm surprised they used this in AoPS. Their notation is; $ a \pmod{b}$ means "any number equivalent to $ a$ modulo $ b$"

Let's translate this into more common notation, first. The problem statement is:

[b]Given that:[/b]
$ a,b,a',b' \; \in \mathbb{Z} \qquad \leftarrow \; \mathbb{Z} \; \text{means "Integers"}$
$ a \equiv a' \pmod{m}$
$ b \equiv b' \pmod{m}$

[b]Show that:[/b]
$ a \plus{} b \equiv a' \plus{} b' \pmod{m}$
$ ab \equiv a'b' \pmod{m}$.

[b]Re-writing the givens:[/b]

Using the definition of "modulo", we can rewrite the givens,
which are given as modular arithmetic [i]equivalences[/i], as algebraic [i]equations[/i],
by introducing two new unknown integer variables, $ h$ and $ k$:

$ a \equiv a' \pmod{m} \implies a \equal{} a' \plus{} hm$ for some integer $ h$
$ b \equiv b' \pmod{m} \implies b \equal{} b' \plus{} km$ for some integer $ k$

[b]For Property 5:[/b]

$ a \plus{} b \equal{} (a' \plus{} hm) \plus{} (b' \plus{} km) \equal{} a' \plus{} b' \plus{} (h \plus{} k)m$

Since $ a' \plus{} b'$ and $ a' \plus{} b' \plus{} (h \plus{} k)m$ differ by an integer multiple of $ m$, they are equivalent modulo $ m$.

$ \therefore a \plus{} b \equiv a' \plus{} b' \plus{} (h \plus{} k)m \equiv a' \plus{} b' \pmod{m}$

[b]For Property 6:[/b]

$ ab \equal{} (a' \plus{} hm)(b' \plus{} km) \equal{} a'b' \plus{} b'hm \plus{} a'km \plus{} hkm^2 \equal{} a'b' \plus{} (b'h \plus{} a'k \plus{} hkm) m$

Since $ a'b'$ and $ a'b' \plus{} (b'h \plus{} a'k \plus{} hkm) m$ differ by an integer multiple of $ m$, they are equivalent modulo $ m$.

$ \therefore ab \equiv a'b' \plus{} (b'h \plus{} a'k \plus{} hkm) m \equiv a'b' \pmod{m}$

===============
==EXAMPLES: ====
===============

[b]Q:[/b] What is $ 1260 \pmod{34}$?

[b]A1:[/b] [i]Using property 5[/i]
$ 1260 \equiv 340 \plus{} 340 \plus{} 340 \plus{} 240 \equiv 0 \plus{} 0 \plus{} 0 \plus{} 240$
$ \equiv 34 \plus{} 34 \plus{} 34 \plus{} 34 \plus{} 34 \plus{} 34 \plus{} 34 \plus{} 2 \equiv 0 \plus{} 0 \plus{} 0 \plus{} 0 \plus{} 0 \plus{} 0 \plus{} 0 \plus{} 2 \equiv 2 \pmod{34}$

[b]A2:[/b] [i]Using property 6[/i]
$ 1260 \equiv 35 \cdot 36 \equiv 1 \cdot 2 \equiv 2 \pmod{34}$

It is a strange use of notation; one way to be cleaner is to denote the equivalence class of a residue $ a \pmod{n}$ as $ [a]$, and then the problems can be stated as $ [a\plus{}b] \equal{} [a] \plus{} [b]$ and $ [ab] \equal{} [a][b]$, where operations in the brackets are standard integer operations and outside are as defined in modular arithmetic.

Again,

Thanks for everyone who answered!  :lol:

I'm sorry I did not formulate my question more clearly...  :blush:

Anyway, I was not actually looking for that proof (thanks for posting it anyway  :) ) as it is on http://www.artofproblemsolving.com/Forum/viewtopic.php?t=246593

[b]And for the people who had questions - my real question was this: please refer to page 6 of this link - http://www.artofproblemsolving.com/Books/Vol1/exc1.pdf - and my question was: how do you prove properties 5 and 6??????????[/b]

Sorry again for not making my question more clear. But thanks, once again, to everyone who answered.  :D

[quote="#5-1Mole"]I've been reading this, and what should anyone now?[/quote]

????????????????

ummm.... would anyone like to answer my post?????

Which of your posts? They were all about 2 congruence properties, which were answered.

Again,

Thanks for everyone who answered!

I'm sorry I did not formulate my question more clearly...

Anyway, I was not actually looking for that proof (thanks for posting it anyway  ) as it is on http://www.artofproblemsolving.com/Forum/viewtopic.php?t=246593

[b]And for the people who had questions - my real question was this: please refer to page 6 of this link - http://www.artofproblemsolving.com/Books/Vol1/exc1.pdf - and my question was: how do you prove properties 5 and 6?????????? [/b]

Sorry again for not making my question more clear. But thanks, once again, to everyone who answered.

No, your question is very clear, everyone understands your question.

The proof I posted, which is just a more thoroughly explained version of the proof you linked, is exactly the proof you are looking for. Properties 5 and 6 there are [i]the same[/i] as the statements I proved, and the statements in the thread you linked.

If you do not understand why, try to think about what it means for two numbers to be equivalent modulo another number.

The rationale is simple -- if these properties hold for [i]any[/i] two pairs of equivalent numbers (the wording of the proof I gave), then they must hold true for [i]every[/i] selection of two pairs of equivalent numbers (the wording of properties 5 and 6), and vice versa. They are equivalent statements.

Thanks for the reply! :)

ohh....  :blush:

I mistook your proof to be the proving the statement made in this link: http://www.artofproblemsolving.com/Forum/viewtopic.php?t=246593 .

I'm still having problems connecting statements [b]5 and 6  of this link :http://www.artofproblemsolving.com/Books/Vol1/exc1.pdf. [/b]

Perhaps it would be a good idea for me to state exactly what I don't understand so that it would be easier for people to help me. In TZF's proof, TZF proved these two statements: a + b = a' + b' (mod m) and ab = a'b' (mod m). The statements that were supposed to be proved were these two: $ (a \plus{} b) \pmod{m} \equiv a \pmod{m} \plus{} b \pmod{m}$ and $ ab \pmod{m} \equiv (a \pmod{m} )( b \pmod{m})$. In TZF's proof, where did the mod m after the a go and where did the mod m after the a + b go? In the proof of statement 6, where did the (mod m) after the ab go and where did the (mod m) after the a go? I guess what I'm really asking is: how does a + b = a' + b' imply $ (a \plus{} b) \pmod{m} \equiv a \pmod{m} \plus{} b \pmod{m}$ and how does ab = a'b' (mod m) imply $ ab \pmod{m} \equiv (a \pmod{m} )( b \pmod{m})$???????????

I would greatly appreciate it if someone could explain this problem to me and I thank you in advance.

The difference is that they are using $ \pmod{m}$ as an operator, while I am rewriting the statements in standard modular arithmetic notation. These are two different meanings of the notation, which is likely the root of your confusion. These meanings are explained below:

1. As an operator, modulo works just like the "%" command in languages such as C and Java. It means, "the remainder of a upon division by m".

2. In modular arithmetic, a line is followed by (mod __) as a declaration of the number system in which we are working (ex. in the mod-5 number system, all numbers are equivalent to one of 0, 1, 2, 3, or 4).

These are two [i]different[/i] uses of the symbol $ \pmod{m}$. Most of the time around AoPS and in contest mathematics, you will see the particular phrase $ \pmod{m}$ used in the second sense -- as a number system declaration at the end of a line, rather than as an operator.

Before going any further, I'm going to rewrite properties 5 and 6 using the notation "%" as the modulo [i]operator[/i], and using $ \pmod{m}$ as an number system [i]declaration[/i], to remove all ambiguity. This does not involve any math, only clarifying the symbols used:

[b]Property 5:[/b] $ (a \plus{} b) \% m \; \equiv \; a \% m \; \plus{} \; b \% m \; \pmod{m}$
[b]Property 6:[/b] $ (ab) \% m \; \equiv \; (a \% m) (b \% m) \; \pmod{m}$

Make sure you understand what the above two properties are saying (keeping in mind the definition of the modulo operator "%") before reading on.

Note that for any integer $ N$, we have $ N \equiv N \% m \pmod{m}$. Make sure you understand why this is the case before reading in.
For example, suppose $ N \equal{} 11$ and $ m \equal{} 3$. $ N \% m \equal{} 2$. Then, I would be asserting here that $ 11 \equiv 2 \pmod{3}$. If you do not understand why this is always the case, revisit the definition of congruence in modular arithmetic.

1. Now, I will plug the numbers in the rewritten form of properties 5 and 6 into the proof I provided earlier. In that proof, I proved that for [i]any[/i] $ a'$ satisfying $ a \equiv a' \pmod{m}$ and [i]any[/i] $ b'$ satisfying $ b \equiv b' \pmod{m}$, the following statements are true:

$ a \plus{} b \equiv a' \plus{} b' \pmod{m}$
$ ab \equiv a'b' \pmod{m}$

2. Because $ a \% m$ and $ b \% m$ satisfy all the requirements for $ a'$ and $ b'$, respectively, we can consider the specific case of my result, when $ a' \equal{} a \% m$ and $ b' \equal{} b \% m$. This gives:

$ a \plus{} b \equiv a \% m \; \plus{} b \% m \; \pmod{m}$
$ ab \equiv (a \% m) (b \% m) \pmod{m}$

3. Note, that since $ N \equiv N \% m \pmod{m}$ for all integers $ N$, we must have that:

$ a \plus{} b \equiv (a \plus{} b) \% m \pmod{m}$
$ ab \equiv (ab) \% m \pmod{m}$

4. Thus, transitively:

$ (a \plus{} b) \% m \; \equiv \; a \% m \; \plus{} \; b \% m \; \pmod{m}$
$ (ab) \% m \; \equiv \; (a \% m) (b \% m) \; \pmod{m}$

as desired.

Thanks very much, TZF!!!!!!!!!!!!!  :D

I just one little question on why $ N \equiv N \% m \pmod{m}$ works. Wouldn't you need a separate proof for that?????????? [b]Can you, or anyone else, write up a proof for that statement????????[/b]

Any help is greatly appreciated and I thank you in advance.

The [url=http://en.wikipedia.org/wiki/Division_algorithm#Statement_of_theorem]Division Algorithm[/url] asserts that, given two integers $ N$ and $ m$, with $ m \neq 0$, there exist unique integers $ Q$ and $ R$ such that $ N\equal{}Qm\plus{}R$ and $ 0 \leq R < |m|$.

$ R$ as used here is nothing but $ N \% m$. So, by the division algorithm, there exists a unique integer $ Q$ such that $ N \equal{} Qm \plus{} N \% m$

This means that $ N$ and $ N \% m$ differ by an integer multiple of $ m$ (namely, $ Qm$). Thus, they are equivalent $ \pmod{m}$.

THANKS!!!!!!!!!!!!! I think I get it now! :)

Thanks for everyone who replied to this topic! :)

I just have one very quick, very simple (I hope) question.

TZF said:

[quote]
The difference is that they are using as an operator, while I am rewriting the statements in standard modular arithmetic notation. These are two different meanings of the notation, which is likely the root of your confusion. These meanings are explained below:

1. As an operator, modulo works just like the "%" command in languages such as C and Java. It means, "the remainder of a upon division by m".

2. In modular arithmetic, a line is followed by (mod __) as a declaration of the number system in which we are working (ex. in the mod-5 number system, all numbers are equivalent to one of 0, 1, 2, 3, or 4).

These are two different uses of the symbol . Most of the time around AoPS and in contest mathematics, you will see the particular phrase  used in the second sense -- as a number system declaration at the end of a line, rather than as an operator. [/quote]

My question is: Aren't the usages 1 and 2 one and the same? Can't they be shown to be same? That is, if N%m = Q%m, then doesn't it force this relation [NOTE: I am using the = sign instead of the three bar sign as I am very bad with latex] to be true by definition: N (mod m) = Q (mod m) - the mod m after the N is placed there just for emphasis - which in reality is N = Q (mod m)???????????????????? AOPS vlume 1 pg. 42-43 makes a point of this and says that the numbers are congruent iff the numbers in base m (assuming you're using mod m) end in the same digit AND two numbers are congruent iff they have the same remainder when divided by m (assuming, once again, that you're using mod m)  and says that these two definitions are one and the same...

Right. That is a definition of equivalence modulo $ m$.

Re-read the two usages I listed and try to absorb their meaning. It is like how the word "jump" can be used as either a noun or a verb -- both relate to the act of jumping, but they have different meanings, and play in differently in the grammar of a sentence.

As an operator, it is just like a function. It [i]does[/i] something -- it takes an input and produces an output. The function-call $ 11 \pmod{3}$, or $ 11 \% 3$, takes in the number $ 11$ and results in a value of $ 2$.

On the other hand, when it is being used as a declaration at the end of a modular arithmetic statement, it isn't actually doing anything. It is simply stating the number system in which the preceding statement was made. For example:
- The statement $ 11 \equiv 2$ is meaningless because we do not know in which modular system we are working.
- The statement $ 11 \equiv 2 \pmod{3}$ makes sense because it is saying "in the mod-3 number system, 11 is equivalent 2".
- The statement $ 11 \equiv 2 \pmod{5}$ is incorrect because it says "in the mod-5 number system, 11 is equivalent to 2", which is false.
As you can see, the $ \text{mod}$ clause at the end is not actually [i]doing[/i] anything -- it is only stating the number system in which we are working.

THANKS!!!!!! :)

[b]So if N%m = Q%m, then this relation [NOTE: I am using the = sign instead of the three bar sign as I am very bad with latex] is forced to be true by definition: N (mod m) = Q (mod m) - the mod m after the N is placed there just for emphasis - which in reality is N = Q (mod m)????????????????????[/b]

Are you asking if $ N \% m \equal{} Q \% m \iff N \equiv Q \pmod{m}$? If so, then yes, that is true.

We don't need the three bars in the left-side statement because they are equal in the "normal" sense, whereas on the right-side statement, the two only must be equivalent in the mod-m system.

[b]@ QuincyCello:[/b] You are likely unsure what he meant because of his usage of the "%" -- we are using this as it is used in Java -- namely, "remainder upon division by"

THANKS everyone who replied!!!!!!!!!!!!!!!! :)

[quote="theax"]$ (a \plus{} b) \pmod{m} \equiv a \pmod{m} \plus{} b \pmod{m}$
$ ab \pmod{m} \equiv (a \pmod{m} )( b \pmod{m})$

[b]How do you prove these properties????????[/b]
[/quote]

[i]If a number [b]a[/b] divides the difference of the numbers [b]b[/b] and [b]c[/b], then [b]b[/b] and [b]c[/b] are said to be congruent relative to [b]a[/b]. ... The number [b]a[/b] is called the modulus.[/i] -- Carl Friederich Gauss, [i]Disquisitiones Arithmeticae[/i], 1801.

With this definition in mind, as one of the earlier posters pointed out, your notation is a bit unusual. Since every number is congruent to itself regardless of the modulus, since, for example, $ a \equiv a \pmod{m}$ means $ m | (a \minus{} a)$. This is a no brainer as any number (other than zero) divides zero.

What it seems you meant is: Given $ a \equiv r_a \pmod{m} \text{ and } b\equiv r_b\pmod{m}$ show that $ (a \plus{} b) \equiv (r_a \plus{} r_b) \pmod{m}$.

Likewise, show $ ab \equiv r_ar_b \pmod{m}$.

This is not difficult.

Let $ a \equal{}mj \plus{} r_a$ and let $ b \equal{}mk \plus{}r_b$ then

$ (a \plus{} b) \equal{} m(j \plus{} k) \plus{} (r_a \plus{} r_b) \\ \implies m|(a \plus{} b \minus{}(r_a \plus{} r_b)) \\ \therefore (a \plus{} b) \equiv (r_a \plus{} r_b) \pmod{m}$.

Also,

$ ab \equal{} m^2jk \plus{}mjr_b \plus{} mkr_a \plus{} r_ar_b \\ \implies m|(ab \minus{} r_ar_b) \\ \therefore ab \equiv r_ar_b \quad \blacksquare$

You generally don't use the $ \equal{}$ sign in modular arithmetic because the numbers aren't necessarily equal. If you use the equal sign, proving what you're asking to prove is trivial. The reason the cogruence symbol is used to show that their residues are equal modulo $ m$ rather than the numbers themselves.

[quote="theax"]Thanks!  :lol:

It seems that all these proofs require some variant of the property on this link:
http://www.artofproblemsolving.com/Forum/viewtopic.php?t=24659[/quote]

I am not certain how number theory (modulo arithmetic) relates to the concept of continuity? Maybe you're seeing something that I do not.

Whether you see something that I do not notwithstanding, what these proofs require is knowledge of the division algorithm: Any integer $ d$ can be expressed as $ d \equal{} mq \plus{} r \quad\text{where } 0\le r < m.$

In the case above, $ m$ divides $ d \minus{}r$, written in symbols as $ m|(d \minus{} r)$, and therefore $ d$ is [i]congruent[/i] to $ r$ modulo $ m$, which is written as: $ d\equiv r\pmod{m}$.

[quote="theax"][b]A SUPER HARD CHALLENGE: Can anyone prove these properties: (a+b) (mod m) = a (mod m) + b (mod m) AND ab (mod m) = (a(mod)) (b(mod m)) [Note: I am using the = sign instead of the three bar sign because I cannot latex] WITHOUT using these properties:

"If a = b (mod m) and p = q (mod m), then:

(a+b) = (p+q) (mod m) & ab = pq (mod m)"[/b]

[/quote]

I agree that your challenge is super hard ... because it's not correct.

If $ a\equiv b$ and $ p\equiv q$ then $ (a \plus{} b)\equiv 2a\equiv 2b$, and likewise $ (p \plus{} q)\equiv 2p\equiv 2q$.

Also $ ab\equiv a^2\equiv b^2\textrm{ and } pq\equiv p^2\equiv q^2$.

For one number to be congruent to another means that both numbers have the same remainder upon division by the modulus.

Thanks for replying!
I will now attempt to clarify the confusion...
@sunehra: Please read the note near the end of my post, reproduced below:
[Note: I am using the = sign instead of the three bar sign because I cannot latex] Sorry for the confusion.

@Dr. No: Sorry, but it seems that I may have left out the 3 in the end. Sorry for the confusion. http://www.artofproblemsolving.com/Forum/viewtopic.php?t=246593

Also, sorry for the typo. What I meant for the without using these properties is:
If a = b (mod m) and p = q (mod m) then a + p = b + q (mod m) and ap = bq (mod m). NOTE: I am using a = sign INSTEAD of the three bar congruent sign because I CANNOT latex. Sorry, once again, for the confusion.

1) If $ a\equiv b(mod m)$ that means $ m\mid a\minus{}b$, also $ m\mid p\minus{}q$ so $ m\mid (a\plus{}p)\minus{}(b\plus{}q)$ so $ a\plus{}p\equiv b\plus{}q(mod m)$.
2) If $ a\equiv b(mod m)$ then $ ap\equiv bp(mod m)$. Similar $ bp\equiv bq(mod m)$. From these 2 we get $ ap\equiv bq(mod m)$

[quote="theax"]Thanks!  :lol:

It seems that all these proofs require some variant of the property on this link:
http://www.artofproblemsolving.com/Forum/viewtopic.php?t=24659

[b]A SUPER HARD CHALLENGE: Can anyone prove these properties: (a+b) (mod m) = a (mod m) + b (mod m) AND ab (mod m) = (a(mod)) (b(mod m)) [Note: I am using the = sign instead of the three bar sign because I cannot latex] WITHOUT using these properties:

"If a = b (mod m) and p = q (mod m), then:

(a+b) = (p+q) (mod m) & ab = pq (mod m)"[/b]

[hide="Click here to see my work"]
I only managed to prove the first one. Is the second one even possible?
 [hide="Click here for a hint of the first one"]
  Keep everything in base ten and, because you're in base ten, you can use the property that division distributes over addition[/hide][/hide][/quote]

Umm... This post says WITHOUT that property...

[quote="theax"]Thanks for replying!

@Dr. No: Sorry, but it seems that I may have left out the 3 in the end. Sorry for the confusion. http://www.artofproblemsolving.com/Forum/viewtopic.php?t=246593

Also, sorry for the typo. What I meant for the without using these properties is:
If a = b (mod m) and p = q (mod m) then a + p = b + q (mod m) and ap = bq (mod m). NOTE: I am using a = sign INSTEAD of the three bar congruent sign because I CANNOT latex. Sorry, once again, for the confusion.[/quote]

No worries, my friend. $ a + p \equiv b + q\quad  \&\quad ap \equiv bq$ are what I thought you meant, but one doesn't solve problems by second guessing the problem statements.

If you don't mind my asking, why can't you $ \text{\LaTeX}$ ? If you have a dollar sign character on your keyboard, you should be able to write $ \text{\LaTeX}$ code just as well as anyone else, at least in this forum.

actually, I never really bothered to learn latex, although I might soon...

Anyway, can anyone do the super hard challenge?

Note that $ (ab \mod m) \equal{} (a\mod m)\cdot(b \mod m)$ is not true if $ x \mod m$ denotes the residue class $ \{...,x\minus{}m,x,x\plus{}m,...\}$.
Try to find a counerexample  :wink:

The only way is to use the same [i]type [/i]of logic used to show that $ p \equiv p', \; q \equiv q' \pmod{m} \; \implies p\plus{}q \equiv p'\plus{}q', \; pq \equiv p'q' \pmod{m}$

These "properties 5 and 6" are just a partiular case of the above, and really, what the book was trying to [i]communicate [/i]was the above. You cannot abandon the type of logic we used because the procedure involved only basic arithmetic and the definition of modular equivalence. In fact, the only difference is that the introduced variables $ h$ and $ k$ would not be variables but unique integers as determined by the Division Algorithm, which does not even simplify the proof. In that sense, your "Super Hard Challenge" is neither useful nor "Super Hard".

Instead of remembering properties 5 and 6 in their notation, it is much more useful to just remember the more general format that several of us proved in this thread (which is at the top of this post).

interesting...
what do other people think?????????

Just remember that you can add, subtract, multiply and take natural exponents like in the integers; or in short: it's a ring  :wink:

Quote: It's a ring...

Thanks for your response! :)
but...
What do you mean?


A 40-sided polygon is drawn with each side of length 1. It is then divided into triangles, with each vertex of each triangle being a vertex of the original polygon. Let A be the area of the smallest triangle. What is the minimum number of square root signs needed to express the exact area of A?

If I'm interpreting the problem correctly, the desired triangle must have all three vertices be consecutive vertices of the 40-gon since all triangles are going to have base length 1, and such triangle will have the minimum height.
So the area is $ (1/2)\sin(19\pi/20)$ (use the formula $ 180(n \minus{} 2)/n$)
... not sure about the closed-form though...

Yeah, I got to that step, but then I got stuck too and the sine of 171 is equal to sin9. So then I looked at the answers and they were like, the value of sin18 is equal to (sqrt(5)-1)/4. Then they had a few more steps and they got the answer which is 3. I tried to use the roots of unity to find sin18, but it didn't work. Do you know how they found the numerical value of sin18.

By the way, you're not allowed to use a calculator during the contest so try not to use a calculator.

I took another look and I think I figured out a solution:

$ \sin(\pi/20) \equal{} \sqrt {\frac {1 \minus{} \cos(\pi/10)}2}$

$ \cos(\pi/10) \equal{} \sqrt {\frac {1 \plus{} \cos(\pi/5)}2}$

$ \cos(\pi/5) \equal{} \phi/2$

http://www.cut-the-knot.org/pythagoras/cos36.shtml

So right now there are indeed 3 radicals, but I don't know how to actually PROVE this representation would be of minimum radicals (which numbers 3).
(By the way what's the source of the problem?)

It's from the Rice Mathematics Test, a test held at Rice University in Houston, Texas.

  If anyone knows a formula for calculating the sine or cosine of any angle, please tell me it.

i guess u can trig bash anything infidently close... :P

[quote="MathTwo"]A 40-sided polygon is drawn with each side of length 1.
~~~
Let A be the area of the smallest triangle. [/quote]

You DIDN'T SPECIFY what kind of 40-sided polygon with sides of 1 this is!

Did you mean a REGULAR 40-sided polygon with sides of 1?

Otherwise, any "40-sided polygon" having sides of 1 could exist
where the polygon "gets squished," and its area approaches
zero.  Then the area of A, the smallest triangle, that was talked
about in this problem, would also approach zero.

Yes, sorry it is a regular 40-sided polygon with side lengths of 1.

I took another look and I think I figured out a solution:

$ \sin(\pi/20) = \sqrt {\frac {1 - \cos(\pi/10)}2}
\cos(\pi/10) = \sqrt {\frac {1 + \cos(\pi/5)}2}
\cos(\pi/5) = \phi/2$

I guess you could just substitute those in and find out if it can be simplified or not?

(i dont know how to quote but this is quoted from ealier in this thread)


Let  $p$ a prime number, $p\geq 5$. Find the number of polynomials of the form
\[ x^p + px^k + p x^l + 1, \quad k > l, \quad k, l \in \left\{1,2,\dots,p-1\right\},  \] which are irreducible in $\mathbb{Z}[X]$.

[i]Valentin Vornicu[/i]

Consider the polynomial in $\mathbb Z_p[x]$. We say that it has the factorization :
\[ x^p+1=(x+1)^p  \]
It's true because $(x+1)^p=\sum_{i=0}^p {p\choose i} x^i=x^p+1$ and $p|{p\choose i}$ for $0<i<p$.
Now suppose that in $\mathbb Z[x]$ we have
\[ x^p+px^k+px^l+1=g(x)h(x)  \].
So in $\mathbb Z_p[x]$ we must have
\[ h(x)=(x+1)^k  \]
and
\[ g(x)=(x+1)^{p-k}  \].
So we have
\[ x^p+px^k+px^l+1=((x+1)^k+pr(x))((x+1)^{p-k}+ps(x))  \]
for some $r(x),s(x)\in \mathbb Z[x]$.
But now just put $x=-1$ in the equation and we get
\[ (-1)^k+(-1)^l=pr(-1)ps(-1)  \]
So if $2|k-l$ then the lhs is $2$ or $-2$ but rhs is divisible by $p$ which is contradiction.
But if $2\nmid k-l$ then we obviously have that $x+1|x^p+px^l+px^k+1$ and so the polynomial is reducible.
So the answer is the number of $k,l$ pairs such that $2| k-l$ and that is $2{\frac{p-1}2\choose2}$.

Note that, if $k-l$ is odd, then $x+1$ divides $x^p+1$ and also $x^k+x^l$, so $P(x)$ is not irreducible. Now suppose $k=l+2r$, $r$ a positive integer. Then let $Q(x)=P(x-1)$. We'll prove that $Q(x)$ is irreducible, from which it will follow that $P(x)$ is irreducible as well.

We have $P(x-1)=(x-1)^p+p(x-1)^k+p(x-1)^l+1$. The binomial expansion of the first term produces multiples of $p$, except for the last term, which is $-1$ and cancels out with the fourth term, $1$. The binomial expansions of the middle two terms produce multiples of $p$ (obviously, since they are multiples of $p$ themselves). The last terms given by each expansion are either both $p$ or both $-p$, since $k, l$ are both even or both odd. Thus $P(x-1)=x^p+pxR(x) \pm 2p$, which is irreducible by Eisenstein's criterion. So we have to count the number of pairs $k, l$ with $k-l$ even, $p>k>l>0$. This gives $2 \times \binom{ \frac{p-1}{2}}{2}$.

[quote=Nima Ahmadi Pour]...
But if $2\nmid k-l$ then we obviously have that $x+1|x^p+px^l+px^k+1$ and so the polynomial is reducible.
...[/quote]
Why??

Wow, 10-year-old post!
It's saying that -1 is a root since $(-1)^p=-1$, and $(-1)^l$ and $(-1)^k$ have opposite signs because $l$ and $k$ have odd difference.

[quote=Eyed]The answer is when $k, l$ are same parity. Clearly if they are different parity, then $x + 1$ is a factor.

Let $f(x) = x^{p} + px^{l} + px^{k} + 1$, where $k, l$ are the same parity. By the rational root theorem, since $f(\pm1)\neq 0$, this means $f$ has no rational roots. Assume $f = g\cdot h$ for nonconstant polynomials $g, h$. Take $\mod p$ to get $g\cdot h\equiv x^{p} + 1 = (x+1)(x^{p-1} - x^{p-2} + \ldots + 1)$. Observe that $\Phi_{2p} = (x^{p-1} - x^{p-2} + \ldots + 1)$, so it is irreducible. Thus, $g\equiv x+1, h\equiv x^{p-1} - x^{p-2} + \ldots + 1\mod p$. Since the degree of $h$ is at least $p-1$, the degree of $g$ is $1$, so $g$ has a rational root, which also means $f$ has a rational root, a contradiction. Thus, $f$ is irreducible.[/quote]

$\Phi_{2p} = (x^{p-1} - x^{p-2} + \ldots + 1)$ is irreducible in $\mathbb{Z}$, but not in $\mathbb{Z}_p$.

[quote=Valentin Vornicu]Let  $p$ a prime number, $p\geq 5$. Find the number of polynomials of the form
\[ x^p + px^k + p x^l + 1, \quad k > l, \quad k, l \in \left\{1,2,\cdots,p-1\right\},  \] which are irreducible in $\mathbb{Z}[X]$.

[i]Valentin Vornicu[/i][/quote]
$\color{blue}\boxed{\textbf{Answer:}2{\frac{p-1}{2} \choose 2}}$
$\color{blue}\boxed{\textbf{Proof:}}$
$\color{blue}\rule{24cm}{0.3pt}$
$$P(x)=x^p+px^k+px^{\ell}+1$$
By Rational Root Theorem:
$P(x)$ is reducible in $Z[x]$ if $P$ has a root $x_1\in\mathbb{Z}$ such that $x_1|1$
$$\Rightarrow x_1=1 \text{ or }-1$$
$\color{red}\boxed{\textbf{If } x_1=1:}$
$\color{red}\rule{24cm}{0.3pt}$
$$\Rightarrow 1+p+p+1=0(\Rightarrow \Leftarrow)$$
$\color{red}\rule{24cm}{0.3pt}$
$\color{red}\boxed{\textbf{If } x_1=-1:}$
$\color{red}\rule{24cm}{0.3pt}$
$$\Rightarrow (-1)^p+(-1)^k+(-1)^{\ell}+1=0$$
$$\Rightarrow (-1)^k+(-1)^{\ell}=0$$
$$\Rightarrow k\not\equiv \ell \pmod{2}$$
But we want the complement, that is, the irreducibles in $Z[x]$, counting we get:
$$2 {\frac{p-1}{2} \choose 2} _\blacksquare$$
$\color{red}\rule{24cm}{0.3pt}$
$\color{blue}\rule{24cm}{0.3pt}$

The idea is to look at this polynomial $f$ in $\mathbb F_p$. Suppose that $f=gh$. Note that $$f \equiv x^p + 1 \equiv (x+1)^p,$$ so in particular $g$ and $h$ mod $p$ are both powers of $x+1$.

Now, assume for the sake of contradiction that $f(-1) \neq 0$. Then $f(-1) = 2p$, and hence $$p^2 \mid g(-1)h(-1) = 2p$$ which is an obvious contradiction.

So $k$ and $\ell$ must be the same parity, and the number of such pairs is then $\frac{(p-1)(p-3)}4$.


The special case is XY is parallel to one or both line 1/2
I missed it=.=

No, and I hope they don't actually dock for that since the projective plane covers that case.

I didn't miss it, actually. I wrote it on the paper.

But due to my utter geostupidity, that won't help me get anything above 1 on this problem.

Oh,damn, I overlooked that too. How many marks will this mistake be taken off?

[quote="chelseafc"]Oh,-, I overlooked that too. How many marks will this mistake be taken off?[/quote]
No idea, but this case does worth some points, I got the case where XY l1 and l2 intercept
Almost had everything in 1. Without this case means not completely proven it. I know it's easy to prove


linear algebra
matrix
linear algebra theorems

prove, in general, that (AB)T = BTAT

where T indicates a transpose.

Any help greatly appreciated! :^)

Perhaps you wanted to attract more people with the word "fun" in the title .... This is a trivial calculation, which can be done by everyone who has read the definitions. Besides, this question does not belong to superior algebra, rather to linear algebra.

yeah, well I'm taking a general relativity class and have little math background.  It's not trivial to me.  Should I apologize for not understanding something?


It's getting close to the AMC!!! I was wondering how each person is preparing? Also, for some of the more advanced people who are looking to make MOP or IMO, when did you notice your problem solving skills rapidly improving and what was the key to this?

my math teacher has given us 1 AHSME/AMC for hw every day for the past month... that most of my AMC prep. as for aime prep, im planning on basically doing every single aime again, or perhaps just the harder probs on each one. usamo  prep is aops classes and eventually just doing probs 24/7!!!! =P

if my prob solving skills can count as having rapidly increased, i'd have to say when i joined aops and just started doing old probs, actually intending on doing well on the aime. in 8th grade i was like aime, omg, i'll never make that, but by 9th grade i was like... gotta make USAMO... but i didnt. oh well. this year will be different :lol:. just the sheer difference in amount of math i did in 8th grade compared to 9th and 10th grade definitely helped me get better.

[quote="paladin8"]my math teacher has given us 1 AHSME/AMC for hw every day.[/quote]

OMG, your class is soooo lucky. What school do you go to?

wow, paladin8, you sure are lucky. AMC/AHSME a day will sure make your score go up. I'm reviewing the Art of Problem Solving books to try and refresh my mind on those concepts. I'm also taking practice tests (wherever i can find them) and studying the ones i get wrong. Good Luck to everybody on the AMC 10/12 and beyond!!!  :D

VERY LUCKY

I would be lucky if my teacher didn't throw useless hw on my back...

doing old tests (ASHME, AMC, AIME)

i just go to a regular public school, Bellevue High School in case you were wondering. but my math teacher used to teach at AAST and has like a billion copies of all the old AHSME's and AIME's. its really great. i better get that perfect amc10 this year =P.

Doing old exams will help. I did pretty much all of the AHSMES, AMC 10s, and AMC12s. So now, I am just going back to them and redoing the problems, hoping to get a better score. Usually, I get something like 125 on AMC 10s so I'm hoping for something in the 130 range the second time I take it. Also, reviewing AoPS volume I so I don't forget stuff on the day of the exam. Finally, redoing some old AIMEs so in case I get into AIME, I don't have to cram it all in.

Good luck to everyone! (Not that people need it.... :lol: )


parameterization
geometry
calculus
calculus computations

How would I find the parametrization of the curve x^(2/3)+y^(2/3)=1 and use it to compute the area of the interior? Thanks.

Please take a look, my post #5 [url]http://www.mathlinks.ro/Forum/viewtopic.php?p=365221#p365221[/url]


function
real analysis
real analysis unsolved

Let f be a function from X into Y, and g be a function from Y into Z. Assume that the composition g(f(x)) is onto Z.

Show that g is onto Z.

We need to show that there is an y in Y with g(y) = z.

Sinci g(f(x)) is onto, g(f(x)) = z. So, how to show that f(x) = y?

We have assumed: for any $z\in Z$ there exists $x\in X$ such that $g(f(x))=z$.

Want to prove: for any $z\in Z$ there exists $y\in Y$ such that $g(y)=z$.

Solution: let $y=f(x)$, where $x$ is such that $g(f(x))=z$.


I have the following questions.

1. Let $ X_0\equal{}0$ and $ X_{n\plus{}1}\equal{}max(X_n,W_n)$ for $ n\ge 0$ where $ W_n$'s are i.i.d. process with $ P(W_n\equal{}1)\equal{}p, P(W_n\equal{}0)\equal{}1\minus{}p, 0<p<1$
Determine in which senses (a.s., m.s., p., d.) the sequence $ {X_n}$ converges and identify the limit, if any.

2.Let $ X_0\equal{}0$ and $ X_{n\plus{}1}\equal{}X_n\plus{}W_n\minus{}p$ for $ n\ge 0$ where $ W_n$'s are i.i.d. process with $ P(W_n\equal{}1)\equal{}p, P(W_n\equal{}0)\equal{}1\minus{}p,  0<p<1$
Determine in which senses (a.s., m.s., p., d.) the sequence $ {X_n}$ converges and identify the limit, if any.

Thanks.

1. $ X_n$ takes only two value $ 0$ and $ 1$, $ X_n \equal{} max(W_1, ..., W_{n \minus{} 1})$, calculate the probability that $ X_n \equal{} 0$ you will get what you want.
2. Apply classical central limit theorem.
A similar exercise:
Let answer Q1 in case $ W_n$ has uniformly distribution on $ [0,1]$ (or standard normal distribution).