Sie wählen zufällig zwei unterschiedliche Ganzzahlen zwischen 1 und 100 aus. Wie hoch ist die Wahrscheinlichkeit, dass die größere Zahl genau doppelt so groß ist wie die kleinere Zahl?

Ich habe kürzlich einen HackerRank-Test für eine Data Science-Position durchgeführt und diese Frage falsch gestellt. Ich bin zu gekommen 1/200. Hier ist wie:

Es gibt 50 Kombinationen, die dies wahr machen. (dh {1,2}, {2,4}, {3,6} ... {50,100}). Die Wahrscheinlichkeit, dass eine bestimmte Zahl gewählt wird, ist 1/100. Die Wahrscheinlichkeit, dass der spezifische Satz ausgewählt wird, ist (1/100 * 1/100).

Da es 50 Sätze gibt,

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

Ich gehe natürlich davon aus, dass 1 und 100 enthalten sind. Aber das war die falsche Antwort. Kann mir jemand helfen, meinen Fehler zu verstehen?

Ihr erster Fehler ist, dass es 50 Ergebnisse gibt, es gibt tatsächlich 100 (Bearbeiten: Siehe Kommentar unten zur Verdeutlichung). Dies liegt daran, dass das Erhalten von (1,2) und (2,1) das Ergebnis von zwei getrennten Ergebnissen ist, aber in jedem Fall ist die größere Zahl genau doppelt so groß wie die kleinere Zahl.

Die insgesamt möglichen Möglichkeiten, dies zu erreichen, sind also tatsächlich in der Menge angegeben:

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

Welches ist eine Liste von 100 möglichen Ergebnissen.

Die Gesamtzahl der möglichen Ergebnisse beträgt $100 \times 99$

Da es 100 mögliche Zahlen gibt, die beim ersten Mal ausgewählt werden können, und 99 beim zweiten Mal, da sie unterschiedlich sein müssen.

Daher lautet die Antwort:

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

Mit dem gleichen Argument ist es einfach zu beweisen, dass die Wahrscheinlichkeit für den allgemeineren Fall der Auswahl von Zahlen aus wobei n eine positive gerade Zahl ist, ist gegeben durch:$1, 2, ..., n$$n$

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

Der "Hacker" im Namen des Tests schlägt vor, dass wir versuchen, eine rechnerorientierte Lösung zu finden.

Beginnen wir daher mit einem Programm zur Brute-Force-Aufzählung von (a) den "günstigen" Fällen, in denen eine ganze Zahl doppelt so groß ist wie die andere, und (b) allen möglichen Fällen. Die Antwort wäre dann ihr Verhältnis. Ich habe eine allgemeine Lösung codiert. Seine Eingabe ist eine positive ganze Zahl nund seine Ausgabe ist die Wahrscheinlichkeit.

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)

(Der Beweis der Richtigkeit beruht auf der Tatsache, dass für jede positive Zahl .)$i \ne 2i$$i$

Dieses Programm erfordert Tests und bis zu Inkremente für jede Iteration der inneren Schleife. Daher sind bei jeder Ausführung der inneren Schleife zwischen und Berechnungen erforderlich , oder insgesamt bis . Das ist Leistung: OK für kleine wie , aber schrecklich, wenn oder so überschreitet .$3$$3$$3n$$6n$$3n^2$$6n^2$$O(n^2)$$n$$n=100$$n$$10000$

Als Hacker möchten Sie als Erstes die quadratische Leistung eliminieren, indem Sie die innere Schleife vereinfachen (falls möglich). Gehen Sie zu diesem Zweck systematisch die Zeilen in der inneren Schleife (wie nummeriert) durch und beachten Sie Folgendes:

1. Zeile 1 wird für jeden Wert von ibis auf einmal ausgeführt und daher mal allinkrementiert . Folglich kann für die Berechnung von die Schleife durch Inkrementieren um ersetzt werden .$n-1$alljalln-1

2. Zeile 2 wird genau einmal ausgeführt, wenn und ansonsten überhaupt nicht. Daher kann es durch Inkrementieren um wenn .$2i \le n$all$1$$2i \le n$

3. Zeile 3 wird ausgeführt, sobald sie gerade iist.

Hier ist das transformierte Programm.

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)

Können wir weiter gehen und seine Schleife beseitigen?

1. Zeile 1 'wird mal ausgeführt. Daher wird um erhöht .$n$alln*(n-1)

2. Zeile 2 'wird nur ausgeführt, wenn . Eine Möglichkeit, dies zu zählen, ist (die größte Ganzzahl kleiner oder gleich ).$2i \le n$$\lfloor n/2\rfloor$$n/2$

3. Zeile 3 'wird nur für gerade Werte von . Wiederum passiert das times.⌊ n / 2 $i$$\lfloor n/2 \rfloor$

Die zweite Transformation des Programms ist:

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)

Dies ist bereits eine enorme Leistung: Ein -Algorithmus wurde auf einen -Algorithmus reduziert (der als "geschlossene Formel" für die Antwort angesehen werden kann).O ( 1 $O(n^2)$$O(1)$

Schließlich gibt es einige einfache algebraische Transformationen, die wir durchführen können, indem wir die Initialisierung (Zeile 0) in die erste Verwendung jeder Variablen rollen und die Zeilen 2 '' und 3 '' kombinieren:

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

Zu diesem Zeitpunkt könnte ein Mensch das Programm ausführen. Machen wir es mit :$n=100$

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

Die Ausgabe ist daher .$1/99$

Zusammenfassend kann ein Brute-Force-Algorithmus mithilfe einfacher Programmumschreibungsregeln systematisch in ein elegantes -Programm umgewandelt werden.$O(1)$

Zunächst einmal sind Abtasten Sie ohne Ersatz. Somit gibt es 100 * 99 verschiedene Ergebnisse, z. B. (1,1) ist kein gültiges Ergebnis.

Zweitens spielt die Reihenfolge keine Rolle. Der größere muss genau zweimal sein, nicht der zweite. Entfernen Sie daher symmetrische Paare.

Somit sind 50 von (100) * 99/2 positiv oder 1/99