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 - 07-03-2015 12:12:39

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

les isoléd et les groupés

Bonjour à tous,
A partir de quel entier peut on dénombrer moins d'isolés que de groupés ?
Un isolé est un chiffre qui apparait une seule fois dans un nombre. Un seul chiffre isolé dans un nombre suffit à classer ce nombre dans la catégorie des isolés.
Exemples: 7779 est un isolé. 4545 est un groupé.

Bon amusement

PS: Je me suis contenté de donner le nombre de chiffres que contient ce nombre, ayant fait ce calcul à la main. Les informaticiens pourront sans doute affiner le résultat.

  • |
  • Répondre

#0 Pub

 #2 - 07-03-2015 13:13:43

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

les isolés ey les groupés

Quel est le sens de ta question ?
Le nombre d'isolés (ou de groupés) supérieurs à un nombre donné est infini.

 #3 - 07-03-2015 14:15:35

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

les isolés zt les groupés

Petite précision suite à la remarque de Titoufred: En regardant les petits nombres, il est évident que les isolés sont les plus nombreux. En revanche, la tendance va s'inverser pour les grands nombres. En triant les isolés/groupés 1 par 1 depuis 0, il y aura bien 1 nombre pour lequel il y aura égalité. c'est ce nombre qui est demandé.
J'espère que c'est plus clair maintenant.

 #4 - 07-03-2015 15:02:38

ckronikks
Habitué de Prise2Tete
Enigmes résolues : 7
Messages : 12

Les isolés et les groups

En ne travaillant que sur les entiers naturels positifs je trouve que l'entier a partir duquel on trouve plus de groupés que d'isolés est composé de 5 chiffres

 #5 - 08-03-2015 09:23:30

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

les isilés et les groupés

Ckronikks, je ne crois pas. Je pense que tu n'as pas bien saisi l'énoncé. Je redonne des exemples d'isolés et de groupés:
13225 est un isolé (1,3 et 5 isolés)
13333 isolé (1 isolé)
13133 groupé (pas de chiffres isolés, 1 est présent 2 fois, 3 est présent 3 fois).

Pour te persuader que pour les nombres à 5 chiffres les isolés sont largement majoritaires:
15678 nombre pris au hasard: isolé.
Le 1er groupé suivant sera 16116. Soit une série de plus de 400 nombres isolés pour un groupé !
Et ce n'est pas un cas...isolé.

 #6 - 08-03-2015 09:31:10

ckronikks
Habitué de Prise2Tete
Enigmes résolues : 7
Messages : 12

Les isolés et les groupé

Ah oui effectivement je n'avais pas compris l'énoncé du tout pour moi un isolé  ne comportait que des chiffres différents ex:1234 ou 47653. Alors qu'un groupé contient au moins 2chiffres identiques ex: 22345 ou 19737 ou 22. Merci de m'avoir replacé sur la bonne route :p

 #7 - 09-03-2015 16:27:16

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

les isolés et les hroupés

Bonjour,
La première idée est de faire un calcul exhaustif en partant de zéro. On peut ne traiter qu'environ 1/9ème des nombres en remarquant que la proportion d'isolés et de groupés dans une séquence du genre 1000->1999 est identique à celle de la séquence 1000->9999.
Le calcul montre que de 0 à 10^11, la proportion de groupés n'est que de 0.00826, et qu'on n'est pas sorti de l'auberge.

J'ai ensuite procédé par simulation, en générant des nombres aléatoires de 50 chiffres (pour chaque nombre, le 1er chiffre est pris égal à 1, les autres sont tirés au hasard successivement).
Pour chaque grand nombre, je calcule la proportion de groupés dans les k premiers chiffres de ce nombre, ce qui me donne 50 valeurs. j'ai généré 10^6 grans nombres, et ai obtenu 50 moyennes (pour k variant de 1 à 50).

Je trouve que la proportion de groupés passe au-dessus de 50% pour les nombres de 41 chiffres. En affinant un peu, je dirais que 5*10^40 doit être une approximation raisonnable.

 #8 - 09-03-2015 17:01:16

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

les isolés zt les groupés

Bravo Enigmatus. Je constate que, même avec l'usage de l'informatique, la résolution n'est pas simple, et qu'il t'a fallu ruser. Je me doutais bien qu'un résultat à l'entier près n'était pas à la portée des ordinateurs ordinaires. Ton résultat confirme mon calcul (avec la bonne formule, une calculette et une minute suffisent).
C'est un problème de dénombrement assez classique, mais pas des plus simples...

 #9 - 10-03-2015 11:53:05

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

Les isolés et les grouupés

Je n'ai pas trouvé de formule miracle, mais un algorithme rapide qui calcule de façon exacte (en principe) le nombre  d'isolés parmi les nombres à n chiffres.
Voici les résultats

Code:

Nombres à 40 chiffres
Nombre total  :         9000000000000000000000000000000000000000
Nombre d'isolés :       4714771207916973382037140560106496803560
Nombre de groupés :     4285228792083026617962859439893503196440
Proportion d'isolés :   5.238635E-01
Proportion de groupés : 4.761365E-01 (0.475989 pour la simulation)

Nombres à 41 chiffres
Nombre total  :         90000000000000000000000000000000000000000
Nombre d'isolés :       44374958540727402429889915556882003947569
Nombre de groupés :     45625041459272597570110084443117996052431
Proportion d'isolés :   4.930551E-01
Proportion de groupés : 5.069449E-01 (0.506805 pour la simulation)

Ajouté :
La proportion d'isolés est de 0.5016311 dans les 4*10^40 premiers nombres, et de 0.4999159 dans les 5*10^40 premiers.

 #10 - 13-03-2015 16:31:14

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

les isolés et les grouoés

nodgim #8 a écrit:

Ton résultat confirme mon calcul (avec la bonne formule, une calculette et une minute suffisent).

Si tu as fait un calcul exact, retrouves-tu les valeurs que j'obtiens en #9 pour les nombres à 40 et 41 chiffres ?

 #11 - 13-03-2015 17:15:10

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

kes isolés et les groupés

Bonjour Enigmatus.
Cette enigme n'était pas facile tout de même. De plus, elle fait suite à une série serrée d'énigmes assez ardues. D'où le peu d'engouement suscité, j'imagine un peu de lassitude générale. Une approche informatique ne s'avère pas plus facile, compte tenu de la taille du nombre en jeu....

Comment dénombrer les isolés des groupés sans faire de redondance ?
Dans le cas général, pour un nombre à n chiffres écrits en base b, il y a b^n nombres possibles. Avec un chiffre isolé, il y a:
n*(b-1)^(n-1) nombres.
n est l'emplacement du chiffre isolé. Il ne doit plus apparaitre dans les n-1 autres chiffres, d'où le (b-1)^(n-1).
Comme on peut trouver b isolés, le nombre de solutions est:
b*n*(b-1)^(n-1).
Cependant, dans ce calcul, les paires d'isolés sont comptées 2 fois, il faut les ôter:
-n(n-1)*b(b-1)/2*(b-2)^(n-2).
Ici, on ôte en trop les triplets d'isolés, il faut donc les rajouter:
+n(n-1)(n-2)*b(b-1)(b-2)/6*(b-3)¨(n-3)
Etc...

La formule générale est donc:
S=-(-1)^k*A(n,k)*C(b,k)*(b-k)^(n-k) pour 0<k<b

il reste tout de même à ôter les isolés comptés indûment, ceux qui ont un zéro isolé en 1er chiffre. La formule est construite sur le même principe.
S0= (b-1)^(n-1)+(-1)^k*A(n-1,k)*C(b-1,k)*(b-k-1)^(n-k-1) pour 0<k<b-1.

