Timeline for What is the fairest order for stage-striking (and is it the Thue-Morse sequence)?
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 30, 2018 at 22:34 | comment | added | Claude Chaunier | And the common values for $v_0$ and $v_1$ are integers, unlike for other $n$'s. Could it be a consequence of $v_0$ = $v_1$? | |
| Nov 30, 2018 at 22:23 | comment | added | Claude Chaunier | There definitely is something going on with these $n$ of the form $2(\ell^2-1)$. The number of sequences reaching the minimum $|v_1-v_0|$ is big compared to other $n$'s. They are $23654$ for $\ell=4, n=30$ in the unrestricted case ($3746$ with the same number of 0's and 1's). While for $n=28$ they only are $6$ in the unrestricted case ($8$ for the minimum with the same number of 0's and 1's). There must be some structure connecting all those solutions. | |
| Nov 30, 2018 at 20:01 | history | edited | Claude Chaunier | CC BY-SA 4.0 |
Added a similar remarkable identity with as many 0's as 1's
|
| Nov 30, 2018 at 7:16 | comment | added | Claude Chaunier | The minima are different for $n=24, 26$ and $28$ for example. Take $n=24$. 110001000101000101001101 yields the unrestricted minimum $0.00000\,63595\,\dots$, but when restricting the sequences to have the same number $12$ of 0's and 1's, the sequence 100101010110000101111010 yields the restricted minimum $0.00001\,9884\dots$. | |
| Nov 28, 2018 at 22:41 | comment | added | Harry Altman | Interestingly the two minima are not always the same; they're first different for $n=15$. (I decided to include $n$ odd and allow sequences where the number of $0$'s and of $1$'s differ by $1$.) But I don't yet have counterexamples for even $n$; maybe those could be the same? Seems unlikely, but... | |
| Nov 28, 2018 at 22:29 | comment | added | Harry Altman | I'm realizing now that maybe I should've restricted to even $n$ and required an equal number of $0$'s as $1$'s, since otherwise we get something that works in this random scenario but not the original perfect-information scenario. But, whatever! The computations above show (reverse) Thue-Morse is still not optimal with that restriction, and the question without that restriction is still quite interesting. :) | |
| Nov 28, 2018 at 22:25 | comment | added | Harry Altman | Also worth noting: The total $n$ in these cases is is $2(k+1)^2-2$. So for $n$ of the form $2(k^2-1)$, we get an optimal difference of $0$. Nice! | |
| Nov 28, 2018 at 13:55 | history | edited | Claude Chaunier | CC BY-SA 4.0 |
added the word "once" without which it wasn't making sense.
|
| Nov 28, 2018 at 13:49 | comment | added | Claude Chaunier | Wow, thanks @RaphaelB4. I detailed your insightful one-line proof in the answer. | |
| Nov 28, 2018 at 13:47 | history | edited | Claude Chaunier | CC BY-SA 4.0 |
proved it following RaphaelB4's insight.
|
| Nov 28, 2018 at 12:04 | comment | added | RaphaelB4 | Hi Claude, your conjecture can be easily proved using that $ v_1(0^k b_1...b_n)+1=\frac{n+2+k}{n+2}(v_1(b_1...b_n)+1)$ | |
| Nov 28, 2018 at 11:52 | comment | added | Claude Chaunier | Oh well, maybe most sequences score $n-o(n)$. That's something to check. | |
| Nov 28, 2018 at 11:46 | comment | added | Claude Chaunier | Not only are those monotonic sequences of length $n = 2k(k+2)$ as fair as a sequence can ever get, but the score both players expect with them is asymptotically $n-o(n)$, leaving them both quite satisfied ! | |
| Nov 28, 2018 at 11:00 | history | answered | Claude Chaunier | CC BY-SA 4.0 |