\(\)Χρόνια πολλά σε όλους.
Μια μικρή υπόδειξη για όσους προσπαθούν την άσκηση 60:
\(\)Υπόδειξη για τη λύση της άσκηση 60-atoms-XX
Η εκφώνηση λέει το εξής: δίνεται ένα $N$ (φυσικός αριθμός) και κάποια υποσύνολα του $\Set{1, 2, \ldots, N}$, των οποίων το σύνολο το ονομάζουμε, έστω, $X$ (τα στοιχεία του $X$ είναι λοιπόν υποσύνολα του $\Set{1, 2, \ldots, N}$).
Ένα υποσύνολο $A \subseteq \Set{1, 2, \ldots, N}$ λέγεται άτομο
(*) αν όποιο στοιχείο $S \in X$ και να πάρουμε είτε $A \subseteq S$ είτε $A \cap S = \emptyset$
και επιπλέον αν δε μπορεί να μεγαλώσει άλλο και να εξακολουθεί να έχει αυτή την ιδιότητα (είναι όπως λέμε μεγιστικό με αυτή την ιδιότητα).
Να υπολογιστούν όλα τα άτομα.
Παρατήρηση: Με τον ορισμό αυτό το κενό σύνολο δεν είναι άτομο γιατί δεν είναι μεγιστικό.
Το παρακάτω Λήμμα θα σας είναι χρήσιμο.
Λήμμα 1: Αν $x, y \in \Set{1, 2, \ldots, N}$ τότε τα $x, y$ ανήκουν στο ίδιο άτομο αν και μόνο αν ανήκουν ακριβώς στα ίδια σύνολα του $X$.
Απόδειξη: Ας υποθέσουμε πρώτα ότι τα $x, y$ ανήκουν στο $A \subseteq \Set{1, 2, \ldots, N}$ που είναι άτομο. Ας πούμε λοιπόν ότι $x \in S \in X$. Αφού το $A$ είναι άτομο και δεν είναι ξένο προς το $S$ (αφού έχουν το $x$ κοινό στοιχείο) έπεται ότι $A \subseteq S$ και άρα έχουμε και $y \in S$. Δείξαμε λοιπόν ότι αν το ένα από τα $x, y$ ανήκει σε κάποιο στοιχείο του $X$ τότε ανήκει και το άλλο. Άρα τα $x, y$ ανήκουν ακριβώς στα ίδια στοιχεία του $X$.
Για την αντίστροφη κατεύθυνση ορίζουμε το σύνολο $A \subseteq \Set{1, 2, \ldots, N}$ να αποτελείται από όλα τα στοιχεία του $\Set{1, 2, \ldots, N}$ που ανήκουν ακριβώς στα στοιχεία του $X$ όπου ανήκει και το $x$. To $Α$ προφανώς περιέχει και το $y$. Θα δείξουμε ότι το $A$ είναι άτομο. Έστω $S \in X$ λοιπόν. Θα πρέπει να δείξουμε ότι είτε $A \subseteq S$ είτε $A \cap S = \emptyset$.
Περίπτωση 1: $x \in S$: Τότε εκ κατασκευής του $A$ έχουμε $A \subseteq S$ (αφού όλα τα στοιχεία του $A$ ανήκουν όπου και το $x$ και άρα ανήκουν και στο $S$).
Περίπτωση 2: $x \notin S$: Τότε κανένα στοιχείο του $A$ δεν ανήκει στο $S$, αφού το $x$ δεν ανήκει και όλα τα στοιχεία του $A$ ανήκουν στα ίδια σύνολα. Άρα $A \cap S = \emptyset$.
Απομένει να δειχτεί ότι το $A$ είναι μεγιστικό, δε μπορούμε δηλ. να προσθέσουμε ένα στοιχείο $z$ ακόμη και να διατηρεί την ιδιότητα (*). Αν $z \notin A$ αυτό σημαίνει ότι υπάρχει σύνολο $S \in X$ τέτοιο ώστε είτε $z \in S, z \notin S$ είτε $z \notin S, x \in S$. Σε κάθε μια από τις δυο περιπτώσεις παύει να ισχύει η ιδιότητα (*) για το σύνολο $S$ αν προσθέσουμε το $z$ στο $A$. Άρα το $A$ είναι μεγιστικό με την ιδιότητα (*).
Η απόδειξη είναι πλήρης.