Challenge Math Challenge - February 2020

[pbuk]

View attachment 256406

High Schoolers only

11. Answer the following questions:
a.) How many knights can you place on a $n\times m$ chessboard such that no two attack each other?

That is a good high school question.

b.) In how many different ways can eight queens be placed on a chessboard, such that no queen threatens another? Two solutions are not different, if they can be achieved by a rotation or by mirroring of the board.

Surely this one is a bit too hard though?

 

[fresh_42]

Surely this one is a bit too hard though?

Yes. It's an experiment. I will accept a correct answer, without proof.

 

[Antarres]

Just an edit, now that enough time has passed so I can't edit the original post.

Spoiler: Question #4 - edit

If $f$ has a limit at infinity, this uniform continuity of the sequence coincides with this limit, so we see that uniform continuity of $f_n$ implies that $g$ is constant and equal to limit of f$f$ at infinity at all points.

Here it's supposed to be 'uniform convergence' of the sequence, not continuity of its functions..

 

[Infrared]

If $f$ has a limit at infinity
$\cdots$
Hence $f$ is uniformly continuous on the whole domain.

This part of the argument is OK but it's probably easier to use overlapping intervals like $[0,2N]$ and $[N,\infty)$ so that you don't have to worry about the case that $x$ and $y$ belong to differenti intervals.

However, I think you're handwaving a bit in the case where there isn't a limit at infinity. In particular, the following seems to be false:

Same goes if the function was oscillating, but not being periodic(like for example $\sin(x^2)$).

The function $f(x)=\sin(2\pi x)+e^{-x}$ is not periodic, but $f_n(x)=\sin(2\pi x)+e^{-(n+x)}$ converges uniformly to $\sin(2\pi x)$.

 

[Antarres]

Thanks for the remark, now that I reread what I wrote, I notice it sounds a bit handwavy. I should've refined it a bit before posting. So, I will revisit the case where no limit exists here, assuming the case with finite limit to be established(and what you mentioned about intervals makes it easier indeed, I was a bit hasty when I wrote this, so I didn't ponder on it much, thanks for that remark).

Spoiler: Question #4 - no limit case

In case where $f(x)$ has no limit as $x$ approaches infinity, it can either increase/decrease without bound or oscillate. The case of divergent increase/decrease, we have disbanded since that would violate the condition that $f(x+n)$ converges uniformly as $n \rightarrow \infty$. The oscillation case remains.First we observe that, if $f(x)$ is periodic with period $\frac{1}{k}$, $k \in \mathbb{N}$, then for every $n \in \mathbb{N}$, $f(x+n)=f(x)$, because $n$ is an integer multiple of the period. Hence the sequence $f_n(x)$ is constant for fixed $x$, so it converges uniformly to $g(x)=f(x)$. Since we assume $f(x)$ is well defined and continuous on its domain, we have that, since it is continuous on a closed interval $[0,T]$, it is uniformly continuous on that interval. Then by periodicity and continuity, it is uniformly continuous on the whole domain. So both $f$ and $g$ are uniformly continuous.The idea of why we picked specific forms for function $f(x)$ in the two cases we considered before, is to narrow down possible representations of $g(x)$. Namely, if $f$ is oscillating, then the sequence $f_n(x)=f(x+n)$ is surely oscillating with the change of both $x$ and $n$, behaving the same way $f$ does. By maintaining that $n$ is an integer multiple of the period of $f$, we obtain uniform convergence, because we're making the sequence constant with $n$, but if we allow $f_n$ to oscillate with $n$, we won't have any function that it would converge to, because we can't suppress its oscillation at infinity otherwise, since it is governed by the behavior of $f$ which is preset. Therefore, we conclude that the general form of $g(x)$ must be a combination of the cases we found above.

So the general form of $g(x)$ which is asymptotic form of $f(x)$ at infinity, is $g(x)=ap(x)+b$, where $a$ and $b$ are constants, and $p$ is a function whose period is of form $T=\frac{1}{k}$ for some natural number $k$. This form is uniformly continuous by what we have proven before, when we considered periodic case of $f(x)$.

As it is the limit of $f(x)$ at infinity, the form of $f(x)$ would in general be
$$f(x)=s(x)p(x)+t(x)$$
where $s$ and $t$ are continuous functions with the same domain as $f$, who have finite limits as $x \rightarrow \infty$, and $p$ is a periodic continuous function with period $T=\frac{1}{k}$ for some natural number $k$. By the two cases we considered before, all three of these functions are uniformly continuous, hence their combination obtained via addition and multiplication is also uniformly continuous(this is a well known property of uniform continuity).

This concludes our proof, we don't have any possible malfunctioning cases now, I believe.

 

[etotheipi]

12. Determine (with justification, but without explicit calculation) which of
a.) $1000^{1001}$ and ${1002}^{1000}$
b.) $e^{0.000009}-e^{0.000007}+e^{0.000002}-e^{0.000001}$ and $e^{0.000008}-e^{0.000005}$
is larger.

Spoiler: Problem 12 - Part b)

I haven't completed part a), however for part b),

Let $u = e^{0.000001}$ such that

$A = e^{0.000009}-e^{0.000007}+e^{0.000002}-e^{0.000001} = u^{9} - u^{7} + u^{2} - u$
$B = e^{0.000008}-e^{0.000005} = u^{8} - u^{5}$

Now considering $A - B$,
$A - B = u^9 - u^8 - u^7 + u^5 + u^2 - u = u(u+1)(u-1)^{2}(u^5 - u^2-1)$

Since $u$, $u+1$ and $(u-1)^{2}$ are all positive, we just need to work out the sign of the final term.

$(u^5 - u^2 -1) = u^2(u^3-1) -1$

Since $u = e^{0.000001}$ is only a little greater than 1, $(u^3-1)$ is going to be very close to 0+, then on multiplication by $u^{2}$ - which is also very close to 1 - and finally subtraction of the one, this term will become negative. And a negative $A-B$ implies the second sum is larger than the first.

 

[Pi-is-3]

Spoiler: Problem 12 - Part b)

I haven't completed part a), however for part b),

Let $u = e^{0.000001}$ such that

$A = e^{0.000009}-e^{0.000007}+e^{0.000002}-e^{0.000001} = u^{9} - u^{7} + u^{2} - u$
$B = e^{0.000008}-e^{0.000005} = u^{8} - u^{5}$

Now considering $A - B$,
$A - B = u^9 - u^8 - u^7 + u^5 + u^2 - u = u(u+1)(u-1)^{2}(u^5 - u^2-1)$

Since $u$, $u+1$ and $(u-1)^{2}$ are all positive, we just need to work out the sign of the final term.

$(u^5 - u^2 -1) = u^2(u^3-1) -1$

Since $u = e^{0.000001}$ is only a little greater than 1, $(u^3-1)$ is going to be very close to 0+, then on multiplication by $u^{2}$ - which is also very close to 1 - and finally subtraction of the one, this term will become negative. And a negative $A-B$ implies the second sum is larger than the first.

So much better than what I was going to post. I just expanded $e^x$ upto first 3 terms to get the second greater than first.

 

[etotheipi]

So much better than what I was going to post. I just expanded #e^x# upto first 3 terms to get the second greater than first.

That sounds as though it could be a good solution as well though!

 

[fresh_42]

Spoiler: Problem 12 - Part b)

I haven't completed part a), however for part b),

Let $u = e^{0.000001}$ such that

$A = e^{0.000009}-e^{0.000007}+e^{0.000002}-e^{0.000001} = u^{9} - u^{7} + u^{2} - u$
$B = e^{0.000008}-e^{0.000005} = u^{8} - u^{5}$

Now considering $A - B$,
$A - B = u^9 - u^8 - u^7 + u^5 + u^2 - u = u(u+1)(u-1)^{2}(u^5 - u^2-1)$

Since $u$, $u+1$ and $(u-1)^{2}$ are all positive, we just need to work out the sign of the final term.

$(u^5 - u^2 -1) = u^2(u^3-1) -1$

Since $u = e^{0.000001}$ is only a little greater than 1, $(u^3-1)$ is going to be very close to 0+, then on multiplication by $u^{2}$ - which is also very close to 1 - and finally subtraction of the one, this term will become negative. And a negative $A-B$ implies the second sum is larger than the first.

A bit more formalism than "little greater than"
$1<u<u^2<u^5 =e^{0.000005} < 4^{0.000005}< 4^{0.5}=2$
would have been nice, but your solution is correct.

 

[fresh_42]

I have solved part (a). I will post the answer in text form when I solve both parts. Untill then I have numbered all the equations.
-----

Spoiler: Problem 11(a)

View attachment 256655
I have taken m as vertical and n as horizontal, it doesn't matter as both will change on rotating the board.
The language of question is quite complex. If the question wants maximum value of knights tgen it will always be in second case(Case 1 will match values if m is in the form of (3x +1)) except when m is 1.

This is close, but for $n=6=3k$ and $m=3$ you have $6$ knights, but $9$ are possible.

It is better to distinguish the cases $m=1,m=2,m>2$.

 

[mmaismma]

This is close, but for $n=6=3k$ and $m=3$ you have $6$ knights, but $9$ are possible.

It is better to distinguish the cases $m=1,m=2,m>2$.

In my answer I have already told that required number is always maximum in case 2 except for $m=1$ which will give $9$ for the given case. However if you want me to distinguish the cases as $m=1,m=2,m>2$, here it is.

Spoiler: Problem 11(a)

 

[Pi-is-3]

In my answer I have already told that required number is always maximum in case 2 except for $m=1$ which will give $9$ for the given case. However if you want me to distinguish the cases as $m=1,m=2,m>2$, here it is.

Spoiler: Problem 11(a)

View attachment 256790

You can simplify the formulas of n=odd.

For n and m both odd the formula can be simplified to $\frac{mn+1}{2}$ .
For n odd, m even, the formula can be simplified to $\frac{mn}{2}$ .

This way both the cases of n feel interconnected.

 

[Not anonymous]

12. Determine (with justification, but without explicit calculation) which of
a.) $1000^{1001}$ and ${1002}^{1000}$
is larger.
b.) $e^{0.000009}−e^{0.000007}+e^{0.000002}−e^{0.000001}$ and $e^{0.000008}−e^{0.000005}$
is larger.

I am not entirely sure if this is an acceptable solution. This solution relies on knowing that $2 \lt e \lt 3$ and derives some bounds based on powers or logarithms based on that. In that sense, it is not free from calculation, though it does not rely on any further explicit calculation. I guess the ideal solution would use some standard identities that I am unaware of.

Spoiler: 12

a.) Define $f(x) = x ^ {\frac {3002-x} {2}}$ and $g(x) = \log f(x) = \dfrac {3002-x} {2} \log x$
It is easy to see that ${1000}^{1001} = f(1000)$ and ${1002}^{1000} = f(1002)$

Since logarithm is a monotonically increasing function, proving that $\log a \gt \log b$ is equivalent to proving that $a \gt b$ provided logarithm is well-defined for those values.

$g'(x) = \dfrac {3002-x} {2x} - \dfrac {\log x} {2} = \ \dfrac {1501} {x} - \dfrac {1 + \log x} {2}$

For $x \geq 1000, g'(x) \leq (1.501 - \dfrac {1 + \log 1000} {2}) \lt 1.501 - 2.5 \Rightarrow x \lt 0$, where I use the fact that $e \lt 3$. We know that $3^4 = 81 < 1000$. Therefore $3^4 \lt 1000 \Rightarrow e^4 \lt 1000 \Rightarrow \log 1000 \gt 4$ .

Since $g(x)$ has a negative slope for $x \geq 1000$, $g(y) \lt g(1000) \ \forall y \gt 1000$. Hence, $g(1002) \lt g(1000) \Rightarrow f(1002) \lt f(1000) \Rightarrow 1000^{1001} \gt 1002^{1000}$

b.) Let $x = e^{0.000001}$ and let $A, B$ denote the 2 expressions whose values are to be compared. Then $A - B = (e^{0.000009}−e^{0.000007}+e^{0.000002}−e^{0.000001}) - (e^{0.000008}−e^{0.000005})$ is equivalent to $x^9 - x^7 + x^2 - x - x^8 + x^5 = x(x^8 - x^6 + x - 1 - x^7 + x^4) \ = x(x^8 - x^7 - x^6 + x^4 + x - 1) = x(x^7(x-1) - x^4(x^2 - 1) + (x-1)) = x(x-1)(x^7 -x^4(x+1) + 1) \ = x(x-1)(x^7 - x^5 - x^4 + 1) = x(x-1)(x^5(x^2 - 1) - (x^2 + 1)(x^2 - 1)) = x(x-1)(x^2 - 1)(x^5 - (x^2 + 1))$

Since $x > 1$ ($e^a \gt 1 \ \forall a \gt 0$ and by definition $x = e^{0.000001}$), it follows that $x(x-1)(x^2 - 1) \gt 0$. We try to find whether $(x^5 - (x^2 + 1))$ is positive or not, and for this we may compare the logarithms of $x^5$ and $(x^2 + 1)$. Note that in the derivations, by $\log x$ I mean the natural logarithm of $x$.

$\log {x^5} = \log {e^{0.000005}} = 0.000005$

$\log {x^2 + 1} = \log {e^{0.000002} + 1} \gt \log 2$
Since $2 \lt e \lt 3 \lt 4$, $\log 2 \gt \log_{4} 2 = 0.5$
Since $0.5 > 0.000005$, it follows that $\log {x^5} \lt \log {x^2 + 1} \Rightarrow (x^5 - (x^2 + 1)) \lt 0$. Hence the value $x(x-1)(x^2 - 1)(x^5 - (x^2 + 1)) \lt 0$ implying that $A - B \lt 0$ or $A \lt B$.

Therefore $e^{0.000009}−e^{0.000007}+e^{0.000002}−e^{0.000001}$ must be smaller that $e^{0.000008}−e^{0.000005}$

 

[Not anonymous]

Sorry, I missed adding parentheses in one of the steps

Spoiler: Question 12

It was meant to be read as $\log {(x^2+1)} = \log {(e^{0.000002}+1)} > \log 2$. In the earlier post, I missed the brackets around $x^2+1$ and $e^{0.000002}+1$

 

[fresh_42]

In my answer I have already told that required number is always maximum in case 2 except for $m=1$ which will give $9$ for the given case. However if you want me to distinguish the cases as $m=1,m=2,m>2$, here it is.

Spoiler: Problem 11(a)

View attachment 256790

$m=2$ and $n=2$ allows $4\neq n$ knights.

For $n$ and $m$ both odd the formula can be simplified to $\frac{mn+1}{2}$.
For $n$ odd, $m$ even, the formula can be simplified to $\frac{mn}{2}$.

it can be further simplified to $\lceil \dfrac{nm}{2}\rceil$.

Nobody with an idea how to find the correct number for part b)?

 

[mmaismma]

You can simplify the formulas of n=odd.

For n and m both odd the formula can be simplified to $\frac{mn+1}{2}$ .
For n odd, m even, the formula can be simplified to $\frac{mn}{2}$ .

This way both the cases of n feel interconnected.

You are right but I didn't simplify the formula intentionally. Because this way one can easily figure out how I have derived the formulas.

 

[mmaismma]

m=2m=2m=2 and n=2n=2n=2 allows 4≠n4≠n4\neq n knights

Yes you are right. There is an exception for such small boards that I couldn't figure out.

it can be further simplified to ⌈nm2⌉⌈nm2⌉\lceil \dfrac{nm}{2}\rceil.

What is a 'ceil'?

 

[fresh_42]

Yes you are right. There is an exception for such small boards that I couldn't figure out.

You have almost everything right except for $m=2$. The example of a $2\times 2$ board can be generalized to $n\times 2$ boards. The formula is a bit tricky. I suggest to write $n=4k+r\, , \,r=1,2,3,4$.

What is a 'ceil'?

Rounded to the next upper integer.

You are right but I didn't simplify the formula intentionally. Because this way one can easily figure out how I have derived the formulas.

You can give an easy and straight argument if you look at an actual board and observe what a knight move does.

 

[Infrared]

In case where $f(x)$ has no limit as $x$ approaches infinity, it can either increase/decrease without bound or oscillate.

By "increase/decrease without bound" do you mean $\lim_{x\to\infty}|f(x)|=\infty$ or just $\lim\sup_{x\to\infty}|f(x)|=\infty$? What does "oscillate" mean?

First we observe that, if $f(x)$ is periodic with period $\frac{1}{k}$, $k \in \mathbb{N}$, then for every $n \in \mathbb{N}$, $f(x+n)=f(x)$, because $n$ is an integer multiple of the period. Hence the sequence $f_n(x)$ is constant for fixed $x$, so it converges uniformly to $g(x)=f(x)$. Since we assume $f(x)$ is well defined and continuous on its domain, we have that, since it is continuous on a closed interval $[0,T]$, it is uniformly continuous on that interval. Then by periodicity and continuity, it is uniformly continuous on the whole domain. So both $f$ and $g$ are uniformly continuous.

I agree with this (and probably you also mean to allow functions which are eventually periodic).

The idea of why we picked specific forms for function $f(x)$ in the two cases we considered before, is to narrow down possible representations of $g(x)$. Namely, if $f$ is oscillating, then the sequence $f_n(x)=f(x+n)$ is surely oscillating with the change of both $x$ and $n$, behaving the same way $f$ does. By maintaining that $n$ is an integer multiple of the period of $f$, we obtain uniform convergence, because we're making the sequence constant with $n$, but if we allow $f_n$ to oscillate with $n$, we won't have any function that it would converge to, because we can't suppress its oscillation at infinity otherwise, since it is governed by the behavior of $f$ which is preset.

I can't figure out what mathematical claim you are making here. Can you make this precise?

Therefore, we conclude that the general form of $g(x)$ must be a combination of the cases we found above.

Why?

 

[Antarres]

By "increase/decrease without bound" do you mean $\lim_{x\to\infty}|f(x)|=\infty$ or just $\lim\sup_{x\to\infty}|f(x)|=\infty$? What does "oscillate" mean?

Okay, well I mean the first, that $\lim_{x\to\infty} |f(x)| = \infty$. From the way $f_n$ is constructed, we see that its convergence depends on the behavior of $f$ at infinity, and that $g(x)$ is precisely asymptotic form of $f$ at infinity.
So what I meant is, that if we have no limit, that means that either limit is in positive/negative infinity(that's what I meant by increase/decrease without bound), or the number of accumulation points is not equal to one(there's no unique pointt to which the sequence converges for fixed $x$, violating pointwise convergence, and hence uniform convergence as well).

I agree with this (and probably you also mean to allow functions which are eventually periodic).

I indeed do allow that case(in which a function eventually turns to behaving periodic), I commented on it later in the answer, when I obtain the general form of $f$.

I can't figure out what mathematical claim you are making here. Can you make this precise?

What I mean is that behavior of $f_n$, the way its limit approaches as $n\to\infty$, is the same way $f$ behaves as $x\to\infty$, unless we make the sequence independent of $n$. This is a consequence of how we constructed $f_n$ as just being a translation along $x$-axis. So we choose that either $f$ has a finite limit, hence the sequence also has a finite limit, which makes it uniformly converge to a constant(which I addressed in the first answer), or $f$ can be periodic with a specific period that would make $f_n$ independent of $n$. This is the case of periodic function with period $\frac{1}{k}$. Now, this doesn't exhaust the possible behaviors of $f$, but it does exhaust possible behaviors of $f_n$ and hence $g$.

If we, for example, allow $f$ to be periodic with a different period from the form we mentioned, that would make $f_n$ limit undefined, since it would produce more than one accumulation point(which I addressed when I talked about general rational and irrational periods). Even if $f$ is aperiodic, it must be of such behavior that at infinity it becomes a periodic function of period $\frac{1}{k}$, otherwise $f_n$ wouldn't converge even pointwise.

So that's what I meant, these two cases are two possibilities of how $f_n$ would converge, and from there I give the general form of $g$ which is $aP(x) + b$. Every $g$ can be written in this general form, since $P$ is a completely general function of period $\frac{1}{k}$, it just has to be continuous. So I considered specific cases on how $f_n$ converges and then combined them in general way.

From there, I find that then $f$ must be of general form $s(x)P(x)+t(x)$, where $s$ and $t$ converge towards $a$ and $b$ we find in $g$, and $P$ is just a periodic function of period $\frac{1}{k}$, so it doesn't interrupt the convergence of $f_n$.

All other cases can be broken down to these possibilities, the main thing is that we essentially want $f_n$ to have a well defined limit, and then we take all possible combinations of functions that give that. I think it is precise enough now, unless I missed something that is of essential importance. Also when I mention accumulation points, it is an abuse of words, since in terms of uniform convergence those 'points' are functions, while in terms of pointwise converges they are actually points. But it should be clear from the context what I mean in every particular case.

 

[Antarres]

Spoiler: Question #3

a)
By Green's theorem:
$$\oint_C Pdx+Qdy = \int\int \left(\frac{\partial Q}{\partial x}-\frac{\partial P}{\partial y}\right)dxdy$$
we have that if the integrand on the right-hand side is equal to 1, we get the formula for the area. One of the functions for which this is satisfied is $P=0$, $Q=x$. Then we rewrite the theorem:
$$\oint_C xdy = \int\int dxdy = A$$
Now we use the parametrization given in the exercise $dy = y'(t)dt$, so we have:
$$\int_0^{2\pi} x(t)y'(t)dt = A$$
Squaring the relation and using Cauchy-Schwarz in integral form, gives:
$$A^2 = \left(\int_0^{2\pi} x(t)y'(t)dt\right)^2 \leq \int_0^{2\pi} (x(t))^2dt\int_0^{2\pi}(y'(t))^2dt$$
This proves the inequality.
b) Assume we translated the curve so that $\int_0^{2\pi} x(t)dt$. Then Wirtinger's inequality holds.
Before using it, we will observe the property of arc-length parametrization that follows from its definition. Namely:
$$dt = \sqrt{dx^2 + dy^2} = \sqrt{(x'(t))^2 + (y'(t))^2}dt$$
from which we conclude $(x'(t))^2 + (y'(t))^2 = 1$.
Now we apply Wirtinger's inequality to the one we had in a):
$$\int_0^{2\pi} (x(t))^2dt\int_0^{2\pi}(y'(t))^2dt \leq \int_0^{2\pi} (x'(t))^2dt\int_0^{2\pi}(y'(t))^2dt$$
We denote now:
$$I_x = \int_0^{2\pi} (x'(t))^2dt \qquad I_y = \int_0^{2\pi} (y'(t))^2dt$$
We then use the AM-GM inequality, remembering that both of the numbers above are nonnegative:
$$\left(\frac{I_x+I_y}{2}\right)^2 \geq I_xI_y$$
But also, integrating the relation $(x'(t))^2 + (y'(t))^2 = 1$ over $t$, we find:
$$I_x + I_y = 2\pi$$
Then we combine the two expressions above:
$$I_xI_y \leq \pi^2$$
Substituting this into Wirtinger's inequality, we find finally:
$$A^2 \leq \int_0^{2\pi} (x'(t))^2dt\int_0^{2\pi}(y'(t))^2dt \leq \pi^2$$
From here we obtain the relation that's needed by taking square root of both side.
c)
We examine the conditions where Wirtinger inequality turns into equality, and also conditions of equality for AM-GM and Cauchy-Schwarz that we used.
Wirtinger's inequality equality condition:
$$x'(t) = a\sin(x+\phi)$$
for $a$ and $\phi$ constant.
AM-GM inequality equality condition:
$$I_x = I_y$$
Cauchy-Schwarz inequality equality condition:
$$x(t) = cy'(t)$$
for $c$ a constant.
The first condition, along with the condition $(x'(t))^2 + (y'(t))^2 = 1$, gives:
$$|a|=1 \qquad y'(t) = acos(x+\phi)$$
the first condition coming from the fact that $|x(t)|$ has to be less than or equal to 1.
The second condition is then trivial, of form $0=0$.
The third condition gives $x(t) = \int x'(t)dt = -acos(x+\phi) = cy'(t) \Rightarrow c=-1$.
So Wirtinger's equality condition implies other conditions trivially, and this conditions implies the equation of a circle. Hence, $A=\pi$ can only happen if $C$ is a circle.

 

[Infrared]

Even if $f$ is aperiodic, it must be of such behavior that at infinity it becomes a periodic function of period $\frac{1}{k}$, otherwise $f_n$ wouldn't converge even pointwise.

I think this is your key claim that I wasn't able to find a clear proof of in your writing. Could you give a rigorous argument for this? There is a very simple, direct argument that doesn't require any casework.
Also, I didn't see where you used uniform instead of just pointwise convergence.

Your answer to number 3 is good! This is my favorite argument for the isoperimetric inequality, and I thought I had to share :)

 

[Antarres]

Hmm, well I think my case argument was based on classifying cases by how many accumulation points can $f_n$ have, since if it doesn't converge pointwise, it won't converge uniform either. But since I didn't find a way to make it more rigorous, although I didn't find any counterexample to it, I found a simpler $\epsilon-\delta$ type of argument, which is probably much clearer.

Spoiler: Question #4 - $\epsilon-\delta$

Let's see if the continuity of $f$ along with uniform convergence of $f_n$ implies that $f$ is uniformly continuous.
First choose $\epsilon>0$. Then choose $N\in\mathbb{N}$ such that for all $n\geq N$ and all $x$, $|f_n(x)-g(x)|<\frac{\epsilon}{2}$.
Then, we find $\delta$ such that(for $n\geq N$):
$$|x-y| <\delta \Rightarrow |f_n(x)-f_n(y)|=|f_n(x) - g(x)+g(x)-f_n(y)| \leq |f_n(x)-g(x)|+|g(x)-f_n(y)|<\epsilon$$
This $\delta$ is independent of $x$ and $y$(because the boundary we obtained using uniform convergence doesn't depend on $x$ or $y$), so we find that functions $f_n(x)$ are uniformly continuous for $n\geq N$, or in other words $f$ is uniformly continuous for $x>N$(since $f_n(x) = f(x+n)$).
Now we divide the positive $x$-axis into overlapping intervals: $[0,2N]$ and $[N,\infty]$.
By what we derived above, $f$ is proven to be uniformly continuous on the second interval. But $[0,2N]$ is closed and $f$ is continuous on it, hence $f$ is uniformly continuous on it.
So this proves that $f$ is uniformly continuous on the whole domain.

Now we turn to proving uniform continuity of $g$. For $\epsilon>0$, choose $N$ such that for $n\geq N$: $|f_n(x) - g(x)| <\frac{\epsilon}{3}$, for all $x$.
Also from uniform continuity of $f$, we find $\delta$ such that for all $x$ and $y$ in the domain and any $n\geq N$:
$$|x-y|<\delta \Rightarrow |f_n(x)-f_n(y)|<\frac{\epsilon}{3}$$
Then:
$$|x-y|<\delta \Rightarrow |g(x)-g(y)| = |g(x) - f_n(x) + f_n(x) - f_n(y)+f_n(y)-g(y)|\\ \leq |g(x)-f_n(x)| + |f_n(x)-f_n(y)| + |f_n(y)-g(y)|<\epsilon$$
The boundary is by construction independent of $x$ and $y$, so $g$ is also uniformly continuous.

 

[Infrared]

Great, this is much clearer!

I think you could do it your original way too: $g(x+1)=\lim_{n\to\infty}f(x+1+n)=\lim_{n\to\infty}f(x+n+1)=g(x)$, so $g$ is periodic with period dividing $1$. It's continuous by uniform convergence, so uniformly continuous.

 

[Antarres]

Oh true, that's exactly how I wanted to form it, but I used a lot of words to formulate it, since for some reason I didn't feel comfortable writing it in limit form. Thanks for the remark, it would've shortened my argument immensely if I just wrote it that way.

 

[Antarres]

Spoiler: Question #10

The idea for the proof is as follows. Basically for chosen functional $F$, we want to find a decomposition of vectors of $\mathcal{H}$ to the ones belonging to its kernel, and the ones belonging to the orthogonal complement of the kernel, where orthogonal complement is defined with respect to the bilinear form $\beta$. This will allow us to make a decomposition of a vector such that actions of the bilinear form and functional on it coincide, so we find the relation we need. We construct the proof, by first inspecting the property of orthogonal complement.

I will assume here that $\beta(x,x) = 0$ is equivalent to $x=0$, since that wasn't mentioned, but if we take that all vectors have non-zero norm, we exclude the zero vector(cause the form is bilinear) from the space, which shouldn't happen.

Denote $K = \ker F$ which is a subset of $\mathcal{H}$(a closed subset, by continuity of $F$), we assert that $K^\perp$ is one-dimensional(if we exclude the trivial case where kernel would take up the whole space, for which choice $f^\dagger=0$ would suffice). Suppose that it isn't, that there are two independent non-zero vectors $v_1$ and $v_2$ in $\mathcal{H}$, that belong to $K^\perp$. Then we have that $F(v_1)v_2 - F(v_2)v_1$ is a non-zero vector from $K^\perp$, but by linearity of $F$ we have that
$$F(F(v_1)v_2-F(v_2)v_1) = 0$$
which is a contradiction as it would indicate $F(v_1)v_2 - F(v_2)v_1 \in K$. We can extend this argument to any number of dimensions.
Assume $K^\perp$ is spanned by $n$ vectors. Then we create sum of form:
$$v=\sum_i a_i F(y_1)F(y_2)\dots y_i F(y_{i+1})\dots F(y_n) $$
such that $\sum_i a_i=0$.
Then $F(v)=0$, similar to above so its a contradiction.
So $K^\perp$ is one-dimensional.
Let's find a vector $w\in K^\perp$ such that $F(w) = \beta(w,w)$.
Choose:
$$w= \frac{yF(y)}{\beta(y,y)}$$
for some non-zero $y\in K^\perp$. By substitution we see that it satisfies the relation above that we wanted to impose. We can span $K^\perp$ with $w$.
That means that any vector from $\mathcal{H}$ can be decomposed in the form $v = u + kw$, where $k$ is a scalar, $u\in K$ and $w \in K^\perp$. It follows that:
$$F(x) = kF(w) = k\beta(w,w) = \beta(w,u + kw) = \beta(w,x)$$
where we used $\beta(u,w)=0$ - the orthogonal complement definition, and $F(u) = 0$ cause $u\in K$. Therefore we constructed $w\in\mathcal{H}$ such that $F(x) = \beta(w,x)$, so in our formula $w=f^\dagger$.

Let's prove uniqueness. Suppose there are $f_1^\dagger$ and $f_2^\dagger$ that both satisfy the identity $F(x) = \beta(f,x)$ for all $x\in\mathcal{H}$.
Then, take $x = f_1^\dagger - f_2^\dagger$. It follows that:
$$F(x) = \beta(f_1^\dagger, f_1^\dagger-f_2^\dagger)$$
but also:
$$F(x) = \beta(f_2^\dagger,f_1^\dagger-f_2^\dagger)$$
Subtracting the identities above we find:
$$\beta(f_1^\dagger - f_2^\dagger, f_1^\dagger-f_2^\dagger) = 0 \Rightarrow f_1^\dagger = f_2^\dagger.$$
The uniqueness is thus proved.

 

[archaic]

What I ask for, is an approach / solution using some sort of limits. I say "using calculus" in the wording of the question, which is not clear enough but if I make it totally clear, I'll give the way of the solution ;)

Maybe like this?

Spoiler

$$\begin{align*}
\int_a^b\,f(x)dx&=\lim_{n\to\infty}\sum_{k=0}^{n}\,f\left(a+k\frac{b-a}{n}\right)\frac{b-a}{n}\\
&=\lim_{n\to\infty}\sum_{k=0}^{n}\,f\left((a+d)-d+k\frac{(b+d)-(a+d)}{n}\right)\frac{(b+d)-(a+d)}{n}\\
&=\int_{a+d}^{b+d}f(x-d)dx
\end{align*}$$

 

[fresh_42]

Spoiler: Question #10

The idea for the proof is as follows. Basically for chosen functional $F$, we want to find a decomposition of vectors of $\mathcal{H}$ to the ones belonging to its kernel, and the ones belonging to the orthogonal complement of the kernel, where orthogonal complement is defined with respect to the bilinear form $\beta$. This will allow us to make a decomposition of a vector such that actions of the bilinear form and functional on it coincide, so we find the relation we need. We construct the proof, by first inspecting the property of orthogonal complement.

I will assume here that $\beta(x,x) = 0$ is equivalent to $x=0$, since that wasn't mentioned, but if we take that all vectors have non-zero norm, we exclude the zero vector(cause the form is bilinear) from the space, which shouldn't happen.

Denote $K = \ker F$ which is a subset of $\mathcal{H}$(a closed subset, by continuity of $F$), we assert that $K^\perp$ is one-dimensional(if we exclude the trivial case where kernel would take up the whole space, for which choice $f^\dagger=0$ would suffice). Suppose that it isn't, that there are two independent non-zero vectors $v_1$ and $v_2$ in $\mathcal{H}$, that belong to $K^\perp$. Then we have that $F(v_1)v_2 - F(v_2)v_1$ is a non-zero vector from $K^\perp$, but by linearity of $F$ we have that
$$F(F(v_1)v_2-F(v_2)v_1) = 0$$
which is a contradiction as it would indicate $F(v_1)v_2 - F(v_2)v_1 \in K$. We can extend this argument to any number of dimensions.
Assume $K^\perp$ is spanned by $n$ vectors. Then we create sum of form:
$$v=\sum_i a_i F(y_1)F(y_2)\dots y_i F(y_{i+1})\dots F(y_n) $$
such that $\sum_i a_i=0$.
Then $F(v)=0$, similar to above so its a contradiction.
So$K^\perp$ is one-dimensional.
Let's find a vector $w\in K^\perp$ such that $F(w) = \beta(w,w)$.
Choose:
$$w= \frac{yF(y)}{\beta(y,y)}$$
for some non-zero $y\in K^\perp$. By substitution we see that it satisfies the relation above that we wanted to impose. We can span $K^\perp$ with $w$.
That means that any vector from $\mathcal{H}$ can be decomposed in the form $v = u + kw$, where $k$ is a scalar, $u\in K$ and $w \in K^\perp$. It follows that:
$$F(x) = kF(w) = k\beta(w,w) = \beta(w,u + kw) = \beta(w,x)$$
where we used $\beta(u,w)=0$ - the orthogonal complement definition, and $F(u) = 0$ cause $u\in K$. Therefore we constructed $w\in\mathcal{H}$ such that $F(x) = \beta(w,x)$, so in our formula $w=f^\dagger$.

Let's prove uniqueness. Suppose there are $f_1^\dagger$ and $f_2^\dagger$ that both satisfy the identity $F(x) = \beta(f,x)$ for all $x\in\mathcal{H}$.
Then, take $x = f_1^\dagger - f_2^\dagger$. It follows that:
$$F(x) = \beta(f_1^\dagger, f_1^\dagger-f_2^\dagger)$$
but also:
$$F(x) = \beta(f_2^\dagger,f_1^\dagger-f_2^\dagger)$$
Subtracting the identities above we find:
$$\beta(f_1^\dagger - f_2^\dagger, f_1^\dagger-f_2^\dagger) = 0 \Rightarrow f_1^\dagger = f_2^\dagger.$$
The uniqueness is thus proved.

At first sight it looks as if you had proven Riesz' representation theorem. However, the task is a different one. We want to know its generalization to any continuous bilinear form which is bounded on the diagonal from below, but which doesn't necessarily define orthogonality. Riesz' representation theorem is useful for the proof, but not equivalent to the statement.

 

[Not anonymous]

11. b.) In how many different ways can eight queens be placed on a chessboard, such that no queen threatens another? Two solutions are not different, if they can be achieved by a rotation or by mirroring of the board. (For this part there is no proof required.)

Spoiler: Question 11.b.

Is the answer 17? I consider an arrangement to be "different" or "unique" if it cannot be obtained as a rotation (by 90, 180 or 270 degrees) or as a mirror image (reflect across horizontal or vertical center line of chessboard) of any other arrangement in the unique set. The following are 17 unique arrangements I get:

1. [1, 5, 8, 6, 3, 7, 2, 4]
2. [1, 6, 8, 3, 7, 4, 2, 5]
3. [1, 7, 4, 6, 8, 2, 5, 3]
4. [1, 7, 5, 8, 2, 4, 6, 3]
5. [2, 4, 6, 8, 3, 1, 7, 5]
6. [2, 5, 7, 1, 3, 8, 6, 4]
7. [2, 5, 7, 4, 1, 8, 6, 3]
8. [2, 6, 1, 7, 4, 8, 3, 5]
9. [2, 6, 8, 3, 1, 4, 7, 5]
10. [2, 7, 3, 6, 8, 5, 1, 4]
11. [2, 7, 5, 8, 1, 4, 6, 3]
12. [3, 1, 7, 5, 8, 2, 4, 6]
13. [3, 5, 2, 8, 1, 7, 4, 6]
14. [3, 5, 8, 4, 1, 7, 2, 6]
15. [3, 6, 2, 5, 8, 1, 7, 4]
16. [3, 6, 2, 7, 1, 4, 8, 5]
17. [3, 6, 2, 7, 5, 1, 8, 4]

Each array or list above is to be interpreted as denoting an arrangement with each element in the list denoting the column number (occupied on the chessboard) of the queen placed in the row number corresponding to the index of that element of that list. So for example, arrangement [3, 6, 2, 7, 5, 1, 8, 4] means that in row 1 of the chessboard, the queen is placed in column 3, in row 2, the queen is in column 6 and so on till in row 8, the queen is in column 4.

If the answer is correct, I can share the script I wrote to find the solution, if that will help.

 

[fresh_42]

17 is too many, but reflections along the diagonals are considered equal. Do you have the number without equivalence, i.e. how many possibilities at all?

Remember that I only need the numbers, regardless how you found them.

 

[Not anonymous]

17 is too many, but reflections along the diagonals are considered equal. Do you have the number without equivalence, i.e. how many possibilities at all?

Remember that I only need the numbers, regardless how you found them.

When not considering rotations and mirror images as being equivalent, I got 92 different ways to place 8 queens on 8x8 chessboard such that no 2 queens attack each other. I had not considered the possibility of reflection along diagonals in the solution I had posted.

 

[fresh_42]

92 is correct. Fundamental solutions are less than 17.

 

[Not anonymous]

92 is correct. Fundamental solutions are less than 17.

Thanks. Will look at the arrangements from the earlier solution again after sometime and find duplicates arising from diagonal reflections

 

[Not anonymous]

92 is correct. Fundamental solutions are less than 17.

Spoiler: Question 11.b.

Is the answer 12? The following are the unique arrangements when diagonal reflections also to be treated as non-unique.

1. [1, 5, 8, 6, 3, 7, 2, 4]
2. [1, 6, 8, 3, 7, 4, 2, 5]
3. [2, 4, 6, 8, 3, 1, 7, 5]
4. [2, 5, 7, 1, 3, 8, 6, 4]
5. [2, 5, 7, 4, 1, 8, 6, 3]
6. [2, 6, 1, 7, 4, 8, 3, 5]
7. [2, 6, 8, 3, 1, 4, 7, 5]
8. [2, 7, 3, 6, 8, 5, 1, 4]
9. [2, 7, 5, 8, 1, 4, 6, 3]
10. [3, 5, 2, 8, 1, 7, 4, 6]
11. [3, 5, 8, 4, 1, 7, 2, 6]
12. [3, 6, 2, 5, 8, 1, 7, 4]

The arrangements in my earlier solution that are now considered non-unique because they are diagonal reflections of some other arrangement in the final solution are:
[1, 7, 4, 6, 8, 2, 5, 3]
[1, 7, 5, 8, 2, 4, 6, 3]
[3, 1, 7, 5, 8, 2, 4, 6]
[3, 6, 2, 7, 1, 4, 8, 5]
[3, 6, 2, 7, 5, 1, 8, 4]

 

[fresh_42]

Spoiler: Question 11.b.

Is the answer 12? The following are the unique arrangements when diagonal reflections also to be treated as non-unique.

1. [1, 5, 8, 6, 3, 7, 2, 4]
2. [1, 6, 8, 3, 7, 4, 2, 5]
3. [2, 4, 6, 8, 3, 1, 7, 5]
4. [2, 5, 7, 1, 3, 8, 6, 4]
5. [2, 5, 7, 4, 1, 8, 6, 3]
6. [2, 6, 1, 7, 4, 8, 3, 5]
7. [2, 6, 8, 3, 1, 4, 7, 5]
8. [2, 7, 3, 6, 8, 5, 1, 4]
9. [2, 7, 5, 8, 1, 4, 6, 3]
10. [3, 5, 2, 8, 1, 7, 4, 6]
11. [3, 5, 8, 4, 1, 7, 2, 6]
12. [3, 6, 2, 5, 8, 1, 7, 4]

The arrangements in my earlier solution that are now considered non-unique because they are diagonal reflections of some other arrangement in the final solution are:
[1, 7, 4, 6, 8, 2, 5, 3]
[1, 7, 5, 8, 2, 4, 6, 3]
[3, 1, 7, 5, 8, 2, 4, 6]
[3, 6, 2, 7, 1, 4, 8, 5]
[3, 6, 2, 7, 5, 1, 8, 4]

Very good!

 

[mmaismma]

11. Answer the following questions:
a.) How many knights can you place on a $n\times m$ chessboard such that no two attack each other?

Spoiler: Problem 11(a)

There are three cases. $r$ is the required number.
CASE 1: When any of $m$ & $n$ $=1$
$r=n/m$
($r=n$ for $m=1$ and vice versa)
CASE 2: When any of $m$ & $n$ $=2$
(let $q=$ number equal to 2 & $p=$ other number)
1. $p=4x+0$
$r=\frac{pq}2$
2. $p=$else
$r=(\lfloor\frac p2\rfloor+1)\times q$
CASE 3: When both $m$ & $n$ $\gt2$
$r=\lceil\frac{mn}2\rceil$

 

[fresh_42]

Spoiler: Problem 11(a)

There are three cases. $r$ is the required number.
CASE 1: When any of $m$ & $n$ $=1$
$r=n/m$
($r=n$ for $m=1$ and vice versa)
CASE 2: When any of $m$ & $n$ $=2$
(let $q=$ number equal to 2 & $p=$ other number)
1. $p=4x+0$
$r=\frac{pq}2$
2. $p=$else
$r=(\lfloor\frac p2\rfloor+1)\times q$
CASE 3: When both $m$ & $n$ $\gt2$
$r=\lceil\frac{mn}2\rceil$

Let me sort this out. $r$ be the number of knights on an $n \times m$ board.

You already correctly had the cases $m=1$ in which we get $r=n$ and $m>2$ with $r=\lceil\frac{mn}2\rceil$. Now only $m=2$ was left to do.

If $m=2$ and $n=4k$ then you say $r=n$, since $m=q=2$ and thus $q/2=1\, , \,p=r=n.$
This is correct.

If $m=2$ and $n=4k+s$ with $s=1,2,3$ then you get $r=(\lfloor\frac p2\rfloor+1)\times q$ which is in the variables of the problem $r=(\lfloor\frac n2\rfloor+1)\times 2$.
This is correct, too.

The arrangement in case of two rows is

 

[Antarres]

Spoiler: Question #9

In order to calculate the Legendre symbol $\left(\frac{a}{p}\right)$, we are going to use Euler's criterion:
$$\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p}$$

Observing that $\lambda_{a,p}$ is a permutation, we will decompose it into cycles. We observe that any cycle that is a part of the permutation must be of form: $(x, ax, a^2x, a^3x,\dots, a^kx)$, where $k$ is the smallest natural number such that $a^{k+1} \equiv 1 \pmod{p}$, and every number in the cycle is taken modulo $p$.
Such a number $k$ exists and is smaller than $p-1$, since we have only $p-1$ distinct elements in $\mathbb{Z}_p^\times$.
We also observe that all cycles in our permutation must be of same length, because this permutation is induced by left multiplication. That is, if $k$ is the smallest number such that $a^{k+1} \equiv 1 \pmod{p}$, then there can't be another number $l$ satisfying the same property(because only one of them can be considered 'smallest'), and so the cycle will always be terminated by $a^kx$, for every $x$, and fixed $a$.

We conclude that, if we take $k$ to be the length of a cycle corresponding to number $a$(cycles then terminate with $a^{k-1}x$), that there are $\frac{p-1}{k}$ cycles in the permutation $\lambda_{a,p}$. Every cycle of length $k$ has the signature $(-1)^{k-1}$. Therefore we have:
$$\text{sgn}(\lambda_{a,p}) = \left((-1)^{k-1}\right)^\frac{p-1}{k}$$
The above expression is equal to $1$ for odd $k$, and equal to $(-1)^\frac{p-1}{k}$ for even $k$.
Now also, for even $k$:
$$a^{\frac{p-1}{2}} = (a^{\frac{k}{2}})^{\frac{p-1}{k}} \equiv (-1)^\frac{p-1}{k} \pmod{p}$$
The last equality above follows because if $a^k \equiv 1 \pmod{p}$ then $a^\frac{k}{2} \equiv \pm 1 \pmod{p}$. But also we can't have $a^\frac{k}{2} \equiv 1 \pmod{p}$ since $k$ is the smallest positive integer such that this relation holds. Hence it must be $a^\frac{k}{2} \equiv -1 \pmod{p}$.
For odd $k$, we have:
$$a^\frac{p-1}{2} = (a^k)^\frac{p-1}{2k} \equiv 1 \pmod{p}$$
Hence we have that, by Euler's criterion we mentioned at the beginning:
$$\left(\frac{a}{p}\right) = \text{sgn}(\lambda_{a,p})$$
QED

 

[suremarc]

Spoiler: Question #9

In order to calculate the Legendre symbol $\left(\frac{a}{p}\right)$, we are going to use Euler's criterion:
$$\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p}$$

Observing that $\lambda_{a,p}$ is a permutation, we will decompose it into cycles. We observe that any cycle that is a part of the permutation must be of form: $(x, ax, a^2x, a^3x,\dots, a^kx)$, where $k$ is the smallest natural number such that $a^{k+1} \equiv 1 \pmod{p}$, and every number in the cycle is taken modulo $p$.
Such a number $k$ exists and is smaller than $p-1$, since we have only $p-1$ distinct elements in $\mathbb{Z}_p^\times$.
We also observe that all cycles in our permutation must be of same length, because this permutation is induced by left multiplication. That is, if $k$ is the smallest number such that $a^{k+1} \equiv 1 \pmod{p}$, then there can't be another number $l$ satisfying the same property(because only one of them can be considered 'smallest'), and so the cycle will always be terminated by $a^kx$, for every $x$, and fixed $a$.

We conclude that, if we take $k$ to be the length of a cycle corresponding to number $a$(cycles then terminate with $a^{k-1}x$), that there are $\frac{p-1}{k}$ cycles in the permutation $\lambda_{a,p}$. Every cycle of length $k$ has the signature $(-1)^{k-1}$. Therefore we have:
$$\text{sgn}(\lambda_{a,p}) = \left((-1)^{k-1}\right)^\frac{p-1}{k}$$
The above expression is equal to $1$ for odd $k$, and equal to $(-1)^\frac{p-1}{k}$ for even $k$.
Now also, for even $k$:
$$a^{\frac{p-1}{2}} = (a^{\frac{k}{2}})^{\frac{p-1}{k}} \equiv (-1)^\frac{p-1}{k} \pmod{p}$$
The last equality above follows because if $a^k \equiv 1 \pmod{p}$ then $a^\frac{k}{2} \equiv \pm 1 \pmod{p}$. But also we can't have $a^\frac{k}{2} \equiv 1 \pmod{p}$ since $k$ is the smallest positive integer such that this relation holds. Hence it must be $a^\frac{k}{2} \equiv -1 \pmod{p}$.
For odd $k$, we have:
$$a^\frac{p-1}{2} = (a^k)^\frac{p-1}{2k} \equiv 1 \pmod{p}$$
Hence we have that, by Euler's criterion we mentioned at the beginning:
$$\left(\frac{a}{p}\right) = \text{sgn}(\lambda_{a,p})$$
QED

I was working on this, and took the same approach. Unfortunately, I didn’t realize that k-cycles have the signature $(-1)^{k-1}$, and not $(-1)^k$. D’oh!

 

[fresh_42]

Spoiler: Question #9

In order to calculate the Legendre symbol $\left(\frac{a}{p}\right)$, we are going to use Euler's criterion:
$$\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p}$$

Observing that $\lambda_{a,p}$ is a permutation, we will decompose it into cycles. We observe that any cycle that is a part of the permutation must be of form: $(x, ax, a^2x, a^3x,\dots, a^kx)$, where $k$ is the smallest natural number such that $a^{k+1} \equiv 1 \pmod{p}$, and every number in the cycle is taken modulo $p$.
Such a number $k$ exists and is smaller than $p-1$, since we have only $p-1$ distinct elements in $\mathbb{Z}_p^\times$.
We also observe that all cycles in our permutation must be of same length, because this permutation is induced by left multiplication. That is, if $k$ is the smallest number such that $a^{k+1} \equiv 1 \pmod{p}$, then there can't be another number $l$ satisfying the same property(because only one of them can be considered 'smallest'), and so the cycle will always be terminated by $a^kx$, for every $x$, and fixed $a$.

We conclude that, if we take $k$ to be the length of a cycle corresponding to number $a$(cycles then terminate with $a^{k-1}x$), that there are $\frac{p-1}{k}$ cycles in the permutation $\lambda_{a,p}$. Every cycle of length $k$ has the signature $(-1)^{k-1}$. Therefore we have:
$$\text{sgn}(\lambda_{a,p}) = \left((-1)^{k-1}\right)^\frac{p-1}{k}$$
The above expression is equal to $1$ for odd $k$, and equal to $(-1)^\frac{p-1}{k}$ for even $k$.
Now also, for even $k$:
$$a^{\frac{p-1}{2}} = (a^{\frac{k}{2}})^{\frac{p-1}{k}} \equiv (-1)^\frac{p-1}{k} \pmod{p}$$
The last equality above follows because if $a^k \equiv 1 \pmod{p}$ then $a^\frac{k}{2} \equiv \pm 1 \pmod{p}$. But also we can't have $a^\frac{k}{2} \equiv 1 \pmod{p}$ since $k$ is the smallest positive integer such that this relation holds. Hence it must be $a^\frac{k}{2} \equiv -1 \pmod{p}$.
For odd $k$, we have:
$$a^\frac{p-1}{2} = (a^k)^\frac{p-1}{2k} \equiv 1 \pmod{p}$$
Hence we have that, by Euler's criterion we mentioned at the beginning:
$$\left(\frac{a}{p}\right) = \text{sgn}(\lambda_{a,p})$$
QED

