There are n doors, and n buttons that control them.
combinatorics/doors.and.buttons New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
There are n doors, and n buttons that control them. Each button changes the state (open->closed or closed->open) of some subset of the doors (possibly zero of them). You aren't told which button affects which doors; you can only learn that by pressing buttons. In how few moves can you be sure of getting all the doors open (if any combination of buttons opens them all)? What if you cannot see which doors a button press affects? [ Editor: problem statement reconstructed from the problem text quoted in the thread and Seth Breidbart's replies; the original posting is not in the collected material. The starting state of the doors is not stated there. ]
Show solution
In article <3255E372.7C7C@ix.netcom.com>, Dennis A. Sevakis <spinman@ix.netcom.com> wrote: >>> The problem states that buttons can change 0 doors. I take this to >>> mean that it is possible to have one button open all the doors, and >>> n - 1 buttons do nothing. The best case here would be 1 press to >>> open all the doors; the worst case would be n presses. Except that you aren't given the information about which button affects which doors, you can only learn that by pressing buttons. >Of course, the problem asks, "...in how few moves can it be solved?", >not, "...given that the problem is solvable, what is the greatest >number of moves you ever have to make to solve it?" They are not >identical questions. "In how few moves can it be solved" generally means worst-case, especially when the best case is trivial. >It's not that I don't believe you, but no PARTICULAR examples of where >it takes 2n-1 presses constitute proof that they are indeed the worst >cases. No, that just shows that 2n-1 is a lower bound. Other postings have already shown it to be an upper bound. >You also mention that if you can't "...observe what's going on", it >takes (2^n)-1 presses. What do you mean by "...can observe what's >going on"? Can see which doors are affected by the button you press. >It seems to me that if you can't observe what's going on, you may >indeed never end up solving the problem (we're talking worst cases, >right?). Please explain what you mean. With 2^n - 1 presses, I can guarantee that at some point all the doors were open, if there's any combination of buttons that opens them all. >How would you go about proving it for both your situations (oblivious >and non-oblivious) for all n? Non-oblivious is done. For oblivious, any Gray code will work. -- Seth Breidbart <sethb@panix.com> [ Editor: so the answer is 2n-1 presses in the worst case when you can see the doors, and 2^n - 1 when you cannot. The postings with the upper-bound proof and the worst-case examples for 2n-1 are not in the collected material. ]