# Simple combinations - Party Lamps [IOI 98]

You are given N lamps and four switches. The first switch toggles all lamps, the second the even lamps, the third the odd lamps, and last switch toggles lamps $1, 4, 7, 10, \dots$

Given the number of lamps, N, the number of button presses made (up to $10,000$), and the state of some of the lamps (e.g., lamp $7$ is off), output all the possible states the lamps could be in.

Naively, for each button press, you have to try $4$ possibilities, for a total of $4^{10000}$ (about $10^{6020}$ ), which means there's no way you could do complete search (this particular algorithm would exploit recursion).

Noticing that the order of the button presses does not matter gets this number down to about $10000^4$ (about $10^{16}$ ), still too big to completely search (but certainly closer by a factor of over $10^{6000}$ ).

However, pressing a button twice is the same as pressing the button no times, so all you really have to check is pressing each button either 0 or 1 times. That's only $2^4 = 16$ possibilities, surely a number of iterations solvable within the time limit.

Above is a simple problem with a brief explanation of the solution. What I am not able to conclude is the part where it says order doesn't matter and switches solution from $4^{10000}$ to $10000^4$. Any idea ?

-
$24=16$? Shouldn't that be $2^4=16$? – Gerry Myerson Jan 20 '13 at 6:22

## 2 Answers

If order doesn't matter then all that matters is how many times each switch is toggled. There are four switches; let's say the first one is toggled $a$ times, the second, $b$ times, the third, $c$ times, the fourth, $d$ times. Since the total amount of toggling is given as at most $10000$, we have $$a+b+c+d\le10000$$ So now consider $10004$ stones lying in a line on the ground, and paint $4$ of them blue. This leaves $10000$ unpainted stones in $5$ groups, corresponding to the numbers $a$, $b$, $c$, $d$, and $10000-(a+b+c+d)$. So, the number of solutions of the displayed inequality is $10004$-choose-$4$, which is very roughly $10000^4$. A somewhat less rough estimate would be $(1/24)(10000^4)$.

-

The naive solution works in this way: There are four buttons we can push. We need to account for at most $10000$ button presses. Let's make it easier and say we only have to account for at most three button presses. Then our button-press 1 is either the first button, the second one, the third one, or the fourth one. Similarly for button presses 2 and 3. So there are four options at each of the three decisions, thus $4^3$. The same logic gets $4^{10000}$.

(Actually, there are some other options: this counts only the $10000$-press cases; not, say, the $4586$-press cases. But the point is that it's too big, so the point stands.)

The better solution works this way. Since pressing any button only affects the same lightbulb, then we can separate it into four problems about pressing a button at most $10000$ times. Again, let's count only the $10000$-press cases. We can think of a button press as a square, and then put the squares into four groups, where each group represents what buttons was pressed. It now doesn't matter what order the button-presses happened. All that matters is the number of times the buttons were pressed. So then you choose how to arrange $10000$ objects into $4$ groups, which is ${10000\choose 4}\approx 10000^4$ [for some definitions of $\approx$].

(Again, this simplifies things because we only considered the $10000$-press cases, but again the point is that it's too big.)

That idea is taken to the extreme in the best solution, which notices that the parity (even-or-odd-ness) is the only thing that really matters about the number of times each button was pressed.

-