49th Eötvös Competition Problems 1945

1.  Knowing that 23 October 1948 was a Saturday, which is more frequent for New Year's Day, Sunday or Monday?

2.  A convex polyhedron has no diagonals (every pair of vertices are connected by an edge). Prove that it is a tetrahedron.

3.  Prove that among any n positive integers one can always find some (at least one) whose sum is divisible by n.

[Read More...]

48th Eötvös Competition Problems 1944

1.  Prove that 46²ⁿ⁺¹ + 296·13²ⁿ⁺¹ is divisible by 1947.

2.  Show that any graph with 6 points has a triangle or three points which are not joined to each other.

3.  What is the smallest number of disks radius ½ that can cover a disk radius 1?

[Read More...]

47th Eötvös Competition Problems 1943

1.  Show that a graph has an even number of points of odd degree.

2.  P is any point inside an acute-angled triangle. D is the maximum and d is the minimum distance PX for X on the perimeter. Show that D ≥ 2d, and find when D = 2d.

3.  x₁ < x₂ < x₃ < x₄ are real. y₁, y₂, y₃, y₄ is any permutation of x₁, x₂, x₃, x₄. What are the smallest and largest possible values of (y₁ - y₂)² + (y₂ - y₃)² + (y₃ - y₄)² + (y₄ - y₁)². 

Solutions

Problem 1

Show that a graph has an even number of points of odd degree.

Solution

Let the n points of the graph have degree d₁, d₂, ... , d_n. Then the no. of edges is (∑ d_i)/2. Hence ∑ d_i is even. So an even number of the d_i must be odd. 

Problem 2

P is any point inside an acute-angled triangle. D is the maximum and d is the minimum distance PX for X on the perimeter. Show that D ≥ 2d, and find when D = 2d.

Solution

If X is any point of the segment YZ except its endpoints, then PX < max(PY, PZ), so if the triangle is ABC, then D = max(PA, PB, PC). Also since the triangle is acute, d = min(PR, PS, PT), where R, S, T are the feet of the perpendiculars from P to BC, CA, AB respectively.

At least one of the angles at P must be ≤ 60^o. Suppose it is ∠APS. Then PS = AP cos APS ≤ AP/2. Hence D ≥ d/2. We can get equality only if all the angles are 60^o. But in that case ∠ TAP = ∠SAP = 30^o, so ∠A = 60^o and similarly for the other angles, so ABC is equilateral. 

Problem 3

x₁ < x₂ < x₃ < x₄ are real. y₁, y₂, y₃, y₄ is any permutation of x₁, x₂, x₃, x₄. What are the smallest and largest possible values of (y₁ - y₂)² + (y₂ - y₃)² + (y₃ - y₄)² + (y₄ - y₁)².

Solution

Put [y₁,y₂,y₃,y₄] = (y₁ - y₂)² + (y₂ - y₃)² + (y₃ - y₄)² + (y₄ - y₁)². Obviously, [x₁,x₂,x₃,x₄] = [x₂,x₃,x₄,x₁] = [x₃,x₄,x₁,x₂] = [x₄,x₁,x₂,x₃] and similarly for [x₂,x₁,x₃,x₄] etc, so we need only consider the 6 values: [x₁,x₂,x₃,x₄], [x₁,x₂,x₄,x₃], [x₁,x₃,x₂,x₄], [x₁,x₃,x₄,x₂], [x₁,x₄,x₂,x₃], [x₁,x₄,x₃,x₂]. But equally, [x₁,x₂,x₃,x₄] = [x₁,x₄,x₃,x₂] etc (rotating the other way), so there are only three values to consider: [x₁,x₂,x₃,x₄], [x₁,x₂,x₄,x₃], [x₁,x₃,x₂,x₄].

Now it is easy to check that [x₁,x₂,x₃,x₄] - [x₁,x₂,x₄,x₃] = 2(x₂-x₁)(x₄-x₃) > 0, and [x₁,x₃,x₂,x₄] - [x₁,x₂,x₃,x₄] = 2(x₄-x₁)(x₃-x₂) > 0, so we have [x₁,x₂,x₄,x₃] < [x₁,x₂,x₃,x₄] < [x₁,x₃,x₂,x₄]. Thus [x₁,x₃,x₂,x₄] is the largest possible value and [x₁,x₂,x₄,x₃] is the smallest possible value.

[Read More...]

46th Eötvös Competition Problems 1942

1.  Show that no triangle has two sides each shorter than its corresponding altitude (from the opposite vertex).

2.  a, b, c, d are integers. For all integers m, n we can find integers h, k such that ah + bk = m and ch + dk = n. Show that |ad - bc| = 1.

3.  ABC is an equilateral triangle with area 1. A' is the point on the side BC such that BA' = 2·A'C. Define B' and C' similarly. Show that the lines AA', BB' and CC' enclose a triangle with area 1/7.

Solutions

Problem 1

Show that no triangle has two sides each shorter than its corresponding altitude (from the opposite vertex).

Solution

Suppose AD > BC and BE > AC. Then AD > BC ≥ BE > AC ≥ AD. Contradiction. Similarly in the other cases.

Problem 2

a, b, c, d are integers. For all integers m, n we can find integers h, k such that ah + bk = m and ch + dk = n. Show that |ad - bc| = 1.

Solution

In particular we can take h, k so that ch + dk = 1, so c and d have no common factor. Now take m = 1, n = 0. Then ch + dk = 0, so c divides dk and hence k. Suppose k = cr, then h = -dr. So -adr + bcr = 1. Hence ad - bc = ±1. 

Problem 3

ABC is an equilateral triangle with area 1. A' is the point on the side BC such that BA' = 2·A'C. Define B' and C' similarly. Show that the lines AA', BB' and CC' enclose a triangle with area 1/7.

Solution

Take the enclosed triangle to be DEF as shown. Let the line AA' meet the line through C parallel to BB' at X.

By symmetry, DEF is equilateral and AD = BE = CF. So ∠CFX = ∠CXF = 60^o, so CFX is also equilateral. So CX = CF = BE. Hence CXBE is a parallelogram. So CF is parallel to BX and hence CA'F and BA'X are similar. So BX = 2 CF. But BX = CE (parallelogram), so F is the midpoint of CE. Similarly, D is the midpoint of AF, and E is the midpoint of BD. Now area BEC = 2 area BEF = 2 area DEF. Similarly, area AFC = 2 area DEF and area BDA = 2 area DEF. But area ABC = area BEC + area AFC + area BDA + area DEF. Hence result.

[Read More...]

45th Eötvös Competition Problems 1941

1.  Prove that (1+x)(1+x²)(1+x⁴) ... (1+x^2n-1) = 1 + x + x² + x³ + ... + x^2n-1.

2.  The a parallelogram has its vertices at lattice points and there is at least one other lattice point inside the parallelogram or on its sides. Show that its area is greater than 1.

3.  ABCDEF is a hexagon with vertices on a circle radius R (in that order). The three sides AB, CD, EF have length R. Show that the midpoints of BC, DE, FA form an equilateral triangle.

Solutions

Problem 1

Prove that (1+x)(1+x²)(1+x⁴) ... (1+x^2n-1) = 1 + x + x² + x³ + ... + x^2n-1.

Solution

Multiply the lhs by 1-x. We have (1-x)(1+x) = 1-x², (1-x²)(1+x²) = 1-x⁴, (1-x⁴)(1+x⁴) = 1-x⁸, and so on. So (1-x)lhs = 1-x²ⁿ. Similarly, (1-x)rhs = 1-x²ⁿ. 

Problem 2

The a parallelogram has its vertices at lattice points and there is at least one other lattice point inside the parallelogram or on its sides. Show that its area is greater than 1.

Solution

This follows immediately from Pick's theorem, which makes one worry that a proof of Pick's theorem might be expected. An alternative is to use the formula for the area of a triangle: the triangle with coordinates (x₁,y₁), (x₂,y₂), (x₃,y₃) has area ±(x₁(y₂ - y₃) + x₂(y₃ - y₁) + x₃(y₁ - y₂))/2. So the area of a lattice triangle must be a multiple of ½ and hence ≥½. Now take the extra lattice point and join it to the vertices of the parallelogram. If the point is inside the parallelogram, we get 4 lattice triangles, each area ≥½. If the point is on a side of the parallelogram, then we get 3 lattice triangles, each area ≥½.

However, proving the area theorem is also fairly tedious. The idea is to enclose the triangle in a lattice rectangle, so that its area is a rectangle area less various right-angle triangle areas, all of which can be written straight down. The problem is that there are several different cases to consider. 

Problem 3

ABCDEF is a hexagon with vertices on a circle radius r (in that order). The three sides AB, CD, EF have length r. Show that the midpoints of BC, DE, FA form an equilateral triangle.

Solution

Use vectors. Take the origin at the center of the circle. Denote the vector OX by X. Let the midpoint of BC, DE, FA be P, Q, R respectively. Then P = (B+C)/2, Q = (D+E)/2. So the vector QP is (B+C-D-E)/2. If we rotate through 60^o, then B becomes A, C becomes C-D, D becomes C, and E becomes E-F, so the vector QP becomes (A+C-D-C-E+F)/2 = (A+F-D-E)/2, which is the vector QR. Hence PQR is equilateral.

[Read More...]

44th Eötvös Competition Problems 1940

1.  Each button in a box is big or small, and white or black. There is at least one big button, at least one small button, at least one white button, and at least one black button. Show that there are two buttons with different size and color.

2.  m and n are different positive integers. Show that 2^2m + 1 and 2²ⁿ + 1 are coprime.

3.  T is a triangle. Show that there is a triangle T' whose sides are equal to the medians of T, and that T'' is similar to T. 

Solutions

Problem 1

Each button in a box is big or small, and white or black. There is at least one big button, at least one small button, at least one white button, and at least one black button. Show that there are two buttons with different size and color.

Solution

Suppose not. There is a big button. Suppose it is white. Then the small button must be white also (or it would be have different size and color from the big white). Now if the black button is big it is different size and color from the small white. If it is small it is different size and color from the big white. Contradiction. We obtain an exactly similar contradiction if the big button is black. 

Problem 2

m and n are different positive integers. Show that 2^2m + 1 and 2²ⁿ + 1 are coprime.

Solution

wlog m < n. Suppose p divides both 2^2m + 1 and 2²ⁿ + 1. Then since they are both odd, p must be odd. It must also divide their difference 2^2m(2^2n-m - 1) and hence 2^2n-m - 1. But (2^2n-m - 1)(2^2n-m + 1) = (2^2n-m+1 - 1), so p also divides (2^2n-m+1 - 1) and so by a trivial induction (2²ⁿ - 1). But it divides (2²ⁿ + 1), so it must divide their difference 2. But p is odd, so they have no common factors. 

Problem 3

T is a triangle. Show that there is a triangle T' whose sides are equal to the medians of T, and that T'' is similar to T.

Solution

Let L, M be the midpoints of BC, AC respectively. Take B' as the reflection of B in M, so that AB'CB is a parallelogram. Let N be the midpoint of B'C. Then MN is parallel to AB' and half its length. Hence it is also equal and parallel to BL. So MNLB is a parallelogram and hence LN = BM. Finally, AN has the same length as the median from C. So ALN has sides equal to the medians of ABC. Thus the triangle T certainly exists.

Note that MNCL is a parallelogram, so X is the midpoint of LN. Hence AX is a median of T. But X is the midpoint of MC, so AX = (3/4) AC. Now LN is the median from B (in length), and we have shown that the median to it is (3/4) the length of the side opposite to B. Similarly for the other sides. So T'' has sides equal to those of T times (3/4). In particular, it is similar to T.

[Read More...]

43rd Eötvös Competition Problems 1939

1.  Show that (a + a')(c + c') ≥ (b + b')² for all real numbers a, a', b, b', c, c' such that aa' > 0, ac ≥ b², a'c' ≥ b'².

2.  Find the highest power of 2 dividing 2ⁿ!

3.  ABC is acute-angled. A' is a point on the semicircle diameter BC (lying on the opposite side of BC to A). B' and C' are similar. Show how to construct such points so that AB' = AC', BC' = BA' and CA' = CB'.

Solutions

Problem 1

Show that (a + a')(c + c') ≥ (b + b')² for all real numbers a, a', b, b', c, c' such that aa' > 0, ac ≥ b², a'c' ≥ b'².

Solution Using the fact that aa', ac, a'c' are all non-negative we find that if a ≥ 0, then so is a', c, c'. Similarly, if a ≤ 0, then so is a', c, c'. Hence ac' and a'c are non-negative. Their geometric mean is bb'. Hence (ac' + a'c)/2 ≥ bb'. Hence (a + a')(c + c') = ac + a'c' + (ac' + a'c) ≥ b² + 2bb' + b'² = (b + b')². 

Problem 2

Find the highest power of 2 dividing 2ⁿ!

Solution

Let X = {1, 2, 3, ... , 2ⁿ}. There are 2^n-1 multiples of 2 in X, 2^n-2 multiples of 2², 2^n-3 multiples of 2³, ... 1 multiple of 2ⁿ. The multiples of 2 contribute 2^n-1 powers of 2. The multiples of 2² contribute an additional 2^n-2 powers of 2 and so on. So the highest power of 2 divding 2ⁿ! is 2^k, where k = 2^n-1 + 2^n-2 + ... + 1 = 2ⁿ - 1.

Problem 3

ABC is acute-angled. A' is a point on the semicircle diameter BC (lying on the opposite side of BC to A). B' and C' are similar. Show how to construct such points so that AB' = AC', BC' = BA' and CA' = CB'.

Solution

Let points A', B', C' lie on the altitudes as shown. Now CA'D and CBA' are similar, so CA'/CD = CB/CA'. Hence CA'² = CD·CB. Similarly, CB'² = CE·CA. But ∠AEB = ∠ADB = 90^o, so AEDB is cyclic. Hence CD·CB = CE·CA, so CA'² = CB'². So CA' = CB'. Similarly for the other two desired equalities.

[Read More...]

42nd Eötvös Competition Problems 1938

1.  Show that a positive integer n is the sum of two squares iff 2n is the sum of two squares.

2.  Show that 1/n + 1/(n+1) + 1/(n+2) + ... + 1/n² > 1 for integers n > 1.

3.  Show that for every acute-angled triangle ABC there is a point in space P such that (1) if Q is any point on the line BC, then AQ subtends an angle 90^o at P, (2) if Q is any point on the line CA, then BQ subtends an angle 90^o at P, and (3) if Q is any point on the line AB, then CQ subtends an angle 90^o at P. 

Solutions

Problem 1

Show that a positive integer n is the sum of two squares iff 2n is the sum of two squares.

Solution

If n = a² + b², then 2n = (a+b)² + (a-b)². Conversely if 2n = a² + b², then n = ( (a+b)/2)² + ( (a-b)/2)², and since a²+b² is even, so are a±b, and hence (a±b)/2 are integers. 

Problem 2

Show that 1/n + 1/(n+1) + 1/(n+2) + ... + 1/n² > 1 for integers n > 1.

Solution

There are n²-n terms after the first. These terms are all at least 1/n² and at least one of them is > 1/n², so their sum > (n²-n)/n² = 1 - 1/n. Hence the sum of all the terms > 1. 

Problem 3

Show that for every acute-angled triangle ABC there is a point in space P such that (1) if Q is any point on the line BC, then AQ subtends an angle 90^o at P, (2) if Q is any point on the line CA, then BQ subtends an angle 90^o at P, and (3) if Q is any point on the line AB, then CQ subtends an angle 90^o at P.

Solution

It is sufficient to find a point O such that ∠AOB = ∠BOC = ∠COA = 90^o. For then AO is normal to the plane BOC, so if P is any point in the plane BOC, we have ∠AOP = 90^o, In particular, it is true for any point P on the line BC. Similarly for the other vertices.

Take AB = c, CA = b, BC = a, as usual. Suppose OA = x, OB = y, OC = z. Then x² + y² = c², y² + z² = a², z² + x² = b², so x² = (b² + c² - a²)/2, y² = (a² - b² + c²)/2, z² = (a² + b² - c²)/2. Since the triangle is acute-angled, each of the brackets is positive, so we can choose such x, y, z.

[Read More...]

41st Eötvös Competition Problems 1937

1.  a₁, a₂, ... , a_n is any finite sequence of positive integers. Show that a₁! a₂! ... a_n! < (S + 1)! where S = a₁ + a₂ + ... + a_n.

2.  P, Q, R are three points in space. The circle C_P passes through Q and R, the circle C_Q passes through R and P, and the circle C_R passes through P and Q. The tangents to C_Q and C_R at P coincide. Similarly, the tangents to C_R and C_P at Q coincide, and the tangents to C_P and C_Q at R coincide. Show that the circles are either coplanar or lie on the surface of the same sphere.

3.  A₁, A₂, ... , A_n are points in the plane, no three collinear. The distinct points P and Q in the plane do not coincide with any of the A_i and are such that PA₁ + ... + PA_n = QA₁ + ... + QA_n. Show that there is a point R in the plane such that RA₁ + ... + RA_n < PA₁ + ... + PA_n.

Solutions

Problem 1

a₁, a₂, ... , a_n is any finite sequence of positive integers. Show that a₁! a₂! ... a_n! < (S + 1)! where S = a₁ + a₂ + ... + a_n.

Solution

We use induction on n to prove the stronger result that the lhs < S!. For n = 1 there is nothing to prove. For n = 2, we have (a₁+a₂)!/(a₁!a₂!)= (a₁+1)(a₁+2)...(a₁+a₂)/(1·2 ... ·a₂) > 1. Now given the result for 2 and n we have (a₁ + a₂ + ... + a_n+1)! > (a₁ + a₂ + ... + a_n)! a_n+1! > a₁! a₂! ... a_n+1!, which is the result for n+1.

Problem 2

P, Q, R are three points in space. The circle C_P passes through Q and R, the circle C_Q passes through R and P, and the circle C_R passes through P and Q. The tangents to C_Q and C_R at P coincide. Similarly, the tangents to C_R and C_P at Q coincide, and the tangents to C_P and C_Q at R coincide. Show that the circles are either coplanar or lie on the surface of the same sphere.

Solution

Let L be the common tangent to C_P and C_Q at R. Let π be the plane normal to L at R. Then the center O_P of C_P lies in π and so does the line L_P normal to the plane of the circle C_P at O_P. Similarly, we take O_Q to be the center of C_Q, and the line L_Q normal to the plane of the circle C_Q at O_Q. L_Q also lies in the plane π, so if L_P and L_Q do not meet then they must be parallel, so C_P and C_Q are coplanar. On the other hand if they meet at X, then X is equidistant from every point of C_P and also from every point of C_Q, so C_P and C_Q must lie on the sphere center X radius XR.

Similarly, C_Q and C_R are either coplanar or both lie on the surface of a sphere. If C_P and C_Q are coplanar, and C_Q and C_R are coplanar, then all three circles are coplanar. If C_P and C_Q lie on the surface of a sphere S and C_Q and C_R lie on the surface of a sphere S' ≠ S or lie in a plane S', then S ∩ S' must be C_Q. But C_P ∩ C_R = Q lies in S and S' and hence on C_Q. So P, Q, R are not distinct. Contradiction. Similarly if C_P and C_Q are coplanar and C_Q and C_R lie on the surface of a sphere. So the only remaining possibility is that all three circles lie on the same sphere.

Problem 3

A₁, A₂, ... , A_n are points in the plane, no three collinear. The points distinct P and Q in the plane do not coincide with any of the A_i and are such that PA₁ + ... + PA_n = QA₁ + ... + QA_n. Show that there is a point R in the plane such that RA₁ + ... + RA_n < PA₁ + ... + PA_n.

Solution

Take R to be the midpoint of PQ. If A lies inside the segment PQ, then RA < (PA + QA)/2. If A lies elsewhere on the line PQ, then RA = (PA + QA)/2. Now suppose A does not lie on the line PQ, then rotate A about R through 180^o to A', so that APA'Q is a parallelogram. Then 2 RA = AA' > AP + PA' = PA + QA, so RA > (PA + QA)/2. Since no three points are collinear, at least one A_i must lie off the line PQ, and for that point we have RA_i < (PA_i + QA_i)/2. For the others we certainly have RA_i ≤ (PA_i + QA_i)/2. So summing ∑ RA_i < &sum PA_i.

[Read More...]

40th Eötvös Competition Problems 1936

1.  Show that 1/(1·2) + 1/(3·4) + 1/(5·6) + ... + 1/( (2n-1)·2n) = 1/(n+1) + 1/(n+2) + ... + 1/(2n).

2.  ABC is a triangle. Show that, if the point P inside the triangle is such that the triangles PAB, PBC, PCA have equal area, then P must be the centroid.

3.  Given any positive integer N, show that there is just one solution to m + ½(m + n - 1)(m + n - 2) = N in positive integers. 

Solutions

Problem 1

Show that 1/(1·2) + 1/(3·4) + 1/(5·6) + ... + 1/( (2n-1)·2n) = 1/(n+1) + 1/(n+2) + ... + 1/(2n).

Solution

We have 1/( (2m-1)·2m) = 1/(2m-1) - 1/2m, so the sum is 1 - 1/2 + 1/3 - 1/4 + ... + 1/(2n-1) - 1/2n = h - k, where h = 1 + 1/3 + 1/5 + ... + 1/(2n-1), and k = 1/2 + 1/4 + ... + 1/2n. But h - k = (h+k) - 2k = (1 + 1/2 + 1/3 + ... + 1/2n) - (1 + 1/2 + 1/3 + ... + 1/n) = 1/(n+1) + 1/(n+2) + ... + 1/2n. 

Problem 2

ABC is a triangle. Show that, if the point P inside the triangle is such that the triangles PAB, PBC, PCA have equal area, then P must be the centroid.

Solution

Extend AP to meet BC at K. Then triangles PAB and PAC have the same base PA and ratio of heights BK/CK. Hence K is the midpoint of BC, so P lies on the median from A. Similarly, it lies on the other medians, so it must be the centroid. 

Problem 3

Given any positive integer N, show that the is just one solution to m + ½(m + n - 1)(m + n - 2) = N in positive integers.

Solution

Put T_r = ½r(r-1). So 1 = T₂ < T₃ < T₄ < ... . Also T_r+1 - T_r = r. Take r such that T_r < N ≤ T_r+1. Then 1 < N - T_r ≤ T_r+1 - T_r = r. Put m = N - T_r, then 1 ≤ m ≤ r. Put n = r+1-m, then 1 ≤ n, and r = m+n-1, so we have a solution as required. Now since m is positive, we cannot take r any larger. If we take it smaller, then we will have m > r and hence n = r+1-m ≤ 0, which is not allowed. So the solution is unique.

[Read More...]

39th Eötvös Competition Problems 1935

1.  x₁, x₂, ... , x_n is any sequence of positive reals and y_i is any permutation of x_i. Show that ∑ x_i/y_i ≥ n.

2.  S is a finite set of points in the plane. Show that there is at most one point P in the plane such that if A is any point of S, then there is a point A' in S with P the midpoint of AA'.

3.  Each vertex of a triangular prism is labeled with a real number. If each number is the arithmetic mean of the three numbers on the adjacent vertices, show that the numbers are all equal.

Solutions

Problem 1

x₁, x₂, ... , x_n is any sequence of positive reals and y_i is any permutation of x_i. Show that ∑ x_i/y_i ≥ n.

Solution

By AM/GM (∑ x_i/y_i)/n ≥ geometric mean of x_i/y_i which is 1 since ∏ x_i = ∏ y_i.

Problem 2

S is a finite set of points in the plane. Show that there is at most one point P in the plane such that if A is any point of S, then there is a point A' in S with P the midpoint of AA'.

Solution

The points must form disjoint pairs (A,A') with P the midpoint of each pair. But P is the centroid of each pair and hence the centroid of all the points, but that is a uniquely defined point. 

Problem 3

Each vertex of a triangular prism is labeled with a real number. If each number is the arithmetic mean of the three numbers on the adjacent vertices, show that the numbers are all equal.

Solution

We have 3a₁ = a₂ + a₃ + b₁, 3a₂ = a₁ + a₃ + b₂, 3a₃ = a₁ + a₂ + ba2 ₃. Adding gives a₁ + a₂ + a₃ = b₁ + b₂ + b₃. Hence (a₁ - b₁) = -(a₂ - b₂) - (a₃ - b₃) (*).

We also have 3b₁ = b₂ + b₃ + a₁. Subtracting from the first equation above, 4(a₁ - b₁) = (a₂ - b₂) + (a₃ - b₃). Adding (*) gives 5(a₁ - b₁) = 0. Hence a₁ = b₁. Similarly a₂ = b₂ and a₃ = b₃. But now the first two equations give 2a₁ = a₂ + a₃ and 2a₂ = a₁ + a₃, subtracting, 3(a₁ - a₂) = 0, so a₁ = a₂. Similarly a₂ = a₃. Hence all the numbers are equal.

[Read More...]

38th Eötvös Competition Problems 1934

1.  E is the product 2·4·6 ... 2n, and D is the product 1·3·5 ... (2n-1). Show that, for some m, D·2^m is a multiple of E.

2.  Given a circle, find the inscribed polygon with the largest sum of the squares of its sides.

3.  For i and j positive integers, let R_ij be the rectangle with vertices at (0, 0), (i, 0), (0, j), (i, j). Show that any infinite set of R_ij must have two rectangles one of which covers the other. 

Solutions

Problem 1

E is the product 2·4·6 ... 2n, and D is the product 1·3·5 ... (2n-1). Show that, for some m, D·2^m is a multiple of E.

Solution

We have D = (2n)!/(2ⁿ n!), so 2²ⁿD/E = 2nCn, which is an integer. 

Problem 2

Given a circle, find the inscribed polygon with the largest sum of the squares of its sides.

Solution

If there are more than 3 vertices, then the mean angle (between two adjacent sides) is ≥ 90^o, so there must be a vertex with angle ≥ 90^o. But now we can remove that vertex without increasing the sum of the squares.

So let us consider triangles.

Let M be the midpoint of BC. Applying the cosine formula to AMB and AMC and adding, we get AB² + AC² = 2AM² + 2BM². So if we keep B and C fixed and allow A to vary on the circle, then we maximize AB² + AC² by maximizing AM². But that is clearly achieved by taking AM to contain O the center of the circle (for AM² = AO² + OM² - 2·AO·OM cos AOM, which is maximized by taking ∠AOM = 180^o). Thus the triangle ABC is not optimal unless each pair of sides is equal, so the optimal triangle must be equilateral. Note that none of its sides are diameters, so the triangles we derive from any 4-gon must have smaller sum of squares, so no 4-gons are optimal. Since all n-gons are worse than 4-gons (since they have a vertex with angle > 90^o), no n-gon is optimal for n > 4. Thus the unique optimal polygons are the equilateral triangles. 

Problem 3

For i and j positive integers, let R_ij be the rectangle with vertices at (0, 0), (i, 0), (0, j), (i, j). Show that any infinite set of R_ij must have two rectangles one of which covers the other.

Solution

Take any rectangle R_ij. There are only finitely many rectangles R_mn with m ≤ i and n ≤ j. So there must be infinitely many with m > i or infinitely many with n > j. wlog we may assume there are infinitely many with m > i. They must all have n < j or they would contain R_ij. But there are only finitely many values for n available < j, so infinitely many must share some value n' < j. But now given any two of these, one contains the other.

[Read More...]

37th Eötvös Competition Problems 1933

1.  If x² + y² = u² + v² = 1 and xu + yv = 0 for real x, y, u, v, find xy + uv.

2.  S is a set of 16 squares on an 8 x 8 chessboard such that there are just 2 squares of S in each row and column. Show that 8 black pawns and 8 white pawns can be placed on these squares so that there is just one white pawn and one black pawn in each row and column.

3.  A and B are points on the circle C, which touches a second circle at a third point P. The lines AP and BP meet the second circle again at A' and B' respectively. Show that triangles ABP and A'B'P are similar.

Solutions

Problem 1

If x² + y² = u² + v² = 1 and xu + yv = 0 for real x, y, u, v, find xy + uv.

Solution

If u = 0, then v = ±1, and yv = 0, so y = 0. Hence xy + uv = 0. So assume u ≠ 0. Then x = yv/u. So 1 = x² + y² = y²(v²/u² + 1) = y²/u², so y = ±u. If y = u, then x + v = 0, so x = -v and hence xy + uv = 0. If y = -u, then -x + v = 0, so x = v and xy + uv = 0. So in all cases xy + uv = 0. 

Problem 2

S is a set of 16 squares on an 8 x 8 chessboard such that there are just 2 squares of S in each row and column. Show that 8 black pawns and 8 white pawns can be placed on these squares so that there is just one white pawn and one black pawn in each row and column.

Solution

Take a graph with 8 points r₁, ..., r₈ and 8 points c₁, ... , c₈. Join r_i and c_j iff the square in row r_i and column c_j of the chessboard is in S. Now every point of the graph has degree 2. We can partition the edges into disjoint cycles. For given any point P, just trace out a path from P. Eventually the path must reach a point Q already on the path. Q must be P, because otherwise it would have degree > 2. So P belongs to a cycle. But any two cycles must be disjoint or we would have a point with degree > 2. Since we must alternate between r-points and c-points as we go around a cycle, each cycle must have an even number of points. So we can label the edges around each cycle alternately black and white. Now every point must have one black and one white edge, so there must be one black and one white pawn in each row and column. 

Problem 3

A and B are points on the circle C, which touches a second circle at a third point P. The lines AP and BP meet the second circle again at A' and B' respectively. Show that triangles ABP and A'B'P are similar.

Solution

Let the centers of the circles be O, O'. Consider triangles OPA and O'PA'. There are isosceles and ∠OPA = ∠O'PA', so they are similar. Hence PA/PA' = OA/OA'. Similarly, PB/PB' = OB/OB', so PA/PA' = PB/PB'. But ∠APB = ∠A'PB'. Hence APB and A'PB' are similar.

[Read More...]

36th Eötvös Competition Problems 1932

1.  Show that if m is a multiple of aⁿ, then (a + 1)^m -1 is a multiple of aⁿ⁺¹.

2.  ABC is a triangle with AB and AC unequal. AM, AX, AD are the median, angle bisector and altitude. Show that X always lies between D and M, and that if the triangle is acute-angled, then angle MAX < angle DAX. 

3.  An acute-angled triangle has angles A < B < C. Show that sin 2A > sin 2B > sin 2C. 

Solutions

Problem 1

Show that if m is a multiple of aⁿ, then (a + 1)^m -1 is a multiple of aⁿ⁺¹.

Solution

We use induction on n. For n = 0 we have to show that (a+1)^m - 1 is a multiple of a. That is obvious if we expand by the binomial theorem. So suppose it is true for n. Put m = am', where m' is divisible by aⁿ. For convenience we also put A = a+1. Then we have A^m - 1 = (A^m' - 1)(A^m'(a-1) + A^m'(a-2) + ... + A^m' + 1). The first bracket is divisible by aⁿ⁺¹ by induction. The second bracket has a terms, so adding a and subtracting a 1s we can write it as a + (A^m'(a-1) - 1) + (A^m'(a-2) - 1) + ... + (A^m' - 1). Now each term is divisible by a and hence the sum is divisible by a. So A^m - 1 is divisible by aⁿ⁺² as required.

Problem 2

ABC is a triangle with AB and AC unequal. AM, AX, AD are the median, angle bisector and altitude. Show that X always lies between D and M, and that if the triangle is acute-angled, then angle MAX < angle DAX.

Solution

wlog ∠B > ∠C. So ∠B + ∠B + ∠A > ∠C + ∠B + ∠A = 180^o. Hence ∠B + ∠A/2 > 90^o. Hence ∠AXB = 180^o - ∠B - ∠A/2 < 90^o. So D must lie inside the segment BX. Since ∠B > ∠C, we have AC > AB. But CX/BX = AC/AB, so CX > BX. Hence M lies inside the segment CX. So X lies between D and M.

Let O be the circumcenter and N the midpoint of the arc BC. Then A, X, N are collinear. Since the triangle is acute-angled, O must lie on the opposite side of BC to N, so ∠MAN < ∠OAN = ∠DAN.

Problem 3

An acute-angled triangle has angles A < B < C. Show that sin 2A > sin 2B > sin 2C.

Solution

If 2B ≤ 90^o, then A+B < 2B ≤ 90^o, so C > 90^o. Contradiction. Also 2C < 180^o. Hence 2C > 2B > 90^o. But sin 2x is decreasing over this range, so sin 2B > sin 2C.

If 2A ≥ 90^o, then we have sin 2A > sin 2B for the same reason. So we need to consider the case 2A < 90^o < 2B. Since C < 90^o, we have A + B > 90^o and hence 2B > 180^o - 2A. Hence sin 2B < sin(180^o - 2A) = sin 2A.

[Read More...]

35th Eötvös Competition Problems 1931

1.  Prove that there is just one solution in integers m > n to 2/p = 1/m + 1/n for p an odd prime.

2.  Show that an odd square cannot be expressed as the sum of five odd squares.

3.  Find the point P on the line AB which maximizes 1/(AP + AB) + 1/(BP + AB). 

Solutions

Problem 1

Prove that there is just one solution in integers m > n to 2/p = 1/m + 1/n for p an odd prime.

Solution

We have 2/(2k+1) = 1/(k+1) + 1/((k+1)(2k+1)) for any odd 2k+1, so there is certainly at least one solution.

Suppose 2/p = 1/m + 1/n, then 2mn = p(m+n), so p divides 2mn. But p is odd, so p must divide mn. It is prime, so it must divide m or n. If it divides n, then n ≥ p. But m > n, so m > p. Hence 1/m + 1/n < 1/p + 1/p. Contradiction. So p divides m. Put m = kp. Then 1/n = 2/p - 1/kp = (2k-1)/kp. But k and 2k-1 have no common factor, so 2k-1 must divide p. But p is prime, so p = 2k-1 and n = 1/k. Thus we have a unique solution. 

Problem 2

Show that an odd square cannot be expressed as the sum of five odd squares.

Solution

An odd square must be 1 mod 8. So the sum of five odd squares is 5 mod 8 and cannot be a square. 

Problem 3

Find the point P on the line AB which maximizes 1/(AP + AB) + 1/(BP + AB).

Solution

wlog AB = 1. P must lie on the segment AB, for otherwise we can reduce both AP and BP by moving P closer to the segment. So take P on the segment a distance x from A. Then we want to maximize 1/(1+x) + 1/(2-x) = 3/(2+x-x²) subject to 0 ≤ x ≤ 1. But 2+x-x² = 9/4 - (x - 1/2)², so we minimize the quadratic by taking x = 0 or 1. In other words we maximize the required expression by taking P = A or B.

[Read More...]

34th Eötvös Competition Problems 1930

1.  How many integers (1) have 5 decimal digits, (2) have last digit 6, and (3) are divisible by 3?

2.  A straight line is drawn on an 8 x 8 chessboard. What is the largest possible number of the unit squares with interior points on the line?

3.  An acute-angled triangle has circumradius R. Show that any interior point of the triangle other than the circumcenter is a distance > R from at least one vertex and a distance < R from at least one vertex. 

Solutions

Problem 1

How many integers (1) have 5 decimal digits, (2) have last digit 6, and (3) are divisible by 3?

Solution
We can write the number as d₄d₃d₂d₁6. There are 10 choices for each of d₁, d₂, d₃. Now if the digit sum of the other digits is 0, d₄ must be 3, 6 or 9. If it is 1, d₄ must be 2, 5 or 8. If it is 2, d₄ must be 1, 4, or 7. So in any case we have three choices for d₄. Hence 3000 possibilities in all. 

Problem 2

A straight line is drawn on an 8 x 8 chessboard. What is the largest possible number of the unit squares with interior points on the line?

Solution

There are 14 internal grid lines. The line can cross each one at most once, so it can make a total of at most 14 crossings. But one crossing is required each time it changes unit square, so at most 1+14 = 15 squares. But 15 is certainly possible - take a line parallel to a main diagonal and close to it. 

Problem 3

An acute-angled triangle has circumradius R. Show that any interior point of the triangle other than the circumcenter is a distance > R from at least one vertex and a distance < R from at least one vertex.

Solution

Since the triangle is acute-angled, the circumcenter O must lie inside the triangle. So it must lie in (or on) one of the triangles PAB, PBC, PCA. Suppose it lies in PAB. Then PA + PB > OA + OB = 2R, so either PA or PB >R. Similarly, P must lie inside one of the triangles OAB, OBC, OCA and so one of the distances <R.

[Read More...]

33rd Eötvös Competition Problems 1929

1.  Coins denomination 1, 2, 10, 20 and 50 are available. How many ways are there of paying 100?

2.  Show that ∑_{i=0 to k} nCi (-x)ⁱ is positive for all 0 ≤ x < 1/n and all k ≤ n, where nCi is the binomial coefficient.

3.  L, M, N are three lines through a point such that the angle between any pair is 60^o. Show that the set of points P in the plane of ABC whose distances from the lines L, M, N are less than a, b, c respectively is the interior of hexagon iff there is a triangle with sides a, b, c. Find the perimeter of this hexagon. 

Solutions

Problem 1

Coins denomination 1, 2, 10, 20 and 50 are available. How many ways are there of paying 100?

Solution

For 2n there are n+1 ways using just the 1 and 2 coins (0, 1, 2, ... or n 2s). Similarly, there are m+1 ways of paying 20m or 20m+10 with just the 10 and 20 coins. Hence using just the 10, 20, 50 coins we get (for example there are 4 ways of paying 70 without using a 50 and 2 ways with, total 6):

0  10  20  30  40  50  60  70  80  90  100
0   1   2   2   3   4   5   6   7   8   10

Hence there are 1·51 + 1·46 + 2·41 + 2·36 + 3·31 + 4·26 + 5·21 + 6·16 + 7·11 + 8·6 + 10·1 = 784 ways in total. 

Problem 2

Show that ∑_{i=0 to k} nCi (-x)ⁱ is positive for all 0 ≤ x < 1/n and all k ≤ n, where nCi is the binomial coefficient.

Solution

The sum is (1 - nx) + (nC1 - nC2 x)x² + (nC3 - nC4 x)x⁴ + ... . There may be an unpaired term at the end, but if so it is non-negative. A typical bracket is nCi(1 - x(n-i)/(i+1) ) > nCi (1 - 1/(i+1) ) > 0. So the sum is positive. 

Problem 3

L, M, N are three lines through a point such that the angle between any pair is 60^o. Show that the set of points P in the plane of ABC whose distances from the lines L, M, N are less than a, b, c respectively is the interior of hexagon iff there is a triangle with sides a, b, c. Find the perimeter of this hexagon.

Solution

P must lie in the strip a distance a either side of L and in the strip a distance b either side of M. So it must lie in the parallelogram PQRS. It must also lie in the strip a distance c either side of N. So we evidently require that AB lies between P and N. Put k = 2/√3. Then QR = 2ka (since the angles are all 60^o). Similarly, PQ = 2kb. Also AQ + QC = 2kc, so PA + CR = 2k(a+b-c). But PA = CR by symmetry and PAB is equilateral, so AB = k(a+b-c). We get a hexagon iff PA = k(a+b-c) > 0 and similar conditions apply if we consider the strip about M relative to the parallelogram given by the strips about L and N, or the strip L about relative to the third parallelogram. Thus we require c < a+b, b < c+a, a < b+c, or a, b, c to form a triangle.

We have also shown that the perimeter of the hexagon is 2k(a+b-c) + 2k(b+c-a) + 2k(c+a-b) = 2k(a+b+c).

[Read More...]

32nd Eötvös Competition Problems 1928

1.  Show that for any real x, at least one of x, 2x, 3x, ... , (n-1)x differs from an integer by no more than 1/n.

2.  The numbers 1, 2, ... , n are arranged around a circle so that the difference between any two adjacent numbers does not exceed 2. Show that this can be done in only one way (treating rotations and reflections of an arrangement as the same arrangement).

3.  Given two points A, B and a line L in the plane, find the point P on the line for which max(AP, BP) is as short as possible. 

Solutions

Problem 1

Show that for any real x, at least one of x, 2x, 3x, ... , (n-1)x differs from an integer by no more than 1/n.

Solution

For i = 1, 2, ... , n let S_i = {y | (i-1)/n ≤ [y] < i/n}. We wish to show that one of the given n-1 points belongs to S¹ or Sⁿ. Suppose not. Then they belong to the n-2 sets S², S³, ... , S^n-1. So two of them rx and sx must belong to the same Si. But now |r-s|x belongs to S₁ or S_n. Contradiction. 

Problem 2

The numbers 1, 2, ... , n are arranged around a circle so that the difference between any two adjacent numbers does not exceed 2. Show that this can be done in only one way (treating rotations and reflections of an arrangement as the same arrangement).

Solution

The unique solution is 1,3,5, ... ,largest odd, largest even, ... , 6, 4, 2.

Start with 1. Its neighbors must be 2 and 3. Now only 4 is available to go on the other side of 2, now only 5 is available to go next to 3, now only 6 is available to go next to 4, and so on. 

Problem 3

Given two points A, B and a line L in the plane, find the point P on the line for which max(AP, BP) is as short as possible.

Solution

Let B be the point further from the line (or one of them). Let B' be the foot of the perpendicular from B to the line. If BB' > AB', then we must obviously take P = B'. If not, then let X be the point where the perpendicular bisector of AB meets the line. We take P to be X. For X must lie between A' and B'. If we take P to the right of X then max(AP,BP) = AP and AP > AX. If we take P to the left of X, then max(AP, BP) = BP and BP > BX.

[Read More...]

31st Eötvös Competition Problems 1927

1.  a, b, c, d are each relatively prime to n = ad - bc, and r and s are integers. Show ar + bs is a multiple of n iff cr + ds is a multiple of n.

2.  Find the sum of all four digit numbers (written in base 10) which contain only the digits 1 - 5 and contain no digit twice.

3.  r is the inradius of the triangle ABC and r' is the exradius for the circle touching AB. Show that 4r r' ≤ c², where c is the length of the side AB. 

Solutions

Problem 1

a, b, c, d are each relatively prime to n = ad - bc, and r and s are integers. Show ar + bs is a multiple of n iff cr + ds is a multiple of n.

Solution

d(ar+bs) - b(cr+ds) = (ad-bc)r = nr, so if (ar+bs) is a multiple of n, then so is b(cr+ds). But b is relatively prime to n, so (cr+ds) is a multiple of n. Similarly, if (cr+ds) is a multiple of n, then so is d(ar+bs) and hence (ar+bs). 

Problem 2

Find the sum of all four digit numbers (written in base 10) which contain only the digits 1 - 5 and contain no digit twice.

Solution

Denote the digits as d₃d₂d₁d₀. If we fix d₀ = k, then there are 4·3·2 ways of choosing the other digits, so there are 24 such numbers. The sum of their d₀ digits is 24k. Thus the sum of the d₀ digits for all the numbers is 24(1+2+3+4+5) = 24·15 = 360. A similar argument works for the other digits, so the sum of the numbers is 360(1+10+100+1000) = 399960. 

Problem 3

r is the inradius of the triangle ABC and r' is the exradius for the circle touching AB. Show that 4r r' ≤ c², where c is the length of the side AB.

Solution

Let the incenter be I and the relevant excenter be E. Then ∠IAE = ∠IBE = 90^o, so AIBE is cyclic. Let the center of the circle through A,I,B,E be C. Then r = IP, r' = EQ. But IP·EQ ≤ XZ·ZY, where XY is the diameter perpendicular to AB. We have XZ·ZY = AZ·ZB = c²/4.

[Read More...]

30th Eötvös Competition Problems 1926

1.  Show that for any integers m, n the equations w + x + 2y + 2z = m, 2w - 2x + y - z = n have a solution in integers.

2.  Show that the product of four consecutive integers cannot be a square.

3.  A circle or radius R rolls around the inside of a circle of radius 2R, what is the path traced out by a point on its circumference? 

Solutions

Problem 1

Show that for any integers m, n the equations w + x + 2y + 2z = m, 2w - 2x + y - z = n have a solution in integers.

Solution

w = n, x = m+n, y = m, z = -(m+n). 

Problem 2

Show that the product of four consecutive integers cannot be a square.

Solution

(n-1)n(n+1)(n+2) = (n²+n)(n²+n-2) = (n²+n-1)² - 1. Any two squares differ by more than 1, so it cannot be a square. 

Problem 3

A circle or radius R rolls around the inside of a circle of radius 2R, what is the path traced out by a point on its circumference?

Solution

The the rolling circle have center O' and the large circle have center O. Suppose the initial point of contact is A. Let A' be the point of the rolling circle that is initially at A. When the contact has moved to B, take ∠AOB = θ. Then since the small circle has half the radius, ∠A'OB = 2θ. Hence ∠O'OA' = θ, so A' lies on OA. Equally it is clear that it can reach any point on the diameter AC.

[Read More...]