سوال 1- دایره اعداد با n عدد حقیقی روی آن
سوال 2- نقشه‌ی قابل ساخت در کشور عجایب
سوال 4- تعداد جای‌گشت‌های قابل‌مرتب‌شدن را به صورت یک فرمول بر حسب k به دست آورید.
سوال 6 - مجموعه x متشکل از اجتماع مجموعه‌های دیگر
سوال ۱ روز دوم مرحله ۲ دوره ۲۳: رشته‌ی نزدیک
بازی رنگی - سوال ۱ - مرحله ۲ - ۱۳۹۳
وزنه‌ها و ماشین جادویی - سوال ۲ - مرحله ۲ - ۱۳۹۳
گاوی خسیس - سوال ۳ - مرحله ۲ - ۱۳۹۳
انتقال مهره‌های گاوی - سوال ۴ - مرحله ۲ - ۱۳۹۳
یافتن کوچکترین پیچ و مهره با مقایسه آنها
شرکتی دوربین‌های عکاسی تولید می‌کند. هر مدل دوربین این شرکت با مجموعه‌ی قابلیت‌هایی که دارد شناخته میشود (یعنی دو دوربین با یک مجموعه‌ی قابلیت٬ از یک مدل محسوب خواهند شد و برعکس). مجموعه‌ی کل قابلیت‌هایی که یک دوربین می‌تواند داشته باشد برابر با مجموعه‌ی $A= {a_1, a_2,..., a_n}$ است.
در سال اول تاسیس٬ این شرکت دوربین‌های مدل $X_1,X_2,...,X_m$ را به بازار ارائه داد که به ترتیب دارای مجموعه‌ی قابلیت‌های $A_1,A_2,...,A_m$ بودند. برای این که تمام مدل‌ها دارای جذابیت مخصوص به خود باشند٬ هیچکدام از این مدل‌ها تمام قابلیت‌های یک مدل دیگر را دارا نبود ( یعنی اگر $A_i \subset A_j$ آن‌گاه $i=j$).
در سال دوم این شرکت تصمیم گرفت مجموعه‌ای از مدل‌ها را از روی مدل‌های ارائه شده در سال اول طراحی کند و به بازار ارائه کند. روش به این گونه بود که هر مدلی مثل $Y$ با مجموعه‌ی قابلیت‌های $B$ که دارای دو شرط زیر بود به بازار ارائه شد. - به ازای هر مدل سال قبل مثل $X_i$٬ باید $Y$ حداقل یکی از قابلیت‌های $X_i$ را دارا باشد. (یعنی $B\cap A_i \neq \varnothing$). - به ازای هر زیرمجموعه از $B$ مثل $B'$ که $B \neq B'$٬ مدلی که با قابلیت‌های $B'$ تعیین میشود دارای شرط اول نباشد.
این شرکت همانطور که مجموعه‌ی مدل‌های سال دوم را از روی مدل‌های سال اول طراحی کرد٬ دقیقاً با همین روش مجموعه‌ی مدل‌های سال سوم را از روی مجموعه‌ی مدل‌های سال دوم طراحی کرد. ثابت کنید که مجموعه‌ی مدل‌های سال اول و سوم عیناً مانند هم است.
سلام میدونستید انجمن علمی نخبگان دانشگاه صنعتی شریف مسابقه تخصصی مهارت سنجی برنامه نویسی و داده کاوی گذاشته است آدرس سایتش www.fanavard.com
2015-08-06 06:58:10 -0500 امیر شکریسلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه
2016-10-26 10:37:38 -0500 امیر شکریدر این اثبات هر مدل را با مجموعه ی قابلیت های آن نشان میدهیم.
میگوییم مجموعه ی مدل های {$B_1,B_2,B_3,...,B_y$}$B=$ تولیدی کل مدل های {$C_1,C_2,C_3,...,C_y$}$C=$ هست اگر مجموعه ی $B$ شامل تمام مدل هایی باشد که:
شرط اول: به ازای هر مدل مانند $C_i$ ($C_i \in C$) باید تمام اعضای مجموعه ی $B$ اشتراکی ناتهی با $C_i$ داشته باشند.
شرط دوم: به ازای هر $B_i$ ($B_i \in B$) هیچ زیرمجموعه ای از $B_i$ مانند $Y$ پیدا نمیشود که شرط اول را داشته باشد و $Y \neq B_i$.
اصل 1: هر تولیدی کل برای داشتن شرط دوم لازم دارد که هیچ دو مجموعه ای را شامل نشود که یکی زیر مجموعه ی دیگری باشد.
تولیدی جزء مجموعه ی {$C_1,C_2,C_3,...,C_y$}$C=$ را اینگونه بدست می آوریم: ابتدا $D$ را مساوی $A$ (مجموعه مرجع) قرار میدهیم. سپس تا زمانی که عضوی مانند $a_i$ پیدا شود که در صورت حذف کردن آن ، $D$ با تمام مجموعه های درون $C$ اشتراک ناتهی داشته باشد، $a_i$ را از درون مجموعه ی $D$ برمیداریم. در انتهای مجموعه ی $D$ تولیدی جزء مدل های مجموعه ی $C$ است.
اصل 2: تولیدی سال دوم تولیدی کل مدل های سال اول و تولیدی سال سوم تولیدی کل مدل های سال دوم است.
لم 1: به ازای هر $A_i$($A_i \in A$) هیچ زیر مجموعه ای از $A_i$ مانند $Y$ یافت نمیشود که $Y \neq A_i$ و $Y$ با تمام تولیدات سال دوم اشتراک ناتهی داشته باشد.
اثبات: یک زیر مجموعه با شرایط گفته شده مانند $Y$ را در نظر بگیرید. به ازای هر $A_i$، $B_i$ را مساوی $A_i - Y$ تعریف میکنیم. حال تولیدی جزء مجموعه ی {$B_1,B_2,B_3, ... , B_m$}$B=$ را مساوی $D$ در نظر بگیرید. میبینیم که $D$ هیچ اشتراکی با $Y$ ندارد و از آنجا که هیچ $j$ ای پیدا نمیشود که $A_j \subset A_i$ پس هیچ $j$ ای پیدا نمیشود که $A_j \subset Y$. پس هیچکدام از $B_i$ ها تهی نیستند. در نتیجه از آنجا که $D$ با تمام $B_i$ ها اشتراک دارد، پس با تمام $A_i$ ها نیز اشتراک دارد و همچنین شرط دوم را نیز دارد (چون تولیدی جزء است). پس مجموعه ی $D$ جزء تولیدات سال دوم است. پس به ازای هر زیر مجموعه با شرایط گفته شده در سال دوم مدلی تولید شده که اشتراک تهی با آن داشته باشد.
اصل 3: همه ی مدل های سال اول در سال سوم نیز تولید میشوند چون تمام مدل های سال اول زیر مجموعه ای از تولیدی کل مدل های سال دومند. یعنی مدل های سال اول هیچکدام از دو شرط گفته شده را نقض نمیکنند. واضح است که مدل های سال اول اشتراک ناتهی با همه ی مدل های سال دوم دارند. چون رابطه ی اشتراک رابطه ای دو طرفه هست. از طرفی با توجه به لم 1 شرط دوم را نیز داراست.
لم 2: در سال سوم هیچ مدلی تولید نمیشود که در سال اول تولید نشده باشد.
اثبات: فرض کنید چنین مدلی تولید شود. مجموعه قابلیت های این مدل را $Y$ بگیرید. به ازای هر $A_i$، $B_i$ را مساوی $A_i - Y$ تعریف میکنیم. حال تولیدی جزء مجموعه ی {$B_1,B_2,B_3, ... , B_m$}$B=$ را مساوی $D$ در نظر بگیرید. میبینیم که $D$ هیچ اشتراکی با $Y$ ندارد و از آنجا که هیچ کدام از $A_i$ ها زیر مجموعه ی $Y$ نیستند (با توجه به اصل 1) میتوان فهمید که هیچکدام از $B_i$ ها تهی نیستند. در نتیجه از آنجا که $D$ با تمام $B_i$ ها اشتراک دارد، پس با تمام $A_i$ ها نیز اشتراک دارد و همچنین شرط دوم را نیز دارد (چون تولیدی جزء است). پس مجموعه ی $D$ جزء تولیدات سال دوم است. از آنجا که $Y$ با $D$ اشتراک تهی دارد پس شرط اول نقض میشود که این تناقض است. پس فرض خلف باطل و لم گفته شده اثبات میشود.
حال باتوجه به لم 2 و اصل 3 تولید سال اول و سوم عینا مانند همند.
