1
$\begingroup$

Motivation. The following has a real-life (!) inspiration from a discussion about how to connect lamps and switches in an efficient way.

Question. Let $n\in\mathbb{N}$ be a positive integer and let $\{1,\ldots,n\}$ represent $n$ lamps, each of which is in exactly one of the states OFF or ON. Let $E\subseteq {\cal P}(\{1,\ldots,n\})$. For every $e\in E$ we have an "$e$-button", such that if that button is pressed, every element of $e$ switches its state (either from OFF to ON, or vice versa). We say that $E$ is state-complete if the following condition holds:

If all lamps are OFF and if $k\in \{1,\ldots, n\}$ is given, there is a finite button-sequence $e_1, \ldots, e_m \in E$ such that after all the buttons have been pressed, lamp $k$ is ON and all other lamps are OFF.

For instance, $\big\{\{k\}: k\in \{1,\ldots,n\}\big\}$ is state-complete, and $\big\{\{1,\ldots,n\}\big\}$ is not state-complete for $n\geq 2$.

Given $n\in \mathbb{N}$, what is the least cardinality that a state-complete set $E\subseteq {\cal P}(\{1,\ldots,n\})$ can have?

Improve this question
$\endgroup$
6
  • 7
    $\begingroup$ Think of $\mathcal P(\{1,\dots,n\}$ as an $n$-dimensional vector space over the $2$-element field. You're asking for the minimal size of a set $E$ whose linear combinations include all the standard basis vectors $\{k\}$. Such an $E$ spans the whole space, so the minimum size is $n$. $\endgroup$
    – Andreas Blass
    Commented May 14, 2022 at 17:15
  • 7
    $\begingroup$ Or, more elementary, if you have $k<n$ buttons, you get at most $2^k<2^n$ combinations of lamps, thus not all. This contradicts to the possibility to switch each separate lamp. $\endgroup$
    – Fedor Petrov
    Commented May 14, 2022 at 17:33
  • 2
    $\begingroup$ So, we have found a complicated description of the identity function. $\endgroup$
    – Gerry Myerson
    Commented May 15, 2022 at 1:40
  • 1
    $\begingroup$ hm, why do not they commute? $\endgroup$
    – Fedor Petrov
    Commented May 15, 2022 at 8:05
  • 1
    $\begingroup$ Right - I am wrong, sorry $\endgroup$
    – Dominic van der Zypen
    Commented May 15, 2022 at 9:46

1 Answer 1

Reset to default
1
$\begingroup$

This problem is a sort of generalization of the game 'Lights out'.

There are a few paper's e.g. by M. Zaidenberg (for example "Periodic harmonic functions on lattices and points count in positive characteristic.") on the underlying mathematics.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ This seems pretty unrelated. And the comments below the question seem sufficient, in fact. $\endgroup$
    – Alessandro Della Corte
    Commented May 15, 2022 at 12:44
  • $\begingroup$ No, it is related: it is the special case where the switches are associated to the set of all neighbours and it gives rise to fairly beautiful mathematics involving e.g. elliptic curves over finite fields. $\endgroup$
    – Roland Bacher
    Commented May 15, 2022 at 13:18

Not the answer you're looking for? Browse other questions tagged .