
Re: 2012 Putnam Exam, Problem A6
Posted:
Dec 23, 2012 3:12 PM


"Mike Terry" <news.dead.person.stones@darjeeling.plus.com> wrote in message news:_ednfU2lOrMxUrNnZ2dnUVZ8vKdnZ2d@brightview.co.uk... > "quasi" <quasi@null.set> wrote in message > news:k6tdd897t057g58mr3mi3cbon31e38our0@4ax.com... > > Corrected version: > > > > My solution to Problem A6 on the 2012 Putnam Exam ... > > > > Problem: > > > > If f: R^2 > R is a continuous function such that for all > > rectangular regions D in R^2 of area 1, int_D f = 0, > > must f = 0? > > > > Answer: Yes. > > > > Proof: > > > > Suppose f satisfies the hypothesis but f != 0. > > > > Then f(P) != 0 for some point P. > > > > Replacing f by f if necessary, we can assume f(P) > 0. > > > > Since f is continuous, f is positive in a neighborhood of P, > > hence, since any rectangular region D of area 1 containing P > > in its interior has int_D f = 0, it follows that the interior > > of D must also contain a point Q such that f(Q) < 0. > > > > Without loss of generality, we can translate the coordinate > > system so that the origin is at P and rotate the axes so that > > Q lies on the positive xaxis. > > > > Let d be the distance from P to Q. > > > > Then P = (0,0) and Q = (d,0). > > > > Some terminology ... > > > > By "adjacent rectangles" we mean two nondegenerate closed > > rectangular regions whose intersection is a common edge. > > > > It's immediate that if D1 and D2 are adjacent rectangles > > then D1 U D2 is a rectangular region and > > > > int_(D1 U D2) f = (int_D1 f) + (int_D2 f) > > > > By "complementary rectangles" we mean two adjacent rectangles > > whose union is a rectangular region of area 1. > > > > By hypothesis, if D1 and D2 are complementary rectangles then > > > > int_D2 f = (int_D1 f) > > > > Since f is positive in a neighborhood of P and negative in a > > neighborhood of Q, there exists w > 0 such that f is positive > > on the w by w square with vertices > > > > (w/2,w/2) (w/2,w/2) > > (w/2,w/2) (w/2,w/2) > > > > and f is negative on the w by w square with vertices > > > > (d  w/2,w/2) (d + w/2,w/2) > > (d  w/2,w/2) (d + w/2,w/2) > > > > Since the function > > > > M(x) = 1  d*x + d/x > > > > is such that > > > > M(x) > oo as x > 0+, > > > > it follows that we can choose u with 0 < u <= w such that > > M(u) is a positive integer, m say, with m > 1. > > > > Let S be the u by u square with vertices > > > > (u/2,u/2) (u/2,u/2) > > (u/2,u/2) (u/2,u/2) > > > > and let T be the u by u square with vertices > > > > (d  u/2,u/2) (d + u/2,u/2) > > (d  u/2,u/2) (d + u/2,u/2) > > > > Let a = int_S f and let b = int_T f. > > > > Then a > 0 and b < 0. > > > > For each positive integer n, let G_n be the rectangular region > > with vertices > > > > upper left: (u/2+(n1)*(u/(1u^2)),u/2+1/u) > > upper right: (u/2+(n1)*(u/(1u^2)),u/2+1/u) > > lower left: (u/2+(n1)*(u/(1u^2)),u/2) > > lower right: (u/2+(n1)*(u/(1u^2)),u/2) > > > > and let H_n be the rectangular region with vertices > > > > upper left: (u/2+(n1)*(u/(1u^2)),u/2+1/u) > > upper right: (u/2+(u^3/(1u^2))+(n1)*(u/(1u^2)),u/2+1/u) > > lower left: (u/2+(n1)*(u/(1u^2)),u/2) > > lower right: (u/2+(u^3/(1u^2))+(n1)*(u/(1u^2)),u/2) > > > > It's easily verified that the following pairs of rectangular > > regions are complementary: > > > > S, G_1 > > > > G_n, H_n, for all positive integers n > > > > H_n, G_(n+1), for all positive integers n > > > > It follows that > > > > int_(G_n) f = a, for all positive integers n > > > > int_(H_n) f = a, for all positive integers n > > > > In particular, int_(G_m) f = a. > > > > By choice of m, the rectangular regions T and G_m are > > complementary, so int_(G_m) f = a implies int_T f = a. > > > > On the other hand, we have int_T f = b, so a = b, > > contradiction, since a > 0 and b < 0. > > > > Therefore f = 0, as claimed. > > > > quasi > > Hi quasi, > > I like this proof very much, but I feel you have not presented it as well as > you could. The basic idea is very simple, but your presentation is full of > mysterious coordinates, and very little motivating text that would explain > how the proof actually works. This would surely put off a lot of people > from following your proof, so I'll have a go at explaining the simple idea > behind it. > > The basic idea is that *if* we have a small square A of length u where > Integral f >0 on A, then we can construct another square E, offset from A by > a small amount, where also Integral f > 0 on E. (Then by repetition, a > whole sequence of further squares where Integral f > 0 on each square). > > To construct E given A, first construct a long thin rectangle B above A so > that area (A+B) = 1. > > Then we construct a thin rectangle C to the right of B, so that area (B+C) = > 1, and then rectangle D to the right of C so that area (C+D) = 1. > > Finally we construct a rectangle E beneath D so that area (D+E) = 1. > > Here's a picture: > > BBBCDDD > BBBCDDD > BBBCDDD > BBBCDDD > BBBCDDD > BBBCDDD > BBBCDDD > BBBCDDD > AAA EEE > AAA EEE > AAA EEE > > A & B are examples of complementary rectangles, in your terminology. > Similarly B&C, C&D, and D&E are complementary. > > Clearly B and D are similar, and so A and E are similar, i.e. E is another > square > like A, but shifted to the right a bit. Looking at the integrals of f on > each region, we have: > > Int_A f = Int_B f = Int_C f = Int_D f = Int_E f > > [using Int_X f to mean the integral of f over rectangle X] > > So E, like A has a positive integral for f, as claimed. > > The above process can be repeated to make further new squares with positive > integral for f, stepping to the right by the same amount with each > repetition of the process.
It occurs to me that since the stepping procedure can be applied both horizontally and vertically, an adaptation of quasi's proof solves the problem with slightly weaker hypotheses:
If f: R^2 > R is a continuous function such that for all *ALLIGNED* rectangular regions D in R^2 of area 1, int_D f = 0, must f = 0?
i.e. the result remains true if we are just given int_D f = 0 for rectangles D that are products of intervals [a,b] and [c,d] in the underlying coordinates of R^2. (Quasi's proof uses a rotation at one point to bring two positive and negative points of f onto the xaxis, but we can work around this without using any rotation by "stepping" both horizontally and vertically rather than just horizontally in the proof. With this change, all the rectangles used in the proof are "alligned".)
Also, the same "stepping" argument works fine for higher dimensional R^n, but luckily the stepping process breaks down in R^1. (Luckily, as the analogous result is clearly false for R^1! :))
Mike.
> > Once this basic "stepping" idea is understood, the proof is straight > forward: > > 1. If f is not identically zero, there is a point where it is >0 > 2. ..which in turn implies there is another point where it is <0 > (as you explain perfectly well, so I won't repeat it) > 3. Continuity of f means we can arrange things and choose coords > etc. so that there is a little square at the origin where f>0 > and another square somewhere off to the right where f<0. > We take the offset distance to be d. > 4. But now we can choose an even smaller square A at the origin > where f>0, and if we follow the stepping procedure above we > can show there are a sequence of squares offset from A where > f>0 on each square, and we can choose the size of A so that > one of these squares lands smack on our square where supposedly > f<0, contradiction. > > The unclear bit is maybe in (4), but it's easy when we see what we're trying > to do! :) > > If our square A has length u, what is the "offset" to our next square E (in > the diagram above)? > > A has length u > B has width u, length (1/u)u = (1  u^2)/u > so B+C has width u/(1  u^2), which is our offset value > > If our square where supposedly f<0 is offset from A by distance d, we simply > have to choose u so that > > m * u/(1  u^2) = d > > for a suitable positive integer m. m will be the number of times we need to > repeat the stepping process to reach the square which reveals the > contradiction. We can choose such an m because the offset is a continuous > function of u, converging to zero as u tends to zero... > > (Hmmm, this doesn't look quite the same as your calculation for suitable m > ????) > > > Anyway, I hope this saves people the trouble of trying to work out the logic > behind your proof from the coordinate expressions you give, as the logic is > simple, but the expressions in your proof do not really bring this out. > > I hasten to add that all the above is there in your proof and I'm just > explaining it  I don't know whether I'd have worked this out without seeing > your proof, so all credit goes to you! :) > > Regards, > Mike. >

