Sunday, January 15, 2006

And after a long hiatus, a math puzzle.

I have a "device" which can be configured via n ON/OFF switches and I want to test that device with every possible combination of settings for those n switches.

1) (Trivial) How many combinations are there of all possible settings for the n switches?

2) (Slightly trickier) Imagine that there is a "cost" associated with flipping a switch. (Perhaps they're big switches and you have to manually yank them from ON to OFF or back again. Or maybe it just takes time to flip a switch, who knows?)

How can you arrange the order of all possible tests to absolutely minimize the total number of switches you have to flip? (The theoretical minimum would, of course, be no more than one switch being flipped every single time between consecutive tests. How close can you come to that ideal?)

(Update: Replying to the first commenter, let's assume that the switches are all initially OFF. I don't think it would make any difference in starting with some other initial configuration, but I'd be fascinated if it did.)

3) (Even trickier) I'm not sure how to ask this formally so perhaps someone can help out. Imagine that switches "wear out" after a certain number of flips. so you want to spread the number of flips approximately evenly across all switches.

Clearly, to do this, you're going to have to compromise and increase the total number of flips, but you're willing to pay that price if you can do "wear-levelling" across the switches (for some undefined but reasonably obvious definition of "wear-levelling").

I'm not sure how to phrase the corresponding question, so consider this an open discussion.

Do not post solutions yet. Solutions will be accepted starting Monday, noon, EST. Until then, you should only ask questions in the comments section. Any submitted solutions posted before then will be deleted.


wolfa said...

What is the initial configuration of the switches? Am I allowed to choose one to lower the costs in (2) or (3), or are they necessarily all off?

CC said...


Good point. See "Update" in original posting.