4 ms·

I know the original problem. I'm curious how he obtains a deterministic solution for the version where the warden can switch the light-bulb state at random (exc

by hurin 11y ago

I know the original problem. I'm curious how he obtains a deterministic solution for the version where the warden can switch the light-bulb state at random (excerpt below). “I reserve the right to flip the light on or off between interrogations up to 12 times in total.” Maybe it's poorly worded?

justinpombrio 11y ago
You mean the Easy++ problem? The solution isn't very different from the solution to Easy (i.e. the original problem); it just takes longer to run. For the Hard problem, you're on your own. The wording is very careful :-)
- hurin 11y ago
  >> “I reserve the right to flip the light on or off between interrogations up to 12 times in total.” > The wording is very careful :-) Do you mean he can flip the switch 12 times in total between all interrogations? Or that between every interrogation he can flip the switch up to 12 times. That's what I mean by poorly worded.
  - justinpombrio 11y ago
    The former, hence the phrase "in total", and the number 12 instead of 1.
    - hurin 11y ago
      > The former, hence the phrase "in total", and the number 12 instead of 1. It wasn't very clear. >> You mean the Easy++ problem? The solution isn't very different from the solution to Easy (i.e. the original problem); it just takes longer to run. Btw what's the run-time on your easy++ solution? - I think the run-time on the solution to the regular problem with a single counter is around ~26 years, so all your prisoners will die before they can get released unless you're doing something more clever than the basic solution. Also I'm not sure I understand the difference between your Easy and Hard problems? I assume the prisoner who is not interrogated with the other inmates just estimates the run-time for their solution and waits (which I think is part of the original problem anyway ? )

4 ms·

I know the original problem. I'm curious how he obtains a deterministic solution for the version where the warden can switch the light-bulb state at random (exc

by hurin 11y ago

justinpombrio 11y ago
You mean the Easy++ problem? The solution isn't very different from the solution to Easy (i.e. the original problem); it just takes longer to run. For the Hard problem, you're on your own. The wording is very careful :-)
- hurin 11y ago
  >> “I reserve the right to flip the light on or off between interrogations up to 12 times in total.” > The wording is very careful :-) Do you mean he can flip the switch 12 times in total between all interrogations? Or that between every interrogation he can flip the switch up to 12 times. That's what I mean by poorly worded.
  - justinpombrio 11y ago
    The former, hence the phrase "in total", and the number 12 instead of 1.
    - hurin 11y ago
      > The former, hence the phrase "in total", and the number 12 instead of 1. It wasn't very clear. >> You mean the Easy++ problem? The solution isn't very different from the solution to Easy (i.e. the original problem); it just takes longer to run. Btw what's the run-time on your easy++ solution? - I think the run-time on the solution to the regular problem with a single counter is around ~26 years, so all your prisoners will die before they can get released unless you're doing something more clever than the basic solution. Also I'm not sure I understand the difference between your Easy and Hard problems? I assume the prisoner who is not interrogated with the other inmates just estimates the run-time for their solution and waits (which I think is part of the original problem anyway ? )