Math Challenge - June 2023

[Infrared]

Welcome to the reinstatement of the monthly math challenge threads!

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. Have fun!

1. (solved by @Throwaway_for_June ) Given a rectangle and a triangle in the plane, describe how to construct a line that cuts both in half by area using a compass and straightedge. [Edit: This is a lot more annoying than I intended. Feel free to ignore this problem, but if you do solve of course post it!]

2. (Main problem solved by @fresh_42 and @mathwonk . Counterexample given by @pasmith ) For a function $f:\mathbb{R}\to\mathbb{R}$ define $P(f)=\{T\in\mathbb{R}: f(x+T)=f(x) \text{ for all } x\in\mathbb{R}\}$. Note that $f$ is periodic if and only if $P(f)$ contains a nonzero element. If $f$ is continuous and not constant, show that $P(f)=\{nT:n\in\mathbb{Z}\}$ for some real number $T.$ Give a counterexample when $f$ is not continuous.

3. (solved by @julian) Show that $\sqrt{5}+\sqrt[3]{7}+\sqrt[5]{3}$ is irrational.

4. (solved by @projective) Suppose that $G$ is a group of order $63$ with normal subgroups of order $7$ and $9$. Show that $G$ is abelian.

5. (solved by @martinbn) Let $\zeta=e^{2\pi i/n}=\cos(2\pi/n)+i\sin(2\pi/n).$ Evaluate the product $(1-\zeta)(1-\zeta^2)...(1-\zeta^{n-1}).$

6. (solved by @PeroK) A rook starts on the square a1 on an otherwise empty chessboard. Every turn, the rook makes a legal move uniformly at random. What is the expected number of turns it will take it for it to reach the opposite corner h8? Staying on the same square does not count as a turn.

7. (solved by @fresh_42) Let $GL_n^+(\mathbb{R})$ be the set of invertible $n\times n$ real matrices with positive determinant. Suppose that $A$ and $B$ are elements of $GL_n^+(\mathbb{R})$ and similar in the sense that $A=PBP^{-1}$ for some $P\in GL_n(\mathbb{R})$. Can you necessarily find a matrix $Q\in GL_n^+(\mathbb{R})$ such that $A=QBQ^{-1}?$ In other words, if two matrices in $GL_n^+(\mathbb{R})$ are conjugate as elements of $GL_n(\mathbb{R})$, are they also conjugate as elements of $GL_n^+(\mathbb{R})?$

8. (solved by @nuuskur) Let $\mathcal{F}$ be a collection of subsets of $\mathbb{N}$ which is totally ordered by inclusion, i.e. for any $A,B\in\mathcal{F}$, either $A\subseteq B$ or $B\subseteq A.$ Is it possible for $\mathcal{F}$ to be uncountable?

9. (solved by @mathwonk) Identify $S^3$ with $\{(z,w)\in\mathbb{C}^2: |z|^2+|w|^2=1\}.$ Consider the projection map $\pi:S^3\to\mathbb{C}P^1, \pi(z,w)=[z:w]$. This is called the Hopf map. Compute explicitly the preimages of $[1:0]$ and $[0:1]$ as subsets of $S^3$ and verify that they are linked circles.

10. (solved by @mathwonk) Suppose $A$ and $B$ are disjoint (thanks @mfb !) subsets of $[0,1]^2$ such that $(0,0)$ and $(1,1)$ are elements of $A$ and $(0,1)$ and $(1,0)$ are elements of $B.$ Which of the following are possible?

1) $A$ and $B$ are both connected.

2) $A$ and $B$ are both path-connected.

3) $A$ is path-connected and $B$ is connected.[/COLOR]

 

[DeBangis21]

Yes! Let us launch the ball rolling, our mathematicians, physicists, and co.

 

[BWV]

6) (fixed mistake)

Spoiler

at any position in the board, a rook has 14 squares it can legally reach

cannot reach H8 on turn 1.
with each turn after the first the odds of not getting H8 are
6/7 (not in H or 8 so cant reach)
+
(1/7)(13/14) (in H or 8 but dont reach H8)
=97/98

Solving for (1-97/98)=0.5 gives 194 moves, add one move for the first so

195 moves

 

[mfb]

Is 10 missing a condition that $A \cap B = \emptyset$?

@BWV: That can't be right.

Spoiler

Due to symmetry, there are 49 equivalent fields. You expect all of them to be reached in an average of 6.25 moves?

Where do you get that 6/7 chance from? After the first move: Sure. But later? Check the 1/7, too.

 

[BWV]

Is 10 missing a condition that $A \cap B = \emptyset$?

@BWV: That can't be right.

