function
number theory
number theory unsolved

find all function $ f: \mathbb{N} \to \mathbb{N}$,such that $ \forall a,b,c,d \in\mathbb{N}$:
$ f(a)f(b)f(c)f(d)\equal{}f(a^2\plus{}b^2\plus{}c^2\plus{}d^2)$

I'm assuming that $ \mathbb{N} \equal{} \{1, 2, 3, \ldots\}$. If $ 0$ is counted as a natural number, the problem is even easier.

[hide="(possible beginning of a ) solution"]
First, we have

$ f(4) \equal{} f(1^2 \plus{} 1^2 \plus{} 1^2 \plus{} 1^2) \equal{} f(1)^4$

$ f(7) \equal{} f(2^2 \plus{} 1^2 \plus{} 1^2 \plus{} 1^2) \equal{} f(1)^3 f(2)$

$ f(10) \equal{} f(2^2 \plus{} 2^2 \plus{} 1^2 \plus{} 1^2) \equal{} f(1)^2 f(2)^2$.

Now, noting that $ 28 \equal{} 25 \plus{} 1 \plus{} 1 \plus{} 1 \equal{} 16 \plus{} 4 \plus{} 4 \plus{} 4 \equal{} 9 \plus{} 9 \plus{} 9 \plus{} 1$ we get

$ f(3) \equal{} f(1) f(2)$ and

$ f(5) \equal{} f(1) f(2)^3$.

Next, $ 34 \equal{} 25 \plus{} 4 \plus{} 4 \plus{} 1 \equal{} 16 \plus{} 16 \plus{} 1 \plus{} 1$ so we must have

(*) $ f(2)^5 \equal{} f(1)^8$

while from $ 60 \equal{} 49 \plus{} 9 \plus{} 1 \plus{} 1 \equal{} 36 \plus{} 16 \plus{} 4 \plus{} 4$ we find

$ f(6) \equal{} f(1)^2$.

So far so good, but $ 112 \equal{} 100 \plus{} 4 \plus{} 4 \plus{} 4 \equal{} 36 \plus{} 36 \plus{} 36 \plus{} 4$ now implies

$ f(10) f(2)^3 \equal{} f(1)^2 f(2)^5 \equal{} f(1)^{10} \equal{} f(6)^3 f(2) \equal{} f(1)^6 f(2)$ so

$ f(2) \equal{} f(1)^4$

which together with (*) implies $ f(1) \equal{} 1$.

[i]If there is any number $ m$ such that $ f(m) > 1$, we let $ m$ be the smallest such number, but then we find $ a,b,c,d$ with $ m \equal{} a^2 \plus{} b^2 \plus{} c^2 \plus{} d^2$ (always possible, by the four squares theorem) from which $ f(m) \equal{} f(a)f(b)f(c)f(d)$ forces $ f(m) \equal{} 1$ since $ a,b,c,d$ are all strictly less than $ m$. This contradiction implies that $ f(m) \equal{} 1$ for all natural numbers, and this is the only possible function.[/i]

EDIT: this last step is obviously wrong, as some numbers cannot be written as the sum of four positive squares. Will update when I've fixed this.
[/hide]

very nice work RANDOMGRAFH.yes $ \mathbb{N}\equal{}\{1,2,...\}$
but I think the end of solution is not correct,can you find $ a,b,c,d\in\mathbb{N}$ for $ m\equal{}3,5,6,8,9$?obviously you can not...
by four squares theorem we find $ a,b,c,d\in\mathbb{Z}$...and maybe some of them be zero.
is there a stornger version for four squares theorem?

Bleah. You're right. I confused myself by working on the case with 0 first. Back to the drawing board....

Ok, I got it, but it's not as elementary as I would have liked. The solution below relies on the known formula for the number of representations of $ N$ as a sum of four squares. This formula is (or should be) well known, but it's certainly not elementary and I wouldn't expect an Olympiad problem to rely on it. Therefore I expect there's a more elegant solution than the one I present below.

ali666, is this an olympiad problem?

Anyway, here's the fact we need. Let $ r_4(N)$ be the number of solutions to

$ N \equal{} x_1^2 \plus{} x_2^2 \plus{} x_3^2 \plus{} x_4^2$

where by "number of solutions" we count as distinct any two different 4-tuples $ (x_1,x_2,x_3,x_4)$. Note that this implies that, for instance, $ 32 \equal{} 4^2 \plus{} 4^2$ counts as 24 different solutions (6 to place the 0's and 4's, 4 to choose signs, as in $ 32 \equal{} 0^2 \plus{} 4^2 \plus{} ( \minus{} 4)^2 \plus{} 0^2$). A classical theorem of number theory (see, for instance, Hardy and Wright) says that

$ r_4(N) \equal{} 8 \sum_{d|N, 4 \not \mid d} d$

in words, add up all the divisors of $ N$ except for those which are multiples of 4, and multiply by $ 8$. This is the number of representations!

[hide="Complete solution"]
We first show that $ f(m) \equal{} 1$ for $ m \leq 4$. We do this as above, but for completeness here's a quick recap:

$ 4 \equal{} 1^2 \plus{} 1^2 \plus{} 1^2 \plus{} 1^2$ implies $ f(4) \equal{} f(1)^4$
$ 7 \equal{} 2^2 \plus{} 1^2 \plus{} 1^2 \plus{} 1^2$ implies $ f(7) \equal{} f(1)^3f(2)$
$ 10 \equal{} 2^2 \plus{} 2^2 \plus{} 1^2 \plus{} 1^2$ implies $ f(10) \equal{} f(1)^2 f(2)^2$
$ 28 \equal{} 3^2 \plus{} 3^2 \plus{} 3^2 \plus{} 1^2 \equal{} 4^2 \plus{} 2^2 \plus{} 2^2 \plus{} 2^2$ implies $ f(3) \equal{} f(1) f(2)$
$ 28 \equal{} 5^2 \plus{} 1^2 \plus{} 1^2 \plus{} 1^2 \equal{} 4^2 \plus{} 2^2 \plus{} 2^2 \plus{} 2^2$ implies $ f(5) \equal{} f(1) f(2)^3$
$ 34 \equal{} 5^2 \plus{} 2^2 \plus{} 2^2 \plus{} 1^2 \equal{} 4^2 \plus{} 4^2 \plus{} 1^2 \plus{} 1^2$ implies $ f(2)^5 \equal{} f(1)^8$ (*)
$ 60 \equal{} 7^2 \plus{} 3^2 \plus{} 1^2 \plus{} 1^2 \equal{} 6^2 \plus{} 4^2 \plus{} 2^2 \plus{} 2^2$ implies $ f(6) \equal{} f(1)^2$
$ 112 \equal{} 10^2 \plus{} 2^2 \plus{} 2^2 \plus{} 2^2 \equal{} 6^2 \plus{} 6^2 \plus{} 6^2 \plus{} 2^2$ implies, after substituting some of the above, that $ f(2) \equal{} f(1)^4$ which together with (*) forces

$ f(1) \equal{} f(2) \equal{} f(3) \equal{} f(4) \equal{} 1$.

Our next task is to reduce all other natural numbers to these known values. To this end, let's say that a number $ m$ is [b]reducible[/b] if for some $ x,y,z,a,b,c,d$ we have

$ m^2 \plus{} x^2 \plus{} y^2 \plus{} z^2 \equal{} a^2 \plus{} b^2 \plus{} c^2 \plus{} d^2$ with $ 0 < a,b,c,d < m$.

The point of this definition is that if $ m$ is reducible and we already know that $ f(k) \equal{} 1$ for $ k < m$, then $ f(m) \equal{} 1$ as well because $ f(m)f(x)f(y)f(z) \equal{} f(a)f(b)f(c)f(d) \equal{} 1$ forces $ f(m) \equal{} 1$.

[b]Step 1.[/b] Every odd $ m$, $ m \geq 5$ is reducible.

To see this, consider

$ N \equal{} m^2 \plus{} 2^2 \plus{} 1^2 \plus{} 1^2$

Note that $ N \equiv 7 \bmod 8$ since every odd square is congruent to 1 modulo 8. Therefore $ N$ is [b]not[/b] a sum of 3 integer squares (reason: all squares are congruent to 0, 1 or 4 modulo 8, and three of these never add up to 7).

The representation of $ N$ as $ m^2 \plus{} 4 \plus{} 1 \plus{} 1$ yields 192 distinct representations in the sense explained above (we can rearrange the terms in 12 ways, and choose signs in 16 ways). However, since $ m \geq 5$ we have $ N \geq 31$, and since $ N$ is odd the sum of the divisors of $ N$ which are not multiples of 4 is at least 32. By the theorem on the number of representations, $ N$ has at least 256 representations so it must have at least one representation

$ N \equal{} a^2 \plus{} b^2 \plus{} c^2 \plus{} d^2$

which is different from $ m^2 \plus{} 4 \plus{} 1 \plus{} 1$. Moreover, all of $ a,b,c,d$ are positive ($ N$ is not a sum of 3 squares), and they are all less than $ m$. To see this last assertion, Note that if $ a \equal{} m$ than $ N \minus{} a^2$ is 6 which can only be written as a sum of 3 squares as $ 6 \equal{} 4 \plus{} 1 \plus{} 1$. Furthermore, if $ a > m$ than $ a^2 \geq m^2 \plus{} 2m \plus{} 1 \geq m^2 \plus{} 11$, contradiction.

Therefore, $ N \equal{} m^2 \plus{} 2^2 \plus{} 1 \plus{} 1 \equal{} a^2 \plus{} b^2 \plus{} c^2 \plus{} d^2$ with $ 0 < a,b,c,d < m$ and so $ m$ is reducible, QED.

[b]Step 2.[/b] If $ m$ is reducible, so is $ 2m$.

This is trivial: just multiply $ m^2 \plus{} x^2 \plus{} y^2 \plus{} z^2 \equal{} a^2 \plus{} b^2 \plus{} c^2 \plus{} d^2$ by 4 to obtain $ (2m)^2 \plus{} (2x)^2 \plus{} (2y)^2 \plus{} (2z)^2 \equal{} (2a)^2 \plus{} (2b)^2 \plus{} (2c)^2 \plus{} (2d)^2$ and it is clear that $ 0 < 2a, 2b, 2c, 2d < 2m$ so $ 2m$ is reducible.

[b]Step 3.[/b] Every $ m$ greater than 5 is reducible.

First, we note that 6 and 8 are reducible:

$ 6^2 \plus{} 1^2 \plus{} 1^2 \plus{} 1^2 \equal{} 5^2 \plus{} 3^2 \plus{} 2^2 \plus{} 1^2$

$ 8^2 \plus{} 4^2 \plus{} 4^2 \plus{} 4^2 \equal{} 6^2 \plus{} 6^2 \plus{} 6^2 \plus{} 2^2$

Finally, every integer $ m$ can be written as $ m \equal{} 2^k n$ with $ n$ odd. If $ n \geq 5$ then $ n$ is reducible by step 1 and so $ m$ is reducible by iterating step 2. If $ n \equal{} 3$ and $ m$ is $ \geq 5$ then $ k > 0$ so we have $ m \equal{} 2^{k \minus{} 1} \times 6$ and again $ m$ is reducible. Finally, if $ n \equal{} 1$ then $ m \equal{} 2^k$ and if $ m \geq 5$ we have $ m \equal{} 2^{k \minus{} 3} \times 8$, showing once more that $ m$ is reducible.

That's it! To formally prove that $ f(m) \equal{} 1$ for all $ m$, assume the contrary and let $ m$ be smallest natural number for which $ f(m) \neq 1$. We cannot have $ m \equal{} 1, 2, 3, 4$ by what we showed in the beginning, so $ m$ must be reducible. Therefore there are $ x,y,z,a,b,c,d$ with

$ m^2 \plus{} x^2 \plus{} y^2 \plus{} z^2 \equal{} a^2 \plus{} b^2 \plus{} c^2 \plus{} d^2$ and $ 0 < a,b,c,d < m$. From the minimality of $ m$ it follows that $ f(a) \equal{} f(b) \equal{} f(c) \equal{} f(d) \equal{} 1$ so $ f(m) \equal{} 1$, too. QED

[/hide]

thanks a lot [b]randomgraph[/b]  :D
yes,it is an an olympiad problem,I found this problem in a persian book which collected some olympiad problems...so I think there exist more elementary solution...anyway your solution is very nice... :first:


calculus
integration
function
logarithms
derivative
rotation
complex analysis

Evaluate $ \int_{\gamma} \sqrt {z} dz$ where $ \gamma$ is the upper half of the unit circle.

I contend that this problem does not make sense because they did not tell us specifically what branch of the complex square root function to use. Am I right?

Usually if they don't specify, you take the "principal" branch. There's a conventional default for just this reason. If you really want to be precise, check what the integral would be for any branch (I wouldn't be surprised if in this case it's actually the same, by the way; however, I didn't check).

Taking the principal branch doesn't make sense because the path hits -1 otherwise I would have assumed that also. As there are an infinite number of branches, how can I prove that I have found what the integral will be for any branch?

OK $ \sqrt{z} \equal{} e^{\frac{1}{2}\log(z)}$ and take an arbitrary branch of log whose bad line is not in the region of integration. Is that ok? Am I missing something?

Can you prove that the integral is independent of the branch of the logarithm that you take though?

Actually, I'm sorry -- there's only one 'branch' of square root which is the "right" choice here. You must take the principal branch of logarithm. If you try to do it in the lower half plane, the jump (in log) occurs at $ \theta \equal{} \minus{}\phi$ and $ 2\pi \minus{} \phi$, and then you will have a problem (with sqrt) at $ z \equal{} e^{i(\pi \minus{} \phi/2)}$. It's not true that there's a problem because the path "hits" -1, as that's the end of the path, and when you're integrating, a single point doesn't matter.

If you choose the other branch, it just negates the whole integral.

You can parametrize, or just take the antiderivative.

First write it out as a multi-expression:

\begin{align*} \sqrt {z} & = Exp[1/2\log(z)] \\
& = Exp[1/2(ln(r) + i(\Theta + 2k\pi))];\quad k = 0,1 \end{align*}

Then look at the real and imaginary multi-sheets for this function I posted where I've color-coded the principal branch red, and the secondary branch blue.  That's it.  That's all the sheeting going on with square root, just two.  Now I can segregate each multi-sheet into separate non-overlapping sheets by choosing the branch cut anywhere.  Suppose I segregate them (make a branch cut) along the negative real axis.  Certainly as shown, that would make two non-overlapping real sheets and two imaginary sheets corresponding to two single-valued functions.  That's what the principal branch and the secondary branch is.  In terms of the multi-expression above, that would correspond to:

$ S_1(z) = Exp[1/2(ln(r) + i\Theta)];\quad - \pi < \Theta\leq \pi$

$ S_2(z) = Exp[1/2(ln(r) + i(\Theta + 2\pi))] = - S_1(z);\quad - \pi < \Theta\leq \pi$

Now can integrate either of them by parameterizing the contour:

$ \mathop\int\limits_{C} S_1(z)dz = \int_{0}^{\pi} e^{i\theta/2}i e^{i\theta}d\theta = 2/3(e^{3\pi i/2} - 1)$

$ \mathop\int\limits_{C} S_2(z)dz = - 2/3(e^{3\pi i/2} - 1)$

Now, if I wished, I could use anti-derivates but then I need to segregate the sheets so that the contour does not pass through (or touch) the cut because then the integration path would no longer be going through regions in which the function was analytic.  That's easy.  How about these two:

$ S_a(z) = Exp[1/2(ln(r) + i\Theta)];\quad - \pi/2 < \Theta\leq 3\pi/2$

$ S_b(z) = Exp[1/2(ln(r) + i(\Theta + 2\pi))] = - S_a(z);\quad - \pi/2 < \Theta\leq 3\pi/2$

Now the contour passes through a region in which both $ S_a$ and $ S_b$ are analytic so I can take anti-derivatives:

$ \mathop\int\limits_{C} P_a(z)dz = 2/3z^{3/2}\Biggr\vert_{1}^{ - 1} = 2/3(e^{3\pi i/2} - 1)$

$ \mathop\int\limits_{C} P_b(z)dz = - 2/3(e^{3\pi i/2} - 1)$

Alright, now make the cut somewhere along the contour like the positive imaginary axis:

$ \mathop\int\limits_{C} z^{1/2}dz;\quad z^{1/2} = Exp[1/2(ln(r) + i\Theta)];\quad \pi/2 < \Theta\leq5\pi/2$

No problem there also, just integrate individually over each separate piece of the multi-sheet.  Can't use anti-derivative though in this case since now the contour passes through the cut, that is, need to parameterize it.

[correction]

Can still use anti-derivatives even if the contour passes through the branch-cut.  In that case, just break up the integration over branches which are contiguous.  So in the case of the cut along the positive imaginary axis and the contour $ C$, the upper unit half circle:

$ \mathop\int\limits_{C} z^{1/2}dz;\quad z^{1/2} = Exp[1/2(ln(r) + i\Theta)],\quad \pi/2 < \Theta\leq 5\pi/2$

\begin{align*} \mathop\int\limits_{C} z^{1/2}dz & = \int_{i}^{ - 1}z^{1/2}dz;\quad z^{1/2} = Exp[1/2(ln(r) + i\Theta)];\quad 0 < \Theta\leq 2\pi \\
& + \int_{1}^{i}z^{1/2}dz;\quad z^{1/2} = Exp[1/2(ln(r) + i\Theta)];\quad \pi < \Theta\leq 3\pi \\
& = 2/3(e^{3\pi i/2} - e^{3\pi i/4}) + 2/3(e^{15\pi i/4} + 1) \\
\end{align*}

[edit] correct typos

This is kind of interesting:  I've plotted contours for the case of the branch-cut along the positive imaginary axis.   In that case:

\begin{align*}
\mathop\int\limits_{C} z^{1/2}dz &;\quad z^{1/2}=Exp[1/2(ln(r)+i\Theta)];\quad \pi/2<\Theta\leq 5\pi/2 \\
&= \mathop\int\limits_{Green} z^{1/2}dz+\mathop\int\limits_{Yellow} z^{1/2}dz
\end{align*}

How about this then:  In terms of anti-derivatives, what is the value of the integral as a function of the angle of the branch-cut?

$ f(\omega)=\mathop\int\limits_{C}z^{1/2}dz;\quad z^{1/2}=Exp[1/2(ln(r)+i\Theta)];\quad \omega<\Theta\leq \omega+2\pi$

where $ C$ is the same upper half unit circle.

Just havin' a lil' fun that's all.

Were those plots generated with Mathematica? If so, can you post the code that you used?

Here's the Mathematica ver 6 code.  It's in input form so I can cut and paste it.
Hope you have ver 6.  That gives you interactive 3D graphic capabilities and can rotate them with the mouse.  If you want, once you cut and paste it into Mathematica, convert it to standard form to look better.

[code]
(* principal branch*)
f1[z_] := E^((1/2)*(Log[Abs[z]] + I*Arg[z]));
(* secondary branch *)
f2[z_] := E^((1/2)*(Log[Abs[z]] + I*(Arg[z] + 2*Pi)));

(* compare anti-derivatives to numerical results *)
i1 = NIntegrate[f1[z]*I*E^(I*t) /. z -> E^(I*t),
       {t, Pi/2, Pi}];
i2 = NIntegrate[f2[z]*I*E^(I*t) /. z -> E^(I*t),
       {t, 0, Pi/2}];
i1 + i2
N[(2/3)*(E^((3*Pi*I)/2) - E^((3*Pi*I)/4)) +
     (2/3)*(E^((15*Pi*I)/4) + 1)]

(* plot real surfaces *)
p1 = ParametricPlot3D[{Re[z], Im[z], Re[f1[z]]} /.
       z -> r*E^(I*t), {r, 0, 1}, {t, -Pi, Pi},
     PlotStyle -> Red]
p2 = ParametricPlot3D[{Re[z], Im[z], Re[f2[z]]} /.
       z -> r*E^(I*t), {r, 0, 1}, {t, -Pi, Pi},
     PlotStyle -> Blue]

(* trace on real sheets *)
trace1 = ParametricPlot3D[{Re[z], Im[z], Re[f2[z]]} /.
         z -> E^(I*t), {t, 0, Pi/2}, PlotStyle ->
         {Thickness[0.03], Yellow}];
trace2 = ParametricPlot3D[{Re[z], Im[z], Re[f1[z]]} /.
         z -> E^(I*t), {t, Pi/2, Pi}, PlotStyle ->
         {Thickness[0.03], Green}];
psum1 = Show[{p1, p2, trace1, trace2}, PlotRange -> All,
     PlotLabel -> Real*Surface]

(* plot imaginary sheets*)
p3 = ParametricPlot3D[{Re[z], Im[z], Im[f1[z]]} /.
       z -> r*E^(I*t), {r, 0, 1}, {t, -Pi, Pi},
     PlotStyle -> {Red}]
p4 = ParametricPlot3D[{Re[z], Im[z], Im[f2[z]]} /.
       z -> r*E^(I*t), {r, 0, 1}, {t, -Pi, Pi},
     PlotStyle -> {Blue}]

(* trace on imaginary sheets *)
trace3 = ParametricPlot3D[{Re[z], Im[z], Im[f2[z]]} /.
         z -> E^(I*t), {t, 0, Pi/2}, PlotStyle ->
         {Thickness[0.03], Yellow}];
trace4 = ParametricPlot3D[{Re[z], Im[z], Im[f1[z]]} /.
         z -> E^(I*t), {t, Pi/2, Pi}, PlotStyle ->
         {Thickness[0.03], Green}];
psum2 = Show[{p3, p4, trace3, trace4}, PlotRange -> All,
     PlotLabel -> Imaginary*Surface]
GraphicsGrid[{{psum1, psum2}}]
[/code]

[quote="shawtoos"]First write it out as a multi-expression:

\begin{align*} \sqrt {z} & = Exp[1/2\log(z)] \\
& = Exp[1/2(ln(r) + i(\Theta + 2k\pi))];\quad k = 0,1 \end{align*}

Then look at the real and imaginary multi-sheets for this function I posted where I've color-coded the principal branch red, and the secondary branch blue.  That's it.  That's all the sheeting going on with square root, just two.  Now I can segregate each multi-sheet into separate non-overlapping sheets by choosing the branch cut anywhere.  Suppose I segregate them (make a branch cut) along the negative real axis.  Certainly as shown, that would make two non-overlapping real sheets and two imaginary sheets corresponding to two single-valued functions.  That's what the principal branch and the secondary branch is.  In terms of the multi-expression above, that would correspond to:

$ S_1(z) = Exp[1/2(ln(r) + i\Theta)];\quad - \pi < \Theta\leq \pi$

$ S_2(z) = Exp[1/2(ln(r) + i(\Theta + 2\pi))] = - S_1(z);\quad - \pi < \Theta\leq \pi$

Now can integrate either of them by parameterizing the contour:

$ \mathop\int\limits_{C} S_1(z)dz = \int_{0}^{\pi} e^{i\theta/2}i e^{i\theta}d\theta = 2/3(e^{3\pi i/2} - 1)$

$ \mathop\int\limits_{C} S_2(z)dz = - 2/3(e^{3\pi i/2} - 1)$

Now, if I wished, I could use anti-derivates but then I need to segregate the sheets so that the contour does not pass through (or touch) the cut because then the integration path would no longer be going through regions in which the function was analytic.  That's easy.  How about these two:

$ S_a(z) = Exp[1/2(ln(r) + i\Theta)];\quad - \pi/2 < \Theta\leq 3\pi/2$

$ S_b(z) = Exp[1/2(ln(r) + i(\Theta + 2\pi))] = - S_a(z);\quad - \pi/2 < \Theta\leq 3\pi/2$

Now the contour passes through a region in which both $ S_a$ and $ S_b$ are analytic so I can take anti-derivatives:

$ \mathop\int\limits_{C} P_a(z)dz = 2/3z^{3/2}\Biggr\vert_{1}^{ - 1} = 2/3(e^{3\pi i/2} - 1)$

$ \mathop\int\limits_{C} P_b(z)dz = - 2/3(e^{3\pi i/2} - 1)$

Alright, now make the cut somewhere along the contour like the positive imaginary axis:

$ \mathop\int\limits_{C} z^{1/2}dz;\quad z^{1/2} = Exp[1/2(ln(r) + i\Theta)];\quad \pi/2 < \Theta\leq5\pi/2$

[/quote]

So, if I understand you correctly, the question is ambiguous since you come out with different answers when you use the principal and the secondary branches. But I am still kind of confused about why there are only two branches. It seems like at whatever angle you choose to take out a ray, you get a different branch because the restrictions on $ \theta$ are unique. Furthermore, it seems like you get a choice of two unique branches for every angle because you can always add $ 2 \pi$ to $ \theta$.

The sheeting overlaps once in the square root multi-sheet (Riemann surfaces I plotted above).  Therefore for each value of $ z=x+iy$ corresponding to some point in the x-y plane of the multi-sheet, there will be two values for $ f(z)=\sqrt{z}$. This of course is a consequence of the definition: $ z^{1/2}=Exp[1/2(ln(r)+i(\Theta+2k\pi)];k=0,1$.
We arbitrarily segregate the sheeting into two single-valued (and analytic) components representing two "branches'' of the square root multi-function.  We do this to take advantage of all the trappings granted to analytic functions.  We can segregate the multi-sheet anyway desired even cut it up like the spokes on a bicycle tire, alternating the choice of the sheet to use for each segment.

What though is the minimum amount of segregating, the ``simplest'' way to define single-valued components of this multi-sheet that would yield the largest contiguous and analytic regions?  Well, that would be just a single "cut'', a single line emanating from the origin and going outward:  this segregates the multi-sheet into two single-valued branches having only one line of discontinuity and thus only one location, the line, where they are not analytic. By convention, we usually make this cut along the negative real axis with the ``principal'' branch having argument $ -\pi<\Theta\leq \pi$ but that is only arbitrary:

Suppose we are given the ambiguous assignment (professors do that sometimes you know to make us think):

Express the integral of $ \sqrt{z}$ over the upper half unit circle ($ C^{+})$, using anti-derivatives.

Two questions need to be addressed:

(1)  Which sheet of the multi-sheet is the integration being performed over?
(2) Assuming only one cut, at what angle $ \omega$ is this (straight line) cut made with respect to the real axis?

In order to use anti-derivatives, segregate the contour into sections, then define analytic branches (determinations) for the square root so that each section of the contour lies completely inside the respective branches.  We can then evaluate the integral over each section by using the anti-derivative of the branch which contains it.

If the branch-cut is in the lower half-plane, then we can define determinations which completely encompass the contour and thus the integral for each sheet is a single anti-derivative from $ 1$ to $ -1$.  The integral over each sheet is given as $ S_1$ and $ S_2$ below. Determinations for the selected sheets are given as the expressions for $ z^{1/2}$.

\begin{align*}
S_1=\mathop\int\limits_{C^{+}} z^{1/2}dz &=\int_1^{-1}z^{1/2}dz;\quad z^{1/2}=Exp[1/2(ln(r)+i\Theta)];\quad -\pi/2<\Theta\leq 3\pi/2 \\
&=2/3(e^{3\pi i/2}-1)
\end{align*}

\begin{align*}
S_2=\mathop\int\limits_{C^{+}} z^{1/2}dz &=\int_1^{-1}z^{1/2}dz;\quad z^{1/2}=Exp[1/2(ln(r)+i\Theta)];\quad 3\pi/2<\Theta\leq 7\pi/2 \\
&=2/3(e^{9\pi i/2}+1)=-S_1
\end{align*}

If the cut is in the upper half-plane or on the real axis, then the integral is a function of the branch-cut:  We define analytic branches which (fully) encompass the contour piece-wise as necessary and take the corresponding anti-derivatives:

Letting $ 0\leq\omega\leq \pi$, then:

\begin{align*}
S_1(\omega)=\mathop\int\limits_{C^{+}} z^{1/2}dz &=\int_{e^{\omega i}}^{-1} z^{1/2}dz;\quad z^{1/2}=Exp[1/2(ln(r)+i\Theta)];\quad -\pi/2<\Theta\leq 3\pi/2 \\
&+\int_{1}^{e^{\omega i}} z^{1/2}dz;\quad z^{1/2}=Exp[1/2(ln(r)+i\Theta)];\quad \pi<\Theta\leq 3\pi \\
&=2/3(e^{3\pi i/2}-e^{3\omega i/2})+2/3(e^{3(2\pi+\omega)i/2}+1)
\end{align*}

\begin{align*}
S_2(\omega)=\mathop\int\limits_{C^{+}} z^{1/2}dz &=\int_{e^{\omega i}}^{-1} z^{1/2}dz;\quad z^{1/2}=Exp[1/2(ln(r)+i\Theta)];\quad 3\pi/2<\Theta\leq 7\pi/2 \\
&+\int_{1}^{e^{\omega i}} z^{1/2}dz;\quad z^{1/2}=Exp[1/2(ln(r)+i\Theta)];\quad 3\pi<\Theta\leq 5\pi \\
&=2/3(e^{9\pi i/2}-e^{3/2(2\pi+\omega)i})+2/3(e^{3/2(4\pi+\omega)i}-1)
\end{align*}

I'm stunned that nobody has pointed out that, by convention, $ \sqrt{1} \equal{} 1$, not $ \minus{} 1$.  So I don't find the integral particularly ambiguous. (though I would clearly point out the assumption if you are submitting the solution)


geometry
ratio
quadratics
algebra
quadratic formula

Look at the triangles 12-18-27 and 8-12-18.  They have 5 pairs of congreunt parts (two sides and 3 angles).  If we have two right triangles that have 5 pairs of congruent parts, what is the hypotenuse divided by the shorter side in one of these triangles?

seems to be 2.25
its just 27/12 and 18/8

From the CAML right? I took it as well.

Let one triangle have short leg $ x$ and hypotenuse $ rx$ ($ r$ being the ratio of the hypotenuse to the leg). It's pretty clear that 3 of the 5 congruent parts are the angles, so we have a couple of similar right triangles. The third leg of the right triangle is $ \sqrt{r^2x^2\minus{}x^2}\equal{}\sqrt{x^2(r^2\minus{}1)}\equal{}x\sqrt{r^2\minus{}1}$.

In our other triangle, let the longer leg be $ rx$ and the short leg $ x\sqrt{r^2\minus{}1}$ so that the hypotenuse is $ \sqrt{r^2x^2\plus{}x^2(r^2\minus{}1)}\equal{}\sqrt{r^2x^2\plus{}r^2x^2\minus{}x^2}\equal{}x\sqrt{2r^2\minus{}1}$.

By our similar triangle ratios, we have $ \frac{x\sqrt{2r^2\minus{}1}}{rx}\equal{}\frac{x\sqrt{r^2\minus{}1}}{x}\implies \sqrt{2r^2\minus{}1}\equal{}r\sqrt{r^2\minus{}1}$
Then:
$ 2r^2\minus{}1\equal{}r^2(r^2\minus{}1)$
$ 2r^2\minus{}1\equal{}r^4\minus{}r^2$
$ r^4\minus{}3r^2\plus{}1\equal{}0$
$ (r^2\plus{}r\minus{}1)(r^2\minus{}r\minus{}1)\equal{}0$

$ r^2\plus{}r\minus{}1\equal{}0$ gives a negative value for $ r$, so we consider $ r^2\minus{}r\minus{}1\equal{}0$.

Quadratic formula: $ r\equal{}\frac{1\pm\sqrt{5}}{2}$. If the numerator is $ 1\minus{}\sqrt{5}$ then $ r<1$ and $ rx<x$, which is clearly not true, so we conclude that $ \boxed{r\equal{}\frac{1\plus{}\sqrt{5}}{2}\equal{}\phi}$ (yes, the golden ratio).

@Nandubetax: The given triangles are NOT right triangles, just random triangles (AIME15 forgot to mention that), so those ratios don't work... I suspect the CAML people gave those specific examples with equal ratios to throw people off.

Thanks!

I let the short leg be $ a$ and the hypotenuse be $ b$...that's probably what threw me off.


vector
function
calculus
derivative
linear algebra
matrix

I know that a set of vector functions ${\vec{v_{1}}(t), \vec{v_{2}}(t)+...+\vec{v_{n}}(t)}$ in a vector space $\mathbb{V}$ if $c_{i}= 0$ for the following equation:

$c_{1}\vec{v_{1}}(t)+c_{2}\vec{v_{2}}(t)+...+c_{n}\vec{v_{n}}(t) \equiv \vec{0}$

Where does the Wronskian come into play? Is it basically a determinant with functions and derivatives?

Thanks

[quote="ragingbullrocky"]Where does the Wronskian come into play?[/quote]
It comes next after a linear differential equation.

I think you're thinking of linear dependence vs linear independence. If you have a set $\{v_{1}, v_{2}, ... , v_{n}\}$. Then the wronskian:

$\text{det}\left(\begin{matrix}v_{1}& v_{2}& ... & v_{n}\\ v'_{1}& v'_{2}& ... & v'_{n}\\ . & . & ... & . \\ v^{(n-1)}_{1}& v^{(n-1)}_{2}& ... & v^{(n-1)}_{n}\\ \end{matrix}\right)$

is either always zero or never zero (on some interval). If it is always zero then the set is linearly dependent and if it is never zero then it is linearly independent. It's been awhile, so I may be missing some conditions or something.

Here a more direct way to see it. Start with the homogeneous linear differential equation

$y^{[n]}+p_{n-1}(t)y^{[n-1]}+\cdots+p_{1}(t)y'+p_{0}(t)y=0$

where $p_{0},p_{1},\dots p_{n-1}$ are continuous on some interval $(a,b).$ Now suppose we have found $n$ functions $v_{1}(t),v_{2}(t),\dots v_{n}(t)$ each of which is a solution to the differential equation.

We now know that any arbitrary linear combination of these functions, that is

$v(t)=c_{1}v_{1}(t)+c_{2}v_{2}(t)+\cdot+c_{n}v_{n}(t)$

is a solution of the differential equation. So now the question is this: have we found all solutions of this differential equation? To answer this, we turn to the existence-uniqueness theorem for differential equations. Given $t_{0}\in(a,b)$ and a set of initial conditions $y(t_{0})=a_{0},y'(t_{0})=a_{1},\dots y^{[n-1]}(t_{0})=a_{n-1},$ there is some neighborhood of $t_{0}$ such that there exists exactly one solution to the differential equation on that interval.

That gives us a simple way to tell whether or not we can find a solution that meets any possible initial conditions at $t_{0}.$ Attempting to solve for those initial conditions, we get the linear system:

$\begin{bmatrix}v_{1}&v_{2}&\cdots&v_{n}\\ v_{1}'&v_{2}'&\cdots&v_{n}'\\ \vdots&\vdots&\ddots&\vdots\\ v_{1}^{[n-1]}&v_{2}^{[n-1]}&\cdots&v_{n}^{[n-1]}\end{bmatrix}\begin{bmatrix}c_{1}\\ c_{2}\\ \vdots\\ c_{n}\end{bmatrix}= \begin{bmatrix}a_{0}\\ a_{1}\\ \vdots\\ a_{n-1}\end{bmatrix}$

This has a unique solution for any possible right hand side precisely when the determinant of the matrix on the left - the Wronskian - is nonzero.

Then there is a differential equations computation that can be made. (HilbertThm90 alluded to this.) If $W(t)=W(v_{1},v_{2},\dots,v_{n})(t)$ is the Wronskian, then $W'(t)+p_{n-1}(t)W(t)=0.$ This first-order ODE also obeys the existence uniqueness theorem: if it is ever zero on $(a,b),$ then it is always zero. Hence if it is ever nonzero, then it is always nonzero. The set $\{v_{1},v_{2},\dots,v_{n}\}$ is a basis for the solution space precisely when the Wronskian is nozero.

The key theorem that drives all of this is the existence-uniqueness theorem. I have told a differential equations class "There is only one theorem in this course." I was only half joking.


complex analysis
real analysis
real analysis unsolved

If we know $ x \equal{} y e ^y$, how do we prove

$ y \equal{} \sum_{n \equal{} 1}^\infty \frac {( \minus{} 1)^{n \minus{} 1} n^{n \minus{} 1}}{n!} x^n$

?

Is there a general procedure to find the inverse of power series?

2) Yes, there is; see http://en.wikipedia.org/wiki/Lagrange_inversion_theorem

Is there any special idea for the proof? I've tried to prove it with a=b=0 and i couldn't do it.

The main idea is to use complex analysis :lol: Here is a sketch of a derivation of this formula. Assume wlog $ a=b=0$. Let $ g(z) = \sum_{n=1}^{\infty} a_n z^n$. Then
\begin{align*}
a_n &= \mathrm{Res}_0\left(\frac{g'(z)}{nz^n}\right) = \frac{1}{2\pi i} \oint \frac{g'(z)dz}{n z^n} = \frac{1}{n} \cdot \frac{1}{2\pi i} \oint \frac{dw}{f(w)^n} \\ &= \frac{\mathrm{Res}(\frac{1}{f(w)^n} )}{n} = \frac{1}{n}\cdot \frac{1}{(n-1)!} \frac{d^{n-1}}{dw^{n-1}} \left(\frac{w^n}{f(w)^n}\right).
\end{align*}

The Lagrange inversion theorem does have a purely combinatorial proof based on a generalization of a certain "cycling" argument for computing the Catalan numbers.


are there any good books out there to improve chess strategy. i want to learn all the famous opening moves, checkmate moves, etc.  :)

Improve your Opening play...forgot the author but you can look at it


probability
function
number theory
prime factorization
prime numbers
number theory unsolved

I don't know if this is the correct place to post this, but I am curious what others have to say about something I am stuck on.  I was thinking about simple ways to evaluate how likely a number is to be prime in my head.  While thinking about this, I encountered a contradiction which must have resulted from an error.  But where did I go wrong?

[b]Background info that you most-likely know:[/b]
*If a number ends with 5 it is divisible by 5
*If a number ends with an even number or 0 it is even
*If a number ends with 1,3,7, or 9 then it is not divisible by 5 or 2 (the first and third prime)
*If the sum of the digits of a number is divisible by 3, then the number is divisible by 3 (ie 10350111 is divisible by 3 because 1+0+3+5+0+1+1+1=12 and 12/3=4)
*All numbers can be represented by a distinct set of prime factors (ie 144 = 2*2*2*2*3*3 and 105=3*5*7).  I have adopted the convention of writing them from least to greatest, so if it starts with 5 that means it has no 2s or 3s and is divisible by neither.

[b]Therefore, if a number ends in 1, 3, 7, or 9 and the sum of its digits is not divisible by 3, it is not divisible by 2, 3, or 5... and therefore its smallest possible factor is 7.[/b]  This makes it easier to test for primality and it's easy to do it in your head.  If a number from 1 to 1000 passes this test there is a 63% chance it is prime.  If a number from 1 to 10 million passes this test, there is very nearly a 25% chance it is prime.
---------------------------------------------------------------------------

[b]Now I began to look at what fraction of numbers end in 1,3,7, or 9 and are not divisible by 3.[/b]

[1]well 1, 3, 7, and 9 are 4 of 10 digits and therefore 4/10 of numbers end with one of these.  1/3 of numbers are divisible by 3 and numbers ending in each digit (0-9) have an equal chance of being divisible by 3 because it cycles (3,6,9,12,15,18,21,24,27,30,... making the cycle of last digits 3 6 9 2 5 8 1 4 7 0 repeat).  Therefore 1-1/3=2/3 of numbers are NOT divisible by 3.  SO in conclusion, the fraction of numbers that end with digits 1, 3, 7, or 9 and are NOT divisible by 3 is 4/10 * 2/3 = [b]4/15[/b].  This has been confirmed experimentally on my computer up to 100 million.

[2]Now I decide I want to instead find the fraction of numbers whose prime factorization begins with 7 or greater.  This should be the same answer right? (as 2, 3, and 5 are the only primes below 7).  The portion of numbers that start with 2 in their prime factorization are the even numbers (1/2).  The portion that start with 3 are the numbers divisible by 3 (1/3) but not 2 so 1-1/2-x=1/3, x = 1/6.  So 1/6 of numbers start with 3 in their prime factorization.  What about 5?  1-1/2-1/6-x=1/5, x = 2/15.  Therefore all numbers that DON'T start with 2, 3, or 5 in their prime factorization represent 1-1/2-1/6-2/15=[b]1/5[/b].  This means the first prime factor the number could have is 7.

[b][u]So why, then, did i get 4/15 with my first approach and 1/5 with my second???[/b][/u]  This is a 1/15 difference.  Where is my mistake?

Ok, first, a very beautiful theorem about prime numbers, called the Prime Number Theorem, gives us some great relations about primality.  Here is a link:

http://en.wikipedia.org/wiki/Prime_number_theorem

Also, it has been shown that given some random positive integer $ n$, there is a $ \frac{1}{ln\hspace n}$ probability that it is prime.  If you are interested in learning about primality testing, there is a ton of literature out there, and I would recommend you take a look at it.  There are some remarkable facts about primes that can be derived from very little heavy machinery.

Secondly, as for your ideas, in your second approach you merely are counting wrong.  If you want to count how big sets are, you need to use the Inclusion-Exclusion Principle.  If a set $ X$ consists of $ n$ consecutive integers (and for simplicity suppose $ n$ is divisible by $ 30$), then the number of elements in $ X$ divisible by $ 2,3,$ or $ 5$ is

$ \frac{n}{2}+\frac{n}{3}+\frac{n}{5}-(\frac{n}{6}+\frac{n}{10}+\frac{n}{15})+\frac{n}{30}=\frac{11n}{15}$.

So the amount of numbers not divisible by a $ 2,3$ or $ 5$ is $ \frac{4n}{15}$.

Ah thanks!  I assumed my first solution was the correct one since I had verified it extensively (experimentally).  Where did I go wrong in my second approach though?  I proved somewhere (I'd have to look around to find my notes) that the probability that a number starts with $ P_{n}$ (the nth prime) in its prime factorization (given that the factors are written in order from least to greatest) is $ \frac{P_{n}-P_{n-1}}{P_{n}*P_{n-1}}$ allowing $ 1$ to be prime for the case where $ P_{n}=2$.  Is this incorrect then?

[quote] The portion that start with 3 are the numbers divisible by 3 (1/3) but not 2 so 1-1/2-x=1/3, x = 1/6. So 1/6 of numbers start with 3 in their prime factorization. What about 5? 1-1/2-1/6-x=1/5, x = 2/15.[/quote]

You have an easy error in this calculations. You wrote that number of natural integers which starts with 3 in their prime factorization is 1-1/2-x=1/3, so x=1-1/2-1/3, and for 5 it's 1-1/2-1/6-x=1/5, so x=1-1/2-1/6-1/5. You should write it in another way. 1-1/2=1/2 is a number of integers which starts with 2 in their PF(prime factorization), so also 1/2 doesn't start and [b]from them[/b] 1/3 starts with 3 like in a chain:
1 [b]3[/b] 5 7 [b]9[/b] 11 13 [b]15[/b] ...
In general this number is 1/3 of 1/2 which equals to 1/6.
Then for five it's 1/5*(1-1/2-1/6)=1/15. So number of integers which doesn't starts with 2,3 or 5 i their PF is 1-1/2-1/6-1/15 which equals to 4/15. I completely don't understand why you used formula 1-1/2-1/6-1/5=x for 5. You could write it in this form 1-1/2-1/6-4/5(1-1/2-1/6)=1/15.
I found an easy formula to find how much of numbers starts with pn in PF.

(1-1/2)(1-1/3)(1-1/5)(1-1/7)*.....*1/pn

where 2,3,5,7,...,pn is set of following primes from 2 to n-th prime. And formula telling us how much of numbers starts with prime greater when pn in their PF:

(1-1/2)(1-1/3)(1-1/5)(1-1/7)*.....*(1-1/pn)
In the last post you should receive:
1/2*2/3*4/5*6/7=8/35
You make a mistake: 1-27/35 is not a 7/35, but 8/35.

[quote]
I found an easy formula to find how much of numbers starts with pn in PF.

(1-1/2)(1-1/3)(1-1/5)(1-1/7)*.....*1/pn

where 2,3,5,7,...,pn is set of following primes from 2 to n-th prime. And formula telling us how much of numbers starts with prime greater when pn in their PF:

(1-1/2)(1-1/3)(1-1/5)(1-1/7)*.....*(1-1/pn)[/quote]
This can't be true,
$ (1-\frac{1}{2})*(1-\frac{1}{3})=\frac{1}{3}$

I think what you mean is that the portion of numbers that are divisible by $ P_{0}$, $ P_{1}$, $ P_{2}$, ... , $ P_{n-1}$, or $ P_{n}$ is  $ 1-\prod_{p: prime}^{P_{n}}\((1-\frac{1}{p})$

So the portion of numbers that start with $ P_{n}$ in their prime factorization should be $ \prod_{p: prime}^{P_{n-1}}\((1-\frac{1}{p})-\prod_{p: prime}^{P_{n}}\((1-\frac{1}{p})$ ,  correct?

I honestly don't remember where I came up with that subtraction method... I think I justified it through experimentation (with Java) with numbers through about 1 million and didn't spend the time to really think about how valid it was.  Unfortunately both methods have the correct answers for the first two fractions ($ 1/2$ and $ 1/6$) so perhaps I was just being careless.

[quote]
In the last post you should receive:
1/2*2/3*4/5*6/7=8/35
You make a mistake: 1-27/35 is not a 7/35, but 8/35.[/quote]
Yes :P $ 15-7=8$ not $ 7$ thanks.

[quote]This can't be true,
(1-\frac{1}{2})*(1-\frac{1}{3})=\frac{1}{3} [/quote]
Why?
1/2 starts with 2, 1/6 with 6 so 1-1/2-1/6=1/3 starts with number greater then 3 in prime factorization. This formula is not for calculations how much numbers starts with pn in PF! For this is the upper formula:

(1-1/2)(1-1/3)(1-1/5)(1-1/7)*.....*1/pn ,
so
(1-1/2)*1/3=1/6

[quote="fen"]
Why?
1/2 starts with 2, 1/6 with 6 so 1-1/2-1/6=1/3 starts with number greater then 3 in prime factorization. This formula is not for calculations how much numbers starts with pn in PF! For this is the upper formula:

(1-1/2)(1-1/3)(1-1/5)(1-1/7)*.....*1/pn ,
so
(1-1/2)*1/3=1/6[/quote]

Ah so you're saying that the formula for the portion of numbers that start with $ P_{n}$ in their PF is $ \frac{1}{P_{n}}\prod_{p: prime}^{P_{n-1}}\((1-\frac{1}{p})$ which happens to be equivalent to $ \prod_{p: prime}^{P_{n-1}}\((1-\frac{1}{p})-\prod_{p: prime}^{P_{n}}\((1-\frac{1}{p})$.  Your formula is factored and more compact.

For any curious people, $ P_{n}$: $ \frac{1}{P_{n}}\prod_{p: prime}^{P_{n-1}}\((1-\frac{1}{p})$

$ 2$: $ \frac{1}{2}$
$ 3$: $ \frac{1}{6}$
$ 5$: $ \frac{1}{15}$
$ 7$: $ \frac{4}{105}$
$ 11$: $ \frac{8}{385}$
$ 13$: $ \frac{16}{1001}$
$ 17$: $ \frac{192}{17017}$
$ 19$: $ \frac{3072}{323323}$
$ 23$: $ \frac{55296}{7436429}$
$ 29$: $ \frac{110592}{19605131}$
$ 31$: $ \frac{442368}{86822723}$
$ ...$

[quote]the portion of numbers that are divisible by $ P_{0}$, $ P_{1}$, $ P_{2}$, ... , $ P_{n-1}$, or $ P_{n}$ is  $ 1-\prod_{p: prime}^{P_{n}}\((1-\frac{1}{p})$[/quote]

If this is true, couldn't it be combined with the Sieve of Eratosthenes to approximate $ \pi(x)$ (the prime counting function)?

The formula would look like this (i think): $ \pi(x)$ $ \approx$ $ x-x\prod_{p: prime}^{P_{n}<\sqrt{x}}\((1-\frac{1}{p})+\pi(\sqrt{x})$

For the record, the actual $ \pi(10^{6})$ is $ 78498$ while this formula yields $ \approx81133.26351$ with $ x=10^{6}$
How do I account for the error?

EDIT: [quote]the actual $ \pi(10^{6})$ is $ 78498$ while this formula yields $ \approx81133.26351$ with $ x=10^{6}$[/quote] is correct when plugged into:

$ \pi(x)$ $ \approx$ $ x-(x-x\prod_{p: prime}^{P_{n}<\sqrt{x}}\((1-\frac{1}{p}))+\pi(\sqrt{x})$
$ \pi(x)$ $ \approx$ $ x\prod_{p: prime}^{P_{n}<\sqrt{x}}\((1-\frac{1}{p})+\pi(\sqrt{x})$

The other formula yields the "non-prime counting function" heh I guess I just posted the wrong formula.  I still can't account for the error though.

[quote="Xombie"]EDIT: $ \pi(x)$ $ \approx$ $ x\prod_{p: prime}^{P_{n}<\sqrt{x}}\((1-\frac{1}{p})+\pi(\sqrt{x})$

The other formula yields the "non-prime counting function" heh I guess I just posted the wrong formula.  I still can't account for the error though.[/quote]
It is not true (discussed in russian forum). Mertens formul $ \prod_{p<N}(1-\frac{1}{p})=\frac{e^{-\gamma}}{lnN}(1+o(1))$.
But $ \pi(x)=\frac{x}{ln x}(1+o(1))\not = \frac{x2e^{-\gamma}}{lnx}(1+o(1))$.


A game is played with a special fair cubic die which has one red side, two blue sides, and three green sides. The result is the color of the top side after the die has been rolled. Whip and Ward play a game in which they alternate rolls. Whip has the first roll. The game continues until two consecutive red results are obtained. The player who rolls the second of the consecutive reds wins. Find the probability that Ward wins the game.

[hide]
For all rolls except the first one, there was a 1/6 probability that the previous roll was red.
So on any given roll, the probability of winning is 1/36 except for the first roll in whcih it is 0.
Since the first roll has no chance of winning, in effect Ward goes first. Since Ward goes first, Ward is 36/35 times more likely than Whip to win, so the probabiltiy of Ward winning is 1/(1+35/36) or 36/71.
[/hide]


trigonometry
calculus
calculus computations

$ 1 \plus{} \frac {x^{3}}{3!} \plus{} \frac {x^{6}}{6!} \plus{} \frac {x^{9}}{9!} \plus{} \cdots$

http://www.mathlinks.ro/viewtopic.php?t=179254
To kunny: Send for me  link of  the   the problem. Thanks

That reminds of me an old Putnam.

[url]http://www.mathlinks.ro/Forum/viewtopic.php?p=1411663#1411663[/url]

In what relation are exactly your series and the answer?! One is a Taylor expansion (depends on $ x$) and the other is a constant!?

Just solve the corresponding differential equation with initial conditions:
\[ u''' \equal{} u \\
u(0) \equal{} 1 \\
u'(0) \equal{} u''(0) \equal{} 0\]
By the usual method (look for solutions of the form $ e^{rx}$ ), we get $ u(x) \equal{} \sum_{k \equal{} 1}^3 c_k e^{r_k x}$ where $ \lbrace r_k\rbrace$ are the roots of $ r^3 \equal{} 1$.  Solve the linear system for $ \lbrace c_k\rbrace$:
\[ \sum_{k \equal{} 1}^3 c_k \equal{} 1 \\
\sum_{k \equal{} 1}^3 c_k r_k \equal{} \sum_{k \equal{} 1}^3 c_k r_k^2 \equal{} 0\]
and we're done.

[hide="comes out to:"]$ c_1 \equal{} c_2 \equal{} c_3 \equal{} \frac {1}{3}$, $ u(x) \equal{} \frac {1}{3}e^x \plus{} \frac {2}{3}e^{ \minus{} \frac {x}{2}}\left[\cos \left(\frac {\sqrt {3}}{2}x\right) \plus{} \sin\left(\frac {\sqrt {3}}{2}x\right)\right]$[/hide]


Consider the metric space ([0, 1], | · |).In this space, no number smaller than 0 or more than 1 exists.

a) Show that any interval in the form (r,s), where 0 < r < s < 1 is open in this space.

b)Show that any interval in the form [0, s), where s < 1, is open in this space.

c) Show that any interval in the form (r, 1], where r > 0, is open in this space.

Let $ M\equal{}([0,1],\left|\cdot\right|)$.  For (a), given a point $ x\in (r,s)$, let $ \epsilon\equal{}\min(x\minus{}r,s\minus{}x)$.  Then $ B_{\epsilon}(x)\subseteq (r,s)$ so $ (r,s)$ is open.  Since $ (r,s)$ is open in $ \mathbb{R}$, we can write $ (r,s)\equal{}[0,1]\cap (r,s)$, so it's open in $ M$.


calculus
integration
number theory
relatively prime

Show that for each odd prime number y, there is exactly one positive integer x such that x(x+y) is a perfect square.

I have a solution, but I'd like to see others.

[hide]

we begin by noting that $x$ and $y$ are relatively prime

we show this by letting $x=ay$ for positive integer $a$, hence $ay(ay+y) = a(a+1)(y^2)$

since this will never be a perfect square, we know that $x \not = ay$, and that $x$ and $y$ are indeed relatively prime

this then implies that $x+y$ and $x$ are relatively prime as well, and thus $x+y$ and $x$ must both be perfect squares

so, we let $x+y = n^2$ and $x = m^2$

then we have $x = n^2 - y = m^2$, which implies that $y = (n-m)(n+m)$ but since $y$ is prime, and since $n+m > n-m$, we know $n-m = 1$ and $n+m = y$

thus, $n = m+1$, and we now have $x+y = (m+1)^2$ and $x = m^2$

subtracting the two , we get:

$y = (m+1)^2 - m^2 = 2m+1$

$\frac{y-1}{2} = m = \sqrt{x}$

$x = \Big( \frac{y-1}{2} \Big)^2$

and this will be the only answer for $x$ that yields a perfect square, given the odd integer prime $y$

[/hide]

Interesting proof.  Here's mine:

[hide]Let our desired square be $z^2$, so that $x^2 + xy = z^2$.  First factor the equation as $(z + x)(z - x) = xy$.

Suppose first that $x$ is prime. Then we must have $z + x = y$ and $z - x = x$, or $z + x = xy$ and $z - x = 1$, since all values involved are integers, and $z > x$. Solving the first set of simultaneous equations gives $y = 3x$, which is a contradiction since $y$ is prime. Solving the second set gives $y = 2 + 1/x$, which is also a contradiction as $y$ must be an integer (letting $x = 1$ gives the trivial solution $y = 3$, $z = 2$).

Now assume that $x = ab$, where $a,b>1$ (i.e. $x$ is not prime). Then we have $(z + x)(z - x) = a(by)$.  This yields at least one possible set of simultaneous equations: $z + x = by$ and $z - x = a$. Solving these gives $y = 2a + a/b$. If $y$ is to be integral, we must assume that $b|a$, i.e that $a = kb$. Then we have $y = 2kb + k = k (2b + 1)$.  If $y$ is to be prime, we must have $k = 1$, meaning that $a = b$ and we must have $x = a^2$. So, $x$ must be a perfect square.  This immediately shows that we have only one solution, for $x$ may be factored in only one way as a perfect square (and so no other factorization of $x$ will yield a prime integral $y$).  This leads to $y = 2a + 1$, allowing us to generate all odd prime $y$, and (looking back at our simultaneous equations), we find that $z = a^2 + a$. We therefore have the unique solution set $(x,y) = (a^2, 2a + 1)$ for integral $a>0$ such that $y$ is an odd prime.

This proof is a little bit abbreviated, but I think it makes sense.  Note you can check that my solution set works (though not that it's unique), by expanding $a^2(a^2 + 2a + 1) = (a^2 + a)^2$.[/hide]

Here's another proof!

$x(x+y) = x^2 + xy$, which is greater than $x^2$ for positive $x$ and $y$ (given)
Let $(x+n)^2$ be the desired perfect square, so $x^2 + xy = (x+n)^2$
$x^2 + xy = x^2 + 2nx + n^2$
$xy = 2nx + n^2$
$y = 2n + n^2/x$

Since both sides of the equation are prime, then $x$ must equal $n^2$. Otherwise, the expression will have a factor of $n$ as one of its factors, which would mean it was composite.

Then $x(x+y) = (x + \sqrt{x})^2$
Which by algebra yields $2\sqrt{x} + 1 = y$, which is a nice solution.

P.S. ZantTrang is foughby.

[quote="Sceptus_magnum"]
P.S. ZantTrang is foughby.[/quote]
Pssh, your mom is foughby!  You should have come to these  forums a long time ago... I love how your proof gets the same work done as mine in about 1/5 of the space.


Let $ a,b,c>0$ such that $ a^2\plus{}b^2\plus{}c^2\equal{}3$. Prove that:

\[ \left(\frac{2}{\sqrt{a\plus{}b}}\minus{}1\right)\left(\frac{2}{\sqrt{b\plus{}c}}\minus{}1\right)\left(\frac{2}{\sqrt{c\plus{}a}}\minus{}1\right)\ge (\sqrt{2}\minus{}1)^3\]


Euler
geometry
geometric transformation
reflection
homothety
ratio
circumcircle

The centers of three circles isotomic with the Apollonian circles of triangle $ABC$ located on a line perpendicular to the Euler line of $ABC.$

What's a circle isotomic to another circle? Is it the locus of the points isotomic to the points of the first circle? (I'm not sure that locus is a circle; I'm just asking)

Actually, the problem should be:

[i]The reflections of the centers of the three Apollonian circles of a triangle ABC in the midpoints of the respective sides BC, CA, AB lie on one line which is perpendicular to the Euler line of triangle ABC.[/i]

Here is my [b]solution[/b]:

First, we use a lemma which I showed in post #2 in the thread http://www.mathlinks.ro/Forum/viewtopic.php?t=16823 :

[b]Lemma 1.[/b] Let P be a point in the plane of a triangle, and let the lines AP, BP, CP intersect the lines BC, CA, AB at the points X, Y, Z, respectively. Let the lines YZ, ZX, XY meet the lines BC, CA, AB at the points X', Y', Z', respectively. It is well-known that the points X', Y', Z' lie on one line, the so-called [b]tripolar[/b] of the point P with respect to triangle ABC. Now, let the parallel to the line YZ through the point A intersect the line BC at A'. Then, the line X'Y'Z' (the tripolar of the point P with respect to triangle ABC) passes through the midpoint of the segment AA'.

Now, in the configuration of Lemma 1, we will show:

[b]Lemma 2.[/b] If we consider not only the point A' where the parallel to the line YZ through the point A intersects the line BC, but also the points B' and C' where the parallels to the lines ZX and XY through the points B and C intersect the lines CA and AB, then the reflections A", B", C" of these points A', B', C' in the midpoints of the sides BC, CA, AB of triangle ABC lie on one line, and this line is the image of the line X'Y'Z' (the tripolar of the point P with respect to triangle ABC) under the homothety with center G and factor -2. Hereby, G is the centroid of triangle ABC.

[i]Proof.[/i] Let T be the midpoint of the segment AA'; then, after Lemma 1, this point T lies on the line X'Y'Z'.

Let M be the midpoint of the side BC of triangle ABC. Then, the segment AM is a median of triangle ABC, and thus it passes through the centroid G of triangle ABC and is divided by G in the ratio AG : GM = 2 (with directed segments).

Since the point A" is the reflection of the point A' in the midpoint M of the side BC of triangle ABC, the point M is also the midpoint of the segment A'A". Hence, the segment AM is a median of triangle AA'A", and thus it passes through the centroid G' of triangle AA'A" and is divided by G' in the ratio AG' : G'M = 2 (with directed segments).

Now since both points G and G' lie on the segment AM and divide the segment AM in the same ratio AG : GM = 2 and AG' : G'M = 2, it follows that these points G and G' coincide. In other words, the centroid G of triangle ABC coincides with the centroid G' of triangle AA'A"; this yields that the point G is the centroid of triangle AA'A".

Now, since the point T is the midpoint of the side AA' of triangle AA'A", the line A"T is a median of triangle AA'A", and hence, it passes through the centroid G of triangle AA'A" and is divided by G in the ratio A"G : GT = 2. Hence, GA" : GT = - A"G : GT = -2. Consequently, the homothety with center G and factor -2 maps the point T to the point A". But since the point T lies on the line X'Y'Z', its image A" must therefore lie on the image of the line X'Y'Z' under the homothety with center G and factor -2. Similarly, the points B" and C" also lie on the image of the line X'Y'Z' under this homothety. Hence, the three points A", B", C" lie on one line, and this line is the image of the line X'Y'Z' under the homothety with center G and factor -2. Lemma 2 is proven.

Now, consider a particular case of all the above: In fact, let P be the orthocenter of triangle ABC. Then, the lines AP, BP, CP are the three altitudes of triangle ABC, and their points of intersection X, Y, Z with the lines BC, CA, AB are the feet of these altitudes. The triangle XYZ is the orthic triangle of triangle ABC; hence, by a well-known theorem, the sides YZ, ZX, XY of this orthic triangle are antiparallel to the sides BC, CA, AB of triangle ABC with respect to the triangle ABC. In particular, the line YZ is antiparallel to the side BC of triangle ABC. Thus, the line AA', being parallel to the line YZ, is also antiparallel to the side BC of triangle ABC. But an antiparallel to a side of a triangle through the opposite vertex is the tangent to the circumcircle of the triangle at that vertex; hence, the line AA', being antiparallel to the side BC of triangle ABC and passing through the opposite vertex A, must be the tangent to the circumcircle of triangle ABC at the vertex A. So, now we know what the point A' really is: It is the point where the tangent to the circumcircle of triangle ABC at the vertex A intersects the line BC. But it is well-known that this point is the center of the A-Apollonius circle of triangle ABC. Hence, we can conclude that the point A' is the center of the A-Apollonius circle of triangle ABC. Similarly, the point B' is the center of the B-Apollonius circle, and the point C' is the center of the C-Apollonius circle. And, of course, the points A", B", C" are the reflections of these centers A', B', C' in the midpoints of the sides BC, CA, AB of triangle ABC. Now the link to your problem is clear: Your problem just asks to prove that the points A", B", C" lie on one line which is perpendicular to the Euler line of triangle ABC. Actually, the fact that the points A", B", C" lie on one line now immediately follows from Lemma 2, so it remains to show that this line A"B"C" is perpendicular to the Euler line of triangle ABC.

In fact, Lemma 2 states that the line A"B"C" is the image of the line X'Y'Z' under a certain homothety. Since a homothety maps any line to a parallel line, it follows that the line A"B"C" is parallel to the line X'Y'Z'. Hence, instead of proving that the line A"B"C" is perpendicular to the Euler line of triangle ABC, it is enough to show that the line X'Y'Z' is perpendicular to the Euler line of triangle ABC. But remembering how we defined the points X', Y', Z' - namely, we defined them as the points of intersection of the lines YZ, ZX, XY with the lines BC, CA, AB, and the points X, Y, Z were the feet of the altitudes of triangle ABC -, we see that this directly follows from [url=http://www.cip.ifi.lmu.de/~grinberg/Schroeder/Schroeder.html#6]Lemma 1 of the posting [Schroeder6] in my "Schröder Points Database"[/url]. And by the way, the line X'Y'Z' is called the [b]orthic axis[/b] of triangle ABC.

$ \blacksquare$

  Darij

Let $ O_a , O_b , O_c$  the centers of the A-,B- and C- Apollonius circles of  $ \triangle ABC.$ These centers are the intersections of the tangents to the circumcircle $(O)$ at $A,B,C$ with $BC,$ $CA,$ $AB,$ respectively. Using barycentric coordinates, we get

$ O_a  (0: b^2: \minus{} c^2) \  , \ O_b ( \minus{} a^2: 0: c^2) \ , \ O_c  (a^2: \minus{} b^2: 0)$

Reflections of $ O_a, O_b, O_c$ about the midpoints of $ BC ,CA , AB$ are:

$ U_a (0: \minus{} c^2: b^2) \ , \ U_b (c^2: 0: \minus{} a^2) \ , \ U_c ( \minus{} b^2: a^2: 0)$

$U_a,U_b,U_c$ are collinear on the line $ \mathcal{L}\equiv a^2x \plus{} b^2y \plus{} c^2z \equal{} 0,$ which is the trilinear polar of the 3rd Brocard point of $\triangle ABC,$ $ X_{76}\left (\frac {_1}{^{a^2}}: \frac {_1}{^{b^2}}: \frac {_1}{^{c^2}} \right).$ The infinite point of $\perp \mathcal{L}$ is then $ T_{\infty} (S_BS_A \plus{} S_CS_A \minus{} 2S_BS_C),$ which coincides the infinite point $X_{30}$ of the Euler  line $e$  of $ \triangle ABC$ $\Longrightarrow$ $ e \perp  \mathcal{L}.$ In addition, $X_{858} \equiv \mathcal{L} \cap e.$

$ O$ is circumcenter, $ H$ orthocenter, $ N$ 9-point circle center of $ \triangle ABC.$ Let $ (U), (V), (W)$ be the A-, B-, C-Apollonius circles of $ \triangle ABC$ and $ (X), (Y), (Z)$ their reflections in the perpendicular bisectors of $ BC, CA, AB.$ Let  $ (U'), (V'), (W')$ be A'-, B'-, C'-Apollonius circles of its medial $ \triangle A'B'C'$ and $ (X'), (Y'), (Z')$ their reflections in the perpendicular bisectors of $ B'C', C'A', A'B'.$ Quadrilaterals $ AU'A'X', BV'B'Y', CW'C'Z'$ are parallelograms $ \Longrightarrow$ $ (X'), (Y'), (Z')$ are circles with diameters $ AU, BV, CW.$ Powers of $ O$ to $ (X'), (Y'), (Z')$ are all equal to $ OA^2 \equal{} OB^2 \equal{} OC^2$ and powers $ H$ to $ (X'), (Y'), (Z')$ are all equal to half the power of $ H$ to $ (O)$ $ \Longrightarrow$ $ ONH \perp X'Y'Z'$ is radical axis of $ (X'), (Y'), (Z')$ $ \Longrightarrow$ $ ONH \perp XYZ$ is radical axis of $ (X), (Y), (Z).$

EDIT: See also [url]http://www.mathlinks.ro/viewtopic.php?t=278520[/url] for another solution.


[quote="joml88"]If $(x,y)$ is a solution to the system

\[xy=6 \ \ \text{and} \ \ x^2y+xy^2+x+y=63,\]

find $x^2+y^2.$[/quote]

Given the equations, one can factor the second one into $(xy)(x+y) + (1)(x+y) = 63.$

By grouping, one yields $(xy+1)(x+y) = 63$.  Because we were given $xy = 6,$ we know $(6+1)(x+y) = 63,$ so $x+y = 9.$

Now to find $x^2+y^2,$ we note that $x^2+y^2 = (x+y)^2 - 2xy$.

Therefore, $x^2+y^2 = 9^2 - 2*6 = \fbox{69}.$

I would put my solution, but it's identical to the ones given.  :D


logarithms
number theory proposed
number theory

Prove the stronger statement than one of Mathlinks contest problems: there exists a constant $C>0$ such that for all n the sum of digits of $2^n$ is greater than $Clnn$.
   Far more difficult: is it true that the quotient between the sum of digits of $2^n$ and $lnn$ goes to infinity for large n?

I can prove the first part for $C = \frac 1 {\log4}$ (at least for $n \geq 4$).

Do you know the answer for part b)? Is it understandable?

Pierre.

I think I also found a constant of this type just by reasoning on the last digits of 2^n and grouping them, but for the second question I have no idea. I searched some results, but I found nothing, unfortunately. Keep searching.

As a general result, I only know that $S(a^n)$ tends to $+ \infty$ when $a$ is any positive integer which is not of the form $10^r$, but the proof is not easily understandable (in my opinion).

Maybe Blang knows more about it because he investigated this kind of question some years ago... ;)

Pierre.

[i]Pierre, allons, tu dois maintenant en connaître plus que moi sur le sujet :)
Je ne retrouve pas l'article de Senge et Strauss, ils n'en parlent pas?
Y en a bien qui parlent parfois en russe, ici... :D [/i]

[b]Well, I think that part b) of Harazi's problem is an open question...[/b]

Well, it is not totally nonsense. Concrete Mathematics is quite a good book  :P

Pierre.

[quote="harazi"]Not before you prove the second assertion ( of course, if you proved that one, the first question is silly, just like you, who did not observe that!) using the prime number theorem! Poor students...[/quote]
ok, this weekend I give you a proof, but please be sure that u have a COMPLETE proof of the first part, ok?   :D

Ok! Man, you really are teacher at university? Either this is a conspiracy against me, or it is really the most crazy thing that I have ever heard. I have my complete solution for the first question, hope you'll have yours. Even if I don't understand something: if you manage to solve the second question, obviously you have solved the first one. So, what is difficult to understand: that a sequence tending to infinity is unbounded? Well,... it is true!

Please can you give any hint for part (a)?  (of course other than prime number theorem)

[quote="harazi"]Prove the stronger statement than one of Mathlinks contest problems: there exists a constant $C>0$ such that for all n the sum of digits of $2^n$ is greater than $Clnn$.[/quote]
I would think in the following way.

Consider last $4^0$, $4^1$, ..., $4^k$ digits of $2^n$, where $k=[\log_4(n\log_10 2)]$. We will show that each new part adds at least one non-zero digit. Indeed, if all digits from $4^l+1$ to $4^{l+1}$ are zeros, then the number formed by last $4^l$ digits is divisible by $2^{4^{l+1}}$ ( do you know why? ;) ). On the other hand $4^l$-digit number is at most $10^{4^l}$, so $10^{4^l}\geq 2^{4^{l+1}}$, i.e. $10\geq 16$ -- contradiction.

Therefore the sum of digits of $2^n$ is at least $[\log_4 n]-C$.


How many whole cubes that are two inches along each edge fit into a rectangular box measuring one foot by 14 inches by 16 inches on the inside?

Or you could do:

$ 16 \cdot 14 \cdot 12 \equal{} 2688 \div 8 \equal{} \boxed{336}$

However, I would recommend my way, because the math is simpler. xD

yay.  my 1111th post that counts.


limit
function
trigonometry
calculus
calculus computations

I just start to learn big-O little-o and not so familiar with it . So i need someone to explain how we should do this

Prove that when $n\rightarrow \infty$ then for $\epsilon>0$ ,$\exp(-n)=o\left(\frac{1}{n^{\epsilon}}\right)$

Also how to prove

(i) $o(1)+o(1)=o(1)\cdot o(1)=o(1)$

(ii)$o(1)\leq O(1)$

Thanks

Since $\lim_{n \rightarrow \infty} \frac{e^{-n}}{\frac{1}{n^{\epsilon}}} =0$ so we have $e^{-n} = o (\frac{1}{n^{\epsilon}})$.

let $g(n)=o(1)$, then $\lim_{n \rightarrow \infty} g(n) =0$, since $\lim_{n \rightarrow \infty} 2g(n) =0$ then so $o(1)+o(1)=2 g(n) = o(1)$.

Let $f(n)=o(1)$ and $g(n)=O(1)$, so $\lim_{n \rightarrow \infty} f(n) =0$ and $\lim_{n \rightarrow \infty} |g(n)| <M$.  then you can argue  $f(n) \leq g(n)$.

im just wondering , if $o(1)+o(1)=o(1)$ ,does this means that $o(1)=0$ ??

No. $o(1)$ isn't a quantity. It's a function that converges to 0 when you take whatever limit you're considering. The statement $o(1) + o(1) = o(1)$ is just the statement that the sum of any two functions that converge to 0 at a certain point also converges to 0 at that point.

Similarly, $O(1)$ (or whatever) is a statement about the behavior of a function in a limit and doesn't necessarily represent anything in particular.

It's true that $\sin x=O(1)$ but it's not true that $O(1)=\sin x$.  :P [Littlewood's remark] Since the symbols $O(\dots)$ and $o(\dots)$ represent [b]classes[/b] of functions, it would be more precise to write $\sin x\in O(1)$. Other examples: \[e^{-n}\in o(2^{-n})\subset O(2^{-n}) \subset o(n^{-2})\]  \[o(1)+o(1)\subseteq o(1)\] ($o(1)+o(1)= o(1)$ also makes sense, but this is a stronger statement). Is it true that $O(f)o(g)=o(f)O(g)$? :wink:


Let s_n denote the number of ways in which the set {1,2,..,n} can be partioned into 3 non empty sets. For exmple s_4=6, the six partitions being

{1}{2}{3,4} , {1}{3}{2,4} , {1}{4}{2,3}
{2}{3}{1,4} , {2}{4}{1,3} , {3}{4}{1,2}

Show that s_n is determined by the recurrence relation $ s_0\equal{}0, s_1\equal{}0$ and $ s_n\equal{} 3s_{n\minus{}1}\plus{}2^{n\minus{}2}\minus{}1 (n>1)$

[hide="Method 1"] I claim that $ \sum_{n \ge 0} \frac{s_n}{n!} x^n \equal{} (e^x \minus{} 1)^3$.  Prove this by inclusion-exclusion. [/hide]
[hide="Method 2"] I claim that $ \sum_{n \ge 0} s_n x^n \equal{} \frac{x^3}{(1 \minus{} x)(1 \minus{} 2x)(1 \minus{} 3x)}$.  Prove this by a bijection. [/hide]

Whoah!! that's really confusing. I don't even understand the second one. How would you do the first?

I have to admit that answer was sort of tongue-in-cheek.  Here's the elementary approach: call the sets red, green, and blue.  You already know the answer when the sets don't have to be non-empty: it's just $ 3^n$, since any element can be red, green, or blue.  But now you've overcounted

- The partitions without any red,
- The partitions without any green,
- The partitions without any blue.

So you subtract these, and now you have to add back...


trigonometry
LaTeX
algebra
polynomial
binomial theorem
complex numbers
geometry

in a triangle ABC angle A=x, angle B=2x, and andgle C=4x

prove that 1/AB+1/AC=1/BC.

$ \text{\LaTeX}$ would help in your posts...

[hide]By the law of sines, $ AB = 2R\sin{C}$, $ BC = 2R\sin{A}$, $ CA = 2R\sin{B}$. $ x+2x+4x =\pi$, so $ x =\frac{\pi}{7}$. Now we want to show that $ \frac{1}{\sin\frac{4\pi}{7}}+\frac{1}{\sin\frac{2\pi}{7}}=\frac{1}{\sin\frac{\pi}{7}}$. Then, let $ \frac{\pi}{7}=\theta$. By the double angle formula, we have
$ \frac{1}{\sin\frac{4\pi}{7}}+\frac{1}{\sin\frac{2\pi}{7}}=\frac{1}{\sin\frac{\pi}{7}}$;
$ \Leftrightarrow\frac{1}{2\sin{2\theta}\cos{2\theta}}+\frac{1}{\sin{2\theta}}=\frac{1}{\sin{\theta}}$;
$ \Leftrightarrow\frac{1}{2\cos{2\theta}}+1 =\frac{\sin2\theta}{\sin\theta}$;
${ \Leftrightarrow\frac{1}{2\cos2\theta}}+1 = 2\cos\theta$;
$ \Leftrightarrow 1+2\cos2\theta = 4\cos\theta\cos2\theta$;
$ \Leftrightarrow 1+4\cos^{2}\theta-2 = 4\cos\theta(2\cos^{2}\theta-1)$;

$ 8\cos^{3}\theta-4\cos^{2}\theta-4\cos\theta+1 = 0$.

We apply deMoivre's Theorem, and find that $ \cos{7\theta}= 64\cos^{7}\theta-112\cos^{5}\theta+56\cos^{3}\theta-7\cos\theta$. This is because $ \cos7\theta+i\sin7\theta = (\cos\theta+i\sin\theta)^{7}$, which is just deMoivre, and we can expand with the Binomial Theorem and take the imaginary part of both sides. Then, we substitute $ \sin^{2}\theta = 1-\cos^{2}\theta$ multiple times, work through the algebra, and get the result.

Consider the equation $ \cos{7\theta}=-1$. In the interval $ [0,2\pi)$, it has the solutions $ \theta =\frac{\pi}{7},\frac{3\pi}{7},\frac{5\pi}{7},\pi,\frac{9\pi}{7},\frac{11\pi}{7},\frac{13\pi}{7}$, and the cosines of each of these angles is a root of $ 64x^{7}-112x^{5}+56x^{3}-7x+1 = 0$, by the septuple angle formula. It has a root of $ \cos{\pi}=-1$, so we can factor out $ x+1$, to get $ 64x^{6}-64x^{5}-48x^{4}+48x^{3}+8x^{2}-8x+1 = 0$. But $ \cos\frac{\pi}{7}=\cos\frac{13\pi}{7}$, $ \cos\frac{3\pi}{7}=\cos\frac{11\pi}{7}$, and $ \cos\frac{5\pi}{7}=\cos\frac{9\pi}{7}$, so there are 3 double roots, and the polynomial is a square, and its square root is $ 8x^{3}-4x^{2}-4x+1$, which we can find by letting its square root be equal to $ 8x^{3}+bx^{2}+cx\pm1$, squaring, and matching coefficients. The roots of $ 8x^{3}-4x^{2}-4x+1 = 0$ are $ \frac{\pi}{7},\frac{3\pi}{7},\frac{5\pi}{7}$. But doesn't that polynomial look familiar?

Indeed. Let $ x =\cos\theta$, and we get the one we had before. Now, we saw that $ \cos\frac{\pi}{7}$ was a root of the polynomial in $ x$, so $ \frac{\pi}{7}$ is a root of the polynomial in $ \theta$ and that thing is indeed equal to 0, so we're done.[/hide]

[hide="simpler"]
By the law of sines, $ AB \equal{} 2R\sin{C}$, $ BC \equal{} 2R\sin{A}$, $ CA \equal{} 2R\sin{B}$. $ x\plus{}2x\plus{}4x \equal{}\pi$, so $ x \equal{}\frac{\pi}{7}$. Now we want to show that $ \frac{1}{\sin\frac{4\pi}{7}}\plus{}\frac{1}{\sin\frac{2\pi}{7}}\equal{}\frac{1}{\sin\frac{\pi}{7}}$

$ \sin\frac{2\pi}{7}\sin\frac{4\pi}{7}\equal{} 2\sin\frac{\pi}{7}\cos\frac{\pi}{7}\sin\frac{3\pi}{7}$
also
$ 2\sin\frac{3\pi}{7}\cos\frac{\pi}{7}\equal{}\sin\frac{4\pi}{7}\plus{}\sin\frac{2\pi}{7}$
so
$ \sin\frac{2\pi}{7}\sin\frac{4\pi}{7}\equal{}\sin\frac{\pi}{7}(\sin\frac{4\pi}{7}\plus{}\sin\frac{2\pi}{7})$
dividing by $ \sin\frac{4\pi}{7}\sin\frac{2\pi}{7}$
we get
$ \frac{1}{\sin\frac{4\pi}{7}}\plus{}\frac{1}{\sin\frac{2\pi}{7}}\equal{}\frac{1}{\sin\frac{\pi}{7}}$
[/hide]

[hide="no trig"]
$ \Delta ABC$ is a part of regular heptagon (see attached picture). Applying Ptolemy for ACBD we have:
$ AB*DC\equal{}AC*BD\plus{}AD*BC$. As $ AD\equal{}AB\equal{}c$ , $ BD\equal{}BC\equal{}a$, $ DC\equal{}AC\equal{}b$ we obtain:
$ c*b\equal{}b*a\plus{}c*a$ divide by $ abc$ to get $ \frac{1}{a}\equal{}\frac{1}{c}\plus{}\frac{1}{b}$[/hide]

wow thanks!

and i'll try to use $ latex$ more.


At the start a jar contains only quarters and coins of lesser value. The average value of these coins is 9 cents. Adding a quarter to the jar raises the average to 11 cents. Find hte probability that a coin randomly selected from the jar at the start is a quarter.

[hide]2/7[/hide]

[quote="nebula42"]Next time, try not to give every topic the same name. It's a little bit confusing.  :wink:
Even better, you can put everything in the same topic.

[hide]Anyway, for this problem, you can let $ n$ be the number of coins inside the jar at the beginning, and then find $ n$ by getting an equation with the information given. After that, you can probably find the number of quarters that were in the jar using $ n$.[/hide][/quote]

Sorry about that..... Idk what to call my topics since they all are from the same test from teh same year..... I guess I would do horrible on the test :lol: ... Well, I'll try my best to give new names :)
THx for solution!


I'll start easy. This is actually a Caesar Cipher... kind off.

KXEMNU EXNFTL RTP MLXZGHE XAM HZ ZGBRE YH MGNHFT MLXEETFL XAM LXDTF HAP XA LB KTBE MLXU XAM.

Fine, I'll give you guys a big hint.
[hide="Hint"]
Think Backwards.

[/hide]

Well, it was easy given that it was a Caesar cipher...

"The best liar is he who makes the smallest amount of lying go the longest way" Samuel Butler

I wouldn't have seen it without the hint though :)

ycj zajt veqgqphtv tvxk yon

[hide="Hint"]AoPS[/hide]

[hide="Solution"]
YOU HAVE DECRYPTED THIS YAY

(vigenere cipher with key as AOPS)
[/hide]

tdi lntemlnj riauqety nbilay er wntadelb ymu.

[hide]
Substitution:

a=c, b=g, d=h, e=i, i=e, j=l, l=n,  m=o, n=a,  q=r,  r=s, t=t, u=u,  w=w, y=y

The decrypted version is as follows:

"The national security agency is watching you."
[/hide]
.

[quote](vigenere cipher with key as AOPS)[/quote]

What's vigenere cipher? Please don't tell me to google that as I do not have access to that.

[quote="fortenforge"]P7WBLS7ZDBWX7WYSBSPMZ7TMK7GHK7SOKA7FX7ZY
UL7LHI7OTUL7VPUDYDF7MN7ZDBWX7TKAADTKABBZ7K
UW7OOSSHRVZOR7LF7CVGR7VENAS7AY7ZMTKI7TTSO
OTTSPMZ7TMK7ZOBKVCVIGF17QLHFYKWAX17UKANQH
V7OBRAYYR17MHFHE7ZYMOBSLMANQL17XHOHNKABNU
17MVFLLBJX17ZUN7HZQPMBESBBL17BM7VBKXQ7AY7NB
UL7DOXHY7MOBKKBLG7Z7YSNAS7AY7ZMTKI7WTHUDPG
F17WYLMQF17WBLHJ17KYVGPDLVSBBL17LSHDBTQF17
DHIDZDYR17ZUN7WHQJOSTHU7TVAM7HNHFR

[hide="Hints"]
[hide="Hint 1"]
Vigenere Cipher
[/hide]
[hide="Hint 2"]
'1' and '7' represent punctuation.
[/hide]
[hide="Hint 3"]
HKHTZ
[/hide]
[/hide][/quote]

[hide="Answer"]“I MUST STUDY POLITICS AND WAR THAT MY SONS MAY HAVE LIBERTY TO STUDY MATHEMATICS AND PHILOSOPHY.  MY SONS OUGHT TO STUDY MATHEMATICS AND PHILOSOPHY, GEOGRAPHY, NATURAL HISTORY, NAVAL ARCHITECTURE, NAVIGATION, COMMERCE, AND AGRICULTURE, IN ORDER TO GIVE THEIR CHILDREN A RIGHT TO STUDY PAINTING, POETRY MUSIC, ARCHITECTURE, STATUARY, TAPESTRY, AND PORCELAIN.” --  JOHN ADAMS[/hide]

Playfair Cipher

HATWK DLSYH NBKNL XFNCM WTDOZ BKSYK IGMXM XYHAT BTPCZ SHBST SVOZB QWKQI RXYHA TBTPC ZSHBN OBXBD XBKLM LDWOS WTTPC QGTBV XGTDV NHXPP
[hide="Hints"]
Partial key:

B R  I G H
T * X E N
S * M P *
O * Y F W
L *  A C *

*'s represent parts of the key I won't tell you.

Don't know what a playfair cipher is? Click [url=http://en.wikipedia.org/wiki/Playfair_cipher]here[/url].
[/hide]

Seeing as no one was able to get the playfair cipher with the partial key I will give you the full key:

[hide="Key"]
B R  I G H
T V X E N
S U M P D
O Z Y F W
L Q A C  K

J is treated the same as I.
[/hide]

[hide="Answer"]“I  KNOW NOT WITH WHAT WEAPONS WORLD WAR III WILL BE FOUGHT BUT WORLD WAR IV WILL BE FOUGHT WITH STICKS AND STONES” - ALBERT EINSTEIN.[/hide]

See fortenforge's post for a link explaining playfair ciphers.

Is it really that hard to figure out?  There's two possible posts (the ones that refer to the playfair cipher).

http://en.wikipedia.org/wiki/Playfair_cipher

What I meant is could you provide an explanation for the answers to the ciphers?

If you bothered to read the article about Playfair Ciphers, you just chug the letters in.  It's like a substitution code, except you already know the code...

For ALL of them, not just the Playfair...

[hide="Explanations"]
[hide="Problem 1"]
KXEMNU EXNFTL RTP MLXZGHE XAM HZ ZGBRE YH MGNHFT MLXEETFL XAM LXDTF HAP XA LB KTBE MLXU XAM.

This was a [url=http://en.wikipedia.org/wiki/Caesar_cipher]Caesar Cipher[/url]. The key was a shift of 7 for encryption. The hard part was to recognize that the message had been reversed before encrypting it.

Solution:
The best liar is he who makes the smallest amount of lying go the longest way Samuel Butler.
[/hide]
[hide="Problem 2"]
ycj zajt veqgqphtv tvxk yon

This was encrypted using a [url=http://en.wikipedia.org/wiki/Vigenere_Cipher]Vigenere Cipher[/url].
It would have been impossible to crack it without the keyword given because of it's length.
The key was given to be AOPS.
Guessing that this message used a Vigenere Cipher gives us that the solution is:
YOU HAVE DECRYPTED THIS YAY.
[/hide]
[hide="Problem 3"]
tdi lntemlnj riauqety nbilay er wntadelb ymu.

This was a substitution cipher. Frequency Analysis should have been enough to crack it.
The key turned out to be "NSA CIA FBI" of course removing repeated letters and adding the rest of the alphabet to get:

NSACIFBDEGHJKLMOPQRTUVWXYZ

The solution was:
The national security agency is watching you.
[/hide]
[hide="Problem 4"]
P7WBLS7ZDBWX7WYSBSPMZ7TMK7GHK7SOKA7FX7ZY
UL7LHI7OTUL7VPUDYDF7MN7ZDBWX7TKAADTKABBZ7K
UW7OOSSHRVZOR7LF7CVGR7VENAS7AY7ZMTKI7TTSO
OTTSPMZ7TMK7ZOBKVCVIGF17QLHFYKWAX17UKANQH
V7OBRAYYR17MHFHE7ZYMOBSLMANQL17XHOHNKABNU
17MVFLLBJX17ZUN7HZQPMBESBBL17BM7VBKXQ7AY7NB
UL7DOXHY7MOBKKBLG7Z7YSNAS7AY7ZMTKI7WTHUDPG
F17WYLMQF17WBLHJ17KYVGPDLVSBBL17LSHDBTQF17
DHIDZDYR17ZUN7WHQJOSTHU7TVAM7HNHFR

By the Hints we were told this was a Vigenere cipher. There was some sort of twist obviously because of the lack of spaces and the number of 1's and 7's.
Hint 3 gave us the key which was "HKHTZ". This is actually the word "ADAMS" encrypted with a Caesar cipher.
Decrypting the message with the key gave us:

I7MUST7STUDY7POLITICS7AND7WAR7THAT7MY7SO
NS7MAY7HAVE7LIBERTY7TO7STUDY7MATHEMATICS7A
ND7PHILOSOPHY7MY7SONS7OUGHT7TO7STUDY7MATH
EMATICS7AND7PHILOSOPHY17GEOGRAPHY17NATURA
L7HISTORY17NAVAL7ARCHITECTURE17NAVIGATION
17COMMERCE17AND7AGRICULTURE17IN7ORDER7TO7GI
VE7THEIR7CHILDREN7A7RIGHT7TO7STUDY7PAINTIN
G17POETRY17MUSIC17ARCHITECTURE17STATUARY17
TAPESTRY17AND7PORCELAIN7JOHN7ADAMS

The 7 obviously represents the space and the 1 seems to represent a ",".
Knowing this gives us:
“I MUST STUDY POLITICS AND WAR THAT MY SONS MAY HAVE LIBERTY TO STUDY MATHEMATICS AND PHILOSOPHY. MY SONS OUGHT TO STUDY MATHEMATICS AND PHILOSOPHY, GEOGRAPHY, NATURAL HISTORY, NAVAL ARCHITECTURE, NAVIGATION, COMMERCE, AND AGRICULTURE, IN ORDER TO GIVE THEIR CHILDREN A RIGHT TO STUDY PAINTING, POETRY MUSIC, ARCHITECTURE, STATUARY, TAPESTRY, AND PORCELAIN.” -- JOHN ADAMS

which is the answer.
[/hide]
[hide="Problem 5"]
HATWK DLSYH NBKNL XFNCM WTDOZ BKSYK IGMXM XYHAT BTPCZ SHBST SVOZB QWKQI RXYHA TBTPC ZSHBN OBXBD XBKLM LDWOS WTTPC QGTBV XGTDV NHXPP

I told you that this was a [url=http://en.wikipedia.org/wiki/Playfair_cipher]Playfair cipher[/url]. I had hoped that giving a partial key would have been enough to figure out the answer but no one could so I gave you the whole key:
B R  I G H
T V X E N
S U M P D
O Z Y F W
L Q A C K

The key is actually the phrase "Bright Vixens jump, dozy fowl quack". This phrase includes every letter of the alphabet. Another such phrase is "The quick brown fox jumps over a lazy dog". Another such phrase is "Five boxing wizards jump quickly". I found it interesting that all the phrases used the word "jump".

Anyways, with the key you could easily decrypt the message using the instructions on the wikipedia site giving you:
“I KNOW NOT WITH WHAT WEAPONS WORLD WAR III WILL BE FOUGHT BUT WORLD WAR IV WILL BE FOUGHT WITH STICKS AND STONES” - ALBERT EINSTEIN.
[/hide]
[/hide]

Next Cipher:

Edit: I made a mistake encrypting it. Here is the real ciphertext:
ITAOSRLIOREANOCTEHASAHLSTOAYOYUOKNFRGETRHLEGYUEOEOHRGTLCMCSEFOOGAACLEVMTIPE

[hide="Hint"]
Railfence Cipher
[/hide][url][/url]

Seeing as no one was able to get it, I thought that I might give you a website that will decrypt it for you.

Here is the url: [url]http://www.math.temple.edu/~renault/cryptology/railfence.html[/url].

Or if you rather would try to decrypt it yourself here is a hint:
[hide="Hint"]
Split the text like this:

ITAOSRLIOREANOCTEHA
SAHLSTOAYOYUOKNFRGETRHLEGYUEOEOHRGTLC
MCSEFOOGAACLEVMTIPE

and try arranging it to form a message.
[/hide]

[hide]ismathclasstooeasyforyoulookingforagreaterchallengeyouvecometotherightplace[/hide]

using the website.


I am planning to take the October SAT II in Physics.

I want to know how much detail and rigor is need for the exam especially in topics like Optics and Modern Physics. I've seen the questions - they are easy. I'm asking about the topics - how many different, which ones and in what detail should they be done.

Please help! I can clarify my question if you want.

I've done SAT II in physics more than a year ago and - they [i]are[/i] easy. I haven't prepared at all and I scored 800. I believe that it is a multiple choice test only so there's not really that much to think about - just choose the right answer!

haha... really... no need to prepare for it.  its got the most ridiculous curve in the world; an 800 is only around 90th percentile...

Whats SAT II PHYSiCS?SOmethin international???

By the way...could somone tell me nice tips and stuff for preparin for science olympiads(only regional level and then hopefully national!!!)

[quote="shadysaysurspammed"]Whats SAT II PHYSiCS?SOmethin international???[/quote]
You could say so :) . It's a test that some (American) colleges require you to take if want to apply.

you need to know the basics of all basic physics, none of the questions are really hard, they just test to see if you know the basics of everything, and can apply your knowledge, more concepts than equations, the sparknotes online guide is pretty good, but i knew everything in it anyway(that is how i studied)


For acute triangle ABC, cevians AD, BE, and CF are concurrent at P.
Prove
$\displaystyle 2(\frac{1}{AP}+\frac{1}{BP}+\frac{1}{CP})\leq \frac{1}{PD}+\frac{1}{PE}+\frac{1}{PF}$
and determine when equality holds

I am going to guess that equality holds when the triangle is equilateral  :)

Triangle ABC is fixed, only the location of P changes


Does anyone know about the ongoing math contest,so called West Chinese Math Olympiad?
If so,please be so kind to provide a web-site or any other source.

I am also here in Guiyang (Guizhou province) of China at CWMO 2008 (from Romania), but I don't think there is a website about the contest.

Today (1st November) was also the first day of the competition, but I think we are not allowed to post the problems yet, to avoid cheating.

I will post the problems after the final results will be show up.

 [hide=" for Erken"] My room its just near Kazakhstan Leader and Serghey ( a student from Kazakhstan). [/hide]

Hi!
I am acquainted with the majority of the team, Nursultan,Yegor and Sanzhar, we represented our country at the last IMO.
That's the first time when Romania sends the team to CWMO,right?
uh...I am confused,how posting of these problems can initiate cheating ?
But I guess, you can provide some information about their performance today?

Good luck, and send greetings to my team.

:)The Chinese professor said that it is better to post them after the coordination. Today was the coordonation for the first day :) but I don't really know the scores for Kazahstan but I think they had a computer, too. Maybe I will tell them to write you a private message about their scores.

Thanks for saying good luck :D, and yes it is the first time for Romania here.

How did you do today?
So the coordination is over,right?Perhaps,it is already allowed to post the problems.
Please do so,and if you know any information how did Kazakhstan team perform,please share it with me.
Thanks.


probability
function
integration
expected value
real analysis
real analysis unsolved

Suppose $ p(x)$ is a continuous probability density function which
satisfying the following condition (where $ n$ is integer and $ k$ is positive
constant, t is time and no less than zero):
\[ \int_{0}^{\infty}n(\int_{t}^{\infty}p(x)dx)^{n \minus{} 1}p(t)t dt \equal{} \frac {k}{n} \int_{0}^{\infty} tp(t)dt\]
When k=1, it is clear that the exponential distribution $ p(t) \equal{} ce^{ \minus{} ct}$ is one solution. My first question is: Is this solution unique?
My second question is: For any positive k, what is the solution? Is the solution unique? If it is, then how to prove the uniqueness?
Thanks a lot! :)

Let $ Y$ be a random variable with density $ p$. The left-hand side is the expected value of the minimum of $ n$ independent copies of $ Y$, while the right-hand side is $ \frac{k}{n}$ times the expected value of $ Y$.

Obviously, there are many solutions that fit some pair $ k,n$. Can we hit all $ n$ at once with a given $ Y$ and $ k$? Only if $ k\equal{}1$, because the equation reduces to $ E(Y)\equal{}kE(Y)$ at $ n\equal{}1$. For any given pair $ k>0,n>1$, there are of course many solutions, with too many degrees of freedom to be interesting. All the action is at $ k\equal{}1$, at least with the given framing.

OK, take $ k\equal{}1$ and suppose $ Y$ is a solution for all $ n$. What can we say about $ Y$?
The expected value of $ Y_1\plus{}Y_2\plus{}\cdots\plus{}Y_n$ ($ n$ independent copies) is $ nE(y)$, given that $ Y_1$ is smallest. The expected value of $ Y_2\minus{}Y_1$ given that $ Y_1$ is smallest is thus $ \frac1{n\minus{}1}\left(nE(y)\minus{}nE(\min_i Y_i)\right)\equal{}E(y)$.
That's also a sufficient condition, so that property makes all exponential random variables solutions, as you said.
That's all I've got for now.

So, does this mean the uniqueness of exponential distributions? If not, how to prove or disprove the uniqueness?


algebra
polynomial
quadratics
number theory
prime numbers
number theory unsolved

I have a great problem. How fast , and in which way are we able to see if there exists or doesn't exist a $kth$ root of $n$ mod $p$ where $p$ is a prime ???

If you want to know if there is an $x$ with $x^k = n \mod p$, then you can check this by calculating $n^{\frac{p-1}{\gcd(p-1 , k)}} \mod p$. It has a solution iff the residue is $1$.

Reason:
The multiplicative group $\mathbb{Z} / p \mathbb{Z}^*$ is cyclic, thus isomorphic to $\mathbb{Z} / (p-1) \mathbb{Z}$ (this times with addition). Such an isomorphism can be found by taking a primitive root $\zeta \mod p$ and then mapping $\zeta^s \to s \mod (p-1)$.
So you want to know iff there is an $x=\zeta^y$ with $x^k \equiv n=\zeta^s \mod p$, this means nothing else than checking iff $y \cdot k \equiv s \mod (p-1)$ can be solved.
Now $y \cdot k \equiv s \mod m$ can be solved iff $\gcd(k, m) | s$ (by Bezout for example), so iff $\gcd(k, m) | \gcd(s,m) \iff \frac{m}{\gcd(s, m)} | \frac{m}{\gcd(k,m)}$. Now also $z=\frac{m}{\gcd(s, m)}$ is the smallest number with $m| z \cdot s$. Thus the equation can be solved iff $\frac{m}{\gcd(k,m)} \cdot s \equiv 0 \mod m$ (because the solutions $t$ of $m|t \cdot s$ are exactly the multiples of $z$).
Using this for $m=p-1$ and changing back to the multiplication $\mod p$, we get:
$n^\frac{p-1}{\gcd(k, p-1)} \equiv 1 \mod p$ iff $n$ is a $k$-th power.

Note that $a^b \mod m$ can be calculated very fast, thus this should solve it.

Edit: errors corrected

Thank you very very much. This is really impressive (and also very helpful :) )

Very nice argument ZetaX, I'll add my few pennies tough :)
There is a criterion for solving TomciO's equation $\mbox{ mod } N$ for $N$ a positive integer. (Maybe you (TomciO) were aware of it ?)
Let $n \in \mathbb{N}$ and $a \in \mathbb{N.}$ For any positive integer $k$, the number of solutions $\mbox{ mod } p$ to
\begin{eqnarray*} x^n \equiv a ( \mbox{ mod } p ) & \mbox{ and } & x^n \equiv a ( \mbox{ mod } p^k ) \end{eqnarray*}
is equal. Therefore $x^n \equiv a ( \mbox{ mod } p )$ is solvable if and only if $x^n \equiv a ( \mbox{ mod } p^k )$ is solvable for all $k \in \mathbb{N}$.
Now let $N = \prod p^{\alpha}$. By the preceding remark, the equation $x^n \equiv a ( \mbox{ mod } N )$ is solvable if and only if, for all prime divisors $p$ of $N$ the equation $x^n \equiv a ( \mbox{ mod } p )$ is solvable, which is what we want.
If this is of interest, I can write down all the proofs.

EDIT: @ZetaX: BTW, shouldn't there be  $n^\frac{p-1}{\gcd(k, p-1)} \equiv 1 \mod (p)$ rather than $n^\frac{p-1}{\gcd(k, p-1)} \equiv 1 \mod (p-1)$ at the end of the post ?

EDIT2: Is this correct ? Is this what you meant ? (I got lost at a point)
\begin{eqnarray*} \gcd ( k, p - 1 ) |s & \Longleftrightarrow & \frac{p - 1}{\gcd ( k, p - 1 )} \cdot s \equiv 0 ( \mbox{ mod } p - 1 )\\ (\mbox{Apply the isomorphism}) & \Longleftrightarrow & n^{\frac{p - 1}{\gcd ( k, p - 1 )}} \equiv 1 ( \mbox{ mod } p )\\ & & \end{eqnarray*}

Hehe, thank you, though I haven't post anything in this topic :). Anyway, I'm very interested in this issue so, if you could post the proofs, when you have time, I would be grateful.

To TomciO and jastrzab: I'm sorry for that, confusing nicknames is becoming my speciality. Tough I must admit that it does attract attention sucessfully :) (That was not my intent homever). Anyway I hope I'm not becoming schizophrenic :roll:

{x}: yes, you are right for both, I messed up some variables and wrote $p-1$ instead of $p$.
Hope it's correct now.

Sorry for that nonsense, I shouldn't write something after only 3 hours of sleep last night...

[quote="{x}"]If this is of interest, I can write down all the proofs.[/quote]
I am very interested of the proofs of your statements...if you can please post them ;)

Thanks!

What {x} forgot is that $a$ and $n$ have to be coprime (otherwise $\mod p^2$ already problems occur, e.g. $a=p, n=2 , N=p^2$, such that we have to look at the $p$-adic valuations, too; indeed this could be done but makes it uglier).
The claim that we have just to show that it can be solved comes directly from the Chinese Remainder Theorem.
The claim that there is a solution $\mod p$ iff there is one $\mod p^k$ comes for odd $p$ from the fact that there exists primitive roots $\mod$ any power of an odd prime.
And well, $\mod 2^k$ gets a bit ugly (looking $\mod 2$ to see if it has a solution is not enough, you need to look $\mod 8$), but there is at least some pseudo-primitive root $\zeta$ (indeed $\zeta=5$ works) such that $\zeta^s$ runs through all residues $\mod 2^k$ that are $\equiv 1 \mod 4$, so all are reached by $\pm \zeta^s$, and the same reasoning as above works.

Here goes the proof :) :

Note that given a polynomial $F(X)$ , I denote by $F'(X)$ it's ("formal") derivative.
I will make us of the following Lemma's,
[b]Lemma 1.[/b] Let $a, b, N$ be three positive integers. If $( a, N ) = 1$, then the equation
\begin{eqnarray*} ax + b & \equiv & 0 ( \mbox{mod } N ) \end{eqnarray*}
has exactly one solution.

[b]Lemma 2.[/b] Let $F ( X ) \in \mathbb{Z} [ X ]$ and $n \in \mathbb{N} .$ Then
\begin{eqnarray*} x \equiv x_0 ( \mbox{mod } n ) & \Longrightarrow & F ( x ) \equiv F ( x_0 ) + ( x - x_0 ) F' ( x_0 ) ( \mbox{mod } n^2 ) \end{eqnarray*}

[b]Theorem.[/b] Let $F ( X ) \in \mathbb{Z} [ X ]$. Let $p$ be a prime number and $k$ a positive integer.
Given $x_0 \in \mathbb{F}_{p^k}$ let $S_F^{\mathbb{F}_{p^k}} ( x_0 ) = \left\{ x \in \mathbb{F}_{p^{k + 1}} | F ( x ) \equiv 0 \left( \mbox{mod } p^{k + 1} \right) \mbox{ and } x \equiv x_0 \left( \mbox{mod } p^k \right) \right\}$
If $F ( x_0 ) \not \equiv 0 ( \mbox{mod } p^k )$, then (clearly) $\# S_F ( x_0 ) = 0$.
If $F ( x_0 ) \equiv 0 ( \mbox{mod } p^k )$, then
\begin{eqnarray*} \# S_F ( x_0 ) & = & \left\{\begin{array}{l} 1, \mbox{when } p \nmid F' ( x_0 )\\ 0, \mbox{when } p|F' ( x_0 ) \mbox{ and } p^{k + 1} \nmid F ( x_0 )\\ p, \mbox{when } p|F' ( x_0 ) \mbox{ and } p^{k + 1} | F \left( x_0 \right) \end{array}\right. \end{eqnarray*}
[b]Proof.[/b] Suppose that $F ( x_0 ) \equiv 0 ( \mbox{mod } p^k )$.
Let $x \in \mathbb{F}_{p^{k + 1}}$ be an element of $\mathbb{F}_{p^{k + 1}}$ such that
\begin{eqnarray} x \equiv x_0 ( \mbox{mod } p^k ) & \mbox{ and } & F ( x ) \equiv 0 ( \mbox{mod } p^k ) \nonumber\\ \mbox{WLOG} & \Updownarrow & \nonumber\\ x = x_0 + tp^k, t \in [ 0 ; p - 1 ] & \mbox{ and } & F ( x ) = Ap^k, A \in \mathbb{Z} \end{eqnarray}
If we do not assume this then $x \not \in S_F$. Hence it suffice to determine how many $x$'s with these assumptions satisfy the additional requirement $F ( x ) \equiv 0 ( \mbox{mod } p^{k + 1} )$, to obtain the cardinality of $S_F$.

Since $x \equiv x_0 ( \mbox{mod } p^k )$, by the lemma
\begin{eqnarray*} F ( x ) & \equiv & F ( x_0 ) + ( x - x_0 ) F' ( x_0 ) ( \mbox{mod } p^{2 k} ) \end{eqnarray*}
\begin{eqnarray*} F ( x ) & \equiv & F ( x_0 ) + ( x - x_0 ) F' ( x_0 ) ( \mbox{mod } p^{k + 1} ) \end{eqnarray*}
Hence we have $F ( x ) \equiv 0 ( \mbox{mod } p^{k + 1} )$ if and only if
\begin{eqnarray*} F ( x_0 ) + ( x - x_0 ) F' ( x_0 ) & \equiv & 0 ( \mbox{mod } p^{k + 1} )\\ Ap^k + ( x_0 + tp^k - x_0 ) F' ( x_0 ) & \equiv & 0 ( \mbox{mod } p^{k + 1} )\\ Ap^k + tp^k F' ( x_0 ) & \equiv & 0 ( \mbox{mod } p^{k + 1} )\\ A + tF' ( x_0 ) & \equiv & 0 ( \mbox{mod } p ) \end{eqnarray*}
[b]1.[/b] If $p \not | F' ( x_0 )$, then by Lemma 1 for each $A$ there is exactly one $t$ such that $A + tF' ( x_0 ) \equiv 0 ( \mbox{mod } p )$ holds.
Whence we obtain a unique $x = x_0 + tp^k$ satysfying our requirement in $( 1 )$, and such that $F ( x ) \equiv 0 ( \mbox{mod } p^{k + 1} )$. And so $\# S_F = 1$.

[b]2.[/b] If $p|F' ( x_0 )$ and $p|A$ (equivalently $p^{k + 1} | Ap^k = F ( x_0 )$), then for any $t \in [ 0 ; p - 1 ]$ the equation $A + tF' ( x_0 ) \equiv 0 ( \mbox{mod } p )$ holds.
Hence we obtain $p$ solutions : $x_0, x_0 + p^k, \ldots, x_0 + ( p - 1 ) p^k$ satysfying $F ( x ) \equiv 0 ( \mbox{mod } p^{k + 1} )$ and our requirement (1). So $\# S_F = p$.

[b]3.[/b] If $p|F' ( x_0 )$ and $p \not | A$, then for all $t \in [ 0 ; p - 1]$, we have $A + tF' ( x_0 ) \not \equiv 0 ( \mbox{mod } p )$.
Hence there is no $x$ satysfying our requirement (1) and such that $F ( x ) \equiv 0 ( \mbox{mod } p^{k + 1} )$. So $\# S_F = 0$.

[b]Corollary 1.[/b] Let $F ( X ) \in \mathbb{Z} [ X ]$. Let $p$ be a prime number such that
\begin{eqnarray*} F ( x ) \equiv 0 ( \mbox{mod } p ) & \mbox{ and } & F' ( x ) \equiv 0 ( \mbox{mod } p ) \end{eqnarray*}
has no common solutions. Then for all $k = 1, 2, \ldots$ the number of solution
\begin{eqnarray*} F ( x ) \equiv 0 ( \mbox{mod } p ) & \mbox{ and } & F ( x ) \equiv 0 ( \mbox{mod } p^k ) \end{eqnarray*}
is equal.

Now apply the corollary to polynomials $F ( X ) = X^n - a$ with $a$ and $n$ such that $p \not | an$, to obtain the claim.
@ZetaX: I'm quite uncertain about that last line, since you say that $a$ and $n$ need to be coprime, when I believe that $p \not | an$ should suffice... Anyway I will correct my previous post, as soon as I will clear my own contradictions relating the subject :)
@others: If the proof seems clumsy, then it's probably true. I'll try to find better ways of writting it down. Also I'm in a mood in which I know I make frequently mistakes, so I hope not this time ...

Thanks {x}.
I'll make addition...
Claim
Len $n>1$ is a positive integer. If $a$ is an integer for which $x^{n}\equiv\ a(mod p)$ has solution for all prime numbers $p>V$ where $V$ is some positive integer,then
(i)$a=b^n$ or
(ii)8 is divisional of $n$ and $a=2^{\frac{n}{2}}b^n$ for some $b$.

This claim has been proved by E. Trost in 1934.
It is interesting that the cases $n=2,4$ can be proved by elementary knowledge in the theory of quadratic residuals.
If anyone is interested I can post the proof ;)

The case $n=2$ was posted before (take a big $q$): http://www.mathlinks.ro/Forum/viewtopic.php?t=64322
(I think $n=4$ will be similar)

[quote="ZetaX"]
I think $n=4$ will be similar[/quote]
You are right ;)

[quote="bilarev"]The problem 6 of IMO 2003 can be solve immediately if the following Conjecture(Emil Artin) is proved:
If $a>1$ is squarefree then exist infinitely many primes $p$ for which $a$ is a primitive root $mod p$.[/quote]
Note that it was (as much as I know) already proven that there are at most two exceptions.

[quote="ZetaX"]
Note that it was (as much as I know) already proven that there are at most two exceptions.[/quote]
See http://mathworld.wolfram.com/ArtinsConstant.html ;)

[quote="bilarev"] It is interesting that the cases $n=2,4$ can be proved by elementary knowledge in the theory of quadratic residuals.
If anyone is interested I can post the proof ;)[/quote]
Do you have the proof in the general case ? (I hope it's not too long)
I'm interested about it :)

Problem
(1)                                                     $x^n\equiv a(modp)$
has solutions for every prime $p>V$.
[color=blue]Preposition 1[/color]
Let $a,n$ are positive integers. If the problem is realized,then the polynomial $f(x)=x^n-a$ is reducible in $Q(\xi)$, where $\xi$ is nth primitive root of unity.
[color=blue]Preposition 2[/color]
If the problem is realized and if $w$ is a root of $f(x)=x^n-a$ , then $Q(w)$ is normal over $Q$.
[color=blue]Preposition 3[/color]
Let $f(x)=x^n-a$ and $a=p^{\alpha{}_1}{}_{1}p^{\alpha{}_2}{}_{2}...p^{\alpha{}_s}{}_{s}$. If $1=(n,\alpha'_1,...,\alpha'_s)$. then $f(x)$ is irreducible over $Q$.

Here is one proof of the case n=2 http://www.mathlinks.ro/Forum/viewtopic.php?t=64322 .
The case n=4 is similar.
We can cosider only the case a>0 because if n is even we proved that a is a square and if n is odd then (1) msut have solutions with -x.
Lets propose that $a\neq b^n$ and $a=p^{\alpha{}_1}{}_{1}p^{\alpha{}_2}{}_{2}...p^{\alpha{}_s}{}_{s}$. If $d=(n,\alpha_1,...,\alpha_s)$, then $a=b^d$ for some positive integer b and $d<n$ and if $b=p^{\alpha'{}_1}{}_{1}p^{\alpha'{}_2}{}_{2}...p^{\alpha'{}_s}{}_{s}$ and $n=dn'$. Then $1=(n,\alpha'_1,...,\alpha'_s)$.According to Preposition 3 teh polynomial $f(x)=x^n'-b$ is irreducible over $Q$. If $w$ is real root of $f(x)$($w$ exists because $b>0$), then $w^n'=b$ or $w^n=b^d=a$. According to Preposition 2 it follows that $Q(w)$ is normal over $Q$.But if $n'>2$ then $f(x)=x^n'-b$ has a complex root which is in $Q(w)$-contradiction because $Q(w)$ is normal over $Q$. We have that $d<n$ and therefore $n'=2$ and $a=b^\frac{n}{2}$.
If $n=2m, (m,2)=1$, then $a=c^2$(n-even) and $a=b^m$. Thus $a=b^m=c^2=(d{}^2){}^m=d^n$. If $n=4m$ for m-odd- analogical.
If $n=2^km, (m,2)=1,k\geq3$ therefore $a=b{}^{2{}^{k-1}m}$. Lets $b=ch^2$, where c is squarefree.According to Preposition 1 we have, that $\sqrt{c}^m\in Q(\xi)$ where $\xi$ is primitive $2^k-th$ root of unity.But m is odd therefore $\sqrt{c}\in Q(\xi)$. But the only real subfield of $Q(\xi)$ is $Q(\sqrt{2})$. Thus $c=2$ and $a=2^\frac{n}{2}b^n$ which we had to prove ;)


Determine all functions $f: \mathbb R \to \mathbb R$ such that
\[f(x\minus{}f(y))\equal{}2f(x)\plus{}x\plus{}f(y)\quad, \forall x,y \in \mathbb R.\]

[quote="Victory.US"]determine all fuction $ R \to R$ such that :
$ f(x \minus{} f(y)) \equal{} 2f(x) \plus{} x \plus{} f(y), \forall x,y \in R$[/quote]

Let $ P(x,y)$ be the assertion $ f(x\minus{}f(y))\equal{}2f(x)\plus{}x\plus{}f(y)$
Let $ a\equal{}f(0)$

$ P(f(\minus{}2a),\minus{}a)$ $ \implies$ $ f(f(\minus{}2a)\minus{}f(\minus{}a))\equal{}2f(f(\minus{}2a))\plus{}f(\minus{}2a)\plus{}f(\minus{}a)$
$ P(f(\minus{}2a),\minus{}2a)$ $ \implies$ $ a\equal{}2f(f(\minus{}2a))\plus{}2f(\minus{}2a)$ and the previous line becomes $ f(f(\minus{}2a)\minus{}f(\minus{}a))\equal{}a\plus{}f(\minus{}a)\minus{}f(\minus{}2a)$

$ P(\minus{}a,0)$ $ \implies$ $ f(\minus{}2a)\equal{}2f(\minus{}a)$ and so $ f(\minus{}2a)\minus{}f(\minus{}a)\equal{}f(\minus{}a)$ and the previous line becomes $ f(f(\minus{}a))\equal{}a\minus{}f(\minus{}a)$

$ P(f(\minus{}a),\minus{}a)$ $ \implies$ $ a\equal{}2f(f(\minus{}a))\plus{}2f(\minus{}a)$ and so $ f(f(\minus{}a))\equal{}\frac a2\minus{}f(\minus{}a)$

Comparing the two previous lines, we get $ a\equal{}0$

Then $ P(x,0)$ $ \implies$ $ f(x)\equal{}\minus{}x$ and it is easy to verify that this indeed is a solution.

Hence the unique solution $ \boxed{f(x)\equal{}\minus{}x}$ $ \forall x$

$ f(x \minus{} f(y)) \equal{} 2f(x) \plus{} x \plus{} f(y)$, $ \forall x,y \in R$
then $ f(x\minus{}f(x))\minus{}2f(x)\minus{}f(y)\equal{}x$
set $ y\equal{}y_0$ then  $ f(x\minus{}f(y_0))\minus{}2f(x)\minus{}f(y_0)\equal{}x$

$ x \in R$ thus forall $ t\in R$ there exist $ u,v$ such that $ t\equal{}f(u)\minus{}2f(v)$

it 's nice way,too :P

[quote="Victory.US"]$ f(x \minus{} f(y)) \equal{} 2f(x) \plus{} x \plus{} f(y)$, $ \forall x,y \in R$
then $ f(x \minus{} f(x)) \minus{} 2f(x) \minus{} f(y) \equal{} x$
set $ y \equal{} y_0$ then  $ f(x \minus{} f(y_0)) \minus{} 2f(x) \minus{} f(y_0) \equal{} x$

$ x \in R$ thus forall $ t\in R$ there exist $ u,v$ such that $ t \equal{} f(u) \minus{} 2f(v)$[/quote]
I'm sorry but I dont understand at all your nice way  :blush:  :

The second line is obviously wrong and must be either  $ f(x \minus{} f(x)) \minus{} 3f(x) \equal{} x$, either  $ f(x \minus{} f(y)) \minus{} 2f(x) \minus{} f(y) \equal{} x$

The third line is just the problem statement.

I dont understand how you got $ t \equal{} f(u) \minus{} 2f(v)$ (but it's easy to get $ t \equal{} f(u) \minus{} 3f(v)$

And I dont understand hou you get the result $ f(x)\equal{}\minus{}x$ from $ t \equal{} f(u) \minus{} 2f(v)$ (if you get another proof for) or even from $ t \equal{} f(u) \minus{} 3f(v)$ (which is easy to prove)

Could you please, give us some precisions.
Thanks.

[quote="Victory.US"]i made some mistake In latex.sorry :blush:
it must be $ f(x \minus{} f(y)) \minus{} 2f(x) \minus{} f(y) \equal{} x$
Let $ y \equal{} 0$ then denote $ f(0) \equal{} a$ we have $ f(x \minus{} a) \minus{} 2f(x) \equal{} x \plus{} a$ ,for all $ x\in R$

the right have value in $ R$ then the left hve value in $ R$, then for all $ t \in R$ there exist $ u,v$ and $ f(t) \equal{} f(u) \minus{} 2f(v)$                                              .(1)

take $ x$ by $ f(y)$ then$ f(f(x)) \equal{} \minus{} f(x) \plus{} \frac {a}{2}$   (2)
thus take $ x$ by $ f(x)$ then $ f(f(x) \minus{} f(y)) \equal{} \minus{} (f(x) \minus{} f(y)) \plus{} a$
take $ x \equal{} f(x) \minus{} f(y)$ then $ f(f(x) \minus{} 2f(y)) \equal{} \minus{} (f(x) \minus{} 2f(y)) \plus{} 2a$    .(3)

from (1) and (3) we have $ f(t) \equal{} f(f(u) \minus{} 2f(v)) \equal{} \minus{} (f(x) \minus{} 2f(y)) \plus{} 2a \equal{} \minus{} t \plus{} a$
which $ f(x) \equal{} \minus{} x \plus{} 2a$, for all x in R. and from (2) lead to $ a \equal{} 0$ then $ f(x) \equal{} \minus{} x$

$ f(x) \equal{} \minus{} x$ solution to the equation.[/quote]

Ok, I undertand.
Thanks.


This one of many upcoming graphs that I made a while back. Don't bother trying to find the equations, there is more than one graph. :D

This is one I made using ppt and paint. :lol:

This is a really cool green light graph i made. I forgot what my basic theme was when I made it though.  :P

Guess what they are? :P
[hide="From left to right"]boy,sign,Christmas tree, and the sun. :lol: [/hide]