Solutions for advanced problems "A" in October, 2002

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. 299. P and Q are interior points of the square ABCD such that PAQ\(\displaystyle \angle\)= PCQ\(\displaystyle \angle\)= 45^o. Determine the length PQ in terms of the lengths BP and DQ.

Solution. Let BP=p, DQ=q and PQ=x. x needs to be expressed in terms of the lengths p and q.

One of the points P and Q lies in the interior of the triangle ABC, and the other in the interior of the triangle ACD. Thus there are two cases:

1. If P lies inside triangle ABC and Q lies inside triangle ACD then the orientations of both triangle APQ and triangle CQP are the same as that of the square ABCD.

Reflect the point B in the lines AP and CP; let the reflections be U and V, respectively. It follows from the reflection that AU=AB=AD, and by adding up the angles at vertex A we have QAU\(\displaystyle \angle\)=DAQ\(\displaystyle \angle\). Hence the triangles AQU and AQD are congruent. Analogously, the triangles CQV and CQD are also congruent.

It follows from the conruences that the angles marked with the same colour in the Figure are equal, PU=PV=PB=p and QU=QV=QD=q. The triangles PQU and PQV are congruent because they have pairwise equal sides. Thus their angles at U and V are equal. the sum of these two angles equals the sum of the angles of the square ABCD at B and D, therefore PUQ\(\displaystyle \angle\)=PVQ\(\displaystyle \angle\)=90^o. Hence with the Pythagorean theorem

\(\displaystyle x=\sqrt{p^2+q^2}.\)

It also follows from the reasoning that the angles marked blue and yellow are equal, so are the angles marked red and green, and the line segment BP is parallel to QD.

2. If Q lies iside the triangle ABC and P inside the triangle ACD then the triangles APQ and CQP both have the orientation opposite to that of the square ABCD. In that case, the solution is more complicated (and so is the result).

As seen above, the quadrilateral QBPD is a trapezium, its bases are QB and PD, and PQ²=BQ²+DP². It also follows from the arrangement of the points that BP>DP and BQ<DQ.

We will first show that for every trapezium of this kind, there are suitable points A and C, such that ABCD is a square and PAQ\(\displaystyle \angle\)=PCQ\(\displaystyle \angle\)=45^o.

Let therefore QBPD be a trapezium in which PQ²=BQ²+DP². Let U and V be the two points with QU=QV=BQ and PU=PV=DP; let U lie on the same side of the diagonal PQ as the point B, and let V lie on the same side as the vertex D. The converse of the Pythagorean theorem implies that PUQ\(\displaystyle \angle\)=PVQ\(\displaystyle \angle\)=90^o.

Let A be the intersection of the bisectors of the angles BQU and DPU, and let C be the intersection of the bisectors of the angles BQV and DPV.

The line segments AB, AU and AD are equal in length since they are symmetrical about the lines AQ and AP. Similarly, CB=CV=CD because these three line segments are symmetrical about the lines CQ and CP. By adding up the angles of the hexagons ABQUPD and CDPVQB we have PAQ\(\displaystyle \angle\)=PCQ\(\displaystyle \angle\)=45^o and PAD\(\displaystyle \angle\)=BCD\(\displaystyle \angle\)=90^o. Hence the quadrilateral ABCDis a square.

It follows from the conditions BP>DP and BQ<DQ that the points U and V lie between the arms of the angles PQB and QPD, respectively. The points A and B as well as the points C and D lie on opposite sides of the line PQ, and the square ABCD really contains the line segment PQ in its interior.

Let a denote the side length of the square-val, and let BQ=y, QD=z. We are going to express x in terms of the lengths of the line segments a, p, q. The arrangement of the points shows that \(\displaystyle {1\over\sqrt2}a

As seen above, x²=y²+z². The line segment BD is the diagonal of the square, thus \(\displaystyle BD=\sqrt2a\).

Consider the trapezium QBPD. Let QBP\(\displaystyle \angle\)=\(\displaystyle \beta\) and PDQ\(\displaystyle \angle\)=\(\displaystyle \delta\). Apply the cosine rule to the triangles QBP, BPD, PDQ and DQB:

x²=p²+y²-2pycos \(\displaystyle \beta\)

2a²=p²+z²+2pzcos \(\displaystyle \beta\)

x²=q²+z²-2qzcos \(\displaystyle \delta\)

2a²=q²+y²+2qycos \(\displaystyle \delta\)

By eliminating the cosines, we have

Divide the sum of the equations (1) and (2) by (y+z):

x²+2a²=p²+q²+2yz,

and hence

(y-z)²=x²-2yz=p²+q²-2a²

and

(y+z)²=x²+2yz=2x²+2a²-p²-q².

Square the difference of the equations (1) and (2):

(2a²-x²)²(y-z)²=(p²-q²)²(y+z)²

(2a²-x²)²(p²+q²-2a²)=(p²-q²)²(2x²+2a²-p²-q²)

The number 2a²-x² can be calculated from this equation (quadratic at most). The leading coefficient is non-negative: p²+q²-2a²=(y-z)²\(\displaystyle \ge\)0.

If the leading coefficient is 0, that is p²+q²-2a²=(y-z)²=0, then y=z, the quadrilateral QBPD is a parallelogram, and p=q=a. It is easy to see that if P and Q lie on the circles of radius a centred at B and D, respectively, symmetrically about the centre of the square then PAQ\(\displaystyle \angle\)=PCQ\(\displaystyle \angle\)=45^o will be true. In that case all we know about the length of the line segment PQ is that it lies in the interval \(\displaystyle [(2-\sqrt2)a,\sqrt2a)\).

If the leading coefficient is positive then the quadratic formula can be applied to the equation (3). Since the constant term is negative, the equation has one positive and one negative root.We also know that \(\displaystyle x<\sqrt2a\), that is, 2a²-x²>0, thus we need the positive root:

\(\displaystyle 2a^2-x^2={-(p^2-q^2)^2+\sqrt{(p^2-q^2)^4+ (p^2+q^2-2a^2)(p^2-q^2)^2(6a^2-p^2-q^2)}\over p^2+q^2-2a^2}=\)

\(\displaystyle ={-(p^2-q^2)^2+2|p^2-q^2|\sqrt{-3a^4+2a^2(p^2+q^2)-p^2q^2} \over p^2+q^2-2a^2},\)

\(\displaystyle x=\sqrt{2a^2+{(p^2-q^2)^2-2|p^2-q^2|\sqrt{-3a^4+2a^2(p^2+q^2)-p^2q^2} \over p^2+q^2-2a^2}}.\)

A. 300. Find all pairs (a, b) such that a and b are whole numbers and a² + ab + b²is a multiple of 7⁵.

Solution. Consider the following identities:

It follows that a²+ab+b² is only divisible by 7⁵ if any of the following conditions holds:

- a and b are both divisible by 7³;

- a=7²p, b=7²q, where p\(\displaystyle \equiv\)2q (mod 7) or q\(\displaystyle \equiv\)2p (mod 7);

- a=7p, b=7q, where p\(\displaystyle \equiv\)18q (mod 7³) or q\(\displaystyle \equiv\)18p (mod 7³);

- a\(\displaystyle \equiv\)1353b (mod 7⁵) or b\(\displaystyle \equiv\)1353a (mod 7⁵).

A. 301. Let a₀,a₁,... a sequence of non negative numbers such that for every k, m \(\displaystyle \ge\)0, a_k+m \(\displaystyle \le\)a_k+m+1 + a_k a_m. Assume, additionally, that na_n < 0.2499 holds for sufficiently large n. Prove that there exists a number q for which 0<q<1 and a_n<qⁿ if n is large enough.

Solution. Let p=0,2499 and let \(\displaystyle 1n₀ such that if n\(\displaystyle \ge\)n₀ then na_n<p. If n₀ is chosen to be large enough, it is also true that \(\displaystyle {n\over n-2}

For every N\(\displaystyle \ge\)n₀ let \(\displaystyle S(N)=\sup\{na_n:~n\ge k\}\). With the choice of n₀, for example, S(n₀)\(\displaystyle \le\)p.

If N\(\displaystyle \ge\)n₀ and n\(\displaystyle \ge\)2N, then

\(\displaystyle na_n=n\sum_{k=n}^\infty(a_k-a_{k+1})\le n\sum_{k=n}^\infty a_{[k/2]}a_{[(k+1)/2]}\le n\sum_{k=n}^\infty{S(N)\over\big[{k\over2}\big]} \cdot{S(N)\over\big[{k+1\over2}\big]}<\)

\(\displaystyle

This is true for all n\(\displaystyle \ge\)2N, therefore

\(\displaystyle S(2N)=\sup\{na_n:~n\ge2N\}\le4rS^2(N),\)

that is, 4rS(2N)\(\displaystyle \le\)(4rS(N))². By repeated application of the above, we get

\(\displaystyle S(2^mN)\le{1\over4r}\big(4rS(N)\big)^{2^m}< \big(4rS(N)\big)^{2^m}.\)

Now let n>n₀ be an arbitrary positive integer. Let m be a non-negative integer, such that 2^mn₀\(\displaystyle \le\)n<2^m+1n₀ should be true. Then

\(\displaystyle a_n\le{1\over n}S(2^mn_0)< {1\over n}\big(4rS(n_0)\big)^{2^m}< \big(4pr\big)^{2^m}< \big(4pr\big)^{n/2n_0} \le\left(\root{2n_0}\of{4pr}\right)^n.\)

Since the number r was chosen to make 4pr<1 true, the number \(\displaystyle q=\root{2n_0}\of{4pr}\) satisfies the requirement of the problem..