4th Austrian-Polish Mathematics Competition 1981 Problems



4th Austrian-Polish Mathematics Competition 1981 Problems

1.  Find the smallest n for which we can find 15 distinct elements a1, a2, ... , a15 of {16, 17, ... , n} such that ak is a multiple of k.


2.  The rational sequence a0, a1, a2, ... satisfies an+1 = 2an2 - 2an + 1. Find all a0 for which there are four distinct integers r, s, t, u such that ar - as = at - au.
3.  The diagram shows the incircle of ABC and three other circles inside the triangle, each touching the incircle and two sides of the triangle. The radius of the incircle is r and the radius of the circle nearest to A, B, C is rA, rB, rC respectively. Show that rA + rB + rC ≥ r, with equality iff ABC is equilateral. 

4.  n symbols are arranged in a circle. Each symbol is 0 or 1. A valid move is to change any 1 to 0 and to change the two adjacent symbols. For example one could change ... 01101 ... to ... 10001 ... . The initial configuration has just one 1. For which n can one obtain all 0s by a sequence of valid moves? 

5.  A quartic with rational coefficients has just one real root. Show that the root must be rational. 

6.  The real sequences x1, x2, x3, ... , y1, y2, y3, ... , z1, z2, z3, ... satisfy xn+1 = yn + 1/zn, yn+1 = zn + 1/xn, zn+1 = xn + 1/yn. Show that the sequences are all unbounded. 

7.  If N = 2n > 1 and k > 3 is odd, show that kN - 1 has at least n+1 distinct prime factors. 

8.  A is a set of r parallel lines, B is a set of s parallel lines, and C is a set of t parallel lines. What is the smallest value of r + s + t such that the r + s + t lines divide the plane into at least 1982 regions?
9.  Let X be the closed interval [0, 1]. Let f: X → X be a function. Define f1 = f, fn+1(x) = f( fn(x) ). For some n we have |fn(x) - fn(y)| < |x - y| for all distinct x, y. Show that f has a unique fixed point.
[Read More...]


3rd Austrian-Polish Mathematics Competition 1980 Problems



3rd Austrian-Polish Mathematics Competition 1980 Problems

1.  A, B, C are infinite arithmetic progressions of integers. {1, 2, 3, 4, 5, 6, 7, 8} is a subset of their union. Show that 1980 also belongs to their union.


2.  1 = a1 < a2 < a3 < ... is an infinite sequence of integers such that an < 2n-1. Show that every positive integer is the difference of two members of the sequence.
3.  P is an interior point of a tetrahedron. Show that the sum of the six angles subtended by the sides at P is greater than 540o.
4.  [Missing]

Solutions

3rd APMC 1980 Problem 1

A, B, C are infinite arithmetic progressions of integers. {1, 2, 3, 4, 5, 6, 7, 8} is a subset of their union. Show that 1980 also belongs to their union.
Solution
If any two of 4, 6, 8 belong to the same set, then we are done. So assume (wlog) that 4 ∈ A, 6 ∈ B and 8 ∈ C. Then 5 cannot belong to A or B or we are done, so 5 ∈ C. Similarly 3 cannot belong to A or B or we are done, so 3 ∈ C. But if 3 and 5 are in C, then so is 7. Since 7 and 8 are in C, then so are all integers > 8 and hence 1980.
Thanks to Suat Namli

 
[Read More...]


2nd Austrian-Polish Mathematics Competition 1979 Problems



2nd Austrian-Polish Mathematics Competition 1979 Problems

1.  ABCD is a square. E is any point on AB. F is the point on BC such that BF = BE. The perpendicular from B meets EF at G. Show that ∠DGF = 90o.



2.  Find all polynomials of degree n with real roots x1 ≤ x2 ≤ ... ≤ xn such that xk belongs to the closed interval [k, k+1] and the product of the roots is (n+1)/(n-1)! .
3.  Find all positive integers n such that for all real numbers x1, x2, ... , xn we have S2S1 - S3 ≥ 6P, where Sk = ∑ xik, and P = x1x2 ... xn.
4.  Let N0 = {0, 1, 2, 3, ... } and R be the reals. Find all functions f: N0 → R such that f(m + n) + f(m - n) = f(3m) for all m, n.
5.  A tetrahedron has circumcenter O and incenter I. If O = I, show that the faces are all congruent.
6.  k is real, n is a positive integer. Find all solutions (x1, x2, ... , xn) to the n equations:
x1 + x2 + ... + xn = k
x12 + x22 + ... + xn2 = k2
...
x1n + x2n + ... + xnn = kn
7.  Find the number of paths from (0, 0) to (n, m) which pass through each node at most once. 

8.  ABCD is a tetrahedron. M is the midpoint of AC and N is the midpoint of BD. Show that AB2 + BC2 + CD2 + DA2 = AC2 + BD2 + 4 MN2.
9.  Find the largest power of 2 that divides [(3 + √11)2n+1].
[Read More...]


1st Austrian-Polish Mathematics Competition 1978 Problems



1st Austrian-Polish Mathematics Competition 1978 Problems

1.  Find all real-valued functions f on the positive reals which satisfy f(x + y) = f(x2 + y2) for all positive x, y.
2.  A parallelogram has its vertices on the boundary of a regular hexagon and its center at the center of the hexagon. Show that its area is at most 2/3 the area of the hexagon.


3.  Let x = 1o. Show that (tan x tan 2x ... tan 44x)1/44 < √2 - 1 < (tan x + tan 2x + ... + tan 44x)/44.
4.  Given a positive rational k not equal to 1, show that we can partition the positive integers into sets Ak and Bk, so that if m and n are both in Ak or both in Bk then m/n does not equal k.
5.  The sets A1, A2, ... , A1978 each have 40 elements and the intersection of any two distinct sets has just one element. Show that the intersection of all the sets has one element.
6.  S is a set of disks in the plane. No point belongs to the interior of more than one disk. Each disk has a point in common with at least 6 other disks. Show that S is infinite.
7.  S is a finite set of lattice points in the plane such that we can find a bijection f: S → S satisfying |P - f(P)| = 1 for all P in S. Show that we can find a bijection g: S → S such that |P - g(P)| = 1 for all P in S and g(g(P) ) = P for all P in S.
8.  k is a positive integer. Define a1 = √k, an+1 = √(k + an). Show that the sequence an converges. Find all k such that the limit is an integer. Show that if k is odd, then the limit is irrational.
9.  P is a convex polygon. Some of the diagonals are drawn, so that no interior point of P lies on more than one diagonal. Show that at least two vertices of P do not lie on any diagonals.

Solutions

1st APMC 1978 Problem 1

Find all real-valued functions f on the positive reals which satisfy f(x + y) = f(x2 + y2) for all positive x, y.
Solution
If x + y = k and x2 + y2 = h then xy = (k2 - h)/2, so x, y are the roots of the polynomial z2 - kz + (k2 - h)/2 = 0. This polynomial has positive real roots provided that (1) k > 0, (2) k2 ≥ 2(k2 - h) or h ≥ k2/2, and (3) k2 > k2 - 2(k2-h) or h < k2. So if k > 0 and k2/2 ≤ h < k2, then f(k) = f(h). In other words, f must be constant on the interval [k2/2, k2). Take An to be the interval with k = (1.2)n. The the intervals An and An+1 overlap and ... A-2, A-1, A0, A1, A2, ... cover the positive reals, so f is constant on the positive reals.
Thanks to Suat Namli

1st APMC 1978 Problem 3

Let x = 1o. Show that (tan x tan 2x ... tan 44x)1/44 < √2 - 1 < (tan x + tan 2x + ... + tan 44x)/44.
Solution
Note that (3-√8) + (√8-2) = 1 and (3-√8) = (√8-2)2/4, so if the positive integers A, B, satisfy A + B = 1, A < B2/4, then A < 3-√8.
Now for 0 < y < 45o, we have 1 = tan 45o = (tan y + tan(45o-y) )/(1 - tan y tan(45o-y)), so (tan y + tan(45o-y)) + tan y tan(45o-y) = 1. But by AM/GM (tan y + tan(45o-y)) < (tan y tan(45o-y))2/4, provided y ≠ 45o/2. So by the result above we have (tan y + tan(45o-y)) < 3 - √8, and hence (tan x tan 2x ... tan 44x)1/44 < (3 - √8)22/44 = √2 - 1. Also √8 - 2 < (tan y + tan(45o-y)) and hence √2 - 1 = (22/44)(√8 - 2) < (tan x + tan 2x + ... + tan 44x)/44.
Thanks to Suat Namli
 
 
[Read More...]


15th Asian Pacific Mathematics Olympiad 2003 Problems



15th Asian Pacific Mathematics Olympiad 2003 Problems

1.  The polynomial a8x8 +a7x7 + ... + a0 has a8 = 1, a7 = -4, a6 = 7 and all its roots positive and real. Find the possible values for a0.


2.  A unit square lies across two parallel lines a unit distance apart, so that two triangular areas of the square lie outside the lines. Show that the sum of the perimeters of these two triangles is independent of how the square is placed.
3.  k > 14 is an integer and p is the largest prime smaller than k. k is chosen so that p ≥ 3k/4. Prove that 2p does not divide (2p - k)!, but that n does divide (n - k)! for composite n > 2p.
4.  Show that (an + bn)1/n + (bn + cn)1/n + (cn + an)1/n < 1 + (21/n)/2, where n > 1 is an integer and a, b, c are the sides of a triangle with unit perimeter.
5.  Find the smallest positive integer k such that among any k people, either there are 2m who can be divided into m pairs of people who know each other, or there are 2n who can be divided into n pairs of people who do not know each other.

15th APMO 2003 Problem 1

The polynomial a8x8 +a7x7 + ... + a0 has a8 = 1, a7 = -4, a6 = 7 and all its roots positive and real. Find the possible values for a0.
Answer 1/28
Solution
Let the roots be xi. We have Sum xi2 = 42 - 2·7 = 2. By Cauchy we have (x1·1 + ... + x8·1) ≤ (x12 + ... + x82)1/2(12 + ... + 12)1/2 with equality iff all xi are equal. Hence all xi are equal. So they must all be 1/2.

15th APMO 2003 Problem 2

A unit square lies across two parallel lines a unit distance apart, so that two triangular areas of the square lie outside the lines. Show that the sum of the perimeters of these two triangles is independent of how the square is placed.
Solution



15th APMO 2003 Problem 3

k > 14 is an integer and p is the largest prime smaller than k. k is chosen so that p ≥ 3k/4. Prove that 2p does not divide (2p - k)!, but that n does divide (n - k)! for composite n > 2p.
Solution
Since k > p, we have p > 2p-k and hence p does not divide any of 1, 2, 3, ... , 2p-k. But p is prime, so it does not divide (2p - k)! So 2p does not either.
Now consider composite n > 2p. Note that k > 14, so p ≥ 13, so n > 26. Take q to be the largest prime divisor of n and put n = qr. We now have three cases.
(1) q > r ≥ 3. Then n > 2p ≥ 3k/2, so 2n/3 > k. Hence n-k > n-2n/3 = n/3 ≥ n/r = q > r. So q and r are distinct integers < n-k. Hence n = qr divides (n-k)!.
(2) r = 2. Then n = 2q > 2p. But p is the largest prime < k. Hence q ≥ k, so n-k ≥ n-q = q. Obviously q > 2 (since n > 26), so q and 2 are distinct integers < n-k. Hence n = 2q divides (n-k)! .
(3) The final case is n = q2. We show that 2q ≤ n-k. Suppose not. Then 2q ≥ n-k+1 ≥ (2p+1)-k+1 ≥ 3k/2 + 1 - k + 1 = k/2 + 2. So q ≥ k/4 + 1. Also since 2q ≥ n-k+1, we have k ≥ n-2q+1 = (q-1)2 ≥ k2/16. If k > 16, this is a contradiction. If k = 15 or 16, then p = 13 and k ≥ (q-1)2 gives q ≤ 5, so n = q2 ≤ 25. But n > 2p = 26. Contradiction. So we have established that 2q ≤ n-k. But that means that q and 2q are distinct integers ≤ n-k and so their product 2n divides (n-k)!.
Thanks to Gerhard Woeginger for this.

15th APMO 2003 Problem 4

Show that (an + bn)1/n + (bn + cn)1/n + (cn + an)1/n < 1 + (21/n)/2, where n > 1 is an integer and a, b, c are the sides of a triangle with unit perimeter.
Solution
We may take a ≥ b ≥ c. Since a + b + c = 1 and a < b+c, we have b ≤ a < 1/2. Hence (an + bn)1/n < 21/n/2 (*).
We have (b + c/2)n = bn + n/2 c bn-1 + other positive terms > bn + cn. Hence (bn + cn)1/n < b + c/2. Similarly, (cn + an)1/n < a + c/2. Adding we get (bn + cn)1/n + (cn + an)1/n < a+b+c = 1. Adding to (*) gives the required result.
 
 

Let the lines be L, L'. Let the square be ABA'B', with A, A' the two vertices not between L and L'. Let L meet AB at X and AB' at Y. Let L' meet A'B' at X' and A'B at Y'. So AXY and A'X'Y' are similar. Suppose angle AXY = x. If we move L towards A by a distance d perpendicular to itself, then AX is shortened by d cosec x. If L' remains a distance 1 from L, then A'X' is lengthened by d cosec x. The new triangle AXY is similar to the old. Suppose that perimeter AXY = k·AX, then perimeter AXY is increased by kd cosec x. Since AXY and A'X'Y' are similar, perimeter A'X'Y' is shortened by kd cosec x, so the sum of their perimeters is unchanged. It remains to show that the sum of the perimeters does not depend on the angle x.
Let us move L towards A until L' passes through A', at which point the perimeter of A'X'Y' is zero. Now if h is the height of AXY (from the base XY), then 1 + h = AA' sin(45o + x) = sin x + cos x. The perimeter of AXY is h/sin x + h/cos x + h/(sin x cos x) = h(sin x + cos x + 1)/(sin x cos x) = (sin x + cos x - 1)(sin x + cos x + 1)/(sin x cos x) = 2, which is independent of x.
[Read More...]


14th Asian Pacific Mathematics Olympiad 2002 Problems



14th Asian Pacific Mathematics Olympiad 2002 Problems

A1.  xi are non-negative integers. Prove that x1! x2! ... xn! ≥ ( [(x1 + ... + xn)/n] ! )n (where [y] denotes the largest integer not exceeding y). When do you have equality?


A2.  Find all pairs m, n of positive integers such that m2 - n divides m + n2 and n2 - m divides m2 + n.
A3.  ABC is an equilateral triangle. M is the midpoint of AC and N is the midpoint of AB. P lies on the segment MC, and Q lies on the segment NB. R is the orthocenter of ABP and S is the orthocenter of ACQ. The lines BP and CQ meet at T. Find all possible values for angle BCQ such that RST is equilateral.
A4.  The positive reals a, b, c satisfy 1/a + 1/b + 1/c = 1. Prove that √(a + bc) + √(b + ca) + √(c + ab) ≥ √(abc) + √a + √b + √c.
A5.  Find all real-valued functions f on the reals which have at most finitely many zeros and satisfy f(x4 + y) = x3f(x) + f(f(y)) for all x, y. 

14th APMO 2002 Problem 1

xi are non-negative integers. Prove that x1! x2! ... xn! ≥ ( [(x1 + ... + xn)/n] ! )n (where [y] denotes the largest integer not exceeding y). When do you have equality?
Solution
Answer: Equality iff all xi equal.
For given 2m the largest binomial coefficient is (2m)!/(m! m!) and for 2m+1 the largest binomial coefficient is (2m+1)!/( m! (m+1)!). Hence for fixed xi + xj the smallest value of xi! xj! is for xi and xj as nearly equal as possible.
If x1 + x2 + ... + xn = qn + r, where 0 < r < n, then we can reduce one or more xi to reduce the sum to qn. This will not affect the rhs of the inequality in the question, but will reduce the lhs. Equalising the xi will not increase the lhs (by the result just proved). So it is sufficient to prove the inequality for all xi equal. But in this case it is trivial since k! = k! . 

14th APMO 2002 Problem 2

Find all pairs m, n of positive integers such that m2 - n divides m + n2 and n2 - m divides m2 + n.
Solution
Assume n ≥ m.
(m+1)2 - m = (m+1) + m2. Clearly n2 increases faster than n, so n2 - m > n + m2 for n > m+1 and hence there are no solutions with n > m+1. It remains to consider the two cases n = m and n = m+1.
Suppose n = m. Then we require that n2 - n divides n2 + n. If n > 3, then n2 > 3n, so 2(n2 - n) > n2 + n. Obviously n2 - n < n2 + n, so if n > 3, then n2 - n cannot divide n2 + n. It is easy to check that the only solutions (with n = m) less than 3 are n = 2 and n = 3.
Finally suppose n = m+1. We require m2 - m - 1 divides m2 + 3m + 1. If m >= 6, then m(m - 5) > 3, so 2(m2 - m - 1) > m2 + 3m + 1. Obviously m2 - m - 1 < m2 + 3m + 1, so m2 - m - 1 cannot divide m2 + 3m + 1 for m >= 6. Checking the smaller values, we find the solutions less than 6 are m = 1 and m = 2.
Summarising, the only solutions are: (n, m) = (2, 2), (3, 3), (1, 2), (2, 1), (2, 3), (3, 2). 

14th APMO 2002 Problem 3

ABC is an equilateral triangle. M is the midpoint of AC and N is the midpoint of AB. P lies on the segment MC, and Q lies on the segment NB. R is the orthocenter of ABP and S is the orthocenter of ACQ. The lines BP and CQ meet at T. Find all possible values for angle BCQ such that RST is equilateral.
Answer 15o.
Solution
 
Suppose CP < BQ. Since R is the intersection of BM and the perpendicular from P to AB, and S is the intersection of CN and the perpendicular from Q to AC, we have MR > NS. Hence (treating BC as horizontal), R is below S. But T must be to the right of the midpoint of BC. Hence T is to the right of the perpendicular bisector of RS, so RST cannot be equilateral. Contradiction. Similarly if CP > BQ. So CP = BQ. 

Let L be the midpoint of BC. Put ∠CBP = x and ∠RAM = y. So RM = AM tan y, TL = BL tan x = AM tan x. But ∠APB = 60o + x, so y = 30o - x. So if x ≠ 15o, then TL ≠ RM. However, RST equilateral implies TL = RM, so x and hence also ∠BCQ = 15o.

14th APMO 2002 Problem 4

The positive reals a, b, c satisfy 1/a + 1/b + 1/c = 1. Prove that √(a + bc) + √(b + ca) + √(c + ab) ≥ √(abc) + √a + √b + √c.
Solution
Thanks to Suat Namli for this.
Multiplying by √(abc), we have √(abc) = √(ab/c) + √(bc/a) + √(ca/b). So it is sufficient to prove that √(c + ab) ≥ √c + √(ab/c).
Squaring, this is equivalent to c + ab ≥ c + ab/c + 2√(ab) or c + ab ≥ c + ab(1 - 1/a - 1/b) + 2√(ab) or a + b >= 2√(ab) or (√a - √b)2 ≥ 0.
[Read More...]


13th Asian Pacific Mathematics Olympiad 2001 Problems



13th Asian Pacific Mathematics Olympiad 2001 Problems
A1.  If n is a positive integer, let d be the number of digits in n (in base 10) and s be the sum of the digits. Let n(k) be the number formed by deleting the last k digits of n. Prove that n = s + 9 n(1) + 9 n(2) + ... + 9 n(d).


A2.  Find the largest n so that the number of integers less than or equal to n and divisible by 3 equals the number divisible by 5 or 7 (or both).
A3.  Two equal-sized regular n-gons intersect to form a 2n-gon C. Prove that the sum of the sides of C which form part of one n-gon equals half the perimeter of C.
A4.  Find all real polynomials p(x) such that x is rational iff p(x) is rational.
A5.  What is the largest n for which we can find n + 4 points in the plane, A, B, C, D, X1, ... , Xn, so that AB is not equal to CD, but for each i the two triangles ABXi and CDXi are congruent? 

Solutions

13th APMO 2001 Problem 1

If n is a positive integer, let d+1 be the number of digits in n (in base 10) and s be the sum of the digits. Let n(k) be the number formed by deleting the last k digits of n. Prove that n = s + 9 n(1) + 9 n(2) + ... + 9 n(d).
Solution
Let the digits of n be ad, ad-1, ... , a0, so that n = ad 10d + ... + a0. Then n(k) = ad 10d-k + ad-1 10d-k-1 + ... + ak. Obviously s = ad + ... + a0. Hence s + 9 n(1) + ... + 9 n(d) = ad(9.10d-1 + 9.10d-2 + ... + 9 + 1) + ad-1(9.10d-2 + ... + 9 + 1) + ... + ad-k(9.10d-k-1 + ... + 9 + 1) + a1(9 + 1) + a0 = ad 10d + ... + a0 = n. 

13th APMO 2001 Problem2


Find the largest n so that the number of integers less than or equal to n and divisible by 3 equals the number divisible by 5 or 7 (or both).
Solution
Answer: 65.
Let f(n) = [n/3] - [n/5] - [n/7] + [n/35]. We are looking for the largest n with f(n) = 0. Now [n/5] + [n/7} <= [n/5 + n/7] = [12n/35] = [n/3 + n/105]. So for [n/5] + [n/7] to exceed [n/3] we certainly require n/105 ≥ 1/3 or n ≥ 35. Hence f(n) ≥ 0 for n ≤ 35. But f(n+35) = [n/3 + 11 + 2/3] - [n/5 + 7] - [n/7 + 5] + [n/35 + 1] = [n/3 + 2/3] - [n/5] - [n/7] + [n/35] ≥ f(n) (*). Hence f(n) ≥ 0 for all n. But f(n+105) = [n/3 + 35] - [n/5 + 21] - [n/7 + 15] + [n/35 + 3] = f(n) + 2. Hence f(n) ≥ 2 for all n ≥ 105.
Referring back to (*) we see that f(n+35) > f(n), and hence f(n+35) > 0, unless n is a multiple of 3. But if n is a multiple of 3, then n + 35 is not and hence f(n+70) > f(n+35) > 0. So f(n) > 0 for all n ≥ 70.
f(70) = 1. So f(69) = 2 (we have lost 70, a multiple of 7). So f(68) = f(67) = f(66) = 1 (we have lost 69, a multiple of 3). Hence f(65) = 0 (we have lost 66, a multiple of 3). 


13th APMO 2001 Problem3

Two equal-sized regular n-gons intersect to form a 2n-gon C. Prove that the sum of the sides of C which form part of one n-gon equals half the perimeter of C.
Solution
Let one regular n-gon have vertices P1, P2, ... , Pn and the other have vertices Q1, Q2, ... , Qn. Each side of the 2n-gon forms a triangle with one of the Pi or Qi. Note that Pi and Qj must alternate as we go around the 2n-gon. For convenience assume that the order is P1, Q1, P2, Q2, ... , Pn, Qn. Let the length of the side which forms a triangle with Pi be pi, and the length of the side which forms a triangle with Qi be qi. Each of these triangles has one angle (180o - 360o/n). Adjacent triangles have one of their other angles equal (alternate angles), so all the triangles are similar. If the sides of the triangle vertex Pi have lengths ai, bi, pi, then the side PiPi+1 is bi + qi + ai+1, and ai/ai+1 = bi/bi+1 = pi/pi+1. Similarly, if the sides of the triangle vertex Qi have lengths ci, di, qi, then the side QiQi+1 is di + pi+1 + ci+1 and ci/ci+1 = di/di+1 = qi/qi+1. But ai/bi = di/ci (not ci/di), because the triangles alternate in orientation.
Put ai/pi = h, bi/pi = k. Note that ai + bi > pi, so h + k - 1 > 0. We have also ci/qi = k, di/qi = h. Adding the expressions for PiPi+1 we get perimeter Pi = ∑(bi + qi + ai+1) = k ∑ pi + ∑ qi + h ∑ pi. Similarly, perimeter Qi = (h + k) ∑ qi + ∑ pi. The two n-gons are equal, so (h + k - 1) ∑ pi = (h + k - 1) ∑ qi. Hence ∑ pi = ∑ qi, which is the required result.

13th APMO 2001 Problem4

Find all real polynomials p(x) such that x is rational iff p(x) is rational.
Solution
It is necessary for all the coefficients of x to be rational. This is an easy induction on the number of coefficients. For p(0) must be rational, hence ( p(x) - p(0) )/x must be rational for all rational x and so on.
Clearly this condition is also sufficient for polynomials of degree 0 or 1.
There are obviously no quadratics, for if p(x) = ax2 + bx + c, with a, b, c rational, then p(√2 - b/2a) = 2a - b2/4a + c, which is rational.
We prove that if there are also no higher degree polynomials. The idea is to show that there is a rational value k which must be taken for some real x, but which cannot be taken by any rational x.
Suppose p(x) has degree n > 1. Multiplying through by the lcm of the denominators of the coefficients, we get p(x) = (a xn + b xn-1 + ... + u x + v)/w, where a, b, ... , w are all integers. Put x = r/s, where r and s are coprime integers, then p(r/s) = (a rn + b rn-1s + ... + u r sn-1 + v sn)/( w sn). Let q be any prime which does not divide a or w. Consider first a > 0. p(x) must assume all sufficiently large positive values. So it must in particular take the value k = m + 1/q, where m is a sufficiently large integer. So k = (mq + 1)/q. The denominator is divisible by q, but not q2 and the numerator is not divisible by q. Suppose p(r/s) = k for some integers r, s. The denominator of p(r/s) is w sn. We know that w is not divisible by q, so q must divide s. But n > 1, so q2 divides w sn. The numerator of p(r/s) has the form a rn + h s. Neither a nor r is divisible by q, so the numerator is not divisible by q. Thus no cancellation is possible and we cannot have p(r/s) = k. Thus there must be some irrational x such that p(x) = k.
If a < 0, then the same argument works except that we take k = m + 1/q, where m is a sufficiently large negative integer.

13th APMO 2001 Problem 5

What is the largest n for which we can find n + 4 points in the plane, A, B, C, D, X1, ... , Xn, so that AB is not equal to CD, but for each i the two triangles ABXi and CDXi are congruent?
Answer 4
Solution
Many thanks to Allen Zhang for completing the proof
Assume AB = a, CD = b with a > b. If ABX and CDX are congruent, then either AX or BX = CD = b, so X lies either on the circle SA center A radius b, or on the circle SBcenter B radius b. Similarly, CX or DX = AB = a, so X lies either on the circle SC center C radius a, or on the circle SD center D radius a. Thus we have four pairs of circles, (SA, SC), (SA, SD), (SB, SC), (SB, SD) each with at most 2 points of intersection. X must be one of these 8 points.
However, we show that if two points of intersection of (SA, SC) are included, then no points of (SB, SD) can be included. The same applies to each pair of circles, so at most 4 points X are possible. Finally, we will give an example of n = 4, showing that the maximum of 4 is achieved.
So suppose (SA, SC) intersect at X and Y. We must have BX = DX and BY = DY, so X and Y both lie on the perpendicular bisector of BD. In other words, XY is the perpendicular bisector of BD, so D is the reflection of B in the line XY. There is no loss of generality in taking B (and D) to be on the same side of AC as X. Let A' be the reflection of A in the line XY. Since B lies on the circle center A radius a, D must lie on the circle center A' radius A. Thus the triangles A'XC and CDA' are congruent.
(Note that A and C can be on the same side of XY or opposite sides.) Hence D is the same height above AC as X, so DX is perpendicular to XY. Hence X is the midpoint of BD. Also ∠A'CD = ∠CA'X = 180o - ∠CAX, so AX and CD are parallel. They are also equal, so ACDX is a parallelogram and hence AC = DX = BD/2. In the second configuration above, both A and C are on the same side of XY as D, so the midpoint M of AC lies on the same side of XY as D. In the first configuration, since AX = b < a = CX, M lies to the right of XY.
Now suppose there is a solution for the configuration (SB, SD). Thus there is a point Z such that ABZ and ZDC are congruent. Then AZ = CZ, so Z lies on the perpendicular bisector of AC and hence on the same side of XY as D. But it is also a distance a from D and a distance b from B, and a > b, so it must lie on the same side of XY as B. Contradiction. So there are no solutions for the configuration (SB, SD), as required. That completes the proof that n ≤ 4.
For an example with n = 4, take a regular hexagon ACDBX3X2. Extend the side X2X3 to X1X4, with X1, X2, X3, X4 equally spaced in that order, so that X1AX2 and X3BX4 are equilateral. Then ABX1 and CX1D are congruent, ABX2 and DX2C are congruent, ABX3 and X3CD are congruent, and ABX4 and X4DC are congruent.

[Read More...]


Arithmetic Facts Flashcards



Arithmetic Facts Flashcards


Guidelines:

The Three Stacks.  Initially, some (if not all) of the new flashcards are divided into a weekly stack and a daily stack.  After several weeks of daily work, a finished stack is created. 


Getting Started.  Individual flashcards are initially created by cutting the flashcard sheets along the lines.  Answers should be written lightly in pencil on the back.  On the first day, go through a large stack of new flashcards (perhaps more than 100 cards), by dividing it into two stacks: the weekly stack, which are those cards the child knows very well and quickly (e.g. as quickly as one ought to know 2+3=5), and the daily stack, which are those cards the child either doesn’t know, or should be recalled more quickly.

<  The child then needs to practice the daily stack every day for the rest of the week.  Then, on the determined day of the week, shuffle together the weekly stack and the daily stack, and go through it all in order to create a new daily stack and weekly stack.  Once the weekly stack becomes smaller you can add more new flashcards to it.  The daily stack should never be so big that it takes too much time to get through; it should be between 10 and 50 cards, and take just a few minutes to get through.  The drive to school can be an ideal time to do the daily stack.  Once a card has been in the weekly stack for about two months and there seems to be no chance that it will ever be forgotten, then it can be put into the finished stack.  The goal is to have all of the flashcards end up in the finished stack.  Even this finished stack should be reviewed a couple times per year.

Read more:



[Read More...]


3rd Grade Arithmetic Facts Practice Sheets



All about these third grade arithmetic facts practice sheets

  • Free download! You can download our third grade arithmetic facts practice sheets for free from our website: www.meaningfulmathbooks.com.  On this website, there are also sheets designed for fourth and fifth grade, as well as a variety of other resources related to Making Math Meaningful books.



  • Facts of the Week!  (See next page.)  Central to the idea behind these sheets is that every week there are five facts on the board which the teacher works on with the whole class during the week in a variety of ways (e.g., using movement, rhythmical work, games, etc.).  These facts of the week then appear multiple times on the sheets for the current week, and are then reviewed systematically for the next several weeks. 
Background work.  These sheets should ideally be the culmination of two years of work.  If the work in first and second grade has been effective, then the children should feel that these sheets are easy.  If these sheets become too difficult and tedious, then it is likely that the classroom work being done in preparation for these sheets is either insufficient or not effective enough.

Timing and rhythm.  The intention is that the first practice sheet should be done at some point between the end of September and the end of October of third grade.  It can, of course, vary depending upon the class.  After that, a sheet should be done (nearly) every day until the whole set of 100 sheets is completed.  There are 20 weeks (100 days) of sheets in this set.  Each sheet has 30 problems.

Completion.  Since these sheets are designed to be an integral part of learning the math facts, it is important that each sheet of the entire set be completed, otherwise certain facts won’t get adequate exposure.

Caution!  This should be fun and easy for the students.  If successful, this builds their confidence.  It is important to make sure that these sheets don’t become torture for the students.  Try to de-emphasize the importance of speed.  Help the students to realize that improvement is what is important.
The whole picture.  The 30 problems listed on a particular sheet are only a part of the daily math practice.  It would be very unfortunate if daily math practice consisted of nothing more that the 30 arithmetic facts practice problems that appear on these sheets.
  • When the class is not in a math main lesson, daily math practice should take about 10 minutes.  The 30 arithmetic facts may take 3-5 minutes.  The remaining 5-7 minutes can be spent doing a couple of written (vertical) arithmetic problems, some brief rhythmical work, or something else.
  • When the class is in a math main lesson, daily math practice should take about 30 minutes.  The 30 arithmetic facts may take 3-5 minutes.  After that, the remaining 25 minutes of math practice (during a math main lesson) consists of the material that was brought in previous blocks and the current one.
The elements of math practice.  The following list shows some of the aspects to consider when planning math practice for the day.
  • Arithmetic facts practice sheet.  The teacher copies by hand the 30 problems from a given day (see following sheets) onto paper to be photocopied.[1]  (about 5 minutes)
  • Mental arithmetic.  The teacher may decide to read the first 6 problems orally.
  • Extra math practice problems.  There should be a few problems that the teacher comes up with and writes on the board.  The students copy them into their practice books and work out the answers.  These problems also include practice and review of material covered in previous math blocks.  (Takes 20-25 minutes if the class is in a math block, otherwise only 5 minutes.)
  • Challenge problems.  It is important that the last few problems (that the teacher adds on) be more challenging in order to keep the “quicker” students fully engaged.
What comes next?  The next set of practice sheets is titled Fourth Grade Arithmetic Facts Review Sheets, and is intended to thoroughly review the math facts covered on the first practice sheets.

The hope is that just five minutes per day practicing these arithmetic facts results in the whole class quite effortlessly learning their math facts by heart.

And what happens if…?  We hope that it won’t happen, but there may be a few children at the end of third grade who still haven’t learned their arithmetic facts.  In order to help these children, we can give them a multiplication/division table (i.e., a square for the tables).  Additionally, these students should study the basic arithmetic problems with flashcards during morning practice time.

Read more:
[Read More...]


12th Asian Pacific Mathematics Olympiad 2000 Problems



12th Asian Pacific Mathematics Olympiad 2000 Problems

A1.  Find a13/(1 - 3a1 + 3a12) + a23/(1 - 3a2 + 3a22) + ... + a1013/(1 - 3a101 + 3a1012), where an = n/101.
A2.  Find all permutations a1, a2, ... , a9 of 1, 2, ... , 9 such that a1 + a2 + a3 + a4 = a4 + a5 + a6 + a7 = a7 + a8 + a9 + a1 and a12 + a22 + a32 + a42 = a42 + a52 + a62 + a72 = a72 + a82 + a92 + a12.


A3.  ABC is a triangle. The angle bisector at A meets the side BC at X. The perpendicular to AX at X meets AB at Y. The perpendicular to AB at Y meets the ray AX at R. XY meets the median from A at S. Prove that RS is perpendicular to BC.
A4.  If m < n are positive integers prove that nn/(mm (n-m)n-m) > n!/( m! (n-m)! ) > nn/( mm(n+1) (n-m)n-m).
A5.  Given a permutation s0, s2, ... , sn of 0, 1, 2, .... , n, we may transform it if we can find i, j such that si = 0 and sj = si-1 + 1. The new permutation is obtained by transposing si and sj. For which n can we obtain (1, 2, ... , n, 0) by repeated transformations starting with (1, n, n-1, .. , 3, 2, 0)? 

Solutions
Find a13/(1 - 3a1 + 3a12) + a23/(1 - 3a2 + 3a22) + ... + a1013/(1 - 3a101 + 3a1012), where an = n/101.
Solution
Answer: 51.
The nth term is an3/(1 - 3an + 3an2) = an3/( (1 - an)3 + an3) = n3/( (101 - n)3 + n3). Hence the sum of the nth and (101-n)th terms is 1. Thus the sum from n = 1 to 100 is 50. The last term is 1, so the total sum is 51.

Find all permutations a1, a2, ... , a9 of 1, 2, ... , 9 such that a1 + a2 + a3 + a4 = a4 + a5 + a6 + a7 = a7 + a8 + a9 + a1 and a12 + a22 + a32 + a42 = a42 + a52 + a62 + a72 = a72 + a82 + a92 + a12.
Solution
We may start by assuming that a1 < a4 < a7 and that a2 < a3, a5 < a6, a8 < a9.
Note that 1 + ... + 9 = 45 and 12 + ... + 92 = 285. Adding the three square equations together we get (a12 + ... + a92) + a12 + a42 + a72 = 285 + a12 + a42 + a72. The total must be a multiple of 3. But 285 is a multiple of 3, so a12 + a42 + a72 must be a multiple of 3. Now 32, 62 and 92 are all congruent to 0 mod 3 and the other squares are all congruent to 1 mod 3. Hence either a1, a4 and a7 are all multiples of 3, or none of them are. Since 45 is also a multiple of three a similar argument with the three linear equations shows that a1 + a4 + a7 is a multiple of 3. So if none of a1, a4, a7 are multiples of 3, then they are all congruent to 1 mod 3 or all congruent to 2 mod 3. Thus we have three cases: (1) a1 = 3, a4 = 6, a7 = 9, (2) a1 = 1, a4 = 4, a7 = 7, and (3) a1 = 2, a4 = 5, a7 = 8.
In case (1), we have that each sum of squares equals 137. Hence a82 + a92 = 47. But 47 is not a sum of two squares, so this case gives no solutions.
In case (2), we have that each sum of squares is 117. Hence a52 + a62 = 52. But the only way of writing 52 as a sum of two squares is 42 + 62 and 4 is already taken by a4, so this case gives no solutions.
In case (3), we have that each sum of squares is 126 and each linear sum 20. We quickly find that the only solution is 2, 4, 9, 5, 1, 6, 8, 3, 7.
Obviously, this generates a large number of equivalent solutions. We can interchange a2 and a3, or a5 and a6, or a8 and a9. We can also permute a1, a4 and a7. So we get a total of 2 x 2 x 2 x 6 =48 solutions. 

ABC is a triangle. The angle bisector at A meets the side BC at X. The perpendicular to AX at X meets AB at Y. The perpendicular to AB at Y meets the ray AX at R. XY meets the median from A at S. Prove that RS is perpendicular to BC.
Solution
Let the line through C parallel to AX meet the ray BA at C'. Let the perpendicular from B meet the ray C'C at T and the ray AX at U. Let the line from C parallel to BT meet BA at V and let the perpendicular from V meet BT at W. So CVWT is a rectangle.
AU bisects ∠CAV and CV is perpendicular to AU, so U is the midpoint of WT. Hence the intersection N of AU and CW is the center of the rectangle and, in particular, the midpoint of CW. Let M be the midpoint of BC. Then since M, N are the midpoints of the sides CB and CW of the triangle CBW, MN = BW/2.
Since CC' is parallel to AX, ∠CC'A = ∠BAX = ∠CAX = ∠C'CA, so AC' = AC. Let A' be the midpoint of CC'. Then AU = C'T - C'A'. But N is the center of the rectangle CTWV, so NU = CT/2 and AN = AU - NU = C'T - C'A' - CT/2 = C'T/2. Hence MN/AN = BW/C'T. But MN is parallel to BW and XY, so SX/AX = MN/AN = BW/C'T.
Now AX is parallel to VW and XY is parallel to BW, so AXY and VWB are similar and AX/XY = VW/BW = CT/BW. Hence SX/XY = (SX/AX) (AX/XY) = CT/C'T.
YX is an altitude of the right-angled triangle AXR, so AXY and YXR are similar. Hence XY/XR = XA/XY. But AXY and C'TB are similar, so XA/XY = C'T/BT. Hence SX/XR = (SX/XY) (XY/XR) = (CT/C'T) (C'T/BT) = CT/BT. But angles CTB and SXR are both right angles, so SXR and CTB are similar. But XR is perpendicular to BT, so SR is perpendicular to BC. 

If m < n are positive integers prove that nn/(mm (n-m)n-m) > n!/( m! (n-m)! ) > nn/( mm(n+1) (n-m)n-m).
Solution
The key is to consider the binomial expansion (m + n-m)n. This is a sum of positive terms, one of which is nCm mm(n-m)n-m, where nCm is the binomial coefficient n!/( m! (n-m)! ). Hence nCm mm(n-m)n-m < nn, which is one of the required inequalities.
We will show that nCm mm(n-m)n-m is the largest term in the binomial expansion. It then follows that (n+1) nCm mm(n-m)n-m > nn, which is the other required inequality.
Comparing the rth term nCr mr(n-m)n-r with the r+1th term nCr+1 mr+1(n-m)n-r-1 we see that the rth term is strictly larger for r ≥ m and smaller for r < m. Hence the mth term is larger than the succeeding terms and also larger than the preceding terms.

Given a permutation s0, s2, ... , sn of 0, 1, 2, .... , n, we may transform it if we can find i, j such that si = 0 and sj = si-1 + 1. The new permutation is obtained by transposing si and sj. For which n can we obtain (1, 2, ... , n, 0) by repeated transformations starting with (1, n, n-1, .. , 3, 2, 0)?
Solution
Experimentation shows that we can do it for n=1 (already there), n = 2 (already there), 3, 7, 15, but not for n = 4, 5, 6, 8, 9, 10, 11, 12, 13, 14. So we conjecture that it is possible just for n = 2m - 1 and for n = 2.
Notice that there is at most one transformation possible. If n = 2m, then we find that after m-1 transformations we reach
1  n  0  n-2  n-1  n-4  n-3 ... 4  5  2  3
and we can go no further. So n even fails for n > 2.
If n = 15 we get successively:
1 15 14 13 12 11 10 9 8 7 6 5 4 3 2 0 start
1 0 14 15 12 13 10 11 8 9 6 7 4 5 2 3 after 7 moves
1 2 3 0 12 13 14 15 8 9 10 11 4 5 6 7 after 8 more moves
1 2 3 4 5 6 7 0 8 9 10 11 12 13 14 15 after 8 more moves
1   2   3   4   5   6   7   8   9  10  11  12  13  14  15   0   after 8 more moves
This pattern is general. Suppose n = 2m - 1. Let P0 be the starting position and Pr be the position:
1   2   3 ... R-1   0,   n-R+1  n-R+2  n-R+3 ... n,   n-2R+1  n-2R+2 ... n-R, ... , R  R+1 ... 2R-1 
Here R denotes 2r and the commas highlight that, after the initial 1 2 ... R-1 0, we have increasing runs of R terms. If we start from Pr, then the 0 is transposed successively with R, 3R, 5R, ... , n-R+1, then with R+1, 3R+1, ... , n-R+2, and so on up to 2R-1, 4R-1, ... , n. But that gives Pr+1. It is also easy to check that P0 leads to P1 and that Pm is the required finishing position. Thus the case n = 2m - 1 works. Now suppose n is odd but not of the form 2m - 1. Then we can write n = (2a + 1)2b - 1 (just take 2b as the highest power of 2 dividing n + 1). We can now define P0, P1, ... , Pb as before. As before we will reach Pb:
1 2 ¼ B-1 0, 2aB 2aB+1¼ (2a+1)B-1, (2a-1)B ¼ 2aB-1, ¼ , 3B, 3B+1, ¼ 4B-1, 2B, 2B+1, ¼ , 3B-1, B, B+1, ¼ , 2B-1 
where B = 2b - 1. But then the 0 is transposed successively with B, 3B, 5B, ... , (2a-1)B, which puts it immediately to the right of (2a+1)B-1 = n, so no further transformations are possible and n = (2a+1)2b - 1 fails.
[Read More...]


11th Asian Pacific Mathematics Olympiad 1999 Problems



11th Asian Pacific Mathematics Olympiad 1999 Problems

A1.  Find the smallest positive integer n such that no arithmetic progression of 1999 reals contains just n integers.
A2.  The real numbers x1, x2, x3, ... satisfy xi+j ≤ xi + xj for all i, j. Prove that x1 + x2/2 + ... + xn/n ≥ xn.


A3.  Two circles touch the line AB at A and B and intersect each other at X and Y with X nearer to the line AB. The tangent to the circle AXY at X meets the circle BXY at W. The ray AX meets BW at Z. Show that BW and BX are tangents to the circle XYZ.
A4.  Find all pairs of integers m, n such that m2 + 4n and n2 + 4m are both squares.
A5.  A set of 2n+1 points in the plane has no three collinear and no four concyclic. A circle is said to divide the set if it passes through 3 of the points and has exactly n - 1 points inside it. Show that the number of circles which divide the set is even iff n is even.

Find the smallest positive integer n such that no arithmetic progression of 1999 reals contains just n integers.
Solution
Answer: 70.
Using a difference of 1/n , where n does not divide 1999, we can get a progression of 1999 terms with m = [1998/n] or m = [1998/n] - 1 integers. Thus {0, 1/n, 2/n, ... , 1998/n} has m+1 integers, and {1/n, 2/n, ... , 1999/n} has m integers. So we are ok until n gets so large that the gap between [1998/n] and [1998/(n+1)] is 3 or more. This could happen for 1998/n - 1998/(n+1) just over 2 or n > 31. So checking, we find [1998/31] = 64, [1998/30] = 66, [1998/29] = 68, [1998/28] = 71.
We can get 68 integers with {1/29, 2/29, ... , 1999/29} and 69 with {0, 1/29, 2/29, ... , 1998/29}. We can get 71 with {1/28, 2/28, ... , 1999/28}, but we cannot get 70. Note that a progression with irrational difference gives at most 1 integer. A progression with difference a/b, where a and b are coprime integers, gives the same number of integers as a progression with difference 1/b. So it does not help to widen the class of progressions we are looking at.

