International Mathematical Talent Search

Solutions and Comments Round 10

Problem 1/10

Solution 1:

Solution 2:

Comments:

Alternately, one finds that 9•(1) – 4•(2) produces y² – z² = 84. This equation may also be solved in integers by factoring both sides, but the previous solutions are more straightforward.

Problem 2/10

Solution 1:

Solution 2:

Comments:

Since neither the hypothesis nor the conclusion involved tight bounds, it would have been a violation of the “spirit of the problem” to obtain and utilize sharper approximations than the ones used above.

This problem, as well as the next one, were originally posed by Mr. F. David Hammer some years ago. Mr. Hammer is presently an industrial mathematician/computer analyst; some years ago, during his academic career, he prepared the problems for the excellent Stockton State Mathematics Contest.

Problem 3/10

where a_n, b_n, c_n, d_n depend only on n, such that

Solution 1:

Solution 2:

Solution 3:

From the first two of these we find that c_n = b_n – 1, while the first and last equations — upon substituting for c_n — yield a_n = n/2 + 1 – nb_n . Hence, upon substituting these values for a_n and c_n, from the first equation we find that b_n = 1 – n / (2(n – d_n)) , which in turn leads to a_n = 1 + nd_n / (2(n – d_n)) and c_n = –n / (2(n – d_n)) where d_n = n – e with 0 < e < 1 . For example, if d_n = n – 1/2, then (a_n, b_n, c_n, d_n) = ((2n² – n + 2)/2, 1 – n, –n, n – 1/2)) .

Problem 4/10

1. discard them if they are of the same color,
2. discard the black ball and return to the bag the red ball if they are different colors.

Solution:

Comments:

Problem 5/10

Solution:

Referring to the figure on the right, note that PQ has been extended to meet the circumcircle of DAXY at poínt H. The reader should recall that the measure of an angle inscribed in a circle equals one-half the measure of its intercepted arc. From this result, it follows that two angles inscribed in a circle and intercepting a common arc are equal and also that, in a cyclic quadrilateral, opposite angles are supplementary. We shall be applying these results to four cyclic quadrilaterals of our figure: ACPQ and ABQP (both inscribed in the circumcircle of DABC) and AQHX and HAQY (both inscribed in the circumcircle of DAXY).

Since ÐACP and ÐAQP are opposite angles of ACPQ, they are supplementary. So

Since ÐAQH and ÐHXA are opposite angles of AQHX,

From (1) and (2), it follows that ÐACP and ÐHXA are supplementary. Thus segments HX and YC must be parallel.

Now ÐBAQ and ÐBPQ are both inscribed in the circumcircle of DABC and both intercept arc BQ. So ÐBAQ equals ÐBPQ. A similar argument in the circumcircle of DAXY reveals that ÐYAQ equals ÐYHQ. Since ÐYAQ coincides with ÐBAQ, ÐBPQ equals ÐYHQ. Thus segments XP and HY must be parallel.

It follows that XHYP is a parallelogram, and its diagonals must bisect each other. Thus, XY is bisected by PH, which is the extension PQ.

Comments:

Solutions and Comments Round 11

Problem 1/11

Solution 1:

Solution 2:

Solution 3:

Since m must be an integer, it follows that m = 5, which yields n = 470, as before.

Solution 4:

Solution 5:

Comments:

One procedure for expressing a/b as the sum of “unit fractions” (i. e., fractions of the form 1/n) is to let n₁ = éb/aù , the smallest integer greater than b/a (This is the “ceiling function” of b/a). Then n₁ – b/a < 1, and hence an₁ – b < a. Moreover, a/b – 1/n₁ = (an₁ – b) / bn₁ . Repeat the process with (an₁ – b) / bn₁ in place of a/b. Since an₁ – b < a , this process must terminate in a finite number, say k steps. When an_k – b = 1 we are done. This process is known as the “Greedy Algorithm” and the proof that it terminates relies on the “Well-Ordering Property” of the natural numbers: Any nonempty subset of the natural numbers has a smallest element.

Problem 2/11

Solution 1:

Solution 2:

Solution 3:

Solution 4:

Solution 5:

Comments:

Problem 3/11

For what value of n can a rhombic 2n-gon be dissected into 666 rhombi?

Solution 1:

Solution 2:

Since each iteration produces i more rhombi, the total number of rhombi produced in constructing a rhombic 2n-gon will be

Solution 3:

Comments:

Problem 4/11

Solution 1:

where O is the intersection point of the angle bisectors at A, B, and C . Let E, F, G, and H be the feet of the perpendiculars from O to the sides of the quadrilateral, as shown in the figure below. Then DAEO and DAOH are congruent, since ÐOAE = ÐOAH, ÐOEA = ÐOHA, and |OA| = |OA| . Therefore, |OE| = |OH| . One can similarly show that |OE| = |OF| and |OF| = |OG| . Therefore, one may conclude that |OH| = |OG| .

To conclude the solution, we must still show that ÐODG = ÐODH . This can be done in several ways. For instance, if we construct a circle with radius |OG| and center O , then since GD and DH are tangent to the circle, the line OD will bisect the angle at D .

Alternately, one can argue that the right triangles DOGD and DODH are congruent, as they have the same hypotenuse and equal legs.

Solution 2:

Setting the product of the left hand sides equal to the product of the right hand sides of the above equations produces (after cancellations) the equation sin x = sin y . Since x + y ¹ 180°, it follows that x = y . Therefore, DO bisects ÐADC, as claimed.

Comments:

Problem 5/11

Solution 1:

Thus, there is a polynomial a(z) such that

and therefore

Now g(x) will be of degree less than 4 if and only if a(x) º 1 . In that case g(x) = 33x³ – 6x² + 383x + 5, and this is the desired polynomial.

Solution 2:

be satisfied. This system has the unique solution a = 33, b = –6, c = 383, and d = 5. Therefore, the desired polynomial is of degree 3 (otherwise we would have a = 0, for degree 2, or a = b = 0, for degree 1, or a = b = c = 0, for degree 0), and it is g(x) = 33x³ – 6x² – 383x + 5 .

Comments:

Problems Round 13

Problem 1/13

Problem 2/13

Problem 3/13

Problem 4/13

Problem 5/13

Solutions and Comments Round 14

Problem 1/14

Solution 1:

We can do the same thing for the expression with c and d. Thus, by squaring the original equation and dividing by two, the result follows.

Solution 2:

Thus, (a⁴ + b⁴ + (a – b)⁴) / 2 = (c⁴ + d⁴ + (c – d)⁴) / 2 , or equivalently, a⁴ + b⁴ + (a – b)⁴ = c⁴ + d⁴ + (c – d)⁴ .

Solution 3:

Problem 2/14

Notice that the sum of these three prices is $8.25, and that the product of these three numbers is also 8.25 . Identify four prices whose sum is $8.25 and whose product is also 8.25 .

Solution:

Let a, b, c, and d be the prices (in cents). We wish to find a, b, c, d so that

Suppose, without loss of generality, that a is not divisible by 5. Then 5⁸ divides bcd. Since each of these integers is less than 5⁴ = 625, none is divisible by 5⁴. Therefore, 5 divides each of b, c and d. But this would imply that 5 does not divide a + b + c + d = 825, a contradiction. Therefore all the integers are divisible by 5.

Suppose, without loss of generality, that a is not divisible by 25. Then 5⁷ divides bcd. If 25 divides each of b, c, and d then 25 does not divide a + b + c + d = 825, a contradiction. Thus, without loss of generality, b is also not divisible by 25, while 125 divides both c and d. Thus c and d must be one of the numbers {125, 250, 375}. We may check each of these values for c, d and solve for a and b. Doing this, we find that:

Therefore, 25 must divide each of a, b, c, d. Let A = a / 25, B = b / 25, C = c / 25 and D = d / 25. We wish to find integers A, B, C, D satisfying:

Now, the only multiple of 11 between 2 and 18 is 11. Therefore, without loss of generafity, we may set A = 11. Thus we have

Thus {B, C, D} Î {2, 3, 4, 6, 8, 12, 16}. Without loss of generality, 3 divides B, thus B = 3, 6 or 12. Checking each case, we find

Since only the last case yields integer solutions, the four prices must be $0.50, $2.00, $2.75 and $3.00 .

Problem 3/14

Solution 1:

Solution 2:

Solution 3:

Comments:

Problem 4/14

Solution 1:

Then

