Solutions for problems "A" in October, 2000

In this page only the sketch of the solutions are published; in some cases only the final results. To achieve the maximum score in the competition more detailed solutions needed.

A. 245. We want to make a round trip with our car. There are a few gas-stations along the road where the total amount of fuel is enough to make two round trips. Prove that there is a station from where the round trip can be completed in both directions.

Solution. The proof works by induction with respect to the number of gas-stations.

If each station contains enough fuel to reach the two neighbouring ones, the problem is trivial. So assume the there exist two neighbouring stations at the points A and B of the trip such that the gas-station at A does not contain enough fuel to reach B. Denote the amount of fuel at the two gas-stations by a and b. It can be assumed that ab, otherwise A and B can be exchanged.

Denote by C the point between A and B, which can be reached if we start from A. Now we modify the configuration of the trip and the gas-stations. Reduce the amount of fuel at A and B to 0 and b-a, respectively; moreover, decrease the length of arc AB by the distance AC. In this modified configuratioon the total amount of fuel is enough to make two round trips again, but the empty gas-station at A can be removed. Thus, by the induction, there exists a gas-station S from where the round trip is possible in both directions. We show that starting from this station, the round trips are possible in the original case as well.

Start a trip from S. While A and B are not reached, there is no difference between the original and the modified situation. Reaching A or B, there is two differences between the two configurations: first, in the original case, the next part of the trip is longer by the distance AC; second, we can take the extra amount a of fuel, which is exactly enough to pass this extra distance. Thus we can pass the arc AB. After leaving A and B we always have more fuel in the original case than in the modified configuration.

A. 246. Find all quadruples of real numbers x, y, z, w which satisfy x+y+z+w=x⁷+y⁷+z⁷+w⁷=0.

Shay Gueron, Haifa

Solution.

Lemma. If a,b are real numbers and a0, then the system X+Y=a, X⁷+Y⁷=b of equations has at most one solution (ignoring the order of variables).

Proof. Let X=a/2-Z, Y=a/2+Z. By the simmetry it can be assumed that Z0. Substituting this into the second equation,

The left hand side is strictly increasing or decreasing in Z if a>0 or a<0, respectively. Thus the equation holds for at most one Z. The lemma is complete.

Now we prove that all solutions for system (1) contain of two pairs of complement real numbers. Suppose that the sum of two of the variables is not zero, say x+y0. Let a=-(x+y) and b=-(x⁷+y⁷). The numbers z,w satisfy the system

z+w=a,    z⁷+w⁷=b.

The pair (-x,-y) is a solution for this system; by the lemma there is no more solution. Thus z=-x and w=-y, or z=-y and w=-x

If the sum of any two of x,y,z,w is 0, then x=y=z=w=0.

A. 247. Prove that there is no point on the lines determined by the sides of the unit square whose distance from each vertex of the square is rational.

Á. Kovács, Budapest

Solution. We will use several times the following two lemmas.

lemma 1. Suppose that the positivce integers A, B and C are relative prime and satisfy A²+B²=C².

a) If A is even, then there exist some relative prime positive integersP and Q such that A=2PQ, B=P²-Q² and C=P²+Q²;

b) If A is odd, then there exist some relative prime positive odd integers P and Q such that A=PQ, B=(P²-Q²)/2 and C=(P²+Q²)/2.

Proof. From the equation A²=(B+C)(B-C). In case a), the greatest common divisor of the two factor is 2; then there exist some positive integers P, Q such that B+C=2P² and B-C=2Q². This implies the statement.

In case b), the two factors are relative prime, thus they are odd squares; B+C=P² and B-C=Q² for some odd P and Q. This also imples the statement.

lemma 2. If A,B,C,D are positive integers and AB=CD, then there exist some positive integers P,Q,R,S such that A=PQ, B=RS, C=PR and D=QS. If the pairs A,B and C,D are relative prime, respectively, then P,Q,R,S are pairwise relative prime.

Proof. Let P=(A,C), Q=A/P, R=C/P and S=B/R=D/Q. (The last equation holds, because B/R=BP/C=ABP/AC=CDP/AC=DP/A=D/Q.) These numbers satisfy the equation; we only have to show that S is integral.

By the construction, Q and R are relative prime; thus Qx+Ry=1 for some integers x and y. Then S=(Qx+Ry)S=(QS)x+(RS)y=Dx+By is integral.

The second part of the lemma follows from the fact that the numbers A=PQ, B=RS, and C=PR, D=QS are relative prime, respectively.

lemma 3. if there exists a point on a line determined by a side of the unit square, then the system

(1a)    x²+y²=zw;    (1b)    z²-w²=2xy

has positive integral solution.

Proof. The point cannot be a vertex of the cube. Magnify the square and the point such that the side of the suqre and the four distances are all integers.

By Pythagoras' theorem

a²+(a+b)²=c²;    a²+b²=d².

Choose the scaling such that a and b are relative prime. By the first equation, one of a and a+b must be even, the other one is odd. This implies that b is odd. From the second condition, a is even.

By lemma 1 there exist some positive integers p,q,r,s such that p and q, r and s are relative prime, respectively, and

a=2pq,    a+b=p²-q²,    c=p²+q²

and

a=2rs,    b=r²-s²,    d=r²+s².

(We obtain the same if the point is an interior point of the edge of the square.)

Solving the equations for a,

(2)   p²-q²-r²+s²=2pq=2rs.

By lemma 2, pq=rs implies that there exist some positive integers x,y,z,w which are pairwise relative prime and satisfy p=xz, q=yw, r=xw and s=yz. Substitute these into (2):

x²z²-y²w²-x²w²+y²z²=2xyzw;

(3)   (x²+y²)(z²-w²)=2xy^.zw.

There can be at most one even number between x,y,z,w. If all of them are odd, then the left-hand side of (3) is divisible by 4, the right-hand side not; this is a contradiction. Thus, one of x,y,z,w is even. Then the right-hand side of (3) is divisible by 4; on the leftt-hand side the factor x²+y² is not divisible by 4, thus z²-w² is even. This implies that z and w are odd; so one of x and y must be the even one. The factor x²+y² is odd.

The number x²+y² is relative prime to 2xy, because it is relative prime to x and y, moreover it is odd. The number z²-w² is relative prime to zw. So, (3) can hold only if x²+y²=zw and z²-w²=2xy, in other words, the quadruple (x,y,z,w) i s a solution for the system (1a), (1b).

4. lemma. The system (1a),(1b) has no positive integer solution.

Proof. Suppose that there exist solutions, and take a solution for which the product xyzw is minimal.

If both x and y are divisible by a prime number p, then, by (1a), z or w is divisible by p as well; by (1b) this implies that both z and w is divisible by p. In this case a smaller solution can be obtained dividing all variables by p. Thus, x and y must be relative prime. In a similar way we can prove that also z and w are relative prime.

The number z²-w²=2xy is even; this is possible only if z and w are odd. Then x²+y²=zw is odd, so one of x and y is even. By the symmetry it can be assumed that x is even and y is odd.

Equation (1b) says , moreover we know that the pairs (z+w)/2, (z-w)/2 and x/2, y are relative prime. By lemma 2 there exist some positive integers k,l,m,n which are pairwise relative prime and

From this x=2km, y=ln, z=kl+mn and w=kl-mn. Substitute these quantities into (1a):

4k²m²+l²n²=k²l²-m²n²;

(4)   5k²m²=(k²-n²)(l²+m²).

On the right-hand side, the factor k²-n² is relative prime to k², and l²+m² is relative prime to m². Thus (4) can hold only in two cases:

Case 1: k²-n²=m² and l²+m²=5k²;

case 2: k²-n²=5m² and l²+m²=k².

In case 1,

(5a)    k²-n²=m²,    (5b)    l²+m²=5k².

The number y=ln is odd, n is even. From equation (5a), k is odd and m is even. By lemma 1 and (5a), there exist some odd positive integers and such that

n=    m=(²-²)/2,    k=(²+²)/2.

Substituting this to (5b),

(²+²)²+()²=l².

Again, by lemma 1 there exist some positive integers and such that

²+²=2,    =²-²,    l=²+².

TThus, the quartet (, , , ) is a solution for the system (1); but, at the same time,

This contradicts the minimality of the quartet (x,y,z,w).

In case 2,

(6a)    k²-n²=5m²,    (6b)    l²+m²=k².

Similarly to the previous case, l is odd; by equation (6b), m is even and k is odd. By lemma 1 and equation (6b), there exist some odd positive integers and such that

l=,    m=(²-²)/2,    k=(²+²)/2.

Substitute these in (6a):

(²-²)²+n²=()².

Again, by lemma 1 there exist some positive integers , such that

²-²=2,    n=²-²,    =²+².

In this case the quartet (,,,) is a solution for the system (1a),(1b), contradicting