Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 13-11-2015 10:40:06

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2954

Nombrs récalcitrants

Bonjour à tous.
Un nombre n est dit récalcitrant à un nombre m s'il n'est pas divisible par m et si ça reste vrai même si on change la valeur d'un seul chiffre de n.

Pour les nombres de 3 chiffres récalcitrants à 13 (on parle de vrais nombres à 3 chiffres, mais on peut changer le chiffre des centaines à 0 dans le test de divisibilité. Par exemple si 131 est déclaré récalcitrant, ça implique entre autre que 031 n'est pas divisible par 13):
Pouvez vous donner une valeur max du nombre de ces nombres, avant même de les chercher ?
Si vous ne disposez par d'informatique, comment vous y prendrez vous pour trouver ces nombres ?

Bon amusement



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 13-11-2015 20:02:09

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3319

Nombres réaclcitrants

Donc on cherche tous les nombres de trois chiffres récalcitrants à 13.

On peut déjà faire une grosse majoration du nombre de ces nombres.
E_(1000/13)=76 et entre 100 et 999 il y a 900 nombres il y a donc au maximum 900-76=824 nombres de ce genre.

Ensuite il faut chercher le la valeur minimale que prend se maximum donc la borne supérieure. Ca n'a pas l'air très compliqué mais pour le moment à par la méthode bourrin j'ai pas trop d'idée. Je reviendrai donc!

shadock

EDIT: E_(x) désigne la partie entière par valeur inférieure de x.


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #3 - 13-11-2015 20:08:30

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2954

Nombres réaclcitrants

@shadock: le nombre max de récalcitrants de 3 chiffres à 13 peut être beaucoup plus bas que ce que tu avances. Il est vrai que déja cette première question oblige à bien avancer dans le problème !

Bon courage

 #4 - 13-11-2015 21:49:25

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3319

Nombres récalcitrrants

Ah oui je me doute bien, c'était un maximum, j'ai pas dit que c'était le plus petit smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #5 - 14-11-2015 12:18:06

godisdead
Expert de Prise2Tete
Enigmes résolues : 22
Messages : 639

Nombres récalcitraants

de 0 à 1000, il y a 76 multiples de 13.
pour un nombre ABC, les binômes AB, AC et BC sont tous différents pour les 76 premiers multiples.
Un nombre récalcitrant ne peut pas être de la forme XBC si BC fait parti des 76 binômes. (idem pour AXC et ABX)
Donc la liste des nombre récalcitrants est l'union des 24 paires restantes pour AB/AC et BC ... Et là, ça dépasse mes compétences smile

 #6 - 14-11-2015 12:33:15

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,472E+3

Nombres récalcitrantss

Vu que les modulos des unités, des dizaines et des centaines sont tous différents pour 13,

On a à peine 3 nombres sur 12 pour les centaines, et 4 / 13 pour les dizaines et unités qui peuvent l'être sur un total de 900 nombres.

3/12 x 4/13 x 4/13  x 900  = 21, ...

On a donc au plus 21 nombres qui conviennent. Et c'est à la louche .

Avec tableur , je tombe sur 15.

 #7 - 14-11-2015 17:29:40

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2954

Nombres ércalcitrants

@Godisdead: comment es tu arrivé au 24 ?
@Gwen: pas compris ta démarche, peux tu développer ?
Sinon, il n'y a pas 15 récalcitrants, enfin c'est peut être parce que tu n'as pas lu une précision de l'énoncé qui est arrivée tardivement.

@tous: Pour trouver les récalcitrants, il suffit de lister les nombres de 100 à 999 et d'ôter:
-les nombres qui finissent par ..13,..26,..39,...
-les nombres dont le 1er et le dernier chiffre sont 1..4 (à cause du 104) 1..7, etc..
-les nombres dont le 1er et 2ème chiffre sont 10.., 11.., à cause des 104 et 117, ...

Mais on peut faire plus court avec une autre méthode, qui marche aussi pour les nombres à 4 chiffres et plus.

 #8 - 14-11-2015 17:47:28

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,472E+3

nomvres récalcitrants

J'avais zappé le "0 à la place des centaines" :

Il en reste donc 11 :
309
383
470
514
561
605
648
692
779
901
957

 #9 - 14-11-2015 18:43:42

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2954

Nombres récalcitraants

Oui Gwen, je suis d'accord.
Pour les retrouver sans avoir besoin de procéder par élimination, il faut s'intéresser aux nombres modulo 13 qui ne peuvent pas être atteints par les chiffres décimaux.

 #10 - 14-11-2015 19:40:24

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 682

Nombres récalcitrannts

On liste les 76 multiples de 13 inférieurs à 999.
On écrit la liste des entiers de 100 à 999.
On élimine les entiers qui donnent 13 après une modification d'un chiffre.
On élimine les entiers qui donnent 26 après une modification d'un chiffre.
On élimine les entiers qui donnent 39 après une modification d'un chiffre.
etc
On élimine les entiers qui donnent 988 après une modification d'un chiffre.

On obtient ainsi 11 entiers à 3 chiffres récalcitrants à 13, à savoir

[309, 383, 470, 514, 561, 605, 648, 692, 779, 901, 957]

Voilà !

 #11 - 14-11-2015 22:44:58

portugal
Professionnel de Prise2Tete
Enigmes résolues : 22
Messages : 374

Nombres récalcitrrants

En approximation pour un nombre de n chiffres,n'a on pas ce nombre environ égal à 4/13 puissance n ?

 #12 - 15-11-2015 07:37:24

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2954

nombres récakcitrants

Oui masab, c'est bon, c'est l'application de mon message 7. Saurais tu retrouver ces nombres sans procéder par ces éliminations ?

@Portugal: c'est un peu la même idée que Gwen, j'avoue que je ne la comprends pas vraiment. Peux tu développer ?

 #13 - 15-11-2015 12:54:48

portugal
Professionnel de Prise2Tete
Enigmes résolues : 22
Messages : 374

Nombers récalcitrants

Je vais essayer demain matin d’écrire mes idées mais j'ai des problèmes d'accès PC ces jours ci et pas facile d’écrire sur mon téléphone...

au fait il y avait un typo dans mon message précédent. c'est bien sur 3/13 et non pas 4/13 à la puissance n auquel je pense.

Si tu peux prolonger de 2/3 jours ça serait sympa et permettrait d'affiner les réponses

 #14 - 15-11-2015 13:14:07

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2954

nombres récamcitrants

Entendu Portugal, car ce n'est pas simple ce petit problème...tant qu'on n'a pas vu la solution.

 #15 - 16-11-2015 12:46:40

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2954

nombres récalcitranys

Un indice.
Avec un nombre récalcitrant, la somme de 2 des chiffres ne peut être complétée par le 3ème pour faire un zéro modulo 13. Sachez qu'avec les chiffres de la base 10, 3 chiffres de la base 13 ne sont pas accessibles.

 #16 - 16-11-2015 22:11:30

portugal
Professionnel de Prise2Tete
Enigmes résolues : 22
Messages : 374

nombres récalcirrants

L'indice est pile mon point de départ. Les "cycles" que décrivent, avec des pas de 1,10 et 100, les 10 premiers nombres consécutifs laissent 3 nombres "de cotés"

d'où le 3/13 impossibles par chiffre et le (3/13)^13 de mon post précédent

Mon idée pour passer à une démonstration plus rigoureuse consiste à décomposer abc en 100*a + 10*b + c et en disant que le modulo de la somme est égale à la somme des modulos pour passer d'une démo "probabiliste approximative" à une démonstration en dénombrement plus précise.

C'est la bonne voie ou il y a plus rapide et directe ?

 #17 - 17-11-2015 07:08:59

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2954

nombres récalcirrants

C'est en effet la bonne voie, Portugal. Ton approximation est d'ailleurs, après calcul exact, assez impressionnante...

 #18 - 17-11-2015 19:00:42

portugal
Professionnel de Prise2Tete
Enigmes résolues : 22
Messages : 374

nombres técalcitrants

j'ai du mal...
Voici pour le plaisir les cycles pour montrer que le caractère cyclique continue pour des nombres de 4, 5, 6..chiffres, condition pour que le "(3/13)^n reste valide"

La méthode ne prend pas en compte les effets de bord ainsi que les "faux nombre à n chiffres".

On vérifie par récurrence que pour tout n la série reste cyclique car :

10^7 * 1/13 = 769230 + 1/13 et les restes par la division par 13 sont donc les même, l'hypothèse de récurrence étant vraie pour les 6 premiers rangs (voir plus bas), elle l'est pour tout n.

Pour l’anecdote, j'ai l'impression que pour tout "pas" non multiple de 13, les reste dans la division par 13 respectent ce même cycle...

Je vais essayer de répondre pour de bon à ton problème... mais c'est pas facile de passer de l'idée au calcul...

n      1        2        3        4        5        6        7        8        9        10        11        12   
1        1        2        3        4        5        6        7        8        9        10        11        12   
2        10        7        4        1        11        8        5        2        12        9        6        3   
3        9        5        1        10        6        2        11        7        3        12        8        4   
4        12        11        10        9        8        7        6        5        4        3        2        1   
5        3        6        9        12        2        5        8        11        1        4        7        10   
6        4        8        12        3        7        11        2        6        10        1        5        9   
7        1        2        3        4        5        6        7        8        9        10        11        12

 #19 - 17-11-2015 19:20:34

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2954

Nombres récalcitrantts

@Portugal: pour trouver les nombres récalcitrants, je me sers du tableau de ton dernier message. Oui mais voilà, comment s'en servir ?

Indice: Il faut poser un système d'équations simples.

 #20 - 17-11-2015 19:22:52

portugal
Professionnel de Prise2Tete
Enigmes résolues : 22
Messages : 374

Nombres rcéalcitrants

J'ai un peu de temps libre en fin de matinée demain...on va voir si je trouve..

 #21 - 17-11-2015 19:35:43

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 682

Nombres récalcitrannts

Soit un nombre n de 3 chiffres.
On l'écrit sous la forme
[TeX]n = 100\,a+10\,b+c[/TeX]
avec a,b,c chiffres, a non nul.
On a modulo 13
[TeX]n \equiv 9\,a+10\,b+c \mod 13[/TeX]
n est récalcitrant s'il vérifie les 3 conditions suivantes :
1) il n'existe pas de chiffre u tel que [latex]9\,u+10\,b+c\equiv 0\mod 13[/latex] ;
2) il n'existe pas de chiffre v tel que [latex]9\,a+10\,v+c\equiv 0\mod 13[/latex] ;
3) il n'existe pas de chiffre w tel que [latex]9\,a+10\,b+w\equiv 0\mod 13[/latex].

En multipliant 1) par 3 et 2) par 4 on obtient les conditions équivalentes :
1') il n'existe pas de chiffre u tel que [latex]u\equiv 9\,b-3\,c\mod 13[/latex] ;
2') il n'existe pas de chiffre v tel que [latex]v\equiv 3\,a-4\,c\mod 13[/latex] ;
3') il n'existe pas de chiffre w tel que [latex]w\equiv 4\,a+3\,b\mod 13[/latex].
Cela montre que si u ou v ou w existent, ils sont donnés par l'expression précédente avec u,v,w compris entre 0 et 12.

Conclusion : n est récalcitrant si et seulement si les valeurs de u, v et w fournies par 1') 2') 3') sont parmi 10, 11, 12.

Choisissons pour u, v, w des valeurs parmi 10, 11, 12. Alors les 3 équations 1') 2') 3') forment un système linéaire d'inconnues a,b,c. En résolvant le système en fonction de u,v,w, on obtient l'unique solution modulo 13 :
[TeX]a \equiv 7\,u-2\,v+5\,w \mod 13[/TeX]
[TeX]b \equiv 8\,u+7\,v-2\,w \mod 13[/TeX]
[TeX]c \equiv 2\,u-5\,v+7\,w \mod 13[/TeX]
On obtiendra un entier récalcitrant chaque fois que a, b et c seront parmi 0,1,...,9.

Finalement on obtient le tableau suivant

Code:

[ u,  v,  w]   [a, b, c]   n

[10, 10, 10]   [9, 0, 1]   901
[10, 10, 11]   [1, 11, 8]   
[10, 10, 12]   [6, 9, 2]   692
[10, 11, 10]   [7, 7, 9]   779
[10, 11, 11]   [12, 5, 3]   
[10, 11, 12]   [4, 3, 10]   
[10, 12, 10]   [5, 1, 4]   514
[10, 12, 11]   [10, 12, 11]   
[10, 12, 12]   [2, 10, 5]   
[11, 10, 10]   [3, 8, 3]   383
[11, 10, 11]   [8, 6, 10]   
[11, 10, 12]   [0, 4, 4]   
[11, 11, 10]   [1, 2, 11]   
[11, 11, 11]   [6, 0, 5]   605
[11, 11, 12]   [11, 11, 12]   
[11, 12, 10]   [12, 9, 6]   
[11, 12, 11]   [4, 7, 0]   470
[11, 12, 12]   [9, 5, 7]   957
[12, 10, 10]   [10, 3, 5]   
[12, 10, 11]   [2, 1, 12]   
[12, 10, 12]   [7, 12, 6]   
[12, 11, 10]   [8, 10, 0]   
[12, 11, 11]   [0, 8, 7]   
[12, 11, 12]   [5, 6, 1]   561
[12, 12, 10]   [6, 4, 8]   648
[12, 12, 11]   [11, 2, 2]   
[12, 12, 12]   [3, 0, 9]   309