Thus if c = a + b + 2k = a + b + 2Ö(ab + 1), then a ~ c and b ~ c, as desired, since ac + 1 = (k + a)² and bc + 1 = (k + b)².

Solution 2:

must be a perfect square. This happens if (k – m)/a = ±1; i. e., if m = k ± a. Then

Note that |a – b| ³ 2 whenever a ~ b, and that when |a – b| = 2, (a – b)² = 4, from which (a + b)² = 4(ab + 1), and hence a + b – 2Ö(ab + 1) = 0 follows. Hence we can choose c = a + b + 2Ö(ab + 1) when |a – b| = 2, and c = a + b ± 2Ö(ab + 1) when |a – b| > 2 .

Solution 3:

to be a perfect square, its discriminant should also vanish; i. e., u and v must satisfy the equation

It follows that v = u ± 1, and c = av² + 2v = a(u ± 1)² + 2(u ± 1) = au² ± 2au + a + 2u ± 2 = a + b ± 2(au + 1) = a + b ± 2Ö(ab + 1), as in the previous solution.

Solution 4:

is a perfect square if s = 2(b – k); i. e., if

Solution 5:

is an integer, and ab + t, ac + t, and bc + t are perfect squares (of (a + b – c)/2, (a – b + c)/2, and (–a + b + c)/2, respectively). Solving the above equation for c, we find that c = a + b ± 2Ö(ab + t), as in the first three solutions above.

Comments:

Moreover, one can also show that if a ~ b, a ~ c, and b ~ c, then there is a positive integer d such that a ~ d, b ~ d, and c ~ d. This problem was posed in the November 1994 issue of Math Horizons.

It should be noted that the use of the discriminants of the quadratics in Solutions 3 and 4 reflects a doze of wishful thinking. While it is true for polynomial squares that for ab + 1 to be a perfect square, b must be of the form au² + 2u for some integer u, it is not true for integer squares. For example, x² + 3x + 21 is a perfect square when x = 1 even though its discriminant is not 0; while 3 · 8 + 1 = 25, even though 8 is not of the form 3u² + 2u for any integer u. Nevertheless, the technique of using discriminants is ‘justified’ by the outcome: we were searching for formulas rather than drawing irrefutable conclusions.

Problem 5/14

Solution 1:

Recall that the area of a triangle is given by one-half the product of the lengths of two sides and the sine of the included angle. By side-angle-side, the three “corner” triangles of the hexagon on the left, DADE, DBFG, and DCHI, are congruent to DABC. Thus, the area of T₁ is

and the area of T₂ is

and in view of the Law of Sines,

upon expanding the expressions above, it is easy to see that T₁ = T₂.

Solution 2:

Since T(ACG’) / T₀ = (b + c) / c and T(AG’H’) / T(ACG’) = (b + c) / b in the hexagon on the right, we find that

Solution 3:

We will use this result to obtain equality of the areas of various triangles and quadrilaterals in the given hexagons.

For instance, we find that T(ABI’) = T(ACF) and T(ABH’) = T(BCE). Also T(ABH’I’) = T(CEF). Since also T(ABH’I’) = T(ABI’) + T(ABH’) + T(CH’I’) – T₀, we have T(BCE) + T(ACF) + T(CH’I’) = T(CEF) + T₀. By similar arguments, T(BCF) + T(ABI) + T(BF’G’) = T(BDI) + T₀, and T(ACG) + T(ABH) + T(AD’E’) = T(AGH) + T₀.

It can also be seen that T(AG’H’) = T(BCDE), T(BD’I’) = T(ACGF), and T(CE’F’) = T(ABHI). Therefore

Comments:

Solutions and Comments Round 15

Problem 1/15

Solution 1:

Solution 2:

Solution 3:

Comments:

More generally, one can show that it is possible to pair off the positive integers 1, 2, 3, 4, ... , 2n – 1, 2n in the desired manner if and only if 1 £ n £ 6 .

Problem 2/15

Solution:

To derive them, one must do a lot of case by case tedious analysis, which we will not reproduce below. In view of the ready availability of speedy home computers, such work is best done via some computer algebra system (like Maple, Mathematica, Macsyma, etc.) or with a computer program (in Pascal, Basic, C, etc.). The key is to devise an algorithm which checks all possible choices for the 10 digits; i. e., all 10! possibilities. While this is a huge number, it shouldn’t take much more than an hour to complete the task.

Naturally, if one can determine the value of any of the letters, the time can be cut down considerably. It turns out that in both parts of the problem it seems easiest to determine R. Interestingly, while Part (ii) is harder, it is more cumbersome to show that R = 4 in Part (i), than to verify that R = 1 in Part (ii). Once we have R = 4 in Part (i), we can determine the rest of its letters rather easily, even without a computer.

Problem 3/15

Solution 1:

In the first case, assume that there are two vertices, A_i and A_j , that are not adjacent to one another, with both of the edges, BA_i and BA_j , colored blue. Then, to avoid creating a monochromatic triangle (one, whose three sides are of the same color), we must color CA_i red (in view of DBCA_i), and CA_j must also be red (in view of DBCA_j). However, the coloring of diagonal A_iA_j will make either DBA_iA_j, or DCA_iA_j monochromatic. Hence this case leads to a monochromatic triangle.

In the second case, we may assume that there are five adjacent vertices, say A₃, A₄, A₅, A₆, A₇ such that the edges BA₃, BA₄, BA₅, BA₆, BA₇ are all blue. Again we will try to avoid creating a monochromatic triangle by careful coloring of the diagonals of the heptagon. To that end, A₃A₇ must be blue (in view of DBA₃A₇), A₄A₆ must be blue (in view of DBA₄A₆), A₃A₅ must be blue (in view of DBA₃A₅), and A₅A₇ must be blue (in view of DBA₅A₇). However, since all three sides of DA₃A₅A₇ are blue, this case also leads to a monochromatic triangle.

Solution 2:

Comments:

To follow the solutions given above, the reader is advised to make his/her own sketches of the different configurations presented.

Problem 4/15

= c² and x² + y² = z² are satisfied. Prove that

(a + x)² + (b + y)² £ (c + z)²,

and determine when equality holds.

Solution 1:

In the figure on the right, in view of the Triangle Inequality, k £ c + z . Since k² = (a + x)² + (b + y)² , this is equivalent to (a + x)² + (b + y)² £ (c + z)² . Equality holds if and only if k = c + z , i. e., if and only if the right triangles with sides a, b, c and x, y, z are similar, i. e., if and only if a/z = b/y = c/z .

Solution 2:

Since (a/c)(x/z) + (b/c)(y/z) = sin q sin f + cos q cos f = cos(q – f) £ 1; and it follows that ax + by £ cz . Therefore, (a + x)² + (b + y)² = (a² + b²) + (x² + y²) + 2(ax + by) £ c² + z² + 2cz = (c + z)². Equality holds if and only if q = f . In that case, the triangles are similar; i. e., a/x = b/y = c/z .

Solution 3:

For positive a, b, c, x, y, z, with a² + b² = c² and x² + y² = z², 0 £ (ay – bx)² Û 2aybx £ a²y² + b²x² Û (ax + by)² = a²x² + 2axby + b²y² £ a²x² + a²y² + b²x² + b²y² = (a² + b²)(x² + y²) = c²z² Û ax + by £ cz Û (a + x)² + 2(ax + by) + (x² + y²) £ c² + 2cz + z² = (c + z)² . Equality holds if and only if ay – bx = 0, in which case a/x = b/y , implying that c²/z² = (a² + b²) / (x² + y²) = ((b²x² / y²) + b²) / (x² + y²) = b²/y² ; i. e., c/z = b/y .

Solution 4:

Let u = (a, b) and v = (x, y) . Then c = Ö(a² + b²) = ||u|| and z = Ö(x² + y²) = ||v|| . In viev of the Triangle Inequality for vectors in the plane it follows that Ö((a + x)² + (b + y)²) = ||u + v|| £ ||u|| + ||v|| = c + z , which is equivalent to the desired inequality. Equality occurs if and only if u = kv for some real constant k , i. e., if and only if a = kx and b = ky . In that case, for positive k , c = ||u|| = ||kv|| = k||v|| = kz .

Comments:

One can also use as an alternate starting point the Cayley-Schwarz Inequality, (a² + b²)(x² + y²) ³ (ax + by)² , which follows from the fact that (a² + b²)(x² + y²) = (ax + by)(ay – bx)² .

More generally, one can also show that if a_i and b_i are positive real numbers for 1 £ i £ n , where n is a positive integer greater than 2, and

if

n S i=1

ai2 = x2 and

n S i=1

bi2 = y2 , then

n S i=1

(ai + bi)2 £ (x + y)2 ,

with equality if and only if a₁/b₁ = a₂/b₂ = ... = a_n/b_n .

In the more restricted setting of the present problem, the result can also be derived by first showing that if (a, b, c) and (x, y, z) are primitive Pythagorian triples (i. e., the greatest common divisor of a, b, c is 1, and the same is true for x, y, z), then (c + z)² – (a + x)² – (b + y)² is the square of a non-negative integer.

Problem 5/15

Let C₁ and C₂ be two circles intersecting at the points A and B , and let C₀ be a circle through A , with center at B . Determine, with proof, conditios under which the common chord of C₀ and C₁ is tangent to C₂?

Solution 1:

Let O denote the center of circle C₁ , P denote the center of circle C₂ , and Q denote the point of intersection of circles C₁ and C₀ , other than A . We claim that AQ is tangent to C₂ at A if and only if the circles C₁ and C₂ have equal radii. To this end, let r₁ = OA = OB be the radius of C₁ and r₂ = PA = PB be the radius C₂ .

Note that the segment connecting the centers of two intersecting circles is the perpendicular bisector of their common chord. Therefore, AB ^ OP and AQ ^ OB. Now assume that AQ is tangent to C₂ at A . Then AQ ^ AP . Therefore, AP is parallel to OB and so ÐAPO = ÐBOP . Moreover, ÐAPO = ÐBPO, so ÐBOP = ÐBPO . Therefore, DBOP is isosceles with equal sides OB and PB . So r₁ = OB = PB = r₂ .

Conversely, assume that r₁ = r₂ . Then AOBP is a rhombus so that AP is parallel to OB . Since AQ ^ OB , it follows that AQ ^ AP . Hence AQ is tangent to C₂ at A .

Solution 2:

Let a = ÐBAQ = ÐAQB and b = ÐBAP = ÐABP . Note that the sine of any angle in a triangle is equal to the ratio of the length of the side opposite the angle to the length of the diameter of the circumscribed circle. Applying this result to the angle a = ÐAQB in DBAQ (which C₁ circumscribes), we have sin a = AB/2r₁ . Also, applying the Law of Cosines in DABP , we have

cos b =

r22 + AB2 – r22 —————— 2r2AB

=

AB —— 2r2

.

Now, AQ is tangent to C₂ at A Û a + b = 90° Û sin a = cos b Û AB/2r₁ = AB/2r₂ Û r₁ = r₂ .

---

IMTS Rounds Index: 1–9 10 11 12 13 14 15 16 17 18 19 20

---

Problems Round 16

Problem 1/16

Prove that if a + b + c = 0 , then a³ + b³ + c³ = 3abc .

Problem 2/16

For a positive integer n, let P(n) be the product of the nonzero base 10 digits of n . Call n “prodigitious” if P(n) divides n . Show that one can not have a sequence of fourteen consecutive positive integers that are all prodigitious.

Problem 3/16

Disks numbered 1 through n are placed in a row of squares, with one square left empty. A move consists of picking up one of the disks and moving it into the empty square, with the aim to rearrange the disks in the smallest number of moves so that disk 1 is in square 1, disk 2 is in square 2, and so on until disk n is in square n and the last square is empty. For example, if the initial arrangement is

3

2

1

6

5

4

9

8

7

12

11

10

then it takes at least 14 moves; i. e., we could move the disks into the empty square in the following order: 7, 10, 3, 1, 3, 6, 4, 6, 9, 8, 9, 12, 11, 12.

What initial arrangement requires the largest number of moves if n = 1995? Specify the number of moves required.

Problem 4/16

Let ABCD be an arbitrary convex quadrilateral, with E, F, G, H the midpoints of its sides, as shown in the figure on the right. Prove that one can piece together triangles AEH, BEF, CFG, DGH to form a parallelogram congruent to parallelogram EFGH .

Problem 5/16

An equiangular octagon ABCDEFGH has sides of length 2, 2Ö2, 4, 4Ö2, 6, 7, 7, 8. Given that AB = 8 , find the length of EF .

---

IMTS Rounds Index: 1–9 10 11 12 13 14 15 16 17 18 19 20

---

Problems Round 17

Problem 1/17

The 154-digit number, 19202122...939495, was obtained by listing the integers from 19 to 95 in succession. We are to remove 95 of its digits, so that the resulting number is as large as possible. What are the first 19 digits of this 59-digit number?

Problem 2/17

Find all pairs of positive integers (m,n) for which m² – n² = 1995.

Problem 3/17

Show that it is possible to arrange in the plane 8 points so that no 5 of them will be the vertices of a convex pentagon. (A polygon is convex if all of its interior angles are less than or equal to 180°.)

Problem 4/17

A man is 6 years older than his wife. He noticed 4 years ago that he has been married to her exactly half of his life. How old will he be on their 50^th anniversary if in 10 years she will have spent two-thirds of her life married to him?

Problem 5/17

What is the minimum number of 3 × 5 rectangles that will cover a 26 × 26 square? The rectangles may overlap each other and/or the edges of the square. You should demonstrate your conclusion with a sketch of the covering.

---

IMTS Rounds Index: 1–9 10 11 12 13 14 15 16 17 18 19 20

---

Problems Round 18

Problem 1/18

Determine the minimum length of the interval [a, b] such that a £ x + y £ b for all real numbers x ³ y ³ 0 for which 19 x + 95 y = 1995.

Problem 2/18

For a positive integer n ³ 2, let P(n) denote the product of the positive integer divisors (including 1 and n) of n. Find the smallest n for which P(n) = n¹⁰.

Problem 3/18

The graph shown on the right has 10 vertices, 15 edges, and each vertex is of order 3 (i. e., at each vertex 3 edges meet). Some of the edges are labeled 1, 2, 3, 4, 5 as shown. Prove that it is possible to label the remaining edges 6, 7, 8, ... , 15 so that at each vertex the sum of the labels on the edges meeting at that vertex is the same.

Problem 4/18

Let a, b, c, d be distinct real numbers such that

a + b + c + d = 3   and   a² + b² + c² + d² = 45.

Find the value of the expression

a5 —————————— (a – b)(a – c)(a – d)

+

b5 —————————— (b – a)(b – c)(b – d)

+

c5 —————————— (c – a)(c – b)(c – d)

+

d5 —————————— (d – a)(d – b)(d – c)

.

Problem 5/18

Let a and b be two lines in the plane, and let C be a point as shown in the figure on the right. Using only a compass and an unmarked straight edge, construct an isosceles right triangle ABC, so that A is on line a, B is on line b, and AB is the hypotenuse of DABC.

---

IMTS Rounds Index: 1–9 10 11 12 13 14 15 16 17 18 19 20

---

Problems Round 19

Problem 1/19

It is possible to replace each of the ± signs below by either – or + so that

± 1 ± 2 ± 3 ± 4 ± ... ± 96 = 1996.

At most how many of the ± signs can be replaced by a + sign?

Problem 2/19

We say (a, b, c) is a primitive Heronian triple if a, b, and c are positive integers with no common factors (other than 1), and if the area of the triangle whose sides measure a, b, and c is also an integer. Prove that if a = 96, then b and c must both be odd.

Problem 3/19

5	5	5	2	1	3	3	4
6	4	4	2	1	1	5	2
6	3	3	2	1	6	0	3
3	0	5	5	0	0	0	6
3	2	1	6	0	0	4	2
0	3	6	4	6	2	6	5
2	1	1	4	4	4	1	5

The numbers in the 7×8 rectangle shown on the right were obtained by putting together the 28 distinct dominoes of a standard set, recording the number of dots, ranging from 0 to 6 on each side of the dominoes, and then erasing the boundaries among them. Determine the original boundaries among the dominoes. (Note: Each domino consists of two adjoint squares, referred to as its sides.)

Problem 4/19

Suppose that f satisfies the functional equation

2 f (x) + 3 f

(

2 x + 29 ———— x – 2

)

= 100 x + 80.

Find f (3).

Problem 5/19

In the figure on the right, determine the area of the shaded octagon as a fraction of the area of the square, where the boundaries of the octagon are lines drawn from the vertices of the square to the midpoints of the opposite sides.

---

IMTS Rounds Index: 1–9 10 11 12 13 14 15 16 17 18 19 20

---

Prepared by Vladimirensa. Last updated on 2^nd August, 1998.