The real numbers x1, x2, x3, ... satisfy xi+j <= xi + xj for all i, j. Prove that x1 + x2/2 + ... + xn/n >= xn.
Solution
We use induction. Suppose the result is true for n. We have:
x1 >= x1
x1 + x2/2 >= x2
...
x1 + x2/2 + ... + xn/n >= xn
Also: x1 + 2x2/2 + ... + nxn/n = x1 + ... + xn
Adding: (n+1) x1 + (n+1)x2/2 + ... + (n+1)xn/n >= 2(x1 + ... + xn). But rhs = (x1 + xn) + (x2 + xn-1) + ... + (xn + x1) >= n xn+1. Hence result.

Two circles touch the line AB at A and B and intersect each other at X and Y with X nearer to the line AB. The tangent to the circle AXY at X meets the circle BXY at W. The ray AX meets BW at Z. Show that BW and BX are tangents to the circle XYZ.
Solution
Let angle ZXW = a and angle ZWX = b. XW is tangent to circle AXY at X, so angle AYX = a. AB is tangent to circle AXY at A, so angle BAX = a. AB is tangent to circle BXY at B, so angle ABX = b. Thus, considering triangle ABX, angle BXZ = a+b. Considering triangle ZXW, angle BZX = a+b.
BXYW is cyclic, so angle BYX = angle BWX = b. Hence angle AYB = angle AYX + angle XYB = a+b = angle AZB. So AYZB is cyclic. Hence angle BYZ = angle BAZ = a. So angle XYZ = angle XYB + angle BYZ = a+b. Hence angle BZX = angle XYZ, so BZ is tangent to circle XYZ at Z. Similarly angle BXY = angle XYZ, so BX is tangent to circle XYZ at X.

Find all pairs of integers m, n such that m2 + 4n and n2 +4m are both squares.
Solution
Answer: (m, n) or (n, m) = (0, a2), (-5, -6), (-4, -4), (a+1, -a) where a is a non-negative integer.
Clearly if one of m, n is zero, then the other must be a square and that is a solution.
If both are positive, then m2 + 4n must be (m + 2k)2 for some positive k, so n = km + k2 > m. But similarly m > n. Contradiction. So there are no solutions with m and n positive.
Suppose both are negative. Put m = -M, n = -N, so M and N are both positive. Assume M >= N. M2 - 4N is a square, so it must be (M - 2k)2 for some k, so N = Mk - k2. If M = N, then M(k-1) = k2, so k-1 divides k2 and hence k2 - (k-1)(k+1) = 1, so k = 2 and M = 4, giving the solution (m, n) = (-4, -4). So we may assume M > N and hence M > Mk - k2 > 0. But that implies that k = 1 or M-1 and hence N = M-1. [If M > Mk - k2, then (k-1)M < k2. Hence k = 1 or M < k+2. But Mk - k2 > 0, so M > k. Hence k = 1 or M = k+1.].
But N2 - 4M is also a square, so (M-1)2 - 4M = M2 - 6M + 1 is a square. But (M-3)2 > M2 - 6M + 1 and (M-4)2 < M2 - 6M + 1 for M >= 8, so the only possible solutions are M = 1, 2, ... , 7. Checking, we find that only M = 6 gives M2 - 6M + 1 a square. This gives the soluton (m, n) = (-6, -5). Obviously, there is also the solution (-5, -6).
Finally, consider the case of opposite signs. Suppose m = M > 0, n = -N < 0. Then N2 + 4M is a square, so by the argument above M > N. But M2 - 4N is a square and so the argument above gives N = M-1. Now we can easily check that (m, n) = (M, -(M-1) ) is a solution for any positive M.

A set of 2n+1 points in the plane has no three collinear and no four concyclic. A circle is said to divide the set if it passes through 3 of the points and has exactly n - 1 points inside it. Show that the number of circles which divide the set is even iff n is even.
Solution
Take two of the points, A and B, and consider the 2n-1 circles through A and B. We will show that the number of these circles which divide the set is odd. The result then follows almost immediately, because the number of pairs A, B is (2n+1)2n/2 = N, say. The total number of circles which divide the set is a sum of N odd numbers divided by 3 (because each such circle will be counted three times). If n is even, then N is even, so a sum of N odd numbers is even. If n is odd, then N is odd, so a sum of N odd numbers is odd. Dividing by 3 does not change the parity.
Their centers all lie on the perpendicular bisector of AB. Label them C1, C2, ... , C2n-1, where the center of Ci lies to the left of Cj on the bisector iff i < j. We call the two half-planes created by AB the left-hand half-plane L and the right-hand half-plane R correspondingly. Let the third point of the set on Ci be Xi. Suppose i < j. Then Ci contains all points of Cj that lie in L and Cj contains all points of Ci that lie R. So Xi lies inside Cj iff Xi lies in R and Xj lies inside Ci iff Xj lies in L
Now plot f(i), the number of points in the set that lie inside Ci, as a function of i. If Xi and Xi+1 are on opposite sides of AB, then f(i+1) = f(i). If they are both in L, then f(i+1) = f(i) - 1, and if they are both in R, then f(i+1) = f(i) + 1. Suppose m of the Xi lie in L and 2n-1-m lie in R. Now suppose f(i) = n-2, f(i+1) = f(i+2) = ... = f(i+j) = n-1, f(i+j+1) = n. Then j must be odd. For Xi and Xi+1 must lie in R. Then the points must alternate, so Xi+2 lies in L, Xi+3 lies in R etc. But Xi+j and Xi+j+1 must lie in R. Hence j must be odd. On the other hand, if f(i+j+1) = n-2, then j must be even. So the parity of the number of C1, C2, ... , Ci which divide the set only changes when f crosses the line n-1 from one side to the other. We now want to say that f starts on one side of the line n-1 and ends on the other, so the final parity must be odd. Suppose there are m points in L and hence 2n-1-m in R. Without loss of generality we may take m <= n-1. The first circle C1 contains all the points in L except X1 if it is in L. So f(1) = m or m-1. Similarly the last circle C2n-1 contains all the points in R except X2n-1 if it is in R. So f(2n-1) = 2n-1-m or 2n-2-m. Hence if m < n-1, then f(1) = m or m-1, so f(1) < n-1. But 2n-1-m >= n+1, so f(2n-1) > n-1. So in this case we are done.
However, there are complications if m = n-1. We have to consider 4 cases. Case (1): m = n-1, X1 lies in R, X2n-1 lies in L. Hence f(1) = n-1, f(2n-1) = n > n-1. So f starts on the line n-1. If it first leaves it downwards, then for the previous point i, Xi is in L and hence there were an even number of points up to i on the line. So the parity is the same as if f(1) was below the line. f(2n-1) is above the line, so we get an odd number of points on the line. If f first leaves the line upwards, then for the previous point i, Xi is in R and hence there were an odd number of points up to i on the line. So again the parity is the same as if f(1) was below the line.
Case (2): m = n-1, X1 lies in R, X2n-1 lies in R. Hence f(1) = f(2n-1) = n-1. As in case (1) the parity is the same as if f(1) was below the line. If the last point j with f(j) not on the line has f(j) < n-1, then (since X2n-1 lies in R) there are an odd number of points above j, so the parity is the same as if f(2n-1) was above the line. Similarly if f(j) > n-1, then there are an even number of points above j, so again the parity is the same as if f(2n-1) was above the line.
Case (3): m = n-1, X1 lies in L, X2n-1 lies in L. Hence f(1) = n-2, f(2n-1) = n. So case has already been covered.
Case (4): m=n-1, X1 lies in L, Xn-1 lies in R. So f(1) = n-2, f(2n-1) = n-1. As in case (2), the parity is the same as if f(2n-1) was above the line.
[Read More...]


10th Asian Pacific Mathematics Olympiad 1998 Problems



10th Asian Pacific Mathematics Olympiad 1998 Problems

A1.  S is the set of all possible n-tuples (X1, X2, ... , Xn) where each Xi is a subset of {1, 2, ... , 1998}. For each member k of S let f(k) be the number of elements in the union of its n elements. Find the sum of f(k) over all k in S.


A2.  Show that (36m + n)(m + 36n) is not a power of 2 for any positive integers m, n.
A3.  Prove that (1 + x/y)(1 + y/z)(1 + z/x) ≥ 2 + 2(x + y + z)/w for all positive reals x, y, z, where w is the cube root of xyz.
A4.  ABC is a triangle. AD is an altitude. X lies on the circle ABD and Y lies on the circle ACD. X, D and Y are collinear. M is the midpoint of XY and M' is the midpoint of BC. Prove that MM' is perpendicular to AM.
A5.  What is the largest integer divisible by all positive integers less than its cube root.

Solutions

S is the set of all possible n-tuples (X1, X2, ... , Xn) where each Xi is a subset of {1, 2, ... , 1998}. For each member k of S let f(k) be the number of elements in the union of its n elements. Find the sum of f(k) over all k in S.
Solution
Answer: 1998(21998n - 21997n).
Let s(n, m) be the sum where each Xi is a subset of {1, 2, ... , m}. There are 2m possible Xi and hence 2mn possible n-tuples. We have s(n, m) = 2ns(n, m-1) + (2n - 1)2n(m-1) (*). For given any n-tuple {X1, ... , Xn} of subsets of {1, 2, ... , m-1} we can choose to add m or not (2 choices) to each Xi. So we derive 2n n-tuples of subsets of {1, 2, ... , m}. All but 1 of these have f(k) incremented by 1. The first term in (*) gives the sum for m-1 over the increased number of terms and the second term gives the increments to the f(k) due to the additional element.
Evidently s(n, 1) = 2n - 1. It is now an easy induction to show that s(n, m) = m(2nm - 2n(m-1)).
Putting m = 1998 we get that the required sum is 1998(21998n - 21997n). 

Show that (36m + n)(m + 36n) is not a power of 2 for any positive integers m, n.
Solution
Assume there is a solution. Take m ≤ n and the smallest possible m. Now (36m + n) and (m + 36n) must each be powers of 2. Hence 4 divides n and 4 divides m. So m/2 and n/2 is a smaller solution with m/2 < m. Contradiction.

Prove that (1 + x/y)(1 + y/z)(1 + z/x) ≥ 2 + 2(x + y + z)/w for all positive reals x, y, z, where w is the cube root of xyz.
Solution
(1 + x/y)(1 + y/z)(1 + z/x) = 1 + x/y + y/x + y/z + z/y + z/x + x/z = (x + y + z)(1/x + 1/y + 1/z) - 1 ≥ 3(x + y + z)/w - 1, by the arithmetic geometric mean inequality,
= 2(x + y + z)/w + (x + y + z)/w - 1 ≥ 2(x + y + z) + 3 - 1, by the arithmetic geometric mean inequality.

ABC is a triangle. AD is an altitude. X lies on the circle ABD and Y lies on the circle ACD. X, D and Y are collinear. M is the midpoint of XY and M' is the midpoint of BC. Prove that MM' is perpendicular to AM
Solution
Take P, Q so that PADB, AQCD are rectangles. Let N be the midpoint of PQ. Then PD is a diameter of the circumcircle of ABC, so PX is perpendicular to XY. Similarly, QY is perpendicular to XY. N is the midpoint of PQ and M' the midpoint of XY, so NM is parallel to PX and hence perpendicular to XY. NADM' is a rectangle, so ND is a diameter of its circumcircle and M must lie on the circumcircle. But AM' is also a diameter, so ∠AMM' = 90o.
Thanks to Michael Lipnowski for the above. My original solution is below.
Let P be the circumcenter of ABD and Q the circumcenter of ADC. Let R be the midpoint of AM'. P and Q both lie on the perpendicular bisector of AD, which is parallel to BC and hence also passes through R. We show first that R is the midpoint of PQ.
Let the feet of the perpendiculars from P, Q, R to BC to P', Q', R' respectively. It is sufficient to show that . BP' = BD/2. BR' = BM' + M'R' = (BD + DC)/2 + M'D/2 = (BD + DC)/2 + ( (BD + DC)/2 - DC)/2 = 3BD/4 + DC/4, so P'R' = (BD + DC)/4. Q'C = DC/2, so BQ' = BD + DC/2 and P'Q' = (BD + DC)/2 = 2P'R'.
Now the circumcircle centre P meets XY in X and D, and the circumcircle centre Q meets XY in D and Y. Without loss of generality we may take XD >= DY. Put XD = 4x, DY = 4y. The circle center R through A, M' and D meets XY in a second point, say M''. Let the feet of the perpendiculars from P, Q, R to XY be P'', Q'', R'' respectively. So on XY we have, in order, X, P'', M'', R'', D, Q'', Y. Since R is the midpoint of PQ, R'' is the midpoint of P''Q''. Now P'' is the midpoint of XD and Q'' is the midpoint of DY, so P''Q'' = XY/2 = 2(x+y), so R''Q'' = x+y. But DQ'' = 2y, so R''D = x-y. R'' is the midpoint of M''D, so M''D = 2(x-y) and hence M''Y = M''D + DY = 2(x-y) + 4y = 2(x+y) = XY/2. So M'' is just M the midpoint of XY. Now AM' is a diameter of the circle center R, so AM is perpendicular to MM'. 

What is the largest integer divisible by all positive integers less than its cube root.
Solution
Answer: 420.
Let N be a positive integer satisfying the condition and let n be the largest integer not exceeding its cube root. If n = 7, then 3·4·5·7 = 420 must divide N. But N cannot exceed 83 - 1 = 511, so the largest such N is 420.
If n ≥ 8, then 3·8·5·7 = 840 divides N, so N > 729 = 93. Hence 9 divides N, and hence 3·840 = 2520 divides N. But we show that no N > 2000 can satisfy the condition.
Note that 2(x - 1)3 > x3 for any x > 4. Hence [x]3 > x3/2 for x > 4. So certainly if N > 2000, we have n3 > N/2. Now let pk be the highest power of k which does not exceed n. Then pk > n/k. Hence p2p3p5 > n3/30 > N/60. But since N > 2000, we have 7 < 11 < n and hence p2, p3, p5, 7, 11 are all ≤ n. But 77 p2p3p5 > N, so N cannot satisfy the condition.
[Read More...]


Fun Math Games for Kids

 
Return to top of page Copyright © 2010 Copyright 2010 (C) CoolMath4Kids - Cool Math 4 Kids - Cool Math Games 4 Kids - Coolmath4kids Bloxorz - Coolmath-4kids - Math games, Fun Math Lessons, Puzzles and Brain Benders, Flash Cards for Addition, Subtration, Multiplication, Fraction, Division - Cool Math 4 Kids - Math Games, Math Puzzles, Math Lessons - Cool Math 4 Kids Math Lessones - 4KidsMathGames - CoolMath Games4Kids coolmath4kids.info. All right reseved.