Enigme Les isolés et les groupés @ Prise2Tete

nodgim · #1

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.

titoufred · #2

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

nodgim · #3

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.

ckronikks · #4

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

nodgim · #5

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é.

ckronikks · #6

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

enigmatus · #7

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.

nodgim · #8

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...

enigmatus · #9

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.

enigmatus · #10

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 ?

nodgim · #11

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 ?

enigmatus · #12

@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

nodgim · #13

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

nodgim · #14

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 ! "

enigmatus · #15

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

nodgim · #16

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.

enigmatus · #17

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

nodgim · #18

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).

enigmatus · #19

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.

nodgim · #20

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é...

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 07-03-2015 12:12:39

Les isolés et less groupés

#0 Pub

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

Les isolé et les groupés

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

Les isolés et les grouéps

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

les isplés et les groupés

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

Les isoléés et les groupés

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

Les isolés et les goupés

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

les isilés et les groupés

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

Les isoléés et les groupés

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

Les isolés et les groupé

Code:

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

Les isolés ett les groupés

nodgim #8 a écrit:

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

Les isolés et lse groupés

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

les isolés rt les groupés

Code:

Code:

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

Les isolés et les groupé

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

Les isolés et les ggroupés

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

Les isolés et les grouupés

Code:

Code:

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

Les isollés et les groupés

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

les usolés et les groupés

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

Les isolés et les grouéps

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

les isolés et leq groupés

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

les isolés et les geoupés

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums