HMMT 二月 2023 · 团队赛 · 第 5 题
HMMT February 2023 — Team Round — Problem 5
题目详情
- [40] Let S be the set of all points in the plane whose coordinates are positive integers less than or 2 equal to 100 (so S has 100 elements), and let L be the set of all lines ` such that ` passes through at least two points in S . Find, with proof, the largest integer N ≥ 2 for which it is possible to choose N distinct lines in L such that every two of the chosen lines are parallel.
解析
- [40] Let S be the set of all points in the plane whose coordinates are positive integers less than or 2 equal to 100 (so S has 100 elements), and let L be the set of all lines ` such that ` passes through at least two points in S . Find, with proof, the largest integer N ≥ 2 for which it is possible to choose N distinct lines in L such that every two of the chosen lines are parallel. Proposed by: Ankit Bisain, Brian Liu, Carl Schildkraut, Luke Robitaille, Maxim Li, William Wang Answer: 4950 p Solution: Let the lines all have slope where p and q are relatively prime. Without loss of generality, q let this slope be positive. Consider the set of points that consists of the point of S with the smallest coordinates on each individual line in the set L . Consider a point ( x, y ) in this, because there is no other point in S on this line with smaller coordinates, either x ≤ q or y ≤ p . Additionally, since each line passes through at least two points in S , we need x + q ≤ 100 and y + p ≤ 100. The shape of this set of points will then be either a rectangle from (1 , 1) to (100 − q, 100 − p ) with the rectangle from ( q + 1 , p + 1) to (100 − q, 100 − p ) removed, or if 100 − q < q + 1 or 100 − p < p + 1, just the initial rectangle. This leads us to two formulas for the number of lines, { (100 − p )(100 − q ) − (100 − 2 p )(100 − 2 q ) p, q < 50 N = (100 − p )(100 − q ) otherwise In the first case, we need to minimize the quantity (100 − p )(100 − q ) − (100 − 2 p )(100 − 2 q ) = 100( p + q ) − 3 pq ( ) ( ) 10000 100 100 = − 3 q − p − , 3 3 3 if one of p, q is above 100 / 3 and the other is below it, we would want to maximize how far these two are from 100 / 3. The case ( p, q ) = (49 , 1) will be the optimal case since all other combinations will have p, q ’s closer to 100 / 3, this gives us 4853 cases. In the second case, we need to minimize p and q while keeping at least one above 50 and them relatively prime. From here we need only check ( p, q ) = (50 , 1) since for all other cases, we can reduce either p or q to increase the count. This case gives a maximum of 4950.