Math Challenge - October 2021

[fresh_42]

Summary: Functional Analysis. Project Management. Set Theory. Group Theory. Lie Theory. Countability. Banach Algebra. Stochastic. Function Theory. Calculus.1. Prove that $F\, : \,L^2([0,1])\longrightarrow (C([0,1]),\|.\|_\infty )$ defined as $$F(x)(t):=\int_0^1 (t^2+s^2)(x(s))^2\,ds$$ is compact.2. A project manager has $n$ workers to finish the project. Let $x_i$ be the workload of the $i-$th person, and
$$
x\in S:= \left\{ x\in \mathbb{R}^n \, \mid \, \sum_{i=1}^nx_i=1\, , \, x_i\geq 0\right\}
$$
a possible partition of work. Let $X_i$ be the set of partitions, which person $i$ agrees upon. We may assume that he automatically agrees if $x_i=0,$ that $X_i$ is closed, and that there is always at least one person which agrees to a given partition, i.e. $\bigcup_{i=1}^n X_i=S.$ Prove that there is one partition that all workers agree upon.


3. Assume the axiom schema of separation for any predicate $P(x)$
$$
\forall A\, : \,\exists M\, : \,\forall x\, : \,\left(x\in M \Longleftrightarrow x\in A \wedge P(x)\right)
$$
Show that $|A|<|\mathcal{P}(A)|$ where $\mathcal{P}(A)$ is the power set of $A.$


4. (solved by @fishturtle1 ) Let $\sigma_1,\ldots,\sigma_n$ be homomorphisms from a group $G$ into the multiplicative group $\mathbb{F}^*$ of a field $\mathbb{F}.$ Show that they are $\mathbb{F}-$linearly independent if and only if they are pairwise distinct.5. (solved by @Office_Shredder ) Prove that general Heisenberg (Lie-)algebras $\mathfrak{H}$ are nilpotent.6. (solved by @Office_Shredder and @Not anonymous ) Prove that the polynomial $\mathbb{N}_0^2\stackrel{P}{\longrightarrow }\mathbb{N}_0$ defined as
$$
P(x,y)=\dfrac{1}{2}\left((x+y)^2+3x+y\right)
$$
is a bijection.


7. Prove that the spectrum of every element of a complex Banach algebra $B$ with $1$ is nonempty. Conclude that if $B$ is a division ring, then $B\cong \mathbb{C}.$8. Let $X_1,\ldots,X_n$ be independent random variables, such that almost certain $a_i\leq X_i-E(X_i)\leq b_i$, and let $0<c\in \mathbb{R}$. Prove that
$$
\operatorname{Pr}\left(\sum_{i=1}^n (X_i-E (X_i))\geq c\right)\leq \exp\left(\dfrac{-2c^2}{\sum_{i=1}^n(b_i-a_i)^2}\right).
$$

9. Let $G\subseteq \mathbb{C}$ be a non-empty, open, connected subset, and $f,g$ holomorphic functions on $G.$ Show that the following statements are equivalent:

1. $f(z)=g(z)$ for all $z\in G.$
2. $\{z\in G\,|\,f(z)=g(z)\}$ has a limit point.
3. There is a $z\in G$ such that $f^{(n)}(z)=g^{(n)}(z)$ for all $n\in \mathbb{N}_0.$

10. (solved by @julian ) Prove that $\pi^2$ is irrational.

11. (solved by @ANB3010 ) Find all functions $f,g$ such that
\begin{align*}
f,g\, &: \,\mathbb{R} \backslash \{-1,0,1\} \longrightarrow \mathbb{R}\\
xf(x)&=1+\dfrac{1}{x}g\left(\dfrac{1}{x}\right)\, \text{ and } \,
\dfrac{1}{x^2}f\left(\dfrac{1}{x}\right)=x^2g(x)
\end{align*}
Extra: (open) Determine a number $r\in \mathbb{R}$ such that $|f(x)-f(x_0)|<0.001$ whenever $|x-x_0|<r$ and $x_0=2,$ and explain why there is no such number if we choose $x_0=1$ even if we artificially define some function value for $f(1).$


12. (open) Solve the following equation system in $\mathbb{R}^3$
\begin{align*}
x^2+y^2+z^2=1 \quad\wedge \quad x+2y+3z=\sqrt{14}
\end{align*}
Extra: (open) Give an alternative solution in case you have the additional information that the solution is unique.13. (solved by @Not anonymous ) If $(x_n)_{n\in \mathbb{N}}\subseteq \mathbb{R}_{>0}$ is a monotone decreasing sequence of positive real numbers such that for every $n\in \mathbb{N}$
$$
\dfrac{x_1}{1}+\dfrac{x_4}{2}+\dfrac{x_9}{3}+\ldots+\dfrac{x_{n^2}}{n}\leq 1
$$
prove that for every $n\in\mathbb{N}$
$$
\dfrac{x_1}{1}+\dfrac{x_2}{2}+\dfrac{x_3}{3}+\ldots+\dfrac{x_{n}}{n}\leq 3
$$
Extra: (open) Prove that both sequences converge to $0.$14. (solved by @Not anonymous ) Solve the following equation system for real numbers:
\begin{align*}
(1)\qquad x+xy+xy^2&=-21\\
(2)\qquad y+xy+x^2y&=14\\
(3)\qquad \,\,\phantom{y+xy} x+y&=-1
\end{align*}
Extra: (solved by @Not anonymous )

​

Consider the two elliptic curves and observe that one has two connection components and the other one has only one. Determine the constant$c\in [1,3]$ in $y^2=x^3-2x+c$ where this behavior exactly changes. What is the left-most point of this curve?15. (solved by @Not anonymous ) Find all real numbers $m\in \mathbb{R}$, such that for all real numbers $x\in \mathbb{R}$ holds
$$
f(x,m):=x^2+(m+2)x+8m+1 >0 \qquad (*)
$$
and determine the value of $m$ for which the minimum of $f(x,m)$ is maximal. What is the maximum?

Extra: (open) The set of all intersection points of two perpendicular tangents is called orthoptic of the parabola. Prove that it is the directrix, the straight parallel to the tangent at the extremum on the opposite side of the focus.

 

[Office_Shredder]

#2 reminds me of the colorful caratheodory theorem, which I recall as being surprisingly powerful though I can't actually remember any applications.For #3, is that $M$ supposed to be a $B$?

 

[fresh_42]

#2 reminds me of the colorful caratheodory theorem, which I recall as being surprisingly powerful though I can't actually remember any applications.

I found it as an application of Brouwer and the author named it "work lemma". I thought PM fits better.

For #3, is that $M$ supposed to be a $B$?

For every set $A$ there is a set $M$ that contains exactly the elements $x$ from $A$ for which $P(x)$ holds.

I corrected the typo $B=M$. I got confused between the German Wiki page that uses $M$ and the English Wiki page that uses $B$.

 

[PeroK]

...

Your profile says you have a PhD (albeit in Mech Eng), so you're not really supposed to be doing the High School () problems!

 

[Office_Shredder]

#3 is actually not that hard, if you can get through the notation and know why this axiom is a thing. Here's a bit of help to cut through the the heart of the question

Spoiler

A predicate $P(x)$ is just a thing which is either true or false for every $x$. For example $P(x)$ is true if $x$ is a finite set, and false if it's infinite would be a predicate. A pretty normal thing to want is to have a set of all objects that are true under a predicate - so you could have the set of all finite sets. This turns out to not be logically consistent!

A somewhat famous result known as Russell's Paradox: let $P(x)$ be true if $x\notin x$, if $x$ does not contain itself, and let $X$ be the set of all sets for which $P(x)$. Then $X\in X$ if and only if $P(x)$, which means $X\notin X$.

So it turns out you literally cannot just assume given a predicate, that there exists a set of all the things which satisfy that predicate. You literally are just not allowed to try to define sets this way.

The axiom schema of separation gives you something similar but much less out of control. It says given a set $A$, and a predicate $P$, that the set of elements of $A$ that satisfy $P$ is in fact a set, and you don't get logical inconsistencies if you assume this.

The other part of the question is cardinalities. $|A|$ is just the size of a set $A$. For infinite sets it's a bit unclear what this even means. You can compare the relative size of two sets by seeing what kind of functions exist between them - if there is a bijection between $A$ and $B$, then we say they have the same size and write $|A| = |B|$. If there is an injection from $A$ to $B$ but no injection from $B$ to $A$, then we say $|A| < |B|$. It's surprisingly hard to prove that this gives a well defined total ordering assuming standard set theory axioms- for every two sets, one of them has an injection to the other one, and if $A$ can be injected into $B$ and $B$ can also be injected into $A$, then there exists a bijection between them.

So when the question says to prove $|A| < |P(A)|$, it's just asking you to show there is an injection from $A$ to $P(A)$ (this part is easy)! But that there does not exist a bijection, because that would contradict the axiom schema of separation.

 

[Office_Shredder]

Alright I'll try #5 assuming I found the correct definition of the general Heisenberg lie algebra.

Spoiler

According to Wikipedia, the general Heisenberg algebra is the set of matrices of the form
$$
\begin{pmatrix}
0 & \mathbf{a}^t & c \\
\mathbf{0} & 0_n & \mathbf{b} \\
0 & \mathbf{0}^t & 0\end{pmatrix}
$$

Where $0_n$ is an $n\times n$ matrix of zeroes, $c$ is a real number, $\mathbf{0}$ is a column vector of $n$ zeroes, and $\mathbf{a}$ and $\mathbf{b}$ are arbitrary column vector of length $n$. For ease of notation and to avoid having to write any matrices in the future I'm going to denote a matrix of this form as $(\mathbf{a},\mathbf{b},c)$ We need to show that $\mathfrak{H}$ is nilpotent, which means $[\mathfrak{H},[\mathfrak{H},[,...,\mathfrak{H}]]]$ eventually results in being left with only 0.

Recall in general for two matrices $[A,B] = AB-BA$. We start by computing the matrix multiplication $(\mathbf{a}_1,\mathbf{b}_1,c_1) (\mathbf{a}_2,\mathbf{b}_2,c_2)$. The first entry of every row of the 1 matrix is 0, and every column of the 2 matrix except for the last column has a 0 for every entry except for the first one, so the only combination of row of first matrix, column of second matrix which has a non-zero dot product is the first row of the 1 matrix, and last column of the 2 matrix, which means the matrix we get from multiplying is all zeroes except for the top right corner, and hence can be written as $(\mathbf{0},\mathbf{0},c)$ where $c=\mathbf{a}_1 \cdot \mathbf{b}_2$.

Hence we can compute the bracket
$$[(\mathbf{a}_1,\mathbf{b}_1,c_1),(\mathbf{a}_2,\mathbf{b}_2,c_2)]= (\mathbf{0},\mathbf{0},\mathbf{a}_1 \cdot \mathbf{b}_2 - \mathbf{a}_2 \cdot \mathbf{b}_1).$$

We can then compute applying another arbitrary bracket
$$[(\mathbf{a}_3,\mathbf{b}_3,c_3),(\mathbf{0},\mathbf{0},\mathbf{a}_1 \cdot \mathbf{b}_2 - \mathbf{a}_2 \cdot \mathbf{b}_1)] = (\mathbf{0},\mathbf{0}, \mathbf{a}_3 \cdot \mathbf{0} - \mathbf{0} \cdot \mathbf{b}_3).$$

And of course, the dot product of the zero vector with anything is 0, so we get overall that for any three matrices $A,B,C\in \mathfrak{H}$, we have $[A,[B,C] = 0$. Hence $[\mathfrak{H}, [\mathfrak{H}, \mathfrak{H}]] =0$ and it's nilpotent as desired.

 

[fresh_42]

Alright I'll try #5 assuming I found the correct definition of the general Heisenberg lie algebra.

Spoiler

According to Wikipedia, the general Heisenberg algebra is the set of matrices of the form
$$
\begin{pmatrix}
0 & \mathbf{a}^t & c \\
\mathbf{0} & 0_n & \mathbf{b} \\
0 & \mathbf{0}^t & 0\end{pmatrix}
$$

Where $0_n$ is an $n\times n$ matrix of zeroes, $c$ is a real number, $\mathbf{0}$ is a column vector of $n$ zeroes, and $\mathbf{a}$ and $\mathbf{b}$ are arbitrary column vector of length $n$. For ease of notation and to avoid having to write any matrices in the future I'm going to denote a matrix of this form as $(\mathbf{a},\mathbf{b},c)$ We need to show that $\mathfrak{H}$ is nilpotent, which means $[\mathfrak{H},[\mathfrak{H},[,...,\mathfrak{H}]]]$ eventually results in being left with only 0.

Recall in general for two matrices $[A,B] = AB-BA$. We start by computing the matrix multiplication $(\mathbf{a}_1,\mathbf{b}_1,c_1) (\mathbf{a}_2,\mathbf{b}_2,c_2)$. The first entry of every row of the 1 matrix is 0, and every column of the 2 matrix except for the last column has a 0 for every entry except for the first one, so the only combination of row of first matrix, column of second matrix which has a non-zero dot product is the first row of the 1 matrix, and last column of the 2 matrix, which means the matrix we get from multiplying is all zeroes except for the top right corner, and hence can be written as $(\mathbf{0},\mathbf{0},c)$ where $c=\mathbf{a}_1 \cdot \mathbf{b}_2$.

Hence we can compute the bracket
$$[(\mathbf{a}_1,\mathbf{b}_1,c_1),(\mathbf{a}_2,\mathbf{b}_2,c_2)]= (\mathbf{0},\mathbf{0},\mathbf{a}_1 \cdot \mathbf{b}_2 - \mathbf{a}_2 \cdot \mathbf{b}_1).$$

We can then compute applying another arbitrary bracket
$$[(\mathbf{a}_3,\mathbf{b}_3,c_3),(\mathbf{0},\mathbf{0},\mathbf{a}_1 \cdot \mathbf{b}_2 - \mathbf{a}_2 \cdot \mathbf{b}_1)] = (\mathbf{0},\mathbf{0}, \mathbf{a}_3 \cdot \mathbf{0} - \mathbf{0} \cdot \mathbf{b}_3).$$

And of course, the dot product of the zero vector with anything is 0, so we get overall that for any three matrices $A,B,C\in \mathfrak{H}$, we have $[A,[B,C] = 0$. Hence $[\mathfrak{H}, [\mathfrak{H}, \mathfrak{H}]] =0$ and it's nilpotent as desired.

Yes, $\mathfrak{H}$ is even meta-abelian. You can also conclude that $\operatorname{ad}X$ is a nilpotent linear transformation and use Engel's theorem to conclude that $\mathfrak{H}$ is nilpotent.

 

[Office_Shredder]

#6

Spoiler

We can redefine this by setting $a=x+y$ and then $P(a,x)= \frac{1}{2}(a^2+a) + x$ for any $a\in \mathbb{N}_0$, and $x\leq a$. We consider incrementing $a$ by 1. The idea is we start at $a=0$, iterate through all the possible choices of $x$, then iterate $a$ up by 1 and reset $x$ to zero. Then iterate through all the possible values of $x$, and repeat the procedure. In particular,

$$P(a+1,0)= \frac{1}{2}(a^2+2a+1+a+1)$$
$$ = \frac{1}{2}(a^2+a) +a +1 $$
$$= P(a,a) +1.$$
Recall that $x$ is not actually allowed to be equal to $a+1$ in our original map. So we have that $P(a,x+1)=P(a,x)+1$ for $x<a$, and $P(a+1,0)=P(a,a)+1$. This shows that as we iterate through $a$ and $x$ as described in the first paragraph $P$ increases by one each time. Hence $P$ is an injection, and since $P(0,0)=0$, it's also a surjection onto $\mathbb{N}_0$.

In fact, this is actually the normal bijection given between these sets

https://www.google.com/imgres?imgur...W_6dfUaW2gJM&w=661&h=602&itg=1&source=sh/x/im

Since a fixed choice of $a$ corresponds to fixing a diagonal line there, and as you increment $x$ you just shift where on the diagonal you are. The only difference is instead of zig zagging through $\mathbb{N}^2$, every time we complete a diagonal we go back to the y-axis where $x=0$, so all the diagonals are going in the same direction.

 

[fresh_42]

#6

Spoiler

We can redefine this by setting $a=x+y$ and then $P(a,x)= \frac{1}{2}(a^2+a) + x$ for any $a\in \mathbb{N}_0$, and $x\leq a$. We consider incrementing $a$ by 1. The idea is we start at $a=0$, iterate through all the possible choices of $x$, then iterate $a$ up by 1 and reset $x$ to zero. Then iterate through all the possible values of $x$, and repeat the procedure. In particular,

$$P(a+1,0)= \frac{1}{2}(a^2+2a+1+a+1)$$
$$ = \frac{1}{2}(a^2+a) +a +1 $$
$$= P(a,a) +1.$$
Recall that $x$ is not actually allowed to be equal to $a+1$ in our original map. So we have that $P(a,x+1)=P(a,x)+1$ for $x<a$, and $P(a+1,0)=P(a,a)+1$. This shows that as we iterate through $a$ and $x$ as described in the first paragraph $P$ increases by one each time. Hence $P$ is an injection, and since $P(0,0)=0$, it's also a surjection onto $\mathbb{N}_0$.

In fact, this is actually the normal bijection given between these sets

https://www.google.com/imgres?imgurl=https://nivotko.files.wordpress.com/2020/04/image-20.png&imgrefurl=https://nivotko.wordpress.com/2012/12/28/on-bijection-of-nxn-to-n/&tbnid=PlMaotaWsPRDkM&vet=1&docid=oHW_6dfUaW2gJM&w=661&h=602&itg=1&source=sh/x/im

Since a fixed choice of $a$ corresponds to fixing a diagonal line there, and as you increment $x$ you just shift where on the diagonal you are. The only difference is instead of zig zagging through $\mathbb{N}^2$, every time we complete a diagonal we go back to the y-axis where $x=0$, so all the diagonals are going in the same direction.

One can also use differentiation to show the increasing behaviour of $P$ and surjectivity by foot.

It can be shown in a rather complicated proof, that $P(x,y)$ and $P(y,x)$ are the only quadratic real polynomials that enumerate $\mathbb{N}^2$ in such a way (Theorem of Fueter-Pólya). It is not known whether the requirement quadratic can be dropped.

 

[fresh_42]

#6

Spoiler

We can redefine this by setting $a=x+y$ and then $P(a,x)= \frac{1}{2}(a^2+a) + x$ for any $a\in \mathbb{N}_0$, and $x\leq a$. We consider incrementing $a$ by 1. The idea is we start at $a=0$, iterate through all the possible choices of $x$, then iterate $a$ up by 1 and reset $x$ to zero. Then iterate through all the possible values of $x$, and repeat the procedure. In particular,

$$P(a+1,0)= \frac{1}{2}(a^2+2a+1+a+1)$$
$$ = \frac{1}{2}(a^2+a) +a +1 $$
$$= P(a,a) +1.$$
Recall that $x$ is not actually allowed to be equal to $a+1$ in our original map. So we have that $P(a,x+1)=P(a,x)+1$ for $x<a$, and $P(a+1,0)=P(a,a)+1$. This shows that as we iterate through $a$ and $x$ as described in the first paragraph $P$ increases by one each time. Hence $P$ is an injection, and since $P(0,0)=0$, it's also a surjection onto $\mathbb{N}_0$.

In fact, this is actually the normal bijection given between these sets

https://www.google.com/imgres?imgurl=https://nivotko.files.wordpress.com/2020/04/image-20.png&imgrefurl=https://nivotko.wordpress.com/2012/12/28/on-bijection-of-nxn-to-n/&tbnid=PlMaotaWsPRDkM&vet=1&docid=oHW_6dfUaW2gJM&w=661&h=602&itg=1&source=sh/x/im

Since a fixed choice of $a$ corresponds to fixing a diagonal line there, and as you increment $x$ you just shift where on the diagonal you are. The only difference is instead of zig zagging through $\mathbb{N}^2$, every time we complete a diagonal we go back to the y-axis where $x=0$, so all the diagonals are going in the same direction.

One can also use differentiation to show the increasing behaviour of $P$ and surjectivity by foot.

It can be shown in a rather complicated proof, that $P(x,y)$ and $P(y,x)$ are the only quadratic real polynomials that enumerate $\mathbb{N}^2$ in such a way (Theorem of Fueter-Pólya). It is not known whether the requirement quadratic can be dropped.

 

[Office_Shredder]

What does surjectivity by foot mean?

I am also wondering for question 1, what does it mean for a function to be compact here?

 

[fresh_42]

What does surjectivity by foot mean?

Step by step starting with $P(x,0)$ and $P(0,y)$, the diagonal argument by formulas.

I am also wondering for question 1, what does it mean for a function to be compact here?

As an operator between Banach spaces: $F(\text{bounded})\text{ is relative compact}.$

 

[Not anonymous]

6. Prove that the polynomial $\mathbb{N}_0^2 \xrightarrow{P} \mathbb{N}_0$ defined as $$
P(x,y) = \dfrac{1}{2}\left((x+y)^2 + 3x + y\right)
$$
is a bijection.

Spoiler: Question 6

Suppose $P(x,y)$ is not a one-to-one mapping function. Then there must exist at least one value $z \in \mathbb{N}_0$ for which there exist $x_1, y_1 \in \mathbb{N}_0$ and $a, b \in \mathbb{N}$, $b \leq y_1$ such that $P(x_1+a, y_1-b) = P(x_1, y_1) = z$, i.e. $P$ maps two different pairs, $(x_1, y_1)$ and $(x_1+a, y_1-b)$, to the same value $z$. Note that the condition $a, b > 0$ arises because $P(x+a, y) \neq P(x,y)$ for any $a \neq 0$ and similarly $P(x, y-b) \neq P(x,y)$ for any $b \neq 0$.

$P(x_1+a, y_1-b) = P(x_1, y_1) \Rightarrow P(x_1+a, y_1-b) - P(x_1, y_1) = 0$
$\Rightarrow \dfrac{1}{2} \left( (x_1+a + y_1-b)^2 - (x_1+y_1)^2 + 3a -b \right) = 0$
$\Rightarrow \left( (a-b)(2p + a - b) + 3a - b \right) = 0 \Rightarrow a^2 + a(2p-2b+3) + (b^2 - 2bp -b) = 0$

(Eq. 1)​

where we define $p = x_1+y_1$ for simplicity. If Eq. 1 is viewed as a quadratic equation in variable $a$, the roots of the equation are given by $\dfrac{-(2p-2b+3) \pm \sqrt{4p^2 + 12p - 8b + 9}}{2}$

(Eq. 2)​

Since we need only natural number roots for $a$, the numerator in (Eq. 2) must be a natural number, and since $p, b$ are natural or whole numbers, this implies that $\sqrt{4p^2 + 12p - 8b + 9} \in \mathbb{N} \Rightarrow 4p^2 + 12p - 8b + 9 \in \mathbb{N}$, i.e. $4p^2 + 12p - 8b + 9$ must be a perfect square and non-zero.

Since $1 \leq b \leq y_1$ and $p = x_1 + y_1 \geq y_1 \geq 0$, we must have $0 < 4p^2 + 4p + 9 \leq 4p^2 + 12p - 8b + 9 \leq 4p^2 + 12p + 1$

(3)​

(3) and the requirement that $S \equiv 4p^2 + 12p - 8b + 9$ be a perfect square imply that $S$ must be of the form $(2p+q)^2$ for some $q \in \mathbb{N}$. Considering the smallest possible values of $q$, i.e. 1, 2 and 3, we see that:
$(2p+1)^2 = 4p^2 + 4p + 1 < S$
$(2p+2)^2 = 4p^2 + 8p + 4 \neq S$ (since $S$ is an odd number whereas LHS is an even number)
$(2p+3)^2 = 4p^2 + 12p + 9 > S \Rightarrow (2p+q)^2 > S \, \, \forall q > 3$

Thus, there is no integer value $q$ for which $(2p+q)^2 = S$, implying that $S$ cannot be a perfect square, and hence no integer-valued solution exists for $a$ in (Eq. 1). This contradicts the initial assumption of $P(x_1+a, y_1-b) = P(x_1, y_1) = z$ with $a, b \in \mathbb{N}$. Therefore, $P(x, y)$ must be a one-to-one function.

(4)​

Next, we prove that $P(x,y)$ is an onto function, i.e. for any $z \in \mathbb{N}$, there must exist some $x,y \in \mathbb{N}_0$ such that $P(x,y) = z$.

Base case: For $z=0$, we see that $(x,y)=(0,0)$ is a solution since $P(0,0) = 0$
Induction step: If a solution (i.e. some $(x_1,y_1) \in \mathbb{N}_0^2$ such that $P(x_1,y_1) = z$) exists for a non-negative integer $z$, then a solution will also exist for $P(x,y) = z+1$. This can be proved as follows.

Case 1: $y_1=0$, i.e. $P(x_1, 0) = z$. Then consider $x=0, y = x_1+1$. $P(x,y) = P(0, x_1+1) = \dfrac{1}{2}((0+x_1+1)^2 + 0 + x_1+1) = \dfrac{1}{2}(x_1^2 +3x_1+2) = \dfrac{1}{2}(x_1^2 +3x_1) + 1$.

(5.1)​

Since $P(x_1, 0)= z$, we have $z = \dfrac{1}{2}(x_1^2 + 3x_1)$

(5.2)​

Combining equations (5.1) and (5.2), we see that $P(0, x_1+1) = P(x_1,0) + 1 = z+1$, i.e. $(0, x_1+1) \xrightarrow{P} z+1$, proving that a solution exists for $z+1$ too.

Case 2: $y_1 > 0$. Then consider $x=x_1+1, y = y_1 - 1$.
$P(x_1+1, y_1-1) = \dfrac{1}{2} \left( (x_1+1+y_1-1)^2 + 3(x_1+1) + (y_1-1) \right)$
$= \dfrac{1}{2} \left( (x_1+y_1)^2 + 3x_1 + y_1 \right) + 1$

(6.1)​

Since $P(x_1,y_1)=z$, we have $z = \dfrac{1}{2}\left( (x_1+y+1)^2 + 3x_1 + y_1 \right)$

(6.2)​

Comparing or combining equations (6.1) and (6.2), we see that $P(x_1+1, y_1-1) = P(x_1,y_1) + 1 = z+1$, i.e. $(x_1+1,y_1-1) \xrightarrow{P} z+1$, proving that a solution exists for $z+1$ too.

Thus, by the method of induction, it is proven that a solution for $P(x,y)=z$ (with $(x,y) \in \mathbb{N}_0^2$) exists for every non-negative integer $z$. This establishes that $\mathbb{N}_0^2 \xrightarrow{P} \mathbb{N}$ is an onto function.

(7)​

From (4) and (7) it follows that $P(x,y)$ defined over $\mathbb{N}_0^2$ is an one-to-one and onto function mapping $\mathbb{N}_0^2$ to $\mathbb{N}$ and is therefore a bijection.

 

[fresh_42]

Suppose $P(x,y)$ is not a one-to-one mapping function. Then there must exist at least one value $z \in \mathbb{N}_0$ for which there exist $x_1, y_1 \in \mathbb{N}_0$ and $a, b \in \mathbb{N}$, $b \leq y_1$ such that $P(x_1+a, y_1-b) = P(x_1, y_1) = z$, i.e. $P$ maps two different pairs, $(x_1, y_1)$ and $(x_1+a, y_1-b)$, to the same value $z$. Note that the condition $a, b > 0$ arises because $P(x+a, y) \neq P(x,y)$ for any $a \neq 0$ and similarly $P(x, y-b) \neq P(x,y)$ for any $b \neq 0$.

I do not see why $b\in [1,y_1]$. You assume that there are two points $(x_1,y_1)$ and $(x_2,y_2)$ with the same image under $P$. You may assume (by exchange of the numbering) that $x_2=x_1+a$ with $a\geq 0$. But then $y_2$ could be anything, i.e. $y_2=y_1+b$ with $b\in \mathbb{Z}$. All I can see is, that you may assume that $a$ and $b$ cannot be zero at the same time. But e.g. all values $(a,b)\in \{(0,1),(1,-1),(1,0),(1,1)\}$ could appear. At least I do not see why not.

Start with $(x_1,y_1)\neq (x_2,y_2)$. This does not mean that both coordinates have to be distinct.

$P(x_1+a, y_1-b) = P(x_1, y_1) \Rightarrow P(x_1+a, y_1-b) - P(x_1, y_1) = 0$
$\Rightarrow \dfrac{1}{2} \left( (x_1+a + y_1-b)^2 - (x_1+y_1)^2 + 3a -b \right) = 0$
$\Rightarrow \left( (a-b)(2p + a - b) + 3a - b \right) = 0 \Rightarrow a^2 + a(2p-2b+3) + (b^2 - 2bp -b) = 0$

(Eq. 1)​

where we define $p = x_1+y_1$ for simplicity. If Eq. 1 is viewed as a quadratic equation in variable $a$, the roots of the equation are given by $\dfrac{-(2p-2b+3) \pm \sqrt{4p^2 + 12p - 8b + 9}}{2}$

(Eq. 2)​

Since we need only natural number roots for $a$, the numerator in (Eq. 2) must be a natural number, and since $p, b$ are natural or whole numbers, this implies that $\sqrt{4p^2 + 12p - 8b + 9} \in \mathbb{N} \Rightarrow 4p^2 + 12p - 8b + 9 \in \mathbb{N}$, i.e. $4p^2 + 12p - 8b + 9$ must be a perfect square and non-zero.

Since $1 \leq b \leq y_1$ and $p = x_1 + y_1 \geq y_1 \geq 0$, we must have $0 < 4p^2 + 4p + 9 \leq 4p^2 + 12p - 8b + 9 \leq 4p^2 + 12p + 1$

(3)​

(3) and the requirement that $S \equiv 4p^2 + 12p - 8b + 9$ be a perfect square imply that $S$ must be of the form $(2p+q)^2$ for some $q \in \mathbb{N}$. Considering the smallest possible values of $q$, i.e. 1, 2 and 3, we see that:
$(2p+1)^2 = 4p^2 + 4p + 1 < S$
$(2p+2)^2 = 4p^2 + 8p + 4 \neq S$ (since $S$ is an odd number whereas LHS is an even number)
$(2p+3)^2 = 4p^2 + 12p + 9 > S \Rightarrow (2p+q)^2 > S \, \, \forall q > 3$

Thus, there is no integer value $q$ for which $(2p+q)^2 = S$, implying that $S$ cannot be a perfect square, and hence no integer-valued solution exists for $a$ in (Eq. 1). This contradicts the initial assumption of $P(x_1+a, y_1-b) = P(x_1, y_1) = z$ with $a, b \in \mathbb{N}$. Therefore, $P(x, y)$ must be a one-to-one function.

(4)​

Next, we prove that $P(x,y)$ is an onto function, i.e. for any $z \in \mathbb{N}$, there must exist some $x,y \in \mathbb{N}_0$ such that $P(x,y) = z$.

Base case: For $z=0$, we see that $(x,y)=(0,0)$ is a solution since $P(0,0) = 0$
Induction step: If a solution (i.e. some $(x_1,y_1) \in \mathbb{N}_0^2$ such that $P(x_1,y_1) = z$) exists for a non-negative integer $z$, then a solution will also exist for $P(x,y) = z+1$. This can be proved as follows.

Case 1: $y_1=0$, i.e. $P(x_1, 0) = z$. Then consider $x=0, y = x_1+1$. $P(x,y) = P(0, x_1+1) = \dfrac{1}{2}((0+x_1+1)^2 + 0 + x_1+1) = \dfrac{1}{2}(x_1^2 +3x_1+2) = \dfrac{1}{2}(x_1^2 +3x_1) + 1$.

(5.1)​

Since $P(x_1, 0)= z$, we have $z = \dfrac{1}{2}(x_1^2 + 3x_1)$

(5.2)​

Combining equations (5.1) and (5.2), we see that $P(0, x_1+1) = P(x_1,0) + 1 = z+1$, i.e. $(0, x_1+1) \xrightarrow{P} z+1$, proving that a solution exists for $z+1$ too.

Case 2: $y_1 > 0$. Then consider $x=x_1+1, y = y_1 - 1$.
$P(x_1+1, y_1-1) = \dfrac{1}{2} \left( (x_1+1+y_1-1)^2 + 3(x_1+1) + (y_1-1) \right)$
$= \dfrac{1}{2} \left( (x_1+y_1)^2 + 3x_1 + y_1 \right) + 1$

(6.1)​

Since $P(x_1,y_1)=z$, we have $z = \dfrac{1}{2}\left( (x_1+y+1)^2 + 3x_1 + y_1 \right)$

(6.2)​

Comparing or combining equations (6.1) and (6.2), we see that $P(x_1+1, y_1-1) = P(x_1,y_1) + 1 = z+1$, i.e. $(x_1+1,y_1-1) \xrightarrow{P} z+1$, proving that a solution exists for $z+1$ too.

Thus, by the method of induction, it is proven that a solution for $P(x,y)=z$ (with $(x,y) \in \mathbb{N}_0^2$) exists for every non-negative integer $z$. This establishes that $\mathbb{N}_0^2 \xrightarrow{P} \mathbb{N}$ is an onto function.

(7)​

From (4) and (7) it follows that $P(x,y)$ defined over $\mathbb{N}_0^2$ is an one-to-one and onto function mapping $\mathbb{N}_0^2$ to $\mathbb{N}$ and is therefore a bijection.

Surjectivity (onto) looks correct.

 

[Not anonymous]

You may assume (by exchange of the numbering) that $x_2 = x_1 + a$ with $a \geq 0$.

Yes, that, and the requirement that the domain points be drawn from $\mathbb{N}_0^2$, and a property of the polynomial $P(x, y)$, are the bases on which I said that the 2nd point ($(x_2, y_2)$) would be of the form $(x_1 + a, y_1 - b)$ with $a, b \in \mathbb{N}$.

I do not see why $b \in [1, y_1]$. But then $y_2$ could be anything, i.e. $y_2 = y_1 + b$ with $b \in \mathbb{Z}$. All I can see is, that you may assume that $a$ and $b$ cannot be zero at the same time. But e.g. all values $(a,b) \in \{(0,1), (1,-1), (1,0), (1,1)\}$ could appear. At least I do not see why not.

If we have 2 points with the same image under $P$, then without loss of generality, we may take the one with the smaller value of $x$ to be $(x_1, y_1)$ and state that the other point, $(x_2, y_2)$ can be related to the first point by $(x_2, y_2) = (x_1+a, y_1-b)$ for some $a, b \in \mathbb{Z}$. I hope it should be obvious that $a, b$ must be integers (not restricted to be non-negative as yet) because of $x_1, y_1, x_2, y_2 \in \mathbb{N}_0$. What I need to clarify further is why $a, b$ must be non-negative integers.

I had already mentioned why both $a$ and $b$ must be non-zero, and I will elaborate on that first for clarity. That $a$ and $b$ cannot be zero at the same time should be obvious from the fact that if $a=0 \land b=0$, then we end up with $(x_2, y_2) = (x_1, y_1)$, violating the requirement that the 2 points be distinct. That neither one of $a$ and $b$ can be zero even if the other is zero can be shown as follows. Suppose $a \neq 0, b = 0$. Then $P(x_2, y_2) = \dfrac{1}{2}\left( (x_1+a+y_1)^2 + 3(x_1+a) + y_1) \right)$
$= \dfrac{1}{2}\left( (x_1+y_1)^2 + a^2 + 2a(x_1+y_1) + 3(x_1+a) + y_1) \right)$
$= P(x_1, y_1) + \dfrac{1}{2}(a^2 + 2a(x_1+y_1) + 3a)$

(8.1)​

Since we denoted the point with the smaller value of $x$ as $(x_1, y_1)$, it must be clear that $a > 0$. But this would mean that in equation (8.1), $P(x_2, y_2) > P(x_1, y_1)$, contradicting the assumption that $P(x_2, y_2) = P(x_1, y_1)$. Hence $b$ must be non-zero whenever $a$ is non-zero.

(8.2)​

Next, suppose $a=0, b \neq 0$.
Then $P(x_2, y_2) = \dfrac{1}{2}\left( (x_1+y_1-b)^2 + 3x_1 + y_1 - b) \right)$
$= \dfrac{1}{2}\left( (x_1+y_1)^2 + b^2 - 2b(x_1+y_1) + 3x_1 + y_1 - b) \right)$
$= P(x_1, y_1) + \dfrac{1}{2}(b^2 - 2b(x_1+y_1) - b)$

(9)​

If $b < 0$, then $(b^2 - 2b(x_1+y_1) - b) > 0$ (using the fact that $(x_1+y_1) \geq 0$ always as $x_1, y_1$ are non-negative integers) and in equation (9) this would lead to $P(x_2, y_2) > P(x_1, y_1)$, contradicting the assumption that $P(x_2, y_2) = P(x_1, y_1)$. Hence $b$ must be a positive integer regardless of the value of $a$.

