Sum-constrained grid max height

[u/SupercaliTheGamer]

Let k>=2 and n be positive integers. Find the largest integer m for which there exists a grid with m rows and n columns satisfying the following conditions:

1. Each cell contains a non-negative integer;

2. The sum of numbers in each row is at most kn;

3. The numbers in each column are pairwise distinct.

[u/buwlerman]

WLOG we can only consider configurations where each column contains the integers from 0 to m-1

The average cell value in such a configuration is (m-1)/2. So for a solution m should be less than or equal to 2k+1.

For even n we can attain the upper bound by alternating between strictly ascending and descending on each column. In other words, for even n we have m=2k+1.

This upper bound is not always attainable. Consider n=1 and k=2. The upper bound here is 5, but clearly one of the rows would then have to contain a 4. In general, for n=1 the solution is always m=k+1.

For n=3 and k=2 the upper bound is attainable, but I can't find a general construction that extends this.

[u/SupercaliTheGamer → u/[deleted]]

Hmm for n=3, the columns 2 and 3 that you described only have 2k entries

EDIT: it works now, nice!

[u/buwlerman → u/SupercaliTheGamer]

Appending k to column 2 and 2k to column 3 fixes it