Problem A. 900. (February 2025)

A. 900. In a room, there are \(\displaystyle n\) lights numbered with positive integers \(\displaystyle 1\), \(\displaystyle 2\), \(\displaystyle \ldots\), \(\displaystyle n\). At the beginning of the game subsets \(\displaystyle S_1\), \(\displaystyle S_2\), \(\displaystyle \ldots\), \(\displaystyle S_k\) of \(\displaystyle \{1,2,\ldots,n\}\) can be chosen. For every integer \(\displaystyle 1\leq i\leq k\), there is a button that turns on the lights corresponding to the elements of \(\displaystyle S_i\) and also a button that turns off all the lights corresponding to the elements of \(\displaystyle S_i\). For any positive integer \(\displaystyle n\), determine the smallest \(\displaystyle k\) for which it is possible to choose the sets \(\displaystyle S_1\), \(\displaystyle S_2\), \(\displaystyle \ldots\), \(\displaystyle S_n\) in such a way that allows any combination of the \(\displaystyle n\) lights to be turned on, starting from the state where all the lights are off.

Proposed by: Kristóf Zólomy, Budapest

(7 pont)

Deadline expired on March 10, 2025.

\(\displaystyle k=n\) is clearly enough, if each switch acts on a different light.

Let's assume \(\displaystyle k<n\), and consider the following homogeneous system of linear equations: \(\displaystyle \sum_{a\in S_i}x_a=0\) for \(\displaystyle 1\leq i\leq k\). A well known fact of linear algebra is that there exists a non-trivial solution (i.e. where not all variables are equal to 0) on the set of real numbers: let such a solution be \(\displaystyle x_j=a_j\). Let \(\displaystyle P\) be the set of indeces where \(\displaystyle a_j>0\) and \(\displaystyle N\) be the set of indeces where \(\displaystyle a_j<0\) (both of these are non-empty according to our assumption). Now the key observation is this: every \(\displaystyle S_i\) must have a non-empty intersection both with \(\displaystyle P\) and \(\displaystyle N\) or must be disjoint from \(\displaystyle P\cup N\).

We will prove that it is not possible that exactly the lamps corresponding to the elements of \(\displaystyle P\) are switched on. Proving this is easy based on our observation: let's consider the last step when \(\displaystyle S_i\) has a non-empty intersection with \(\displaystyle P\cup N\): due to our observation, this will switch some lights in \(\displaystyle P\) and \(\displaystyle N\) to the same state, and no lamp in \(\displaystyle P\cup N\) will be changed in the subsequent steps, which clearly shows that it's not possible to switch on only the lights corresponding to \(\displaystyle P\).

Statistics:

12 students sent a solution.
7 points:	Czanik Pál, Keresztély Zsófia, Kocsis 827 Péter, Szakács Ábel, Varga Boldizsár.
6 points:	Morvai Várkony Albert, Virág Tóbiás.
3 points:	1 student.
2 points:	1 student.
0 point:	3 students.

Problems in Mathematics of KöMaL, February 2025