Challenge Math Challenge - April 2019

[fresh_42]

As (almost) always: have a look on previous challenge threads, too. E.g. in https://www.physicsforums.com/threads/math-challenge-march-2019.967174/ are still problems to solve, and some of them easy, which I find, and in any case useful to know or at least useful to have seen.

As a general note due to a given cause: Please do not edit your posts after they have been answered!
This is in general - not only here - not acceptable, as it makes the threads unreadable and worst case change the entire meaning and thus disrespects the ones who answered! At most an additional commentary marked as "edit (1):" etc. could be added, but nothing within the text, except spell or comma mistakes.

Questions

$1.$ (solved by @SpinFlop ; see also here. ) There are $12$ prisoners who are given the chance to be freed if they pass this test: the warden will put a hat on the head of each prisoner which will be either black or white. The prisoners will get informed that there will be at least one hat of each color. They will be able to see everyone else's hat except their own. Also, there will be no sort of communication among prisoners. The prisoners will be lined up every five minutes starting at $10:00 \space\space a.m.$ and ending at $10:50 \space\space a.m.$ 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. Is there a way for the prisoners to pass the test?

$2.$ (solved by @lpetrich ) For which real numbers $\alpha$ does the improper integral $\int_0^1\int_{-\infty}^\infty\frac{1}{(x^2+y^2)^{\alpha}} dx dy$ converge.

$3.$ Let $a\in\mathbb{C}$ and define $s=t^3+3t^2+at\in\mathbb{C}(t)$. For which $a$ is $\mathbb{C}(t)/\mathbb{C}(s)$ a Galois extension?

$4.$ (solved by @wrobel ) Let $f$ be a continuous element of $L^1((0,\infty))$. Suppose that $x=x(t)$ solves the differential equation $\frac{dx}{dt}=-px+f(t)$. Prove that $\lim_{t\to\infty}x(t)=0$.

$5.$ Let $f:S^5\to S^3\times S^2$ be a smooth [edit: and surjective] function. Show that $f$ takes critical values in any set of the form $S^3\times\{p\}$ for $p\in S^2$.

$6.$ (solved by @lpetrich ) Find the area $A$ enclosed by the asteroid $(x,y)=(\cos^3 t,\sin^3 t)$ for $0\leq t \leq 2\pi\,.$

$7.$ (solved by @lpetrich ) Two surface ships on maneuvers are trying to determine a submarine's course and speed to prepare for an aircraft intercept. Ship $A$ is located at $(4, 0, 0)$, whereas ship $B$ is located at $(0, 5, 0)$. All coordinates are given in thousands of feet. Ship $A$ locates the submarine in the direction of the vector $2\mathbf{i} + 3\mathbf{j} - (1/3)\mathbf{k}$, and ship $B$ locates it in the direction of the vector $18\mathbf{i} - 6\mathbf{j} - \mathbf{k}$. Four minutes ago, the submarine was located at $A=(2, -1, -1/3)$. The aircraft is due in $20$ minutes. Assuming that the submarine moves in a straight line at a constant speed, to what position should the surface ships direct the aircraft?

$8.$ Calculate the following:
$a.)$ (solved by @fbs7 ) $\displaystyle{\int} \dfrac{\sqrt{(x^2-1)^3}}{x}\,dx$
$b.)$ (solved by @lpetrich ) The arc length $L$ of $y=-\dfrac{x^2}{8}+\log x$ for $1\leq x \leq 2$

$9.$ (solved by @lpetrich ) Find the similarity transformations to diagonalize the following matrices:
$a.)$ $A=\begin{pmatrix}1&-\sqrt{2}&1\\ \sqrt{2}&0&-\sqrt{2}\\ 1&\sqrt{2}&1\end{pmatrix}$
$b.)$ $B=\begin{pmatrix}\cos \varphi &-\sin \varphi \\ \sin \varphi& \cos \varphi \end{pmatrix}$

$10.$ (solved by @Math_QED ) Suppose that $\mathbb{F}$ is a finite field with say $|\mathbb{F}|= p^m = q$ and that $V$ is a vector space of finite dimension $n$ over $\mathbb{F}\,.$ Find the order of $\operatorname{GL}(V)\,.$

$1$. The king in chess can move to any neighboring square in three different ways: horizontally, vertically or diagonally. Now, we assume that we have an infinite chessboard and the king starts on some square.
$a.)$ (solved by @fbs7 ) In how many different squares can it be after $n$ moves?
$b.)$ (solved by @Master1022 ) Provide an optimal approach i.e. the minimum number of moves required to reach a destination.
$c.)$ (solved by @Master1022 ) Answer $a.)$ if there is a constraint of no diagonal moves.

$2$. The squares of an $8 \times 8$ chessboard are mistakenly colored in blocks of two colors, such that beginning from top left corner of the chessboard and moving in rows of $2 \times 2$ squares, always from left to right, the colors of $2 \times 2$ squares are $W - B - W - B$ for the odd-numbered rows and $B - W - B - W$ for the even numbered rows - we begin counting of rows with number $1$, where $W$ denotes White and $B$ denotes Black. This board needs to be cut in such a way so that a standard chessboard can be reassembled from the pieces obtained. What is the minimum number of pieces that you need to cut the board and in which way should they be reassembled?

$3$. An algorithm works like this: it starts with a single equilateral triangle and on each (subsequent) iteration, it adds new equilateral triangles all around the outside. When the algorithm finishes its $n$-th iteration how many small triangles will be there?

$4.$ (solved by @YoungPhysicist ) Can the numbers $1, 2, 3, \ldots, 16$ be arranged in a row so that each two adjacent numbers add up to a square number?
Example: $2, 7, 9, 16, \ldots$ would be a possibility for the first four numbers $2 + 7 = 9, 7 + 9 = 16, 9 + 16 = 25$; but then we are stuck.

$5.$ (solved by @ShreyJ ) We are looking for a ten-digit number $N$, where the first digit indicates how many zeros occur in $N$, the second digit, how many ones appear in $N$, the third digit, how many doubles occur in $N$, ... and the tenth digit, how many nines appear in $N$.

 

[Charles Link]

9b is a puzzle. I think it should be simple, but the solution eludes me.

 

[fbs7]

Why these are not solutions to Yoda level No 1?

(a) On 10:00 am every prisoner looks at the color of the hat to his left (left-most prisoner looks at the hat on the right-most prisoner), and then puts his own hat on the head of the prisoner to the right (right-most prisoner passes the hat to left-most prisoner). Then on 10:01 am every prisoner knows the color of his own hat.

(b) On 10:00 am every prisoner looks at the color of the hat to the left (left-most prisoner looks at the hat on the right-most prisoner), and then steps back if that is white. Then each prisoner just looks to his right and see if the other prisoner stepped back and will know the color of his own hat.

I guess a better question is which actions are allowed for the prisoners?

 

[QuantumQuest]

Why these are not solutions to Yoda level No 1?

(a) On 10:00 am every prisoner looks at the color of the hat to his left (left-most prisoner looks at the hat on the right-most prisoner), and then puts his own hat on the head of the prisoner to the right (right-most prisoner passes the hat to left-most prisoner). Then on 10:01 am every prisoner knows the color of his own hat.

How a prisoner can put his own hat onto another prisoner? The hats are put on only by the warden and then every prisoner can just see the hats of every other except his own hat. If a prisoner was allowed to put his hat off and put it on to another prisoner then he would immediately see its color.

(b) On 10:00 am every prisoner looks at the color of the hat to the left (left-most prisoner looks at the hat on the right-most prisoner), and then steps back if that is white. Then each prisoner just looks to his right and see if the other prisoner stepped back and will know the color of his own hat.

The allowable movements of the prisoners are also implied in the wording of the puzzle. They can neither step back nor communicate to each other.

I guess a better question is which actions are allowed for the prisoners?

I think that this is clear in the wording of the puzzle.

(The prisoners) will be able to see everyone else's hat except their own. Also, there will be no sort of communication among prisoners. The prisoners will be lined up every five minutes starting at $10:00 \space\space a.m.$ and ending at $10:50 \space\space a.m.$ 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.

 

[fbs7]

Hmm.. I think this means the only action the prisoner can do it to step forward or not.

But, how can a prisoner step forward based on what he sees, and that not be a communication to other prisoners? Like, say that a prisoner steps forward if he sees a prime number of white hats.

Then, the other prisoners see that one moving forward, and they know that that guy sees a prime number of white hats... that's implicit communication...

 

[fbs7]

Trying my hand at Padawan Level 1(a) (ie High School 1)!

Spoiler

Call $δ_{xn}, δ_{yn}$ two variables, $δ_{xn}, δ_{yn} ∈ \{-n,...,-1,0,1,...,+n\}$.

If the king is initially at position $(x_o,y_o)$, then it can move on move n=1 to positions $(x_1,y_1)= (x_o+δ_{x1},y_o+δ_{y1})$, except to $δ_{x1} = δ_{y1} = 0$ as the king must move from $(x_o,y_o)$. Therefore, on move n=1 in particular the location $(x_o,y_o)$ is forbidden

On move n=2 it can move to $(x_2,y_2)=(x_1+δ_{x1},y_1+δ_{y1})=(x_0+δ_{x2},y_0+δ_{y2})$. That includes being back at $(x_o,y_o)$ for example by moving $(x_o,y_o)=>(x_o+1,y_o)=>(x_o,y_o)$, so on $n=2$ any such location is valid and there are no exceptions.

Induction: if at move $n$ then king can be in any location $(x_n,y_n)=(x_0+δ_{xn},y_0+δ_{yn})$, then at move $n+1$ the king can be at any location $(x_{n+1},y_{n+1})=(x_0+δ_{xn+1},y_0+δ_{yn+1})$. That's because the king can move from $(x_0+δ_{xn},y_0+δ_{yn})$ to $(x_0+δ_{xn}+δ_{x1},y_0+δ_{yn}+δ_{y1}) = (x_0+δ_{xn+1},y_0+δ_{yn+1})$. As the induction is true for n=2 and if true for n then it's true for n+1, then it is true for any n>=2.

As the set $\{-n,...,-1,0,1,...,+n\}$ has $2n+1$ members, then:

At n=0 the king can be at $1=(2n+1)^2$ positions
At n=1 the king can be at $(2n+1)^2-1$ positions
At n>=2 the king can be at $(2n+1)^2$ positions

 

[QuantumQuest]

Hmm.. I think this means the only action the prisoner can do it to step forward or not.

But, how can a prisoner step forward based on what he sees, and that not be a communication to other prisoners? Like, say that a prisoner steps forward if he sees a prime number of white hats.

Then, the other prisoners see that one moving forward, and they know that that guy sees a prime number of white hats... that's implicit communication...

I recommend reading the wording carefully. Only when in line can prisoners make a move forward, if they think that they have a black hat and this will be based on what they see and so, on what they logically deduce. Communication, in the context of this particular puzzle, means direct communication of any kind e.g. speaking, making any sort of gesture, making some sound / noise and in general what constitutes direct communication. On the other hand, making a decision from seeing is a logical deduction which does not constitute such communication.

 

[member 587159]

Solution attempt for 10:

Spoiler

$GL(V)$ are invertible operators $V \to V$. The matrix associated with such an operator (fix a basis for this) is an $n \times n$-matrix, and because there is a bijective correspondence between the invertible linear maps and the associated (invertible) matrices, it suffices to count these matrices, which are precisely the ones with linearly independent rows.

For the first row, we can put any vector in $\mathbb{F}^n$ there, except the null vector. So, there are $q^n-1$ possibilities.

For the second row, all vectors will do except for multiples of the first row, so there are $q^n- q$ possibilities.

For the third row, we cannot have linear combinations of the first two rows, so there are $q^n-q^2$ possibilites.

Repeat the process to end with $q^n - q^{n-1}$ possibilities for the last row.

Hence, the total amount of such matrices is $(q^n-1)(q^n-q)(q^n-q^2) \dots (q^n-q^{n-1})$

 

[fbs7]

Trying Yoda Level 8(a):

Spoiler

$I = \int \frac{\sqrt{(x^2-1)^3}}{x} dx$

using $v^2 = x^2-1$

$v.dv = x.dx, \frac {v.dv}{x^2} = \frac {v.dv}{1+v^2} = \frac{dx}{x}$

$I = \int \sqrt{(v^2)^3} \frac{dx}{x} = \int (v^3).\frac{v}{1+v^2}.dv$
$I = \int \frac{v^4}{1+v^2}.dv = \int \frac{1+(v^2-1).(v^2+1)}{v^2+1}.dv$
$I = \int \frac{1}{1+v^2}.dv + \int (v^2-1).dv$
$I= arctg(v)+v^3/3-v+C$

translating back the variables...

$v=\sqrt{x^2-1}$
$I = arctg(\sqrt{x^2-1})+\frac {\sqrt{(x^2-1)^3}}{3}-\sqrt{x^2-1}+C$

proof:

$v=\sqrt{x^2-1}$
$\frac{dI}{dx} = \frac{dI}{dv} . \frac{dv}{dx} = \frac{d}{dv} ( arctg(v)+v^3/3-v ).\frac{d}{dx} (\sqrt{x^2-1})$
$= ( \frac{1}{1+v^2} + v^2 - 1 ).(1/2).(x^2-1)^{-1/2}.2x$
$= \frac{v^4}{1+v^2} .(x^2-1)^{-1/2}.x$
$= \frac{(x^2-1)^2.(x^2-1)^{-1/2}}{x}$
$= \frac{\sqrt{(x^2-1)^3}}{x}$

 

[lpetrich]

I will attempt to solve problem 2:

Spoiler

It is to find values of $\alpha$ where integral
$$I(\alpha) = \int_0^1 \int_{-\infty}^{\infty} \frac{1}{(x^2+y^2)^\alpha} dx dy$$
converges.

I will first consider convergence for the y integral, and then for the x integral.

For the y integral, I need the possible values of x, and those are between 0 and 1 inclusive. This means that x is nonzero at all but one point, so I will treat it as nonzero in this part. This means that the integrand is finite for $y \ll x$, so we turn our attention to $y \gg x$. In that limit, the y integral becomes
$$ \int \left(\frac{1}{y^{2\alpha}} + O\left(\frac{1}{y^{2(\alpha+1)}}\right)\right) dy $$
That integral will converge whenever $2\alpha > 1$ or $\alpha > (1/2)$.

The integral can be evaluated with the help of a change of variables: $y = x u$ where u ranges between $-\infty$ and $\infty$. This gives us
$$I(\alpha) = \int_0^1 \int_{-\infty}^{\infty} \frac{1}{(x^2+x^2 u^2)^\alpha} x\, dx du = \int_0^1 \frac{dx}{x^{2\alpha-1}} \int_{-\infty}^{\infty} \frac{du}{(1 + u^2)^\alpha}$$
The integral for x will converge whenever $2\alpha - 1 < 1$, or $\alpha < 1$, and doing that integral gives us
$$I(\alpha) = \frac{1}{2(1-\alpha)} \int_{-\infty}^{\infty} \frac{du}{(1 + u^2)^\alpha}$$
Collecting the two bounds for $\alpha$ gives us $(1/2) < \alpha < 1$.

 

[lpetrich]

I will now do Problem 6:

Spoiler

It is to find the area inside a unit-sized astroid, a curve given by $(x,y) = (cos^3 t, sin^3 t)$ for $0 \le t \le 2\pi$.

It is possible to find this area by finding the bounds of y as functions of x, integrating over y, and then integrating over x. But these bounds are given by $y = \pm (1 - |x|^{2/3})^{3/2}$, and that does not look very easy to work with, and finding such expressions will sometimes be impractical or impossible in closed form.

So I seek a formula for the area that uses the curve's rectangular-coordinate statement while integrating over the curve's parameter. This can be taken as the continuous limit of the area of a polygon with vertices given in rectangular coordinates. There is a surprisingly simple formula for that area, the shoelace formula:
$$ A = \frac12 \sum_i ( x_i y_{i+1} - x_{i+1} y_i ) = \sum_i (x_i (y_{i+1} - y_i) - y_i (x_{i+1} - x_i)) $$
In the continuous limit, it becomes, for parameter $t$:
$$ A = \frac12 \oint \left( x \frac{dy}{dt} - y \frac{dx}{dt} \right) dt $$
Substituting in the expressions for the problem:
$$ A = \frac12 \int_0^{2\pi} \left( (\cos^3 t) (3 \sin^2 t \cos t) - (\sin^3 t) (- 3 \cos^2 t \sin t) \right) dt \\ = \frac12 \int_0^{2\pi} (3 \cos^4 t \sin^2 t + 3 \sin^4 t \cos^2 t) dt \\ = \frac32 \int_0^{2\pi} \sin^2 t \cos^2 t \, dt \\ = \frac{3\pi}{8} $$
So the area inside a unit-sized astroid is $3\pi/8$.

 

[lpetrich]

I will solve Problem 8b.

Spoiler

It is to find the length L given by the curve $y = - \frac{x^2}{8} + \log x$ for $1 \le x \le 2$.

For this purpose, I need the formula for arc length for a curve given in rectangular coordinates (x,y) as a function of some parameter t. It is
$$ L = \oint \sqrt{ \left( \frac{dx}{dt} \right)^2 + \left( \frac{dy}{dt} \right)^2 } \, dt $$
For this problem, the parameter t is x, and that simplifies the formula to
$$ L = \int \sqrt{ \left( \frac{dy}{dx} \right)^2 + 1} \, dx $$
Finding $dy/dx = - \frac{x}{4} + \frac{1}{x}$ for the problem condition, and plugging in both it and the bounds of integration,
$$ L = \int_1^2 \sqrt{ \left(- \frac{x}{4} + \frac{1}{x}\right)^2 + 1 } \, dx $$
The expression inside the square root can be simplified:
$$ \left(- \frac{x}{4} + \frac{1}{x}\right)^2 + 1 = \frac{x^2}{16} - 1/2 + \frac{1}{x^2} + 1 = \frac{x^2}{16} + 1/2 + \frac{1}{x^2} + 1 = \left(\frac{x}{4} + \frac{1}{x}\right)^2 $$
It is easy to take the square root of the resulting expression, and it is always positive over the domain of integration, so we have
$$ L = \int_1^2 \left(\frac{x}{4} + \frac{1}{x}\right) dx = \left. \frac{x^2}{8} + \log x \right|_1^2 = \frac38 + \log 2 $$
Thus, $L = \frac38 + \log 2$.

 

[fbs7]

a.)a.)a.) (solved by @fbs7 ) ∫√(x2−1)3xdx∫(x2−1)3xdx\displaystyle{\int} \dfrac{\sqrt{(x^2-1)^3}}{x}\,dx

Ahhh--hahahaha! I solved one at Top-Master-Jedi-Level! Hooray!

 

[Infrared]

I will attempt to solve problem 2:
The integral can be evaluated with the help of a change of variables: $y = x u$ where u ranges between $-\infty$ and $\infty$. This gives us
$$I(\alpha) = \int_0^1 \int_{-\infty}^{\infty} \frac{1}{(x^2+x^2 u^2)^\alpha} x\, dx du = \int_0^1 \frac{dx}{x^{2\alpha-1}} \int_{-\infty}^{\infty} \frac{du}{(1 + u^2)^\alpha}$$

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.

 

[lpetrich]

I will solve Problem 7.

Spoiler

We want the position of the submarine at the time of the aircraft's arrival, at time +20, using minutes as the time unit. We have observations of the submarine's directions relative to two ships at time 0, and the submarine's position at time -4.

So we must first find the position of the submarine at time 0, then extrapolate from its positions at times 0 and -4 to time +20.

For the first part, we have the ships' positions and the directions of the submarine relative to each ship. The positions and directions form lines, and where they intersect is where the submarine is. For distances d₁ and d₂ along observation lines l₁ and l₂, we get for the positions along those lines
$$ l_1 = (4,0,0) + (2,3,-1/3) d_1 ,\ l_2 = (0,5,0) + (18,-6,-1) d_2 $$
For intersection, we set $l_1 = l_2$, and that gives us
$$ 4 + 2d_1 = 18d_2 ,\ 3d_1 = 5 - 6d_2 ,\ -1/3 d_1 = -d_2 $$
The third equation gives us $d_1 = 3d_2$, and inserting it into the above equation gives us
$$ 4 +6d_2 = 18d_2 ,\ 9d_2 = 5 - 6d_2 $$
or $4 = 12d_2$ and $5 = 15d_2$, giving $d_2 = 1/3$, $d_1 = 1$, and the intersection point as $(6,3,-1/3)$.

I now turn to the extrapolation part. For points $\mathbf{x_0}$ and $\mathbf{x_1}$ at times $t_0$ and $t_1$, $\mathbf{x}(t)$ is, for time t, is
$$ \mathbf{x}(t) = \mathbf{x_0} + (\mathbf{x_1} - \mathbf{x_0}) \frac{t - t_0}{t_1 - t_0}$$
and likewise with indices 0 <-> 1. Plugging in the values for our problem, $t_0 = 0$, $\mathbf{x_0} = (6,3,-1/3)$, $t_1 = -4$, $\mathbf{x_1} = (2,-1,-1/3)$, and $t = 20$. That gives position $\mathbf{x}$ as
$$\mathbf{x} = (6,3,-1/3) + ((2,-1,-1/3) - (6,3,-1/3)) \frac{20 - 0}{-4 - 0} = (6,3,-1/3) - 5 (-4,-4,0) = (26,23,-1/3)$$
So the aircraft must be dispatched to point (26,23) and the submarine will be at depth (-1/3).

 

[YoungPhysicist]

High school 4:

Spoiler

You stuck because 2,7,9,16 is the end of the sequence, rather than beginning. Good misdirection though.

Brute force success on first go:

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

Their sum follows the pattern of 9-16-25-16.

 

[SpinFlop]

Questions

$1.$ There are $12$ prisoners who are given the chance to be freed if they pass this test: the warden will put a hat on the head of each prisoner which will be either black or white. The prisoners will get informed that there will be at least one hat of each color. They will be able to see everyone else's hat except their own. Also, there will be no sort of communication among prisoners. The prisoners will be lined up every five minutes starting at $10:00 \space\space a.m.$ and ending at $10:50 \space\space a.m.$ 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. Is there a way for the prisoners to pass the test?

Solution to problem 1

Spoiler

Since there is no communication, we Just need to consider the perspective and thought process of a single prisoner with a black hat. Call him BHP.

Suppose only 1 hat is black. BHP will see all white hats and be able to deduce that his hat must be black.
This prisoner steps forward immediately, ie: 10:00

Suppose 2 prisoners wear black hats. BHP sees only one black hat in the crowd. If BHP's hat is white, then the person with the black hat on will step forward at 10:00. If he does not step forward at 10:00, then that must mean BHP's hat was black. By symmetry they both can now deduce there were two black hats and so they step forward at 10:05.

Suppose 3 prisoners wear black hats. BHP can use the same reasoning as above. At 10:05 if the other two black hats don't step forward, then he knows his was black as well. By symmetry all 3 can deduce there were 3 black hats total and step forward at 10:10.

Suppose N prisoners wear black hats. At 10:(N-2)*5 if the N-1 black hats that BHP sees don't step forward, then he knows his was black as well. By symmetry all N black hats can deduce there were N black hats total and step forward at 10:(N-1)*5

So the rule is as follows:
If a prisoner sees N black hats, then he should step forward at 10:(N)*5 because his hat is black. Thus, if 11 hats are black (the max number possible), BHP would see 10 hats and step forward at 10:50. Just in time!

 

[QuantumQuest]

Suppose 2 prisoners wear black hats. BHP sees only one black hat in the crowd. If his was white, then the person with the black hat on will step forward at 10:05.

If I understand it correctly you mean that initially BHP, as you call it, sees only one black hat. If his hat was white then wouldn't this mean that there would be just one person with a black hat? Then, I see a discrepancy between the time you write and your above analysis for one black hat.

 

[SpinFlop]

Ahhhh, there were some number typos in my original post. I have fixed them. Let me know if that clears it up.

 

[QuantumQuest]

Of course, if all 12 were black, then none would step forward.

This cannot be the case as it violates the data given in the wording of the problem:

The prisoners will get informed that there will be at least one hat of each color.

 

[SpinFlop]

Again, thanks for catching an error. The last sentence has been removed. It was extraneous anyways. I also rephrased some of my reasoning for clarity.
Cheers

 

[SpinFlop]

$4.$ Let $f$ be a continuous element of $L^1((0,\infty))$. Suppose that $x=x(t)$ solves the differential equation $\frac{dx}{dt}=-px+f(t)$. Prove that $\lim_{t\to\infty}x(t)=0$.

Solution to 4

Spoiler

Rewrite as:
$$\frac{dx}{dt} + px- f(t) = 0$$
This contains the homogeneous linear equation:
$$\frac{dx}{dt} + px = 0$$
Which converts to the characteristic equation:
$$\lambda + p = 0$$
Thus, the homogeneous solution is:
$$x_{h}(t) = Ae^{\lambda t} \rightarrow x_{h}(t) = Ae^{-p t}$$
Clearly, we have (assuming p is positive!):
$$\lim_{t\to\infty}x_{h}(t)=0$$
The full solution is given by the sum of the homogeneous and particular solutions:
$$x(t) = x_{h}(t) + x_{p}(t)$$
Where the particular solution is found by solving:
$$\frac{dx_{p}(t)}{dt} + px_{p}(t) = f(t)$$
Thus:
$$x_{p}(t) + p\int_0^t x_{p}(t)\, dt = \int_0^t f(t) \, dt$$
Taking the limit we get
$$\lim_{t\to\infty}x_{p}(t) + p\lim_{t\to\infty}\int_0^t x_{p}(t)\, dt = \lim_{t\to\infty}\int_0^t f(t) \, dt < \infty$$
where the inequality follows from the fact that $f$ is a continuous element of $L^1((0,\infty))$
In order for this integral $\lim_{t\to\infty}\int_0^t x_{p}(t)\, dt$ to converge to a finite value we must have that:
$$\lim_{t\to\infty}x_{p}(t)=0$$
And so we get:
$$\lim_{t\to\infty}x(t) = \lim_{t\to\infty}x_{h}(t) + \lim_{t\to\infty}x_{p}(t) = 0$$

 

[Infrared]

Where the particular solution is found by solving:
$$\frac{dx_{p}}{dt} = f(t)$$

This does not give a solution to the differential equation.

Also, this would give $x_p(t)=C+F(t)$ where $F$ is an antiderivative to $f$. Your expression for $x_p(t)$ is just a constant.

 

[SpinFlop]

This does not give a solution to the differential equation.

Also, this would give $x_p(t)=C+F(t)$ where $F$ is an antiderivative to $f$. Your expression for $x_p(t)$ is just a constant.

Thanks for catching that, I don't know why I left off the other term. It only makes my proof a bit longer. I also cleaned up my notation for the integral limits to make it more clear. I edited my original post to reflect these changes. Let me know if you see any other glaring mistakes.

 

[lpetrich]

I have a solution for the differential equation in Problem 4:

Spoiler

The equation that we must solve is
$$ \frac{dx}{dt} + px = f(t) $$
We solve it by first finding the homogeneous solution, and then using it to find the full solution. The homogeneous equation:
$$ \frac{dx}{dt} + px = 0 $$
That is easy to solve: $x = x_0 e^{-pt}$. For the general case, we make the constant of integration $x_0$ a variable: $X(t)$. Then
$$ \frac{d}{dt} (X e^{-pt}) + p X e^{-pt} = f(t) $$
giving us
$$ \frac{dX}{dt} = f(t) e^{pt} $$
The complete solution is thus
$$ x = C e^{-pt} + \int_{-\infty}^{t} e^{-p(t-s)} f(s) \, ds $$
If $x$ is assumed to be bounded at $-\infty$, then $C = 0$ and
$$ x = \int_{-\infty}^{t} e^{-p(t-s)} f(s) \, ds = \int_0^\infty e^{-p s} f(t - s) \, ds$$

 

[Infrared]

In order for this integral $\lim_{t\to\infty}\int_0^t x_{p}(t)\, dt$ to converge to a finite value we must have that:
$$\lim_{t\to\infty}x_{p}(t)=0$$

This isn't true, unfortunately. A continuous function with smaller and smaller "spikes" can be integrable on $[0,\infty)$ and yet fail to have a limit at infinity.

Edit: thanks for noticing that $p>0$ is necessary.

 

[Infrared]

@lpetrich You're very close, but the function $f$ is only assumed to be defined on $(0,\infty)$, which causes problems with your substitution at the end.

 

