mathematica.gr

Δημοσιεύτηκε: **Τρί Σεπ 14, 2021 11:14 pm**

Μια αποθήκη έχει σχήμα ορθογώνιου παραλληλεπιπέδου, τα μήκη των ακμών της οποίας είναι ακέραιοι αριθμοί. Η αποθήκη γεμίζεται με κοντέινερ διαστάσεων $1 \times 1 \times 3$ . Εξάλλου τα κοντέινερ μπορούν να τοποθετηθούν όπως βολεύει, αλλά οι έδρες τους θα πρέπει να είναι παράλληλες προς τις έδρες της αποθήκης. Ποιο είναι το μέγιστο ποσοστό του όγκου οποιασδήποτε αποθήκης όγκου τουλάχιστον 200

, που εγγυημένα υπάρχει η δυνατότητα να γεμίσουμε με κοντέινερ.

Κατάλληλο και για μικρότερες τάξεις. Πηγή: Ενιαία Κρατική Εξέταση Ρωσίας, 2018.

Δημοσιεύτηκε: **Παρ Σεπ 17, 2021 10:20 am**

Ισχυρίζομαι ότι μπορούμε να καλύψουμε πάντα όλη την αποθήκη εκτός από το πολύ 8 κυβάκια:

Έστω ότι η αποθήκη μας είναι μεγέθους $a \times b \times c$ . Μπορούμε εύκολα να καλύψουμε κομμάτια της μορφής $3 \times b \times c$ και με διαδοχικές καλύψεις θα μας μείνει ακάλυπτο ένα κομμάτι της μορφής $a' \times b \times c$ με $a' \in \{0,1,2\}$ . Με παρόμοιο τρόπο κατά μήκος και των άλλων αξόνων μας μένει ακάλυπτο ένα κομμάτι της μορφής $a'\times b' \times c'$ με $a',b',c' \in \{0,1,2\}$ .

Άρα έχουμε το πολύ

ακάλυπτα κυβάκια και άρα εγγυημένα μπορούμε να καλύψουμε το $96\%$ . (Για όγκο τουλάχιστον 200

.)

Αυτό είναι και το βέλτιστο διότι στην αποθήκη $2 \times 2 \times 50$ όγκου 200

μπορούμε να τοποθετούμε τα κοντέινερ μόνο κάθετα και αναγκαστικά σε κάθε μια από τις 4 στήλες θα περισσέψουν από

τετράγωνα. (Επειδή $50 \equiv 2 \bmod 3$ .)

mathematica.gr

Πλήρωση αποθήκης με κοντέινερ

Πλήρωση αποθήκης με κοντέινερ

Re: Πλήρωση αποθήκης με κοντέινερ