On retrouve bien nos 11 entiers récalcitrants à 3 chiffres !

 #22 - 17-11-2015 19:56:56

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2954

nimbres récalcitrants

C'est ça Masab, bravo !
J'ai une variante un poil plus simple, mais qui ne se prête pas à l'informatisation.
Bravo encore.

 #23 - 18-11-2015 02:16:14

portugal
Professionnel de Prise2Tete
Enigmes résolues : 22
Messages : 374

nombres révalcitrants

J'ai un début mais pas j'ai l'impression que c'est beaucoup plus lourd qu'utile et sous réserves d'erreurs de calcul...Bonne piste ?

Notre tableau d'impossibilités :
         10      11      12
1        10      11      12
10        9        6       3
100       12      8       4

abc  [13] = 100a [13] + 10b [13] + c [13]

c ne peut pas prendre les valeurs 10,11,12 [13]
Donc si 100a [13]+ 10b [13]<> 1,2,3, on pourra trouver c assurant la divisibilité par 13.  On trouve donx les conditions :

100a [13] + 10b [13] = 3   --> (1,2) et (2,1) (3,0)  solutions de (100a [13], 10b [13] )
100a [13] + 10b [13] = 16   --> (9,7)
100a [13] + 10b [13] = 2  --> (2,0), (1,1)
100a [13] + 10b [13] = 15  --> (7,8)
100a [13] + 10b [13] = 1  --> (1,0)
100a [13] + 10b [13] = 14  --> (9,5) ,(7,7), (6,8)

On a donc un maximum de 11 couples (a,b) possibles pour que abc puisse être récalcitrant.

On pourrait alors recommencer sur les couples (a,c) et (b,c) et croiser les résultats pour conclure ?

 #24 - 18-11-2015 08:26:43

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2954

bombres récalcitrants

@Portugal: ce n'est ni tout à fait ma solution, ni tout à fait celle de Masab, mais pourquoi pas ?
Peux tu donner au moins un nombre récalcitrant pour valider  ton raisonnement ?

 #25 - 18-11-2015 16:37:11

portugal
Professionnel de Prise2Tete
Enigmes résolues : 22
Messages : 374

Nombres récalciitrants

Bon je n'ai pas fait dans la finesse...

J'ai appliqué la méthode décrite précédemment (mail il y a avait des oublis pour former le tableau suivant  des couples possibles pour que le nombre soit récalcitrant

isolé    val    manq    100a    10b    c
c    12    1    1    0    
c    11    2    1    1    
c    10    3    1    2    
b    9    4    1         3
b    6    7    1         6
b    3    10    1         9
c    11    2    2    0    
c    10    3    2    1    
c    12    14    2    12    
b    9    4    2         2
b    6    7    2         5
b    3    10    2         8
c    10    3    3    0    
c    12    14    3    11    
c    11    15    3    12    
b    9    4    3         1
b    6    7    3         4
b    3    10    3         7
c    11    15    5    10    
c    10    16    5    11    
b    6    7    5         2
b    3    10    5         5
c    12    14    6    8    
c    10    16    6    10    
b    6    7    6         1
b    3    10    6         4
c    12    14    7    7    
c    11    15    7    8    
b    6    7    7         0
b    3    10    7         3
c    12    14    9    5    
c    10    16    9    7    
b    3    10    9         1
b    9    17    9         8
c    12    14    10    4    
c    11    15    10    5    
b    3    10    10         0
b    9    17    10         7
c    11    15    11    4    
c    10    16    11    5    
b    9    17    11         6
b    6    20    11         9
a    12    1         0    1
a    8    5         0    5
a    4    9         0    9
a    12    1         1    0
a    8    5         1    4
a    4    9         1    8
a    8    5         2    3
a    4    9         2    7
a    8    5         4    1
a    4    9         4    5
a    8    5         5    0
a    4    9         5    4
a    12    14         5    9
a    4    9         7    2
a    12    14         7    7
a    4    9         8    1
a    12    14         8    6
a    12    14         10    4
a    8    18         10    8
a    12    14         11    3
a    8    18         11    7
a    12    14         12    2
a    8    18         12    6


Pour qu'un nombre soit récalcitrant il faut donc trouver les triplets (1100a, 10b, c) dont les 3 combinaisons sont toujours différentes de 0

J'ai trouvé les suivant mais je pense que j'en ai raté un (première colonne les valeur des chiffre * 1,10,100  modulo 13, la deuxième étant  le nombre en système décimal.

109    309
123    389
205    605
218    648
301    901
3 11 7    957
6 8 1     561
6 10 4    514
10 5 0    470
11 5 9     779

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Riri, Fifi et ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete