A630. Ensembles additivement séparés Imprimer
A6. Partages et partitions

calculator_edit.png  

Problème proposé par Michel Lafond
Un ensemble E d’entiers naturels de cardinal N est dit additivement séparé si les 2N parties de E ont des sommes distinctes deux à deux.
Ainsi E = {1, 2, 4, 8} est additivement séparé car ses 16 parties ont pour sommes les entiers de 0 à 15.
Mais E’ = {3, 5, 6, 7} est aussi additivement séparé car ses 16 parties ont pour sommes distinctes:
0, 3, 5, 6, 7,
3 + 5 = 8, 3 + 6 = 9,  3 + 7 = 10, 5 + 6 = 11,  5 + 7 = 12,  6 + 7 = 13,
3 + 5 + 6  = 14, 3 + 5 + 7  = 15, 3 + 6 + 7  = 16, 5 + 6 + 7  = 18
et  3 + 5 + 6 + 7   = 21,
De plus MAX (E’) = 7 est plus petit que MAX (E) = 8.
Trouver pour chaque k appartenant à {2,3,4,5,6,7,8,9,10} un ensemble Ek ayant k éléments et avec MAX (Ek ) minimal.

 Solution


pdfDaniel Collignon et pdfMichel Lafond ont résolu le probème.

A noter que ce problème a été posé pour la première fois par P. Erdös en 1969 et a fait l'objet de la part de nombreux auteurs: J.H. Conway, Richard Guy, Tom Bohman et alii d'analyses diverses sous le titre: "Sets of integers whose subsets have distinct sums"
On peut consulter avec intérêt l'article de pdfTom Bohman intitulé "A sum packing problem of Erdös and the Conway-Guy sequence"


Tous les nombres ci-après sont des nombres entiers positifs qui ne commencent jamais par 0.

Q1 : ab57 est un nombre de quatre chiffres divisible par 23.

Quel entier s'écrit ab ?

Q2 : abc205 est un nombre de six chiffres divisible par 139.

Quels entiers s'écrivent ab ?

Q3 : abcde37 est un nombre de sept chiffres divisible par 13.

Quel est le plus petit entier qui s'écrit abcde37 ?

Q4 : abc314 est un nombre de six chiffres divisible par 48.

Quel entier s'écrit abc ?

Qâ‚… : abcd9e41f  est un nombre de neuf chiffres divisible par 831168.
Quels sont les chiffres a,b,c,d,e et f?

Nota:comme les cinq questions se résolvent trivialement avec un automate,seul un traitement manuel mérite d'être pris en considération.