who wrote: A house has an even number of lamps distributed among its rooms in such a way that there are at least three lamps in every room. Each lamp shares a switch with exactly one other lamp, not necessarily from the same room. Each change in the switch shared by two lamps changes their states simultaneously. Prove that for every initial state of the lamps there exists a sequence of changes in some of the switches at the end of which each room contains lamps which are on as well as lamps which are off. Let's prove that given an initial configuration with at least one room $ r_{1}$ having all lamps in the same position, we can reduce the number of such rooms by one. Switch a lamp in $ r_{1}$. If that lamp is connected to another one in $ r_{1}$, we're done (because there are at least three lamps here). Otherwise, we've affected another room $ r_{2}$. If $ r_{2}$ now has lamps in both states, we're finished. Otherwise, we've just turned it into a monochromatic room. Choose a lamp in it, different from the one just switched, and switch it. We keep doing this, each time choosing a lamp different from the ones already switched, until we first reach a room we've been in before: $ r_{m} = r_{n}$ for some $ m > n$. Before making the last move, the room $ r_{n}$ had been left with one room on and two off, or vice-versa. Our last move affects one of the two lamps in $ r_{n}$ which share the same state, so $ r_{m} = r_{n}$ will have lamps of both states, as will all rooms we've been through, including $ r_{1}$. We have thus reduced the number of rooms which have all lamsp in the same position.

Let's call rooms which have all bulbs in the same state boring and all other rooms interesting. Two lamps are called friends if they share the same switch, and two lamps are called neighbors if they are in the same room (note that two lamps can be both friends and neighbors). A room containing two lamps which are friends is called narcissist and all other rooms are called generous. Let there be a total of $n$ rooms in the house. We induct on $n.$ The base case $n=1$ is trivial: note that there must be at least four lamps (since there are an even number of lamps in the house). If one of them is in a different state than the others, we're done. Otherwise, pick two friends and change their states. Now, suppose our assertion holds true for $j$ rooms. We need to show that if we add another room in the house, we shall still be able to find a sequence of change of states which leads to all the rooms being interesting. Label the rooms $\{R_1, R_2, \cdots , R_j, R_{j+1}\}.$ Claim: There exists a sequence of change of states which leads to all the rooms $R_1, R_2, \cdots , R_j$ being interesting. Proof: By our inductive hypothesis, if there weren't any new room $R_{j+1},$ there would exist such a sequence of change of states. Now, if no lamp in $R_{j+1}$ were friends with a lamp in one of the other rooms, adding this new room wouldn't affect this sequence at all. What we do when adding the new room disturbs this state of sequence is mimicking the friendship between two lamps. Consider two lamps $L_1$ and $L_2$ which were friends in the original configuration of $j$ rooms but aren't friends anymore after another room has been added. We can still impose some rules upon ourselves to make $L_1$ and $L_2$ look like friends. That is, we vow that whenever we change the state of $L_1,$ we shall also change the state of $L_2.$ This keeps the sequence of change of states undisturbed. $\blacksquare$ So suppose all the rooms $R_1, R_2, \cdots , R_j$ are interesting. If $R_{j+1}$ is interesting as well, we're done. So let $R_{j+1}$ be boring. If $R_{j+1}$ were narcissist as well, we'd be done because changing the state of two of its lamps would keep the lamps in the other rooms unaffected and make $R_{j+1}$ interesting. Let's choose a lamp in $R_{j+1},$ which makes $R_{j+1}$ interesting. Changing its state affects the state of a lamp in another room. If that room is still interesting, we're done. Suppose that room is boring. If it were narcissist, we'd be done because then we could change the state of two of the lamps in it without affecting any of the others. Then, choose another lamp in that room and change its state. Note that that makes that room interesting again. Keep doing this operation until we reach another lamp in the room $R_{j+1}$ again. That makes two of the lamps in $R_{j+1}$ in a different state from the others, so $R_{j+1}$ is interesting and so are all of the other rooms. Hence, we're done. $\blacksquare$

We represent a lamp which is on by $1$ and the one off by $0$.Call a room unattained if its lamps are either all on or all off, and attained otherwise.Call two rooms $P$ and $Q$ connected if there exists a pair of lamps among them which have a common switch. If two unattained rooms are connected then we change the state of a pair of lamps connected among them.This decreases the number of unattained rooms.If no two unattained rooms are connected among themselves then each of them are only connected to attained rooms.If there exists an attained room which is connected to one of the unattained rooms and has atleast two on and two off lamps then change the state of a pair of lamps between that attained room and the corresponding unattained room.Again this decreases the number of unattained rooms.In fact we cannot decrease the number of unattained rooms by this process only when every unattained room is connected to an attained room and the state of the connected lamp of the attained room is the only lamp of that state in the attained room.This also means that the two rooms share a switch only among one pair of lamps. (Let us call this kind of connected rooms poorly-connected) In this case,change of state between a pair of connected lamps between two rooms makes the attained room unattained and vice versa.If the newly obtained unattained room is connected to an unattained room we can reduce the number of unattained rooms by previous paragraph.Otherwise the originally attained room was connected to another attained room poorly.Going like this we see that this generates new poorly connected attained rooms to avoid the decrease of unattained rooms.Since the number of attained rooms is not infinite there must an attained or unattained room connected not poorly to an attained room.Contradiction! This means that this situation cannot arise. Finally that we have described a method of decreasing the number of unattained rooms,we can induct on the same,the base case being trivial.

Beautiful problem! I am short on time so will provide a sketch for now.

Can we solve this using induction on the number of switches??

This post is unfortunately left out inadvertently

Solution from Twitch Solves ISL: First, we interpret the problem in a graph-theoretic language: We interpret the problem as a graph $G$ with rooms corresponding to vertices and switches with edges (which may include self-loops). The only condition is that the minimal degree is at least $3$ (where self-loops contribute $2$ to the degree). The edges come in two colors, which we call aligned (switches between lamps of the same state) or clashing (switches between lamps of different states). We wish to label the endpoints of each edge with $0$'s and $1$'s (corresponding to ``off'' and ``on'') such that aligned edges have $00$ or $11$ on their endpoint; clashing edges have $01$ or $10$ on their endpoint; every vertex has both $0$'s and $1$'s written (we call such edges happy). For simplicity, we assume (WLOG) the graph $G$ is connected. We will also assume $|V(G)| > 2$ (the case $|V(G)|=2$ is easy). We describe an algorithm to do so: it takes place in several steps. Step 1. Let $T$ be a spanning tree of $G$, and root the tree $T$ by taking any non-leaf $v_0$. Start by assigning all edges of $v_0$ in $T$ in such a way that $v_0$ is happy. Then starting from $v_0$ and following the pattern, label all edges of $T$ such that all vertices of $v_0$ become happy except for the leaves (which will only have one label). Step 2. Let $H$ be the set of leaves of $T$, considered also an induced subgraph of $T$. Every vertex of $H$ has at least one label. If we take a spanning forest of $H$, then we can proceed similarly as in Step 1 until there is at most one vertex in each connected component of $H$ which is not happy. Step 3. Consider the set $S$ of remaining unhappy vertices; the set $S$ is an independent set, by construction. Because the minimal degree is $3$, they each have at least one more edge. So they can be made happy. We then label any remaining edges of $G$ arbitrarily; since all vertices are happy already it doesn't matter how. A cartoon of the process is given below. [asy][asy] size(9cm); draw(box((-4,-1), (4,1)), blue+dashed); label("$H$", (4,1), dir(90), blue); pair v0 = (0,4); pair w1 = (-3,2); pair w2 = (-1.5,2); pair w3 = ( 1,2); pair w4 = ( 3,2); draw(v0--w1); draw(v0--w2); draw(v0--w3, lightgrey); draw(v0--w4); pair x1 = (-3,0); pair x2 = (-1.5,0); pair x3 = (-0.5,0); pair x4 = (2,0); pair x5 = (3,0); draw(w1--x1, lightgrey); draw(w2--x2); draw(w3--x3, lightgrey); draw(w3--x4); draw(w4--x5, lightgrey); dot(v0); dot(w1); dot(w2); dot(w3); dot(w4); draw(x1..(-1,-0.5)..x3, blue); draw(x3..(1,-0.5)..x4, paleblue); draw(x2..(0,-0.8)..x5, blue); dot(x1, blue); dot(x2, blue); dot(x3, blue); dot(x4, blue); dot(x5, blue); draw(box(x4+(-0.2,-0.2), x4+(0.2,0.2)), red); draw(box(x5+(-0.2,-0.2), x5+(0.2,0.2)), red); defaultpen(fontsize(8pt)); void main(string s1, string s2, pair X, pair Y, pair t1, pair t2) { label(s1, 0.85*X+0.15*Y, t1*dir(Y-X)); label(s2, 0.85*Y+0.15*X, t2*dir(Y-X)); } main("0", "0", v0, w1, dir(-90), dir(-90)); main("1", "1", v0, w2, dir(10), dir(120)); main("0", "1", v0, w3, dir(-10), dir(-120)); main("0", "0", v0, w4, dir(90), dir(90)); main("1", "0", w1, x1, dir(90), dir(90)); main("0", "0", w2, x2, dir(90), dir(90)); main("0", "1", w3, x3, dir(90), dir(90)); main("1", "1", w3, x4, dir(90), dir(90)); main("1", "0", w4, x5, dir(90), dir(90)); label("1", x1, dir(-15)*2.5, blue); label("1", x3, dir(195)*2.5, blue); label("0", x3, dir(-15)*2.5, blue); label("1", x4, dir(195)*2.5, blue); label("1", x2, dir(-15)*2.5, blue); label("0", x5, dir(195)*2.5, blue); [/asy][/asy] The edges used in Step 1 and the tree $T$ itself are black; the labeling is done from top to bottom. The spanning forest of $H$ and its vertices are drawn in blue; the labeling is done from left to right. The vertices of $S$ are colored red and one more edge is used for each of them (not shown). Clashing edges are drawn in a lighter color than aligned edges.

Wow this was such a cool problem! And I also used graphs! Consider a graph $G$ where the rooms are the vertices. Let each edge denote a switch connecting a lamp at one room to a lamp at a different room (we allow loops and multiple edges between two vertices). Define a cycle in $G$ in the usual way (but here we also consider cycles with only one vertex or only two vertices). Call a vertex $V$ just-fixed if all but one lamp in $V$ are in the same state, broken if all lamps in $V$ are the same state, and normal-fixed otherwise. Further a vertex is called fixed if it is just-fixed or normal-fixed. Our goal is to get all the vertices to be fixed. Claim: Let $C$ be any cycle in $G$. Then all the vertices in $C$ can be fixed. Proof: i)If the cycle is a loop: Then two lamps $L_1,L_2$ in one vertex (say $V$) share a switch. If $L_1,L_2$ are in different states initially, then they can never be in the same states by any sequence of switches. Otherwise if $L_1,L_2$ are in the same state, then if at any time, $V$ is broken, then we simply change the states of both $L_1,L_2$ and $V$ will be normal-fixed. ii)If the cycle is not a loop: Denote the cycle $C$ by $V_1-V_2-\dots-V_{k}-V_1$, where $k\geq 2$. Let the edge/switch between vertices $V_i$ and $V_{i+1}$ be denoted by $e_i$ (here $V_{k+1}=V_1$). Now perform the following algorithm (call it ALGORITHM) repeatedly- "Choose the smallest index $j$ such that $V_j$ is broken. Change the switch $e_j$." If we can stop before reaching $V_k$ then all the vertices will have been fixed. Otherwise suppose we reach $V_k$ and it is broken. Then change $e_k$. Now note that $V_k$ is just-fixed. If $V_1$ becomes broken, then run ALGORITHM again as long as we do not reach $V_{k-1}$. If we stop before that, then done. If $V_{k-1}$ is broken, change $e_{k-1}$. Since $e_k$ and $e_{k-1}$ operate on different lamps in $V_k$, so changing $e_{k-1}$ makes $V_k$ normal-fixed and we can finally stop ALGORITHM. Hence all vertices in $C$ have been fixed. $\square$ Now consider all connected sub-graphs in $G$. Since for each $V\in G$, $\deg(V)\geq 3$, we know that none of the sub-graphs is a tree (connected graph with no cycles), since it is well-known that a tree must have at least two vertices with degree 1. Now just consider any broken vertex $A_1$ and a path $A_1-A_2-\dots-A_m-C$ where $C$ denotes a cycle $-V_1-\dots-V_{k}-V_1$. Again let $f_i$ denote a switch/edge between $A_i$ and $A_{i+1}$. Now run ALGORITHM (replace $V$ with $A$ and $e$ with $f$) on the vertices $A_1,A_2,\dots,A_m$. If we stop before reaching $A_m$, we are done. If $A_m$ needs to be fixed, then change the switch between $A_m$ and $V_1$. Now our Claim will take care of the cycle $C$. Thus all vertices can be fixed. $\blacksquare$

The idea is to push forward, making the rooms that satisfy the condition more and more. It is made via a dumb greedy actions. We take a room which is not ok, flip a lamp, then another room could be spoiled, we again try to recover that room, the other one gets damaged, and so on till, we hope, there is no room spoiled. What follows is just a routine argument. Consider a configuration that maximizes the number of rooms satisfying the condition. We claim all the rooms are ok, that's, they have two lamps of different states. Assume, on the contrary, $ R_0$ is a room with all the lamps having the same state. Take a lamp $ \ell_0$ in $ R_0$ and change its state. It's matched with another lamp $ \ell_1$. If $ \ell_1$ is also in $ R_0$ we are done since $ R_0$ is already ok, because there is another lamp in it with different state. Suppose $ \ell_1$ is in some other room $ R_1\neq R_0$. If changing the state of $ \ell_1$ doesn't spoil the things in $ R_1$ we are done, otherwise we take a lamp $ \ell'_1\neq \ell_1$ in $ R_1$ and flip its state, thus $ R_1$ is still ok. It also affects the state of the lamp $ \ell_2$ that is matched with $ \ell'_1$ mounted in a room $ R_2$. Proceeding with this process leads to two possible outcomes. Either we reach a room $ R_n$ which is not spoiled after the lamp $ \ell_n$ in it is flipped, or we reach a room $ R_n$ which coincides with some previous room $ R_m, m<n$. In the latter case, the room $ R_n$ is already ok since $ \ell_m,\ell_m'$ in $ R_m$ are in different states and we enter again $ R_m$ in another lamp different from $ \ell_m, \ell'_m$. Thus, in all cases, we increase the number of rooms that are ok, contradiction. Comment. I think, the graph theory approach makes things worse, instead of helping, see also my remarks here. The right approach, in my humble opinion, is to imagine the picture as disjoint subsets of points (each subset being a room, each point - a lamp) and some full matching between the points. The problem is easier than it appears in the first glance.

Solved with Th3Numb3rThr33. Interpret the problem as follows: each room is a vertex of degree at least three in a (not necessarily simple) graph, and each pair of lamps represents an edge between two (not necessarily distinct rooms.) The goal is to color the edges with two colors such that each vertex has edges of both colors. Call a vertex monochromatic if all its edges are the same color. Assume for contradiction the goal is not possible, and take a configuration with the smallest number of monochromatic vertices. Let \(v_1\) be one such monochromatic vertex, and select an edge \(v_1\sim v_2\). If we flip the color of this edge, then \(v_2\) must become monochromatic by minimality. From here, select an edge \(v_2\sim v_3\) in the same way, and construct such a sequence \(v_1\to v_2\to\cdots\). But this sequence can not have any cycles: if for example, \(v_k\to v_1\) appears in the sequence, then toggling the color of \(v_k\sim v_1\) makes \(v_1\) monochromatic again, which is absurd since \(\deg v_1\ge3\) and all edges incident to \(v_1\) besides \(v_1\sim v_2\) are the same color. Thus the sequence continues forever, contradiction.

We call a room bad if all the lights in the room are the same state and good otherwise. Let $s(L)$ denote the state of lamp $L$ (on or off). Suppose that some room is bad, and let the lamps in the bad room be $L_1, L_2, L_3$. WLOG let all of them be on. If 2 lamps in the room are connected, we can just switch them and make them good. So assume no 2 are connected in the same room. Let $L_1$ be connected to $L_4$ and let $L_5,L_6$ be the other lamps in the same room as $L_4$. If $s(L_4)=s(L_5)$ or $s(L_4)=s(L_6)$, then switching $L_1$ would make both rooms good. So assume that $s(L_4) \neq s(L_{5,6})$. If $L_2$ shares a switch with either $L_5$ or $L_6$, switching $L_2$ would make both rooms good. So assume $L_1,L_2,L_3$ all share switches with lamps from different rooms. Let $L_2$ share a switch with $L_7$ (same room as $L_8, L_9$) and $L_3$ share a switch with $L_{10}$ (same room as $L_{11}, L_{12}$). Now switch any one of $L_1, L_2, L_3$ WLOG $L_2$. Now the first room has become good whereas the room containing $L_7, L_8, L_9$ is bad. Suppose $L_8$ is connected to any of $L_5, L_6, L_{11}, L_{12}$. Then turning $L_8$ would make all rooms good. Hence we need to introduce a new room which becomes bad upon switching $L_8$. Say, $L_8$ is connected to $L_{13}$ in room $L_{13}, L_{14}, L_{15}$. By the same logic, $L_{14}, L_{15}$ cannot be connected to any of the previous rooms, and this process can only continue finitely since there are a finite number of rooms. Hence at some point we must reach a bad room where one of the lamps is connected to one of the equal lamps in a good room. So we can always reduce the number of bad rooms by $1$.

Basically the same argument as 123, but I think its a bit easier to understand. FTSOC suppose that there exists some configuration for which it is impossible to get each room to have at least one off and one on lamp. Suppose that there are $n$ such rooms, which we will denote as good rooms(and the other type as bad rooms). We show that we can get this number of bad rooms down from $n$ to $n-1$ rooms, and thus, down to $0$ rooms at the end. Suppose there is a bad room $v_1$. Notice that because this room has at least $3$ lamps within it, for $v_1$ to be bad, it must have no pair of lamps within it which are linked by a switch and all of the corresponding lamps which are linked by a switch to each of the lamps within $v_1$ must be in rooms which are one step away from becoming bad by that lamp. In other words, the lamp which each of the lamps in $v_1$ is linked to by a switch must be a switch in its room which, if it changes its state, that room would become bad. Pick an arbitrary lamp in $v_1$ and change its state along with the corresponding lamp (which is in another room). Then we have to repeat the same process on the room in which the corresponding lamp is in. Notice that we can never go back to previous lamps, because if we did, then it would not be to a lamp which "saves" the lamp from being bad by one step, so it would result in all lamps being good. Therefore, we must have an infinite number of lamps, a contradiction. Oops, it seem like the graph representation was a lot clearer than this one.

suppose we can not do that . Suppose we have k rooms each has at least 3 lamps and number of lamps is 2n than number of switchs is n . And we interpret problem to graph theoritic language. we have bipartite graph one component is lamps in the houses and other component is switchs , consider lamps and switches as vertices.it is clear that degree of each lamp is 1 and deg of each switch is 2.let if switch is on we color it`s edges to blue otherwise to red.suppose we can do that condition for $k_{1}$ rooms ( $k_{1}$ less than k )

who wrote: A house has an even number of lamps distributed among its rooms in such a way that there are at least three lamps in every room. Each lamp shares a switch with exactly one other lamp, not necessarily from the same room. Each change in the switch shared by two lamps changes their states simultaneously. Prove that for every initial state of the lamps there exists a sequence of changes in some of the switches at the end of which each room contains lamps which are on as well as lamps which are off. Proposed by Australia

ISL marabot solve Define connected as shares a switch with. Suppose there are some number of rooms where each of its lamps are of the same state. We will show that if this number is greater than $0$, we can always decrease it. This solves the problem. Let $r_1$ be one of these rooms. Switch a lamp in $r_1$. If this lamp is connected with another lamp in $r_1$, then we are done. If this lamp is connected with a lamp in $r_2$, then if $r_2$ has lamps with all the same state prior to the switch, then we are also done. For this to not be possible, we need $r_2$ to have all lamps with the same state after the switch. Now we are at the same position as the beginning with $r_2$ swapped with $r_1$. Now we switch a lamp in $r_2$, which is connected to another lamp in $r_3$. Repeat this process until we reach a room we've been in before. Call that room $r_n$ can call the room we reach before it $r_m$. Prior to the last switch, $r_n$ had two lights on and the other off, or vice versa. WLOG it's two lights on and the other off. Note that the off light is already connected to some room not equal to $r_m$, so one of the on lights is switched. So $r_n$ won't have all it's lamps with the same state. Thus, we have decreased that number.

Let a room be boring if it only contains lights of the same state. Suppose our initial configuration has at least one boring room. We claim that we can reduce the number of boring rooms by one, which through repeated application will prove the problem. Notice that if we change a lamp in a boring room, the number of boring rooms cannot increase, and must decrease unless the room with the other changed lamp becomes boring. Start with a boring room, then do the following procedure repeatedly: change a light from the last created boring room (the initial boring room if this is first change). This procedure ends when a change doesn't create a boring room, which decreases the number of boring rooms by one, so it suffices to prove this procedure always ends. Suppose that a room went boring two times in this procedure. Consider the first time this happens. Notice that after the first time the room went boring, two changes were made to the light, and it is boring again. This means that the two changes were done to the same light. However, this also means two changes were done to the light it's linked to, so the corresponding room has been boring twice, contradiction. Therefore, we will eventually run out of rooms, forcing the procedure to stop and finishing the problem.

Claim: If there are any number of rooms, each with at least $3$ lamps, and some pairs of lamps are connected but no lamp is connected to two other lamps, then it is possible to switch the lamps such that each room has at two lamps in different states. Proof: Note that this problem is equivalent to each pair of connected lamps being always the same or always opposite of each other. Say that two lamps are "directly connected" if they are always the same and "oppositely connected" if they are always opposite of each other. We will use induction on the number of rooms. In the base case, there is 1 room. This is clearly possible since there are at least 3 lamps, so one can simply find two lamps not connected to each other and switch them so one is on and the other is off. Assume there are multiple rooms. Let $A$ be a room. Case 1: $A$ has two lamps connected to each other or a lamp not connected to anything Proof for this case: Let $a$ be a lamp not connected to any lamp outside of $A$. Let $b$ be a lamp in $A$ that isn't connected to $a$. By the inductive hypothesis, it is possible to switch all the lamps not in $A$ such that each room has a lamp that is on and a lamp that is off. Note that $a$ can't be affected by this. If $b$ is affected by this, switch $a$ such that it is the opposite of $b$. If $b$ is not affected by this, then switch both $a$ and $b$ such that they are the opposite of each other. So, $A$ will have two opposite lamps. Case 2: Every lamp in $A$ is connected to a lamp in another room Proof for this case: Let $a$ and $b$ be two lamps in $A$. Let them be connected to $a'$ and $b'$, respectively, which are in other rooms. Case 2a: When $a$ and $b$ are opposite, $a'$ and $b'$ are the same: By the inductive hypothesis, in the case with all the rooms except for $A$ where $a'$ and $b'$ are directly connected, it is possible to switch the lights such that each room has a light on and a light off. So, it is possible to switch all the lamps not in $A$ so that each room has a lamp on and a lamp off and $a'$ and $b'$ are the same as each other. Then, $a$ and $b$ will be different from each other, so $A$ will have two opposite lamps. Case 2b: When $a$ and $b$ are opposite, $a'$ and $b'$ are opposite: Using similar logic to case 2a, but making $a'$ and $b'$ oppositely connected instead, this case works. Thus, the claim is true, which is enough to prove the problem statement.

Really chunky solution, but whatever. We will first define a term. Let a free lamp be a lamp that can be whatever we want it to be, without breaking the other lamp with the same switch. A room with a free lamp always satisfies the required condition. Note that if a room contains two lamps connected by the same switch, the two lamps are essentially one free lamp, which clearly makes the problem easier. Therefore, in the below proof, we will assume that there is no room with two lamps controlled by one switch. We now use strong induction on the number of rooms. The case with one room is trivial. Let the number of rooms be $n$. First, we create a graph, where each node is a room and two nodes are connected if and only if there is a switch that controls a lamp in each room. We see that each node must be connected to at least two other nodes, as if that is not the case, the room has to be completely connected to another room. If that other room has more lamps, it provides more free lamps, then clearly works by strong induction with $2$ rooms and $n-2$ rooms. If the other room has the same number of lamps, this still clearly woks by strong induction with $2$ rooms and $n-2$ rooms. Now, this means that the number of connections in the graph must be at least $\frac{2n}{2}=n$, which means that there must exist a loop of nodes. Let the nodes in this loop in order be $a_1,a_2,\dots,a_k$, where $k\le n$. We can let $a_1$ provide a free lamp to $a_2$, $a_2$ provide a free lamp to $a_3$, etc, until $a_k$ provides a free lamp to $a_1$. Then, each of these rooms still has at least one lamp left, so it can provide free lamps to everything connected to the loop(or not if $k=n$, in that case we're just done). QED. Edit2: I just realized that I didn't explain the last sentence clearly enough/correctly enough. The loop nodes give free lamps to anything connected to it besides the loop itself, and a room with a free lamp can reach another room with a free lamp, etc. This clearly continues to the entire connected region because of the argument we used with the leading out of the loop. Remember that if the graph is disconnected, it is taken care of by strong induction.

Is this right? I bolded the parts which are most likely to have errors. Suppose that we have a graph where each room represents a node, and two nodes are connected if there exist two lamps from those rooms which share a switch. Then, call a pair of rooms good if they are in the same component. Assume that in every room there exists a lamp which shares a switch with a lamp not in that room (we can do this because we could just delete the room otherwise). Now, suppose that we have a room which contains two lamps which share a switch. Then, regardless of the states of the other lamps in that room, we will always be able to have this room contain lamps which are on, as well as lamps which are off. This means that the states of the other lamps are "free", which means that the lamps they are connected to are also "free". Inductively, it follows that the whole component will be able to satisfy the condition in the problem. Then, we can simply delete the whole component. This allows us to assume that every switch connects two lamps from different rooms. Next, suppose there exists two rooms such that there are two switches which connect four different lamps, two from each room. It's easy to show (by simply taking cases) that the rest of the lamps in these rooms are "free". Similar to the first process, we can apply this logic inductively and so we may assume that there do not exist two rooms such that there are two switches which connect four different lamps (i.e. for any two lamps in a room, each one shares a switch with lamps from different rooms). Finally, assume there are at least three rooms in the house (the other cases being trivial). Then let three of them be rooms $1$, $2$, and $3$. Then there must exist two lamps from room $1$ such that one connects to room $2$ and the other connects to room $3$. Again, notice that all of the other lamps in these three rooms are "free". Thus we may assume that no three rooms satisfying the condition stated exist, by induction. Now we have exhausted all cases, so we are done. $\blacksquare$

Call a room boring if all the lamp states are the same. Call it interesting if there is exactly one lamp that is different from all the rest. We prove that if there is a positive number of boring rooms there is a way to decrease this number by one. Pick any room that is boring then switch the state of one of them to make it interesting. If we're not done, some other room was just made boring. Then in that boring room, we switch the state of some lamp to make it interesting. Eventually following this algorithm, we're either done, or we have to go back to a room we have already entered. In this case, consider the first time we revisit a room, $r$. Every room that was operated on is now interesting, except for the one we just entered. Before entering, the room was interesting so there is exactly one lamp to make it boring. When we first entered this room we operated on the very same lamp, so that means we have visited the room before $r$, call it $s$ previously, unless the room entering sequence goes $r\to s\to r.$ This is a contradiction with the fact that we operate on a different lamp than one that was just changed, so we're done.

Call a room bad if all of its lamps are in the same state, and good otherwise. We will find an algorithm that always decreases the number of bad rooms, as long as there is at least 1 bad room. Take a bad room, and call it room 1. Change one of its lamps. If this change did not make a previously good room bad, then we have already succeded in reducing the number of bad rooms. If this does make another room, say room 2, bad, we then flip a lamp in room 2 that wasn't connected to the one we just flipped. If this lamp is connected to a lamp in room 1, then this will make room 2 good while not making room 1 bad, so we are done in this case. Otherwise, this lamp is linked to another room, which we call room 3. If we keep doing this, eventually we will return to an already visited room, and have successfully decreased the number of bad rooms, so we are done.

i think i may have misunderstood the problem There are $2n$ vertices. Call a bad room a room in which the lamps are either all on or all off. We proceed by induction on $n$ with the base case trivial. Assume the statement for $n=k$. Let graph $G$ have $2k+2$ vertices and let the rooms be $A_1,\ldots,A_r$. Assume there exists $1\leq i<j\leq r$ such that there exists an edge $vu$ between $A_i$ and $A_j$ (otherwise it is trivial). Now apply the induction hypothesis on all the vertices except $v$ and $u$ with rooms being $A_1,\ldots,A_{i-1},A_{i+1},\ldots,A_{j-1},A_{j+1},\ldots,A_r,A_i\cup A_j\setminus\{v,u\}$. At most one room is bad, and it is among $A_i$ and $A_j$. Then just change the state of $v$ and $u$ so that we remove the bad room, completing the induction step. $\square$ EDIT: fakesolve the assumption that at most one of $A_i$ and $A_j$ is bad is incorrect

Hopefully this works? Let edges be lamps (on or off), and let nodes be rooms. We wish for all of the nodes to have at least one of each colored edge attached to it. For each connected component of the graph: Pick some edge and remove it, leaving the graph still connected (since the degree of each node is greater than or equal to 3, such edge must exist; otherwise the graph is a bamboo). From one of the endpoints of that edge as the root, construct the DFS tree, with its edges alternating on/off based on distance from the root. Place back the removed edge in off. Now, the root node has both on/off edges and is good. Also, all non-leaf nodes are good since they have edges going in them and out of them in the DFS tree, so they must be of opposite color. Now, all leaf nodes either have 1 or 2 free edges left (1 if and only if they are matched with the removed edge at the start). Pick either that node with free degree 1, or any random node. Color any of its edges its missing color if it exists, or any random color if not. Go to the other end of the edge just colored, and repeat. If at any point we return to a leaf node we already fixed, go to another unfixed leaf node. Thus, we can fix any leaf node we consider; we thus can fix all nodes.

Quote: Each lamp shares a switch with exactly one other lamp When translating the problem into graph theory, vertices are lamps. An edge is a switch incident to the two vertices the switch controls. Is the graph described in the problem any graph or is it the graph with $|E|=\frac{1}{2}|V|$ and $\frac{1}{2}|V|$ connected components? I read a few monovariant sols from above and it seems like the graph is the latter.

Call a room bad if it does not satisfy the condition. We describe an algorithm that reduces the number of bad rooms by 1. Start at a bad room. If two lamps in that room share a switch, we are done. Otherwise, flip a switch and go the room that is connected to the switch. If this room went from good to bad, then repeat. Eventually, we must reach a room we have visited before. Consider the first repeated room. But the only switch that could be changed to make that room bad again is the switch that was changed originally, and this is only possible if the room that was visited immediately before was the same both times. This is impossible, as we assumed this was the first repeated room, and we are done.

Call the process of fixing a room the process of making it not monochromatic. Suppose for the sake of contradiction that every room has at least one unfixed room. Take the first unfixed room, and flick on an arbitrary light in there. If It turns on a light in the same room, done. Otherwise, a light elsewhere turns on. If that light keeps the room fixed, then also done. Otherwise, the process of turning on this light will make another unfixed room. Now fix this room. Repeat until we visit a room we have visited before. The only way to unfix this room again is to turn off/on the light that fixed it in the first place. But this was already on our switch list that we made while fixing rooms, contradiction. Hence we have achieved a contradiction, and we are done.

I think this one is more accessible, probably even to a student who just needs to reinterpret the problem and after that it's just logic. Let the rooms be vertices, each with degree at least 3 where each edge represents a lamp sharing a connection with some lamp in another room (vertex). The problem is reduced to saying that we need a configuration such that each of the edges incident to any vertex are not all the same color. Indeed, if we switch some v_1<->v_2 it must still not work, so v_2 must become monochromatic. Then the sequence v_1-v_2-...v_k must never be a loop, otherwise after v_k becomes monochromatic switch v_k with v_1, since v_1 has 2 of the first color and 1 of the second color but switching that edge's color changes it from first to second color, v_1 is now not monochromatic, so we're done! And finally, note that this sequence cannot be infinite since it must EVENTUALLY cycle. $\blacksquare$

Fairly boring problem. Suppose that there exists some set of rooms $S$ that don't satisfy the condition. We will prescribe an operation that strictly decreases $|S|$, more or less in the most obvious way possible. Say some room $R \in S$. If there exists two lamps in $R$ connected to each other, we are done immediately. Else, this means that flipping a lamp in $R$ causes some other room $R_1$ to not work; now, perform the same operation on $R_1$, and so on. This gives us a path $R, R_1, R_2, \dots, R_n$. If $R_n$ does not connect to any more rooms, then it must have a self-loop, thus we can finish. Else, $R_n = R_i$ must cycle eventually, but then $R_i$ necessarily also has to work (because the originally toggled lamp was still toggled.) Thus done.

Take simple graph $G(V,E)$ where two rooms are connected iff they share a connected bulb Use induction on $n$. If there is a room with degree $4+$ or a loop we are done. Assume the graph is $3$-regular Now select the edges of a spanning tree and select any non-selected edge. This creates a single cycle with branch-like extensions that connect all of the points of the graph. Selecting bulbs along selected edges provides a solution.

Rewrite We show that if there are a nonzero amount of rooms with all lamps of the same state, we can decrease the amount of such rooms. Call such rooms dull and lamps that share a switch connected. Suppose we couldn't decrease the number of dull rooms. Suppose $r_1$ is a dull room. If two connected lamps were both in $r_1$ then we can just switch both those lamps and thus decrease the amount of dull rooms. Therefore, no two connected lamps can be both in $r_1$. Now, there must exist a room that has a lamp connected to one in $r_1$. Randomly choose such a room and call it $r_2$. If we switch a lamp connecting $r_1$ and $r_2$, we see that $r_1$ isn't dull anymore, and thus $r_2$ must become dull so that the number of dull rooms is preserved. In particular, $r_2$ cannot be dull before the switch. Now, we can choose another room $r_3$ sharing a switch with $r_2$, and get that it must be dull after the switch, and similarly we choose rooms $r_4, r_5, \ldots, $ in the same manner. Each room $r_i$ cannot dull prior to the switch of the lamp shared with $r_{i - 1}$. However, at some point some $r_n$ repeats (since there are a finite number of rooms), but $r_n$ is dull due to having been switched earlier, which is a contradiction because it can't be dull after the switch.

We say that a room is good if there exist both lamps that are on as well as lamps that are off; conversely, say that a room is bad if all lamps are either on or off. Note that it suffices to devise an algorithm that will strictly decrease the number of bad rooms upon running it, as applying our algorithm sufficiently many times would then result in a configuration with no bad rooms at all. Our algorithm is as follows. Suppose that there exists some bad room $R_1$. If there exists a pair of lamps in $R_1$ that share a switch, then we can simply toggle the states of those two lamps; since $R_1$ has at least three lamps as given, it would then become a good room, so we are finished in this case. Otherwise, consider some lamp in $R_1$ that shares a switch $s_1$ with a lamp in another room, which we call $R_2$. Toggle this switch; clearly, $R_1$ becomes a good room. If $R_2$ remains good or becomes good, then we are again finished. Otherwise, $R_2$ has been made into a bad room. We then repeat the same considerations above on $R_2$, considering whether there exists a pair of lamps in $R_2$ sharing a switch; if so, we are done and terminate. If not, we flip the switch $s_2$ of some lamp in $R_2$ that is shared with a lamp in another room, say $R_3$ while guaranteeing that $s_1\neq s_2$, as each room has at least three lamps. If $R_3$ is good, we are again finished and terminate; otherwise, we repeat the same process on $R_3$. We then repeat this process indefinitely many times until termination; it then suffices to prove that such a termination must happen. Indeed, if there exists some room $R_n$ containing a pair of lamps sharing a switch, then we terminate. Otherwise, by finiteness, we must come across some room $R_n$ that we have processed previously, so that there exists some $k<n-1$ satisfying $R_k=R_n$. Before flipping the common switch $s_{n-1}$ connecting rooms $R_{n-1}$ and $R_n$, we note that flipping the switch $s_k$ between $R_k$ and $R_{k+1}$ has made $R_k=R_n$ to be already good. Since each lamp shares a switch with exactly one other lamp and $k<n$, we must have $s_k\neq s_{n-1}$, implying that flipping switch $s_{n-1}$ does not undo $s_k$. Since room $R_n$ has at least two lamps, it will remain good, thus terminating our algorithm. One can check that running our algorithm will make each $R_i$ good, for all $i\in\{1,2,\cdots,n\}$. Since $R_1$ was originally bad, this algorithm must then decrease the number of bad rooms. $\blacksquare$ - Jörg

Since the induction I made through the rooms is the same as the other solutions, I tried and proved the induction through the lamps. However, it is much longer than the induction through the rooms, I will share it if I am not lazy.(Includes several case analysis )

Let a room be good if it does not have all lamps in the same state, we claim we can monotonically increase the number of good rooms. Take any bad room, then flip some arbitrary lamp in that room, and "mark" the room. If the other lamp flipped is in the same room, we are done. Otherwise, we flip a lamp in some other room. If the room is not bad after flipping, we are done. If the room turns bad, "mark" it and note we have not changed the number of good rooms. Repeat this until we operate on a marked room, which turns it good, so observe that we only operated on marked rooms, all of which were good before except $1$, but now all of them are good, so we increased the number of good rooms by $1$.

We proceed with induction on $n,$ the number of rooms. The base case, $n=1,$ is trivial. Now assume that our proposition holds for some positive integer $n = k.$ Then suppose that we have $n+1$ rooms, and view these rooms as vertices in a graph. For each switch that alters the state of two lights, draw an edge between the room(s) they are in. In addition, denote the rooms as $R_1, R_2, \dots, R_{n+1}.$ Clearly, the graph cannot be a forest/tree as each vertice has a degree greater or equal to $3.$ Hence a cycle connecting the vertices $$R_1 \rightarrow R_2 \rightarrow R_3 \rightarrow \cdots \rightarrow R_k \rightarrow R_1$$exists. Now, say that a room is $\textit{good}$ if it satisfies the desired condition and $\textit{bad}$ if it does not. By the inductive hypothesis we can make all the rooms $R_2, R_3, \dots R_{n+1}$ good. If $R_1$ is good, we are done, so assume otherwise. Then we can use a switch to make $R_1$ good, if $R_2$ is good too we are done, so assume $R_2$ is bad. Then we can continue this process until we reach $R_k.$ At this point, if $R_k$ is bad we can alter the switch between $R_k$ and $R_1.$ This will make $R_k$ good again, and clearly will keep $R_1$ as good because it has exactly one lamp $d$ that is different from all its other lamps, but this lamp corresponds to a lamp in $R_2,$ and thus not a lamp in $R_k.$ Therefore all lamps will become good, so our induction is complete. QED

Did I misunderstand something? Suppose there are $2m$ lamps with $n$ rooms, theb naturally $2m \geq 3n \implies m > n.$ Now $2^m > 2^n$ which is greater than the number of all attainable lamp states where for each room, lamps in it are either all on or all off; thus there exists a state where the statement in the problem holds.

Acclab wrote: Did I misunderstand something? Suppose there are $2m$ lamps with $n$ rooms, theb naturally $2m \geq 3n \implies m > n.$ Now $2^m > 2^n$ which is greater than the number of all attainable lamp states where for each room, lamps in it are either all on or all off; thus there exists a state where the statement in the problem holds. aren't there $2^{2m}$ attainable lamp states in total rather than $2^n$??? Also, it doesnt make sense that the total number of ways to alter the switches is greater than the total number of attainable lamp states, as that means that two configurations of changing light switches yields the same lamp configuration, but this is clearly impossible