There are $M = 100$ intact glasses at day 0. On each day $t = 1, 2, \ldots, 50$, sender A may irreversibly break any subset of the currently intact glasses. Receiver B perfectly observes the full pattern of intact and broken glasses at the end of each day.
The communication is one-way (A to B) and noiseless.
Compute the maximal number of distinct messages A can send to B over all 50 days.
How many bits of information does this correspond to?
Provide an explicit coding scheme that achieves this maximum.
Hints
Focus on a single glass. Since breaking is irreversible and the receiver sees the state each day, the only thing that matters is when (or whether) each glass gets broken.
Each glass has 51 possible trajectories: break on day 1, day 2, ..., day 50, or never break. The glasses are independent, so the total count is a product.
The maximum number of messages is $51^{100}$. To build the coding scheme, represent each message as a 100-digit base-51 number, where digit $i$ tells you which day to break glass $i$.
Worked Solution
How to Think About It: The critical constraint is irreversibility -- once a glass is broken, it stays broken forever. This means the state of the 100 glasses is a monotone binary string: each position can only transition from 0 (intact) to 1 (broken), never back. The receiver sees the full state each day, so the message is encoded in the entire sequence of states across all 50 days. The question is: how many distinct monotone trajectories are possible?
Quick Estimate: If we had just 1 day, we could send
^{100}$ messages (break any subset). With 50 days, each glass can be broken on any one of 50 days or never broken at all. That gives 51 choices per glass. So the total is $51^{100}$. Let's verify this is correct by thinking carefully about what distinguishes messages.
Approach: Each glass independently has its own timeline. We need to count the number of distinct observable trajectories.
Formal Solution:
Consider a single glass. Over 50 days, it starts intact and can be broken on exactly one day (or never). The receiver observes the state each day, so the observable trajectory of one glass is fully determined by the day it is broken (if ever):
Broken on day 1: trajectory is $(1, 1, 1, \ldots, 1)$ -- broken from day 1 onward
Broken on day 2: trajectory is $(0, 1, 1, \ldots, 1)$ -- intact on day 1, broken from day 2 onward
...
Broken on day 50: trajectory is $(0, 0, \ldots, 0, 1)$ -- intact until day 50
Never broken: trajectory is $(0, 0, \ldots, 0)$
So each glass has exactly $50 + 1 = 51$ distinct trajectories.
Since the 100 glasses are independent (breaking one does not affect another), the total number of distinct messages is:
$N = 51^{100}$
The number of bits: $\log_2(51^{100}) = 100 \log_2 51 = 100 \times \log_2 51$
Assign each message an index in $\{0, 1, \ldots, 51^{100} - 1\}$. Represent this index in base 51 as a 100-digit number $(d_1, d_2, \ldots, d_{100})$ where $d_i \in \{0, 1, \ldots, 50\}$.
For glass $i$: - If $d_i = 0$: never break glass $i$ - If $d_i = k$ for $k \in \{1, \ldots, 50\}$: break glass $i$ on day $k$
On each day $t$, sender A breaks exactly those glasses $i$ for which $d_i = t$. Receiver B observes the state after each day and decodes by recording, for each glass, the first day it appeared broken (or "never").
This scheme is optimal because it achieves exactly $51^{100}$ distinct messages, and no scheme can exceed this: the state space of monotone binary trajectories for 100 glasses over 50 days has exactly this cardinality.
Answer: The maximum number of distinct messages is $51^{100}$, corresponding to
00 \log_2 51 \approx 567.2$ bits. The coding scheme assigns each glass a "break day" from $\{0 \,(\text{never}), 1, 2, \ldots, 50\}$, encoding each message as a base-51 number with 100 digits.
Intuition
The key insight is that irreversibility simplifies the counting dramatically. Each glass is a monotone binary channel -- it can only go from 0 to 1, never back. So its entire trajectory over 50 days is fully described by a single number: when it breaks. This converts a seemingly complex combinatorial problem into a simple product of independent choices. The result $51^{100}$ is much larger than the naive single-day capacity of
^{100}$ -- the extra days multiply the alphabet size from 2 (broken or not) to 51 (broken on which day, or never). This style of reasoning -- reducing a complex sequential process to independent per-component choices -- appears frequently in information theory, combinatorics, and even in counting the number of possible order book states in a market.