Challenge 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.

 

[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, <br /> f : \mathbb{R} \to \mathbb{R} : x \mapsto \begin{cases} 1 &amp; x \in \mathbb{Q} \\ 0 &amp; 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?