More On Prisoners and Switches...
The previous post here was on this puzzle.
One would like to say a bit more on the spokesman based protocol itself, given in the solution available online and its generalization to cases where there are MORE THAN 2 SWITCHES.
One obvious thought is: let there be 5 switches. The prisoners divide themselves into two equal groups; each group elects a spokesman. Group A works with switches 1 and 2. Group B with switches 3 and 4. Each group runs the same protcol as given in the online solution. Switch 5 is used by spokesman of either group (once) to indicate that his group has finished. And once he has toggled switch 5, the spokesmen wait for switch 5 to be toggled again - on his subsequent visits, he toggles some other switch not 5. Thus, the spokesman of the group which finishes first can know that the other group has also finished and can give the answer - we have applied a straightforward recursion to the already known 'base' solution.
Let us revisit the solution to the original puzzle (2 switches A and B): there, B is a dummy or 'noise' switch used only when prisoners have to necessarily toggle a switch - the information transfer from each prisoner is thru switch A (we could call this the 'info' switch). This implies two groups of prisoners can share their 'noise switch'. Thus we readily see that the above simple recursion works just as well with 4 rather than 5 switches - group A uses switches 1 and 2, group B uses 1 and 3 (1 being the shared noise switch); switch 4 can be used by the spokesmen to indicate the respective groups are done.
A question suggests itself: Is this the best that can be done with 4 switches (switch 4 seems seriously underutilized above!)? And if only 3 switches are there can one improve upon the 'base' 2-switch method?
What about improvements to the protocol if more switches, say M are available? Again an obvious thought is: Keep 1 switch aside, keep one more switch as a noise switch and divide the prisoners into as many groups as there are switches remaining - ie M-2 groups; each group has a spokesman. There could also be a 'grand spokesman' elected among these spokesmen. One could have an info switch for each group of prisoners, all groups share the same noise switch (kept aside above). Further, we could play the base version of the game only among spokesmen of the groups at a higher level -using the 1 switch kept aside at the beginning as the info switch and the common noise switch remains the noise switch at this level as well.The 'grand spokesman' answers finally.
Question: How to improve upon this?
One more thought: as each spokesman joins the higher level game, he also can bring with him the 'info' switch of his former group (his ex-teammates will only play with the common noise switch for the rest of the game; their job is done; moreover, they dont need to be informed that their group has decided; this is crucial) which can possibly be used to speed up the decision making among spokesmen (how this could be done is not clear; switches being added at 'runtime'could be difficult). Probably a key difficulty here is that spokesmen graduate to the higher level NOT simultaneously. Still, in this protocol, once a spokesmen has started playing the higher level game, the info switch of his original group remains idle for the rest of the show - that is probably wasteful :)
One would like to say a bit more on the spokesman based protocol itself, given in the solution available online and its generalization to cases where there are MORE THAN 2 SWITCHES.
One obvious thought is: let there be 5 switches. The prisoners divide themselves into two equal groups; each group elects a spokesman. Group A works with switches 1 and 2. Group B with switches 3 and 4. Each group runs the same protcol as given in the online solution. Switch 5 is used by spokesman of either group (once) to indicate that his group has finished. And once he has toggled switch 5, the spokesmen wait for switch 5 to be toggled again - on his subsequent visits, he toggles some other switch not 5. Thus, the spokesman of the group which finishes first can know that the other group has also finished and can give the answer - we have applied a straightforward recursion to the already known 'base' solution.
Let us revisit the solution to the original puzzle (2 switches A and B): there, B is a dummy or 'noise' switch used only when prisoners have to necessarily toggle a switch - the information transfer from each prisoner is thru switch A (we could call this the 'info' switch). This implies two groups of prisoners can share their 'noise switch'. Thus we readily see that the above simple recursion works just as well with 4 rather than 5 switches - group A uses switches 1 and 2, group B uses 1 and 3 (1 being the shared noise switch); switch 4 can be used by the spokesmen to indicate the respective groups are done.
A question suggests itself: Is this the best that can be done with 4 switches (switch 4 seems seriously underutilized above!)? And if only 3 switches are there can one improve upon the 'base' 2-switch method?
What about improvements to the protocol if more switches, say M are available? Again an obvious thought is: Keep 1 switch aside, keep one more switch as a noise switch and divide the prisoners into as many groups as there are switches remaining - ie M-2 groups; each group has a spokesman. There could also be a 'grand spokesman' elected among these spokesmen. One could have an info switch for each group of prisoners, all groups share the same noise switch (kept aside above). Further, we could play the base version of the game only among spokesmen of the groups at a higher level -using the 1 switch kept aside at the beginning as the info switch and the common noise switch remains the noise switch at this level as well.The 'grand spokesman' answers finally.
Question: How to improve upon this?
One more thought: as each spokesman joins the higher level game, he also can bring with him the 'info' switch of his former group (his ex-teammates will only play with the common noise switch for the rest of the game; their job is done; moreover, they dont need to be informed that their group has decided; this is crucial) which can possibly be used to speed up the decision making among spokesmen (how this could be done is not clear; switches being added at 'runtime'could be difficult). Probably a key difficulty here is that spokesmen graduate to the higher level NOT simultaneously. Still, in this protocol, once a spokesmen has started playing the higher level game, the info switch of his original group remains idle for the rest of the show - that is probably wasteful :)
posted by R.Nandakumar @ 10:58 AM
0 Comments:
Post a Comment
<< Home