Προβλήματα Μαθηματικών

Αύγουστος 17, 2010

Πτώση μέχρι καταστροφής

Filed under: Λυμένα Προβλήματα,Με επιπλέον ερωτήματα — Mihalis Kolountzakis @ 11:00 μμ

Μια εταιρεία παραγωγής μαγικών ειδών σας ζητάει να εκτιμήσετε την ποιότητα της νέας γυάλινης σφαίρας που έχει κατασκευάσει, και ειδικότερα σας ζητάει να αποφασίσετε από ποιον όροφο του 36-όροφου κτηρίου της πρέπει να πέσει για να σπάσει.

Για το σκοπό αυτό σας διαθέτει ακριβώς δύο πανομοιότυπες γυάλινες σφαίρες.

Εσείς πρέπει λοιπόν να αποφασίσετε ποιο είναι το ελάχιστο n\ge 1 τέτοιο ώστε αν η γυάλινη σφαίρα πέσει από τον n-οστό όροφο σπάει αλλά αν πέσει από τον (n-1)-όροφο τότε δε σπάει.

Ένας προφανής τρόπος να το κάνετε αυτό χρησιμοποιώντας μάλιστα μόνο τη μια σφαίρα είναι να ανεβαίνετε τους ορόφους έναν-έναν και από κάθε όροφο να ρίχνετε τη σφαίρα μέχρι να σπάσει.

Όμως αυτός ο όροφος παίρνει εν γένει πολλές δοκιμές.

Προσπαθείστε να το κάνετε με όσο λιγότερες δοκιμές μπορείτε.

Advertisements

2 Σχόλια »

  1. Έστω οτι έχει Ν ορόφους το κτήριο.Με την μέθοδο αυτή που δοκιμάζεις ένα ένα θέλει (στη χειρότερη πάντα δυνατή περίπτωση) Ν-1 προσπάθειες (αν δεχτούμε οτι σίγουρα σπάει απο τον τελευταίο).Μια άλλη ιδέα είναι η εξής.

    Κάνω μια διαμέριση των ορόφων σε Κ κομμάτια.Τότε ξεκινάω από το πιο χαμηλό, το Ν/Κ.Αν σπάσει τότε κάνω την κοπιαστική διαδικασία, και κάνω έτσι Ν/Κ -2 δοκιμές(αν έχει σπάσει στο Ν/Κ και δεν έχει σπάσει στο Ν/Κ-2 τότε σίγουρα είναι στο ενδιάμεσο και γλυτώνω μια δοκιμή).Αν δεν σπάσει, πάω στο επόμενο, το 2Ν/Κ.Αν σπάσει τότε κάνω τις δοκιμές ανάμεσα στα 2 προηγούμενα, δηλαδή πάλι Ν/Κ -2 προσπάθειες.Με αυτό το συλλογιστικό προχοράω.

    Έτσι συνολικά οι δοκιμές είναι (Ν/Κ)+Κ-3. Αυτό είναι μια συνάρτηση με άγνωστο το Κ, που θέλω να την ελαχιστοποιήσω, και έτσι βρίσκω οτι η καλύτερη διαμέριση είναι στο (N)^1/2.

    Τελικά, οι μέγιστες δοκιμές με αυτή τη μέθοδο είναι 2(Ν)^1/2 -3 κάτι που είναι σηματική βελτίωση για μεγάλο Ν.Στο κτήριο που δώθηκε χρειάζομαι δηλαδή στη χειρότερη περίπτωση 9 δοκιμές.Δεν ξέρω αν αυτή η μέθοδος είναι η βέλτιστη, αλλά δεν βρίσκω τώρα κάτι καλύτερο.Και σε περίπτωση που δεν είναι τετράγωνος τότε φαντάζομαι θα δουλεύει με το ακέραιο μέρος με μικρές διαφορές στις δοκιμές αλλά θα είναι πάλι Ο(sqrt(N))

    Μου αρέσει!

    Σχόλιο από olack — Αύγουστος 18, 2010 @ 6:31 πμ

  2. Πολύ σωστή και μεθοδική προσέγγιση.

    Υπάρχει τρόπος να βελτιωθεί η σταθερά στο O(\sqrt{N}): παρατηρούμε ότι 36=1+2+3+\cdots+8 (είναι αυτό που λέμε τριγωνικός αριθμός) και κοιτάμε πρώτα στον 8ο όροφο. Αν σπάσει κοιτάμε έναν έναν από κει και κάτω αλλιώς κοιτάμε στον όροφο 8+7=15. Αν σπάσει κοιτάμε από τον 9 έως τον 14, κλπ. Αυτό δίνει βελτιωμένη σταθερά. Αν ο αριθμός δεν είναι τριγωνικός τότε πάμε μέχρι τον επόμενο τριγωνικό.

    Όμως η σταθερά δεν είναι και τόσο σημαντική.

    Κάτω φράγματα;

    Αυτό που πρέπει ακόμη να γίνει είναι να βεβαιωθούμε ότι η τάξη μεγέθους είναι η σωστή. Να δείξουμε δηλ. ότι οποιαδήποτε σωστή μέθοδος θα χρειαστεί σε κάποιες περιπτώσεις να κοιτάξει τουλάχιστον C\sqrt{N} ορόφοους, όπου C είναι μια μικρή σταθερά, π.χ. C=10^{-2}.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Αύγουστος 18, 2010 @ 11:24 πμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Blog στο WordPress.com.

Αρέσει σε %d bloggers: