You are not allowed to perform this action
سوال ۶
فرض کنید $A\subseteq \{0,1\}^n$ و $|A|=a$ و $v \in A$.(پس بردار $v$ دارای $n$ مولفه است که میتوانیم آنها را با اعداد $\{1,2,…,n\}$ شمارهگذاری کنیم.) میگوییم مجموعهی $S$ از مولفهها بردار $v$ را تعیین میکند، اگر تو تنها اگر نتوانیم عضوی غیر از $v$ در $A$ پیدا کنیم که در تمام مولفههای عضو $S$ مانند $v$ باشد.
- ثابت کنید عضوی در $A$ هست که حداکثر با $lg_2a$ مولفه قابل تعیین است.
- ثابت کنید که میتوان مجموعهای از مولفهها مثل $S$ پیدا کرد که اولا $|S| \leq a-1$ و ثانیا $S$ برای تمام اعضای $A$ تعیینکننده باشد.