Re: Putnam Exam 2004 -- [*SPOILERS*]

From: Rohit Tripathi (trip7294_at_dowling.edu)
Date: 12/05/04 

Date: 5 Dec 2004 07:51:51 -0800

For B-2 I did the following:

let a=m/(m+n)
    b=(n/(m+n)

and therefore (a+b) = 1, and (a+b)^(m+n) = 1 too

The binomial expansion of (a+b)^(m+n) = C_0 a^(m+n) + .... + C_n a^(n)
b^m + ... C_(m+n) b^(m+n)

C_n a^n b^m is less than 1 and greater than 0, as all terms in the
expansion are non negative.

check it out !
what do you think?

-rohit

rusin@vesuvius.math.niu.edu (Dave Rusin) wrote in message news:<cou6em$edc$1@news.math.niu.edu>...
> The Sixty-Fifth Annual Putnam Exam was held today. I have already
> posted a copy of the questions. Here are as many answers as I have
> at this moment; I have nothing to say about A-5 and B-6.
>
> If I were the grader I wouldn't give myself full credit for some of
> these answers but I think rather than nail down all the details I
> will wait for someone else to provide the slickest answers, making
> the drudgery unnecessary... (See Problems A-2, A-4, and problems
> with detailed computations such as B-3, B-4, B-5.)
>
> Overall I thought this was an easier exam than is typical, which
> made the event much more fun for the "average" students taking the test.
>
> I will add these answers and any other interesting responses to the
> files I make available about Putnam questions; see
> http://www.math.niu.edu/~rusin/problems-math/
>
> A-1.
>
> Suppose that S.O.'s success count S(N) stayed strictly below 0.80 N
> for all N < K, but that S(K) >= 0.80 K. This requires S(K-1) = S(K) - 1.
> Then from S(K-1)/(K-1) < 4/5 and S(K)/K >= 4/5 we conclude that
> 0 <= 5 S(K) - 4 K < 1 ; since 5 S(K) - 4 K is an integer, it must
> then equal zero, so S(K) = 4/5.
>
> Comment: Obviously the same proof works for any percentage of the form
> 1 - 1/m with integer m, but for more general percentages the result
> is false. This problem will make a very pretty example the next time
> I teach the Intermediate Value Theorem :-)
>
> A-2.
>
> From Heron's formula, the area and side lengths of a triangle satisfy
> 16 A^2 = 2 (a^2b^2+a^2c^2+b^2c^2) - (a^4+b^4+c^4)
> Viewed as a quadratic polynomial in X = a^2, this function is clearly
> increasing as long as X < (b^2+c^2), which means that the area of a
> triangle increases with the length of any side as long as the angle
> opposite that side is acute (a^2 < b^2 + c^2 ).
>
> (A student pointed out to me at lunch that this is also obvious from
> A = (1/2) b h, where the height h of the triangle varies with a but
> c is fixed; the maximum height occurs with sides b and c perpendicular.)
>
> It then suffices to observe that we can transform triangle T_1 to T_2
> by a sequence of operations which lengthen just one edge at a time. This
> is not entirely obvious since, for example, we are not given that the
> smaller triangle is acute. But it's easy to see in a sketch which I will
> not attempt in ASCII, showing the portion of the positive octant in
> a,b,c -space which corresponds to triangles ( a < b+c, etc. ); the acute
> triangles are the ones external to three cones around the coordinate
> axes ( a^2 < b^2 + c^2, etc.) If one always lengthens the shortest edge
> (from among those that need to be lengthened to change T_1 into T_2),
> then that will always be opposite an acute angle. (An obtuse angle will
> always be opposite the _largest_ side, and that cannot the the only side
> remaining to be lengthened since T_2 is acute.)
>
> Note: I guess I had never before stopped to think about under exactly
> what conditions it is true that lengthening the sides of a triangle
> increases the area. Now I know!
>
> A-3.
>
> We prove by induction that u_n = (n-1)!! = (n-1)(n-3)(n-5)..., which
> is easily checked to be valid for small n. Of course this will mean
> the u_n are integral.
>
> If the claim is true for u_n and u_{n+2} then u_{n+2} = (n+1) u_n, so
> the first column of the matrix in the determinant is a multiple of u_n,
> and we have simply the recurrence relation
> u_{n+3} = (n+1) u_{n+1} + n!/u_n
> = (n+1) n!! + n!!
> = (n+2) n!! = (n+2)!!,
> providing the inductive step.
>
> A-4.
>
> This is a heavily-used formula when n = 2 : xy = (1/4)( (x+y)^2 - (x-y)^2 ).
> I guess I never really thought about generalizing it before!
>
> It suffices to arrange it so that the right side is a nonzero multiple of
> every x_i ; for then it is a degree-n polynomial and also a multiple of
> x_1 x_2 ... x_n, so the quotient of the two sides is a constant
> (necessarily rational, as can be seen from substituting x_1 = ... = 1);
> we can then divide through to make the constant be 1.
>
> If we arrange it so that the right side is symmetric in the x_i, then
> it suffices to make sure it vanishes when x_1 = 0.
>
> For odd n this is easy: for any subset T of N = {1, 2, ..., n}, let
> S(T) = the sum of the x_i with i in T. Then consider
>
> X = \sum (-1)^|T| ( S(T) - S(N-T) )^n ,
>
> the sum taken over all subsets T of N. When we substitute x1=0 we
> obtain an alternating sum of terms of the form ( S(U) - S(M-U) )^n
> where M = N - {1}. Each such term arises exactly twice, once from
> S(U union {1}) - S(M-U) and once from S(U) - S(N-U); since the cardinalities
> of U and U union {1} are of opposite parity, these two summands
> will cancel. Thus, X vanishes when x1=0.
>
> On the other hand, X (apparently) doesn't vanish identically; for example,
> when all x_i equal 1, we have
> c = \sum (-1)^|T| ( |T| - |N-T| )^n = \sum (-1)^k (2k-n)^n C( n,k ),
> which seems to equal (-2)^n n! (I computed the first few examples but
> didn't prove this formula in general.)
>
> So whatever the value of c really is (it's obviously integral) we
> can divide X by c to get a sum which is a multiple of x1, and thus
> of each x_i, and thus of the product x1 x2 ... x_n, but the
> quotient must be both constant and taking the value 1.
>
> I didn't take advantage of the opportunity to use 0 as a coefficient!
>
> A-5.
>
> No clue. I worked out the case n=1 completely; the expected number of
> components is (m+1)/2 . I suppose there might be some kind of induction
> argument, but since they ask us to prove the number of components is
> AT LEAST mn/8, that suggests that what we're supposed to do is to find
> a lot of configurations with lots of components, so that we can bound
> the expected number without doing all the grubby computations.
>
> A-6.
>
> Heh, heh, check this one out:
> Let F(x,y,z,w) = f(x,y) + f(z,w) - f(x,w) - f(z,y); then integrate
> F^2 over the box [0,1]^4 . Done!
>
> (This is the distillation of about 5 pages of computations, followed by
> a great big step back to look at What The Computations Really Mean.
> I have learned that to understand these integral inequalities it pays
> to think in terms of step functions and simple functions; writing all that
> out gave me a solution but then I realized this other way to say it.
> Note that it is critical that the domain of integration be the UNIT square.)
>
> B-1.
>
> This is really standard. Write r = p/q in lowest terms; then we have
> c_n p^n + c_{n-1} p^{n-1} q + ... + c_0 q^n = 0
> and so for each j between 0 and n we see q^j divides
> c_n p^n + c_{n-1} p^{n-1} q + ... + c_{n-j+1} p^{n-j+1} q^{j-1}
> = p^{n-j}( c_n p^{j} + c_{n-1} p^{j-1} q + ... + c_{n-j+1} p^1 q^{j-1} )
> Since p and q are coprime, q^j divides the other factor. Dividing
> through, we may express the integer quotient as a polynomial in r.
>
> B-2.
>
> Another slick one: Let S = {1, 2, ..., m}, T = {m+1, ..., m+n}.
> How many functions are there from S union T to S union T ? (m+n)^(m+n).
> Among those are the functions that send precisely m elements of the
> domain to S, and the other n elements to T. There are C(m+n,m) ways
> to choose which elements go to S, and once those are chosen there are
> m^m n^n such functions. So (m+n)^(m+n) >= (m+n)!/m!n! m^m n^n .
>
> B-3.
>
> If a > 2 we may use a constant function: a rectangle measuring a by
> 2a/(a-2) has perimeter and area equal.
>
> If a<2 there is no such function. The area is a m where m is the
> mean value of f over [0,a], which is certainly no larger than the
> maximum value M of f on the interval. On the other hand, the perimeter
> is at least the length of the line segments joining (0,0), (a,0), and
> (x,M) for some x in the interval, but each of the non-horizontal segments
> has length more than M, so the perimeter is more than 2M, which is
> more than aM, which is more than a m, the area. The case a=2 is
> similar; just use the fact that the perimeter is then at least
> 2 + 2 sqrt(1 + M^2).
>
> B-4.
>
> This is pretty standard too. One could matrices, but let's instead
> view the plane as being the set of complex numbers; a rotation by
> an angle theta is accomplished by multiplication by u = exp(i theta).
> (The function f(z) = P + u (z - P) is the rotation around P.)
> So we are composing the functions
> R_k(z) = P_k + u ( z - P_k) = u z + (1-u) k
> By induction on m we find
> (R_m o ... o R_2 o R_1) (z) = u^m (z) + S_m where S_m =
> (1-u) m + u S_{m-1}, i.e.
> S_m = (1-u) ( m + u (m-1) + u^2 (m-2) + ... + u^m (0) ).
> = m - u - u^2 - ... - u^m = m - (u - u^{m+1})/(1 - u)
>
> In the problem we were given that theta = 2 pi / n , so u^n = 1,
> meaning
> (R_n o ... o R_2 o R_1) (z) = u^n (z) + S_n = z + n,
> a simple translation R(x,y) = (x+n, y).
>
> This motion is easily demonstrated for low n.
>
> B-5.
>
> It makes more sense to deal with the logs. We need to look at
>
> lim_{x->1-} lim_{N->\infty} sum_{n=0}^N x^n (log(1+x^{n+1}) - log(1+x^n))
>
> = lim_{x->1-} lim_{N->\infty}
> ( sum_{n=1}^N (x^{n-1} - x^n) log(1+x^n) ) -log(2) + x^N log(1+x^{N+1})
>
> For any x < 1, the last term tends to 0 as N->\infty, so we have only
> - log(2) + lim_{x->1-} (1/x - 1) sum_{n=1}^\infty x^n log(1+x^n)
>
> Now, we may estimate the infinite sum using bounds on the logarithm from
> its Taylor series; for example, we have log(1+x^n) > x^n - x^{2n}/2 but
> log(1+x^n) < x^n - x^{2n}/2 + x^{2n}/3 . From these we obtain inequalities
> on the sum: it lies between x^2/(1-x^2) - (1/2)(x^3/(1-x^3)) and
> x^2/(1-x^2) - (1/2)(x^3/(1-x^3)) + (1/3)(x^4/(1-x^4)), and we may obtain
> more bounds of this type. Multiplying in the additional factor (1/x - 1)
> (which is positive) gives bounds such as
> x^1/(1+x) - (1/2)(x^2/(1+x+x^2)) and
> x^1/(1+x) - (1/2)(x^2/(1+x+x^2)) + (1/3)(x^3/(1+x+x^2+x^3))
> Applying these bounds to each x < 1 we find the limit to lie between
> 1/2 - (1/2)(1/3) and 1/2 - (1/2)(1/3) + (1/3)(1/4)
> and more generally it is alternately larger or smaller than a partial sum of
> the the absolutely convergent series
> (1/1)(1/2) - (1/2)(1/3) + (1/3)(1/4) - ...
> Carrying out this argument more generally to finite expansions of the
> Taylor series shows that the limit must equal this infinite sum.
>
> If we add 2( (1/2)(1/3) + (1/4)(1/5) + (1/6)(1/7) + ...) we obtain
> the famous telescoping series, which sums to 1. But in like manner we may
> recognize this addend as 2( (1/2) - (1/3) + (1/4) - (1/5) + ... ), which is
> 2 (1-log(2)). So the series in the last paragraph converges to 2 log(2) - 1.
>
> So I conclude that the logarithm of the original limit is log(2) - 1,
> and so the limit itself must be 2/e .
>
> B-6.
>
> No clue. It's a nice problem though -- sort of a teaser for the Twin Prime
> conjecture or something. (Let A = set of all primes.)
>
> For contrast, consider what happens when A = set of all squares (B = set
> of (almost) all composites), or A = an arithmetic progression (B is an
> ideal of Z), or A = powers of 2 (this B is indeed sparse).
> I look forward to a solution of this one.

Relevant Pages

  • Putnam Exam 2004 -- [*SPOILERS*]
    ... triangle increases with the length of any side as long as the angle ... the first column of the matrix in the determinant is a multiple of u_n, ... S= the sum of the x_i with i in T. Then consider ... 2a/has perimeter and area equal. ...
    (sci.math)
  • Re: Putnam Exam 2004 -- [*SPOILERS*] A4
    ... > I guess I never really thought about generalizing it before! ... > we can then divide through to make the constant be 1. ... > can divide X by c to get a sum which is a multiple of x1, ...
    (sci.math)
  • Re: Dik T. Winter says: Definition: sum{i in N} i = 0
    ... A figure is called triangle* iff ... sum summs infinitely many summands. ... Induction to the infinite is valid and sound, as long as measure is preserved. ... balls naturally numbered from 1, we insert balls 10n-9 through 10n, and remove ball n at each iteration n. ...
    (sci.math)
  • Re: Dik T. Winter says: Definition: sum{i in N} i = 0
    ... triangle is a figure without any corner, ... sum summs infinitely many summands. ... There is an obvious difference of your meaning of "proof" and the common ... "It is not very difficult to evaluate infinite sums. ...
    (sci.math)
  • Re: help with T-tests
    ... sum of squared differences: 392 ... you can use a normal distribution approximation. ... ANOVA way before you think of multiple t-tests. ...
    (sci.stat.math)