صفحه ۲۸
سوالهای آنالیز ترکیبی
۸ تا سوال از مبحث آنالیز ترکیبی گذاشتم. میتونید میزان سوادتون توی مبحث آنالیز ترکیبی رو باهاشون بسنجید.
موفق باشید.
۱- ۱۵ تیم در یک تورنمنت شرکت کرده‌اند. هر تیم ۷ برد و ۷ باخت دارد. به چند طریق میتوان ۳ تیم از میان آنها انتخاب کرد به طوری که هر کدام در بین خودشان یک برد و یک باخت داشته باشند؟
۲- ثابت کنید تعداد رشته های n تایی از صفر و یک به طوری که هر دو تا حداقل در سه مکان متفاوت باشند حداکثر برابر (۲n/(n+1 است.
۳- یک کمیسیون ۴۰ بار تشکیل جلسه داده است. در هر جلسه ۱۰ عضو کمیسیون شرکت کرده‌اند. در ضمن هیچ دو عضوی از کمیسیون بیش از یک بار با هم در جلسه ها نبوده‌اند. ثابت کنید تعداد اعضای کمیسیون از ۶۰ بیشتر است.
۴- دنباله ای از اعداد ۱ تا ۹ داده شده است. ابتدا سه جمله ی اول دنباله را به صورت صعودی مرتب میکنیم. سپس جملات ۳ و ۴ و ۵ را به ترتیب صعودی مرتب میکنیم. بعد جملات ۵ و ۶ و ۷ و در نهایت جملات ۷ و ۸ و ۹ دنباله را به صورت صعودی مرتب میکنیم. به ازای چند دنباله اولیه متشکل از اعداد ۱ تا ۹، دنباله ی به دست آمده
۹ ، ۸ ، ۷ ، ۶ ، ۵ ، ۴ ، ۳ ، ۲ ، ۱ می‌باشد؟
۵- در یک اتاق دو کتابخانه وجود دارد. یکی k قفسه و دیگری k+m قفسه دارد. تعدادی کتاب در کتابخانه ی اول وجود دارد و میدانیم هیچ یک از k قفسه ی این کتابخانه خالی نیست. کلیه کتابهای این کتابخانه را بر می‌داریم و در کتابخانه ی دوم قرار می‌دهیم به طوری که باز هیچ یک از k+m قفسه ی این کتابخانه خالی نباشد. کتابی را «ویژه» می‌نامیم که تعداد کتابهای هم قفسه با این کتاب در حالت اول بیش از حالت دوم باشد. ثابت کنید حداقل m+1 کتاب ویژه وجود دارد.
۶- n تیم فوتیال در یک دوره مسابقه شرکت کرده‌اند. هر دو تیم دقیقاً یک بار با هم مسابقه می‌دهند. در هر بازی به برنده ۲ امتیاز، به بازنده صفر امتیاز و در صورت تساوی به هر یک از دو تیم ۱ امتیاز تعلق می‌گیرد. ثابت کنید در پایان مسابقات اختلاف امتیاز بین هر دو تیم متوالی در جدول امتیازات حداکثر n است.
۷- 12k نفر در یک مهمانی شرکت کرده‌اند. هر نفر دقیقاً با 3k + 6 نفر دیگر از مهمانان دست می‌دهد. همچنین میدانیم تعداد افرادی که با هر [هر] دو نفر دست می‌دهند، عددی ثابت است. تعداد افراد شرکت کننده در این مهمانی را تعیین کنید.
۸- تعداد زیرمجموعه های لااقل دو عضوی مجموعه ی {۱، ۲، ۳، ... ، ۲n} که مجموع هر دو عضو متمایز آنها از ۲n بزرگتر است، چند تاست؟
۱۳۸۹/۰۹/۰۱ · ۱۵:۴۱
آزمون آزمایشی مرحله ۱
این آزمون تو مدارس خودتون به صورت حضوری (شبیه‌سازی جلسه امتحان) برگزار میشه (به صورت همزمان در تعداد زیادی از مدارس کشور)، بعد هم پاسخنامه‌ها به دست ما می‌رسه و ما صحیحش میکنیم و نمره‌هاش رو بهتون اعلام میکنیم! تاریخ آزمون صبح جمعه ۱۹ آذر ۸۹ هستش و تمام تلاشمون رو میکنیم که دقیقا تو همین تاریخ برگزار بشه (حالا اگه مجبور شدیم تاریخ رو عوض کنیم دیگه مجبور شدیم خب!)
در مورد سبک سوالات و تعداد سؤالات و تعداد گزینه‌ها و مدت امتحان و ... هم فقط میتونم بگم که ما تمام تلاشمون رو میکنیم که شبیه مرحله ۱ باشه! :دی
فقط برای برگزاری این امتحان در مدارس مختلف، نیاز به کمک شما داریم، یعنی از هر مدرسه‌ای یه نفر آدم معتبر (!) باید مسئولیت برگزاری این امتحان تو مدرسشون رو بر عهده بگیره که ما سؤالات رو به اون تحویل بدیم و پاسخنامه‌ها رو از اون تحویل بگیریم و خیالمون راحت باشه که آزمون رو تو مدرسشون به صورت استاندارد برگزار می‌کنه!
حالا واسه اینکه این امتحان به بهترین نحو و در بیشترین تعداد مدارس ممکن برگزار بشه، شما باید تو مدرستون یه آدم معتبر (مثلا یکی از فارغ‌التحصیلان مدرستون که مدال المپیاد داشته باشه یا مدیر مدرسه یا هرکس دیگه‌ای که بشه روش حساب کرد) رو خبر کنید که به ما ایمیل بزنه و اعلام آمادگی کنه، ما بقیش رو با اون هماهنگ خواهیم کرد!
واسه بچه‌های مدارسی که به هردلیلی آزمون توش برگزار نمیشه هم یه فکری خواهیم کرد! فکرمون احتمالا این خواهد بود که سر همون ساعت که امتحان تو مدارس دیگه برگزار میشه ما هم سوالا رو میزاریم تو شاززز و تا یه زمانی بهش مهلت میدیم که جواباش رو بهمون ایمیل کنه!(اگه فکر بهتری به ذهنتون رسید بگید! :دی)
یادآوری: ایمیل شاززز این بود: sh44zzz [AT] gmail [DOT] com
پ.ن: لطفا هرچه زودتر واسه پیدا کردن اون آدم معتبر تو مدرستون اقدام کنید!
۱۳۸۹/۰۸/۲۴ · ۱۷:۵۹
دومین مسابقات اینترنتی برنامه‌نویسی دانش‌آموزی ایران
دور دوممسابقات اینترنتی برنامه‌نویسی دانش‌آموزی(که دور اولش توی تابستون برگزار شد) به زودی شروع میشه.
مسابقه اول از بیست و یک آبان (جمعه) شروع میشه و برای یک هفته ادامه پیدا می‌کنه.
مسلماً شرکت توی این مسابقه به همه‌ی علاقه‌مندها توصیه میشه (مخصوصاً از نوع المپیاد کامپیوتری)
من سعی می‌کنم اطلاعات بیشتری در مورد مسابقه از برگزارکننده‌ها بگیرم و به همین پست اضافه کنم. (البته توی سایت مسابقه هم توضیحات خوبی در مورد نحوه‌ی برگزاری، مقالات آموزشی، آرشیو سؤالات و ... هست که میتونید ازشون استفاده کنید.)
یادتون نره اگه می‌خواید شرکت کنید باید از طریق سایت مسابقاتثبت نامکنید.
به‌روز‌رسانی:اطلاعات بیشتر در مورد ISPC، به نقل از برگزارکنندگان:
«هدف اصلی ispc ایجاد محیطی برای پیشرفت دانش‌آموزان راهنمایی و دبیرستان در زمینه‌ی علوم کامپیوتر است. ispc به محدوده‌ی خاصی از علوم کامپیوتر محدود نمی‌شود و در طول زمان ممکن است مباحث جدیدی به آن اضافه شود. سطح مطالب و مسابقه‌های ispc برای دانش‌آموزان متوسط و بالا در نظر گرفته شده است. دانش‌آموزانی که در یک موضوع خاص سطح خیلی بالایی دارند، شاید مسابقه‌های پیکارجو در آن زمینه نیابند و این طبیعی است.
در زمینه‌هایی که با المپیاد کامپیوتر اشتراک دارند، تخمین ما این است که مطالب برای بیشتر دانش‌آموزانی که به دوره‌ی المپیاد راه نیافته‌اند می‌تواند مفید باشد. البته در صورتی که افراد بیشتری کمک کنند شاید بتوانیم بخش مخصوص المپیادی‌ها را هم اضافه کنیم، اما به نظر می‌رسد اگر کارهای مخصوص المپیاد توسط باشگاه دانش‌پژوهان جوان انجام شود، منسجم‌تر و بهتر صورت می‌گیرد.
البته ماهیت و فلسفه ispc هنوز در حال شکل گرفتن است و این به خاطر نوپا بودن و تکراری نبودن این جریان است. امیدواریم که با کمک دوستان این جریان به جریان موفقی مبدل بشود.»
۱۳۸۹/۰۸/۱۹ · ۲۰:۳۰
جواب "چند تا سؤال"
خب هفته پیش مهران پست «چندتا سؤال» رو داده بود که توی این پست راه حل اون سؤال‌ها رو می‌گیم:
۱- برای حل این سوال از استقرا استفاده میکنیم. پایه استقرا: برای n=۱، عدد مورد نظر ۲ است. هر عدد n+۱ رقمی مورد نظر را بر حسب عدد n رقمی به این صورت می‌سازیم:
اگر عدد n رقمی بر ۲n+۱بخشپذیر بود آن را بعلاوه ۲×۱۰nمیکنیم و در غیر این صورت آن را بعلاوه ۱۰nمیکنیم تا عدد به دست آمده بر ۲n+۱بخش‌پذیرباشد.
۲- چون ۳۹ عدد متوالی داریم میتوان گفت که حداقل ۲۰تای آنها در یک بازه ۱۰۰تایی (یعنی بین۱۰۰×kو۱۰۰×(k+۱)) هستند. با استفاده از اصل لانه کبوتری میتوان ثابت کرد که مجموع ارقام یکی از این ۲۰ عدد بر ۱۱ بخشپذیر است (اثبات بر عهده خواننده!)
۳- همانطور که در راهنمایی پست قبل اشاره شد "عدد مورد نظر، برابر میانگین تمام اعداد یادداشت شده به ازای جایگشت‌های مختلف افراد است." برای محاسبه مجموع اعداد یادداشت شده میتوان در نظر گرفت که هر عدد چند بار در جای درست خود ظاهر شده است. مثلا می‌خواهیم ببینیم عدد ۱ چند بار در جای درست خود در جایگشت آمده است، فرض میکنیم که عدد ۱ در جای اول (جای درست) قرار دارد. در این صورت برای دیگر اعداد(n-۱)!حالت وجود دارد. پس ۱ در(n-۱)!جایگشت در جای خود است. چون n عدد داریم در مجموعn×(n-۱)!بار اعداد در جای درست خود قرار گرفته‌اند. یعنی مجموع اعداد نوشته شده برابرn!و میانگین آنها برابرn! ÷ n! = ۱خواهد بود.
۴- جعبه ها را براساس تعداد سیب‌ها به صورت افزایشی مرتب میکنیم. اگر تعداد گلابی‌ها در جعبه‌های فرد بیشتر از نیمی از کل گلابی‌ها بود همان جعبه‌ها را (به همراه جعبه آخر برای حالت n زوج) انتخاب میکنیم. در غیر این صورت جعبه های زوج را (به همراه جعبه آخر برای n فرد و یا هر یک از جعبه های فرد برای n زوج) انتخاب میکنیم. در این صورت حداقل نیمی از سیب‌ها و نیمی از گلابی‌ها را در[n÷۲]+۱تا از جعبه‌ها خواهیم داشت.
۵- سوال از ما گرافی با n راس می‌خواهد که درجه‌ی هیچ ۳ رأسی از آن برابر نباشد. برای ساختن این گراف (برای nهای زوج)n÷۲از رئوس را در بالا وn÷۲را در پایین قرار می‌دهیم. هر رأس از بالا را، به تمامی رئوس پایینی که در سمت چپ آن قرار ندارند وصل میکنیم. (به این ترتیب هر رأس پایین هم به تمامی رئوس بالایی که در سمت راست آن قرار ندارند وصل می‌شود). به این ترتیب دنباله‌ی درجات گراف حاصل «۱، ۱، ۲، ۲، ...،n÷۲،n÷۲» خواهد بود.) برای n فرد کافی است یک رأس با درجه‌ی ۰ به گراف اضافه کنیم)
۱۳۸۹/۰۸/۱۲ · ۱۰:۵۸
چند تا سؤال
(راهنمایی: استقرا خیلی خوبه)
۲- ثابت کنید بین هر ۳۹ عدد متوالی، میتوان عددی را پیدا کرد که مجموع رقم‌های آن بر ۱۱ بخشپذیر باشد.
(راهنمایی: لانه‌ی کبوتری هم خیلی خوبه)
۳- n فوتبالیست با شماره‌های ۱ تا n، و n صندلی با شماره‌های ۱ تا n وجود دارد. با هر سوت مربی،
n نفر به صورت کاملا تصادفی روی صندلی‌ها می‌نشینند و مربی تعداد افرادی
که روی صندلی با شماره‌ی خودشان نشسته‌اند را یادداشت می‌کند. این آزمایش
را به دفعات زیاد تکرار می‌کند. میانگین تمام اعداد نوشته شده چه عددی
خواهد بود؟
(راهنمایی: عدد مورد نظر، برابر میانگین تمام اعداد یادداشت شده به ازای جایگشت‌های مختلف افراد است.)
۴- n جعبه داریم. در جعبه‌ی i-ام aiکیلو سیب، biکیلو گلابی وجود دارد. ثابت کنید می‌توانیم با برداشتن[n/۲]+۱تا از جعبه‌ها را برداریم، که حداقل نیمی
از [کل] گلابی‌ها و حداقل نیمی از [کل] سیب‌ها را برداشته باشیم.
(راهنمایی: استقرا همیشه آسون‌ترین راه نیست)
۵- قرار شد تیم المپیاد کامپیوتر جهانی امسال ۳-نفره
باشد و
مسئولین کمیته برای موفقیت هر چه بیشتر تیم، به فکر افتاده‌اند. آنها بعد
از بررسی‌های بسیار، و مشاوره با نویسندگان شاززز، توانستند شرط لازم و
کافی برای موفقیت تیم را کشف کنند: «تعداد دوستان هر فرد (از ۳ نفر تیم، و
در بین تمامی شرکت‌کنندگان) باید با تعداد دوستان ۲ نفر دیگر برابر باشد.»
بعد از تلاش‌های بسیار، و با اجرای الگوریتم‌های پیچیده، کمیته به این
نتیجه رسید که امسال به هیچ وجه تیم جهانی المپیاد کامپیوتر نتیجه‌ی خوبی
نخواهد گرفت و به همین دلیل تصمیم گرفته المپیاد کامپیوتر را منحل کند. با
دانستن تعداد شرکت‌کنندگان، یک نحوه‌ی دوستی ممکن بین افراد را بیابید.
(دوستی رابطه‌ی دوطرفه است.)
(راهنمایی: فهمیدن سؤال نصف سؤاله!)
۱۳۸۹/۰۸/۰۵ · ۰۸:۵۴
سفرنامه‌ی IOI ۲۰۱۰ (المپیاد جهانی کامپیوتر سال ۲۰۱۰)
به نام خدا
سلام بچه‌ها! خوبین؟
اگه منو نمی‌شناسید من علی بابایی یکی از «نویسندگان سابق» این وبلاگم (چقدر زود پیر شدیم!). معمولا وقتی یه نویسنده «سابق» میشه دیگه چیزی نمی‌نویسه. من هم قصد سنت‌شکنی نداشتم، ولی چون قبلا قول داده بودم سفرنامه‌ی IOI رو بنویسم، این پست رو زدم.
این سفرنامه، در مورد سفر تیم المپیاد کامپیوتر ایران به IOI 2010 است. ایده‌ی نوشتن سفرنامه قبل از رفتن به IOI تو ذهنم بود. بعدش که برگشتیم تا یه مدت وقت نکردم درستش کنم. الان یه چند وقتیه شروع کردم و قسمت اولش آماده شده.
قبل از شروع سفرنامه چندتا نکته:
-تو این مدتی که داشتم سفرنامه رو آماده می‌کردم، این سوال که «این سفرنامه به درد شما می‌خوره یا نه» مدام می‌اومد سراغم و جواب قانع کننده‌ای براش پیدا نکردم. کلا برای خود من نوشتن همچین چیزی به درد بخوره اما نمی‌دونم خوندنش به درد شما می‌خوره یا نه!
-اولش فکر می‌کردم که کل سفرنامه رو میشه تو ۵-۶ صفحه و تو یه پست نوشت. ولی وقتی شروع به نوشتن کردم، دیدم همین تیکه‌ی اولش خودش کلی شد. برای همین تصمیم گرفتم که به صورت چند قسمت بنویسمش و اینجا بذارم. از همین اول هم بگم که ممکنه زمان بین گذاشتن قسمت‌ها طولانی بشه! ولی سعیم رو می‌کنم که زود تمومش کنم.
-احتمالا از قسمت‌های بعدی عکس هم می‌ذارم و چون کار کردن با editor وبلاگ برای گذاشتن عکس و ... سخته، ممکنه که بقیه‌ی قسمت‌ها رو تو یه صفحه‌ی دیگه درست کنم و اینجا فقط لیکش رو بذارم.
قسمت اول سفرنامه در مورد وقایعیه که قبل از سفر برامون اتفاق افتاد. برای خوندن این قسمت روی «قسمت اول» کلیک کنید. برای نوشتن این قسمت، یه سری ایده هم بهروز داد که ازش تشکر می‌کنم.
۱۳۸۹/۰۷/۲۷ · ۰۸:۳۰
نویسنده‌های جدید
۳ نویسنده‌ی جدید به جمع نویسنده‌های شاززز اضافه شدن، برای اینکه تعداد پست‌ها زیاد نشه همه رو یه جا معرفی می‌کنم:
حسین شایسته، علامه‌حلی تهران، طلای دوره‌ی ۲۰ کامپیوتر
نازنین علیپور، فرزانگان تهران، طلای دوره‌ی ۱۹ کامپیوتر
محمد زابلیان، شهید اژه‌ای اصفهان، طلای دوره‌ی ۱۹ کامپیوتر
۱۳۸۹/۰۷/۱۵ · ۱۶:۳۶
Hello World
من سید مهران خلدی هستم، از بچه‌های دوره‌ی ۱۹ کامپیوتر، و قرار شده به عنوان نویسنده‌ی جدید شاززز در خدمت‌تون باشم.
امیدوارم بتونم کمک کنم
به‌روز‌رسانی:احتمالا چند تا صفحه‌ی جداگانه قراره برای وبلاگ آماده بشه، احتمالا اولی‌ش «ویکی‌شازززیا» هستش که قراره در مورد منابع المپیاد و یه سری توصیه و اینجور چیزها باشه. اما قبلش لازم بود یه تغییراتی روی قالب اجرا بشه (نترسید، قالب تغییر محسوسی نمی‌کنه، صرفا یه مقدار با سرویس‌های جدید بلاگفا سازگار میشه) برای همین ممکنه یه کم وقت بگیره.
به‌روز‌رسانی:خب، بازنویسی قالب هم تموم شد. الآن قالب از صفحات جداگانه هم پشتیبانی می‌کنه. سمت راست وبلاگ، توی بخش پیوندها، یه لینک به نام «لیست صفحات جداگانه» وجود داره. روی اون کلیک کنید تا لیست این صفحات رو ببینید. این صفحات، صفحاتی هستن که چون احتمالا در آینده هم قراره زیاد تغییر بکنند، از بقیه جدا شدن. اولین صفحه‌ی جدا هم با اسم «ویکی‌شازززیا» قرار داده شده. توضیحات بیشتر رو همونجا بخونید. خب دیگه، من خسته شدم، یه مدت کمتر فعالیت می‌کنم.
به‌روز‌رسانی:صفحه‌ی تغییرات اضافه شد. میل جدید شاززز راه‌اندازی شد. (توضیحات بیشتر در صفحه‌ی تغییرات)
۱۳۸۹/۰۷/۰۹ · ۱۴:۲۹