We have a graph that its vertexes are the arrangements of $1,2,...,n$ (so it has $n!$ vertexes). There is an edge between two vertexes if they were opposite in $k$ elements. For $k=1,2$ we now that this graph has a Hamilton cycle. Find the greatest $k$ according to $n$ that we can say for this $k$ that the graph has a Hamilton cycle.

What does it mean "opposite"? Different?
How two permutations can differ in just 1 element? So $k=1$ does not make sense to me.


$ \frac{86}{100}\equal{}\frac{x}{124}\rightarrow 10664\equal{}100x \rightarrow x\equal{}106.64$

[quote="JRav"]$ \frac {86}{100} \equal{} \frac {x}{124}\rightarrow 10664 \equal{} 100x \rightarrow x \equal{} 106.64$[/quote]
No... I got different answer..

$ 126\times \frac {86}{100} \equal{} \boxed{108.36}$

[quote="JRav"]You got the right answer,..., for 126.  That is why you got a different answer.  He's asking for 86% of 124, not 126. :lol:[/quote]
Oops.. You are right.. I'm sorry.. :blush:

Yep. Explanation to what they are doing:

86% = .86, so to find 86 % of any number n, you would just evaluate .86n


vector
real analysis
real analysis unsolved

Let S be a closed set. Give an example to show that conv(S) is not necessarily closed.
Could you please write the set as the form like S={........} not to be misunderstanding by me.

Thanks for your considerations.

In $\mathbb{R}^{2}$, consider the set $S=\{(0,1),(n,0); \ n \in \mathbb{Z}\}$.

give an example when $S$ is compact (in infinite dimensional vector space ..)


Find the number of ordered pairs of real numbers $(a,b)$ such that $(a+bi)^{2002}= a-bi$.

Well...

[hide] I will use $z'$ to denote the conjugate. Let $z=a+bi$ so that $z^{2002}=z'$. The magnitude of a complex number is the same as the magnitude of its conjugate: $|z|^{2002}=|z'| \Rightarrow |z|^{2002}=|z|$.

$\Rightarrow |z|^{2002}-|z|=0 \Rightarrow |z|(|z|^{2001}-1)=0$. $|z|=0$ or $|z|^{2001}=1$. The first equation has $1$ solution. $|z|=1$ so that $z\cdot z' = 1$ $\Rightarrow z'=\frac{1}{z}$.

Substituting into the original, $|z|^{2002}= \frac{1}{z}$ or $|z|^{2003}=1$. Obviously, there are $2003$ solutions in this case.

$1+2003=2004$ total [/hide]

Sorry there is a mistake in the third paragraph and it won't let me edit.

It should be $z^{2002}=\frac{1}{z}$ or $z^{2003}=1$. And there are $2003$ solutions for $z$.

Then add the $1$ to get a total of $2004$.

This level of problem generally belongs in Intermediate.


[quote="xpmath"]Um... this is pretty easy but I need help.

For the following, either find positive integers satisfying the equation, or prove there are no positive integers that can satisfy them:

a. $ a^{2}+b^{2}+c^{2}+d^{2}=2007$
b. $ a^{2}+b^{2}+c^{2}=2007$.

Thanks[/quote]

Subtracting the equations, we get $ d^{2}=0$ making d 0. however, all numbers must be positive. Therefore there are no numbers that work.

OR

We have from equation b that $ a^{2}+b^{2}+c^{2}=2007.$ Substituting, $ 2007+d^{2}=2007$ or $ d^{2}=0$ NOw we have d is 0, however this does not work because all of the numbers must be positive. Therefore, There is not a working set {a,b,c,d}

Those aren't equations. They're two different problems.

b. $ 2007\equiv7 \bmod{8}$, but the only quadratic residues $ \bmod{8}$ are 0, 1, and 4.  Because there is no way to add three of these together to get 7 (the closest are 4+1+1=6 and 4+4+0=8), 2007 cannot be the sum of three perfect squares.

a. The ordered quadruple (a,b,c,d)=(3,3,15,42) is one solution, as obviously, are the permutations thereof.  You only needed one solution, correct?

[quote="Phelpedo"]All positive integers are expressible as a sum of three squares except those of the form $ 4^{k}(8n+1)$ and all positive integers are expressible as a sum of four squares.[/quote]
The sad thing is, I'd have to prove that for it to really count. Thanks for the help though :)
Yes, roadnottaken, I only needed one :)

[quote="Phelpedo"]All positive integers are expressible as a sum of three squares except those of the form $ 4^{k}(8n+1)$ and all positive integers are expressible as a sum of four squares.[/quote]
That should be $ 4^{k}(8n+7)$.  I just proved this statement for k=0.  A simple counterexample to your statement is $ 9=4^{0}(8\times1+1)=1^{2}+2^{2}+2^{2}$.  See [url=http://mathworld.wolfram.com/LagrangesFour-SquareTheorem.html]Lagrange's Four-Square Theorem[/url].


prove that a00000...000b can never be a square
for example if a was 4 and b was 8, we'd get the number 40000000...0008

ive only gotten as far as to knowing it must be 1 mod 3 or 0 mod 3 and 1 mod 4 or 0 mod 4 which gives me some casework, but im looking for an easier solution

How many 0's?

If there were an even number of 0's I think it's possible for it to be square. But I know that an odd number, even if a000000 were square, +b would spoil it.

any number of 0s
ive gotten to proving that a00000000000000000...00a cant be a square but no farther

A perfect square of an even number is of the form $(2n)^2=4n^2$ which means that $b$ either is $0,4$ or $8$
I assume you exclude 0, since otherwise, $a000000...0000$ can be a perfect square if $a=1,4$ or $9$
It is impossible for a perfect square to end in an eight, so $b$ can't be $8$ as well.
If $b=4$, then the root should be of the form $(c*10+2)$ or $(c*10+8)$ (with $c$ integer) and $(c*10+2)^2=100c^2+40c+4$
But $100c^2+40c$ can't possibly be of the form $a000000...0000$ (same for $160c+64$), so $b$ cannot equal $4$ too.

A perfect square of an odd number is of the form $(2n+1)^2=4n(n+1)+1$ which means that the number $a000000...000b$ can only end in either 1 or 9.
If it ends in a $9$, the root should be of the form $(d*10+3)$ (with $d$ integer) and $(d*10+3)^2=100d^2+60d+9$
Again, $100d^2+60d$ cannot be of the form $a000000...0000$, so $b$ aint $9$ as well.
Last option: $b=1$; which means the root is of the form $(e*10+1)$ or $(e*10+9)$. $100e^2+20e$ and $100e^2+180e+81$ can't possibly be of the form $a000000...000$.

Sorry for the rather weird explanation  :blush:  Hope it helps though  :)


Vezi [url]http://www.pro-didactica.ro/articole/examene2007/m1_1v41-45f.pdf[/url], cu excelente solutii si comentarii!


Hi on page 32 of AMY there was a paragraph saying that the following idea ties the 3 solutions together I don't see how the last step (although I know why its true) comes from the previous statements in the paragraph. :)

RM=RN since R is on the symmetry axis of kite OMEN. So arc RM has the same measure as arc RN. Then by angle chasing RM bisects angle OMN and RN bisects ONM. Thus R is incenter of OMN.


function
integration
real analysis
real analysis unsolved

Consider the functions $f(x),g(x),h(x)$ which satisfies the system of differential equation as follows.

Supposed that $f(x), h(x)$ always take positive values.

\[f'(x)g(x)-f(x)g'(x)=h(x)\]
\[g'(x)h(x)-g(x)h'(x)=-f(x)\]
\[h'(x)f(x)-h(x)f'(x)=g(x)\]

Let $h(x)=\frac{1}{3x^2+1},\ g(0)=0$, find $f(x),\ g(x)$.

Can anyone solve this problem? :)

kunny

Thanks to Professor Qinian Jin from Virginia Tech for helping with this problem. Without his help I wouldn't have solved this problem. I also can't wait to read his paper which he will publish in few weeks.
[hide]
Using some basic algebra and the fact that $ g(0) \equal{} 0$  we
see that from the first equation $ f'(0)g(0) \plus{} g'(0)f(0) \equal{} h(0) \equal{} 1 \leftrightarrow g'(0)f(0) \equal{} 1$, and from the second equation we see that $ g'(0)h(0) \minus{} g(0)h'(0) \equal{} \minus{} f(0) \leftrightarrow g'(0) \equal{} \minus{} f(0)$ ans so we have a system that we can solve to get $ f(0) \equal{} 1$ and $ g'(0) \equal{} \minus{} 1$. Now because $ f(0) \equal{} 1$ we can solve for $ f'(0)$ from the third given equation as follows: $ h'(0)f(0) \minus{} h(0)f'(0) \equal{} g(0) \leftrightarrow \minus{} f'(0) \equal{} 0 \leftrightarrow f'(0) \equal{} 0$. Also,Note that the definition of $ \sinh(x) \equal{} \dfrac{e^{x} \minus{} e^{ \minus{} x}}{2}$ , and that the definition of
$ \cosh(x) \equal{} \dfrac{e^{x} \plus{} e^{ \minus{} x}}{2}$.

Now that we have essential information about initial conditions we can begin.

