Παγωτά

[αρψ2400]

Έχω 100 κλειστά κουτιά στις θέσεις 1,2,3,....,99,100. Κάθε κουτί μπορεί να περιέχει μέχρι 2 παγωτά. Κάθε υποσύνολο 35 κουτιών περιέχει τουλάχιστον 7 παγωτά. Ποιός είναι ο ελάχιστος αριθμός παγωτών που μπορεί να περιέχουν τα κουτιά;

[Mihalis_Lambrou]

Έχω 100 κλειστά κουτιά στις θέσεις 1,2,3,....,99,100. Κάθε κουτί μπορεί να περιέχει μέχρι 2 παγωτά. Κάθε υποσύνολο 35 κουτιών περιέχει τουλάχιστον 7 παγωτά. Ποιός είναι ο ελάχιστος αριθμός παγωτών που μπορεί να περιέχουν τα κουτιά;

Απάντηση: παγωτά κατ' ελάχιστο.

Αν έχουμε ή λιγότερα άδεια κουτιά, τότε τα υπόλοιπα (τουλάχιστον) κουτιά έχουν τουλάχιστον από παγωτό το καθένα. Σε αυτή την περίπτωση ικανοποιούνται οι συνθήκες του προβλήματος διότι οποιαδήποτε κουτιά έχουν συνολικά τουλάχιστον παγωτά. Το συνολικό πλήθος των παγωτών στα κουτιά είναι τουλάχιστον παγωτά. Μάλιστα, πετυχαίνουμε ακριβώς με άδεια κουτιά και με παγωτό το καθένα.

Τώρα, αν έχουμε ή περισσότερα άδεια κουτιά, σίγουρα πρέπει να υπάρχει κουτί με παγωτά. Πράγματι, αν όλα τα υπόλοιπα είχαν το πολύ παγωτό τότε παίρνοντας άδεια και οποιαδήποτε άλλα κουτιά (σύνολο ), θα είχαμε το πολύ παγωτά, ενώ ξέρουμε ότι πρέπει να περιέχουν τουλάχιστον 7. Συνεπώς σίγουρα υπάρχει κουτί με παγωτά. Συμπεραίνουμε ότι το σύνολο των κουτιών περιέχει τουλάχιστον παγωτά.

Σε όλες τις περιπτώσεις τα παγωτά είναι με ισότητα σε κάποια περίπτωση.

[Mihalis_Lambrou]

Πρόσθετη άσκηση:

Δείξτε ότι με τις συνθήκες του παραπάνω προβλήματος,

α) Τα άδεια κουτιά είναι το πολύ ,

β) Αν είχαμε ή περισσότερα άδεια κουτιά τότε το σύνολο των παγωτών θα ήταν τουλάχιστον .

(Στην προηγούμενη λύση δείξαμε ότι στην περίπτωση β) είχαμε τουλάχιστον παγωτά. Αυτό επαρκούσε για τις ανάγκες της λύσης, αλλά τώρα βελτιώστε αυτό το νούμερο. Υπόψη ότι δεν βελτιώνεται και άλλο. Επίσης, υπάρχουν παραδείγματα με και άδεια κουτιά.)

[Mihalis_Lambrou]

Πρόσθετη άσκηση:

Δείξτε ότι με τις συνθήκες του παραπάνω προβλήματος,

α) Τα άδεια κουτιά είναι το πολύ ,

β) Αν είχαμε ή περισσότερα άδεια κουτιά τότε το σύνολο των παγωτών θα ήταν τουλάχιστον .

(Στην προηγούμενη λύση δείξαμε ότι στην περίπτωση β) είχαμε τουλάχιστον παγωτά. Αυτό επαρκούσε για τις ανάγκες της λύσης, αλλά τώρα βελτιώστε αυτό το νούμερο. Υπόψη ότι δεν βελτιώνεται και άλλο. Επίσης, υπάρχουν παραδείγματα με και άδεια κουτιά.)

α) 'Εστω ότι είχαμε ή περισσότερα άδεια κουτιά. Τότε παίρνοντας τα αυτά σύν άλλα για να έχουμε σύνολο , τότε το πλήθος των παγωτών θα ήταν το πολύ , άτοπο. Άρα τα άδεια κουτιά είναι το πολύ .

β) 'Εστω ότι είχαμε ακριβώς άδεια κουτιά (ανάλογα η περίπτωση με ή ). Ισχυρίζομαι ότι από τα υπόλοιπα το πολύ θα έχουν από παγωτό. Πράγματι, αν είχαμε κουτιά με παγωτό, τότε παίρνοντας τα αυτά σύν άλλα με παγωτό τότε θα είχαμε κουτιά με συνολικό αριθμό παγωτών. Άτοπο. Άρα υπάρχουν το πολύ κουτιά με παγωτό και άρα τα υπόλοιπα κουτιά έχουν από . Το σύνολο των παγωτών είναι τότε παγωτά.