by 
Διαθέτουμε δύο πανομοιότυπα μπαλάκια φτιαγμένα απο υλικό που σπάει. Θέλουμε να διαπιστώσουμε απο ποιο όροφο και πάνω ενός ουρανοξύστη 100 ορόφων αν αφήσουμε ένα μπαλάκι να πέσει ελεύθερα θα σπάσει.
Ζητείται η μέθοδος που θα δώσει απάντηση στο ζητούμενο, με τις λιγότερες δυνατές προσπάθειες.
Σπύρο καλησπέρα.
Είναι 14 οι προσπάθειες;
Έχω μια λύση αλλά θα περιμένω να δουν το πρόβλημα και άλλοι φίλοι.
Σωστά Γιάννη.
Καλημέρα,
Αρχικά ήθελα να κάνω μία ερώτηση: αν κάποιο μπαλάκι σπάσει στην πρώτη μας προσπάθεια μετά θα έχουμε διαθέσιμο μόνο το ένα που έμεινε ή μπορούμε να πάρουμε πάλι ένα ώστε πάντα να έχουμε διαθέσιμα 2;
Νίκο καλημέρα. Μονο δύο διαθέτουμε. Με αυτά πρέπει να βρουμε το ζητούμενο.
Δύο μόνο! Δύσκολα μας βάζεις Σπύρο.
Καλημέρα Σπύρο. Ξύπνησα πρωί πρωί και την είδα. Η πρώτη μπακαλίστικη σκέψη πρώτα ανά 10 με το πρώτο μπαλάκι και μετά ανά 2. Ψάχνω για μία γενική λύση. Ας πούμε ότι είχαμε ουρανοξύστη με 300 ορόφους. Πόσες προσπάθειες θα έπρεπε να κάνουμε το ελάχιστο;
Νομίζω ότι είναι ανά 14 και μετά ανά 2. Για τους 200 ορόφους θα χρειαζόμουνα 19 προσπάθειες.
xy=100 , x-1+y/2=min –> 100/y-1+y/2=min ΆΡΑ 100/y=y/2
Καλημέρα Πάνο.
Δεν εινα η βέλτιστη λύση αυτή που προτείνεις. Για παραδειγμα αν το πρώτο μπαλάκι σπάσει στον 90οστο όροφο θα χρειαστείς και άλλες 9 για να βρεις ποιός απο τους 81ο εως 89 είναι ο χαμηλότερος που θα σπάσει το δεύτερο. Δηλαδή 18 προσπάθειες.
Η απάντηση .οπως είπε ο Γιάννης είναι 14 προσπάθειες.
Καλημέρα
Σκεφτόμουν, χρησιμοποιώντας την απάντηση του Πάνου Αν αφήσω το πρώτο μπαλάκι στον όροφο 14 και σπάσει τότε θέλω 13 το πολύ κινήσεις για να βρω αν θα σπάσει από τον 1 έως τον 13. Αν δε σπάσει από τον όροφο 14, τότε το ξανά αφήνω στον όροφο 27, μειώνω κατά ένα τον αριθμό του βήματος. Αν σπάσει στον 27 θέλω το πολύ από τον 15 έως τον 26 προσπαθειες… Δυστυχώς δεν έχω τόσο καθαρό μυαλό για να βρω το 14…
Συγγνώμη την απάντηση του Γιάννη εννοούσα.
Καλημέρα σε όλους.
Νίκο είσαι πολύ κοντά!
(Από τον 15 ως τον 26 είναι 12 προσπάθειες).
Μάλλον πάει βηματιστά αφού κάθε φορά θα έχω μία προσπάθεια λιγότερη. Άρα θα πρέπει ν(ν+1)/2=100
ν=14. Τη πρώτη φορά θα το ρίξω από τον 14ο τη δεύτερη από τον 27ο τη τρίτη από τον 39ο και πάει λεγοντας Ελπίζω τώρα που ξύπνησα καλύτερα ναμαι και σωστός.
Σωστα Πάνο. Γενικά αν έχουμε x ορόφους πρέπει να ξεκινήσουμε απο τον n-οστο όροφο όπου n(n+1)>=2x και να συνεχίσουμε όπως είπες.
Νίκο τώρα είδα και τη δική σου απάντηση. Σωστός. Ουσιαστικά αυτή είναι η λογική.
Σας ευχαριστώ που ασχοληθήκαυε
Παραθέτω κάποιες σκέψεις για το πρόβλημα:
Ας υποθέσουμε ότι αφήνουμε το πρώτο μπαλάκι από ύψος (όροφο) κ. Υπάρχουν δύο περιπτώσεις, να σπάσει ή να μην σπάσει.
Αν σπάσει, πρέπει να δοκιμάσουμε τους ορόφους από 1 μέχρι και (κ-1) με τη σειρά. Έχουμε ήδη μια προσπάθεια. Έτσι θα χρειασθούμε, στη χειρότερη περίπτωση (αν δεν σπάσει το δεύτερο μπαλάκι μέχρι και τον κ-2 όροφο, οπότε θα πρέπει να δούμε τι θα γίνει και στον κ-1 όροφο) κ συνολικά προσπάθειες. (Την πρώτη και τις επόμενες κ-1). Αν το (δεύτερο) μπαλάκι σπάσει στον κ-1 όροφο, τότε αυτός είναι και ο μικρότερου ύψους. Αν δεν σπάσει, τότε ο κ όροφος είναι ο ζητούμενος. Αν το δεύτερο μπαλάκι σπάσει πιο πριν, ας πούμε στον κ-3, όροφο, τότε αυτός είναι που ζητάμε (και θα έχουμε κάνει λιγότερες από κ προσπάθειες, δηλαδή σταθήκαμε τυχεροί).
Αν δεν σπάσει (το πρώτο μπαλάκι), θα ανεβούμε (κ-1) ορόφους (γιατί έχουμε ήδη μια προσπάθεια), αν θέλουμε ο αριθμός των προσπαθειών να είναι ο ίδιος.
Προχωρώντας με το ίδιο σκεπτικό, αν δεν σπάσει (το πρώτο πάντα μπαλάκι) ανεβαίνουμε (κ-2), μετά (κ-3)… μέχρι 1 και έτσι διατηρούμε τον αριθμό των προσπαθειών ίδιο.
Θα έχουμε ανεβεί λοιπόν 1+2+…(κ-1)+κ ορόφους, έχοντας φτάσει ή και υπερβεί τον 100 όροφο!
Άρα:
1+2+…+(κ-1)+κ μεγαλύτερο ή = 100. Η εξίσωση κ.(κ+1)/2 =100 δίνει κ περίπου 13,7 (Προφανώς κρατάμε μόνο τη θετική λύση) .
Στρογγυλοποιώντας το 13,7 στο 14, έχουμε τη λύση.
Θα πρέπει να δοκιμάσουμε από τους ορόφους:
14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100.
(Στρογγυλοποιώντας στο 14, το γινόμενο κ(κ+1)/2 γίνεται ίσο με 105, δηλαδή υπερβαίνουμε τον αριθμό των ορόφων (δεν μας ενοχλεί καθόλου αυτό στη λύση μας, αφού εμείς μετά τον 99 ελέγχουμε μόνο και τον 100) και η πλήρης σειρά είναι:
14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 102,104, 105
Ας δούμε από περιέργεια τι θα συμβεί αν επιλέξουμε στρογγυλοποίηση στο 13, παρότι δεν ικανοποιείται η ανισότητα μεγαλύτερο ή ίσο του 100. Το γινόμενο κ(κ+1)/2 γίνεται ίσο με 91 και τότε η σειρά των ορόφων γίνεται:
13, 25, 36, 46, 55, 63, 70, 76, 81, 85, 88, 90, 91
Οπότε εξαντλείται η σειρά στον όροφο 91. Θα χρειαζόμασταν λοιπόν να ελέγξουμε και τους υπόλοιπους 9 ορόφους. Η εξίσωση ή κ.(κ+1)/2 =9, δίνει τη λύση κ περίπου 3,77 και με στρογγυλοποίηση κ=4. Άρα θα θέλαμε 13+4 = 17 προσπάθειες, δηλαδή περισσότερες απ’ ότι για κ=14)
ΟΠΟΤΕ:
Μιλώντας για το πρώτο μπαλάκι:
Αν σπάσει στη πρώτη ρίψη (14 όροφο), πρέπει να δοκιμάσουμε διαδοχικά τους ορόφους από 1 έως και (χειρότερη μας τύχη) 13, δηλαδή 14 προσπάθειες.
Αν δεν σπάσει στην πρώτη ρίψη, αλλά στη δεύτερη (27 όροφο), τότε θα έχουμε κάνει δύο προσπάθειες με το πρώτο μπαλάκι και θα πρέπει να ελέγξουμε διαδοχικά 12 ορόφους (από τον 15 μέχρι και τον 26) δηλαδή πάλι 14 προσπάθειες.
Αν δεν σπάσει ούτε στη δεύτερη, αλλά στην τρίτη (39 όροφο), τότε θα έχουμε κάνει 3 προσπάθειες με το πρώτο μπαλάκι και θα πρέπει να ελέγξουμε διαδοχικά τους ορόφους από 28 μέχρι 38, δηλαδή 11 προσπάθειες, άρα συνολικά πάλι 14 προσπάθειες.
Και ούτω καθ’ εξής….