we know from the first given equation that $ f'g \minus{} g'f \equal{} h$ so after multiplying through by $ h$, we get equation (1)
\[ hf'g \minus{} hg'f \equal{} h^2\]
. We also know from the third given equation that $ h'f \minus{} hf' \equal{} g$, so after multiplying through by $ g$ we get equation(2)
\[ gh'f \minus{} ghf' \equal{} g^2\]
.Now adding the two equations we get equation (3)
\[ \minus{} g'hf \plus{} gh'f \equal{} h^2 \plus{} g^2 \leftrightarrow (gh' \minus{} g'h)f \equal{} h^2 \plus{} g^2\]
.Now we use the second given equation $ g'h \minus{} gh' \equal{} \minus{} f \leftrightarrow gh' \minus{} g'h \equal{} f$ and substitute for $ f$ in
equation (3) to yield
\[ (gh' \minus{} g'h)^2 \equal{} h^2 \plus{} g^2\]
Dividing through by $ h^4$ (because we notice a reverse quotient rule in play) we obtain equation (4)
\[ (\dfrac{gh' \minus{} g'h}{h^2})^2 \equal{} \dfrac{1}{h^2}(1 \plus{} (\dfrac{g}{h})^2)\]
But we reverse the quotient rule and see that equation (4) is equivalent to
\[ ((\dfrac{g}{h})')^2 \equal{} \dfrac{1}{h^2}(1 \plus{} (\dfrac{g}{h})^2)\]
Now we $ \dfrac{g}{h} \equal{} k$, then we get equation (5)
\[ (k')^2 \equal{} \dfrac{1}{h^2}(1 \plus{} k^2)\]
Next we look at
\[ k' \equal{} \dfrac{g'h \minus{} gh'}{h^2}\]
we note that
\[ k'(0) \equal{} \dfrac{g'(0)h(0) \minus{} g(0)h'(0)}{(h(0))^2} \equal{} \dfrac{( \minus{} 1)(1)}{1} \equal{} \minus{} 1 < 0\]
and thus,
\[ k' \equal{} \dfrac{ \minus{} 1}{h}\sqrt(1 \plus{} k^2)\]
It follows that
\[ \displaystyle\int \dfrac{1}{\sqrt(1 \plus{} k^2)}\,dx \equal{} \minus{} \displaystyle\int\dfrac{1}{h}\,dx\]
which is equivalent to
\[ \sinh^{ \minus{} 1}(k) \equal{} 0 \minus{} \displaystyle\int{1 \plus{} 3x^2}\,dx \equal{} \minus{} (x \plus{} x^3) \plus{} C\]
$ \leftrightarrow$
\[ k \equal{} \sinh( \minus{} (x \plus{} x^3) \plus{} C)\]
and since $ k(0) \equal{} 0 \equal{} \sinh(C) \equal{} \dfrac{e^{C} \minus{} e^{ \minus{} C}}{2} \leftrightarrow C \equal{} 0$. So,
\[ k \equal{} \dfrac{g}{h} \equal{} \sinh( \minus{} x \minus{} x^3)\]
From the previous equation we could solve for $ g$, thus
\[ g(x) \equal{} \dfrac{\sinh( \minus{} x \minus{} x^3)}{1 \plus{} 3x^2} \equal{} \dfrac{e^{ \minus{} x \minus{} x^3} \minus{} e^{x \plus{} x^3}}{2(1 \plus{} 3x^2)}\]
Now that we have $ g(x)$ we can solve for $ f(x)$, and so,
\[ f(x) \equal{} \sqrt {g^2 \plus{} h^2}\]

\[ \equal{} \sqrt {h^2(1 \plus{} (\sinh( \minus{} x \minus{} x^3))^2)}\]

\[ \equal{} \sqrt {(h^2)(\cosh( \minus{} x \minus{} x^3))^2}\]

\[ \equal{} (h)(\cosh( \minus{} x \minus{} x^3))\]

\[ \equal{} \dfrac{e^{ \minus{} x \minus{} x^3} \plus{} e^{x \plus{} x^3}}{2(1 \plus{} 3x^2)}\]
WE ARE DONE, that took 30 minuts to write in latex. It is also 1:32am so if I made mistakes please know that
I was very very exhausted when wrote this post.[/hide]

hello, i got this here
$ \left\{ f \left( x \right) \equal{}{\frac {\cosh \left( {x}^{3}\plus{}x \right) }{
3\,{x}^{2}\plus{}1}},g \left( x \right) \equal{}\minus{}{\frac {\sinh \left( {x}^{3}\plus{}x
 \right) }{3\,{x}^{2}\plus{}1}} \right\}$
or
$ \left\{ f \left( x \right) \equal{}\minus{}{\frac {\cosh \left( {x}^{3}\plus{}x \right) }
{3\,{x}^{2}\plus{}1}},g \left( x \right) \equal{}{\frac {\sinh \left( {x}^{3}\plus{}x
 \right) }{3\,{x}^{2}\plus{}1}} \right\}$
Sonnhard.

Remember that $ f(x)$ takes only positive values i.e. the range is positive. i had to make a choice when I took the square root of $ k$.  $ k'(0) \equal{} \minus{} 1 < 0$ and therefore the function is decreasing. Thus my choice of
$ k\equal{}\dfrac{ \minus{} 1}{h}\sqrt {1 \plus{} k^2}$ is correct because if  $ k\equal{}\dfrac{1}{h}\sqrt {1 \plus{} k^2}$, then $ k$ wouldn't be decreasing at $ k(0)$.

hello, ok, i have forgotten it,sorry.
Sonnhard.

No worries. It is a lot of algebra, so making a mistake is very easy.


function
limit
real analysis
real analysis unsolved

Let $ f: R\minus{}>R^*$ a function and $ F$ be a primitive of $ f$ with $ F(0)\equal{}0$ . Prove that exist $ c \in (0,1)$ s. t $ |1\minus{}\frac{F(c)}{f(c)}|<1$

Since $ f(x)\neq 0$, $ \forall x \in \mathbb{R}$, and $ f$ has the Darboux property, it means that $ f$ has the same sign everywhere. Let's take $ f(x) > 0$, $ \forall x \in \mathbb{R}$.

And now, I will show that $ \lim_{x\to 0, x > 0}f(x) \neq 0$.Suppose the contrary we get from L'Hospital rule that $ 0 \equal{} \lim_{x\to 0, x > 0}f(x) \equal{} \lim_{x\to 0, x > 0}\frac {F'(x)}{x'} \equal{} \lim_{x\to 0, x > 0} \frac {F(x)}{x}$.
But $ F$ is differentiable at $ 0$ , so $ \lim_{x\to 0, x > 0} \frac {F(x) \minus{} F(0)}{x \minus{} 0} \equal{} F'(0) \equal{} f(0) \equal{} 0$, contradiction. There there must be a value $ \epsilon_0 \in (0,1)$ and a sequence $ x_n \in (0,1)$ such that $ x_n \to 0$ but $ f(x_n) > \epsilon_0$, $ \forall n \in \mathbb{N}$.
But because $ F$ is continuous it follows that $ \lim_{n\to \infty} \frac {F(x_n)}{f(x_n)} \equal{} 0$ $ (1)$.Since $ f(x) > 0$ and $ F$ is increasing and $ x_n > 0$ we get that $ \frac {F(x_n)}{f(x_n)} > 0$ $ (2)$.And from $ (1)$ and $ (2)$ the conclusion follows.

Analogously, we can prove the case $ f(x) < 0$, $ \forall x\in\mathbb{R}$.

[hide]
Applying mean value theorem to $ Fx$ on $ [0, 1]$ yields:

$ F\,1\equal{}\frac{F\,1\minus{}F\,0}{1\minus{}0}\equal{}fc$
for some $ c\in (0,1)$

[b]Svejk[/b] already explained why $ f$ has constant sign, so $ F$ is strictly monotonic.

[b]1.[/b]
if $ F$ is strictly increasing ( $ f\,c>0$ ) , then
$ 0<c<1\Rightarrow F\,0<F\,c<F\,1\equal{}fc$
$ 0<F\,c<f\,c$
$ 0<\frac{F\,c}{f\,c}<1$

[b]2.[/b]
if $ F$ is strictly decreasing ( $ f\,c<0$ ) , then
$ 0<c<1\Rightarrow F\,0>F\,c>F\,1\equal{}fc$
$ 0>F\,c>f\,c$
$ 0<\frac{F\,c}{f\,c}<1$

So, we got a little bit stronger result than needed.

Both cases could easily be handled at once like this:
monotonicity of $ F$ yields that $ F\,c$ and $ F\,1\equal{}f\,c$
have same sign, and $ F\,c$ is always strictly between $ 0\equal{}F\,0$ and $ F\,1\equal{}f\,c$
hence having smaller modulus than $ f\,c$, which gives us $ 0<\frac{F\,c}{f\,c}<1$

 [/hide]


Every card in a deck has a picture of one shape - circle, square, or triangle, which is painted in one of the three colors - red, blue, or green. Furthermore, each color is applied in one of three shades - light, medium, or dark. The deck has 27 cards, with every shape-color-shade combination represented. A set of three cards from the deck is called complementary if all of the following statements are true:

i. Either each of the three cards has a different shape or all three of the card have the same shape.
ii. Either each of the three cards has a different color or all three of the cards have the same color.
iii. Either each of the three cards has a different shade or all three of the cards have the same shade.

How many different complementary three-card sets are there?

Brainteaser- There are 4 ways to satisfy (i), 4 to satisfy (ii), and 4 to satisfy (iii), so why isn't the answer 64?

Well I'll tell you how I solved it:[hide="sol"]Every combination of two cards defines a third card to form a complementary set; there are ${27\choose 2}$ two card sets which define a total of $\left(\frac{{27\choose 2}}{{3\choose 2}}\right)=\boxed{117}$ three card sets.[/hide]
And I'm not really sure what your brainteaser is...

OK. The brainteaser is sort of a common mistake (I think anyway). Conditions 1,2,3 are independent. There are 4 ways to satisfy each (all different or 3 ways for all same). Thus the natural answer would be 64...

If you never actually think about the problem, you might make that mistake, as you might make any other mistake...so i wouldn't say it's a brainteaser...

Have you guys ever played set? Its exactly like This problem. You put 12 cards in the middle and race to try to find a set like the problem explains. (Except you have to consider 4 variables, i think)

[quote="me@home"]But that logic makes no sense... do you know anyone who actually made that mistake?[/quote]
I think his brainteaser is asking why that logic makes no sense.

Well, i think this example demonstrates it.  When you say "the three shapes are the same", that doesn't determine the three shapes...

Lol I thought it might have been a common mistake.

@K81o7, that's why we include 3 possibilities under that category. More specifically, we categorize in this way
Shape:
-all different
-all circle
-all square
-all triangle
Color:
-all different
-all red
-all blue
-all green
Shade:
-all different
-all medium
-all light
-all dark

We know that, for each of the 3 traits, a complementary set falls into one of these 4 subcategories. Additionally, it might appear that there is a bijection between the combinations of subcategories and complementary sets, which makes me think that this is a rather common trap.

Oh yeah I said the wrong thing for some reason  :blush:

What I meant is that "the three shapes are different" doesn't tell us which is which.

Don't worry, I know what I'm talking about, I was just stupid there and didn't say what I was thinking...quite the opposite in fact :D

So if yo generalized the problem and made it really hard so that my way (above) doesn't work, you could estimate a decent lower bound with your "brainteaser"... :P


What is the greatest surface area of a rectangular solid that can be built from 16 identical unit cubes?

You should build a 1*1*16 rectangular solid.

$ 1*1\plus{}1*1\plus{}16*1*4\equal{}2\plus{}64\equal{}\boxed{66}$.


geometry
circumcircle
trigonometry
geometry solved

Let $ ABC$ be a triangle with $ AC\neq BC$ and $ AB < AC$.  The circle $ K$ is the circumcircle of $ ABC$.  Suppose that the tangent at $ A$ of the circle $ K$ intersects $ BC$ at $ D$.  Let $ T$ be the circle tangent to the circle $ K$ and touching the line segments $ AD$ and $ BD$ at $ M$ and $ N$, respectively.

Prove that if $ J$ is the center of the escribed circle of the triangle $ ABC$ opposite to the point $ C$ (or in other words, touching the side $ AB$), then $ J$, $ M$, and $ N$ are collinear.

[hide]
Let $ p : \equal{} AD$, $ q : \equal{} CD$, $ a : \equal{} BC$, $ b : \equal{} CA$, $ c : \equal{} AB$, and $ x : \equal{} MD \equal{} ND$. Also, $ s : \equal{} (a\plus{}b\plus{}c)/2$ is the semiperimeter of ABC.

Using Casey's Theorem, or the Generalization of Ptolemy's Theorem, with the tuple $ (A,C,B,T)$, one gets
\[ a(p\minus{}x)\plus{}b(q\minus{}a\minus{}x)\equal{}c(q\minus{}x)\,,\]
or $ x \equal{}\frac{ap\plus{}bq\minus{}cq\minus{}ab}{2(s\minus{}c)}$.

Let $ M'$ be a point on $ AD$ such that $ \angle{AJM'}$ is a right angle.  Since $ JA \equal{}\frac{s\minus{}b}{\sin\left(\frac{A}{2}\right)}$ and $ \angle{DAJ}\equal{}\frac{B\minus{}C}{2}$, then
\[ y :\equal{}AM'\equal{}\frac{s\minus{}b}{\sin\left(\frac{A}{2}\right)\cos\left(\frac{B\minus{}C}{2}\right)}\,.\]
According to the Law of Sine with the triangle $ ACD$, one gets
\[ p\equal{}b\left(\frac{\sin(C)}{\sin(B\minus{}C)}\right)\,,\]
and
\[ q\equal{}b\left(\frac{\sin(B)}{\sin(B\minus{}C)}\right)\,.\]
Note that $ \angle{JM'A}\equal{}\frac{\pi}{2}\minus{}\frac{B\minus{}C}{2}\equal{}\angle{DMN}$.  If one verifies $ M' \equal{} M$, one then proves the collinearity of $ J$, $ M$, and $ N$.  Hence, it suffices to show that $ DM\plus{}M'A \equal{} DA$, or $ x\plus{}y \equal{} p$.

One begins with
\[ \sin(C)\equal{}\cos\left(\frac{\pi}{2}\minus{}C\right)\equal{}\cos\left(\frac{A}{2}\plus{}\frac{B\minus{}C}{2}\right)\,.\]
That is,
\[ \sin(C)\equal{}\cos\left(\frac{A}{2}\right)\cos\left(\frac{B\minus{}C}{2}\right)\minus{}\sin\left(\frac{A}{2}\right)\sin\left(\frac{B\minus{}C}{2}\right)\,.\]
Thus,
\[ \frac{\cos\left(\frac{A}{2}\right)}{\sin(C)}\equal{}\frac{1}{\cos\left(\frac{B\minus{}C}{2}\right)}\plus{}\frac{\sin\left(\frac{B\minus{}C}{2}\right)\sin\left(\frac{A}{2}\right)}{\sin(C)\cos\left(\frac{B\minus{}C}{2}\right)}\,.\]
Consequently,
\[ \frac{\sin(A)}{\sin(C)}\equal{}\frac{2\sin\left(\frac{A}{2}\right)\cos\left(\frac{A}{2}\right)}{\sin(C)}\equal{}\frac{2\sin\left(\frac{A}{2}\right)}{\cos\left(\frac{B\minus{}C}{2}\right)}\plus{}\frac{2\sin\left(\frac{B\minus{}C}{2}\right)\sin^{2}\left(\frac{A}{2}\right)}{\sin(C)\cos\left(\frac{B\minus{}C}{2}\right)}\,.\]
Hence,
\[ \frac{a}{c}\equal{}\frac{2\sin^{2}\left(\frac{A}{2}\right)}{\sin\left(\frac{A}{2}\right)\cos\left(\frac{B\minus{}C}{2}\right)}\plus{}\frac{\left(2\sin\left(\frac{B\minus{}C}{2}\right)\sin\left(\frac{A}{2}\right)\right)^{2}}{\sin(C)\sin(B\minus{}C)}\,.\]
Using the identity $ \sin^{2}\left(\frac{A}{2}\right) \equal{}\frac{(s\minus{}b)(s\minus{}c)}{bc}$, one obtains
\[ \frac{a}{c}\equal{}\left(\frac{(s\minus{}b)(s\minus{}c)}{bc}\right)\left(\frac{2}{\sin\left(\frac{A}{2}\right)\cos\left(\frac{B\minus{}C}{2}\right)}\right)\plus{}\frac{\left(\sin(B)\minus{}\sin(C)\right)^{2}}{\sin(C)\sin(B\minus{}C)}\,.\]
This means
\[ \frac{a}{c}\equal{}\left(\frac{2(s\minus{}c)}{bc}\right)\left(\frac{s\minus{}b}{\sin\left(\frac{A}{2}\right)\cos\left(\frac{B\minus{}C}{2}\right)}\right)\plus{}\left(\frac{\sin(B)}{\sin(C)}\minus{}1\right)\left(\frac{\sin(B)}{\sin(B\minus{}C)}\minus{}\frac{\sin(C)}{\sin(B\minus{}C)}\right)\,.\]
As a result,
\[ \frac{a}{c}\equal{}\left(\frac{2(s\minus{}c)}{bc}\right)y\plus{}\left(\frac{b}{c}\minus{}1\right)\left(\frac{q\minus{}p}{b}\right)\,.\]
Hence,
\[ y\equal{}\frac{ab}{2(s\minus{}c)}\minus{}\frac{(b\minus{}c)(q\minus{}p)}{2(s\minus{}c)}\equal{}p\minus{}x\,.\]
Therefore, $ x\plus{}y \equal{} p$, and the problem is proved.

[/hide]

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

  darij


IMO Shortlist
sum of cubes
modular arithmetic
number theory
Hi

Can anyone check whether what I got is right??

Thanks,

[hide]Since a cube of an integer is congruent to either
0,1, or -1 (mod9), and $2002^2002$ is congruent to 4 (mod9)., we need at least 4 terms.[/hide]

Note that it's an open problem if every integer can be written as sum of four cubes.

This was on a UK training camp exam recently. I'll post a proper solution (although I'm aware people above have sketched one out).

Claim: t=4 is the minimum.

Proof:

Consider the equation modulo 9. Obviously $3|x_{i}\Rightarrow x_{i}^{3}\equiv 0 \mod 9$. If 3 and $x_{i}$ are coprime, $\phi(9)=6$, so $({x_{i}}^{3})^{2}\equiv 1\mod{9}$ by Euler's Theorem. Therefore ${x_{i}}^{3}\equiv$ $-1$ or $1 \mod 9$. However, $2002^{2002}\equiv 4^{2002}\equiv 4^{4}\equiv 4 \mod{9}$, so if t<4, $LHS\not=RHS$. Therefore, $t\geq 4$.

However, t=4 is achievable using the values $(10*2002^{667})^{3}+(10*2002^{667})^{3}+(2002^{667})^{3}+(2002^{667})^{3}= 2002^{2002}$, so this must be our minimum achievable value. :)

[quote=orl]What is the smallest positive integer $t$ such that there exist integers $x_1,x_2,\ldots,x_t$ with  \[x^3_1+x^3_2+\,\ldots\,+x^3_t=2002^{2002}\,?\][/quote]

[u]Solution.[/u] We claim that $\text{Min} \{t\} = 4$.

[i]Proof.[/i]. Firstly, we show that $ t = 4$ works.
Note that: $2002^{2002} = (10 \cdot \alpha)^3 + (10 \cdot \alpha)^3 + \alpha ^3 + \alpha^3$ where $\alpha = 2002^{667}$.

Now we show that $t=4$ is optimal.

Suppose for the sake of contradiction that $t \le 3$ works.
We consider the expressions $\pmod {9}$.The right side is: $ {2002^3}^{667} \cdot 2002 \equiv 4 \pmod{9}$.

But , $\forall a \in \mathbb{Z}$, $a^3 \equiv 0 , 1, -1 \pmod{9}$. Hence the sum of any three or two of these won't be equal to $ 4 \pmod{ 9}$.

This problem is in 104 Number Theory problems by Titu Andreescu.

[quote=fjm30]I tried to solve this question and I am getting a result which is of course wrong. Can anyone please tell where I am doing a mistake.
Here is my solution...
If we work modulo 7 then 2002^2002 is congruent to 0 modulo 7 and any cube is (0,-1,1) modulo 7 so sum of two or three cubes can be zero modulo seven, so any value of t should work.[/quote]

Bump...

Wow this problem is quite simple...
First, with this problem, like we would with any other, try to guess at some nice numbers that may satisfy this condition... well, $2002^{2002}$ is indeed a really big number, so it would be quite nice if we could somehow reduce it to something feasible, at least something to the order of a thousand... wait this is a no-brainer, let the $gcd$ of our numbers be $2002^{2001}$, which of course is a perfect cube. Thus let's write $x_i=b_i \cdot 2002^{667}$ to get:

$2002^{2001}(b_1^3+...+b_t^3)=2002^{2002}=>b_1^3+...+b_t^3=2002$.
Looking at it for a moment, we immediately see that $2002=2 \cdot 1001 = 2 \cdot (10^3+1)=10^3+10^3+1^3+1^3$ must satisfy this equation- aha so we have found that $t=4$ indeed works, and thus we've got to prove that no other $t<4$ (aka $t=2$ and $t=3$) ends up working... well, this seems like an easy prey for some simple modular arithmetic manipulation...

Well, of course the usual modulos $3,4,5$ will be quite useless here, so let's start with $9$, as we know $x^3 \equiv 0,+-1 \pmod{9}$... now let's try to fiind $2002^{2002} \pmod{9}$:
$2002^{2002} \equiv 4^{2002} \equiv 4^{2001} \cdot 4 \equiv 64^{667} \cdot 4 \equiv 4 \pmod{9}$- thus $x_1^3+...+x_t^3 \equiv 4 \pmod{9}$, and as $x_i^3 \equiv 0,+-1 \pmod{9} => t \geq 4$, we're done.

Finally, our answer is $t=4$, with $x_1,x_2,x_3,x_4=2002^{667}, 2002^{667} , 2002^{667}  \cdot 10, 2002^{667}  \cdot 10$

[hide=Solution]
Considering the equation modulo \(9\) we get that
\[x_1^3 + x_2^3 + \cdots + x_t^3 = 2002^{2002} \equiv 4 \pmod{9}\]
and since the only cubic residues modulo \(9\) are \(0,1,-1\), we easily infer \(t\geq 4\).
Now it suffices to give an explicit solution for \(t=4\):
\[(2002^{667})^3 + (2002^{667})^3 + (10\cdot 2002^{667})^3 + (10\cdot 2002^{667})^3 = 2002^{2002}\]
[/hide]

??

The answer is $t = 4$; taking mod $9$ and using the fact that all cubes are $-1, 0, 1 \pmod 9$ tells us that we require at least $4$ cubes to attain $2002^{2002} \equiv 4 \pmod 9.$ A construction is $(x_1, x_2, x_3, x_4) = (10 \cdot 2002^{667}, 10\cdot 2002^{667}, 2002^{667}, 2002^{667})$.

why is this an isl problem, it's just number sense plus low aime level reduce modulos

We see clearly that 2002=10^3+10^3+1^3+1^3, so we need to multiply by 2002^2001, which evidently is a perfect cube, so we take the numbers 2*(10*2002^667)^3+2*(1*2002^667)^3=2002^2002, as desired. To prove this is the minimum, note that mod 9, 2002^2002=4^2002=4^4=4 mod 9, and each cube can only contribute 1,0, or -1 mod 9.

We claim that the smallest possible value of $t$ is $4$.

Taking the equation modulo 9, we see that $$x_1^3+x_2^3+\dots+x_t^3 \equiv 4 \pmod{2002}.$$ Since the possible residues of cubes modulo 9 are -1, 0, 1, we see that $t \ge 4$, and $t=4$ is achievable when $(x_1, x_2, x_3, x_4)=(2002^{667}, 2002^{667}, 10 \cdot 2002^{667}, 10 \cdot 2002^{667})$. $\blacksquare$

The answer is $t = \boxed{4}$, which is achievable with $x_1=x_2=10 \cdot 2002^{667}$ and $x_3=x_4=2002^{667}$.

To show the bound, take mod $9$:

\[\sum x_i^3 \equiv 4 \pmod{9}.\]

It is known that each cube mod $9$ are $-1,0,1$ which shows that $t \ge 4$. Thus, our lower bound is proved, so the answer is $t=4$.

We claim that the answer is $\boxed{4},$ this is possible with $1000x+1000x+x+x,$ where $x=2002^{2001}.$

Note that the cubic residues in mod  9 are 0,-1,1, so 2002^2002 is 4^2002 which is 4 in mod 9 (note that 4^3 is 1 in mod 9) contraidction.

Cubes should spark the idea of taking $\mod{9}$ where the only cubic residues belong to $\{-1, 0, 1\}$. Thus, since $2002^{2002} \equiv 4^{2002} \equiv 4^{4} \equiv 256 \equiv 13 \equiv 4 \mod{9}$, we know that we need that $t \geq 4$. Now it merely suffices to find a construction. We take $x_1 = x_2 = 2002^{2001}1000$ and $x_3 = x_4 = 2002^{2001}1000$. These will sum to $2002^{2002}$

I claim that the answer is $4$. \\\\
Note that by Euler's Totient, we have that $4^6\equiv 1\mod 9$, so using this, we have that
\[2002^{2002}\equiv 4^{2002}\equiv(4^{1998})*(4^4)\equiv4^4\equiv256\equiv 4 \mod 9.\]
Now, notice that all cubes must be $0$, $1$, or $-1$ mod $9$, meaning that we must have at least $4$ cubes in order to be able to have them sum to $2002^{2002}$, which can be achieved with
\[2002^{2002}=(10*2002^{667})^3+(10*2002^{667})^3+(2002^{667})^3+(2002^{667})^3,\]
finishing the problem.

I spent a while on this because i thought $t$ was $2002$ for a while and tunneled oops.
Note that the cubic residues modulo $9$ are $\{0,1,8 \}$.
$$2002^{2002} \equiv 4^{2002 \pmod{6}} \equiv 4^4 \equiv 4 \pmod{9}$$.
So the smallest possible value of $t$ is $\geq 4$.
Now for a construction take $(x_{1}, x_{2}, x_{3}, x_{4})=(10 \cdot 2002^{667},  10 \cdot 2002^{667}, 2002^{667}, 2002^{667})$

Taking the expression modulo $9$ implies that $t\geq 4$. Now we just need to see that $2002^{2002} = (2002^{667})^3(1+1+10^3+10^3)$ to end the problem.

$$\mathbb{Q.E.D.}$$


Given nonnegative integer numbers $ a,b,c,$

Prove that there does not exist a function $ f: N\minus{}>N$ satisfying for each $ x,y$ from $ N$:

$ f(x\plus{}y)\plus{}f(x)\plus{}f(y)\equal{}xy\plus{}ax\plus{}by\plus{}c$

put x->y and y->x: f(x+y) + f(x) + f(y) = xy + ax + by + c = xy + ay + bx + c, x(a - b) + y(b - a) = 0, for each x, y in N, so a = b
put y = 0: 2f(x) + f(0) = ax + c [1], f(x) = (a/2)x + (c - f(0))/2
in [1] put x = 0: c = 3f(0), so f(x) = (a/2)x + f(0)
Initial condition can be written: (a/2)(x + y) + (a/2)x + (a/2)y + 3f(0) = xy + ax + ay + 3f(0), 0 = xy, contradiction


geometry
incenter
trigonometry
geometry unsolved

i think could solve with Apollonius  LLP (P=ta) and then we have [b]r[/b]
then we have [b]a[/b] with p - (p-a)
and then  p=aha/2r we have [b]ha[/b]
and then tangent from [b]ta[/b] to C(A,ha)

is this correct ?

[b]no this is not correct i tried and didn't work[/b]
[b]ta[/b] is not the incenter BC foot  :(  :(  :(

it's simple: $ r_a \equal{} p \tan \frac{A}{2}$. Costruct the A-excircle $ \Gamma_a$ an call its center $ I_a$. Let on the segment $ AI_a$ a point P such that $ \overline{AP}\equal{}t_a$. The side line BC is one of the 2 tangent line from P to $ \Gamma_a$.


calculus
integration
trigonometry
symmetry
limit
calculus computations

For real number $ a$ with $ |a|>1$, evaluate $ \int_0^{2\pi} \frac{d\theta}{(a\plus{}\cos \theta)^2}$.

answer is:

\[ \frac{2\pi\sqrt{a\plus{}1}}{(a\minus{}1)\sqrt{a\minus{}1}}\]

by symmetry:

\[ \int_0^{2\pi}\frac{d\theta}{(a\plus{}\cos\theta)^2}\equal{}2\int_0^{\pi}\frac{d\theta}{(a\plus{}\cos\theta)^2}\equal{}\frac{2}{a^2}\int_0^{\pi}\cfrac{d\theta}{\left(1\plus{}\cfrac{\cos^2\frac{\theta}{2}\minus{}\sin^2\frac{\theta}{2}}{a}\right)^2}\equal{}\]

\[ \equal{}\frac{2}{a^2}\int_0^{\pi}\frac{1}{\cos^4\frac{\theta}{2}}\cfrac{d\theta}{\left(\frac{1}{\cos^2\frac{\theta}{2}}\plus{}\cfrac{1\minus{}\frac{sin^2\frac{\theta}{2}}{\cos^2\frac{\theta}{2}}}{a}\right)^2}\equal{}\frac{2}{a^2}\int_0^{\pi}\frac{1}{\cos^4\frac{\theta}{2}}\cfrac{d\theta}{\left(1\plus{}\tan^2\frac{\theta}{2}\plus{}\cfrac{1\minus{}\tan^2\frac{\theta}{2}}{a}\right)^2}\equal{}\]

\[ \equal{}\frac{2}{a^2}\int_0^{\pi}\frac{1}{\cos^4\frac{\theta}{2}}\cfrac{d\theta}{\left(1\plus{}\frac{1}{a}\plus{}\left(1\minus{}\frac{1}{a}\right)\tan^2\frac{\theta}{2}\right)^2}\equal{}\]

\[ \equal{}\frac{2}{(a\plus{}1)^2}\int_0^{\pi}\frac{1}{\cos^4\frac{\theta}{2}}\cfrac{d\theta}{\left(1\plus{}\frac{a\minus{}1}{a\plus{}1}\tan^2\frac{\theta}{2}\right)^2}\]

Put $ \psi^2\equal{}\frac{a\minus{}1}{a\plus{}1}$, and:

\[ \psi \tan\frac{\theta}{2}\equal{}\sinh u \Longrightarrow d\theta \equal{} \frac{2\cos^2\frac{\theta}{2}}{\psi}\cosh{u}du\]

So the integral:

\[ \equal{} \frac{4}{\psi (a\plus{}1)^2}\int_0^{\infty}\frac{1}{\cos^4\frac{\theta}{2}}\frac{\cos^2\frac{\theta}{2}\cosh{u}\;du}{(1\plus{}\sinh^2{u})^2}\equal{}\frac{4}{\psi (a\plus{}1)^2}\int_0^{\infty}\left(1\plus{}\frac{\sinh^2{u}}{\psi^2}\right)\frac{du}{\cosh^3{u}}\equal{}\]

\[ \equal{}\frac{4}{\psi (a\plus{}1)^2}\left(1\minus{}\frac{1}{\psi^2}\right)\int_0^{\infty}\frac{1}{\cosh^3{u}}du \;\; \plus{} \;\;\frac{4}{\psi^3 (a\plus{}1)^2}\int_0^{\infty}\frac{1}{\cosh{u}}du\]

These two integrals can be easily calculated to be:

\[ \int_0^{\infty}\frac{1}{\cosh^3{u}}du \equal{} \frac{\pi}{4} \;\;\;\; \int_0^{\infty}\frac{1}{\cosh{u}}du \equal{} \frac{\pi}{2}\]

Plugging back and rearranging we have:

\[ \equal{} \frac{\pi (\psi^2\plus{}1)}{\psi^3(a\plus{}1)^2}\equal{} \frac{2\pi a}{(a^2\minus{}1)^{\frac32}}\]

So our integral is:

\[ \int_0^{2\pi}\frac{d\theta}{(a\plus{}\cos\theta)^2}\equal{}\frac{2\pi a}{(a^2\minus{}1)^{\frac32}}\]

(I missed a constant factor when I first did it, so thats why my previous answer differs a bit...  :oops: )

[hide]Define $ f(a) \equal{} \int_0^{\pi} \frac{1}{a \plus{} \cos \theta} \, d \theta$ and $ g(a) \equal{} \int_0^{\pi} \frac{1}{a \minus{} \cos \theta} \, d \theta$, with a > 1. Making the substitution $ \tan \frac{\theta}{2} \equal{} x$, we have

$ f(a) \equal{} 2\int_0^{\plus{} \infty} \frac{1}{a(x^2\plus{}1) \plus{} 1 \minus{} x^2}\,dx \equal{} 2 \int_0^{\plus{} \infty} \frac{1}{(a\plus{}1) \plus{} (a\minus{}1)x^2}\,dx$

$ \equal{} \frac{2}{\sqrt{a^2\minus{}1}} \int_0^{\plus{} \infty} \frac{\sqrt{\frac{a\minus{}1}{a\plus{}1}}}{1 \plus{} \left(x \sqrt{\frac{a\minus{}1}{a\plus{}1}}\right)^2}\,dx$

$ \equal{} \frac{2}{\sqrt{a^2\minus{}1}} \lim_{b \to \plus{} \infty} \left[\arctan\left(x \sqrt{\frac{a\minus{}1}{a\plus{}1}}\right)\right]^b_0$

$ \equal{} \frac{\pi}{\sqrt{a^2\minus{}1}}$.

In a similar fashion we can prove that $ g(a) \equal{} \frac{\pi}{\sqrt{a^2\minus{}1}}$.

Now we note that:

$ \frac{d f(a)}{da} \equal{} \frac{d}{da} \, \frac{\pi}{\sqrt{a^2\minus{}1}} \equal{} \minus{} \frac{\pi a}{(a^2\minus{}1)^{3/2}} \equal{} \int_0^{\pi} \frac{d}{da} \frac{1}{a \plus{} \cos \theta}\,d \theta \equal{} \minus{} \int_0^{\pi} \frac{1}{(a \plus{} \cos \theta)^2}\,d \theta$

$ \equal{}> \int_0^{\pi} \frac{1}{(a \plus{} \cos \theta)^2}\,d \theta \equal{} \frac{\pi a}{(a^2\minus{}1)^{3/2}}$.

Similarly, we find that $ \int_0^{\pi} \frac{1}{(a \minus{} \cos \theta)^2}\,d \theta \equal{} \frac{\pi a}{(a^2\minus{}1)^{3/2}}$.

Now let a > 1. Then,

$ \int_0^{2 \pi} \frac{1}{(a \plus{} \cos \theta)^2}\,d \theta \equal{} \int_0^{\pi} \frac{1}{(a \plus{} \cos \theta)^2}\,d \theta \plus{} \int_{\pi}^{2 \pi} \frac{1}{(a \plus{} \cos \theta)^2}\,d \theta$

$ \equal{} \int_0^{\pi} \frac{1}{(a \plus{} \cos \theta)^2}\,d \theta \plus{} \int_0^{\pi} \frac{1}{(a \minus{} \cos \theta)^2}\,d \theta$

where the substitution $ \theta \equal{} x \plus{} \pi$ was made on the second integral. Therefore, for a > 1,

$ \int_0^{2 \pi} \frac{1}{(a \plus{} \cos \theta)^2}\,d \theta \equal{} \frac{\pi a}{(a^2\minus{}1)^{3/2}} \plus{} \frac{\pi a}{(a^2\minus{}1)^{3/2}} \equal{} \frac{2 \pi a}{(a^2\minus{}1)^{3/2}}$.

If a < -1, then

$ \int_0^{2 \pi} \frac{1}{(a \plus{} \cos \theta)^2}\,d \theta \equal{} \int_0^{\pi} \frac{1}{(a \plus{} \cos \theta)^2}\,d \theta \plus{} \int_0^{\pi} \frac{1}{(a \minus{} \cos \theta)^2}\,d \theta$

$ \equal{} \int_0^{\pi} \frac{1}{(\minus{}a \minus{} \cos \theta)^2}\,d \theta \plus{} \int_0^{\pi} \frac{1}{(\minus{}a \plus{} \cos \theta)^2}\,d \theta$

$ \equal{} \frac{\pi (\minus{}a)}{(a^2\minus{}1)^{3/2}} \plus{} \frac{\pi (\minus{}a)}{(a^2\minus{}1)^{3/2}} \equal{} \frac{2 \pi (\minus{}a)}{(a^2\minus{}1)^{3/2}} \equal{} \frac{2 \pi |a|}{(a^2\minus{}1)^{3/2}}$

(because now -a > 1, and |a| = -a if a < 0). Therefore, since |a| = a if a > 0, for any |a| > 1, we have

$ \int_0^{2 \pi} \frac{1}{(a \plus{} \cos \theta)^2}\,d \theta \equal{} \frac{2 \pi |a|}{(a^2\minus{}1)^{3/2}}$.[/hide]

Much simpler solution:

$ \int_0^{2\pi} \frac{1}{(a \plus{} \cos \theta)^2} \, d \theta= \int_0^{\pi} \frac{1}{(a \plus{} \cos \theta)^2}+ \frac{1}{(a \plus{} \cos (2\pi-\theta))^2} \, d \theta $

$=2\int_0^{\pi} \frac{1}{(a \plus{} \cos \theta)^2} \, d \theta  $

$=\frac {2}{a^2-1}\int_0^{\pi} \frac{a^2-1}{(a \plus{} \cos \theta)^2} \, d \theta  $

$=\frac {2}{a^2-1}\int_0^{\pi} \frac{a(a+\cos \theta)-(a\cos \theta +1)}{(a \plus{} \cos \theta)^2} \, d \theta  $

$=\frac {2a}{a^2-1}\int_0^{\pi} \frac{1}{a \plus{} \cos \theta} \, d \theta-\frac {2}{a^2-1}\int_0^{\pi} \frac{a\cos \theta +\cos ^2\theta+\sin ^2\theta}{(a \plus{} \cos \theta)^2} \, d \theta  $

$=\frac {2a}{a^2-1}\int_0^{\pi} \frac{1+\tan^2\frac{\theta}{2}}{a(1+\tan^2\frac{\theta}{2}) \plus{} 1-\tan^2\frac{\theta}{2}} \, d \theta-\frac {2}{a^2-1}\int_0^{\pi} \frac{\cos \theta (a +\cos \theta)+\sin ^2\theta}{(a \plus{} \cos \theta)^2} \, d \theta  $

$=\boxed{\frac {2a}{(a^2-1)(a+1)}\int_0^{\pi} \frac{\sec^2\frac{\theta}{2}}{1+\biggl(\sqrt{\frac {a-1}{a+1}}\tan\frac{\theta}{2}\biggr)^2 } \, d \theta-\frac {2}{a^2-1}\int_0^{\pi} \frac{(\sin \theta)' (a +\cos \theta)-\sin \theta(a+\cos \theta)'}{(a \plus{} \cos \theta)^2} \, d \theta}  $

$=\frac {4|a|}{(a^2-1)\sqrt{a^2-1}}\biggl(\tan^{-1} \sqrt{\frac {a-1}{a+1}}\tan\frac{\theta}{2}\biggr)_0^{\pi}-\frac {2}{a^2-1} \biggl(\frac{\sin \theta}{a \plus{} \cos \theta}\biggr)_0^{\pi} $

$=\frac {2|a|\pi}{(a^2-1)\sqrt{a^2-1}}$


Rectangle A is inscribed in ractnagle B so that each side of rectangle B contains one and only vertex of rectangle A.  If the dimensions of rectangle A are 1 and 2, and the area of rectangle B is $\frac{22}{5}$, compute the perimeter of rectangle B.

Refer to the below diagram.  WMZ, ZOY, YXP, and XNW are similar, with pairs of opposite triangles congruent.  Let MW =  XP = x.  Then MZ = XP = (1-x^2)^(1/2), and since the ratio of similarity is 1:2, ZO = XN = 2x and OY = WN = 2(1-x^2)^(1/2).  So the dimensions of rectangle MNPO are x+2(1-x^2)^(1/2) by 2x+(1-x^2)^(1/2).  Since the area of this rectangle is 22/5, we have

[x+2(1-x^2)^(1/2)]*[2x+(1-x)^(1/2)] = 22/5
2x^2 + 5x(1-x^2)^(1/2) + 2(1-x^2) = 22/5
5x(1-x^2)^(1/2) = 12/5
x(1-x^2)^(1/2) = 12/25
x^2(1-x^2) = 144/625
x^4 - x^2 + 144/625 = 0
(x^2 - 16/25)(x^2 - 9/25) = 0
x = 4/5 or 3/5.

Thus the dimensions of MNPO are 11/5 by 2.  The perimeter is then 42/5.


Suppose $ A$ and $ B$ are $ n\times n$ matrices satisfying $ A^2 \equal{} A$, $ B^2 \equal{} B$ and $ (A \plus{} B)^2 \equal{} A \plus{} B$. Is it true that $ AB \equal{} O$?

$ (A\plus{}B)^2 \equal{} A \plus{} B$

$ <\equal{}> (A\plus{}B)(A\plus{}B) \equal{} A\plus{}B$

$ <\equal{}> A^2 \plus{} AB \plus{} BA \plus{} B^2 \equal{} A \plus{} B$

$ <\equal{}> A \plus{} AB \plus{} BA \plus{} B \equal{} A \plus{} B$

$ <\equal{}> AB \plus{} BA \equal{} O$ *

$ <\equal{}> A(AB \plus{} BA) \equal{} AO$

$ <\equal{}> A^2B \plus{} ABA \equal{} O$

$ <\equal{}> AB \plus{} ABA \equal{} O$

$ <\equal{}> AB(I \plus{} A) \equal{} O$

$ <\equal{}> \minus{}BA(I \plus{} A) \equal{} O$ **

$ <\equal{}> \minus{}BA \minus{} BA^2 \equal{} O$

$ <\equal{}> \minus{}BA \minus{} BA \equal{} O$

$ <\equal{}> \minus{}2BA \equal{} O$

$ <\equal{}> BA \equal{} O$

$ \equal{}> AB \equal{} O$***

where equalities ** and *** follow from *.

ifai didn't specify the field these matrices were over. There needs to be a hypothesis that the field is not of characteristic $ 2.$ The statement is false in characteristic $ 2$, as can be seen by letting $ A\equal{}B\equal{}I.$

Can you spot in Carcul's proof the one line in which he needed the characteristic of the field not to be $ 2?$

[quote="Carcul"]$ (A \plus{} B)^2 \equal{} A \plus{} B$
$ < \equal{} > \minus{} 2BA \equal{} O$

$ < \equal{} > BA \equal{} O$
where equalities ** and *** follow from *.[/quote]
Maybe in this step ?  :)


algebra
polynomial
Ring Theory
algebra unsolved

Rationalize:

$ \displaystyle\frac{1}{1\plus{}\sqrt[]{3}\plus{}\sqrt[4]{5}\plus{}\sqrt[6]{7}\plus{}\sqrt[8]{9}}$

indicate the amount of rational denominator figures.

 Greetings:D

[quote="TALENTO"]Rationalize:

$ \displaystyle\frac {1}{1 \plus{} \sqrt []{3} \plus{} \sqrt [4]{5} \plus{} \sqrt [6]{7} \plus{} \sqrt [8]{9}}$

indicate the amount of rational denominator figures.

 Greetings:D[/quote]

I'm sorry but I dont understand the phrase "indicate the amount of rational denominator figures."

What is the problem exactly ? To show that $ \sqrt []{3} \plus{} \sqrt [4]{5} \plus{} \sqrt [6]{7} \plus{} \sqrt [8]{9}$ is a rational number ?  :huh:

$ \frac {1}{1 \plus{} \sqrt []{3}}$ : http://www.wolframalpha.com/input/?i=1%2F%281%2Bpower%283%2C1%2F2%29%29
$ \frac {1}{1 \plus{} \sqrt []{3} \plus{} \sqrt [4]{5}}$ : http://www.wolframalpha.com/input/?i=1%2F%281%2Bpower%283%2C1%2F2%29%2Bpower%285%2C1%2F4%29%29
$ \frac {1}{1 \plus{} \sqrt []{3} \plus{} \sqrt [4]{5} \plus{} \sqrt [6]{7}}$ : http://www.wolframalpha.com/input/?i=1%2F%281%2Bpower%283%2C1%2F2%29%2Bpower%285%2C1%2F4%29%2Bpower%287%2C1%2F6%29%29
$ \frac {1}{1 \plus{} \sqrt []{3} \plus{} \sqrt [4]{5} \plus{} \sqrt [6]{7} \plus{} \sqrt [8]{9}}$ : http://www.wolframalpha.com/input/?i=1%2F%281%2Bpower%283%2C1%2F2%29%2Bpower%285%2C1%2F4%29%2Bpower%287%2C1%2F6%29%2Bpower%289%2C1%2F8%29%29

Somebody may be able to calculate, but I think the result to be considerably complicated.

Hello excuse my English not so good. the problem is in Spanish and do not translate well.
What he asks is to rationalize and to indicate the sum of digits of the denominator.

Greetings  :D

Hello not understand this but as it relates to rationalize, to for example:

$ \displaystyle\frac{1}{\sqrt[]{10}}\equal{}\displaystyle\frac{\sqrt[]{10}}{10}$

$ \displaystyle\frac{1}{\sqrt[]{10}\plus{}1}\equal{}\displaystyle\frac{\sqrt[]{10}\minus{}1}{9}$

Greetings  :D

Another example would be:

$ \displaystyle\frac {1}{1 \plus{} \sqrt []{3} \plus{} \sqrt [4]{5}} \equal{} \displaystyle\frac {(1 \plus{} \sqrt []{3} \minus{} \sqrt [4]{5})(4 \minus{} 2\sqrt []{3} \plus{} \sqrt []{5})(1 \plus{} 4\sqrt []{15})}{239}$

Greetings  :D

[quote="TALENTO"]Another example would be:

$ \displaystyle\frac {1}{1 \plus{} \sqrt []{3} \plus{} \sqrt [4]{5}} \equal{} \displaystyle\frac {(1 \plus{} \sqrt []{3} \minus{} \sqrt [4]{5})(4 \plus{} 2\sqrt []{3} \plus{} \sqrt []{5})(33 \plus{} 4\sqrt []{15})}{849}$

Greetings  :D[/quote]

Unfortunately, this is wrong.

$ 1\plus{}\sqrt 3\plus{}\sqrt[4]5 > 2$ and so $ LHS<\frac 12$

$ 1\plus{}\sqrt 3\minus{}\sqrt[4]5>1$
$ 4\plus{}2\sqrt 3\plus{}\sqrt 5>9$
$ 33\plus{}4\sqrt{15}>48$

So $ RHS >\frac {432}{849}>\frac 12$

So $ RHS > LHS$ and your equality is wrong.

Pco thanks right now if I corrected already

Greetings  :D

I have an idea of the method the problem can be solved but for my computer it takes too much time to do the computations. I tried to make an univariate polynomial ring by Sage but I'm not interested to wait until it finishes computations. I takes at least several minutes to make the ring and I terminated the computation before it finishes.

I asked the problem on sage forum: http://groups.google.com/group/sage-support/browse_thread/thread/5b9c3ad40447d6b4

I suppose TALENTO found this problem in some contest (could you confirm, TALENTO ?) and so it certainly may be solved in some clever lines, without any heavy tool.

The problem is in trouble and how to solve algebra editorial Racso

What I think is that it is appropriate to find a rationalizing factor and eliminating the radicals in the denominator.

But as calls for the sum of rational numbers in the denominator could be thought of other things. As you may not need to find the sum razionalizar figures.

Greetings  :D


calculus
integration
trigonometry
logarithms
function
calculus computations

how can we find sums like :  $ \sum_{n\equal{}0}^\infty \frac{1}{3\plus{}8n(n\plus{}1)}$

If I did not have Maple handy  :)  (it returns $ \frac{\sqrt{2}\pi}{8}\tanh\frac{\sqrt 2 \pi}{4}$), I would let $ f(x)\equal{}\sum_{n\equal{}0}^\infty \frac{x^{n\plus{}1}}{3\plus{}8n(n\plus{}1)}$. Since $ 3f(x)\plus{}8x^2f''(x)\equal{}\sum_{n\equal{}0}^\infty (3\plus{}8n(n\plus{}1))\frac{x^{n\plus{}1}}{3\plus{}8n(n\plus{}1)}\equal{}\frac{x}{1\minus{}x}$, we have a hope of finding $ f$ by solving this differential equation. The problem is, I can't solve it.  :(

[quote="waelalghamdi"]how can we find sums like :  $ \sum_{n \equal{} 0}^\infty \frac {1}{3 \plus{} 8n(n \plus{} 1)}$[/quote]

there are quite a few ways of finding such sums, integral calculus, complex variables, etc.  ........ here is an elementary method, uses trigonometry.

what you have is

 $ \textbf S \;\equal{}\; \sum_{n \equal{} 0}^\infty \frac {1}{3 \plus{} 8n(n \plus{} 1)} \;\equal{}\; \dfrac {1} { 8} \sum_{n \equal{} 0}^\infty \frac {1}{ \left( n\plus{}\dfrac{1}{2}\right) ^ 2 \plus{} \left( \dfrac{1}{\sqrt 8}\right) ^2 } \qquad \qquad \ldots \;\;\;\ldots \;\;\; (1)$

now start with

$ \cos \,\theta \;\equal{}\; \prod_{k\equal{}0} ^\infty \; \left( \; 1 \minus{} \dfrac {4\,\theta ^ 2} { (2k\plus{}1) ^2 \; \pi ^2} \right)$

take natural logarithms of both sides and differentiate w.r.t.  $ \theta$ to get

$ \tan\,\theta \;\equal{}\; \sum_{k\equal{}0} ^\infty \;\dfrac { 8\;\theta } { (2k\plus{}1)^2\;\pi^2 \minus{} 4\,\theta ^2 }$

$ \text {replace } \qquad \theta \qquad \text {with } \qquad \imath \cdot \pi\,\theta \qquad \text { to get }$

$ \tan \;  (\imath \cdot \pi\,\theta ) \;\equal{}\; \imath\; \tanh \left( \pi\,\theta\right) \;\equal{}\; \sum_{k\equal{}0} ^\infty \;\dfrac { 8\;\imath \cdot \pi\,\theta } { (2k\plus{}1)^2\;\pi^2 \plus{} 4\,\pi^2\,\theta ^2 }$

$ \Rightarrow \qquad \sqrt 8 \cdot  \tanh \left( \pi\,\theta \right) \;\equal{}\; \dfrac {2}{\pi}  \;\sum_{k\equal{}0} ^\infty \;\dfrac { \sqrt 8 \cdot \theta } {(k\plus{} \dfrac {1}{2} )^2  \plus{} \theta ^2 }$

comparing with equation $ (1)$,  we see that we need to put $ \theta \;\equal{}\;  \dfrac {1} {\sqrt 8}$ and we are basically done. and so,

$ \textbf S \;\equal{}\; \boxed { \dfrac {\pi}{2\;\sqrt 8 } \;\tanh \left( \dfrac {\pi } {\sqrt 8} \right) }$

As the sum is asked upto infinity can we take limit n->infinity of the integral of the function?

well the sum and integral aren't identical
it seems like it'd be pretty complicated.

[quote="waelalghamdi"]thanks mlok & misan,,,

and if anyone knows other ways (preferred more elementary) please post them.[/quote]

i know of $ 3$ other ways of doing it ( but i am not going to type them out here ), and i am sure there isn't going to be a more elementary solution than the one i posted..... one only needs to know some basic trigonometry and some basic calculus to get to the answer...  :|


linear algebra
matrix
geometry proposed
geometry

A circle passes through 3 non-collinear points $(a,b) (c,d) (e,f)$. What point is the center of the circle located on?  The final answer should not have any trigonometric functions.

The equation of the circle is $\left | \begin{array}{cccc} x^2+y^2 & x & y & 1\\\ a^2+b^2 & a & b & 1\\\ c^2+d^2 & c & d & 1\\\ e^2+f^2 & e & f & 1\\ \end{array}\right| =0$. From this equation

you can easily find the centre $O(x_0,\ y_0)$and the radius $R$ of the circle:

$\Delta\cdot (x^2+y^2)+mx+nx+p=0$, i.e. $(x-x_0)^2+(y-y_0)^2=R^2\Longrightarrow$

$x_0=-\frac{m}{2\Delta},\ y_0=-\frac{n}{2\Delta}, R^2=\frac{m^2+n^2-4p\Delta}{4\Delta ^2}$, where

$\Delta=\left | \begin{array}{ccc} a & b & 1\\\ c & d & 1\\\ e & f & 1 \\ \end{array}\right| \ne 0\Longrightarrow x_0= \frac{1}{2\Delta}\cdot \left | \begin{array}{ccc} a^2+b^2 & b & 1\\\ c^2+d^2 & d & 1\\\ e^2+f^2 & f & 1 \end{array}\right| \ ;\ \ \ y_0=$$-\frac{1}{2\Delta} \cdot \left| \begin{array}{ccc} a^2+b^2 & a & 1\\\ c^2+d^2 & c & 1\\\ e^2+f^2 & e & 1\\ \end{array} \right| .$

Well no one has posted in this for a while... and not quite understanding what Virgil Nicula has shown... I thought I might just give the answer:
[hide]$y=\frac{a(c^2-e^2+d^2-f^2)+c(e^2-a^2+f^2-b^2)+e(a^2-c^2+b^2-d^2)}{2b(e-c)+2d(a-e)+2f(c-a)}$

$x=\frac{b(d^2-f^2+c^2-e^2)+d(f^2-b^2+e^2-a^2)+f(b^2-d^2+a^2-c^2)}{2a(f-d)+2c(b-f)+2e(d-b)}$[/hide]
I would show my proof, but its really long and I don't have time to type it.

You will learn later the notion " the determinant of a matrix ".


dayereye W va vatare BC az an mafroozand(saabet)
noghteye motaghayere A rooye kaman BC (yeki az kaman ha) motoghayer ast.
dayereye W1 bar AB(dar X),BC(dar Y) va W momas asd
agar vasate XY ra Z benamim sabet konid:
AZ ba taghyire A az noghteye saabet migozarad

[color=blue]Masale[/color]. Mosalas $ABC$ mafroz ast. Farz konid $\mathcal C$ dayere mohiti va $\mathcal W$ dayere bashad ke bar $AB ,AC$ va $\mathcal C$ , be tartib dar $X,Y,Z$ momas ast.Neshan dahid $I$ markaze dayere mohatiye $ABC$ , vasate parekate $XY$ast.

[color=blue]Rahehale[/color] farz konid $R$ vas $S$ markaze caman haye $AB$ va $AC$ ke shamel $C$ va $B$ nistand bashand.
Tabdile tajanosi ke be markaze $Z$ , $\mathcal W$ ro be $\mathcal C$ tabdil mikonad $X$ ra be $R$ va $Y$ ra be $S$ badal mikonad. Dar natije $ZXR$ va $ZYS$ bar yek estaghamatan.

Sesh zelhi ye mohatiye $RASCZB$ ra dar nazar begirid. Bana bar ghaziyeye pascual : $X$ , $Y$ va mahale taghotoye $CR$ va $BS$ ke markaze dayere mohatist ham khatand.
Masale Hal shod.


function algorithm parameterization algebra polynomial trigonometry geometry

I need some help with the following program.  This program is supposed to run under 5 seconds.  i've got this working code but it goes way pass 5 seconds as the data gets larger and larger.  So far this is what I have done.  I'm using a recursive function to
go through this. I have the code and program below:  DOes anyone have a better idea?

The cows have not only created their own government but they have chosen to create their own money system. In their own rebellious way, they are curious about values of coinage. Traditionally, coins come in values like 1, 5, 10, 20 or 25, 50, and 100 units, sometimes with a 2 unit coin thrown in for good measure.

The cows want to know how many different ways it is possible to dispense a certain amount of money using various coin systems. For instance, using a system of {1, 2, 5, 10, ...} it is possible to create 18 units several different ways, including: 18x1, 9x2, 8x2+2x1, 3x5+2+1, and many others.

Write a program to compute how many ways to construct a given amount of money using supplied coinage. It is guaranteed that the total will fit into both a signed long long (C/C++) and Int64 (Free Pascal).

PROGRAM NAME: money
INPUT FORMAT
The number of coins in the system is V (1 <= V <= 25).

The amount money to construct is N (1 <= N <= 10,000). Line 1:  Two integers, V and N
Lines 2..:  V integers that represent the available coins (no particular number of integers per line)

SAMPLE INPUT (file money.in)
3 10
1 2 5

OUTPUT FORMAT
A single line containing the total number of ways to construct N money units using V coins.
SAMPLE OUTPUT (file money.out)
10

#include<iostream>
#include<fstream>

using namespace std;

int numberofcoins, amount, numberofsolutions;
int coin[25];

void calc(int c, int startindex)
{
int totalamount;
totalamount=c;

for(int a=startindex;a<numberofcoins;a++)
{
if(totalamount==amount)
{
numberofsolutions++;
return;
}

if(totalamount>amount)
{
return;
}

else
calc(totalamount+coin[a],a);
}

}

char junk;
int main()
{
ifstream infile("money.in");
ofstream outfile("money.out");
infile>>numberofcoins;
cout<<"The number of different coins is"<<" "<<numberofcoins<<endl;
infile.get(junk);
infile>>amount;
cout<<"The amount is:"<<" "<<amount<<endl;
infile.get(junk);
cout<<"The coins are"<<endl;
for(int b=0;b<numberofcoins;b++)
{
infile>>coin[b];
infile.get(junk);
}
int minIndex;
int temp=0;
for(int a=0;a<numberofcoins;a++)
{
minIndex=a;
for(int c=a;c<numberofcoins;c++)
{
if(coin[c]<coin[minIndex])
minIndex=a;
}
temp=coin[c];
coin[c]=coin[minIndex];
coin[minIndex]=coin[c];
}
for(int a=0;a<numberofcoins;a++)
cout<<coin[a]<<" ";
cout<<endl;

calc(0,0);
outfile<<numberofsolutions<<endl;
return 0;
}

Can you explain what your program does, like your telling a human what to do instead of a computer?  Sorry, but it's hard to read un-indented stuff, and I really don't know C++ that much.

Well he did, didn't he? :?

anyway, I'd consider working with modulo. Arrange them from small to large and look. There's an easy solution to this, it's just a very classical combinatorics problem that works with modulo :)

And about the 5 seconds, eum :P perhaps on a 386 processor :D

It's

I'm too lazy to try and figure out what the code does since it look's so bad, and people who are more familiar with other languages (i.e. me)  will have an even more hard time.

And I'm on this prgram too.  What I would do is try to find out how many ways you can get to N with just one type of coin, then two and so on.

yea.  I emailed Mr. Kolstad and that was what was needed to do the program.  However, DP is different for every problem.  Basically, DP for one problem may not be the same for different one.  What I did was that I used a recursive function to add up the coins one by one.  I started from the largest coins and added just as large or smaller coins.  Supposedly DP means no recursive functions whatsoever.  What im stuck on is to how to DP this program.  Does anyone have any idea?

[quote="guangweicao"]Supposedly DP means no recursive functions whatsoever.[/quote]
Where did you get this idea?  :?
[quote="USACO Training Site"]Dynamic programming is a confusing name for a programming technique that dramatically reduces the runtime of algorithms: from exponential to polynomial. The basic idea is to try to avoid solving the same problem or subproblem twice.[/quote]
I've solved quite a few DP problems with recursion. :)

The key is to [b]avoid solving the same subproblem twice.[/b]  I think the example given on the site (finding the maximum decreasing subsequence of a series of integers) is quite confusing for those first learning DP. I know it was for me when I was trying to figure out what it meant.

I think a simpler example is the fibonacci sequence. Let's say it's your job to find out what the nth term of the fibonacci sequence is.  How would you approach this problem? (Anyone feel free to post ideas)

[quote="h_s_potter2002"]Have you tried using the Greedy Algorithm to help?[/quote]
Please explain how you would use the greedy algorithm on this problem.  I'm not exactly sure how it would be applied here.

I emailed mr. kolstad and this was what he had to say:

Suppose we know how to make N cents with the first K types of coins.
We can probably seed that with 1 cent and 1 type of coin -- exactly
one way.  We can even seed it with all the single coin values.

Now, if we know that, then
   nways(N,K) = nway(N, K-1) + nway(N-coin[K], K);

   "the number of ways to make N cents with the first k
    coins is the number of ways to make N cents using the first K-1
    coins (i.e., without using the Kth coin) plus the number of
    ways to make N-coin[K] cents using the first K coins.  For the
    second set of ways, we then add the Kth coin to arrive at a
    total of N cents.

im still havent got what this means yet.  Can someone clarify?

[quote="countersixte"]I think a simpler example is the fibonacci sequence. Let's say it's your job to find out what the nth term of the fibonacci sequence is.  How would you approach this problem? (Anyone feel free to post ideas)[/quote]

I would make an array, N long, and make the first two values 1 and 1.  THen, I would add the two values before the first empty space, and put the result in that space.  That way, you wouldn't need to find out the 3rd number in the seqence twice.

And I forgot about my idea using the Greedy Algorithm.

For fibonacci, I'd use the general term :D

[quote="h_s_potter2002"]I would make an array, N long, and make the first two values 1 and 1.  THen, I would add the two values before the first empty space, and put the result in that space.  That way, you wouldn't need to find out the 3rd number in the seqence twice.[/quote]

Excellent idea.  This is much better than simply using recursive descent and calculating each term over and over again.

A slight variation on this is to do the recursive descent, but each time you check to see if you have already calculated that term.  If you have, simply return the term.  Otherwise, you must calculate the value of the term.  This way, along with [b]h_s_potter2002[/b]'s idea, only forces you to compute the value of each term once.

As you can see, it is typical for these types of problems to have both an iterative and recursive solution.  Personally, I prefer the recursive solution because it is more intuitive to me, but the choice is yours.

there is two way to achieve DP
top-down or bottom-up (i am not sure which is which)
take the fibonnacci sequence

one way is classical DP
f[0]=f[1]=1
for (i=2;i<n;i++)
f[i]=f[i-1]+f[i-2];

this is one way, the other way is memoization

something like
f[1..n]=0
int fib(int x){
  if (x==1 || x==0) return 1;
  if (f[x]==0) f[x]=fib(x-1)+fib(x-2);
  return f[x];
}

My algorithm is 15 lines long, and utilises a recursion. (I was too lazy to implement I/O.)

The basic idea is to use the recursion efficiently. When the recursive function starts, it is given a target amount to reach, and a "max" parameter indicating the monetary values it's allowed to use. (In my program, max is the index of the coins array; as max increases, the number of available coins decreases.) The function then deals with each case: 0 coins of "max" value are used, 1 coin of "max" value is used, and so on. For each case, it decreases the target value accordingly and adds 1 to max. When the index gets to the last element (invariably 1, otherwise some cases are not solvable), the function returns 1 (there is only one way, given a target amount, to accomplish the task with 1c coins). [i]Edit: the revised version returns 0 if no solution can be found, just in case the cows don't feel like using 1c coins.[/i] Then the function mops up all the values its recursions give, and returns it.

Revised Java program [url=http://www.0t8.net/files/coinage.txt]here[/url].

[quote="bugzpodder"]i think he changed it for everyone because i havent emailed him recently (last time i emailed him about it was three months ago when he said i had too much templates)[/quote]
He must have changed it fairly recently, since I had a compile-time problem a few weeks ago, as I said earlier.

So, [b]guangweicao[/b], did you solve the problem yet?  :)

I've been on the thing ever since the end of May, and the time limit for me was only 5 minutes.

Anyways, I'm the same problem, and here's how I'm trying it.  I think it's too slow though, I'm sure though since there is a run-time error when I try to run it on the website, and plus, it's down right now:

int findWays(int amount, int amountUsed)
{
	int i, ways=0;

	if(amount == 0)
		return 1;
	else if(amount < 0)
		return 0;
	else
	{
		for(i=0; coins[i]<=amountUsed; i++)
		{
			ways += findWays(amount - coins[i], coins[i]);
		}
		return ways;
	}
}

So basically, you start out with the total amount.  Then, you subtract the value of a coin from it.  You then do this for all of the values of the next coins that are smaller than or equal to the coin last subtracted, so that 121 and 211 aren't counted as different.  Keep doing this untill you get an amount less than or equal to 0.  If the amount is euqal to 0, then you add one to the number of ways.  Otherwise, you do nothing.

I think there is a another way to do this, becuase this one seems like it won't really work for all of the test cases.

Let's say this is the input:
-------------------
3 10
1 2 5
-------------------
So, we have 3 coins ( 1 cents, 2 cents and 5 cents).  We have to find the number of ways we can make 10 cents with these coins.  Try to find a solution that deals with each coin only once, and then the frequency of that coin is "locked in".  I will show you the first step of the program's execution and then rephrase the smaller problem in the form of another input.

(I am putting this into code to make it look a little nicer)

So, for this input, we have
[code]
0 5's --------------------> Find the solutions to:
                                     2 10
                                     1 2
1 5   --------------------> Find the solutions to:
                                     2 5
                                     1 2
2 5's --------------------> Find the solutions to:
                                     2 0
                                     1 2
[/code]

Hope this helps!

If anyone doesn't understand, don't hesitate to post questions/comments.

here are some hints:
1) How would you do this by hand?
2) If you knew how many ways you could construct every amount of money with the first K coins, could you figure out how many ways you could contruct an amount of money with the first K+1 coins?
3) In your recursive solution, are you calculating anything twice?

Would anyone care to comment on my solution [url=http://www.0t8.net/files/coinage.txt]here[/url]? Given my limited compsci experience, I'd like to know if the algorithm is time-and-space efficient. (It sure was simple to code, but as always simplicity doesn't always equal efficiency.)

Also, I am working through the USACO training site... currently reading the WINNING SOLUTIONS article. Mr. Kolstad has this following piece of advice:

"- Avoid dynamic memory like the plague: statically allocate everything."

Why's that? I've used dynamic memory allocation in at least 3 of my programs, and found them QUITE invaluable. It has saved me a lot of headache.

avoid doubles at all costs

you have something like i<=Target/coins[max]  (well you had coinsM which is the double value of coins[max])

try something like i*coins[max]<=Target

now everything is integers

[quote="Osiris"]
Also, I am working through the USACO training site... currently reading the WINNING SOLUTIONS article. Mr. Kolstad has this following piece of advice:

"- Avoid dynamic memory like the plague: statically allocate everything."

Why's that? I've used dynamic memory allocation in at least 3 of my programs, and found them QUITE invaluable. It has saved me a lot of headache.[/quote]

Dynamic memory is useful for some problems. But if you use it when you don't need it, you unnecessarily increase the chance of a bug, and the bug may occur well before the program actually crashes or produces the wrong answer, making it harder to find.

[quote="bugzpodder"]what exactly is dynamic memory allocation??  like when you use pointers and objects (such as when constructing a binary tree)??[/quote]
Yes, dynamic memory is often used when creating trees.  It involves allocating memory during a program's execution.  In C++, it involves the use of the [i]new[/i] and [i]delete[/i] operators.  In C, it involves the malloc function.  This newly allocated block of memory is often referred to through the use of pointers and the like.  It is often helpful to use dynamic memory when constructing ADTs to allocate space for new nodes.

I've tried two ways, and both aren't working for the last problem.  Here is the first one:

[code]int findWays(int amount, int amountUsed)
{
	int i, ways=0, j;

	for(i=0; coins[i]<amountUsed && coins[i]<=money; i++)
	{
		if(coins[0] == coins[i])
		{
			if(amount%coins[0] == 0)
				ways += 1;
			continue;
		}
		for(j=1; j*coins[i]<=money; j++)
		{
			if(amount - coins[i]*j > 0)
				ways += findWays(amount - coins[i]*j, coins[i]);
			else if(amount - coins[i]*j == 0)
				ways++;
			else ;
		}
	}
	return ways;
}[/code]

This one ia basically an improvement over the last one I posted.  I subtract an amount of money, using each coin untill I get a number equal to or less than 0.  The only difference in this one though it that I subtract multiples of that number too make it faster.  For example, in the first run,  for intput

3 10
1 2 5

I would subtract these numbers:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10  Using only 1's
2, 4, 6, 8, 10 using only 2's
5, 10 using only 5's

Here is the next way:

[code]int findWays(int amount, int nCoins)
{
	if(amount  == 0)
		return 1;
	else if(amount < 0)
		return 0;
	else if(nCoins == 1)
	{
		if(amount%coins[0]==0)
			return 1;
		return 0;
	}
	else
		return findWays(amount, nCoins-1) + findWays(amount-coins[nCoins-1], nCoins);
}[/code]

This is the way Mr. Kolstad told the OP, I think.  You basically find out the amount of ways there are for the first K-1 coins, and then find the number of ways there are to make the total amount, minus the amount of the kth coin, using the first K coins.

Both of these fail on the 8th test case:
25 100
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1

Is there any way to inrpove these ways?

Dynamic memory as in

int * intarray = new int [x];

where x can actually be a variable, not a const. I found this especially invaluable in the Number Triangles program, where if I were to read in the entire array, it would not be very space-efficient. Instead, I just had 2 dynamic arrays:

(array 1 contains line n - 1)
read line n into array 2
do operation on array 1 and 2
point array 1 to array 2 instead
point array 2 to a new location (new dynamic array)
repeat

Of course, after I solved the problem I saw Mr. Kolstad's solution, and it made me look like a fool.  :cool:

[quote="Osiris"]I found this especially invaluable in the Number Triangles program, where if I were to read in the entire array, it would not be very space-efficient.[/quote]
Although being space efficient might be quite important in real-world situations, for the USACO it doesn't matter how much space you waste as long as you don't go over the memory limit.

Also, the input for the problems will usually have some sort of bound, like "N rows ( 1 <= N <= 1000 )" so there is a limit on how much space you need to declare.  In this case, it is sometimes easier just to declare all of it ( as long as it is under the memory limit ) and only use as much as necessary.

I'm not saying that you can't dynamically allocate memory, I'm just saying that if you don't, it's one less thing you have to worry about.

[quote="h_s_potter2002"]Is there any way to inrpove these ways?[/quote]
Yes.  It looks like your second findWays function is almost there.  All you have to do is some "memoizing".  Memoization is a way of preventing your program from computing something twice.  Wasting time doing something twice is time you could be using to do something else.  Try making a two-dimensional array like this:
[code]int num_ways[MAX_NUMCOINS][MAX_AMOUNT][/code]

MAX_NUMCOINS would be 25 in this case and MAX_AMOUNT would be 10000.  Initialize all the elements of the num_ways to -1 or some other impossible value of your choice.  Then, make some changes in your findWays function.  The first thing your function should do is check to see if it has already done this particular computation before (i.e. is num_ways[nCoins-1][amount] >= 0?).  If it is, return this value and you're done.  Otherwise, you must compute the value just like you already are.  Then, right before you return, store the result into the corresponding position in the array. So you might have something like this:
[code]...
num_ways[nCoins-1][amount] = findWays(amount, nCoins-1) + findWays(amount-coins[nCoins-1], nCoins);
return num_ways[nCoins-1][amount];
...[/code]
That way, the next time your function comes across the same arguments, it won't have to recalculate the results.

Yeah, so it's like the same thing I did for the fibinocci ones earlier in this thread.  I think the main reason I didn't think of that was I thought all my function calls would be different.  Now the only problem I have i with the last test case, but I really have no idea on how to debug it, it would take way too long.


calculus
integration
function
geometry
rotation
geometric transformation
calculus computations

Hello,
i am having a final next week.i have three questions in voulme section i couldn't solve
please help me with any or all.

thanks
----------------------------
1-
---
Consider the region bounded by y=sec(x),y=1,x=0 and x=by/3.
Find the volum of the solid that is obtained by rotating that region around x-axis.

--
2-
--
consider the region bounded by y=x^1/2 and y=x.Find the volume of the solid that is obtained by rotating that region about the line x=2

---
3
---
Consider the region bounded by x=4y^2-y^3 and x=0.Find the volume of the solid obtained by rotating that region about x-axis

Thanks!

plz help espically with the last one
1000000 million thanks

For the last one I belive you would have to evaluate the following integral:

$\int_{0}^{4} (4x^2 - x^3)2 \pi x dx$

(Hint: switch the x and y axis around)

First consider the graph of the cubic function $x=4y^2-y^3$ on $y-x$ plane, that is to say, you will take the $y-axis$ for horizontal direction and $x-axis$ for vertical direction. Let $f(y)=4y^2-y^3,$ differentiate this with respect to $y$, we have $f'(y)=8y-3y^2=y(8-3y),$ so we obtain the maximal value $f(\frac{8}{3})=(\frac{8}{3})^2 (4-\frac{8}{3})=\frac{256}{27}),$ and the minimal value $f(0)=0$. Then Cut the solid by the plane $x=t\ (0\leq t\leq \frac{256}{27}),$ which is vertical to $x-axis$ and let $A\ (y_1,\ f(y_1)),\ B(y_2,\ f(y_2))\ (\frac{8}{3}\leq y_1 \leq 4,\ 0\leq y_2 \leq \frac{8}{3})$ be the intersection points of the cubic function $x=f(y)$ and the line $x=t.$ Now let $P$ the intersection point of the line $x=t$ and $x-axis,$ the cross-section which is obtained by cutting the solid by the plane $x=t$ is the line segment $AB.$ Thus the desired volume $V$ is obtained by integrating the something the area of the cross-section, which is the area bounded by two circles with the same center point $P,$ times the infinitesmal thickness in direction of $x$ with respect to $x$, we obtain as follows.

$V=\int_0^{\frac{256}{27}} \pi y_1^2\ dx-\int_0^{\frac{256}{27}} \pi y_2^2\ dx$

$=\pi (\int_4^{\frac{8}{3 }} y_1^2 \frac{dx}{dy_1}\ dy_1-\int_0^{\frac{8}{3}} y_2^2 \frac{dx}{dy_2}\ dy_2)$

$=\pi (-\int_{\frac{8}{3}}^4 y^2f'(y)\ dy-\int_0^{\frac{8}{3}} y^2f'(y)\ dy)\ \because \text{the variable of the integration is arbiterary real numbers}$

$=-\pi \int_0^4 y^2f'(y)\ dy\ \because \text{the unification of the integral interval}$

$=-\pi \{[f(y)\cdot y^2]_0^4\ -\int_0^4 f(y)\cdot 2y\ dy\}$

$\because \text{by the integral by parts and}\ f(0)=f(4)=0$

Consequently we obtain $\boxed{V=\int_0^4 2\pi y f(y)\ dy}$

I don't know the name of the method in your country, we call this Baum-Kohen Integral in particular among highschool students [b]in mathematics for entrance university [/b]in Japan. You can image the roll of the toilet paper , Japanese english? I don't admit using this Baum-Kohen Integral directly, because we don't always need to use it. Probably in your country this integral is the formula.

kunny

Thanks everybody VERY MUCH
i hope someone give me one-line solution of problem 2
again THANKS VERY VERY MUCH!

For #2:

If you graph your region, it is only bounded for x from 0 to 1. However, you are asked to rotate the region around the vertical line x = 2, so your volume is going to have, on average, a bigger radius. Thus the resulting integral is:

$\left[ \int_{0}^{1} (x^{\frac{1}{2}} - x) 2 \pi (2 - x) dx \right]$

edit: removed the term $\pi (1)^2 (1)$ from top.

In this case we don't need to use the formula $\int_a^b 2\pi |f(x)|\ dx$ ;)

By the way what do you call the method like this, swapnillium? :)

[quote="swapnillium"]For #2:

If you graph your region, it is only bounded for x from 0 to 1. However, you are asked to rotate the region around the vertical line x = 2. So after you rotate your region you would have to add this extra volume of the region between x = 1 to 2 (which forms a cylinder of radius 1 and height 1) to your volume. Thus the resulting integral is:

$\left[ \int_{0}^{1} (x^{\frac{1}{2}} - x) 2 \pi (2 - x) dx \right] + \pi (1)^2(1)$[/quote]

Where is the cylinder swapnillium ???  :huh: :)

I guess I didn't read the question so well. I was trying to rotate the empty space from x = 1 to 2.  :blush:

thanks very much
btw kunny,in q2 why did u use y^2 and y instead of y and y^(1/2) ??
can u also write it in term of x ???
and how can we graph prob 3??
THANKS ALOT

If you want to graph/visualize these solids of rotation, try the following website. Here you can actually choose which function you want to graph and how you want to rotate it!!

http://cs.jsu.edu/mcis/faculty/leathrum/Mathlets/rotsolid.html


linear algebra
matrix
algebra
polynomial
linear algebra unsolved

Suppose $ A_{11}$, $ A_{12}$, ..., $ A_{mm}$ are $ n\times n$ matrices that commute. Prove that the determinant of the block matrix $ \left(A_{ij}\right)_{1\leq i\leq m,\ 1\leq j\leq m}$ is $ \det\left(\sum_{\sigma\in S_m}{\epsilon\left(\sigma\right)\cdot A_{\sigma\left(1\right)1}A_{\sigma\left(2\right)2}...A_{\sigma\left(m\right) m}\right)}$.

I think this sketch of a proof should work for matrices with entries in any field $K$ (you didn't specify the field, so I assume this is what you meant? :?). We may assume that $K$ is algebraically closed.

Let $\mathcal A(A_{ij})$ be that large $mn\times mn$ block matrix, and let $D(A_{ij})$ be its formal determinant $\sum_{\sigma\in S_m}\varepsilon(\sigma)A_{1\sigma(1)}A_{2\sigma(2)}\ldots A_{m\sigma(m)}$. Suppose we manage to prove that

$(P)$: If $A_{ij}$ commute, $\mathcal A(A_{ij})$ is invertible iff $D(A_{ij})$ is invertible.

Then we could proceed as follows:

The determinant of $\mathcal A$ is the product of all those $\lambda\in K$ (counted with multiplicities) for which $\lambda I_{mn}-\mathcal A$ is not invertible. However, $\lambda I_{mn}-\mathcal A(A_{ij})$ is $-\mathcal A(A_{ij}(\lambda))$, where $A_{ij}(\lambda)$ equals $A_{ij}$ if $i\ne j$ and $A_{ij}-\lambda I_n$ if $i=j$. Now expand $D(A_{ij}(\lambda))$ as a polynomial in $\lambda$ with coefficients in $\mathcal M_n(K)$. The first coefficient is $(-1)^nI_n$, and the last coefficient is $D(A_{ij})$. We want to prove that the product of all those $\lambda$ (again, counted with multiplicities) for which this expression is not invertible is equal to the determinant of $D(A_{ij})$.

All the coefficients in the "polynomial" constructed above commute, so we can make them upper triangular simultaneously through a similarity (remember that $K$ is algebraically closed). We can see now that this expression in $\lambda$ is not invertible iff $\lambda$ verifies on of the $n$ polynomial expressions on the diagonal. These $n$ polynomials have $(-1)^n$ as leading terms, and the eigenvalues of $D(A_{ij})$ as free terms, so the product of all their roots, counted with multiplicities, is equal to the determinant of $D(A_{ij})$, which is exactly what we wanted to prove.

All that remains now is to prove $(P)$.

One direction is, I think, easier: Suppose $D(A_{ij})$ is invertible. Multiply $\mathcal A(A_{ij})$ with its "adjoint" $\mathcal A^*(A_{ij})$ to get an $mn\times mn$ block matrix with $n\times n$ blocks, the blocks on the main diagonal being $D(A_{ij})$, and those off the main diagonal being zero. If $D(A_{ij})$ is invertible then this matrix is invertible as well, i.e. $\mathcal A(A_{ij})\mathcal A^*(A_{ij})$ is invertible, and from this the conclusion that $\mathcal A(A_{ij})$ itself is invertible follows.

Conversely, assume that $\mathcal A(A_{ij})$ is invertible. In order to show that $D(A_{ij})$ is invertible, we should show that it has no eigenvectors. Instead of proving this for the general case and getting lost in notation, let's see what happens when $m=3$.

We have $\mathcal A=\begin{pmatrix}A_{11}& A_{12}& A_{13}\\A_{21}& A_{22}& A_{23}\\A_{31}& A_{32}& A_{33}\end{pmatrix}$. Let $f\in K^3$ such that $D(A_{ij})f=0$. It's then easy to check that $\mathcal A\begin{pmatrix}(A_{22}A_{33}-A_{23}A_{32})f\\(A_{23}A_{31}-A_{21}A_{33})f\\(A_{21}A_{32}-A_{22}A_{31})f\end{pmatrix}=0$, which means that $(A_{22}A_{33}-A_{23}A_{32})f=(A_{23}A_{31}-A_{21}A_{33})f=(A_{21}A_{32}-A_{22}A_{31})f=0\ (*)$, because $\mathcal A$ is invertible. In the same way we can prove that $(A_{ij}A_{kl}-A_{il}A_{kj})f=0$ for all $i,j,k,l\in\overline{1,3}$ with $i\ne k,\ j\ne l$, so in particular $(A_{12}A_{33}-A_{13}A_{32})f=0$. Together with the first relation from $(*)$, this shows that $\mathcal A\begin{pmatrix}0\\A_{33}f\\-A_{32}f\end{pmatrix}=0\Rightarrow A_{33}f=A_{32}f=0$. Again, in the same way, we can prove that $A_{ij}f=0,\ \forall i,j\in\overline{1,3}$, so $\mathcal A\begin{pmatrix}f\\0\\0\end{pmatrix}=0\Rightarrow f=0$. This is exactly what we wanted.

I hope it's Ok, but I bet nobody will read it, so even if it isn't, there's no problem there :P.

[quote="grobber"]
Multiply $\mathcal A(A_{ij})$ with its "adjoint" $\mathcal A^*(A_{ij})$ to get an $mn\times mn$ block matrix with $n\times n$ blocks, the blocks on the main diagonal being $D(A(_{ij})$, and those off the main diagonal being zero. [/quote]
Grobber, could you please explain this moment: why the product $\mathcal A(A_{ij})\mathcal A^*(A_{ij})$ should be diagonal blocked.

By "adjoint" I don't mean the usual conjugate transpose thingy, but rather [url=http://planetmath.org/encyclopedia/MatrixAdjoint.html]this[/url]. And it's not the usual adjoint of the $mn\times mn$ matrix $\mathcal A(A_{ij})$; it's the analogous of the adjoint if you treat the blocks of $\mathcal A$ as elements, and you view $\mathcal A$ as an $m\times m$ matrix.

For instance, if $m=2$, then $\mathcal A=\begin{pmatrix}A&B\\C&D\end{pmatrix}$, and its so-called adjoint that we use here is $\begin{pmatrix}D&-B\\-C&A\end{pmatrix}$. As you can easily check, when $A,B,C,D$ are pairwise commutative, the product of these two matrices is precisely $\begin{pmatrix}AD-BC&0\\0&AD-BC\end{pmatrix}$.


If $ x,y,z$ are positive reals such that $ xyz\equal{}1$ and
\[ \frac{1}{x}\plus{}\frac{1}{y}\plus{}\frac{1}{z} \ge x\plus{}y\plus{}z\]
Prove that
\[ \frac{1}{x^k}\plus{}\frac{1}{y^k}\plus{}\frac{1}{z^k} \ge x^k\plus{}y^k\plus{}z^k\]
For any positive integer $ k$

nice but easy,
we have $ \frac {1}{x} \plus{} \frac {1}{y} \plus{} \frac {1}{z}\geq x \plus{} y \plus{} z$
$ \Leftrightarrow xy \plus{} yz \plus{} zx\geq x \plus{} y \plus{} z$
$ \Leftrightarrow (1 \minus{} x)(1 \minus{} y)(1 \minus{} z)\geq 0$
using the formula $ a^k \minus{} 1 \equal{} (a \minus{} 1)(a^{k \minus{} 1} \plus{} ... \plus{} 1)$ we get,
$ (1 \minus{} x^k)(1 \minus{} y^k)(1 \minus{} z^k) \equal{} (1 \minus{} x)(1 \minus{} y)(1 \minus{} z)(x^{k \minus{} 1} \plus{} ... \plus{} 1)(y^{k \minus{} 1} \plus{} ... \plus{} 1)(z^{k \minus{} 1} \plus{} ... \plus{} 1)\geq 0$
$ \Leftrightarrow \frac {1}{x^k} \plus{} \frac {1}{y^k} \plus{} \frac {z^k} \geq x^k \plus{} y^k \plus{} z^k$
equality holds when $ x \equal{} 1$ or $ y \equal{} 1$ or $ z \equal{} 1$
using my solution we can also prove that, if $ x,y,z > 0$ and $ xyz \equal{} 1$ and $ \frac {1}{x} \plus{} \frac {1}{y} \plus{} \frac {1}{z}\leq x \plus{} y \plus{} z$
then $ \frac {1}{x^k} \plus{} \frac {1}{y^k} \plus{} \frac{1}{z^k} \leq x^k \plus{} y^k \plus{} z^k$ holds for all integer $ k$

can we assume that $ \frac{1}{x}>\equal{} x, \frac{1}{y}>\equal{}y,\frac{1}{z}.\equal{}z$.and then the inequality is trivial

[quote="aadil"]can we assume that $ \frac {1}{x} > \equal{} x, \frac {1}{y} > \equal{} y,\frac {1}{z}. \equal{} z$.and then the inequality is trivial[/quote]
No we cant.....

Because the thing you did is assuming $ x^2 <\equal{}1$, which is wrong, since $ x,y,z$ can be any numbers in $ R$ that satisfy $ xyz\equal{}1$.

Thanks peine, very nice...couldn't think of that... :lol:

Anyone for an induction approach?


geometry
circumcircle
incenter
geometry proposed

In a scalene triangle $ABC$ with $\angle A = 90^\circ,$ the tangent line at $A$ to its circumcircle meets line $BC$ at $M$ and the incircle touches $AC$ at $S$ and $AB$ at $R.$
The lines $RS$ and $BC$ intersect at $N,$ while the lines $AM$ and $SR$ intersect at $U.$
Prove that the triangle $UMN$ is isosceles.

In a triangle $ ABC$, where $ I$ is the incenter, and $ D,E,F$ the tangenty points of the incircle with $ BC,CA,AB$, and $ L \in BI \cap EF$, we have that $ BL \perp CL$. (A proof of this you can found in the begging of my proof of this problem: [url]http://www.mathlinks.ro/Forum/viewtopic.php?t=132338[/url])

Now we just consider $ V,W$ as the intersection points of $ RS$ with the circumcircle of $ ABC$. Then $ \widehat{AV} \equal{} \widehat{BV}$ and $ \widehat{AW} \equal{} \widehat{CW}$, and $ \angle{MNU} \equal{} \frac {\widehat{CW} \minus{} \widehat{BV}}{2}$ , and $ \angle{MUN} \equal{} \angle{AUS} \equal{} \frac {\widehat{AW} \minus{} \widehat{AV}}{2}$, thus $ MUN$ is isosceles.

we see angles MUN= AUR=ARS-RAU=ASR-ACB=SNC so triangle MUN is isosceless q.e.d

How showed nicely Huyen Vu, this problem is truly generally and $M\equiv N$ iff $b^{2}+c^{2}=a(b+c)$.

easy to get <SRA=45;let <ACB=a; then <ABC=90-a;then <UNM=90-a-45=45-a;<UMB=90-2a=2<UNM;Hence :<UNM=<NUM......Q.E.D.

This problem is true generally, i.e. for any value of $ A$ .  Prove easily that $ M\equiv N\Longleftrightarrow b^{2} \plus{} c^{2} \equal{} a(b \plus{} c)$ and
$ MB > NB\Longleftrightarrow b^2 \plus{} c^2 > a(b \plus{} c)$ . In both cases, $ m(\widehat{MUN}) \equal{} m(\widehat {MNU}) \equal{} \frac 12\cdot|B \minus{} C|$ (see [b][u]Huyền Vũ[/u][/b]).
[u]Otherwise[/u], if denote the diameter $ [AA']$ in the circumcircle $ C(O)$ of $ \triangle ABC$ and  $ T\in AA'\cap RS$ , then
observe that $ m(\widehat {AA'O})\equal{}\frac 12\cdot |B\minus{}C|$ and the quadrilaterals $ NTDA'$ , $ UASA'$ are cyclically a.s.o.


Given an interior point in an equilateral triangle minimize the inverse of the lengths from that point  to the three separate edges. So, calling this triangle ABC and the  point d, find the minimum of (1/(distance between d and  edge AB) + (1/distance between d and edge BC) + (1/distance between d  and edge AC).

[hide]Let $ E$, $ F$, and $ G$ the foots of the perpendiculars from $ D$ to $ BC$, $ AC$ and $ AB$.
Let the angles:
$ BDE \equal{} a$, $ BDG \equal{} b$, $ ADG \equal{} c$, $ ADF \equal{} d$, $ CDF \equal{} e$ and $ CDE \equal{} f$
So:
$ \frac {1}{DE} \plus{} \frac {1}{DF} \plus{} \frac {1}{DG} \equal{} \frac {tan a \plus{} tan b \plus{} tan c \plus{} tan d \plus{} tan e \plus{} tan f}{AB}$
And the function $ tan$ is convex in this interval $ (0^o \minus{} 90^o)$, then by Jensen inequality:
$ \frac {tan a \plus{} tan b \plus{} tan c \plus{} tan d \plus{} tan e \plus{} tan f}{AB}\geq \frac {6(tan \frac {a \plus{} b \plus{} c \plus{} d \plus{} e \plus{} f}{6})}{AB} \equal{} \frac {6\sqrt3}{AB}$
$ \frac {1}{DE} \plus{} \frac {1}{DF} \plus{} \frac {1}{DG}\geq\frac {6\sqrt3}{AB}$[/hide]

[hide="Alternate solution (hidden so you can try it yourself first):"]
Let $ a$ be the lengths of the sides of the equilateral triangle, and let $ P$ be the interior point under discussion. Let $ x$, $ y$, and $ z$ be the perpendicular distances from $ P$ to the sides $ AB$, $ BC$, and $ AC$ respectively. We want to minimize $ \frac {1}{x} \plus{} \frac {1}{y} \plus{} \frac {1}{z}$.

Notice that triangle ABC can be partitioned into triangles PAB, PBC, and PAC, the sum of whose areas is $ \frac {1}{2}ax \plus{} \frac {1}{2}ay \plus{} \frac {1}{2}az \equal{} \frac {a^2\sqrt {3}}{4}$. So $ x \plus{} y \plus{} z \equal{} \frac {a\sqrt {3}}{2}$.

By the Arithmetic-Geometric-Harmonic (AM-GM-HM) inequality, $ \frac {3}{\frac {1}{x} \plus{} \frac {1}{y} \plus{} \frac {1}{z}} \leq \sqrt [3]{xyz} \leq \frac {x \plus{} y \plus{} z}{3}$ with equality if and only if $ x \equal{} y \equal{} z$.

Rearranging this inequality gives $ \frac {1}{x} \plus{} \frac {1}{y} \plus{} \frac {1}{z} \geq \frac {3}{\sqrt [3]{xyz}} \geq \frac {9}{x \plus{} y \plus{} z} \equal{} \frac {6\sqrt {3}}{a}$, again with equality if and only if $ x \equal{} y \equal{} z$.

Therefore the sum of the distances is minimized when $ x \equal{} y \equal{} z$ and has a minimum value of $ \frac {6\sqrt {3}}{a}$[/hide]


This is a problem I thought of that deals with functional equations.
Let $ f$ be a function on odd natural numbers returning natural numbers. If $ f(n \plus{} 2) \equal{} f(n) \plus{} n$, and $ f(1)\equal{}0$ find $ f(n)$.

By the obvious pattern, f(2n+1) = $ n^2$  :)

we take $ a_n\equal{}f(2n\plus{}1)$
$ a_0\equal{}0$ and $ a_{n\plus{}1}\equal{}a_n\plus{}2n\plus{}1$ gives $ a_n\equal{}a_0\plus{}\sum_{j\equal{}0}^{n\minus{}1}a_{j\plus{}1}\minus{}a_j\equal{}\sum_{j\equal{}0}^{n\minus{}1}2j\plus{}1\equal{}n^2$
so $ f(n)\equal{}\frac{(n\minus{}1)^2}{4}$

[quote="madness"][quote="10000th User"][quote="Yongyi781"]First of all, $ 0$ is not a natural number, so $ f(1)$ can't return $ 0$ :P[/quote]That's a matter of definitions. I'm not going to start another already discussed topic about whether 0 is a natural number or not. For this problem, accept the fact that 0 is a natural number.[/quote]

0 isnt a natural number so the person who set the question shd probably mention N union {0}.[/quote]

Sorry, I also think that 0 is not a natural number. I ment 0 AND natural numbers, as you guys said.

The definition differs from country to country. It is obvious what the problem means.


What is the sum of all positive two-digit integers with exactly 12 positive factors?

$ 72$ and $ 60$ are the only two choices. (I think.)  So the answer is $ \boxed{132}$.  Anybody find more?

How do you quickly find the answer to this?

Just realized this is FTW, not alcumus lol, I don't think there is an easy way (most of these problems are taken directly from other tests, so they might not actually be countdown questions)

You could do cases, like using the number of factors trick
[url=http://tinyurl.com/yaazd3cu]~

Lots of OP people are OP at bashing like hi_im_bob

I got 60+72+84+9+96=402. I just used guess and check because I couldn't really find an easy way lol.


:!:  b.m.m e do adad 6 va k.m.m e unha 48 ast. majmoue an do adad chist?  :)

vaghti hasele jameshoon yekta bashe,oon 2 adad be soorate yekta moshakhas mishan,vali ba dashtane b.m.m va k.m.m nemitoonim 2 ada ro moshakhas konim. :roll:

k.m.m besoorate [a,b] va b.m.m besoorate (a,b) ast.
do adade motebayen besoorate (a',b')=1 darim va hasele k.m.m besoorate [a,b]=a'b'd. vaghti k.m.m va b.m.m ra darim mitoonim do adad ro moshakh'as konim:
[b]48=6a'b'  =>  a'b'=8  => b'>a'  =>  b'=8[/b] va [b]a'=1[/b]
va [b]a=a'd[/b] darim [b]a=6[/b] va [b]b=b'd[/b]darim [b]b=48[/b]   :oops:

$\text{lcm}(a,b)=48\wedge \gcd (a,b)=6$
agar $a=p_{1}^{\alpha_{1}}\hdots p_{m}^{\alpha_{m}}\wedge a=p_{1}^{\beta_{1}}\hdots p_{m}^{\beta_{m}}$, $\text{lcm}(a,b)\gcd (a,b)=\prod_{k=1}^{m}p_{k}^{\min (\alpha_{k},\beta_{k})+\max(\alpha_{k},\beta_{k})}=ab$.
Banabarin, $ab=\text{lcm}(a,b)\gcd (a,b)=48\cdot 6=(2\cdot 3)(2\cdot 3)2^{3}$. Chon $\text{lcm}(a,b)=48\wedge \gcd (a,b)=6$, $(a,b)=(48,6),(6,48)\implies a+b=54$.

Be nazar miyad ke dar Iran $\text{lcm}=\text{kmm}$ va $\gcd=\text{bmm}$.

az toozih va javabe kameletoon motshakeram  :)

estedlale khodam dorost tare :blush:  :lol:

esbate shoma ham kamelan doroste, makhsoosan touzihetoon harf nadare!  :lol:

maskhare mikoni?!
alan ke vaght nadaram vali badan kamelesho minevisam!!!!


Let f(0)=0,f(1)=1 and f(n+1)=f(n) + f(n-1) for n>=1.
Solve the equation in positive integers :
f(2n+1)=k^2.

Well, this is a challenge problem...
(I've first mentioned that f(12)=144 and then i was trying to find all n for which f(n)=k^2,I have managed to find an answer when n=2m+1,but not when n=2m,
so if someone solve the general argument f(n)=k^2, please post it.)

You may find some interest to read that :
http://www.mathlinks.ro/viewtopic.php?t=1423&highlight=fibonacci

Pierre.


trigonometry
calculus
calculus computations

How do you show that the parametric equations of this curve are:

$x = 2a \cot \theta$,  $y = 2a \sin^{2}\theta$ ?

Source: Stewart 5e, 10.1, #41

Thanks

Curves don't have a unique parameterization.

In this one, though, $\theta$ probably stands for the angle that the line that defines the curve makes, so it would be a good idea to work off of that.

For more information:

http://mathworld.wolfram.com/WitchofAgnesi.html


just wondering if any of you ever studied the subject of brain plasticity ? The subject seems to be trendy these days. They had a feature on it on Dan Rather report on HD Net. I also heard of the book The Brain that Changes Itself that seems to be a big hit also.

I haven't studied it wholly in a class or lesson, but I have read about neuroplasticity, brain growth, and brain development in a scientific book I purchased online.

[size=75][b][u]Welcome to Your Brain: Why you Lose your Car Keys but Never Forget How to Drive and Other Puzzles of Everyday Life.[/u]Sandra Aamodt, Ph.D and Sam Wang, Ph.D.[/b][/size]

Part III of the book if you want to skip ahead to the subject of neuroplasticity. The examples given are quite thorough, and anyone interested in subject will enjoy it.

-arb95.


cam grea problema asta
am mari dubii asupra corectitudinii solutiei pe care o voi da, dar totusi o voi posta :)
imi ramane doar sa sper ca veti avea rabdarea sa cititi solutia mea, si sa`mi spuneti daca e corecta sau nu. eu sper ca este, desi ma indoiesc :)
[hide="solutie"]pentru inceput, voi introduce niste notatii si conventii :
$S$=suma din enunt.
consider si ca $|z_{k}|=1$ si ca punctele apar in ordinea fireasca pe cercul unitate, si ca $z_{1}=1$. (este permis, deoarece "simplific" prin $z_{1}$ toate fractiile).
se observa ca :
$\bigg|\frac{z_{i}+z_{j}}{z_{i}-z_{j}}\bigg|^{2}=\frac{4}{|z_{i}-z_{j}|^{2}}-1$.
deci daca $S$ este minima atunci si $S'=\sum \frac{1}{|z_{i}-z_{j}|^{2}}$ este minima.
o voi studia pe $S'$.
$a_{ij}=\frac{1}{|z_{i}-z_{j}|^{2}}$.
$S_{k}=\sum_{cyc}a_{i,k+i}$, pentru $1\leq k\leq [n/2]$. (unde indicii sunt modulo $n$ iar termenii nu se repeta (adica cei care au mai fost intalniti deja nu se mai iau si a doua oara, $a_{ij}$ se considera identic cu $a_{ji}$ adica este numarat o singura data)).
se observa pentru inceput ca :
$\sum_{k=1}^{[n/2]}S_{k}=S$, deoarece fiecare pereche din $S$ apare exact in una din sumele $S_{k}$, si exact o singura data.
sumele $S_{k}$ vor fi descompuse la randul lor in "cicluri" :
un ciclu are forma
$h,\ k+h,\ 2k+h,\ \ldots$.
primul ciclu incepe cu $h=1$. al doilea ciclu, daca exista, incepe cu $h$`ul minim (care nu a aparut in ciclurile de mai sus)
voi da un exemplu complet pentru $n=6$ :
$S_{1}=\big(a_{12}+a_{23}+a_{34}+a_{45}+a_{56}+a_{61}\big)$. (un singur ciclu)
$S_{2}=\big(a_{13}+a_{35}+a_{51}\big)+\big(a_{24}+a_{46}+a_{62}\big)$. (doua cicluri)
$S_{3}=\big(a_{14}\big)+\big(a_{25}\big)+\big(a_{36}\big)$. (trei cicluri . observatie : nu am introdus si $a_{41}$ deoarece am introdus deja $a_{14}$).
revenind la problema, fie un ciclu oarecare. voi studia in ce conditii suma dintre termenii acelui ciclu este minima. voi presupune ca ciclul are chiar lungime $n$ (este irelevant ce lungime are sau care ciclu anume este ales, dar prefer asa pentru a nu mai introduce notatii).
suma cautata este
$Q=\sum_{i=1}^{n}\frac{1}{|z_{i}-z_{i+1}|^{2}}$.
privind,in "poligonul" $A_{1}A_{2}\ldots A_{n}$, inscris in cercul unitate, pot scrie  (observatie : acesta nu este neaparat un poligon, ci mai degraba o linie franta inchisa (care se autointersecteaza sau nu). pentru $n=5$, ciclul generat de $k=2$ este o stea. in orice caz, pasii demonstratiei raman valabili, deci in continuare cand ma refer la poligon, inteleg si astfel de figuri)
$Q=\sum_{i=1}^{n}\frac{1}{A_{i}A_{i+1}^{2}}$.
fie $q_{i}$ unghiul dintre $OA_{i}$ si $OA_{i+1}$, $q_{i}\in(0,2\pi)$. (observatie, poligonul considerat poate sa fie doar un segment, si atunci unghiul este chiar $\pi$, si unghiul poate fi mai mare decat $\pi$ deoarece este orientat)
observatie : $\sum q_{i}$ este un multiplu intreg de $2\pi$, si este fix pentru un ciclu dat, deoarece depinde doar de ordinea in care sunt luate punctele. deoarece am considerat un ciclu arbitrar, pot spune ca $\sum q_{i}=R=\mbox{constant}$.
$A_{i}A_{i+1}=2\sin (q_{i}/2)$.
deci $Q=2\sum\sin (q_{i}/2)$.
fie $W=Q/2$ si $w_{i}=q_{i}/2$. deoarece este vorba doar de coeficienti, voi continua studiind doar suma $W$.
fie functia $f(x)=\frac{1}{\sin^{2}x}$, $f: (0,\pi)\rightarrow\mathbb{R}$.
$f$ este continua pe $(0,\pi)$ si
$f''(x)=\frac{3\sin^{2}x-2\sin^{4}x}{\sin^{6}x}\geq 0$, deci $f$ este convexa.
deoarece $w_{i}\in(0,\pi)$, rezulta ca :
$W=\sum f(w_{i})\geq n\cdot f\bigg(\frac{\sum w_{i}}{n}\bigg)=n\cdot f(R/2n)$.
deci $W$ este minima atunci cand $w_{i}$ sunt egale, adica poligonul este regulat (sau segmentul este diametru).
chiar daca ciclul ales a fost arbitrar, observatia de mai sus imi permite sa afirm ca minimul lui $S'$ se atinge atunci cand $z_{i}$ sunt radacinile de ordinul $n$ ale unitatii. intr`adevar : voi nota cu indicele $0$ sumele corespunzatoare acestui caz, si in rest aceleasi notatii. deoarece in acest caz, pentru [b]orice[/b] ciclu ales, $w_{i}$`urile corespunzatoare sunt egale, pot spune ca pentru orice ciclu are loc $W\geq W_{0}$, deci $Q\geq Q_{0}$, $S_{k}\geq S{}_{k}{}_{0}$ si $S'\geq S'_{0}$. faptul acesta rezulta din constructia ciclurilor. daca punctele sunt radacinile de ordinul $n$ ale unitatii, atunci poligonul este regulat, iar ciclurile "mai mici" sunt poligoane regulate cu varfurile printre varfurile poligonului mare.
rezulta ca minimul sumei se atinge atunci cand $z_{i}$ sunt radacinile de ordinul $n$ ale unitatii.
mai ramane de calculat $S_{0}$ in acest caz :
$S_{0}=\sum_{i<j}\frac{|u_{i}+u_{j}|^{2}}{|u_{i}-u_{j}|^{2}}=\frac{|1+u^{j-i}|^{2}}{|1-u^{j-i}|^{2}}$,
adica
$S_{0}=\sum_{k=1}^{n-1}\frac{(n-k)\cdot|1+u^{k}|^{2}}{|1-u^{k}|^{2}}$.
pentru $n=3$ obtinem chiar estimarea din ipoteza.
pentru $n=4$ obtinem $S_{0}=4$, si deci $S\geq 4$.
in orice caz, $S\geq S_{0}$.
insumand convenabil termenii din $S_{0}$ (profitand de faptul ca $u$ a fost ales arbitrar dintre cele $n-1$ radacini ale unitatii (diferite de $1$)), se obtine :
$S_{0}=\sum_{k=1}^{n-1}\frac{n-k}{n-1}\bigg(\sum_{u}\frac{|1+u|^{2}}{|1-u|^{2}}\bigg)=\frac{n}{2}\bigg(\sum_{k=1}^{n-1}\frac{|1+u^{k}|^{2}}{|1-u^{k}|^{2}}\bigg)$.
cand $n$ este par lucrurile ies frumos, deoarece termenul din mijloc este $0$, si daca $n=2p$, avem $\frac{|1+u^{p+k}|}{|1-u^{p+k}|}=\frac{|1-u^{k}|}{|1+u^{k}|}$ si se aplica inegalitatea mediilor, obtinandu`se $S_{0}\geq \frac{n}{2}\cdot 2(p-1)=\frac{n(n-2)}{2}$.
cand $n$ este impar nu am mai cautat sa gasesc o aproximare doar in functie de $n$. e de calculat o suma de functii trigonometrice si nu stau deloc bine cu rabdarea pentru asa ceva :)
oricum, aproximarile doar in functie de $n$ sunt mai slabe, deoarece in inegalitatea mediilor de exemplu, egalitatea se atinge doar pt $n=4$.
$S_{0}$ calculat mai sus ramane cea mai buna valoare din membrul drept.[/hide]

[quote="maky"]$\bigg|\frac{z_{i}+z_{j}}{z_{i}-z_{j}}\bigg|^{2}=\frac{2}{|z_{i}-z_{j}|^{2}}-1$.[/quote]
O prima observatie: cred ca in loc de $2$-ul de la numaratorul fractiei din membrul drept trebuie $4$. Mai citesc in continuare.

ups :) sunt neatent, ca de obicei...am corectat acum

Pentru maky. Pare corecta (dar incompleta) solutia ta (eu nu am gasit nici o hiba!).
Se poate folosi urmatoarea:
[color=blue]Lema[/color]
Daca $z_{1}, z_{2}, ..., z_{n}\in\mathbb{C}$ si $|z_{1}|=|z_{2}|=...=|z_{n}|=R$, atunci \[S_{n}=\sum_{1\leq i<j\leq n}|z_{i}-z_{j}|^{2}\leq R^{2}n^{2}.\] [hide="Solutia lemei."]Tinand cont ca $|z_{1}|=|z_{2}|=...=|z_{n}|=R$, avem \[z_{1}\cdot\overline{z_{1}}=z_{2}\cdot\overline{z_{2}}=...=z_{n}\cdot\overline{z_{n}}=R^{2}.\] Atunci \[S_{n}=\sum_{1\leq i<j\leq n}(z_{i}-z_{j})(\overline{z_{i}}-\overline{z_{j}})=R^{2}n(n-1)-T_{n},\] unde \[T_{n}=\sum_{1\leq i<j\leq n}(z_{i}\cdot\overline{z_{j}}+\overline{z_{i}}\cdot z_{j}).\] E suficient sa aratam ca $T_{n}\geq-nR^{2}.$
Intr-adevar, \[T_{n}=z_{1}(\overline{z_{1}}+\overline{z_{2}}+...+\overline{z_{n}})+z_{2}(\overline{z_{1}}+\overline{z_{2}}+...+\overline{z_{n}})+...+z_{n}(\overline{z_{1}}+\overline{z_{2}}+...+\overline{z_{n}})-R^{2}n=\]  \[=(z_{1}+z_{2}+...z_{n})\overline{(z_{1}+z_{2}+...+z_{n})}-R^{2}n=|z_{1}+z_{2}+...+z_{n}|^{2}-nR^{2}\geq-R^{2}n.\] In concluzie, $S_{n}\leq R^{2}n(n-1)+R^{2}n=R^{2}n^{2}$ si lema este demonstrata. [/hide]
[hide="Observatie."]Daca mai folosim si inegalitatea mediilor, solutia problemei rezulta imediat.[/hide]

am revenit
sper ca n`am busit aproximarile astea
[hide="continuare"]aveam
$S_{0}=\frac{n}{2}\Bigg(\sum_{k=1}^{n-1}\frac{|1+u^{k}|^{2}}{|1-u^{k}|^{2}}\Bigg)$.
pentru $n$ par problema a fost demonstrata, si anume :
$S\geq \frac{n(n-2)}{2}$.
fie $n$ impar.
atunci, voi calcula :
$T=\sum_{k=1}^{n-1}\frac{|1+u^{k}|^{2}}{|1-u^{k}|^{2}}$.
deci $2S_{0}=nT$.
evident,
$T\geq \frac{|1+u|^{2}}{|1-u|^{2}}+\frac{|1+u^{n-1}|^{2}}{|1-u^{n-1}|^{2}}=2\cdot\frac{|1+u|^{2}}{|1-u|^{2}}$, unde pe $u$ il alegem chiar $\cos \frac{2\pi}{n}+i\,\sin\frac{2\pi}{n}$.
egalitatea se atinge doar cand $n=3$. (clar)
$\frac{|1+u|^{2}}{|1-u|^{2}}=\frac{4}{|1-u|^{2}}-1=\frac{1}{\sin^{2}\frac{\pi}{n}}-1$.
pentru $n=3$, obtin :
$T=2\cdot\bigg(\frac{4}{3}-1\bigg)=\frac{2}{3}$, iar $S_{0}=\frac{3}{2}\cdot\frac{2}{3}=1$, deci se obtine chiar inegalitatea dorita si anume $S\geq S_{0}=1$.
pentru $n\geq 5$, folosesc inegalitatea $\sin x<x$ :
$\sin^{2}\frac{\pi}{n}<\frac{\pi^{2}}{n^{2}}$,
deci $T>2\cdot\bigg(\frac{n^{2}}{\pi^{2}}-1\bigg)$.
adica $S_{0}>n\bigg(\frac{n^{2}}{\pi^{2}}-1\bigg)$,
adica $S_{0}>\frac{n(n^{2}-\pi^{2})}{\pi^{2}}$.
voi arata ca
$\frac{n(n^{2}-\pi^{2})}{\pi^{2}}>\frac{n(n-2)}{2}$ (*)
(*) este echivalent cu :
$2n^{3}-2n\pi^{2}=n^{2}\pi^{2}-2n\pi^{2}$, sau
$n^{2}(2n-\pi^{2})>0$.
cum $\pi^{2}<10$, iar $n\geq5$, rezulta ca (**) este adevarata.
deci am demonstrat problema si pentru $n$ impar.
observatii :
am demonstrat ca pentru $n\geq 4$, are loc inegalitatea
$S\geq \frac{n(n-2)}{2}$, cu egalitate pt $n=4$.
nu am folosit ca $n$ este impar in demonstratie (decat ca sa presupun $n\geq 5$).
deci pt $n\geq 5$,
$S_{0}\geq\frac{n(n^{2}-\pi^{2})}{\pi^{2}}$. (***)
voi nota cu $x_{n}$ valoarea lui $S_{0}$ ca functie de $n$ : de exemplu $x_{3}=1$, $x_{4}=4$, etc...
conform (***) :
$\lim_{n\rightarrow\infty}\frac{x_{n}}{n^{2}}=+\infty$,
si
$\lim_{n\rightarrow\infty}\frac{x_{n}}{n^{3}}\geq 1$,
deci aproximarea (***) este mult mai tare decat cea din ipoteza. (insa exista altele mai tari cred, deoarece am renuntat la multi termeni acolo).[/hide]

[hide="Estimand in continuare"]
In cazul unui poligon regulat, suma ar trebui sa arate cam asa: \[M =-\frac{n(n-1)}2+\sum_{k=1}^{n-1}\frac{n-k}{\sin^{2}\left( \frac{k \pi}{n}\right)}=-\frac{n(n-1)}2+S_{1337}.\] Folosind inegalitatea mentionata de maky mai sus ($x > \sin x$), obtinem
\begin{eqnarray*}S_{1337}&>& \frac{n^{2}}{\pi^{2}}\sum_{k=1}^{n-1}\frac{n-k}{k^{2}}\\ \ &=& \frac{n^{2}}{\pi^{2}}\left( n \sum_{k=1}^{n-1}\frac1{k^{2}}-\sum_{k=1}^{n-1}\frac1{k}\right) \\ \ &\approx& \frac{n^{2}}{\pi^{2}}\left( n \frac{\pi^{2}}6-\left( \ln(n-1)+\gamma \right) \right) \\ \ &=& \frac{n^{3}}6-\frac{n^{2}}{\pi^{2}}\left( \ln(n-1)+\gamma \right) ,\end{eqnarray*}
unde $\gamma$ este constanta Euler-Mascheroni, deci \[M > \frac{n^{3}}6-\frac{n^{2}}{\pi^{2}}\left( \ln(n-1)+\gamma+\frac12 \right)+\frac{n}2 .\] (ultima inegalitate inseamna ca $M > f(n)$, unde $\lim_{n \to \infty}\left( f(n)-\left[ \frac{n^{3}}6-\frac{n^{2}}{\pi^{2}}\left( \ln(n-1)+\gamma+\frac12 \right)+\frac{n}2 \right] \right) = 0$.)
Se pot face si estimari mai bune: impartim suma-n doua $1 \to \left\lfloor \frac{n-1}2 \right\rfloor$ si $\left\lfloor \frac{n-1}2 \right\rfloor+1 \to n-1$, dupa care folosim identitatea $\sin \left( \pi-x \right) = \sin x$ pentru termenii din $\left\lfloor \frac{n-1}2 \right\rfloor+1 \to n-1$.

Pentru o majorare a acestei sume, cred ca s-ar putea folosi $\sin x > x-\frac{x^{3}}6$, dar iese foarte urat.

PS: Nu stiu daca se poate calcula exact aceasta suma.
[/hide]

olioooo... :)
cred ca se pot gasi o groaza de aproximari din ce in ce mai bune in felu asta :) insa nici eu nu cred ca se poate calcula...problema deschisa :D