问:
Why is the equal volume sufficient to solve the puzzle without any calculations?
I was reading the following puzzle:

There is a glass of juice and a glass of water with identical volumes.
We take 1 full spoon of the juice and put it in the glass of water.

After briefly stirring the mixture, we put a full spoon of the mixture
back into the glass of juice.

Question: which amount is greater? The
amount of juice in the water or the amount of water in the juice?

I worked it out that the amounts are equal by calculating the ratio of juice in the water etc and assuming a prefect mixture.

But although the solution  reported the same result, I don't understand really understand its logic and seems faulty to me.

The solution states:

After the exchange the amount of juice in the water must be the same as the amount of water in the juice, since the volumes of the two
glasses after the exchange are the same. The juice missing from the
one glass was moved to the other having the missing volume replaced by
water.

So I don't have a problem proving it algebraically. I am trying to understand the intuition behind ths stated answer.

Isn't it based on the assumption that e.g. the juice poured in the water glass might be in lower parts and we just remove using the spoon, water from the surface?

Otherwise why is the equal volume used here? It seems to me that we remove a volume of juice from the juice glass (e.g. x which is the volume of the spoon) and we put back in a volume of a mixture (not water).

答:
It doesn’t matter just what combination of water and juice is returned to the juice glass: since the glasses end up equally full, whatever amount of juice is missing from the juice glass must be exactly compensated for by the amount of water brought in from the water glass. This can be verified algebraically as follows.

At the end the juice glass contains some amount $J$ of juice and some amount $w$ of water, and the water glass contains some amount $W$ of water and $j$ of juice. We know that

$$J+j=W+w$$

and

$$J+w=W+j\,.$$

Subtracting the second equation from the first, we find that

$$j-w=w-j\,,$$

so $w=j$ and hence $W=J$. Note that the argument does not assume any specific kind of mixing (e.g., uniform) in the water glass after the first transfer.


问:
Invert Trigonometric System of Equations
In my research, I have a system of trig equations that I would like to invert. I know $\alpha$ and $\beta$ ($\theta$ is a constant) in the following system.

$$\cos \alpha  = \cos \theta \cos x + \sin \theta \sin x \cos y$$
$$\tan \beta = \frac{\cos x +\cos \theta \cos \alpha}{\sin \theta \sin x \sin y} $$

I would like to find an inversion in the form:
$$\text{trig}(x) =\; ...$$
$$\text{trig}(y) = \;...$$

How can this be done?

答:
It's doubtful there are explicit formulas as you write them. Nevertheless, using tangent half angle formulas:

$$\cos x=\dfrac{1-t^2}{1+t^2}, \ \ \sin x = \dfrac{2t}{1+t^2}, \ \ \tan x=\dfrac{2t}{1-t^2}$$

$$\cos y=\dfrac{1-u^2}{1+u^2}, \ \ \sin y = \dfrac{2u}{1+u^2}, \ \ \tan y=\dfrac{2u}{1-u^2}$$

with  $t=\tan \tfrac{x}{2} \ \text{and} \ \ u=\tan \tfrac{y}{2}$, you have a method of attack providing solutions in (most) trigonometric equations.

Indeed, with these formulas, the given system:

$$\begin{cases}\cos \alpha & =& \cos \theta \cos x + \sin \theta \sin x \cos y\\
\tan \beta & = & \dfrac{\cos x +\cos \theta \cos \alpha}{\sin \theta \sin x \sin y}\end{cases}$$

becomes, with evident notations:

$$\begin{cases}C_1 & = & C_3 \dfrac{1-t^2}{1+t^2}+S_3\dfrac{2t}{1+t^2} \dfrac{1-u^2}{1+u^2}\\
T_2 & = & \dfrac{\dfrac{1-t^2}{1+t^2} +C_3 C_1}{S_3 \dfrac{2t}{1+t^2} \dfrac{2u}{1+u^2}}\end{cases}$$

In this way, your issue is brought back to the intersection between 2 curves with (in general) 4th degree polynomial equations:

$$\begin{cases}S_3 2t(1-u^2)& = &(1+u^2)(C_1(1+t^2)-C_3(1-t^2))  \ \ \ & (a)\\4T_2S_3tu & = & (1+u^2)((1-t^2)+C_1C_3 (1+t^2))  \ \ \ & (b)\end{cases}\tag{1}$$

which can have at most $4 \times 4 = 16 $ real solutions $(t_k,u_k)$.

Here is a case with 4 solutions (corresponding to case $\alpha=\theta=\pi/4$ and $\beta=$arctan $2$): the curve in blue (resp. in red) has equation (a) (resp. (b)) in (1);
($t$ on abscissas and $u$ on the ordinates) giving, for the indicated root, $t=0.5782=\tan \dfrac{x}{2} \implies x=1.0485 $ radians and the same thing for $u=0.5164 =\tan \dfrac{y}{2} \implies y=0.9534 $ radians.

Edit: An afterthought after having seen the elegant solution by Claude Leibovici.

I didn't notice at first that equations (1) (a) and (b) are separable under the form:

$$\begin{cases}\dfrac{1-u^2}{1+u^2}& = &\dfrac{C_1(1+t^2)-C_3(1-t^2)}{S_3 2t}  \ \ \ & (a)\\ \dfrac{2u}{1+u^2} & = & \dfrac{(1-t^2)+C_1C_3 (1+t^2)}  {2T_2S_3t}\ \ \ & (b)\end{cases}\tag{2}$$

where we recognize in the two LHS $\cos y$ and $\sin y$ resp. Expressing that $\cos^2 y+\sin^2 y=1$ gives the same kind of fourth degree equation for $t$ as Claude has found...

ContentLicense: CC BY-SA 4.0


问:
On proving that $f: \mathbb{R}^2 \to \mathbb{R}$ given by $(x, y) \mapsto xy$ is continuous in the topological sense (Adams and Franzosa)
Please do not use any material related to metrics; these are not yet defined at this point in the text.

Assume I am working with the standard topology in all cases.

Let $(a, b) \subset \mathbb{R}$. I wish to show that the preimage induced by $f$ is open; i.e.,
$$f^{-1}((a, b)) = \{(x, y) \in \mathbb{R}^2 \mid a < xy < b\}\text{.}$$

This is from Example 4.6 of Adams and Franzosa:

We can prove this explicity by showing that for each point $(p, q) \in f^{-1}((a, b))$, there is an open square centered at $(p, q)$ and contained in $f^{-1}((a, b))$. In fact, if we set $m = \min\{b - pq, pq - a\}$ and choose $\delta > 0$ so that $\delta|p|$, $\delta|q|$, and $3 \delta^2$ are all less than $m/3$, then it can be shown that $(p - \delta, p + \delta) \times (q - \delta, q + \delta) \subset f^{-1}((a, b))$.

Could someone please explain how one yields such a solution?

It is clear that $m$ represents the minimum vertical distance (in $\mathbb{R}^2$) between a point in $f^{-1}((a, b))$ and the two lines which bound the region, but I have no idea how the $\delta$ is chosen.

答:
I am not sure of the point in giving a proof like that when an extra line or two demonstrates the point clearly. It is not like space is at a premium in a 500+ page book!

We want to show that for the given $\delta$, if $x \in B(p,\delta)$ and $y \in B(q,\delta)$ then $xy \in (a,b)$. (Note that such $y$ satisfy $|y| < |q|+\delta$.)

Note that $m=\min(|a-pq|,|b-pq|)$, so it is sufficient to show that
$|xy-pq| < m$, since then $xy \in B(pq, m) \subset (a,b)$.

\begin{eqnarray}
|xy-pq| &\le& |xy-py|+|py-pq| \\
&\le& |y||x-p| + |p||y-q| \\
&\le& (|q|+\delta) \delta+ |p| \delta \\
&=& |q|  \delta + \delta^2 + |p| \delta \\
&\le& {m \over 3} + {1 \over 3} {m \over 3} + {m \over 3} \\
&<& m
\end{eqnarray}


问:
Why the fourth homology of the cofibre of Moore space $H_4(C) = 0$?
Why the fourth homology of the cofibre of Moore space (of dimension 2) equals $0$ i.e. $H_4(C) = 0$?

Could anyone explain this to me, please? I think it is related to the construction of Moore space of dimension 2 and that there are no cells in the fourth dimension, but why there are cells in the third dimension?

Definition:

Let $G$ be an abelian group and $n$ an integer $\geq 2.$ A Moore space of type $(G,n)$ is $1-$connected, $CW-$complex $X$ such that:

$$ \widetilde{H}_i(X) = \begin{cases}
      0 & if \, i \neq n, \\
      G &  if   i = n.
   \end{cases} $$

答:
Use the long exact sequence in homology as @JHF said: given a map $f: X \to X$ with cofiber $C$, it will look like
$$
\dots \to H_4(X) \xrightarrow{f_*} H_4(X) \to H_4(C) \to H_3(X) \to \dots
$$
You know from the definition of $X$ that its homology groups in this range are zero, so the long exact sequence looks like
$$
\dots \to 0 \to 0 \to H_4(C) \to 0 \to \dots
$$


问:
Factorize in R[x]
I have the polynomial $x^8+1$, I know that there's no root for solve this in $\Bbb R[x]$ but i want to factorize this to the minimal expression. This is possible or this is irreducible?</p>

答:
Fun fact:

$$x^4+1=(x^2+\sqrt{2}x+1)(x^2-\sqrt{2}x+1).$$

This can be derived by setting $x^4+1$ equal to a product of two monic quadratics with unknown coefficients and then solving for said coefficients little by little. As a consequence,

$$x^8+1=(x^4+\sqrt{2}x^2+1)(x^4-\sqrt{2}x^2+1).$$

We can go further. For example, set

$$x^4+\sqrt{2}x^2+1=(x^2+ax+b)(x^2-ax+1/b),$$

yielding

$$\begin{cases}-a^2+b+1/b & =\sqrt{2} \\ a/b-ab & = 0 \end{cases} $$

Rule out $a=0$ to obtain $b=\pm1$ from the second equation, then plug those candidates into the first equation yielding $a=\sqrt{\pm2-\sqrt{2}}=\sqrt{2-\sqrt{2}}$ with $b=1$. The second factor of $x^8+1$ that is written above is similarly reducible. I leave the details as an exercise. The full factorization is

$$\begin{array}{lll} x^8+1 & = & \left(x^2+\sqrt{2-\sqrt{2}}x+1\right) \times \left(x^2-\sqrt{2-\sqrt{2}}x+1\right) \\ &  \times & \left(x^2+\sqrt{2+\sqrt{2}}x+1\right) \times\left(x^2-\sqrt{2+\sqrt{2}}x+1\right). \end{array}$$

over the real numbers $\bf R$. With the quadratic formula applied to the above you can get the roots to $x^8+1$ exactly (they are precisely the primitive $16$th roots of unity) in the form of nested radicals, and hence the full factorization in $\bf C$.

By the way, I should mention that the only nonlinear polynomials over $\bf R$ that are irreducible are quadratics with negative discriminant. This is because the nonreal roots of any real-coefficient polynomial can be paired off into conjugates, and then each conjugate pair of linear factors can be put together to obtain a real quadratic, thus every real-coefficient polynomial can be factored into real linear and quadratic factors.

Over $\bf Q$, as Belgi notes, a simple shift allows Eisenstein's criterion to apply.

ContentLicense: CC BY-SA 3.0

Title: Factorize in R[x]


问:
Identities with quadratic forms
Let $y_1,\dots, y_n$ be vectors in $\mathbb{R}^p$ and let $\mu$ be an additional vector in $\mathbb{R}^p$. Let $M\in\mathbb{R}^{p\times p}$ be a symmetric positive definite matrix. I have some difficulties into prove the following identity
\begin{equation}\sum_{i=1}^n (y_i-\mu)'M^{-1}(y_i-\mu)=n(\bar{y}-\mu)'M^{-1}(\bar{y}-\mu)+\sum_{i=1}^n (y_i-\bar{y})'M^{-1}(y_i-\bar{y})\end{equation}
where
\begin{equation}\bar{y}\triangleq \frac{1}{n}\sum_{i=1}^n y_i\end{equation}
I've tried to expand the generic product $(y_i-\mu)'M^{-1}(y_i-\mu)$ but this seems to me useless to prove the previous identity.

答:
Using linearity of the transpose and matrix multiplication we get

\begin{align}
(y_i-\mu)^TM^{-1}(y_i-\mu) &= (y_i-\overline{y})^TM^{-1}(y_i-\mu) + (\overline{y} - \mu)^TM^{-1}(y_i-\mu)\\
&= (y_i-\overline{y})^TM^{-1}(y_i-\overline{y}) + (y_i-\overline{y})^TM^{-1}(\overline{y}-\mu) + (\overline{y} - \mu)^TM^{-1}(y_i-\mu).
\end{align}

Now since $(\overline{y} - \mu)^TM^{-1}(y_i-\mu)$ is a scalar and $M^{-1}$ is symmetric, we have
$$(\overline{y} - \mu)^TM^{-1}(y_i-\mu) = \left((\overline{y} - \mu)^TM^{-1}(y_i-\mu)\right)^T = (y_i-\mu)^TM^{-1}(\overline{y} - \mu)$$
so
$$(y_i-\mu)^TM^{-1}(y_i-\mu) = (2y_i - \overline{y}-\mu)^TM^{-1}(\overline{y}-\mu).$$
Summing over $i=1, \ldots, n$ and again using linearity gives
\begin{align}
\sum_{i=1}^n (y_i-\mu)^TM^{-1}(y_i-\mu) &= \sum_{i=1}^n (2y_i - \overline{y}-\mu)^TM^{-1}(\overline{y}-\mu) +\sum_{i=1}^n(y_i-\overline{y})^TM^{-1}(y_i-\overline{y}) \\
&= \left(2\sum_{i=1}^n y_i - n\overline{y}-n\mu \right)^T M^{-1}(\overline{y}-\mu)+\sum_{i=1}^n(y_i-\overline{y})^TM^{-1}(y_i-\overline{y}) \\
&= (2n\overline{y} - n\overline{y}-n\mu)^TM^{-1}(\overline{y}-\mu)
+\sum_{i=1}^n(y_i-\overline{y})^TM^{-1}(y_i-\overline{y}) \\
&= n(\overline{y}-\mu)^TM^{-1}(\overline{y}-\mu)
+\sum_{i=1}^n(y_i-\overline{y})^TM^{-1}(y_i-\overline{y}).
\end{align}

Title: Identities with quadratic forms


问:
Is the weak topology on $\mathbb{R}^{\infty}$ the same as the box topology?
Let $\mathbb{R}^{\infty}=\bigcup\limits_{n=1}^{\infty}\mathbb{R}^{n}$ be the subset of $\mathbb{R}^{\omega}$ consisting of all sequences which are nonzero for only finitely many terms.  Give $\mathbb{R}^{\infty}$ the weak topology, that is, $A\subset \mathbb{R}^{\infty}$ is open iff $A\cap \mathbb{R}^{n}$ is open in $\mathbb{R}^{n}$ for each $n$.  Is $\mathbb{R}^{\infty}$ a subspace of $\mathbb{R}^{\omega}$ with the box topology?

The reason why I think this is true is because it looks like the box topology is the weak topology with respect to the natural inclusions $\mathbb{R}^n\to\mathbb{R}^{\omega}$ [Edit: I have doubts about this particular claim.]

答:
Yes, the weak topology and the box topology on $\mathbb{R}^\infty$ are the same.  One direction is easy: it is clear that every basic open subset in the box topology has open intersection with each $\mathbb{R}^n$ and so is open in the weak topology.

The converse requires more work.  Let me first remark that both topologies are translation-invariant: this is obvious for the box topology, and for the weak topology, it follows from the fact that any translate of $\mathbb{R}^n$ by an element of $\mathbb{R}^\infty$ is contained in $\mathbb{R}^N$ for some $N$.  Now suppose $U\subseteq\mathbb{R}^\infty$ is an open neighborhood of a point $p$ in the weak topology; we may translate to assume $p$ is the origin.  Then $U\cap\mathbb{R}$ contains some interval $[-\epsilon_1,\epsilon_1]$.  Since $[-\epsilon_1,\epsilon_1]$ is compact, openness of $U\cap\mathbb{R}^2$ implies it actually contains a box $[-\epsilon_1,\epsilon_1]\times[-\epsilon_2,\epsilon_2]$ by the tube lemma.  Continuing this process, we get a sequence $(\epsilon_n)$ of positive numbers such that $U\cap\mathbb{R}^n$ contains $\prod_{i=1}^n[-\epsilon_i,\epsilon_i]$ for each $n$.  This implies that $U$ contains $\prod_{i=1}^\infty(-\epsilon_i,\epsilon_i)\cap\mathbb{R}^\infty$ and so is a neighborhood of the origin in the box topology as well.

(Alternatively, instead of using a translation to assume $p$ is the origin, we could have started by picking $n$ such that $p\in\mathbb{R}^n$ and taking a compact neighborhood $K$ of $p$ in $\mathbb{R}^n$ contained in $U\cap\mathbb{R}^n$, and then found a set of the form $K\times\prod[-\epsilon_i,\epsilon_i]$ contained in $U$.)

More generally, a similar argument shows that given a sequence of locally compact pointed spaces $(X_n)$, the box topology on the "direct sum" $\bigoplus X_n$ (i.e. the subset of the product $\prod X_n$ consisting of points which are the basepoint on all but finitely many coordinates) is the same as the colimit topology considering $\bigoplus X_n$ as the colimit of the finite products.


问:
Differential equation with the Substitution method
I'm trying to solve this equation below :

$$ y' = \sin\left(\frac{y}{x}\right) + \frac{y}{x}  \tag 1 $$

The first step was to to substitute $\frac{y}{x}$ with $u$

=>   $ u = \frac{y}{x}$     => $y' = u'x + u \tag 2$

Then with
$(1) = (2)$,  I got at the end

$$\dfrac{\ln\left(\cos\left(y\right)+1\right)-\ln\left(1-\cos\left(y\right)\right)}{2} = \ln|x| + C$$

And after more simplification :
$$\frac{\cos(y)}{1-\cos(y)} = 2Cx   $$

How can I get the general function from this equation ?

答:
From your last line:
$$\frac{\cos(y)+1}{1-\cos(y)} = Cx^2$$
$$\cos(y)+1 = Cx^2(1- \cos y)$$
$$ \cos y (1+Cx^2)=Cx^2-1$$
$$ \cos y =\dfrac {Cx^2-1}{ Cx^2+1}$$
$$\implies y(x)=\cos^{-1} \left ( \dfrac {Cx^2-1}{ Cx^2+1} \right)$$

Or more simply:

$$u'x= \sin u$$
$$\int \dfrac {du}{\sin u}=\int \dfrac {dx}{x}$$
$$-\ln (\cot u/2)=\ln x +K$$
$$\cot \dfrac u 2=\dfrac C x$$
$$u=2 \cot ^{-1} \left ( \dfrac Cx \right)$$
$$\boxed {y(x)=2x \cot ^{-1} \left ( \dfrac Cx \right)}$$

For the integral note that:
$$I=\int \dfrac {dx}{\sin x }=\int \dfrac {dx}{2 \sin x/2 \cos x/2}$$
$$I=\int \dfrac 12\dfrac {\cos x/ 2dx}{\sin x/2 \cos ^2 x/2}$$
$$I=\int \dfrac {d \tan \dfrac x 2}{\tan \dfrac x2}=\ln \tan \dfrac x 2+C$$

Or you can use Weierstrass substitution
$$\int \dfrac {dx}{\sin x} =\int \dfrac {1+t^2}{2t}\dfrac {2dt}{1+t^2}
=\int \dfrac {dt}{t}=\ln t +C$$
Where $t=\tan \dfrac x 2$


问:
How do I solve $2\left(5^x\right)+5^{-x}=3$ for $x$?
I understand logs and can solve simpler equations like

$$
7^x=3 \\
\log7^x=\log3\\
x = \frac{\log3}{\log7}
$$

But the addition in this particular expression really throws me off and I have no idea how to even approach it:

$$
2\left(5^x\right)+5^{-x}=3
$$

If it was a multiplication, no problem, but I have never seen problems with addition like this before.

I have tried rearranging and factorising, e.g. $5^{-x}\left(2\left(5^{2x}\right)+1\right)=3$, but can someone show me what I need to do to solve problems of this form?

Body:
you can put $y=5^x$

so $2y+\frac{1}{y}=3$ $\rightarrow$$ 2y^2+1-3y=0$

$\triangle =9-8=1$

so , $Y=1$ OR $y=\frac{1}{2}$

finally;

$y=5^x=1$$\rightarrow$ $ x=0$

or
$y=5^x=\frac{1}{2}$$\rightarrow$ $ x=\frac{-ln(2)}{ln(5)}$


答:
Alternative perspective.

Adopt the syntax that $J$ is the juice that remains in the juice glass, $j$ is the amount of juice that was transferred, and $w$ is the amount of water that was transferred.

The challenge is to prove that $j = w.$

It is totally irrelevant whether the initial volume of the juice and water glasses are equal.  It is also totally irrelevant whether there is one transfer or multiple transfers.  The only critical point is that the volume of the mixture in the Juice glass after the transfer(s) is identical to the initial volume in the Juice glass.

Therefore,

$$J + j ~=~ \text{starting volume in Juice glass} ~=~ \text{ending volume in Juice glass} ~=~ J + w.$$

Therefore,

$$j = w.$$

Title: Why is the equal volume sufficient to solve the puzzle without any calculations?

Body:
I was reading the following puzzle:

There is a glass of juice and a glass of water with identical volumes.
We take 1 full spoon of the juice and put it in the glass of water.

After briefly stirring the mixture, we put a full spoon of the mixture
back into the glass of juice.

Question: which amount is greater? The
amount of juice in the water or the amount of water in the juice?

I worked it out that the amounts are equal by calculating the ratio of juice in the water etc and assuming a prefect mixture.

But although the solution  reported the same result, I don't understand really understand its logic and seems faulty to me.

The solution states:

After the exchange the amount of juice in the water must be the same as the amount of water in the juice, since the volumes of the two
glasses after the exchange are the same. The juice missing from the
one glass was moved to the other having the missing volume replaced by
water.

So I don't have a problem proving it algebraically. I am trying to understand the intuition behind ths stated answer.

Isn't it based on the assumption that e.g. the juice poured in the water glass might be in lower parts and we just remove using the spoon, water from the surface?

Otherwise why is the equal volume used here? It seems to me that we remove a volume of juice from the juice glass (e.g. x which is the volume of the spoon) and we put back in a volume of a mixture (not water).


问:
Make sure that $m \mathbb{Z}\times n\mathbb{Z}$ is an ideal of $\mathbb{Z} \times \mathbb{Z} $
good night!

Make sure that $m \mathbb{Z}\times n\mathbb{Z}$ in the ring $\mathbb{Z} \times \mathbb{Z} $ is an ideal.

I couldn’t come up with a convincing answer. Could you help me? Thanks in advance!

I know that ideal is a product $R\times S$ of rings with identity has the form $I\times J$, where $I, J$ are ideals in $R, S$ respectively. Moreover, since $\mathbb{Z}$ is a principal ideal domain, every ideal of $ \mathbb{Z} $ has the form $m\mathbb{Z}$ for some $m$. Hence every ideal of $ \mathbb{Z}\times \mathbb{Z} $ has the form $m\mathbb{Z} \times n\mathbb{Z}$ for soem $m, n \in \mathbb{Z}.$

But, Is it true?

答:
First, make sure that $m\mathbb Z$ and $n\mathbb Z$ are ideals of $\mathbb Z$. How would you do that? You just take generic  elements $a\in m\mathbb Z$ and $b\in\mathbb Z$ and check that $ab\in m\mathbb Z$, right?

