Ini adalah tindak lanjut dari pertanyaan ini di math.stackexchange.
Mari kita katakan bahwa himpunan non-kosong S ⊆ ℤ adalah swadaya jika untuk setiap a ∈ S, terdapat elemen yang berbeda b, c ∈ S sedemikian rupa sehingga a = b + c. Untuk bilangan bulat positif n , contoh sederhana termasuk S = n ℤ yang ideal, atau (untuk n > 3) interval bilangan bulat [- n , n ].
Kami akan mengatakan bahwa S adalah sangat mandiri jika S adalah memisah dari -S: yaitu, jika suatu ∈ S, kemudian - sebuah ∉ S. Tak satu pun dari contoh di atas adalah sangat mandiri, karena mereka sebenarnya ditutup di bawah negasi. Ada set yang terbatas yang sangat mandiri: misalnya, set {−22, −20, −18, −16, −12, ,12, −10, −2, 1, 3, 7, 8, 15 , 23} dan {−10, −8, −6, −2, 1, 3, 4, 5}.
Pertanyaan 1. Untuk bilangan bulat positif N > 0, apakah ada algoritma poly ( N ) -waktu [atau polylog ( N ) -waktu ) untuk (i) menghasilkan himpunan swadaya kuat yang nilai absolut maksimumnya adalah N , atau (ii) ) menentukan bahwa tidak ada set seperti itu ada? [ Sunting : seperti yang ditunjukkan dalam jawaban terlama + komentar saya tentang itu, selalu ada set untuk N ≥ 10.]
Pertanyaan # 2. Untuk N > 0, dapatkah Anda membangun set swadaya kuat dengan nilai absolut maksimum N , dan yang memiliki elemen paling sedikit?
sumber
Jawaban:
Saya kira algoritma waktu linear seharusnya dimungkinkan untuk Pertanyaan # 1) (dan jika Anda bersedia berurusan dengan representasi yang berbeda, algoritma waktu O (1))
Diberikan N> = 23, kami membangun set mandiri yang berisi 1 dan N.
Kita dapat melakukannya dengan mudah jika kita membuat yang sama untuk N-1, dan kemudian menambahkan N ke set yang dihasilkan.
Untuk kasus dasar 23, kita bisa mulai dengan contoh yang Anda buat.
Untuk menurunkan ukuran, kita harus dapat menggunakan pendekatan serupa:
Bangun set yang berisi
1, N and N-1.Kami menggunakan set terbatas ini dan melakukan konstruksi ini secara rekursif untuk menurunkan ukuran ke O (logN) sebagai berikut:
Jika N adalah genap, untuk membangun himpunan yang berisi 1, N dan N-1, secara konstruktif himpunan himpunan yang berisi 1, N / 2 dan N / 2-1 (yaitu himpunan yang sesuai dengan N / 2) dan tambahkan N dan N-1 untuk set yang dihasilkan. Karena N-1 = N / 2 + N / 2-1 dan N = 1 + N-1, ini adalah himpunan yang valid.
Jika N adalah ganjil, buat satu set untuk N-1 dan N untuk set yang dihasilkan.
Untuk kasus dasar, kita dapat mulai dengan {−22, −20, −18, −16, −14, −12, −10, −2, 1, 3, 7, 8, 15, 23, 24} untuk N = 24. Untuk 24 <N <= 47, kita dapat menggunakan algoritma waktu linier di atas dan membangun set untuk N = 24. Untuk N> = 48 kita beralih ke mengurangi setengahnya.
Bahkan, untuk komposit N, kita dapat membawa ukuran lebih jauh ke ukuran yang diperlukan untuk salah satu bilangan prima kecil yang membagi N: Temukan set untuk bilangan prima kecil, dan cukup gandakan semua angka dengan faktor yang sesuai.
Mungkin menarik untuk membuktikan beberapa batasan yang lebih rendah dalam kasus N adalah prima.
sumber
Untuk N ≥ 10, seseorang dapat membangun seperangkat ukuran mandiri yang paling banyak sebelas, sebagai berikut:
Contoh yang lebih pendek disajikan dalam pertanyaan asli sesuai dengan kasus N = 10. Ini hampir optimal, karena setiap set mandiri sangat harus memiliki kardinalitas setidaknya delapan .
Dengan demikian, masalahnya dapat dipecahkan dalam waktu O (log (N)) [diambil dalam operasi aritmatika biasa pada N], menghasilkan serangkaian kardinalitas antara delapan dan sebelas.
Konstruksi untuk jawaban ini pertama kali disajikan untuk pertanyaan math.stackoverflow , yang juga memberikan intuisi untuk konstruksi. Bisakah kita mendapatkan konstruksi yang lebih kecil lagi, misalnya mencocokkan batas bawah delapan untuk setiap N> 9? Bagaimana dengan kasus N ∈ {8,9}?
sumber