Le résultat final est donc S-S0

NB: le S0 corrige assez peu le S. On est de l'ordre du 10^-3.
L'approximation du S est déja bonne pour les 4 premières sommes.

Enigmatus, je n'ai pas de grosse machine de calcul, peut être pourras tu vérifier le nombre exact avec 40 et 41 chiffres ?

 #12 - 13-03-2015 18:45:59

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

Les isolés et les groués

@nodgim #11
Je suppose que S et S0 sont des sommations pour respectivement 0<k<b, et 0<k<b-1.

Voici nos résultats pour b=10 et n variant de 1 à 3 :

Code:

enigmatus

Nombres à 1 chiffres + nombres de 1 à 1 chiffres
Nombre total  :          10   10
Nombre d'isolés :        10   10
Nombre de groupés :       0    0
Proportion d'isolés :   1.000000E+00 1.000000E+00
Proportion de groupés : 0.000000E+00 0.000000E+00

Nombres à 2 chiffres + nombres de 1 à 2 chiffres
Nombre total  :          90  100
Nombre d'isolés :        81   91
Nombre de groupés :       9    9
Proportion d'isolés :   9.000000E-01 9.100000E-01
Proportion de groupés : 1.000000E-01 9.000000E-02

Nombres à 3 chiffres + nombres de 1 à 3 chiffres
Nombre total  :         900 1000
Nombre d'isolés :       891  982
Nombre de groupés :       9   18
Proportion d'isolés :   9.900000E-01 9.820000E-01
Proportion de groupés : 1.000000E-02 1.800000E-02

Code:

nodgim

n=  1 S=  10 S0=   8 S-S0=   2
n=  2 S=  90 S0=  63 S-S0=  27
n=  3 S= 990 S0= 576 S-S0= 414

 #13 - 13-03-2015 18:59:41

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

Less isolés et les groupés

Il y a manifestement un problème avec le S0. Il faut que je regarde ça de plus près.

 #14 - 13-03-2015 22:29:36

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

Les isolés et les grooupés

Je crois comprendre ce qu'il se passe. Ma formule a été conçue pour des nombres dont le nombre de chiffres est au moins supérieur à la base. Ce qui est normal, vu que je recherchais en base 10 un nombre d'isolés égal au nombre de groupés, donc des grands nombres. Je ne me suis pas préoccupé des nombres à peu de chiffres. Et on voit bien que ça cloche pour le cas des petits nombres.

J'ai bien pour S40 un 0,5328.., mais pour l'ensemble des nombres compris entre 1 et 10^40 (et non pas pour les seuls nombres à 40 chiffres) et sans le S0. Les résultats de la formule ont été comparés avec certains exemples de base n+1 à 2n chiffres (donc tjs une base plus petite que le nb de chiffres), et ils sont exacts à l'unité près.

Il serait tout de même étonnant qu'on ait trouvé un résultat identique avec une formule fausse. Toutefois, il reste des détails à regarder de mon coté pour le S0, que je maintiens, mais qui n'a pas été vérifié aussi bien que le S (n'a pas été comparé avec une autre méthode).

Comme dirait le professeur Tournesol dans sa fusée lunaire, en parlant de son dispositif automatique pour éviter les météores: "si le dispositif n'avait pas fonctionné, nous aurions été écrasés, mais le pire, c'est qu'il aurait fallu refaire tous les calculs ! "

 #15 - 14-03-2015 08:16:56

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

Les isolés et els groupés

Voici nos résultats respectifs pour 40, 41 et 42 chiffres

Code:

enigmatus

Nombres à                                              40 chiffres                             1 à 40 chiffres
Nombre total  :           9000000000000000000000000000000000000000   10000000000000000000000000000000000000000
Nombre d'isolés :         4714771207916973382037140560106496803560    5273590662713314863104981634891590745124
Nombre de groupés :       4285228792083026617962859439893503196440    4726409337286685136895018365108409254876
Proportion d'isolés :                                 5.238635E-01                                5.273591E-01
Proportion de groupés :                               4.761365E-01                                4.726409E-01

Nombres à                                              41 chiffres                             1 à 41 chiffres
Nombre total  :          90000000000000000000000000000000000000000  100000000000000000000000000000000000000000
Nombre d'isolés :        44374958540727402429889915556882003947569   49648549203440717292994897191773594692693
Nombre de groupés :      45625041459272597570110084443117996052431   50351450796559282707005102808226405307307
Proportion d'isolés :                                 4.930551E-01                                4.964855E-01
Proportion de groupés :                               5.069449E-01                                5.035145E-01

Nombres à                                              42 chiffres                             1 à 42 chiffres
Nombre total  :         900000000000000000000000000000000000000000 1000000000000000000000000000000000000000000
Nombre d'isolés :       416723236793582247561919165552265115121866  466371785997022964854914062744038709814559
Nombre de groupés :     483276763206417752438080834447734884878134  533628214002977035145085937255961290185441
Proportion d'isolés :                                 4.630258E-01                                4.663718E-01
Proportion de groupés :                               5.369742E-01                                5.336282E-01

Code:

nodgim

n= 40 S=   5238634675463303757819045066784996448400 S0=    125039179869707328709343522062729076496 S-S0=   5113595495593596429109701544722267371904
n= 41 S=  49305509489697113810988795063202226608410 S0=   1129648359082137953921346809290480874568 S-S0=  48175861130614975857067448253911745733842
n= 42 S= 463025818659535830624354628391405683468740 S0=  10203477309810638539419247870618198933128 S-S0= 452822341349725192084935380520787484535612

 #16 - 14-03-2015 12:14:19

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

les isolés et leq groupés

C'est bon pour S40, mais il y a un problème avec le calcul du S0(40) selon ma formule. Je trouve avec ma calculette quelque chose comme 0,01007675 *10^39 et non 0.0125....
ça me donne un S40-S0(40) de 0.522855792....de taux. Ce qui reste différent de ce que tu as trouvé, de toute façon.

 #17 - 14-03-2015 12:43:50

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

les isolés et kes groupés

Je suppose que ce que tu appelles S40 est la valeur de S pour n=40. Qu'est-il censé représenter exactement ?

 #18 - 14-03-2015 16:36:34

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

Les isolés et les grupés

S40= 52386.....
S0(40) est celui dont je ne retrouve pas la valeur que tu as calculée. S40 est le nombre d'isolés compris entre 0 et 10^40-1, en incluant les nombres qui commencent par un seul zéro (ceux qui commencent par plus de 1 zéro ne posent pas de problème, à savoir les nombres à 38 chiffres).

 #19 - 14-03-2015 16:53:40

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

Les isolés et les gropués

Dans tous mes calculs, à part le nombre zéro, je n'ai aucun nombre qui commence par le chiffre zéro.

Édité :
Si je calcule le nombre d'isolés pour les nombres à n chiffres, ces nombres pouvant commencer par un nombre quelconque de zéros, je retrouve tes valeurs de S.

 #20 - 14-03-2015 18:15:03

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

Les isolés et lse groupés

Je viens de comprendre ce qu'il se passe avec ma formule: Les zéros isolés d'un nombre à 30 chiffres par exemple sont oubliés, puisqu'il y a virtuellement 10 zéros en tête: le zéro isolé ne peut être compté, ma formule voit plus qu'un zéro, et donc rate les zéros isolés dans ce cas. Ce qui est curieux, c'est que je vois plus d'isolés que le décompte, alors que j'en oublie. ça veut dire qu'il y a d'autres nombres que je compte en trop.

Je vais voir s'il est possible de corriger ça, mais ce n'est pas gagné...

 

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

Mots clés des moteurs de recherche

Mot clé (occurences)

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