$n$ فرد با نام‌های $a_1,…,a_n$ هر کدام خبری را در اختیار دارند. خبر فرد $i$ ام را $b_i$ می‌نامیم. توجه کنید که $b_i$ ها در حالت کلی باهم متفاوتند.

دو نفر می‌توانند با هم تماس بگیرند. اگر $a_i$ با $a_j$ تماس بگیرد و $a_i$ قبل از تماس خبرهای $\beta_i$ و $a_j$ خبرهای $\beta_ j $ را داشته باشند ($\beta_i$ و $\beta_ j $ مجموعه‌هایی از خبرهای اولیه، $b_i$ ها، هستند.) پس از تماس، هر دو دارای خبرهای $\beta_i \cup \beta_ j$ خواهند شد. به عبارتی خبرهای خود را به یک‌دیگر منتقل می‌کنند.

یک مرحله از خبرپراکنی، تماس هم‌زمان و دو به دوی این $n$ نفر با هم می‌باشد. توجه کنید که در یک مرحله از خبرپراکنی یک فرد نمی‌تواند با بیش از یک نفر دیگر تماس بگیرد.

هدف مسئله این است که پیدا کنیم در چند مرحله و چگونه می‌توان خبرهای اولیه، $b_i$ ها، را در اختیار همه‌ی $a_i$ ها قرار داد.

الف) اگر $n=7$ باشد حداقل تعداد مراحل برای خبرپراکنی را به‌دست آورید و نیز نشان دهید که در هر مرحله چه افرادی باید با هم تماس بگیرند.

ب) حداقل تعداد مراحل را برای $n=2^k$ به‌دست آورده اثبات نمایید. (نحوه‌ی ایجاد تماس‌ها در این قسمت خواسته نشده است.)

$I-4$: ۳ وارد پشته می‌شود.

$I-5$: ۴ وارد پشته می‌شود.

$O-6$: پشته خالی می‌شود (ابتدا ۴ و سپس ۳ از پشته خارج می‌شوند).

الف) نشان دهید که آیا دنباله‌ی $2,1,3,6,4,5$ قابل تولید از دنباله‌ی $1,2,3,4,5,6$ می‌باشد یا خیر؟ دنباله‌ی $3,2,1,5,4,6$ چطور؟ در صورت مثبت بودن پاسخ، ترتیب انجام اعمال $I$ و $O$ را مشخص کنید. در غیر این صورت ادعای خود را ثابت کنید.

ب) اگر $t_n$ تعداد دنباله‌های قابل تولید از دنباله‌ی $1,2,…,n$ باشد، $t_n$ را به صورت یک فرمول صریح بر حسب $n$ محاسبه نمایید. (الگوریتم لازم نیست.)

ج) یک جایگشت $a_1,…,a_n$ از اعداد ۱ تا $n$ از اعداد ۱ تا $n$ داده شده است. برنامه‌ای بنویسید که مشخص کند آیا این دنباله‌ قابل تولید از دنباله‌ی $1,2,…,n$ است یا خیر. اعداد دنباله به ترتیب چپ به راست به صورت ورودی به برنامه‌ی شما داده می‌شود. خروجی باید در صورت قابل تولید بودن دنباله، کلمه‌ی YES و سپس رشته‌ای از $I$ و $O$ باشد به طوری که با انجام این اعمال، به ترتیب، بتوان دنباله‌ی مورد نظر را تولید کرد. اگر دنباله قابل تولید نباشد خروجی برنامه‌ی شما باید کلمه‌ی NO باشد.

د) در این بند فرض کنید که هر عمل $O$، خرج نمودن فقط یک واگن از پشته است (و نه تمامی آن‌ها). در این صورت اگر $S_i$ تعداد دنباله‌های قابل تولید از دنباله‌ی $1,2,…,i$ باشد، $s_n$ را به صورت فرمولی بر حسب $s_i$، $(i<n)$، محاسبه نمایید. (الگوریتم لازم نیست.)

• سوال بعد
• سوال قبل