Lamps of the hall switch by only five keys. Every key is connected to one or more lamp(s). By switching every key, all connected lamps will be switched too. We know that no two keys have same set of connected lamps with each other. At first all of the lamps are off. Prove that someone can switch just three keys to turn at least two lamps on.
Problem
Source: Iran Second Round MO 2018 - P5
Tags: combinatorics, Iran
27.04.2018 12:37
I have a long solution by induction that the base form for $n=3$ has a bit case-work. I'll post it as soon as possible.
27.04.2018 16:33
my solution was like 4 pages considering it as a graph and considering cases for the edge of vertices (the number of keys connected to the light)
27.04.2018 19:25
Let us consider a graph with two parts first parts triples of keys and second part lights connect a light to a triple of keys if by pushing them the light becomes on.Let the keys be $K_1,K_2,K_3,K_4,K_5$ and the lights be $L_1,L_2,\dots ,L_n$.First of all if a lamp isn't connected to any key ignore it.By case chase by the number of keys every lamp is connected one can see $deg(L_i) \ge 4 \forall i \in \{1,2,\dots ,n \}$ also because the set of lamps every key is connected is distinct one can see $n \ge 3$ so the number of edges of graph is at least $3*4=12$ by averaging there is a triple which is connected to at least two lamps so we are done.
27.04.2018 21:59
I think it was hard for a problem 5 but the result is weak.With my solution one can prove that there exist two triples with that property or there exists a triple that turns on at least three lamps.So I have a little doubt about my solution.Can anyone check that for me please?
27.04.2018 22:15
Here's my solution: I induct on $n$ the number of lamps. First of all note that $n\ge 3$. Assume we can switch three keys to turn at least two lamps for $n$ lamps. Now imagine $n+1$ lamps! Call lamps $L_1,L_2,...,L_n,L_{n+1}$ and don't consider $L_{n+1}$. Now if between $n$ remained lamps every two keys has different set of connected lamps we are done. So assume the counter, there is at least two keys call them $A$ and $B$ such that they are connected to same lamps between $n$ lamps and $B$ is connected to $L_{n+1}$. Here consider three left keys. Degree: The number of connected lamps to a key is called degree of that key. Call three left keys $X,Y,Z$. Note that by switching $A$ and $B$ we have 1 light lamp so if we assume the counter $X,Y,Z$ must have degree two or degree one. Now easy to see with a bit case-work if we switch $X,Y,Z$ we have at least two lighten lamps. Q.E.D. But we need to prove the base form $n=3$ that it's a bit longer: Consider five keys $A,B,X,Y,Z$ and three lamps $L_1, L_2, L_3$. We have at most: [*] three degree-2 keys [*] three degree-1 keys [*] one degree 3 keys Easy to check that we have at least one degree-1 and one degree-2 key. Now note that if we have three degree-1 one key we can switch these three keys to turn at least 2 lamps. So assume the counter and we have at most two degree-1 keys. So casework on the number of degree-1 keys: a) Exactly one degree-1 So we have three degree-2 keys now easy to see there is two degree-2 such that if we switch them with the degree-1 key we can reach 2 lighten lamps. b) Exactly two degree-1 So we have at least two degree-2 keys such that they have 1 common lamp. Because of we have two degree-1 so there is one degree-1 key not connected to the degree-2 keys' command lamp and if we switch it with the degree-1 keys we are done. Q.E.D.
27.04.2018 22:23
Taha1381 wrote: I think it was hard for a problem 5 but the result is weak.With my solution one can prove that there exist two triples with that property or there exists a triple that turns on at least three lamps.So I have a little doubt about my solution.Can anyone check that for me please? I think your solution is right. Check Farzanegan-1 Channel on telegram.
28.04.2018 18:57
Taha1381 wrote: I think it was hard for a problem 5 but the result is weak.With my solution one can prove that there exist two triples with that property or there exists a triple that turns on at least three lamps.So I have a little doubt about my solution.Can anyone check that for me please? I worked on you idea! And I got that you are wrong, check my example out: Consider all possible actions! Probabilty of a lamp to be switched odd times is $\frac{1}{2}$. On the other hand we have $5$ lamps so averenge of them is $5\times \frac{1}{2}=\frac{5}{2}$ that is says that some cases contain three keys. This solution is compelety wrong because of few reasons. The most important an trivial one is that it's possible to the averenege do not contain any three-key action. I'm completey sure that this is wrong. So if you meant this you should think more.
28.04.2018 21:58
AlirezaOpmc wrote: Taha1381 wrote: I think it was hard for a problem 5 but the result is weak.With my solution one can prove that there exist two triples with that property or there exists a triple that turns on at least three lamps.So I have a little doubt about my solution.Can anyone check that for me please? I worked on you idea! And I got that you are wrong, check my example out: Consider all possible actions! Probabilty of a lamp to be switched odd times is $\frac{1}{2}$. On the other hand we have $5$ lamps so averenge of them is $5\times \frac{1}{2}=\frac{5}{2}$ that is says that some cases contain three keys. This solution is compelety wrong because of few reasons. The most important an trivial one is that it's possible to the averenege do not contain any three-key action. I'm completey sure that this is wrong. So if you meant this you should think more. I disscused about triples of keys not keys themselves I proved no matter how the lamps are connected to keys but there is at least 4 triples so that every triple can turn on a light if we push all three lamps in the triple.And then by averaging I proved one of the triples do this for two lamps.
09.07.2018 09:53
Very short solution: Let $x_1,x_2,x_3,x_4,x_5$ be binary strings where $i$th digit of any $x_n$ is $1$ if $n$th key turns $i$th lamp and $0$ otherwise. We must show existence of $x_i,x_j,x_k$ such that $x_i\oplus x_j \oplus x_k$ has at least 2 ones.($\oplus $ is bitwise XOR) Suppose it is false. Then all among $x_1 \oplus x_3\oplus x_4,x_1 \oplus x_3\oplus x_5,x_1 \oplus x_4\oplus x_5$ have at most $1$ ones. Also note that all are distinct(XOR of any two is XOR of some 2 distinct $x_i$, hence cannot be 0) Consider $x=x_1\oplus x_2$. We show that XOR of $x$ and some string from above has at least $2$ ones. If $x$ has at least 3 ones then it is obviously true (all strings above have at most 1 ones). Also it can be seen that if $x$ has at most 2 ones then there can be only two distinct $y$ having at most 1 ones such that $x\oplus y$ has at most $1$ ones. Since we have three strings above, XOR of some string with $x$ has atleast 2ones. WLOG let it be $y=x_1\oplus x_3 \oplus x_4$ then $x \oplus y=x_2\oplus x_3 \oplus x_4$ and it has at least 2 ones, a contradiction.
04.10.2018 10:14
My Solution : There are $n$ lamps $L_{1},L_{2},\cdots,L_{n}$ and 5 switches $S_{1},\cdots,S_{5}$. If $L_{i}$ is connected to an odd number of switches in any subset of $\{S_{i},S_{j},S_{k}\}$, It will turn on. Let $(L_{m},(S_{i},S_{j},S_{k}))$ be the "Good Pair" if $L_{i}$ turns on by these switches.$( 1\le i\le j\le k \le 5)$ By reductio ad absurdum, Any set $\{S_{i},S_{j},S_{k}\}$ has 1 or less Good Pair. So the number of Good Pairs are at most 10. By the way, If $L_{i}$ is connected $l_{i}$ switches, it belongs to $X_{i}=\binom{l_{i}}{1}\cdot\binom{5-l_{i}}{2}+\binom{l_{i}}{3}$ Good Pairs. So we can get the conclusion that $X_{i}\ge 4$(equality holds when $l_{i}=3$), there are at least $4n$ Good Pairs. So $n\le 2$. However, there are at most $2^2=4$ distinct switches in this case. Contradiction.
07.03.2024 12:59
Construct a table where the rows are the keys $K_1,K_2,K_3,K_4,K_5$ and the column are the lamps $L_1,L_2,...,L_n$. Colour the intersection of $i.$ row and $j.$ column if $K_i$ and $L_j$ are connected. Assume contrary. We have $i)$ There are odd number of coloured squares in every column. $ii)$ There doesn't exist same coloured columns. $iii)$ There doesn't exist $3$ rows where at least $2$ columns have an odd number of coloured squares in those $3$ rows. We will get contradiction with these conditions. Claim $1$: There cannot be $2$ rows and $2$ columns such that their intersections are white. Proof: Assume that there exists. WLOG let these columns be $L_1,L_2$ and these rows be $K_1,K_2$. If there is a row whose intersections with $L_1,L_2$ are black, then we can choose that row and $K_1,K_2$ but this contradicts with $(iii)$. There are odd number of black squares in each $L_i$ so there must be $1$ black square in each $L_1,L_2$ columns. But in this case we can choose the two rows which $L_1$ and $L_2$ has their black squares in and $K_1$ which contradicts with $(iii)$ again. Claim $2$:: There doesn't exist a column whose all squares are black. Proof: Assume that there exists. Let that column be $L_1$. The other columns can have at most $3$ black squares because of $(ii)$. WLOG $L_2\cap K_1$ is black and $L_2\cap K_4$ and $L_2\cap K_5$ are white. So we can choose $K_1,K_4,K_5$ which contradicts with $(iii)$. Claim $3$: There doesn't exist a column which contains exactly $1$ black square. Proof: Assume that there exists. WLOG let it be $L_1$. But because of Claim $1$, there must be at least $3$ black squares in $K_2,K_3,K_4,K_5$ for each column. If there is a column (WLOG $L_2$) whose $3$ squares are black in $K_2,K_3,K_4,K_5$, then we can take $K_1$ and the row whose intersection with both $L_1,L_2$ are white and a row whose intersection with $L_2$ is black which contradicts with $(iii)$. By $(i)$, there must be a column whose all squares are black but this contradicts with Claim $2$. By these claims, we get that each column must contain exactly $3$ black squares. WLOG $L_1$ is black in $K_1,K_2,K_3$ and white in $K_4,K_5$. If $L_2$ and $L_1$ have two common rows, WLOG $L_2$ is black in $K_1,K_2,K_4$ and white in $K_3,K_5$. In this case we can choose $K_3,K_4,K_5$ which contradicts with $(iii)$. If $L_2$ and $L_1$ have one common row, WLOG $L_2$ is black in $K_1,K_4,K_5$ and white in $K_2,K_3$. But in this case we can choose $K_1,K_2,K_3$ which contradicts with $(iii)$ again as desired.$\blacksquare$
25.03.2024 22:29
Taha1381 wrote: Let us consider a graph with two parts first parts triples of keys and second part lights connect a light to a triple of keys if by pushing them the light becomes on.. Hello, we can use pigeonhole principle in last part, as "number of triples of keys"=10 < 12 $\leq$ "number of edges"
25.03.2024 22:35
Taha1381 wrote: I think it was hard for a problem 5 but the result is weak.With my solution one can prove that there exist two triples with that property or there exists a triple that turns on at least three lamps.So I have a little doubt about my solution.Can anyone check that for me please? I think we cannot prove there exists a triple that turns on at least three lamps. Consider the following counterexample:
Attachments:
