Solutions for problems "B" in October, 2001

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.

B.3482.Four good friends notice that if each of them divides the number of the books he has by the sum of the digits of that number, they all get the same integer: 13. Prove that at least two of them have the same number of books. (4 points)

Proposed by: L. Gerőcs, Budapest

Solution. Consider the number of the books owned by any one of the friends. We shall show that the sum of the digits in that number is exactly 3. If it were at most 2, then with appropriate digits a,b the number could be written in the form 10a+b, where a+b is equal to the sum of the digits. Then 0<10a+b<13(a+b). Now suppose the number of the digits is n\(\displaystyle ge\)4. If a₁,a₂,...,a_n denote the digits of the number, then

10^n-1\(\displaystyle le\)10^n-1a₁+10^n-2a₂+...+a_n=13(a₁+a₂+...+a_n)\(\displaystyle le\)13^.9^.n<200n ,

10^n-3<2n follows. However, it can be proved that if n\(\displaystyle ge\)4 then 10^n-3>2n. For n=4 it is clearly true, otherwise it easily follows by induction.

The number of books is therefore 100a+10b+c, where the digits a,b,c satisfy a\(\displaystyle ge\)1 and 100a+10b+c=13(a+b+c), that is, 29a=b+4c\(\displaystyle le\)35. Hence a=1 and 20\(\displaystyle le\)4c\(\displaystyle le\)29, and thus the possible values of c are 5,6 and 7. The number of books owned by any one friend is therefore 195, 156 or 117, which means that there must be two friends with the same number of books.

B.3483.The midpoint of side AB of a rectangle ABCD is F. P is a point on the angle bisector from C. The orthogonal projection of P on the line BC is Q. Prove that if line PF is perpendicular to line DQ then AP=BC. (3 points)

Solution. Let R denote the projection of the point P onto the line AB, and let a,b, and x denote the lengths of the segments CB, BF and CQ. If the line PF is perpendicular to the line DQ then the triangle DCQ is similar to the triangle PRF. Hence CQ/CD=RF/RP, that is, x/(2b)=(b-x)/(a-x), and thus ax-x²=2b²-2bx. With a few transformations it follows that (2b-x)²+(a-x)²-a²=0. Therefore AP²=AR²+RP²=(2b-x)²+(a-x)²=a²=BC², and hence AP=BC is true. By using the above reasoning, it is easy to show that the converse of the statement is also true, on condition that P\(\displaystyle ne\)F.

B.3484. The angles of a triangle are , , . , \(\displaystyle \cot{{\beta}\over2}\), are consecutive integers. Find the largest angle of the triangle. (3 points)

Solution. Let \(\displaystyle \cot{{\beta}\over2}=A\). If \(\displaystyle 0x>0, and thus A is a positive integer.

\(\displaystyle A=\cot{{\beta}\over2}=\cot({\pi\over2}-{{\alpha}\over2}-{{\gamma}\over2})=\tan({{\alpha}\over2}+{{\gamma}\over2})={\tan{{\alpha}\over2}+\tan{{\gamma}\over2}\over1-\tan{{\alpha}\over2}\tan{{\gamma}\over2}}=\)

\(\displaystyle ={1/(A-1)+1/(A+1)\over1-1/(A^2-1)}={2A\over A^2-2}\ ,\)

and hence A²-2=2, A=2. Thus \(\displaystyle \cot{{\alpha}\over2}=1\), that is \(\displaystyle \alpha={\pi\over2}\) is the largest angle of the triangle. (Note that such a trianle really exists.)

B.3485.The elements of the set A are positive integers. If x, y\(\displaystyle in\)A, x>y then . How many elements can the set A have at most? (4 points)

Vojtech Jarnik mathematics competition, Ostrava, 2001

Solution 1. With some transformation of the condition, we can see that if x,y\(\displaystyle in\)A and x>y, then 25>25x/(x+25)\(\displaystyle ge\)y. Thus every element of the set A is less than 25, with the exception of at most one element. Therefore the set may only have a finite number of elements, let us denote those elements by . x₁>x₂>...>x_n. As we have seen, if n>1 then x₂\(\displaystyle le\)24.

If 0<a<b then 25a/(a+25)<25b/(b+25), which is easy to check by finding the common denominator. Thus the function 25x/(x+25) is strictly monotone increasing on the set of positive numbers.

using that, we can reason as follows. If n\(\displaystyle ge\)3 then 13>25^.24/49\(\displaystyle ge\)25x₂/(25+x₂)>x₃. Furthermore, if n\(\displaystyle ge\)4 then 9>25^.12/37\(\displaystyle ge\)25x₃/(25+x₃)>x₄, if n\(\displaystyle ge\)5 then 7>25^.8/33\(\displaystyle ge\)25x₄/(25+x₄)>x₅, and if even n\(\displaystyle ge\)6 holds, then 5>25^.6/31\(\displaystyle ge\)25x₅/(25+x₅)>x₆. Thus it follows for every i\(\displaystyle ge\)0 that x_6+i\(\displaystyle le\)4-i, and therefore n\(\displaystyle le\)9, and the set A may have at most 9 elements.

Finally, let us construct a set A of 9 elements that satisfies the rquirements. Basically, this is the same as the above reasoning, but reversed. Let A={x₁,x₂,...,x₉}, where x₉=1,x₈=2,x₇=3,x₆=4,x₅=6,x₄=8,x₃=12,x₂=24 and x₁=600. Let 1\(\displaystyle le\)i<j<k\(\displaystyle le\)9. If \(\displaystyle x_i-x_j\ge{x_ix_j\over25}\) then \(\displaystyle x_i-x_\)x_i-x_j\ge{x_ix_j\over25}>{x_ix_k\over25}">,thus it is enough to check whether \(\displaystyle x_i-x_{i+1}\ge{x_ix_{i+1}\over25}\) for all 1\(\displaystyle le\)i\(\displaystyle le\)8, which is always true.

Solution 2. By rearranging the condition, we get that \(\displaystyle \left|{1\over x}-{1\over y}\right|\ge{1\over25}\) for all x,y\(\displaystyle in\)A. Thus the reciprocals of the elements of the set are pairwise separated by a distance of at least 1/25. It follows that there may be the reciprocals of at most 5 elements in the interval \(\displaystyle (0,{1\over5})\), that is, there may be at most 5 elements greater than 4. Therefore, the number of elements cannot be greater than 9.

Nine elements are possible. If the elements of the set are 1, 2, 3, 4, 5, 7, 10, 17, 54, then the difference of any two reciprocals is greater than 1/25. (The solution also shows that it is enough to check for pairs of consecutive elements.)

B.3486. Given 2001 points and a circle of unit radius in the plane, prove that there exists a point on the circumference of the circle such that the sum of its distances from the given points is at least 2001. (4 points)

International Hungarian Mathematics Competition, 2001

Solution. Let A and B be the endpoints of a diameter, and let the given points be P₁,P₂,...,P₂₀₀₁. The triangle inequality states that

AP_i+BP_i\(\displaystyle ge\)AB=2,

for every i, that is,

\(\displaystyle \sum_{i=1}^{2001}AP_i+\sum_{i=1}^{2001}BP_i\geq2\cdot2001=4002.\)

It immediately follows that at least one of A and B satisfies the requirements of the problem.

B.3487. f(x) is a function defined on positive real numbers, and f(x)+2^.f(1/x)=3x+6 everywhere in the domain. Find all such functions f(x). (3 points)

Solution. Let x be an arbitrary positive number, then 1/x is also positive. Thus the functions f in the problem satisfy f(x)+2f(1/x)=3x+6 and f(1/x)+2f(x)=3/x+6. By adding these and dividing each side of the resulting equality by 3, we get f(x)+f(1/x)=x+1/x+4. If that is subtracted from the second equality, the result is f(x)=2/x-x+2. There is one single such function f , the function f that assigns f(x)=2/x-x+2 to every positive real x. This function does satisfy the requirement.

B.3488. The lengths of the sides of a rectangular billiards table ABCD are AB=150 cm and BC=205 cm. There are four holes, one in each corner. At corner A, a ball is struck in a direction enclosing an angle of 45^o with the side of the table, and it is moving away from the hole. Whenever the ball hits the edge of the table, it rebounds elastically. What will happen to the ball? (4 points)

Solution. Under ideal circumstances, the ball does not lose speed during its motion. Let us divide the sides AB and CD of the table into 150 equal parts, and the sides BC and DA into 205 equal parts. (We could as well divide the appropriate sides into 30 and 41 equal parts, but that would not be of any advantage for the solution). The path of the ball on the table is a polygon that consists of the consecutive line segments s₁,s₂,.... The direction of the motion of the ball always encloses a 45^o angle with the sides of the table. It always hits the edge of the table at one of the points of division (including the corners), since if the starting point of a segment s_i of the path is a point of division then so is the endpoint.

First let us show that the ball cannot hit any point of division twice from the same direction.

assume that s_i=s_j (i<j) and the ball travels along them in the same direction then the same is true for the segments, s_i-1 and s_j-1, too. It follows by induction that the starting point of the line segment s_j-i+1 coincides with the starting point of s₁, which means that having covered the segment s_j-i the ball should have fallen into the hole at vertex A.

The ball cannot hit any point of division more than twice, and thus its path must consist of a finite number of segments. Sooner or later it must disappear in a hole. The question is: whitch hole?

Assume that it disappears at the hole at vertex A after covering the segment s_n. Then by reversing its path we can see that s_n=s₁ and these two segments are covered in opposite directions. The same is true for the segments s_n-1 and s₂, and so on. There are n such pairs, and the middle two segments must coincide, which is impossible.

Let us show that the ball cannot disappear at vertex D either. Then the path of the ball would be symmetrical in the symmetry axis parallel to the side AB of the table. That could only be possible if the number of segments were even and the common point of the middle two segments lay on the axis, that is, it should be the midpoint of either AD or BC. That point, however, is not a point of division, since 205 is an odd number.

Finally, let us show that the ball cannot disappear at vertex C either. Then the path of the ball would be symmetrical about the centre of the table. That is only possible if the number of segments is odd, and the middle segment passes through the centre. However, the lines passing through the centre and enclosing a 45^o angle with the sides do not intersect the sides BC and DA at points of division but at a distance of 27,5 cm from the vertices The ball will inevitably disappear in the hole at vertex B.

B.3489. Prove that . (5 points)

Solution. The identity

\(\displaystyle (a+b)^n+(a-b)^n=2\sum_{0\le i\le n/2}{n\choose2i}b^{2i}a^{n-2i}\ .\)

follows from the binomial theorem. With the help of this identity, the sum in the problem can be written in the form

\(\displaystyle \sum_{i=0}^n{2n\choose2i}3^i={1\over2}((1+\sqrt{3})^{2n}+(1-\sqrt{3})^{2n})={1\over2}((4+2\sqrt{3})^n+(4-2\sqrt{3})^n)=\)

\(\displaystyle =2^{n-1}((2+\sqrt{3})^n+(2-\sqrt{3})^n)=2^n\sum_{0\le i\le n/2}{n\choose2i}3^{i}2^{n-2i}\,\)

which immediately leads to the statement of the problem.

B.3490. The benches of the Great Hall of the Parliament of Neverenough are arranged in a rectangle of 10 rows of 10 seats each. All the 100 MPs have different salaries. Each of them asks all his neighbours (sitting next to, in front of, or behind him, as well as those four seated diagonally in front of or behind him, i.e. 8 members at most) how much they earn. They feel a lot of envy towards each other: an MP is content with his salary only if he has at most one neighbour who earns more than himself. What is the maximum possible number of MPs who are satisfied with their salaries? (4 points)

Kvant

Solution. Represent the assembly hall of the parliament by a 10 by 10 table. It is easy to see that at most two out of the four MP's seated in any 2 by 2 square may be satisfied with their salaries. Since the 10 by 10 table can be divided into 25 2x2 squares, in each of which there may be at most two satisfied MP's, there may be at most 50 such members of the whole parliament.

We cannot state more than that. If the MP's seated in the even-numbered rows all have lower salaries than those in the odd-numbered rows, and within each odd-numbered row the salaries decrease left to right, then there will be exactly 50 satisfied MP's.

B.3491. Is the following statement true or false? ``Given n red points in the space, it is always possible to place 3n blue points in the space such that there is at least one blue point in the interior of each tetrahedron determined by the red points.'' (5 points)

from the idea of Z. Füredi

Solution. The statement is not true. Consider the following construction.. Let e and f be skew lines, and let E₁,E₂,...,E_k and F₁,F₂,...,F_k be points lying on the lines e and f, respectively, in the given order.

It is easy to show that for 1\(\displaystyle le\)i,j\(\displaystyle le\)k-1 no two of the tetrahedra E_iE_i+1F_jF_j+1 have a common interior point. Assume, that E_iE_i+1F_jF_j+1 and E_i'E_i'+1F_j'F_j'+1 are two such tetrahedra. For simplicity, let i\(\displaystyle ne\)i', say, i<i'. then the plane passing through the point E_i+1 and the line f separate the vertices of the two tetrahedra. (It is allowed that some vertices lie on the plane itself.) The plane definitely separates their interior points. Now if n=2k\(\displaystyle ge\)16 and the above n points are considered red then it follows from k²-8k+1=(k-4)²-15>0 that 3n=6k<(k-1)², and thus however we mark 3n points blue, there must be at least one among the (k-1)² tetrahedra of red vertices mentioned above that contains no blue points in its interior.