Challenge Math Challenge - April 2019

QuantumQuest

Gold Member
If the prisoners are killed immediately if even one walks up incorrectly even once,...
Isn't this obvious from the wording of the question?

In order to pass the test, all the prisoners with a black hat and only them, will have to step forward during the same line-up. If they succeed, all prisoners will be freed otherwise they will all be executed.
I think that the question states explicitly what is needed to be stated.

I think this bit is enough (you don't need the earlier work) since in the last product, the first integral converges iff $\alpha<1$ and the second does if $\alpha>1/2.$

You also seem to have confused which bound went with which variable of integration but as the integrand is symmetric in $x,y$, this is okay!

Nice work.
Is this function related to Riemann Zeta function in the critical strip?

ShreyJ

High School 5:
$$N=6210001000$$
Solution: I started at $N=8100000000$ and kept modifying the number until it stabilized.

Infrared

Gold Member
Is this function related to Riemann Zeta function in the critical strip?

Not that I'm aware of. Do you have something in mind?

wrobel

4.4. Let ff be a continuous element of L1((0,∞))L^1((0,\infty)). Suppose that x=x(t)x=x(t) solves the differential equation dxdt=−px+f(t)\frac{dx}{dt}=-px+f(t). Prove that limt→∞x(t)=0\lim_{t\to\infty}x(t)=0.
First it should be clarified what $p$ is. For example if $p=0$ then the assertion is wrong.
If $p=const>0$ then the proof is as follows.

$$x(t)=e^{-pt}x(0)+\int_0^te^{-p(t-s)}f(s)ds.$$ And we have
$$\int_0^te^{-p(t-s)}f(s)ds=\int_0^Te^{-p(t-s)}f(s)ds+\int_T^te^{-p(t-s)}f(s)ds.$$
Since $f\in L^1(\mathbb{R}_+)$ we see that for any $\varepsilon>0$ there exists $T^*>0$ such that for any $T>T^*$ and for any $t>T$ the following estimate holds
$$\Big|\int_T^te^{-p(t-s)}f(s)ds\Big|<\varepsilon.$$
On the other hand, with any fixed $T$ we have
$$\int_0^Te^{-p(t-s)}f(s)ds\to 0$$ as $t\to \infty$
There is no need to assume continuity of $f$.

Master1022

Here is my attempt at Highschool Problem 1(b). Not sure how rigorous my working needs to be, but here is my attempt.

We know that a minimum path must not include movements in more than one cardinal direction (eg. cannot move left and then later up) because that extra move is redundant and can be avoided by making diagonal moves. Thus, my plan is basically to move diagonally and in only one cardinal direction.

Let us fix our king at some arbitrary origin, and then let us draw lines that extend in the four 'cardinal' directions around the king. Here is a more qualitative description of the method first:
1. Set up boundary lines for your king emanating from his current position
2. For a given destination, evaluate whether it lies on any of the 4 boundary lines
- If it lies on a boundary line, then move in that respective direction and then go back to step 2
3. If not, see which quadrant the destination is in and move diagonally 1 move in that direction - then go back to one and repeat

e.g. path from (0,0) to (4,5): (0,0) --> (1,1) --> (2,2) --> (3,3) --> (4,4) --> (4,5)

Slightly more mathematical, but not much. Let us define a cartesian coordinate system such that the centre of each square is defined by a pair of integer coordinates $(x,y)$ and our King will start at $(0,0)$.

For a given destination $(a,b)$, let us assume that $a > b$. We will end up moving diagonally b times and then vertically $a - b$ times. Therefore, for destination $(a,b)$, we will only move $|a| - |b|+ |b| = |a|$ times.

This makes sense following on from part (a). Thinking about the possible squares (that the king can land after n moves) as an area of a square $(2n + 1)^2$ as written by fbs7 for the general n. For us to reach a square in the minimum number of moves $(n)$, we need $n$ such that it is the first square to include our destination point. This will only happen if $\textbf{n = number of moves = max(|a|,|b|)}$ for all n.

How do we know that this method yields a minimum path?
1. There are no redundant moves in two cardinal directions
2. There is not 1 shortest path, can flip around instructions of the 'algorithm' and will generate another version of the path.

Please let me know if this is insufficient (whether or not I have arrived at the correct answer). Many thanks in advance.

wrobel

5.5. Let f:S5→S3×S2f:S^5\to S^3\times S^2 be a smooth function. Show that ff takes critical values in any set of the form S3×{p}S^3\times\{p\} for p∈S2p\in S^2.
what if the whole sphere is mapped into a single point?

Master1022

Here is my attempt at Highschool problem 1(c).

Given that we cannot move diagonally, there are squares which we can only reach if the number of moves $n$ is even, and others that can only be reached when $n$ is odd.

For any $n$ moves, we know that the furthest squares that can be reached are all the squares whose coordinates $(a,b)$ are such that $|a| + |b| = n$. Drawing this out on a cartesian coordinate system draws out a rotated square, which makes sense from intuition. So we have dealt with the outermost squares, but now we need to deal with all squares within our region. So when $n$ is, for example, even (and greater than 0), it can only move in increments on 2 moves. Therefore, it will always remain on a square with the colour that it started with (helpful to picture a chess-board as in the question). For an odd $n$, the king will be forced to end on a square that is of a different colour to the one that it initially began in. The diagonal movement was able to act as effectively 2 moves, thus allowing the king to move to a square of the same colour.

Thus, the possible inner squares will be all the smaller rotated squares for any $n_i$ that is smaller than $n$ and returns the same result: $remainder(n,2) = remainder(n_i ,2)$ (not worrying about n = 0 at the moment). It can reach these smaller squares just by oscillating back and forth, between adjacent squares, if necessary.

Getting to some maths:
Splitting this into: for even n = 0:
the number of squares = 1

for even n > 0:
each new 'layer' will have $4n$ squares of possible destinations.

Thus, the total number of possible squares = $1 + \sum_{n=2}^n 4 n$, with the latter part forming the sum of an arithmetic sequence (a = 2, d = 2, $\lambda = n/2$). This can thus be re-written as $1 + 4 \times \frac{\lambda}{2}(2 + 2 \lambda) = \mathbf{ 1 + 4 \lambda(1 + \lambda)}$

For odd n > 0:
Following on from the same logic, basically, everything is the same as even numbers, except that it won't be able to return to its original square, so it won't have the extra +1. However, the formula for the arithmetic sequence needs to be redone:
let $\mu = \frac{n+1}{2}$
$number of squares = 4\sum_{n=1}^n n = 4 * \frac{\mu}{2}(2(1) + 2(\mu - 1)) = 4 \mu ^ 2 = \mathbf{(n+1)^2}$

In conclusion, for $n$ moves, $\lambda = n/2$, the king can move:
if n = 0: 1 square
if n > 0 and even: $1 + 4 \lambda(1 + \lambda)$ squares
if n > 0 and odd: $(n+1)^2$ squares

Infrared

Gold Member
@wrobel

Apologies, I forgot the crucial condition that $f$ is onto!

Mentor
2018 Award

QuantumQuest

Gold Member
Let us fix our king at some arbitrary origin, and then let us draw lines that extend in the four 'cardinal' directions around the king. Here is a more qualitative description of the method first:
1. Set up boundary lines for your king emanating from his current position
2. For a given destination, evaluate whether it lies on any of the 4 boundary lines
- If it lies on a boundary line, then move in that respective direction and then go back to step 2
3. If not, see which quadrant the destination is in and move diagonally 1 move in that direction - then go back to one and repeat
I see a good effort here but I can't visualize it in the exact way needed.

Let us define a cartesian coordinate system such that the centre of each square is defined by a pair of integer coordinates $(x,y)$ and our King will start at $(0,0)$ .

For a given destination $(a,b)$ , let us assume that $a > b$ . We will end up moving diagonally b times and then vertically $a - b$ times. Therefore, for destination $(a,b)$ , we will only move $|a| - |b|+ |b| = |a|$ times.

This makes sense following on from part (a). Thinking about the possible squares (that the king can land after n moves) as an area of a square $(2n + 1)^2$ as written by fbs7 for the general n. For us to reach a square in the minimum number of moves $(n)$ , we need $n$ such that it is the first square to include our destination point. This will only happen if n = number of $\textbf{n = number of moves = max(|a|,|b|)}$ for all n.
I don't ask for a rigorous way of describing the minimum number of moves required to reach a destination. I just ask for the optimal strategy for this, described as a number of steps. So, moving in the diagonal direction as you say, is the first step. Now, from what you write I see that you're on the right way for the next step but how can we describe it in simple words i.e. next, what is the move in order to reach the destination, independently of whether it is on the diagonal or not?

Master1022

I see a good effort here but I can't visualize it in the exact way needed.
Thank you for your response. I have attached a quick sketch to try to help visualise my thinking.

Edit: Please let me know if this is not legible

QuantumQuest

Gold Member
Here is my attempt at Highschool problem 1(c)...
For even $n \gt 0$ the number of squares is not correct. Check it again.

QuantumQuest

Gold Member
I have attached a quick sketch to try to help visualise my thinking.
Yes. So, again to my question: You're moving diagonally and if the destination is not on the diagonal, what is the next move?

Master1022

For even $n \gt 0$ the number of squares is not correct. Check it again.
Thank you for your response. Is the answer not $(n+1)^2$, which is equivalent to what I have written? I thought it would be this as it will be the total number of squares of the same colour as the starting square within our region of furthest possible squares.

Master1022

Yes. So, again to my question: You're moving diagonally and if the destination is not on the diagonal, what is the next move?
Thanks for your response. Maybe my steps weren't clear enough. However, to address your question, do we just move in one cardinal direction that will most quickly put us on a similar diagonal with the destination? However, isn't this method the same as the one as I outlined, with the steps just reversed?

Last edited:

QuantumQuest

Gold Member
However, to address your question, do we just move in one cardinal direction that will most quickly put us on a similar diagonal with the destination? However, isn't this method the same as the one as I outlined, with the steps just reversed?

Let's take it in a simple way. We are moving along a diagonal - whichever it is. If we meet our target (=destination) we're done. If not , there is a simple way to state what you do according to where is the destination relatively to the point on the diagonal that you are. That's all I ask. The way you describe it is as taking another diagonal etc. Is this the optimal way?

QuantumQuest

Gold Member
Is the answer not $(n+1)^2$ , which is equivalent to what I have written? I thought it would be this as it will be the total number of squares of the same colour as the starting square within our region of furthest possible squares.

each new 'layer' will have $4n$ squares of possible destinations.
For instance take $n = 2$. Then what you write means that starting from, say, a black square, the possible squares of the new layer, as you call it, will be $8$. Now I ask, is this premise correct?

EDIT: As a hint, if you take the next positive even integer i.e. $n = 4$ then what I ask above may be more evident.

Last edited:

Master1022

For instance take $n = 2$. Then what you write means that starting from, say, a black square, the possible squares of the new layer, as you call it, will be $8$. Now I ask, is this premise correct?

EDIT: As a hint, if you take the next positive even integer i.e. $n = 4$ then what I ask above may be more evident.
Thank you for your response. This is what I found for n = 2 and n = 4. Are you saying that I am missing some squares?

The outer layers seem to have 4n squares in them, so I will keep looking

QuantumQuest

Gold Member
@Master1022 as I check again High School problem $1 c$ I see that you mean that the total sum is $1$ plus a new layer (=possible positions) each time and the series is on even numbers, so you finally mean $(n + 1)^2$ but the way is written is more cumbersome than it needs to. So, what is the difference from $n$ being odd?

"Math Challenge - April 2019"

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving