Challenge Math Challenge - April 2019

Infrared

Gold Member
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.

Last edited:

Infrared

Gold Member
@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.
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.
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.

Last edited:

QuantumQuest

Gold Member
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

Gold Member
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?

Last edited:

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

Gold Member
$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

Gold Member
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?

Last edited:

fbs7

Attempt at Padawan-level #5

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

Last edited:

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

Gold Member
$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

Gold Member
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

Gold Member
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.

Last edited:

QuantumQuest

Gold Member
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.

Last edited:

pinball1970

Gold Member
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

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

Gold Member
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

Gold Member
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.

Last edited:

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.

"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