سوال ۲۱
مجموعه $S=\{1,2,\ldots 6\}$ مفروض است. $T$ یک تابع است که به هر یک از زیرمجموعه‌های $S$ یکی از زیرمجموعه‌های $S$ را نسبت می‌دهد. چند تابع $T$ وجود دارد که دارای خاصیت زیر است؟ $$\forall P,Q\subseteq S: P\subseteq Q \Leftrightarrow T(P)\subseteq T(Q)$$
- $2$
- $64$
- $720$
- $64!$
- $2^{6\times64}$
پاسخ
گزینه (۳) درست است.
به راحتی قابل درک است که $T(\varnothing)=\varnothing$ و $T(S)=S$. حاصل $T(\{5\})،T(\{4\})،T(\{3\})،T(\{2\})،T(\{1\})$ و $T(\{6\})$ را به دلخواه $\{5\}،\{4\}،\{3\}،\{2\}،\{1\}$ و $\{6\}$ در نظر می‌گیریم که این کار به $6!$ یعنی ۷۲۰ طریق ممکن است.
حال اگر فرض کنیم $T(\{x_n\})=\{y_n\}،...،T(\{x_2\})=\{y_2\}،T(\{x_1\})=\{y_1\}$، از مجموعه‌های دو عضوی به بعد عضو متناظر به هر زیر مجموعه به صورت منحصر به فرد به شکل زیر پیدا می‌شود:
$$T( \{ x_{i_1},x_{i_2},...,x_{i_k} \}) = \{y_{i_1},y_{i_2},...,y_{i_k} \}$$
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
