سوالهای آنالیز ترکیبی

۸ تا سوال از مبحث آنالیز ترکیبی گذاشتم. میتونید میزان سوادتون توی مبحث آنالیز ترکیبی رو باهاشون بسنجید.

موفق باشید.

۱- ۱۵ تیم در یک تورنمنت شرکت کرده‌اند. هر تیم ۷ برد و ۷ باخت دارد. به چند طریق میتوان ۳ تیم از میان آنها انتخاب کرد به طوری که هر کدام در بین خودشان یک برد و یک باخت داشته باشند؟

۲- ثابت کنید تعداد رشته های n تایی از صفر و یک به طوری که هر دو تا حداقل در سه مکان متفاوت باشند حداکثر برابر (۲ⁿ/(n+1 است.

۳- یک کمیسیون ۴۰ بار تشکیل جلسه داده است. در هر جلسه ۱۰ عضو کمیسیون شرکت کرده‌اند. در ضمن هیچ دو عضوی از کمیسیون بیش از یک بار با هم در جلسه ها نبوده‌اند. ثابت کنید تعداد اعضای کمیسیون از ۶۰ بیشتر است.

۴- دنباله ای از اعداد ۱ تا ۹ داده شده است. ابتدا سه جمله ی اول دنباله را به صورت صعودی مرتب می‌کنیم.  سپس جملات ۳ و ۴ و ۵ را به ترتیب صعودی مرتب می‌کنیم. بعد جملات ۵ و ۶ و ۷ و در نهایت جملات ۷ و ۸ و ۹ دنباله را به صورت صعودی مرتب می‌کنیم. به ازای چند دنباله اولیه متشکل از اعداد ۱ تا ۹، دنباله ی به دست آمده

۹ ، ۸ ، ۷ ، ۶ ، ۵ ، ۴ ،‌ ۳ ،‌ ۲ ، ۱ می‌باشد؟

۵- در یک اتاق دو کتابخانه وجود دارد. یکی k قفسه و دیگری k+m قفسه دارد. تعدادی کتاب در کتابخانه ی اول وجود دارد و میدانیم هیچ یک از k قفسه ی این کتابخانه خالی نیست. کلیه کتابهای این کتابخانه را بر می‌داریم و در کتابخانه ی دوم قرار می‌دهیم به طوری که باز هیچ یک از k+m قفسه ی این کتابخانه خالی نباشد. کتابی را «ویژه» می‌نامیم که تعداد کتابهای هم قفسه با این کتاب در حالت اول بیش از حالت دوم باشد. ثابت کنید حداقل m+1 کتاب ویژه وجود دارد.

۶- n تیم فوتیال در یک دوره مسابقه شرکت کرده‌اند. هر دو تیم دقیقاً‌ یک بار با هم مسابقه می‌دهند. در هر بازی به برنده ۲ امتیاز، به بازنده صفر امتیاز و در صورت تساوی به هر یک از دو تیم ۱ امتیاز تعلق می‌گیرد. ثابت کنید در پایان مسابقات اختلاف امتیاز بین هر دو تیم متوالی در جدول امتیازات حداکثر n است.

۷- 12k نفر در یک مهمانی شرکت کرده‌اند. هر نفر دقیقاً با 3k + 6 نفر دیگر از مهمانان دست می‌دهد. همچنین می‌دانیم تعداد افرادی که با هر [هر] دو نفر دست می‌دهند،‌ عددی ثابت است. تعداد افراد شرکت کننده در این مهمانی را تعیین کنید.

۸- تعداد زیرمجموعه های لااقل دو عضوی مجموعه ی {۱، ۲، ۳، ... ، ۲n} که مجموع هر دو عضو متمایز آنها از ۲n بزرگتر است،‌ چند تاست؟