15th Swedish Mathematical Society Problems 1975

1.  A is the point (1, 0), L is the line y = kx (where k > 0). For which points P (t, 0) can we find a point Q on L such that AQ and QP are perpendicular?

2.  Is there a positive integer n such that the fractional part of (3 + √5)ⁿ > 0.99?

3.  Show that aⁿ + bⁿ + cⁿ ≥ ab^n-1 + bc^n-1 + ca^n-1 for real a, b, c ≥ 0 and n a positive integer.

4.  P₁, P₂, P₃, Q₁, Q₂, Q₃ are distinct points in the plane. The distances P₁Q₁, P₂Q₂, P₃Q₃ are equal. P₁P₂ and Q₂Q₁ are parallel (not antiparallel), similarly P₁P₃ and Q₃Q₁, and P₂P₃ and Q₃Q₂. Show that P₁Q₁, P₂Q₂ and P₃Q₃ intersect in a point.

5.  Show that n divides 2ⁿ + 1 for infinitely many positive integers n.

6.  f(x) is defined for 0 ≤ x ≤ 1 and has a continuous derivative satisfying |f '(x)| ≤ C |f(x)| for some positive constant C. Show that if f(0) = 0, then f(x) = 0 for the entire interval. 

Solutions

Problem 2

Is there a positive integer n such that the fractional part of (3 + √5)ⁿ > 0.99?

Answer

yes

Solution

Expanding by the binomial theorem we see that (3 + √5)ⁿ + (3 - √5)ⁿ is an integer, but 0 < (3 - √5) < 1, so (3 - √5)ⁿ < 0.01 for sufficiently large n.

Thanks to Suat Namli

Problem 3

Show that aⁿ + bⁿ + cⁿ ≥ ab^n-1 + bc^n-1 + ca^n-1 for real a, b, c ≥ 0 and n a positive integer.

Solution

By AM/GM (aⁿ + bⁿ + bⁿ + ... + bⁿ)/n ≥ ab^n-1. Similarly (bⁿ + cⁿ + cⁿ + ... + cⁿ)/n ≥ bc^n-1 and (cⁿ + aⁿ + aⁿ + ... + aⁿ)/n ≥ ca^n-1. Adding gives the result.

Thanks to Suat Namli

Problem 5

Show that n divides 2ⁿ + 1 for infinitely many positive integers n.

Solution

For n = 3 we have 2ⁿ + 1 = 9 which is a multiple of 3. Now we have 2^3k + 1 = (2^k + 1)(2^2k - 2^k + 1), so if 2^k + 1 = 0 mod 3, then 2^2k = 1 mod 3, so 2^2k - 2^k + 1 = 1 + 1 + 1 = 0 mod 3. So if 3^h divides 2^k + 1, then 3^h+1 divides 2^3k + 1. Hence (by a trivial induction) for n = 3^k, n divides 2ⁿ + 1.

Thanks to Suat Namli

[more...]

14th Swedish Mathematical Society Problems 1974

1.  Let a_n = 2^n-1 for n > 0. Let b_n = ∑_r+s≤n a_ra_s. Find b_n - b_n-1, b_n - 2b_n-1 and b_n.

2.  Show that 1 - 1/k ≤ n(k^1/n - 1) ≤ k - 1 for all positive integers n and positive reals k.

3.  Let a₁ = 1, a₂ = 2^a₁, a₃ = 3^a₂, a₄ = 4^a₃, ... , a₉ = 9^a₈. Find the last two digits of a₉.

4.  Find all polynomials p(x) such that p(x²) = p(x)² for all x. Hence find all polynomials q(x) such that q(x² - 2x) = q(x-2)².

5.  Find the smallest positive real t such that x₁ + x₃ = 2t x₂, x₂ + x₄ = 2t x₃, x₃ + x₅ = 2t x₄ has a solution x₁, x₂, x₃, x₄, x₅ in non-negative reals, not all zero.

6.  For which n can we find positive integers a₁, a₂, ... , a_n such that a₁² + a₂² + ... + a_n² is a square? 

Solutions

Problem 2

Show that 1 - 1/k ≤ n(k^1/n - 1) ≤ k - 1 for all positive integers n and positive reals k.

Solution

AM/GM applied to k, 1, ... , 1 gives k^1/n ≤ (k+n-1)/n, so n(k^1/n - 1) ≤ k-1, which is second inequality.

AM/GM applied to k^(n+1)/n, k^(n+1)/n, ... , k^(n+1)/n, 1 (n+1 terms in all) gives k ≤ (n k^(n+1)/n + 1)/(n+1), or (n+1)k - 1 ≤ n k^(n+1)/n or 1 - 1/k ≤ n k^1/n - n, which is the first inequality.

Thanks to Suat Namli

Problem 3

Let a₁ = 1, a₂ = 2^a₁, a₃ = 3^a₂, a₄ = 4^a₃, ... , a₉ = 9^a₈. Find the last two digits of a₉.

Answer

21

Solution

Working mod 100, we find 9¹ = 9, 9² = 81, 9³ = 29, 9⁴ = 61, 9⁵ = 49, 9⁶ = 41, 9⁷ = 69, 9⁸ = 21, 9⁹ = 89, 9¹⁰ = 1, 9¹¹ = 9, so periodic period 10. Thus we only need to find the last digit of a₈. Working mod 10 we find 8¹ = 8, 8² = 4, 8³ = 2, 8⁴ = 6, 8⁵ = 8, 8⁶ = 4, so periodic period 4. Thus we need to find a₇ mod 4. We find 7¹ = 3, 7² = 1, 7³ = 3, so periodic period 2. Now a6 is obviously even, so a₇ = 1 mod 4. Hence a₈ = 8 mod 10. Hence a₉ = 21 mod 100. 

Problem 5

Find the smallest positive real t such that x₁ + x₃ = 2t x₂, x₂ + x₄ = 2t x₃, x₃ + x₅ = 2t x₄ has a solution x₁, x₂, x₃, x₄, x₅ in non-negative reals, not all zero.

Answer

1/√2

Solution

It is easy to check that x₁ = x₅ = 0, x₂ = x₄ = 1, x₃ = √2, t = 1/√2 works.

Suppose for some t we have a solution x_i. Then 0 = 2tx₂ + 2tx₄ - 4t²x₃ = x₁ + 2x₃ + x₅ - 4t²x₃. Hence x₃ = 0 or 4t² - 2 = (x₁ + x₅)/x₃ ≥ 0. If x₃ = 0, then x₂ + x₄ = 0, so x₂ = x₄ = 0. Hence x₁ + x₃ = 0 and x₃ + x₅ = 0, so all x_i = 0. Contradiction. So we must have 4t² - 2 ≥ 0 and hence t ≥ 1/√2. 

Problem 6

For which n can we find positive integers a₁, a₂, ... , a_n such that a₁² + a₂² + ... + a_n² is a square?

Answer

all positive n

Solution

Take a₁ = 3, a_n+1 = (a₁² + a₂² + ... + a_n² - 1)/2. For put b_n = a₁² + a₂² + ... + a_n². We show by induction that bn is an odd square. True for 1. Suppose true for n, then a_n+1 = (b_n - 1)/2, which is even, since odd squares are 1 mod 4. Hence b_n+1 = b_n + a_n+1² = (b_n² - 2b_n + 1 + 4b_n)/4 = ((b_n + 1)/2)², which is an odd square.

Thanks to Suat Namli

[more...]

13th Swedish Mathematical Society Problems 1973

1.  log₈2 = 0.2525 in base 8 (to 4 places of decimals). Find log₈4 in base 8 (to 4 places of decimals).

2.  The Fibonacci sequence f₁, f₂, f₃, ... is defined by f₁ = f₂ = 1, f_n+2 = f_n+1 + f_n. Find all n such that f_n = n².

3.  ABC is a triangle with ∠A = 90^o, ∠B = 60^o. The points A₁, B₁, C₁ on BC, CA, AB respectively are such that A₁B₁C₁ is equilateral and the perpendiculars (to BC at A₁, to CA at B₁ and to AB at C₁) meet at a point P inside the triangle. Find the ratios PA₁:PB₁:PC₁.

4.  p is a prime. Find all relatively prime positive integers m, n such that m/n + 1/p² = (m + p)/(n + p).

5.  f(x) is a polynomial of degree 2n. Show that all polynomials p(x), q(x) of degree at most n such that f(x)q(x) - p(x) has the form ∑_2n<k≤3n (a^k + x^k), have the same p(x)/q(x).

6.  f(x) is a real valued function defined for x ≥ 0 such that f(0) = 0, f(x+1) = f(x) + √x for all x, and f(x) < ½ f(x - ½) + ½ f(x + ½) for all x ≥ ½. Show that f(½) is uniquely determined. 

Solutions

Problem 1

log₈2 = 0.2525 in base 8 (to 4 places of decimals). Find log₈4 in base 8 (to 4 places of decimals).

Answer

0.5253

Solution

log₈4 = 1 - log₈2 

Problem 2

The Fibonacci sequence f₁, f₂, f₃, ... is defined by f₁ = f₂ = 1, f_n+2 = f_n+1 + f_n. Find all n such that f_n = n².

Answer

12

Solution

The first few values are f₁ = 1, f₂ = 1, f₃ = 2, f₄ = 3, f₅ = 5, f₆ = 8, f₇ = 13, f₈ = 21, f₉ = 34, f₁₀ = 55, f₁₁ = 89, f₁₂ = 144, f₁₃ = 233, f₁₄ = 377. Note that the only solution to f_n = n² for n ≤ 12 is n = 12. We claim that f_n > n² for n ≥ 13. It is true for n = 13, 14. Suppose it is true for n, n+1, then f_n+2 > (n+1)² + n² = 2n² + 2n + 1. But n²-2n-3 = (n-3)(n+1) > 0, so 2n²+2n+1 > n²+4n+4 = (n+2)², so the result is true for n+2 and hence for all n ≥ 13.

Thanks to Suat Namli

Problem 4

p is a prime. Find all relatively prime positive integers m, n such that m/n + 1/p² = (m + p)/(n + p).

Answer

for p = 2, (m,n) = (1,2) or (1,4) for p > 2, (m,n) = (p²-p-1,p²).

Solution

Multiplying across we get (n-m)p³ = n(n+p). But n is prime to n-m, so n must divide p³. If n = 1, then p³ divides p+1. Contradiction. If n = p, then p² divides 2p, so p = 2, so m = 1. If n = p², then n-m = p+1, so m = p²-p-1. If n = p³, then p³-m = p³+p, which is impossible since m and p are both positive.

[more...]

12th Swedish Mathematical Society Problems 1972

1.  Find the largest real number a such that x - 4y = 1, ax + 3y = 1 has an integer solution.

2.  A rectangular grid of streets has m north-south streets and n east-west streets. For which m, n > 1 is it possible to start at an intersection and drive through each of the other intersections just once before returning to the start?

3.  A steak temperature 5^o is put into an oven. After 15 minutes, it has temperature 45^o. After another 15 minutes it has temperature 77^o. The oven is at a constant temperature. The steak changes temperature at a rate proportional to the difference between its temperature and that of the oven. Find the oven temperature.

4.  Put x = log₁₀2, y = log₁₀3. Then 15 < 16 implies 1 - x + y < 4x, so 1 + y < 5x. Derive similar inequalities from 80 < 81 and 243 < 250. Hence show that 0.47 < log₁₀3 < 0.482.

5.  Show that ∫ ₀¹ (1/(1 + xⁿ)) dx > 1 - 1/n for all positive integers n.

6.  a₁, a₂, a₃, ... and b₁, b₂, b₃, ... are sequences of positive integers. Show that we can find m < n such that a_m ≤ a_n and b_m ≤ b_n. 

Solutions

Problem 1

Find the largest real number a such that x - 4y = 1, ax + 3y = 1 has an integer solution.

Answer

1

Solution

For a = 1, we have x = 1, y = 1. Suppose a > 1. Then a(4y+1) = 1-3y, so y = -(a-1)/(4a+3) < 0. But a-1 < 4a+3 (since a is positive), so y > -1. Contradiction. So there are no solutions with a > 1.

Thanks to Suat Namli

Problem 2

A rectangular grid of streets has m north-south streets and n east-west streets. For which m, n > 1 is it possible to start at an intersection and drive through each of the other intersections just once before returning to the start?

Answer

mn even

Solution

Suppose a path is possible. Let N,S,E,W be the number of moves north, south, east, west. Then the total number of moves N + S + E + W = mn. Since the path is closed we have E = W and N = S. Hence N + S + E + W is even and hence mn is even.

wlog suppose n is even. The diagram shows one way of making the drive using a comb shape.

Problem 3

A steak temperature 5^o is put into an oven. After 15 minutes, it has temperature 45^o. After another 15 minutes it has temperature 77^o. The oven is at a constant temperature. The steak changes temperature at a rate proportional to the difference between its temperature and that of the oven. Find the oven temperature.

Answer

205^o

Solution

The steak temperature is obviously A - Be^-kt, where A is the oven temperature, B and k are constants and t is the time. (One can write down the differential equation and solve it). Put h = e^-15k.

So we have A - B = 5, A - Bh = 45, A - Bh2 = 77. Subtracting, B(1 - h) = 40, Bh(1 - h) = 32. Hence h = 4/5, B = 200, A = 205.

Problem 5

Show that ∫ ₀¹ (1/(1 + xⁿ)) dx > 1 - 1/n for all positive integers n.

Solution

We have 1/(1+xⁿ) = 1 - xⁿ/(1+xⁿ) > 1 - xⁿ (for x in (0,1)). Hence ∫ ₀¹ (1/(1 + xⁿ)) dx > 1 - ∫ ₀¹ xⁿ dx = 1 - 1/(n+1) > 1 - 1/n.

Thanks to Thomas Linhart

[more...]

11th Swedish Mathematical Society Problems 1971

1.  Show that (1 + a + a²)² < 3(1 + a² + a⁴) for real a ≠ 1.

2.  An arbitrary number of lines divide the plane into regions. Show that the regions can be colored red and blue so that neighboring regions have different colors.

3.  A table is covered by 15 pieces of paper. Show that we can remove 7 pieces so that the remaining 8 cover at least 8/15 of the table.

4.  Find (65533³ + 65534³ + 65535³ + 65536³ + 65537³ + 65538³+ 65539³)/(32765·32766 + 32767·32768 + 32768·32769 + 32770·32771).

5.  Show that max_|x|≤t |1 - a cos x| ≥ tan²(t/2) for a positive and t ∈ (0, π/2).

6.  99 cards each have a label chosen from 1, 2, ... , 99, such that no (non-empty) subset of the cards has labels with total divisible by 100. Show that the labels must all be equal. 

Solutions

Problem 1

Show that (1 + a + a²)² < 3(1 + a² + a⁴) for real a ≠ 1.

Solution

We have a² + a + 1 = (a + 1/2)² + 3/4 > 0. So for a ≠ 1, we have 0 < (a - 1)²(a² + a + 1) = (a - 1)(a³ - 1) = a⁴ - a³ - a + 1. Hence 2(1 + a⁴) > 2a(1 + a²), so (1 + a + a²)² = 1 + 2a + 3a² + 2a³ + a⁴ < 3(1 + a² + a⁴). 

Problem 2

An arbitrary number of lines divide the plane into regions. Show that the regions can be colored red and blue so that neighboring regions have different colors.

Solution

Induction on the number of lines. Obvious for 1 line. Suppose true for n lines. Now add the n+1st line and change the color of every region on one side of the new line. 

Problem 4

Find (65533³ + 65534³ + 65535³ + 65536³ + 65537³ + 65538³+ 65539³)/(32765·32766 + 32767·32768 + 32768·32769 + 32770·32771).

Answer

7·2¹⁶

Solution

Put N = 65536 = 2¹⁶. Then numerator = (N-3)³ + (N-2)³ + (N-1)³ + N³ + (N+1)³ + (N+2)³ + (N+3)³ = ((N-3)³ + (N+3)³) + ((N-2)³ + (N+2)³) + ((N-1)³ + (N+1)³) + N³ = 2(N³ + 27N) + 2(N³ + 12N) + 2(N³ + 3N) + N³ = 7(N³ + 12N).

Put M = N/2 = 32768. Denominator = (M-3)(M-2) + (M-1)M + M(M+1) + (M+2)(M+3) = 4M² + 12 = N² + 12. Hence expr = 7N. 

Problem 6

99 cards each have a label chosen from 1, 2, ... , 99, such that no (non-empty) subset of the cards has labels with total divisible by 100. Show that the labels must all be equal.

Solution

Let the labels be a₁, a₂, ... , a₉₉. Use cyclic subscripts so a₁₀₀ means a₁, a₁₀₁ means a₂ etc. The 99 sums a_i, a_i + a_i+1, a_i + a_i+1 + a_i+2, ... , a_i + a_i+1 + ... + a_i+98 must all be non-zero mod 100 and all unequal (otherwise their difference would give a subset with zero sum mod 100). So one of them must equal -a_i-1 mod 100. If it is any but the last, then a_i-1 + a_i + ... + a_i+k gives a subset with sum 0 mod 100. So it must be the last. In other words a_i-1 = -(a_i + a_i+1 + ... + a_i+98). But this is independent of i because a_i + a_i+1 + ... + a_i+98 = a₁ + a₂ + ... + a₉₉. So a_i-1 are all equal mod 100 and hence are all equal.

[more...]

10th Swedish Mathematical Society Problems 1970

1.  Show that infinitely many positive integers cannot be written as a sum of three fourth powers of integers.

2.  6 open disks in the plane are such that the center of no disk lies inside another. Show that no point lies inside all 6 disks.

3.  A polynomial with integer coefficients takes the value 5 at five distinct integers. Show that it does not take the value 9 at any integer.

4.  Let p(x) = (x - x₁)(x - x₂)(x - x₃), where x₁, x₂ and x₃ are real. Show that p(x) p''(x) ≤ p'(x)² for all x.

5.  A 3 x 1 paper rectangle is folded twice to give a square side 1. The square is folded along a diagonal to give a right-angled triangle. A needle is driven through an interior point of the triangle, making 6 holes in the paper. The paper is then unfolded. Where should the point be in order to maximise the smallest distance between any two holes?

6.  Show that (n - m)!/m! ≤ (n/2 + 1/2)^n-2m for positive integers m, n with 2m ≤ n. 

Solutions

Problem 1

Show that infinitely many positive integers cannot be written as a sum of three fourth powers of integers.

Solution

Squares must be 0 or 1 mod 4, so any number = 3 mod 4 is not even the sum of three squares. 

Problem 3

A polynomial with integer coefficients takes the value 5 at five distinct integers. Show that it does not take the value 9 at any integer.

Solution

The polynomial can be written as (x-a)(x-b)(x-c)(x-d)(x-e)q(x) + 5 for some distinct integers a, b, c, d, e. Now let x be any other integer (not a, b, c, d, e). If q(x) = 0, then the value is 5, not 9. If q(x) ≠ 0, then |q(x)| ≥ 1. At most two of |x-a|, |x-b|, |x-c|, |x-d|, |x-e| can be 1 and at most two can be 2. So their product is certainly > 4. But to get 9 we must have (x-a)(x-b)(x-c)(x-d)(x-e)q(x) = 4. 

Problem 6

Show that (n - m)!/m! ≤ (n/2 + 1/2)^n-2m for positive integers m, n with 2m ≤ n.

Solution

Put n = 2m+r, so we have to show that (m+r)(m+r-1)...(m+1) ≤ (m + (r+1)/2)^r. But this is just AM/GM applied to m+r, ... m+1.

Thanks to Suat Namli

[more...]

9th Swedish Mathematical Society Problems 1969

1.  Find all integers m, n such that m³ = n³ + n.

2.  Show that tan π/3n is irrational for all positive integers n.

3.  a₁ ≥ a₂ ≥ ... ≥ a_n is a sequence of reals. b₁, b₂, b₃, ... b_n is any rearrangement of the sequence B₁ ≥ B₂ ≥ ... ≥ B_n. Show that ∑ a_ib_i ≤ &sum a_iB_i.

4.  Define g(x) as the largest value of |y² - xy| for y in [0, 1]. Find the minimum value of g (for real x).

5.  Let N = a₁a₂ ... a_n in binary. Show that if a₁ - a₂ + a₃ - ... + (-1)^n-1a_n = 0 mod 3, then N = 0 mod 3.

6.  Given 3n points in the plane, no three collinear, is it always possible to form n triangles (with vertices at the points), so that no point in the plane lies in more than one triangle? 

Solutions

Problem 1

Find all integers m, n such that m³ = n³ + n.

Answer

m = n = 0.

Solution

n and n² + 1 are relatively prime, so both must be cubes. Hence n² is also a cube. But the only consecutive integers which are both cubes are 0 and 1. 

Problem 2

Show that tan π/3n is irrational for all positive integers n.

Solution

tan π/3 = √3, which is irrational by the usual argument. (If √3 = a/b in lowest terms, then 3b² = a², so 3 must divide a and hence b. Contradiction.).

Now cos nx + i sin nx = (cos x + i sin x)ⁿ. Put c = cos x, s = sin x, t = tan x. Expanding by the binomial theorem and equating real and imaginary parts, we get sin nx = nC1 c^n-1s - nC3 c^n-3s³ + ... , cos nx = cⁿ - nC2 c^n-2s² + ... . Hence tan nx = (nC1 t - nC3 t³ + ... )/(1 - nC2 t² + ... ). Hence if t is rational, then so is tan nx. But tan π/3 is irrational, so tan π/3n must also be irrational. 

Problem 3

a₁ ≥ a₂ ≥ ... ≥ a_n is a sequence of reals. b₁, b₂, b₃, ... b_n is any rearrangement of the sequence B₁ ≥ B₂ ≥ ... ≥ B_n. Show that ∑ a_ib_i ≤ &sum a_iB_i.

Solution

This is the well-known rearrangement inequality. Let S = ∑ a_ib_i. Let S' be the sum after swapping b_i and b_j. Then S' - S = (a_i - a_j)(b_j - b_i). So if i ≤ j, then a_i - a_j ≥ 0, so S' - S has the same sign as b_j - b_i. In other words, we get the largest sum if the bs are sorted the same way as the as. 

Problem 4

Define g(x) as the largest value of |y² - xy| for y in [0, 1]. Find the minimum value of g (for real x).

Answer

3 - √8

Solution

y² - xy = (y - x/2)² - x2/4, so y² - xy has a minimum at y = x/2. It is decreasing for y < x/2 and increasing for y > x/2. Thus the largest value of y² - xy must be at y = 0, x/2 or 1. The values there are 0, x²/4, |1-x|. So for x outside the interval (0,1), g(x) ≥ 1/4. For x ∈ (0,1) we have g(x) = max(x²/4, 1-x). The quadratic x² + 4x - 4 = 0 has roots -2 ± √8, which are approx and -4.83 and 0.83. Hence g(x) = 1-x for x ≤ √8 - 2, and x²/4 for x ≥ √8 - 2, and the minimum value of g(x) in the interval (0,1) is g(√8 - 2) = 3 - √8, which is approx 0.18 and < 1/4. Thus this is also the minimum value of g(x) for all x. 

Problem 5

Let N = a₁a₂ ... a_n in binary. Show that if a₁ - a₂ + a₃ - ... + (-1)^n-1a_n = 0 mod 3, then N = 0 mod 3.

Solution

We have N = a₁2^n-1 + a₂2^n-2 + ... + a_n = a₁(-1)^n-1 + a₂(-1)^n-2 + ... + a_n = (-1)^n-1(a₁ - a₂ + a₃ - ... + (-1)^n-1a_n) = 0 mod 3. 

Problem 6

Given 3n points in the plane, no three collinear, is it always possible to form n triangles (with vertices at the points), so that no point in the plane lies in more than one triangle?

Answer

Yes

Solution

Take a slope different from that of the line joining any two of the points. Now divide the points into groups of three by parallel lines of that slope. (Start with a line distant from all the points and move it gradually towards the points, without changing its slope. It crosses the points one at a time.) Now join the points in each group.

[more...]

8th Swedish Mathematical Society Problems 1968

1.  Find the maximum and minimum values of x² + 2y² + 3z² for real x, y, z satisfying x² + y² + z² = 1.

2.  How many different ways (up to rotation) are there of labeling the faces of a cube with the numbers 1, 2, ... , 6?

3.  Show that the sum of the squares of the sides of a quadrilateral is at least the sum of the squares of the diagonals. When does equality hold?

4.  For n ≠ 0, let f(n) be the largest k such that 3^k divides n. If M is a set of n > 1 integers, show that the number of possible values for f(m-n), where m, n belong to M cannot exceed n-1.

5.  Let a, b be non-zero integers. Let m(a, b) be the smallest value of cos ax + cos bx (for real x). Show that for some r, m(a, b) ≤ r < 0 for all a, b. 

Solutions

Problem 1
Find the maximum and minimum values of x² + 2y² + 3z² for real x, y, z satisfying x² + y² + z² = 1.
Answer
3, 1
Solution

x² + 2y² + 3z² = (x² + y² + z²) + y² + 2z² = 1 + y² + 2z² ≥ 1. Equality if x = 1, y = z = 0.

x² + 2y² + 3z² ≤ 3(x² + y² + z²) = 3. Equality if x = y = 0, z = 1.

Problem 2

How many different ways (up to rotation) are there of labeling the faces of a cube with the numbers 1, 2, ... , 6?

Answer

30

Solution

Rotate the cube so that 1 is uppermost. There are then 5 choices for the opposite face. There are then 4! = 24 ways of arranging the other 4 faces, but groups of 4 are related by rotation, so 5·6 = 30 ways in all.

[more...]

7th Swedish Mathematical Society Problems 1967

1.  p parallel lines are drawn in the plane and q lines perpendicular to them are also drawn. How many rectangles are bounded by the lines?

2.  You are given a ruler with two parallel straight edges a distance d apart. It may be used (1) to draw the line through two points, (2) given two points a distance ≥ d apart, to draw two parallel lines, one through each point, (3) to draw a line parallel to a given line, a distance d away. One can also (4) choose an arbitrary point in the plane, and (5) choose an arbitrary point on a line. Show how to construct (A) the bisector of a given angle, and (B) the perpendicular to the midpoint of a given line segment.

3.  Show that there are only finitely many triples (a, b, c) of positive integers such that 1/a + 1/b + 1/c = 1/1000.

4.  The sequence a₁, a₂, a₃, ... of positive reals is such that ∑ a_i diverges. Show that there is a sequence b₁, b₂, b₃, ... of positive reals such that lim b_n = 0 and ∑ a_ib_i diverges.

5.  a₁, a₂, a₃, ... are positive reals such that a_n² ≥ a₁ + a₂ + ... + a_n-1. Show that for some C > 0 we have a_n ≥ Cn for all n.

6.  The vertices of a triangle are lattice points. There are no lattice points on the sides (apart from the vertices) and n lattice points inside the triangle. Show that its area is n + ½. Find the formula for the general case where there are also m lattice points on the sides (apart from the vertices). 

Solutions

Problem 1

p parallel lines are drawn in the plane and q lines perpendicular to them are also drawn. How many rectangles are bounded by the lines?

Answer

pq(p-1)(q-1)/4

Solution

The lines give a p x q array of possible vertices. We pick any vertex, then any vertex not in the same row or column. That defines a rectangle. It can be done in pq(p-1)(q-1) ways and gives each rectangle 4 times. 

Problem 3

Show that there are only finitely many triples (a, b, c) of positive integers such that 1/a + 1/b + 1/c = 1/1000.

Solution

wlog a ≤ b ≤ c. Then a ≤ 3000, so there are only finitely many possible values for a. Now for given a we have 1/b + 1/c = fixed. Again there are only a finite number of possibilities for b, and c is then fixed. 

Problem 4

The sequence a₁, a₂, a₃, ... of positive reals is such that ∑ a_i diverges. Show that there is a sequence b₁, b₂, b₃, ... of positive reals such that lim b_n = 0 and ∑ a_ib_i diverges.

Solution

Put b_n = 1/(a₁ + a₂ + ... + a_n). Then lim b_n = 0. Given any m we can find n such that s_n > 2s_m and hence s_k > 2s_m for any k > m. Hence a_m+1b_m+1 + ... + a_kb_k ≥ (s_k - s_m)/s_k = 1 - s_m/s_k > 1/2 for any k > n. Hence ∑ a_nb_n diverges.

Thanks to Thomas Linhart

Problem 6

The vertices of a triangle are lattice points. There are no lattice points on the sides (apart from the vertices) and n lattice points inside the triangle. Show that its area is n + ½. Find the formula for the general case where there are also m lattice points on the sides (apart from the vertices).

Answer

The area of any polygon with all vertices at lattice points (and boundary not self-intersecting) is ½b + c - 1, where b is the number of lattice points on the boundary (including vertices) and c is the number of lattice points inside.

Solution

This is just Pick's theorem, which is bookwork.

[more...]

6th Swedish Mathematical Society Problems 1966

1.  Let {x} denote the fractional part of x = x - [x]. The sequences x₁, x₂, x₃, ... and y₁, y₂, y₃, ... are such that lim {x_n} = lim {y_n} = 0. Is it true that lim {x_n + y_n} = 0? lim {x_n - y_n} = 0?

2.  a₁ + a₂ + ... + a_n = 0, for some k we have a_j ≤ 0 for j ≤ k and a_j ≥ 0 for j > k. If a_i are not all 0, show that a₁ + 2a₂ + 3a₃ + ... + na_n > 0.

3.  Show that an integer = 7 mod 8 cannot be sum of three squares.

4.  Let f(x) = 1 + 2/x. Put f₁(x) = f(x), f₂(x) = f(f₁(x)), f₃(x) = f(f₂(x)), ... . Find the solutions to x = f_n(x) for n > 0.

5.  Let f(r) be the number of lattice points inside the circle radius r, center the origin. Show that lim_r→∞ f(r)/r² exists and find it. If the limit is k, put g(r) = f(r) - kr². Is it true that lim_r→∞ g(r)/r^h = 0 for any h < 2?

Solutions

Problem 1

Let {x} denote the fractional part of x = x - [x]. The sequences x₁, x₂, x₃, ... and y₁, y₂, y₃, ... are such that lim {x_n} = lim {y_n} = 0. Is it true that lim {x_n + y_n} = 0? lim {x_n - y_n} = 0?

Answer

Yes, no.

Solution

Since {x_n} tends to 0, we must have {x_n} < 1/3 for sufficiently large n. Similarly for y_n. Hence {x_n + y_n} = {x_n} + {y_n} for sufficiently large n, which proves the first part.

A counter-example for the second part is x_n = 0, y_n = 1/n. Then {x_n - y_n} = 1 - 1/n which does not tend to 0.

Problem 2

a₁ + a₂ + ... + a_n = 0, for some k we have a_j ≤ 0 for j ≤ k and a_j ≥ 0 for j > k. If a_i are not all 0, show that a₁ + 2a₂ + 3a₃ + ... + na_n > 0.

Solution

We have a_i ≤ 0 for i ≤ k, so i a_i ≥ k a_i for i ≤ k. Hence ∑₁^k i a_i ≥ k ∑₁^k a_i (*). Similarly, ∑_k+1ⁿ i a_i ≥ k ∑_k+1ⁿ a_i (**). Since not all a_i are 0 we cannot have equality in (*) and (**). Hence ∑ i a_i > k ∑₁^k a_i + k ∑_k+1ⁿ a_i = 0.

Problem 3

Show that an integer = 7 mod 8 cannot be sum of three squares.

Solution

All squares are 0, 1 or 4 mod 8.

Problem 4

Let f(x) = 1 + 2/x. Put f₁(x) = f(x), f₂(x) = f(f₁(x)), f₃(x) = f(f₂(x)), ... . Find the solutions to x = f_n(x) for n > 0.

Answer

x = -1 or 2.

Solution

f(x) = x iff 0 = x² - x - 2 = (x+1)(x-2). Now it is clear by a trivial induction that f_n(x) = linear/linear. So f_n(x) = x is a quadratic and so has at most two roots. But x = -1 and 2 are obviously roots, so they are the only roots.

Problem 5

Let f(r) be the number of lattice points inside the circle radius r, center the origin. Show that lim_r→∞ f(r)/r² exists and find it. If the limit is k, put g(r) = f(r) - kr². Is it true that lim_r→∞ g(r)/r^h = 0 for any h < 2?

Answer

k = π

Yes, any h > 1.

Solution

The area of the circle is πr². We may tile the plane with squares side 1 centered on the lattice points. A circle encloses some complete squares and some incomplete squares. If all the squares were complete the circle would enclose πr², since the incomplete squares have smaller area, it encloses ≥ πr² squares. Any square which intersects the disk radius r-2 must be completely inside the disk radius r, so there are at least π(r-2)² squares completely inside the disk radius r. So the number of lattice points is at least π(r-2)². If the lattice point lies inside the circle then its square lies entirely inside the circle radius r+2, so the number of lattice points is at most π(r+2)². So π(1 - 2/r)² ≤ f(r)/r² ≤ π(1 + 2/r)². Hence lim f(r)/r² = π.

The inequality above gives |g(r)| ≤ 4π(r+1), so lim g(r)/r^h = 0 for h > 1.

[more...]

5th Swedish Mathematical Society Problems 1965

1.  The feet of the altitudes in the triangle ABC are A', B', C'. Find the angles of A'B'C' in terms of the angles A, B, C. Show that the largest angle in A'B'C' is at least as big as the largest angle in ABC. When is it equal?

2.  Find all positive integers m, n such that m³ - n³ = 999.

3.  Show that for every real x ≥ ½ there is an integer n such that |x - n²| ≤ √(x - ¼).

4.  Find constants A > B such that f( 1/(1+2x) )/f(x) is independent of x, where f(x) = (1 + Ax)/(1 + Bx) for all real x ≠ -1/B. Put a₀ = 1, a_n+1 = 1/(1 + 2a_n). Find an expression for a_n by considering f(a₀), f(a₁), ... .

5.  Let S be the set of all real polynomials f(x) = ax³ + bx² + cx + d such that |f(x)| ≤ 1 for all -1 ≤ x ≤ 1. Show that the set of possible |a| for f in S is bounded above and find the smallest upper bound. 

Solutions

Problem 2
Find all positive integers m, n such that m³ - n³ = 999.
Answer
10³ - 1³, 12³ - 9³
Solution
The fastest way to do this is simply to write down the small cubes: 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728, 2197 (those at least you should know), 2744, 3375, 4096, 4913, 5832, 6859. Note that 6859 - 5832 > 999 and (n+1)³ - n³ is obviously an increasing function of n, so there are no solutions for m ≥ 19. We find the solutions for m < 19 by inspection.


Problem 3
Show that for every real x ≥ ½ there is an integer n such that |x - n²| ≤ √(x - ¼).
Solution
|x - n²| ≤ √(x - ¼) is equivalent to x² - (2n²+1)x + n⁴ + 1/4 ≤ 0. The roots are n² ± n + 1/2, so the inequality is satisfied for n² - n + 1/2 ≤ x < n² + n + 1/2. But these intervals cover the reals ≥ 1/2, because n² + n + 1/2 = (n+1)² - (n+1) + 1/2

[more...]

4th Swedish Mathematical Society Problems 1964

1.  Find the side lengths of the triangle ABC with area S and ∠BAC = x such that the side BC is as short as possible.

2.  Find all positive integers m, n such that n + (n+1) + (n+2) + ... + (n+m) = 1000.

3.  Find a polynomial with integer coefficients which has √2 + √3 and √2 + 3^1/3 as roots.

4.  Points H₁, H₂, ... , H_n are arranged in the plane so that each distance H_iH_j ≤ 1. The point P is chosen to minimise max(PH_i). Find the largest possible value of max(PH_i) for n = 3. Find the best upper bound you can for n = 4.

5.  a₁, a₂, ... , a_n are constants such that f(x) = 1 + a₁ cos x + a₂ cos 2x + ... + a_n cos nx ≥ 0 for all x. We seek estimates of a₁. If n = 2, find the smallest and largest possible values of a₁. Find corresponding estimates for other values of n. 

Solutions

Problem 1

Find the side lengths of the triangle ABC with area S and ∠BAC = x such that the side BC is as short as possible.

Answer

BC = 2√(S tan(x/2)), AB = AC = √(S/(sin(x/2)cos(x/2)) )

Solution

For given BC, the locus of A with ∠BAC = x is the arc of a circle. The area is BC times the height, so we maximise the area by taking AB = AC. Since we want BC as small as possible, we must have AB = AC. So suppose BC = 2k, height = h. Then S = hk, and h = k cot(x/2). So S = k² cot(x/2). Hence k = √(S tan(x/2)). Then the other sides have length k/sin(x/2). 

Problem 2

Find all positive integers m, n such that n + (n+1) + (n+2) + ... + (n+m) = 1000.

Answer

(m,n) = (15,55), (24,28), (4,198).

Solution

There are m+1 terms, average size (2n+m)/2. So (m+1)(2n+m) = 2000 = 16·125. Note that m+1 and 2n+m have opposite parity. Also 1 < m+1 < 2n+m. So we have m+1 = 16, 25 or 5. 

Problem 3

Find a polynomial with integer coefficients which has √2 + √3 and √2 + 3^1/3 as roots.

Answer

(x⁴ - 10x² + 1)(x⁶ - 6x⁴ - 6x³ + 12x² - 36x + 1) = 0

Solution

(x + √2 + √3)(x - √2 - √3) = x² - 5 - 2√6. Similarly, (x + √2 - √3)(x - √2 + √3) = x² - 5 + 2√6, so √2 + √3 is a root of (x² - 5 - 2√6)(x² - 5 + 2√6) = x⁴ - 10x² + 1.

√2 + 3^1/3 is a root of (x - √2)³ - 3 = 0, or (x³ + 6x - 3) - (3x² + 2)√2 = 0. Multiplying by (x³ + 6x - 3) + (3x² + 2)√2 we get (x³ + 6x - 3)² - 2(3x² + 2)2 = 0 or x⁶ - 6x⁴ - 6x³ + 12x² - 36x + 1 = 0.

So, (x⁴ - 10x² + 1)(x⁶ - 6x⁴ - 6x³ + 12x² - 36x + 1) = 0 has both required roots.

[more...]

3rd Swedish Mathematical Society Problems 1963

1.  How many positive integers have square less than 10⁷?

2.  The squares of a chessboard have side 4. What is the circumference of the largest circle that can be drawn entirely on the black squares of the board?

3.  What is the remainder on dividing 1234⁵⁶⁷ + 89¹⁰¹¹ by 12?

4.  Given the real number k, find all differentiable real-valued functions f(x) defined on the reals such that f(x+y) = f(x) + f(y) + f(kxy) for all x, y.

5.  A road has constant width. It is made up of finitely many straight segments joined by corners, where the inner corner is a point and the outer side is a circular arc. The direction of the straight sections is always between NE (45^o) and SSE (157½^o). A person wishes to walk along the side of the road from point A to point B on the same side. He may only cross the street perpendicularly. What is the shortest route?

6.  The real-valued function f(x) is defined on the reals. It satisfies |f(x)| ≤ A, |f ''(x)| ≤ B for some positive A, B (and all x). Show that |f '(x)| ≤ C, for some fixed C, which depends only on A and B. What is the smallest possible value of C? 

Solutions

Problem 1
How many positive integers have square less than 10⁷?
Answer
3162
Solution
I find this a somewhat baffling question (in the sense of why on earth would anyone set a question like this!). There are algorithms for calculating the square root, but no one is likely to remember them. So one has to resort to kludges. Probably most people remember enough squares to know that 312 = 961, 32² = 1024, so the answer is 31xx. We have 31002 = 9610000, which is 390000 short. We have 31xy² = 31002 + 6200·xy + xy². So we want roughly xy = 3900/62 = about 63. So we try 3162 and 3163.



Problem 2
The squares of a chessboard have side 4. What is the circumference of the largest circle that can be drawn entirely on the black squares of the board?
Answer
radius = √40, circumference = 2√40 π
Solution

 

Consider the arc of the circle that lies in a particular black square. Its endpoints must be vertices of the square (otherwise the continuation of the arc would enter a white square). Suppose the two vertices are opposite (A and B in the diagram below). Then the two vertices of the next square along the circle cannot be opposite or the circle would pass through three collinear points (so they must be B and C in the diagram). Hence the center lies on the the perpendicular bisectors of AB and BC, so it must be O. That works, as shown in the diagram above.

If no square on the circle has opposite vertices on the circle, then it is easily seen that the circle must pass through the four vertices of a square and so is smaller than the case above. (Of course, if the circle is contained in a single square, then it is smaller still.)

 Problem 3
What is the remainder on dividing 1234⁵⁶⁷ + 89¹⁰¹¹ by 12?
Answer
9
Solution
1234 = 1 mod 3, so 1234⁵⁶⁷ = 1 mod 3. 89 = -1 mod 3, so 89¹⁰¹¹ = -1 mod 3. Hence 1234⁵⁶⁷ + 89¹⁰¹¹ = 0 mod 3. 1234 is even, so 1234⁵⁶⁷ = 0 mod 4. 89 = 1 mod 4, so 89¹⁰¹¹ = 1 mod 4. Hence 1234⁵⁶⁷ + 89¹⁰¹¹ = 1 mod 4. So it is 9 mod 12.

[more...]

2nd Swedish Mathematical Society Problems 1962

1.  Find all polynomials f(x) such that f(2x) = f '(x) f ''(x).

2.  ABCD is a square side 1. P and Q lie on the side AB and R lies on the side CD. What are the possible values for the circumradius of PQR?

3.  Find all pairs (m, n) of integers such that n² - 3mn + m - n = 0.

4.  Which of the following statements are true?

(A) X implies Y, or Y implies X, where X is the statement, the lines L₁, L₂, L₃ lie in a plane, and Y is the statement, each pair of the lines L₁, L₂, L₃ intersect.

(B) Every sufficiently large integer n satisfies n = a⁴ + b⁴ for some integers a, b.

(C) There are real numbers a₁, a₂, ... , a_n such that a₁ cos x + a₂ cos 2x + ... + a_n cos nx > 0 for all real x.

5.  Find the largest cube which can be placed inside a regular tetrahedron with side 1 so that one of its faces lies on the base of the tetrahedron. 

Solutions

Problem 1

Find all polynomials f(x) such that f(2x) = f '(x) f ''(x).

Answer

4x³/9

Solution

Suppose deg f = n. Then deg f ' = n-1 and deg f " = n-2, so n = n-1+n-2. Hence n = 3. So put f(x) = ax³ + bx² + cx + d. Then we have 8ax³ + 4bx² + 2cx + d = (3ax² + 2bx + c)(6ax + 2b) = 18a²x³ + 18abx² + (6ac+4b²)x + 2bc. Comparing x³, a = 4/9. Then comparing x², b = 0. Comparing x, c = 0. Comparing constant term, d = 0. 

Problem 2

ABCD is a square side 1. P and Q lie on the side AB and R lies on the side CD. What are the possible values for the circumradius of PQR?

Answer

any value in [1/2, 1/√2]

Solution

Let O be the circumcenter. Then OP + OR ≥ PR ≥ AD = 1, so the radius is at least 1/2. P,Q,R always lie inside or on the circle through A,B,C,D which has radius 1/√2, so the radius is at most 1/√2.

Now take ∠RPQ = 90^o, then QR is a diameter of the circumcircle and so the circumradius is ½QR. By adjusting the positions of Q, R we can obviously get QR to have any value in [1,√2]. 

Problem 3

Find all pairs (m, n) of integers such that n² - 3mn + m - n = 0.

Answer

(m,n) = (0,0) or (0,1)

Solution

(3m+1)(3n-1) = 3n²-1, so if p divides 3n-1, then it also divides 3n²-1, and hence also (3n²-1) - n(3n-1) = n-1, and hence also (3n-1) - 3(n-1) = 2. So 3n-1 = 0, ±1 or ±2. But n must be an integer, so 0, 1, -2 do not work. -1 gives n = 0 and hence m = 0, which is a solution. 2 gives n = 1 and hence m = 0, which is a solution.

[more...]

1st Swedish Mathematical Society Problems 1961

1.  Let S be the system of equations (1) y(x⁴ - y² + x²) = x, (2) x(x⁴ - y² + x²) = 1. Take S' to be the system of equations (1) and x·(1) - y·(2) (or y = x²). Show that S and S' do not have the same set of solutions and explain why.

2.  Show that x₁/x_n + x₂/x_n-1 + x₃/x_n-2 + ... + x_n/x₁ ≥ n for any positive reals x₁, x₂, ... , x_n.

3.  For which n is it possible to put n identical candles in a candlestick and to light them as follows. For i = 1, 2, ... , n, exactly i candles are lit on day i and burn for exactly one hour. At the end of day n, all n candles must be burnt out. State a possible rule for deciding which candles to light on day i.

4.  288 points are placed inside a square ABCD of side 1. Show that one can draw a set S of lines length 1 parallel to AB joining AD and BC, and additional lines parallel to AD joining each of the 288 point to a line in S, so that the total length of all the lines is less than 24. Is there a stronger result?

5.  n is a positive integer. Show that x⁶/6 + x² - nx has exactly one minimum a_n. Show that for some k, lim_n→∞ a_n/n^k exists and is non-zero. Find k and the limit.

Solutions

Problem 1

Let S be the system of equations (1) y(x⁴ - y² + x²) = x, (2) x(x⁴ - y² + x²) = 1. Take S' to be the system of equations (1) and x·(1) - y·(2) (or y = x²). Show that S and S' do not have the same set of solutions and explain why.

Solution

S' has the solution x = 0, y = 0, but S does not. Replacing (2) by x·(1) - y·(2) introduces the extra solution. 

Problem 2

Show that x₁/x_n + x₂/x_n-1 + x₃/x_n-2 + ... + x_n/x₁ ≥ n for any positive reals x₁, x₂, ... , x_n.

Solution

AM/GM. 

Problem 3

For which n is it possible to put n identical candles in a candlestick and to light them as follows. For i = 1, 2, ... , n, exactly i candles are lit on day i and burn for exactly one hour. At the end of day n, all n candles must be burnt out. State a possible rule for deciding which candles to light on day i.

Answer

n odd.

If i < n/2, light i candles starting from 1. If i > n/2, light i candles starting from n. Eg 1; 1,2; 3,4,5; 2,3,4,5; 1,2,3,4,5.

Solution

Total candle hours = 1 + 2 + ... + n = n(n+1)/2. Hence (n+1)/2 per candle. But each candle is lit for a whole number of hours, so n must be odd.

Rule above gives pairs of days 1, 2, ... , i and i+1, i+2, ... , n, plus the final day when all candles are lit. Each candle is lit once for each pair of days (and is lit on the final day). 

Problem 4

288 points are placed inside a square ABCD of side 1. Show that one can draw a set S of lines length 1 parallel to AB joining AD and BC, and additional lines parallel to AD joining each of the 288 point to a line in S, so that the total length of all the lines is less than 24. Is there a stronger result?

Answer

≤ 18 6/23

Solution

Place 12 horizontal non-overlapping strips width 1/12 across the square. Take S to be the center-lines of the strips. Join each point to the center-line of its strip. So we have 12 lines length 1 and 288 lines length at most 1/24, total at most 24.

Take 24 equally spaced parallel lines, including two edges of the square. So the distance between two adjacent lines is 1/23. Color the lines alternately red and blue. Let R be the sum of the distances of the 288 points from the nearest red line and B the sum of the distances from the nearest blue line. For each point the sum of the distance to the nearest blue line and the distance to the nearest red line is 1/23, because each point lies in a strip width 1/23 bounded by the nearest red line and the nearest blue line. Hence B + R = 288/23. So at least one of B, R is ≤ 144/23. So if we take that set of 12 lines as the lines we get a total length for the lines and perpendicular segments of at most 12 + 144/23 = 18 6/23. 

Problem 5

n is a positive integer. Show that x⁶/6 + x² - nx has exactly one minimum an. Show that for some k, lim_n→∞ a_n/n^k exists and is non-zero. Find k and the limit.

Answer

k = 6/5, limit = -5/6.

Solution

Derivative is x⁵ + 2x - n, which is strictly monotonic increasing. It is -n at 0. So it has a single zero for some h > 0 and is negative for x < h, and positive for x > h. Hence the zero represents a minimum.

At n^1/5 derivative is n + 2n^1/5 - n = 2n^1/5 > 0, so minimum is before n^1/5. At n^1/5-1, derivative is n - 5n^4/5 + O(n^3/5) + 2n^1/5 - n which is less than 0 for sufficiently large n. So the minimum occurs (for sufficiently large n) for x = n^1/5-h for some 0 < h < 1. The value at n^1/5 - h is (1/6) n^6/5 + O(n) - n^6/5 = -5/6 n^6/5 + O(n).

Comment. Early Western olympiad questions often used basic calculus.

 

[more...]