Is it necessarily the case that an optimal solution for n+1 can be derived from an optimal solution for n by making additional cuts (i.e., by splitting some of the fractions)? Another way to ask this is whether an optimal solution for n+1 can be reduced to an optimal solution for n by combining pieces. I.e., can the groupings up to n always be formed with certain pieces from the n+1 solution always occurring in pairs? Tom Victor Miller writes:
Allan, Thanks. Why didn't I see that? In any case it's not completely clear to me what the algorithms were to find good solutions for f(n), but here's one:
Do this inductively -- collect a whole bunch of good solutions for f(n), and try to extend them to f(n+1), by a sort of bin packing procedure: have n+1 bin of capacity 1/(n+1) and for each solution for f(n) try to place the pieces in the bins so that you need to make the minimal number of cuts to make them fit exactly. It's not clear, a priori, which of the minimal solutions to f(n) will extend to f(n+1), you need to collect a bunch of them.
On Tue, Dec 19, 2017 at 10:47 AM, Allan Wechsler <acwacw@gmail.com> wrote:
Google translate seems to work fine for the Russian discussion at dxdy.ru. Every once in a while you trip over something (like LCM = NOK).
They seem like a rather jolly, collegial crew over there.
They also wrestled momentarily with the worry that the optimal solution might be irrational, but somebody quickly demonstrated that the problem was equivalent to very big systems of linear equations with rational coefficients, exactly as Victor pointed out here.