Vous sélectionnez au hasard deux entiers distincts entre 1 et 100. Quelle est la probabilité que le plus grand nombre soit exactement le double du plus petit?

J'ai récemment passé un test HackerRank pour un poste en Data Science et j'ai mal répondu à cette question. Je suis venu 1/200. Voici comment:

Il y a 50 combinaisons qui rendront cela vrai. (c'est-à-dire {1,2}, {2,4}, {3,6} ... {50,100}). La probabilité qu'un nombre spécifique soit choisi est 1/100. La probabilité que l'ensemble spécifique soit choisi est (1/100 * 1/100).

Puisqu'il y a 50 ensembles,

P=50*(1/100)*(1/100)=1/200

Je suppose bien sûr que 1 et 100 sont inclus. Mais ce n'était pas la bonne réponse. Quelqu'un peut-il m'aider à comprendre mon erreur?

Votre première erreur est qu'il y a 50 résultats, il y en a réellement 100 (Edit: Voir le commentaire ci-dessous pour des éclaircissements). En effet, obtenir (1,2) et (2,1) sont les résultats de deux résultats séparés, mais dans chaque cas, le plus grand nombre est exactement le double du plus petit.

Donc, le total des façons possibles d'obtenir cela est en fait donné par l'ensemble:

{(1,2), (2,1), (2,4), (4,2), ..., (50,100), (100,50)}

C'est une liste de 100 résultats possibles.

Le nombre total de résultats possibles est de$100 \times 99$

Puisqu'il y a 100 nombres possibles à choisir la première fois, puis 99 pour la seconde car ils doivent être distincts.

D'où la réponse est donnée par:

$P = \frac{100}{100 \times 99} = \frac{1}{99}$

En utilisant le même argument, il est simple de prouver que la probabilité pour le cas plus général de choisir des nombres parmi où est un nombre pair positif est donnée par:$1, 2, ..., n$$n$

$P = \frac{1}{n-1}$

Le "Hacker" au nom du test suggère que nous essayons de trouver une solution informatique.

Commençons donc par un programme d'énumération par force brute de (a) les cas "favorables" où un entier est le double de l'autre et (b) tous les cas possibles. La réponse serait alors leur ratio. J'ai codé une solution générale. Son entrée est un entier positif net sa sortie est la probabilité.

n=100
all=favorable=0
for i=1 to n
    for j=1 to n
        if (i != j) all=all+1                  {1}
        if (j == 2*i) favorable = favorable+1  {2}
        if (i == 2*j) favorable = favorable+1  {3}
return(favorable / all)

(La preuve d'exactitude repose sur le fait que pour tout nombre positif .)$i \ne 2i$$i$

Ce programme nécessite tests et jusqu'à incréments pour chaque itération de la boucle interne. Il faut donc entre et calculs à chaque exécution de la boucle interne, soit à total. C'est la performance : OK pour les petits comme , mais terribles une fois que dépasse environ.$3$$3$$3n$$6n$$3n^2$$6n^2$$O(n^2)$$n$$n=100$$n$$10000$

En tant que hacker, l'une des premières choses que vous voudrez faire est d'éliminer les performances quadratiques en simplifiant la boucle interne (si possible). À cette fin, parcourez systématiquement les lignes de la boucle intérieure (numérotées) et notez les points suivants:

1. La ligne 1 est exécutée une seule fois pour chaque valeur de iet allest donc incrémentée fois. Par conséquent, pour le calcul de , la boucle peut être remplacée par incrémentation de .$n-1$alljalln-1

2. La ligne 2 est exécutée exactement une fois lorsque et sinon pas du tout. Par conséquent, il peut être remplacé par incrémentation de chaque fois que .$2i \le n$all$1$$2i \le n$

3. La ligne 3 est exécutée une fois fournie iest paire.

Voici le programme transformé.

n=100
all=favorable=0
for i=1 to n
    all = all + (n-1)                      {1'}
    if (2*i <= n) favorable = favorable+1  {2'}
    if (even(i)) favorable = favorable+1   {3'}
return(favorable / all)

Pouvons-nous aller plus loin et éliminer sa boucle?

1. La ligne 1 'est exécutée fois. Par conséquent est incrémenté de .$n$alln*(n-1)

2. La ligne 2 'n'est exécutée que lorsque . Une façon de compter cela est (le plus grand entier inférieur ou égal à ).$2i \le n$$\lfloor n/2\rfloor$$n/2$

3. La ligne 3 'est exécutée uniquement pour les valeurs paires de . Encore une fois, cela se produit times.$i$$\lfloor n/2 \rfloor$

La deuxième transformation du programme est:

n=100
all=favorable=0                     {0}
all = all + n * (n-1)               {1''}
favorable = favorable + floor(n/2)  {2''}
favorable = favorable + floor(n/2)  {3''}
return(favorable / all)

C'est déjà un accomplissement formidable: un algorithme a été réduit à un algorithme (qui peut être considéré comme une "formule fermée" pour la réponse).$O(n^2)$$O(1)$

Enfin, il y a quelques transformations algébriques simples que nous pouvons faire en roulant l'initialisation (ligne 0) dans la première utilisation de chaque variable et en combinant les lignes 2 '' et 3 '':

n=100
all = n * (n-1) 
favorable = 2 * floor(n/2) 
return(favorable / all)

À ce stade, un humain pourrait exécuter le programme. Faisons-le avec :$n=100$

all = 100 * (100-1) = 100*99
favorable = 2 * floor(100/2) = 2*50 = 100
favorable/all = 100 / (100*99) = 1/99

La sortie est donc .$1/99$

Pour résumer, un algorithme de force brute peut être transformé systématiquement en utilisant des règles de réécriture de programme simples en un programme élégant et élégant .$O(1)$

Tout d'abord, vous échantillonnez sans remplacement. Ainsi, il y a 100 * 99 résultats différents, par exemple (1,1) n'est pas un résultat valide.

Deuxièmement, l'ordre n'a pas d'importance. Le plus grand doit être exactement deux fois, pas le second. Ainsi, supprimez les paires symétriques.

Ainsi, 50 sur (100) * 99/2 sont positifs, soit 1/99