Solutions for problems "B" in March, 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.

B.3532.A bug is crawling about on a sheet of squared paper. In every step, it can move two units to the right, four units to the left, three units up, or five units down the page. During its walk, it makes a turn of exactly 90^o after each step. Which are the fields that the bug can visit in this way? (3 points)

Solution. The walk of the bug with the given conditions can be represented on an infinite square lattice. Let us set up a coordinate system with its origin at the bug's initial position and its axes parallel to the horizontal and vertical lines forming the lattice. With each move of the bug (left, right, up or down), the first coordinate of its position changes by an even number. Thus the bug can only reach lattice points with even abscissas. We shall prove that the bug can reach all such points.

Define allowed walks as the walks starting with a horizontal move and terminating with a vertical move. Such walks can be linked to form longer walks by making the endpoint of one walk the starting point of the next. With the right-and-up walk, the position of the bug changes by the vector (2,3), and with n such walks the bug arrives at the point (2n,3n). The right-up-left-down walk changes the bug's position by the vector (-2,-2), and n such walks take the bug to the point (-2n,-2n). Thus for every even number N, there is an allowed walk that terminates at a point of abscissa N.

All there remains to prove is that if the bug has arrived at a particular vertical lattice line with an allowed walk then it can continue its walk to reach any lattice point on that line. It is clear that this only requires the existence of allowed walks that move the bug with each of the vectors (0,1) and (0,-1). The former is achieved by the walk right-up-right-up- left-down, and the latter by one right-up-right-down-left-down walk corresponding to the vector (0,-7), followed by six of the walk corresponding to (0,1).

B.3533.Ann wrote 32 integers on a large sheet of paper, and covered each number with a card. Then he told Bob that if he chose 7 cards, she would tell him whether the sum of the 7 covered numbers is odd or even. At least how many times did Bob have to choose 7 cards in order to find out if the sum of all 32 numbers on the sheet was odd or even? (4 points)

Solution. First we shall prove that 6 questions are enough. Note that the sum of a few integers is even if and only if the sum of their remainders is even when they are divided by 2. Let Bob choose the 7 cards that cover the first 7 numbers, the 7 cards that cover the second 7 numbers, the 7 cards that cover the third 7 numbers, the 7 cards that cover the fourth 7 numbers, the cards covering the first 5 numbers and the 29th and 30th numbers, and finally, those covering the first 5 numbers and the 31st and 32nd numbers. If the sum s_i of the numbers under any set of 7 cards is even, let him write down a 0, and if it is odd, let him write down a 1. If the sum of the 6 numbers written down is even then the sum of the 32 numbers is also even, otherwise it is odd, since the sum of the numbers s_i equals the number obtained by adding the double of the sum of the first 5 numbers to the sum of all the 32 numbers. Thus the sum of the 32 numbers is even if and only if the sum of the numbers s_i is even. According to the above, this will occur if and only if the sum of the 6 numbers written down by Bob is even.

Now we shall show that 5 or fewer questions are not enough. 4 or less is obviously not enough, since in that case there would be numbers that are not chosen by Bob at all. If any of those numbers were changed by 1, the answers would remain the same although the parity of the sum of the 32 numbers would change. For the same reason, 5 question could only prove to be enough if the five sets of 7 chosen cards covered all the numbers together. In that case there are the following possibilities: (a) one card appeared in 4 questions and every other card in exactly one question; (b) one card appeared 3 times and another appeared twice; (c) three cards appeared in 2 questions each. In the cases (b) and (c), let A be a number (i.e. the card over it) that appeared in exactly 2 questions, and consider another number in each of those two questions that only appeared once in Bob's questions. Let those numbers be B and C. Suppose that the numbers A,B,C are replaced by A+1,B-1,C-1, respectively, with all other numbers unchanged. Then the sum of the 32 numbers is reduced by 1, and thus the parity of the sum has changed. The answer given by Ann to all 5 questions by B, however, would stay the same. Therefore, these 5 questions are not enough for finding out whether the sum of the numbers is even or odd. In the case (a), let A be the number that occurred 4 times, and let each of B,C,D,E denote a number that occurred next to A in those 4 questions. Now suppose that the numbers A,B,C,D,E are replaced by A+1,B-1,C-1,D-1,E-1, leaving all other numbers unchanged. The sum of the 32 numbers is reduced by 3, which changes its parity, while Ann's answers all remain the same. Therefore, these 5 questions are also insufficient for finding out whether the sum of the numbers is odd or even.

First we shall prove that 6 questions are enough. Note that the sum of a few integers is even if and only if the sum of their remainders is even when they are divided by 2. Let Bob choose the 7 cards that cover the first 7 numbers, the 7 cards that cover the second 7 numbers, the 7 cards that cover the third 7 numbers, the 7 cards that cover the fourth 7 numbers, the cards covering the first 5 numbers and the 29th and 30th numbers, and finally, those covering the first 5 numbers and the 31st and 32nd numbers. If the sum s_i of the numbers under any set of 7 cards is even, let him write down a 0, and if it is odd, let him write down a 1. If the sum of the 6 numbers written down is even then the sum of the 32 numbers is also even, otherwise it is odd, since the sum of the numbers s_i equals the number obtained by adding the double of the sum of the first 5 numbers to the sum of all the 32 numbers. Thus the sum of the 32 numbers is even if and only if the sum of the numbers s_i is even. According to the above, this will occur if and only if the sum of the 6 numbers written down by Bob is even.

B.3534. Charging at the opponent's goal, a soccer player has run along a polygonal line not intersecting more than once any straight line parallel to a side of the soccer field. Show that the soccer player cannot have run more than the sum of the two sides of the field. (3 points)

Solution. Let us set up a coordinate frame with its origin at the starting point P₀ of the path of the forward, and its axes parallel to the sides of the field. Let the axes be directed so that the path of the forward falls in the 1st quadrant. If the path of the forward is the polygon P₀P₁...P_n, let the coordinates of the point P_i be x_i and y_i. According to the given condition, 0=x₀$\displaystyle le$x₁$\displaystyle le$...$\displaystyle le$x_n$\displaystyle le$a and 0=y₀$\displaystyle le$x₁$\displaystyle le$...$\displaystyle le$y_n$\displaystyle le$b, where a and b are the lengths of the sides of the field. It follows from the triangle inequality that d_i$\displaystyle le$(x_i+1-x_i)+(y_i+1-y_i), where d_i is the length of the line segment P_iP_i+1. The equality occurs if and only if x_i+1=x_i or y_i+1=y_i. The length of the forward's path is $\displaystyle \sum_{i=0}^{n-1}d_i\le\sum_{i=0}^{n-1}\Bigl((x_{i+1}-x_i)+(y_{i+1}-y_i)\Bigr)=\sum_{i=0}^{n-1}(x_{i+1}-x_i)+\sum_{i=0}^{n-1}(y_{i+1}-y_i)=x_n+y_n\le a+b\ ,$ as stated. The solution also shows that equality can occur if and only if the forward starts at one corner of the field, his path terminates at the opposite corner, and he always runs parallel to one of the sides of the field.

B.3535. Let U, V, W be points on the lines containing the sides BC, CA and AB of a triangle ABC, respectively. Prove that the perpendiculars drawn to the sides at U, V, and W are concurrent if and only if

AW²+BU²+CV²=AV²+CU²+BW².

(3 points)

Solution. Let us first investigate the case when the three lines all intersect at the point P, and let us introduce the quantity s=UP²+VP²+WP². According to the Pythagorean theorem, AW²+BU²+CV²+s=AP²+BP²+CP²=AV²+CU²+BW²+s, and the stated equality follows immediately.

Now assume that the three lines are not concurrent. Let Q denote the intersection of the perpendiculars drawn at the points U and V to the lines of the appropriate sides. Let W₀ be the foot of the perpendicular dropped from Q to the line of the side AB. Then W₀$\displaystyle ne$W. According to the above, AW₀²+BU²+CV²=AV²+CU²+BW₀², that is, (AW₀-BW₀)(AW₀+BW₀)=AV²+CU²-BU²-CV². In order to prove the converse of the statement already proved, it is enough to show that (AX-BX)(AX+BX)$\displaystyle ne$(AY-BY)(AY+BY) if X,Y are two distinct points of the line AB.

This can be proved as follows: The value of the expression (AX-BX)(AX+BX) is 0 if and only if X is the midpoint F of the line segment AB, otherwise its value is positive or negative, depending on whichof the open rays FB and FA the point X belongs to. For the reason of symmetry, therefore, we can assume that X and Y both lie on the ray FB. Let the point X move along the ray FB, starting at F. Initially, the value of the expression x=(AX-BX)(AX+BX) is 0. While X is on the line segment FB, AX is increasing, BX is decreasing, and AX+BX does not change, thus the value of x is strictly increasing. When X has reached and passed the point B, the value of AX-BX will be constant, and AX and BX will be increasing. Thus the value of x will go on increasing strictly. Hence, if X and Y both lie on the ray FB then our statement follows from the equality (AX-BX)(AX+BX)=(AY-BY)(AY+BY).

B.3536. Find the minimum value of ${x^2\over8}+x\cos x+\cos2x$ . (4 points)

Solution.

$\displaystyle {x^2\over8}+x\cos x+\cos2x={x^2\over8}+x\cos x+2\cos^2x-1={1\over8}(x+4\cos x)^2-1\ge-1\ ,$

and equality occurs if and only if f(x)=x+4cosx=0. The value of the continuous function f at the point x=0 is f(0)=4, which is positive, while at the point x=$\displaystyle pi$ it is f($\displaystyle pi$)=$\displaystyle pi$-4, which is negative. It follows from Bolzano's intermediate-value theorem that there exists a point 0<x<$\displaystyle pi$ where f(x)=0. Thus the minimum value of the expression of the problem is -1.

B.3537. The foot of the altitude from vertex B of a triangle ABC on side AC is H, the foot of the angle bisector from B is D, and the inscribed circle touches AC at E. The midpoint of the segment AC is F. Prove that EF is the geometric mean of FD and FH. (4 points)

Solution. Let a,b and c denote the sides opposite the corresponding vertices. If a=c, then the points D,E,F and H coincide, and in that case the statement is true. Otherwise, we can assume without the restriction of generality that a>c, and then the points C,F,D,E,H lie on the ray CA in this order. In order to determine the line segments EF, FD and FH, let us first calculate the lengths of CD, CE, CF and CH. It is clear that CF=b/2 and CE=s-c=(a+b-c)/2, and thus EF=CE-CF=(a-c)/2. Since the angle bisector divides the opposite side in the ratio of the adjacent sides, $\displaystyle CD={a\over a+c}b$, ezért $\displaystyle FD=CD-CF=b{a-c\over2(a+c)}$. Finally, by applying the cosine rule we get CH=acos$\displaystyle gamma$=(a²+b²-c²)/2b, that is, FH=CH-CF=(a²-c²)/2b. Hence

$\displaystyle FD\cdot FH={b(a-c)\over2(a+c)}\cdot{(a+c)(a-c)\over2b}=\Bigl({a-c\over2}\Bigr)^2=EF^2\ ,$

and that was the statement to prove. Note that the solution did not use the information that H was on the side AC.

B.3538. Find a positive real number that will increase by a factor of 2501 if the first and fifth digits after the decimal point are interchanged. (5 points)

Solution. Let X denote the number in question, and let X' be the number obtained by interchanging the digits. If X$\displaystyle ge$0.1, then X'<10X. therefore X<0.1, that is X=A+10^-5a and X'=A+10^-1a, where a is a non-0 digit and A is a positive number less than 0.1 in which the fifth digit after the deciomal point is 0. It follows from the condition Az X'=2501X that

$\displaystyle A={7499a\over2500}\cdot{1\over10^5}\ .$

Hence the number a has to make the digit preceding the decimal point in 7499a/2500 be 0.

Since 7499/2500 is only a little less than 3, that will be true in the single case a=7, and hence A=0,000209972 and X=0,000279972. 2501 times this number, 0,700209972 can really be obtained from X by interchanging the digits in the first and fifth decimal places. Therefore, this is the single solution of the problem.

B.3539. There are 8 breakable objects in a box. One of them is worth 50,000 forints (HUF), three are worth 30,000 forints each, and the remaining four are worth 20,000 each. The box is accidentally dropped during transportation. If each object will break with a probability of 1/2 independently of each other, what is the probability that the damage is no more than 100,000 forints? (4 points)

Solution. Let P(A_i) (0$\displaystyle le$i$\displaystyle le$1), P(B_i) (0$\displaystyle le$i$\displaystyle le$3) and P(C_i) (0$\displaystyle le$i$\displaystyle le$4) denote the probability that exactly i of the objects worth 50 000, 30 000 and 20 000 forints (HUF) will break. Then

$\displaystyle P(A_i)={1\over2}{1\choose i},P(B_i)={1\over2^3}{3\choose i};P(C_i)={1\over2^4}{4\choose i},$

as each object will break with a probability of 1/2, independently of each other. The probability that exactly i, j and k of the 50 000, 30 000 and 20 000-forint objects will break, respectively, is P(A_i)P(B_j)P(C_k), since the events are independent. To make calculations shorter, let us introduce the quantities

$\displaystyle P(B_{\le i})=\sum_{j=0}^iP(B_j);P(C_{\le i})=\sum_{j=0}^iP(C_j),$

too. If the 50 000-forint object does not break, and none of the 30 000-forint objects break then no matter how many of the the 20 000-forint objects break, the damage made will not exceed 100 000 forints.

The probability of that event is P(A₀)P(B₀)=1/16. By systematically considering every possibility in the same way, we get that the probability in question is

$\displaystyle P={1\over16}+P(A_0)\Bigl(P(B_1)P(C_{\le3})+P(B_2)P(C_{\le2})+P(B_3)P(C_0)\Bigr)+$

$\displaystyle +P(A_1)\Bigl(P(B_0)P(C_{\le2})+P(B_1)P(C_{\le1})\Bigr)=$

$\displaystyle ={1\over16}+{1\over2}\Bigl({3\over8}\cdot{15\over16}+{3\over8}\cdot{11\over16}+{1\over8}\cdot{1\over16}\Bigl)+{1\over2}\Bigl({1\over8}\cdot{11\over16}+{3\over8}\cdot{5\over16}\Bigr)={121\over256}\ .$

B.3540. In a triangle, consider the sum of the squares of the heights and the sum of the squares of the sides. In what interval does the ratio of the two numbers vary? (5 points) (based on the idea of Balogh János, Kaposvár)

Solution. It follows from Heron's formula $\displaystyle A=\sqrt{s(s-a)(s-b)(s-c)}$ and the area formulae 2A=ah_a=bh_b=ch_c that the ratio in question is

$\displaystyle x={1\over4}\Bigl({1\over a^2}+{1\over b^2}+{1\over c^2}\Bigr){(a+b+c)(a+b-c)(b+c-a)(c+a-b)\over a^2+b^2+c^2}\ .$

If a=b=c=1, then x=3/4, and in the degenerate case when a=b=1, c=2 we have x=0. If a=b=1 is fixed, for every 1$\displaystyle le$c<2 there exists a triangle with sides a,b,c. For 1$\displaystyle le$c$\displaystyle le$2 , x=x(c) is a continuous function of c. Therefore, the ratio in question may assume any value in the interval (0,3/4]. We shall prove that theratio cannot be more than 3/4.

