Ας υποθέσουμε ότι έχετε μια μπάρα σοκολάτας που αποτελείται, ως συνήθως, από πολλά τετράγωνα διατεταγμένα σε ορθογώνιο σχέδιο.
Ο στόχος σας είναι να χωρίσετε τη σοκολάτα σε μικρά τετράγωνα (πάντα σπάζοντας κατά μήκος των γραμμών μεταξύ των τετραγώνων) με τον ελάχιστο αριθμό βημάτων.
i) Πόσα βήματα θα χρειαστούν για τη σοκολάτα της εικόνας;
ii) Γενικεύστε για μία σοκολάτα $m \times n$.
Υποθέτω ότι σε κάθε βήμα κόβεται ένα μόνο κομμάτι σοκολάτας κόβεται σε δύο. Έτσι, σε κάθε νέο βήμα, τα κομμάτια που υπήρχαν συνολικά πριν από το βήμα αυξάνονται κατά ένα μετά από το βήμα. Επομένως για να χωριστεί μια σοκολάτα 4×7 σε 28 μοναδικά κομμάτια χρειάζονται 28-1=27 βήματα και, ομοίως για μια σοκολάτα m×n, χρειάζονται mn-1 βήματα.
ΑπάντησηΔιαγραφήμοναδιαία, σόρι
ΔιαγραφήΊσως ακόμα πιο ενδιαφέρουσα πάντως είναι η περίπτωση που οι τομές επιτρέπονται σε περισσότερα από ένα κομμάτια τη φορά.
ΑπάντησηΔιαγραφήΙδού πεδίον δόξης..😊