This result is called Zolotarev's Lemma. You used but haven't explicitly stated that $k+1=\operatorname{ord}a$. It's a bit easier to read if you start with that definition and the remark that the cycles are disjoint.

Hint for problem 10:
Consider $B(f)(g)=\beta(f,g)$, and use Riesz representation theorem to establish an isometry $T$ between $\mathcal{H}^*$ and $\mathcal{H}$. Then apply Banach's fixed-point theorem on the function $Q(f)=f-\lambda (T(B(f))-T(f))$ for a suitable $\lambda$.

 

[Infrared]

I don't know if @fresh_42 didn't want the fact that $\mathbb{Z}_p^*$ is cyclic to be used for problem 9, but the result follows easily from it. If $a=b^2\in\mathbb{Z}_p^*$ is a square, then $\lambda_a=\lambda_{b}\circ\lambda_{b}$ is even. On the other hand, if $a$ is not a square, then it is an odd power of a generator, and hence also a generator. So $\lambda_a$ is a $(p-1)$-cycle, which is odd.

 

[fresh_42]

I don't know if @fresh_42 didn't want the fact that $\mathbb{Z}_p^*$ is cyclic to be used for problem 9, but the result follows easily from it. If $t$ is a generator, and $a\in\mathbb{Z}_p^*$ is a square, then $a=t^{2k}$ for some integer $k$, so $\lambda_a=\lambda_{t^k}\circ\lambda_{t^k}$ is even. On the other hand, if $a=t^{2k+1}$, then $a$ is also a generator, so $\lambda_a$ is a $(p-1)$-cycle and hence odd.

It does no harm to give an elementary proof.

 

[PeroK]

Well done @etotheipi. It's a very nice shortcut way for this particular case. However, there is a more general way we can solve problems like this. I won't tell what is it but if anyone else wants to try the problem and come up with a correct solution, he / she'll also get credit.

Can you explain what you mean by problems like this? $A$ is a specific matrix, which is its own inverse. What sort of generalisation are you looking for?

 

[QuantumQuest]

Can you explain what you mean by problems like this? $A$ is a specific matrix, which is its own inverse. What sort of generalisation are you looking for?

Well, there is some specific procedure we can follow, a relation coming out of it and then the classic way we treat problems like this.

 

[PeroK]

Well, there is some specific procedure we can follow, a relation coming out of it and then the classic way we treat problems like this.

That's all very well, but I have no idea what the question is asking! Problems like what? Perhaps no one has solved it because no one knows what you're driving at.

 

[skanskan]

In question 1) is the power of n inside the cosine or outside it?

 

[QuantumQuest]

That's all very well, but I have no idea what the question is asking! Problems like what? Perhaps no one has solved it because no one knows what you're driving at.

I'm not saying anything cryptic. When I say problems like this I literally mean it: problems that ask to calculate some power(s) of a matrix. So, in standard curricula for mathematicians, there is a standard way to treat problems like this - the solution given so far in the challenge is absolutely acceptable but there is some more formal way to tackle the whole thing ;)

 

[Infrared]

In question 1) is the power of n inside the cosine or outside it?

Outside

 

[suremarc]

Since the solution I came up with is relatively simple and ignores @fresh_42’s hint, I feel like I must be completely wrong.

Spoiler: Problem 10

Consider the operator $\mathrm{B_1}: \mathcal{H}\rightarrow\mathcal{H}$ defined by $\mathrm{B_1}(f)=(\beta(f,\cdot))^*$. The question essentially is asking for a proof that $\mathrm{B_1}$ is a bijection.
Now, $\beta(f,f)$ bounded below implies that $\mathrm{B_1}$ is, too:
$$\beta(f,f)=\langle\mathrm{B_1}f,f\rangle\leq\|\mathrm{B_1}f\|\|f\|$$
by Cauchy-Schwarz;
$$\Rightarrow\|\mathrm{B_1}f\|\|f\|\geq C\|f\|^2\\
\Rightarrow\|\mathrm{B_1}f\|\geq C\|f\|; \|f\|\neq 0.$$
When $\|f\|=0$ the final inequality is trivially true. Additionally, the same can be applied to the map $\mathrm{B}_2(f)=(\beta(\cdot,f))^*=\mathrm{B}_1^*(f)$.

Now, we use the following fact: a continuous linear map is bounded below iff it is injective with closed range.
This means that $\mathrm{B_1}$ and $\mathrm{B_2}$ are injective with closed range. By the closed range theorem, $\mathrm{im(B_1)=ker(B_1^*)^\perp=ker(B_2)^\perp}$. But since $\mathrm{B_2}$ is injective, $\mathrm{ker(B_2)}$ is trivial, and so $\mathrm{im(B_1)}=\mathcal{H}$. So $\mathrm{B_1}$ is injective and surjective, proving the original result.

I tried to use the hint, and was able to apply the fixed point theorem for $\lambda\in(1,2)$, but didn’t know what to do after that.

 

[fresh_42]

Since the solution I came up with is relatively simple and ignores @fresh_42’s hint, I feel like I must be completely wrong.

Spoiler: Problem 10

Consider the operator $\mathrm{B_1}: \mathcal{H}\rightarrow\mathcal{H}$ defined by $\mathrm{B_1}(f)=(\beta(f,\cdot))^*$. The question essentially is asking for a proof that $\mathrm{B_1}$ is a bijection.
Now, $\beta(f,f)$ bounded below implies that $\mathrm{B_1}$ is, too:
$$\beta(f,f)=\langle\mathrm{B_1}f,f\rangle\leq\|\mathrm{B_1}f\|\|f\|$$
by Cauchy-Schwarz;
$$\Rightarrow\|\mathrm{B_1}f\|\|f\|\geq C\|f\|^2\\
\Rightarrow\|\mathrm{B_1}f\|\geq C\|f\|; \|f\|\neq 0.$$
When $\|f\|=0$ the final inequality is trivially true. Additionally, the same can be applied to the map $\mathrm{B}_2(f)=(\beta(\cdot,f))^*=\mathrm{B}_1^*(f)$.

Now, we use the following fact: a continuous linear map is bounded below iff it is injective with closed range.
This means that $\mathrm{B_1}$ and $\mathrm{B_2}$ are injective with closed range. By the closed range theorem, $\mathrm{im(B_1)=ker(B_1^*)^\perp=ker(B_2)^\perp}$. But since $\mathrm{B_2}$ is injective, $\mathrm{ker(B_2)}$ is trivial, and so $\mathrm{im(B_1)}=\mathcal{H}$. So $\mathrm{B_1}$ is injective and surjective, proving the original result.

I tried to use the hint, and was able to apply the fixed point theorem for $\lambda\in(1,2)$, but didn’t know what to do after that.

I'm a bit skeptical about your use of duality. E.g. why is $\operatorname{im}B_1 =\mathcal{H}\,?$ Didn't you use $\mathcal{H}=\left(\mathcal{H}^*\right)^*$ with $\beta$ instead of the inner product? In other words: why does $B_1$ land in the space you claim it does? You have only added an asterix.

I know that boundedness and continuity is equivalent. Can you reference the theorem you used to make the range closed, not only dense? I think this is the crucial point. My proof does those things in smaller steps by using Banach to actually define the specific image $f^\dagger$ we are looking for.

The whole theorem is a generalization of Riesz, so we have to be careful with duality, i.e. rigorously separate the inner product and the given bilinear form. The simple notation with an asterix needs a bit of an explanation.