پرسش‌های ترکیبیات، شمارش سطح۱ - سری۱

۱- تعداد kn نفر به چند روش می‌توانند دور k میز متمایز بنشینند، جوری که دور هر میز درست n نفر نشسته باشند؟

راهنمایی ۱ (کلیک کنید)

پاسخ: ${\frac{(kn)!}{n^k}$

۲- چند تا k تایی مرتب مانند (a₁, a₂, a₃, ..., a_k) هست، جوری که داشته باشیم:

a₁ ≤ a₂ ≤ a₃ ≤ ... ≤ a_k ≤ n

راهنمایی ۱ (کلیک کنید)

اگر می‌خواستیم داشته باشیم:

a₁ < a₂ < a₃ < ... < a_k < n

کار ساده‌تر بود.

راهنمایی ۲ (کلیک کنید)

اکنون عددها را تغییر دهید تا مانند آن چه در راهنمایی۱ داشتیم، داشته باشیم:

b₁ < b₂ < b₃ < ... < b_k < p

و این برابری با برابری صورت مساله سازگار باشد.

۳- ثابت کنید $(n-2k)\left(\large\begin{array} {GC+18} n \\ k \end{array}\right)\ = n\[\left(\large\begin{array} n-1 \\ k \end{array}\right)\ - \left(\large\begin{array} n-1 \\ k-1 \end{array}\right)\]$

راهنمایی ۱ (کلیک کنید)

به دو روش بشمارید.

۴- ثابت کنید $\left(\large\begin{array} {GC+18} n+1 \\ 3 \end{array}\right)\ - \left(\large\begin{array} n-1 \\ 3 \end{array}\right)\ = (n-1)^2$

راهنمایی ۱ (کلیک کنید)

به دو روش بشمارید.

۵- اگر q عددی طبیعی باشد که از عدد طبیعی p کوچک‌تر باشد ثابت کنید ${\left(\large\begin{array} {GC+18} p \\ q \end{array}\right) }^2 \gt \left(\large\begin{array} {GC+18} p \\ q+1 \end{array}\right)\left(\large\begin{array} {GC+18} p \\ q-1 \end{array}\right)$

راهنمایی ۱ (کلیک کنید)

از تناظر یک به یک کمک بگیرید.

۶- اگر p عددی طبیعی باشد که از عدد طبیعی q کوچک‌تر است ثابت کنید $\left(\large\begin{array} {GC+18} p \\ 2 \end{array}\right) +\left(\large\begin{array} {GC+18} q \\ 2 \end{array}\right) \ge \left(\large\begin{array} {GC+18} p+1 \\ 2 \end{array}\right) +\left(\large\begin{array} {GC+18} q-1 \\ 2 \end{array}\right)$

راهنمایی ۱ (کلیک کنید)

از تناظر یک به یک کمک بگیرید.

۷- از سه نوع غذای قیمه پلو و سبزی پلو با ماهی و چلوکباب می‌خواهیم برای یک جمع n نفره غذا بخریم. این کار به چند روش ممکن است؟

راهنمایی ۱ (کلیک کنید)

عدد n را کوچک در نظر بگیرید و دانه دانه بشمارید تا ارتباط پاسخ با n و 3 را پیدا کنید.

۸- فرض کنید b_n تعداد روش‌های نوشتن یک رشته‌ی n تایی از نشانه‌های + و - باشد به طوری که هیچ دو نشانه‌ی - پشت سر هم نباشند. برای n های طبیعی و بزرگ‌تر از 3 ثابت کنید:

b_n = b_n-1 + b_n-2

راهنمایی ۱ (کلیک کنید)

تلاش کنید تا دنباله‌ی n تایی را از دنباله‌ی n-1 تایی بسازید.

راهنمایی ۲ (کلیک کنید)

به این فکر کنید که نخستین نشانه در دنباله‌ی n تایی چیست؟

۹- اگر f_n تعداد دنباله‌های n تایی از رقم‌های 0 و 1 و 2 باشد، جوری که دو رقم پشت سر هم 1 یا دو رقم پشت سر هم 2 نداشته باشد،
الف) یک رابطه‌ی بازگشتی برای محاسبه‌ی f_n پیدا کنید.
ب) ثابت کنید:

$f_n = 1 + 2\left(\large\begin{array} {GC+18} n+1 \\ 2 \end{array}\right) + 2^2\left(\large\begin{array} n+1 \\ 4 \end{array}\right) + 2^3 \left(\large\begin{array} n+1 \\ 6 \end{array}\right) + ...$

راهنمایی ۱ (کلیک کنید)

تلاش کنید تا دنباله‌ی n تایی را از دنباله‌ی n-1 تایی بسازید.

راهنمایی ۲ (کلیک کنید)

دو رقم نخست دنباله‌ی n تایی را بررسی کنید.

راهنمایی ۳ (کلیک کنید) رابطه‌ی بازگشتی را ببینید.

f_n = 2f_n-1 + f_n-2

راهنمایی ۴ (کلیک کنید)

از رابطه‌ی بازگشتی و نیز از تعداد دنباله‌های یک و دو رقمی که دانه دانه شمرده‌اید کمک بگیرید.

۱۰- عدد طبیعی n را چند جور می‌توان به کمک عددهای طبیعی کوچک‌تر یا مساوی خودش نوشت؟

راهنمایی ۱ (کلیک کنید)

مثلا عدد طبیعی را می‌توان به چهار روش نوشت. ببینید: ۳ و ۱+۲ و ۲+۱ و ۱+۱+۱

راهنمایی ۴ (کلیک کنید)

از رابطه‌ی بازگشتی کمک بگیرید.

۱۱- تعداد روش‌های نوشتن یک رشته‌ی n تایی از نشانه‌های + و - به طوری که هیچ دو نشانه‌ی - پشت سر هم نباشند را پیدا کنید.

راهنمایی ۱ (کلیک کنید)

از اصل جمع کمک بگیرید.

راهنمایی ۲ (کلیک کنید)

به این فکر کنید که این دنباله‌ی n تایی چند تا نشانه‌ی - دارد؟

راهنمایی ۳ (کلیک کنید)

فرض کنید این دنباله‌ی n تایی تنها k نشانه‌ی - دارد و تعداد این دنباله‌ها را بیاید.

راهنمایی ۴ (کلیک کنید)

آیا می‌توانید به کمک حل این مساله اثری از دنباله‌ی فیبوناچی در مثلث خیام پیدا کنید؟

۱۲- اگر a و b دو عدد طبیعی متمایز باشند ثابت کنید $\left(\large\begin{array} {GC+18} ab+1 \\ 2 \end{array}\right) = \left(\large\begin{array} a+1 \\ 2 \end{array}\right) \left(\large\begin{array} b+1 \\ 2 \end{array}\right) + \left(\large\begin{array} a \\ 2 \end{array}\right) \left(\large\begin{array} b \\ 2 \end{array}\right)$

راهنمایی ۱ (کلیک کنید)

به دو روش بشمارید.

۱۳- چند جور می‌توان یک کاشی به شکل زیر را در یک جدول m در n جای داد؟

راهنمایی ۱ (کلیک کنید)

جایی که خانه‌ی وسط (از ردیف سه‌تایی) کاشی در آن می‌نشیند را بررسی کنید.

۱۴- اگر S مجموعه‌ای n عضوی باشد، تعداد زوج مرتب‌هایی مانند (A, B) را بیابید که
الف) $A \cup B = S$

راهنمایی ۱ (کلیک کنید)

می‌توانید مثلا A را سه عضوی بگیرید و تعداد B ها را بشمارید.

راهنمایی ۲ (کلیک کنید)

تعداد عضوهای A را عددهای مختلف بگیرید و B ها را بشمارید و از اصل جمع کمک بگیرید.

راهنمایی ۳ (کلیک کنید) راه دوم

یک عضو دلخواه S را در نظر بگیرید و ببینید برای ساختن زوج مرتب (A, B) چه حالت‌هایی برای آن عضو قابل تصور است.

ب) $A \cap B = \emptyset$

راهنمایی ۱ (کلیک کنید)

همان راهنمایی‌های الف

پ) $|A \cap B| = 1$

راهنمایی ۱ (کلیک کنید)

یک عضو دلخواه S را در نظر بگیرید و فرض کنید که این همان عضو اشتراک دو مجموعه است.

راهنمایی ۲ (کلیک کنید)

اکنون می‌توانید از راه حل بخش ب کمک بگیرید

راهنمایی ۳ (کلیک کنید) راه دوم

یک عضو دلخواه S را در نظر بگیرید و فرض کنید که این همان عضو اشتراک دو مجموعه است. پس باید در هر دو مجموعه عضو باشد. اکنون فکر کنید که عضوهای دیگر S هر کدام کجا می‌توانند باشند.

۱۵- اگر S مجموعه‌ای n عضوی باشد، تعداد سه تایی مرتب‌هایی مانند (A, B, C) را بیابید که
الف) $A \subseteq B \subseteq C$
ب) $A \subseteq B \cap C$
پ) $A \subseteq B \cup C$
ت) $A \subseteq B , A\cap C=\emptyset$
ث) $A\cup B \subseteq C$
ج) $A\cap B \subseteq C$
چ) $A\cup B \cup C=S$
ح) $A\cap B \cap C=\emptyset$
خ) $A\cap B = A\cap C=\emptyset$
د) $A\cap B = \emptyset, A\cup C=S$

راهنمایی ۱ (کلیک کنید)

همان راهنمایی‌های پرسش ۱۴

۱۷- اگر S مجموعه‌ای n عضوی باشد، همه‌ی زوج مرتب‌هایی مانند (A, B) را که A و B هر دو زیرمجموعه‌ی S هستند را در مجموعه‌ای به نام K می‌ریزیم. به ازای هر عضو K عدد $|A\cap B|$ را یادداشت می‌کنیم. مجموع همه‌ی این عددهای یادداشت شده را پیدا کنید.

راهنمایی ۱ (کلیک کنید)

مجموعه‌ی S را ۲ عضوی بگیرید و مجموع خواسته شده را پیدا کنید.

راهنمایی ۲ (کلیک کنید)

مجموع خواسته شده برابر با $n4^{n-1}$ است.

راهنمایی ۳ (کلیک کنید) راه دوم

برای یک عضو دلخواه از S بررسی کنید که این عضو چند بار در اشتراک‌ها آمده است. این شمارش به درد می‌خورد چون هر بار باعث می‌شود که عدد یادداشت شده یک واحد بیش‌تر باشد.

۱۸- تعداد 2n نفر داریم که می‌خواهیم آن‌ها را در گروه‌های دو نفره دسته‌بندی کنیم. دو نفر در گروه سمتی ندارند و می‌توانید این دو نفر را یک مجموعه‌ی دو نفره بگیرید. هم چنین گروه‌ها نیز فرقی با هم ندارند. این دسته‌بندی به چند روش شدنی است؟

راهنمایی ۱ (کلیک کنید) راه۱

شاید یک راه خوب این باشد که گروه‌ها را متفاوت بگیرید و سپس فکری برای این خطا بکنید.

راهنمایی ۱ (کلیک کنید) راه۲

همه‌ی 2n نفر را به صف کنید و خیلی ساده دو نفر دو نفر از اول صف دسته‌ها را مشخص کنید. روشن است که این راه درست نیست ولی می‌توانید مشکلات آن را برطرف کنید.

راهنمایی ۱ (کلیک کنید) راه۳

تلاش کنید تا هم گروهی بلند قدترین فرد را مشخص کنید.

نمونه تمرين پويا

پرسش‌های ترکیبیات، شمارش سطح۱ - سری۱

پیمایش

ورود کاربر

نمونه تمرين پويا

پرسش‌های ترکیبیات، شمارش سطح۱ - سری۱

پیمایش