Timeline for Size of biggest mutually 0-1 string with odd mutual 1
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 1, 2016 at 10:22 | vote | accept | MR_BD | ||
| Sep 26, 2016 at 17:20 | answer | added | Narad Rampersad | timeline score: 2 | |
| Sep 26, 2016 at 14:39 | answer | added | Fedor Petrov | timeline score: 6 | |
| Sep 26, 2016 at 14:16 | comment | added | Max Alekseyev | This problem is in flavor of Odd/Even-towns discretemath.imp.fu-berlin.de/DMII-2011-12/linalgmethod.pdf | |
| Sep 26, 2016 at 14:06 | comment | added | MR_BD | @fedja Thanks for your helpful comment... i did not understand the agument of your last sentence... | |
| Sep 26, 2016 at 12:48 | comment | added | fedja | It is certainly exponential in $q$. Indeed, take $Q=3$. Then you can do $2$ strings. Now, for $q=RQ$ with odd $R$, you can choose one of those $2$ strings independently in each $6$-block giving you $2^R=2^{q/3}$ choices. On the other hand, they are exponentially fewer than the total number of strings. I doubt anybody can tell you the exact exponent (so that the example and the upper bound match), but I will be happy to be proved wrong. | |
| Sep 26, 2016 at 9:17 | history | asked | MR_BD | CC BY-SA 3.0 |