Math Challenge - April 2019

[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.

 

[QuantumQuest]

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.

Let me get things straight. First, it is not known to the prisoners in advance how many black hats will be or who will have it. So, there will be 1 to 11 black hats. It is the warden's decision exactly how many will be and to whom. But any solution must account for all the posibilities and not for specific cases.
Second, the number of line-ups is already decided by the warden and it is an integral part of the test. How can we change the number of line ups?

 

[fbs7]

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.

Alright, starting trying my hand at Padawan-Level #3:

Spoiler

The orientation of the triangles is irrelevant; in this example, first set of triangles (call i=0) is brown, second set of triangles (call i=1) is red, i=2 is orange, i=3 is yellow, i=4 is green, i=5 is blue. The number of triangles on each iteration (call $T_i$) is {1, 3, 6, 9, 12, 15, ...}, to it seems that $T_0 = 1, T_i = 3*i$, and the total number of triangles in iteration n is $T_0 + T_1 + ... + T_n = 1 + 3 + 6 + ... + 3*n = 1 + \frac{3}{2}*n*(n+1)$:

But how to prove that - not easy! All kinds of coordinate transformation didn't help much, and trilinear coordinates proved to be a pain to prove anything; after 4 hours on this I'm no closer on finding a proof!

How to prove that each iteration $i$ will add exactly $3$ triangles to the scene... grrr... maddening I can't find that proof! Little tip anyone?

 

[fbs7]

Let me get things straight. First, it is not known to the prisoners in advance neither how many black hats will be nor who will have it. So, there will be 1 to 11 black hats. It is the warden's decision exactly how many will be and to whom. But any solution must account for all the posibilities and not for specific cases.
Second, the number of line-ups is already decided by the warden and it is an integral part of the test. How can we change the number of line ups?

The prisoners will not know in advance, but once a prisoner lines up and sees say 7 black hats, he knows that no other prisoner will see less than 6 black hats; and those that see 6 black hats will know that no other prisoner will see less than 5 black hats. Therefore, those prisoners that see 7 black hats and those that see 6 black hats will all come to the same conclusion, which is that no prisoners are seeing 0 black hats.

Therefore, there's no point in using the 10:00 lineup to test the hypothesis that some prisoner will move up because they see 0 black hats, as that hypothesis is impossible.

So, once the prisoners see 6 black hats or 7 black hats, then they can use the 10:00 lineup to say test a different hypothesis, like that some prisoner is seeing 1 black hat. Therefore the prisoner's action on the 10:00 lineup can be to test a possible hypothesis, not an impossible one.

It's not a matter of changing the number of lineups, but of using the 10:00 lineup to test a different hypothesis and avoid spending time confirming a hypothesis that all prisoners know is impossible once the prisoners see a minimum number of black hats.

 

[QuantumQuest]

The prisoners will not know in advance, but once a prisoner lines up and sees say 7 black hats, he knows that no other prisoner will see less than 6 black hats; and those that see 6 black hats will know that no other prisoner will see less than 5 black hats. Therefore, those prisoners that see 7 black hats and those that see 6 black hats will all come to the same conclusion, which is that no prisoners are seeing 0 black hats.

Therefore, there's no point in using the 10:00 lineup to test the hypothesis that some prisoner will move up because they see 0 black hats, as that hypothesis is impossible.

So, once the prisoners see 6 black hats or 7 black hats, then they can use the 10:00 lineup to say test a different hypothesis, like that some prisoner is seeing 1 black hat. Therefore the prisoner's action on the 10:00 lineup can be to test a possible hypothesis, not an impossible one.

It's not a matter of changing the number of lineups, but of using the 10:00 lineup to test a different hypothesis and avoid spending time confirming a hypothesis that all prisoners know is impossible once the prisoners see a minimum number of black hats.

Do the prisoners know in advance how many black hats are there? What if there is just one? Or two? Or three? Again, I'll state the obvious: there must be the first line-up where if there is just one black hat which the prisoner having it will know before this line-up, then he'll step forward. If none steps forward then we go to the second line-up etc. Prisoners cannot avoid any line-up and at the same time they need to use the outcome of the previous line-up - except the case that there is just one black hat, in order to deduce what is the correct thing to do. I cannot explain this in more simple terms.

 

[QuantumQuest]

and the total number of triangles in iteration n is $T_0 + T_1 + ... + T_n = 1 + 3 + 6 + ... + 3*n = 1 + \frac{3}{2}*n*(n+1)$:

This is not correct.

How to prove that each iteration $i$ will add exactly $3$ triangles to the scene...

Be careful here. Check it again.

 

[fbs7]

Do the prisoners know in advance how many black hats are there? What if there is just one? Or two? Or three? Again, I'll state the obvious: there must be the first line-up where if there is just one black hat which the prisoner having it will know before this line-up, then he'll step forward. If none steps forward then we go to the second line-up etc. Prisoners cannot avoid any line-up and at the same time they need to use the outcome of the previous line-up - except the case that there is just one black hat, in order to deduce what is the correct thing to do. I cannot explain this in more simple terms.

Alright; my last attempt at this: why is this not a solution?

(a) If the prisoner sees 0, 2, 4, 6, 8, 10 black hats then he steps up at 10:00
(b) If the prisoner sees 1, 3, 5, 7, 9, 11 black hats then he steps up at 10:05

 

[QuantumQuest]

Alright; my last attempt at this: why is this not a solution?

(a) If the prisoner sees 0, 2, 4, 6, 8, 10 black hats then he steps up at 10:00
(b) If the prisoner sees 1, 3, 5, 7, 9, 11 black hats then he steps up at 10:05

If you read post #44 carefully it's not difficult to understand it.

 

[fbs7]

I think I'm going to answer my own question. If the prisoners are killed immediately if even one walks up incorrectly even once, then the post above is not a solution, as there's 50% chance they will walk up with the wrong solution by 10:00. But, if they can walk up incorrectly at 10:00, then are not killed, then the walkup at 10:05 will be correct, and that will be a solution.

Therefore I suppose there is a rule to the problem, which is that the prisoners can only walk up once, at some time, that must be the right solution or they will all die immediately.

I didn't understand that rule from the writeups, so I tried to find shorter solutions with a smaller number of walkups, even if some of those walkups could be incorrect. The shortest one I could find in that form is the one above.

So, is it true that if the prisoners walk up incorrectly once they are killed?

 

[SpinFlop]

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.

Could you give an example of (or clarify) this? Given that you speak of 'smaller and smaller spikes', this lead me to believe that the limit at infinity is still zero, such as in the classic example of a sine wave in an exponentially decaying envelope:
$$ \lim_{n \rightarrow \infty}e^{-x}sin(x) = 0$$

 

[Infrared]

I mean that the spikes get narrower, not shorter. For example, on the interval $[n,n+1]$ (say for $n>0$), let the graph of $f$ be a triangle with vertices $(n,0),(n+2^{-n},1),(n+2\cdot 2^{-n},0)$ and zero on the rest of the interval.

Then $\int_n^{n+1}f=\frac{1}{2}\cdot 2\cdot 2^{-n}=2^{-n}$, so $\int_1^\infty f=\sum_{n=1}^\infty 2^{-n}=1$

 

[QuantumQuest]

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.

 

[Adel Makram]

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?

 

[member 659869]

High School 5:

Spoiler

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

 

[Infrared]

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]

@wrobel

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

 

[fresh_42]

@wrobel

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

Edited.