Spoiler

Due to symmetry, there are 49 equivalent fields.

Spoiler

I think the 6/7 is right but the 1/7 part was wrong, updated my answer above

 

[martinbn]

5. Let $\zeta=e^{2\pi i/n}=\cos(2\pi/n)+i\sin(2\pi/n).$ Evaluate the product $(1-\zeta)(1-\zeta^2)...(1-\zeta^{n-1}).$

$(x-1)(x-\zeta)(x-\zeta^2)\dots(x-\zeta^{n-1})$ is a polynomial of degree $n$ and has roots all the $n$-th roots of unity, so it is equal to $x^n-1$. Then

$(x-\zeta)(x-\zeta^2)\dots(x-\zeta^{n-1})=\frac{x^n-1}{x-1}=1+x+\cdots+x^{n-1}$, then

$(1-\zeta)(1-\zeta^2)\dots(1-\zeta^{n-1})=1+1+\cdots+1^{n-1}=n$.

 

[malawi_glenn]

@martinbn you beat me to it. Isn't it a problem to have x=1 in that (x^n-1)/(x-1) step though

 

[Infrared]

@BWV That doesn't look right to me. I agree that the probability of not reaching h8 next is 1 when you're not on h or 8 and that the probability of not reaching h8 next is 13/14 when you are, but I don't agree that there is a $6/7$ probability you're neither on the h file nor 8th rank at some random point in the future.

I'm also don't understand exactly what you're equating to $1/2$ and why it would give an expected value.

Edit: I think you meant to write $1-(97/98)^n=1/2$ (you forgot to write the exponent). This would be how to solve the the median number of moves (half of the time it will take longer, half of the time it will take shorter), but that's not the same thing as expected value.

Edit2: One other subtle error. Even if the probability of not getting to h8 next move is $p$, these are not independent events, so you can't multiply them like this. If I'm on the h file, then I'm more likely to be on the h file next turn.

 

[Infrared]

$(x-1)(x-\zeta)(x-\zeta^2)\dots(x-\zeta^{n-1})$ is a polynomial of degree $n$ and has roots all the $n$-th roots of unity, so it is equal to $x^n-1$. Then

$(x-\zeta)(x-\zeta^2)\dots(x-\zeta^{n-1})=\frac{x^n-1}{x-1}=1+x+\cdots+x^{n-1}$, then

$(1-\zeta)(1-\zeta^2)\dots(1-\zeta^{n-1})=1+1+\cdots+1^{n-1}=n$.

Yep, this is totally correct! One very tiny nitpick is that your polynomial being monic is the reason why you can equate it to $x^n-1$ and not some multiple of it.

 

[Infrared]

@martinbnIsn't it a problem to have x=1 in that (x^n-1)/(x-1) step though

If you have two continuous functions which are equal everywhere except at $x=1$, they're also equal at $x=1$ :)

 

[malawi_glenn]

If you have two continuous functions which are equal everywhere except at $x=1$, they're also equal at $x=1$ :)

Yeah that is true, I had some doubt in my own work regarding this problem. Will move on to number 4 now...

 

[martinbn]

@martinbn you beat me to it. Isn't it a problem to have x=1 in that (x^n-1)/(x-1) step though

I am not using that. This is the middle term in the two equalities. Just equate the most left and the most right and plug in that.

 

[julian]

