How to find large prime factors without using computer? What is the largest prime factor of the number 600851475143 ?
This is the third problem of Project Euler.

How to approach this mathematically (without computer programming) ?

Well the point of Project Euler is to program. This is a problem that you could solve by hand but it would take you quite a while.

Factorisation is not a simple thing to do by hand for numbers this big (unless you have some special insight into divisibility by certain special primes).

Just use the bog standard test, square root and check divisibility of primes upto this. Once you find one, divide out and start again. In the end you will have a number that you cannot do this process to. This will be the largest prime factor.

You can use the free R software for this (using the 'gmp' package)

  factorize(600851475143)

Big Integer ('bigz') object of length 4:

[1] 71   839  1471 6857

Hence 600851475143 = 71 * 839 * 1471 * 6857


What is the meaning of the PI function. I am solving for a configuration problem and i have seen a function π
This is a function not 3.14 which is the value of pi. While accessing some lectures i found out that they also call this symbol as product of something. I don't have much to show for it but here's the symbol .

Please lead me to some resource.

Maybe it's the product function $\Pi_{i=0}^{n}x_i\equiv x_0 \cdot x_1 \cdot \ldots \cdot x_n$. See https://en.wikipedia.org/wiki/Product_(mathematics)

There's also the number theory use, where $\pi(x)$ is the number of primes less than or equal to $x$. See https://en.wikipedia.org/wiki/Prime-counting_function

As most of us know, Pi is defined as the ratio of a circle’s diameter to its circumference. As a retired engineer, l still have it memorized to 7 decimal points, ie 3.1415926. It is called a transcendental number, or function, because using finite math it Never divides out. In (about) 1990, MIT used a Cray supercomputer to see if the machine could finish in a day. It could not... even after 10e670,000,000,000+/- permutations. (l honestly don’t remember how many orders of magnitude it ran but it certainly convinced me.) The most recent and accurate attempt was In 2014: the world record was a computer that calculated Pi (π) correctly to 13,300,000,000,000 decimal places.
Many mathematicians now call it an “indefinite finite” function, or an “irrational” number, but to me it is asymptotic. Ask your pc to find sq rt 145 and you will see similar results. There are lots of them out there.  Fortran (or formula translation) language run on a mainframe will generally throw you out after 10e7 with an error code saying Excceeds Maximum Allowed Permutations.
For the record, the formula used for calculating pi is:
Gregory-Leibniz Series:
\frac{\pi}{4}=1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\frac{1}{9}-\ldots.  Written non-code: pi/4=1-1/3+1/5-1/7+1/9-...  Notice the denominators are prime numbers.
Where frac = fraction
And ldots   = ellipsis (continue series - ...)
If one uses this method he or she will quickly substitute ldots with lDIOTS for it’s tedious nature is... Tedious    :-)
There are about five accepted formulas but l consider the G-L series the most fundamentally beautiful.  Hope this helped.


Triple integral visualisation problem with a sphere and a cylinder Write a triple integral in cylindrical coordinates for the volume of the solid cut from a ball of radius 2 by a cylinder of radius 1, one of whose rulings is a diameter of the ball.

I am unable to understand how to get $z=f(r,\theta)$ and the limits.
Any help would be appreciated

Hint:

The better way to solve this problems to use cylindrical coordinates.

The sphere of center $(0,0,0)$ and radius $2$ has equation: $r^2+z^2=4$ and, without loss of generality, we can assume that cylinder has the axis parallel to the $z$ axis , and center at $(0,1,0)$ and radius $1$ so it has equation: $r=2\sin \theta$.
this means that the limits of the volume limited by the sphere and the cylinder are:
$$
0\le \theta \le 2\pi \qquad 0\le r \le 2 \sin \theta \qquad-\sqrt{4-r^2}\le z \le \sqrt{4-r^2}
$$

so, using the symmetries of the figure, the volume is:
$$
V=4 \int_0^{\frac{\pi}{2}}\int_0^{2\sin \theta}\int_0^{\sqrt{4-r^2}}rdzdrd\theta
$$
where $rdzdrd\theta$ is the volume element in cylindrical coordinates.

can you do from this?

The equation for the ball is
$$
x^2 + y^2 + z^2 = 2^2
$$
and we have a cylinder inside this ball with radius 1, this would give the limits:
$$
0 \le r \le 1\\
0 \le \theta \le 2\pi
$$
since the radius is 1 and a cylinder has a circular bottom which is a "full lap" around the unit circle hence the $2\pi$
The height of the cylinder is
$$
4^2 - 2^2 = h^2 \Rightarrow h = \sqrt{12}
$$
you can draw a rectangle inside a circle and get a triangle with cathetus 2 (radius = 1) and h (the unknown). The diagonal is the diameter of the circle which is 4. Since the cylinder is stationed in the origin, z has the limits $$-\frac{\sqrt{12}}{2} \le z \le\frac{\sqrt{12}}{2}$$
Which would give you the integral
$$
\int_{\theta=0}^{2\pi} \int_{z=-\frac{\sqrt{12}}{2}}^{\frac{\sqrt{12}}{2}}\int_{r=0}^{1}(r^2 + z^2)r \cdot drdzd\theta
$$
I might have made some mistake somewhere, but hope this helps you anyway!


probability - Understanding range of probability density function Consider:$$f_{X,Y}\left(x,y\right)\:=\:\begin{pmatrix}8xy & 0\le x\le y\le 1 \\0 & otherwise\end{pmatrix}$$
I want to calculate $f_X\left(x\right)$, $f_Y\left(y\right)$, the expectations of them, and $E\left[XY\right]$.

But, i don't how to determine the range of the integrals for each $f_X\left(x\right)$, $f_Y\left(y\right)$. What is the rule? (for example, for $f_X\left(x\right)$, i need to do $\int _0^1f_{X,Y}\left(x,y\right)dy\:$ or $\int _x^1f_{X,Y}\left(x,y\right)dy\:$?)
tnx!

$f_X(x)=\int_x^1f_{X,Y}(x,y)dy$. Why? If you integrate from $0$ to $1$ you are saying that $x=0$ which is not well deduced.

The definition, in this case, of the marginal distribution $F_X(x)$ is
$$F_X(x) = \int_{-\infty}^\infty f(x,y)\,dy.$$

From the domain of definition of your pdf, this simplifies to the integral $\int_0^1 f(x,y)\,dy$.  Do you see why?


How to explain this quirk of the chain rule? Assume I have a function $f = f(y, \phi(y,x))$ and I want to calculate $\frac{\partial f}{\partial y}$, I use the chain rule to get

\begin{equation}
\frac{\partial f}{\partial y} = \frac{\partial f}{\partial y} + \frac{\partial f}{\partial \phi}\frac{\partial \phi}{\partial y}
\end{equation}

but obviously the $\frac{\partial f}{\partial y}$ represent different things on each side of equality. How do I explain this? I'm guessing it is a notational issue.

Edit: Just to give some context why this troubles me. Here $x_i$ refers to the ith component of the vector $\mathbf{x}$ in euclidean space. In an acoustic textbook the Lighthill stress tensor $T_{ij}$ is involved in the following identity:

\begin{equation}
\frac{\partial}{\partial x_i} \frac{T_{ij}(\mathbf{y},t-|\mathbf{x}-\mathbf{y}|/c)}{|\mathbf{x}-\mathbf{y}|} = \frac{\frac{\partial T_{ij}}{\partial y_i}}{|\mathbf{x}-\mathbf{y}|} - \frac{\partial}{\partial y_i} \frac{T_{ij}(\mathbf{y},t-|\mathbf{x}-\mathbf{y}|/c)}{|\mathbf{x}-\mathbf{y}|}  \end{equation}

This can only be resolved if the numerator in the term $\frac{\frac{\partial T_{ij}}{\partial y_i}}{|\mathbf{x}-\mathbf{y}|}$ is given a different interpretation...Just try showing this:

Let $t-|\mathbf{x}-\mathbf{y}|/c = \phi(t,\mathbf{x}, \mathbf{y})$

\begin{array}{lcl}
\frac{\partial}{\partial x_i} \frac{T_{ij}(\mathbf{y},\phi)}{|\mathbf{x}-\mathbf{y}|} & = & \frac{1}{|\mathbf{x}-\mathbf{y}|} \frac{\partial}{\partial x_i}T_{ij}(\mathbf{y},\phi) + T_{ij}(\mathbf{y},\phi) \frac{\partial}{\partial x_i} \frac{1}{|\mathbf{x}-\mathbf{y}|}  \\
& = &  \frac{1}{|\mathbf{x}-\mathbf{y}|} (\frac{\partial T_{ij}}{\partial \phi}\frac{\partial \phi}{\partial x_i}) + T_{ij}(\mathbf{y},\phi) \frac{\partial}{\partial x_i} \frac{1}{|\mathbf{x}-\mathbf{y}|}\\
& = &  -\frac{1}{|\mathbf{x}-\mathbf{y}|} (\frac{\partial T_{ij}}{\partial \phi}\frac{\partial \phi}{\partial y_i}) + T_{ij}(\mathbf{y},\phi) \frac{\partial}{\partial x_i} \frac{1}{|\mathbf{x}-\mathbf{y}|}
\end{array}

\begin{array}{lcl}
\frac{\partial}{\partial y_i} \frac{T_{ij}(\mathbf{y},\phi)}{|\mathbf{x}-\mathbf{y}|} & = & \frac{1}{|\mathbf{x}-\mathbf{y}|} \frac{\partial}{\partial y_i}T_{ij}(\mathbf{y},\phi) + T_{ij}(\mathbf{y},\phi) \frac{\partial}{\partial y_i} \frac{1}{|\mathbf{x}-\mathbf{y}|}  \\
& = &  \frac{1}{|\mathbf{x}-\mathbf{y}|} ( \frac{\partial}{\partial y_i}T_{ij} +\frac{\partial T_{ij}}{\partial \phi}\frac{\partial \phi}{\partial y_i}) - T_{ij}(\mathbf{y},\phi) \frac{\partial}{\partial x_i} \frac{1}{|\mathbf{x}-\mathbf{y}|}
\end{array}

Adding up the last line from each expression gives the result.

Let's use a different notation: for a function of two variables $f$, denote by $\partial_1f$ and $\partial_2f$ the first-order derivatives of $f$ with respect to the first and second variable respectively, namely:
\begin{align*}
\partial_1f(x,y)&=\lim_{h\to0}\frac{f(x+h,y)-f(x,y)}h,&
\partial_2f(x,y)&=\lim_{h\to0}\frac{f(x,y)-f(x,y+h)}h.
\end{align*}
Now, from the chain rule,
$$\frac{\mathrm{d}}{\mathrm{d}y}\Bigl(f\bigl(y,\phi(y,x)\bigr)\Bigr)
=\partial_1f\bigl(y,\phi(y,x)\bigr)+\partial_1\phi(y,x)\partial_2f\bigl(x,\phi(y,x)\bigr),$$
where
$$\frac{\mathrm{d}}{\mathrm{d}y}\Bigl(f\bigl(y,\phi(y,x)\bigr)\Bigr)=\lim_{h\to0}\frac{f\bigl(y+h,\phi(y+h,x)\bigr)-f\bigl(y,\phi(y,x)\bigr)}{h}.$$

In fact, I try to always be careful to what I'm writing and what I really mean. First, I'm careful to never say the function f(x), but the function $f$ (unless $f$ is a function with codomain a set of functions). At best, $f(x)$ is an expression that depends on $x$.

Then I use symbols like $\partial_1$, $\partial_2$, etc. for functions, and things like $\dfrac{\mathrm{d}}{\mathrm{d}x}$ or $\dfrac{\partial}{\partial x}$ for expressions (though, in fact, it's slightly more complicated).

(Hence, I hate when people say something like [something] is a function of $x$. Heck, what does it mean to be a function of $x$? you're a function or you're not, you can't be a function of $x$; at best, you're an expression that depends on $x$).

Then there's something I like to do: take a function $f$ of two variables and define the function $g$ by
$$g(y,x)=f(x,y).$$

Then I like to ask this question: with your notation, what sense do you give to
$$\frac{\partial g}{\partial x}?$$
or to any other variation on the theme:
$$\frac{\partial g(x,y)}{\partial x},\ \frac{\partial g}{\partial x}(x,y),\ \ldots$$

It would seem you have encountered a typing error.  The left f is merely the label and the right side reveals some structure, yet it carries the same label.  So differentiating both sides eliminates the quantity sought.  This makes no sense.  What would make more sense is if the label on the left were given as g, then your computation provides an answer.  The problem is that the given equation is self-referencing and thus it leads nowhere.


what are some of the methods to do divergent/convergent? I have no problem with integration finding volumes, surface area and such. But the whole series / sequence chapters completely throw me off, I have no idea where to even begin with problems given. What is the strategy for dealing with series/sequences?

for example, I don't even know where to begin with this one:

\begin{equation} \sum_{n=1}^\infty \frac{1}{n^{\ln{n}}} \end{equation}

Sorry if this is discouraging, but basically the strategy is: trial and error.  You need to know things like the comparison test, ratio test, root test, integral test, alternating series test and any others you come across, but there is no definitive answer for which one to use in any particular case.  A couple of suggestions:

if the term $a_n$ includes factorials, the ratio test may be worth a try;
for rational functions the comparison test (perhaps in the limit form) might be good.

You also need to know the comparative rates of growth of various functions, starting with things like
$$\hbox{constant}<\ln n<n^\alpha<a^n<n!$$
for large $n$.

For the specific example you have asked, just note that $\ln n>2$ for $n\ge8$ and then use a comparison test.

Comparison test can be used. Since $\ln n > 2$ for $n\ge 9$ it follows $\displaystyle{\sum_{n=9}^{\infty}\frac{1}{n^{\ln n}}<\sum_{n=9}^{\infty}\frac{1}{n^2}}$, which is a convergente series.


Trigonometric functions for complex numbers I thought I had defined what cos(ai) and sin(ai) was earlier today when I did the following:

$e^{(vi)} = \cos(v) + i\sin(v)$
If we let $v = ai$, where a is real, we get:
$e^{(aii)} = \cos(ai) + i\sin(ai) = e^{(-a)}$
Since $e^{(-a)}$ is a real number, the $i\sin(ai)$ must be 0, and therefor $\cos(ai)$ must be $e^{(-a)}$.
So I have concluded that $\cos(ai) = e^{(-a)}$ and $\sin(ai) = 0$

I am pretty sure this is wrong since I have seen different answers online, but I would like to know what I did wrong.

Thanks

It's worth knowing these identities:

$$\cos it = \cosh t$$
$$\sin it = i \sinh t$$

I presume you are familiar with the hyperbolic functions $\cosh$ and $\sinh$. These are usually defined as $\cosh t \equiv \frac12(e^t+e^{-t})$, and $\sinh t \equiv \frac12(e^t-e^{-t})$.

These functions have properties which parallel those of the circular functions.

So, it is indeed true that $\cos it$ is a real number when $t$ is real.

Addendum: An easy way to remember this is that it is completely analogous to how the sign is handled with circular functions: $\cos(-t)=\cos t$ and $\sin(-t)=-\sin t$.

The thing is $\sin{(ai)}$ is complex and not real, so you cannot say $\cos{(ai)}$ and $\sin{(ai)}$ both equal to zero.


What is the number of possible $ x$ values in $\frac{x}{100}= \sin(x)$ Problem
 $\frac{x}{100}= \sin(x)$ We are asked to find the number of possible values of $x$ in this scenario and I had tried to figure it out by the use of trigonometric identities but then i had realized that there are no trig identities that can help me... or is there?

steps that i had tried:
I first multiplied 100 on both sides to get $x$ by itself to get:
$100(\sin x)=x$

Then i determined that $\sin x \le 1$ therefore I had determined that $\frac{x}{100}$ is $\le 1$

But when i look at the answer choices all of them are less than $100$ meaning that all of them are going to make $\frac{x}{100}$ less than 100 when $x$ is substituted.

Since $|\sin x|\le 1$, one needs only to consider $\frac{|x|}{100} \le 1$, or $|x|\le 100$. Since both functions are odd, we restrict ourselves to the interval $[0,100]$. The curve

$$\tag{1} y = \frac{ x}{100}$$

is positive on $(0,100]$. $\sin x$ is periodic with period $2\pi$. On each (half) period

$$[0,\pi], [2\pi, 3\pi], \cdots [2n\pi, (2n+1)\pi]$$

as long as $(2n+1) \pi <100$, the curve $(1)$ intersects $\sin x$ at $2$ points. Since $15.5< 100/2\pi <16$, this means that there are $32$ nonnegative solution and thus $63$ solution in the real line.

look at this site body must be [1]: https://www.wolframalpha.com/input/?i=x%2F100%20%3D%20sin(x)


What is the sum of this fraction series? $$\frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \frac{1}{9} + \frac{1}{11} .... + \frac{1}{99}?$$ Is there a way to do without calculation? I would appreciate an answer that gives an easy way to find this sum.

Define $$H_k=\frac{1}{1}+\frac{1}{2}+\cdots+\frac{1}{k}$$

These are called harmonic numbers.  Then your sum is $H_{100}-\frac{1}{2}H_{50}-1$.

If you're happy with an approximation, we know that $H_k\approx \ln k + \frac{1}{2k}+\gamma$, where $\gamma\approx  0.5772156$.  Hence your answer is approximately $\ln 100 + \gamma-0.5 \ln 50 -\frac{\gamma}{2}-1\approx 1.93776648$

You can get an exact answer on Wolfram Alpha, but it isn't particularly nice.  The above approximation is correct to four decimal places.

You could probably use simple sequence addition then simplify afterwords,
For example $1+3+5......99$ is equivalent to $((99+1)/2)^2$ which is $2500$ so the denominator would be $2500$ then find the number of terms and add the numerator.


In $\triangle ABC$, if $\angle B=60^\circ$ and $\sin A\sin C=\lambda$, then what is the range of $\lambda$? In $\triangle ABC$ if $\angle B=60^\circ$ and $\sin A\sin C=\lambda$, then what is the range of $\lambda$?

Try: Using $$\cos B=\frac{a^2+c^2-b^2}{2ab}$$

So $a^2-ac+c^2=b^2$. From $\sin A\sin C=\lambda$, substitute $$ac=4R^2\lambda$$
where $R$ is circumradius of $\triangle ABC$.

Could some help me how to calculate $\lambda$? Thanks.

$$\sin A\sin C=\frac12\bigg(\cos(A-C)-\cos(A+C))=\frac12\bigg(\cos D+\frac12\bigg)$$ where $D=|A-C|$ which lie between $0^\circ$ to $120^\circ$
So $-\frac{\sqrt3}2 \leq \cos D \leq 1$

So the range is from $\bigg[\frac{1-\sqrt3}4, \frac34\bigg]$


Is $\mathbb{Q}(\sqrt{2}, \sqrt{3})$ a normal extension? I want to reason as to whether $K=\mathbb{Q}(\sqrt{2}, \sqrt{3})$ is a normal extension over $\mathbb{Q}$. There are competing definitions and so my question is re-phrased as:

Is it true that for every irreducible polynomial $f \in \mathbb{Q}[X]$ which has (at least) one root in $K$, $f$ splits completely in $K$?

Any help that can be offered is appreciated.

Yes, it is. A basic theorem in Galois theory says that a finite extension $E \supseteq F$ is normal and separable if and only if $E$ is the splitting field of a separable polynomial $f(X) \in F[X]$.

It suffices to consider $f(X) = (X^2-2)(X^2-3)$. Its splitting field must contain $\sqrt{2}$ and $\sqrt{3}$, and since $K$ is the smallest field containing both of them, $K$ must in fact be the splitting field of $f(X)$. Therefore $K$ is normal over $\mathbb{Q}$.

If we consider $F=\mathbb{Q}[{2^{\frac{1}{3}}}]$, then $f=x^3-2$ has a root in $F$. However, the other two roots are complex. (Why?) But $F\subseteq \mathbb{R}$.
Hence $f$ cannot split over $F
$.


Approximating next prime number Suppose that there is a prime number. Now I want to approximate the next prime number. (It does not have to be exact.) What would be the time-efficient way to do this?

Edit: what happens if we limit the case to the prime number of the form $4k+1$ where k is a natural number?

Edit: it's fine to replace approximate prime number with finding any prime number that is bigger than the given prime number in a time-efficient way.

You could use the fact that the density of primes around $p$ is about $\frac 1{\ln p}$ to say the next is around $p + \ln p$, but the variance on this estimate is huge.  For $4k+1$ primes, the density is about the same as $4k+3$ primes, so the estimate would be $p + 2 \ln p$.

To find the next, just start from $p$ and check all numbers of the form $6k+1$ or $6k+5$ until you find one.  You shouldn't have to check toooo many. (On average, $\frac {\ln p}3$)

To find any larger prime, just search the Web for the largest known prime.

well.. an exact calculation could be provided by: $p(n)=(f(n-1)/f(n))*(p(n-1)-1)$ where f(n) is defined as $π(n)$ in this question: Expected smallest prime factor

Well besides that an approximation of the previous formula could be: $ p(n)=(ln(n+1)/ln(n-1))*((ln(n)-ln(n-1))/(ln(n+1)-ln(n))*(p(n-1)-1)$

I will come back  with some more infos.

I hope i've helped


Algebraic topology question (Qual) I am having trouble with a QR problem.  I would appreciate some help. Construct a connected $CW$-complex $X$ with $H_0(X, \mathbb{Z}) =
\mathbb{Z}, H_1(X, \mathbb{Z}) = \mathbb{Z}\times \mathbb{Z}/10\mathbb{Z}$ and $H_2(X, \mathbb{Z}) = \mathbb{Z}
\times \mathbb{Z}.$

Can you first find a connected space with $$H_1(X,Z) = \mathbb{Z}_{10}$$ and $$H_2 = 0$$

How about a connected space with $$H_1 = \mathbb{Z}$$ and $$H_2 = \mathbb{Z} \times \mathbb{Z}$$

Then maybe you can find a way to combine these spaces?

Hint: Make use of the Kunneth formula for two spaces where one of them has trivial $n$th-degree homology.


Factor quadratic equation formula $ax^2+bx+c=(dx+e)(fx+g)$, and my goal is to find a formula to find $d,e,f,$ and $g$ when given $a,b,$ and $c$ and that also works for complex numbers

Without loss of generality the standard quadratic factors as ...
$$ ax^2+bx+c=a(x-d)(x-e) $$

where $d$ and $e$ are the two solutions you get from the quadratic formula)

By comparing the coefficients, we have
$$c=eg$$
$$a=df$$
$$b=dg+ef$$

There are three equations but four variables namely $d,e,f$ and $g$. So, you can not get a unique solution.


If the partial derivatives are continuous then the function is differentiable in the context of 3 dimensions Context: This question has been bugging me for a while, mainly due to no knowledge of linear algebra and availability of only an ugly book Stewart's Calculus. There is a sufficient condition for a function $f(x,y)$ to be differentiable at $(x_0,y_0)$. According to Stewart, the partial derivatives have to be continuous at $(x_0,y_0)$. (But, I saw in other places that they have to be continuous in an open region. (Anyways clarify this issue, first.)) I need to prove that it is a sufficient condition without the use of linear algebra.

Sidenote: For the definition of differentiability for function of two variables, I would use the precise limit definition instead of Stewart's approximation definition.

Trials: I have proved the theorem for every linear path. It is not that difficult. But, I am certain that it is not sufficient. I do not have any intuition of the problem. Just manipulated the definitions to suck out something significant.

Thank you for your help.

You can construct a function $f: \mathbb{R}^2 \to \mathbb{R}$ where the partial derivatives are continuous at $\vec0$, but $f$ isnt even continuous there. Let $C$ denote the closed circle with radius 1 centered $(0,1)$ and define $f:\mathbb{R}^2 \to \mathbb{R}$ as
$$f(x) = \begin{cases}1,&x\in C \mbox{ or } x_2 \leq 0 \\
0, & \mbox{otherwise}\end{cases}.$$

You can prove that for every vector $v \in \mathbb{R}^2$, there is an $\epsilon>0$ such that $f$ is constant on the line segment $L=\{av: -\epsilon < a< \epsilon\}$. Therefore, all directional derivatives at the origin (including partial derivatives) are 0, and are continuous. However, $f$ isnt even continuous at the origin let alone differentiable.

So, I think you are right in saying that the partial derivatives being continuous only at one point is not sufficient.


Imaginary to the power of fractional number I am sorry if it's stupid, but I don't know how to calculate imaginary number "$i$" power to fractional number. I know:

$$\begin{aligned}
i^2 &= -1\\
i^3 &= \;\;\;i \\
i^4 &= -1
\end{aligned}$$

and so on. I know that multiplying a complex number by "$i^n$" rotates the magnitude vector of that complex number, like: $i(a+bi)$ rotates for $90$ degrees, $i^2(a+bi)$ rotates it for $180$ degrees, to the power of $3$ rotates for $270$ degrees... and so on. And I can even know how to calculate it:

$$\begin{aligned}
    i(a+bi) &= -b + ai\\
    i^2(a+bi) &= -a + bi
\end{aligned}$$

and so on. But my problem is, I know multiplying a complex number by $i^{0.5}$ rotates for $45$ degrees, but I have no idea how to calculate it, and represent as complex:

$$
i^{0.5} (a + bi) = ?????
$$

Could anyone explain it in simply words for simply guy like me? Or give some link with explanation? Thanks in advance for any help.

PS. Of course I know it's something like:

$$
i^{0.5}(a + bi) = (0.707\ldots * a) + (0.707\ldots * b)i
$$

But have no idea how it happened :)

(Slight correction in your question: $i^3 = -i$, and $i^4 = i^0 = 1$.)

Maybe polar representation will help.

If you have a complex number, you can express it either as real and imaginary parts $(a+bi)$ or as magnitude and angle in the complex plane ($re^{i\theta}$, with $r$ being how long it is, and $\theta$ being what angle it makes with the positive real (positive $x$) axis).

So your number is either represented as $0 + 1i$, or $1e^{i\pi/2}$.

Taking the square root of the latter expression directly give you one value: $\sqrt{1}e^{i\pi/4}$. (There's another value, $1e^{i5\pi/4}$, which comes by applying De Moivre's theorem.) So this square root of $i$ makes an angle of $\pi/4$ (or $45^{\circ}$) in the complex plane, and has a length of $1$. (The other is in the third quadrant.)

In real-imaginary form, this is $\sqrt{2}/2 + i\sqrt{2}/2$, which is what you wrote at the end. You can convert from polar to this form by the formula $r\cos \theta + i r \sin \theta$.

You can then use this expression to get a value for $i^{0.5}(a+bi)$ with the FOIL method.

Hope this helps!

You are right, is not as easy than a power by an integer. You must to use the De Moivre's formula


Functional inequalities involving the condition $\left(\int_0^t f(x)dx\right)^2 \ge \int_0^t f(x)^3dx$ I was reading the solution to a functional inequality in an article when the author made the following remarks without giving any proof: let $f(x): [0, \infty]\to[0, \infty]$ be such that
$$\left(\int_0^t f(x)dx\right)^2 \ge \int_0^t f(x)^3dx$$
for all $t>0$. Then, the following two statements are true:

$\int_0^t f(x)dx \le \frac{t^2}{2}$;
$\int_0^t f(x)^\gamma dx \le \frac{1}{\gamma +1}\left(2\int_0^t f(x)dx\right)^{(\gamma + 1)/2}$ for all positive $t$ and $\gamma \in [1,3]$.

Again, there is no proof in the article, so I don't know if these statements are fairly easy to prove or are very involved. One thing that might be worth mentioning is that all these inequalities become exact when $f(x)=x$. I am wondering if anyone has an idea or have seen these before.

While I do not have the answer to the question, one can use Hölder's inequality to get some weaker bounds :

Hölder's inequality

$$
\int_0^t f(x).1 \,\mathrm{d}x \leq \left(\int_0^t f(x)^p \,\mathrm{d}x\right)^{1/p}\left(\int_0^t 1^q\,\mathrm{d}x\right)^{1/q}
$$

with parameters $p=3$, $q=3/2$ gives, after a few manipulations

$$
\int_0^t f(x) \,\mathrm{d}x \leq t^2,
$$

which differs from the first statement by a factor $2$.

Likewise, applying Hölder's inequality

$$
\int_0^t f(x)^a.f(x)^b \,\mathrm{d}x \leq \left(\int_0^t f(x)^{ap} \,\mathrm{d}x\right)^{1/p}\left(\int_0^t f(x)^{bq}\,\mathrm{d}x\right)^{1/q}
$$

with $a, b>0$, setting $ap=3$, $bq=1$ and $a+b=\gamma$, gives a unique choice of parameters (namely, $a=(3\gamma-3)/2$ and $b=(3-\gamma)/2$). One then obtains

$$
\int_0^t f(x)^\gamma \,\mathrm{d}x \leq \left(\int_0^t f(x) \,\mathrm{d}x\right)^{(\gamma+1)/2},
$$

which again is one constant away from the second statement.


Plot phase plane for system of differential equations I'm in need of some help with matlab code.  I'm working on a problem which gives the following system:

$$x'=x^2 - x - y$$

$$y'=x-y$$

We are asked to solve the system numerically starting with $(x(0), y(0))=(-0.3,-0.3)$ for $t \in [0,10]$. Additionally, we are asked to plot the solution in a phase plane and also as a function of time.

My initial reaction is to try and use the ode45 function, then plot the $x$ and $y$ components as functions of time.  The thing that I'm really having trouble with is plotting the phase plane...

Any help/links/advice is greatly appreciated!

The phase portrait of a system of two first-order ODEs can be obtained in a similar manner as described in this post, e.g. using Matlab's quiver function. Otherwise, one can plot several trajectories $(x (t), y (t))$ obtained by numerical integration (here with ode45) and having different initial conditions.

Since this is a system of first order ordinary differential equation, I recommend you try to use 4-th order Runge-Kutta method to numerically solve the problem.

A very detailed description of 4-th order Runge-Kutta Method could be found at Runge-Kutta Method.


what is a function? please. Axiom schema of replacement: Let the domain of the function $F$ be the set $A$. Then the range of $F$ (the values of $F(x)$ for all members $x$ of $A$) is also a set. — Tarski–Grothendieck set theory

I can't fully appreciated the axiom; for me, when talking about the function $F$, we should assume a domain and a range before.  So sounds that the axiom is circular.

So my question is: what is a function?
If a function is defined not through sets, then it sounds that “function” is more fundamental concept than “set.”

The usual statement of the axiom schema of replacement is as follows:

For any formula $\phi(x,y,p)$:
$$\forall p( \forall x,y,z(\phi(x,y,p)\land \phi(x,z,p) \to y = z) \to \forall X \exists Y \forall u(u \in Y \leftrightarrow \exists v(v \in X \land \phi(v,u,p))))$$

Here, $p$ is to be thought of as a "parameter", e.g. used if $\phi(x,y,p)$ is the formula $y = (x,p)$; the resulting set $Y$ will depend on $p$. The first part expresses that $\phi(\cdot,\cdot,p)$ is a functional relation: any $x$ admits at most one $y$ such that $\phi(x,y,p)$.
It is this $\phi(x,y,p)$ that is referred to, sloppily, as a "function". But we see that $\phi$ has to be of a rather more explicit form: it needs to be a formula that is expressible using the language of set theory, and we need to be able to verify that it constitutes a functional relation. Only then may we invoke replacement to conclude that $Y_p = \{y\mid\exists x: \phi(x,y,p)\}$ is a set.
We have thus crafted sort of a "formal analogue" of a "function", by using certain formulae (which are syntactical objects) in place of certain sets (which are semantical objects). By imposing functionality, we ensure that our formal analogue behaves more or less like a function. However, we did not specify either "domain" or "codomain", and they may very well not be sets (they can be empty, or consist of all sets!).
The unspecified domain and codomain are what separates a "formal function" from an "internal function", using the standard "suitable collection of ordered pairs" definition.
Now why aren't "formal functions" more general than sets? This is because they are still expressed in terms of "sets" (rather, in terms of the variables $x,y,z,p,u,v,X,Y$, which we want to think of as sets). We cannot dispose of these variables and still sensibly talk about the formulae that we have called "formal functions" cq. "functional relations".

What we have seen above is actually an example of a phenomenon that can be very confusing. We have seen "functions" that are of a different form than what our usual definition of function is. They can be "too large" to fit the usual definition of function.
We, external to the model of set theory, can reason about these "functions". However, the model itself does not have the means to contemplate them as a single object. We say the "function" is external to the model. The usual definition of a function could appropriately (but at the expense of considerable tedium) be called an internal function, because the model is able to reason about it as a single object.
This internal vs. external doctrine comes back at many, sometimes unexpected places in logic, and can give rise to intuitively bewildering statements. You can think of the distinction between $A \vdash B$ and $A \to B$ in propositional calculus as a further example: the former is the external way of saying "if $A$ holds, so does $B$", while the latter is its internal analogue. In propositional calculus, the two notions agree, but in more complicated systems, sometimes one can fail while the other holds (!).

A function $f: A \rightarrow B$ is just a subset $f \subseteq A \times B$ such that for every $a \in A$ there is a unique $b =: f(a) \in B$ with $(a,b) \in f$. Note that $A\times B$ exists as $A \times B = \{ (a,b) \mid a \in A, b \in B \}= \{ \ \{\ \{a\} \ ,\ \{a,b\}\ \} \mid a\in A, b \in B \} \subseteq \mathcal P(\mathcal P(A \cup B)) $, where $\mathcal P(X)$ denotes the power set of $X$.
Also note that we didn't make use of the axiom schema of replacement here.


Prove that the product of the $n$ roots of $e^{-i\cdot \frac{\pi }{2}}$ is given by $e^{i\cdot \frac{\left(2n-3\right)\pi }{2}}$ Let $w=e^{-i\cdot \frac{\pi }{2}}$.

Here's how to tried to solve this:

$\sqrt[n]{w}=e^{i\cdot \left(-\frac{\pi }{2n}+\frac{2\pi }{n}k\right)},\:k\in \left(0;\:1;\:2;\:...;\:n-1\right)$

Factoring out the $1/n$, we get $e^{\frac{i}{n}\cdot \left(-\frac{\pi }{2}+2\pi k\right)}$.

Since for any value of $k$ we get , $e^{\frac{i}{n}\cdot \left(-\frac{\pi }{2}\right)}$, that is, all the roots are the same, the product of the n-th roots would be $\left(e^{\frac{i}{n}\cdot \:\left(-\frac{\pi \:}{2}\right)}\right)^{\left(n-1\right)}$. I get stuck here.

How do I get to $e^{i\cdot \frac{\left(2n-3\right)\pi }{2}}$?

Your approach seems correct, except for a small mistake in the "product". I have solved it as follows.

The $n$ roots of $e^{- \iota \frac{\pi}{2}}$ are given by $e^{\iota \left( - \frac{\pi}{2n} + \frac{2 \pi k}{n} \right)}$ for $k = 0, 1, 2, \cdots, n - 1$

\begin{align*}
\prod\limits_{k = 0}^{n - 1} e^{\iota \left( - \frac{\pi}{2n} + \frac{2 \pi k}{n} \right)} &= e^{- \iota \frac{\pi}{2n}} \prod\limits_{k = 1}^{n - 1} e^{\iota \left( - \frac{\pi}{2n} + \frac{2 \pi k}{n} \right)} \\
&= e^{- \iota \frac{\pi}{2n}} \cdot e^{\sum\limits_{k = 1}^{n} \iota \left( - \frac{\pi}{2n} + \frac{2 \pi k}{n} \right)} \\
&= e^{- \iota \frac{\pi}{2}} \cdot e^{\iota \left( - \frac{\pi}{2n} \left( n - 1 \right) + \frac{2\pi}{n} \frac{n \left( n - 1 \right)}{2} \right)} \\
&= e^{- \iota \left( \frac{\pi}{2n} \left( 1 + n - 1 - 2 n \left( n - 1 \right) \right) \right)} \\
&= e^{\iota \frac{\pi}{2} \left( 2n - 3 \right)}\end{align*}

Hint

$x^n=i^{-1}=-i$

$\implies x^n+i=0$

Vieta's formula says the product $$=(-1)^ni=(e^{i\pi})^n\cdot e^{i\pi/2}$$


necessary condition for the mean value theorem Give an example which demonstrates that continuity is a necessary condition for the mean value theorem:

I thought in this function:

$$g(x) =
\begin{cases}
  x + 1 & x < 1 \\[4pt]
 x - 1 & 1 \leq x\\
 \end{cases}
$$

Clearly $g(x)$ is not continuos in $1$, i try to find the derivative of this function but i stuck some help please for prove that for this function can't use the mean value theorem.

Consider your function $g$ on the interval $[0,1]$. Then $g$ is indeed differentiable in $(0,1)$ (with $g'(x)=1$ for all $x\in(0,1)$. The claim of the mean value theorem would say that there exists $c\in(0,1)$ with $g'(c)=\frac{g(1)-g(0)}{1-0}$, i.e. $1=-1$.

Mean value theorem in its usual formulation applies to differentiable functions. Which should be at least continuous. If a function is not continuous, then there is no tangent in some points (also, it would be strange to ask fo a derivative in jump point, since there g(x + Δx)- g(x) ↛ 0 as Δx→0)


nash equilibirum help! seems tricky Any advice for finding all nash equilibrium for this symmetric game? (B,B) looks like one but I feel like there are more. I tried looking for strictly dominant strategies, but only A weakly dominates D.
\begin{array}{|c|c|c|c|c|}
\hline & A & B & C& D \\
\hline  A & (8,8)& (0,10) & (0,5) & (0,0) \\
\hline B&(10,0)& (1,1)& (-9,5)&(-9,0)\\
\hline C&(5,0)& (5,-9) & (-5,-5)& (-15,0)\\
\hline D&(0,0)& (0,-9)& (0,-15)&(-10,10)\\
\hline
\end{array}

As CommonerG noted, $D$ is worse than $A$ for the row player unless the column player mixes only $B$ and $C$.

So first assume that the column player mixes only $B$ and $C$. Then $C$ strictly dominates $B$ for the row player. That leaves us with

\begin{array}{|c|c|c|}
\hline & B & C\\
\hline  A & (0,10) & (0,5)\\
\hline C& (5,-9) & (-5,-5)\\
\hline D& (0,-9)& (0,-15)\\
\hline
\end{array}

If the column player puts higher weight on $B$, the row player must choose $C$, but then the column player would choose $C$. On the other hand, if the column player puts higher weight on $C$, the row player must choose a mixture of $A$ and $D$, but then the column player would choose $B$. Thus there is no Nash equilibrium in this case.

It follows that neither player mixes only $B$ and $C$, and hence $D$ can be eliminated, leaving us with

\begin{array}{|c|c|c|c|}
\hline & A & B & C\\
\hline  A & (8,8)& (0,10) & (0,5)\\
\hline B&(10,0)& (1,1)& (-9,5)\\
\hline C&(5,0)& (5,-9) & (-5,-5)\\
\hline
\end{array}

If the column player mixes only $A$ and $B$, then $B$ strictly dominates $A$ for the row player, who thus mixes only $B$ and $C$. Since we've excluded that, it follows that neither player mixes only $A$ and $B$.

If the column player mixes only $A$ and $C$, then $A$ strictly dominates $C$ for the row player, leaving us with

\begin{array}{|c|c|c|}
\hline & A & C\\
\hline  A & (8,8)& (0,5)\\
\hline B&(10,0)&(-9,5)\\
\hline
\end{array}

If the row player puts any weight on $A$, the column player chooses $A$, but then the row player must choose $B$. On the other hand, if the row player chooses $B$, the column player chooses $C$, but then the row player must choose $A$. Thus there is no Nash equilibrium in this case.

Now we're left only with the case where both players mix all strategies $A$, $B$ and $C$. That implies that both players can make all three strategies yield the same payoff for the other player, yielding a system of linear equations: $8w_1+0w_2+0w_3=10w_1+1w_2-9w_3=5w_1+5w_2-5w_3$ with $w_1+w_2+w_3=1$.

The solution can be obtained by producing two homogeneous equations by subtraction, e.g. $2w_1+1w_2-9w_3=0$ and $-3w_1+5w_2-5w_3=0$, taking the cross product to find $w\propto(40,37,13)$ and normalizing to find that the only Nash equilibrium is the one in which both players apply the mixed strategy with weights $4/9$, $37/90$ and $13/90$ for strategies $A$, $B$ and $C$, respectively. The value of the game for both players is $8w_1=32/9$.

Note that both players playing $B$ is not a Nash equilibrium, since both players would switch to $C$.

After eliminating D by weakly domination, observe that some mixture of A and B dominates C. It is the case.
The rest is straightforward.


Find the image of an element without clear function rule. How can I find $f(4)$ from the following equation:

$$f(x) + f(2x+1) = 6x+10$$

Let $g(x)=f(x)-2x-4$ to get

$$g(x)+g(2x+1)=0$$

Substitute $x\mapsto2^x-1$ and let $h(x)=g(2^x-1)$ to get

$$h(x)+h(x+1)=0$$

We can produce infinitely many solutions for $h$. An obvious form can be given by trigonometric functions, and more generally Fourier series. As a simple example:

$$h(x)=A\sin(\pi x)$$

$$g(x)=A\sin(\pi\log_2(x+1))$$

$$f(x)=2x+4+A\sin(\pi\log_2(x+1))$$

$$f(4)=12+A\sin(\pi\log_2(5))$$

which depends on the arbitrary value $A$. Thus there is no unique solution, given the conditions.

$f(x)=2x+4$ satisfies the equation so $f(4)=12$


Proving that this sequence is convergent Given $a_1 = 2$, and $ a_{n+1} = \frac{a_n+5}{4} $ for all $n > 1$ , is this sequence convergent? Give a formal proof in either case (converges or diverges).

Attempt: I do think this converges, but cannot say for sure.

$a_1 = 2$

$a_2 = \frac{7}{4}$

$a_3 = \frac{27}{16}$

$a_4 = \frac{107}{64}$

and so on. I can see that it is decreasing and seems to be bounded below by something. But I do not know how to present it formally.

Any help?

The sequence is descendant and positive, so it's convergent.

Where does it converge to ? Supposedly $l$ is its limit.

$l=\frac{l+5}{4}$ gives $l=\frac{5}{3}$

Hint: Use induction to show it's decreasing. Since it's positive it's bounded from below, thus it converges. Say it converges $L \in \mathbb{R}$. Apply the limit on both sides of the recursive formula of the sequence to find the value of L


A question from an engineering undergraduate My question primarily concerns the necessary transition from an undergraduate program in electrical engineering to graduate program in applied mathematics or pure mathematics.

I'm an electrical engineering student. During the first year in my university life, I found myself really fascinated with mathematics, and this summer after my first year of school, I self-studied Velleman's "How to Prove it", and analysis from Spivak's book.
As someone who had never been engaged in the circle of serious mathematics, I am lost as to the purpose of my studying: is it too late/highly improbable for me now to actually pursue a future in applied mathematics or pure mathematics while remaining in engineering as an undergraduate? Although I do have good reasoning skills, and finished Spivak's book in two months, I'm know I have much too long a way to go. Hence my question: should I try to take some mathematics courses outside my program such that I could partially fill the gap of my knowledge and basic abilities of mathematics? If so, is there any general area of math courses I should take? And should I actually complete a math minor or major degree (in my school specialist is ranked higher than major)?

You're probably in your early 20s, so: relax, you're okay. There's plenty of time to learn math. You have not missed some sort of mandatory train for becoming a mathematician or even just doing math at a reasonably advanced level. College is a great time to start doing mathematics.

If you finished Spivak in just two months (depending on the detail you went into), then you're probably already a great deal more capable than most of the students actually doing the math major. So don't think that you have too long of a way to go; you're obviously able and interested, and between the two of those, you can probably complete some sort of math curriculum pretty quickly. I know that I was in that situation as well, at one point. I ended up knocking out the entire math major in a single year by taking all core sequences concurrently. Caution: your mileage may vary.

If you can (i.e. if it fits into your program in terms of scheduling), I'd definitely recommend doing a math major. If you're looking into going into engineering, you must know linear algebra, so take that. Multivariate calculus is also recommended. Beyond that, real and complex analysis are also staples of applied mathematics, along with courses in differential equations.

Aren't engineering students supposed to know algebra and calculus? While mathematics is certainly a better major than, say, the study of 15th century Armenian literature (which is fairly useless as far as today's jobs are concerned), you would be better off studying something with the greatest likelihood of landing you a good job after you graduate. In that regard, electrical engineering is better than pure mathematics.

If I were you, I'd concentrate on the math courses required for the electrical engineering degree, while cultivating the study of things like algebraic number theory as a hobby. Once you have a good degree under your belt and a steady paycheck coming your way, then you can start to explore more philosophical fields of study.

That's the advice I'd give my son.


find the area enclosed by the given ellipse Find the area enclosed by the given ellipse:

$$
(x,y)=(a \cos t, b \sin t) \: , \quad 0\leq t < 2\pi
$$

I have tried to google this as well as look in my notes but I don't know where to start. please point me in the right direction.

Use good old $$\int y\,dx.$$

By symmetry, you can integrate on the half-ellipse, with $t$ from $\pi$ to $0$ (i.e. $x$ from $-a$ to $a$).
We have

$$\frac A2=\int_\pi^0 a\sin t\,(-b\sin t)\,dt=ab\int_0^\pi\sin^2t\,dt.$$

As$$\sin^2t=\frac{1-\cos2t}2$$ the value of the integral is $\dfrac\pi2$, giving

$$A=\pi ab.$$

Note that integration from $2\pi$ to $0$ directly yields the correct answer, as it performs a forward pass with $y$, and a backward pass, which is equivalent to a forward pass with $-y$, because $y\,dx=(-y)(-dx)$. Hence you are integrating $y_+(x)-y_-(x)$ where $y_+,y_-$ are the upper and lower arcs. This is a general method that works for closed curves. The reversal of the range, $2\pi$ to $0$, ensures clockwise rotation.

area is $\pi ab$ also you can derive the area using definite integration


Provide an efficient algorithm for computing $(a + b \sqrt{3})^n$? Provide an efficient algorithm that takes three integers as input and returns two integers that satisfy the condition. Only simple arithmetic operations are allowed (square root operation is not permitted).

Input: $(a, b, n)$ where $a, b, n$ are positive integers greater than $0$.

Output: $(c, d)$ where $c$ and $d$ are integers that satisfy the following condition:
$$ (a + b \sqrt{3})^n = c + d \sqrt{3}$$

Thought it was an interesting problem, haven't come up with a solution yet.

Initially wanted to post the question in StackOverflow but I thought it was more math heavy.

This is similar to having multiplication in complex numbers
$$(x+yi)(u+vi)=(xu-yv)+(xv+yu)i$$ Just instead of imaginary $i$ you have $\sqrt{3}$. So
$$(x+y\sqrt{3})(u+v\sqrt{3})=(xu+3yv)+(xv+yu)\sqrt{3}$$
Now basically abstracting this idea to pairs of integers, you have
$$(x,y)\cdot(u,v)=(xu+3yv,xv+yu)$$
Using this "$\cdot$" $n$ times correctly (actually $n-1$ times), you can calculate $n$-th power of a number. Notice that there are only basic arithmetic operations involved.

Efficience

Since you wanted also efficient algorithm, you can speed this up by using fast exponentiation. Basic idea is that instead of calculating $x$,$x^2$,$x^3$,etc, you just calculate
\begin{align}
x^2 &= x \cdot x \\
x^4 &= x^2 \cdot x^2  \\
x^8 &= x^4 \cdot x^4  \\
&\vdots \\
\end{align}
and then combine the results correctly. This results on average in $\log_2{n}$  multiplication steps as compared to $n$ steps when using naive approach. There are other tricks to speed exponentiation up, suggest you to check them  Fast exponentiation algorithm - How to arrive at it?, https://en.wikipedia.org/wiki/Exponentiation_by_squaring.

Algorithm Pseudocode

To be even more specific, lets construct one such algorithm. Let's pick for example this fast exponentiation algorithm:

Function exp-by-squaring(x, n)
    if n = 0  then return  1;
    else if n is even  then return exp-by-squaring(x * x,  n / 2);
    else if n is odd  then return x * exp-by-squaring(x * x, (n - 1) / 2);

Now replacing $x$ with pair of numbers $a,b$, and similarly the multiplication with the one described above, we get:

Function exp-by-squaring(a, b, n)
    if n = 0  then return  (1,0);
    else if n is even  then return exp-by-squaring(a*a+3b*b, 2ab,  n / 2);
    else if n is odd  then
        (c,d) = exp-by-squaring(a*a+3b*b, 2ab, (n - 1) / 2);
        return (ac+3bd,ad+bc);

This by the way shows how you can calculate powers in general, you just need to have multiplication defined. Even in cases where it first looks like the problem is only solvable by recursions, this trick allows to skip many steps.

Python example

Now if you turn this into python (or any programming language you like), you can play with it:

def exp(a, b, n):
  if n == 0:
    return (1,0)
  elif n % 2 == 0:
    return exp(a*a+3*b*b, 2*a*b,  n / 2)
  elif n % 2 == 1:
    (c,d) = exp(a*a+3*b*b, 2*a*b, (n - 1) / 2)
    return (a*c+3*b*d,a*d+b*c)

For example

print exp(1,1,20)

yields

(268377088, 154947584)

And indeed, $(1+\sqrt{3})^{20} = 268377088+154947584\sqrt{3}$

Also notice there were only $5$ multiplications done, compared to naive $19$:

\begin{align}
(1+\sqrt{3})^2 &= (1+\sqrt{3}) \cdot (1+\sqrt{3})\\
(1+\sqrt{3})^4 &= (1+\sqrt{3})^2 \cdot (1+\sqrt{3})^2\\
(1+\sqrt{3})^8 &= (1+\sqrt{3})^4 \cdot (1+\sqrt{3})^4\\
(1+\sqrt{3})^{16} &= (1+\sqrt{3})^8 \cdot (1+\sqrt{3})^8\\
(1+\sqrt{3})^{20} &= (1+\sqrt{3})^4 \cdot (1+\sqrt{3})^{16}\\
\end{align}

Consider this as a recursion:

$(a_n+b_n\sqrt{3})=(a+b\sqrt{3})^n = (a+b\sqrt{3})(a+b\sqrt{3})^{n-1} = (a+b\sqrt{3})(a_{n-1}+b_{n-1}\sqrt{3}) = aa_{n-1}+3bb_{n-1}+(ab_{n-1}+a_{n-1}b)\sqrt{3}$

Note that you can consider these as elements of a $\mathbb Q$-vector space with the base vectors $1$ and $\sqrt{3}$. With regard to this basis we can write thre recursion as:

$$\begin{pmatrix} a_n \\ b_n \end{pmatrix} = \underbrace{\begin{pmatrix}a & 3b \\ b & a \end{pmatrix}}_{=:M}\begin{pmatrix}a_{n-1}\\ b_{n-1}\end{pmatrix} = \begin{pmatrix}a & 3b \\ b & a \end{pmatrix}^n \begin{pmatrix} 1 \\ 0\end{pmatrix}$$

Now the $n$-th power of $M$ can efficiently be computed if you first  diagonalize $M$ to $M=TDT^{-1}$ Then $M^n = TDT^-1TDT^-1 \cdots TDT^{-1} = TD^nT^{-1}$. Then $D^n$ is just the $n$-th power of the diagonal matrix $D$ which is easy to compute as you just have to take the entries of $D$ to the power of $n$.


The product of $46$ integers is $1$. Which of the following cannot be the sum of these $46$ integers? I am solving a problem about integers.
The product of $46$ integers is $1$. Which of the following cannot be the sum of these $46$ integers?
$A.38$

$B.6$

$C.0$

$D.-14$
To solve this, I think, we can use these equations below since the only way to get a product of 1 with integers which sum is 46, is that
$(-1)^{2n}$ $×$ $(1)^{46-2n} = 1$, $n≥ 0$
and
$(-1)x + (1)y = z$,
where $x$ is the number of times (-1) was used,
$y$ is the number of times of (1) was used, $z∈\{-14,0,6,38\}$
I am not sure if my ideas are correct and can be connected.
Any comments and/or suggestions will be much appreciated. Thank you!

Yes, you are correct so far. Your first equation implies that in the second equation you have $x+y=46$, and $x$ and $y$ are both even. So what does this tell you about the possible values of $z=y-x$? (You could just try each of the four alternatives and see if you can find suitable $x,y$.)

Suppose $a_1,\ldots,a_n$ are integers such that $a_1 \cdots a_n=1$. Then each $a_i \in \{+1,-1\}$. If $k$ of these $n$ integers are $-1$, then $n-k$ are $1$, and their sum is $n-2k$. Moreover, $k$ is even (since the product is $+1$), so that with $k=2\ell$ we have the sum $n-2k=n-4\ell$, with $0 \le k \le n$ and $0 \le \ell \le \left\lfloor\frac{n}{2}\right\rfloor$.
Conversely, any integer of the form $n-4\ell$ is attained by selecting $2\ell$ of the $a_i$'s equal to $-1$'s.
In particular, when $n=46$, the attainable sums are in $\{46-4k: 0 \le k \le 23\}$. Therefore, the only non attainable sum is $0$. $\blacksquare$


Show that $f(\phi)=\sum_{k=0}^\infty \phi^{(k)}(k)$ for $\phi \in D$ has no finite order Let $\phi \in D:=D(K)=C^\infty_0(K) $ be a test function and let $f \in D^*=\{f:D \to \mathbb{R} : f \text{ bounded and linear} \} $ be a distribution.

A distribution has finite order if:

$$\exists m \in \mathbb{N}_0 ~\forall K^{\text{compact}} \subset \mathbb{R}~ \exists C>0 ~\forall \phi \in D: |f(\phi)| \leq C \sum_{i=0}^m ||\phi^{(i)}||_{\infty}$$

Show: $f(\phi)=\sum_{k=0}^\infty \phi^{(k)}(k)$ has no finite order.

So, I have to show the negation, i.e.
$$ \forall m \in \mathbb{N}_0 ~\exists K^{\text{compact}} \subset \mathbb{R}~ \forall C>0~\exists \phi \in D: |f(\phi)| > C \sum_{i=0}^m ||\phi^{(i)}||_{\infty}$$

It would be fine if I could find one $\phi \in D$ s.t. this is fulfilled. But I don't know a lot test functions. And computing the n-th derivative seems strenuous.

I know $$\phi(x)=\begin{cases} \exp\left(-\frac{1}{1-x^2}\right) & ,|x|<1 \\ 0  &,\text{else} \end{cases}$$
as the bump function with compact support on $[-1,1]=:K$.
Here I have $$f(\phi)=\sum_{k=0}^\infty \phi^{(k)}(k)=\phi(0)=e^{-1}.$$
If I set $m=0$ I have: $$C \sum_{i=0}^0 ||\phi^{(i)}||_{\infty}=C \sup_{x \in K} |\phi(x)|=C \phi(0)=C e^{-1}$$
and obviously $e^{-1} \ngtr Ce^{-1} ~\forall C>0$. So this example does not even work for $m=0$ :(

Yeah, I don't really have a leading approach, sorry for that. Has someone got an idea?

Thanks a lot,
Marvin

EDIT: corrected tags
EDIT2: corrected quantors as suggested in the hint

The behaviour of $f(\phi)$ is easiest to control when only one of the terms in the defining sum can be nonvanishing. To this end, for every $k\in \mathbb{N}$ we define $K_k := [k-1,k+1]$. For $\phi \in D(K_k)$ we then have $f(\phi) = \phi^{(k)}(k)$.

It is straightforward to see that the order of the restriction of $f$ to $D(K_k)$ is at most $k$, and when we have established that the order is no smaller than $k$, we have achieved our goal. Given an arbitrary $m\in \mathbb{N}$, we choose a $k > m$, and looking at functions in $D(K_k) \subset D(\mathbb{R})$ then shows that $f$ is not of order $m$.

So we want to show that the distribution $\phi \mapsto \phi^{(k)}(k)$ has exact order $k$. Since translations obviously don't affect the order, let us for simplicity of notation look at $\phi \mapsto \phi^{(k)}(0)$ instead.

Let $\beta \colon \mathbb{R} \to [0,1]$ be a smooth function with $\beta(x) = 1$ for $x \leqslant \frac{1}{2}$ and $\beta(x) = 0$ for $x \geqslant 1$. Define $\chi(x) := \beta(\lvert x\rvert)$, and $\chi_{\varepsilon}(x) := \chi( \varepsilon^{-1}\cdot x)$ for $\varepsilon > 0$. For $0 < \varepsilon \leqslant 1$, the function

$$\psi_{k,\varepsilon} \colon x \mapsto \chi_{\varepsilon}(x)\cdot \frac{x^k}{k!}$$

then belongs to $D([-1,1])$ and satisfies $\psi_{k,\varepsilon}^{(k)}(0) = 1$. Since also $\psi_{k,\varepsilon}^{(i)}(0) = 0$ for $i < k$, we can hope that

$$\sum_{i = 0}^{k-1} \lVert \psi_{k,\varepsilon}^{(i)}\rVert_{\infty}$$

can be made very small. By Leibniz's rule,

$$\psi_{k,\varepsilon}^{(r)}(x) = \sum_{\rho = 0}^r \binom{r}{\rho} \chi_{\varepsilon}^{(\rho)}(x)\cdot \frac{x^{k-r+\rho}}{(k - r + \rho)!}.$$

Since $\chi_{\varepsilon}^{(\rho)}(x) = 0$ for $\lvert x\rvert \geqslant \varepsilon$, we can estimate

$$\lVert \psi_{k,\varepsilon}^{(r)}\rVert_{\infty} \leqslant \sum_{\rho = 0}^r \binom{r}{\rho} \lVert \chi_{\varepsilon}^{(\rho)}\rVert_{\infty} \cdot \frac{\varepsilon^{k - r + \rho}}{(k - r + \rho)!}.$$

By the chain rule, we have $\lVert \chi_{\varepsilon}^{(\rho)}\rVert_{\infty} = \varepsilon^{-\rho}\cdot \lVert \chi^{(\rho)}\rVert_{\infty}$, and thus

$$\lVert \psi_{k,\varepsilon}^{(r)}\rVert_{\infty} \leqslant \varepsilon^{k-r}\sum_{\rho = 0}^r \binom{r}{\rho} \lVert \chi^{(\rho)}\rVert_{\infty} \frac{1}{(k - r + \rho)!} \leqslant \frac{\varepsilon^{k-r}}{(k - r)!} \sum_{\rho = 0}^r \binom{r}{\rho} \lVert \chi^{(\rho)}\rVert_{\infty}.$$

Finally, we see that

$$\sum_{i = 0}^m \lVert \psi_{k,\varepsilon}^{(i)}\rVert_{\infty} \leqslant M\cdot \varepsilon \tag{$\ast$}$$

whenever $m \leqslant k-1$, where $M$ can be chosen as

$$\sum_{r = 0}^{k-1}\frac{1}{(k - r)!}\sum_{\rho = 0}^r \binom{r}{\rho}\lVert \chi^{(\rho)}\rVert_{\infty}.$$

From $(\ast)$ it is easy to see that $\phi \mapsto \phi^{(k)}(0)$ doesn't have order $m < k$: Given $C > 0$, we have

$$\psi_{k,\varepsilon}^{(k)}(0) = 1 > C\cdot \sum_{i = 0}^m \lVert \psi_{k,\varepsilon}^{(i)}\rVert_{\infty}$$

for all $0 < \varepsilon < \min \bigl\{ 1, (CM)^{-1}\bigr\}$.

Informally speaking, order of a distribution f(.) is the smallest n such that f(fi(.)) does not contain derivatives of fi(.) of order greater than n.
A lot of formalism makes it hard to read.
By my informal criterion the distribution in question clearly has infinite order.


Drawing 3 cards from a deck 3 cards are drawn from a standard deck of 52 cards without replacement. Let $X_1$ be a random variable that is 1 if the 1st card drawn is a King and 0 otherwise $X_2$ be a random variable that is 1 if the 2nd card drawn is a king and 0 otherwise. What is the probability that $X_2 = 1$?

My thinking is that $P(X_2 = 1) = P(X_2 = 1|X_1 = 1) + P(X_2 = 1|X_1 = 0)$, so $P(X_2 = 1) = \frac{\frac{4}{52} \times \frac{3}{51}}{\frac{4}{52}} + \frac{\frac{48}{52} \times \frac{4}{51}}{\frac{48}{52}} = \frac{7}{51}$.

Is this right way of thinking, or should the answer just be $\frac{4}{52}$ by symmetry?

You made a mistake in the first equation of not multiplying $P(X_1=1)$ and $P(X_1=0)$, it should be $$P(X_2=1)=P(X_1=1)P(X_2=1|X_1=1)+P(X_1=0)P(X_2=1|X_1=0)$$ and your answer is indeed $\frac{4}{52}$. (This equation is the Law of Total Probability)

Note: The calculation is $$P(X_2=1)=\frac{1}{13}\cdot \frac{3}{51}+\frac{12}{13}\cdot\frac{4}{51}=\frac{1}{13}$$

The probability of the first card being a King is 4/52, or 1/13. Should the first card had been a King, the probability of the second card being a King is now 3/51, or 1/17. However, if the first card wasn't a King, then the odds that the second card is a King is 4/51.

If you sum the two scenarios, applying a product of their condition, you get the following:

$P(X_2) = 1/13 * 1/17 + 12/13 * 4/51$

$= 1/221 + 48/663$

$= 1/221 + 16/221$

$= 17/221$

$= 1/13$

Edit:

Fixed fraction error.


What is the Bi-affine plane I want to know the definition of the Bi-affine plane. In an article it says that semi-symmetric plane is same as bi-affine plane. But I want to the exact definition and axioms. Also There are two types of Bi-affine planes Type I and Type II. It defines only in one paper, that is in German, but I don't know German and difficult to translate with math symbols (using google and other online translations).

Can you help me to find  the definitions of the Bi-affine plane of type I and II, pls..

If there are any references, pls tell me...

Thanks.

The very first page defines it:

  Eine Inzidenzstruktur $\mathfrak A$, die (A1), (A2) und (A3,h) für eine natürliche Zahl $h$ erfüllt, heißt $h$-affine Inzidenzebene. Sind $\mathfrak P, \mathfrak G$ endlich, so heiß $\mathfrak A$ endlich. Eine $2$-affine Ebene heißt auch biaffin

In other words:
A bi-affine (incidence) plane is a structure satisfiying
$(A1), (A2)$ and $(A3,2)$:
$$\begin{align*}
(A1)\qquad & \text{for each } P, Q\in \mathfrak P \ \exists!\ g\in\mathfrak G \text{ such that } g \text{ incides with both } P,Q \\
(A2)\qquad & \text{There are } P,Q,R \in \mathfrak P \text{ such that no } g\in\mathfrak G \text{ incides with all three}\\
(A3,2)\qquad & \forall (P,g)\in\mathfrak P\times \mathfrak G: \ 1\le\pi(P,g) \le 2
\end{align*}$$

Definition 6 defines a $w$-line by $O(g) = n$ and a $v$-line by $O(g) = N$(where $N$ is the order and $n$ is the suborder)
Which is given in eqn. (5) / Definition 2 by
$$N = \max_{g\in\mathfrak G} O(g), \qquad n=\min_{g\in\mathfrak G} O(G)$$

Definition 7 defines a Type I biaffine plane to be one such that every point has a $w$-line inciding it.
Definition 8 defines a Type II biaffine plane to be one such that every point has a $v$-line inciding it.

I read one paper that defined bi-affine as follows:
   We say $f(u,x)$ is bi-affine if the function $f(u,x)$ is affine for any $x$ and the function is affine for any fixed $u$.

Dimitris Bertsimas, Vishal Gupta, etc., "Data-driven robust optimization".


$e^{i\theta} = 1$ for all $\theta$? What is the conceptual error in the following derivation?
$$
e^{i\theta} = e^{i\frac{2\pi}{2\pi}\theta} = (e^{i2\pi})^{\frac{\theta}{2\pi}} = 1^{\frac{\theta}{2\pi}} = 1
$$
It is clear to me that the second move is illegal, I just don't know why.

$a^{x y} \not = (a^x)^y$ in general.

For example, $[(-1)^2]^{1/2} = 1$ but $(-1)^1 = -1$.

You may wish to look up "branch cuts" to understand conceptually why this is true.

$\theta$ is the angle from the real axis so what you did that while converting $e^{i\theta}$ to $e^{i\theta \frac{2\pi}{2\pi}}$ you change the complex number because if $\theta \ne 2\pi$ then $e^{i\theta \frac{2\pi}{2\pi}} \ne e^{i2\pi \left(\frac{\theta}{2\pi}\right)}$ because the argument of the $e^{i\theta }$ is $\theta$ and the argument of $e^{i2\pi}$ is $2\pi$


Is the multiplicative Chernoff bound stronger than additive one? The multiplicative Chernoff Bound says for $X_i \in \{0,1\}$ that satisfies $\mathbb{E}[X_i] = p$,
$$
\mathbb P\left(\sum\limits_i^n{X_i} \geq np(1+\delta)\right) \leq e^{-\frac{1}{3} np\delta^2} \>.
$$

The additive version says that
$$
\mathbb P\left(\sum\limits_{i}^nX_i \geq np+n\epsilon \right) \leq e^{-2n\epsilon^2} \>.
$$

I wonder if the multiplicative version could be stronger. Let $\epsilon = p \delta$, then the additive Chernoff bound is reduced to
$$
\mathbb P\left(\sum\limits_{i}^{n}{X_i} \geq np(1+\delta)\right) \leq e^{-2np^2\delta^2} \>.
$$ This is a much weaker bound when $p \ll 1$.

How can these two versions of Chernoff bounds have such a difference? I mean, which step in deriving these two bounds diverges, causing the fact I have illustrated?

No version is stronger than the other. Look at the proofs of both statements and you'll notice (e.g. http://en.wikipedia.org/wiki/Chernoff_bound) that one case uses $1+x\lt e^x$ while the other does not. This explains the divergence you mention.

Here is one proof of the additive Chernoff bound you mentioned. Let $t$ be any positive real number. We have

$$
\begin{align*}
\Pr\left[ \bar{X} > p + \epsilon \right] & = \Pr\left[ \exp\left( t \sum_{i = 1}^n (X_i - p) \right) > \exp( t n \epsilon ) \right] \\
& \leq \frac{ \prod_{i = 1}^n \mathrm{E}[ \exp(t(X_i - p)) ] }{\exp(tn\epsilon) }  \\
& \leq \frac{ \prod_{i=1}^n \exp( t^2/8 ) }{\exp(tn\epsilon) } \\
& = \exp( n(t^2/8 - t\epsilon) ),
\end{align*}
$$
where second inequality is due to Markov's inequality, the last but one inequality is due to Hoeffding's lemma by considering $(X_i - p)$ as a random variable. By setting $t = 4\epsilon$, your additive version of Chernoff bound is achieved.

Since Hoeffding's lemma holds for any random variable with domain $[a, b]$ such that $b - a \leq 1$, it does not make most use of domain $[0, 1]$. Hence it is weaker. And this explains why it is much weaker when $p \ll 1$.

The multiplicative Chernoff bound you mentioned is derived by the multiplicative one in Chernoff Bound, Wikipedia which does not use Hoeffding's lemma in its proof. And the proof is subject to the domain $[0, 1]$.

Considering the multiplicative and additive ones in Wikipedia.  I think the additive one is technically stronger than the multiplicative one since the multiplicative one uses one more relaxation like @ivan said.


Find how many parts are in a triangle Recently, I got this interesting riddle in a math test, which I still can't solve. Here are the exact words:

  Each side of an equilateral triangle was divided into 100 equal parts. Points received
  connected by segments. How many parts did you get?

Here is an example for a triangle with just 3 points on each side:

That much lines really confuses me. I tried to find a ratio between number of lines and parts, and how does each new line drawn divides the others, but it doesn't seem to work. What could be the possible solution to this?

This Rust program gives the answer 205689153 in about a minute and a half.  It’s based on the Euler characteristic formula $V - E + F = 1$ for a connected plane graph with $V$ vertices, $E$ edges, and $F$ faces.  But there doesn’t seem to be a nice formula to find $V$ and $E$ without lots of computation, because in some cases, multiple pairs of segments concur at the same intersection point.  So we just list all the intersections and count up the duplicates.

use std::collections::hash_map::HashMap;

fn det(a: (i32, i32), b: (i32, i32), c: (i32, i32)) -> i32 {
    (b.0 - a.0) * (c.1 - a.1) - (b.1 - a.1) * (c.0 - a.0)
}

fn gcd(mut x: i32, mut y: i32) -> i32 {
    while y != 0 {
        let z = x % y;
        x = y;
        y = z;
    }
    x
}

fn reduce(n: i32, d: i32) -> (i32, i32) {
    let g = gcd(n, d);
    (n / g, d / g)
}

fn main() {
    for &n in &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100] {
        let sides = [
            (1..n).map(|i| (i, 0)).collect::<Vec<_>>(),
            (1..n).map(|i| (n - i, i)).collect::<Vec<_>>(),
            (1..n).map(|i| (0, n - i)).collect::<Vec<_>>(),
        ];
        let segments = (0..)
            .zip(&sides)
            .flat_map(|(i, side0)| {
                sides[i + 1..].iter().flat_map(move |side1| {
                    side0
                        .iter()
                        .flat_map(move |&a| side1.iter().map(move |&b| (a, b)))
                })
            })
            .collect::<Vec<_>>();
        let mut regions = 1 + segments.len() as i64;
        let mut intersections = HashMap::new();
        for (i, &(a, b)) in (0..).zip(&segments) {
            for &(c, d) in &segments[i + 1..] {
                let p = det(c, d, a);
                let q = det(c, d, b);
                if p * q < 0 && det(a, b, c) * det(a, b, d) < 0 {
                    if *intersections
                        .entry((
                            reduce(a.0 * q - b.0 * p, q - p),
                            reduce(a.1 * q - b.1 * p, q - p),
                        ))
                        .or_insert(i)
                        == i
                    {
                        regions += 1;
                    }
                }
            }
        }
        println!("{} {}", n, regions);
    }
}

Output:

1 1
2 4
3 27
4 130
5 385
6 1044
7 2005
8 4060
9 6831
10 11272
100 205689153

Here are the results when dividing each side into $n$ parts for all $1 \le n \le 120$:

1, 4, 27, 130, 385, 1044, 2005, 4060, 6831, 11272, 16819, 26436, 35737, 52147, 69984, 92080, 117952, 157770, 193465, 249219, 302670, 368506, 443026, 546462, 635125, 757978, 890133, 1041775, 1191442, 1407324, 1581058, 1837417, 2085096, 2365657, 2670429, 3018822, 3328351, 3771595, 4213602, 4694337, 5140756, 5769306, 6279934, 6987991, 7661637, 8355580, 9122179, 10077408, 10860478, 11882437, 12859392, 13960045, 15028393, 16394970, 17583472, 18980292, 20342943, 21871402, 23445913, 25385163, 26876233, 28911262, 30947106, 32961190, 35048842, 37459587, 39569107, 42324415, 44890158, 47731083, 50294455, 53649654, 56360842, 59879101, 63420084, 66857380, 70408212, 74445273, 78040573, 82622160, 86647137, 91124683, 95665744, 101133132, 105569497, 110811364, 116310795, 122023012, 127352503, 134068833, 139524337, 146093875, 152642448, 159496621, 166630228, 174340821, 180991705, 189418792, 197333184, 205689153, 213416806, 223144743, 231395536, 241509546, 251118018, 260392267, 270368527, 282027867, 291604741, 303685314, 314632365, 326674581, 337687342, 351301695, 363291763, 376664530, 390047007, 403508989, 417603979, 433264083

The answer is simple $100^3$. Discard the amount of parts that disappear when three segment get through the same point, At least $99^3$. I assume that you know how to find all other such cases (if exist:))


Probabilistic proof of green-eyed dragons logic puzzle I came across the "green-eyed dragons" puzzle (alternatively known as the "blue eyed villagers" puzzle). The typical proof uses a straightforward inductive strategy. I came up with a probabalistic proof, and I wondered if there are holes in it.

The puzzle in its (possibly original) form can be found here:
https://www.physics.harvard.edu/uploads/files/undergrad/probweek/prob2.pdf
and the inductive proof here:
https://www.physics.harvard.edu/uploads/files/undergrad/probweek/sol2.pdf.

Theorem: All 100 dragons transform at midnight on the first night.

Proof: It suffices to prove that each dragon independently concludes
$$\Pr[\textrm{exactly 100 dragons have green eyes}] = 1$$

Upon departing, we tell the dragons collectively that at least one of
them has green eyes. Specifically, we impart the knowledge that
$$\Pr[\textrm{at least 1 dragon has green eyes}] = 1$$

Define $L_i$ to be the event that at least $i$ dragons have green eyes, and $E_i$ to be the event that exactly $i$ dragons have green eyes.

Then the above probability can be restated as:

\begin{align*}
\Pr[L_1] = {100 \choose 1} \Pr[E_1] + {100 \choose 2} \Pr[E_2] + \dots + {100 \choose 100} \Pr[E_{100}]
\end{align*}

Because each dragon observes the eye color of every other dragon except himself, each dragon concludes independently that:

\begin{align*}
\Pr[E_0] = \Pr[E_1] = \Pr[E_2] = \dots = \Pr[E_{98}] = 0
\end{align*}

Therefore, each dragon concludes

\begin{align*}
\Pr[L_1] = {100 \choose 99} \Pr[E_{99}] + \Pr[E_{100}] = 1
\end{align*}

Note that

\begin{align*}
\Pr[E_{99}] &= 1-\left(\Pr[E_0] + {100 \choose 1}\Pr[E_1] + \dots + {100 \choose 98}\Pr[E_{98}] + \Pr[E_{100}]\right) \\
&= 1- \Pr[E_{100}]
\end{align*}

Therefore,
\begin{align*}
{100 \choose 99} \Pr[E_{99}] + \Pr[E_{100}] &= 1 \\
100(1-\Pr[E_{100}]) + \Pr[E_{100}] &= 1 \\
100 - 99\Pr[E_{100}] &= 1 \\
\Pr[E_{100}] &= 1
\end{align*}

Thus, each dragon individually concludes that with probability 1, all
100 dragons have green eyes (including himself). This reasoning
happens simultaneously across all dragons, and thus they all transform
together on the first midnight, QED.

This is a problem about knowledge, not about probability. When the traveller leaves, they all know that at least one dragon has green eyes. If there had been only one such dragon, that dragon would know they had green eyes and would transform at midnight.

The next morning all the dragons know that no dragon transformed at midnight. They therefore also know that there are at least two dragons with green eyes. If there were exactly two, they would transform at midnight. It doesn't happen, so the next morning the dragons know that there are at least three dragons with green eyes.

The information that no dragons transform in the night is additional information not present on the first day. A dragon does not know whether or not it has green eyes until ninety nine nights have passed. If it hasn't got green eyes, the others will all transform on the ninety ninth night. If it does have green eyes, they will all transform on the hundredth night.

Since these two possibilities are live, no dragon can conclude on the first night that all dragons have green eyes.

Actually I think there is a major flaw in this logic.
I have seen this and variants in the past. I understand both the 100 day answer, and the 2 day answer.

However -

One important datum is omitted and it is significant enough to affect the logic going from 3 up to larger values for N.
Each dragon knows there are at least 99 green eyed dragons from personal observation. And he/she knows that every other dragon knows there are at least 98 green-eyed dragons (N-2) from direct observation.

The logic for this is
Dragon 1 thinks “I may have red eyes. So dragon 2-100 will hope that each of them has red eyes too. So thus they would know that all would see either one or two red eyeds dragons. But no dragon could logically think any other dragon could sees more than two reds as threy must each see 98 greens. And I know they really can only see one at most because I cam see 99.”

So Dragon 1 knows that Dragons 2 to 99 also know there are only 3 possibilities at most.

1: All green eyes

2: Dragon 1 only has red eyes

3: Dragon 1 and whichever other Dragon is thinking also has red eyes.

No dragon (eg number 1) can believe any other dragon (2 to 100) could think there are more than two sets of red eyes.
Dragon 1 knows that option 3: is not possible because of the 99 greens visible. But Dragon 1 does not know that Dragons 2-100 know that.

So Dragon 1 can think “I have red eyes and if I do each of the other dragons thinks the same of themselves. If I don’t have red eyes, then each other dragon may still think they may have red eyes.”

The extrapoloations of increasing N values from 3 up do not hold. A simple test with only 5 dragons shows this.
There are either 1 red and 4 green or 5 green. But each individual dragon can assume the others may think there are 2 red and 3 green. But each dragon knows there can not be less than 4 greens and that all other dragons must know there can not be less than 3 greens. The option that somehow there could be 4 reds and 1 green, And that green would then leave on day 1 is NOT possible. As the logic chain for N>3 relies on this And subsequent steps it is flawed.

However if the puzzle was restated that the person leaving said there is no more than one set of red eyes - something they all know, but which they dont know all the others know - this extra knowledge triggers them all to get the knowledge that they each have green eyes.

Bill


System of equations and recurrence relation I am trying to find the general solution for $N$ of the following system of equations
$$
\begin{cases}
    (x_n - x_{n-1})^2 + (y_n - y_{n-1})^2 = \left(\frac{\theta}{N}\right)^2 \\
    {x_n}^2 + {y_n}^2 = 1
\end{cases}
$$
with the initial values $x_0 = 1$ and $y_0 = 0$ and the following

$\theta$ is a constant and $0 \leqslant \theta \leqslant 2$
$N$ is a constant and we want to find the terms $(x_N, y_N)$

Using substitution with respect to $N$, we have
$$
\begin{align}
    x_0 = 1 \quad & ; \quad y_0 = 0 \\
    x_1 = -\frac{\theta^2 - 2N^2}{2N^2} \quad & ; \quad y_1 = -\frac{\theta \sqrt{4N^2 - \theta^2}}{2N^2} \\
    x_2 = \frac{\theta^4 - 4N^2\theta^2 + 2N^4}{2N^4} \quad & ; \quad y_2 = \frac{(\theta^3 - 2N^2\theta) \sqrt{4N^2 - \theta^2}}{2N^4} \\
    x_3 = -\frac{\theta^6 - 6N^2\theta^4 + 9N^4\theta^2 - 2N^6}{2N^6} \quad & ; \quad y_3 = -\frac{(\theta^5 - 4N^2\theta^3 + 3N^4\theta) \sqrt{4N^2 - \theta^2}}{2N^6}
\end{align}
$$
By using substitution, it becomes very difficult with $N \geqslant 2$.

Using complex numbers as well, it is obvious from the second equation that the $n^{th}$ point can be written
$$z_n=e^{i\alpha_n}.$$
Then
$$|e^{i\alpha_n}-e^{i\alpha_{n-1}}|=|e^{i(\alpha_n-\alpha_{n-1})}-1|=|e^{i\alpha}-1|=\frac\theta N.$$
It is easy to show that this equation has at most two solutions in $e^{i\alpha}$, which are conjugate. If we always keep the same sign of $\alpha$, then by induction
$$z_n=e^{i\alpha_n}=e^{i\alpha_{n-1}}e^{i\alpha}=e^{in\alpha}.$$

Because it is very difficult to solve this relation, we can use complex numbers. Let
$$(x_n, y_n) = x_n + iy_n \quad \text{and} \quad z_n = x_n + iy_n$$
then we have
$$z_1 = -\frac{\theta^2 - 2N^2}{2N^2} + i\frac{\theta \sqrt{4N^2 - \theta^2}}{2N^2}$$
and the term $z_1$ is always given by the same expression with respect to $N$.
To compute the product of two complex numbers, we multiply the magnitudes and add the arguments. Since $\lvert z_1 \rvert = 1$, we have
$$\forall k \in \mathbb{N}^*, \lvert (z_1)^k \rvert = 1$$
and it rotates $z_1$ by $\arg(z_1)$ for $k$ times. Since the magnitude is always equal to 1, we stay in orbit around the unit circle.
Consider the following picture:

In particular, we notice that
$$\forall n,N \in \mathbb{N}^*, \arg(z_n) \leqslant \frac{\theta}{N} \quad , \quad n \leqslant N$$
because the length of the chord between two terms is given by
$$\frac{\theta}{N} = \lvert z_n - z_{n-1} \rvert = \sqrt{(x_n - x_{n-1})^2 + (y_n - y_{n-1})^2} \quad , \quad n \leqslant N$$
and we can reduce the length of each chord such that we obtain the term
$$z_N = \left(-\frac{\theta^2 - 2N^2}{2N^2} + i\frac{\theta \sqrt{4N^2 - \theta^2}}{2N^2}\right)^N$$
and by taking its limit, we eventually have
$$\cos(\theta) + i\sin(\theta) = \lim\limits_{N \to \infty} \left(-\frac{\theta^2 - 2N^2}{2N^2} + i\frac{\theta \sqrt{4N^2 - \theta^2}}{2N^2}\right)^N$$
as each chord becomes smaller and smaller and closer to the circle, we denote by $\theta$ the arc length measure around the unit circle in radians.


How to learn measure theory by myself? I'm an engineer student. I have taken a couple of courses in probability, but none of them offered formal proofs involving probability spaces and sigma algebras. How might I formalise my knowledge of probability without having to take further courses?

Read the Bartle´s book about Measure and Lebesgue Integral, lecture recommended, do you need some prerequisites as some set theory, some topology(the first half of Munkres book) and integral calculus.


ODE with inverse function. Solve $f^{-1}(x)=f'(x)$. Find all functions $f:\mathbb{R}^+\rightarrow\mathbb{R}^+$ such that $$f^{-1}(x)=f'(x)$$

I think one such function would be of the form $f(x)=ax^b$. But then $b$ would be irrational and when $x\lt0$ this causes problems. So I guess letting $f(x)=-a(-x)^b$ for $x<0$ might work. But that's only one possibble solution, what are all the solutions?

Edit: With the comment of Joey Zou, the domain and range has been changed to $(0,\infty)$.

Edit: I already know the solution of the form $ax^b$. However, what I'm really asking is whether it is the unique solution.

Partial answer, in order to confirm the Omnomnomnom's assumption that some solutions on the form $f(x)=ax^b$ do exist.

$$f^{-1}(x)=f'(x)\qquad \text{on }x>0$$
Search of particular solutions on the form $\quad f(x)=ax^b$ :

$f=ax^b \quad\to\quad x=\left(\frac{f}{a}\right)^{1/b}$

Hence the inverse fonction of $f(x)$ expressed as a function of $x$ is :
$$f^{-1}(x)=\left(\frac{x}{a}\right)^{1/b}$$
to be not confused with $x$ expressed as a function of $f$.

If a solution of the form $f(x)=ax^b$ exists, it must satisfy the equation :
$$f^{-1}(x)=f'(x)=\left(\frac{x}{a}\right)^{1/b}=abx^{b-1}$$
First condition : $x^{1/b}=x^{b-1}\quad\to\quad b^2-b-1=0$
$$b=\frac{1\pm\sqrt{5}}{2}$$
Second condition : $\left(\frac{1}{a}\right)^{1/b}=ab \quad\to\quad a=b^{-\frac{b+1}{b}}$

So, two different particular solutions are obtained :

First : $\quad f(x)=\left(\frac{2\:x}{1+\sqrt{5}}\right)^{\frac{1+\sqrt{5}}{2}}$

Second : $\quad f(x)=\left(\frac{2\:x}{1-\sqrt{5}}\right)^{\frac{1-\sqrt{5}}{2}}$

Make the substitution $y = f(x)$ to rewrite this equation as
$$
y = f'(f(y))
$$
Rewrite this as
$$
y\,f'(y) = f'(f(y)) \,f'(y)
$$
Now, integrate both sides with respect to $y$.  Using integration by parts, note that
$$
\int y\,f'(y) \,dy = y\,f(y) - \int f'(y)\,dy = (y - 1)f(y) + C
$$
Using substitution, note that
$$
\int f'(f(y)) \,f'(y)\,dy =
\int f'(u)\,du = f(u) + C = f(f(y)) + C
$$
Conclude that any $f$ satisfying our original equation must satisfy
$$
(y - 1)f(y) = f(f(y)) + C
$$
In terms of $x$, this says
$$
(f^{-1}(x) - 1)x = f(x) + C
$$
This isn't quite a solution, but at least we don't have any derivatives here.

Things to be said from here:

Note that with $y = 1$, we have
$$
0 \cdot f(1) = f(f(1)) + C \implies C = -f(f(1))
$$
Note also that if $f(y) = 0$ for any $y$, that $y$ must satisfy
$$
f(f(y)) = f(f(1))
$$
but if $f$ is "invertible" and therefore $1$ to $1$, then this should never happen.


$f:(-1,1)\rightarrow \mathbb{R}, \lim_{x\rightarrow 1} \frac{x+1}{x^2-1}$. Does $f$ have a limit at 1? $f:(-1,1)\rightarrow \mathbb{R}, \lim_{x\rightarrow 1} \frac{x+1}{x^2-1}$. Does $f$ have a limit at 1?

So, my assumption is obviously that this DNE, because after manipulation and viewing graphically, we see that it does not.

I started out my proof, trying to go by the negation of a limit definition.

$\exists \epsilon>0, \forall \delta>0, 0<|x-x_o|<\delta \Rightarrow |f(x)-L|\geq\epsilon$.

Where do I go from here? I am having a hard time moving forward with this. I tried towards contradiction, but this will not work algebraically, and also I am a bit uncomfortable doing this sequentially. Just looking for some rationale to help me get through this.

Assume it does, say, $L$, then for some $\delta>0$ we have if $x\in(1-\delta,1)$ then $|(x+1)/(x^{2}-1)-L|<1$, so for all such $x\in(1-\delta,1)$, $|1/(x-1)-L|<1$, or $1/(1-x)<1+|L|$. Since $1/(1-x)\rightarrow\infty$ as $x\rightarrow 1^{-}$, so $\infty\leq 1+|L|$ as we take limit both sides as $x\rightarrow 1^{-}$.


How to calculate the probability of at least an item dropping. So I play this online MMORPG where a monster drops items once killed.
There are a total of 10 items that can drop. Each of them has a 1% chance of dropping. A maximum of 2 items can drop at once. What are the odd's that at least one of the item drops?
Question 2
The actual number of items is 15 different items.
7 items have a .5% chance of dropping
1 item has a .6% chance of dropping
5 items have a 1% chance of dropping
2 items have a .2% chance of dropping
Assuming 2 items can drop at a max, what are the new odds then of getting at least 1 item to drop?

There are a total of 10 items that can drop. Each of them has a 1% chance of dropping. A maximum of 2 items can drop at once. What are the odd's that at least one of the item drops?

First, note that the requirement that "A maximum of 2 items can drop at once" directly implies that the drops cannot be independent.  Without much more information regarding how the choices are being made, there's no way to give you a mathematically correct answer.
Here are two simplified options (I'll point out a big problem with both afterwards):

Roll a $100$-sided die ten times, once for each item.  If the roll is a $1$, then that item is added to a vector of possible drops.  After you've finished all ten rolls, check how many items are in the vector.  If it's two or fewer, the player receives all (0, 1, or 2) of them.  If it's more than two, roll a $\binom{k}{2}$-sided die to choose which two the player will receive (each side corresponds to a different pair of items).
Roll a $100$-sided die once.  If the roll result $R_1$ is greater than $10$, then nothing drops for the player, and we don't continue.  Otherwise, item #$R_1$ drops for the player and we roll a $100$-sided die again.  If the second roll $R_2$ is between $1$ and $10$ inclusive but not $R_1$ again, then item #$R_2$ drops as well.

The probability that at least one drop occurs is then either $1-(1-0.01)^{10} \approx 0.095617925$ in case (1) or $0.1$ in case (2).
The problem in both cases is that the actual drop rates are wrong.  Choosing a pair of items in the first case lowers the drop rates to less than 1% while rolling a second time in the second case raises the drop rates to above 1%.  If I were to design a system to drop at most two items out of ten, I would do the second case, as it's less work-intensive and players tend to under-estimate small probabilities more often than they over-estimate them (there's a statistical reason for this), but if we want to fix it so the final drop probabilities are 1%, we need to fix both of them by solving for an unknown probability $p$ rather than thinking of it as a $100$-sided die roll.
Doing this yields the following equations in each case:

$$(1-p)^9(1+4p) = 0.95 \implies p\approx 0.0100116 \\ \implies \text{Prob. that at least one item drops} = 1-(1-p)^{10} \approx 0.0957241$$
$$p + 9p^2 = 0.01 \implies p\approx 0.0092328 \\ \implies \text{Prob. that at least one item drops} = 10p \approx 0.092328$$

In any case, I'm not touching question 2, as it has the same lack of independence shown here, with the same problems, but with the added complication of not being able to assume the correction factors are equal...

$$1-(1-0.01)^{10}$$
We found this by modelling it as a Binomial random variable.
Question 2 answer
First off, you should try to ask your question in one go (or ask a separate question). This makes it fair to the answerer(s).
Anyway, it is easier to ask the complement question: what is the chance of nothing dropping. This is the same strategy as earlier, really. After you answer this question (getting the answer $x$), then take $1-x$ and you have your required answer.


General rule for $(A \land B) \lor (\neg A \land D)$ I encountered the following small expression:
$$
(n\ge0\land y \gt 5) \lor(n \lt 0  \land x > 10).
$$
The answer should be easily $(x > 10 \land y \gt 5)$ but unfortunately I don't see how the components get factored out in a way to exploit the tautology $n\ge0 \lor n\lt 0 = true$ and simplify the expression.
I tried to use the distributive law but I got a longer and worse expression.
Maybe there is a general proven formula to back up the computation in these cases?

Any help would be extremely appreciated.

The proposition $(n\ge0\land y \gt 5) \lor(n \lt 0  \land x > 10)$ is not equivalent to $(x > 10 \lor y \gt 5)$.

For example, take $n=0$, $x=11$ and $y=0$.

However, it is true that $(n\ge0\land y \gt 5) \lor(n \lt 0  \land x > 10)$  implies $(x > 10 \lor y \gt 5)$.

Consider the cases $A = true$ and $\neg A = true$ and compare the truth values of these statements. So your answer should actually say $ x > 10 \vee y > 5$.


bayes rule question regarding exam performance related In an exam, there is a problem that $60\%$ of students know the correct answer. However, there is $15\%$ chance that a student picked the wrong answer even if he/she knows it and there is also a $25\%$ chance that a student does not know the answer but guessed it correctly. If a student did get the problem right, what is the chance that this student really knows the answer?

In an exam, there is a problem that 60% of students know the correct answer. However, there is 15% chance that a student picked the wrong answer even if he/she knows it and there is also a 25% chance that a student does not know the answer but guessed it correctly. If a student did get the problem right, what is the chance that this student really knows the answer?


Existence of length-monotonic homotopy in planar domains For a planar, simply connected domain $U \subset \mathbb{R}^2$ let $\gamma_0\colon [0, 1]\longrightarrow U$, $\gamma_1\colon [0, 1]\longrightarrow U$ be two differentiable curves in $U$ with same endpoints, i.e. $\gamma_0(0) = \gamma_1(0)$, $\gamma_0(1) = \gamma_1(1)$. Assume $\gamma_0$ and $\gamma_1$ are each injective (not self-intersecting) on $(0, 1)$, i.e. apart from the end points and also do not intersect each other.
Let $H \colon [0, 1]^2 \longrightarrow U$ be a homotopy with $H(t, j) = \gamma_j(t)$ for $j \in \{0, 1\}$.
I will denote the second parameter, the "morph parameter", of $H$ as $\theta$.
Assume that for all $\theta \in [0, 1]$, $H([0, 1], \theta)$ are disjoint sets, i.e. not any curves defined by $H$ intersect.

Let $L_{t_0, t_1}(\gamma)$ be the length functional
\begin{equation}
L_{t_0, t_1}(\gamma) \quad = \quad \int_{t_0}^{t_1}
\; || \dot{\gamma}(t) || \;
\; d t
\end{equation}

My questions:

Does always a length-monotonic homotopy exist?
Precisely: does always exist a $H$ like described above such that $L_{0, 1}(H(\cdot, \theta))$ is monotonic in $\theta$ and strictly monotonic if we assume $L_{0, 1}(\gamma_0) \neq L_{0, 1}(\gamma_1)$?

If this is asked too generally, would it help or make a difference if we assume the shorter curve, let's say $\gamma_0$ is shorter, is actually the shortest connection between $\gamma_0(0)$ and $\gamma_0(1)$?
Would it help or make a difference if we further assume $\gamma_0(0)$ and $\gamma_0(1)$ are on the boundary $\partial U$ and the longer curve $\gamma_1$ is actually a boundary section connecting $\gamma_0(0)$ and $\gamma_0(1)$?

Is it even possible to choose $H$ such that $L_{0, 1}(H(\cdot, \theta))$ is linear in $\theta$? (Intuitively I think if monotonic is possible it should be possible to exchange an amount of length between nearby curves by some perturbation, maybe enough to linearize $L_{0, 1}(H(\cdot, \theta))$.)

I especially wonder if this is a known (maybe classical) result or if it somehow follows "obviously" or "easily" from some known broader theorem. Or is it maybe not true?

Some context:

I am interested in finding the "length-energy" minimal homotopy in the sense of $H$ minimizing

\begin{equation}
\text{minimize} \quad \int_{0}^{1}
\Big( \frac{\partial}{\partial \theta} \; L_{0, 1}(H(\cdot, \theta)) \Big)^2 \;
\; d \theta
\end{equation}

