# Can somebody rephrase this putnam problem for me?

1. Nov 19, 2007

### ehrenfest

1. The problem statement, all variables and given/known data
http://math.stanford.edu/~vakil/putnam07/07putnam5.pdf

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. Nov 19, 2007

### Hurkyl

Staff Emeritus
Problem 2 says:
Solve sample 3 in a manner that makes use of the sum
$\sum 1/(n_i + 1)$.​

3. Nov 19, 2007

### ehrenfest

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

$$1/(n_{i_1}}) - 1/(n_{i_1} +1)+ 1/(n_{i_2} +2) - 1/(n_{i_2}+1})$$

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.

Thanks.