David Ding: Indirect Thinking

Imagine attending a classical concert. As the pianist strikes the ivory keys of a Steinway as soothing melodies flow out of the grand instrument, the sound is rudely interupted by a--"cough!". "Cough!" again. You roll your eyes, annoyed by the fact that people in 2022 still haven't observed the proper etiquettes of enjoying the fine arts. Then, remembering that this is a sold-out concert at a very large hall, and the building itself is designed to reverberate sounds--harmony or cacophony, you put your mind at ease. Of course! Why wouldn't you hear a cough? It's simple math!

Let's calculate the probability of hearing a cough at a classical concert. In fact, the question is not if, but rather how many, coughs you will hear in the span of a, say, 2-hour classical concert at a packed hall. At the first glance, it might be near impossible to calculate since anyone or combination of people in the audience will perform the reflexive action of the diaphragm at any given time. However, this is where indirect thinking comes in. Rather than directly finding the probability of at least one audience memeber coughing, let us instead ascertain the probability that no one coughs. Then our answer is simply 1 minus that number.

Assuming each person has a tendency of coughing independent of others. Also, assuming, in 2022 given the benefit of the doubt, a vast majority of concertgoers observe the proper etiquettes and would not cough unless his/her body absolutely forces the issue. This means, say in a five minute span, one's probability of coughing is a mere 0.01%. Further assume that we are at Carnegie Hall, one of the most famous concert venues in the world with a seating capacity of 2804 (Stern Auditorium), and it's a packed house. Then we have:

\begin{align} P(\text{At Least One Cough}) &= 1 - (1 - 0.0001)^{2804} = \boxed{0.2445} \end{align}

That's right, even with ALL concertgoers observing the etiquettes and would only cough if even physical suppression is not enough, there would still be a 25% chance that a cough will be heard in any given 5-minute span. Let us extrapolate it to 0.25 coughs per five minutes or 0.05 coughs per minute, then in a 2 hour performance, the average number of coughs would be:

Where X is a Poisson random variable with parameter \(\lambda = 0.05\), representing 0.05 coughs per minute. Keep in mind that this is the best case scenario assuming only one cough is heard, which our original calculation did not assume.

As a remark, here \(X \sim \text{Poisson} (\lambda = 0.05)\) is an appropriate model as the coughs occur independently. We can even calculate the probability of, say, hearing 10 coughs in a 2-hour concert (OMG!), which is:

\begin{align} P(X = 10) &= \left.\frac{(\lambda t)^k e^{-(\lambda t)}}{k!}\right |_{\lambda = 0.02, t = 120, k = 10} \\ \\ &= \frac{6^{10} e^{-6}}{10!} \\ \\ &= \boxed{0.0413} \end{align}

There is a greater than 4% chance you will hear 10 coughs in a 2-hour concert, even assuming everyone follows the etiquettes.

Indirect Thinking Applications

Here is a curious problem that illustrates the power of indirect thinking. From MIT Primes Step 2017 Entrance Exam, Q12:

"In a certain country the Congress consists of 30 congress-people. Every pair of them are either friends or enemies with each other. It is known that every congress-person has exactly 6 friends in Congress. The Congress has many committees. In fact, every 3 congress-persons form a committee. Find 4 the number of committees such that all three members are pairwise friends or all three members are pairwise enemies. Explain."

Upon first glance, this problem may seem impossible. One would need to apply graph theory, and even so, it is not clear how to draw the connections such that each of the 30 congress members have exactly 6 friends. However, upon close inspection, we simply need to find the number of committees where all three members are pairwise friends OR all three members are pairwise enemies. Since there are three types of committees: all-friends, all-enemies, and mixed, and we are to find the total of the first two, can we somehow use indirect thinking here?

The answer is yes! Indirect thinking here means finding the total number of mixed committees and subtracting the result from the total number of committees, which is \(\binom{30}{3} = 4060\). The indrect thinking strategy works here because forming a mixed committee can be streamlined for each starting congress member. Pick any member. Then, to form a mixed committee with that member, simply pick a friend of that member and an enemy of that member. The committee, though three-person, can actually then be thought of as a two-party system:

For each member, there are 6 friends and 23 enemies to choose, and the options are independent of each other. Therefore, there are \(6 \times 23 = 138\) mixed committee options for each member. Since there are 30 members, this amounts to \(138 \times 30 = 4140\).

The quantity "4140" obviously multi-counts the number of mixed committees. However, it is not triple-counting. To see this, consider a committee made up of persons 1, 2, and 3. Say the committee is formed from person 1's perspective, and they choose 2 as their friend and 3 as their enemy. If 2 and 3 are friends, then the same committee will be formed from 3's perspective, but never from 2's perspective, and vice versa. This means that for any distinct three-member committee, it can be formed from exactly two of the committee's members. Hence, this is double-counting.

Our answer then is simply \(4060 - 2070 = \boxed{1990}\) all-friends or all-enemies committees.

Generalization and Sanity Checking

Applying this line of thinking, we can generalize the number of all-friends or all-enemies committees for this case. Consider an N-person congress (N > 3) where each person has F friends rest are enemies. Again every three people form a committee. Then our number of all-friends or all-enemies committees is:

For example, consider a 6-person congress where each person has 2 friends and rest are enemies. The number of all-friends or all-enemies committees is surprisingly only 2. You can easily draw out the graph for one of the cases and count for yourself! Applying our formula above, we get:

\begin{align} &\binom{6}{3} - \frac{6 \times 2 \times 3}{2} \\ &= 20 - 18 \\ &= 2 \\ \end{align}

As a sanity check, assume everyone is friends with everyone else, then \(F = N-1\) and we get:

\begin{align} &\binom{N}{3} - \frac{N(F)(N-F-1)}{2} \\ &= \binom{N}{3} - \frac{N(N-1)(N-(N-1)-1)}{2} \\ &= \binom{N}{3} - \frac{N(N-1) \times 0}{2} \\ &= \binom{N}{3} - 0 = \binom{N}{3} \end{align}

If everyone has exact two other friends, then one scenarios would be that every three person in the congress form a "friends triangle" (assume N is a multiple of 3). In this case, we can then directly calculate that the number of all-friends committees is \(N/3\). Indirectly, we have:

\begin{align} &\binom{N}{3} - \frac{N(2)(N-3)}{2} \\ &= \binom{N}{3} - N(N-3) \\ \end{align}

If everyone just has one friend, then we either have mixed or all-enemy comittees. Indirectly, we have:

\begin{align} &\binom{N}{3} - \frac{N(1)(N-2)}{2} \\ &= \binom{N}{3} - \frac{N(N-2)}{2} \\ \end{align}