under the boundary condition $H(t, j) = \gamma_j(t)$ for given $\gamma_j$ and $j \in \{0, 1\}$.
By Euler-Lagrange equations I can deduce that the ideal $L_{0, 1}(H^*(\cdot, \theta))$ should be linear in $\theta$ but I wonder if one can assume that such a homotopy always exists.

My thoughts so far:

In case that $\gamma_0$ and $\gamma_1$ enclose a convex domain, I guess one can show that property by analyzing the linear blend from $\gamma_0$ to $\gamma_1$, i.e. $\gamma_{\theta} = \theta \gamma_0 + (1-\theta) \gamma_1$. I guess this would not work where $\gamma_{\theta}$ moves through the shortest connection of $\gamma_0(0)$ and $\gamma_0(1)$ within the enclosed domain. This is why I mentioned above that it may be helpful to assume $\gamma_0$ is itself that shortest connection.

For the non-convex case I think Riemann's mapping theorem may be helpful. However, so far I wasn't able to conclude an answer from that theorem.

Further note that it is not true for non-planar surfaces: $\gamma_0$ and $\gamma_1$ might enclose a "mountain" and the homotopy would have to cross that mountain. Such a mountain could be made arbitrarily high, leading to arbitrarily long intermediate curves.
I guess it may be true for planar multiply connected domains, given that $\gamma_0$ and $\gamma_1$ are homotopic at all.

Please also don't hesitate to give partial answers or hints if you don't know the "perfect" full answer! Thanks in advance!

The answer to your question is positive. Below is a bit sketchy proof, making arguments complete would require much more work (pretty, much, writing a research paper).

First of all, I will work with simply-connected closed polygonal domains  $X$, rather than open simply connected planar sets  (see remarks at the bottom of the answer): The proof is already complicated in this setting.

Then $X$ is a length space: The length of a curve in $X$ is the usual Euclidean length:
$$
\ell(c)= \int_0^1 |c'(t)|dt.
$$
Define the intrinsic distance $d$ between two points $p, q$ in $X$ as the infimum of lengths of paths in $X$ connecting $p$ and $q$. One verifies that $X$ is complete and every two points are connected by a length-minimizing curve: Such curves are called geodesic. I will always parameterize geodesics with the constant speed. One verifies that geodesics are piecewise-linear paths in the plane.

One then verifies that $(X,d)$  is a CAT(0) space: Geodesic triangles in $(X,d)$ are "thinner" than their comparison triangles in the Euclidean plane $E^2$.

You can read more about CAT(0) spaces in the book

M. Bridson, A. Haefliger, Metric Spaces of Non-Positive Curvature, Springer-Verlag, 1999.

For instance, in order to see that  $(X,d)$  is a CAT(0) space triangulate the domain $X$ (using Euclidean triangles; you can even do so that the vertices of the triangulation are all on the boundary of $X$) and observe that the resulting simplicial complex satisfies the "link condition" (page 206 of the book): For every vertex $v$ of the triangulation, the length of each cycle in the link $L_v$, is $\ge 2\pi$. This condition is trivially satisfied since $L_v$   contains no cycles! From this, it follows that $(X,d)$ is locally CAT(0). Since $X$ is simply-connected, it follows that $(X,d)$ is CAT(0).

The definition of geodesics in metric geometry is different from the one you know in Riemannian geometry: They are required to be globally (rather than locally) length-minimizers. However, in CAT(0) setting, there is a local-to-global principle: Each local length-minimizer is a global length-minimizer.

The most important (for us) property of CAT(0) spaces is that the distance function $d$ is convex:

For any two geodesics $c_1(t), c_2(t)$ in $(X,d)$ the function $f(t)=d(c_1(t), c_2(t))$ is a convex function of one variable. (See page 176 of the book.)

From this, it follows that any two points $p, q$ in $(X,d)$ are connected by a unique (constant speed) geodesic $c_{pq}(t), t\in [0,1]$, and the latter depends continuously on $(p,q)\in X\times X$.

Now, Suppose that $\gamma_0(s), \gamma_1(s), s\in [0,1]$ are two piecewise-linear paths in $X$ satisfying
$$
\gamma_0(0)=\gamma_1(0), \gamma_0(1)=\gamma_1(1).
$$
(By an approximation argument, one can also handle general rectifiable paths.)

Their length (with respect to $d$) is the same as their Euclidean length. We construct the "geodesic" homotopy between these curves by the formula:
$$
F(s,t)= c_{\gamma_0(s)\gamma_1(s)}(t), s\in [0,1], t\in [0,1].
$$

Lastly, convexity of the distance function will imply that the function
$$
L(t)=Length (F(\cdot, t))
$$
is convex as a function of $t$.

What you are asking for, however, is monotonicity of length. I will describe the modification so that it is non-strictly monotonic. With a bit more work, one can get strict monotonicity.

For concreteness, assume that $L(1)=\ell(\gamma_1)\ge L(0)= \ell(\gamma_0)$. Let $L(t_0)$ denote the minimum of the function $L(t)$, $t_0\in [0,1]$. By convexity of $L(t)$, it is decreasing on $[0,t_0]$ and increasing on $[t_0, 1]$ (both non-strictly on some interval containing $t_0$). Let $t_1\in [t_0, 1]$ be maximal such that $L(t_1)=L(0)$. I will modify the homotopy $F(s,t)$ to a new homotopy $G(s,t)$ as follows:

For $t\in [t_1,1]$,  set $G(s,t)=F(s,t)$, since the length $L(t)$ is strictly increasing on $[t_1,1]$.

For $t\in [0,t_1]$ I will define $G(s,t)$ so that the curve
$$
c_t: s\mapsto G(s,t)
$$
has length $L(0)$. Namely, let $\lambda(t)$ denote the difference $L(0)-L(t)$: It is $\ge 0$ since $t\in [0, t_1]$. Extend $c_t$ to $[1,1+\lambda(t)]$ so that:

(a) The extension curve $b_t$ has constant speed (except for finitely many points where the derivative does not exist).

(b)  For $s\in [1, 1+ \frac{1}{2}\lambda(t)]$ the extension curve backtracks length $\lambda(t)/2$ along $c_t$.

(c) For $s\in [1+ \frac{1}{2}\lambda(t), 1+\lambda(t)]$ the extension curve goes back to $c_t(1)$ covering length   $\frac{1}{2}\lambda(t)$ along the way.

The resulting curve $a_t(s), s\in [0, 1+\lambda(t)]$, now has length $L(0)$. The only problem is that it is defined not on the unit interval. But we can reparameterize it with constant speed to redefine it on the unit interval. The result is a map $G(s,t)$. One verifies that this map is still continuous. By the construction, each curve $s\mapsto G(s,t)$ has length $L(0)$ for $s\in [0,t_1]$.

Two more things:

One can eliminate the assumption that $X$ has polygonal boundary by an approximation argument (the, suiably defined, limit of a sequence of CAT(0) spaces is again CAT(0)).
If $L(0)<L(1)$, one can also modify the above proof to make it work in open domains in the plane. (Again, by an approximation argument.) However, I am not sure how to deal with the case $L(0)=L(1)$: Approximation arguments will no longer work.


Proof that the product of primitive Pythagorean hypotenuses is also a primitive Pythagorean hypotenuse Just to be clear, I call an integer $c$ a 'primitive Pythagorean hypotenuse' if there exist coprime integers $a$ and $b$ satisfying $a^2+b^2 = c^2$. I noticed that the set of such primitive Pythagorean hypotenuses seems to form a closed set under multiplication (and indeed this is backed up by this Mathworld page -- see equations (25)-(26)). However, I can't find a proof of it (the link above provides a book reference but I don't have access to it), or come up with one myself.

Some thoughts: Euler showed that $c$ is a primitive Pythagorean triple iff it is odd and can be written as the sum of two squares $c = m^2+n^2$ for some coprime integers $m$ and $n$. It is straightforward to show that the product of a sum of two squares is also a sum of two squares (and hence the set of all Pythagorean hypotenuses is closed under multiplication), but I'm having trouble with the primitive/coprime part. In other words I can show that if $c_1 = m_1^2 + n_1^2$ and $c_2 = m_2^2 + n_2^2$ then there exist $m_3$ and $n_3$ such that $c_1c_2 = m_3^2 + n_3^2$, but I can't show that if $gcd(m_1,n_1)=gcd(m_2,n_2)=1$ then it is possible to choose $m_3$ and $n_3$ such that $gcd(m_3,n_3)=1$. Any hints or references would be appreciated!

Edit (in response to individ's comments): Note that the formulae
$$ m_3 = m_1 n_2 - n_1 m_2 \ , \ n_3 = m_1 m_2 + n_1 n_2 $$
and
$$ m_3 = m_1 n_2 + n_1 m_2 \ , \ n_3 = m_1 m_2 - n_1 n_2 $$
do not always produce coprime $m_3$ and $n_3$. The earliest example of this I could find is
$$ m_1 = 8, n_1 = 1, m_2 = 31, n_2 =92 $$
for which the first formula above gives $m_3 = 705, n_3 = 340$ (both divisible by 5), and the second formula above gives $m_3=767, n_3=156$ (both divisible by 13). However $m_3^2 + n_3^2 = 612,625$ is still the hypotenuse of a primitive triple because
$$ 199176^2 + 579343^2 = 612625^2  $$
and $gcd(199176,579343)=1$. (Sorry for the rather ugly example, but it was the simplest I could find (maybe because I don't know how to search efficiently!).)

Let consider the ring of Gaussian integers $\mathbb Z[i]$.
For $\zeta=a+ib\in \mathbb Z[i]$ we say that $\zeta$ is primitive if $\gcd(a,b)=1$.
Note that $\zeta$ is primitive if and only if for each $d\in\mathbb Z$, $d\mid\zeta$ implies $d=\pm 1$. Consequently, factors of primitive numbers are primitive.

An odd integer $x\in\mathbb Z$ is a primitive Pythagorean hypotenuse if and only if there exists a primitive $\xi\in\mathbb Z[i]$ such that $x=\xi\bar\xi$.

Let $x=\xi\bar\xi$ be a primitive Pythagorean hypotenuse and, since $\mathbb Z[i]$ is an UFD, take the prime factorization $\xi=\pi_1^{e_1}\cdots \pi_r^{e_r}$.
Since $\xi$ is primitive and $x$ odd, each factor $\pi_j$ is primitive and with no common factor with $2$, hence $\Im(\pi_j^4)\neq 0$.
Since $\pi_j\bar\pi_j\mid x$ can assume that $\Im(\pi_j^4)>0$ for each $j$.

Let $y=\eta\bar\eta$ be another primitive Pythagorean hypotenuse with $\eta=o_1^{d_1}\cdots o_s^{d_S}$ and $\Im(o_j^4)>0$.

We claim that $\xi\eta$ is primitive.
For assume on contrary that $d\mid\xi\eta$ for some $d\in\mathbb Z$.
Let $\pi\in\mathbb Z[i]$ be an irreducible factor of $d$. Then, wlog, $\pi\mid\xi$.
Then $\pi$ is primitive and $\bar\pi\mid d\mid\xi\eta$, but $\bar\pi\not\mid\xi$, hence $\bar\pi\mid \eta$.
This is a contradiction, because $\Im(\bar\pi^4)<0$.

This proves that $xy$ is a primitive Pythagorean hypotenuse.

Rewrite the equation in this form:

$$(m^2+n^2)(x^2+y^2)=z^2+q^2$$

Then the solution is always there.

$$z=mx+ny$$

$$q=nx-my$$


Show that set of Real numbers has the same cardinality as a set of Irrational Numbers. How can I show that sets $| \mathbb R-\mathbb Q |$ and $ | \mathbb R |$ have same cardinality.
My Solution:
As long as for element in one set I can match it with unique element in another set they have same cardinality:
After removing $\mathbb Q $ from $\mathbb  R$ I can shift elements of Irrational numbers to correspond to elements of two sets match like this:
$
\begin{array}{c|c|c|c|c|c}
\mathbb R&0&1&\cdots&n&\cdots\\\hline
\mathbb R\setminus\mathbb Q & \sqrt{2} &\sqrt{5} &\cdots & \sqrt{n+1} &\cdots
\end{array}
$ Note that I use n as Real number for simplicity.

Even if this solution is correct, I feel like Professor won't accept it on exam.
How would formal solution look like?

Define
$$f(x)=\begin{cases}x+\sqrt 2\text{ if } x-n\sqrt 2\in\Bbb Q\text{ for some integer }n\ge 0 \\ x\text{ otherwise}\end{cases}$$

Clearly, $\mathbb{R} \setminus \mathbb{Q}$ has at most the same cardinality as $\mathbb{R}$ and is an infinite set. The set can therefore be either countable or of the same cardinality as $\mathbb{R}$.

Assuming the continuum hypothesis, if $|\mathbb{R} \setminus \mathbb{Q}| \neq |\mathbb{R}|$, we must then have that $\mathbb{R} \setminus \mathbb{Q}$ is countable.

But the union of two countable sets is countable, and $(\mathbb{R} \setminus \mathbb{Q}) \cup \mathbb{Q} = \mathbb{R}$. Therefore $\mathbb{R} \setminus \mathbb{Q}$ must have the same cardinality as $\mathbb{R}$.


Prove that OD is a the angle bisector of the angle BOC. Let $ABC$ be a non-isosceles triangle and $I$ be the intersection of the three internal angle bisectors. Let $D$ be a point of $BC$ such that $ID \perp BC$ and $O$ be a point on $AD$ such that $IO \perp AD$.
Prove that $OD$ is a the angle bisector of $\angle BOC$.

This problem can be solve using the knowledge about Harmonic conjugate and polar. Notice me if you need those information.

hope this still can help.

Thanks you for your solution. #Samara
My solution: