اول از همه بگم که تگ استقرا خیلی گول زننده بود. من کلی سعی کردم با استقرا حل کنم ولی آخر سر بدون استقرا حل شد :) اگه شما هم مثل من رو استقرا فکر کردین و حل نشد، قبل از اینکه راه حل رو بخونین یه بار دیگه فکر کنین شاید بدون استقرا حل شد. کلا هرجای راه‌حل احساس کردید بقیه‌اش رو خودتون می‌تونید حدس بزنید، خوبه دیگه ادامه‌ی راه‌حل رو نخونید و فکر کنید.

حالا بریم سراغ راه‌حل:

فرض کنیم $n$ نفر داریم و تونستیم با $k$برنامه کاری کنیم که هرکسی حداقل یه بار هرکس دیگه رو روی سن دیده باشه. حالا می‌تونیم جواب رو با $n$تا دنباله‌ی دودویی به طول $k$ مدل کنیم. این طوری که اگه نفر $i$ در برنامه‌ی $j$ام روی سن رفته بود، بیت $j$ام از دنباله‌ی $i$ رو یک می‌ذاریم، وگرنه صفر می‌ذاریم. حالا تو این مدل جدید، مسئله به این تبدیل می‌شه که $n$تا دنباله به طول $k$ پیدا کنید به طوری که به ازای هر دو دنباله مثل $v$ و $u$، اندیس $1 \le i \le k$ وجود داشته باشد به طوری $u_i$ یک باشد و $v_i$ صفرباشد و $k$ هم کمینه باشد.

خب اول برای $n$های کوچیک می‌بینیم $k$ چند می‌شه.

برای $n=2$: دوتا دنباله ۰۱ و ۱۰. پس $k=2$

برای $n=3$: ۳ تا دنباله ۱۰۰ و ۰۱۰ و ۰۰۱. پس $k=3$

برای $n=4$: ۴تا دنباله ۱۱۰۰ و ۱۰۱۰ و ۱۰۰۱ و ۰۱۰۱. پس $k=4$

برای $n=5$: ۵تا دنباله ۱۱۰۰ و ۱۰۱۰ و ۱۰۰۱ و ۰۱۰۱ و ۰۱۱۰. پس $k=4$

برای $n=6$: ۶تا دنباله ۱۱۰۰ و ۱۰۱۰ و ۱۰۰۱ و ۰۱۱۰ و ۰۱۰۱ و ۰۰۱۱. پس $k=4$

برای $n=7$: تو این حالت نمی‌شه با دنباله‌های ۴بیتی مساله رو حل کرد. چرا؟

اگه دقت کنیم می‌فهمیم که ما داریم جوری توی دنباله‌ها ۱ قرار می‌دیم که اندیس‌های یک هیچ دنباله‌ای زیرمجموعه‌ی اندیس‌های یک دنباله‌ی دیگه نباشه. درواقع شرط مساله برقراره، اگر و فقط اگر هیچ دو دنباله‌ای نباشند که ۱های یکی زیرمجموعه‌ی ۱های دیگری باشه.

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

این مساله به قضیه اسپرنر معروفه. درواقع اسپرنر ثابت می‌کنه، اگه مجموعه‌مون $k$تا عضو داشته باشد، حداکثر تعداد زیرمجموعه‌هایی که دوبه دو زیرمجموعه‌ی هم نیستند $k \choose k/2$ هست. اثبات اینکه این تعداد وجود داره ساده‌ است. اثبات اینکه از این بیشتر نمی‌شه رو از لینکی که گذاشتم بخونید.

بنابراین تو مساله‌ی ما، تعداد برنامه‌ها یا همون $k$ باید اون قدر باشه که ${k \choose {k/2}} \ge n$

پس اگه $n=7$ باشه، ۴ برنامه جواب نمی‌ده. چون $4 \choose 2$ از ۷ کمتره. اما ۵تا جواب می‌ده. چون $5 \choose 2$ از ۷ بیشتره. درواقع اگه حداکثر ۱۰ نفر آدم داشته باشیم با ۵تا برنامه مساله حل می‌شه. اگه ۲۰تا آدم داشته باشیم با ۶تا برنامه حل می‌شه و ...