To prove, we need to show that the inequality

$\displaystyle {(a^2b^2+b^2c^2+c^2a^2)(2a^2b^2+2b^2c^2+2c^2a^2-a^4-b^4-c^4)\over a^2b^2c^2(a^2+b^2+c^2)}\le3$

is true whenever a,b,c are the sides of a triangle. With the notations a²=x>0, b²=y>0, c²=z>0, this clearly follows from the inequality

$\displaystyle \Bigl(2(xy+yz+zx)-x^2-y^2-z^2)\Bigr)(xy+yz+zx)\le3(x+y+z)xyz$

which is true for all non-negative x,y,z.

By multiplicatiom and rearrangement, we get that the inequality is equivalent to

x³y+xy³+y³z+yz³+z³x+zx³-2(x²y²+y²z²+z²x²)$\displaystyle ge$0,

which is in turn equivalent to

xy(x-y)²+yz(y-z)²+zx(z-x)²$\displaystyle ge$0.

This last inequality is clearly true for all non-negative x,y,z. It is aso clear that for x,y,z>0, equality can only occur in the case x=y=z. Therefore, the ratio in question assumes its maximum value of 3/4 if and only if the triangle is equilateral.

B.3541. Let $\displaystyle f(x)={ax+b\over cx+d}$. Prove that if f(f(f(1)))=1, and f(f(f(2)))=3, then f(1)=1. (5 points)

Solution. Define an "allowed" function as any non-constant function of the form $\displaystyle {ax+b\over cx+d}$ defined on the set of real numbers with the exception of a finite subset. This requires that ad-bc$\displaystyle ne$0 for the coefficients of the function. With a simple calculation, it is easy to check that any particular value can only be assumed once by a function of this kind.

The composition of the allowed functions $\displaystyle f(x)={ax+b\over cx+d}$ and $\displaystyle g(x)={a'x+b'\over c'x+d'}$ is also an allowed function:

$\displaystyle (f\circ g)(x)={(aa'+bc')x+(ab'+bd')\over(ca'+dc')x+(cb'+dd')}$,

as it would follow from the inequality (aa'+bc')(cb'+dd')-(ab'+bd')(ca'+dc')= that (a'd'-b'c')(bc-ad)=0, which is impossible. Finally, the function fog fis undefined at a point x if and only if either g(x) is undefined (there are a finite number of such points), or f(g(x)) is undefined (which also occurs at a finite number of points), or x=-(cb'+dd')/(ca'+dc') (which occurs no more than once).

Since the function F=fofof is not constant on its domain, the function f cannot be constant either, and thus F is also an allowed function, and it has a fixed point at 1: F(1)=1. How many fixed points may an allowed function have? the condition $\displaystyle h(x)={Ax+B\over Cx+D}=x$ (on the domain of h) is equivalent to the condition Cx²+(D-A)x-B=0. Hence h may have 2 fixed points at most, except in the case of C=D-A=-B=0 when h(x)=x on the domain of h, which means that all points are fixed points.

Since F(2)$\displaystyle ne$2, the function F cannot have more than 2 fixed points, one of which is 1. If f(1)$\displaystyle ne$1, then consider the numbers u=f(1) and v=f(u). f is defined for these numbers, and f(v)=1. If u=v, then 1=f(f(u))=f(f(v))=f(1), and if v=1, then also 1=f(v)=f(1), which is contradiction. Furthermore,

F(u)=(Fof)(1)=(fofofof)(1)=(foF)(1)=f(1)=u,

and similarly

F(v)=(Fof)(u)=(fofofof)(u)=(foF)(u)=f(u)=u ,

that is 1,u,v are three distinct fixed points of the function F. This contradiction proves that f(1)=1.

Already signed up?
New to KöMaL?