# Math Challenge - October 2021

• Challenge
• fresh_42
• Featured
In summary, the conversation covers various mathematical topics such as functional analysis, project management, set theory, group theory, Lie theory, countability, Banach algebra, stochastic, function theory, and calculus. The problems discussed include proving the compactness of a function space, finding a partition that all workers agree upon in project management, using the axiom schema of separation to prove the cardinality of a set is less than its power set, showing the linear independence of homomorphisms in a field, proving the nilpotency of general Heisenberg algebras, establishing the bijection of a polynomial function, proving the non-emptiness of the spectrum in a complex Banach algebra, using probability to show the upper bound of
fresh_42
Staff Emeritus
2023 Award
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*}
\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*}
\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.

Last edited:
#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##?

Office_Shredder said:
#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.
Office_Shredder said:
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##.

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

nuuskur, MathematicalPhysicist and fresh_42
#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

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.

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

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.

Last edited by a moderator:
docnet and fresh_42
Office_Shredder said:
Alright I'll try #5 assuming I found the correct definition of the general Heisenberg lie algebra.

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.

#6
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

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
Office_Shredder said:
#6
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

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 said:
#6
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

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.

docnet
What does surjectivity by foot mean?

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

Office_Shredder said:
What does surjectivity by foot mean?
Step by step starting with ##P(x,0)## and ##P(0,y)##, the diagonal argument by formulas.
Office_Shredder said:
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}.##

Last edited:
fresh_42 said:
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.

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.

docnet
Not anonymous said:
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.

Not anonymous said:
##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.

docnet
fresh_42 said:
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}##.

fresh_42 said:
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]##.

docnet
Not anonymous said:
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.

fresh_42 said:
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.

Not anonymous said:
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.
Not anonymous said:
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.
Not anonymous said:
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.

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.

sysprog said:
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.

fresh_42 said:
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
.

Last edited:
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_π

Last edited:
sysprog
fresh_42 said:
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.

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.

fresh_42 said:
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?

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##

ANB3010
Not anonymous said:
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).##
Not anonymous said:
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.

Last edited:
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)

fresh_42 said:
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.

fresh_42 said:
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).

Office_Shredder said:
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.
Not anonymous said:
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.

Office_Shredder said:
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##.

fresh_42 said:
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.

Not anonymous said:
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##.

Does
fresh_42 said:
(open)
mean that anybody can have a go?

George Keeling said:
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.

Last edited:
George Keeling and berkeman
fresh_42 said:
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$$

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.

Not anonymous said:
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.

Replies
100
Views
8K
Replies
86
Views
10K
Replies
114
Views
7K
Replies
93
Views
12K
Replies
61
Views
7K
Replies
42
Views
7K
Replies
60
Views
9K
Replies
56
Views
8K
Replies
67
Views
8K
Replies
33
Views
7K