Συνάρτηση σε δυναμοσύνολο

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

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

Συνάρτηση σε δυναμοσύνολο

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Ιαν 31, 2018 9:40 pm

Έστω \mathcal{P}_n το σύνολο όλων των υποσυνόλων του \{1,2,\ldots,n\}. Ορίζουμε ως c(n,m) το σύνολο όλων των συναρτήσεων f: \mathcal{P}_n \to \{1,2,\ldots,m\} ώστε f(A \cap B) = \min\{f(A),f(B)\} για κάθε A,B \in \mathcal{P}_n.

Να αποδειχθεί ότι

\displaystyle   c(n,m) = \sum_{j=1}^m j^n

Επεξεργασία: Διόρθωση σοβαρότατου τυπογραφικού. Δεν είναι γινόμενο αλλά άθροισμα. :oops: Ευχαριστώ τον Δημήτρη Σκουτέρη που το πρόσεξε.



Λέξεις Κλειδιά:
Άβαταρ μέλους
emouroukos
Γενικός Συντονιστής
Δημοσιεύσεις: 1379
Εγγραφή: Δευ Δεκ 22, 2008 1:27 pm
Τοποθεσία: Αγρίνιο

Re: Συνάρτηση σε δυναμοσύνολο

#2

Μη αναγνωσμένη δημοσίευση από emouroukos » Πέμ Φεβ 01, 2018 2:46 pm

Έστω \displaystyle {X_n} = \left\{ {1,2, \ldots ,n} \right\} και \displaystyle X_n^i = {X_n} \setminus \left\{ i \right\} για κάθε \displaystyle i \in \left\{ {1,2, \ldots ,n} \right\}. Συμβολίζουμε με \cal{A} το σύνολο των συναρτήσεων f με τη δοσμένη ιδιότητα και \cal{B} το σύνολο όλων των διατεταγμένων (n+1)-δων \displaystyle \left( {k,{k_1},{k_2}, \ldots ,{k_n}} \right), όπου \displaystyle {k,{k_1},{k_2}, \ldots ,{k_n} \in {X_m}} με \displaystyle {k \ge {k_i}} για κάθε \displaystyle i \in \left\{ {1,2, \ldots ,n} \right\}.

Ισχυρισμός: Η απεικόνιση

\displaystyle \varphi :{\cal{A}} \to {\cal{B}}:f \mapsto \varphi \left( f \right): = \left( {f\left( {{X_n}} \right),f\left( {X_n^1} \right),f\left( {X_n^2} \right), \ldots ,f\left( {X_n^n} \right)} \right)

είναι 1-1 και επί.

Απόδειξη του Ισχυρισμού: Η \varphi είναι καλά ορισμένη, αφού αν f \in \cal{A} τότε για κάθε \displaystyle i \in \left\{ {1,2, \ldots ,n} \right\} ισχύει

\displaystyle f\left( {X_n^i} \right) = f\left( {X_n^i \cap {X_n}} \right) = \min \left\{ {f\left( {X_n^i} \right),f\left( {{X_n}} \right)} \right\} \le f\left( {{X_n}} \right).

Θεωρούμε την απεικόνιση

\displaystyle \psi :{\cal{B}} \to {\cal{A}}:\left( {k,{k_1},{k_2}, \ldots ,{k_n}} \right) \mapsto \psi \left( {k,{k_1},{k_2}, \ldots ,{k_n}} \right): = f,

όπου \displaystyle f:{\cal{P}} \left( {{X_n}} \right) \to {X_m} η συνάρτηση που ορίζεται από τις σχέσεις:

\displaystyle {f\left( {{X_n}} \right) := k}

και

\displaystyle f\left( Y \right): = \min \left\{ {{k_i}:i \notin Y} \right\}

για κάθε γνήσιο υποσύνολο \displaystyle Y του \displaystyle {{X_n}}.

Επειδή για κάθε A, B \in {\cal{P}} \left( {{X_n}} \right) ισχύει

\displaystyle \left\{ {{k_i}:i \notin A \cap B} \right\} = \left\{ {{k_i}:i \notin A} \right\} \cup \left\{ {{k_i}:i \notin B} \right\},

έπεται ότι \displaystyle f\left( {A \cap B} \right) = \min \left\{ {f\left( A \right),f\left( B \right)} \right\} και άρα η \psi είναι καλά ορισμένη.

Από την υπόθεση, έπεται ότι για κάθε f \in \cal{A} και κάθε γνήσιο υποσύνολο \displaystyle Y του \displaystyle {{X_n}} ισχύει

\displaystyle f\left( Y \right) = f\left( {\bigcap\limits_{i \notin Y} {X_n^i} } \right) = \min \left\{ {f\left( {X_n^i} \right):i \notin Y} \right\}.

Άρα, οι συναρτήσεις \displaystyle \varphi και \displaystyle \psi είναι αντίστροφες, οπότε ο ισχυρισμός έπεται.

Επομένως, αρκεί να βρούμε το πλήθος των στοιχείων του \cal{B}. Για κάθε \displaystyle k \in {X_m}, το πλήθος των n-άδων \displaystyle \left( {{k_1},{k_2}, \ldots ,{k_n}} \right) με \displaystyle {k_i} \in {X_m} και \displaystyle {k_i} \le k για κάθε \displaystyle i \in \left\{ {1,2, \ldots ,n} \right\} είναι ίσο με \displaystyle {k^n}. Επομένως, από την προσθετική αρχή, είναι

\displaystyle c\left( {n,m} \right) = \left|  {\cal{A}} \right| = \left|  {\cal{B}} \right| = \sum\limits_{k = 1}^m {{k^n}}

και το ζητούμενο δείχθηκε.


Βαγγέλης Μουρούκος

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

Re: Συνάρτηση σε δυναμοσύνολο

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Φεβ 01, 2018 5:11 pm

Ωραία. Ήταν η άσκηση Α3 του διαγωνισμού Putnam του 1993.


silouan
Επιμελητής
Δημοσιεύσεις: 1183
Εγγραφή: Τρί Ιαν 27, 2009 10:52 pm

Re: Συνάρτηση σε δυναμοσύνολο

#4

Μη αναγνωσμένη δημοσίευση από silouan » Πέμ Φεβ 01, 2018 7:26 pm

Ας δούμε και την ακόλουθη:
Έστω \mathcal{F} το σύνολο των συναρτήσεων f : \mathcal{P}(S) \longrightarrow \mathbb{R} ώστε για κάθε X, Y \subseteq S, έχουμε f(X \cap Y) = \min (f(X), f(Y)), όπου S είναι ένα πεπερασμένο σύνολο (και \mathcal{P}(S) το δυναμοσύνολο). Να βρεθεί το
\displaystyle \max_{f \in \mathcal{F}}| \textrm{Im}(f) |.


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

Re: Συνάρτηση σε δυναμοσύνολο

#5

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Φεβ 01, 2018 9:58 pm

Σιλουανέ, δεν είναι προφανές από την λύση του Βαγγέλη ότι το μέγιστο είναι |S|+1; Ή χάνω κάτι;


silouan
Επιμελητής
Δημοσιεύσεις: 1183
Εγγραφή: Τρί Ιαν 27, 2009 10:52 pm

Re: Συνάρτηση σε δυναμοσύνολο

#6

Μη αναγνωσμένη δημοσίευση από silouan » Παρ Φεβ 02, 2018 12:53 am

Ναι, Δημήτρη!
Το πρόβλημα είναι από Διαγωνισμό Επιλογής της Ρουμανίας 2007, απλά ήθελα να αναδείξω τη σύνδεση.
https://artofproblemsolving.com/communi ... 150p848051


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

Re: Συνάρτηση σε δυναμοσύνολο

#7

Μη αναγνωσμένη δημοσίευση από Demetres » Παρ Φεβ 02, 2018 5:04 pm

silouan έγραψε:
Πέμ Φεβ 01, 2018 7:26 pm
Ας δούμε και την ακόλουθη:
Έστω \mathcal{F} το σύνολο των συναρτήσεων f : \mathcal{P}(S) \longrightarrow \mathbb{R} ώστε για κάθε X, Y \subseteq S, έχουμε f(X \cap Y) = \min (f(X), f(Y)), όπου S είναι ένα πεπερασμένο σύνολο (και \mathcal{P}(S) το δυναμοσύνολο). Να βρεθεί το
\displaystyle \max_{f \in \mathcal{F}}| \textrm{Im}(f) |.

Ας δούμε και μια διαφορετική απόδειξη. Αν f(A) = f(\emptyset) για κάθε A, δεν έχω κάτι να δείξω. Αλλιώς παίρνω A με ελάχιστο μέγεθος ώστε f(A) \neq f(\emptyset).

Αν το B δεν περιέχει το A, τότε |B \cap A| < |A|, οπότε f(\emptyset) = f(A \cap B) = \min\{f(A),f(B)\}. Αφού f(A) \neq f(\emptyset), τότε f(B) = f(\emptyset).

Αν το B περιέχει το f(A), από την επαγωγική υπόθεση στο σύνολο S' = S \setminus A, το f(B) παίρνει το πολύ |S| - |A| + 1 διαφορετικές τιμές. [Επειδή ισχύει ότι f((B \cap C) \setminus A) = \min\{f(B \setminus A),f(C \setminus A)\}.]

Συνολικά λοιπόν η εικόνα της f έχει το πολύ 1 + |S| - |A| + 1 \leqslant |S| + 1 στοιχεία.


Απάντηση

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

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

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