Daily Archives: 2012/10/18

A water sharing problem and Sage

Posted on by

Here is the problem: There are n students, each with a cup that could contain water or could be empty. We assume that the cups have no limit and that there is at least one student with some water. Order the students from those who have the most water to those who have the least, with arbitrary choices in cases of ties. Following this order, each student takes turn sharing his water equally with the other students. In other words, a student with r ounces of water will give r/n ounces to each of the others (and hence have r/n ounces remaining for himself).

Q1: Is it possible that there is an initial configuration so that, at the end, all the students have exactly the same amount they started with?
This would mean that sharing was in fact not a loss.

Q2: Will this process “usually even out” the distribution of water?
(Part of the answer is to try to make this question more precise!)

Q3: Does the initial ordering of the students (ie, who pours when) matter?

This can be viewed as a matrix question. The action of the i-th student sharing water can be viewed as a linear transformation A_i on the vector of water quantities, indexed by the students. I think that in general the answer to Q1 is “yes.” Here is the Sage code in the case of 3 students:

sage: A1 = matrix(QQ, [[1/3,0,0],[1/3,1,0],[1/3,0,1]])
sage: A2 = matrix(QQ, [[1,1/3,0],[0,1/3,0],[0,1/3,1]])
sage: A3 = matrix(QQ, [[1,0,1/3],[0,1,1/3],[0,0,1/3]])
sage: (A1*A2*A3).eigenvectors_right()                 
[(1, [(1, 2, 3)], 1), 
 (0.1851851851851852? - 0.05237828008789241?*I, 
 [(1, 0.?e-57 + 1.414213562373095?*I, -1.000000000000000? - 1.414213562373095?*I)], 1), 
 (0.1851851851851852? + 0.05237828008789241?*I, 
 [(1, 0.?e-57 - 1.414213562373095?*I, -1.000000000000000? + 1.414213562373095?*I)], 1)]

In other words, the product A_1A_2A_3 has eigenvalue \lambda = 1 with eigenvector \vec{v} = (1,2,3). This means that in the case that student 1 has 3 ounces of water, student 2 has 2 ounces of water, student 3 has 1 ounce of water, if each student shares water as explained in the problem, at the end of the process, they will each have the same amount as they started with.

I don’t know the answer to Q2 or Q3.