0

Here is an interview question:

There are 100 distinguishable windows arranged in a straight line, 2 people and 50 days. One of them sends a message to the other by breaking any number of windows on any given day. What is the maximum number of information bits they can transmit?

Second part: The first person breaks windows, while the second one repairs some of them. They want to transfer as many bits as possible every day. Determine an algorithm and the maximum possible amount of bits that can be transmitted. The first person can get information by looking at windows which were repaired, second one - with broken windows.

The first part can be solved as follows: Each window is independent, and there are 51 possible states (broken at i-th day) for each window. Therefore, there are $51^{100}$ distinguishable ways to break the windows, which means that $log_2(51^{100})$ bits of information can be transmitted. How do I solve the second part?

Leeisateam
  • 13
user6703592
  • 535
  • 1
    Isn't the first one the other way round? For each window you choose one of 51 choices (when do break it, if ever), so with 100 windows you have $51^{100}$ choices. – Jukka Kohonen Oct 03 '21 at 11:29
  • @JukkaKohonen sorry it is a typo, have corrected – user6703592 Oct 03 '21 at 11:48
  • The question is "How many bits of information he can transfer?". So your answer is that he can transfer $51^{100}$ bits? That does not seems to be realistic. Also the question does not specify whether windows are distinguishable one from another. So whether you only know that, say, three windows were broken or you know exact position of the three broken windows in a row of 100 windows. So to me the question is stated ambiguously. – azerbajdzan Oct 03 '21 at 12:06
  • @azerbajdzan sorry the bits should take $log_2,$ pls see my update – user6703592 Oct 03 '21 at 12:11
  • For the second part, how about $3^{100}$ as each window will be either not broken, broken without repair, or broken with repair. – acat3 Oct 03 '21 at 12:25

1 Answers1

1

Let's consider just 1 day of communication for now.

Strategy 1: Considering the first person's transmission, let's call a broken window a "1" and an unbroken window a "0". Naively, the first person could transmit up to 100 bits, and the second could transmit $n$ bits, if $n$ windows were broken by the first person. If the bits are assumed to have equal probability of being a "0" or a "1", then in expectation, the second person will be able to transmit 50 bits.

For Strategy 1, the worst case scenario would be if the first person transmits all zeros by not breaking any windows. Then the second person won't be able to transmit any bits.

Strategy 2: To improve the worst case scenario, the first person could "sacrifice" the first window by using it as follows: if the first window is broken, then the second person should invert the other 99 bits (broken window = "0", unbroken window = "1"), otherwise read the other 99 windows normally. If at least 50 out of the 99 bits the first person wants to transmit are 0, they should break the first window and invert the 99 bits. Else, don't invert the 99 bits.

This guarantees that there would be at least 50 broken windows, and the second person could use the first 50 to transmit a guaranteed 50 bits, for instance.

Strategy 2 would have a worst case scenario of the first person transmittng 99 bits, and the second person transmitting 50 bits, for a total of 149 bits.

I'm not sure how to prove whether this is the optimal strategy, though.

Now, let's try a similar version of the problem where they communicate over a period of many days, where some windows might already be broken before the first person chooses which windows to break.

Strategy 3: Let's call a window "affectable" if the current player can change its state. So for the first person, their "affectable" windows are the unbroken ones, and for the second person, their "affectable" windoes are the broken ones.

Let's say at the start of some person's turn, there are at least 66 affectable windows. (Base case: this is true on Day 1.) Using a similar tactic, the person can use the first 66 affectable windows to transmit 65 bits of information and gurantee that at least 33 of those 66 windows are affected by them (i.e. broken or repaired by them). If there are more than 66 affectable windows at the start of the first person's turn, they should affect all the other windows. This ensures the next person will have at least 33 + (100-66) = 67 affectable windows at the start of their turn, which they can choose to repair. Both players can use this strategy, making a loop.

If both players use this strategy, each person can transmit a guaranteed 65 bits on their turn. I think this strategy is optimal, where I'm trying to maximise the worst case number of bits a person can transfer on any turn, but I'm not sure how to prove it.

Let's try yet another strategy, where each person might have a variable of bits transmitted each day.

Strategy 4: Each person uses all n affectable windows, to transmit n-1 bits, while guaranteeing that at least $\lfloor{n/2}\rfloor$ + (100-n) windows are affectable by the next person. This strategy performs at least as well as Strategy 3. If the bits are assumed to have some given probability of being a "1" or a "0" then the expected number of bits each person can transmit could be calculated using a Markov chain, or estimated using a Monte Carlo simulation (it's somewhat tedious, so I'm not gonna do this).

Leeisateam
  • 13