L'Hôpital's rule states that for functions $f$ and $g$ which are differentiable on an open interval $I$ except possibly at a point $c$ contained in $I$, if $\lim_{x \rightarrow c} f (x) = \lim_{x \rightarrow c} g (x) = 0$ or $\pm \infty$, and $g' (x) \not= 0$ for all $x \in I$ with $x \not= c$, and $\lim_{x \rightarrow c} \dfrac{f' (x)}{g'(x)}$ exists, then

\begin{align*}
\lim_{x \rightarrow c} \dfrac{f(x)}{g(x)} = \lim_{x \rightarrow c} \dfrac{f'(x)}{g'(x)} .
\end{align*}

The differentiation of the numerator and denominator often simplifies the quotient or converts it to a limit that can be evaluated directly.

Using this,

\begin{align*}
\lim_{x \rightarrow 1} \dfrac{x^n-1}{x-1} = \lim_{x \rightarrow 1} \dfrac{n x^{n-1}}{1} = n .
\end{align*}

 

[dextercioby]

You don't need L'Hôpital, you can just factor (x-1) in the numerator.

 

[julian]

You don't need L'Hôpital, you can just factor (x-1) in the numerator.

I was adding to the discussion of posts #7 and #10.

 

[dextercioby]

I understand, I've just told you that bringing l'Hôpital's rule into evaluation of that limit is overkill, i.e. not necessary. You can simply evaluate the limit by factoring the denominator into the numerator.

 

[julian]

@Infrared Sticking to tradition it is "5. (solved by @martinbn ) Let $\zeta = e^{2 \pi i /n} =\cdots$ ".

 

[malawi_glenn]

Perhaps its just me who is bothered with $\frac{x^n-1}{x-1}$ (not defined for $x=1$) and then evaulating something at $x=1$ because I always nag about this with my students xD

$p(x) = (x-\zeta)(x-\zeta^2)\cdots (x-\zeta^{n-1})(x-\zeta^n) = (x-\zeta)(x-\zeta^2)\cdots (x-\zeta^{n-1})(x-1) = x^n-1$ because the polynomial has all roots of unity and has leading coefficnet equal to 1.
Since 1 is a root to $x^n-1$ we can factor out $x-1$ which yields $x^n-1 = (x-1)(x^{n-1} + \ldots + x + 1)$. This is true because $(x-1)(x^{n-1} +x^{n-2} + \ldots + x + 1) = x^n +x^{n-1} + \ldots + x^2 + x - (x^{n-1} +x^{n-2} + \ldots + x + 1) = x^n - 1$.
Now, since we have a polynomial equation $p(x) = (x-\zeta)(x-\zeta^2)\cdots (x-\zeta^{n-1})(x-1) = x^n-1 = (x-1)(x^{n-1} +x^{n-2} + \ldots + x + 1) = (x-1)q(x)$ we must have $q(x) = (x-\zeta)(x-\zeta^2)\cdots (x-\zeta^{n-1}) = x^{n-1} +x^{n-2} + \ldots + x + 1$.
We can evaulate $q(1) = (1-\zeta)(1-\zeta^2)\cdots (1-\zeta^{n-1}) = 1^{n-1} +1^{n-2} + \ldots + 1 + 1 = n .$

 

[martinbn]

@malawi_glenn
This

$(x-\zeta)(x-\zeta^2)\dots(x-\zeta^{n-1})=\frac{x^n-1}{x-1}=1+x+\cdots+x^{n-1}$

contains this

$(x-\zeta)(x-\zeta^2)\dots(x-\zeta^{n-1})=1+x+\cdots+x^{n-1}$

Now, plug in.

 

[malawi_glenn]

My problem is division with something that is potentially equal to zero.

 

[Infrared]

My problem is division with something that is potentially equal to zero.

If you agree that $1+x+\ldots+x^{n-1}=(x-\zeta)\ldots(x-\zeta^{n-1})$ for all $x\neq 1$, then they must also be equal at $x=1$ since both sides are continuous (see my post 10)

Alternatively, you can just check that $\zeta^k$ for $1\leq k<n$ is a root of the lefthand side using the identity $(1-x^n)/(1-x)=1+x+\ldots+x^{n-1}$ for $x\neq 1$ and hence it must factor like this.

 

[malawi_glenn]

If you agree that $1+x+\ldots+x^{n-1}=(x-\zeta)\ldots(x-\zeta^{n-1})$ for all $x\neq 1$, then they must also be equal at $x=1$ since both sides are continuous (see my post 10)

Alternatively, you can just check that $\zeta^k$ for $1\leq k<n$ is a root of the lefthand side using the identity $(1-x^n)/(1-x)=1+x+\ldots+x^{n-1}$ for $x\neq 1$ and hence it must factor like this.

I know, but as mentioned, I always nag about this with ny students. I tell them to factorize instead of dividing

 

[PeroK]

Solution for number 6. I'm only no my phone, so typing a lot is difficult.

The rook needs to get to either row 8 or column h, then hit h8 from there. The probability of getting to either row 8 or column h is the same from any other square. And the probability of hitting h8 is the same from any square on either row 8 or column h.

The upshot is that there are only two expected values: $E(x)$ is the expected value from a1 ( or any square not on row 8 or column h) and $E(1)$ is the expected value from column 8 or row h.

We can use the recursive relations:
$$E(x)= 1 + \frac 6 7 E(x) + \frac 1 7 E(1)$$To give$$E(x) = 7 + E(1)$$Which also makes sense binomially! And
$$E(1) = \frac 1 {14} + 1 + \frac 3 7 E(1) + \frac 1 2 E(x)$$To give$$8E(1) = 15 + 7E(x)$$Solving these gives$$E(x) = 71, \ E(1) = 64$$PS in general, for an $n \times n$ board, we have$$E(1) = n^2, E(x) = n^2 +n -1$$

 

[Infrared]

@PeroK Very nice! Just one small error: In your expression $E(1)=1+\frac{1}{14}+\frac{3}{7}E(1)+\frac{1}{2}E(x),$ the last three terms should be the weighted expected value of moves to get to h8 after making the current move (since you already added the $+1$), which means that the $\frac{1}{14}$ should be multiplying $0$, not $1.$ Deleting the $\frac{1}{14}$ from this equation makes your solution $(E(x),E(1))=(70,63)$ instead of $(71,64).$

 

[PeroK]

Something about that $\frac 1 {14}$ didn't feel right! But, I couldn't see what.

 

[PeroK]

My friend, who is non-mathematical, said that the 64 (or 63) couldn't be a coincidence.

The rook will land on each square equally often, hence the expected number of moves to get back to its starting square is 64. After one move, when it is on the correct row or column, it must take an expected 63 moves to get back from there. That's $E(1)$!

PS that would have been an insightful opening gambit!

 

[pasmith]

(2): For the noncontinuous case, $$f : \mathbb{R} \to \mathbb{R} : x \mapsto \begin{cases} 1 & x \in \mathbb{Q} \\ 0 & x \notin \mathbb{Q} \end{cases}$$ has $P(f) \supset \mathbb{Q}$ by closure of $\mathbb{Q}$ under addition. If $t \notin \mathbb{Q}$ then $$f(-t +t) = f(0) = 1 \neq 0 = f(-t)$$ and $t \notin P(f)$. Hence $P(f) = \mathbb{Q}$ which is not of the form $T\mathbb{Z}$ for any $T \in \mathbb{R}$.

 

[mathwonk]

hint/warning for #1: It seems that a line bisects a rectangle by area iff it passes through the centroid, but this is not true for triangles. Apparently the lines bisecting a general triangle form an "envelope". So it seems you have to discern which line through the centroid of the rectangle also belongs to this envelope. ?? interesting problem. I woud guess you have a chance iff this envelope is defined by (lines tangent to) arcs of circles.

 

[Infrared]

hint/warning for #1: It seems that a line bisects a rectangle by area iff it passes through the centroid, but this is not true for triangles. Apparently the lines bisecting a general triangle form an "envelope". So it seems you have to discern which line through the centroid of the rectangle also belongs to this envelope. ?? interesting problem.

Yes, I intended for it to be easy problem and to just connect the two centroids and realized my blunder afterwards. I'm pretty sure it should still be possible because if you work it out in coordinates, you only need to adjoin a square root to solve for the equation of the line, but this definitely isn't what I had in mind at first. Hopefully the rest of the problems should be free from glitches!

 

[julian]

#3: We have that $\alpha = \sqrt{5} + 7^{1/3} + 3^{1/5}$ is a algebraic number being the root of a monic polynomial with integer coefficients:

https://www.wolframalpha.com/input?i=minimal+polynomial+5^{1/2}+++7^(1/3)+3^(1/5)

Where $a_0 \not= 0$. By the rational root theorem, if $\alpha = p/q$ where $p$ and $q$ are coprime integers, we must have $q$ divides $1$ and $p$ divides $a_0$. In other words, $\alpha$ must be an integer that divides $a_0$. However, from putting $\sqrt{5}+ 7^{1/3} + 3^{1/5}$ into a calculator it is obviously not an integer. Hence, it is irrational. You are allowed to use wolfram alpha and a calculator?

 

[Infrared]

I would prefer that you do it by hand :)

With that being said, do you see an easy to way to check that $\sqrt{5}+\sqrt[3]{7}+\sqrt[5]{3}$ is an algebraic integer (I think you mean this as opposed to algebraic number, which just means that it is a root of an integer, not necessarily monic, polynomial) without explicitly writing down its minimal polynomial?

 

[julian]

The sum of algebraic integers is an algebraic integer and each of $\sqrt{5}$, $\sqrt[3]{7}$, and $\sqrt[5]{3}$ are algebraic integers. Do I need to use that theorem? Or is there another way?

It is getting quite late here. Tomorrow!

 

[Infrared]

That theorem should be fair game to use and I trust that you can do the arithmetic to verify that $\sqrt{5}+\sqrt[3]{7}+\sqrt[5]{3}$ is not an integer, so I'll count it as solved.

I'll share the solution I had in mind. If the sum is rational, then $\sqrt{5}\in\mathbb{Q}(\sqrt[3]{7},\sqrt[5]{3}).$ The field on the righthand side contains $\mathbb{Q}(\sqrt[3]{7})$ and $\mathbb{Q}(\sqrt[5]{3})$ as subfields so its degree over $\mathbb{Q}$ is a multiple of both 3 and 5, hence a multiple of 15. Also, its degree over $\mathbb{Q}$ is at most 15 because in general $[K(\alpha,\beta):K]=[K(\alpha,\beta):K(\alpha)]\cdot [K(\alpha):K]\leq [K(\beta):K]\cdot [K(\alpha):K].$ So $[\mathbb{Q}(\sqrt[3]{7},\sqrt[5]{3}):\mathbb{Q}]=15$ and it cannot have a degree 2 element like $\sqrt{5}.$

One interesting thing to note is that our methods are good for different generalizations of the original problem. If I instead asked to prove that the numbers $\sqrt{5},\sqrt[3]{7},\sqrt[5]{3}$ are rationally independent, then your method seems quite difficult to use since after clearing denominators you would have to explain why no integer combination of these numbers could be an integer, which doesn't simplify the problem.

Instead, if some of the degrees of the roots were not coprime, then my method could fail because the degree of the composite field might not be the product of degrees of the base fields (you could get a new prime factor in the degree!) and also last sentence could fail to be a contradiction if there was the needed divisibility.

 

[julian]

Now I'm more awake, I can look into it and find that the theorem isn't difficult to prove. It is easy to establish that:

\begin{align*}
& 2.2 < \sqrt{5} < 2.3
\nonumber \\
& 1.9 < \sqrt[3]{7} < 2
\nonumber \\
& 1.2 < \sqrt[5]{3} < 1.3
\nonumber \\
\end{align*}

So that

\begin{align*}
5.3 < \sqrt{5} + \sqrt[3]{7} + \sqrt[5]{3} < 5.6
\end{align*}

 

[fresh_42]

@Infrared I have a question regarding problem #2. It looks as if you expected to use the intermediate value theorem. I think a minimality argument is sufficient, but I may have overlooked something in my proof:

Set $$P(f;T):=\left\{nT\,|\,n\in \mathbb{Z}\right\}\quad \text{ for some } T\in \mathbb{R}$$
Since $0\in P(f)$ in any case, we have $P(f)=\{0\}=P(f;0)$ for non-periodic functions $f.$ We may therefore assume that $f$ is periodic and $T_0$ the minimal, positive, non-zero element of $P(f).$

Edit: If no such minimal period $T$ existed, and $\{0\}\subsetneq P(f)$ then we had a sequence $(T_n)_{n\in \mathbb{N}}$ with $\lim_{n \to \infty}T_n=0.$ In every neighborhood of $x$ was an element $|T_n|<\varepsilon$ such that $f(x)=f(x+T_n)$. As $f$ is continuous, $f(x)$ was constant for all $|x|<\varepsilon,$ i.e. on an interval of positive length. Therefore, $f(x)$ would be constant everywhere, i.e. $T=0$ and $P(f)=\{0\}.$

Or: The sets $A(x_0)=\{x_0\}+\{T\in P(f)\,|\,f(x_0)=f(x_0+T)\}$ are closed by the continuity of $f.$ If no minimal $T_0$ existed at some point $x_0$ then we could construct a zero-sequence $(T_n)$ such that $x_0\not\in A(x_0)$ which contradicts closeness.

If such an element was negative then (by using the for-all-quantifier in the definition of $P(f)$)
\begin{align*}
f(x+|T_0|)=f((x+|T_0|)+T_0)=f((x+|T_0|)-|T_0|)=f(x)
\end{align*}
and we can choose $|T_0|$ instead. By the same argument, we will find per induction in both directions that $P(f;T_0)\subseteq P(f).$ Now assume $0\neq T\in P(f).$ Then we have to show that $T=nT_0$ for some $n\in \mathbb{Z}.$ We assume that $T>T_0$, since there is nothing to show for $T=T_0$ and negative values, can be turned into positive by the above argument. Let $T\in [\,nT_0,(n+1)T_0\,).$ Then
$$
f(x+(T-nT_0))=f((x-nT_0)+T)\stackrel{T\in P(f)}{=}f(x-nT_0)\stackrel{P(f;T_0)\subseteq P(f)}{=}f(x)
$$
contradicting the minimality of $T_0$ since
$$
T-nT_0 < (n+1)T_0-nT_0=T_0.
$$
except $T-nT_0=0.$

I may have overlooked something, which leads me to my question: What do you mean by counterexample? The function
$$
f(x)=\begin{cases}|\sin(x)|&\text{ if }x\not \in \mathbb{Z}\pi \\ -2 &\text{ if }x \in \mathbb{Z}\pi\end{cases}
$$
is still periodic with $P(f)=P(f;\pi)$ but not continuous anymore.