Maths Olympiad Prep

Library / /108 of 144

Combinatorics Difficulty 8.6 Shortlist Find the answer

In the coordinate plane consider the set S S of all points with integer coordinates. For a positive integer k k, two distinct points AA, BS B\in S will be called k k-*friends* if there is a point CS C\in S such that the area of the triangle ABC ABC is equal to k k. A set TS T\subset S will be called k k-*clique* if every two points in T T are k k-friends. Find the least positive integer k k for which there exits a k k-clique with more than 200 elements.

*

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

To solve this problem, we need to find the least positive integer k k such that there exists a set TS T \subset S with more than 200 points where every pair of points in T T are k k -friends. This entails ensuring that for each pair of points A,BT A, B \in T , there exists a point CS C \in S such that the area of the triangle ABC \triangle ABC equals k k .

Let's proceed with the solution step by step:

1. Understanding the Geometry:
- The area of a triangle ABC \triangle ABC formed by points A(x1,y1),B(x2,y2),C(x3,y3) A(x_1, y_1), B(x_2, y_2), C(x_3, y_3) is given by:
Area(ABC)=12x1(y2y3)+x2(y3y1)+x3(y1y2) \text{Area}(\triangle ABC) = \frac{1}{2} \left| x_1(y_2-y_3) + x_2(y_3-y_1) + x_3(y_1-y_2) \right|
For the area to be k k , we require:
x1(y2y3)+x2(y3y1)+x3(y1y2)=2k \left| x_1(y_2-y_3) + x_2(y_3-y_1) + x_3(y_1-y_2) \right| = 2k

2. **Required Condition for k k -friendship**:
- We want every pair of points A A and B B in the set T T to be k k -friends. This means for any two points, say (xi,yi) (x_i, y_i) and (xj,yj) (x_j, y_j) , there should exist a point (xk,yk) (x_k, y_k) such that the area of ABC=k \triangle ABC = k .

3. Ensuring Integer Area Values:
- The condition derived implies the determinant-like calculation must result in an integer. Hence, 2k 2k should be a multiple of any determinant formed from integer coordinates.
- For any significant number of (xi,yi) (x_i, y_i) , the periodicity in area values can be ensured by the greatest common divisor (GCD) of these values being 1.

4. Using the Least Common Multiple (LCM):
- To ensure that every possible outcome for yiyj y_i - y_j results edges to 2k 2k , we work with periods of such pairs.
- The smallest k k that works should assure divisibility by each possible edge, i.e., k k is a scalar multiple of the LCM of numbers up to a certain value dictated by the choice of over 200 elements.
- To sustain a large set, the determinant variations should be multiples of a common base scale horizon. This is physically by a required subgroup of grid coordinate segments. The complete LCM of the numbers from 1 to 14 provides such combinatorial grid guarantee up to 14 14 .

5. **Calculating k k **:
-
- Therefore, the minimum k k can be computed as:
k=12lcm(1,2,,14) k = \frac{1}{2} \operatorname{lcm}(1, 2, \dots, 14)
- Calculating this gives:
lcm(1,2,,14)=360360 \operatorname{lcm}(1, 2, \dots, 14) = 360360
- Thus,
k=12×360360=180180 k = \frac{1}{2} \times 360360 = 180180

So, the least positive integer k k for which there exists a k k -clique with more than 200 elements is:
180180 \boxed{180180}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.