Ceci fait suite à cette question sur math.stackexchange.
Disons qu'un ensemble non vide S ⊆ ℤ est autoportant si pour tout a ∈ S, il existe des éléments distincts b, c ∈ S tels que a = b + c. Pour les entiers positifs n , des exemples simples incluent l'idéal S = n ℤ, ou (pour n > 3) l'intervalle entier [- n , n ].
Nous dirons que S est fortement autosuffisant si S est disjoint de −S: c'est-à-dire, si a ∈ S, alors - a ∉ S. Aucun des exemples ci-dessus n'est fortement autosuffisant, car ils sont en fait fermés en cours de négation. Il existe des ensembles finis qui sont fortement autoportants: par exemple, les ensembles {−22, −20, −18, −16, −14, −12, −10, −2, 1, 3, 7, 8, 15 , 23} et {−10, −8, −6, −2, 1, 3, 4, 5}.
Question 1. Pour un entier positif N > 0, existe-t-il un algorithme poly ( N ) -temps [ou polylog ( N )-temps] pour soit (i) produire un ensemble fortement autosuffisant dont la valeur absolue maximale est N , ou (ii ) déterminer qu'un tel ensemble n'existe pas? [ Modifier : comme indiqué dans la réponse la plus ancienne + mon commentaire à ce sujet, il existe toujours un tel ensemble pour N ≥ 10.]
Question 2. Pour N > 0, pouvez-vous construire l'ensemble fortement autosuffisant avec la valeur absolue maximale N , et qui a le moins d'éléments possibles?
la source
Réponses:
Je suppose qu'un algorithme de temps linéaire devrait être possible pour la question # 1) (et si vous êtes prêt à traiter avec une représentation différente, un algorithme de temps O (1))
Étant donné tout N> = 23, nous construisons un ensemble fortement autoportant qui contient 1 et N.
Nous pouvons le faire facilement si nous construisons la même chose pour N-1, puis ajoutons N à l'ensemble résultant.
Pour le cas de base de 23, nous pouvons commencer avec votre exemple d'ensemble.
Pour réduire la taille, nous devrions pouvoir utiliser une approche similaire:
Construire des ensembles contenant
1, N and N-1.Nous utilisons ces ensembles contraints et faisons cette construction récursivement pour ramener la taille à O (logN) comme suit:
Si N est pair, pour construire un ensemble contenant 1, N et N-1, construire récursivement un ensemble contenant 1, N / 2 et N / 2-1 (ie ensemble correspondant à N / 2) et ajouter N et N-1 à l'ensemble résultant. Puisque N-1 = N / 2 + N / 2-1 et N = 1 + N-1, il s'agit d'un ensemble valide.
Si N est impair, construisez un ensemble pour N-1 et N pour l'ensemble résultant.
Pour les cas de base, nous pouvons commencer par {−22, −20, −18, −16, −14, −12, −10, −2, 1, 3, 7, 8, 15, 23,24} pour N = 24. Pour 24 <N <= 47, nous pouvons utiliser l'algorithme de temps linéaire ci-dessus et construire sur l'ensemble pour N = 24. Pour N> = 48, nous passons à la réduction de moitié.
En fait, pour le composite N, nous pouvons ramener la taille plus bas à la taille requise pour l'un des petits nombres premiers qui divise N: Trouvez un ensemble pour le petit nombre premier et multipliez simplement tous les nombres par un facteur approprié.
Il pourrait être intéressant de prouver certaines bornes inférieures dans le cas où N est premier.
la source
Pour N ≥ 10, on peut construire un ensemble de tailles fortement autoportant au maximum onze, comme suit:
L'exemple le plus court présenté dans la question initiale correspond au cas N = 10. Ceci est presque optimal, car tout ensemble fortement autoportant doit avoir une cardinalité d' au moins huit .
Ainsi, le problème est résoluble en temps O (log (N)) [repris dans les opérations arithmétiques mondaines sur N], donnant un ensemble de cardinalité entre huit et onze.
La construction de cette réponse a d'abord été présentée pour la question math.stackoverflow , qui donne également l'intuition de la construction. Peut-on encore obtenir des constructions plus petites, par exemple en faisant correspondre la borne inférieure de huit pour chaque N> 9? Qu'en est-il des cas de N ∈ {8,9}?
la source