سوال ۱- جدول n*n از اعداد ۱ تا n داده شده...
سوال ۲- برش نواحی یک جدول n در n
سوال ۳ - رنگ آمیزی دیوار خانه‌ی عمو نقّاش
سوال ۴ - روشی برای انتخاب سالن انتظار در هر روز و دیدن تلویزیون آن در شهر المپیادی‌ها
سوال 5- احداث جاده و مرکز پلیس در شهرهای کشور علی کوچولو
سوال 6- وزن کم ترین زبان n کلمه ای که هم پیشوند -آزاد باشد و هم پسوند-آزاد
سوال ۷- مجموعه‌ی سه تایی های پایدار
سوال 2- قورباغه‌ي پهلوان روی محور اعداد صحیح
سوال ۵- رنگ‌آمیزی پراکنده یک جدول با رنگ‌های سیاه و سفید
در یک جمع $n$ نفره٬ هر دو نفر یا با هم آشنا هستند یا نیستند. فرض کنید افراد با شماره‌های ۲٬۱ تا $n$ نام‌گذاری شده‌اند و آشنایی رابطه‌ای دو طرفه است؛ یعنی اگر $i$ با $j$ آشنا باشد حتماً $j$ هم با $i$ آشناست.
الف) با دانستن تمام روابط آشنایی در یک جمع $n$ نفره٬ دایره‌های دوبه‌دو نامتقاطع $C_n ,...,C_2,C_1$ در صفحه کشیده‌اند به طوری که دایره‌های $C_i$ و $C_j$ متداخل‌اند اگر و فقط اگر بین فرد $i$ و فرد $j$ رابطه‌ی آشنایی وجود داشته باشد. ثابت کنید در این جمع٬ به ازای هر چهار فرد متمایزِ $a$٬ $b$٬ $c$ و $d$٬ که $a$ با $b$٬ $b$ با $c$ و $c$ با $d$ آشناست٬ حتماً یا $a$ با $c$ آشناست یا $b$ با $d$.
ب) جمعی را در نظر بگیرید که در آن به ازای هر چهار فرد متمایز $a$٬ $b$٬ $c$ و $d$٬ که $a$ با $b$٬ $b$ با $c$ و $c$ با $d$ آشناست٬ حتماً یا $a$ با $c$ آشناست یا $b$ با $d$. ثابت کنید با دانستن تمام آشنایی‌های این جمع٬ می‌توان دایره‌های دوبه‌دو نامتقاطع $C_n ,...,C_2,C_1$ در صفحه کشید به طوری که دایره‌های $C_i$ و $C_j$ متداخل باشند اگر و فقط اگر بین فرد $i$ و فرد $j$ در آن جمع رابطه‌ی آشنایی وجود داشته باشد.
برای مثال در شکل زیر افرادی که با پاره‌خط به هم وصل شده‌اند با هم آشنا هستند و دایره‌ها نیز بر همین اساس رسم شده‌اند.
سلام میدونستید انجمن علمی نخبگان دانشگاه صنعتی شریف مسابقه تخصصی مهارت سنجی برنامه نویسی و داده کاوی گذاشته است آدرس سایتش www.fanavard.com
2015-08-06 07:14:17 -0500 امیر شکریسلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه
2016-10-26 11:09:57 -0500 امیر شکریفسمت الف یک حالت بندی سادس برای قسمت ب بدین صورت عمل مکنیم: ابتدا یک لم ثابت میکنیم که در همر مولفه همبندی که شرایط مسله رو داره یک راس وجود داره که بقیه راس ها وصله یعنی دلتا بزرگ برابر n-1 است. حالا میایم از استقرا قوی روی تعداد راس ها استفاده میکنیم اینجوری که میای راس که به همه وصل هست رو تو مولفه همبندی در نظر میگیری به جای یک دایره بزرگ رسم میکنی حالا اون رو حذف مکنی طبق فرض مسله برای بقیه گراف حل می کنی بعد اون هارو داخل دایره بزرگ میگذاری. واضحه که با حذف راس بازم شرط برای هر زیرگراف القای هر مسیر به طول چهار شرط برقراره . حالا اثبات لم : راس با بیشترین درجه رو X مینامیم مجموعه همسایه های X رو A و مجموعه ناهمسایه هاشو B می نامیم حالا چون گراف همبنده یک یال از B به A وجود داره فرض کن B1 در B به A1 در A متصله حالا بیا مسیر های به طول چهار Ai X A1 B1 رو در نظر بگیر برای تمام اعضای A در نظر بگیر چون X به B1 وصل نیست پس A1 به Ai وصله پس A1 به تمام همسایه های X و خود X و B1 وصله پس در جه A1 از X بیشتره و تنقاض حاصل نتیجه میده که مجمومه B تهی است پس دلتا = n-1 .
