We want to reduce the number of non-integers while preserving row and column sums. Intuitively, if we change to , then if we can increase by something else in the same row or column and keep alternately increasing/decreasing stuff, we'll eventually have to "cycle" back to (and the cycle must have even length, since we switch between modifying in the same row and modifying in the same column).

This motivates us to take a bipartite graph where is the set of rows, is the set of columns, and the grid numbers are written on corresponding edges. Furthermore, we can take out all edges with integer labels; we want to get down to zero edges. Because all rows and columns have integer sums, each vertex has degree at least , and so we can find an (even) cycle. Then the rest is clear: taking an edge label in the cycle that minimizes (where denotes the nearest integer function), we can proceed as described in the first paragraph.

Trying some small cases really helps to find this crucial lemma...

Lemma: If and , then the teacher can divide apples evenly among students with just pieces in all.

Proof: One way is just inducting on . Otherwise, motivated by the previous problem, we interpret this as a bipartite graph the edges represent the portions of apple students in get from the vertices in . At first, label each edge with . We want to reduce to edges (i.e. a tree) by modifying edges and deleting the zero labels. To this end, suppose we have a cycle , which must be even since is bipartite. If the edge label minimizes in the cycle, then change to or accordingly and alternately modify the other edges in the cycle by , preserving both the sum of edges emanating from vertices in (which must be ) and the sum of edges emanating from vertices in (which must be ), as well as the positiveness of the edge labels. If we change to in the process, then we lose at least one edge; otherwise, if we change it to , then the vertex in belonging to it goes from edges (necessary to participate in the cycle) to exactly edge (since all its other edges must become ), and we still lose at least one edge. Clearly this process terminates when we reach a tree of vertices, as desired.

Let for , so . The bipartite graph only has connected components with vertices in and vertices in with and thus at least edges for some . Since the sum of all such is , there are at most components and thus at least edges, with equality achievable by the lemma.

Induction is clearly the most natural path, as long as we find a reasonable way to go down from and to and .

Lemma: Given integers, we can find of them with sum divisible by .

Proof: Well-known pigeonhole on partial sums .

Directly using this lemma and inducting does not work, because we can be left with numbers in . However, is quadratic, so with a little fiddling we weaken the hypothesis to "," with the base case being clear. Now it works smoothly, since if we use the lemma to break our set into groups of numbers with sum both divisible by and at most (first we put the 's in their own groups, and then just work with the numbers in ), then dividing each of these groups' sums by , we have a new sum at least
for , as desired.