Φρουτεμπορική

Συντονιστές: Demetres, socrates, silouan

Άβαταρ μέλους
Al.Koutsouridis
Δημοσιεύσεις: 951
Εγγραφή: Πέμ Ιαν 30, 2014 11:58 pm
Τοποθεσία: Αθήνα

Φρουτεμπορική

#1

Μη αναγνωσμένη δημοσίευση από Al.Koutsouridis » Πέμ Αύγ 08, 2019 10:59 am

Σε εκατό κούτες είναι τοποθετημένα πορτοκάλια, μήλα και μπανάνες. Αποδείξτε ότι μπορούμε να διαλέξουμε 51 κούτες, στις οποίες συνολικά υπάρχουν από όλα τα πορτοκάλια τουλάχιστον τα μισά, από όλα τα μήλα τουλάχιστον τα μισά και από όλες τις μπανάνες τουλάχιστον οι μισές.



Λέξεις Κλειδιά:
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8181
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Φρουτεμπορική

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Κυρ Αύγ 11, 2019 2:11 pm

Δίνω μια απόδειξη η οποία χρησιμοποιεί ένα μη στοιχειώδες θεώρημα. Θα ενδιαφερόμουν αν δω αν υπάρχει κάτι άλλο.

Αριθμούμε τις κούτες από το 1 ως το 100. Αν δεν ισχύει το ζητούμενο, για κάθε υποσύνολο A του X = \{1,2,\ldots,100\} υπάρχει ένα φρούτο ώστε οι αντίστοιχες κούτες να περιέχουν λιγότερα από τα μισά φρούτα αυτού του είδους. Τότε οι αντίστοιχες κούτες του A^{\mathrm{c}} περιέχουν περισσότερα από τα μισά φρούτα αυτού του είδους.

Κατασκευάζουμε τώρα ένα γράφημα με κορυφές τα υποσύνολα του X μεγέθους 49 όπου συνδέουμε 2 με ακμή αν και μόνο αν είναι ξένα μεταξύ τους. Από γνωστό θεώρημα (*) ο χρωματικός αριθμός αυτού του γραφήματος είναι 100 - 2 \cdot 49 + 2 = 4.

Αυτό σημαίνει ότι θα υπάρχουν δύο ξένα μεταξύ τους σύνολα A,B μεγέθους 49 και ένα συγκεκριμένο φρούτο, έστω πορτοκάλι, ώστε στα αντίστοιχα κουτιά των A και B τα πορτοκάλια να είναι περισσότερα από τα μισά. Αυτό όμως είναι άτοπο αφού τότε στην ένωση των A,B θα είχαμε περισσότερα πορτοκάλια από όσα υπάρχουν.

(*) Η εικασία του Kneser λέει ότι το γράφημα με κορυφές τα υποσύνολα του \{1,2,\ldots,n\} μεγέθους r < n/2 όπου συνδέουμε δύο μεταξύ τους αν και μόνο αν είναι ξένα μεταξύ τους έχει χρωματικό αριθμό n-2r+2. Ένας χρωματισμός με τόσα χρώματα είναι ο εξής: Χρωματίζουμε όλα τα r-σύνολα που περιέχουν το 1 με το χρώμα 1. Χρωματίζουμε όλα τα r-σύνολα που περιέχουν το 2 αλλά όχι το 1 με το χρώμα 2 κ.ο.κ. μέχρι να χρωματίσουμε όλα τα r-σύνολα που περιέχουν το n-2r+1 αλλά όχι τα 1,2,\ldots,n-2r με το χρώμα n-2r+1. Τέλος χρωματίζουμε όλα τα υπόλοιπα σύνολα (ανά δύο δεν είναι ξένα μεταξύ τους) με το χρώμα n-2r+2. Η εικασία αποδείχθηκε από τον Lovász χρησιμοποιώντας ένα τοπολογικό θεώρημα (το θεώρημα Borsuk-Ulam). Για τη συγκεκριμένη περίπτωση που χρησιμοποίησα θέλουμε την περίπτωση του θεωρήματος στην 3-διάστατη σφαίρα το οποίο δεν είναι στοιχειώδες να αποδειχθεί.


Άβαταρ μέλους
Al.Koutsouridis
Δημοσιεύσεις: 951
Εγγραφή: Πέμ Ιαν 30, 2014 11:58 pm
Τοποθεσία: Αθήνα

Re: Φρουτεμπορική

#3

Μη αναγνωσμένη δημοσίευση από Al.Koutsouridis » Κυρ Αύγ 11, 2019 8:57 pm

Demetres έγραψε:
Κυρ Αύγ 11, 2019 2:11 pm
Θα ενδιαφερόμουν αν δω αν υπάρχει κάτι άλλο.
Το πρόβλημα είναι το υπ’ αριθμόν 4830 του περιοδικού «Τα μαθηματικά στο σχολείο», τεύχος 4, 2005. Η λύση που δίνεται στο περιοδικό είναι η παρακάτω.

Λήμμα:
Έστω ότι υπάρχουν 2n κούτες, το πλήθος των πορτοκαλιών και μήλων σε κάθε μία από τις οποίες δεν υπερβαίνει το A και B αντίστοιχα. Τότε οι κουτές μπορούν διαμεριστούν σε δυο ομάδες των n κουτών έτσι, ώστε αυτές οι ομάδες να διαφέρουν το πολύ κατά A ως προς το συνολικό αριθμό των πορτοκαλιών και το πολύ κατά B ως προς το συνολικό αριθμό των μήλων.
Απόδειξη:
Το πλήθος των πορτοκαλιών και μήλων στην i- οστή (i=1,2,…, 2n) κούτα θα το συμβολίσουμε με A_{i} και B_{i} αντίστοιχα. Εξάλλου θα θεωρήσουμε ότι A_{1} \geq A_{2} \geq … \geq A_{2n}.

Θα σχηματίσουμε τις δύο ομάδες κουτών με τον ακόλουθο τρόπο. Αρχικά την μια ομάδα θα την σχηματίσουμε με την κούτα νούμερο 1 και την άλλη με την κούτα νούμερο 2. Ύστερα, όταν τοποθετούνται στις ομάδες οι κούτες με νούμερα από το 1 έως 2k (k=1,2,…,n-1), προσθέτουμε στις διάφορες ομάδες κουτών τις κούτες με νούμερα 2k+1 και 2k+2, μάλιστα εκείνη από αυτές, στην οποία τα μήλα δεν είναι λιγότερα από την άλλη, προστίθεται σε εκείνη την ομάδα, όπου τα μήλα δεν είναι περισσότερα, από την άλλη.

Στο τέλος ως προς το πλήθος των πορτοκαλιών η διαφορά μεταξύ των ομάδων δεν θα υπερβαίνει

(A_{1}-A_{2}) +(A_{3}-A_{4}) + … + (A_{2n-1}-A_{2n}) \leq A_{1} \leq A.

Παρατηρούμε, πως στη διαδικασία σχηματισμού των ομάδων αλλάζει η διαφορά ως προς τον αριθμό των μήλων μεταξύ τους. Έστω R_{k} (k=1,…,k-1) η διαφορά την χρονική στιγμή κατά την οποία στις ομάδες προστίθενται οι κούτες με νούμερα από 1 έως 2k. Τότε R_{1}=|B_{1}-B_{2}| \leq B και αν R_{k} \leq B, τότε R_{k+1} \leq max \{R_{k}, \ |B_{2k+1}-B_{2k+2}\ | \} \leq B. Από την αρχή της μαθηματικής επαγωγής R_{n} \leq B. Το λήμμα αποδείχθηκε.
Λύση:
Διαλέγουμε από τις 100 κούτες αυτήν, στην οποία τα πορτοκάλια δεν είναι λιγότερα από όλες τις υπόλοιπες. Ύστερα από τις 99 απομείναντες εκείνη, στην οποία τα μήλα δεν είναι λιγότερα από κάθε μια από τις 98 απομείναντες. Στη συνέχεια με την διαδικασία που υποδείχτηκε στην απόδειξη του λήμματος διαιρούμε τις 98 κούτες σε ομάδες των 49, λαμβάνοντας ως A το πλήθος των πορτοκαλιών στη πρώτη κούτα που διελέγχτηκε και ως B το πλήθος των μήλων στη δεύτερη. Από τις δυο ομάδες που σχηματίστηκαν διαλέγουμε εκείνη στην οποία ο συνολικός αριθμός μπανανών δεν είναι λιγότερος από το συνολικό αριθμό μπανανών των κουτών της άλλης.

Εύκολα βλέπουμε, ότι διαλέγοντας τις 1+1+49=51 κούτες, έχουμε διαλέξει τουλάχιστον το μισό αριθμό των συνολικών πορτοκαλιών, τουλάχιστον το μισό συνολικό αριθμό των μήλων και τουλάχιστον το μισό συνολικό αριθμό μπανανών.

Σκιαγραφείτε και μια δεύτερη λύση ( από αναγνώστη) ως σχόλιο με παρόμοια (ίδια) ιδέα με αυτή που περιέγραψε ο κ. Δημήτρης παραπάνω.

Η λύση αυτή στηρίζεται στο λεγόμενο Ham sandwich theorem: για οποιαδήποτε τρία σώματα στο χώρο υπάρχει επίπεδο, που διαιρεί τον όγκο καθενός εξ αυτών των σωμάτων στο ήμισυ. Τοποθετούμε τις κούτες στο χώρο έτσι, ώστε κανένα επίπεδο να μην τέμνει πάνω από τρεις κούτες. Ως σώματα θα θεωρήσουμε την ένωση όλων των πορτοκαλιών, την ένωση όλων των μήλων και την ένωση όλων των μπανανών. Τώρα αν φέρουμε το επίπεδο που διαιρεί και τα τρία σώματα κατά το ήμισυ, τότε στη μια πλευρά αυτού θα βρεθούν τουλάχιστον 49 κούτες. Διαλέγοντας, όλες τις κούτες εκτός από αυτές, προκύπτει η ζητούμενη ομάδα κουτών. Σημειώνεται επίσης ότι στη γενίκευση του προβλήματος για  k είδη φρούτων και για αρκούντος μεγάλο αριθμό κουτών N η απάντηση είναι ο ελάχιστος ακέραιος που δεν είναι μικρότερος του \dfrac{N+k-1}{2}.


Το πρόβλημα μου άρεσε αρκετά, άλλωστε ψηφίστηκε από τους αναγνώστες ως το καλύτερο της χρονιάς, και είπα να το μοιραστώ.

Για τους ανήσυχους υπάρχει το βιβλίο Using the Borsuk-Ulam theorem, Matousek J., που φαίνεται να είναι ενδιαφέρον και διαπραγματεύεται τοπολογικές μεθόδους στην επίλυση προβλημάτων συνδιαστικής.

Υπάρχει και το φυλλάδιο "Εικασία του Kneser και τοπολογικές μέθοδοι στην συνδιαστική" δυστυχώς στα ρωσικά, που διαπαραγματεύεται μερικές από τις ιδέες που ανέφερε ο κ.Δημήτρης στην λύση του με ποιο εκλαϊκευμένο τρόπο. (το φυλλάδιο είναι για μαθητές καλοκαιρινού σχολείου)
τελευταία επεξεργασία από Al.Koutsouridis σε Τετ Αύγ 14, 2019 7:45 pm, έχει επεξεργασθεί 3 φορές συνολικά.


Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8181
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Φρουτεμπορική

#4

Μη αναγνωσμένη δημοσίευση από Demetres » Δευ Αύγ 12, 2019 11:39 am

Πολύ ωραία απόδειξη. Ευχαριστώ!


Απάντηση

Επιστροφή σε “Συνδυαστική - Προχωρημένο Επίπεδο (Seniors)”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης