المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۳:سوال ۵

سوال ۵

فرض کنید $n$ یک عدد طبیعی بزرگ‌تر از یک باشد. ثابت کنید برای

$$k=\lceil 3\times ( \frac{3}{2} )^{n-2} \rceil$$

دنباله‌ی $A_1,A_2,…,A_k$ وجود دارد بطوری که

$$A_i \subseteq \{1,2,…,n\} \quad , \quad A_i \ne A_j \\ , |A_i \vartriangle A_j |=1 \Longleftrightarrow |i-j|=1 \quad , \quad 1\leq i,j\leq n$$

منظور از $A_i \vartriangle A_j$ تفاضل متقارن $A_i$ و $A_j$ یعنی $(A_i – A_j) \cup (A_j –A_i)$ است. همچنین $\lceil n \rceil$ نمایانگر کوچک‌ترین عدد صحیح ناکم‌تر از $n$ است.

مثال: در حالت $n=3$ خواهیم داشت $k=5$ و دنباله‌ی مورد نظر می‌تواند به صورت زیر باشد:

$$A_1=\{ \} \quad , \quad A_2=\{ 1 \} \quad , \quad A_3=\{1,2 \} \quad , \quad A_4=\{1,2,3\} \quad , \quad A_5=\{2,3\}$$

راهنمایی: می‌توانید از استقرا استفاده نمایید.


ابزار صفحه