(10)​

A more intuitive explanation of (10) is that $b < 0$ means $y_2 > y_1$ and since we already have $x_2 > x_1$, this leads to $P(x_2, y_2) > P(x_1, y_1)$ since $P$ is a strictly increasing function over $\mathbb{N}_0^2$.

That $b \leq y_1$ arises because otherwise $y_2 = y_1-b$ would be negative, a violation of the requirement that $y_2 \in \mathbb{N}_0$. Putting this together with the above observations, we see that $a, b > 0$ (to be more precise, belong to $\mathbb{N}$), and $b \in [1, y_1]$.

 

[fresh_42]

since $P$ is a strictly increasing function over $\mathbb{N}_0^2$.

This is the essential statement! It already means that $P$ is injective in the first quadrant. It is what had to be shown.

 

[Not anonymous]

We may assume that he automatically agrees if $x_i = 0$, that $X_i$ is closed, and that there is always at least one person which agrees to a given partition

1. What does "$X_i$ is closed" mean in the context of partitions? I am aware of open and closed intervals and open and closed sets whose elements are ranges, but I am unable to relate these to partitions of the form mentioned in the question ... since $x_i$'s in any of these partition are singleton real numbers, not ranges, I don't get how the possibility of an open set would arise in the first place.
2. Does each worker accept or reject a partition based only on the workload assigned to him and so will not bother about the remaining workload is distributed among others?
3. If the answer to the previous doubt is yes, then is it also implicitly implied that that if worker accepts a partition where his workload is some $w > 0$, then he will accept any other partition where his workload is less than $w$? If this is indeed the case, then I think I can see how intervals are involved.

 

[fresh_42]

1. What does "$X_i$ is closed" mean in the context of partitions? I am aware of open and closed intervals and open and closed sets whose elements are ranges, but I am unable to relate these to partitions of the form mentioned in the question ... since $x_i$'s in any of these partition are singleton real numbers, not ranges, I don't get how the possibility of an open set would arise in the first place.

It only says that the boundaries are feasible points, i.e. $x_i=0$ is allowed.

2. Does each worker accept or reject a partition based only on the workload assigned to him and so will not bother about the remaining workload is distributed among others?

Yes.

3. If the answer to the previous doubt is yes, then is it also implicitly implied that that if worker accepts a partition where his workload is some $w > 0$, then he will accept any other partition where his workload is less than $w$? If this is indeed the case, then I think I can see how intervals are involved.

Yes.

 

[sysprog]

10. Prove that $\pi^2$ is irrational.

According to Leonhard Euler (announced in 1785, fully proven in 1741):
$$\frac {\pi^2} 6 = \frac 1 {1^2} + \frac 1 {2^2} + \frac 1 {3^2} + \frac 1 {4^2} + \frac 1 {5^2} \dots$$
This equality shows that $\pi^2$ is not algebraic, wherefore it is transcendental, and therefore irrational.

 

[fresh_42]

This equality shows that $\pi^2$ is not algebraic

It does not: $1=\dfrac{1}{2}+\dfrac{1}{4}+\dfrac{1}{8}+\ldots$ but $1$ is certainly algebraic.

 

[sysprog]

It does not: $1=\dfrac{1}{2}+\dfrac{1}{4}+\dfrac{1}{8}+\ldots$ but $1$ is certainly algebraic.

I was merely digesting from a Wikipedia article: https://en.wikipedia.org/wiki/Basel_problem#The_proof
e.g.

Consequences of Euler's proof​

By Euler's proof for

explained above and the extension of his method by elementary symmetric polynomials in the previous subsection, we can conclude that ##{\displaystyle

is always a rational multiple of

. Thus compared to the relatively unknown, or at least unexplored up to this point, properties of the odd-indexed zeta constants, including Apéry's constant

, we can conclude much more about this class of zeta constants. In particular, since ${\pi}$ and integer powers of it are transcendental, we can conclude at this point that

is irrational, and more precisely, transcendental for all

.

 

[Office_Shredder]

I'm pretty sure that statement is using the fact that $\pi$ is transcendental to conclude that $\zeta(2k)$ is transcendental. Nothing has been done on that page to prove this fact.

 

[fresh_42]

The proof of transcendence is not difficult but quite tricky and long. That's why I asked to prove $\pi\not\in\mathbb{Q}$ which is a lot easier.

The transcendence of $\pi$ was first proven by Lindemann in 1882
http://www.digizeitschriften.de/dms/img/?PID=GDZPPN002246910
which is a century later than Euler's formula. This means that either the entire mathematical world failed to see the corollary for one hundred years, or that Euler did not imply the transcendence of $\pi$. Another proof which uses the Gamma function and following Hilbert can be found on
https://de.wikibooks.org/wiki/Beweisarchiv:_Algebra:_Körper:_Transzendenz_von_e_und_π

 

[Not anonymous]

It only says that the boundaries are feasible points, i.e. $x_i=0$ is allowed.

Yes.

Yes.

Thanks for the clarifications. I am attempting to solve the problem based on these. I am not sure if the proof is rigorous enough to qualify as an acceptable solution, but I hope that at least the logic I use is not way off the mark.

Spoiler: Question 2

Let $w_i$ denote the maximum workload accepted by worker $i$, i.e. $w_i = \max\limits_{x \in X_i} x_i \, \forall i \in \{1, 2, ..., n\}$.

Now consider the partition $T \in S$ defined as follows:
$T := (w_1, \min (w_2, 1-w_1), \min (w_3, 1-(w_1+w_2)), ..., T_n = 1-\sum_{i=1}^{n-1} T_i)$ with
$T_i = \min (w_i, 1-\sum\limits_{j=1}^{i-1} T_j) \, \forall i = 2, 3, ..., n-1$ where $T_i$ is the workload assigned to worker $i$ by partition $T$. In simple terms, $T$ assigns to worker 1 the max workload acceptable to him, then sequentially distributes remaining workload among workers 2 to $n-1$ such that each of those workers get either the whole of the pending workload at point (i.e. the balance remaining after assignment up to previous worker) or the maximum workload acceptable to them, whichever is minimum (so that the assigned workload is accepted by all of them) and finally assigns the entire remaining balance workload to the last worker, worker $n$.

Based on the way it is defined, it should be obvious that $T \in X_i \, \forall i=1, 2, ..., n-1$, i.e. the partition is accepted by workers $1$ to $n-1$. We need to show that $T \in X_n$ too.

Suppose $T \notin X_n$. Then $T_n > 0$ (since otherwise worker $n$ would have accepted it, as every worker accepts a partition where he is assigned no work).

$T_n > 0 \Rightarrow \sum\limits_{i=1}^{n-1} T_i < 1 \Rightarrow \sum\limits_{i=1}^{k} T_i < 1 \, \, , \forall k = 1, 2, ..., n-1$

(1)​

But (1) implies $w_k < 1 - \sum_{i=1}^{k-1} T_i \, \, , \forall k = 1, 2, ..., n-1$

(2)​

because otherwise there would exist some $k \in \{1, 2, .., n-1\}$ such that $w_k \geq 1 - \sum\limits_{i=1}^{k-1} T_i$ and this would imply
$T_k = \min (w_k, 1 - \sum\limits_{i=1}^{k-1} T_i) = 1 - \sum\limits_{i=1}^{k-1} T_i$, which in turn leads to
$\sum_{i=1}^{k} T_i = \sum\limits_{i=1}^{k-1} T_i + (1 - \sum\limits_{i=1}^{k-1} T_i) =$ and this contradicts condition (1).

Therefore partition $T$ must be equivalent to $\left(w_1, w_2, ..., w_{n-1}, T_n \right)$ with $T_n = (1 - \sum\limits_{i=1}^{n-1} w_i)$

(3)​

$T \notin X_n \Rightarrow T_n > w_n \Rightarrow (T_n - w_n) > 0$

(4)​

Now consider another partition $T' \in S$ defined in terms of $T$ as follows:
$T' = (w_1 + \dfrac{\delta}{n-1}, w_2 + \dfrac{\delta}{n-1}, \ldots, w_{n-1}+ \dfrac{\delta}{n-1}, T_n - \delta)$ where $\delta$ is any arbitrarily chosen real number such that $0 < \delta < (T_n - w_n)$.

Clearly, $T' \notin X_i$ for any $i \in \{1, 2, ..., n-1, n\}$ since $T'_i = w_i + \dfrac{\delta}{n-1} > w_i$ making the partition is unacceptable to workers $1$ to $n-1$ and $T'_n = T_n - \delta > w_n$ making the partition unacceptable to worker $n$ too. But this contradicts the fact/precondition that $\bigcup_{i=1}^n X_i = S$. Thus our assumption that $T \notin X_n$ must be incorrect. And it therefore follows that $T \in X_i \, \forall i \in \{1, 2, ..., n\}$, i.e. we have at least one partition in $S$ that is acceptable to all workers.

 

[Not anonymous]

15. Find all real numbers $m \in \mathbb{R}$, such that for all real numbers $m \in \mathbb{R}$ holds$$
f(x,m) := x^2 + (m+2)x + 8m + 1 > 0 \, \, \, \, \, \,(*)
$$
and determine the value of $m$ for which the minimum of $f(x,m)$ is maximal. What is the maximum?

Spoiler: Question 15

If $f(x,m)$ is greater than 0 for all values of $x$, then the global minimum of $f(x,m)$ (for a fixed value of $m$) too should be greater than 0. To find the minimum of $f(x,m)$ for a fixed value of $m$, we equate the partial derivative w.r.t. $x$ to 0.

At the extremum points (with $x$ being the variable),
$\dfrac {\partial f} {\partial x} = 2x + m + 2 = 0 \Rightarrow x = \dfrac {-(m+2)} {2}$

(1)​

Since $\dfrac {\partial^2 f} {\partial x^2} = 2 > 0$ for all values of $x$, the extremum point(s) given by equation (1) must be minimal points, not maxima. Thus, the minimum value of $f(x,m)$ for a fixed $m$ is $f(\frac {-(m+2)} {2}, m) = \dfrac {28m - m^2} {4}$

(2)​

Since we want the minimum, given by equation (2), to be greater than 0, we get
$\dfrac {28m - m^2} {4} > 0 \Rightarrow m(28-m) > 0 \Rightarrow m \in (0, 28)$

(3)​

From equation (3) it follows that for $f(x,m) > 0$ for all $x$ if and only if $m$ is any real number in the range $(0, 28)$.

To find the value of $m$ or which the minimum of $f(x,m)$ is maximal, we start with equation (2) and take its derivative w.r.t. $m$. For convenience, we denote the minimum of $f(x,m)$ (for a fixed $m$) given by equation (2) as $g(m)$, i.e. $g(m) = \dfrac {28m - m^2} {4}$.

$g'(m) = 0 \Rightarrow \dfrac {28 - 2m}{4} = 0 \Rightarrow m = 14$

(4)​

Since $g''(m) = -\dfrac{1}{2} < 0$ for all values of $m$, the extremum point given by equation (4) must be a maximal point, not a minimum.

Thus the maximum of the minimal value of $f(x,m)$ taken across all values of $m$ that satisfy the condition/inequality (*) stated in the question is $g(14) = 49$

 

[fresh_42]

Thanks for the clarifications. I am attempting to solve the problem based on these. I am not sure if the proof is rigorous enough to qualify as an acceptable solution, but I hope that at least the logic I use is not way off the mark.

Let $w_i$ denote the maximum workload accepted by worker $i$, i.e. $w_i = \max\limits_{x \in X_i} x_i \, \forall i \in \{1, 2, ..., n\}$.

Now consider the partition $T \in S$ defined as follows:
$T := (w_1, \min (w_2, 1-w_1), \min (w_3, 1-(w_1+w_2)), ..., T_n = 1-\sum_{i=1}^{n-1} T_i)$ with
$T_i = \min (w_i, 1-\sum\limits_{j=1}^{i-1} T_j) \, \forall i = 2, 3, ..., n-1$ where $T_i$ is the workload assigned to worker $i$ by partition $T$.

You have to prove $T\in S$ because it is not true without additional assumptions. Consider the following situation with $n=3$:

Set $(w_1,w_2,w_3):=(0.3\, , \,0.8\, , \,0.3)$ then $T=(0.3\, , \,0.7\, , \,-0.1) \not\in S.$ But even in case $T\in S,$ e.g. for $(w_1,w_2,w_3):=(0.3\, , \,0.3\, , \,0.8)$ with $T=(0.3\, , \,0.3\, , \,0.4)\in S$ you do not get the solution, which is the black dot at $(0.1\, , \,0.1\, , \,0.8).$

In simple terms, $T$ assigns to worker 1 the max workload acceptable to him, then sequentially distributes remaining workload among workers 2 to $n-1$ such that each of those workers get either the whole of the pending workload at point (i.e. the balance remaining after assignment up to previous worker) or the maximum workload acceptable to them, whichever is minimum (so that the assigned workload is accepted by all of them) and finally assigns the entire remaining balance workload to the last worker, worker $n$.

Based on the way it is defined, it should be obvious that $T \in X_i \, \forall i=1, 2, ..., n-1$, i.e. the partition is accepted by workers $1$ to $n-1$. We need to show that $T \in X_n$ too.

Suppose $T \notin X_n$. Then $T_n > 0$ (since otherwise worker $n$ would have accepted it, as every worker accepts a partition where he is assigned no work).

$T_n > 0 \Rightarrow \sum\limits_{i=1}^{n-1} T_i < 1 \Rightarrow \sum\limits_{i=1}^{k} T_i < 1 \, \, , \forall k = 1, 2, ..., n-1$

(1)​

But (1) implies $w_k < 1 - \sum_{i=1}^{k-1} T_i \, \, , \forall k = 1, 2, ..., n-1$

(2)​

because otherwise there would exist some $k \in \{1, 2, .., n-1\}$ such that $w_k \geq 1 - \sum\limits_{i=1}^{k-1} T_i$ and this would imply
$T_k = \min (w_k, 1 - \sum\limits_{i=1}^{k-1} T_i) = 1 - \sum\limits_{i=1}^{k-1} T_i$, which in turn leads to
$\sum_{i=1}^{k} T_i = \sum\limits_{i=1}^{k-1} T_i + (1 - \sum\limits_{i=1}^{k-1} T_i) =$ and this contradicts condition (1).

Therefore partition $T$ must be equivalent to $\left(w_1, w_2, ..., w_{n-1}, T_n \right)$ with $T_n = (1 - \sum\limits_{i=1}^{n-1} w_i)$

(3)​

$T \notin X_n \Rightarrow T_n > w_n \Rightarrow (T_n - w_n) > 0$

(4)​

Now consider another partition $T' \in S$ defined in terms of $T$ as follows:
$T' = (w_1 + \dfrac{\delta}{n-1}, w_2 + \dfrac{\delta}{n-1}, \ldots, w_{n-1}+ \dfrac{\delta}{n-1}, T_n - \delta)$ where $\delta$ is any arbitrarily chosen real number such that $0 < \delta < (T_n - w_n)$.

Clearly, $T' \notin X_i$ for any $i \in \{1, 2, ..., n-1, n\}$ since $T'_i = w_i + \dfrac{\delta}{n-1} > w_i$ making the partition is unacceptable to workers $1$ to $n-1$ and $T'_n = T_n - \delta > w_n$ making the partition unacceptable to worker $n$ too. But this contradicts the fact/precondition that $\bigcup_{i=1}^n X_i = S$. Thus our assumption that $T \notin X_n$ must be incorrect. And it therefore follows that $T \in X_i \, \forall i \in \{1, 2, ..., n\}$, i.e. we have at least one partition in $S$ that is acceptable to all workers.

I do not know an algorithm, but my indirect solution per Brouwer's fixed point theorem is a bit tricky, so I assume that it is difficult to find a constructive proof for any dimension.

 

[Office_Shredder]

I'm a bit confused by #2. You said in post 18 of the thread that a worker will accept any partition based only on the workload assigned to them (which the original problem description didn't seem to include at all). So if $(w_1,w_2,w_3)=(0.3,0.3,0.8)$, it sounds like $(0.3,0.3,0.4)$ is in fact an acceptable solution, along with a literal infinitude of other solutions. Are you sure this clarification is correct? I feel like it makes the problem trivially easy, and it is not needed in two dimensions at least.

I'm not really sure how to read the picture you drew, but I suspect it does not conform with post #18 (and that would make me happy to learn #18 is wrong)

 

[Not anonymous]

Set $(w_1, w_2, w_3) := (0.3, 0.8, 0.3)$ then $T = (0.3, 0.8, -0.1) \notin S$.

Sorry, there was a mistake in the first part of definition of $T$ in my previous post, more specifically in the value of $T_3$ which is not in accordance with the definition of $T_i$ given subsequently. Please read that as:
$T := (w_1, \min (w_2, 1-w_1), \min (w_3, 1-(T_1+T_2)), ..., T_n = 1 - \sum\limits_{i=1}^{n-1} T_i)$ with $T_i = \min (w_i,\sum\limits_{j=1}^{i-1} T_j) \, \, \forall i = 2, 3, \ldots, n-1$. The more verbal explanation I gave for $T$ in that same post too is in accordance with the correct definition. With the correct definion of $T$, $(w_1, w_2, w_3) := (0.3, 0.8, 0.3)$ will yield $T = (0.3, 0.7, 0) \in S$, not $T = (0.3, 0.8, -0.1)$. I apologize for the silly mistake that caused the confusion.

But even in case $T \in S$, e.g. for $(w_1, w_2, w_3) := (0.3, 0.3, 0.8)$ with $T = (0.3, 0.3, 0.4) \in S$ you do not get the solution, which is the black dot at $(0.1, 0.1, 0.8)$.

Sorry, I do not understand why only $(0.1, 0.1, 0.8)$ is a solution but not $(0.3, 0.3, 0.4)$. One of the doubts I asked before attempting to solve this question was whether it could be assumed that "if a worker accepts a partition where his workload is some $w > 0$, then he will accept any other partition where his workload is less than $w$" and you replied with a yes. So if $(w_1, w_2, w_3) := (0.3, 0.3, 0.8)$, why wouldn't $T = (0.3, 0.3, 0.4) \in S$ be a partition that is acceptable to all 3 workers? After all, the workload assignment of $T$ equals but does not exceed the maximum acceptable workloads for workers 1 and 2 and is below the max workload for worker 3, so why would any of them reject $T$? I don't see why there would always be only one partition that is acceptable to all workers. So for $(w_1, w_2, w_3) := (0.3, 0.3, 0.8)$, I view both $(0.3, 0.3, 0.4)$, $(0.1, 0.1, 0.8)$ as being partitions acceptable to all workers (and there would be countless more such acceptable-to-all-workers partitions in this case, such as for e.g. $(0.15, 0.15, 0.7) \in S$, $(0.299, 0.299, 0.402) \in S$, $(0.2991, 0.2991, 0.4018) \in S$ and so on).

 

[fresh_42]

I'm a bit confused by #2. You said in post 18 of the thread that a worker will accept any partition based only on the workload assigned to them (which the original problem description didn't seem to include at all).

Yes, the third point in post #18 is wrong. Every worker has his own set of feasible points regardless of the others. These sets don't have to be convex or even connected. The crucial point is that $x_i=0$ are part of these sets of feasible partitions.

3. If the answer to the previous doubt is yes, then is it also implicitly implied that that if worker accepts a partition where his workload is some $w>0$, then he will accept any other partition where his workload is less than w? If this is indeed the case, then I think I can see how intervals are involved.

This is not necessary.

We have only two conditions: the work has to be done $\cup X_i=S$ and nothing to do at all $x_i=0$ will be accepted.

So if $(w_1,w_2,w_3)=(0.3,0.3,0.8)$, it sounds like $(0.3,0.3,0.4)$ is in fact an acceptable solution, along with a literal infinitude of other solutions. Are you sure this clarification is correct? I feel like it makes the problem trivially easy, and it is not needed in two dimensions at least.

I'm not really sure how to read the picture you drew, but I suspect it does not conform with post #18 (and that would make me happy to learn #18 is wrong)

$(0.3,0.3,0.4) \not\in X_1\cup X_2$.

 

[Not anonymous]

Yes, the third point in post #18 is wrong. Every worker has his own set of feasible points regardless of the others. These sets don't have to be convex or even connected.

Okay, that makes the problem harder and I will need to think afresh to come up with an answer, if at all it is solvable using only concepts I have learned up to high school and just a little beyond.

 

[fresh_42]

Okay, that makes the problem harder and I will need to think afresh to come up with an answer. Thanks again for clarifying.

I'm not sure whether this is right. In my example, we have the point $(0.1,0.1,0.8)$ as the only solution where all three workers agree upon. A solution $T=(0.3,0.3,0.4)$ isn't possible even if workers agree on less workload. Only $Z$ would have less work, $X,Y$ have more and so wouldn't agree on $T$.

 

[George Keeling]

Does

(open)

mean that anybody can have a go?

 

[fresh_42]

Does

mean that anybody can have a go?

No. It means that the problems for high schoolers are relatively easy and I wanted to add a bonus round for them with a bit more complicated questions. It was an attempt to attract more kids.

The label 'open' only indicates which parts have still to be solved (by high schoolers). It was necessary because people could solve one part but don't solve the 'Extra' part, and theoretically vice versa.

 

[Not anonymous]

13. (open) If $(x_n)_{n \in \mathbb{N}} \subseteq \mathbb{R}_{>0}$ is a monotone decreasing sequence of positive real numbers such that for every $n \in \mathbb{N}$ $$
\dfrac{x_1}{1} + \dfrac{x_4}{2} + \dfrac{x_9}{3} + ... + \dfrac{x_{n^2}}{n} \leq 1
$$
prove that for every $n \in \mathbb{N}$ $$
\dfrac{x_1}{1} + \dfrac{x_2}{2} + \dfrac{x_3}{3} + ... + \dfrac{x_n}{n} \leq 3
$$

Spoiler: Question 13

Let us denote the 2 sequence summations by $S_n$ and $T_n$ for any $n \in \mathbb{N}$, i.e. $$S_n := \dfrac{x_1}{1} + \dfrac{x_4}{2} + \dfrac{x_9}{3} + ... + \dfrac{x_{n^2}}{n}$$ and
$$T_n := \dfrac{x_1}{1} + \dfrac{x_2}{2} + \dfrac{x_3}{3} + ... + \dfrac{x_n}{n}$$

Then, $$
T_{(n+1)^2-1} = \sum_{i=1}^{n} \sum_{j=i^2}^{(i+1)^2-1} \dfrac{x_j}{j} = \sum_{i=1}^{n} \dfrac{x_{i^2}}{i^2} + \sum_{i=1}^{n} \sum_{j=i^2+1}^{(i+1)^2-1} \dfrac{x_j}{j}
$$

(1)​

$$
\sum_{i=1}^{n} \dfrac{x_{i^2}}{i^2} \leq \sum_{i=1}^{n} \dfrac{x_{i^2}}{i} = S_n
$$

(2)​

Since $(x_n)_{n \in \mathbb{N}}$ is a strictly decreasing sequence of positive numbers, $\dfrac{x_j}{j} < \dfrac{x_{i^2}}{i^2}$ if for any $i, j \in \mathbb{N}$ with $j > i^2$. Therefore,
$$
\sum_{j=i^2+1}^{(i+1)^2-1} \dfrac{x_j}{j} < \sum_{j=i^2+1}^{(i+1)^2-1} \dfrac{x_{i^2}}{i} = ((i+1)^2-1-i^2)\dfrac{x_{i^2}}{i^2} = 2i \dfrac{x_{i^2}}{i^2} = \dfrac{2x_{i^2}}{i}

\Rightarrow \sum_{i=1}^{n} \sum_{j=i^2+1}^{(i+1)^2-1} \dfrac{x_j}{j} < 2S_n
$$

(3)​

Using equations/inequalities (2) and (3) in (1), we get $T_{(n+1)^2-1} < S_n + 2S_n \equiv 3S_n$ for any positive integer $n$. And since $T_j > T_i$ for any $j > i$ (since $T_n$ is a sum of a sequence consisting of only positive numbers), it follows that $T_n < T_{(n+1)^2-1} < 3S_n$ for any $n \in \mathbb{N}$.

(4)​

And since it is given that $S_n \leq 1$ for any $n$, (4) implies that $T_n < 3$ for any $n$, which is equivalent to saying that $\dfrac{x_1}{1} + \dfrac{x_2}{2} + \dfrac{x_3}{3} + ... + \dfrac{x_n}{n} < 3$ for any $n$. Hence proved.

 

[fresh_42]

Spoiler: Question 13

Let us denote the 2 sequence summations by $S_n$ and $T_n$ for any $n \in \mathbb{N}$, i.e. $$S_n := \dfrac{x_1}{1} + \dfrac{x_4}{2} + \dfrac{x_9}{3} + ... + \dfrac{x_{n^2}}{n}$$ and
$$T_n := \dfrac{x_1}{1} + \dfrac{x_2}{2} + \dfrac{x_3}{3} + ... + \dfrac{x_n}{n}$$

Then, $$
T_{(n+1)^2-1} = \sum_{i=1}^{n} \sum_{j=i^2}^{(i+1)^2-1} \dfrac{x_j}{j} = \sum_{i=1}^{n} \dfrac{x_{i^2}}{i^2} + \sum_{i=1}^{n} \sum_{j=i^2+1}^{(i+1)^2-1} \dfrac{x_j}{j}
$$

(1)​

$$
\sum_{i=1}^{n} \dfrac{x_{i^2}}{i^2} \leq \sum_{i=1}^{n} \dfrac{x_{i^2}}{i} = S_n
$$

(2)​

Since $(x_n)_{n \in \mathbb{N}}$ is a strictly decreasing sequence of positive numbers, $\dfrac{x_j}{j} < \dfrac{x_{i^2}}{i^2}$ if for any $i, j \in \mathbb{N}$ with $j > i^2$. Therefore,
$$
\sum_{j=i^2+1}^{(i+1)^2-1} \dfrac{x_j}{j} < \sum_{j=i^2+1}^{(i+1)^2-1} \dfrac{x_{i^2}}{i} = ((i+1)^2-1-i^2)\dfrac{x_{i^2}}{i^2} = 2i \dfrac{x_{i^2}}{i^2} = \dfrac{2x_{i^2}}{i}

\Rightarrow \sum_{i=1}^{n} \sum_{j=i^2+1}^{(i+1)^2-1} \dfrac{x_j}{j} < 2S_n
$$

(3)​

Using equations/inequalities (2) and (3) in (1), we get $T_{(n+1)^2-1} < S_n + 2S_n \equiv 3S_n$ for any positive integer $n$. And since $T_j > T_i$ for any $j > i$ (since $T_n$ is a sum of a sequence consisting of only positive numbers), it follows that $T_n < T_{(n+1)^2-1} < 3S_n$ for any $n \in \mathbb{N}$.

(4)​

And since it is given that $S_n \leq 1$ for any $n$, (4) implies that $T_n < 3$ for any $n$, which is equivalent to saying that $\dfrac{x_1}{1} + \dfrac{x_2}{2} + \dfrac{x_3}{3} + ... + \dfrac{x_n}{n} < 3$ for any $n$. Hence proved.

Right. But let me add a shorter version (with the same ideas):

For every natural number $n$ there is a number $k\in \mathbb{N}$ such that $k^2\leq n<(k+1)^2.$ Hence
\begin{align*}
\sum_{i=1}^n \dfrac{x_i}{i}&\leq\sum_{i=2}^{k+1} \sum_{j=(i-1)^2}^{i^2-1}\dfrac{x_j}{j}\leq \sum_{i=2}^{k+1} \left(2i-1\right)\dfrac{x_{(i-1)^2}}{(i-1)^2}\\&=\sum_{i=1}^k (2i+1)\dfrac{x_{i^2}}{i^2}
\leq 3\sum_{i=1}^k \dfrac{x_{i^2}}{i}\leq 3\cdot 1 =3
\end{align*}
by the given condition.