MathDB
Lamps with soft-buttons

Source: Indian Team Selection Test 2015 Day 3 Problem 3

July 11, 2015
combinatorics

Problem Statement

There are n≥2n\ge 2 lamps, each with two states: <spanclass=′latex−bold′>on</span><span class='latex-bold'>on</span> or <spanclass=′latex−bold′>off</span><span class='latex-bold'>off</span>. For each non-empty subset AA of the set of these lamps, there is a <spanclass=′latex−italic′>soft−button</span><span class='latex-italic'>soft-button</span> which operates on the lamps in AA; that is, upon <spanclass=′latex−italic′>operating</span><span class='latex-italic'>operating</span> this button each of the lamps in AA changes its state(on to off and off to on). The buttons are identical and it is not known which button corresponds to which subset of lamps. Suppose all the lamps are off initially. Show that one can always switch all the lamps on by performing at most 2n−1+12^{n-1}+1 operations.
Back to ProblemsView on AoPS