Este é um acompanhamento para esta pergunta em math.stackexchange.
Digamos que um conjunto não vazio S ℤ ℤ seja auto-sustentável se, para todo a ∈ S, existirem elementos distintos b, c ∈ S tais que a = b + c. Para números inteiros positivos n , exemplos simples incluem o ideal S = n ℤ ou (para n > 3) o intervalo inteiro [- n , n ].
Diremos que S é fortemente auto-sustentável se S for separado de −S: isto é, se a S, então - a ∉ S. Nenhum dos exemplos acima é auto-suficiente, porque na verdade eles estão fechados sob negação. Existem conjuntos finitos que são fortemente autossustentáveis: por exemplo, os conjuntos {−22, −20, −18, −16, −14, −12, −10, −2, 1, 3, 7, 8, 15 , 23} e {−10, −8, −6, −2, 1, 3, 4, 5}.
Questão 1. Para um número inteiro positivo N > 0, existe um algoritmo poly ( N ) -time [ou polylog ( N ) -time ]] para (i) produzir um conjunto fortemente autossustentável, cujo valor absoluto máximo é N , ou (ii) ) determinam que esse conjunto não existe? [ Editar : como indicado na resposta mais antiga + no meu comentário, sempre existe um conjunto para N ≥ 10.]
Questão 2. Para N > 0, você pode construir o conjunto fortemente autossustentável com o valor absoluto máximo N e qual possui o menor número possível de elementos?
fonte
Respostas:
Suponho que seja possível um algoritmo de tempo linear para a pergunta nº 1) (e se você estiver disposto a lidar com uma representação diferente, um algoritmo de tempo O (1))
Dado qualquer N> = 23, construímos um conjunto fortemente autoportante que contém 1 e N.
Podemos fazer isso facilmente se construirmos o mesmo para N-1 e depois adicionar N ao conjunto resultante.
Para o caso base de 23, podemos começar com seu conjunto de exemplos.
Para diminuir o tamanho, poderemos usar uma abordagem semelhante:
Conjuntos de construções que contêm
1, N and N-1.Usamos esses conjuntos restritos e fazemos essa construção recursivamente para reduzir o tamanho para O (logN) da seguinte maneira:
Se N for par, para construir um conjunto contendo 1, N e N-1, construa recursivamente um conjunto contendo 1, N / 2 e N / 2-1 (ou seja, conjunto correspondente a N / 2) e adicione N e N-1 ao conjunto resultante. Como N-1 = N / 2 + N / 2-1 e N = 1 + N-1, esse é um conjunto válido.
Se N for ímpar, construa um conjunto para N-1 e N para o conjunto resultante.
Para os casos base, podemos começar com {−22, −20, −18, −16, −14, −12, −10, −2, 1, 3, 7, 8, 15, 23,24} para N = 24. Para 24 <N <= 47, podemos usar o algoritmo de tempo linear acima e desenvolver o conjunto para N = 24. Para N> = 48, passamos a reduzir pela metade.
De fato, para o composto N, podemos reduzir ainda mais o tamanho necessário para um dos primos pequenos que divide N: encontre um conjunto para o primo pequeno e apenas multiplique todos os números por um fator adequado.
Pode ser interessante provar alguns limites inferiores no caso de N ser primo.
fonte
Para N ≥ 10, pode-se construir um conjunto de tamanho fortemente auto-suficiente no máximo onze, da seguinte maneira:
O exemplo mais curto apresentado na pergunta original corresponde ao caso N = 10. Isso está próximo de ser ideal, pois qualquer conjunto fortemente autossustentável deve ter cardinalidade de pelo menos oito .
Assim, o problema é solucionável no tempo O (log (N)) [retomado em operações aritméticas mundanas em N], produzindo um conjunto de cardinalidade entre oito e onze.
A construção desta resposta foi apresentada pela primeira vez na pergunta math.stackoverflow , que também fornece a intuição para a construção. Ainda podemos obter construções menores, por exemplo , igualando o limite inferior de oito para cada N> 9? E os casos de N ∈ {8,9}?
fonte