Organizing Containers of Balls

  • + 0 comments

    To make a container (row) of size N monochromatic, that row must retrieve N balls of the same color from a suitable source. A suitable source is any column of the container array that has at least N balls, because each column is monochromatic by the problem statement. But if all such suitable columns have more than N balls, then some other row will have to accept the surplus, making it polychromatic. Therefore, if a solution exists, it is necessary that every row have a unique counterpart column containing the same number of balls.

    Notice also that if every row has a unique counterpart column of the same size, then also every column has a unique counterpart row of the same size.

    Conversely, assuming every row has a unique counterpart column of the same size, every row can be made monochromatic. Indeed, say the counterpart of row i is column j. The balls corresponding to cell ij will not be swapped because they are already of the color of column j. The rest will be swapped with the balls from column j. But where will the balls from row i but columns other than j go? They will be in turn uptaken by the rows corresponding to these columns, by the assumprion.

    Thus, the problem has a solution if and only if each row has a corresponding column of equal size. Thus, if X is the array of row sizes, and Y of column sizes, for each i there must be a unique j such that X[i] = Y[j]. Since X and Y are arrays of the same length, this is equivalent to Y being a permuted copy of X, which in turn is equivalent to sorted array X being equal to sorted Y.

    def organizingContainers(container):
        l = len(container)
        X = [sum([container[i][j] for j in range(l)]) for i in range(l)]
        Y = [sum([container[i][j] for i in range(l)]) for j in range(l)]
        if sorted(X) == sorted(Y):
            return "Possible"
        else:
            return "Impossible"