Ο γρίφος της ημέρας – Τρία σύνολα (για πολύ καλούς λύτες)

Στα σύνολα Α, Β, Γ παρατηρούνται τα ακόλουθα:

  1. Τα σύνολα Α και Β έχουν από 100 στοιχεία το καθένα.

  2. Το πλήθος των υποσυνόλων τού Α συν το πλήθος των υποσυνόλων τού Β συν το πλήθος των υποσυνόλων τού Γ ισούται με το πλήθος των υποσυνόλων της ένωσης των τριών συνόλων.

Πόσα τουλάχιστον στοιχεία έχει η τομή των τριών συνόλων;

προτάθηκε από τον Θανάση Παπαδημητρίου 

3 σχόλια

  1. Στράτος Απάντηση

    Το πλήθος των υποσυνόλων ενος συνόλου ν στοιχείων ισούται με 2^ν. Επομένως, αν α τα στοιχεία του συνόλου Γ, και β τα στοιχεια της ένωσης των τριών συνόλων, έχουμε:

    2^100+2^100+2^α=2^β, που καταλήγει σε α=101, β=102

    Για την ενωση και τη τομή τριών συνόλων ισχύει:

    AUBUΓ=A+B+Γ-Α∩Β-Α∩Γ-Β∩Γ+Α∩Β∩Γ

    Παρατηρούμε ότι:

    Α∩Β>=98
    Α∩Γ>=99
    Β∩Γ>=99

    Επομένως:

    Α∩Β∩Γ>=98+99+99+102-100-100-101, δηλαδή Α∩Β∩Γ>=97

  2. ΚΣ Απάντηση

    ‘Εστω χ,το πληθος των στοιχείων του Γ. Αθροίζοντας τα επιμέρους σύνολα έχουμε 2^100+2^100+2^χ= 2^101+2^χ κ βάσει της εκφώνησης αυτό θα πρέπει να ισούται με 2^ψ, όπου ψ το πλήθος των στοιχείων του συνόλου της ένωσης. Αυτό ισχύει μόνο στην τιμή χ=101 => 2^101+2^101=2^102.
    Με τουλάχιστον 97 κοινά στοιχεία το ζητούμενο είναι εφικτό. Με 96, χρειάζεται τα 5 στοιχεία του Γ να συνδυαστούν με κάποια του Α (4) και του Β (4) και να προκύψουν συνολικά 6 στοιχεία, κατάσταση που δεν είναι εφικτή. Αφού αν “απορροφηθούν” τα 5 στοιχεία του Α, θα πρέπει με τα 4+4-5=3 στοιχεία να υπάρξει μόνο 1 επιπλέον στοιχείο, όχι κοινό και στα τρία σύνολα.

  3. Θανάσης Παπαδημητρίου Απάντηση

    Στράτο, Κωστή, είστε μεγιστοτιτανοτεράστιοι!
    Επιτρέψτε μου μόνο να δείξω σε απλή (ελπίζω) γλώσσα το γιατί όχι λιγότερο από 97:

    Από τα 102 στοιχεία της ένωσης(Α,Β,Γ), αφού τα σύνολα Α και Β έχουν από 100 στοιχεία το καθένα, θα έχουν τουλάχιστον τα 98 στοιχεία κοινά, αλλιώς η ένωση(Α,Β,Γ) θα είχε τουλάχιστον 3+97+3=103 στοιχεία, άτοπο. Συνεπώς η τομή(Α,Β) έχει 98 τουλάχιστον στοιχεία.
    Επίσης, για να έχει το σύνολο Γ ακριβώς 101 στοιχεία, θα πρέπει να έχει όλα τα στοιχεία της ένωσης(Α,Β,Γ) εκτός από ένα. Αν το στοιχείο της ένωσης που λείπει από το Γ ΔΕΝ είναι στοιχείο της τομής(Α,Β), τότε η τομή(Α,Β,Γ) δεν μπορεί να έχει λιγότερα από 98 στοιχεία. Αν όμως το στοιχείο που λείπει από το Γ είναι στοιχείο της τομής(Α,Β), τότε η τομή(Α,Β,Γ) περιορίζεται στα 98-1=97 στοιχεία. Πιο κάτω αποκλείεται..

    Παράδειγμα ελαχίστου
    Α = {1,2,3,…,100} -> 100 στοιχεία
    Β = {3,4,5,…,102} -> 100 στοιχεία
    Γ = {1,2,4,5,..,100,101,102} -> 101 στοιχεία
    Ένωση(Α,Β,Γ) = {1,2,3,…,102} -> 102 στοιχεία
    Τομή(Α,Β) = {3,4,5,…,100} -> 98 στοιχεία
    Τομή(Α,Β,Γ) = {4,5,…,99,100} -> 97 στοιχεία

Αφήστε μια απάντηση

Η ηλ. διεύθυνση σας δεν δημοσιεύεται. Τα υποχρεωτικά πεδία σημειώνονται με *