Układanka do cięcia pałeczek

Problem: Dostajemy zestaw drążków o długości całkowitej. Całkowita suma ich długości wynosi n (n + 1) / 2.

Czy możemy je rozbić, aby uzyskać kije wielkości czasie wielomianowym? ${1,2,\ldots,n}$

Co zaskakujące, jedynym odniesieniem do tego problemu jest starożytna dyskusja:

http://www.iwriteiam.nl/cutsticks.html

Co jeszcze wiadomo na temat problemu? Czy możemy udowodnić, że problemem jest „otchłań”?

Aktualizacja: Problem drążków tnących wiąże się z tym, że każdy drążek ma co najmniej jednostek długości. (Zobacz komentarze i odpowiedź Tsuyoshi dla przypadku nieograniczonego).$n$

Uwaga: Jak Jukka Suomela skomentował pytanie, strona z linkiem do pytania dotyczy innego problemu niż problem wskazany w pytaniu, ponieważ problem na stronie ma ograniczenie, że długości danych patyczków są większe lub równe n. Ta odpowiedź dotyczy problemu bez tego ograniczenia. Ponieważ komentarz Emila do pytania odnosi się do problemu z ograniczeniem, nie ma sprzeczności między jego komentarzem a następującą odpowiedzią.

Problem jest NP-zupełny, nawet jeśli liczby podano jednostronnie.

Problemem z 3 partycjami jest następujący problem:
Wystąpienie : dodatnie liczby całkowite a ₁ ,…, _{nw jednostkowej} , gdzie n = 3m, a suma n liczb całkowitych jest równa mB, tak że każda a _i spełnia B / 4 < a _i <B / 2.
Pytanie : Czy liczby całkowite a ₁ ,… _n można podzielić na m multiset, aby suma każdego multisetu była równa B?

Problem z 3 partycjami jest NP-zupełny, nawet jeśli ₁ ,…, _n są różne [HWW08] (dziękuję Serge Gaspers za to , że mi o tym powiedziałeś ). Możliwe jest ograniczenie tej ograniczonej wersji problemu z 3 partycjami do tego problemu w następujący sposób.

Załóżmy, że otrzymaliśmy przykład problemu z 3 partycjami składającego się z różnych dodatnich liczb całkowitych a ₁ ,…, _n . Niech m = n / 3 i B = (a ₁ +… + a _n ) / m, i niech N będzie maksimum wśród _i . Rozważmy następujące wystąpienie problemu sztyftu: wystąpienie zawiera jeden kawałek o długości K dla każdego k∈ {1, ..., N} ∖ {A ₁ , ..., A _N }, a m pałeczki o długości B, wykorzystując fakt że każdy a _i spełnia warunek _i > B / 4 ≥ N / 2, łatwo jest udowodnić, że ten problem z drążkiem ma rozwiązanie, i tylko wtedy, gdy wystąpi problem z 3 partycjami.

Bibliografia

[HWW08] Heather Hulett, Todd G. Will, Gerhard J. Woeginger. Multigraficzne realizacje sekwencji stopni: maksymalizacja jest łatwa, minimalizacja jest trudna. Operacje Research Letters , 36 (5): 594-596, wrzesień 2008. http://dx.doi.org/10.1016/j.orl.2008.05.004