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

From: Robin Chapman (rjc_at_ivorynospamtower.freeserve.co.uk)
Date: 12/06/04 

Date: Mon, 06 Dec 2004 08:49:38 +0000

Dave Rusin wrote:

> 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/
>

>
> 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.)

An alternative method: enlarging the second trinagle by a constant
factor allows us to assume that a = a'. Draw both triangles on the
same base: ABC and A'BC say with A and A' on the same side of BC.
Draw the line L through A parallel to BC and the line L' perpendicalar
to L at A. If the second triangle had larger area, A' would lie
beyond L (opposite side of L to BC). Divide the "beyond" of L into
two quadrants by L'. If A' is beyond L then b' > b if L is
in one quadrant and c' > c in the other (here is where we use acuteness).

> 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.)

I got
n! x_1 x_2 ... x_n = sum_T (-1)^{n-|T|}(S(T))^n
eschewing coefficient -1. :-)

>
> 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 .

Alternative:
One of the terms in the binomial expansion of (m+n)^{m+n}
is (m+n choose m) m^m n^n so that (m+n)^{m+n} > (m+n choose m) m^m n^n 

-- 
Robin Chapman, www.maths.ex.ac.uk/~rjc/rjc.html
"Lacan, Jacques, 79, 91-92; mistakes his penis for a square root, 88-9"
Francis Wheen, _How Mumbo-Jumbo Conquered the World_

Relevant Pages

  • Re: trig identity
    ... This would mean our reference angle ... -sqrtand that the opposite side ... 30:60:90 triangle as our reference ...
    (sci.math)
  • Re: Calculate Angle and Length in Triangle
    ... triangle, where Angle1 is opposite Side1 etc ... If angles A & B are not internal angles opposite sides a & b adapt as ... PS the above formula validates Dave's "would be" triangles. ... The angle provided is not the angle of a corner. ...
    (microsoft.public.excel.programming)
  • Re: RSA Challenges
    ... including the triangle, if Said i.e. remarks the pen? ... wipe the single pretty notices before Basksh does? ... Basksh's reactor opposite instincts, it will up clean the toe. ...
    (sci.crypt)
  • trig identity
    ... This would mean our reference angle ... -sqrtand that the opposite side ... 30:60:90 triangle as our reference ... or pi/3 radians. ...
    (sci.math)
  • just revising via a ball depending on the swamp is too well-known for Said to fetch it
    ... If you will reward Eddie's triangle onto folks, it will broadly point the detective. ... For Angela the county's just, opposite me it's controlled, whereas via you it's calming dominant. ...
    (sci.crypt)