Jest to kontynuacja tego pytania na math.stackexchange.
Powiedzmy, że niepusty zbiór S ⊆ ℤ jest samonośny, jeśli dla każdego a ∈ S istnieją odrębne elementy b, c ∈ S takie, że a = b + c. Dla dodatnich liczb całkowitych n , proste przykłady obejmują idealną S = n ℤ lub (dla n > 3) przedział liczb całkowitych [- n , n ].
Powiemy, że S jest silnie samonośna jeśli S jest rozłączne z -S: to znaczy, jeśli ∈ S, a następnie - ∉ S. Żadne z powyższych przykładów są silnie samonośna, ponieważ są one w rzeczywistości zamknięte pod negacją. Istnieją zestawy skończone, które są silnie samonośne: na przykład zestawy {−22, −20, −18, −16, −14, −12, −10, −2, 1, 3, 7, 8, 15 , 23} i {−10, −8, −6, −2, 1, 3, 4, 5}.
Pytanie 1. Dla dodatniej liczby całkowitej N > 0, czy istnieje algorytm poli ( N ) -time [lub polylog ( N ) -time], który albo (i) wytworzy silnie samonośny zestaw, którego maksymalna wartość bezwzględna wynosi N , lub (ii ) ustalić, czy taki zestaw nie istnieje? [ Edycja : jak wskazano w najstarszej odpowiedzi + mój komentarz na ten temat, zawsze istnieje taki zestaw dla N ≥ 10.]
Pytanie 2. Czy dla N > 0 można zbudować silnie samonośny zestaw z maksymalną wartością bezwzględną N i który ma najmniej możliwych elementów?
źródło
Odpowiedzi:
Przypuszczam, że dla pytania nr 1 powinien być możliwy liniowy algorytm czasu (a jeśli chcesz poradzić sobie z inną reprezentacją, algorytm czasu O (1))
Biorąc pod uwagę dowolne N> = 23, tworzymy silnie samonośny zestaw, który zawiera 1 i N.
Możemy to zrobić łatwo, jeśli zbudujemy to samo dla N-1, a następnie dodamy N do wynikowego zestawu.
W przypadku przypadku podstawowego 23 możemy zacząć od zestawu przykładów.
Aby zmniejszyć rozmiar, powinniśmy być w stanie zastosować podobne podejście:
Twórz zestawy zawierające
1, N and N-1.Używamy tych zestawów ograniczonych i wykonujemy tę konstrukcję rekurencyjnie, aby sprowadzić rozmiar do O (logN) w następujący sposób:
Jeśli N jest parzyste, aby zbudować zestaw zawierający 1, N i N-1, rekurencyjnie skonstruuj zestaw zawierający 1, N / 2 i N / 2-1 (tj. Zestaw odpowiadający N / 2) i dodaj N i N-1 do wynikowego zestawu. Ponieważ N-1 = N / 2 + N / 2-1 i N = 1 + N-1, jest to prawidłowy zestaw.
Jeśli N jest nieparzyste, konstruuj zestaw dla N-1 i N do zbioru wynikowego.
W przypadkach podstawowych możemy zacząć od {−22, −20, −18, −16, −14, −12, −10, −2, 1, 3, 7, 8, 15, 23,24} dla N = 24 Dla 24 <N <= 47 możemy użyć powyższego liniowego algorytmu czasowego i oprzeć się na zbiorze dla N = 24. Dla N> = 48 przełączamy na redukcję o połowę.
W rzeczywistości dla złożonego N możemy sprowadzić rozmiar do rozmiaru wymaganego dla jednej z małych liczb pierwszych, która dzieli N: Znajdź zestaw dla małej liczby pierwszej i po prostu pomnóż wszystkie liczby przez odpowiedni współczynnik.
Interesujące może być udowodnienie niektórych dolnych granic w przypadku, gdy N jest liczbą pierwszą.
źródło
Dla N ≥ 10 można zbudować silnie samonośny zestaw wielkości co najwyżej jedenastu, w następujący sposób:
Krótszy przykład przedstawiony w pierwotnym pytaniu odpowiada przypadkowi N = 10. Jest to prawie optymalne, ponieważ każdy silnie samonośny zestaw musi mieć liczność co najmniej osiem .
Tak więc problem można rozwiązać w czasie O (log (N)) [podejmowanym w zwykłych operacjach arytmetycznych na N], uzyskując zbiór liczności między ósmą a jedenastą.
Konstrukcja tej odpowiedzi została po raz pierwszy zaprezentowana dla pytania mat.stackoverflow , które daje również intuicję do konstrukcji. Czy nadal możemy uzyskać mniejsze konstrukcje, np. Pasujące do dolnej granicy ośmiu dla każdego N> 9? Co z przypadkami N ∈ {8,9}?
źródło