The answer to the bonus riddle is that o(N) is possible. The following result is used to encode information in the lamps after most have already been set to off and some random subset remains: Consider ways to encode information into a subset of bits in a string of length N (all bits outside subset forced to 0) such that the information can be decoded based only on the encoded string, without knowing which subset the encoding was restricted to. The following decode procedure allows encoding C bits in any subset of size M as long as M >= C * (log2(N) + O(1)) - If a string contains 4 or more 1 bits, cut it in half (round cut point down if in the middle of an element) and return the result of recursively decoding the left half, then the right half. Swap 0 and 1 in the recursive result (this swapping is not necessary for the overall proof here, it only removes a factor of 2 from the number of bits needed in the worst case - a worse result would be good enough for the lamp riddle). - If the string contains 0 or 3 set bits, return empty output. - If the string contains one set bit, return '1', if two '0'. Proof: Consider the tree structure defined by the recursive cutting in half, with leaf nodes containing either the number 0 or 1. Remove all nodes under which there no set bits. As long as there are leaf nodes that do not either contain at least the number 3 or have a sibling tree with total at least 3, collapse their parent node to a leaf node with a value equaling its subtree total. This will result in all leaf nodes containing 1, 2, 3, or 4. We'll discard any 4th set bit and treat it the same as 3. Nodes with 1 or 2 are attached to an intermediate node leading to one or more of the 3s. Any 2 will allow communicating one bit by setting one or both of the bits there. We can assume that there are none in the worst bit efficiency case. Consider the division of the graph into parts belonging to a particular 3-node and shared ones (depending on whether the intermediate nodes have one or more 3-node children). Any "private" part will be a chain of intermediate nodes with possible 1-node leaf nodes attached. The height of the graph is bounded by log2(N). If N3 is the number of nodes with value 3, the total number of intermediate nodes is thus bounded by N3 * log2(N). If there is a chain of x intermediate nodes leading to a 3-node, such that the chain is not shared with any other 3-nodes, then either the subtree of the chain contains at most x/2 1- nodes, or the subtree can encode at least one bit by itself. This is because of the swapping of 0 and 1 between odd and even levels of the tree - if more than half the nodes had a 1-child, at least one would necessarily be at a level where the single bit encodes the correct result. For parts of the chain from root to a 3-node that is shared with other 3-nodes, we divide the "cost" of 1-nodes between all below. That means at most a half 1-node per intermediate node for each 3-node. Thus for each 3-node, either its own subtree can encode at least one bit and there are at most log2(N) 1-nodes corresponding to it, or its subtree may not encode a bit by itself but there are at most log2(N)/2 corresponding 1-nodes. For any 3-node whose "private" chain does not encode a bit, we can collapse the subtree into a 1 or 2 that does encode a bit, possibly converting another 3-node into one that does encode a bit in its chain. In either case we can encode a bit per at most two 3-nodes (possibly originally containing 4+4 bits), and for each bit there are at most log2(N) 1-nodes that will be set to 0. Construction for the main riddle: My previous answer used a group division, where each group had the property that an error-correcting code would allow detecting and correcting one-bit errors, and the encoded value allowed rejecting 1/6 of lamps as "not last" when there were no errors. This will use a similar construction, but with rejected portion approaching 1 as group size goes to infinity. The basic idea is to keep setting lamps off until only a small portion remains, then encode a Hamming code checksum assuming remaining lamps are set to 1. If the checksum indicates no error, the last bit must be either one of the 1s or in a limited area of bits used for the signaling itself which has to contain more 0s for that purpose. Let the size of a group be M. We want to record a Hamming-type checksum, which requires log2(M) bits. Divide the group further into subgroups of size x. We'll pick some arbitrary remaining (not set to 0 yet) position for each checksum bit, and record the positions using the technique of the above lemma. We'll put the checksum bits in the same subgroup, so each position requires log2(x) bits. To be able to encode them all in one subgroup, the lemma requires log2(M) * log2(x) * log2(x) bits to remain available in that subgroup (plus a few bits for identifying which subgroup the checksum bits are in). We'll denote that quantity by E. To cope with possible one-bit errors, we'll just record the same thing in 3 subgroups. This gives the following encoding procedure: Keep setting lamps to off, unless the subgroup has at most E remaining lamps, in which case set it on (this will be used to distinguish the 3 encoding subgroups as they'll have less lamps on). Continue this until there are only 3 subgroups with E remaining lamps. At this point, we'll select the values we will set for all the remaining lamps. We can use the subgroup that just fell below E for the checksum bits. Encode its identifier and some free lamp positions within it in each of the 3 subgroups. Every remaining lamp outside those subgroups will be set to on. Calculate the Hamming checksum for the bits outside the chosen checksum bits, then finally set the values of the checksum bits. The encoding of the lemma requires at most 5 set bits for each encoded bit, so the 3 subgroups containing encoded values can be identified as those having substantially fewer than E set bits. At least two of them will give identical encoded values, which allows getting the Hamming checksum and then verifying the value overall. If the code is correct, the last bit must be in one of the 3 subgroups, one of the checksum bits, or a 1 bit elsewhere. This gives a total of (M/x)*E + 3x possible bits. The value of x minimizing this (substituting log(x) = log(M)/2) is x = sqrt(M * log2(M)**3 / 12), and the number of remaining bits is around 6 times that, or sqrt(M*log2(M)**3 * 3). Using this construction in the original group scheme gives a required number of guesses around 4/3 * 3**(1/3) * log2(N) * N**(2/3) Seems like this scheme becomes useful with N somewhere around ten thousand (though the above approximation isn't too good at that point yet and gives a somewhat more pessimistic picture, not 100% sure if the calculation I used was accurate either).