Consider a $n\times n$ board. A pawn is placed on the top left square of the board. The pawn must go to the bottom right square of the board by moving right and down on the board. We must label each square of the board with a positive integer in such a way that the sum of the numbers labeled is different for each possible path the pawn can take. How can we minimize the greatest value labeled?
What I've noticed so far:
There are $\begin{aligned}\binom{2n-2}{n-1}\end{aligned}$ possible paths the pawn can take, each passing by $2n-1$ different squares of the board. If we are allowed to use $x$ different numbers, then there are $\begin{aligned}\binom{2n+x-2}{x-1}\end{aligned}$ possible sums of $2n-1$ elements, so we must have at least $\begin{aligned}\binom{2n-2}{n-1}\le \binom{2n+x-2}{x-1}\end{aligned}$, but that's an inequality that I don't know how to solve for $x$.
If we label the whole $k$-th column with $(n+1)^{k-1}$, then the sum of the values in each path will have a different representation in base $n+1$ and the greatest value labeled is $(n+1)^{n-1}$, so $(n+1)^{n-1}$ is an upper bound for the desired answer, but of course not every representation in base $n+1$ is associated with a path, therefore it should be possible to refine this upper bound.
Any tips about how to approach this problem and get good bounds for the desired answer will be very welcome.
ETA2: I think I misunderstood the question to ask for the arrangement that minimizes the maximum sum, rather than the maximum label. I'm leaving the answer here for "historical interest." :-)
I think this works (ETA after fixing a typo):
One can achieve the minimum by adhering to the following procedure. Let the squares be identified as $(x, y)$, with $0 \leq x, y \leq n-1$, and let the label at $(x, y)$ be denoted $f(x, y)$. Begin by setting $f(x, 0) = f(0, y) = 1$. (That is, label all squares along the bottom row and leftmost column with the number $1$.)
Now, begin labelling columns from left to right. We assign
$$ f(x, y) = f(x-1, y-1) + \binom{x-y+n-1}{x} $$
This "reserves" enough values for those paths that pass through $(x, y-1)$ without passing through $(x, y)$. Then the lowest-sum path passes straight down and then to the right (and yields the lowest sum possible), while the highest-sum path passes straight right and then down. You will find that the lower path has sum $2n-1$, while the higher path has sum $\binom{2n-2}{n-1}+2n-2$, achieving the minimum highest sum.
For example, for $n = 5$, we have the square
$$ \begin{array}{ccccc} 1 & 2 & 3 & 5 & 9 \\ 1 & 2 & 4 & 8 & 15 \\ 1 & 2 & 5 & 11 & 21 \\ 1 & 2 & 5 & 11 & 21 \\ 1 & 1 & 1 & 1 & 1 \end{array} $$
which I believe produces every sum from $9$ through $78$ exactly once.
Please let me know if I've made an error and there is a duplicate sum!