Вычислим множество B всех сумм ax+by в доказанных границах и оставим суммы от 0 до требуемой верхней границы T. Если добавлено k монет по 1, каждая сумма v из B даёт все целые значения от v до v+k. Чтобы эти промежутки покрыли от 0 до T, необходимо и достаточно k≥vnext−v−1 для любых соседних сумм и k≥T−vmax. Поэтому минимум k равен максимуму этих разрывов и остатка в конце. Это одновременно нижняя граница и доказательство покрытия всех сумм.
Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.
Шаг 1. Вычислим множество B всех сумм ax+by в доказанных границах и оставим суммы от 0 до требуемой верхней границы T. Если добавлено k монет по 1, каждая сумма v из B даёт все целые значения от v до v+k. Чтобы эти промежутки покрыли от 0 до T, необходимо и достаточно k≥vnext−v−1 для любых соседних сумм и k≥T−vmax. Поэтому минимум k — максимум этих разрывов и остатка в конце. Это одновременно нижняя граница и доказательство покрытия всех сумм.