Ένα δύσκολο combinatorics πρόβλημα με κλειδιά και κλειδαριές. Βρες το ελάχιστο κόστος

🔐 Πρόβλημα με Κλειδιά & Κλειδαριές

👉 Μπορείς να βρεις το ελάχιστο κόστος;

Ένα κτίριο έχει 160 ορόφους. Σε κάθε όροφο υπάρχουν:

• 2 πόρτες διαδρόμου
• 4 δωμάτια (1 άτομο σε κάθε δωμάτιο)

Κάθε πόρτα έχει κλειδαριά και κάθε κλειδαριά ανοίγει με μοναδικό κλειδί.

Ισχύουν:

• Κάθε άτομο ανοίγει μόνο το δωμάτιό του
• Κάθε άτομο έχει πρόσβαση στον διάδρομο του ορόφου του
• Μπορεί να έχει πρόσβαση και σε άλλους ορόφους

Κόστος:

• Νέο κλειδί: 3
• Αντίγραφο: 2

👉 Να βρεθεί το ελάχιστο συνολικό κόστος.

👉 Δες τη λύση

Βασική ιδέα: 👉 Σε κάθε όροφο μπορούμε να σχεδιάσουμε το σύστημα έτσι ώστε ένα άτομο να έχει μόνο ένα κλειδί.

Άρα το πρόβλημα γίνεται: 👉 160 όροφοι × 3 άτομα = 480 ζεύγη κλειδιών
Κάθε άτομο έχει:

• 1 κλειδί δωματίου
• 1 κλειδί διαδρόμου

Άρα θέλουμε διαφορετικά ζεύγη κλειδιών: \[ \frac{n(n-1)}{2} \ge 480 \]
Λύνοντας: \[ n \ge 32 \]
👉 Ελάχιστα διαφορετικά κλειδιά: 32

Συνολικά κλειδιά που χρειάζονται: \[ 160 \cdot 3 \cdot 2 = 960 \]
Από αυτά:

• 192 είναι διαφορετικά (νέα)
• 928 είναι αντίγραφα

Κόστος: \[ 192 \cdot 3 + 928 \cdot 2 \] \[ = 576 + 1856 \] \[ = \boxed{2432} \]