AlgoBlog: Spinning switch
I don't have full proofs for this yet. I got the idea from here (entry of 23 May 2005), though note that the original question can be solved by a much simpler argument.
You have a device with n settings. To allow the user to select a setting, you have a rotating dial with n [evenly spaced] distinct positions. The inside edge of the dial consists of n different signal emitters. This edge rests on an internal cylinder with n different recognizers corresponding to the emitters. You would like to configure the dial such that for each position, exactly one emitter lines up with its corresponding recognizer. This way, your device will know what setting the user has selected. Let's say that the settings are numbered 0, ..., n - 1 and you would like each counterclockwise turn of the dial to increment the setting mod n. Two questions: For what values of n is this feasible, and what is an efficient algorithm to generate a configuration for a feasible n?
[I visualized the numbers on the dial itself and a fixed pointer, which is why I thought counterclockwise. If you visualize the numbers in fixed positions around the dial and a pointer on the dial, clockwise makes more sense.]
You have a device with n settings. To allow the user to select a setting, you have a rotating dial with n [evenly spaced] distinct positions. The inside edge of the dial consists of n different signal emitters. This edge rests on an internal cylinder with n different recognizers corresponding to the emitters. You would like to configure the dial such that for each position, exactly one emitter lines up with its corresponding recognizer. This way, your device will know what setting the user has selected. Let's say that the settings are numbered 0, ..., n - 1 and you would like each counterclockwise turn of the dial to increment the setting mod n. Two questions: For what values of n is this feasible, and what is an efficient algorithm to generate a configuration for a feasible n?
[I visualized the numbers on the dial itself and a fixed pointer, which is why I thought counterclockwise. If you visualize the numbers in fixed positions around the dial and a pointer on the dial, clockwise makes more sense.]