Skip to main content
MathOverflow

Return to Answer

added 42 characters in body
Source Link
Bennett McElwee
Bennett McElwee
  • 131
  • 5

I didn't think this would be possible with an infinite number of mathematicians, but Eric's solution is fantastic. It did take me a while to understand how it works, and I was confused because I think some of its inequalities are not quite right. So I have created this answer to fill in the gaps and clarify his great solution. If you get the urge to upvote this answer, please upvote Eric's first.

We take up Eric's solution at the line that says:

Then there exists an integer $N$ such that for every $i>N$, $M_i=v_i$.

And we continue:

Mathematician $i$ with $i<N$ can determine $N$. However mathematician $N$ cannot determine $N$ since they don't know whether $v_N=M_N$. So each mathematician with $i\geq N$ only knows that $N\leq i$.

Now if $i>N$, then $M_i=v_i$ by definition of $N$ so we know that mathematician $i$ could guess $P_i$ where

$$P_i = 1+v_i$$

and be correct. However, mathematician $i$ does not know this since they only know that $i\geq N$.

If $i\leq N$, then we know mathematician $i$ could guess $Q_i$ where

$$Q_i=1+\max\{M_{N},M_{N-1},\dots,M_{i+1},M_{i-1},\dots,M_1,M_0\}$$

and only one at most will be wrong. (This is a solution for the finite-mathematician version of this problem.) But mathematician $i$ only knows this if $i<N$.

Therefore for mathematician $i$, the strategy for guessing is as follows.

If there is a $K>i$ such that $M_K\neq v_K$, then $N>i$ and mathematician $i$ can determine $N$. They should guess $Q_i$:

$$H_i=1+\max\{M_{N},M_{N-1},\dots,M_{i+1},M_{i-1},\dots,M_1,M_0\}$$

If there is no such $K$ then they know that either $i>N$ or $i=N$. If $i>N$ then they could guess $P_i$ and be correct. If $i=N$ then they could guess $Q_i$ (and maybe end up making the only wrong guess). And since $i=N$, we get $Q_i=Q_N=1+\max\{M_{i-1},M_{i-2},\dots,M_1,M_0\}$$Q_i=Q_N=R_i$ where $R_i = 1+\max\{M_{i-1},M_{i-2},\dots,M_1,M_0\}$.

Since they don't know which of these cases holds, they should just guess $max\{P_i,Q_i\}$$max\{P_i,R_i\}$:

$$H_i=1+\max\{v_i,M_{i-1},M_{i-2},\dots,M_1,M_0\}$$

With this strategy, all mathematicians $i$ where $i>N$ will guess correctly; and all mathematicians $i$ where $i\leq N$ will guess correctly, except possibly one.

And that solution is exactly Eric's, just spelled out a bit more explicitly.

For me, the finite-mathematicians version of the problem is mindblowing; this infinite version even more so. I think more people should have their minds blown by it, and I hope this presentation will help.

I didn't think this would be possible with an infinite number of mathematicians, but Eric's solution is fantastic. It did take me a while to understand how it works, and I was confused because I think some of its inequalities are not quite right. So I have created this answer to fill in the gaps and clarify his great solution. If you get the urge to upvote this answer, please upvote Eric's first.

We take up Eric's solution at the line that says:

Then there exists an integer $N$ such that for every $i>N$, $M_i=v_i$.

And we continue:

Mathematician $i$ with $i<N$ can determine $N$. However mathematician $N$ cannot determine $N$ since they don't know whether $v_N=M_N$. So each mathematician with $i\geq N$ only knows that $N\leq i$.

Now if $i>N$, then $M_i=v_i$ by definition of $N$ so we know that mathematician $i$ could guess

$$P_i = 1+v_i$$

and be correct. However, mathematician $i$ does not know this since they only know that $i\geq N$.

If $i\leq N$, then we know mathematician $i$ could guess

$$Q_i=1+\max\{M_{N},M_{N-1},\dots,M_{i+1},M_{i-1},\dots,M_1,M_0\}$$

and only one at most will be wrong. (This is a solution for the finite-mathematician version of this problem.) But mathematician $i$ only knows this if $i<N$.

Therefore for mathematician $i$, the strategy for guessing is as follows.

If there is a $K>i$ such that $M_K\neq v_K$, then $N>i$ and mathematician $i$ can determine $N$. They should guess $Q_i$:

$$H_i=1+\max\{M_{N},M_{N-1},\dots,M_{i+1},M_{i-1},\dots,M_1,M_0\}$$

If there is no such $K$ then they know that either $i>N$ or $i=N$. If $i>N$ then they could guess $P_i$ and be correct. If $i=N$ then they could guess $Q_i$ (and maybe end up making the only wrong guess). And since $i=N$, we get $Q_i=Q_N=1+\max\{M_{i-1},M_{i-2},\dots,M_1,M_0\}$.

Since they don't know which of these cases holds, they should just guess $max\{P_i,Q_i\}$:

$$H_i=1+\max\{v_i,M_{i-1},M_{i-2},\dots,M_1,M_0\}$$

With this strategy, all mathematicians $i$ where $i>N$ will guess correctly; and all mathematicians $i$ where $i\leq N$ will guess correctly, except possibly one.

And that solution is exactly Eric's, just spelled out a bit more explicitly.

For me, the finite-mathematicians version of the problem is mindblowing; this infinite version even more so. I think more people should have their minds blown by it, and I hope this presentation will help.

I didn't think this would be possible with an infinite number of mathematicians, but Eric's solution is fantastic. It did take me a while to understand how it works, and I was confused because I think some of its inequalities are not quite right. So I have created this answer to fill in the gaps and clarify his great solution. If you get the urge to upvote this answer, please upvote Eric's first.

We take up Eric's solution at the line that says:

Then there exists an integer $N$ such that for every $i>N$, $M_i=v_i$.

And we continue:

Mathematician $i$ with $i<N$ can determine $N$. However mathematician $N$ cannot determine $N$ since they don't know whether $v_N=M_N$. So each mathematician with $i\geq N$ only knows that $N\leq i$.

Now if $i>N$, then $M_i=v_i$ by definition of $N$ so we know that mathematician $i$ could guess $P_i$ where

$$P_i = 1+v_i$$

and be correct. However, mathematician $i$ does not know this since they only know that $i\geq N$.

If $i\leq N$, then we know mathematician $i$ could guess $Q_i$ where

$$Q_i=1+\max\{M_{N},M_{N-1},\dots,M_{i+1},M_{i-1},\dots,M_1,M_0\}$$

and only one at most will be wrong. (This is a solution for the finite-mathematician version of this problem.) But mathematician $i$ only knows this if $i<N$.

Therefore for mathematician $i$, the strategy for guessing is as follows.

If there is a $K>i$ such that $M_K\neq v_K$, then $N>i$ and mathematician $i$ can determine $N$. They should guess $Q_i$:

$$H_i=1+\max\{M_{N},M_{N-1},\dots,M_{i+1},M_{i-1},\dots,M_1,M_0\}$$

If there is no such $K$ then they know that either $i>N$ or $i=N$. If $i>N$ then they could guess $P_i$ and be correct. If $i=N$ then they could guess $Q_i$ (and maybe end up making the only wrong guess). And since $i=N$, we get $Q_i=Q_N=R_i$ where $R_i = 1+\max\{M_{i-1},M_{i-2},\dots,M_1,M_0\}$.

Since they don't know which of these cases holds, they should just guess $max\{P_i,R_i\}$:

$$H_i=1+\max\{v_i,M_{i-1},M_{i-2},\dots,M_1,M_0\}$$

With this strategy, all mathematicians $i$ where $i>N$ will guess correctly; and all mathematicians $i$ where $i\leq N$ will guess correctly, except possibly one.

And that solution is exactly Eric's, just spelled out a bit more explicitly.

For me, the finite-mathematicians version of the problem is mindblowing; this infinite version even more so. I think more people should have their minds blown by it, and I hope this presentation will help.

Source Link
Bennett McElwee
Bennett McElwee
  • 131
  • 5

I didn't think this would be possible with an infinite number of mathematicians, but Eric's solution is fantastic. It did take me a while to understand how it works, and I was confused because I think some of its inequalities are not quite right. So I have created this answer to fill in the gaps and clarify his great solution. If you get the urge to upvote this answer, please upvote Eric's first.

We take up Eric's solution at the line that says:

Then there exists an integer $N$ such that for every $i>N$, $M_i=v_i$.

And we continue:

Mathematician $i$ with $i<N$ can determine $N$. However mathematician $N$ cannot determine $N$ since they don't know whether $v_N=M_N$. So each mathematician with $i\geq N$ only knows that $N\leq i$.

Now if $i>N$, then $M_i=v_i$ by definition of $N$ so we know that mathematician $i$ could guess

$$P_i = 1+v_i$$

and be correct. However, mathematician $i$ does not know this since they only know that $i\geq N$.

If $i\leq N$, then we know mathematician $i$ could guess

$$Q_i=1+\max\{M_{N},M_{N-1},\dots,M_{i+1},M_{i-1},\dots,M_1,M_0\}$$

and only one at most will be wrong. (This is a solution for the finite-mathematician version of this problem.) But mathematician $i$ only knows this if $i<N$.

Therefore for mathematician $i$, the strategy for guessing is as follows.

If there is a $K>i$ such that $M_K\neq v_K$, then $N>i$ and mathematician $i$ can determine $N$. They should guess $Q_i$:

$$H_i=1+\max\{M_{N},M_{N-1},\dots,M_{i+1},M_{i-1},\dots,M_1,M_0\}$$

If there is no such $K$ then they know that either $i>N$ or $i=N$. If $i>N$ then they could guess $P_i$ and be correct. If $i=N$ then they could guess $Q_i$ (and maybe end up making the only wrong guess). And since $i=N$, we get $Q_i=Q_N=1+\max\{M_{i-1},M_{i-2},\dots,M_1,M_0\}$.

Since they don't know which of these cases holds, they should just guess $max\{P_i,Q_i\}$:

$$H_i=1+\max\{v_i,M_{i-1},M_{i-2},\dots,M_1,M_0\}$$

With this strategy, all mathematicians $i$ where $i>N$ will guess correctly; and all mathematicians $i$ where $i\leq N$ will guess correctly, except possibly one.

And that solution is exactly Eric's, just spelled out a bit more explicitly.

For me, the finite-mathematicians version of the problem is mindblowing; this infinite version even more so. I think more people should have their minds blown by it, and I hope this presentation will help.