Well, Kubus got gold by scoring 536. Congrats!

But weeblie did bad! only 381 which gave him Silver.

i can't understand one thing he got only 5 in RIV... may be some uncareful mistake!

BTW, i participated at online IOI and got 399 which would manage me a silver if we did not face VISA problem! :mad:

Did anyone participate at online / real IOI?

(Simon Filip from moldova got 275 and last position for bronze)

Mahbub

Wow, 4 perfect scores, with the U.S. getting one of them.  And the U.S. got all gold medals.  That's really awesome.

Actually, I did even worse... I only got bronze (missed the silver with only 12 points!).

The first day was pretty OK (256 points, a nice number :D ) but the second day was a disaster. Missed the "order-can-be-reversed" part on the birthday task (lost 20 points :( ) and only got 5 points from rivers (had a little, little bug in my DP solution, argh!).

Could have scored 500. :(

Didn't like this years contest. Three tasks had "need-to-be-analyzed-using-pen-and-paper solutions" (MEA, REC and BIR). IOI should have at most 1 such task, otherwise the whole competition feels more like a math competition. :P

And worse of all was the 50% rule (I would like to call it more like a 60% to 70% rule). It's not worth to gamble with a "fast and clever, but not 100% verified solution" any more.

Oh! That's really shcoking news weeblie!

I must agree with Mr. Bus - MEA, REC and BIR were not too difficult problems, I even think that MEA was too easy for the IOI. Programming and informatics is all about math and the IOI problems should not be solvable just by brute-force-using of pre-learned algorithms. I liked this year's problems, although they were on the easy side. Except for the last 24 points for the MOU problem (you could get 76 for quite a simple approach).

And concerning the 50% rule, it's OK if you have a guarrantee that it is worth writing a slower solution. I think you should better write a slow and working solution than a fast and sometimes-not-working one. (Of course, some tricks and optimalizations can earn you points, I got 10 extra by writing out the best found solution before the time limit for the RIV problem;-)
However, it shouldn't be overdrawn. My teammate did a really nice and clever solution with interval trees hung on interval trees last year and earned 10 points more compared to much simpler solutions, just because only one input case was maximal and others were about 100 times smaller.

Finally, speaking about your bugs, Weeblie, I know that feeling from our qualification camp; finding a very nice model solution and getting 0 points because of a stupd bug a coupe of times taught me to be more careful and to spend some time testing. Actually, I am very happy that all I wrote at the IOI ran as I expected. Well, you have two more years to go, and what else than being 12 points below the silver line can teach you better to give more attention to the little stupid bugs;-)

[quote="bus"]MEA, REC and BIR were actually not that hard math problems, I think that a good programmer shouldn't have problems with doing a little bit of mathematics. (Well, I like math problems anyway  :) .) And the 50 % rule is in my opinion not a bad idea at all. It has actually been there all the time, they just never explicitly stated on the previous IOIs that you'll get 50 (or whatever number of) points for a slow solution. Being able to write a slow solution shows that you're better than somebody who can't write any solution at all. Although it's true that you could still get like 75 % for some really simple solutions ...
Oh, and Slovakia won 4 gold medals as well! I'm so happy ...  :lol:[/quote]

Previous years, a bad program only got 30% (never explicitly stated, as you said), now, you can get the double.

I don't mind problems that need math, too much, but 3 of them was far too many. REC was actually an excellent task of that type: if you want 100, make math solution, otherwise, DP is enough to get nearly full points. BIR wasn't all that bad either (had a very interesting solution :D ). But MEA sucked... Far too easy (just check statistics if you aren't sure... 46% had over 90 points on that task!) and only math. Definitively not (shouldn't be) a IOI task. (okay, must say that I also had 100 on MEA, before people thinks that I'm only complaining on that task becuase I failed it :P ).

I can also agree with kubus on the point that IOI problems should not be solved using "pure standard" algorithms. But, well, they never have those, do they? You must always "convert" them before using standard algorithms. ;)

DP problems are nice as well. :D

kubus: Well, bugs usually shows themselves if you only have a little debug time left... For day 1, I completed my tasks after 3.5 hours, which gave me 1.5 hours of debugging time (creating stupid solutions and generate random tests to check against them :D ). For day 2, I only had 20 minutes (wasted more than one hour on RIV, writing the wrong DP solution in the start of contest :P ).

well i am unfortunate! why this happened to me?? WHY??

i have done the GAR in normal way got 60.
MEA was ez. i got 100.
MOU was a bit tough. got 50.

So DAY1 = 210

RIV i could not find any DP soln. so made brute force and got 50
BAR i could not find O(n) soln and got 54
I found the correct startegy to solve REC but got 85. i got TLE in the last thee cases. it is a bit confusing!

And thus DAY2=189

And total 210+189=399 :?

I would easily get silver huh? :D

But badluck!

The most diffucult part this year was actually writing on US keyboards. :P

A lot of people (including me) is usually using 102-keys keyboard (on US keyboards, the button between "z" and "shift" is missing, which is a very important button). :D

Hm, I've never seen one of those 102-key keyboards. What button is it that you were missing? But I agree that the keyboard was somewhat annoying. I couldn't get used to the "\" key which was to the right of the right shift instead of above the return key. And also I've been hitting the scroll lock instead of insert quite a lot :-) .

[quote="bus"]Oh, and Slovakia won 4 gold medals as well! I'm so happy ...  :lol:[/quote]

Well, I am also surprised by Slovak team [url=http://www.ioi2005.pl/competition/results/medalists.php]IOI 2005 team results.[/url] But look Eric Price is almost performing similarly to Reid Barton in 2001, except that he is falling short of 1 one point at IMO and doesn't have a big lead wrt other competitors but a perfect score itself is also quite nice, isn't it ?!  ;)

not bad result for iran !! two silvers & two bronze !! but they could be better !!  :oops:


Here's a programming challenge inspired by [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=122446]2006 Putnam A2[/url]:

Define a subset $T$ of the nonnegative integers as follows:

$0\in T.$

For $n>0,\ n\in T$ if and only iff $n+1-t$ is composite for all $t\in T,t<n.$

The first five members of $T$ are $0,3,8,11,32.$

The challenge: find all members of $T\cap [0,N]$ for some reasonable $N.$ (The bigger the $N,$ the better the answer.)

Once that's done, do we have enough evidence to make plausible conjectures about $T?$ The one thing we do know for sure is that $T$ is infinite - that was the point of the Putnam problem. But there are other questions to ask, like what would we estimate as the asymptotic cardinality of $T\cap [0,N],$ or what powers of $2$ belong to $T.$

I don't have the environment to run it, but here's an algorithm that should be pretty good:
[hide="Algorithm"]
Step 1 (Sieve of Eratosthenes)
Create an array isprime() indexed from 2 to N+1. Set initial values equal to 1.
Loop from i=2 until i^2>N+1:
{if isprime(i)=1,
Loop from j=i until ij>N+1:
{Set isprime(ij)=0}
Else do nothing}

Now we have an array of all numbers less than or equal to $N+1$ telling us which are prime, and it took $O(N\log \log N)$ time to get there.
Use this array to build a list of all primes less than or equal to $N+1$.

Step 2 (Constructing T)
Create an array isinT() indexed from 0 to N. Set initial values equal to 1. Create an empty list T.
Loop from i=0 to N:
{if isinT(i)=1,
Append i to T. Loop over the list of primes j until i+j-1>N:
{Set isinT(i+j-1)=0}
Else do nothing}

That T should be the list of all elements of $T$ less than or equal to $N$. If there are $k$ of those and $p$ entries in the list of primes, this second part takes $O(N+pk)=O(pk)$ time. For large $N$, $p=O(\frac{N}{\log N})$.
It isn't too hard to show that $k\ge O(\log N)$: $pk+k>N$.

This should work very fast for some pretty large $N$. The only limit to worry about is memory.[/hide]

Thank you, TripleM. Your list is now the subject of a dicussion which has migrated back to the Putnam forum.

[quote="TripleM"]Its probably easy to prove, but they're all in pairs (x,x+3), heh.[/quote]

I've posted the proof [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=864683#864683]here[/url].  It was not, in fact, very hard -- the important fact is actually that they're all in pairs $(2x, 2x+3)$.  Can this be used to speed up the algorithm at all?


linear algebra
matrix
linear algebra unsolved

Let $n$ be an odd positive integer and $A$ be $n\times n$ matrix whose enteries are all either $1$ or $-1$. If $a_{i}$ be the multiply of enteries of $i$'th line and $b_{j}$ be the multiply of enteries of $j$'th column, prove that:

$\sum^{n}_{i=1}a_{i}+\sum^{n}_{j=1}b_{j}\neq 0$

is this true if $n$ is even?

This has nothing to do with linear algebra.*

I think I read the following argument in Engel:
Start with a matrix filled with 1's. Its "sum" is $2(2k+1)$. Now replace the 1's with (-1)'s where necessary. At each step the "sum" stays the same, increases by 4 or decreases by 4, so it's constant modulo 4 (it's 2). But $2 \not\equiv 0 \left( \bmod \, 4 \right)$ and that finishes it.

[quote="sinajackson"]Is this true if $n$ is even?[/quote]
No. You put 1's everywhere, except on the positions $(1,1), (2,2), \ldots, (k,k)$, where you obviously put (-1)'s.

*Or at least that's my first impression.


function
induction
number theory
Diophantine equation
combinatorics unsolved
combinatorics

A sequence of integes with $ n$ elements $ a_1,a_2,...,a_n$ is called [i]nice[/i] iff $ \forall i \equal{} \overline{1,n \minus{} 1},a_{i \plus{} 1} \plus{} a_{i} \equal{} (a_{i \plus{} 1} \minus{} a_i)^2$. Find the number of nice sequences with $ n$ elements in term of $ n$.

For an odd integer $ k$ define the function $ q(k)\equal{}\frac{k^2\minus{}1}{8}$. Rewrite the diophantine equation as $ 8x\plus{}1\equal{}(2y\minus{}2x\minus{}1)^2$, i.e. if we denote $ z\equal{}2y\minus{}2x\minus{}1$ (an odd integer), we must have $ x\equal{}\frac{z^2\minus{}1}{8}\equal{}q(z)$ and $ y\equal{}\frac{1\plus{}z}{2}\plus{}\frac{z^2\minus{}1}{8}\equal{}q(2\plus{}z)$. Conversely, all integer solutions of $ q(z)\plus{}y\equal{}(q(z)\minus{}y)^2$ with $ z>0$ are given by $ q(z)\equal{}q(w),y\equal{}q(\pm (2\plus{}w))$, i.e. $ y\in\{q(2\plus{}z),q(|2\minus{}z|)\}$ and we always have two different solutions.

For every sequence $ a_i$ with the described property we can therefore determine odd $ z_i>0$ with $ a_i\equal{}q(z_i)$ and for $ i\equal{}1,\ldots,n\minus{}1: z_{i\plus{}1}\in\{2\plus{}z_i,|2\minus{}z_i|\}$. Conversely, any such sequence fulfills the required property. We can summarise our considerations as: [b]there exists an infinite number of nice sequences and we have exactly $ 2^{n\minus{}1}$ different nice sequences with a fixed starting point $ a_1$ of the form $ q(z),z>0$ and odd[/b].

Thank you, Mr.hjbrasch. It is right that there exists infinite nice sequences. :(

Now, could you consider the case when we add one more condition to the original problem: $ a_1\equal{}a_n\equal{}0$ :idea:

[b]The answer is $ \left({n\minus{}1\atop\left[\frac{n\minus{}1}{2}\right]}\right)$[/b], where $ [x]$ denotes the largest integer smaller than or equal to $ x$. [b]I will provide a more general result[/b]: for positive integers $ n\geq 2,m\geq 0$ let $ S(n,m)\equal{}\left|\left\{(a_1,\ldots,a_n)\Big |a_i\in\mathbb{Z},a_{i\plus{}1}\plus{}a_i\equal{}(a_{i\plus{}1}\minus{}a_i)^2,a_1\equal{}\frac{m^2\plus{}m}{2},a_n\equal{}0\right\}\right|$, e.g., $ S(n,0)$ denotes the number you are after. From my previous post we have learnt that nice sequences $ a_i$ correspond to sequences $ z_i$ via the $ q$-mapping. Therefore, we can compute

$ S(n,m)\equal{}\left|\left\{(z_1,\ldots,z_n)\Big |z_{i\plus{}1}\in\{2\plus{}z_i,|2\minus{}z_i|\},z_1\equal{}2m\plus{}1,z_n\equal{}1\right\}\right|$. Note, that from $ z_i\equal{}1$ we can move to $ z_{i\plus{}1}\equal{}1,3$ and from $ z_i\equal{}2k\plus{}1>1$ to $ z_{i\plus{}1}\equal{}2(k\minus{}1)\plus{}1,2(k\plus{}1)\plus{}1$. We conclude the following recursive behavior of $ S(n,m)$.

Initialisation: $ S(2,0)\equal{}S(2,1)\equal{}1$ and everywhere else $ S(2,\ldots)$ vanishes

Recursion: $ S(n\plus{}1,m)\equal{}\left\{\begin{array}{ll}S(n,0)\plus{}S(n,1) & \mbox{if}\;m\equal{}0\\ S(n,m\minus{}1)\plus{}S(n,m\plus{}1) & \mbox{if}\;m>0\end{array}\right.$

[b]Claim[/b]: $ S(2n,m)\equal{}\left({2n\minus{}1\atop n\minus{}1\minus{}\left[\frac{m}{2}\right]}\right)$ and $ S(2n\plus{}1,m)\equal{}\left({2n\atop n\minus{}\left[\frac{m\plus{}1}{2}\right]}\right)$

[i]Proof[/i]: Via induction on $ n$ taking into account the different cases. The situation for $ S(2,\ldots)$ is easily confirmed. For $ n>1$ compute $ S(2n,0)\equal{}S(2n\minus{}1,0)\plus{}S(2n\minus{}1,1)\equal{}\left({2n\minus{}2\atop n\minus{}1}\right)\plus{}\left({2n\minus{}2\atop n\minus{}2}\right)\equal{}\left({2n\minus{}1\atop n\minus{}1}\right)$ and for $ m>0$ we have $ S(2n,m)\equal{}S(2n\minus{}1,m\minus{}1)\plus{}S(2n\minus{}1,m\plus{}1)\equal{}$ $ \left({2n\minus{}2\atop n\minus{}1\minus{}\left[\frac{m}{2}\right]}\right)\plus{}\left({2n\minus{}2\atop n\minus{}1\minus{}\left[\frac{m\plus{}2}{2}\right]}\right)\equal{}\left({2n\minus{}1\atop n\minus{}1\minus{}\left[\frac{m}{2}\right]}\right)$.

Similarly, for $ n>0$ we calculate $ S(2n\plus{}1,0)\equal{}S(2n,0)\plus{}S(2n,1)\equal{}\left({2n\minus{}1\atop n\minus{}1}\right)\plus{}\left({2n\minus{}1\atop n\minus{}1}\right)\equal{}\left({2n\atop n}\right)$ and for $ m>0$ we get $ S(2n\plus{}1,m)\equal{}S(2n,m\minus{}1)\plus{}S(2n,m\plus{}1)\equal{}$ $ \left({2n\minus{}1\atop n\minus{}1\minus{}\left[\frac{m\minus{}1}{2}\right]}\right)\plus{}\left({2n\minus{}1\atop n\minus{}1\minus{}\left[\frac{m\plus{}1}{2}\right]}\right)\equal{}\left({2n\atop n\minus{}\left[\frac{m\plus{}1}{2}\right]}\right)\;$ QED.


algebra
polynomial
absolute value
algebra proposed

Let $p\geq5$ a prime and $k$ a non-negative integer. Prove that the polynomial (only the coefficients of $X^{2^{k}\cdot(p-3)}$ and $X^{0}$ are not $1$)
$X^{2^{k}\cdot (p-2)}+pX^{2^{k}\cdot (p-3)}+X^{2^{k}\cdot(p-4)}+...+X^{2^{k}}+2$
is irreducible. Prove that the result is still true if we commute the coefficients p and 2.

By [url=http://www.mathlinks.ro/Forum/viewtopic.php?highlight=perron&t=150]this topic[/url], we get that $g = Y^{p-2}+p Y^{p-3}+Y^{p-4}+\ldots+Y+2$ is irreducible.
Furthermore, using [url=http://www.mathlinks.ro/Forum/viewtopic.php?highlight=tst+polynomial+irreducible&t=53271]this extremely nice problem[/url], we get our result ($2$ is not a square :) ).

The second also reduces to the case $k=0$, but I can't see how to solve that one right now.

PS: I don't think I can prove those results in contest :huh:

EDIT: Proving that $h = Y^{p-2}+2 Y^{p-3}+Y^{p-4}+\ldots+Y+p$ is irreducible is actually easier than proving that $g$ is irreducible. If $h$ had a root $|z| \leq 1$, then $|p| = \left| z^{p-2}+2 z^{p-3}+z^{p-4}+\ldots+z \right| \leq p-2$, contradiction. If $h = uv$, then the free term of $u$ or $v$ is $\pm 1$ (since $p$ is prime). By Viete we get that $h$ has a root of absolute value $\leq 1$, contradiction.


Show that $4\cos^{2}\theta-4\cos^{4}\theta+\cos^{2}(2\theta)=\sin^{2}(-\theta)+\cos^{2}(-\theta)$.

[hide="hint"]
$\sin^{2}\theta+\cos^{2}\theta=1$

$\sin2\theta=2\cos\theta\sin\theta$
[/hide]

I worked on it and messed up somewhere. Shobber's solution is good.


This Inequality seems very nice,but I don't know its solution.
With x,y,z>0 and :x+y+z=1
prove that:$ (ab\plus{}bc\plus{}ca)^3 \geq abc$

[quote="tuandokim"]This Inequality seems very nice,but I don't know its solution.
With x,y,z>0 and :x+y+z=1
prove that:$ (ab \plus{} bc \plus{} ca)^3 \geq abc$[/quote]
Try $ a \equal{} \frac {2}{3}$ and $ b \equal{} c \equal{} \frac {1}{6}.$ :wink:


vector
algebra
polynomial
induction
Ring Theory
superior algebra
superior algebra unsolved

Let $ R$ be a finite commutative ring. Prove that $ R$ has a multiplicative identity element $ (1)$ if and only if the annihilator of $ R$ is $ 0$ (that is, $ aR\equal{}0, \;a\in R $ imply $ a\equal{}0$).

Proof of the non-trivial implication: Let $ R\neq \{0\}$ be a commutative ring with $ Ann(R) \equal{} 0$. It suffices to show that the image of the natural algebra homomorphism
\[ \iota: R\rightarrow End_R(R), a\mapsto (x\mapsto ax)
\]
contains the identity on $ R$. Then $ \iota$ is an isomorphism, and  the identity in $ End_R(R)$ translates to the unit element of $ R$.

Let $ Ann(R) \equal{} 0$. Then $ \iota$ is injective. Since $ R$ is finite, the natural ring homomorphism $ \mathbb Z\rightarrow End_R(R)$ factors through the injection $ \mathbb Z/n\mathbb Z\hookrightarrow End_R(R)$ for some $ n > 0$. By the Chinese remainder theorem, it suffices to show the claim if $ n$ is a prime power $ n \equal{} p^r$.[hide="Because..."]If $ n \equal{} p_1^{r_1}\cdot\ldots\cdot p_s^{r_s}$ is the prime decomposition of $ n$, then the natural ring isomorphism provided by  the Chinese remainder Theorem
\[ \mathbb Z/n\mathbb Z \equal{} \oplus_i\mathbb Z/p_i^{r_i}\mathbb Z
\]
induces the following commutative diagram of rings by tensoring with $ R$
\[ \begin{array}{ccc} R & \rightarrow & \oplus R_i \\
\downarrow & & \downarrow \\
End_R(R) & \rightarrow & \oplus_iEnd_{Ri}(R_i) \end{array}
\]
with $ R_i \equal{} R/p_i^{r_i}R \equal{} R\otimes_{\mathbb Z/n\mathbb Z}\mathbb Z/p_i^{r_i}\mathbb Z$. The horizontal arrows are natural isomorphisms, the vertical arrows are just $ \iota$ and $ \oplus_i \iota_i$, respectively.[/hide]

Let $ n \equal{} p^r$. $ R': \equal{} R/pR$ is a finite dimensional $ \mathbb F_p$-vector space with $ R'\neq 0$, by Nakayama. Take $ a\in R\setminus pR$. Let $ f(X)\in\mathbb Z[X]$ be a monic polynomial such that $ f(X) \mod p$ is the minimal polynomial of the multiplication $ \iota_a$ with $ a$ in $ R'$. The endomorphism $ f(\iota_a)\in End_R(R)$ takes values in $ pR$ such that $ f(\iota_a)^r$ is the zero map on $ R$. Define $ g(X) \equal{} f(X)^r \mod p^r$. Then $ g(0)\in \mathbb Z/p^r\mathbb Z$ is a unit since it is a unit mod $ p$, hence $ g(0)^m \equal{} 1$ for some $ m > 0$. Expanding $ g(\iota_a)^m \equal{} 0$ shows that $ 1\in \mathbb Z/p^r\mathbb Z$ is a linear combination of powers of $ \iota_a$ with linear coefficients in $ \mathbb Z/p^r\mathbb Z$. In other words, $ id_R$ is contained in the image of $ \iota$. Pulling the relation back via $ \iota$ defines a/the unity element of $ R$.

now I've understood your solution. thank you!

does anyone have an idea how to prove this with more elementary methods?

[quote="-oo-"]does anyone have an idea how to prove this with more elementary methods?[/quote]I am wondering what is not elementary in the proof. What is happening here is a bunch of identifications compatible one to another, because the homomorphisms are natural. Maybe it is just a question of presentation that it does not look like being elementary.

... but discussion is welcome and encouraged - in particular if something in my proof needs some more explication. I have exchanged some details in PMs with -oo-.

Another approach maybe:

Let $ e$ be the largest idempotent in $ R$. By this I mean that $ ef \equal{} f$ for any idempotent $ f\in R$. $ e$ exists, because the idempotents form a finite (and hence complete) lattice. $ R$ can then be broken up as $ R \equal{} R(1 \minus{} e)\oplus Re$. Assuming $ e$ is not a unit, any annihilator in the non-zero ring $ R(1 \minus{} e)$ is an annihilator for $ R$, and $ R(1 \minus{} e)$ has no non-zero idempotents. So the problem is reduced to the case when $ R$ has no non-zero idempotents; I'll assume this in what follows.

Let $ a\in R$ be a non-zero element. The sequence of ideals $ (a^n)$ eventually stabilizes, so let $ I$ be the smallest such ideal. Then $ a$ acts as a bijection on $ I$, so some power $ a^n$ is an idempotent. By our assumption of no non-zero idempotents, $ a$ must be nilpotent. Hence the ring $ R$ consists of nilpotent elements. But the existence of an annihilator is now clear: start with some non-zero $ a_1\in R$. If it's not an annihilator, replace it with a non-zero product $ a_1a_2$, and so on. We must eventually get to an annihilator, because, since $ R$ is finite and consists of nilpotent elements, $ a^n \equal{} 0,\ \forall a$ for some $ n$, so no element can appear $ n$ times in the product $ 0\ne\prod a_i$.

Just one more thing: Third Edition pointed out to me that I wrote $ 1\minus{}e$ when we didn't know whether or not the ring had a unit. That does indeed look rather silly, but by $ R(1\minus{}e)$ I simply meant the set of elements of $ R$ having the form $ x\minus{}xe,\ x\in R$.

... or work in the unitalization of $ R$, in which $ R$ is an ideal. of course, it's the same.

This is very elegant, but I am having trouble with tiny logical twists in the following part from my point of view:[quote="grobber"]Let $ e$ be the largest idempotent in $ R$. By this I mean that $ ef \equal{} f$ for any idempotent $ f\in R$. $ e$ exists, because the idempotents form a finite (and hence complete) lattice. $ R$ can then be broken up as $ R \equal{} R(1 \minus{} e)\oplus Re$. Assuming $ e$ is not a unit, any annihilator in the non-zero ring $ R(1 \minus{} e)$ is an annihilator for $ R$, and $ R(1 \minus{} e)$ has no non-zero idempotents. So the problem is reduced to the case when $ R$ has no non-zero idempotents; I'll assume this in what follows.[/quote]- We cannot utter "$ e$ is not a unit" (unless we interpret $ e$ as endomorphism of $ R$).
- Why do we know that having chosen the maximal idempotent $ e$ (it is unique), both $ Re$ and $ R(1\minus{}e): \equal{}\{a\minus{}ea|a\in R\}$ are non-zero to derive a proper decomposition? I believe that the maximality is too much to demand here. Shouldn't we better take a sub-maximal idempotent - if is exists? NB that in unitary rings it is the element of unity which allows us to pick a sub-maximal idempotent if some maximality argument is applied.

All this can be easily repaired by a standard irreducibility argument: If there is an idempotent $ e$ such that both $ Re$ and $ R(1\minus{}e)$ are non-trivial, then split $ R$ and use induction on the number of elements of $ R$. Note that the annihilator naturally respects the decomposition, as well. Otherwise there is no non-trivial idempotent meaning that every idempotent induces either the zero-map or the identity on $ R$.

[quote="Third Edition"]- We cannot utter "$ e$ is not a unit" (unless we interpret $ e$ as endomorphism of $ R$).
[/quote]

$ e$ being idempotent, "unit" here is the same as "multiplicative identity". Conversely, if the ring is unital, the largest idempotent is the multiplicative identity. So if you don't like the phrase "$ e$ is not a unit" replace it with "$ R$ is not a unital ring", which is what the whole thing is about anyway.

[quote="Third Edition"]
- Why do we know that having chosen the maximal idempotent $ e$ (it is unique), both $ Re$ and $ R(1 \minus{} e): \equal{} \{a \minus{} ea|a\in R\}$ are non-zero to derive a proper decomposition? I believe that the maximality is too much to demand here. Shouldn't we better take a sub-maximal idempotent - if is exists? NB that in unitary rings it is the element of unity which allows us to pick a sub-maximal idempotent if some maximality argument is applied.
[/quote]

Why do you want (or need) them to be non-zero? I assumed the ring is not unital, so $ R(1 \minus{} e)$ is certainly non-zero (otherwise $ ex \equal{} x$ for all $ x$, i.e. $ e$ would be a multiplicative identity), but $ e$, the largest idempotent, may very well be zero; in fact, the first paragraph does precisely this: it reduces the problem to the case when the largest idempotent in our ring is zero, i.e. when all the elements of the ring are nilpotent.

Long story short, the proof amounts to this: assuming the ring is not unital, we find an annihilator (which has to be non-zero by definition).

[quote="grobber"][quote="Third Edition"]- We cannot utter "$ e$ is not a unit" (unless we interpret $ e$ as endomorphism of $ R$).
[/quote]

$ e$ being idempotent, "unit" here is the same as "multiplicative identity". Conversely, if the ring is unital, the largest idempotent is the multiplicative identity. So if you don't like the phrase "$ e$ is not a unit" replace it with "$ R$ is not a unital ring", which is what the whole thing is about anyway.
[/quote]Ok, this is a just confusion between the notions "the unit element" and "a unit".
[quote]
[quote="Third Edition"]
- Why do we know that having chosen the maximal idempotent $ e$ (it is unique), both $ Re$ and $ R(1 \minus{} e): \equal{} \{a \minus{} ea|a\in R\}$ are non-zero to derive a proper decomposition? I believe that the maximality is too much to demand here. Shouldn't we better take a sub-maximal idempotent - if is exists? NB that in unitary rings it is the element of unity which allows us to pick a sub-maximal idempotent if some maximality argument is applied.
[/quote]

Why do you want (or need) them to be non-zero? I assumed the ring is not unital, so $ R(1 \minus{} e)$ certainly is non-zero (otherwise $ ex \equal{} x$ for all $ x$, i.e. $ e$ would be a multiplicative identity), but $ e$, the largest idempotent, may very well be zero; in fact, the first paragraph does precisely this: it reduces the problem to the case when the largest idempotent in our ring is zero, i.e. when all the elements of the ring are nilpotent.[/quote] ... another way to clarify the logical dilemma I pointed out. But certainly there was no risk for the proof to fail anyway.  :)
[quote]Long story short, the proof amounts to this: assuming the ring is not unital, we find an annihilator (which has to be non-zero by definition).[/quote]Funny, I thought that from the very beginning reading your lines. ;)

http://www.mathlinks.ro/viewtopic.php?p=1264610#1264610
[quote="grobber"]Then $ a$ acts as a bijection on $ I$, so some power $ a^n$ is an idempotent.[/quote]
could you explain this to me? I have forgotten the argument. thanks  :oops:

Solution:

Lemma:

Let $R$ be finite ring and $r$ in $R$ such that $rR=R$. Prove that exists multiplicative $1\in R$.

Proof:

Take action $r: S_{|R|}\to S_{|R|}$, $r(r_1,...,r_{|R|})=(rr_1,...,rr_{|R|})$, where $R=\{r_i\}_i$. Group $Sym(S_{|R|})$ is finite so exists $i:r^i(r_1,...,r_{|R|})=(r_1,...,r_{|R|})$, so $r^i=1$. $\Box$

Return to main problem. So we need to prove that exists $r\in R: rR=R$. Let define for every elrment $f\in R$ rings $A_f=fR$, $B_f=\{x\in R| xf=0\}$. Take element $x\in R\setminus \{0\}: \max(|A_x|,|B_x|) = \max_{r\in R\setminus\{0\}}max(|A_r|,|B_r|)$. Easy to see that if $\forall u\in R, uR\not= R$ then $\forall u\in R, \exists v\not= 0\in R: uv= 0$. Easy to see that if $ab=0$, then $A_a\subseteq B_b, A_b\subseteq B_a$, so if we take $y\not= 0 : xy= 0$ and from definition of $x$, there exists element $h\in R: |B_h|=\max_{r\in R\setminus\{0\}}max(|A_r|,|B_r|)$, easy to see that $\forall w\in R: wh\not= 0, B_h\subseteq B_{wh}$, so $B_h= B_{wh}$, so $\forall w\in R\setminus B_h , B_w\subseteq B_{wh}= B_h$.

Take any element $w\in R\setminus B_h$, if exists elements $e, q\in R\setminus B_h : we =wq$, then $e-q\in R\setminus B_h$, but $w(e-q) = 0$. If $\forall w\in R$ exists $w'\in R\setminus B_h : ww'\in B_h$, then take smaler ring $R/B_h$ ($B_h$ is Ideal in $R$). So this smaller is without $1$, so from same problem $\exists b\in R\setminus B_h : bR\subseteq B_h$, but then $brR= 0$, so $b\in B_r$. So $\exists e\in R : e(R\setminus B_h) = R\setminus B_h$, so $eR = R$ and so from lemma there exists multiplicative $1\in R$. done


modular arithmetic
number theory unsolved
number theory

Prove that $ 5n^3 \plus{}7n^5 \equiv 0$ (mod 12) $ \forall n \in \mathbb{Z}$

We shall prove that $ 5n^3 \plus{} 7n^5$ is divisible by 4 and 3. Note that $ 5n^3 \plus{} 7n^5 \equal{} n^3(5 \plus{} 7n^2)$.

If $ n$ is even, it is clearly divisible by 4. If $ n$ is odd, $ 4|5 \plus{} 7n^2$.

If $ 3|n$, it is obviously divisible by 3. If $ n \equal{} 3k\pm1$, $ 5 \plus{} 7n^2\equiv0\pmod3$.


[quote="aidan"]There are $ n$ men and $ n$ women at a tennis tournament. How many ways are there to form $ n$ pairs of male-female players?[/quote]
[hide]
$ n^{2}\plus{}(n\minus{}1)^{2}\plus{}...\plus{}1\equal{}\frac{n(2n\plus{}1)(n\plus{}1)}{6}$[/hide]

:huh:

[hide="Induction disagrees"]
Claim: $ n!$
Base case: $ 1! \equal{} 1$ way for one male/female is obvious.
Inductive step: Assume for $ n\minus{}1$. Take the $ n$th male, and pair him with a random female. There's $ n$ ways to do this, and then we have $ n\minus{}1$ males and females. Since there $ (n\minus{}1)!$ ways to do that by the inductive hypothesis, there are $ n(n\minus{}1)! \equal{} n!$ ways to do it for $ n$.
[/hide]

[hide="solution?"]Line up the men by IQ (or however you want to line them up, as long as it's fixed).  Now make a line of women facing the men.  Each pair of people facing each other will make a pair.[code]MMMMMMMMM
WWWWWWWWW[/code]
There are $ n!$ ways to line up the women.  That gives all the possible combinations.  $ n!$ is the answer.[/hide]

Extension...
$ m>n$  there are $ n$ pairs of $ m$ men and $ n$ women.  ($ m\minus{}n$ men get left out)
How many ways?

easy
you just line them up again
there are now $ \binom{m}{n}n!$ ways to arrange the bottom row

Wow i didn't think of induction.. But nice solutions!  :)


Find all pairs of integers $ (x,y)$ such that $ x^2 \minus{} xy \plus{} y^2 \equal{} 79$.

I tried multiplying by $ x\plus{}y$ on both sides to get $ x^3\plus{}y^3\equal{}79(x\plus{}y)$, but I'm stuck after that.

This problem is crying out for [url=http://mathworld.wolfram.com/EisensteinInteger.html]Eisenstein Integers[/url].

I get
[hide]
$ (7,10)$ and $ ( \minus{} 7, \minus{} 10)$.

Also $ (10,7)$ and $ (\minus{}10,\minus{}7)$.
[/hide].

EDIT: Okay, okay . . .  :roll:

[quote="E^(pi*i)=-1"]This problem is crying out for [url=http://mathworld.wolfram.com/EisensteinInteger.html]Eisenstein Integers[/url].

I get
[hide]
$ (7,10)$ and $ ( \minus{} 7, \minus{} 10)$.
[/hide].[/quote]

How about [hide]$ (10,7)$ and $ ( \minus{}10, \minus{}7)$.  :P [/hide]

Are you sure you didn't miss some?

[hide]
$ (7, \minus{} 3)$, for instance?

Never heard of Eisenstein integers, but you could brute-force it by seeing it as

$ x^2 \minus{} (y)x \plus{} (y^2 \minus{} 79) \equal{} 0$
$ \Delta \equal{} \minus{} 3y^2 \plus{} 316$
$ \minus{} 3y^2 \plus{} 316 \ge 0 \rightarrow \minus{} 10 \le y \le 10$

$ x \equal{} \frac {y \pm \sqrt {316 \minus{} 3y^2}}2$

Then look for values of $ y \le 10$ such that $ 316 \minus{} 3y^2$ is a square (3, 7, and 10).
Each of these has the corresponding x solutions...

Therefore, part of solution is composed of the pairs $ (10, 3), ( \minus{} 7, 3), (10, 7)$ (but you can invert the order of them or multiply both by -1 and you still get a valid solution, I'm just lazy to write them all down).
[/hide]

I don't really get the Eisenstein Integers...or how you got to your answers.  A little more help please?   :blush:

ffao used the quadratic formula in terms of the other variable and examined the discriminant for negative values.

Sorry, I wasn't thinking straight.  Eisenstein integers are definitely the way to do this problem:

[hide]
We want to factorize $ 79$ as $ (a \plus{} b\omega)(a \plus{} b\omega^2)$.  $ 79 \equal{} (\pm 2)^2 \plus{} 3(\pm 5)^2$, so we get $ a \equal{} 2 \plus{} 5 \equal{} 7$, $ b \equal{} 2(5) \equal{} 10$ or $ a \equal{} 5 \minus{} 2 \equal{} 3$, $ b \equal{} 2(5) \equal{} 10$, or equivalent things.  So $ \pm (3,10)$ and $ \pm (7,10)$ work.  But we need to remember that there are three units: $ 1$, $ \omega$, and $ \omega^2$.  Multiplying $ 3 \plus{} 10\omega$ by $ \omega$ gives $ 3(\omega \plus{} \omega^2) \plus{} 7\omega \equal{} \minus{} 3 \plus{} 7\omega$, so $ \pm ( \minus{} 3,7)$ works.  Nothing else gives anything new, so these are the only solutions.
[/hide]

Indeed.  The tricky thing about working with the Eisenstein integers numerically is that every number has five other associates and conjugates:  $ a \plus{} b \omega$ automatically has the same norm as

$ a \omega \plus{} b \omega^2 \equal{} \minus{} b \plus{} (a \minus{} b) \omega$
$ a \omega^2 \plus{} b \equal{} (b \minus{} a) \minus{} a \omega$
$ a \plus{} b \omega^2 \equal{} (a \minus{} b) \minus{} b \omega$
$ a \omega \plus{} b \equal{} b \plus{} a \omega$
$ a \omega^2 \plus{} b \omega \equal{} \minus{} a \plus{} (b \minus{} a) \omega$

and since $ 79$ is prime we should therefore expect, in total, exactly six solutions.

Same as above, but perhaps a simpler way ( that is not involving Einstein numbers explicitly ) is note that one can write
$ 4x^2\minus{}4 xy\plus{}4 y^2 \equal{}  u^2\plus{}3v^2$
where $ u\equal{}2x\minus{}y$ and $ v\equal{}y$  and 79 can be written as  $ 4^2\plus{}3(5^2)$

[quote="Gyan"] 79 can be written as  $ 2^2 \plus{} 3(5^2)$[/quote]Gyan, you almost typed this.    This is what you meant, correct?

Not "79 can be written as 4^2 + 3(5^2)."


Let $ ABC$ acute triangle and $ H$ the orthocenter. Let $ D,E,F$ arbitrary point on sides $ AH,CH,AC$
Prove that tangent line from $ B$ to circle with diameter $ CD,AE,HF$ have same length

let $ H_1,H_2,H_3$ be the intersections of $ AH,BC$ and $ BH,AC$ and $ CH,AB$ respectively,now just noe that $ H_1$ lies on the circle with diameter $ CD$,let $ t_1$ be the length of tangent line from $ B$ to this circle,so according to the [b]power of point $ B$ with respect to this circle[/b] we get that:

$ t_1^2\equal{}BH_1.BC$

now in the same way as above,let $ t_2,t_3$ be the length of tnagent lines from $ B$ to the circles with diameter $ HF,AE$ respectively so we get that:

$ t_2^2\equal{}BH.BH_2$

$ t_3^2\equal{}BH_3.BA$

so in order to prove that $ t_1\equal{}t_2\equal{}t_3$ we have to prove that:

$ BH_1.BC\equal{}BH_2.BH\equal{}BH_3.BA$

just note that $ H_3AH_2H$ is cyclic so according to the power of point $ B$ wrt this circle we get that:

$ BH_3.BA\equal{}BH.BH_2$ (I)

and also we know that $ H_2HH_1C$ is cyclic so again according to the power of point $ B$ wrt this circle we get that:

$ BH.BH_2\equal{}BH_1.BC$ (II)

now from (I),(II) we get that:

$ BH_1.BC\equal{}BH_2.BH\equal{}BH_3.BA\Rightarrow t_1\equal{}t_2\equal{}t_3$

as desired...


The product of two of the four roots of the quartic equation $x^4 - 18x^3 + kx^2+200x-1984=0$ is $-32$. Determine the value of $k$.

i think you shuold put the solution and problem in different posts...

[hide="My Solution"]Let the four roots be $ a,b,c,d$. By Vieta's Formulas, we have the following:

$ ab \equal{} \minus{} 32$
$ abcd \equal{} \minus{} 1984$
$ cd \equal{} 62$
$ a \plus{} b \plus{} c \plus{} d \equal{} 18$*
$ ab \plus{} ac \plus{} ad \plus{} bc \plus{} bd \plus{} cd \equal{} k$
$ abc \plus{} abd \plus{} acd \plus{} bcd \equal{} \minus{} 200$

Substituting given values obtains the following:

$ ac \plus{} ad \plus{} bc \plus{} bd \equal{} k \minus{} 62 \plus{} 32 \equal{} k \minus{} 30$
$ (a \plus{} b)(c \plus{} d) \equal{} k \minus{} 30$
$ \minus{} 32c \plus{} 62b \plus{} 62a \minus{} 32d \equal{} \minus{} 200$
$ 31(a \plus{} b) \minus{} 16(c \plus{} d) \equal{} \minus{} 100$
*Multiplying the equation by 16 gives

$ 16(a \plus{} b) \plus{} 16(c \plus{} d) \equal{} 288$. Adding it to the previous equation gives

$ 47(a \plus{} b) \equal{} 188$
$ a \plus{} b \equal{} 4$
$ c \plus{} d \equal{} 18 \minus{} 4 \equal{} 14$
$ (a \plus{} b)(c \plus{} d) \equal{} 4(14) \equal{} 56 \equal{} k \minus{} 30$
$ k \equal{} \boxed{86}$[/hide]

Your solution is so much shorter than mine.  :lol:

Instead of doing that adding, I substituted a+b for 18-c-d which made it take much longer.  :blush:

oh, 2 more things.
1. take out "And again, how do I add this to the resources section?"

2. change the title. it shouldnt have vieta because it hints at the solution(regardless of how obvious it may be)

[hide="Better solution"]Let two factors of the LHS be $ (x^{2}\plus{}ax\plus{}c)(x^{2}\plus{}bx\plus{}d)$. We know that $ c\equal{}\minus{}32$ and as a result, $ d\equal{}62$. So we have $ (x^{2}\plus{}ax\minus{}32)(x^{2}\plus{}bx\plus{}62)\equal{}x^{4}\plus{}(a\plus{}b)x^{3}\plus{}(ab\plus{}30)x^{2}\plus{}(\minus{}32b\plus{}62a)x\minus{}1984$. So we have two equations, $ a\plus{}b\equal{}\minus{}18$ and $ 62a\minus{}32b\equal{}200$. Solving, we get $ (a,b)$ as $ (\minus{}4,\minus{}14)$so $ k\equal{}56\plus{}30\equal{}86$.[/hide]

[hide="Solution"]Let the roots of the quartic be $a, b, c, d$. Then we have $a+b+c+d=18$, $ab+ac+ad+bc+bd+cd=k$, $abc+abd+acd+bcd=-200$, $abcd=-1994$.
WLOG let $ab=-32$. Substituting this into $abcd=-1984$, we see that $cd=62$. Then the equations become $a+b+c+d=18$, $30+ac+ad+bc+bd=k$, $-32c-32d+62a+62b=-200$

In order to find $k$ we need to find $ac+ad+bc+bd$. Factoring this yields \[a(c+d)+b(c+d)=(a+b)(c+d)\]
Furthermore, \[-32c-32d+62a+62b=-32(c+d)+62(a+b)\]
Now, let $u=a+b$ and $v=c+d$. Then we have $u+v=18, 62u-32v=-200$. Solving gives $u=4$ and $v=18$, so $k=30+4\times 14=\boxed{86}$[/hide]

Let $a,b,c,d$ be roots of the polynomial.

By Vieta's formulas:

$$a+b+c+d = 18$$$$ab+ac+ad+bc+bd+cd = k$$$$abc+abd+acd+bcd =-200$$$$abcd =-1984.$$
Without loss of generality, assume that $ab=-32$, then by the last equation, $cd=62$. We can re-write the equations as follows,
$$(a+b)+(c+d) = 18$$$$ac+ad+bc+bd + 30 = (a+b)(c+d) + 30 = k$$$$-32c-32d+62d+62d =-200$$
Letting $m=a+b$ and $n=c+d$, we see that $m+n = 18$, $-32n+62m=-200$, so $m=4$ and $n=14$. $k = mn + 30 = \boxed{86}$.

[quote=srisainandan6]Here is a good polynomial's handout: Did you get this from YCMA?
[url]https://youthconway.com/handouts/polynomials.pdf[/url][/quote]

yup

Let $a$, $b$, $c$ and $d$ be the roots to this quartic equation.

WLOG, let $a$ and $b$ be the roots to this quartic whose product is $-32$.

By Vieta's Formula, we know that:
$$\implies a + b + c + d = 18$$$$\implies ab + ac + ad + bc + bd + cd = k$$$$\implies abc + abd + bcd + acd = -200$$$$\implies abcd = -1984$$
Note that:
$$\implies \frac{abcd}{ab} = 62 = cd$$
$\implies ab + ac + ad + bc + bd + cd = -32 + ac + ad + bc + bd + 62 = k$
$$\implies ac + ad + bc + bd = k - 30$$
We can factor $ac + ad + bc + bd$ as $(a + b)(c + d)$.
$$\implies (a + b)(c + d) = k - 30$$
Note that:
$$\implies abc + abd + bcd + acd = ab(c + d) + cd(a + b) = -200$$
We know that $a + b + c + d = 18$ so $a + b = 18 - (c + d)$. We also figured $ab = -32$ and $cd = 62$.
$$\implies -32(18 - (c + d)) + 62(c + d) = -200$$$$\implies -576 + 32c + 32d + 62c + 62d = -200$$$$\implies 94c + 94d = 376$$$$\implies 94(c + d) = 376$$$$\implies c + d = 4$$$$\implies a + b = 14$$
(or vice versa).

Hence:
$$\implies (14)(4) = k - 30$$$$\implies 56 = k - 30$$$$\implies k = \boxed{86}$$$\blacksquare$

[size=125]credits to my blog[/size]

There is a [i]much[/i] easier way (in my opinion)

[hide=Solution]We can factor the quartic as $(x^2+ax-32)(x^2+bx+62)$. Expanding this gives $x^4+(a+b)x^3+(ab+30)x^2+(62a-32b)x-1984$. We have $a+b=-18$, $62a-32b=200$. We know that $32a+32b=-576$, so $94a=-376$, which means that $a=-4$. So, $b=-14$, and we need to compute $ab+30=\boxed{86}$, the answer.[/hide]

Shoot this is the same as #6 :blush:

@above i think you meant 86 but nice solution

I like Vieta’s, but this feels like an AIME Problem 4 or 3.

[hide=Solution]Let the roots of the equatoon be $a,b,c,$ and $d$. By Vieta's,
\begin{align*}
a+b+c+d=18 \\
ab+ac+ad+bc+bd+cd=k \\
abc + abd + acd + bcd = -200 \\
abcd=-1984
\end{align*}
Since $abcd=-1984$ and $ab=-32$, then, $cd=62$. Notice that $$abc + abd + acd + bcd = -200$$ can be factored into $$ab(c+d)+cd(a+b)=-32(c+d)+62(a+b).$$ From the first equation, $c+d=18-a-b$. Substituting it back into the equation, $$-32(18-a-b)+62(a+b)=-200$$
Expanding, $$-576+32a+32b+62a+62b=-200 \implies 94a+94b=376$$
So, $a+b=4$ and $c+d=14$. Notice that $$ab+ac+ad+bc+bd+cd=ab+cd+(a+b)(c+d)$$Plugging all our values in, $$-32+62+4(14)=\boxed{86}.$$

Let the roots be $a,b,c,d$ and WLOG $ab=32$. By Vieta's, $abcd=-1984$, so $cd=62$. Now we present two solutions.

$\textbf{Solution~1:}$ Method of Undetermined Coefficients.

Suppose $x^4 - 18x^3 + kx^2+200x-1984$ factors as $(x^2+rx-32)(x^2+sx+62)$ for some $r,s\in\mathbb{C}$. Upon expansion, we have $$(x^2+rx-32)(x^2+sx+62)=x^4+(r+s)x^3+(rs+30)x^2+(62r-30s)x-1984.$$ Equating coefficients, we have the system \begin{align*}r+s&=-18\\ rs+30&=k\\ 62r-30s&=200\end{align*} whose solution is $(r,s)=(-4,-14)$ by Cramer's Rule. Hence, $k=rs+30=86$. $\square$

$\textbf{Solution~2:}$ Vieta's Formulas.

By Vieta's, \begin{align*}a+b+c+d&=18\\ab+ac+ad+bc+bd+cd&=k\\abc+abd+acd+bcd&=-200,\end{align*} but since $ab=-32,c=62$, we have the system \begin{align*}(a+b)+(c+d)&=18\\(a+b)(c+d)&=k-30\\62(a+b)-32(c+d)&=-200.\end{align*} Substituting $a+b=r,c+d=s$ gives us the exact same system we solved in $\textbf{Solution~1}$. $\square$

[quote=OlympusHero][quote=sshi]Hello, OlympusHero's Method is faster, but ATGY's is easier to think of.[/quote]

Really? What first came to my mind was my method, I never even thought about ATGY's :huh:[/quote]

I also thought of Method of Undetermined Coefficients first.
@below yup :)

As seen in my solution, both methods ultimately boil down to the same system. :)

My solution from WOOT:

Let the roots of the quartic be $a,b,c,d$ with $ab=-32$. By Vieta's, we have:
$$\begin{cases}a+b+c+d=18\\ab+ac+ad+bc+bd+cd=k\\abc+bcd+cda+dab=-200\\abcd=-1984\end{cases}$$
Using $ab=-32$, this is:
$$\begin{cases}a+b+c+d=18\\ac+ad+bc+bd+cd=k+32\\bcd+cda-32c-32d=-200\\cd=62\end{cases}$$
$$\Rightarrow\begin{cases}a+b+c+d=18\\(a+b)(c+d)=k-30\\62a+62b-32c-32d=-200\\cd=62\end{cases}$$
Let $x=a+b$ and $y=c+d$. We have $x+y=18$ and $62x-32y=-200$. Solving, $x=4$ and $y=14$. Substituting into $xy=k-30$, we will find that $\boxed{k=86}$.

The answer is $86$. By Vieta we have
\begin{align*}
    \sum r_i&=18\tag{$1$} \\
    \sum r_ir_j&=k\tag{$2$} \\
    \sum r_ir_jr_k&=-200\tag{$3$} \\
    r_1r_2r_3r_4&=-1984\tag{$4$}
\end{align*}
Let WLOG $r_1r_2=-32$. Using $(2)$ we have $r_3r_4=-1984/-32=62$. Using $r_1r_2$, $r_3r_4$ and equation $(1)$ in equation $(3)$ we have \[ 62(r_1+r_2)-32(r_3+r_4)=-200\tag{$5$} \]
Rewriting the equation $(2)$ we have \[ (r_1+r_2)(r_3+r_4)+30=k\tag{$6$} \]
Solving the equation $(1)$ and $(5)$ in terms of variable $r_1+r_2$ and $r_3+r_4$ we get $4, 14$. Putting these value in the equation $(6)$ we get out answer $k=86$.

[hide=solution]
Let the roots of this polynomial be $a$, $b$, $c$, and $d$. Suppose that the two roots that multiple to $-32$ are $a$ and $b$, so $ab=-32$. Vieta's gives us $abcd=-1984$, so $cd=62$. We also know that \[abc+abd+acd+bcd=62(a+b)-32(c+d)=-200,\] and that $(a+b)+(c+d)=18$, so solving this system gives $a+b=4$ and $c+d=14$.

Vieta's again gives us \[k=ab+ac+ad+bc+bd+cd=-32+62+(a+b)(c+d)=30+4\cdot 14=\boxed{86}.\]
[/hide]

By Veita the product of the other 2 roots are 62, let the 4 roots be $a,b,c,d$ by vieta's we have $a+b+c+d=18,ab+ac+Ad+bc+bd+cd$, and $abc+acd+abd+bcd=-200$

And then we can do some calculator from here to get that $k=\boxed{86}$

Assume the roots of the equation $x^4-18x^3+kx^2+200x-1984=0$ are $\alpha  ,\beta  ,\gamma  ,\delta$  Given product of any two roots of this equation is -32. By Vietas Relation we get $$\alpha+\beta+\gamma+\delta=18$$  $$\alpha\beta+\beta\gamma+\gamma\alpha+\alpha\delta+\beta\delta+\gamma\delta=k$$  $$\alpha\beta\gamma+\beta\gamma\delta+\alpha\beta\delta+\alpha\gamma\delta=-200$$  $$\alpha\beta\gamma\delta=-1984$$
Lets assume $\alpha\beta=-32$ from product of roots we get $\alpha\beta\gamma\delta=-1984\implies\gamma\delta=62$  $$\alpha\beta\gamma+\beta\gamma\delta+\alpha\gamma\delta+\alpha\beta\delta=-200\implies62(\alpha+\beta)-32(\gamma+\delta)\implies62(\alpha+\beta)-32(18-(\alpha+\beta))=-200\implies94(\alpha+\beta)=376\implies\boxed{\alpha+\beta=4}$$
From these we also get $\boxed{\gamma+\delta=14}$ Therefore, $$\alpha\beta+\beta\gamma+\gamma\alpha+\delta\alpha+\beta\delta+\gamma\delta=k\implies(\alpha+\beta)(\gamma+\delta)+\alpha\beta+\gamma\delta=14.4+62-32=56+30\implies86.$$ Is the correct answer...
Vietas Relation :love:

[hide=solution]
Let the roots be $a,b,c,d$ and WLOG assume $ab=-32$. By Vieta's, we have

\begin{align}
&abcd = - 1984\\
&a + b + c + d = 18\\
&ab + ac + ad + bc + bd + cd = k\\
&abc + abd + acd + bcd = - 200
\end{align}

From $(1)$, we get $cd=62$. Thus, it suffices to find $ac+ad+bc+bd+30$ which is equivalent to finding $(a+b)(c+d)+30$. From $(3)$, we have

\[ab(c+d)+(a+b)cd=62(a+b)-32(c+d)=-200\]
\[\implies 31(a+b)-16(c+d)=-100\]

Letting $i=a+b$ and $j=c+d$, we have

\begin{align*}
&31i-16j = -100\\
&i+j=18
\end{align*}

Solving, we get $i=4$, $j=14$, so $k=30+4 \cdot 14 = \boxed{86}$.
[/hide]

Let the roots of the quartic be $a$, $b$, $c$ and $d$. WLOG, let $ab=-32$, and by Vieta's, we have that $abcd=-1984$, meaning that $cd=-62$. Let $x=a+b$ and $y=c+d$. By Vieta's, we have that
\[18=a+b+c+d=(a+b)+(c+d)=x+y,\]
and
\[-200=abc+abd+acd+bcd=cd(a+b)+ab(c+d)=62x-32y.\]
Solving the system of equations gives us that $x=4$ and $y=14$. Again using Vieta's, we have that
\[k=ac+ad+bc+bd+ab+cd=(a+b)(c+d)+ab+cd=xy-32+62,\]
or $xy+30$, giving us that $k$ is $86$, finishing the problem.


modular arithmetic
function
number theory
relatively prime
arithmetic sequence
prime numbers
number theory open

im not sure about this so it's here in the open problems

if we have $ a,b$ two relatively prime positive integers then there are infinitely many primes in arithmetic sequence $ a_n \equal{} a\cdot n \plus{} b$.
is there a known bound for the first one? like $ n < a^2$ or something like that

tnx for help

Yes; this is [url=http://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arithmetic_progressions]Dirichlet's theorem on arithmetic progressions[/url].  I don't know the answer to the second question.

the second question is [b]the question[/b] :lol:  :P i know about dirichlet's theorem but tnx anyway.
someone must have been wondering this. it's quite an obvious and very interesting question and i think i'd be a very useful result. not saying an easy one:D
it would be bold to conjecture $ n<a$ but im currently just interested in any bound at all. something analog to bertrand's postulate or something similar

I may be attacking it from the wrong direction, but can't we choose $ b$ to satisfy $ b \equiv \minus{} na \pmod {a_{i}}$ for $ n < f(a)$ for some function $ f$ and $ a_i$ is a sequence of relatively prime numbers which are also relatively prime to $ a$, and then the first prime will occur after the $ f(a)$th term?

A [url=http://en.wikipedia.org/wiki/Prime_number_theorem#The_prime_number_theorem_for_arithmetic_progressions]generalization of the PNT[/url] does indeed hold, which (I believe) implies the following generalization of Bertrand's postulate:  for every $ \epsilon > 0$ there exists $ N$ such that for any prime $ p_k > N$ in a given arithmetic progression, the next prime $ p_{k\plus{}1}$ in the same progression satisfies $ p_k \le (1 \plus{} \epsilon) p_{k\plus{}1}$.  The problem is that this result is asymptotic, so it doesn't say anything about the first such prime.  (Indeed, if you're familiar with Erdos' proof of Bertrand's Postulate, the primes up to $ 2047$ are verified to satisfy the postulate by [i]casework[/i]; the content of the proof is also asymptotic.)

Anyway, expanding on bambaman's comment:  fix $ b$.  The solution to the system of congruences

$ a \plus{} b \equiv 0 \bmod p_1$
$ 2a \plus{} b \equiv 0 \bmod p_2$
$ 3a \plus{} b \equiv 0 \bmod p_3$
...
$ ka \plus{} b \equiv 0 \bmod p_k$

for the sequence of primes $ (p_i)$ relatively prime to both $ a$ and $ b$ defines a value of $ a, 0 \le a < p_1 p_2 ... p_k$ such that the arithmetic progression $ a_n \equal{} an \plus{} (a \minus{} 1)$ has first $ k$ values composite.  One has an asymptotic for $ p_1 p_2 ... p_k$ that I don't quite recall and, under the assumption that the value of $ a$ is essentially random (see [url=http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6W9F-4SDNKBK-1&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=dd3d6e9d28e50caccac5ee6a206396b0]this paper[/url], for example), that provides us with a very rough idea of the kind of relation between $ a$ and $ k$ we're looking for.


How to solve the below problem? I know that it is set cover which is NP-Compete but it is special case which can solved quickly.

[code]
Ethernet Routing:
Farmer John recently bought new computers for all his cows. Since the cows love the Internet, he must wire his farm with Ethernet cables and routers. Since the purchase of these routers makes a hefty dent in FJ's budget, he wants to buy the minimum possible number of routers.

The farm is a connected collection of N (1 <= N <= 100,000) fields (conveniently numbered 1..N) linked by N-1 roads of length 1 with no loops. FJ can place a router in any field he wishes. The cows each have ethernet cables of length K (0 <= K <= 10) and can connect to any router within that distance. The routers themselves have their own connections to the Internet and may be placed anywhere.

Computer the minimum number of routers to be placed so each cow's computer can be plugged into at least one router.
[/code]

Note: the graph is an unrooted tree. Given the input sizes, the algorithm should be O(NK), O(NK^2) max.

Choose an arbitrary root, and consider the deepest leaf $ l$. It's pretty intuitive (and shouldn't be that hard to prove) that of all the nodes which cover $ l$, the only one which should have a router is the $ K$-th ancestor of $ l$. So place a router there, remove all the nodes which are covered by it, and repeat. With a modified DFS, this can be made to run in $ O(NK)$.


[i]a[/i] is a root of [i]x[/i] in the quadratic equation $x^2 + bx + a$. If $a \ne 0$ then find
[i]a[/i] + [i]b[/i].

[hide]$a + \alpha = -b$, $a\alpha = a$ $\Longrightarrow$ $\alpha = 1$ and $a + b = -1$.[/hide]

[quote="mathgeniuse^ln(x)"][hide]Using root-coefficient relationship we can show that the sum is -1.[/hide][/quote]
[hide="He means:"]If we write this quadratic as $(x-r_1)(x-r_2)$ using $r_1,r_2$ as roots, we can compare coefficients to our quadratic $x^2 + bx + a$.
This gives us $-(r_2+r_1)=b$ (because the x coefficients are equal) and $r_1r_2=a$. Since $a$ is either $r_1 \text{or }r_2$ (let's name it $r_1$), $r_2=1$. So $a+b=a+(-1-a)=\boxed{-1}$[/hide]
[quote="ArcticMonkey"][hide]$a^2 + ba + a=0 \implies a+b=-1$[/hide][/quote]
[hide="elaborated..."]Since $a$ is a root of $x^2+bx+a$, when we set $x=a$ we get zero. This gives us $a^2 + ba + a=0 \implies a^2 + ba= -a \implies a+b=-1$. In the last step, divide through by $a$ (we know from the problem it can't be zero, which could have caused problems)[/hide]


:lol: let x,y,z satisfy $x^2+9y^2+9z^2+6=k^2$ with k>0.
and T=$1+9xy+6yz+9zx$
find max T? :D

Well if you change $6yz \longrightarrow 27yz$ then i find the maximum?

[hide="Solution for 27yz"]Let $3y=a,3z=b$ ,then
$x^2+a^2+b^2=k^2-6$

We have $T-1=9x\frac{a}{3}+27\frac{ab}{9}+9x\frac{b}{3}=3(xa+ab+bx) \le
3(x^2+a^2+b^2)=3k^2-18$[/hide]


inequalities
function
inequalities proposed

[quote="Arne"]Prove that if a + b + c + d = 0 then $(a^3 + b^3 + c^3 + d^3)(a^5 + b^5 + c^5 + d^5) \geq 0$. Can we generalize this?[/quote]

It comes from British MO 2 (or a close variant) from 03/04. Most solutions are pretty ugly, but mainly generalisable i believe.

PS: the original question was in the form:
$a + b + c + d = 0$
Prove that $a^3 + b^3 + c^3 + d^3>0$ iff $a^5 + b^5 + c^5 + d^5>0$... almost the same.
The question also asked for the 3 term case.

Consider S(n)=a^4+b^4+c^4+d^4
It is easy to derive that
S(n+4)=(S(2)/2)S(n+2) + (S(3)/3)S(n+1) -abcdS(n)
Put n=1
S(5)=S(2)S(3)/2 + S(3)S(2)/3=S(2)S(3)(5/6)
Since S(2) is always positive, S(5), S(3) have the same sign.
So S(3)S(5)>=0

dear siuhochung, can  you explain your solution better.or post it in LATEX.
now I think I have another solution.
assume $a\geq b\geq c\geq d$
we can know
$(a^3 + b^3 + c^3 + d^3)\geq 0\Leftrightarrow a^3 + b^3 \geq -(c^3 + d^3)\Leftrightarrow a^2-ab+b^2\geq c^2-cd+d^2
\Leftrightarrow ab\leq cd$
with the similar way we can know $(a^5 + b^5 + c^5 + d^5)\geq 0\Leftrightarrow ab\leq cd$
                   :)

Since Kueh spoke about generalizable proofs, why don't actually generalize the problem:

[color=blue][b]General problem.[/b] Let n be an odd positive integer > 1.

[b](a)[/b] Let a, b, c be three reals satisfying a + b + c = 0. Then, the numbers abc and $a^n+b^n+c^n$ have the same sign.

[b](b)[/b] Let a, b, c, d be four reals satisfying a + b + c + d = 0. Let's WLOG assume that $a\geq b\geq c\geq d$. Then, the numbers cd - ab and $a^n+b^n+c^n+d^n$ have the same sign.[/color]

[i]Solution.[/i] First we show a lemma:

[color=blue][b]Lemma 1.[/b] [b](a)[/b] If x and y are two positive reals and k is an arbitrary positive integer > 1, then $x^k+y^k<\left(x+y\right)^k$.
[b](b)[/b] If x and y are two negative reals and k is an odd positive integer > 1, then $x^k+y^k>\left(x+y\right)^k$.[/color]

[i]Proof of Lemma 1.[/i] In order to prove Lemma 1 [b](a)[/b], we note that, by the binomial formula, $\left(x+y\right)^k=x^k+\binom{k}{1}x^{k-1}y+\binom{k}{2}x^{k-2}y^2+...+\binom{k}{k-1}xy^{k-1}+y^k>x^k+y^k$ (since k > 1, we really have some terms except of $x^k$ and $y^k$), so that $x^k+y^k<\left(x+y\right)^k$, and Lemma 1 [b](a)[/b] is proven. In order to prove Lemma 1 [b](b)[/b], we apply Lemma 1 [b](a)[/b] to the positive reals -x and -y (these are positive, since x and y are negative) and get $\left(-x\right)^k+\left(-y\right)^k<\left(\left(-x\right)+\left(-y\right)\right)^k$; since k is odd, we have $\left(-x\right)^k=-x^k$, $\left(-y\right)^k=-y^k$ and $\left(\left(-x\right)+\left(-y\right)\right)^k=\left(-\left(x+y\right)\right)^k=-\left(x+y\right)^k$; thus, $\left(-x^k\right)+\left(-y^k\right)<-\left(x+y\right)^k$, and consequently, $x^k+y^k>\left(x+y\right)^k$, what proves Lemma 1 [b](b)[/b]. Hence, Lemma 1 is proven.

Now, to the solution of the problem:

[b](a)[/b] At first, we notice that the case when one of the numbers a, b, c is 0 can be left out of consideration; in fact, in this case, we trivially have abc = 0, and we can easily prove that $a^n+b^n+c^n=0$: In fact, since one of the numbers a, b, c is 0, we can WLOG assume that a = 0. Then, the equation a + b + c = 0 becomes b + c = 0. Hence, b = -c. Thus, since n is an odd integer, $b^n=-c^n$. Together with a = 0, this yields $a^n+b^n+c^n=0^n+\left(-c^n\right)+c^n=0$. So we see that both numbers abc and $a^n+b^n+c^n$ are 0, and hence they have the same sign.

In the following, we will therefore assume that none of the numbers a, b, c is 0.

WLOG assume that $a\geq b\geq c$. Then, since a + b + c = 0, we have $a\geq 0$ and $c\leq 0$ (in fact, it is trivial that among three numbers which add up to 0, the greatest must be $\geq 0$ and the least must be $\leq 0$). Since we have assumed that none of the numbers a, b, c is 0, the inequalities $a\geq 0$ and $c\leq 0$ become a > 0 and c < 0.

Now we have two cases to distinguish between:

[b]Case 1.[/b] We have b > 0.
[b]Case 2.[/b] We have b < 0.

(The case b = 0 cannot occur, since we have said that none of the numbers a, b, c is 0.)

In Case 1, we have a > 0, b > 0 and c < 0, and thus abc < 0. On the other hand, after Lemma 1 [b](a)[/b], since a and b are positive, we have $a^n+b^n<\left(a+b\right)^n$. But a + b + c = 0 yields a + b = -c, and since n is an odd integer, we thus have $\left(a+b\right)^n=-c^n$. Thus, $a^n+b^n<-c^n$, and therefore $a^n+b^n+c^n<0$. So we see that both numbers abc and $a^n+b^n+c^n$ are negative, and hence they have the same sign.

In Case 2, we have a > 0, b < 0 and c < 0, and thus abc > 0. Since the numbers b and c are negative, Lemma 1 [b](b)[/b] yields $b^n+c^n>\left(b+c\right)^n$. But a + b + c = 0 yields b + c = -a, and since n is an odd integer, this becomes $\left(b+c\right)^n=-a^n$, so that $b^n+c^n>-a^n$, and thus $a^n+b^n+c^n>0$. So we see that both numbers abc and $a^n+b^n+c^n$ are positive, and hence they have the same sign.

Altogether, we have shown that in every case, the numbers abc and $a^n+b^n+c^n$ have the same sign. Thus, part [b](a)[/b] of the problem is solved.

[b](b)[/b] Since $a\geq b\geq c\geq d$ and a + b + c + d = 0, we must have either a = b = c = d = 0, what is a trivial case which we leave to the reader, or a > 0 and d < 0 (in fact, if four numbers add up to 0, then either all of them equal 0, or the greatest among them is > 0 and the smallest is < 0).

First let's consider the case when b = 0. In this case, the equation a + b + c + d = 0 becomes a + c + d = 0, and the numbers cd - ab and $a^n+b^n+c^n+d^n$ are equal to cd and $a^n+c^n+d^n$, respectively. Hence, proving that the numbers cd - ab and $a^n+b^n+c^n+d^n$ have the same sign is equivalent to proving that the numbers cd and $a^n+c^n+d^n$ have the same sign. Since a > 0, the signs of the numbers cd and acd are equal. Hence, we have to prove that the numbers acd and $a^n+c^n+d^n$ have the same sign. But this trivially follows from part [b](a)[/b] of the problem, remembering that a + c + d = 0. Hence, we have solved part [b](b)[/b] of our problem for the case b = 0. Thus, in the following, we may assume that $b\neq 0$. By a similar argument, we handle the case c = 0, and thus, in the following, we will assume that $c\neq 0$. Hence, we have assumed that both numbers b and c are nonzero.

Now we distinguish between three cases:

[b]Case 1.[/b] We have b > 0 and c > 0.
[b]Case 2.[/b] We have b > 0 and c < 0.
[b]Case 3.[/b] We have b < 0 and c < 0.

(Maybe you are missing the case when b < 0 and c > 0 - but this case is impossible, since we must have $b\geq c$.)

First we consider Case 1. In this case, b > 0 and c > 0. Together with a > 0 and d < 0, this yields ab > 0 and cd < 0, so that cd - ab < 0. On the other hand, since the numbers a, b, c are positive, the number a + b is positive, too; thus, using Lemma 1, we get $a^n+b^n<\left(a+b\right)^n$ and $\left(a+b\right)^n+c^n<\left(\left(a+b\right)+c\right)^n$; thus, $a^n+b^n+c^n=\left(a^n+b^n\right)+c^n<\left(a+b\right)^n+c^n<\left(\left(a+b\right)+c\right)^n=\left(a+b+c\right)^n$. But a + b + c + d = 0 yields a + b + c = -d, and since n is an odd integer, this yields $\left(a+b+c\right)^n=-d^n$. Thus, $a^n+b^n+c^n<-d^n$, and $a^n+b^n+c^n+d^n<0$. So we have found that both numbers cd - ab and $a^n+b^n+c^n+d^n$ are negative; thus, they have the same sign.

Similarly we can handle Case 3; in this case, the numbers cd - ab and $a^n+b^n+c^n+d^n$ are positive and thus have the same sign.

Hence, we have shown that the numbers cd - ab and $a^n+b^n+c^n+d^n$ have the same sign in the Cases 1 and 3. Remains the Case 2. In this case, b > 0 and c < 0. On the other hand, we know that a > 0 and d < 0. Since a + b + c + d = 0, we have a + b = - (c + d). Let's denote $m=\frac{a+b}{2}=\frac{-\left(c+d\right)}{2}$ and $x=\frac{a-b}{2}$ and $y=\frac{c-d}{2}$. Then, the number m is positive (since $m=\frac{a+b}{2}$, and a and b are positive), and the numbers x and y are $\geq 0$ (since $x=\frac{a-b}{2}$ and $a\geq b$, and $y=\frac{c-d}{2}$ and $c\geq d$). We have $m+x=\frac{a+b}{2}+\frac{a-b}{2}=a$, $m-x=\frac{a+b}{2}-\frac{a-b}{2}=b$, $-\left(m-y\right)=-\left(\frac{-\left(c+d\right)}{2}-\frac{c-d}{2}\right)=c$ and $-\left(m+y\right)=-\left(\frac{-\left(c+d\right)}{2}+\frac{c-d}{2}\right)=d$. Thus, $cd-ab=\left(-\left(m-y\right)\right)\left(-\left(m+y\right)\right)-\left(m+x\right)\left(m-x\right)=x^2-y^2$.
Now we distinguish between three subcases:

[b]Subcase 1.[/b] We have x < y.
[b]Subcase 2.[/b] We have x = y.
[b]Subcase 3.[/b] We have x > y.

First, we consider Subcase 3. In this subcase, x > y, and thus m + x > m + y. But m + x = a, and m + y = -d (since - (m + y) = d). Thus, a > -d. Also, we know that a + b = - (c + d); in other words, a + b = (-d) + (-c). Finally, we know that $a\geq b$ and $-d\geq -c$ (the latter is because $c\geq d$). Hence, we have $\left(a;\;b\right)\succ\left(-d;\;-c\right)$; here, majorization is to be understood in the stronger sense of this word (so, for strictly convex functions, we have strict inequality in the Karamata inequality). Also, the numbers a, b, -d and -c are all positive (since a > 0, b > 0, d < 0 and c < 0). Hence, by the Karamata inequality, applied to the two number arrays (a; b) and (-d; -c) satisfying $\left(a;\;b\right)\succ\left(-d;\;-c\right)$ and to the function $f\left(t\right)=t^n$ which is strictly convex on $\mathbb{R}^+$ (since n > 1), we get $a^n+b^n>\left(-d\right)^n+\left(-c\right)^n$ (as we have said, we have strict inequality). Since n is odd, we have $\left(-d\right)^n=-d^n$ and $\left(-c\right)^n=-c^n$; thus, we obtain $a^n+b^n>\left(-d^n\right)+\left(-c^n\right)$. Hence, $a^n+b^n+c^n+d^n>0$. On the other hand, since x and y are $\geq 0$, and since x > y, we have $x^2>y^2$, and thus $x^2-y^2>0$, so that $cd-ab=x^2-y^2>0$. Hence, the numbers cd - ab and $a^n+b^n+c^n+d^n$ are both positive, and thus they have the same sign.

Similarly, in the Subcase 1, one shows that the numbers cd - ab and $a^n+b^n+c^n+d^n$ are both negative, and thus they have the same sign.

Finally, consider the Subcase 2. In this case, x = y, and thus m + x = m + y. But m + x = a and m + y = -d (since - (m + y) = d). Thus, a = -d, and thus, since the integer n is odd, $a^n=-d^n$. Similarly, $b^n=-c^n$. Thus, $a^n+b^n+c^n+d^n=\left(-d^n\right)+\left(-c^n\right)+c^n+d^n=0$. On the other hand, x = y yields $cd-ab=x^2-y^2=y^2-y^2=0$. Hence, the numbers cd - ab and $a^n+b^n+c^n+d^n$ are both zero, and thus they have the same sign.

Altogether, we have seen that in every possible case, the numbers cd - ab and $a^n+b^n+c^n+d^n$ have the same sign. Thus, part [b](b)[/b] of the problem is solved.

What really aggravates me about this problem is that the solution is absolutely straightforward, but almost impossible to write up properly. Reminds me of problem 1 from the BWM 2005 first round...

[[b]EDIT:[/b] The original, non-general problem was also discussed at http://www.mathlinks.ro/Forum/viewtopic.php?t=4256 .]

  Darij


Here's some questions where I hope you people can help me with  :) !

Q1. If 2^1000 is divided by 5, what will the remainder be?
<Hint: Consider dividing 2^1, 2^2, 2^3.....etc by 5>

I have absolutely no clue on this one  :( .

Q2. At 6pm, the hands of a clock are 180o apart. How long will it be before the hands of clock are 180o apart again.

Thats all for now!

[hide="1"]You should look for a pattern here, or just do some simple modular arithmetic,

$2^{1000}=16^{250}\equiv 1^{250}\equiv1 \mod 5$[/hide]

[quote="Heldensheld"]
Q2. At 6pm, the hands of a clock are 180o apart. How long will it be before the hands of clock are 180o apart again.
[/quote]
[hide] If you think about it, the next occurence must be after 7:00. Let $x$ be the number of minutes after 7 pm. The minute hand is at $6x^{\circ}$. The hour hand is at $(\frac{7}{12}*360+\frac{x}{2})^{\circ}=(210+\frac{x}{2})^{\circ}$, since there are 720 minutes in 12 hours, so each minute is half a degree.
$210+\frac{x}{2}-180=6x$.
$30+\frac{x}{2}=6x$.
$60+x=12x$.
$11x=60$.
$x=\frac{60}{11}=5+\frac{5}{11}$. So the answer is $\boxed{65+\frac{5}{11}}$. [/hide]


[quote="Rust"][quote="Redriver"]
Equation in natural $x(x+1)(x+2)....(x+k-1)=y^{2},k>1$ have not solutions.[/quote][/quote]

Can you prove it for me ?

Solution is long. I give it in russian forum.

Can you type it again for me to see :( ?

Forum adress: http//lib.mexmat.ru/forum/ .

But I don't understand this language :( !

It is a famous result due to Erdos and Selfridge.

It isn't so difficult to prove that this equation has not solutions for y>0.Suppose there is a solution (x,y) and suppose that  that p is the greater prime divisor of x(x+1)(x+2)....(x+k-1)=y^2 then and 2p must divide it.Usin'g Bertrand's postulate there is a prime q which divide           x(x+1)....(x+k-1) but p<q<2p .......


[quote="909"]PS. I'm forigner yeah.. my english is too bad.. so I hope understand my proof :)

Zero inverse number is exist.

0xa = 1

is false.

so a is ALL NUMBERS

now
A is set
A have all numbers
A have also "a"

but

this is can't exist, because  by axiom of choice.

so  "a" is element(All set is can't have this)

thus 0 inverse number is exist..

I started call "a" number is trans-infinite(or end of infinite)

for example

Possible 1^a = 3(or anything)

How do you think of that.[/quote]

Let me try to get that into better English.

There exists an additive inverse of zero

for any real number $a$, $a\times0=1$ is false

Call $A$ the set of all numbers
$A$ also includes $a$

but this cannot exist, because by the axiom of choice,
$a$ must be in all subsets of $A$
but that is not possible
so $a$ is trans-infinite
therefore it is possible that there is a number $a$ such that $1^{a}=3$ and other things like that
e.g. the inverse of zero

I don't really understand
maybe I'm not rephrasing this correctly

but I am pretty sure that the axiom of choice states
that every subset in a given set
has at least one element in common
with at least one other subset in that set

which may throw off the proof completely...


show that the set of positive integers which cant be represented  as the sum of distinct perfect suare is finite.

The largest integer which is not the sum of unequal squares is $128.$
This result is due to Sprague (1947-1949).

You may have a look here :
http://www.kalva.demon.co.uk/short/soln/sh00n6.html

More generally, for each $k$, there is a largest integer, say $f(k)$, which is not the sum of unequal $k$-powers.
Sprague's result is $f(2) = 128.$
Using computers, Dressler and Parks have shown that $f(3) = 12758.$

Pierre.


For $ V\subset\mathbb{R}$ and $ a,b\in V$ , define

$ a\plus{}b\equal{}a.b$

$ a\times b\equal{}a^{b}$

Prove that $ V$ is a vector space.

My problem is , $ a\plus{}0\equal{}0\neq a$ . Hence the zero vector does not exist . So how can $ V$ be vector space ?

[quote="perfect_radio"]$ 1$ is the zero vector here.[/quote]

but isn't that "zero vector" has to be in the form $ (0,0,0....,0)$ ? How to define "zero vector" ?? Thanks

The zero vector doesn't have to have any "necessary form." It just has to satisfy $ a\plus{}\text{zero vector}\equal{} a$ for all $ a\in V$. And there has to be additive inverses, so for all $ a\in V$ there must exist a $ \minus{}a\in V$ such that $ a\plus{}(\minus{}a) \equal{}\text{zero vector}$.

In this case $ \minus{}a \equal{}\frac{1}{a}$ and $ a\plus{}1 \equal{} a(1) \equal{} a$ so it is the zero vector.

It'd not a vector space- the operations aren't defined everywhere.


Today, I work out a simple problem,but i don't know the meaning of it:

If $ rank(A) \equal{} r$, then we can write $ A$ as the follow form:

$ A \equal{} \sum_{k\equal{}1}^{r}A_{k}$ ,where $ rank(A_{k}) \equal{} 1$

It's a simple problem because:

$ A \equal{} P\begin{bmatrix}E_{r}&0\\0&0\end{bmatrix}Q$ ,where $ P$ and $ Q$ are full rank

then $ A \equal{} \sum_{k\equal{}1}^{r}PE_{kk}Q$, where $ E_{kk}$ means the intercross of k-row and k-column of the matrix is $ 1$, other elements is $ 0$.

obviously, $ rank(PE_{kk}Q) \equal{} rank(E_{kk}) \equal{} 1$

And my question is : what does this mean? In other words, this conclusion tell us what?

This is tensor rank, which I explained [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1397138#1397138]here[/url].


Can you tell me what is Angle Chasing??
It is a part the AoPS book, but i am in China and i don't have a copy, so can you explain what it is??
Thanks!

here is the copy of the first page of angle chasing
Click the pictuer, it will enlarge it

Thank you so much...
For 236 and 237, you just find the measure of the angles step by step and get the final answer. Is that what we call angle chasing?

thanks for showing me what angle chasing is too!
 :D


search
function
induction
linear algebra
matrix
vector
modular arithmetic

1. If $ a$ and $ b>2$ are any positive integers, prove that $ 2^a+1$ is not divisible by $ 2^b-1$.

2. a) Prove that if $ m>n$ then $ a^{2^n}+1$ is a divisor of $ a^{2^m}-1$.
    b) Show that if $ a,m,n$ are positive with $ m%Error. "neqn" is a bad command.
$, then $ (a^{2^m}+1, a^{2^n}+1) =$ $ 1$ if $ a$ is even, and $ 2$ if $ a$ is odd.

3. Show that if $ (a,b)=1$ and $ p$ is an odd prime, then $ (a+b, \frac{a^p+b^p}{a+b}) = 1$ or $ p$.

4. Let $ a$ and $ b$ be positive integers such that $ (1+ab)|(a^2+b^2)$. Show that the integer $ \frac{a^2+b^2}{1+ab}$ must be a perfect square.

5. Given integers $ a,b,c,d,m,n,u,v$ satisfying $ ad-bc=\pm1$, $ u=am+bn$, $ v=cm+dn$, prove that $ (m,n)=(u,v)$.

6. Consider the set $ \psi$ of integers $ 1,2,...,n$. Let $ 2^k$ be the integer in $ \psi$ that is the highest power of $ 2$. Prove that $ 2^k$ is not a divisor of any other integer in $ \psi$. Hence, prove that $ \sum_{j=1}^{n}\frac{1}{j}$ is not an integer if $ n>1$.

7. Prove $ {1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+...+\frac{1}{1999}-\frac{1}{2000}=\frac{1}{1001}+\frac{1}{1002}+\frac{1}{1003}+...+\frac{1}{2000}}$. Note the left side consists of alternating signs while the right side is all addition. Hint: It may be easier to prove a general case rather than a specific case.

As a side note, I believe number 4 is the hardest one on here, with number 5 being the easiest. I've also solved 2a, but would like verification whether the proof is written well.

Nearly all of these have been posted before.  #4, in particular, is an extremely well-known IMO problem, #6 is posted about once a week, and #7 is a lemma in yet another well-known problem.

It is usually considered bad form to post multiple questions in a topic.  Please limit your questions per post and do a little more searching first.

[hide]Proof of 2a:

Note that

$ a^{2^m} \minus{} 1 \equal{} (a^{2^{m \minus{} 1}} \plus{} 1)(a^{2^{m \minus{} 1}} \minus{} 1) \equal{} (a^{2^{m \minus{} 1}} \plus{} 1)(a^{2^{m \minus{} 2}} \plus{} 1)(a^{2^{m \minus{} 2}} \minus{} 1) \equal{} (a^{2^{m \minus{} k}} \minus{} 1)\prod_{i \equal{} 1}^{k}(a^{2^{m \minus{} i}} \plus{} 1)$.

Thus as long as $ n \equal{} m \minus{} 1, n \equal{} m \minus{} 2, n \equal{} m \minus{} 3, ... , n \equal{} m \minus{} k$, then $ a^{2^n} \plus{} 1|a^{2^m} \minus{} 1$. In order for this to be possible, $ m > n$.

The phrasing seems a little bit weird, is there any other way to phrase it better?
[/hide]

EDIT: My bad t0rajir0u, I will search before I post next time >_<. Sorry about that!

Could someone help me find/solve some of these? I'm having a difficult time finding some of these.

The only one I've found so far is #4 and #3

Also, I think I solved the first part of #6:
[hide="Proof for first part of #6"]Note $ 2^k$ doesn't divide any of the integers in $ \psi < 2^k$ since if $ a > b$, then $ a$ does not divide $ b$. For the integers in $ \psi > 2^k$, we assume the case where $ \psi$ consists of the max possible number of integers. In other words, $ n \equal{} 2^{k \plus{} 1} \minus{} 1$. It is clear that $ 2 * 2^k > 2^{k \plus{} 1} \minus{} 1$ and $ 1 * 2^k < 2^k \plus{} 1$. Thus, each integer in $ \psi > 2^k$ can be written as $ 2^k * x$ for $ 1 < x < 2$. Since x cannot be an integer, $ 2^k$ does not divide $ \psi$.[/hide]

I think I also solved #1, please point out any errors you see in this proof:

[hide="Proof for #1"]Assume $ 2^b \minus{} 1|2^a \plus{} 1$.
By long division, we see that $ \frac {2^a \plus{} 1}{2^b \minus{} 1} \equal{} 2^{a \minus{} b} \plus{} 2^{a \minus{} 2b} \plus{} \frac {1 \plus{} 2^{a \minus{} 2b}}{2^b \minus{} 1}$.
We note two things: first, $ \frac {1 \plus{} 2^{a \minus{} nb}}{2^b \minus{} 1} \equal{} 2^{a \minus{} (n \plus{} 1)b} \plus{} 2^{a \minus{} (n \plus{} 2)b} \plus{} \frac {1 \plus{} 2^{a \minus{} (n \plus{} 2)b}}{2^b \minus{} 1}$ for any integer $ n$. Second, $ 2^{a \minus{} nb} \plus{} \frac {1 \plus{} 2^{a \minus{} nb}}{2^b \minus{} 1} \equal{} \frac {1 \plus{} 2^{a \minus{} (n \minus{} 1)b}}{2^b \minus{} 1}$.

Thus, $ (\sum_{k \equal{} 1}^{n}2^{a \minus{} kb}) \plus{} \frac {1 \plus{} 2^{a \minus{} nb}}{2^b \minus{} 1} \equal{} q \plus{} r$ for some quotient $ q$ and remainder $ r$, with $ r \equal{} 0$ since we assumed $ 2^b \minus{} 1|2^a \plus{} 1$.

Let $ n$ be $ n$ such that $ a \minus{} nb$ is the first negative $ a \minus{} nb$.
Note $ 2^{a \minus{} b} \plus{} ... \plus{} 2^{a \minus{} (n \minus{} 1)b} \equal{}$ an integer.
However, $ 2^{a \minus{} nb} \plus{} \frac {1 \plus{} 2^{a \minus{} nb}}{2^b \minus{} 1} \equal{} \frac {1}{2^{|a \minus{} nb|}} \plus{} \frac {1 \plus{} \frac {1}{2^{|a \minus{} nb|}}}{2^b \minus{} 1} \equal{} \frac {2^b \plus{} 2^{|a \minus{} nb|}}{2^{|a \minus{} nb|}(2^b \minus{} 1)}$.

Let $ b \equal{}$ the smallest possible $ b \equal{} 3$.
Then $ 2^b \plus{} 2^{|a \minus{} nb|} < 2^{|a \minus{} nb|}(2^b \minus{} 1)$ because $ 8 \plus{}$ (a power of 2) $ <$ (a power of 2) $ * 7$
This statement clearly holds for $ b > 3$ and thus all possible values of $ b$.

This contradiction implies $ 2^{a \minus{} nb} \plus{} \frac {1 \plus{} 2^{a \minus{} nb}}{2^b \minus{} 1}$ is not an integer, and thus $ r$ cannot equal $ 0$ (because $ q$ must be an integer).

Therefore, $ 2^a \plus{} 1$ is not divisible by $ 2^b \minus{} 1$.
[/hide]

[hide="Generating functions for 7"]
Statement: \[ 1 \minus{} \frac{1}{2} \plus{} \frac{1}{3} \minus{} \frac{1}{4} \plus{} \cdots \plus{} \frac{1}{2n\minus{}1} \minus{} \frac{1}{2n} \equal{} \frac{1}{n\plus{}1} \plus{} \frac{1}{n\plus{}2} \plus{} \cdots \plus{} \frac{1}{2n}\]

This is a simple exercise in induction, however I propose an alternative proof.
Proof:

The generating function for the left hand side as coefficient of $ x^{2n}$,

\[ \frac{\log(1\plus{}x)}{1\minus{}x} \equal{} x \plus{} (1 \minus{} \frac{1}{2}) x^2 \plus{} \cdots\]

We can discard the odd powers of this generating function by replacing x with -x then averaging this new function with the one above,

\[ \frac{1}{2}\left( \frac{\log(1\plus{}x)}{1\minus{}x} \plus{} \frac{\log(1\minus{}x)}{1\plus{}x}\right)\]

For the right hand side, we construct the generating functions,

\[ \minus{}\frac{\log(1\minus{}x)}{1\minus{}x} \equal{} x \plus{} (1 \plus{} \frac{1}{2})x^2 \plus{} \cdots\]

\[ \minus{}\frac{\log(1\minus{}x^2)}{1\minus{}x^2} \equal{} x^2 \plus{} (1 \plus{} \frac{1}{2})x^4 \plus{} \cdots\]

Subtracting the second from the first, then discarding the odd powered terms using the aforementioned technique gives the generating function for the RHS. Finally we get that the LHS = RHS if,

\[ \minus{}\frac{\log(1\minus{}x^2)}{x^2 \minus{} 1} \plus{} \frac{\log(1\minus{}x)}{2(x\minus{}1)} \minus{} \frac{\log(1\plus{}x)}{2(x\plus{}1)} \equal{} \frac{1}{2}\left( \frac{\log(1\plus{}x)}{1\minus{}x} \plus{} \frac{\log(1\minus{}x)}{1\plus{}x}\right)\]

Which is a simple exercise in algebra.

[/hide]

Wow nice Javaman, that is an interesting alternative proof.

I just proved #7 via brute force:

[hide="Brute Force Proof for #7"]We first move all the members with even denominators to the right side and with odd denominators to the left side to get $ {1+\frac{1}{3}+...+\frac{1}{999}=\frac{1}{2}+\frac{1}{4}+...+\frac{1}{1000}+\frac{2}{1002}+\frac{2}{1004}+...+\frac{2}{2000}}$.

We simplify further by reducing the $ \frac{2}{x}$ terms, with each term either canceling out a term from the left side or doubling a term from the right side. We repeat this procedure as follows:

First simplification:
$ {1+\frac{1}{3}+...+\frac{1}{499}=\frac{1}{2}+\frac{1}{4}+...+\frac{1}{500}+\frac{2}{502}+\frac{2}{504}+...+\frac{2}{1000}}$

Second simplification:
$ {1+\frac{1}{3}+...+\frac{1}{249}=\frac{1}{2}+\frac{1}{4}+...+\frac{1}{250}+\frac{2}{252}+\frac{2}{254}+...+\frac{2}{500}}$

.
.
.
.
.

Eighth simplification:
$ 1+\frac{1}{3}=\frac{1}{2}+\frac{2}{4}+\frac{2}{6}$

We end up with $ 1=1$.

[/hide]

[hide="Another way for #7"]
It's kind of similar to yours ark_xm, but:
$ 1\minus{}\frac{1}{2}\plus{}...\minus{}\frac{1}{2n}\equal{}(1\plus{}\frac{1}{2}\plus{}\frac{1}{3}\plus{}...\plus{}\frac{1}{2n})\minus{}(\frac{2}{2}\plus{}\frac{2}{4}\plus{}...\plus{}\frac{2}{2n})\equal{}\frac{1}{n\plus{}1}\plus{}\frac{1}{n\plus{}2}\plus{}...\plus{}\frac{1}{2n}$
Done!
[/hide]

[hide="Proof for number 5"]

Let $ (m,n) = d$.
Since $ d|m$ and $ d|n$, $ d|mx + ny$ for any integers $ x$ and $ y$.
In other words $ d$ divides any linear combination of $ m$ and $ n$.
Thus, $ d|am + bn = u$ and $ d|cm + dn = v$.
Therefore, $ d = (m,n)\le(u,v)$ by definition of the greatest common divisor of $ u$ and $ v$. (If $ d > (u,v)$, then $ (u,v)$ wouldn't be true)

Now we want to show $ (u,v)\le(m,n)$ in order to prove $ (u,v) = (m,n)$.
Assume a matrix $ A = \begin{pmatrix} a' & b' \\
c' & d'\end{pmatrix}$ where $ a' = \frac {d}{ad - bc}, b' = \frac { - b}{ad - bc}, c' = \frac { - c}{ad - bc},$ and $ d' = \frac {a}{ad - bc}$.
We then multiply $ A$ by a vector $ \begin{pmatrix} u \\
v \end{pmatrix}$ to get

\begin{eqnarray*} \begin{pmatrix} a' & b' \\
c' & d'\end{pmatrix} \begin{pmatrix} u \\
v \end{pmatrix} & = & \begin{pmatrix}\frac {du}{ad - bc} - \frac {bv}{ad - bc} \\
\frac { - cu}{ad - bc} + \frac {av}{ad - bc}\end{pmatrix} \\
& = & \begin{pmatrix}\frac {dam + dbn - bcm - dbn}{ad - bc} \\
\frac { - cam - cbn + cam + adn}{ad - bc}\end{pmatrix} \\
& = & \begin{pmatrix}\frac {m(ad - bc)}{ad - bc} \\
\frac {n(ad - bc)}{ad - bc} \end{pmatrix} \\
& = & \begin{pmatrix} m \\
n \end{pmatrix}\end{eqnarray*}

Note that since $ ad - bc = \pm1$, the elements of $ A$ are all integers. Thus $ m$ and $ n$ can be written as a linear combination of $ u$ and $ v$ (e.g. $ m = a'u + b'v, n = c'u + d'v$).

Thus, using the same idea as in the beginning of the proof, let $ (u,v) = g$.
Since $ g|u$ and $ g|v$, $ g$ divides any linear combination of $ u$ and $ v$.
So $ g|a'u + b'v = m$ and $ g|c'u + d'v = n$.
Therefore, $ g = (u,v)\le(m,n)$ by definition of the greatest common divisor of $ m$ and $ n$.

$ (u,v)\le(m,n)$ and $ (m,n)\le(u,v)$ concludes that $ (m,n) = (u,v)$.

[/hide]

If possible, it'd be great if someone could go through my proofs and make sure there's no error/ambiguousness. I'm new to doing rigorous proofs and would appreciate any sort of feedback. Thanks :)

[hide="Complete proof of #2"]

For the first part, note that
\begin{eqnarray*}a^{2^m} - 1 & = & (a^{2^{m - 1}} + 1)(a^{2^{m - 1}} - 1) \\
& = & (a^{2^{m - 1}} + 1)(a^{2^{m - 2}} + 1)(a^{2^{m - 2}} - 1) \\
& . & \\
& . & \\
& . & \\
& = & (a^{2^{m - k}} - 1)\prod_{i = 1}^{k}(a^{2^{m - i}} + 1) \end{eqnarray*}
where $ k$ can be any positive integer.

Since $ m > n$, we can express $ n$ as $ n = m - x$ for some positive integer $ x$.
Thus $ a^{2^n} + 1$ = $ a^{2^{m - x}} + 1$, which will always be a factor for $ a^{2^m} - 1$ as shown above.
In other words, as long as $ n = m - 1, n = m - 2, n = m - 3, ... ,$ or $ n = m - k$, then $ a^{2^n} + 1|a^{2^m} - 1$.
Since $ m > n$, this concept can be applied.

For the second part, let $ (a^{2^m} + 1, a^{2^n} + 1) = d$.
Since $ m \neq n$ and $ (x,y) = (y,x)$ for any integers $ x$ and $ y$, we can assume $ m > n$ (or $ n > m$) without loss of generality.
We see that $ d|a^{2^n + 1}$ because it is the greatest common divisor, and $ a^{2^n + 1}|a^{2^m} - 1$ due to the first part of this question (we assumed $ m > n$).
Thus $ d$ also divides $ a^{2^m} - 1$.
Because $ d|a^{2^m} + 1$ and $ d|a^{2^m} - 1$, $ d|(x)(a^{2^m} + 1) + y(a^{2^m} - 1)$ for some integers $ x$ and $ y$.
Let $ x = 1$ and $ y = - 1$.
Then $ d|2$ and thus $ d = 1$ or $ d = 2$.

Now we take a look at when $ a$ is odd/even.

When $ a$ is even, $ a^{2^m} + 1$ and $ a^{2^n} + 1$ are both odd. This implies $ d = 1$ ($ d = 2$ would mean $ 2$ can divide odd numbers, which is false).

When $ a$ is odd, $ a^{2^m} + 1$ and $ a^{2^n} + 1$ are both even. This implies $ d = 2$ ($ d = 1$ would not be the greatest common divisor because $ 2$ divides all even numbers and $ 2 > 1$).
[/hide]

[hide="Complete proof of 2nd part of #6"]
Let $ l$ be the least common multiple of the set $ \beta = \{1,2,3,...,n\}$. Then
\begin{eqnarray*}\sum_{j = 1}^{n}\frac {1}{j} & = & \frac {1}{1} + \frac {1}{2} + ... + \frac {1}{n} \\
& = & (\frac {1}{1} + \frac {1}{2} + ... + \frac {1}{n})(\frac {l}{l}) \\
& = & \frac {\frac {l}{1} + \frac {l}{2} + ... + \frac {l}{n}}{l}\end{eqnarray*}

Since $ n > 1$, the unique factorization of $ l$ must contain some power of $ 2$ because there must be at least one even number in $ \beta$. In fact, $ l$ must contain the integer in $ \beta$ that is the highest power of $ 2$, which we will denote as $ 2^k$, because the least common multiple of a given set is defined as the product of the highest powers of the prime numbers that divide any member of the set. In this case, $ 2^k|2^k$. Thus $ l$ can be written as $ 2^kx$ for some odd number $ x$ that satisfies $ 2^kx = l$. The reason $ x$ is odd is because $ 2$ is the only prime number and thus any product of prime numbers excluding $ 2$ will result in an odd number (odd number $ *$ odd number $ =$ odd number).

We can then rewrite $ \frac {\frac {l}{1} + \frac {l}{2} + ... + \frac {l}{n}}{l}$ as $ \frac {\frac {2^kx}{1} + \frac {2^kx}{2} + ... + \frac {2^kx}{n}}{2^kx}$.

We need to show that the numerator and the denominator of this equation is either odd and even, or even and odd, in order to prove $ \sum_{j = 1}^{n}\frac {1}{j}$ is not an integer.

Since the denominator $ 2^kx$ is even (because an even number $ 2^k$ multiplied by an odd number $ x$ is always even), we need to show the numerator is odd.

Note that every number in set $ \beta$ divides $ l$ by definition of the least common multiple. This implies $ \frac {2^kx}{i}$ for $ i = 1,2,...,n$ is always an integer.
Also note that from the first part of the question, $ 2^k$ does not divide any other integer in $ \beta$. This implies the only odd number in the numerator $ \frac {2^kx}{1} + \frac {2^kx}{2} + ... + \frac {2^kx}{n}$ is $ \frac {2^kx}{2^k}$
because none of the denominators can cancel out $ 2^k$ and thus all terms except $ \frac {2^kx}{2^k}$ is being multiplied by an even number $ 2^x$ where $ 1 \le x \le k$.

Because the sum of even numbers results in an even number, the numerator can be viewed as the sum of the even number $ \sum_{j = 1}^{n}(\frac {2^kx}{1} + \frac {2^kx}{2} + ... + \frac {2^kx}{n}) - \frac {2^kx}{2^k}$ and the odd number $ \frac {2^kx}{2^k}$. Therefore, the numerator must be odd because an even number plus an odd number is an odd number.

Thus we have shown that $ \sum_{j = 1}^{n}\frac {1}{j}$ cannot be an integer because an even denominator does not divide an odd numerator.

 [/hide]

[hide="non-brute force proof for #7"]
Proof by induction:
Assume the general case
\begin{eqnarray*}(\frac {1}{1} - \frac {1}{2}) + ... + (\frac {1}{n - 1} - \frac {1}{n}) & = & \frac {1}{\frac {n}{2} + 1} + \frac {1}{\frac {n}{2} + 2} + ... + \frac {1}{\frac {n}{2} + \frac {n}{2}} \\
& = & \sum_{i = \frac {n}{2} + 1}^{\frac {n}{2}}\frac {1}{i}\end{eqnarray*}
holds for $ n =$ any positive even integer.

Testing the base case $ n = 2$, we get
$ \frac {1}{1} - \frac {1}{2} = \frac {1}{\frac {2}{2} + 1}$
$ \frac {1}{2} = \frac {1}{2}$.

Assume the general case holds for $ n$. By induction, we need to show it also holds for $ n + 2$.

\begin{eqnarray*}(\frac {1}{1} - \frac {1}{2}) + ... + (\frac {1}{n - 1} - \frac {1}{n}) + (\frac {1}{n + 1} - \frac {1}{n + 2}) & = & \sum_{i = \frac {n}{2} + 1}^{\frac {n}{2}}\frac {1}{i} + (\frac {1}{n + 1} - \frac {1}{n + 2}) \\
& = & \frac {1}{\frac {n}{2} + 1} + \sum_{i = \frac {n}{2} + 2}^{\frac {n}{2} - 1}\frac {1}{i} + (\frac {1}{n + 1} - \frac {1}{n + 2}) \\
& = & \sum_{i = \frac {n}{2} + 2}^{\frac {n}{2} - 1}\frac {1}{i} + \frac {1}{n + 1} + \frac {1}{\frac {n}{2} + 1} - \frac {1}{n + 2} \\
& = & \sum_{i = \frac {n}{2} + 2}^{\frac {n}{2} - 1}\frac {1}{i} + \frac {1}{n + 1} + \frac {n + 2 - \frac {n}{2} - 1}{(\frac {n}{2} + 1)(n + 2)} \\
& = & \sum_{i = \frac {n}{2} + 2}^{\frac {n}{2} - 1}\frac {1}{i} + \frac {1}{n + 1} + \frac {\frac {n}{2} + 1}{(\frac {n}{2} + 1)(n + 2)} \\
& = & \sum_{i = \frac {n}{2} + 2}^{\frac {n}{2} - 1}\frac {1}{i} + \frac {1}{n + 1} + \frac {1}{n + 2} \\
& = & \frac {1}{\frac {n + 2}{2} + 1} + \frac {1}{\frac {n + 2}{2} + 2} + ... + \frac {1}{\frac {n + 2}{2} + \frac {n}{2} - 1} + \frac {1}{n + 1} + \frac {1}{n + 2} \\
& = & \frac {1}{\frac {n + 2}{2} + 1} + \frac {1}{\frac {n + 2}{2} + 2} + ... + \frac {1}{n} + \frac {1}{n + 1} + \frac {1}{n + 2} \\
& = & \sum_{i = \frac {n + 2}{2} + 1}^{\frac {n + 2}{2}} \frac {1}{i} \end{eqnarray*}

Thus, $ {1 - \frac {1}{2} + \frac {1}{3} - \frac {1}{4} + ... + \frac {1}{1999} - \frac {1}{2000} = \frac {1}{1001} + \frac {1}{1002} + \frac {1}{1003} + ... + \frac {1}{2000}}$ is true because this is simply an instance of the general case with $ n = 2000$.

[/hide]

[hide="proof of #3"]
Since $ x^n + y^n = (x + y)(x^{n - 1} - x^{n - 2}y + x^{n - 3}y^2 - ... + y^{n - 1})$ when $ n$ is odd, we can rewrite $ \frac {a^p + b^p}{a + b}$ as $ (a^{p - 1} - a^{p - 2}b + a^{p - 3}b^2 - ... + b^{p - 1})$ (because $ p$ is given to be odd).

Let the function $ f(b) = (a^{p - 1} - a^{p - 2}b + a^{p - 3}b^2 - ... + b^{p - 1})$.

Note that $ b\equiv - a \pmod {a + b}$ by definition.. This means $ f(b)\equiv f( - a) \pmod{a + b}$ because of the multiplication and addition properties for congruence.

(e.g. Let a polynomial $ g(x) = c_0 + c_1 x + c_2 x^2 + ... + c_n x^n$ for some constant $ c_i : 0 \le i \le n$.
If $ u\equiv v \pmod m$ for some integers $ u, v,$ and $ m$, then
$ \begin {eqnarray*}u^2 \equiv v^2\pmod m & \Rightarrow & u^n \equiv v^n \pmod m \\
& \Rightarrow & c_n u^n \equiv c_n v^n \pmod m \\
& \Rightarrow & c_{n - 1} u^{n - 1} \equiv c_{n - 1} v^{n - 1} \pmod m \\
& \Rightarrow & c_0 + c_1 u + c_2 u^2 + ... + c_n u^n \equiv c_0 + c_1 v + c_2 v^2 + ... + c_n v^n\pmod m \\
& \Rightarrow & g(u) \equiv g(v)\pmod m \end {eqnarray*}$
)

Thus,
$ \begin{eqnarray*}a^{p - 1} - a^{p - 2}b + a^{p - 3}b^2 - ... + b^{p - 1} & \equiv & a^{p - 1} - a^{p - 2}( - a) + a^{p - 3}( - a)^2 - ... + ( - a)^{p - 1} \pmod {a + b} \\
& \equiv & pa^{p - 1} \pmod {a + b} \end {eqnarray*}$
We can simplify to $ pa^{p - 1}$ since each term can be expressed generally as $ ( - 1)^j(a)^i( - a)^j$ with $ i + j = p - 1$. So $ ( - 1)^j(a)^i( - a)^j = ( - 1)^{2j}(a)^{i + j} = a^{p - 1}$. Since we have $ p$ terms of $ a^{p - 1}$, we end up with $ pa^{p - 1}$.

Next we use the fact that if $ x\equiv y \pmod m$, then $ (x,m) = (y,m)$ to see that $ (\frac {a^p + b^p}{a + b}, a + b) = (pa^{p - 1}, a + b) = d$ for some integer $ d$.
This implies $ d|a + b$ and $ d|pa^{p - 1}$.

Since we're given $ (a,b) = 1$, we can say $ (a, a + b) = 1 \Rightarrow (a^{p - 1}, a + b) = 1$ because $ a$ and $ a + b$ are coprime (so multiplying $ a$ by itself will not change the greatest common divisor).

If $ d|a + b$ and $ (a^{p - 1},a + b) = 1$, then $ (d,a^{p - 1}) = 1$.

Therefore, $ d|p$ since $ d$ is coprime to $ a^{p - 1}$ and $ d|pa^{p - 1}$.

Since $ p$ is a prime number, then $ d$ must be $ 1$ or $ p$.
[/hide]

[hide="proof of #4"]
Let $ \frac{a^2+b^2}{1+ab} = k$ for some integer $ k$.
Assume $ k$ is not a perfect square.
Consider all possible combinations of pairs $ (a,b)$, where $ a$ and $ b$ are positive integers, such that $ \frac{a^2+b^2}{1+ab} = k$ for a fixed integer $ k$.
Suppose that $ (a',b')$ is the pair that minimizes the sum of $ a+b$ over all possible pairs $ (a,b)$ .
Without loss of generality, we can assume $ a' \ge b'$.

We then get $ \frac{a^2+(b')^2}{1+ab'} = k$ by plugging $ b'$ into $ b$. This can be rewritten as a quadratic of the form

$ a^2 - (kb')a + ((b')^2-k) = 0$.

By Vieta's formula, we know that for any quadratic, $ ax^2 + bx + c$, the sum of its roots $ = \frac{-b}{2a}$ and the product of its roots $ =\frac{c}{a}$. Thus in this case, let the two roots be $ a$ and $ a'$ (since we already know one of the roots must be $ a'$).

Then $ a+a'= kb'$ and $ aa'=(b')^2-k$. The first equation shows that $ a$ is an integer (since $ kb'-a'$ is an integer). The second equation shows that $ a \neq 0$. This is because $ k=(b')^2$ if $ a=0$, which contradicts our assumption that $ k$ is not a perfect square.

We also note that $ a$ cannot be negative. Otherwise, $ a^2 - (kb')a + ((b')^2-k) = a^2 + (kb')|a| + ((b')^2-k) > a^2 + k + ((b')^2-k) = a^2 + (b')^2 > 0$
which contradicts the fact that  $ a^2 - (kb')a + ((b')^2-k) = 0$.

Thus, $ a$ is a positive integer, making $ (a,b')$ one of the possible combinations such that $ \frac{a^2+(b')^2}{1+ab'} = k$ for a fixed integer $ k$.

However, since we assumed $ a' \ge b'$, the second equation tells us that
$ a=\frac{(b')^2-k}{a'} < a'$ (since $ (b')^2-k < (a')^2$ and thus $ \frac{(b')^2-k}{a'} < \frac{(a')^2}{a'} = a'$)

Hence, $ a + b' < a' + b'$, which contradicts the minimality $ a'+b'$.

Therefore, $ k$ must be a perfect square since $ a=0$ is the only way to avoid this contradiction.
[/hide]


Given right triangle $ ABC$, with $ AB \equal{} 4, BC \equal{} 3,$ and $ CA \equal{} 5$. Circle $ \omega$ passes through $ A$ and is tangent to $ BC$ at $ C$. What is the radius of $ \omega$?

My solution too.
The radius of $ \omega$ is $ R \equal{} \frac {25}{8}$.


The sum of a certain number of positive integers is 31. What is the biggest their product can be?

(1) 55296 (2) 78732 (3) 118098 (4) 49152  (5) None of the above''

Yes!!! I answered wrong before, so I deleted my post. But now I think I got the right answer.
It's 78732.

Here is the explanation- 3+3+3+3+3+3+3+3+3+4=31.
And, 3^9x4=78732.

We divide 31 into numbers as close as possible to each other.  Therefore, 31 = $ 3 \cdot 9 \plus{} 4$.

We multiply $ 3^9 \cdot 4$ and get $ \boxed{78732}.$


let $ a$ , $ b$ , $ c$ , $ d$ $ \in ]0,\plus{}\infty[$ , prove that :

$ \left(\frac{a}{a\plus{}b}\right)^2\plus{}\left(\frac{b}{b\plus{}c}\right)^2\plus{}\left(\frac{c}{c\plus{}d}\right)^2\plus{}\left(\frac{d}{d\plus{}a}\right)^2\geq 1$

thank's Marius Mainea

is there a nice prof for

$ \frac{1}{(1\plus{}x)^2}\plus{}\frac{1}{(1\plus{}y)^2}\geq\frac{1}{1\plus{}xy}$

From $ A.M.\geq{G.M.}$, it follows:

$ \frac{1}{(1\plus{}x)^2}\plus{}\frac{1}{(1\plus{}y)^2}\geq{\frac{2}{(1\plus{}x)(1\plus{}y)}}$

Now, to obtain $ \frac{2}{(1\plus{}x)(1\plus{}y)}\geq{\frac{1}{1\plus{}xy}}$;

I tried $ 2\plus{}2xy\geq{1\plus{}x\plus{}y\plus{}xy}$ but it gives $ (1\minus{}x)(1\minus{}y)\geq{0}$ which doesn't holds always whereas the inequality holds.......... :maybe:

Post your solution Marius Mainea!

[quote="y-a-s-s-i-n-e"]
is there a nice prof for
$ \frac {1}{(1 \plus{} x)^2} \plus{} \frac {1}{(1 \plus{} y)^2}\geq\frac {1}{1 \plus{} xy}$[/quote]

\[ { \frac {1}{(1 \plus{} x)^2} \plus{} \frac {1}{(1 \plus{} y)^2}\minus{}\frac {1}{1 \plus{} xy}
\equal{}{\frac { \left( x\,y\minus{}1 \right) ^{2}\plus{}x\,y\, \left( x\minus{}y
 \right) ^{2}}{ \left( 1\plus{}x \right) ^{2} \left( 1\plus{}y \right) ^{2}
 \left( 1\plus{}x\,y \right) }}}\]

\[ {\left(\frac{a}{a\plus{}b}\right)^2\plus{}\left(\frac{b}{b\plus{}c}\right)^2\plus{}\left(\frac{c}{c\plus{}d}\right)^2\plus{}\left(\frac{d}{d\plus{}a}\right)^2  \equal{} 1\plus{}
{\frac {a{b}^{2} \left( a\minus{}c \right) ^{2}\plus{}c \left( {b}^{2}\minus{}ac \right) ^
{2}}{ \left( a\plus{}b \right) ^{2} \left( b\plus{}c \right) ^{2} \left( a\plus{}c
 \right) }}\plus{}{\frac {c{d}^{2} \left( c\minus{}a \right) ^{2}\plus{}a \left( {d}^{2}\minus{}
ac \right) ^{2}}{ \left( c\plus{}d \right) ^{2} \left( d\plus{}a \right) ^{2}
 \left( a\plus{}c \right) }}}\]

Sergey Markelov

[quote="y-a-s-s-i-n-e"]let $ a$ , $ b$ , $ c$ , $ d$ $ \in ]0, + \infty[$ , prove that :

$ \left(\frac {a}{a + b}\right)^2 + \left(\frac {b}{b + c}\right)^2 + \left(\frac {c}{c + d}\right)^2 + \left(\frac {d}{d + a}\right)^2\geq 1$[/quote]
I think we also have this ineq
$ \left(\frac {a}{a + b}\right)^k + \left(\frac {b}{b + c}\right)^k + \left(\frac {c}{c + d}\right)^k + \left(\frac {d}{d + a}\right)^k\geq \frac {}{4^{k - 1}$ for all $ k\geq 2$
The proof is used your problem and becnuli ineq

[quote="y-a-s-s-i-n-e"]thank"s markelov i did like your solution but it's ugly this why i m trying to find a proof with theorem

sorry Allnames but i can"t  see  your inequality[/quote]
Sorry y-a-s-s-i-n-e , i cant edit it,my ideal is istead of $ 2$,we can choose $ k\geq 2$,and this ineq is still true
Can you quote my post and checs where is error
Sorry if ia have grammar mistakes

[quote="y-a-s-s-i-n-e"]thank's Marius Mainea

is there a nice prof for

$ \frac {1}{(1 \plus{} x)^2} \plus{} \frac {1}{(1 \plus{} y)^2}\geq\frac {1}{1 \plus{} xy}$[/quote]

Actually there's more than one nice proof for this.
One is:
From Cauchy-Schwarz:
$ (1\plus{}xy)(1\plus{}\frac{x}{y})\geq(1\plus{}x)^2$ and $ (1\plus{}xy)(1\plus{}\frac{y}{x})\geq(1\plus{}y)^2$
So :
$ \frac {1}{(1 \plus{} x)^2} \plus{} \frac {1}{(1 \plus{} y)^2}\geq \frac{1}{(1\plus{}xy)(1\plus{}\frac{x}{y})} \plus{}\frac{1}{(1\plus{}xy)(1\plus{}\frac{y}{x})} \equal{} \frac {1}{1 \plus{} xy} \times (\frac{y}{x\plus{}y}\plus{}\frac{x}{x\plus{}y}) \equal{} \frac {1}{1 \plus{} xy}$

[quote="y-a-s-s-i-n-e"]$ \left(\frac {a}{a \plus{} b}\right)^k \plus{} \left(\frac {b}{b \plus{} c}\right)^k \plus{} \left(\frac {c}{c \plus{} d}\right)^k \plus{} \left(\frac {d}{d \plus{} a}\right)^k \geq \frac {4}{4^{k \minus{} 1} }$ for all $ k \geq 2$[/quote]
$ \left(\frac {a}{a \plus{} b}\right)^k \plus{} \left(\frac {b}{b \plus{} c}\right)^k \plus{} \left(\frac {c}{c \plus{} d}\right)^k \plus{} \left(\frac {d}{d \plus{} a}\right)^k \geq \frac {1}{4^{k \minus{} 1} }$ for all $ k \geq 2$
Thank y-a-s-s-i-n-e,i think this ineq is true

thank"s brianchung11  nice prof

allnames take $ k\equal{}2$ we get $ S \geq \frac{1}{4}$ and in  the first  inequality we have $ S \geq 2$  :idea:

[quote="y-a-s-s-i-n-e"]let $ a$ , $ b$ , $ c$ , $ d$ $ \in ]0, \plus{} \infty[$ , prove that :

$ \left(\frac {a}{a \plus{} b}\right)^2 \plus{} \left(\frac {b}{b \plus{} c}\right)^2 \plus{} \left(\frac {c}{c \plus{} d}\right)^2 \plus{} \left(\frac {d}{d \plus{} a}\right)^2\geq 1$[/quote]
Find   k  max to the inequality trus
$ \left(\frac {a}{a \plus{} b}\right)^2 \plus{} \left(\frac {b}{b \plus{} c}\right)^2 \plus{} \left(\frac {c}{c \plus{} d}\right)^2 \plus{} \left(\frac {d}{d \plus{} a}\right)^2\plus{}\frac{k    abcd}{(a\plus{}b)(b\plus{}c)(c\plus{}d)(d\plus{}a)} \geq 1\plus{}\frac{k}{16}$

[quote="Allnames"][quote="y-a-s-s-i-n-e"]$ \left(\frac {a}{a \plus{} b}\right)^k \plus{} \left(\frac {b}{b \plus{} c}\right)^k \plus{} \left(\frac {c}{c \plus{} d}\right)^k \plus{} \left(\frac {d}{d \plus{} a}\right)^k \geq \frac {4}{4^{k \minus{} 1} }$ for all $ k \geq 2$[/quote]
$ \left(\frac {a}{a \plus{} b}\right)^k \plus{} \left(\frac {b}{b \plus{} c}\right)^k \plus{} \left(\frac {c}{c \plus{} d}\right)^k \plus{} \left(\frac {d}{d \plus{} a}\right)^k \geq \frac {4}{4^{k \minus{} 1} }$ for all $ k \geq 2$
Thank y-a-s-s-i-n-e,i think this ineq is true[/quote]
I can't edit my last post so i must post the new
My problem is very easy,the most difficult is proving it is true with $ k\equal{}2$
Then Use Mean ineq we have this ineq

[quote="y-a-s-s-i-n-e"]thank's Marius Mainea

is there a nice prof for

$ \frac {1}{(1 \plus{} x)^2} \plus{} \frac {1}{(1 \plus{} y)^2}\geq\frac {1}{1 \plus{} xy}$[/quote]

I  know a very nice proof for this inequality, given by Darij Grinberg:
According to the Cauchy-Schwarz inequality we deduce that $ (x \plus{} y)(1 \plus{} xy) \geq (\sqrt {x} \plus{} \sqrt {x}y)^{2} \equal{} x(1 \plus{} y)^2 \Rightarrow \frac {1}{(y \plus{} 1)^2} \geq \frac {x}{x \plus{} y} \cdot \frac {1}{1 \plus{} xy}$. Also $ \frac{1}{(x \plus{} 1)^2} \geq \frac {y}{x \plus{} y} \cdot \frac {1}{1 \plus{} xy}$. Adding-up the last two inequalities, the conclusion follows.


geometry
geometric transformation
rotation
conics
ellipse
linear algebra

give a rotation that takes the following equation 2x^2 - 3xy + 5y^2 +2x -3y + 2=0
 to       5x^2-3xy +2y^2 - 3x +2y +2=0. i think it uses matrices in some way.


c 2  =a 2 +b 2
b 2 =a 2 -c 2
a 2 =b 2 +c 2

my sister made this up...she wanted me to post this...she's in 5th grade

[quote="math92"]c 2  =a 2 +b 2
b 2 =a 2 -c 2
a 2 =b 2 +c 2
[/quote]

Maybe we're supposed to solve it...
[hide]
\[c^2 =a^2 +b^2 \]
\[b^2 =a^2 -c^2 \]
\[a^2 =b^2 +c^2 \]
Substituting, we see $b^2 =a^2 -(a^2+b^2)$, which is useless. Substituting something else, we see $c^2 =a^2 +a^2-c^2 \Rightarrow a=c$. Substituting again, we see $0=b^2$, or $b=0$. That's all you can do.
[/hide]

oh sorry, i forgot to tell you what to do. :blush: Find a 2 +b 2
(don't find the numerical value because there's an infinite amount of answers)

(continuatioin)what is $a^2-c^2$ in terms of $b$?

[quote="Stan17"]any multiple of b...[/quote]
what do you mean


The equation is also$(x-1)(y+2)=54$ and then we watch the divisors of $54$
$x-1=1$ and $y+2=54$ or
$x-1=2$ and $y+2=27$ and so on ! :roll:

[quote="alex__ib"]Let there be x and y so that:
$xy+2x-y=56$

x and y are natural numbers.  :lol:[/quote]

[hide]
Factor it to equal using Simon's favorite factoring trick:

$(x-1)(y+2)=54$
and then it is obviously solvable.  :) [/hide]

[quote="lotrgreengrapes7926"][quote="Virgil Nicula"][hide="Hint 3"]$x=1+\frac{54}{y+2}\ .$[/hide][/quote]
[hide="Continuation"] $\frac{54}{y+2}$ must be a natural number, so $y+2$ must be a factor of $54$. $54$ has factors: $1,2,3,6,9,18,27,54$, so $y=1,4,7,16,25,52$ and $x=19,10,7,4,3,2$. $(x,y)=(2,52), (3,25), (4,16), (7,7), (10, 4), (19, 1)$ [/hide][/quote]
[hide="hint"]Simon's favorite factoring trick[/hide]
[hide]With simon's we get $(x-1)(y+2)=54$
For 1,54 we get 2, 52
For 2,27 we get 3, 25
For 3,18 we get 4, 16 and 19, 1
For 6,9 we get 7,7 and 10,4[/hide]

just wanna say something (and i also wanna see if my signature works and i'm too lazy to go preview it, which is around three clicks away) - if you ever see something expressible as the form axy + bx + cy = d, think simon's favorite factoring trick.