The Inventory Organization Problem


N items are to be placed in positions in a table by the following algorithm:

1. Under the restriction that no more than C columns can be used, the minimum number of rows required is computed. Call this number R.
2. The items are placed into the table using R rows, such that the number of columns used is minimized. Let C' be the number of columns used.

Problem: Given a fixed value of C, the maximum number of columns, find the largest value of N for which C' is less than C. Assume C is greater than 0.

Answer: N = (C-1)^2 is the largest value for which C' is less than C.

Proof: Two things must be shown. First, that for N = (C-1)^2, we indeed have C' is less than C. Second, that for any M is greater than N, we have C' at least as large as C.

(1) Let N = (C-1)^2. Then R = (C-1), for the maximum number of objects that can be placed in (C-2) rows is (C-2)(C) = C^2 - 2C which is one less than (C-1)^2 = C^2 - 2C + 1. On the other hand, (C-1) rows suffice since (C-1)^2 is less than (C-1)(C), the maximum number of objects that can be placed in (C-1) rows. Now knowing that R = (C-1), it follows that C' is less than C since we can form the N objects into a square table consisting of C-1 columns. Thus C', the MINIMUM number of columns needed, is less than C. (2) Now suppose M is greater than N = (C-1)^2 and that under the algorithm, C' is less than C. We may suppose that M is one larger than a multiple of C, for the following reason. For any value of R, (R-1)C + 1 will minimize the total number of objects, and hence the total number of columns necessary. Thus M = CK + 1 for some K, and since M is greater than N, we see that K is at least C-1. Also, in this case R = K+1. But the maximum number of objects that can be placed in R rows and C-1 columns is (K+1)(C-1) = CK + (C-K) - 1, which since C-K-1 is at most zero, is less than CK + 1 = M. This contradicts the assumption that C' is less than C, and so no such M exists.

Together, these steps prove that N = (C-1)^2 is the largest value for which C' is less than C.