28. C5 (FRA) Let be three positive integers with . Let be an -tuple of integers satisfying the following conditions: (i) . (ii) For each with , either or . Show that there exists a pair of distinct indices with such that .
Solution
28. Note that w.l.o.g., we can assume that and are coprime. Indeed, otherwise it suffices to consider the problem in which all 's and are divided by . Let be the number of indices with and the number of those with (0 \leq i < n). We have , , and thus , , and . Consider the sequence , . We claim that at least one of the 's equals zero. We begin by noting that each is of the form , where ; therefore is always divisible by . Moreover, is 0 or . We conclude that if no is 0 then all 's are of the same sign. But this is in contradiction with the relation . Consequently some is zero, as claimed.
Second solution. As before we assume . Let us define a sequence of points in inductively as follows. Set and define as if and otherwise. The points form a trajectory in continuously moving upwards and rightwards by steps of length 1. Clearly, for all . Since , it follows that , . Since , it follows that . We observe that if and only if . We shall show that such with and must exist. If meets in an interior point, then our statement trivially holds. From now on we assume the opposite. Let be the rectangle with sides parallel to the coordinate axes and with vertices at and . Let be the part of the trajectory lying inside . We may assume w.l.o.g. that the endpoints of lie on the vertical sides of . Then there obviously exists such that the endpoints of lie on the horizontal sides of . Consider the translate of for the vector . The endpoints of lie on the vertical sides of . Hence and have some point in common. The translate of point for the vector belongs to and satisfies .