Discussion :

[Ja Rasta]

Bonjour à tous.
J'ai un exercice contenant 5 questions mais je n'arrive pas à comprendre 2 de leurs.

Voici le problème et les 2 questions auxquelles je cherche la solution :

On considère le problème suivant qu’on appellera 3SumSet :
Input : A, B et C des ensembles d’entiers (positifs ou n´egatif )
Question : Existe-t-il trois valeurs a ∈ A, b ∈ B et c ∈ C telles que a + b = c.
La taille d’une instance est la somme des cardinalités des trois ensembles de départ.

1. Donnez une instance de taille 9 du problème 3SumSet qui a une solution puis une instance de taille 5 qui n’a pas de solution.

2. Montrer que pour toute instance I de ce problème , il existe une instance I' de même taille ne contenant que des entiers positifs telle que I a une solution si et seulement si I' a une solution.

Si quelqu'un a une solution à me proposer j'en suis preneur.
Merci d'avance!!!

[picodev]

On considère le problème suivant qu’on appellera 3SumSet :
Input : A, B et C des ensembles d’entiers (positifs ou n´egatif )
Question : Existe-t-il trois valeurs a ∈ A, b ∈ B et c ∈ C telles que a + b = c.
La taille d’une instance est la somme des cardinalités des trois ensembles de départ.

1. Donnez une instance de taille 9 du problème 3SumSet qui a une solution puis une instance de taille 5 qui n’a pas de solution.

Bonjour,
C'est pas bien compliqué. Tu comprends déjà qu'il faut trouver trois ensembles, le nombre total de nombre dans les 3 ensembles est la taille du problème.
Un problème de taille 9 consiste donc à trouver trois ensembles contenant en tout 9 nombres, s'il a une solution alors un des nombres de A ajouté à un des nombres de B donne un des nombres de C …
Par exemple une instance de taille 7 qui possède une solution est A={1} B={-1} C={1,2,15,7,0}. En revanche si on enlève le 0 de C …

2. Montrer que pour toute instance I de ce problème , il existe une instance I' de même taille ne contenant que des entiers positifs telle que I a une solution si et seulement si I' a une solution.

Si quelqu'un a une solution à me proposer j'en suis preneur.
Merci d'avance!!!

Que se passerait-il si tu ajoutais à tous les éléments de A,B et C de I le plus petit des éléments de A,B et C ? Tu obtiens une nouvelle instance I' …

[tbc92]

Je corrige la dernière phrase de Picodev :
Que se passerait-il si tu ajoutais un nombre a à tous les éléments de A, un nombre b à tous les éléments de B, et le nombre a+b à tous les éléments de C ?

[Ja Rasta]

Merci à vous les amis.

Bonne soirée.