[lpetrich]

So it starts at 0, not at -oo. I'll take that into account.

Spoiler

I had earlier found
$$ \frac{dX}{dt} = f(t) e^{pt} $$
Integrating from $t = 0$ gives
$$ X(t) = X(0) + \int_0^t f(s) e^{ps} \, ds $$
Thus giving us
$$ x(t) = e^{-pt} x(0) + \int_0^t e^{-p(t-s)} f(s) \, ds $$
I will attempt to prove the statement of the problem. For the first term, it is easy. It rather obviously tends to 0 as $t \to \infty$. It is the second one that is difficult. Being a member of $L^1((0,\infty))$ means that
$$ \int_0^\infty |f(t)| \, dt = F < \infty $$
I tried to continue by subdividing the domain of integration and using a suitable inequality for $e^{-p(t-s)}$, but I found a risk of creating an infinite number of subdivisions, with the risk of being unable to interchange the summation and taking the limit of infinity. So I'm stumped.

 

[lpetrich]

I will solve Problem 9.

Spoiler

The two matrices are
$$ A = \begin{pmatrix} 1 & -\sqrt{2} & 1 \\ \sqrt{2} & 0 & -\sqrt{2} \\ 1 & \sqrt{2} & 1 \end{pmatrix} ,\ B = \begin{pmatrix} \cos\varphi & -\sin\varphi \\ \sin\varphi & \cos\varphi \end{pmatrix} $$
For a matrix $M$, the similarity-transformation matrix $S$ satisfies $S^{-1} M S = D$ or $M S = S D$, where D is a diagonal matrix. The matrix D contains the eigenvalues of M and each column of S the appropriate (right) eigenvector of M for that column's eigenvalue in D. That is, S consists of column x such that $Mx = \lambda x$ for eigenvalue $\lambda$ in the corresponding column of D.
$$ S = \begin{pmatrix} x_1 \\ x_2 \\ \dots \\ x_n \end{pmatrix}^T ,\ D = \text{diag}(\lambda_1, \lambda_2, \dots, \lambda_n) $$
So I must find the eigenvalues and eigenvectors for each matrix.

The second can be made easier to work with by going from trigonometric to exponential functions with Euler's formula $e^{i\varphi} = \cos\varphi + i \sin\varphi$. This can then be turned into rational polynomial functions by taking $z = e^{i\varphi}$. This gives us
$$ B = \begin{pmatrix} \frac12(z + z^{-1}) & - \frac1{2i}(z - z^{-1}) \\ \frac1{2i}(z - z^{-1}) & \frac12(z + z^{-1}) \end{pmatrix} $$

One can find the eigenvalues by finding the roots of the characteristic polynomial $\det(M - \lambda I)$. Doing that, I find $-(\lambda - 2)(\lambda^2+4)$ for A and $(\lambda - z)(\lambda - z^{-1})$ for B. Their solutions are $(2, 2i, -2i)$ for A and $(z, z^{-1})$ for B. The corresponding eigenvectors are $(1,0,1)$, $(1,-i\sqrt{2},-1)$, and $(1,i\sqrt{2},-1)$ for A and $(1,-i)$ and $(1,i)$ for B.

The resulting similarity transformations are
$$ S(A) = \begin{pmatrix} 1 & 1 & 1 \\ 0 & -i\sqrt{2} & i\sqrt{2} \\ 1 & -1 & -1 \end{pmatrix} ,\ S(B) = \begin{pmatrix} 1 & 1 \\ -i & i \end{pmatrix} $$
with
$$ D(A) = \text{diag}(2,2i,-2i) ,\ D(B) = \text{diag}(z,z^{-1}) = \text{diag}(e^{i\varphi},e^{-i\varphi}) $$

 

[fbs7]

Suppose 2 prisoners wear black hats. BHP sees only one black hat in the crowd. If BHP's hat is white, then the person with the black hat on will step forward at 10:00. If he does not step forward at 10:00, then that must mean BHP's hat was black. By symmetry they both can now deduce there were two black hats and so they step forward at 10:05.

Hmm... isn't the deduction based on whether others walked up communication? There's actually no need to see if other prisoners walked up or not, just use the very clever rule that @SpinFlop came up with.

Each prisoner $i$ just needs to see the other prisoners once, count the black hats at $N_i$, then remember to walk up at $10:00 + N_i*5$. Then all the prisoners don't need to see anything else.

If there is 1 black hat on prisoner $i$, then prisoner $i$ will step up at 10:00 and everybody else will plan to step up by 10:05. Therefore, success at 10:00.

If there are 2 black hats on prisoners $i, j$, then prisoners $i,j$ will step up at 10:05, and everybody else will plan to step up by 10:10. Therefore, success at 10:05. And so forth.

I wonder if any $F(N)$ that indicates the walk up time based on how many hats he sees will solve the problem as long as $F(N)$ is a bijection from {0..10) to {10:00,10:05,...,10:50}. For example, I suspect that this will also solve the problem: f(10)=10:00, f(8)=10:05, ..., f(0)=10:25, f(9)=10:30, f(7)=10:35, etc...

@SpinFlop = very smart on his solution! I almost fried my brain thinking about this and didn't solve it!PS: Tentative proof that any bijective $F(N)$ solves the problem: call $B$ = set of prisoners with black hats, and $W$ = set of prisoners with white hats, and $P=B∪W$, and call $N=N_p$ as the number of black hats seen by prisoner p∈P.

There will be success if all prisoners p∈B step up at the some time, and no p∈W step up at that time, therefore $N_p$ is the same for all p∈B, and that's different from $N_p$ for all p∈W. If there are N black hats in all prisoners, then $N_p$=N-1 if p∈B and $N_p$=N if p∈W. Therefore $F(N)$ is a solution if $F(N)<>F(N-1)$, and as that is valid for any N∈{0, 1, ... , 10}, then that's a bijection, ie any bijection solves the problem.

 

[QuantumQuest]

Hmm... isn't the deduction based on whether others walked up communication?

No, it is not. See my post #7. The only way for prisoners to save their life is to be smart and make the right decision

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.

This can solely be based on deduction as there is no way for communication among prisoners.

 

[QuantumQuest]

Each prisoner $i$ just needs to see the other prisoners once, count the black hats at $N_i$, then remember to walk up at $10:00+N_i∗5$.

Just a clarification: what does $i$ stand for?

 

[fbs7]

This can solely be based on deduction as there is no way for communication among prisoners.

Correct. I'm just pointing out that there's no need for a prisoner to see if other prisoners walk; that was used in the original argument and I think that's unnecessary. The prisoners can do that blindfolded, once they see all the other hats once, and be based solely by counting the number of hats that prisoner sees.

Btw, $i$ is the number of the prisoner, from 1 to 12. So first prisoner is $i$=1, second prisoner is $i$=2 and so forth.

Now, I suspect that there are 11! different choices for $f(N)$, so the solution is not unique. I suspect the prisoners would have to know which of the different $f(N)$ they all will use, so they would need to have some prior agreement - but no need of communication once they line up by 10:00.

 

[QuantumQuest]

$i$ is the prisoner number, from 1 to 12.

So, if you substitute for $i$ for each prisoner, what is $N_i$ and $10 + N_i*5$?

 

[fbs7]

$N_i$ is the number of black hats prisoner $i$ sees, and $10+N_i*5$ = "10:00" o'clock plus $5*N_i$ minutes.

 

[QuantumQuest]

So the rule is as follows:
If a prisoner sees N black hats, then he should step forward at 10:(N)*5 because his hat is black.

As this is one of the things that were added to the solution afterwards, do you mean if the prisoner sees N black hats before the first line up at 10:00?

 

[fbs7]

Attempt at Padawan-level #5

Spoiler

My procedure to find a solution was to start from the left, then find all solutions assuming a certain number of zeroes, and see which size of the full number will solve the criteria assuming the first digit has so many zeroes. The benefit of this approach is that zeroes not in the first position do not break the solution; therefore

So

0123456789
==========
0xxxxxxxxx => no numbers solve the problem assuming 0 zeroes
1210xxxxxx => solution for 1 zero [note 1]
21200xxxxx => solution for 2 zeroes
3211000xxx => solution for 3 zeroes [note 2]
42101000xx => solution for 4 zeroes
521001000x => solution for 5 zeroes
6210001000 => final solution

So a general problem of "find N-digit numbers" that follow problem rules have solutions for N=4 (with 1 zero), N=5 (with two zeroes), N=7 (with 3 zeroes), N=8 (with 4 zeroes), N=9 (with 5 zeroes) and N=10 (with 6 zeroes).

[note 1] the deduction sequence for this pattern is really by trial and error; for 1 zero, that is

10? => need to fix digit 1
110?? => need to fix digit 1 and 2
120?? => need to fix digit 1 and 2
1210? => that's it, solved for 1 zero, got a 4 digits number

[note 2] once we reach 3+ zeroes, the pattern becomes clear:

N21...1... => spread N zeroes around, and set 1 at digit "N+1"; digit 1 will always have "2", and digit "2" will always have "1".

PS: A-ha! The pattern holds for any base! In hexadecimal base, for a 16-digits number:

0123456789ABCDEF

=================
D2100000000001000

 

[fbs7]

There will be success if all prisoners p∈B step up at the some time, and no p∈W step up at that time, therefore $N_p$ is the same for all p∈B, and that's different from $N_p$ for all p∈W. If there are N black hats in all prisoners, then $N_p$=N-1 if p∈B and $N_p$=N if p∈W. Therefore $F(N)$ is a solution if $F(N)<>F(N-1)$, and as that is valid for any N∈{0, 1, ... , 10}, then that's a bijection, ie any bijection solves the problem.

Holy choo-choo, I made a wrong conclusion! The only requirement is that $F(N)<>F(N-1)$ for any N... there's no requirement that $F(n)<>F(m)$ for $n<>m$. No need for a bijection (although bijections also solve the problem). This also solves the problem (as will many other similar functions):

F(N) = 10:00 if N is odd
F(N) = 10:05 if N is even

Say that prisoners 1, 2, 3, 4, 5 have the black hat, and prisoners 6, 7, 8, 9, 10, 11, 12 have a white hat. Then prisoners 1..5 all see N=4 black hats, and prisoners 6..12 all see N=5 black hats. Therefore, 1..5 all will step up at 10:05, and 6..12 will step up at 10:00. Problem will always be solved by 10:00 or 10:05. No need to wait for 10:00+5*N.

 

[QuantumQuest]

$N_i$ is the number of black hats prisoner $i$ sees, and $10+N_i*5$ = "10:00" o'clock plus $5∗N_i$minutes.

So, does a prisoner know before the first line up what time he must walk up?

 

[fbs7]

Hmm.. I assumed the procedure was:

(a) line-up
(b) look at the hats
(c) step up or not step up

That is the way to have any prisoners walking up or not by 10:00.

 

[QuantumQuest]

Hmm.. I assumed the procedure was:

(a) line-up
(b) look at the hats
(c) step up or not step up

That is the way to have any prisoners walking up or not by 10:00.

I suggest reading again the question carefully. I also cannot understand this

Say that prisoners 1, 2, 3, 4, 5 have the black hat, and prisoners 6, 7, 8, 9, 10, 11, 12 have a white hat. Then prisoners 1..5 all see N=4 black hats, and prisoners 6..12 all see N=5 black hats. Therefore, 1..5 all will step up at 10:05, and 6..12 will step up at 10:00. Problem will always be solved by 10:00 or 10:05. No need to wait for 10:00+5*N.

 

