2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Задача о покрытии суммой 1 или 2 чисел всех целых от 0 до N
Сообщение16.03.2022, 16:17 
Добрый день,

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

Дано $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$ отрезков.

 
 
 
 Re: Задача о покрытии суммой 1 или 2 чисел всех целых от 0 до N
Сообщение16.03.2022, 18:24 
Аватара пользователя
Если $\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$, а при меньшем числе отрезков не достигается. Т.е. меньшим числом отрезков нельзя обойтись.
Ну а то, что этого числа хватит, вы уже показали.

 
 
 
 Re: Задача о покрытии суммой 1 или 2 чисел всех целых от 0 до N
Сообщение16.03.2022, 21:26 
Спасибо большое, worm2,
верно, я как раз хотел тему закрывать, так как то же самое собирался написать, но Вы оказались быстрее.

(Оффтоп)

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


Спасибо!!!

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group