EisatoponAI: Το Πρόβλημα της Πτώσης των Αυγών: Η Βέλτιστη Στρατηγική με 2 Αυγά

🥚 Το Κλασικό Πρόβλημα

Έχουμε ένα κτίριο με $F$ ορόφους και 2 αυγά.
Ξέρουμε ότι υπάρχει ένας «κρίσιμος» όροφος $K$ :

Για κάθε όροφο ≤ K το αυγό δεν σπάει.
Για κάθε όροφο > K το αυγό σπάει.

Στόχος:

Να βρούμε τον $K$ με τον ελάχιστο δυνατό αριθμό ρίψεων στη χειρότερη περίπτωση.

Αν είχαμε 1 αυγό, θα ήμασταν αναγκασμένοι να ψάξουμε γραμμικά:

1,\ 2,\ 3,\ \dots

Με 2 αυγά, θέλουμε να ισορροπήσουμε ανάμεσα σε γρήγορη αναζήτηση και ασφάλεια.

🔥 Η Κεντρική Ιδέα

Αν ρίξουμε ένα αυγό από έναν ψηλό όροφο και σπάσει, μας μένει μόνο 1 αυγό, άρα πρέπει να ψάξουμε γραμμικά προς τα κάτω.

Άρα:

Αν πάμε πολύ «ψηλά» κινδυνεύουμε να χρειαστούμε πολλές δοκιμές.
Αν πάμε πολύ «χαμηλά» χάνουμε χρόνο ανεβαίνοντας λίγο–λίγο.

Χρειαζόμαστε μια στρατηγική που ισορροπεί αυτές τις δύο περιπτώσεις.

🔢 Το Κλειδί: Πόσους Ορόφους Καλύπτουμε με $T$ Ρίψεις;

Ορίζουμε:

G(T) = \text{μέγιστος αριθμός ορόφων που μπορούμε να καλύψουμε με } T \text{ ρίψεις και 2 αυγά.}

Αν η πρώτη ρίψη γίνει στον όροφο $T$ :

Αν σπάσει, μας μένουν $T-1$ ρίψεις για να ψάξουμε γραμμικά προς τα κάτω → $T-1$ όροφοι.
Αν δεν σπάσει, έχουμε $T-1$ ρίψεις με 2 αυγά για τους πάνω ορόφους → $G(T-1)$ όροφοι.

Άρα:

G(T) = (T-1) + 1 + G(T-1) = T + G(T-1)

Με αρχική τιμή:

G(0)=0

Επομένως:

G(T) = 1 + 2 + 3 + \cdots + T = \frac{T(T+1)}{2}

Αυτό σημαίνει:

Με 14 ρίψεις μπορούμε να χειριστούμε $\frac{14·15}{2}=105$ ορόφους.

ΚΑΙ αποδεικνύεται ότι κανένας αλγόριθμος με 14 ρίψεις δεν μπορεί να κάνει καλύτερα.
Άρα η στρατηγική είναι βέλτιστη.

↗️ Η Βέλτιστη Σειρά Ρίψεων

Αν χρειάζεσαι $T$ ρίψεις, ρίχνεις:

T,\ T+(T-1),\ T+(T-1)+(T-2),\ \ldots

Δηλαδή κάθε φορά ανεβαίνεις 1 όροφο λιγότερο από πριν.

Παράδειγμα: $F=100$

\frac{T(T+1)}{2} \ge 100 \Rightarrow T=14

Ρίψεις:

14
27 (14 + 13)
39 (14 + 13 + 12)
50
60
69
77
84
90
95
99
102 → σταματάς στο 100.

Αν σπάσει κάπου, ψάχνεις γραμμικά προς τα κάτω από τον προηγούμενο ασφαλή όροφο.

🧠 Γιατί Αυτό Είναι Βέλτιστο (σε 1 φράση)

Η χειρότερη περίπτωση από κάθε σημείο πρέπει να είναι ίση, αλλιώς χάνουμε «ασφάλεια» ή «ταχύτητα».
Το μόνο σύνολο βημάτων που εξισορροπεί ακριβώς αυτή την ισότητα είναι: