Hi, steeprock-ga:
Where necessary to make the problem sensible, assumptions are stated
at the beginning of each part. In some parts I have shown a little
more than what was required by the strict wording of the problem (and
in some cases this extra effort may tax the reader's patience). Be
forwarned, but I have also tried to indicate what sections of
reasoning might be considered "additional credit".
1. Although it seems to be a multi-variable calculus exercise, this
part of the problem can be answered with just some algebra and
elementary inequalities involving a function of one variable.
Lemma: (t + 1/t) >= 2 for all t > 0, with equality only at t = 1.
Proof: One could show this basic calculus, but here's a more
elementary approach.
For all t > 0, t^2 - 2t + 1 = (t - 1)^2 >= 0 with equality only if t
= 1.
Thus t^2 + 1 >= 2t, and since t > 0, we can divide both sides by t to
get the desired result:
t + 1/t >= 2
Note that by reversing steps, equality in the final form would imply
equality in the original form, i.e. t = 1.
QED
Now consider the value for the expression:
(x + y + z)(xy + xz + yz)/(xyz)
where x,y,z are any positive values. Setting x,y,z all equal to one
another yields:
(3x)(3x^2)/(x^3) = 9
It remains only to show that this is the smallest possible value. We
will also sketch a proof, though it was not specified in the problem,
that this minimum is attained only when x = y = z.
Let r = (xyz)^(1/3) be the geometric mean of x,y,z.
Define X = x/r, Y = y/r, Z = z/r.
Then XYZ = 1, and:
(x + y + z)(xy + xz + yz)/(xyz) = (X + Y + Z)(XY + XZ + YZ)
after the three factors r^3 = xyz from the denominator are
appropriately distributed.
Expanding the product above gives nine terms, which can be arranged
like this:
XXY + XXZ + XYZ + XYY + XYZ + YYZ + XYZ + XZZ + YZZ
= (XXY + YZZ) + (XXZ + YYZ) + (XYY + XZZ) + 3XYZ
Now, using the relation XYZ = 1, we recognize that each parenthesized
pair of terms in this last formula are reciprocals. Since YZZ =
1/(XXY), YYZ = 1/(XXZ), and XZZ = 1/(XYY), each such pair is of the
form t + 1/t for suitable positive value of t. Therefore the entire
expression is bounded below by:
(XXY + YZZ) + (XXZ + YYZ) + (XYY + XZZ) + 3XYZ >= 2 + 2 + 2 + 3 = 9
just as we wished to show. On the other hand, equality would require
equality of each pair of terms in parentheses to 2, so that equality
requires (by the Lemma's second part):
XXY = YZZ = XXZ = YYZ = XYY = XZZ = 1
But this in turn requires X = Z (since XXY = XYZ), etc. Thus:
X = Y = Z = 1
which requires x = y = z. This completes the demonstration.
2. To make sense of this problem it is necessary to assume that "O is
the center of the isoceles triangle" was meant to be "O is the
circumcenter of the isoceles triangle". The circumcenter is but one
center of a circle associated with a triangle. Some others are the
"incenter", the "orthocenter", and the "barycenter". Please send a
Request for Clarification if you would like more details about these
alternative definitions for "center" of a triangle.
Let A be the apex of an isoceles triangle with base endpoints B and C
as described in the problem. Let O be the circumcenter of this
triangle as restated in my assumption above. Furthermore let P be the
circumcenter of the triangle AOB. We are asked to show that the
circle circumscribing AOB is tangent to AC. An equivalent statement
is to show that the radius PA of that circle is perpendicular to AC at
point A, for a line is tangent to a circle when it meets a radius
perpendicularly at a point on the circle.
That is, we aim to show angle PAC is a right angle, and this is
sufficient to establish the required tangency.
Let us begin once more with a simple result:
Lemma: The circumcenter of an isoceles triangle lies on the angle
bisector drawn from its apex to its base, and this line also
perpendicularly bisects the base.
Proof: The circumcenter is necessarily equidistant from both
endpoints of the base of an isoceles triangle, and so it lies on the
perpendicular bisector of the base. But in an isoceles triangle that
perpendicular bisector is shown to coincide with the angle bisector
from the apex to the base, by congruence of the two halves of the
isoceles triangle thus created. Thus this perpendicular bisector is
also the perpendicular altitude described in the Lemma.
QED
The first application we make of this Lemma is to note that angle BAO
is equal to angle OAC, since we deduce from the Lemma that the
circumcenter O of isoceles triangle ABC sits on the the angle bisector
through A:
<BAO = <OAC
[Note: In this part of the answer, I will use the less-than sign < to
denote angles. Since it is not needed in this part of the problem to
denote an inequality relation, no confusion should result.]
The second application we make of the Lemma is to the circumcenter P
lying on the perpendicular bisector of AB, which also passes through
O, as O is the apex of isoceles triangle AOB. Thus OP is
perpendicular to AB, and (extended if necessary) OP would meet AB at
the midpoint D of AB.
From this we draw the conclusion that angle AOP (which is also angle
AOD) and angle BAO (which is also angle DAO) are complementary (since
triangle ADO has a right angle at vertex D):
<AOP + <BAO = 90
Finally let us take note that because P is equidistant from A and O,
the triangle PAO is isoceles and has equal base angles:
<AOP = <PAO
But <PAO is the sum of two acute angles:
<PAO = <PAB + <BAO
Combining the above results:
<PAC = (<PAB + <BAO) + <OAC
<PAC = <PAO + <BAO = <AOP + <BAO = 90
This accomplishes our aim, to show that angle PAC is a right angle,
and therefore that AC is tangent to the circumscribing circle of
triangle AOB.
3. As given, this part of the problem says to "[d]ecide whether or
not" (an arithmetic value). Clearly a statement rather than an
expression of value is to be expected here. My reconstruction of this
question part is:
"Decide whether or not the cube root of (26 - 15 sqrt(3)) plus the
cube root of (26 + 15 sqrt(3)) IS AN INTEGER." (Caps are for
highlighting my added wording; note also minor alterations elsewhere
including placement of parentheses.)
If this reconstruction is incorrect, please supply the correct one in
a Request for Clarification.
The problem can be addressed with both high powered and elementary
tools. To minimize assumptions about the audience's math background,
we shall only use the tools of arithmetic:
The first observations are simply that:
(2 + sqrt(3))^3 = 26 + 15 sqrt(3)
(2 - sqrt(3))^3 = 26 - 15 sqrt(3)
by brute binomial expansions of these expressions (and collections of
like terms).
Then:
cube root( 26 - 15 sqrt(3) ) + cube root( 26 + 15 sqrt(3) )
= ( 2 - sqrt(3) ) + ( 2 + sqrt(3) )
= 4
an integer.
4. We are asked to prove that d(n) < 2 sqrt(n) for all positive
integers n, where d(n) is the number of distinct positive divisors of
n, not excluding the trivial divisors 1 and n itself. We are also
asked to find all positive integers n such that d(n) >= 2 sqrt(n) - 1.
It simplifies the discussion a bit to separate out the case where n is
a perfect square from the remaining cases. One reason for this is
that d(n) is an odd number only when n is a perfect square.
To see why, consider a "pairing" of one positive divisor r of n with
another given by n/r. Clearly this mapping takes all divisors of n
which are less than sqrt(n) to ones which are greater than sqrt(n),
and vice versa. Only if n is a perfect square, say n = k^2, can the
mapping have a "fixed point", i.e. k = n/k.
So d(n), in general, is twice the number of positive integer divisors
of n below sqrt(n), plus an additional one _if_ n is a perfect square
(so that sqrt(n) itself counts as one distinct divisor).
n is a perfect square
=====================
Say n = k^2. There are only (k-1) positive integers below k =
sqrt(n), so the counting argument above d(n) is at most:
2(k-1) + 1 = 2k - 1 = 2 sqrt(n) - 1
Hence d(n) < 2 sqrt(n).
While we are on the subject, let us deal with the question of which
perfect squares can attain the prescribed upper bound:
d(n) = 2 sqrt(n) - 1
We note that in addition to k, n = k^2 is to be divisible by all
positive integers below k = sqrt(n). This is okay if n = 1 (k=1),
because there aren't any, and also okay for n = 4 (k=2), because the
only such integer is 1.
But beyond that there are no more such perfect squares. In fact if k
> 2, then k-1 is not a divisor of n = k^2 (but is a positive integer
below k). If k-1 were a divisor of k^2, then since k-1 divides k^2 -
1, it would imply k-1 divides 1. But this is not possible if k > 2
(i.e. if k-1 is greater than 1).
n is not a perfect square
=========================
With the perfect squares behind us, we can focus on the slightly more
difficult cases with greater ease. We can now say more simply that
d(n) is twice the number of positive integer divisors of n which are
less than sqrt(n).
It is therefore easy to see that the number of positive integers less
than sqrt(n), also known as floor(sqrt(n)), is strictly less than
sqrt(n) because the latter is not an integer. Hence:
d(n) <= 2 floor(sqrt(n)) < 2 sqrt(n)
That proof of the desired upper bound leaves only the determination of
which (non-perfect square) integers satisfy:
d(n) >= 2 sqrt(n) - 1
Before we get carried away with the somewhat intricate details of
_proving_ the claim (which is not explicitly required by the problem
statement, but we will do anyway), let's identify all the "small
cases" where this is true of non-squares:
d(2) = 2 > 2 sqrt(2) - 1 = 1.828...
d(6) = 4 > 2 sqrt(6) - 1 = 3.899...
d(12) = 6 > 2 sqrt(12) - 1 = 5.928...
I have ruled out by computation any further cases below (say) n = 420.
The case of n = 24 may be instructive. Since the floor of the square
root of 24 is 4, and all four positive integers less than or equal to
4 divide 24, d(24) = 8. But:
2 sqrt(24) - 1 = 8.798...
so 24 doesn't quite have enough divisors. We remark that for n > 25,
it may be required that n be divisible by all the positive integers 1
through 5, so that n must be a multiple of 60. The reasons for this
become apparent below; I mention it only to suggest how rapidly the
computation of cases between 24 and 420 might be accomplished.
The first step in proving that there are no other such cases is to
reexamine our counting argument. We note that if even one of the
integers below sqrt(n) does not divide n, then n cannot be among the
integers satisfying this last condition. For then our upper bound
would improve to:
d(n) <= 2 ( floor(sqrt(n)) - 1 ) < 2 sqrt(n) - 2
and that is sufficiently sharp to contradict d(n) >= 2 sqrt(n) - 1.
So a necessary characteristic of those n which do satisfy d(n) >= 2
sqrt(n) - 1 is that n must be divisible by all the positive integers
less than sqrt(n). Intuitively what one feels is that as a target k =
floor of sqrt(n) grows, so too must the least common multiple of
integers 1 through k, and that while n grows like a quadratic function
of k, it must also have as a divisor that least common multiple, which
would appear to grow at a more than exponential rate. Therefore the
range of values n (or k) for which the condition can be satisfied is
expected to be brief.
It turns out to be messy to deal directly with the least common
multiple of all integers 1 through k, but it suggests that we might
find a simpler expression that relates to the least common multiple of
a few of these. It should be sufficient to use three terms, so that
the resulting cubic function grows rapidly enough (with k) to outstrip
a quadratic function.
To make this argument more precise, consider k = floor(sqrt(n)). Then
n < (k+1)^2.
On the other hand, for k > 2 we know that k, k-1, and k-2 would all
have to be divisors of n in order for n to satisfy the desired "lower
bound" condition d(n) >= 2 sqrt(n) - 1.
Furthermore the least common multiple of k, k-1, and k-2 would have to
be a divisor of n as well (since, by a well known argument, we know n
is such a common multiple, n will be divisible by the least common
multiple).
But how small can LCM(k, k-1, k-2) be? Actually, not a whole lot
smaller than their product. In fact the only prime factor that can
appear in more than one of these terms is 2, and then only if k and
k-2 are both even. So we can prove:
LCM(k, k-1, k-2) >= k(k-1)(k-2)/2
[Note 1: LCM(k, k-1, k-2) = LCM( LCM(k,k-1), k-2)) = LCM(k(k-1), k-2)
= k(k-1)(k-2)/GCD(k(k-1),k-2).]
[Note 2: Further, if k were divisible by more than a first power of 2,
k-2 would not be, and conversely. So at most a single factor of 2 is
at issue here, GCD(k(k-1),k-2) <= 2.]
Now we have seen that if k = floor(sqrt(n)) > 2, then in order for
d(n) >= 2 sqrt(n) - 1, it necessary that:
n < (k+1)^2
and also that:
k(k-1)(k-2)/2 <= n
since this left hand side is to be a positive divisor of the positive
integer n.
But k(k-1)(k-2)/2 < (k+1)^2 can only be satisfied when:
k^3 - 3k^2 + 2k < 2k^2 + 4k + 2
k^3 < 5k^2 + 2k + 2
1 < 5/k + 2/(k^2) + 2/(k^3)
In particular this cannot hold when k >= 6, for:
5/k <= (5/6),
2/(k^2) <= (1/18), and
2/(k^3) <= (1/108)
and (5/6) + (1/18) + (1/108) = 97/108 < 1.
This tells us that the checking we did up through n < 36 was
"exhaustive" enough. There are no further instances larger or small,
square or non-square, to be found.
5. The last part of the problem asks about a winning strategy for a
game in which two players (Alice and Bob) alternate turns at removing
one or more stones from a pile, the rule being that the number of
stones removed must be a divisor of the number of stones in the pile
but not the entire pile. The winner "is the last person who takes a
stone". I interpret this careful avoidance of the phrase "the person
who takes the last stone" to indicate that no one can take the last
stone. Instead the winner will take one of the last two stones,
leaving a position in which no move is possible (a losing position).
A game which starts with Alice's turn and 100 stones is considered.
We are asked to prove that Alice has a forced win, i.e. no matter how
Bob responds, if Alice follows our preordained strategy, she is bound
to win.
Although various strategies are possible, a simple one for Alice to
follow in this case is to remove one stone in each turn.
As a result of this, Bob will always be faced with a pile containing
an odd number of stones, which decreases in each round. When the pile
reaches one stone, Bob has lost.
What happens is this. Alice starts with (and will always face
thereafter) a pile containing an even number of stones.
By removing one each time, she presents Bob with an odd number of
stones to choose from.
But Bob's choices are limited to the divisors of that number of stones
(less than their entire number). Bob is therefore forced by
divisibility to remove an odd number of stones in each of his turns
(because an odd number has no even divisors).
Once Bob takes an odd number of stones from the odd numbered pile, he
leaves Alice with an even number of stones in the pile. Bob cannot
escape his fate so long as Alice removes only one stone (or more
generally, if she doesn't enjoy dragging the game out, removing a
number of stones equal to any odd divisor of the number in the pile).
regards, mathtalk-ga |
