Question

1. Let O be the origin of the plane. Imagine that five points, not equal to O are placed on the plane. Prove that there are two of those points P and Q such that the angle ∠POQ is acute.

View this problem as an application of the pigeonhole principle. What are the pigeonholes? What are the pigeons? Complete the argument.

2. You generate a random N-bit string and compute X = ∑ xi, where xi are the 0 and 1 entries of the string.
What is the probability that X is odd if N is odd?

Answer 1

Using the pigeonhole principle with angles as pigeonholes, it's shown that there must be at least one acute angle among the points. For an odd N-bit string, the probability that the sum of bits is odd is exactly 0.5.

Step-by-step explanation:

To solve the problem using the pigeonhole principle, think of the angles made with the origin as pigeonholes. There are five points besides the origin, there are ten possible pairings to form angles. If we divide a full circle (360 degrees) into four quadrants of 90 degrees each, there are four pigeonholes. With ten possible pairings (pigeons), at least one quadrant must contain more than two pairings. Since angles within a quadrant are acute, it follows that at least one of these angles will be acute, proving the statement

For an N-bit string where N is odd, the probability that the sum X of bits is odd is exactly 0.5. This is because the sum of an odd number of terms that can each be 0 or 1 can be evenly distributed between even and odd results. Therefore, the probability of obtaining an odd sum is equal to the probability of obtaining an even sum, hence P(X is odd) = 0.5.