December 12, 2020
"Yesterday was the first night of Hanukkah, which means millions of Jews began lighting their menorahs. It is traditional to start with one candle in the rightmost position, which is lit using a central candle called a shamash. On the second night, a second candle is added to the left of the first. On the third night, a third candle is added to the left of the second, and so on, until all eight candles have been added on the final night.
With this system for adding candles, whether you are looking at the menorah from the front (i.e., in your home) or back (i.e., through a window), you can easily determine which of the eight nights of Hanukkah it is by counting the number of candles (other than the shamash). But what if you wanted to make that same menorah capable of tracking more than eight nights?
To do that, you’d have to devise a new system of adding or moving candles (other than the shamash in the middle, which is always lit) around the menorah so that it can uniquely indicate as many nights as possible. Your system must read the same forward and backward, so that regardless of whether you’re looking at the menorah from the front or the back you will still know what night it is. What is the greatest number of nights that could be indicated using your system?"
Answer: 80 Nights
Explanation:
If it weren't for the "read the same forward and backward" part of the puzzle, the answer would have been \(2^8 = 256\) nights because it would be the theoretical limit: each of the 8 candles either in lit (1) or unlit(0) state, which combines to form an 8 bit integer of 256 different values. However, such strategy would not be unique. Consider a menorah pattern as follows:
0101 | 0000
Read from left to right, and it would represent the base-10 integer of 80. However, reading from right to left yields a value of 10. Since looking at the menorah you don't know the direction intended, this would not yield a unique night.
We therefore require more information, or bits, to distinguish the direction intended to read the binary code output by the menorah candles. Since there are two directions, we need at least \(\log_2(2) = 1\) bit to represent the direction, thereby capping our theoretical limit of nights to \(2^7 = 128\) (leaving 1 candle at minimum to represent the directional information). Unfortunately, we cannot just *pick* any candle, or bit, to represent the directional information because there is no way to assign the "direction bit" uniquely since the \(i\)th position of the candle from left to right would be the \((9-i)\)th position going from right to left, and \(i \neq (9-i)\) for any integer \(i\). This means we need at least two bits, or candles, to represent the direction, giving us a lower bound of \(2^6 = 64\) nights. We can do better than 64 nights, however, using the following strategy which maximizes the usage of the two bits for direction.
We pick the two candles on both ends of the menorah as our directional candles, since the candles on the ends will not change viewed either from the front or the back. There are four scenarios for the two candles:
Only the first three scenarios can be uniquely determined because the last two will be indistinguishable without knowing the intended viewing direction. Therefore, for each of the distinct scenarios, we just need to maximize as many remaining candles as possible to convey information about the different nights. Please note that each of those three cases are mutually exclusive, so the total representable nights will be the sum of the nights of each of the three scenarios: 00, 11, and 01.
For 00 and 11, we can only uniquely determine whether the ends are lit or not, and not the direction. Therefore, the inner candles must be symmetric about the shamash. For example: 0 110 | 011 0. In this case, the number of nights will be represented by the binary number to the left of the shamash, whether viewed from the front or the back (it will always be the same number).
For the 01 case, the night will be represented by the 6-bit candle pattern in the middle, always going from the unlit (0) end to the lit end (1). This will not change whether the lit end is on the left or on the right. For example, if one sees: 1 010 | 110 0, the number extracted will be 011010, the six bits in the middle going from the 0-end to the 1-end. This will yield the same result even if one sees this menorah from the other side: 0 011 | 010 1.
Therefore, in the first two scenarios, a total of \(2^4 = 16\) nights can be represented because the pattern must be symmetric. In the third scenario, the 6 candles in the middle can be of any pattern, yielding an additional \(2^6 = 64\) nights for a grand total of 80 nights. An example rule might be the following:
Nights 1 to 16: make sure both ends are either 00 and 11. Light the left half of the candle based on the binary representation of night \(N-1\) and reflect across to the right side about the shamash.
Nights 17 to 80: light one and leave the other unlit. Going from the unlit end to the lit end, light the middle six candles to represent the binary number of night \(N-17\).
1010 | 0101: here we see both ends are the same (1), so we simply read off the left side of the menorah: 1010. So it is night (10 + 1) = 11 (here we are counting from 1 and not from 0).
0010 | 0100: Similar to above, except both ends are (0). Again we count the left side: 0010. So it is night (2 + 1) = 3.
0110 | 1111: So one end is lit while the other is unlit. Going from the unlit to the lit side, we get the inner bits as 110111. This translates to 55 in base-10. We then add 17 to it to arrive at night (55 + 17) = 72.
1100 | 0000: Again, one end is lit while the other is unlit. We always go from the unlit end to the lit end, so we get 000001 for our middle bits. This is the value 1 in base-10. We add 17 to it and we arrive at night 18.
The menorah will always consist of a shamash which is always lit, accompanied by 8 candles: 4 on each side. However, if we just have an arbitrary row of \(N\) candles, and the same conditions of the puzzle apply, what is the maximum number of nights?
It turns out that it doesn't matter whether \(N\) is even or odd. If \(N\) is odd, even though we have a "middle" candle that will not change positions when viewed either way, we still wouldn't be able to tell the direction information from that candle alone because we would still get two different results on the other candles when viewed from different sides. The crux in the general case is still using the two end candles effectively to convey the directional information, and then maximize the number of nights represented using the remaining candles. So our general strategy applies:
For 00 and 11, we can utilize half of the candles (as the other half must be symmetric) to represent a total of \(2^{\lceil\frac{N}{2}\rceil}\) nights (if \(N\) is odd we can make use of the middle candle). For 01, we can represent an additional \(2^{N-2}\) nights. So the total number of nights that can be represented by \(N\) candles uniquely when viewed either from the front or the back is: \begin{equation} 2^{\lceil\frac{N}{2}\rceil} + 2^{N-2} \end{equation}