Problem: usc invited each south carolina high school to send up to 39 students to watch a football game . a section which has 199 seats in each row is reserved for those students . what is the least number of rows needed to guarantee that if 2006 students show up , then all students from the same high school can be seated in the same row ?
Rationale: the answer is 12 rows . if 59 schools send 34 students each , then we can sit at most 5 groups of students in the same row , so we will need 12 rows . next , 12 rows are sufficient . assume that this is not the case . suppose the groups of students are seated like this : first the largest group , then the second largest group , then the third largest group , etc . suppose we run out of space - there are not enough seats in any row to seat together the next group . suppose the first group that can not be seated together is the kth group and it consists of n students . then k 61 since any row fits at least 5 groups . also , n 2006 / k 2006 / 61 < 33 ( all groups already seated are no smaller than the kth group ) . so , n 32 . since there is not enough space in any of the 12 rows to seat the kth group , then there must be at least 168 students seated in each of the 12 rows . now , 12 × 168 = 2016 > 2006 a contradiction . so , 12 rows are sufficient . correct answer b
annotated_formula: add(divide(2006, 199), const_2)