Des multiples

 Niveau exercicesPartager :
			        
					
				
Des multiples
Posté par 
Sylvieg   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 
dernyre : 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 
weierstrassre : Des multiples  06-06-20 à 00:30
Vite fait...

 Cliquez pour afficher
123456789*2 = 246913578

12345687*5 = 61728435

Pour 123456, en m'inspirant de la technique du poste, on est sous la forme 9n+3, le multiplicateur ne peut donc qu'être 4 ou 7. 7 est éliminé. Reste 4. On voit rapidement que le diviseur doit commencer par 13 et ne pas terminer par 5. Ca ne laisse pas beaucoup de possibilité, j'ai pas mal tâtonné, à voir....

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

@weierstrass,

 Cliquez pour afficher
J'avais trouvé les mêmes pour 1) et 2) 

Pour 3), un petit plus : Ni 5 ni 2 en dernier.

Il ne reste plus grand chose à vérifier.
 Posté par 
dpire : Des multiples  06-06-20 à 08:59
Bon week-end

Merci pour cet exercice fastidieux 



 Cliquez pour afficher
Pour les 6 chiffres: aucune solution ,la plus proche est 32164 x2 =643218  et non 643215
 Posté par 
dpire : Des multiples  07-06-20 à 19:17
Bonsoir,

Pour 12345678

il y a beaucoup de solutions    :

 Cliquez pour afficher
Par exemple  12356784 x2=24716568 

                              23187564 x2 =46375128

                              12374856x3=37124568

                              21584376x3=64753128

                              13428567x4=53714268

                              21785634x4=87142536

                              12345687x5=61728435

                              17528643x5=87643215

                              12385476x6=74312856

                              14587236x6=87523416

 Posté par 
LittleFoxre : 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 
LittleFoxre : Des multiples  11-06-20 à 18:22


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



 Cliquez pour afficher
from itertools import permutations


def main():
    n = 8

    r = 5*n*(n+1) % 9
    ms = list(m for m in range(2, n) if r*m % 9 == r)

    seen = set()
    for digits in permutations(reversed(range(1, n+1))):
        n = 0
        for d in digits:
            n *= 10
            n += d

        for m in ms:
            if n*m in seen:
                print(n, m, n*m)
        seen.add(n)


if __name__ == "__main__":
    main()


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 
LittleFoxre : Des multiples  11-06-20 à 18:34


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



Trouvez une solution avec les chiffres 123456789ABCDE 
 Posté par 
weierstrassre : 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 re : Des multiples  11-06-20 à 19:10
 Posté par 
dpire : 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 
LittleFoxre : Des multiples  12-06-20 à 20:08


Tu as beaucoup insisté dpi 