(Israël TST 2021 P2)

In Benoît's house, there are 2023 switches and $2023 \times 1011$ light bulbs. Each light bulb corresponds to a pair of switches and lights up precisely when both switches are on. However, Benoît has forgotten to label the light bulbs and does not remember which bulb corresponds to which pair of switches. Initially, all switches are off. Each minute, Benoît can change the state of one switch and then notes the state of the bulbs. What is the minimum time Benoît will need to determine all the correspondences between his bulbs and switches?
Let's show that the answer is $4044=2 \times 2023-2$. For this, we need to try to understand how to choose Benoît's strategy. A first remark is that necessarily, Benoît must turn on each switch at least once in his strategy. Indeed, if for example

Benoît did not turn on switch 1, he would have no way to distinguish between all the bulbs for which one of the switches is switch 1 (of which there are 2022, so more than one).

In order to be able to determine which bulb corresponds to a certain pair of switches $i, j$, it is necessary that for any other pair of switches $k, l$, one can distinguish the bulb corresponding to the first pair from the bulb corresponding to the second pair, or in other words, that there is a moment when one of the two bulbs is on and the other is off. In other words, for any pairs $i, j$ and $k, l$ of switches, there must be a moment when one of the pairs has both switches on, but not the other.

Suppose now that the switches $i, j, k, l$ are all four distinct. Necessarily, to distinguish the two pairs, at least one of the pairs must turn on at some point in Benoît's strategy, suppose the pair $i, j$ turns on first (potentially at the same time as the pair $k, l$). But at the moment Benoît turns on the pair $i, j$, he cannot turn on the pair $k, l$ since the two pairs are disjoint, and therefore there is a moment when the bulb corresponding to $i, j$ is on, and the one corresponding to $k, l$ is off. Benoît therefore does not need to worry about disjoint pairs.

Suppose now that the switches $i, j, k, l$ are not all four distinct, the two pairs are therefore of the form $i, j$ and $i, k$ with $i, j, k$ distinct. In this case, if Benoît does not adapt his strategy well, the two pairs of switches can be turned on at the same time by turning on switch $i$ while switches $j$ and $k$ are already both on. Suppose by contradiction that Benoît has a strategy that touches each of the switches $i, j, k$ only once (we have seen that he must necessarily turn on each of them at least once), suppose he turns on $i$ first, then $j$, then $k$. Then since he does not turn off any of these switches after turning them on, the pairs $i, k$ and $j, k$ of switches are turned on precisely at the same time, and therefore the corresponding bulbs cannot be distinguished from each other, contradiction. Thus, Benoît's strategy must necessarily touch one of the three switches at least twice.

From the previous analysis, in any triplet of switches, one of them must be touched at least twice. Thus, there can be at most 2 switches that are touched only once, and Benoît needs at least $2+2021 \times 2=4044$ minutes.

Let's show that Benoît can indeed find the correspondences between switches and bulbs in 4044 minutes. For this, he numbers the switches from 1 to 2023 and he turns on the switches $1,2, \ldots, 2023$ successively. Then he turns off the switches $1,2, \ldots, 2021$ in this order. This takes exactly 4044 minutes, let's verify that this strategy works. According to our previous study, it is enough to see that for two pairs of switches $i, j$ and $i, k$ with $i, j, k$ distinct, there is a moment when one of the pairs is on and not the other. Without loss of generality, $j < k$, and that the switch $k$ was already on, so $i > k$. But then since $j < k < i$, necessarily $j \leq 2021$ and at some point when Benoît turns off the switches, he turns off the switch $j$, at that moment the switches $i, k$ are still on, which indeed allows to distinguish between the two pairs.