Math Challenge Thread (October 2023)

[Infrared]

The Math challenge threads have returned!

Rules:
1. You may use google to look for anything except the actual problems themselves (or very close relatives).
2. Do not cite theorems that trivialize the problem you're solving.
3. Do not solve problems that are way below your level. Some problems may be intended for high school or early university level students. If a problem looks way too easy for you, leave it for someone else :)
4. Have fun!

1. (solved by @PeroK and @mfb) Fischer random is a variant of chess with all of the same rules, except that in the starting position, the positions of the pieces on the back ranks are scrambled, according to the following rules:

a) Both sides' pieces are scrambled in the same way, so each piece is still opposite an enemy piece of the same type, along the file.
b) The king is between the two rooks.
c) The two bishops are opposite colors.

Verify that there are 960 possible starting positions for Fischer random, explaining the variant's other common name: "chess 960". It might seem that when you reflect the board, you get a position with equivalent game play, so there are effectively only 480 inequivalent starting positions. What is wrong with this logic?

2. solved by @martinbn) Let $v$ be a known nonzero vector in $\mathbb{R}^3.$ If you know $v\cdot w$ and $v\times w,$ can you determine what the vector $w$ must be? If so, give a formula for $w$ in terms of $v$ and $v\cdot w$ and $v\times w$. If not, give an example where there are multiple possible solutions for $w$.

3. solved by @martinbn and @anuttarasammyak)Evaluate the sum $\sum_{n=1}^\infty\frac{1}{n(n+1)(n+2)}.$

4. (solved by @pasmith and @anuttarasammyak)Evaluate $\int_0^1\left(\frac{x^2-4x+2}{2-x}\right)^{100} dx.$

5. (solved by @julian) Show that $\sum_{n=1}^\infty\frac{\sin(n)}{n}=\frac{\pi-1}{2}.$

6. (solved by @martinbn) Let $A$ be the $n\times n$ matrix whose diagonal entries are 1 and whose off-diagonal entries are 2. Find all eigenvalues of $A$ and their multiplicities.

7. (solved by @martinbn) Let $S_5$ be the group of permutations on a 5 element set. Let $X=\{(\sigma,\pi)\in S_5\times S_5: \sigma\pi=\pi\sigma\}.$ What is $|X|?$

8. (solved by @martinbn) Let $\alpha$ be a complex number on the unit circle. Suppose that $f\in\mathbb{Q}[x]$ is irreducible and has $\alpha$ as a root. Show that if $\beta$ is any root of $f$, then $1/\beta$ is also a root.

9. (solved by @mathwonk)Let $M_g$ be the closed orientable surface of genus $g\geq 0.$ Let $\vee_{i=1}^n S^1$ be the wedge product of $n$ circles. Show that if there exists a continuous map $r:M_g\to\vee_{i=1}^n S^1$ with a right homotopy inverse, then $n\leq g$. $r$ having a right homotopy inverse means that there exists $\iota:\vee_{i=1}^n S^1\to M_g$ with $r\circ \iota$ homotopic to the identity map on $\vee_{i=1}^n S^1$. An example of a map with a right homotopy inverse would be a retraction onto a subspace.

10. The point of this problem is to show that if two (connected and closed) diffeomorphic manifolds have the same volume, then there is a diffeomorphism between them that preserves volume. More precisely, let $M$ and $M'$ be diffeomorphic manifolds, which are closed and connected. If $\omega$ and $\omega'$ are volume forms on $M$ and $M'$, respectively, with $\int_M \omega=\int_{M'}\omega'$, then there is a diffeomorphism $f:M\to M'$ such that $f^*\omega'=\omega.$

a) Explain why we may assume without loss of generality that $M=M'$

b) Consider the path of top forms $\omega_t=(1-t)\omega+t\omega'$ with $0\leq t\leq 1.$ Explain why each $\omega_t$ is a volume form on $M.$

c) We will construction the diffeomorphism as the flow of a 1-parameter family of vector fields. Show that if $X_t$ is a 1-parameter family of vector fields and $\phi_t:M\to M$ is its flow map, then $\frac{d}{dt}\phi_t^*\omega_t= \phi_t^*\left(d (\iota_{X_t}\omega_t)+(\omega'-\omega)\right),$ where $\iota$ means interior multiplication. You will need Cartan's formula for the Lie derivative of a differential form, found on the same page.

d) Show that you may smoothly choose the vector fields $X_t$ such that $\frac{d}{dt}\phi_t^*\omega_t=0$ and conclude that $\phi_1:M\to M$ is a diffeomorphism satisfying $\phi_1^*\omega'=\omega.$

 

[julian]

Question #5:

Spoiler

We will evaluate

\begin{align*}
\sum_{n=1}^\infty \frac{\sin nx}{n} \qquad (*)
\end{align*}

for $0 \leq x \leq 2 \pi$ and then set $x=1$. We will do this by evaluating

\begin{align*}
f (x) = \sum_{n=1}^\infty (-1)^n \frac{\sin nx}{n}
\end{align*}

for $-\pi \leq x \leq \pi$ and then at the end making the shift $x \mapsto x - \pi$ to obtain $(*)$.

I will express the sum via a complex contour integration. It employs the fact that the function

\begin{align*}
\dfrac{\sin z x}{\sin \pi z}
\end{align*}

has simple poles at all integer values except when $\sin z x = 0$, as we now verify. First consider the case where $\sin z x \not= 0$ for $z=n$,

\begin{align*}
\dfrac{\sin z x}{\sin \pi z} & = \dfrac{\sin [n + (z-n)] x}{\sin \pi [n + (z-n)]}
\nonumber \\
& = \dfrac{\sin n x + \cdots}{(-1)^n [\pi (z-n) - \frac{1}{3!} \pi^3 (z-n)^3 + \cdots]}
\nonumber \\
& = (-1)^n \dfrac{\sin n x + \cdots}{(z-n) \pi [1 - \frac{1}{3!} \pi^2 (z-n)^2 + \cdots]}
\nonumber \\
& = (-1)^n \dfrac{\sin n x}{(z-n) \pi} + \cdots
\end{align*}

Now consider the case where $\sin z x = 0$ for some $z=n$,

\begin{align*}
\left| \lim_{z \rightarrow n} \dfrac{\sin z x}{\sin \pi z} \right| & = \left| \lim_{z \rightarrow n} \dfrac{\frac{d}{dz} \sin z x}{\frac{d}{dz} \sin \pi z} \right|
\nonumber \\
& = \left| \lim_{z \rightarrow n} \dfrac{x \cos z x}{\pi \cos \pi z} \right| < \infty
\end{align*}

So when $\sin z x$ vanishes for $z = n$, there is no pole at $n$. This allows us to write

\begin{align*}
\sum_{n=1}^\infty (-1)^n \frac{\sin n x}{n} = \frac{1}{2i} \oint_C \dfrac{\sin z x}{z \sin \pi z} dz
\end{align*}

where the contour $C$ is defined in fig (a).

We have

\begin{align*}
2 \sum_{n=1}^\infty (-1)^n \frac{\sin n x}{n} & = \sum_{n=1}^\infty (-1)^n \frac{\sin n x}{n} + \sum_{n=-1}^{-\infty} (-1)^n \frac{\sin n x}{n}
\nonumber \\
& = \frac{1}{2i} \oint_{C+C'} \dfrac{\sin z x}{z \sin \pi z} dz
\end{align*}

where the contour $C'$ is defined in fig (a). We complete the path of integration along semicircles at infinity (see fig (b)) since the integration along them vanishes. Since the resulting enclosed area contains no singularities except at $z=0$, we can shrink this contour down to an infinitesimal circle $C_0$ around the origin (see fig (c)). So that

\begin{align*}
f (x) & = \frac{1}{4i} \oint_{C_0} \dfrac{sin zx}{z \sin \pi z} dz
\end{align*}

We expand the integrand in powers of $z$ about $z=0$ and isolate the $z^{-1}$ term to obtain the residue. Then

\begin{align*}
f (x) & = \frac{1}{4i} (-2 \pi i) \frac{x}{\pi}
\nonumber \\
& = - \frac{x}{2}
\end{align*}

for $-\pi \leq x \leq \pi$. Making the shift $x \mapsto x - \pi$ to obtain for $(*)$

\begin{align*}
\sum_{n=1}^\infty \frac{\sin nx}{n} = \frac{\pi - x}{2}
\end{align*}

for $0 \leq x \leq 2 \pi$. Finally, putting $x=1$ we have:

\begin{align*}
\sum_{n=1}^\infty \frac{\sin n}{n} = \frac{\pi - 1}{2}
\end{align*}

 

[anuttarasammyak]

Question #5

Spoiler

$$\sum_{n=1}^\infty \frac{\sin n}{n}=\int_0^1 dx\sum_{n=1}^\infty \cos nx=\int_0^1 dx (\pi\delta(x)-\frac{1}{2})=\frac{\pi-1}{2}$$

 

[Infrared]

Very nice @julian! Your identity $\sum_{n=1}^\infty\frac{\sin(nx)}{n}=\frac{\pi-x}{2}$ is much easier to get with Fourier series though have you to work backwards a little bit to realize that this is the function you're taking a Fourier series of.

@anuttarasammyak This looks very slick, but a little beyond my comprehension! I'm sure there's a way to make it rigorous, but I haven't really studied distributions so I'm not sure how. Perhaps you could flesh it out for me a little bit?

 

[PeroK]

Question 1

Spoiler

The way I did this was to place the two Rooks first and then the calculation depends on how many squares are between them. This limits the King placement and affects the Bishop placements, depending on whether the Rooks occupy the same coloured squares or not.

I've put this in a table. Here's an explanation of the first three lines:

Line 1: Column 1 indicates that the rooks have 6 squares between them. I.e. they are in their conventional positions. There is only one possibility for this. Note that the Rooks in this case are on opposite coloured squares. The King can occupy any of these 6 squares. In this case, two squares of one colour and one square of the other colour are occupied. So, one Bishop has two possible squares and the second Bishop three possible squares. Finally, the Queen has three possible squares, which also determines the position of the Knights.

Line 2 & 3: The Rooks have 5 squares between them. There are two possibilities for this. Note that the Rooks occupy the same coloured squares. The King has 5 possible squares - 2 of which have the same colour as the Rooks (line 2). This leaves only one square for the first Bishop and 4 squares for the second Bishop. Again the Queen has 3 possible squares.

Line 3 covers the case where the King takes one of the 3 possible squares that have a different colour from the Rooks. The rest is as line 1.

The remaining lines deal with the cases where the Rooks have 4, 3, 2 and 1 space(s) between them.

PS the reason we do not have symmetry under a lateral reflection is the "Kingside" and "Queenside" castling rules.

Rook
Distance	R	K	B1	B2	Q	Total
6	1	6	2	3	3	108​
5	2	2	1	4	3	48​
5	2	3	2	3	3	108​
4	3	4	2	3	3	216​
3	4	1	1	4	3	48​
3	4	2	2	3	3	144​
2	5	2	2	3	3	180​
1	6	1	2	3	3	108​
						960​

[\SPOILER]

 

[mfb]

You can find the answer to (1) without a table by changing the order:

Spoiler

Place the two bishops first: 4*4 options.
In the remaining 6 spots, reserve 3 for rooks and king: (6 choose 3) options. The king takes the middle one.
In the remaining 3 spots, pick one for the queen: 3 options. The remaining two spots are knights.
4*4*(6 choose 3)*3 = 960

 

[anuttarasammyak]

@anuttarasammyak This looks very slick, but a little beyond my comprehension! I'm sure there's a way to make it rigorous, but I haven't really studied distributions so I'm not sure how. Perhaps you could flesh it out for me a little bit?

Attached video titled Fourier series and delta function may supplements my answer.

 

[Infrared]

The solutions by @PeroK and @mfb for the first problem look correct! I'll also share how I counted. There are $\frac{8!}{2!2!2!}=7!$ ways to arrange the 8 pieces. If we choose a setup uniformly at random, there is a 4/7 probability that the two bishops have opposite colors, and then (independently) a $1/3$ probability that the king is between the two rooks, so the number of valid arrangements is $(7!)(\frac{4}{7})(\frac{1}{3})=960.$

 

[pasmith]

(4):

Spoiler

Set $2 - x = \sqrt{2}e^t$. Then $$\begin{split} \int_0^1 \left(\frac{x^2 - 4x + 2}{2 - x}\right)^{100}\,dx &= \int_1^2 \left( (2 - x) - \frac{2}{2 - x}\right)^{100}\,dx \\ &= 2^{50}\sqrt{2}\int_{-\frac12 \ln 2}^{\frac12 \ln 2} e^t\left(e^t - e^{-t}\right)^{100}\,dt \\ &= 2^{150}\sqrt{2} \int_{-\frac12 \ln 2}^{\frac12 \ln 2} (\cosh t + \sinh t)\sinh^{100}t\,dt.\end{split}$$ The $\int_{-\frac12 \ln 2}^{\frac 12 \ln 2} \sinh^{101} t\,dt$ term vanishes by symmetry, and we are left with $$\begin{split} 2^{150}\sqrt{2} \int_{-\frac12 \ln 2}^{\frac12 \ln 2} \cosh t \sinh^{100} t\,dt &= 2^{150}\sqrt{2} \left( \frac{2 \sinh^{101} (\frac12 \ln 2)}{101}\right) \\ &= \frac{2^{151}\sqrt 2}{101} \frac{1}{2^{101}} \left( \sqrt{2} - \frac{1}{\sqrt{2}}\right)^{101} \\ &= \frac{2^{50}\sqrt 2}{101} \left(\frac 1{\sqrt{2}}\right)^{101} \\ &= \frac{2^{50}\sqrt 2}{101} \frac1{2^{50}\sqrt 2} \\ &= \frac{1}{101}.\end{split}$$

 

[martinbn]

3. Evaluate the sum $\sum_{n=1}^\infty\frac{1}{n(n+1)(n+2)}.$

$\frac{1}{n(n+1)(n+2)}=\frac12\left(\frac1n-\frac1{n+1}\right)+\frac12\left(-\frac1{n+1}+\frac1{n+2}\right)$

So the sum telescopes.

 

[martinbn]

6. Let $A$ be the $n\times n$ matrix whose diagonal entries are 1 and whose off-diagonal entries are 2. Find all eigenvalues of $A$ and their multiplicities.

$-1$ is obviously and eigenvalue. In fact $A-Id$ has rank one, the eigenspace $V_{-1}$ is $n-1$ dimensional. And also clearly the vector $(1,1,...,1)^t$ is an eigenvector with eigen value $2n+1$. So two eigenvalues $-1$ and $2n+1$ with multiplicities $n-1$ and $1$.

 

[anuttarasammyak]

Question #4

Spoiler

$$t:=\frac{x^2-4x+2}{x-2}$$
$$(x-2)^2-t(x-2)-2=0$$
By solving this quadratic equation, minding x-2 <0,
$$x-2 =\frac{t}{2}-\frac{\sqrt{t^2+8}}{2}$$
$$dx = (\frac{1}{2}-\frac{2t}{\sqrt{t^2+8}})dt$$
The integral in general is
$$\int_{-1}^{1}(-t)^{2N} (\frac{1}{2}-\frac{2t}{\sqrt{t^2+8}}) dt= \frac{1}{2N+1}$$
The case of 2N=100, it is $\frac{1}{101}$, the solution of the problem.

 

[anuttarasammyak]

So the sum telescopes.

Spoiler

You would complete it with the answer 1/4 which comes from the first term for n=1.

 

[martinbn]

8. Let $\alpha$ be a complex number on the unit circle. Suppose that $f\in\mathbb{Q}[x]$ is irreducible and has $\alpha$ as a root. Show that if $\beta$ is any root of $f$, then $1/\beta$ is also a root.

Because the coefficients are real, even rational, $\bar{\alpha}$ is also a root, and of course it is equal to $\frac1\alpha$. If the degree of $f$ is $n$, then $x^nf(\frac1x)$ and $f(x)$ are irreducible and have the same root $\bar{\alpha}$. So there is a constant $c$ such that $x^nf(\frac1x)=cf(x)$. Then for $x=\beta$ we have $\beta^nf(\frac1\beta)=cf(\beta)$. Hence if $\beta$ is a root, so is $\frac1\beta$.

ps At first I thought that $\alpha$ has to be a root of unity and then $f$ has to divide $x^N-1$ and all its roots have to be roots of unity so for any root $\beta=\frac1\beta$. But I think this is not true. So the extra question is, is it true that $\alpha$ has to be a root of unity or can you give a counter example.

 

[Infrared]

So the extra question is, is it true that has to be a root of unity or can you give a counter example.

This is not the case. For example, $\frac{3}{5}+\frac{4}{5}i$ is on the unit circle, but the angle $\text{arcsin}(4/5)$ is not a rational multiple of pi (the only time $x/\pi$ and $\sin(x)$ can both be rational is when $\sin(x)=0,\pm 1/2,\pm 1$).

 

[martinbn]

This is not the case. For example, $\frac{3}{5}+\frac{4}{5}i$ is on the unit circle, but the angle $\text{arcsin}(4/5)$ is not a rational multiple of pi (the only time $x/\pi$ and $sin(x)$ can both be rational is when $\sin(x)=0,\pm 1/2,\pm 1$).

Ah, good point, I was thinking about algebraic integers. It still should be false, but not so obvious.

 

[Infrared]

Ah, good point, I was thinking about algebraic integers. It still should be false, but not so obvious.

A bit of googling finds a fun argument giving examples: Let $f$ be an irreducible monic degree 4 polynomial in $\mathbb{Z}[x]$ satisfying:

1) $f$ has exactly two real roots.
2) The coefficient of $x^i$ is the same as the coefficient of $x^{4-i}.$

An example of such a polynomial is $x^4-2x^3-2x+1.$ Let $\alpha$ be one of its non-real roots. Then both $\overline{\alpha}$ and $1/\alpha$ are non-real roots unequal to $\alpha$ so they must equal each other. The condition $\overline{\alpha}=1/\alpha$ is equivalent to $|\alpha|=1$ and $\alpha$ can't be a root of unity because no cyclotomic polynomial has two real roots. Maybe showing that this polynomial has a root on the unit circle would've been a better problem for this thread!

 

[martinbn]

2. Let $v$ be a known nonzero vector in $\mathbb{R}^3.$ If you know $v\cdot w$ and $v\times w,$ can you determine what the vector $w$ must be? If so, give a formula for $w$ in terms of $v$ and $v\cdot w$ and $v\times w$. If not, give an example where there are multiple possible solutions for $w$.

I have a question about this one. I am right to assume that from what is given/known in the problem it means that $v\cdot v$ and $v\times (v\times w)$ are also known? If that is the case the triple vector product identity reads $v\times (v\times w) = (v\cdot w)v-(v\cdot v)w$. Therefore $w = \frac{(v\cdot w)v}{v\cdot v}-\frac{v\times (v\times w)}{v\cdot v}$.

 

[Infrared]

Therefore $w = \frac{(v\cdot w)v}{v\cdot v}-\frac{v\times (v\times w)}{v\cdot v}$.

This is correct but this problem was intended for much less advanced students than you :)

 

[martinbn]

This is correct but this problem was intended for much less advanced students than you :)

Sorry, I just read the rules. I owe you a problem. If I come across an interesting one I will message it to you for some of the next sets.

I can do #7, but I am to lazy to type.

 

[Infrared]

Some hints for the remaining problems :)

7)In general, for a finite group $G$, the number of commuting pairs $(g,h)\in G\times G$ is $|G| \cdot \left(\text{number of conjugacy classes of G}\right).$ To prove this, find a formula for the number of elements which commute with a given $g\in G$ and then sum over $g.$

9) How do the cohomology rings of $M_g$ and $\vee_{i=1}^n S^1$ compare?

10)Just to clarify what is meant by the flow map of a 1-paramter family of vector fields: given $p\in M$ let $t\mapsto \phi_t(p)$ be the path in $M$ such that $\frac{d}{dt}\phi_t(p)=X_t(\phi_t(p))$ and $\phi_0(p)=p.$ In particular, $\phi_t:M\to M$ depends on the vector fields $X_s$ for $s\leq t;$ it is not the time $t$ flow map of the fixed vector field $X_t.$

 

[mathwonk]

9) Thanks for the hint. Dually, the hypotheses seem to imply the 1st homology vector space of Mg has a subspace of dimension n which is totally isotropic for the intersection pairing. But the details are a little elusive. Functoriality of cup product seems to make the analogous fact in cohomology immediate, a nice lesson in the superiority of cohomology over homology, which I was told long ago, but failed to see until now.

 

[Infrared]

@mathwonk I think you have it all there! An isotropic subspace can have dimension at most half the dimension of the total space and since the first cohomology of $M_g$ over a field has dimension $2g$, the result is immediate.

 

[martinbn]

7. Let $S_5$ be the group of permutations on a 5 element set. Let $X=\{(\sigma,\pi)\in S_5\times S_5: \sigma\pi=\pi\sigma\}.$ What is $|X|?$

Denoting by $C(\sigma)$ the centralizer of $\sigma$, we have
$$|X| = \sum_{\sigma} |C(\sigma)|$$
Noticing that conjugate elements have conjugate centralizers, and hence the same number of elements in them, we can group the conjugate elements and have
$$|X| = \sum |Conj(\sigma)| |C(\sigma)|,$$
where the sum is over conjugacy classes.
Using the orbit stabilizer theorem, where the action is conjugation we have that $|Conj(\sigma)| |C(\sigma)|=|G|$, so
$$|X| = \sum |G|,$$
where the sum is still over conjugacy classes. Since there are seven cojugacy classes and $|G|=120$, we get $|X|=7\times120 =840$.

 

[mathwonk]

9) even seems to prove the purely group theoretic fact that a group surjection from the fundamental group of the genus g surface to the free group on n generators is only possible for n ≤ g. I.e. such a surjection has a group theoretic right inverse since a free group is, well, free, and then using the representation of the surface as obtained by attaching a cell to a wedge of g circles, one gets a trio of maps as in the problem.

I was at first going at it from the algebraic perspective, showing e.g that one cannot map the surface group of genus 2 onto the free group on 3 generators in a way that sends A1, B1, and A2 to the three free generators, because the relation in the surface group would, I believe, force then A1B1 and B1A1 to go to the same element of the free group.

From a topological perspective, if the map from the surface to the wedge is smooth in some sense, then the inverse image of n regular values chosen on each of the circles, would give a disjoint collection of n one- manifolds whose homology classes would span a totally isotropic subspace. If moreover the homotopy right inverse were actually a right inverse, then the intersection relations between the image in the surface of the circles, with these 1 manifolds, would show the 1 manifolds are independent, but these details were hard to nail down completely. I also got this idea from a web search that felt a bit too close to searching this or closely related problems.

interesting problem! I learned a lot.

 

[mathwonk]

What is also interesting to me is the duality one must use. I had assumed that the subspace in homology spanned by the images of the wedge of circles must be totally isotropic in the homology space of the surface, but this is not true. I.e. if the map from the surface to the wedge is a retraction onto a wedge of circles in the surface, one going once around each handle, then these circles do span a totally isotropic subspace in H_1. Call these generators A1,...,Ag. But these Aj do not need to be the images of the map induced by the homotopy right inverse. I.e. Aj in the wedge does not need to map to Aj in the surface.
I.e. the elements "dual" to these for intersection, i.e. the elements B1,...,Bg, which also span a totally isotropic subspace in homology, (but with Aj.Bj = 1, and Aj.Bk = 0 when j≠k), map to the identity element under the map from the fundamental group of the surface to that of the wedge. So we can choose the right inverse of this map to take A1 back to say A1+B1, since B1 is in the kernel. Then the corresponding homotopy right inverse of the retraction, also takes A1 to A1+B1 in homology, and then the image of the homology of the wedge of circles does not span a totally isotropic subspace of the homology of the surface. (Forgive me for confusing whether the Aj, Bj are elements of homotopy or homology.)

Thus it is the pullback of the operators on homology that are our totally isotropic subspace of cohomology. I.e. those cohomology elements of the wedge that are dual to the homology generators Aj, pull back, under retraction*, to cohomology elements of the surface that again are dual to the homology elements Aj. This means they correspond to intersection with the elements Bj, and it is these elements Bj, which are represented in homology by fibers of the retraction, that span a totally isotropic subspace of H_1 of the surface.

Interestingly these arguments show that the induced map on homology from the surface to the wedge of circles, has kernel of dimension at least as great as the target. This already solves the problem. I.e. we don't need the concept of totally isotropic subspaces if we can prove this independently. It follows of course from the assertion that the fibers over n regular points, one on each circle of the wedge, represent independent homology cycles. hence a smooth map from the surface to the wedge of n circles, which has a right inverse, induces a surjective map on 1st homology whose kernel has dimension at least n dimensional. Thus the first homology of the surface has dimension at least of dimension 2n, hence 2n ≤ 2g.

I realize these answers are sketched, and I am happy to give more details if anyone wants them.