Задача о покрытии суммой 1 или 2 чисел всех целых от 0 до N

[ilghiz]

Добрый день,

есть такая задачка, которая у меня возникла совершенно их другой области.

Дано $N$. Мне надо минимизировать число отрезков, с целочисленными значениями координат концов отрезков $[b_i, e_i], i=1, ..., K$, что

$\forall n=1, \dots, N:$ существует или

1. такое $i$, что $e_i-b_i=n$, или
2. такая пара $i,j$, что $e_i-b_j=n$, $e_j=b_i$ (то есть отрезки стоят паровозиком друг за другом).

Я предполагаю, что минимальное число можно получить расположив первые ${\rm ceil}(\sqrt{N-1})$ слева от нуля с длинами от единицы до ${\rm ceil}(\sqrt{N-1})$, а второй комплект справа от нуля, но с длинами ровно в ${\rm ceil}(\sqrt{N-1})$ большими, где функция ${\rm ceil}$ возвращает наименьшее целое значение не меньше аргумента, но не могу доказать, что оптимальнее не бывает.

Например, мы хотим покрыть все числа от единицы до $99$. Тогда первые $9$ отрезков мы расположим слева от нуля с длинами $1,...,9$, и вторые $9$ - справа от нуля с длинами $10,20,...,90$ и всего потребуется только $18$ отрезков.

[worm2]

Если $\sqrt{N+1}$ — целое число, (т.е. $N = k^2-1$), вашу конструкцию действительно нельзя улучшить.
Это следует из того, что для каждой "точки стыка" (точки, являющейся одновременно концом какого-то отрезка и началом какого-то другого отрезка), которая является концом $p$ отрезков и началом $q$ отрезков, число всевозможных длин отрезков, примыкающих к точке по первому пункту равно $p+q$, а по второму пункту — $pq$, что всего даёт $pq+p+q$ длин отрезков. При фиксированном числе отрезков $p+q$ максимум этой величины достигается, когда $p$ максимально близко к $q$. Ну и можно показать, что если "точек стыка" больше одной, то число всевозможных длин только падает, оптимальна только одна "точка стыка". В случае, когда $N = k^2-1$, при числе отрезков $2(k-1)$ и распределении их слева и справа поровну ($p=q=k-1$) общее число длин отрезков получается равным как раз $(k-1)^2+2(k-1)=k^2-1=N$, а при меньшем числе отрезков не достигается. Т.е. меньшим числом отрезков нельзя обойтись.
Ну а то, что этого числа хватит, вы уже показали.

[ilghiz]

Спасибо большое, worm2,
верно, я как раз хотел тему закрывать, так как то же самое собирался написать, но Вы оказались быстрее.

(Оффтоп)

Все... не буду больше на больную голову теоремы доказывать (у меня сейчас 39 и вроде не ковид, а обычная простуда).

Спасибо!!!