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

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

  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 στοιχεία

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

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