1
$\begingroup$

Here is an interview question for brainstorming:

There are 100 different windows (suppose they stand in a line), 2 people, and 50 days. One communicates with the other by breaking windows in any day. How many bits of information can they transfer?

Second part: On each day the first person breaks windows then the second one repairs some of them. They want to transfer as many bits as possible every day. Find an algorithm and the largest possible amount of bits. (The first person gets information by looking at windows which were repaired and the second one by looking at broken windows.)

The first question is very easy, since each window is independent and there are 51 states (broken at the i-th day) during the 50 days. Therefore there are $51^{100}$ outputs in total. But I have no idea about the second question.

Edit:

I found an answer on a website. I think it makes sense.

In the second case, note that the amount of information that can be sent by one person is limited by how much information the other person sends. Note that if the breaker doesn't break a window, then the repairer cannot repair it. Likewise, if the repairer doesn't repair a window, then the breaker cannot break it on the following day. By this symmetry, one can solve the problem by supposing that the second person just repairs all of the windows all the time. Thus, the first person is able to transfer information $(2^{100})^{50}$ pieces of information. The 2 comes from the fact that he can either break a window or leave it whole on any given day. Again, to convert this to bits just apply $\log_2.$

$\endgroup$
4
  • 1
    $\begingroup$ How do you obtain the $51^{100}$ answer? Once a window is broken it remains broken, right? Thus, any state after day $i$ is not independent of the state at day $i.$ $\endgroup$
    – whuber
    Commented Oct 18, 2021 at 14:32
  • $\begingroup$ @whuber I understand as how many results of 100 windows there are after 100 days. $\endgroup$ Commented Oct 18, 2021 at 18:12
  • $\begingroup$ I see: if we view the windows as being variables whose values are the day on which the window is broken (setting this day to 51 if the window is never broken), then these variables are independent and each window has 51 possible values. For the second question, start by considering how much information can be transferred when a person has only $k$ windows available to break. You might want to begin with a simpler version of the problem where "100" is replaced by "2" or "3," say. $\endgroup$
    – whuber
    Commented Oct 18, 2021 at 19:21
  • $\begingroup$ The website answer you quote suggests one way to communicate information, but it does not demonstrate it "transfers as many bits as possible" each day. In fact, it falls far short of being optimal, if we understand "transfer" in the sense of two-way communications rather than merely sending information from person 1 to person 2. $\endgroup$
    – whuber
    Commented Oct 19, 2021 at 16:49

1 Answer 1

2
$\begingroup$

Let's address the second question, because it's more difficult and the answer you found is not optimal.

Part of the problem lies in the interpretation of "transfer as many bits as possible every day." This raises several issues:

  1. Do we want the transfer to be two-way or just one-way?

  2. Does "as many bits as possible" mean on average or at a minimum?

  3. Does "as many bits as possible" mean for each person or total?

  4. Is a two-way channel with an asymmetric capacity acceptable, or should both people be able to achieve a common guaranteed rate of information transfer to the other?

When the transfer is intended to be one-way only, then the quoted solution in the question is best. This is a trivial matter: with 100 windows, you cannot communicate any more than 100 bits of information and, to achieve this rate, the second person must restore all the windows after each day.

The essence of the problem is captured by considering what daily throughput can be guaranteed for the total two-way communication. That is the version I will discuss. I will also give solutions for the symmetric version of this problem.


To set this up, let the window-breaker be person $A$ and the window-repairer be person $B.$ We might as well solve the problem generally for $n$ windows. I'll just sketch the basic argument and leave the (relatively easy) details for you to prove:

  1. At the beginning of any day, both people know which windows are broken.

  2. A "code" for communicating from $A$ to $B$ is a set of subsets of the intact windows. (Such a subset is a "word" of the code.) A code for communicating from $B$ to $A$ is a set of subsets of the broken windows.

  3. The amount of information a person can send to the other (in bits) is the binary logarithm of the code used by the sender.

  4. Therefore, the total amount of information that can be exchanged in a day is the sum of the logarithms of the sizes of the two codes. We wish to maximize this "daily throughput."

  5. All else being equal, it is better for $A$ to have as many unbroken windows available as possible when $A$ is sending and it is better for $B$ to have as many broken windows as possible when $B$ is sending.

  6. Therefore, an optimal code for $A$ will use words with as many broken windows as possible and an optimal code for $B$ will use words with as many repaired windows as possible.

  7. Using optimal coding, on day $t=0,1,2,\ldots,$ let $A$ have $a$ unbroken windows available (and therefore $n-a$ are broken). Suppose $A$ adopts a code in which the number of unbroken windows available to $B$ is guaranteed to be at least $b.$ Then if the two codes achieve the optimal guaranteed throughput, $B$ must adopt a code that assures $A$ will again have at least $a$ unbroken windows the next day.

  8. This implies $B$ must repair at least $a+b-n$ windows.

  9. Because $A$ only needs to guarantee at least $b$ broken windows for $B$ to repair, the optimal code for $A$ will consist of all words of length $a$ that break at least $b - (n-a) = a+b-n$ more windows. Let the number of these words be $G(a,a+b-n).$

  10. Similarly, the number of words $B$ can use is $G(b, a+b-n).$

It remains only to count and optimize. Basic combinatorial principles tell us

$$G(a,x) = \sum_{k=x}^a \binom{a}{k}.$$

When $X$ is a random variable with a Binomial$(a,1/2)$ distribution $F_a,$

$$G(a,x) = 2^a\left(1 - F_a(x-1)\right).$$

This is usually computed in terms of an incomplete Beta function in constant time.

Thus, the problem is to

Find $0\le a \le n$ and $0\le b \le n$ for which the minimum daily throughput of $\log_2(G(a,a+b-n)) + \log_2(G(b,a+b-n))$ bits is as large as possible.

For smallish $n$--values less than a few thousand are amenable to quick calculations--a brute-force search does the job. (It is intuitively evident $a=b$ at the optimum, but I haven't assumed that.)

For reference, note that the solution quoted in the question has a daily throughput of $n$ bits: $A$ uses a code of $2^n$ words and $B$ cannot communicate any information back. Can we do better than this?

For $n \lt 3,$ the answer is no. But for $n=3,$ the solution $a=b=2$ achieves a daily throughput of $\log_2(9)\approx 3.17$ bits. Let's inspect the details:

  • $a=2$ means $A$ is guaranteed to have at least $2$ intact windows. $b=2$ means $A$ must break at least one of them. There are at $3$ ways this can be done. (When $A$ is presented with $3$ intact windows, she must break at least two of them--but that's okay, because there are now $4$ ways this can be done.)

  • Likewise, there are at least $3$ words available to $B$ (and maybe $4$) that present $A$ with at least $2$ intact windows the next day.

  • Thus, every day there are at least $3 \times 3 = 9$ possible communications from $A$ to $B$ and back again. The rate of $\log_2(9)$ exceeds the rate of $\log_2(8)=3$ in the one-way procedure described in the question.

Things eventually get much better than this. We can study the situation by using the Normal approximation to the Binomial distribution. It shows that asymptotically, for large $n,$ $a$ and $b$ should be around $0.724n.$ This achieves a guaranteed daily throughput of more than $1.38 n$ bits.

The case $n=100$ is nearly asymptotic: the optimum is achieved at $a=b=71,$ with a throughput of at least $134.6.$

Here are plots of some exact solutions (found with brute-force search). The dotted red lines show the asymptotic values. The curves bounce around due to the discrete nature of the optimization problem.

Figure

$\endgroup$
3
  • $\begingroup$ if the source code can be provided this can be quite useful as it provides more insight on the topic $\endgroup$
    – Maximilian
    Commented Oct 21, 2021 at 20:38
  • 1
    $\begingroup$ @Maximilian This is simpler than it might look if you're willing to assume the optimal solution occurs at $a=b.$ f <- function(n, log.G=g) { a <- b <- 0:n; R <- log.G(a,a+b-n) + log.G(b,a+b-n); a.max <- which.max(R) - 1; list(optimum = R[a.max+1], a=a.max) }; f(100) It returns a list giving the optimal rate and optimal value of $a$. It relies on a previously defined implementation of the binary logarithm of $G,$ such as g <- function(n, k) n + pbinom(k-1, n, 1/2, lower.tail=FALSE, log.p=TRUE) / log(2), where pbinom is the R version of $F_a$ I mentioned after item (10). $\endgroup$
    – whuber
    Commented Oct 21, 2021 at 21:27
  • 1
    $\begingroup$ many thanks, I can read it now more clearly. $\endgroup$
    – Maximilian
    Commented Oct 22, 2021 at 7:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.