HMMT 二月 2011 · COMBGEO 赛 · 第 1 题
HMMT February 2011 — COMBGEO Round — Problem 1
题目详情
- A classroom has 30 students and 30 desks arranged in 5 rows of 6. If the class has 15 boys and 15 girls, in how many ways can the students be placed in the chairs such that no boy is sitting in front of, behind, or next to another boy, and no girl is sitting in front of, behind, or next to another girl?
解析
- Determine the smallest value of x for which every distortion of H is necessarily convex. Answer: 4 ′ A A X X 1 6 A A 2 5 ′ A A Y 3 Y 4 ′ Let H = A A A A A A be the hexagon, and for all 1 ≤ i ≤ 6, let points A be considered such that 1 2 3 4 5 6 i ′ ′ ′ ′ ′ ′ ′ ′ A A < 1. Let H = A A A A A A , and consider all indices modulo 6. For any point P in the plane, i i 1 2 3 4 5 6 ′ let D ( P ) denote the unit disk { Q | P Q < 1 } centered at P ; it follows that A ∈ D ( A ). i i ′ ′ Let X and X be points on line A A , and let Y and Y be points on line A A such that A X = 1 6 3 4 1 ′ ′ ′ ′ A X = A Y = A Y = 1 and X and X lie on opposite sides of A and Y and Y lie on opposite sides 1 3 3 1 ′ ′ ′ ′ of A . If X and Y lie on segments A A and A A , respectively, then segment A A lies between the 3 1 6 3 4 1 3 x ′ ′ lines XY and X Y . Note that is the distance from A to A A . 2 1 3 2 Combinatorics & Geometry Individual Test ′ A A X 1 X 6 A A 2 5 ′ A A Y 3 Y 4 x If ≥ 2, then C ( A ) cannot intersect line XY , since the distance from XY to A A is 1 and the 2 1 3 2 ′ ′ ′ distance from XY to A is at least 1. Therefore, A A separates A from the other 3 vertices of the 2 1 3 2 ′ hexagon. By analogous reasoning applied to the other vertices, we may conclude that H is convex. x ′ ′ If < 2, then C ( A ) intersects XY , so by choosing A = X and A = Y , we see that we may choose 2 1 3 2 ′ ′ A on the opposite side of XY , in which case H will be concave. Hence the answer is 4, as desired. 2