Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#4 11-01-2014 10:14:39
- totomm
- Membre
- Inscription : 25-08-2011
- Messages : 1 093
Re : Arithmétique espagnole
Bonjour,
C'est l'ordinateur qui est rapide...
Je n'ai fait que programmer (rapidement) ce que certains seraient tentés de considérer dédaigneusement comme "force brute"
En ignorant que générer toutes les permutations est déjà un exercice de bonne réflexion..
A+ : totomm
Hors ligne
#5 14-01-2014 16:10:04
- miq
- Membre
- Inscription : 08-01-2014
- Messages : 24
Re : Arithmétique espagnole
En supposant que ces chiffres soient différents, on peut déjà déduire: (% est le modulo et \ la division entière)
[tex]C=0[/tex] n'apparaîtrait pas en premier chiffre du nombre et [tex]C>=2[/tex] donnerait une retenue et un chiffre supplémentaire à la somme donc [tex]\bf{C=1}[/tex]
[tex]E=(5⋅U)\%10+(5⋅A)\backslash 10[/tex] (colonne UE) et [tex]E=(5⋅O)\%10[/tex] (colonne OE) soit [tex](5⋅U)\%10+(5⋅A)\backslash 10=(5⋅O)\%10[/tex]
or dans cette équation les termes modulo donnent comme composante +0 ou +5 et le terme division entière donne une composante comprise entre +0 et +4 inclus. Du non chevauchement de ces deux composantes, on peut déduire que [tex](5⋅A)\backslash 10=0[/tex].
Puis que [tex]A\in [0, 1][/tex] et comme on a déjà le 1 que [tex]\bf{A=0}[/tex].
Il reste que [tex]E=(5⋅O)\%10[/tex] donc [tex]E\in[0,5][/tex] et comme on a déjà le 0 que [tex]\bf{E=5}[/tex].
Pour essayer d'automatiser ces derniers calculs, observons [tex]A, I\text{ et }E[/tex]. On déduit assez vite que :
-[tex]A\text{ est pair ssi }I<5[/tex]
-[tex]E=x\text{ ssi }A\in[2x,2x+1][/tex]
on peut utiliser ces deux relations de proche en proche sur chaque colonne pour déterminer les dénombrements successifs.
On récapitule ce qu'on sait déjà ! [tex][C=1, A=0, E=5][/tex]
[tex]E=5[/tex] donc [tex]O\text{ est impair}[/tex] et on a déjà 1 et 5 donc [tex]\bf{O\in[3,7,9]}[/tex].
[tex]O=3[/tex] donne [tex]T\in[1,6][/tex], [tex]O=7[/tex] donne [tex]T\in[3,8][/tex] et [tex]O=9[/tex] donne [tex]T\in[4,9][/tex].
On a déjà 1 et 9(par O) il reste donc [tex]T\in[3,4,6,8][/tex]
D'autre part, [tex]A=0[/tex] donc [tex]I<5[/tex] et on a déjà 0 et 1 donc [tex]\bf{I\in[2,3,4]}[/tex].
[tex]I=2[/tex] donne [tex]T\in[4,5][/tex], [tex]I=3[/tex] donne [tex]T\in[6,7][/tex] et [tex]I=4[/tex] donne [tex]T\in[8,9][/tex].
On a déjà 5 il reste donc [tex]T\in[4,6,7,8,9][/tex].
Le mix de ces 2 listes montre que [tex]\bf{T\in[4,8]}[/tex] (et les secondes lignes des 2 blocs précédents en donnent les [tex]I\text{ et }O[/tex] respectifs.)
On a donc plus que 2 cas de [tex]T[/tex] à tester pour 4 variables restantes [tex][U,R,V,N][/tex].
Si [tex]T=4[/tex], en récapitulant: [tex]C=1, A=0, E=5, T=4, O=9, I=2[/tex] et il nous manque [tex][3,6,7,8][/tex]
[tex]T\text{ est pair}[/tex] donc [tex]N<5[/tex], d'où [tex]N=3[/tex], donc [tex]R\in[6,7][/tex], mais [tex]R=7[/tex] ne colle pas avec [tex]T=4[/tex] donc il nous reste une seule solution [tex]N=3\text{ et }R=6[/tex].
[tex]C=1[/tex] donc [tex]V(>5)\in[7,8][/tex], mais [tex]V=7[/tex] implique [tex]U\in[4,5][/tex] qu'on a déjà et [tex]V=8[/tex] implique [tex]U\in[6,7][/tex]. On a déjà 6 donc seul [tex]U=7[/tex] est encode possible.
On a donc une solution : [tex]\bf{N=3, R=6, V=8, U=7}[/tex]
Si [tex]T=8[/tex], en récapitulant: [tex]C=1, A=0, E=5, T=8, O=7, I=4[/tex] et il nous manque [tex][2,3,6,9][/tex]
[tex]T\text{ est pair}[/tex] donc [tex]N<5[/tex], d'où [tex]N\in[2,3][/tex]. Si [tex]N=2[/tex] alors [tex]R\in[4,5][/tex]qu'on a déjà. Sinon si [tex]N=3[/tex] alors [tex]R\in[6,7][/tex] avec 7 qu'on a déjà, donc il nous reste à nouveau une seule solution [tex]N=3\text{ et }R=6[/tex].
[tex]C=1[/tex] donc [tex]V(>5)=9[/tex] donc [tex]U\in[4,5][/tex] qu'on a déjà.
Donc l'hypothèse [tex]T=8[/tex] est fausse.
En résumé, la réponse est [tex]170469*5=852345[/tex], et elle est unique.
Je n'ai fait que 6 dénombrements de profondeur max 2 et de largeur max 5. Même si la force brute résous le calcul rapidement, je préfère l'élégance de quelques remarques judicieuses. ;)
Dernière modification par miq (14-01-2014 16:12:49)
Hors ligne
#6 27-04-2014 22:07:04
- totomm
- Membre
- Inscription : 25-08-2011
- Messages : 1 093
Re : Arithmétique espagnole
Bonsoir,
Même si la force brute résous le calcul rapidement, je préfère l'élégance de quelques remarques judicieuses. ;)
Comment ne pas être d'accord ! Mais quand on doit dénombrer entre de multiples possibilités, il y a aussi une certaine "élégance" à domestiquer la force brute "sous programmation".
pipo m'a demandé aimablement par mail de lui communiquer le code que j'avais écrit : j'avais programmé en Visual Basic 2010 mode console, et je n'ai pas conservé ce programme très simple dans son principe.
Soit un tableau (ou une liste) initialisé avec C U A T R O V E I N, et en correspondance les 10 chiffres 1234567890
qui permettent de créer les 2 nombres correspondant à CUATRO et VEINTE
Il suffit de "générer des permutations successives" jusqu'à obtenir l'égalité entre les nombres 5xCUATRO et VEINTE
Un algorithme en Python pour Générer successivement toutes les permutations à partir d'une première d'entre elles peut être trouvé en http://tolokoban.org/Articles/EnumPerm/index.html
Je laisse pipo travailler.... A+
Hors ligne