How High Can You Count With Menorah Math?¶
Riddler Express¶
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?
Solution¶
There are two types of menorah configurations.
Symmetrical¶
Some are symmetrical about the center, and thus look the same from the front or back.
To count all the symmetrical configurations, simply count the number of ways to light all the candles (subtract one for no lit candles) on one side of the center, which is:
$$2^{\frac{8}{2}} - 1 = 15$$.
Asymmetrical¶
Some are not symmetrical about the center, and thus have a complementary configuration when viewed from the opposite side.
Another paired example:
Each pair should be counted once.
The number of asymmetrical pairs is half of the difference of the total number of configurations and the total number of symmetrical configurations:
$$\dfrac{2^{8} - 2^{\frac{8}{2}}}{2} = 2^7 - 2^3 = 120$$.
Answer¶
Thus, there are a total of $$15+120 = 135$$
configurations, indicating a maximum of $135$ nights.
A summary of the configurations based on the number of candles lit is given in the table below.
| Candles Lit | Symmetrical Configurations | Asymmetrical Configurations | Total Configurations | Day Indices |
|---|---|---|---|---|
| $1$ | $0$ | $4$ | $4$ | $1 - 4$ |
| $2$ | $4$ | $12$ | $16$ | $5 - 20$ |
| $3$ | $0$ | $28$ | $28$ | $21 - 48$ |
| $4$ | $6$ | $32$ | $39$ | $49 - 86$ |
| $5$ | $0$ | $28$ | $28$ | $87 - 114$ |
| $6$ | $4$ | $12$ | $16$ | $115 - 130$ |
| $7$ | $0$ | $4$ | $4$ | $131 - 134$ |
| $8$ | $1$ | $0$ | $1$ | $135$ |
Here are the $135$ nights:
Note that for a menorah with $2n$ candles, the total number of configurations is :
$$2^n - 1 + \dfrac{2^{2n} - 2^n}{2}$$
$$= 2^{2n-1} + 2^n - 2^{n-1} - 1$$
$$= 2^{2n-1} + 2^{n-1} - 1$$
$$= 2^{n-1}\big(2^n + 1\big) - 1$$
If $1$ were not being subtracted for no candles lit, this would be identical to A007582.