3. Let a, b, c be real numbers and let M be the maximum of the function
y = |4x
3
+ ax
2
+ bx + c| in the interval [−1, 1]. Show that M ≥ 1
and find all cases where equality occurs.
Solution: For a = 0, b = −3, c = 0, we have M = 1, with the
maximum achieved at −1, −1/2, 1/2, 1. On the other hand, if M < 1
for some choice of a, b, c, then
(4x
3
+ ax
2
+ bx + c) − (4x
3
+ 3x)
must be positive at −1, negative at −1/2, positive at 1/2, and
negative at 1, which is impossible for a quadratic function. Thus
M ≥ 1, and the same argument shows that equality only occurs for
(a, b, c) = (0, −3, 0). (Note: this is a particular case of the minimum
deviation property of Chebyshev polynomials.)
4. The real numbers a
1
, a
2
, . . . , a
n
(n ≥ 3) form an arithmetic progres-
sion. There exists a permutation a
i
1
, a
i
2
, . . . , a
i
n
of a
1
, a
2
, . . . , a
n
which is a geometric progression. Find the numbers a
1
, a
2
, . . . , a
n
if
they are all different and the largest of them is equal to 1996.
Solution: Let a
1
< a
2
< ··· < a
n
= 1996 and let q be the ratio of
the geometric progression a
i
1
, . . . a
i
n
; clearly q = 0, ±1. By reversing
the geometric progression if needed, we may assume |q| > 1, and so
|a
i
1
| < |a
i
2
| < ··· < |a
i
n
|. Note that either all of the terms are
positive, or they alternate in sign; in the latter case, the terms of
either sign form a geometric progression by themselves.
There cannot be three positive terms, or else we would have a three-
term geometric progression a, b, c which is also an arithmetic pro-
gression, violating the AM-GM inequality. Similarly, there cannot
be three negative terms, so there are at most two terms of each sign
and n ≤ 4.
If n = 4, we have a
1
< a
2
< 0 < a
3
< a
4
and 2a
2
= a
1
+ a
3
,
2a
3
= a
2
+ a
4
. In this case, q < −1 and the geometric progression is
either a
3
, a
2
, a
4
, a
1
or a
2
, a
3
, a
1
, a
4
. Suppose the former occurs (the
argument is similar in the latter case); then 2a
3
q = a
3
q
3
+ a
3
and
2a
3
+ a
3
q + a
3
q
2
, giving q = 1, a contradiction.
We deduce n = 3 and consider two possibilities. If a
1
< a
2
<
0 < a
3
= 1996, then 2a
2
= a
2
q
2
+ a
2
q, so q
2
+ q − 2 = 0 and
4
q = −2, yielding (a
1
, a
2
, a
3
) = (−3992, −998, 1996). If a
1
< 0 <
a
2
< a
3
= 1996, then 2a
2
= a
2
q + a
2
q
2
, so again q = −2, yielding
(a
1
, a
2
, a
3
) = (−998, 499, 1996).
5. A convex quadrilateral ABC is given for which ∠ABC + ∠BCD <
180
◦
. The common point of the lines AB and CD is E. Prove that
∠ABC = ∠ADC if and only if
AC
2
= CD · CE −AB ·AE.
Solution: Let C
1
be the circumcircle of ADE, and let F be its
second intersection with CA. In terms of directed lengths, we have
AC
2
= CD · CE + AB ·AE if and only if
AB · AE = AC
2
− CD · CE = CA
2
− CA · AF = AC ·AF,
that is, if and only if B, C, E, F are concyclic. But this happens if
and only if ∠EBC = ∠EF C, and
∠EF C = ∠EF A = π − ∠ADE = ∠CDA
(in directed angles modulo π), so B, C, E, F are concyclic if and only
if ∠ABC = ∠ADC (as undirected angles), as desired.
6. Find all prime numbers p, q for which pq divides (5
p
− 2
p
)(5
q
− 2
q
).
Solution: If p|5
p
−2
p
, then p|5 −2 by Fermat’s theorem, so p = 3.
Suppose p, q = 3; then p|5
q
− 2
q
and q|5
p
− 2
p
. Without loss of
generality, assume p > q, so that (p, q − 1) = 1. Then if a is an
integer such that 2a ≡ 5 (mod q), then the order of a mod q divides
p as well as q − 1, a contradiction.
Hence one of p, q is equal to 3. If q = 3, then q|5
3
− 2
3
= 9 · 13, so
q = 13, and similarly p ∈ {3, 13}. Thus the solutions are (p, q) =
(3, 3), (3, 13), (13, 3).
7. Find the side length of the smallest equilateral triangle in which
three discs of radii 2, 3, 4 can be placed without overlap.
Solution: A short computation shows that discs of radii 3 and 4
can be fit into two corners of an equilateral triangle of side 11
√
3 so
5
as to just touch, and that a disc of radius 2 easily fits into the third
corner without overlap. On the other hand, if the discs of radii 3
and 4 fit into an equilateral triangle without overlap, there exists a
line separating them (e.g. a tangent to one perpendicular to their
line of centers) dividing the triangle into a triangle and a (possibly
degenerate) convex quadrilateral. Within each piece, the disc can be
moved into one of the corners of the original triangle. Thus the two
discs fit into the corners without overlap, so the side length of the
triangle must be at least 11
√
3.
8. The quadratic polynomials f and g with real coefficients are such
that if g(x) is an integer for some x > 0, then so is f(x). Prove that
there exist integers m, n such that f (x) = mg(x) + n for all x.
Solution: Let f(x) = ax
2
+ bx + c and g(x) = px
2
+ qx + r;
assume without loss of generality p > 0 and q = 0 (by the change
of variable x → x − q/(2p)). Let k be an integer such that k > s
and t =
(k − s)/p > q/(2p). Since g(t) = k is an integer, so is
f(t) = a(k − s)/p + bt + c, as is
f
k + 1 − s
p
− f
k − s
p
=
b
√
p
1
√
k + 1 − s −
√
k − s
+
a
p
.
This tends to a/p as k increases, so a/p must be an integer; moreover,
b must equal 0, or else the above expression will equal a/p plus a
small quantity for large k, which cannot be an integer. Now put
m = a/p and n = c − ms; then f(x) = mg(x) + n.
9. The sequence {a
n
}
∞
n=1
is defined by
a
1
= 1, a
n+1
=
a
n
n
+
n
a
n
, n ≥ 1.
Prove that for n ≥ 4, a
2
n
= n.
Solution: We will show by induction that
√
n ≤ a
n
≤ n/
√
n − 1
for n ≥ 1, which will imply the claim. These inequalities clearly
hold for n = 1, 2, 3. Now assume the inequality for some n. Let
f
n
(x) = x/n + n/x. We first have for n ≥ 3,
a
n+1
= f
n
(a
n
) ≥ f
n
n
√
n − 1
=
n
√
n − 1
>
√
n + 1.
6
On the other hand, using that a
n
> (n − 1)/
√
n − 2 (which we just
proved), we get for n ≥ 4,
a
n+1
= f
n
(a
n
) < f
n
n − 1
√
n − 2
=
(n − 1)
2
+ n
2
(n − 2)
(n − 1)n
√
n − 2
<
√
n + 2.
10. The quadrilateral ABCD is inscribed in a circle. The lines AB
and CD meet at E, while the diagonals AC and BD meet at F .
The circumcircles of the triangles AF D and BFC meet again at H.
Prove that ∠EHF = 90
◦
.
Solution: (We use directed angles modulo π.) Let O be the
circumcenter of ABCD; then
∠AHB = ∠AHF +∠F HB = ∠ADF +∠F CB = 2∠ADB = ∠AOB,
so O lies on the circumcircle of AHB, and similarly on the circum-
circle of CHD. The radical axes of the circumcircles of AHB, CHD
and ABCD concur; these lines are AB, CD and HO, so E, H, O are
collinear. Now note that
∠OHF = ∠OHC+∠CHF = ∠ODC+∠CBF =
π
2
−∠CAD+∠CBD,
so ∠EHF = ∠OHF = π/2 as desired. (Compare IMO 1985/5.)
11. A 7 × 7 chessboard is given with its four corners deleted.
(a) What is the smallest number of squares which can be colored
black so that an uncolored 5-square (Greek) cross cannot be
found?
(b) Prove that an integer can be written in each square such that
the sum of the integers in each 5-square cross is negative while
the sum of the numbers in all squares of the board is positive.
Solution:
(a) The 7 squares
(2, 5), (3, 2), (3, 3), (4, 6), (5, 4), (6, 2), (6, 5)
7
suffice, so we need only show that 6 or fewer will not suffice.
The crosses centered at
(2, 2), (2, 6), (3, 4), (5, 2), (5, 6), (6, 4)
are disjoint, so one square must be colored in each, hence 5
or fewer squares do not suffice. Suppose exactly 6 squares are
colored. Then none of the squares (1, 3), (1, 4), (7, 2) can be col-
ored; by a series of similar arguments, no square on the perime-
ter can be colored. Similarly, (4, 3) and (4, 5) are not covered,
and by a similar argument, neither is (3, 4) or (5, 4). Thus the
center square (4, 4) must be covered.
Now the crosses centered at
(2, 6), (3, 3), (5, 2), (5, 6), (6, 4)
are disjoint and none contains the center square, so each con-
tains one colored square. In particular, (2, 2) and (2, 4) are not
colored. Replacing (3, 3) with (2, 3) in the list shows that (3, 2)
and (3, 4) are not colored. Similar symmetric arguments now
show that no squares besides the center square can be covered,
a contradiction. Thus 7 squares are needed.
(b) Write −5 in the 7 squares listed above and 1 in the remaining
squares. Then clearly each cross has negative sum, but the total
of all of the numbers is 5(−7) + (45 − 7) = 3.
8
1.2 Canada
1. If α, β, γ are the roots of x
3
− x − 1 = 0, compute
1 − α
1 + α
+
1 − β
1 + β
+
1 − γ
1 + γ
.
Solution: The given quantity equals
2
1
α + 1
+
1
β + 1
+
1
γ + 1
− 3.
Since P (x) = x
3
−x−1 has roots α, β, γ, the polynomial P (x −1) =
x
3
−3x
2
+2x−1 has roots α + 1, β + 1, γ +1. By a standard formula,
the sum of the reciprocals of the roots of x
3
+ c
2
x
2
+ c
1
x + c
0
is
−c
1
/c
0
, so the given expression equals 2(2) − 3 = 1.
2. Find all real solutions to the following system of equations:
4x
2
1 + 4x
2
= y
4y
2
1 + 4y
2
= z
4z
2
1 + 4z
2
= x.
Solution: Define f(x) = 4x
2
/(1 + 4x
2
); the range of f is [0, 1),
so x, y, z must lie in that interval. If one of x, y, z is zero, then all
three are, so assume they are nonzero. Then f(x)/x = 4x/(1 +
4x
2
) is at least 1 by the AM-GM inequality, with equality for x =
1/2. Therefore x ≤ y ≤ z ≤ x, and so equality holds everywhere,
implying x = y = z = 1/2. Thus the solutions are (x, y, z) =
(0, 0, 0), (1/2, 1/2, 1/2).
3. Let f (n) be the number of permutations a
1
, . . . , a
n
of the integers
1, . . . , n such that
(i) a
1
= 1;
(ii) |a
i
− a
i+1
| ≤ 2, i = 1, . . . , n − 1.
9
Determine whether f(1996) is divisible by 3.
Solution: Let g(n) be the number of permutations of the desired
form with a
n
= n. Then either a
n−1
= n − 1 or a
n−1
= n − 2; in
the latter case we must have a
n−2
= n −1 and a
n−3
= n −3. Hence
g(n) = g(n −1) + g(n −3) for n ≥ 4. In particular, the values of g(n)
modulo 3 are g(1) = 1, 1, 1, 2, 0, 1, 0, 0, . . . repeating with period 8.
Now let h(n) = f(n)−g(n); h(n) counts permutations of the desired
form where n occurs in the middle, sandwiched between n−1 and n−
2. Removing n leaves an acceptable permutation, and any acceptable
permutation on n−1 symbols can be so produced except those ending
in n−4, n−2, n−3, n−1. Hence h(n) = h(n−1)+g(n−1)−g(n−4) =
h(n−1)+g(n−2); one checks that h(n) modulo 3 repeats with period
24.
Since 1996 ≡ 4 (mod 24), we have f (1996) ≡ f(4) = 4 (mod 3), so
f(1996) is not divisible by 3.
4. Let ABC be an isosceles triangle with AB = AC. Suppose that
the angle bisector of ∠B meets AC at D and that BC = BD + AD.
Determine ∠A.
Solution: Let α = ∠A, β = (π − α)/4 and assume AB = 1. Then
by the Law of Sines,
BC =
sin α
sin 2β
, BD =
sin α
sin 3β
, AD =
sin β
sin 3β
.
Thus we are seeking a solution to the equation
sin(π − 4β) sin 3β = (sin(π − 4β) + sin β) sin 2β.
Using the sum-to-product formula, we rewrite this as
cos β − cos 7β = cos 2β −cos 6β + cos β − cos 3β.
Cancelling cos β, we have cos 3β − cos 7β = cos 2β − cos 6β, which
implies
sin 2β sin 5β = sin 2β sin 4β.
Now sin 5β = sin 4β, so 9β = π and β = π/9.
10
5. Let r
1
, r
2
, . . . , r
m
be a given set of positive rational numbers whose
sum is 1. Define the function f by f(n) = n −
m
k=1
r
k
n for each
positive integer n. Determine the minimum and maximum values of
f(n).
Solution: Of course r
k
n ≤ r
k
n, so f(n) ≥ 0, with equality for
n = 0, so 0 is the minimum value. On the other hand, we have
r
k
n −r
k
n < 1, so f (n) ≤ m −1. Here equality holds for n = t −1
if t is the least common denominator of the r
k
.
11
1.3 China
1. Let H be the orthocenter of acute triangle ABC. The tangents from
A to the circle with diameter BC touch the circle at P and Q. Prove
that P, Q, H are collinear.
Solution: The line P Q is the polar of A with respect to the circle,
so it suffices to show that A lies on the pole of H. Let D and E
be the feet of the altitudes from A and B, respectively; these also
lie on the circle, and H = AD ∩ BE. The polar of the line AD
is the intersection of the tangents AA and DD, and the polar of
the line BE is the intersection of the tangents BB and EE. The
collinearity of these two intersections with C = AE∩BD follows from
applying Pascal’s theorem to the cyclic hexagons AABDDE and
ABBDEE. (An elementary solution with vectors is also possible
and not difficult.)
2. Find the smallest positive integer K such that every K-element sub-
set of {1, 2, . . . , 50} contains two distinct elements a, b such that a+b
divides ab.
Solution: The minimal value is k = 39. Suppose a, b ∈ S are such
that a + b divides ab. Let c = gcd(a, b), and put a = ca
1
, b = cb
1
, so
that a
1
and b
1
are relatively prime. Then c(a
1
+ b
1
) divides c
2
a
1
b
1
,
so a
1
+ b
1
divides ca
1
b
1
. Since a
1
and b
1
have no common factor,
neither do a
1
and a
1
+ b
1
, or b
1
and a
1
+ b
1
. In short, a
1
+ b
1
divides
c.
Since S ⊆ {1, . . . , 50}, we have a + b ≤ 99, so c(a
1
+ b
1
) ≤ 99, which
implies a
1
+ b
1
≤ 9; on the other hand, of course a
1
+ b
1
≥ 3. An
exhaustive search produces 23 pairs a, b satisfying the condition:
a
1
+ b
1
= 3 (6, 3), (12, 6), (18, 9), (24, 12),
(30, 15), (36, 18), (42, 21), (48, 24)
a
1
+ b
1
= 4 (12, 4), (24, 8), (36, 12), (48, 16)
a
1
+ b
1
= 5 (20, 5), (40, 10), (15, 10), (30, 20), (45, 30)
a
1
+ b
1
= 6 (30, 6)
a
1
+ b
1
= 7 (42, 7), (35, 14), (28, 21)
a
1
+ b
1
= 8 (40, 24)
a
1
+ b
1
= 9 (45, 36)
12
Let M = {6, 12, 15, 18, 20, 21, 24, 35, 40, 42, 45, 48}and T = {1, . . . , 50}−
M. Since each pair listed above contains an element of M, T does
not have the desired property. Hence we must take k ≥ |T |+1 = 39.
On the other hand, from the 23 pairs mentioned above we can select
12 pairs which are mutually disjoint:
(6, 3), (12, 4), (20, 5), (42, 7), (24, 8), (18, 9),
(40, 10), (35, 14), (30, 15), (48, 16), (28, 21), (45, 36).
Any 39-element subset must contain both elements of one of these
pairs. We conclude the desired minimal number is k = 39.
3. Let f : R → R be a function such that for all x, y ∈ R,
f(x
3
+ y
3
) = (x + y)(f(x)
2
− f(x)f(y) + f(y)
2
). (1)
Prove that for all x ∈ R, f(1996x) = 1996f(x).
Solution: Setting x = y = 0 in the given equation, we have
f(0) = 0. Setting y = 0, we find f (x
3
) = xf(x)
2
, or equivalently,
f(x) = x
1/3
f(x
1/3
)
2
. (2)
In particular, x and f (x) always have the same sign, that is, f(x) ≥ 0
for x ≥ 0 and f(x) ≤ 0 for x ≤ 0.
Let S be the set
S = {a > 0 : f(ax) = af(x)∀x ∈ R}.
Clearly 1 ∈ S; we will show a
1/3
∈ S whenever a ∈ S. In fact,
axf(x)
2
= af(x
3
) = f(ax
3
) = f((a
1/3
x)
3
) = a
1/3
f(a
1/3
x)
2
and so
[a
1/3
f(x)]
2
= f(a
1/3
x)
2
.
Since x and f(x) have the same sign, we conclude f(a
1/3
x) = a
1/3
f(x).
Now we show that a, b ∈ S implies a + b ∈ S:
f((a + b)x) = f((a
1/3
x
1/3
)
3
+ (b
1/3
x
1/3
)
3
)
= (a
1/3
+ b
1/3
)[f(a
1/3
x
1/3
)
2
− f(a
1/3
x
1/3
)f(b
1/3
x
1/3
) + f(b
1/3
x
1/3
)
2
]
= (a
1/3
+ b
1/3
)(a
2/3
− a
1/3
b
1/3
+ b
2/3
)x
1/3
f(x
1/3
)
2
= (a + b)f(x).
13
Không có nhận xét nào:
Đăng nhận xét