IMO 1976 SL 5

Origin: NET

Problem

Let a set of p equations be given, a11x1 + \cdot \cdot \cdot + a1qxq = 0, a21x1 + \cdot \cdot \cdot + a2qxq = 0, ... ap1x1 + \cdot \cdot \cdot + apqxq = 0, with coefficients aij satisfying aij = −1, 0, or +1 for all i = 1, . . . , p and j = 1, . . . , q. Prove that if q = 2p, there exists a solution x1, . . . , xq of this system such that all xj (j = 1, . . . , q) are integers satisfying |xj| \leqq and xj ̸= 0 for at least one value of j.

Solution

Thus the perimeter attains its minimum for AB = CD = 4.

(c) Let us assume w.l.o.g. that CD \leqAB. Then C lies inside \triangleBDA′ and hence BC + AD = BC + CA′ < BD + DA′. The maximal value BD + DA′ of BC + AD is attained when C approaches D, making a degenerate quadrangle. 4. The first few values are easily verified to be 2rn + 2−rn, where r0 = 0, r1 = r2 = 1, r3 = 3, r4 = 5, r5 = 11, . . . . Let us put un = 2rn + 2−rn (we will show that rn exists and is integer for each n). A simple calculation gives us un(u2 n−1 −2) = 2rn+2rn−1 +2−rn−2rn−1 +2rn−2rn−1 +2−rn+2rn−1. If an array qn, with q0 = 0 and q1 = 1, is set so as to satisfy the linear recurrence qn+1 = qn +2qn−1, then it also satisfies qn −2qn−1 = −(qn−1 − 2qn−2) = \cdot \cdot \cdot = (−1)n−1(q1 −2q0) = (−1)n−1. Assuming inductively up to n ri = qi, the expression for un(u2 n−1 −2) = un+1 + u1 reduces to 2qn+1 + 2−qn+1 + u1. Therefore, rn+1 = qn+1. The solution to this linear recurrence with r0 = 0, r1 = 1 is rn = qn = 2n−(−1)n , and since [un] = 2rn for n \geq0, the result follows. Remark. One could simply guess that un = 2rn +2−rn for rn = 2n−(−1)n , and then prove this result by induction. 5. If one substitutes an integer q-tuple (x1, . . . , xq) satisfying |xi| \leqp for all i in an equation of the given system, the absolute value of the right-hand member never exceeds pq. So for the right-hand member of the system there are (2pq + 1)p possibilities There are (2p + 1)q possible q-tuples (x1, . . . , xq). Since (2p + 1)q \geq(2pq + 1)p, there are at least two q-tuples (y1, . . . , yq) and (z1, . . . , zq) giving the same right-hand members in the given system. The difference (x1, . . . , xq) = (y1 −z1, . . . , yq −zq) thus satisfies all the requirements of the problem.