Timeline for Binary search with maximum consecutive lies about "is X in subset S?"
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 9, 2013 at 8:43 | comment | added | Borislav Stanimirov | Now that I found out that this was a IMO problem, I found this link: imo-official.org/problems/IMO2012SL.pdf It states that s = 2, 3, 4, 7, 11, 17 for k = 1, 2, 3, 4, 5, 6. This is consistent with my experiments for k = 2 and 3, but apart from "a computer search shows" it doesn't mention how they calculated those values. | |
| Dec 9, 2013 at 7:51 | comment | added | Borislav Stanimirov | Unfortunately, while the original problem is identical to the one in the link, nobody there seems to be discussing or considering my continuation - finding a minimum s for a given k. | |
| Dec 8, 2013 at 21:08 | review | Close votes | |||
| Dec 9, 2013 at 13:24 | |||||
| Dec 8, 2013 at 20:49 | comment | added | domotorp | This was an IMO problem, I think this should help: polymathprojects.org/2012/07/12/… | |
| Dec 8, 2013 at 14:50 | comment | added | Borislav Stanimirov | It seems to me that both problems are only superficially similar. If we cap the number of lies, it's obvious that the secret number can be found. And since the problem from the link deals with the number of questions one player needs to ask and this problem deals with minimizing the size of the set of candidates, I don't think they're related. | |
| Dec 8, 2013 at 14:15 | history | edited | Borislav Stanimirov | CC BY-SA 3.0 |
typos
|
| Dec 8, 2013 at 12:11 | comment | added | Joel David Hamkins | Related: mathoverflow.net/questions/32269/…. | |
| Dec 8, 2013 at 10:04 | review | First posts | |||
| Dec 8, 2013 at 10:07 | |||||
| Dec 8, 2013 at 9:47 | history | asked | Borislav Stanimirov | CC BY-SA 3.0 |