سوال ۱ روز دوم مرحله ۲ دوره ۲۳: رشته‌ی نزدیک
سوال ۴- دسته بندی کارت ها و بیشینه کردن کارت های همانی
سوال ۲- مرتب کردن اعداد ۱ تا n به وسیله‌ي مرتب‌ساز پشته‌ای با دو پشته‌ی A و B
سوال ۳- نشان دهید امیرمهدی همیشه می‌تواند طوری بازی کند که برنده شود.
بازی رنگی - سوال ۱ - مرحله ۲ - ۱۳۹۳
وزنه‌ها و ماشین جادویی - سوال ۲ - مرحله ۲ - ۱۳۹۳
گاوی خسیس - سوال ۳ - مرحله ۲ - ۱۳۹۳
انتقال مهره‌های گاوی - سوال ۴ - مرحله ۲ - ۱۳۹۳
یافتن کوچکترین پیچ و مهره با مقایسه آنها
دنباله و جادوگر - دوره ی 24 - مرحله ی 2
آقای امینی معلم کلاسی شامل $nk$ دانش‌آموز می‌باشد. در این کلاس تعدادی رابطه دوستی بین دانش‌آموزان برقرار است (رابطه دوستی دوطرفه است، یعنی اگر دانش‌آموز a با دانش آموز b دوست باشد، دانش‌آموز b هم با a دوست هست). آقای امینی به کارهای گروهی خیلی علاقه‌مند هست. او می‌خواهد دانش‌آموزان را به $n$ گروه $k$ نفری تقسیم کند. اما برای او مهم است که افراد یک گروه همه با هم دوست باشند. ما می‌دانیم حداقل یک راه برای دسته‌بندی دانش‌آموزان با شرایط گفته شده وجود دارد. دانش‌آموزان که از این امر مطلع شده‌اند به دنبال این هستند که دسته‌بندی معلم را از قبل پیش‌بینی کنند.
الف) نشان دهید که اگر تعداد رابطه‌های دوستی برابر با ${k \choose 2} n^ 2$ باشد، حالتی از روابط دوستی وجود دارد که دسته‌بندی معلم به صورت یکتا مشخص شود.
ب) نشان دهید که اگر تعداد رابطه‌های دوستی بیشتر از ${k \choose 2} n^ 2$ باشد، هیچ حالتی نیست که دسته‌بندی بصورت یکتا انجام پذیرد.
ممنون از اینکه سوال‌های سال قبل رو گذاشتی. این‌جوری کم‌کم جواب این سوال‌ها هم جمع‌آوری میشه.
2014-08-26 02:50:55 -0600 فامیل دورسلام میدونستید انجمن علمی نخبگان دانشگاه صنعتی شریف مسابقه تخصصی مهارت سنجی برنامه نویسی و داده کاوی گذاشته است آدرس سایتش www.fanavard.com
2015-08-06 08:34:36 -0600 امیر شکریسلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه
2016-10-26 08:46:48 -0600 امیر شکریالف)
به استقرای روی $n$ گرافی می سازیم که دارای شرایط مسئله باشد .
حالت پایه $n$=$k$ : در این حالت دقیقا بین هر دو راس یال داریم و گروه بندی به وضوح یکتاست>
فرض کنیم بلدیم مسئله را برای $n$ حل کنیم ، با استفاده از این گراف فرض استقرا گرافی با $k(n+1)$ راس میسازیم ، ابتدا یک گراف کامل $k$ راس در نظر می گیریم _نام آن را $T$ بگذارید_ و بین هر دو راس آن یال می گذاریم ، سپس گراف فرض استقرا برای $nk$ راس را نیز در نظر می گیریم ، همه رئوس $T$ بغیر از یکی از رئوس آن مثل $x$ را به تمامی رئوس گراف فرض استقرا متصل می کنیم . اکنون ثابت می کنیم گراف جدید به اندازه درستی یال دارد و گروه بندی هم یکتاست .
$e=n^2.{k \choose 2} + (k-1).nk + {k \choose 2} = (n+1)^2{k \choose 2}$
از طرفی راس $x$ تنها باید با $k-1 $ راس همسایه است پس دقیقا با $T$ باید در گروه باشد و بقیه گراف هم طبق فرض استقرا گروه بندی درونش یکتاست .
ب)
طبق فرض سوال گروه بندی ای وجود دارد ، این گروه بندی را در نظر میگیرم ، یال های گراف 2 نوع اند ، یال های بین گروه ها و یال های درون گروه ها ، تعداد یال های نوع دوم برابر ${k \choose 2}.n$ است ، پس تعداد یال های بین دسته ها از $n(n-1){k \choose 2}$ بیشتر است ، پس دو گروهم مثل $i$ و $j$ وجود دارد که تعداد یال های بینشان از $k(k-1)$ بیشتر است ، پس راسی مثل $a$ در گروه $i$ وجود دارد که به همه رئوس گروه $j$ متصل است و به شکل مشابه راسی مثل $b$ وجود دارد که به همه رئوس دسته $i$ متصل است ، اگر جای این دو راس را در این گروه ها عوض کنیم ، گروه بندی جدیدی بدست میآید ، پس گروه بندی یکتا نیست !
