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

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

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