1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Can somebody rephrase this putnam problem for me?

  1. Nov 19, 2007 #1
    1. The problem statement, all variables and given/known data

    I am working on Problem 2.

    Can someone rephrase that question for me? I do not see why you would be dividing anything in this problem.

    The monovariant I found in Sample 3 was the sum of the difference between people in adjacent rooms. This number is bounded from above and monotonically increasing. The upper bound is the total number of people times the maximum number of rooms connected to any one room.

    2. Relevant equations

    3. The attempt at a solution
  2. jcsd
  3. Nov 19, 2007 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Problem 2 says:
    Solve sample 3 in a manner that makes use of the sum
    [itex]\sum 1/(n_i + 1)[/itex].​
  4. Nov 19, 2007 #3
    Then I really have no idea. This must be completely different than the way I explained in the first post. I don't know what the n_i are and I still do not see where division would come in.

    But wait. Let n_i be the number of people in room i. The reason you need to add 1 in the denominator is because a room might have 0 people. Now, when someone goes from room i_1 to room i_2, that sum changes by

    [tex] 1/(n_{i_1}}) - 1/(n_{i_1} +1)+ 1/(n_{i_2} +2) - 1/(n_{i_2}+1}) [/tex]

    and it is easy to show that this sum is positive when n_j is greater than or equal to n_i

    So that sum is monotonically increasing.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook