Παράθεση:
Το μέλος KIT_KAT στις 13-09-2007 στις 22:40 έγραψε...
Αν έχουμε μία παράσταση έστω best(n) που περιγράφει το μέγιστο αριθμό που μπορεί να παραχθεί με μοναδική χρήση n ακεραίων (a, b, c, …) τότε θα είναι best(1)=1, και a=1 ενώ ο αριθμός b θα καλύπτει τα b-best(1) έως b-best(1); O βέλτιστος b είναι =3, best(2)=4 και ο συνδυασμός τους καλύπτει τα 1...4 (a, b-a, b, b+a). Δηλαδή έχουμε όλους τους συνδυασμούς για να δημιουργήσουμε τους ακεραίους μέχρι το 4, όπερ σημαίνει πως για κάθε ακέραιο c θα μπορούμε να δημιουργήσουμε τα c-4 έως c+4. Προφανώς η βέλτιστη τιμή για το c είναι τέτοια ώστε c-best(a,b)=best(a,b)+1=5, δηλαδή το c ισούται με 9. Έχουμε τους αριθμούς ως το 13 ενώ το 14 θα πρέπει να προκύπτει ως ο d-best(a,b,c), άρα d=27. Γενικά αποδεικνύεται πώς κάθε απαραίτητος αριθμός y προκύπτει από τον προηγούμενο του, x, αυξημένο κατά 2x, με άλλα λόγια y=3x ή αλλιώς τελικά best(n)=Σ(3^k), k=0…n.
Ανάθεμα αν καταλαβαίνει κανείς την περιγραφή μου, πάντως τα κομμάτια είναι 1, 3, 9, 27... σωστά συνάδελφε; Μας παίδεψες βραδιάτικα...
Υγ: Εντυπωσιακό είναι πως τα 5 κομμάτια θα ήταν η απάντηση αν θέλαμε να ζυγίσουμε βάρη μέχρι 121kg! 40 είναι το μέγιστο βάρος που μπορούμε να ζυγίσουμε με βέλτιστη επιλογή 4 κομματιών.
|
|
Πρώτον: Πολύ σωστά!
Δευτερον, η περιγραφη σου ειναι οντως περίπλοκη! Ακομα και εγω, δυσκολευτηκα να την κατανοησω με την πρώτη ματιά. Μετά κατάλαβα πως εγω το ελυσα με παρομοιο τρόπο, αλλά βασιζόμενος περίσσοτερο σε λογικη - μπακαλίστικη ισως. Εσυ εδειξες ολο το μαθηματικο τυπο - ευγε!
Να παραθεσω και την δική μου λύση, που ειναι λιγο πιο κατανοητη (ε, ενεργειακος ειμαι, με τους αλγοριθμους δεν τα πηγαινα καλα...χο-χο0
Ξεκινησα ως εξής:
Θεωρησα δεδομένο πως ο ενας αριθμός θα ειναι το 1, καθώς διαφορετικά δεν θα υπήρχε τρόπος να ζυγιζουμε το 39. (αφου οι 4 αριθμοι εχουν αθροισμα 40).
Μετα, ειπα πως αφου εχουμε το 1, το 38 προκυπτει με αφαιρεση του 1 απο το 39, το 37 με προσθεση του 1 στο 36, το 36 απο τους συνδυασμους των 3 αλλων αριθμών, το 35 με αφαιρεση μετα του 1 κτλ κτλ. Δηλαδή εφτιαξα το ισοδυναμο πρόβλημα, το οποίο ελεγε πως με 3 αριθμούς θα πρέπει να ζυγιζω το 36,33,30,27,24,21,18,15,12,9,6,3,
Εαν αυτοι οι αριθμιο ειναι το χ,ψ,ζ, τοτε ισχύει
χ+ψ+ζ=39
Πηγα μετα στο 36. Το 36 θα δημιουργηθεί με μια πο τις παρακατω σχέσεις:
χ+ψ=36 ή
χ+ψ-ζ=36
Ευκολα αποδεικνύεται οτι πρέπει να ισχύει χ+ψ=36.
(Εαν ισχυε το χ+ψ-ζ=36, τοτε ζ=1,5 αδυνατο, αφου θελουμε ακεραιο...)
Αρα ζ=3
Τελειως αναλογα, μετα εψαχνα 2 αριθμους με αθροισμα 36, που να μπορουν να ζυγισουν το 36,27,18,9.
Ε, ειναι το 9 και το 27.
(Τωρα οπως το εγραψα, ουτε απο εδω βγάζει κανείς ακρη!
Σε καθε περιπτωση, ευγε!