Inscription / Connexion Nouveau Sujet
Niveau exercices
Partager :

Des multiples

Posté par
Sylvieg Moderateur
05-06-20 à 15:39

Bonjour,
Cet exercice est inspiré de Arithmétique
Le cas 1234567 y est traité.

Je propose d'autres cas :
1) 123456789.
C'est-à-dire : Parmi les 9! entiers qu'on peut écrire avec les chiffres 1, 2, 3, 4, 5, 6, 7, 8 et 9, chacun utilisé une seule fois, peut-on en trouver deux tels que l'un soit un multiple de l'autre ?
2) Et avec 12345678 ?
3) Et avec 123456 ?

Posté par
derny
re : Des multiples 05-06-20 à 18:27

Bonsoir
Sans faire d'arithmétique un programme informatique devrait venir à bout de 123456.
Pour les autres, vu le nombre de cas à examiner à voir.

Posté par
weierstrass
re : Des multiples 06-06-20 à 00:30

Vite fait...

 Cliquez pour afficher

Posté par
Sylvieg Moderateur
re : Des multiples 06-06-20 à 08:42

Bonjour,
@weierstrass,

 Cliquez pour afficher

Posté par
dpi
re : Des multiples 06-06-20 à 08:59

Bon week-end
Merci pour cet exercice fastidieux

 Cliquez pour afficher

Posté par
dpi
re : Des multiples 07-06-20 à 19:17

Bonsoir,
Pour 12345678
il y a beaucoup de solutions    :

 Cliquez pour afficher
                                                            

Posté par
LittleFox
re : Des multiples 11-06-20 à 18:02


Une astuce souvent utile quand on parle de permutation ou de sommation des chiffres d'un nombre est que ces deux opérations conservent la classe modulo 9.

Ainsi, les nombres 123, 231 et 12+3 = 15 font tous partie de la classe  de résidu 6 modulo 9.

Les résidus modulo 9 pour les nombres composés des chiffres de 1 à n sont :

n       1   2   3   4   5   6   7   8   9
classe  1   3   6   1   6   3   1   0   0


Comme le plus grand nombre avec n chiffres est plus petit que n fois le petit de ces nombre, les multiplicateurs vont de 2 à n-1.
Comme le multiplicateur fois le résidu doit être égal au résidu, ça nous laisse comme multiplicateurs:

n   multiplicateur
1   {}
2   {}
3   {}
4   {}
5   {4}
6   {4}
7   {}
8   {2,3,4,5,6,7}
9   {2,3,4,5,6,7,8}

Donc, il n'y a aucune solution pour n = 1,2,3,4 ou 7.
Pour n = 5 ou 6, s'il y a une solution, le multiplicateur est 4.
Pour n = 8 ou 9,  les n-2 multiplicateurs sont possibles.

Ensuite, nous pouvons passer à la programmation, il y a dans le pire cas moins de  7*9! = 2 540 160 tests à faire. C'est tout à fait gérable par un ordinateur

Posté par
LittleFox
re : Des multiples 11-06-20 à 18:22


Un programme très simple comme celui-ci (python):

 Cliquez pour afficher


Montre qu'il n'y a en fait aucune solution pour n = 5 ou 6. Qu'il y a 2338 solutions pour n=8. Et 24609 solutions pour n=9. Le tout en moins d'une seconde.

Seule petite astuce, je parcours les nombres dans l'ordre décroissant de sorte que si un multiple est valide, je l'ai déjà rencontré avant. C'est un tout petit peu plus rapide que vérifier que le multiple contient tous les chiffres une et une seule fois.

Posté par
LittleFox
re : Des multiples 11-06-20 à 18:34


En hexadécimal on a 123456789ABCDEFx2 = 2468ACF13579BDE.

Trouvez une solution avec les chiffres 123456789ABCDE

Posté par
weierstrass
re : Des multiples 11-06-20 à 18:39

Pas mal LittleFox, mais moi et Sylvieg, on l'a fait à la main (et c'est pas si long...)

Posté par
Sylvieg Moderateur
re : Des multiples 11-06-20 à 19:10

Posté par
dpi
re : Des multiples 12-06-20 à 07:27

Je savais bien que Littlefox ferait le tour de la question.
Comme weierstrass ,j'ai cherché à la main "assisté" par Excel

Posté par
LittleFox
re : Des multiples 12-06-20 à 20:08


Tu as beaucoup insisté dpi

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !