25 Απρ 2011

Υποσύνολα με το ίδιο άθροισμα

Παίρνουμε 10 διαφορετικούς ακεραίους από το 1 μέχρι και το 100. Ζητούμε να εξετάσουμε αν από αυτό το σύνολο με τους 10 διαφορετικούς ακεραίους μπορούμε να βρούμε πάντα δύο υποσύνολα, το άθροισμα των στοιχείων των οποίων να είναι ίσο.


Για παράδειγμα ας είναι S = {1, 4, 5, 14, 17, 33, 41, 49, 68, 79, 88}.
Τότε αν θεωρήσουμε τα υποσύνολα Α1 και Α2 του S με Α1 = {5, 14, 17, 33} και Α2 = {1, 68}, παρατηρούμε ότι
5+14+17+33 = 1+68.  

4 σχόλια:

  1. Αν επιλεγούν 10 διαφορετικοί αριθμοί, τότε το σύνολο που συνθέτουν μπορεί να έχει $2^{10}$ υποσύνολα. Ο πλήθος αυτό των υποσυνόλων προκύπτει αν αναπαραστήσουμε τη συμμετοχή ενός αριθμού στο υποσύνολο με το δυαδικό 1 και τη μη συμμετοχή του με 0. Άρα η σύνθεση ενός υποσυνόλου κωδικοποιείται με ένα 10-μπητο αριθμό με δεκαδική τιμή από 0 έως $2^{10}-1$ δηλαδή $2^{10}$ αριθμούς στο σύνολο.

    Το κενό υποσύνολο καθώς και το "πλήρες" υποσύνολο με όλους τους δέκα αριθμούς δεν λαμβάνονται υπόψην γιατί το μεν κενό έχει άθροισμα μελών 0 ενώ το "πλήρες" έχει άθροισμα μελών που είναι σίγουρα μεγαλύτερο από το αντίστοιχο άθροισμα οποιουδήποτε άλλου υποσυνόλου. Έτσι, έχουμε τελικά $2^{10}-2=1022$ διαφορετικά πιθανά υποσύνολα του αρχικού συνόλου των 10 αριθμών.

    Κάθε υποσύνολο αντιστοιχεί σε έναν αριθμό που είναι το άθροισμα των μελών του. Άρα έχουμε 1022 αθροίσματα-εικόνες των συνολικών υποσυνόλων.

    Αν αποδείξουμε ότι το πλήθος των αθροισμάτων-εικόνων που μπορούν να προκύψουν από τουλάχιστον μονομελή υποσύνολα και κατά μέγιστο 9-μελή υποσύνολα του συνόλου των εκατό αριθμών 1,2,...,100 είναι μικρότερο από 1022 τότε τελειώσαμε.

    Το μονομελές υποσύνολο με το μικρότερο άθροισμα-εικόνα είναι το {1} με άθροισα 1, ενώ το 9-μελές υποσύνολο με το μεγαλύτερο άθροισμα είναι το {100, 99, ...,92} με άθροισμα 864.

    Άρα το πεδίο άφιξης του αθροίσματος μελών έχει 864 στοιχεία. Συνεπώς, από τα 1022 πιθανά υποσύνολα των 10 τυχαία επιλεγμένων διαφορετικών αριθμών τουλάχιστον δύο έχουν το ίδιο άθροισμα-εικόνα. Τα δύο αυτά υποσύνολα Α και Β με ίδιο άθροισμα μελών μπορεί να μην έχουν κενή τομή Γ. Αυτό δεν είναι πρόβλημα. Αρκεί να πάρουμε να υποσύνολα Α'=Α-Γ και Β'=Β-Γ οπότε τα Α' και Β' είναι ξένα και έχουν πάλι ίσο άθροισμα μελών.


    Με τίποτα δεν θα φανταζόμουν ότι αυτή η ιδιότητα ισχύει. Φαίνεται ότι αν το αρχικό σύνολο έχει περισσότερα μέλη από 100 ή αν επιλέγονται λιγότεροι από 10 αριθμοί η ιδιότητα παύει να ισχύει.


    JR

    ΑπάντησηΔιαγραφή
  2. Πολύ ωραία λύση με μία μικρή παρατήρηση. Το μεγαλύτερο άθροισμα το βρίσουμε από το {100,99,...,91} και είναι 955 και όχι από το {100, 99, ...,92}.

    Στη λύση σου χρησιμοποιείς χωρίς να το λες την Αρχή του Περιστερώνα, την οποία είχα προγραμματίσει για κάποιες εβδομάδες πιο μετά αλλά αφού ήρθαν έτσι τα πράγματα, θα την αναρτήσω πιο σύντομα

    ΑπάντησηΔιαγραφή
  3. Sorry, τώρα συνειδητοποίησα ότι εξαίρεσες το άθροισμα των δέκα αριθμών ως αδύνατο να είναι κοινό με άλλο υποσύνολο.

    ΑπάντησηΔιαγραφή
  4. Δεν ξέρω ποια είναι η αρχή του περιστερώνα.

    JR

    ΑπάντησηΔιαγραφή