شاززز

شاززز

اینجا وبسایت آزاد المپیاد کامپیوتره! ;)
واسه ی همه ی سطوح از تازه کارها تا طلای جهانی!

بایگانی

جواب "چند تا سؤال"

چهارشنبه, ۱۲ آبان ۱۳۸۹، ۱۰:۵۸ ق.ظ

خب هفته پیش مهران پست «چندتا سؤال» رو داده بود که توی این پست راه حل اون سؤال‌ها رو می‌گیم:

۱- برای حل این سوال از استقرا استفاده می‌کنیم. پایه استقرا: برای 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 فرد کافی است یک رأس با درجه‌ی ۰ به گراف اضافه کنیم)

  • ۸۹/۰۸/۱۲
  • شااززز منگولیا

نظرات  (۰)

هیچ نظری هنوز ثبت نشده است

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی