land of light bulbs

Question

Leuks is the land of light bulbs, where the bulbs are leading a peaceful life, with no humans at all. Presently there are 100 residents . (Of course, they all are light bulbs!).

Let $a_{1}, a_{2}, . . .,a_{100}$ be the 100 residents.

The relationships that exist among the residents are quite complicated to understand.

For example, say, if $a_{1} $ is ON , then $a_{2}$ and $a_{3}$ are OFF, $a_{7}$ is ON.

If $a_{12}$ is ON and $a_{25}$ is OFF , then $a_{20}$ $a_{92}$ $a_{45}$ are ON.

These are just some examples and there are a lot more relationships like this that exist within the community.

Yearly, the community invites some citizens from Earth (of course Humans like you!) to solve this puzzle:

all the 100 bulbs go and hide in boxes numbered $b_{1}, b_{2}, . . .,b_{100} $ sequentially, i.e., a1 goes to b1 and so on.

They tell you ALL relationship possibilities that exist within the community as I gave in the examples.

Your aim is to figure out all the bulbs which are ON, by opening and looking up the ON/OFF status of minimum number of bulbs.

How will you do it? Can you win the prize!

Notes:

1. The human who finds all active bulbs with minimum number of lookups win

2. There is no guarantee that every bulb will be in some relationship. But note that the list of all possible relationships are given to you (For example as a collection of if... then...statements)

3. I am looking for a general algorithmic approach. For example, to start with, if a bulb is not in any relationship, you have to open the corresponding box for sure.

Answer 1

Since we are looking for a generic approach without knowing the exact 'rules', I would suggest the following:

1. First, assign each rule the properties $r_{cw}$ and $r_{ct}$ for the number of bulbs in the when and then clauses and then find the rule with the highest ratio $r_{ct}\over 2^{r_{cw}}$, i.e. the rule potentially giving you the most new knowledge with the fewest number of lookups taking into consideration that the chance for the when clause to be fulfilled is only $2^{r_{cw}}$. As long as we don't know anything about the bulbs, we must assume a 50/50 chance for a bulb to be on or off and the probability for $n$ bulbs to match a given condition is $1\over{2^n}$. Order the bulbs in the when clause in descending order depending on how often they occur in the other when clauses. Open the boxes for the bulbs in the when clause in this order (most used bulb first), stop as soon as a revealed bulb does not match the when clause and if all bulbs match the when clause, note the knowledge you have now gained about the bulbs in the then clause.

2. Throw away all rules, for which we based on the known bulbs can surely say that the when clause is not fulfilled. E.g. if a rule says 'If $a_1$ is on and ..., then ...' and we know that $a_1$ is off, we can ignore the rule.

3. After doing this, reevaluate the properties $r_{cw}$ and $r_{ct}$ for each remaining rule, so that only the number of unknown bulbs in each of the clauses are counted. Now, either find any rule with $r_{cw}=0$ and check if you can gain any new knowledge without opening new boxes or if no such rule exists, find yet again the rule with the highest ratio $r_{ct}\over 2^{r_{cw}}$, open the boxes in the same way as described in step 1. Repeat from step 2 until all rules have been evaluated or ignored.

4. At last, open the boxes of the still unknown bulbs to check their state.

Answer 2

Another approach (probably somewhat different of @jarnbjo's one):

1. Open the boxes of the bulbs which are not involved in any relationship, if they are those (since you have to open them anyway).
2. For the remaining ones, build a set $S$ consisting of all possible states ($2^N$ rows, where $N$ is a number of unopened boxes, so up to $2^{100}=1267650600228229401496703205376$ rows - it's large but forget about the physical restrictions for a while, these don't matter here).
3. For each relationship, exclude from $S$ the rows for which it's false. E.g. "if $A$ then $B$" excludes rows, for which $A$ holds but not $B$.
4. Now, we end up with $S$ being the set of possible states (considering it as a table with rows being the states, and columns being numbers of bulbs/boxes).
5. Pick up the box $b_i$ which has the most balanced number of 1's and 0's in its column in $S$, e.g. $\arg\min_i{|\#_1(i, S)-\#_0(i, S)|}$, where $\#_1(i, S)$ and $\#_0(i, S)$ is the number of ones (ONs) and zeroes (OFFs) in the $i$-th column of the $S$ table, respectively, and open the box. Exclude from $S$ the non-matching states (so the rationale about this step is to exclude the largest number of possibilities even in the worst case).
6. Repeat step 5 while $|S|>1$ (cardinality of $S$ is greater then 1, i.e. until we have only one possibility).

Answer 3

This seems like a relationship problem to me. I think we can try to use

(DSU) DISJOINT SET UNION here. Reference

Assumptions:

1. There are no conflicting relationships
2. Represent all the bulbs with 2 states. a11 means a1 bulb which is ON. Similarly a10 means a1 bulb which is OFF
3. Converse also hold true. For the given example, if 𝑎1 is OFF , then 𝑎2 and 𝑎3 are ON, 𝑎7 is OFF
4. Input example for going over steps:
   1. a61 -> a70, a90 -> a81
   2. a11 -> a20, a30 -> a41, a51, a61
   3. a131 -> a120 (if 13th bulb is ON, 12th would be OFF)

Steps:

1. Let us initially create 2*100 independent sets. This would represent 2 states for each bulb, i.e. ON and OFF. So we would initialize our structure with a10, a11, .... a1001, a1000 (100th bulb)
2. Now let us go over the relationships one by one:
   1. In the first one, we put a61, a70, a90 and a 81 in the same set. Basically we will call Union(a61, a70), Union(a61, a90), Union(a61, a81). Note that we don't need to call Union(a90, a71) or Union(a70, a81), etc. because of the DSU structure. (Think of them as putting the same set!)
   2. We need to add the opposite bulb states to our data structure as well. E.g. add to set Union(a10, a21), Union(a10, a31), Union(a10, a40), Union(a10, a50), Union(a10, a60)
   3. Continue to iterate over all the relationships and perform steps 1 and 2
3. After processing all the relationships we would be left with a bunch of disjoint sets. Each independent of one another. If any bulb has not appeared in the relationship, say a20 then we would have 2 sets belonging to it namely, a200, a201.
4. Now that we have all the disjoint sets, we count them. For the given example we would get 8 disjoint sets, namely:
   1. a11, a20, a30, a41, a51, a61, a70, a81, a90
   2. a10, a21, a31, a40, a50, a60, a71, a80, a91
   3. a101
   4. a100
   5. a111
   6. a110
   7. a131, a120
   8. a130, a121
5. We only need to count one possibility out of ON and OFF for each set's state. Take for e.g. a111 and a110 . We we take in turn to check if bulb a11 is ON or OFF. So we divide the count by 2. This should be the minimum number of bulbs which we need to check.
6. To find out which bulbs are on, we need to check one bulb from each set. That one bulb will tell us the status of the whole set.