Question

a group of n students, all of whom have distinct heights, line up in a single-file line uniformly at random. if a student has any students in front of them who is taller than them, then they cannot see. for this reason, every student files one complaint for each taller student who is in front of them since each one of these students would individually block the original student from seeing. for example, if there were 3 students, where the tallest student was in the front and the shortest student was in the back, there would be 2 complaints from the shortest student and 1 complaint from the middle student. compute the expected number of complaints.

Answer 1

The expected number of complaints when n students line up at random, with each shorter student complaining about taller students in front, can be calculated as the sum of the first n-1 positive integers. This sum is n(n-1)/2, giving us the total expected number of complaints.

Step-by-step explanation:

To calculate the expected number of complaints in a group of n students with distinct heights, we consider each position in the line and determine the probability that any given student will receive a complaint from each other student. Since the heights are distinct, there are n! (n factorial) possible ways to arrange the students. A certain student will only not complain about another student who is in front of them if that other student is shorter.

Consider the student who is the second tallest. No matter where they stand in the line, there will always be exactly one complaint about them from any student behind them (the tallest one). Given there are n-1 other positions that this second tallest student could be in, the expected number complaints just for the tallest student, from this student, would be n-1 divided by n (because on average, the second tallest student would be a complaint for the tallest student in n-1 out of n possible positions in front of them).

Generalizing this pattern, for any given student, the expected number of complaints from all the students behind them can be computed. We sum these expected values across all students to get the total expected number of complaints. The final calculation for total expected complaints is given by:

1. 
   
3. Calculate the number of students that each student can see (n minus their position number).
4. 
   
6. Sum these values for all students.
7. 
   
9. Divide the sum by the number of students to obtain the average number of complaints per student.
10. 
    
12. Multiply this average by the number of students to get the total expected number of complaints.

Since each student in the line has a 1/n chance of being the tallest, the second tallest, and so on, the total expected number of complaints for a line of n students will be (n-1)+(n-2)+...+1, which is the sum of the first n-1 positive integers. This sum is equal to n(n-1)/2. Therefore, the expected number of complaints in a line of n students is n(n-1)/2.