Now, assuming that operations on products are defined coordinate-wisely, you can use the same method to prove that $I=m\mathbb Z\times n\mathbb Z$ is an ideal of $R=\mathbb Z\times\mathbb Z$. In fact, a generic element of $I$ has form $(a,a')$ with $a\in m\mathbb Z$ and $a'\in n\mathbb Z$, and for any $(b,b')\in\mathbb Z\times\mathbb Z$, their product is defined as
$$ (a,a')(b,b')=(ab,a'b'). $$
I believe that you're able to continue by yourself from here :)


答:
Over $\mathbb{C}$, this polynomial splits into linear factors of 8 of the 16 solutions to $x^{16} - 1 = 0$. The irreducible factors of this equation are the cyclotomic polynomials.

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

So $x^8 + 1$ is indeed irreducible over $\mathbb{Q}$, as it is a cyclotomic polynomial.

Over $\mathbb{R}$, this polynomial splits into 4 quadratic polynomials obtained by multiplying out conjugate pairs of 16th roots of unity which have order 16.

Title: Factorize in R[x]

Body: I have the polynomial $x^8+1$, I know that there's no root for solve this in $\Bbb R[x]$ but i want to factorize this to the minimal expression. This is possible or this is irreducible?</p>


问:
Expectations - dependence and independence
Suppose you have two random variables $X$ and $Y$.
Is $E[aX+bY]=aE[X]+bE[Y]$ true if $X$ and $Y$ are independent or even dependent?

And, if $X$ and $Y$ are independent, is it true that $E[XY]=E[X]E[Y]$? Is this true if they are dependent?

答:
The expected value operator is linear. Therefore,
$$E[aX+bY]=aE[X]+bE[Y]$$
If the random variables $X$ and $Y$ are independent, then we have
$$E[XY]=E[X]E[Y]$$
I hope this helps you understand.


问:
Expected number of trials until $k$ failures or number of trials reach $n$
I am trying to find the expected number of trails until the $k$-th failure
or until the number of trials hit $n$, whichever comes first. The success   probability of the trial is $p$.

My calculation gave me the below result.
$$
\sum_{i=0}^{k-1} i{{n}\choose{i}} p^{n-i}(1-p)^{i} + \sum_{i=k}^n i { k-1+i \choose i} p^{i}(1-p)^k
$$

But it seems the result is
$$
\sum_{i=0}^{k-1} i{{n}\choose{i}} p^{n-i}(1-p)^{i} + \sum_{i=k}^n i { i-1 \choose k-1} p^{i-k}(1-p)^k
$$

I don't know what is wrong with my result and how I can get the correct result.

答:
Both expressions are wrong. The correct one is
$$
\sum_{i=0}^{k-1} \color {red}n{{n}\choose{i}} p^{n-i}(1-p)^{i} + \sum_{i=k}^n i { i-1 \choose k-1} p^{i-k}(1-p)^k.\tag1
$$
Here the first term accounts for the events with the number of failures ($i $) in $n $ trials being less than $k $, and the second term accounts for the events with $k $ failures (the $k $-th failure being achieved in $i $-th trial).

The equation (1) can be written also in a more symmetric form:
$$
n\sum_{i=0}^{k-1}{{n}\choose{i}} p^{n-i}(1-p)^{i} + k\sum_{i=k}^n { i\choose k} p^{i-k}(1-p)^k.\tag2
$$


问:
Why $\lim_{r\to 1^-} \int_0^{2\pi}\ln(|f(re^{i\vartheta})|)d\vartheta=-\infty$?
I am studying Greene and Krantz' "Function theory in one complex variable". In section $13.4$, they want to prove that, given $f\in H^p, p\in (0,+\infty),$ if the radial limit function $\tilde f$ is zero on a set of positive measure then $f\equiv 0$.
Their proof is quite short: if $f\not\equiv 0$, we can assume wlog $f(0)\neq 0$ and then by Jensen's formula (given $r<1:\forall \vartheta f(re^{i\vartheta})\neq 0$)
$$-\infty<\ln(|f(0)|)\le\int_0^{2\pi}\ln(|f(re^{i\vartheta})|)d\vartheta/2\pi $$

I have a problem with the following passage:

As $r\to 1^-$ through such$^1$ values, the right hand side of this expression tends to
$$\frac{1}{2\pi}\int_0^{2\pi}\ln(|\tilde{f}(e^{i\vartheta})|)d\vartheta=-\infty$$

I am unsure about one thing: Why is the limit equal to $\frac{1}{2\pi}\int_0^{2\pi}\ln(|\tilde f|)$?

I tried using dominated convergence and Fatou's lemma, to no avail.

Thanks for the help, and Happy Holidays!

Note: for completeness, the proof then concludes by noting that we reached a contradiction and thus $f$ cannot be $\not\equiv 0$.

$^1$: meaning $r$ such that $f$ is not zero on $|z|=r$.

答:
Define $P_r(\vartheta)=\ln(|{f}(re^{i\vartheta})|)^+, N_r(\vartheta)=\ln(|{f}(re^{i\vartheta})|)^-$ so that:
$$\ln(|{f}(re^{i\vartheta})|)= P_r(\vartheta) - N_r(\vartheta)$$

Show first that as $r\to 1^{-}$ the integral$\frac{1}{2\pi}\int_0^{2\pi} P_r(\vartheta) d\vartheta$ is bounded using $f\in H^p$.

After this, all is left is to show that $\frac{1}{2\pi}\int_0^{2\pi} N_r(\vartheta) d\vartheta \to +\infty$. This can be proven by showing that $\frac{1}{2\pi}\int_0^{2\pi} N_{r_k}(\vartheta) d\vartheta \to +\infty$ for every sequence $(r_k)_k$ satisfying $r_k\to 1^-$ as $k\to +\infty$.

So, consider a sequence $(r_k)_k$ satisfying $r_k\to 1^-$ as $k\to +\infty$. By Egorov's theorem applied to the sequence $exp(-{N_{r_k}})$ you can show that $exp(-{N_{r_k}})$ converges uniformly to $0$ on a subset of $(0,2\pi)$ of positive measure. This can be used to prove $\frac{1}{2\pi}\int_0^{2\pi} N_{r_k}(\vartheta) d\vartheta \to +\infty$.

Merry Christmas and Happy New Year!


问:
Inverse of a matrix with outer product
I need to take inverse of this matrix:

\begin{equation}
i \mathbf{I}_8-\begin{pmatrix}
(a+ib-c)\sigma\otimes\sigma & a \sigma\otimes\sigma \\
a \sigma\otimes\sigma & (a-ib-c) \sigma\otimes\sigma
\end{pmatrix}
\end{equation}

Here $\mathbf{I}_8$ is $8*8$ identity matrix and, $\sigma$ is Pauli matrix such that $\sigma\otimes\sigma= \sum_{i=1}^3 \sigma^i\otimes \sigma^i=\left(
\begin{array}{cccc}
 1 & 0 & 0 & 0 \\
 0 & -1 & 2 & 0 \\
 0 & 2 & -1 & 0 \\
 0 & 0 & 0 & 1 \\
\end{array}
\right)$.

I would like to have the final result in terms of $\sigma\otimes\sigma$ and Identity matrix. I tried brute force inverse of the resulting $8*8$ matrix but that way I could not write the final result in terms of $\sigma\otimes\sigma$. I was wondering if there are any identities that can help me simplfy this calculation.

答:
You may use the properties of the Schur complement

\begin{equation}
\left(\begin{matrix} A & B \\ C & D \end{matrix}\right)^{-1} = \left(\begin{matrix} A^{-1} + A^{-1} B S^{-1} C A^{-1} & -A^{-1} B S^{-1} \\ -S^{-1} C A^{-1} & S^{-1} \end{matrix}\right)=
\left(\begin{matrix} I_n & -A^{-1} B \\ 0 & I_m \end{matrix}\right)
\left(\begin{matrix} A^{-1} & 0 \\ 0 & S^{-1} \end{matrix}\right)
\left(\begin{matrix} I_n & 0 \\ -C A^{-1} & I_m \end{matrix}\right),
\end{equation}

with the Schur matrix

\begin{equation}
S = D - C A^{-1} B
\end{equation}

and the inverse of an outer product

\begin{equation}
(E \otimes F)^{-1} = E^{-1} \otimes F^{-1}.
\end{equation}

Note that you still have to invert the submatrices $A, B, C, D$.

Regards

Title: Inverse of a matrix with outer product


问:
Why the result of matrix derivative is its transpose?
I'm having trouble understanding my lecture notes.

Given a matrix $A\in\mathbb R^{n\times n}$ and vectors $u,f\in\mathbb R^n,$ if we calculate the derivative (w.r.t. u) to of $Au-f$ the result will be $A^T.$

Why is it $A^T$ and not just $A$?

答:
For a map $g : \mathbb{R}^n \to \mathbb{R}^n$, it just depends on how you define the Jacobian matrix: is the $(i,j)$ entry $\frac{\partial g_i}{\partial u_j}$ or $\frac{\partial g_j}{\partial u_i}$?

Wikipedia seems to prefer the former, in which case if $g(u) = Au-f$, then $g_i(u) = \sum_{j=1}^n a_{ij} u_j - f_i$ so the $(i,j)$ entry of the Jacobian is $\frac{\partial g_i}{\partial u_j} = a_{ij}$, i.e. the Jacobian is $A$.

But Wikipedia also notes that some authors prefer the latter, where the $(i,j)$ entry of the Jacobian is $\frac{\partial g_j}{\partial u_i} = a_{ji}$, i.e. the Jacobian is $A^\top$.


问:
formula for relating number of successes to number of tries
Imagine we have a jar of marbles, where there are 10 different colors of marbles in the jar.
Let N be the number of marbles drawn in a sample and
K be the number of distinct colors in the sample.
Let C be the total number of colors in the jar (which is 10 in this example).

We know that:
K = F(C,N) + chance.

Intuitively, the more marbles we draw at a time, the more colors we are likely to obtain, up to the maximum.

This strikes me as a binomial. I am looking for a formula to express in more detail how
K = F(C,N).
An obvious feature is that C is the maximum value. So I figure this is a model where K is an increasing proportion of C as N increases.

I already know how to simulate the data, but wish to provide an expression of K depending on C and N.

Any suggestions will be appreciated.

Simulated data for the situation I intend will be as follows. I assume sampling with replacement. For this example, we have 10 colors in the jar (C=10). Note that we start by drawing one marble from the jar, which gives us a sample where N=1 and K=1. The number of colors found in a sample depends on the size of the sample. In this case it is seq(1:20). In this particular simulation, we have an equal representation for each color. The snip of R code I use to simulate the data is:

###snip of modified code for stack exchange exchange

T <- c(1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10)

for (i in 1:N){

for (s in 1:n.sims) {

plot.sample <- sample(T, size=N[i])

K[s,i] <- length(unique(plot.sample))

}

}

Note that the line is just a loess plot at this point and the proper function would level off at C, the maximum number of colors.

If I use the suggested formula
K=N*C/(N+C-1)
I get the figure on the right, which has the right shape, but finds colors very slowly.

If I estimate the function with a scaling coefficient, I get the following graph. Excellent fit: explained variance = 97%, though the visual suggests there could be a better function?

答: When you talk of asymptotic expressions, you seem to be assuming a large number of draws, where it is likely you have seen all the colors.  This simplifies the problem considerably.  It also helps if the draws are with replacement or if there are so many marbles that the number you draw does not change the mix appreciably.  If there are equal numbers of each type of marble, the chance that a particular type is not drawn is $\left(\frac{C-1}C\right)^N$.  When $N$ is large, the chance you have not seen a specific color is small, as you think.  The chance you have not seen two different colors is roughly the square of small, which is very small.  In that case, the chance you have missed some color is just $C\left(\frac{C-1}C\right)^N$.  Is this at all what you were looking for?


问:
Proving that $X$ is a subgroup of $G$

If we're given that some $X\subset G $ such that $e\in X$, and $\forall g \in G$, cosets $gX$ partition $G$, is $X$ a subgroup of $G$?

I'm not quite sure what it is I have to do. If $X$ wasn't a subgroup, then you can't say the cosets of $X$ are an equivalence class of $X$ since you would need inverses and closure (symmetry, transitivity, reflexivity).

Can someone please provide some hints?

答:
Yes, your conjecture is correct. Here is proof:

Suppose $g \in X$. Then, since $e \in X$, $e=g^{-1}g \in g^{-1}X$, so that by cosets of $X$ partitioning $G$, $g^{-1}X=X$, so that $e \in X \Rightarrow g^{-1}e \in g^{-1}X=X$. This proves that $X$ is closed under inversion map $G \rightarrow G$. For composition, if $g,h \in X$, then $h=he \in hX$, so similarly from above, $hX=X$. Then, $hg \in hX=X$, so that $hg \in X$. This with $e \in X$ proves that $X$ satisfies all axioms of a subgroup, so that $X \subset G$ is a subgroup.

Title: Proving that $X$ is a subgroup of $G$


问:
How can I express an infinitely nested unit set?
A unit set S can be expressed by $\{e\}$ where $e$ is a given element. Similarly, a nested unit set can be expressed by $\{\{e\}\}$.
Would the following notation be promptly understood as representing an infinitely nested unit set:
$\{\cdots\{\{e\}\}\cdots\}$?

答: Yes I think that is reasonably clear, although I think it's always a good practice to clarify notation which has the potential for being confused. So for example you could use that notation and add a line with something like "... denoting the infinite nested singleton set" or something like this. As Brian Moehring noted however, the axiom of regularity (https://en.wikipedia.org/wiki/Axiom_of_regularity) which is one of the ZF(C) axioms dictates that not set is an element of itself, which your infinitely nested singleton set is. That doesn't mean what you're doing is wrong, just that you can not construct such an object in ZF(C).


问:
What books do you recommend on graph theory?
I am recently coming across a lot of questions relating to graph theory, one of them is the following:

Given a simple graph G with n vertices. One edge e of G is called edgy, if the vertices of G can be split up into to subtotals A and B such that there are at most 100 edges with one end in A and one end in B and one of these is e. Prove that G has at most 100n edgy edges.

I looked for graph theory books on google and these books came up:

https://www.google.com/search?client=firefox-b-d&q=graph+theory+book

I am looking for books containing graph theory used in IMO's, so that I can learn the theory required for such questions. Could you please suggest some books?

答:
Graph theory with applications
Book by John Adrian Bondy And Murty

Is the best graph theory book you can come across in my opinion. It just offers everything you need to know about graphs.


问:
Find $\mathrm{Aut}(G)$, $\mathrm{Inn}(G)$ and $\mathrm{Aut}(G)/\mathrm{Inn}(G)$ for $G = D_4$
Problem

Find $\mathrm{Aut}(G)$, $\mathrm{Inn}(G)$ and $\mathrm{Aut}(G)/\mathrm{Inn}(G)$ for $G = D_4$

My Attempt

I let $D_4 = \{e, x, y, y^2, y^3, xy, xy^2, xy^3\}$

I found that $\mathrm{Inn}(G)$ consists of 4 bijective conjugation functions, namely $\{\phi_e, \phi_x, \phi_y, \phi_{xy}\}$.  For $\mathrm{Aut}(G)$, I found that there are 12 automorphisms.

Here is the following link that relates to the problem I am doing.

Based on the solution:

Lemma: If $\alpha$ is an automorphism of group $G$ and $G$ has generators $x$ and $y$ with orders $n$ and $m$, respectively then $\alpha(x)$ and $\alpha(y)$ are also generators for $G$ with orders $n$ and $m$.

Proof: First, let us show that the orders agree.  If $g \in G$ has order $n$, let $a = \alpha(g) \in G$ have order $m$.  Then, $a^m = 1$ but by applying $\alpha^{-1} \in \mathrm{Aut}(G)$, we get $g^m = 1$.  However, $g$ has order $n$, so $n$ must divide $m$.  Similarly, $g^n = 1$ and applying $\alpha$, we note that $a^n = 1$, and so we conclude $n = m$.

Secondly, since any element of $G$ can be written as a product of $x$'s and $y$'s, and $\alpha$ is a surjective homomorphism, it follows that any element of $G$ can also be written as a product of $\alpha(x)$ and $\alpha(y)$, hence they generate $G$.

Using this Lemma (or a similar argument), we note that an automorphism of $D_4$ must send $y$ to $y, xy, x^2y$ or $x^3y$ and $x$ to $x$ or $x^3$.  Any such pairing is possible, thus there are $2 \cdot 4 = 8$ such automorphisms...

(The notations that someone use are different from what I denote.)

The question I have is: Why are there 8 automorphisms?  Shouldn't there be 12 automorphisms?  Here is what I have:

$$e \mapsto e$$
$$x \mapsto \text{ either } \{x,y^2, xy^2\}$$
$$y \mapsto \text{ either } \{y, y^3, xy, xy^3\}$$

Then, there are $1 \cdot 3 \cdot 4 = 12$ automorphisms.

Any advices or comments?

答:
We know that $$D_4=\langle x,y|x^2=y^4=1, (yx)^2=1\rangle = \{e, x, y, y^2, y^3, yx, y^2x, y^3x\}$$

Since $x^2 = 1 = (yx)^2 = (yxy)x$, we see that $x = yxy = y^2xy^2 = y^3xy^3 = y^nxy^n$.  From this we can see that $|x| = |yx| = |y^2x|=|y^3x|=2$.  Indeed:

$$(y^nx)^2=(y^nxy^n)x=x^2=1\;.$$

In fact, $2$ is the smallest positive integer $m$ such that $(y^nx)^m = 1$.  On the other hand $|y^3|=4$. So if any automorphism is defined then, according to the Lemma you cited, it must preserve orders; so our possibilities are as follows:

One of

$$\begin{eqnarray}
x&\to&x\\
x&\to&yx\\
x&\to&y^2x\\
x&\to&y^3x
\end{eqnarray}
$$

and one of

$$\begin{eqnarray}
y&\to&y\\
y&\to&y^3
\end{eqnarray}
$$

(Of course, in all cases $1\to 1$.)


问:
Number of schedules that do not repeat a matchup

Background

There are n teams such that n is even. A matchup is a pair of two distinct teams where order does not matter so that (A,B) and (B,A) are equivalent. A schedule is comprised of all n teams in $\frac n2$ matchups. For example, the following is a possible schedule of 8 teams labeled A ... H:

{(A,B) (C,D) (E,F) (G,H)}

Question

From the set of all possible schedules, one is chosen at random. How many schedules in the set of all possible schedules share no matchups with this random schedule?

Progress I've Made

The size of the set of schedules is (n-1)(n-3)(n-5)...(3)(1). For n = 6 there are 15 possible schedules. I've listed these by hand. By inspection, 8 of the 15 possible schedules would share no matchup with a random schedule. However, I have not been able to hit upon an equation that would describe this for all n.

Areas of Inspection

I've attempted to use derangements and other variation of the principle of inclusion-exclusion, but either this is the wrong approach or I'm not using the principles correctly. I read about orthogonal latin squares but am unsure if they apply to the problem.

答:
OEIS A053871 gives the following recursion:

$$a(0) = 1; a(1) = 0; a(n) = 2 (n - 1)*(a(n - 1) + a(n - 2))$$

From the comments there:

The formula is given directly by the Principle of Inclusion and Exclusion.

The first term includes all pairings, the second term excludes all pairings containing each pair, the third term includes all pairings containing each pair of pairs, and so on.


答:
Let $T$ denote the number of trials until the $k$-th failure. The distribution of $T$ is given by
$$
\mathsf{P}(T=i)=\binom{i-1}{k-1}(1-p)^kp^{i-k},\quad i\ge k.
$$
Then (assuming that $n\ge k$) the expectation of $T\wedge n$ is
$$
\mathsf{E}[T\wedge n]=\sum_{i=k}^\infty (i\wedge n)\cdot \mathsf{P}(T=i)=\sum_{i=k}^n i\cdot \mathsf{P}(T=i)+n\cdot \mathsf{P}(T>n),
$$
and
$$
\mathsf{P}(T>n)=\sum_{i=0}^{k-1}\binom{n}{i}(1-p)^ip^{n-i},
$$
i.e., it is the probability that the number of failures in the first $n$ trials is less than $k$. Alternatively,
$$
\mathsf{P}(T>n)=1-\sum_{i=k}^{n}\binom{i-1}{k-1}(1-p)^kp^{i-k},
$$

Title: Expected number of trials until $k$ failures or number of trials reach $n$

Body:
I am trying to find the expected number of trails until the $k$-th failure
or until the number of trials hit $n$, whichever comes first. The success   probability of the trial is $p$.

My calculation gave me the below result.
$$
\sum_{i=0}^{k-1} i{{n}\choose{i}} p^{n-i}(1-p)^{i} + \sum_{i=k}^n i { k-1+i \choose i} p^{i}(1-p)^k
$$

But it seems the result is
$$
\sum_{i=0}^{k-1} i{{n}\choose{i}} p^{n-i}(1-p)^{i} + \sum_{i=k}^n i { i-1 \choose k-1} p^{i-k}(1-p)^k
$$

I don't know what is wrong with my result and how I can get the correct result.


问:
For any non-singular $A$, $\frac{1}{\kappa(A)}\leq\frac{\|E\|}{\|A\|}$ if $E+A$ is singular

Let $A$ be a non singular, and $A+E$ be singular matrix.
Prove that $\frac{1}{\kappa(A)}\leq\frac{\|E\|}{\|A\|}$.

I thought of assuming $\|A+E\|=0$, but it doesn't seem to be right.

答:
It suffices to show that $\|E\|$ is greater than or equal to the smallest singular value of $A$, since $\|A\|=\sigma_{\max}(A)$ and $\kappa(A) = \sigma_{\max}(A) / \sigma_{\min}(A)$.

This follows immediately from a Weyl inequality (see this question and references therein, and/or Corollary 8.6.2 in "Matrix Computations" by Golub and van Loan) that states
$$|\sigma_{\min}(A+E) - \sigma_{\min}(A)| \le \|E\|.$$


问:
Construction in Topology about an counterexample

Let a compact subset $K$ of open set $U$ in $(X, \tau)$ a space topology, so it necessary that there exists compact $S$ so that $K \subset \mathbf{int}(S) \subset S \subset U$?

I know that if I want disprove that, so I need to find a $X$, $U$ and $K$ such that $S$ there's not exists. But, how can I construct $S$?

答:
No, such compact $S$ need not exist. Take any space that is not a locally compact and take any point $p$ that has no neighborhood whose closure is compact. Take $K=\{p\}$.

Or, to be specific, let $X=\mathbb Q$ (the rational numbers) with the  usual topology, and let $K$ be any nonempty compact subset (e.g., a singleton, a finite set, a converging sequence, or something more complicated). There is no non-empty open set $V$ such that the closure of $V$ is compact. In particular, given any open $U$ containing $K$ there is no compact $S$ such that $K \subset \mathbf{int}(S) \subset S \subset U.$


问:
Efficiently finding congruencies
All variables are integers with a value somewhere between 0-99, inclusive.

ax + b % 100 = n and you are given everything except x.

Example: 65x + 6 is congruent with 81 mod 100.

I am trying to find a way to determine the potentially valid values of x without resorting to brute force.  Is there a known method more efficient than brute force for a problem like this?  If so, can anyone explain how the congruencies are found and/or possibly point me in the direction of any tutorials, books, or videos?

Title: Efficiently finding congruencies

Body:
$65x+6\equiv81\bmod100\iff65x\equiv75\bmod100\iff$

$13x\equiv15\bmod20\iff7x\equiv5\bmod20\iff x\equiv3\times7x\equiv3\times5=15\bmod20$


答:
The answer to your question has a very easy part and a hard part.  First, the very easy part.  You pose
$$  a x + b \cong n \pmod{100}  $$
with the example
$$  65 x + 6 \cong 81 \pmod{100}  \text{.}  $$
The basic strategy is the same one you would use if not reduction modulo $100$ were intended: use algebra to solve for $x$.  The first step is very easy, subtract the constant from both sides.
\begin{align*}
a x &\cong n - b\pmod{100}  \\
65 x &\cong 81 - 6  \\
    &\cong 75 \pmod{100}  \text{.}
\end{align*}
(I suspect that you will like to remember, if the result of this subtraction is negative, to add the modulus to the difference to get a result in the interval $[0,100)$ again.)

Now our strategy calls for division by $65$, but there is a "simpler" problem hiding in your example : $65$, $75$, and $100$ have a common factor, $5$, and we can reduce by this common factor.
$$  13 x \cong 15 \pmod{20}  \text{.}  $$
More generally, if $a$ and the modulus, $100$ have a common factor then either $n-b$ also shares that factor and there is a solution or $n-b$ does not share that factor and there is no solution.  So we check that any common factor of $a$ and $100$, $d$, is also a factor of $n-b$.  Having factored $d$ out, we have
$$  (a/d)x \cong (n-b)/d \pmod{100/d}  \text{.}  $$
The easiest way to compute $d$ is using the Euclidean algorithm to compute the greatest common divisor (gcd) of $a$ and $100$.  Having found and divided out the greatest common divisor, we know that $a/d$ and $100/d$ are relatively prime.  This ensures that there is a number, $c$, such that
$$  c \cdot (a/d) \cong 1 \pmod{100/d}  \text{,} $$
That is, $c$ acts like the reciprocal of the coefficient of $x$, so multplying by $c$ is like dividing by that coefficient.

How do we find this $c$?  Use the extended Euclidean algorithm.  The input is two integers, $a/d$ and $100/d$, whose gcd you want to know.  The output is that gcd and also a pair of numbers, $e$ and $f$, with the following immediately useful property:
$$  e \cdot (a/d) + f \cdot (100/d) = \gcd(a/d,100/d) = 1  \text{.}  $$
That is $e$ and $f$ are coefficients for each input that act like their reciprocals when using the other input as modulus.  For us, we want $e$ and we multiply both sides of the equation by $e$:
\begin{align*}
\underbrace{e \cdot (a/d)}_{\cong 1 \pmod{100/d}} x &\cong e \cdot (n-b)/d \pmod{100/d}  \\
x &\cong e \cdot (n-b)/d \pmod{100/d}  \text{.}
\end{align*}
What does the computation of $e$look like in the example?  We want to study the gcd of $13$ and $20$.
\begin{align*}
20 &= 1 \cdot 13 + 7  &  7 &= 1 \cdot 20 - 1 \cdot 13  \\
13 &= 1 \cdot 7 + 6  &  6 &= -1 \cdot 20 + 2 \cdot 13  \\
7 &= 1 \cdot 6 + 1  &  1 &= (7-6) = 2 \cdot 20 -3 \cdot 13  \text{.}
\end{align*}
(In the last line, we have reminded that the multiples of $20$ and $13$ we need are present on prior lines.)

This says that $2$ is the reciprocal of $20$ modulo $13$ and also that $-3$ is the reciprocal of $13$ modulo $20$.  We want the latter and we add the modulus, $20$, to it to get a small positive number.

$$  17 \cdot 13 \cong 1 \pmod{20}  $$
So,
\begin{align*}
17 \cdot 13 x &\cong 17 \cdot 15 \pmod{20}  \\
x &\cong 17 \cdot 15 \pmod{20}  \\
x &\cong 15 \pmod{20}  \text{.}
\end{align*}

If it had been the case that $d = 1$, so we were not working with a reduced modulus, we would be done.  However, when $d > 1$ there are multiple solutions.  We know that $15$ is one solution and we know that $15$ plus multiples of $20$ are solutions.  Since the original congruence is modulo $100$, we want to know all the "$15$ plus multiples of $20$" in $[0,100)$.  (By division, there are $100/20 = 5$, and in general, there are $d$ of them, but let's write them down.)
They are $15$, $35$, $55$, $75$, and $95$.  (If we add $20$ again, we "wrap around" back to $15$.)

Let's test these:
\begin{align*}
65(15) + 6 &\cong 975 + 6 \\
    &\cong 981  \\
    &\cong 81 \pmod{100}  \text{,}  \\
65(35) + 6 &\cong 2275 + 6 \\
    &\cong 2281  \\
    &\cong 81 \pmod{100}  \text{,}  \\
65(55) + 6 &\cong 3575 + 6 \\
    &\cong 3581  \\
    &\cong 81 \pmod{100}  \text{,}  \\
65(75) + 6 &\cong 4875 + 6 \\
    &\cong 4881  \\
    &\cong 81 \pmod{100}  \text{, and}  \\
65(95) + 6 &\cong 6175 + 6 \\
    &\cong 6181  \\
    &\cong 81 \pmod{100}  \text{.}
\end{align*}
This shows that all the numbers we found are solutions.  The argument laid out above shows that these are all of them.

Title: Efficiently finding congruencies

Body:
All variables are integers with a value somewhere between 0-99, inclusive.

ax + b % 100 = n and you are given everything except x.

Example: 65x + 6 is congruent with 81 mod 100.

I am trying to find a way to determine the potentially valid values of x without resorting to brute force.  Is there a known method more efficient than brute force for a problem like this?  If so, can anyone explain how the congruencies are found and/or possibly point me in the direction of any tutorials, books, or videos?


问:
Primes in solutions to Pell-type equations
What is known about primes in solutions to Pell-type equations?

In particular, consider the negative Pell equation $x^2 - 5 y^2 = -1$.
As far as I've been able to check
(in the first $4000$ solutions) the only positive-integer solution with $y$ prime  is $x=38$, $y=17$,
but I don't see any obvious reason why this should be the case.

答:
Let $\alpha = (2 + \sqrt{5})$ and $\beta = (2 - \sqrt{5})$. Note that $\alpha \beta = -1$. The general solution is given by

$$y_n = \frac{\alpha^n - \beta^n}{\alpha - \beta} = \frac{\alpha^n -\beta^n}{2 \sqrt{5}}$$

for $n$ odd. (This follows from general theory and I could explain it but I suspect that you know --- you can use induction, for example). This is related to the fact that $\alpha$ is a unit in the ring $\mathbf{Z}[\sqrt{5}]$. However, what is secretly going on is that there is the larger ring $\mathbf{Z}[\phi]$ where

$$\phi = \frac{1 + \sqrt{5}}{2},$$

and in fact $\phi$ is the fundamental unit, and we have $\alpha = \phi^3$ and $\beta = -\phi^{-3}$. So

$$2 y_n =  \frac{\phi^{3n} - (-\phi)^{-3n}}{\sqrt{5}}$$

is actually divisible by

$$ \frac{\phi^{n} - (-\phi)^{-n}}{\sqrt{5}} = F_n,$$

where $F_n$ is the $n$th Fibonacci number. (This divisibility takes place in $\mathbf{Z}[\phi]$, but the ratio $2y_n/F_n$ is a rational number which is an algebraic integer and thus an actual integer.) Hence $y_n$ is divisible by $F_n$ if $F_n$ is odd and by $F_n/2$ if $F_n$ is even (and the ratio is also $> 1$ for $n > 1$). This shows that $y_n$ is not prime as soon as $F_n >
 2$, so for $n > 3$. Hence $y_3 = 17$ is the only prime value.

For more general Pell-type equations I think one is generally out of luck unless there are forced divisibilities as in this case, and looks similar to the primality or otherwise of the sequence $2^n - 1$.

Added: I guess for those who want a more elementary solution, one can observe (and prove by induction) that the $y$ are given by

$$\frac{1}{2} F_{6n+3} = \frac{F_{2n+1} \cdot (5 F^2_{2n+1}  - 3)}{2}$$

and the RHS is easily seen to be prime only for $n = 1$ whence $F_9/2 = 34/2 = 17$.


问:
show that $\gcd(m^{n-1}-1,n)>1$
Let $p$ be a prime number and $m,n$ be integers greater than $1$ such that
$$n\mid m^{p(n-1)}-1$$
Prove that
$$\gcd(m^{n-1}-1,n)>1$$

My try: Assume  that  prime number $q$ such $q\mid\gcd(m^{n-1}-1,n)$, then
$q\mid m^{n-1}-1$ and $q\mid n$, and if let $d=ord_{m}(q)$, then we have
$$d\mid q-1,\ d\mid n-1$$ Then I can't it. Thanks

答:
Take any prime divisor of $n$ like $q$. Then by the hypothesis of the problem $q|m^{p(n-1)}-1$ which means that $Ord_{q}(m)|p(n-1)$. On the other hand, if for such $q$, $Ord_{q}(m)|n-1$, then $m^{n-1}-1$ will be divisible by $q$ and because it also divides $n$ the claim is proven. But if $Ord_{q}(m)\not| n-1$ then clearly $p|Ord_{q}(m)|q-1$ which shows that $p$ divides $q-1$ for all of the prime divisors of $n$ like $q$, and thus by multiplying all of these prime divisors, $n\equiv1 (mod p)$
Now put $n=pk+1$ and go through the same procedure, then this time you will find out that if the claim doesn't hold, all of the prime divisors of $n$ shall be congruent to 1 mod $p^2$ and so shall $n$ itself. Then put $n=p^2k+1$ and go through the same method again. So $n-1$ shall have infinite $p$'s in its prime factorization which is a contradiction if $n$ is not equal to 1.

Title: show that $\gcd(m^{n-1}-1,n)>1$


问:
Weak continuity of diagonal embeddings of Hilbert spaces
Let $\mathcal{H}$ be an infinite-dimensional separable Hilbert space and let $I: \mathcal{H} \rightarrow \mathcal{H}\otimes \mathcal{H} $ be the (non-linear) map given by the diagonal embedding $h \mapsto h\otimes h, \, h \in \mathcal{H}$.

Is $I$ weakly continuous, i.e. continuous with respect to the weak topologies on $\mathcal{H}$ and $\mathcal{H}\otimes \mathcal{H} $?
If not, is $I$ at least weakly Borel measurable, i.e. measurable with respect to the Borel $\sigma$-algebras of the weak topologies on $\mathcal{H}$ and $\mathcal{H}\otimes \mathcal{H} $?

(Above $\otimes$ stands for the standard tensor product of Hilbert spaces.)

答:
$I$ is not continuous relative to  the weak topologies.  The reason is that the map
$$
  \varphi _v:h\in H\mapsto \langle h\otimes h, v\rangle \in \mathbb R
  \tag 1
  $$
is discontinuous for some  choices of $v$ in $H\otimes H$.  One   such choice is to take an orthonormal basis $\{e_i\}_{i\in \mathbb
N}$  of $H$ and set
$$
  v=\sum_{i=1}^\infty n^{-1}e_i\otimes e_i.
  $$
Observe that in this case
$$
  \varphi _v(h) = \sum_{i=1}^\infty n^{-1}\langle h\otimes h, e_i\otimes e_i\rangle  =
  \sum_{i=1}^\infty n^{-1}\langle h, e_i\rangle ^2.
  \tag2
  $$
Assuming by contadiction that $\varphi _v$  is  cotinuous at zero for the weak topology, there would be
a weak  neighborhood $V$ of zero, such that for every $h$  in $V$, one would have that
$$
  |\varphi _v(h)|<1.
  $$
Observe however that every neighborhood of  zero  in the weak  topology contains some finite codimensional subspace,
say $K$.  If  $h$ is any nonzero vector in $K$, then $\lambda h$ lies in $V$ for every $\lambda $ in $\mathbb R$, so
$$
  \sum_{i=1}^\infty n^{-1}\lambda ^2\langle h, e_i\rangle ^2 < 1,
  $$
whence necessarily
$$
  \sum_{i=1}^\infty n^{-1}\langle h, e_i\rangle ^2 =0,
  $$
from where it follows that $h=0$, conradicting the choice of $h$.

On the other hand, $I$ is clearly norm continuous, hence a measurable map relative to the $\sigma$-algebra of Borel sets
associated to the norm topology.  However, this $\sigma$-algebra is the same as that of weak Borel sets.


问:
Stirling's Approximation and Binomial Random Variable
I am trying to follow equation (1.13) in MacKay's Information Theory textbook (http://www.inference.phy.cam.ac.uk/itprnn/book.pdf). It is:

$$ \ln \binom{N}{r} = \ln \frac{N!}{(N-r)! r!} \approx (N-r) \ln \frac{N}{N-r} + r \ln \frac{N}{r} $$

I am using the approximation in equation (1.12):

$$ \ln x! \approx x \ln x - x + \frac12 \ln 2 \pi x$$

Thus, if I expand the expression in the middle of equation (1.13), I should get 9 terms:

$$ \ln \frac{N!}{(N-r)! r!} = \ln N! - \ln (N-r)! - \ln r! $$
$$ \approx N \ln N - N + \frac12 \ln 2 \pi N - (N-r) \ln (N-r) + (N-r) - \frac12 \ln 2\pi (N-r) - r \ln r + r - \frac12 \ln 2 \pi r$$

Now, I am stuck. If I remove the $\ln$ terms (seems to be valid for large factorials, http://mathworld.wolfram.com/BinomialDistribution.html equation (37)), I am still stuck. The exact problem seems to be manipulating $N \ln N, - (N-r) \ln (N-r), - r \ln r$ into the form MacKay has in equation (1.13).

Thanks.

答:
Your target approximation can be expanded:
$$(N-r) \ln \frac{N}{N-r} + r \ln \frac{N}{r}$$
$$= (N-r) \ln N  - (N-r) \ln ({N-r}) + r \ln N - r \ln r$$
$$= N\ln N -r\ln N + r \ln N  - (N-r) \ln ({N-r}) - r \ln r$$
$$= N \ln N  - (N-r) \ln (N-r)   - r \ln r$$

while your long approximation can be rewritten as
$$N \ln N  - (N-r) \ln (N-r)   - r \ln r  + \frac12 \ln \left(\frac{N}{2 \pi (N-r)r} \right)$$

and the last term of this is much smaller than the others if $N$ is not small and $r$ is not close to $0$ or $N$, so the two are close to each other.


问:
Why is a CDF right-continuous at "a" in [a,b), when property Pr(a<X≤b) doesn't even require point "a" to exist, and "b" could carry baggage?
c.f. wikipedia:Cumulative distribution function properties

"Every cumulative distribution function F is (not necessarily strictly) monotone non-decreasing (see monotone increasing) and right-continuous. "

...

"If the CDF F of X is continuous, then X is a continuous random variable; if furthermore F is absolutely continuous, then there exists a Lebesgue-integrable function f(x) such that

$$F(b)-F(a) = \operatorname{P}(a< X\leq b) = \int_a^b f(x)\,dx$$

for all real numbers a and b. The function f is equal to the derivative of F "almost everywhere", and it is called the probability density function of the distribution of X."

答:
I'm not sure I fully understand the question.

You have the CDF $F(\alpha) = P \{ \omega | X(\omega) \in (-\infty,\alpha] \}$, and since $(-\infty, a] \cup (a,b] = (-\infty, b]$, we have $ P \{ \omega | X(\omega) \in (-\infty,a] \} + P \{ \omega | X(\omega) \in (a,b] \} = P \{ \omega | X(\omega) \in (-\infty,b] \}$, from which we get $P \{ \omega | X(\omega) \in (a,b] \} = F(b)-F(a)$.

There is no choice in the matter once you let $F(\alpha) = P (X^{-1}(-\infty,\alpha])$.

As in the comment above, if $\alpha_n \downarrow \alpha$, then $(-\infty, \alpha] = \cap_n (-\infty, \alpha_n]$. It follows that $X^{-1}(-\infty, \alpha] = \cap_n X^{-1}(-\infty, \alpha_n]$, and since $P$ is a probability measure (hence bounded above), we have $P(X^{-1}(-\infty, \alpha]) = \lim_n P (X^{-1}(-\infty, \alpha_n])$. Or, in other words, $F(\alpha) = \lim_n F(\alpha_n)$.

If $\beta_n \uparrow \beta$, we have $F(\beta_n)$ is non-decreasing and bounded above by $F(\beta)$, hence $\lim_{n} F(\beta_n)$ exists (and is $\le F(\beta)$, of course).

Suppose $a<b$. Choose any $c \in [a,b)$, then $[a,b) = [a,c]\cup (c,b)$, from which we get
$[a,b) = (\cap_n (a-\frac{1}{n},c]) \cup (\cup_n (c,b-\frac{1}{n}]) $. We have $P(X^{-1} (a-\frac{1}{n},c]) = F(c)-F(a-\frac{1}{n})$, hence $P(X^{-1} (a,c]) = F(c)-\lim_n F(a-\frac{1}{n})$, and similarly, $P(X^{-1} (c,b-\frac{1}{n}]) = \lim_n F(b-\frac{1}{n}) -F(c)$, from which it follows that $P(X^{-1}[a,b)) = \lim_n F(b-\frac{1}{n}) - \lim_n F(a-\frac{1}{n})= \lim_{b_n \downarrow b} F(b_n) - \lim_{a_n \downarrow a} F(a_n)$. If $a=b$ then $[a,b) = \emptyset$, and it is easy to see that the formula agrees in this case as well.

Again, there is no choice in the matter.

Note that the formula in the question is incorrect, as the CDF $F = 1_{[0,\infty)}$ shows, with $a=0, b=1$. Then $P(X^{-1}[0,1) ) = 1$, whereas the formula in the question above would result in zero.


问:
Need help understanding formula for probability that something good happens before something bad happens.
My book says this.

Consider a sequence of independent trials, each of which can
be classified as good, bad, or neutral, which happen (on any given trial) with
probabilities $p, q,$ and $1 − p − q$, respectively. (We do not necessarily have
$q = 1 − p$ here, although that case is allowed.) Then the probability that
something good happens before something bad happens is $p/(p + q)$.

My question is, how did they derive this formula $p/(p+q)$ for probability that something good happens before something bad happens?

can someone show me a derivation/explain to me this?

答:
Informally, you can ignore the neutral events, because if one happens you are back where you started.  You can then scale up the probabilities $p$ and $q$ so they sum to $1$, which gets the probability of something good being $\frac p{p+q}$ and the probability of something bad being $\frac q{p+q}$.  Note these sum to $1$ and have the proper ratio, which should convince you.

More formally, the chance of good before bad is a string of neutrals followed by a good and the chance of bad before good is a string of neutrals followed by a bad.  Again, the ratio has to be $\frac pq$ and the sum has to be $1$ because the chance of an infinite string of neutrals is $0$.  If you want, you can sum the geometric series and get the same result for more work.


答: In the repeated trials, the only try that matters is the first one that isn't neutral. For that one, it's good before bad if and only if that one is good. The probability is then as advertised: the probability of good divided by the probability that the try matters.</p>

Title: Need help understanding formula for probability that something good happens before something bad happens.

Body:
My book says this.

Consider a sequence of independent trials, each of which can
be classified as good, bad, or neutral, which happen (on any given trial) with
probabilities $p, q,$ and $1 − p − q$, respectively. (We do not necessarily have
$q = 1 − p$ here, although that case is allowed.) Then the probability that
something good happens before something bad happens is $p/(p + q)$.

My question is, how did they derive this formula $p/(p+q)$ for probability that something good happens before something bad happens?

can someone show me a derivation/explain to me this?


问:
Gluing of Möbius strips
Let $X$ be a Möbius strip. Take $n$ copies of $X$ and glue them by their boundaries (where the morphisms $S^1 \to S^1$ are homeomorphisms) and denote the new space by $Y$. What is a homotopy type of $Y$? At least, how to compute $\pi_1 (Y)$?
I think we need to endow $Y$ with a CW-structure but I don't really see how to do this. It seems to me $\pi_1$ doesn't change but I think this is wrong. Also, I would appreciate any references to places where I can find similar problems with solutions.

答:
I am not sure why the comment is upvoted: your meaning is clear, take $M_1 = \cdots = M_n = M$ all copies of the Mobius band; there are inclusion maps $f_i: S^1 \to M_i$ for all $i$ parameterizing the boundary; take the space $X_n = (M_1 \sqcup \cdots \sqcup M_n)/\sim$ where $f_i(x) \sim f_j(x)$ for all $i,j$. Write $f: S^1 \to X_n$ for the map $f_i$ (which is independent of $i$).

Now it is clear that "$\pi_1$ does not change" is preposterous, because for $X_2 = K$ the Klein bottle. However we can try to take an inductive approach. We have $X_{n+1} = X_n \sqcup_{S^1} M_{n+1}$. We will keep track of both the fundamental group and the particular element $[f]$. In what follows I will freely replace $f$ with $f^{-1}$ as appropriate for the cleanest possible examples; it doesn't really matter.

For $n = 1$ we see that the fundamental group is $\Bbb Z$ with $[f] = 2$. For $n = 2$ we see that the fundamental group is $\langle x, y \mid x^2 = y^2\rangle$ with $[f] = y^2$. For $n = 3$ we see that the fundamental group is $\langle x, y, z \mid x^2 = y^2 = z^2\rangle$.

Because the inclusion map $f_{n+1}$ induces multiplication-by-two on $\pi_1$, we may inductively see that $$\pi_1(X_n) = \langle x_1, \cdots, x_n \mid x_1^2 = x_2^2 = \cdots = x_n^2\rangle,$$ with $[f] = x_n^2$. Notice that when $n = 1$ the relation says nothing.

To see that these are all different you can abelianize. We have $H_1(X_n) = \pi_1(X_n)^{ab} = \Bbb Z^n/\langle 2x_1 - 2x_2, \cdots, 2x_{n-1} - 2x_n\rangle$. A change of coordinates takes this to $\Bbb Z^n/\langle 2y_2, \cdots, 2y_n\rangle$. One finds that $H_1(X_n) = \Bbb Z \oplus (\Bbb Z/2)^{n-1}$ for all $n \geq 1$, which are all pairwise non-isomorphic.

Title: Gluing of Möbius strips


答:
$ax + b \equiv c\pmod{f} \iff ax \equiv (c-b) \pmod{f}.$

Therefore, the general problem reduces to attacking

$$a(x) \equiv e \pmod{f}, ~\text{where}~ a,e,f
~\text{are known integers}.$$

Suppose that $d =$ gcd$(a,f).$  If $d$ does not divide $e$, then the problem has no solution.  If $d$ does divide $e$, then the problem is equivalent to

$$\frac{a}{d}(x) \equiv \frac{e}{d} \pmod{\frac{f}{d}}.$$

Therefore, WLOG, $a,f$ are relatively prime and the general problem to solve is

$$a(x) \equiv e \pmod{f}.$$

One approach to attack this general problem is compute $s$ such that $a(s) \equiv 1\pmod{f}.$  Since $a,f$ are relatively prime, $s$ must exist.

Once $s$ is computed, then you have

$$x \equiv [a(s)](x) \equiv e(s) \pmod{f}.$$

Therefore, the solution will be $x \equiv e(s) \pmod{f}.$

One standard way to compute $s$ is via the Euclidean algorithm.

The easiest way to demonstrate this is by example.

Let $a = 53, f = 75$.

Then $75 = 53(1) + 22.$

$53 = 22(2) + 9.$

$22 = 9(2) + 4.$

$9 = 4(2) + 1.$

Therefore:

$1 = 9 - 4(2)$

$= 9 - (2)[22 - 9(2)] = 9(5) - 22(2)$

$= 22(-2) + (5)[53 - 22(2)] = 53(5) - 22(12)$

$= 53(5) - (12)[75 - 53] = 53(17) - 75(12).$

Therefore, $(53 \times 17) \equiv 1\pmod{75}.$

Title: Efficiently finding congruencies


问:
How to find area of triangle from its medians
The length of three medians of a triangle are $9$,$12$ and $15$cm.The area (in sq. cm) of the triangle is

a) $48$

b) $144$

c) $24$

d) $72$

I don't want whole solution just give me the hint how can I solve it.Thanks.

答:
You know that medians divide a triangle to 6 equal areas. If you find one of them, multiplying with 6 give you the area of whole triangle. Let's denote one area as $S$, now see the figure:

I guess you saw the right triangle.


问:
What is the probability of a randomly chosen integer being even?
There are a number of sets in math that have infinite cardinality but still have a superset. For example, the set of even integers has infinite cardinality, but it is a subset of all integers. The cardinality of the set of integers is infinity, but it has a superset, real numbers. These are just a few examples.

So my question is if a random number was chosen from one of these supersets, what is the probability that it would be a part of one of its infinite subsets? There is an infinity of possibilities that are inside the subset, but also an infinity that is not.

答:
The probability of an integer $x$ (where $|x| < n$ for a fixed $n$) being even, when uniformly randomly chosen, in the limit as $n \to \infty$, is equal to $1/2$.

The reason for the phrasing of this is that you need to be very careful about how you define this.

"Uniformly randomly" essentially ensures each integer is equally likely. Hopefully this choice is obvious.

The reason we first consider $x \in \Bbb Z$ such that $|x|<n$ is because it doesn't make much sense to deal with infinite sets at the outset. For instance, there are infinite many integers, infinitely many even numbers, and infinitely many odd numbers. (All "the same infinity" if you appeal to cardinality, namely $\aleph_0$.) How should you define the proportion which are either? Naively, you could claim
$$\frac{\text{cardinality of even integers}}{\text{cardinality of all integers}} = \frac{\aleph_0}{\aleph_0} = 1$$
but then (aside from being somewhat ill-defined) that claims all integers are even (or odd), which doesn't match up with intuition. So we first want to work with things we know: finite sets.

So, define
$$S_n := \left\{x \in \Bbb Z \; \middle| \; |x|<n\right\} \qquad
E_n := \left\{ x \in S_n \; \middle| \; x \text{ is even } \right\}$$ Obviously,
$$|S_n| = 2n-1 \qquad |E_n| = 2\left\lceil \frac n 2 \right\rceil -1$$
Then
$$\text{probability of $x \in S_n$ being even} = \frac{|E_n|}{|S_n|} = \frac{2 \lceil n/2 \rceil - 1}{2n-1}$$
(obviously uniformly randomly chosen).
To generalize these conclusions to all $x \in \Bbb Z$, we take the limit $n \to \infty$, since $S_n$ becomes $\Bbb Z$ in the limit $n \to \infty$, and $E_n$ likewise represents all of the even integers in the limit. The limit of the ratio can be verified to be $1/2$:
$$\lim_{n \to \infty} \frac{|E_n|}{|S_n|} = \lim_{n \to \infty} \frac{2 \lceil n/2 \rceil - 1}{2n-1} = \frac 1 2$$
This is also easily seen graphically:

If you want to look further into stuff like this, you should look into topics such as measure theory, where these notions are discussed in more generality. Questions like these can be rigorized and handled best in that context, particularly once discussions are taken to probability theory.

You can also generalize this sort of process to your other questions. I just focused on the probability an integer being even since it's simple and intuitive. It's basically the same idea every time.


问:
How can $\sqrt{100+\sqrt{6156}}+\sqrt{100-\sqrt{6156}}$ be equal to $18$?
According to this answer, when $\sqrt{m}$+$\sqrt{n}$ is rational, then $\sqrt{m}$ and $\sqrt{n}$ are rational.

But $\sqrt{100+\sqrt{6156}}+\sqrt{100-\sqrt{6156}} = 18 \in \mathbb{Q}$.

So that would imply $\sqrt{100+\sqrt{6156}}$ and $\sqrt{100-\sqrt{6156}}$ both rational. However, the former is $9 + \sqrt{19}$ and the latter is $9 - \sqrt{19}$, both irrational.

Where is the mistake here?

Thanks.

答: The problem is that the proof of what you linked is actually equivalent to $m-n$ being rational which isn't correct here


问:
How to find the least in $E^{\circ}=\frac{5S^g}{162}+\frac{C^\circ}{50}+\frac{2\pi^2}{360}\textrm{rad}$?
The problem is as follows:

Let $S^{\circ}$, $C^{g}$ and $R\,\textrm{rad}$ the measures of a positive angle in sexagesimal, centesimal and radian degrees respectively such as:

$$E^{\circ}=\frac{5S^g}{162}+\frac{C^\circ}{50}+\frac{2\pi^2}{360R}\textrm{rad}$$

Using this information find the least $E$.

The alternatives in my book are as follows:

$\begin{array}{ll}
1.&\textrm{6}\\
2.&\textrm{8}\\
3.&\textrm{10}\\
4.&\textrm{12}\\
\end{array}$

How exactly should I find the least angle here?.

So far what I remember is that the proportions between each unit are the same in the sense of:

$\frac{S}{360}=\frac{C}{400}=\frac{R}{2\pi}$

Using this information you may find a relationship between the variables.

Plugin these in the above equation I'm getting:

However I find confusing why the degree symbols for $S$ and $C$ appears swapped then I figured that what it might be intended could be that the digits for the angle are represented by the letter but the degree is contrary to what its unit mentions.

For $\frac{5S^g}{162}$:

$\frac{5S^g}{162}\times\frac{360^\circ}{400^g}=\frac{1S}{36}^{\circ}$

For $\frac{C^\circ}{50}$:

Since;

$\frac{S}{360}=\frac{C}{400}$

$C=\frac{10}{9}S$

$\frac{C^\circ}{50}=\frac{10S^\circ}{9}\times \frac{1}{50}=\frac{1S^\circ}{45}$

For: $\frac{2\pi^2}{360R}\textrm{rad}$

Since this case $R$ matches with the degree symbol $\textrm{rad}$ then I would apply the equation:

$\frac{S^{\circ}}{180}=\frac{R\rad}{\pi}$

$R \textrm{rad}=\frac{S^\circ \pi}{180}$

$\frac{2\pi^2}{360R}\textrm{rad}=\frac{2\pi^2 \times 180}{360S^\circ \pi}=\frac{\pi}{S^\circ}$

Then:

$E^{\circ}=\frac{5S^g}{162}+\frac{C^\circ}{50}+\frac{2\pi^2}{360R}\textrm{rad}$

$E^{\circ}=\frac{1S}{36}^{\circ}+\frac{1S^\circ}{45}+\frac{\pi}{S^\circ}$

$E^{\circ}=\frac{S^2+20\pi}{20S}$

Then I assume that this latter expression must me minimized but would it be used calculus for this?

If so:

$E^{\circ}\,'=\frac{1}{20}-\frac{\pi}{S^2}$

Equating this to zero:

$E^{\circ}=2\sqrt{5\pi}$

But I don't know if this is what it was intended?.

Can someone help me here?. I'm stuck, why it doesn't matches any of the alternatives given or could it be that I made a mistake?. Please help.

答:
While it is true that $R$ rad $=\dfrac {S^\circ \pi}{180^\circ} $, it is not true that $\dfrac {2\pi^2}{360R}$rad $= \dfrac {2\pi^2 \times 180^\circ}{360S^\circ\pi}$; the latter is actually equal to $\dfrac {2\pi^2}{360R \text{ rad}}$. To resolve this, we consider the numerical value of $R$ and the conversion of rad to degrees (sexagesimal) seperately:

$$R = \frac {S \pi}{180}, \quad 1 \text{ rad }=\frac {180}{\pi}^\circ$$

Now we have:

$$\frac {2\pi^2}{360R} \text{ rad } = \frac {2\pi^2 \times 180}{360S\pi} \times \frac {180^\circ}{\pi}=\frac {180^\circ}{S}$$

$$E^\circ = \frac{5S^g}{162}+\frac{C^\circ}{50}+\frac{2\pi^2}{360R}\textrm{rad} = \frac {S^\circ}{36} + \frac {S^\circ}{45} + \frac {180^\circ }S = \left(\frac S{20}+\frac{180}S\right)^\circ$$

To minimize this we may use calculus, or better yet, the 2-term form of AM $\ge$ GM:

$$a+b\ge 2\sqrt{ab}$$

$$\frac S{20}+\frac{180}S\ge2\sqrt{\frac S{20}\times \frac {180}S} =6$$

Hence the minimum of $E^\circ$ is $6^\circ$ (which occurs at $S = 60$).


问:
Distribution of range of N geometric random variables
Suppose I have N i.i.d geometric random variables with parameter $p$: $X_1, X_2, \dots, X_N$. I want to know how large the range can often be. I.e. For a fixed significance level $\alpha$, find $\tilde{k} = \operatorname{argmin}_k P(X_{(N)} - X_{(1)} \leq k) \geq 1 - \alpha$, where $X_{(1)} = \min\{X_1, \dots, X_N\}$ and $X_{(N)} = \max\{X_1, \dots, X_N\}$.

What I have so far is that for an arbitrary non-negative integer $k$, $P(X_{(N)} - X_{(1)} = k) = \frac{(1 - (1 - p)^{k + 1})^N}{1 - (1 - p)^N}$. Proof is as follows:

\begin{align*}
P(X_{(N)} - X_{(1)} = k) =& \sum_{k_1 = 1}^{\infty} P(k_1 \leq X_{(1)} \leq X_{(N)} \leq k_1 + k)\\
=& \sum_{k_1 = 1}^{\infty} P(k_1 \leq X \leq k_1 + k)^N\\
=& \sum_{k_1 = 0}^{\infty} ((1 - p)^{k_1} - (1 - p)^{k_1 + k + 1})^N\\
=& \sum_{k_1 = 0}^{\infty} (1 - p)^{Nk_1}(1 - (1 - p)^{k + 1})^N\\
=& (1 - (1 - p)^{k + 1})^N \sum_{k_1 = 0}^{\infty} (1 - p)^{Nk_1}\\
=& \frac{(1 - (1 - p)^{k + 1})^N}{1 - (1 - p)^N}
\end{align*}

Now that I have already obtained the p.m.f of the range, I also want to find the c.d.f of the range, but I cannot get a compact formula for the c.d.f. Can someone help me solve $\tilde{k}$? If that's not do-able, I would also appreciate it if someone can help me find the expected value of the range. I.e. $E[X_{(N)} - X_{(1)}]$.

Thank you so much!

Body:
There are several issues with the solution above. First of all, $P(X_{(N)} - X_{(1)} = k) = \sum_{k_1 = 1}^{\infty} P(k_1 = X_{(1)} \leq X_{(N)} = k_1 + k)$. In fact, we can directly find the c.d.f building on the attempts above:
\begin{align*}
P(X_{(N)} - X_{(1)} \leq k) =& \sum_{k_1 = 1}^{\infty} P(k_1 = X_{(1)} \leq X_{(N)} \leq k_1 + k)\\
=& \sum_{k_1 = 1}^{\infty} [P(k_1 \leq X_{(1)} \leq X_{(N)} = k_1 + k) - P(k_1 + 1 \leq X_{(1)} \leq X_{(N)} \leq k_1 + k)]\\
=& (1 - (1 - p)^{k + 1})^N \sum_{k_1 = 1}^{\infty} [(1 - p)^{Nk_1} - (1 - p)^{N(k_1 + 1)}]\\
=& (1 - (1 - p)^{k + 1})^N (1 - (1 - p)^N) \sum_{k_1 = 1}^{\infty} (1 - p)^{Nk_1}\\
=& (1 - (1 - p)^{k + 1})^N
\end{align*}
Hence, we get $\tilde{k} = \left \lceil {\frac{\log[1 - (1 - \alpha)^{\frac{1}{N}}]}{\log[1 - p]} - 1} \right \rceil$


问:
Stability: orbits spiralling monotonically
I'm working my way through Dynamics and Bifurcations [Jack K. Hale, Huseyin Kocak] and I can't understand this probably trivial implication in Example 11.1 (page 334). We have a following system of ODEs (perturbed harmonic oscillator)
\begin{aligned}
\dot{x}_1 & = x_2 + a x_1 (x_1^2 + x_2^2), \\
\dot{x}_2 & = -x_1 + a x_2 (x_1^2 + x_2^2),
\end{aligned}
$a\in\mathbb{R}$, which in polar coordinates
\begin{equation}
x_1 = r \cos \theta, \quad x_2 = -r \sin \theta,
\end{equation}
reads
\begin{aligned}
\dot{r} & = a r^3, \\
\dot{\theta} & = 1.
\end{aligned}
The book says: "Since $\dot{\theta}>0$, the orbits spiral monotonically in $\theta$ around the origin. Therefore, the stability type of the origin of [the original planar system] is the same as that of the equilibrium point of the radial equation $\dot{r} = a r$."

I fail to see why it matters whether $\theta$ is a monotonic function of $t$ or not. Can't we draw the same conclusion that the radial equation determines the stability of the origin when this condition does not hold? (Let's say $\dot{\theta} = \sin\theta$?)

答:
Since $\dot\theta = 1$, you can integrate (assuming $t_0=0$) so
$$
\theta(t)=t-t_0
$$
which means the angle is increasing (note that you could also conclude this if $\dot \theta >0, \forall t$). This means that the stability of the orbits depends only if the radius increase or decrease (that is, on the signal of $a$).


答:
Your interpretation of "when $\sqrt{m}+\sqrt{n}$ is rational, then $\sqrt{m}$ and $\sqrt{n}$ are rational" is too broad. For example:

$$\sqrt{2}+\sqrt{(3-\sqrt{2})^2}$$

is rational, because it equals $3$. But of course $\sqrt{2}$ is not rational.

The statement "when $\sqrt{m}+\sqrt{n}$ is rational, then $\sqrt{m}$ and $\sqrt{n}$ are rational" might be true when $m,n$ are integers. But the example here has $m=100+\sqrt{6156}$, not an integer.

Title: How can $\sqrt{100+\sqrt{6156}}+\sqrt{100-\sqrt{6156}}$ be equal to $18$?

Body:
According to this answer, when $\sqrt{m}$+$\sqrt{n}$ is rational, then $\sqrt{m}$ and $\sqrt{n}$ are rational.

But $\sqrt{100+\sqrt{6156}}+\sqrt{100-\sqrt{6156}} = 18 \in \mathbb{Q}$.

So that would imply $\sqrt{100+\sqrt{6156}}$ and $\sqrt{100-\sqrt{6156}}$ both rational. However, the former is $9 + \sqrt{19}$ and the latter is $9 - \sqrt{19}$, both irrational.

Where is the mistake here?

Thanks.


问:
Simplifying this expression $(e^u-1)(e^u-e^l)$
Is it possible to write the following

$$(e^u-1)(e^u-e^l)$$

as

$$e^{f(u,l)}-1?$$

答:
The first expression evaluates to $e^{2u}-e^u-e^l+1$, so if your question is whether there is some algebraic manipulation that brings this into the form of an exponential minus $1$ for general $l,u$ then the answer is no.

In fact the range of the function $x\mapsto e^x-1$ in $\Bbb R$ is $(-1,\infty)$, and the product of two values in that range may be outside the range if one is negative and the other sufficiently large. For instance for $u=-1,l=10$ your product will be much less than $-1$, so it cannot be written as $e^x-1$ for any real number $x$. You might want to get around this by using complex numbers for $f(u,l)$, but then consider the example $u=-\ln2,l=\ln3$, for which you have $e^u-1=-\frac12$ and $e^l-1=2$, so the product $(e^u-1)(e^l-1)$ is $-\frac12\times2=-1$, which is not a value $e^x-1$ even for $x\in\Bbb C$, so this shows you just cannot define $f$ for general arguments $u,l$ at all.


问:
How to make two Coins toss probabilities change simultaneously?
Hello , I am trying to make a coin toss game where the probabilities decrase by 1/2 everytime the same face of the coin appears and in the same time increases by that amount for the other face

exemple:

```<code>heads 0 - tails 0 ---> Probabilities : 50% 50%
heads 1 - tails 0 ---> Probabilities : 25% 75%
heads 2 - tails 0 ---> Probabilities : 12.5% 87.5%
heads 2 - tails 1 ---> Probabilities : 25% 75%
heads 2 - tails 2 ---> Probabilities : 50% 50%
heads 2 - tails 3 ---> Probabilities : 75% 25%
etc...
</code>```

To make this happen I made two variable , headtimes(how many times heads appeared) and tailtimes(how many times appeared) , and I used the following formula to get the percentage of each (the initial chances are 50% 50%):

```<code>headstats = 50/2^(headtimes-tailtimes)
tailstats = 100-headstats
</code>```

But it is not functional , as the probabilities jump directly to 100 if the first toss is tails  50/2^(0-1)

Sorry for my bad english epression and thank you already

答:
If I get what you're saying correctly I guess what you need is the following:(H,T are Headtimes and Tailtimes respectively)
$Headstats=( \frac{1}{2}-sgn(H-T)*(\frac{1}{2}-2^{-|H-T|-1}))*100$
$Tailstats=100-Headstats$


答:
WLOG the number of turns that have already occurred that have been recorded as Heads (= H) is greater than or equal to the number of turns that have already occurred that have been recorded as Tails (= T).

Then, you want that the chance of a Heads being recorded on the next turn to be  $\frac{1}{2^{(H+1-T)}}.$

Clearly you will want the chance of a Tails being recorded on the next turn to be 1 - (the chance of a Heads being recorded on the next turn).

The easiest way to do that is to re-define a turn as follows:
Assuming that $(H + 1 - T) \geq 1,$ a Heads will be registered for the turn if and only if, on this turn, when a coin is tossed (H + 1 - T) times, it comes up heads each time.

If so, the H(eads) is recorded for this turn.  If not, a T(ails) is recorded for this turn.

Then, you move on to the next turn.

Addendum

Responding to the OP's comment:

...but I have to do it with only one formula , not an algorithm

Unclear what you intend here.  I'll take a stab at it.  Let me know if I have misinterpreted your comment.

Assume that the number of turns $=N$ is a known value.

Assume that the number of Heads ($H$'s) that have been recorded on these $N$ turns is also a known value.

You can eliminate any consideration of which turns have been recorded as Tails in the following manner:

On a given turn, compute $D = (2H - N)$ and flip a coin $|D| + 1$ times.

If $D \geq 0$ record Heads on the turn only if all $|D| + 1$ coin flips come up heads.

If $D < 0$ record Heads on the turn if any of the
$|D| + 1$ coin flips come up heads.

Is this what you were looking for?

Title: How to make two Coins toss probabilities change simultaneously?

Body:
Hello , I am trying to make a coin toss game where the probabilities decrase by 1/2 everytime the same face of the coin appears and in the same time increases by that amount for the other face

exemple:

```<code>heads 0 - tails 0 ---> Probabilities : 50% 50%
heads 1 - tails 0 ---> Probabilities : 25% 75%
heads 2 - tails 0 ---> Probabilities : 12.5% 87.5%
heads 2 - tails 1 ---> Probabilities : 25% 75%
heads 2 - tails 2 ---> Probabilities : 50% 50%
heads 2 - tails 3 ---> Probabilities : 75% 25%
etc...
</code>```

To make this happen I made two variable , headtimes(how many times heads appeared) and tailtimes(how many times appeared) , and I used the following formula to get the percentage of each (the initial chances are 50% 50%):

```<code>headstats = 50/2^(headtimes-tailtimes)
tailstats = 100-headstats
</code>```

But it is not functional , as the probabilities jump directly to 100 if the first toss is tails  50/2^(0-1)

Sorry for my bad english epression and thank you already


问:
Cardinal Exponentiation Lemma
The following lemma is stated in Kunen's Set Theory:

$\kappa^{\lambda}= 2^{\lambda} = |\mathcal{P}(\lambda)|$ whenever $\kappa,\lambda$ are cardinals with $\lambda$ infinite and $2 \le \kappa \le 2^{\lambda}$. Also, $2^{\aleph_\alpha} \ge \aleph_{\alpha + 1}$ for every ordinal $\alpha$.

I've seen proofs here on stack exchange that show $\kappa^{\lambda}= 2^{\lambda}$ when $2 \le \kappa \le \lambda$ with the following reasoning:

$$2^\lambda \le \kappa^{\lambda} \le (2^\kappa)^\lambda = 2^{\kappa \cdot \lambda} = 2^\lambda.$$
The last equality makes sense because $\kappa \le \lambda$ and $\kappa \cdot \lambda = \text{max}(\kappa, \lambda).$

However, I want to know how to prove this theorem with, instead, the condition that $\kappa \le 2^\lambda.$  Can we use the same chain or inequalities and equalities above?  Is the last equation still justified, or do we need a new proof?

答:
Yes, the same thing works: $$2^\lambda \le \kappa^\lambda\le (2^\lambda)^\lambda = 2^\lambda. $$

Only difference is in the middle inequality, you use the assumption $\kappa\le 2^\lambda$ combined with monotonicity rather than Cantor's theorem $\kappa <2^\kappa$ combined with monotonicity.

Title: Cardinal Exponentiation Lemma


问:
Question on Euler -function
Let $\varphi$ be the Euler $\varphi$-function. We have for any $a\in\mathbb{Z}^+$:

$\varphi(p^a)=p^a-p^{a-1}$

It is clear that all the positive number of the form $np$ with $1\le n\le p^{a-1}$ are not relatively prime to $p^a$.

May I ask how to prove that all the rest of the positive number less than $p^a$, as the above formula indicates, are indeed relatively prime to $p^a$？

I've just written a trial proof:

So here I think I'm asking if there exists a positive integer $y$ such that

$y<p^a$ [given]

$y\neq np$ for any $1\le n\le p^{a-1}$ [given]

$y$ is not relatively prime to $p^a$ ($\implies$ there exists $q\in\mathbb{Z}^+$ with $q>1$ such that $q\mid y$ and $q\mid p^a$) [assumed]

If so, then there exists a prime $\alpha$ such that $\alpha\mid q$. Hence, there exists $m\in\mathbb{Z}^+$ such that $m\alpha =p^a$. Thus, $\alpha=p$ since $p$ is the only prime factor of $p^a$. Then $p\mid q$. Hence, $p\mid y$. We must have $y=np$ for some $1\le n\le p^{a-1}$ because $y<p^a$. By contradiction, such $y$ doesn't exist.

Could anyone verify my proof please?

答: Actually because the only prime divisor of $p^a$ is $p$ the only common prime divisor between $p^a$ and a number less than it can be $p$ so we just have to count all numbers less than $p^a$ which are divisible by $p$ and this number is clearly equal to $p^{a-1}$ so there are totally $p^{a-1}$ numbers less than $p^a$ that are not relatively prime to $p^a$ and therefore $p^a-p^{a-1}$ numbers that are relatively prime to $p^a$.

Title: Question on Euler -function


问:
$12$ points are arranged around a circle. How many ways can you create two pairs of distinct triangles that overlap?
So this question was actually in three parts including a part that asked for non-overlapping triangles which I correctly calculated to be  $2772$. Take this away from the total amount of triangles $\frac{12C3\cdot9C3}{2}=9240$ gives the correct answer 6468. However, just for practice how would you calculate this from scratch without using the non-overlapping triangles?

I think my attempt is very close but I'm not getting the answer:

Choose the first triangle first by pinning down and disregarding any two distinct points from the circle effectively dividing it into two segments (major and minor). In this case to make it systematic, choose them 4 points apart (that is the minimum because 3 points apart will not work as they will not overlap)

Then select one point in the minor segment to complete the triangle $**2C1**$

To make the other triangle, select another point in the minor segment to ensure overlapping $**1C1**$

To complete the other triangle, select two more points from the major segment $**8C2**$

Now repeat this process by gradually increasing the gap between the pinned-down points so you have

$$\frac{(2C1\cdot1C1\cdot8C2+3C1\cdot2C1\cdot7C2+4C1\cdot3C1\cdot6C2+5C1\cdot4C1\cdot5C2+6C1\cdot5C1\cdot4C1+7C1\cdot6C1\cdot3C2+8C1\cdot7C1\cdot2C2)}{2}\cdot12 = 5442$$
The answer is 6468

Edit: the triangles are selected from distinct points (no repetition between the two triangles)

答:
Pick any of the $12$ points as a base point and number the points $1$ through $12$ clockwise starting at the base point. There are $\binom{12}6=924$ ways to choose $6$ of them to be the vertices of the two triangles.

Say that we choose points $p_1,\ldots,p_6$, where $p_1<\ldots<p_6$. There are $7$ ways to assign them to two triangles so that the triangles overlap. If we label a point $0$ for one triangle, $1$ for the other, and then list the labels of $p_1$ through $p_6$ in that order, the acceptable possibilities are $001011$, $001101$, $010011$, $010101$, $010110$, $011001$, and $011010$: these are the labelings that are not cyclic permutations of $000111$, since it is precisely the cyclic permutations of $000111$ that correspond to non-overlapping triangles. And

$$7\binom{12}6=7\cdot 924=6468\,$$

as it should.


答:
This process is much easier than what you listed, but still essentially counts the "non-overlapping triangles first".

We want to count the number of pairs of triangles that overlap.

Such pairs are defined (not necessarily uniquely) by their vertices.

Given any 6 points (out of 12), how many ways are there to get overlapping triangles?

Given any 6 points (out of 12), how many ways are there to get pairs of triangles? $\rightarrow { 6 \choose 3 } / 2 $.

Given any 6 points (out of 12), how many ways are there to get non-overlapping triangles? There are only 3 such pairs, formed by consecutive vertices.

So, there are $10 - 3 = 7 $ overlapping pairs.

How many ways are there to choose 6 points out of 12?

Hence, there are ${ 12 \choose 6 } \times 7 = 6468$ ways.

Title: $12$ points are arranged around a circle. How many ways can you create two pairs of distinct triangles that overlap?

Body:
So this question was actually in three parts including a part that asked for non-overlapping triangles which I correctly calculated to be  $2772$. Take this away from the total amount of triangles $\frac{12C3\cdot9C3}{2}=9240$ gives the correct answer 6468. However, just for practice how would you calculate this from scratch without using the non-overlapping triangles?

I think my attempt is very close but I'm not getting the answer:

Choose the first triangle first by pinning down and disregarding any two distinct points from the circle effectively dividing it into two segments (major and minor). In this case to make it systematic, choose them 4 points apart (that is the minimum because 3 points apart will not work as they will not overlap)

Then select one point in the minor segment to complete the triangle $**2C1**$

To make the other triangle, select another point in the minor segment to ensure overlapping $**1C1**$

To complete the other triangle, select two more points from the major segment $**8C2**$

Now repeat this process by gradually increasing the gap between the pinned-down points so you have

$$\frac{(2C1\cdot1C1\cdot8C2+3C1\cdot2C1\cdot7C2+4C1\cdot3C1\cdot6C2+5C1\cdot4C1\cdot5C2+6C1\cdot5C1\cdot4C1+7C1\cdot6C1\cdot3C2+8C1\cdot7C1\cdot2C2)}{2}\cdot12 = 5442$$
The answer is 6468

Edit: the triangles are selected from distinct points (no repetition between the two triangles)


问:
need to show antiderivative exist
Let $U$ be a simply connected open set and $z_1,\dots, z_n$ be points of $U$ and let $U^*=U\setminus \{z_1,\dots,z_n\},z_i\in U$ Let $f$ be analytic on $U^*$. Let $\gamma_k$ be a small circle centered at $z_k$ and let $$a_k={1\over 2\pi i}\int_{\gamma_k} f(\xi)d\xi$$ let $$h(z)=f(z)-\sum a_k/(z-z_k)$$ we need to show there exist analytic function $H$ such that $H'=h$ </p>

答:
Hints: 1) what is the residue of $h$ at $z_j$?

2) Show that path integrals $\int_\Gamma h(z)\ dz$ in $U \backslash \{z_1,\ldots,z_n\}$ with the same endpoints are always equal.

Title: need to show antiderivative exist


问:
What restrictions lay on truth sets of predicates A(x) and B(x) if the given predicate is true
Suppose we are given 2 predicates
$A(x)$ and $B(x)$ with domain $M$.

Suppose next we are given the following predicate
$$\neg (A(x) \land B(x)) \land (\forall x(A(x) \rightarrow B(x)))$$
which we know is true, so
$$\neg (A(x) \land B(x)) \land (\forall x(A(x) \rightarrow B(x))) = 1$$

The question is how does it restrict the truth sets of $A(x)$ and $B(x)?$

It is obvious that we have
$$\neg (A(x) \land B(x)) = 1 \\
A(x) \land B(x) = 0\\
A(x) = 0 \lor B(x) = 0$$
So from that we get that either truth set for $A(x)$ is $E_A \neq M$ or truth set for $B(x)$ is $E_B \neq M$.

But knowing that
$$\forall x(A(x) \rightarrow B(x)) = 1\\
\forall x(\neg A(x) \lor B(x)) = 1$$
I have no idea how to link it to useful information on truth sets of $A(x)$ and $B(x)$, any suggestions?

答: You are getting hung up on truth sets when there is only one variable in the problem.  Focus on one element $x$ of $M$ and ask whether $A(x)$ and $B(x)$ can be true because all the elements are equivalent.  You have found that both $A(x)$ and $B(x)$ cannot both be true but $A(x) \implies B(x)$.  You should be able to derive that $A(x)$ is false and $B(x)$ can be anything.  Check that in the original axiom and it works.


答: If we put $\kappa = 2^\lambda$, then the equation $2^{\kappa \cdot \lambda} = 2^\lambda$ becomes $2^{2^\lambda} = 2^\lambda$, which is false by Cantor's Theorem. So the final equation is not justified in this situation.

Title: Cardinal Exponentiation Lemma

Body:
The following lemma is stated in Kunen's Set Theory:

$\kappa^{\lambda}= 2^{\lambda} = |\mathcal{P}(\lambda)|$ whenever $\kappa,\lambda$ are cardinals with $\lambda$ infinite and $2 \le \kappa \le 2^{\lambda}$. Also, $2^{\aleph_\alpha} \ge \aleph_{\alpha + 1}$ for every ordinal $\alpha$.

I've seen proofs here on stack exchange that show $\kappa^{\lambda}= 2^{\lambda}$ when $2 \le \kappa \le \lambda$ with the following reasoning:

$$2^\lambda \le \kappa^{\lambda} \le (2^\kappa)^\lambda = 2^{\kappa \cdot \lambda} = 2^\lambda.$$
The last equality makes sense because $\kappa \le \lambda$ and $\kappa \cdot \lambda = \text{max}(\kappa, \lambda).$

However, I want to know how to prove this theorem with, instead, the condition that $\kappa \le 2^\lambda.$  Can we use the same chain or inequalities and equalities above?  Is the last equation still justified, or do we need a new proof?


问:
help with differential equation using substitution
I have the following differential equation:
$$xe^xy'-\dfrac{y}{x}e^x+x\cos (x)=0$$

I tried using substitution, namely:

Let $v=\dfrac{y}{x}$, then $\dfrac{dy}{dx}=\dfrac{dv}{dx}x+v$. Substituting yields:

$$xe^x\left(\dfrac{dv}{dx}x+v\right)-ve^x+x\cos (x)=\dfrac{dv}{dx}x+v-\dfrac{v}{x}+e^{-x}\cos (x)=0$$

But it is still not separable. I also tried the substitution $v=\dfrac{y}{x^2}$. That didn't work either.

For this problem, a substitution should work; honestly, I think I am making a stupid mistake and that's why I am stuck. Could anyone shed me some light on this equation?

答:
I would start by noticing that

\begin{align*}
xe^{x}y' - \frac{y}{x}e^{x} + x\cos(x) = 0 & \Longleftrightarrow y' - \frac{y}{x^{2}} + e^{-x}\cos(x) = 0\\\\
& \Longleftrightarrow e^{1/x}y' - \frac{e^{1/x}}{x^{2}}y = -e^{-x + 1/x}\cos(x)\\\\
& \Longleftrightarrow (ye^{1/x})' = -e^{-x + 1/x}\cos(x)
\end{align*}

Apparently, this is as far as one can go.

Hopefully this helps!


答:
1
$$\neg (A(x) \land B(x)) \land (\forall x(A(x) \rightarrow B(x)))$$

2
$$\neg (A(x) \land B(x)) \equiv (\neg A(x)) \lor (\neg B(x))$$

$$(\forall x(A(x) \rightarrow B(x))) \equiv (\neg A(x)) \lor B(x)$$

3
$$(\neg A(x) \lor \neg B(x)) \land (\neg A(x) \lor B(x)) \equiv (\neg A(x))$$

Title: What restrictions lay on truth sets of predicates A(x) and B(x) if the given predicate is true

Body:
Suppose we are given 2 predicates
$A(x)$ and $B(x)$ with domain $M$.

Suppose next we are given the following predicate
$$\neg (A(x) \land B(x)) \land (\forall x(A(x) \rightarrow B(x)))$$
which we know is true, so
$$\neg (A(x) \land B(x)) \land (\forall x(A(x) \rightarrow B(x))) = 1$$

The question is how does it restrict the truth sets of $A(x)$ and $B(x)?$

It is obvious that we have
$$\neg (A(x) \land B(x)) = 1 \\
A(x) \land B(x) = 0\\
A(x) = 0 \lor B(x) = 0$$
So from that we get that either truth set for $A(x)$ is $E_A \neq M$ or truth set for $B(x)$ is $E_B \neq M$.

But knowing that
$$\forall x(A(x) \rightarrow B(x)) = 1\\
\forall x(\neg A(x) \lor B(x)) = 1$$
I have no idea how to link it to useful information on truth sets of $A(x)$ and $B(x)$, any suggestions?


问:
Semirings of small orders
A semiring is a structure $(R, +, 0, *)$ such that $(R, +, 0)$ is a commutative monoid, $(R, *, 0)$ is a semigroup with zero, and the distributive laws hold.

I know that there were attempts at computing semigroups of small order, and all semigroups up to order $8$ has been computed. Was there a similar attempt at computing semirings of small orders? If yes, where can I find results of that?

答:
This is not a complete answer to your question, but I will sketch a method to construct finite semirings (of small orders).

Since you are interested in semirings of small orders, one strategy would be embedded them into some class of universal semirings via some Cayley’s type representation theorem. For  examples:

if you want to know all groups of order less than some small $n,$ you can do so by looking at subgroups of the symmetric group $S_n.$

For semigroups of order less than $n,$ you can look at sub-semigroups of  symmetric semigroup of endomorphisms of a set (the set of functions to itself) with $n$ elements. The semigroup (in fact, a monoid) of such transformations is of order $n^n,$ and therefore become extermly large with $n.$

There are similar such theorems for other algebraic structures (such as Boolean algebras, categories, ...) as well. Now lets formulate a representation theorem for semirings.

Given a semiring $R,$ additive semigroup endomorphism of $R$ denoted by $\mathbf{End}(R)$ form a semiring under pointwise addition, composition and zero map. Furthermore, there is an injective semiring homomorphism $\Phi : R\hookrightarrow\mathbf{End}(R)$ given by $\Phi(r)(a)=\varphi_r(a)=ra$ for all $a, r\in R,$ and here $\varphi_r\in\mathbf{End}(R).$

It is not difficult to prove this result. Note that we can construction the semiring $\mathbf{End}(R)$ only using the additive structure of $R.$ In other words, any semiring is isomorphic to a sub-semiring of endomorphisms of a semigroup. Now since you have a classification  all semigroups up to order $8,$ you can perform this construction to find some semirings up to there.

Title: Semirings of small orders


问:
When is it solvable:$10^a+10^b\equiv -1 \pmod p$
If $p$ is a prime, $(a,p)=1$,denote $ord(a,p)=d,$  where $d$ is the smallest positive integer solution to the equation $a^d\equiv 1 \pmod p$.We can prove that $$10^n\equiv -1 \pmod p\tag1$$ is solvable iff $ord(10,p)$ is even.

Now,consider this equation,$$10^a+10^b\equiv -1 \pmod p.\tag2$$
If $10$ is a primitive root modulo $p$, then there is an integer $a$ for every $b≠\dfrac{p-1}{2}\pmod {p-1}$ so that $a,b$ satisfies $(2)$.

My question is,what's the necessary and sufficient condition that $(2)$ has at least $1$ solution?

If we are given a prime $p$,how to determine whether $(2)$ is solvabe?

This is a way,but not effectively: for every positive integer $b\leq\frac{1}{2}ord(10,p)$,determine whether $(2)$ is solvabe for $a$.By this way,I find $(2)$ is solvable for these primes,which $10^n\equiv -1 \pmod p$ is not solvable:

$3,31,37,43,53,67,71,83,107,151,163,173,191,199,227,277,283,307,311,317,347,359,397,431,439,443,467,479,523,547,563,587,599,613,631,643,683,719,751,757,773,787,797,827,839,853,883,907,911,919,947,991,\cdots$

My original problem is: how many "$1$" is need at least for a decimal number which is consisting of "$0$" and "$1$" and divisible by $p$?This question is to find these primes that three "$1$" is need at least.

Thank you.

答:
The thing looks pretty general.  Consider 7 in base 2.  Here 2+4-1, mod 7, even though 2 is not a primitive root.  The thing is resolving to what conditions are needed for p to divide the sum of three powers of 10.  The number 37 divides any such sum as long as the three powers are different, modulo 3, eg, 100,011.

Having a period that is divisible by $3$ implies a solution must exist, for this reason.


问:
Let $X$ and $Y$ be subspaces of a vector space $V$. Show that $X\cup Y$ is a subspace if and only if $X\subset Y$ or $Y \subset X$
I'm currently learning linear algebra using textbook Linear Algebra Done Wrong, and I encountered this problem.

Let $X$ and $Y$ be subspaces of a vector space $V$. Show that $X\cup Y$ is a subspace if and only if $X\subset Y$ or $Y\subset X$

I don't really have any idea. I only figured out that 0 is in the set, so it is not empty. What else should I do? Thanks!!

答: I'm assuming you're just working on the forward direction seeing as the reverse direction is trivial. Try proving by contrapositive: so suppose that $X\not\subseteq Y$ and $Y\not\subseteq X$, and we want to show $X\cup Y$ is not a subspace. Then you can take some $x\in X\setminus Y$ and some $y\in Y\setminus X$. Then clearly $x,y\in X\cup Y$, but what about $x+y$?


问:
Proof of the union of two countable sets is countable
I think I have got some clues for how to prove that for two disjoint countable sets, but I don't know how to deal with two ordinary countable sets. I would like to ask for some advice. Thanks. It also would be nice to have a rigorous proof.</p>

答:
Nice problem. This problem lays the foundation for solving many problems, so I will write a very detailed solution.

Let's start with agreeing.

Definition 1: We say that the set $A$ has the same cardinality as set $B$ is there exists $f: A \to B$ that is one-to-one and onto. In this case, we write $A\sim B$.

Definition 2: We say that $A$ is countable if $\mathbb{N}\sim A$. An infinite set that is not countable is called an uncountable set.

For example, we can see that:

The set $\mathbb{Q}$ is countable but the set $\mathbb{R}$ is uncountable.

Your problem, we can write as:

Let $A$ and $B$ countable set. Prove that $A\cup B$ is countable.

Proof: By definition $\color{blue}{(2)}$, we need to show that $\mathbb{N}\sim A\cup B$, so by definition $\color{blue}{(1)}$ we need to prove that $\color{blue}{\text{there exists}}$ a function $f: \mathbb{N}\to A\cup B$ and that $f$ is a function $\color{blue}{\text{one-to-one}}$ and $\color{blue}{\text{onto}}$.

In mathematics it is important, as I have done above to write what you must proof in terms of the results you want to use. Now, let's go back to the hypotheses of the problem.

Since that $A$ is countable set, so $\color{blue}{\text{there exists}}$ a function $g: \mathbb{N}\to A$ such that $g$ is is a function $\color{blue}{\text{one-to-one}}$ and $\color{blue}{\text{onto}}$. Similar, since that $B$ is countable set, so $\color{blue}{\text{there exists}}$ a function $h: \mathbb{N}\to B$ such that $h$ is a function $\color{blue}{\text{one-to-one}}$ and $\color{blue}{\text{onto}}$.

Something common in mathematics is to try to use proofs of already proven theorems, as models to build new proofs. If you have ever proved that naturals are countable, then you will remember that something like "separate the odd and even numbers and then join them by a correspondence rule (a function)" was done.

Let, $$f: \mathbb{N}\to A\cup B$$
defined by $$f(x):=\left\{\begin{aligned}h\left( \frac{n}{2}\right), \quad \text{n is even}\\
g\left( \frac{n+1}{2}\right), \quad \text{n is odd} \end{aligned} \right.$$

It's clear that $f$ is a function $\color{blue}{\text{one-to-one}}$ and $\color{blue}{\text{onto}}$.

Now, it is time for you to work. You must prove that the function $f$ is really $\color{blue}{\text{one-to-one}}$ and $\color{blue}{\text{onto}}$.