سوال ۱- جدول n*n از اعداد ۱ تا n داده شده...
سوال ۳ - رنگ آمیزی دیوار خانه‌ی عمو نقّاش
سوال ۴ - روشی برای انتخاب سالن انتظار در هر روز و دیدن تلویزیون آن در شهر المپیادی‌ها
سوال 5- احداث جاده و مرکز پلیس در شهرهای کشور علی کوچولو
سوال 6- وزن کم ترین زبان n کلمه ای که هم پیشوند -آزاد باشد و هم پسوند-آزاد
سوال ۷- مجموعه‌ی سه تایی های پایدار
سوال ۸- دایره‌های دوبه‌دو نامتقاطع روابط
سوال 2- قورباغه‌ي پهلوان روی محور اعداد صحیح
سوال ۵- رنگ‌آمیزی پراکنده یک جدول با رنگ‌های سیاه و سفید
یک جدول $n \times n$ در اختیار داریم. در ابتدا جدول از $n^2$ ناحیه تشکیل شده است ($n^2$ مربع $۱ \times ۱$). در هر مرحله می‌توانیم تمام دو ناحیه‌ی مجاور (یعنی دو ناحیه که لااقل یک پاره‌خط مشترک دارند) را از جدول انتخاب کنیم و این دو ناحیه را با هم ادغام کنیم؛ یعنی مرز مشترک بین این دو ناحیه را پاک کنیم. فرض کنید طول این مرز مشترک در مرحله‌ی $i$ام $a_i$ باشد. اگر بعد از $k$ مرحله٬ تنها یک ناحیه باقی بماند (یعنی یک مربع $n \times n$٬ اعداد $a_۱,...,a_k$ به دست می‌آیند. برای مثال٬ در شکل سمت چپ بالا اگر نواحی $D$ و $C$ را بخواهیم با هم ادغام کنیم٬ محیط مشترک بین این دو ناحیه ۳ واحد بوده و نهایتاً به شکل پایین می‌رسیم.
الف) روشی ارائه دهید که در آن هر یک از $a_i$ها ۱ یا ۲ باشد.
ب) نشان دهید کمترین مقدار $\sum_{i=1}^k a_i^2$ وقتی رخ می‌دهد که هر یک از $a_i$ها ۱ یا ۲ باشد و با استفاده از این نکته جواب مسئله٬ یعنی کمترین مقدار $\sum_{i=1}^k a_i^2$ را به دست آورید.
سلام میدونستید انجمن علمی نخبگان دانشگاه صنعتی شریف مسابقه تخصصی مهارت سنجی برنامه نویسی و داده کاوی گذاشته است آدرس سایتش www.fanavard.com
2015-08-06 07:36:02 -0500 امیر شکریسلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه
2016-10-26 08:50:21 -0500 امیر شکریستون ها و سطر ها را از 1 تا $n$ شماره گذاری میکنیم. خانه (1,1) را با خانه (2,1) ادغام میکنیم آنرا ناحیه "اصلی" مینامیم سپس برای $j=3$ تا $n$ خانه $(i,1)$ را با ناحیه اصلی ادغام میکنیم و انرا ناحیه اصلی مینامیم. وقتی ستون تمام شد ب سراغ ستون بعدی میرویم و برای $j=1$ تا $n$ خانه $(j,2)$ را به ناحیه اصلی ادغام میکنیم سپس به ستون بعدی میرویم الی اخر. بدین ترتیب هر $a_i$ برابر 1 یا 2 میشود.
به سادگی میشه اثبات کرد اگر یه $a_i$ از 2 بزرگتر باشه ناحیه ای وجود داره که از ادغام 2 ناحیه با مرز بزرگتر از 2 بوجود امده و هر کدام ازاون 2 ناحیه با ادغام چند ناحیه با مرز مشترک 2 یا 1 بوجود امده اند. برهان خلف. فرض کنید روش ادغامی وجود داره که حاصلجمع $a_i$ کمترین مقداره و یک $a_i$ بزرگتر از 2 داره. میدانیم در آن روش ناحیه ای وجود داره که از ادغام 2 ناحیه با مرز بزرگتر از 2 بوجود امده و هر کدام ازاون 2 ناحیه با ادغام چند ناحیه با مرز مشترک 2 یا 1 بوجود امده اند. میشه ثابت کرد اگر اندازه ناحیه اول برابر a و اندازه ناحیه دوم برابر b باشه انگاه $a+b-1$ صورت گرفته. حال همین 2 ناحیه را میتوان با روشی مشابه روش توضیح داده شده با همین تعداد ادغام ادغام کرد که همه $a_i$ برابر 2 یا 1 باشند. حاصلجمع مقدارها کمتر میشود.تناقض. کمترین مقدار حاصل جمع $a_i$ هم برابر $4(n-1)^2+2n-2$ است.
