Problem A. 907. (April 2025)

A. 907. 2025 light bulbs are operated by some switches. Each switch works on a subset of the light bulbs. When we use a switch, all the light bulbs in the subset change their state: bulbs that were on turn off, and bulbs that were off turn on. We know that every light bulb is operated by at least one of the switches. Initially, all lamps were off. Find the biggest number \(\displaystyle k\) for which we can surely turn on at least \(\displaystyle n\) light bulbs.

Based on an OKTV problem

(7 pont)

Deadline expired on May 12, 2025.

We solve the problem in general instead of just for 2025. Let \(\displaystyle f(n)\) denote the largest number \(\displaystyle k\) such that, with \(\displaystyle n\) bulbs, it is always possible to turn on at least \(\displaystyle k\) bulbs. Furthermore, define the following recursive sequence.

Let \(\displaystyle a(0)=0\), \(\displaystyle a(1)=1\). Let \(\displaystyle n \geq 2\), and let \(\displaystyle k\) be the positive integer for which \(\displaystyle 2^k-1 \leq n < 2^{k+1}-1\). Then define \(\displaystyle a(n)=2^{k-1}+a(n-(2^k-1))\). In other words, if \(\displaystyle n=(2^k-1)+i\) where \(\displaystyle 0 \leq i \leq 2^k-1\), then \(\displaystyle a(n)=2^{k-1}+a(i)\). It is clear that this recursive definition indeed defines the sequence \(\displaystyle a(n)\) unambiguously. We also mention another reformulation of the definition, which will be needed later. We obtain \(\displaystyle a(n)\) by writing the number \(\displaystyle n\) in the form \(\displaystyle n=\sum_{i=1}^\ell 2^{k_i}-1\) greedily, that is, once the first few \(\displaystyle k_i\) values have been determined, the next one is always chosen as large as possible. Then \(\displaystyle a(n)=\sum_{i=1}^\ell 2^{k_i-1}\).

We will prove that \(\displaystyle f(n)=a(n)\) holds for all positive integers \(\displaystyle n\). Once this is established, the specific case \(\displaystyle n=2025\) can be easily determined:

Thus \(\displaystyle a(2025)=512+256+128+64+32+16+8=1016\).

Let us now turn to the proof of the general equality. We start with a simple observation. If some bulbs and switches are given under the conditions of the problem, then the order of using the switches does not matter, and pressing a switch twice has no effect. This means there is no point in pressing a switch more than once, and only the subset of switches used matters.

Claim 1: \(\displaystyle a(n) \geq \frac{n+1}{2}\) if \(\displaystyle n \geq 1\).

Proof: We prove this by induction. The claim holds for \(\displaystyle n=1\). Let \(\displaystyle n \geq 2\), and assume the statement holds for smaller values. Let \(\displaystyle n=2^k-1+i\) where \(\displaystyle 0 \leq i \leq 2^k-1\). If \(\displaystyle i=0\), then \(\displaystyle a(2^k-1)=2^{k-1}\), so the claim holds. Otherwise, by induction,

\(\displaystyle a(2^k-1+i)=2^{k-1}+a(i) \geq 2^{k-1}+\frac{i+1}{2} \geq \frac{(2^k-1+i)+1}{2}.\)

Claim 2: The function \(\displaystyle f\) is increasing, and \(\displaystyle f(n+1) \leq f(n)+1\) holds for all positive integers \(\displaystyle n\). Furthermore, these two properties also hold for the function \(\displaystyle a\).

Proof: It is clear that if there is a construction for some number \(\displaystyle n\) where at most \(\displaystyle f(n)\) bulbs can be turned on, then if we take an \(\displaystyle m\)-element subset of the bulbs for any \(\displaystyle m < n\), and restrict the switches to this set, we still obtain a valid construction, in which at most \(\displaystyle f(n)\) bulbs can be turned on, so \(\displaystyle f(m) \leq f(n)\). Furthermore, if we add one more bulb to the \(\displaystyle n\)-bulb construction and connect it to all the switches, we obtain a construction with \(\displaystyle n+1\) bulbs, where at most \(\displaystyle f(n)\) of the original \(\displaystyle n\) bulbs can be turned on, hence at most \(\displaystyle f(n)+1\) in total, so \(\displaystyle f(n+1) \leq f(n)+1\).

For the function \(\displaystyle a\), these statements are easy to prove by induction. For \(\displaystyle a(0), a(1), a(2)\) the properties hold. We need to verify that \(\displaystyle a(n) \leq a(n+1) \leq a(n)+1\). Let \(\displaystyle n=2^k-1+i\) where \(\displaystyle 0 \leq i \leq 2^k-1\), and assume the statement has been verified for \(\displaystyle m<n\). If \(\displaystyle i<2^k-1\), then by definition \(\displaystyle a(n+1)-a(n)=a(i+1)-a(i)\), so the statement holds by induction. If \(\displaystyle i=2^{k}-1\), then \(\displaystyle a(n)=a(n+1)=2^k\), so the statement holds in this case as well.

Claim 3: For any positive integers \(\displaystyle n, m\), we have \(\displaystyle f(n+m) \leq f(n)+f(m)\).

Proof: Take a set of switches for \(\displaystyle n\) bulbs such that at most \(\displaystyle f(n)\) bulbs can be turned on, and take a separate set of switches for \(\displaystyle m\) bulbs such that at most \(\displaystyle f(m)\) bulbs can be turned on. Consider this as one large construction with \(\displaystyle n+m\) bulbs. Then at most \(\displaystyle f(n)+f(m)\) bulbs can be turned on, so by the definition of \(\displaystyle f(n+m)\) it follows that \(\displaystyle f(n+m) \leq f(n)+f(m)\).

Note that by induction this implies

\(\displaystyle f\left(\sum_{i=1}^\ell n_i\right) \leq \sum_{i=1}^\ell f(n_i)\)

for any positive integers \(\displaystyle n_1, n_2, \ldots , n_\ell\).

Claim 4: \(\displaystyle f(2^k-1)=2^{k-1}\).

Proof: In fact, we will not need the lower bound later on, but we will still present a simple, probabilistic proof. We will show the more general statement that we proved for the function \(\displaystyle a(n)\) in Claim 1, namely that \(\displaystyle f(n) \geq \frac{n+1}{2}\) for all positive integers \(\displaystyle n\). Consider an arbitrary construction with \(\displaystyle n\) bulbs. Independently, use each switch with probability \(\displaystyle \frac{1}{2}\). Consider an arbitrary bulb \(\displaystyle \ell\) and a switch \(\displaystyle c\) connected to it. Since the order of switch operations does not matter, we can view the process as first using all switches except \(\displaystyle c\) independently with probability \(\displaystyle \frac{1}{2}\), and then flipping a coin to decide whether to use \(\displaystyle c\). No matter the state of \(\displaystyle \ell\) before using \(\displaystyle c\), after using (or not using) \(\displaystyle c\) it will be on with probability \(\displaystyle \frac{1}{2}\). Let \(\displaystyle X\) be the random variable representing the number of bulbs that are on at the end, and for each bulb \(\displaystyle \ell\), let \(\displaystyle I_\ell\) be the indicator variable which is 1 if \(\displaystyle \ell\) is on, and 0 otherwise. We saw that each bulb is on with probability \(\displaystyle \frac{1}{2}\), so \(\displaystyle \mathbb{E}(I_\ell)=\frac{1}{2}\), where \(\displaystyle \mathbb{E}\) denotes expected value. Note that \(\displaystyle X=\sum I_\ell\), summing over all bulbs. Since expectation is additive, we have

\(\displaystyle \mathbb{E}(X)=\sum \mathbb{E}(I_\ell)=\frac{n}{2}.\)

Furthermore, with positive probability, we use no switches at all, so no bulbs are on. Therefore, there must exist a case where more than \(\displaystyle \mathbb{E}(X)\) bulbs are on, i.e., there exists a switch combination where at least \(\displaystyle \frac{n+1}{2}\) bulbs are on, which is what we wanted to prove.

For the upper bound, we show a construction with \(\displaystyle 2^k-1\) bulbs where no more than \(\displaystyle 2^{k-1}\) bulbs can be turned on. Assign to each bulb a distinct binary sequence of length \(\displaystyle k\) excluding the all-zero sequence. That is, every binary sequence of length \(\displaystyle k\) except the all-zero one is assigned to exactly one bulb. Let there be \(\displaystyle k\) switches, and for each \(\displaystyle 1 \leq i \leq k\), let the \(\displaystyle i\)-th switch (denoted by \(\displaystyle c_i\)) work on exactly those bulbs whose assigned code has a 1 in the \(\displaystyle i\)-th position. Since each bulb’s assigned code has at least one digit 1, every bulb is connected to at least one switch, so this is a valid construction. Suppose we use \(\displaystyle m \geq 1\) switches; due to the symmetry of the construction, we may assume these are \(\displaystyle c_1, c_2, \ldots, c_m\). Then the bulbs that will be on are exactly those whose code has an odd number of 1’s in the first \(\displaystyle m\) positions. It is known that there are exactly \(\displaystyle 2^{k-1}\) such sequences: after choosing the last \(\displaystyle (k-1)\) bits freely, the first bit is uniquely determined to ensure the total number of 1's in the first \(\displaystyle m\) bits is odd. Moreover, the all-zero code does not satisfy this condition, so there are exactly \(\displaystyle 2^{k-1}\) bulbs that are on. Thus, we have shown that regardless of which switches we use (as long as we use at least one), exactly \(\displaystyle 2^{k-1}\) bulbs will be on. Therefore, \(\displaystyle f(2^k-1) \leq 2^{k-1}\), as desired.

Claim 5: For all positive integers \(\displaystyle n\), we have \(\displaystyle f(n) \leq a(n)\).

Proof: Let \(\displaystyle n = \sum_{i=1}^\ell (2^{k_i} - 1)\) be the greedy decomposition. Then we saw that \(\displaystyle a(n) = \sum_{i=1}^\ell 2^{k_i - 1}\), and by the previous two claims,

\(\displaystyle f(n) \leq \sum_{i=1}^\ell f(2^{k_i} - 1) = \sum_{i=1}^\ell 2^{k_i - 1} = a(n),\)

as desired.

From now on, we aim to show that \(\displaystyle f(n) \geq a(n)\) also holds. The crucial claim is the following.

Claim 6: For all positive integers \(\displaystyle n\), we have \(\displaystyle 2f(n - f(n)) \leq f(n)\).

Proof: Consider a construction with \(\displaystyle n\) bulbs where at most \(\displaystyle f(n)\) bulbs can be turned on. Let \(\displaystyle L\) be the set of bulbs. Consider a subset \(\displaystyle C_1\) of switches whose combined use turns on a subset \(\displaystyle S \subseteq L\) of size \(\displaystyle |S| = f(n)\). Now ignore these bulbs and restrict our attention to the remaining bulbs in \(\displaystyle L \setminus S\). On this subset, the switches still define a valid construction with \(\displaystyle n - f(n)\) bulbs. Therefore, there exists a subset \(\displaystyle C_2\) of switches that turns on at least \(\displaystyle f(n - f(n))\) bulbs from \(\displaystyle L \setminus S\). If we first apply the switches in \(\displaystyle C_1\) and then those in \(\displaystyle C_2\), then at least \(\displaystyle f(n - f(n))\) bulbs will be on from \(\displaystyle L \setminus S\), and since we can turn on at most \(\displaystyle f(n)\) bulbs in total, at most \(\displaystyle f(n) - f(n - f(n))\) bulbs from \(\displaystyle S\) can still be on. This means that at least \(\displaystyle f(n - f(n))\) bulbs in \(\displaystyle S\) must have turned off when applying \(\displaystyle C_2\). Thus, if we start from the all-off state and apply \(\displaystyle C_2\), it will turn on at least \(\displaystyle 2f(n - f(n))\) bulbs. But we know that at most \(\displaystyle f(n)\) bulbs can be turned on, which proves the claim.

Let us now prove the main result. Suppose for contradiction that there exists some \(\displaystyle n\) such that \(\displaystyle f(n) \neq a(n)\), and let \(\displaystyle n\) be the smallest such number. Clearly, \(\displaystyle n > 2\). By Claims 2 and 5, in this case \(\displaystyle f(n) = a(n) - 1\). We will aim for a contradiction using Claim 6, which tells us, in this case (and using that \(\displaystyle f(m) = a(m)\) for \(\displaystyle m < n\)), that

\(\displaystyle 2a(n - (a(n) - 1)) = 2a(n - f(n)) = 2f(n - f(n)) \leq f(n) = a(n) - 1.\)

Therefore, to reach a contradiction, it is enough to prove the following claim:

Claim 7: For all positive integers \(\displaystyle n\), we have

\(\displaystyle 2a(n + 1 - a(n)) > a(n) - 1.\)

Proof: We prove this by induction. The statement holds for \(\displaystyle n = 1, 2\). Assume it holds for all \(\displaystyle m < n\), and write \(\displaystyle n = 2^k - 1 + i\) with \(\displaystyle 0 \leq i \leq 2^k - 1\).

First, consider the case \(\displaystyle i = 2^k - 1\). Then \(\displaystyle a(n) = 2^k\), so

\(\displaystyle 2a(n + 1 - a(n)) = 2a(2^{k+1} - 1 - 2^k) = 2 \cdot 2^{k-1} > 2^k - 1 = a(n) - 1,\)

so the statement holds in this case.

Now assume \(\displaystyle i < 2^k - 1\). Then

By Claim 1, \(\displaystyle i + 1 - a(i) \leq \frac{i+1}{2} < 2^{k-1}\), so \(\displaystyle i + 1 - a(i) \leq 2^{k-1} - 1\). So by definition,

\(\displaystyle a((2^{k-1} - 1) + (i + 1 - a(i))) = 2^{k-2} + a(i + 1 - a(i)).\)

Using the induction hypothesis,

which is exactly what we wanted. This completes the proof of the main result.

Statistics:

10 students sent a solution.
7 points:	Aravin Peter, Bodor Mátyás, Holló Martin, Minh Hoang Tran, Varga Boldizsár.
3 points:	2 students.
1 point:	1 student.
0 point:	1 student.
Not shown because of missing birth date or parental permission:	1 solutions.

Problems in Mathematics of KöMaL, April 2025