Olympiad Maths Prep

Library / /8 of 14

Number theory Difficulty 8.7 Shortlist Prove it IMO

In the coordinate plane consider the set SS of all points with integer coordinates. For a positive integer kk, two distinct points A,BSA, B \in S will be called kk-friends if there is a point CSC \in S such that the area of the triangle ABCA B C is equal to kk. A set TST \subset S will be called a kk-clique if every two points in TT are kk-friends. Find the least positive integer kk for which there exists a kk-clique with more than 200 elements.

Solution

To begin, let us describe those points BSB \in S which are kk-friends of the point (0,0)(0,0). By definition, B=(u,v)B=(u, v) satisfies this condition if and only if there is a point C=(x,y)SC=(x, y) \in S such that 12uyvx=k\frac{1}{2}|u y-v x|=k. (This is a well-known formula expressing the area of triangle ABCA B C when AA is the origin.)

To say that there exist integers x,yx, y for which uyvx=2k|u y-v x|=2 k, is equivalent to saying that the greatest common divisor of uu and vv is also a divisor of 2k2 k. Summing up, a point B=(u,v)SB=(u, v) \in S is a kk-friend of (0,0)(0,0) if and only if gcd(u,v)\operatorname{gcd}(u, v) divides 2k2 k.

Translation by a vector with integer coordinates does not affect kk-friendship; if two points are kk-friends, so are their translates. It follows that two points A,BSA, B \in S, A=(s,t)A=(s, t), B=(u,v)B=(u, v), are kk-friends if and only if the point (us,vt)(u-s, v-t) is a kk-friend of (0,0)(0,0); i.e., if gcd(us,vt)2k\operatorname{gcd}(u-s, v-t) \mid 2 k.

Let nn be a positive integer which does not divide 2k2 k. We claim that a kk-clique cannot have more than n2n^{2} elements.

Indeed, all points (x,y)S(x, y) \in S can be divided into n2n^{2} classes determined by the remainders that xx and yy leave in division by nn. If a set TT has more than n2n^{2} elements, some two points A,BTA, B \in T, A=(s,t)A=(s, t), B=(u,v)B=(u, v), necessarily fall into the same class. This means that nusn \mid u-s and nvtn \mid v-t. Hence ndn \mid d where d=gcd(us,vt)d=\operatorname{gcd}(u-s, v-t). And since nn does not divide 2k2 k, also dd does not divide 2k2 k. Thus AA and BB are not kk-friends and the set TT is not a kk-clique.

Now let M(k)M(k) be the least positive integer which does not divide 2k2 k. Write M(k)=mM(k)=m for the moment and consider the set TT of all points (x,y)(x, y) with 0x,y<m0 \leq x, y < m. There are m2m^{2} of them. If A=(s,t)A=(s, t), B=(u,v)B=(u, v) are two distinct points in TT then both differences us,vt|u-s|,|v-t| are integers less than mm and at least one of them is positive. By the definition of mm, every positive integer less than mm divides 2k2 k. Therefore usu-s (if nonzero) divides 2k2 k, and the same is true of vtv-t. So 2k2 k is divisible by gcd(us,vt)\operatorname{gcd}(u-s, v-t), meaning that A,BA, B are kk-friends. Thus TT is a kk-clique.

It follows that the maximum size of a kk-clique is M(k)2M(k)^{2}, with M(k)M(k) defined as above. We are looking for the minimum kk such that M(k)2>200M(k)^{2}>200.

By the definition of M(k)M(k), 2k2 k is divisible by the numbers 1,2,,M(k)11,2, \ldots, M(k)-1, but not by M(k)M(k) itself. If M(k)2>200M(k)^{2}>200 then M(k)15M(k) \geq 15. Trying to hit M(k)=15M(k)=15 we get a contradiction immediately (2k2 k would have to be divisible by 33 and 55, but not by 1515).

So let us try M(k)=16M(k)=16. Then 2k2 k is divisible by the numbers 1,2,,151,2, \ldots, 15, hence also by their least common multiple LL, but not by 1616. And since LL is not a multiple of 1616, we infer that k=L/2k=L / 2 is the least kk with M(k)=16M(k)=16.

Finally, observe that if M(k)17M(k) \geq 17 then 2k2 k must be divisible by the least common multiple of 1,2,,161,2, \ldots, 16, which is equal to 2L2 L. Then 2k2L2 k \geq 2 L, yielding k>L/2k>L / 2.

In conclusion, the least kk with the required property is equal to L/2=180180L / 2=180180.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.