Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Problem A1 from the 2009 Putnam Exam

  1. Jun 17, 2013 #1
    Here is the problem:

    Let f be a real-valued function on the plane such that
    for every square ABCD in the plane, f(A) + f(B) +
    f(C) +f(D) = 0. Does it follow that f(P) = 0 for all
    points P in the plane?



    Below is my solution:

    Create a 3x3 set of boxes (where each box has equal lengths as all of the other boxes) like so:

    . . . .
    . . . .
    . . . .
    . . . .

    The periods represent vertices. Now, denote the value of the function at each vertice by a(1),...,a(16).

    Now, since the sum of any four vertices making a square is zero, we get 18 unique equations (each containing a linear relationship between a unique quadruple of vertices):

    9 (each representing a unit box)
    +
    4 (each representing a box of side length 2 units)
    +
    1 (this equation relates the vertices of the entire 3x3 square)
    +
    4 (each representing a box of side length sqrt(2) units (the diagonal squares)


    Writing these into a matrix, we get an 18x16 matrix mapping a vector whose coordinates are the values of the function at each vertex) to the zero vector. Since we have 18 homogeneous equations and 16 variables, all of the variables must be zero. From this we can clearly conclude that the value of the function is zero for everywhere on the plane.

    Is this solution correct? I can't see any errors, I just thought it was an interesting answer (it was different from the official answer, which I've posted below) and wasn't sure if I was missing anything.

    OFFICIAL ANSWER:

    Yes, it does follow. Let P be any point in the plane. Let
    ABCD be any square with center P. Let E; F; G; H
    be the midpoints of the segments AB; BC; CD; DA,
    respectively. The function f must satisfy the equations
    0 = f(A) + f(B) + f(C) + f(D)
    0 = f(E) + f(F) + f(G) + f(H)
    0 = f(A) + f(E) + f(P) + f(H)
    0 = f(B) + f(F) + f(P) + f(E)
    0 = f(C) + f(G) + f(P) + f(F)
    0 = f(D) + f(H) + f(P) + f(G):
    If we add the last four equations, then subtract the first
    equation and twice the second equation, we obtain 0 =
    4f(P), whence f(P) = 0.
     
  2. jcsd
  3. Jun 17, 2013 #2

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I don't think you have satisfactorily proven that your 18x16 matrix is of full rank
     
  4. Jun 17, 2013 #3
    Well each entry will be 1 or 0, and each combination of 1s and 0s in each row will be different, because each square is unique. There will be 4 1's in each row. Wouldn't that imply that you cuold put the matrix into eschelon form, solving for each a(i)?
     
  5. Jun 17, 2013 #4
    I apologize if I'm wrong, I haven't done much work with matrix algebra as I have only taken theory-based linear algebra (Axler).
     
  6. Jun 17, 2013 #5
    Here we go: "A homogeneous system Ax = 0 has only the zero solution if Ax = 0 has at least as many nontrivial equations as variables."
     
  7. Jun 17, 2013 #6
    That's from page 67 of Multivariable mathematics (4th edition) by Williamson and Trotter.
     
  8. Jun 17, 2013 #7

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The key is nontrivial. If your equations are x+y+z=0, x+y+z=0, x+y+z=0, then you haven't really gotten very far!

    You can always put a matrix into echelon form, but that doesn't mean it's a full rank echelon form matrix (for example the bottom four rows might all be zeros and you have four free degrees of freedom from which to pick your solution)

    This is pretty close to what you want. However it's not quite enough- suppose I have seven variables, x1,...,x7 and every equation of the form
    [tex] x_{i_1}+x_{i_2} + x_{i_3} + x_{i_4} = 0 [/tex]
    where [tex] i_1,i_2,i_3,i_4 \leq 6 [/tex]

    are distinct in each equation. I have 6 choose 4 = 15 equations, and 7 variables, and none of my equations are actual duplicates of other equations. However, vectors (0,0,0,0,0,0,x) for x any real number is a solution to these equations. The problem is that there are linear dependencies amongst my equations
     
  9. Jun 17, 2013 #8
    Ah, I see what you're saying. Thank you for the response, I guess my solution wasn't as elegant as I had thought haha. Even if I was able to show that the equations were nontrivial it would end up being a lot more complex than the official solution.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Problem A1 from the 2009 Putnam Exam
  1. Problem from MIT OCW (Replies: 4)

  2. Problem from Lang (Replies: 8)

Loading...