[fbs7]

I suggest reading again the question carefully. I also cannot understand this

But that's exactly what @SpinFlop said, and that was accepted as a solution, that is, line up at 10:00, look at the hats, decide, then step or up not step immediately, ie at 10:00:

"Suppose only 1 hat is black. BHP will see all white hats and be able to deduce that his hat must be black.
This prisoner steps forward immediately, ie: 10:00 "

 

[QuantumQuest]

But that's exactly what @SpinFlop said, and that was called a solution:

"Suppose only 1 hat is black. BHP will see all white hats and be able to deduce that his hat must be black.
This prisoner steps forward immediately, ie: 10:00 "

What @SpinFlop wrote (after his first correction) was correct . Is what I just asked you to clarify the same thing with what you quote from @SpinFlop? Let me explain in order to be sure that I will be clear: What you quote from SpinFlop says that if there is just one black hat then before the first line-up the prisoner who has it will see only white hats, so he'll deduce that his hat is the only black hat as there is at least one black hat according to the data of the question. So, in the first line-up i.e. at 10:00, he will step up.

As a second point, @SpinFlop has added things in the solution afterwards which I have already quoted and asked for clarification.

 

[QuantumQuest]

Some clarifications about Question $1$ are in order, as I see that there are issues of misunderstanding / misinterpretation of the wording of the question, although I think that it is clear enough:

The 12 prisoners will get one hat each by the warden which can be either black or white. The prisoners will get informed that there will be at least one hat of each color. They will be able to see everyone else's hat except their own. Also, there will be no sort of communication among prisoners. So, before the first line-up, the only way for a prisoner to know how many black hats are there in total, is to see that all the others hats are white because then the only black hat will be his own hat, as there is at least one black hat as per the wording of the question. So, in the first line-up at $10:00\space\space a.m$ he will step forward.

Now, if before the first line-up there are more than one black hats, this means that no prisoner steps forward during the first line-up because none of them can be certain about the color of his hat. But, during the second line-up, both prisoners who see one black hat can step forward: since no prisoner stepped forward during the first line up, they know that there are at least two black hats. So, if a prisoner sees just one black hat, he can conclude that the second black hat is his own hat. Now, what about the prisoners who see two black hats? They obviously can't be certain about the color of their hats. So, they'll stay in line - assuming they're smart enough ;).

Now, to express it more generally, I would prefer to express it this way: Suppose there are $n$ prisoners and $b$ black hats, $1\leq b \leq 11$. During the first $b - 1$ line-ups, no prisoner will step forward. Now, on the $b$th line-up, each prisoner seeing $b - 1$ black hats will be able to step forward. We can conclude this using the same reasoning as above: as the previous line-up did not stop the procedure then he knows that there are at least $b$ black hats. Seeing $b − 1$ on the other prisoners means that there are exactly $b$ black hats, one of which is his own hat. The $n - b$ prisoners with white hats should stay in line as they cannot deduce what is the color of their hats.

 

[fbs7]

A variation with the argument of using the 10:00 to get information about whether there is a single black hat around.

Say there are 5 black hats. So each prisoner will see either 4 or 5 black hats. Therefore, each prisoner will know that no other prisoners can see 0 black hats. Therefore there is no benefit in using the 10:00 lineup expecting the prisoner that see no black hats to step forward.

I suspect there is a way to save one lineup in case the prisoners see 4 black hats or more, but the proper optimization evades me.

 

[pinball1970]

1 black and 11 whites is fine. Black sees all whites and knows he must be black.

2 black and black one observes that black 2 has not stepped forward even though everyone else is black. Therefore he must also be black, steps forward. Black 2 works this out and steps forward.

Does that make sense? Worse case scenario is 6, 6? Edit quantum quest already stated this and extended

 

[fbs7]

Clarification on Padawan-level #3, please?

What's the size of the triangles being added on each iteration? that is

(a) as large as possible
(b)/(c) same size, adding only on edges or on edges and vertices too
(d) smaller (as half size, third size, etc...)

I'm putting my bet that the problem means (c), as that looks prettier and mathematicians like pretty geometric shapes.

 

[QuantumQuest]

Say there are 5 black hats. So each prisoner will see either 4 or 5 black hats. Therefore, each prisoner will know that no other prisoners can see 0 black hats. Therefore there is no benefit in using the 10:00 lineup expecting the prisoner that see no black hats to step forward.

Say that there is only one black hat. Is there no benefit in using the 10:00 line up? If there are are more than one black hats then more line-ups are needed. I suggest reading my post #44.

 

[QuantumQuest]

What's the size of the triangles being added on each iteration? that is

(a) as large as possible
(b)/(c) same size, adding only on edges or on edges and vertices too
(d) smaller (as half size, third size, etc...)

I'm putting my bet that the problem means (c), as that looks prettier and mathematicians like pretty geometric shapes.

The size of the triangles added to each iteration is the same as the initial equilateral triangle. On each iteration a new triangle is added on each free edge.

 

[fbs7]

Say that there is only one black hat. Is there no benefit in using the 10:00 line up? If there are are more than one black hats then more line-ups are needed. I suggest reading my post #44.

Correct, if the prisoners see 0, 1 or 2 black hats, then the lineup for 0 black hats is needed.

But if there are 5 black hats or more, then the smallest number of black hats any prisoner will see is 4 black hats. So once a prisoner sees 4 black hats or more, he'll know not a single prisoner will think that other prisoners are seeing 0, 1 or 2 black hats. If there's no chance that any prisoner is seeing 0, 1 or 2 black hats, then the lineup for 0 black hats will result in no information, therefore can be skipped. That is, if I see 4 black hats or more, then I know up front that nobody will step up on the 0 black hats lineup.

So I suspect there may be an optimized logic with fewer lineups once a prisoner sees some N number of black hats, but I can't get my head on how that would be.