HMMT 十一月 2011 · GEN 赛 · 第 6 题
HMMT November 2011 — GEN Round — Problem 6
题目详情
- [ 5 ] Five people of heights 65, 66, 67, 68, and 69 inches stand facing forwards in a line. How many orders are there for them to line up, if no person can stand immediately before or after someone who is exactly 1 inch taller or exactly 1 inch shorter than himself?
解析
- [ 5 ] Five people of heights 65, 66, 67, 68, and 69 inches stand facing forwards in a line. How many orders are there for them to line up, if no person can stand immediately before or after someone who is exactly 1 inch taller or exactly 1 inch shorter than himself? Answer: 14 Let the people be A, B, C, D, E so that their heights are in that order, with A the tallest and E the shortest. We will do casework based on the position of C . • Case 1: C is in the middle. Then, B must be on one of the two ends, for two choices. This leaves only one choice for D –the other end. Then, we know the positions of A and E since A cannot neighbor B and E cannot neighbor D . So we have 2 options for this case. General Test • Case 2: C is in the second or fourth spot. Then, we have two choices for the position of C . Without loss of generality, let C be in the second spot. Then, the first and third spots must be A and E , giving us two options. This fixes the positions of B and D , so we have a total of 2 × 2 = 4 options for this case. • Case 3: C is in the first or last spot. Then, we have two choices for the position of C . Without loss of generality, let it be in the first spot. Either A or E is in the second spot, giving us two choices. Without loss of generality, let it be A . Then, if D is in the third spot, the positions of B and E are fixed. If E is in third spot, the positions of B and D are fixed, so we have a total of 2 × 2 × (1 + 1) = 8 options for this case. Hence, we have a total of 2 + 4 + 8 = 14 possibilities.