AlgoBlog: Spinning switch

[combinator]

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

Comments

[dvarin]

You left out the bit about the emitters and recognizers and positions having to be evenly spaced. Without that constraint it becomes easy to create a setup that satisfies your problem statement by just cramming all the recognizers into one nth of the wheel.

[combinator]

That's true. Good point.

[platypuslord]

I visualize this as follows:

dial: 0 1 2 3 4
recv: 0 1 2 3 4
emit: 0 2 4 1 3The first row gives the position of the dial, aka, which number is facing the pointer on the bottom, aka, the number of clicks that the dial has been turned

[combinator]

Very nice presentation! My facility with number theory isn't great, so I'll have to think about why having the third row be the sum of the first two is equivalent to a feasible configuration. Also I'll need to think about why the sum mod n works out as you mention. I keep thinking about Gauss' formula which gives n*(n-1)/2, but this is somewhat irrelevant as we are not working with a field here.