Un cas particulier de somme sous réserve

Question

Je suis tombé sur le problème suivant dans mon cours de la complexité-théorie:

donné un ensemble de chiffres $ a:={a_1, \ points, a_n \} \ sous-ensemble _ {\ mathrm {fini}} \ mathbb {n} $ $ et un nombre $ B $ également dans $ \ mathbb {n} $ telle que la condition suivante s'applique: $ a_i $ divise $ a_ {i + 1} $ pour tous $ i et $ a_i .Prouver que ce cas particulier de la somme sous-sol est décidable à la p.

En raison de la condition donnée, $ b $ doit être un multiple de la première $ a \ neq 1 $.Prendre $ A_1 \ NEQ 1: B= A_1 \ CDOT X $ .Trouver ce X me ramène au problème du sous-ensemble, ce qui n'est sûrement pas à la p.

Toute aide serait appréciée.

Answer 1

En bref, l'algorithme gourmand fonctionne, où dans chaque étape, vous trouvez le plus grand nombre de $ a $ et soustrayez-le de $ B $ . Si $ B $ devient zéro, vous obtenez une solution. Si vous atteignez un point où tous les numéros dans $ a $ sont supérieurs à $ B $ la sortie no. < / p>

---

Dans ce qui suit, je lister une description formelle de l'algorithme et une preuve de correction.

Voici une description formelle de l'algorithme. Laisse $ a_0= a, b_0= b $ et $ b_i $ est la valeur de $ B $ après la $ i $ -th itération. Laissez $ a_i $ être les chiffres laissés dans $ a $ après la $ i $ -th itération. Ensuite, l'algorithme va comme suit. Dans chaque étape $ i= 1, \ points $ $ trouver le plus grand nombre $ a_j $ in $ a_ {i-1} $ pas supérieur à $ b_ {i-1} $ . Si aucun numéro de ce type n'existe de sortie non. Sinon, définissez $ b_ {i}= b_ {i-1} - a_j $ et $ a_i= a_ {i- 1} \ setminus \ {A_J \ \ \} $ . Si $ B $ devient égal à zéro puis sortie oui, sinon itérer.

revendication 1. L'algorithme précédente Sortie la réponse correcte de l'instance donnée du cas restreint des sujets de sous-ensemble décrits dans la question.

Avant de prouver la réclamation, nous prouvons une revendication auxiliaire.

réclamation 2. let $ a_1, \ dots a_n $ soit les chiffres dans $ Un $ dans l'ordre croissant. Alors $ \ somme \ limites_ {i= 1} ^ {k-1} a_i pour tous $ k \ dans [n] $ .

preuve. (réclamation 2). Preuve avec induction sur $ K $ . Pour n= 1, la somme est vide. Maintenant, nous le prouvons pour $ K $ . $$ \ sum \ limites_ {i= 1} ^ {k-2} a_i + a_ {k-1} <2a_ {i-1} \ leq a_i, $$ Lorsque la première inégalité est tirée en raison de l'hypothèse d'induction et que la seconde détient par hypothèse depuis $ a_ {k-1} $ divise et est plus petite que $ a {k} $ .

preuves. (réclamation 1) Si l'algorithme génère oui, il s'agit clairement d'une instance YES, puisque elle choisit uniquement des nombres à partir des ensembles donnés et soustrayez des valeurs de $ B $ .

Nous prouvons que, si notre algorithme génère non, l'instance donnée est une instance. À cette fin, nous prouvons que si à l'étape i $ i $ nous choisissons un élément $ a_j $ , puis tout La solution de l'instance donnée doit contenir cet élément. Nous prouvons cela par induction sur $ i $ . Notez que tout $ a_j ', j'> j $ est strictement supérieur à $ b_i $ $ a $ faisaient partie d'une solution s'il existe un. Maintenant, à l'aide de la revendication 1, $ \ SUM \ LIMITS_ {I= 1} ^ {J-1} A_J $ < $ A_J $ et puisque nous ne supprimons que des éléments, $ a_i $ ne contient aucun autre élément inférieur à $ A_J $ et donc, si nous ne choisissons pas $ a_j $ choisir tous les éléments plus petits ne suffira pas d'obtenir une somme égale à $ B $ . Par conséquent, nous devons choisir $ a_j $ .

Answer 2

Considérez l'autre cas spécial suivant de votre problème: $ a_i= c ^ {i-1} $ pour certains $ C \ ge 2 $ .Par exemple, si $ C= 10 $ , nous avons donc $ A_1= 1, a_2= 10, a_2= 100,a_3= 1000, \ points, a ^ n= c ^ {n-1} $ .

Dans ce cas, il existe une solution si et seulement si 0 \ le b et la base $ C $ représentation de $ B $ ne contient pas de chiffres autres que 0 et 1. En particulier, il peut y avoir une solution même pour une classe $ b $ qui ne sont pas des multiples de $ C $ , contredisant votre deuxième paragraphe.

Voir si cela vous aide à réfléchir au problème.