Potongan-potongan puzzle

Masalah: Kami diberi satu set batang yang semuanya memiliki panjang bilangan bulat. Jumlah total panjangnya adalah n (n + 1) / 2.

Bisakah kita memecahnya untuk mendapatkan ukuran tongkat dalam waktu polinomial? ${1,2,\ldots,n}$

Anehnya, satu-satunya referensi yang saya temukan untuk masalah ini adalah diskusi kuno ini:

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

Apa lagi yang diketahui tentang masalahnya? Bisakah kita membuktikan masalahnya sebagai `dalam limbo '?

Pembaruan: Masalah stik memiliki kendala bahwa masing-masing stik setidaknya memiliki panjang unit. (Lihat komentar dan jawaban Tsuyoshi untuk kasus yang tidak dibatasi).$n$

Perhatian: Ketika Jukka Suomela mengomentari pertanyaan itu, halaman yang terhubung dari pertanyaan tersebut adalah tentang masalah yang berbeda dari masalah yang dinyatakan dalam pertanyaan di mana masalah pada halaman tersebut memiliki batasan bahwa panjang tongkat yang diberikan lebih besar atau sama dengan n. Jawaban ini adalah tentang masalah tanpa batasan ini. Karena komentar Emil tentang pertanyaan mengacu pada masalah dengan pembatasan, tidak ada kontradiksi antara komentarnya dan jawaban berikut.

Masalahnya adalah NP-complete, bahkan jika angka diberikan secara unary.

Masalah 3-partisi adalah masalah berikut:
Instance : Positif bilangan bulat a ₁ , ..., a _n di unary, di mana n = 3m dan jumlah dari n bilangan bulat sama dengan mB, sehingga masing-masing _i memenuhi B / 4 < a _i <B / 2.
Pertanyaan : Bisakah bilangan bulat a ₁ ,…, a _n dipartisi menjadi m multiset sehingga jumlah masing-masing multiset sama dengan B?

Masalah 3-partisi adalah NP-complete bahkan jika ₁ ,…, _dan semuanya berbeda [HWW08] (terima kasih kepada Serge Gaspers karena memberi tahu saya tentang ini ). Dimungkinkan untuk mengurangi versi terbatas masalah 3-partisi ini ke masalah yang dimaksud sebagai berikut.

Misalkan kita diberi contoh masalah 3-partisi yang terdiri dari bilangan bulat positif berbeda ₁ ,…, a _n . Misalkan m = n / 3 dan B = (a ₁ +… + a _n ) / m, dan biarkan N menjadi maksimum di antara _i . Pertimbangkan contoh berikut dari masalah tongkat: contoh terdiri dari satu tongkat panjang k untuk setiap k∈ {1, ..., N} ∖ {a ₁ , ..., a _n } dan m tongkat panjang B. Dengan menggunakan fakta bahwa setiap _i memenuhi _i > B / 4 ≥ N / 2, mudah untuk membuktikan bahwa masalah stick ini memiliki solusi jika dan hanya jika instance dari masalah 3-partisi memiliki solusi.

Referensi

[HWW08] Heather Hulett, Todd G. Will, Gerhard J. Woeginger. Realisasi multigraf dari urutan derajat: Maksimal mudah, minimisasi sulit. Operations Research Letters , 36 (5): 594–596, September 2008. http://dx.doi.org/10.1016/j.orl.2008.05.004