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

#1

Έστω $\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$

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

Ευχαριστώ τον Δημήτρη Σκουτέρη που το πρόσεξε.

#2

Έστω $\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}$ το σύνολο των συναρτήσεων

με τη δοσμένη ιδιότητα και $\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},$ το πλήθος των

-άδων $\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}}$

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

#3

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

#4

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

είναι ένα πεπερασμένο σύνολο (και $\mathcal{P}(S)$ το δυναμοσύνολο). Να βρεθεί το
$\displaystyle \max_{f \in \mathcal{F}}| \textrm{Im}(f) |.$

#5

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

; Ή χάνω κάτι;

#6

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

#7

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))$ , όπου είναι ένα πεπερασμένο σύνολο (και $\mathcal{P}(S)$ το δυναμοσύνολο). Να βρεθεί το
$\displaystyle \max_{f \in \mathcal{F}}| \textrm{Im}(f) |.$

Ας δούμε και μια διαφορετική απόδειξη. Αν $f(A) = f(\emptyset)$ για κάθε

, δεν έχω κάτι να δείξω. Αλλιώς παίρνω

με ελάχιστο μέγεθος ώστε $f(A) \neq f(\emptyset)$ .

Αν το

δεν περιέχει το

, τότε $|B \cap A| < |A|$ , οπότε $f(\emptyset) = f(A \cap B) = \min\{f(A),f(B)\}$ . Αφού $f(A) \neq f(\emptyset)$ , τότε $f(B) = f(\emptyset)$ .

Αν το

περιέχει το 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)\}$ .]

Συνολικά λοιπόν η εικόνα της

έχει το πολύ $1 + |S| - |A| + 1 \leqslant |S| + 1$ στοιχεία.

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

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

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

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

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

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

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

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

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