Regarding this problem in UVA: Food portion sizes I know that the optimal S will be either arr[i]/1 or arr[i]/2 or arr[i]/3, where 1 <= i <= n and arr[i] is the required food for ith person, that is we try all arr[i]/1, arr[i]/2, arr[i]/3 for all i and choose the one which gives minimum result. I know that these three choices are the minimum choices in terms of cost for the ith person, but why choosing one of them from one of the n persons results in a minimum total result for all people ? what is the proof for this ?