ترکیبیّات (شمارش)

پاسخنامه‌ی تحلیلی

«$\binom{11}{3}$» درست است. با تعریف متغیرهای جدید $y_1 = x_1 - 2$, $y_3 = x_3 - 1$, $y_4 = x_4 - 3$ و $y_2 = x_2$، معادله به $y_1 + y_2 + y_3 + y_4 = 8$ تبدیل می‌شود که تعداد جواب‌های نامنفی آن $\binom{8+4-1}{4-1} = \binom{11}{3}$ است. سایر گزینه‌ها از جبر اشتباه در جمع کل کاهش ها یا استفاده از فرمول اشتباه برای شرایط مثبت به دست می‌آیند. (ج) تلهٔ تستی: بعد از کم‌کردنِ مجموعِ کرانه‌هایِ پایین از $N$، حتماً باید $k-1$ (نه $k$) به آن عدد اضافه شود.

پاسخنامه‌ی تحلیلی

«120» درست است. با اصل شمول و عدم شمول، ابتدا تعداد اعداد بخش‌پذیر بر ۳، ۴ یا ۵ را محاسبه می‌کنیم: $|A| = 100$، $|B| = 75$، $|C| = 60$، $|A\cap B| = 25$ (اعداد بخش‌پذیر بر ۱۲)، $|A\cap C| = 20$ (اعداد بخش‌پذیر بر ۱۵)، $|B\cap C| = 15$ (اعداد بخش‌پذیر بر ۲۰)، $|A\cap B\cap C| = 5$ (اعداد بخش‌پذیر بر ۶۰). تعداد اعداد بخش‌پذیر بر حداقل یکی از آن‌ها برابر $100+75+60-25-20-15+5 = 180$ است. بنابراین تعداد اعداد بخش‌ناپذیر برابر $300 - 180 = 120$ است. (ج) تلهٔ تستی: برایِ سه یا بیشتر مجموعه، حتماً باید جملهٔ اشتراکِ سه‌تایی را هم اضافه کرد؛ فراموش‌کردنِ آن کم‌شماری می‌دهد.

پاسخنامه‌ی تحلیلی

«یا یک دنباله صعودی به طول ۴ یا یک دنباله نزولی به طول ۴ وجود دارد.» درست است. (الف) طبق قضیهٔ اردوس-سزکرس، هر دنباله‌ای با $mn+1$ عددِ متمایز، یا یک زیردنبالهٔ صعودی به طولِ $m+1$ دارد یا یک زیردنبالهٔ نزولی به طولِ $n+1$. با $m=n=3$، $mn+1=10$؛ چون دقیقاً ۱۰ عدد داریم، تضمین می‌شود که یا صعودیِ طولِ ۴ یا نزولیِ طولِ ۴ وجود دارد. (ب) «حتماً یک دنباله صعودی به طول ۳ وجود دارد» را نقض می‌کند دنبالهٔ کاملاً نزولی $10,9,8,\ldots,1$ که هیچ زیردنبالهٔ صعودیِ بلندتر از ۱ ندارد. «حتماً یک دنباله نزولی به طول ۴ وجود دارد» را نقض می‌کند دنبالهٔ کاملاً صعودی $1,2,\ldots,10$. «هم صعودیِ طولِ ۴ و هم نزولیِ طولِ ۴ وجود دارد» ادعایِ قوی‌تری از قضیه است که قضیه آن را تضمین نمی‌کند (فقط یکی از این دو تضمین شده، نه هر دو هم‌زمان). (ج) تلهٔ تستی: کوچک‌ترین گزینه (مثلِ «صعودیِ طولِ ۳») که به‌ظاهر ضعیف‌تر و «همیشه درست»‌تر به نظر می‌رسد، در واقع تضمین‌شده نیست چون یک دنبالهٔ کاملاً نزولی می‌تواند آن را نقض کند؛ باید دقیقاً همان کرانِ $m+1=n+1=4$ را که قضیه می‌دهد انتخاب کرد، نه کران‌های کوچک‌تر یا ادعاهایِ هم‌زمانِ قوی‌تر.

پاسخنامه‌ی تحلیلی

«150» درست است زیرا ابتدا همه حالات توزیع $3^5=243$ است. با استفاده از اصل شمول، حالت‌هایی که یک دانش‌آموز کتاب نگیرد را کم می‌کنیم: $\binom{3}{1} \times 2^5 = 96$. سپس حالت‌هایی که دو دانش‌آموز کتاب نگیرند را اضافه می‌کنیم: $\binom{3}{2} \times 1^5 = 3$. بنابراین تعداد مطلوب برابر $243 - 96 + 3 = 150$ است. (ج) تلهٔ تستی: فراموش‌کردنِ جملهٔ سومِ شمول‌وطرد ($+\binom{3}{2}1^5$) رایج‌ترین خطا در این نوع سؤال است.

پاسخنامه‌ی تحلیلی

«$144$» درست است. (الف) عدد بر $4$ بخش‌پذیر است اگر دو رقمِ آخرش (به‌عنوانِ یک عددِ دورقمی) بر $4$ بخش‌پذیر باشد. از میانِ ارقامِ $\{0,1,2,3,4,5\}$، زوج‌های متمایزِ دورقمیِ بخش‌پذیر بر $4$ عبارت‌اند از: $04,12,20,24,32,40,52$ (۷ حالت). برایِ زوج‌هایی که خودشان از رقمِ $0$ استفاده کرده‌اند ($04,20,40$؛ ۳ حالت)، سه رقمِ اول از میانِ ۴ رقمِ باقی‌مانده (که همگی غیرصفرند) به‌ترتیب چیده می‌شوند: $P(4,3)=24$ حالت، بدونِ نگرانی از صفرِ ابتدایی. برایِ زوج‌هایی که از $0$ استفاده نکرده‌اند ($12,24,32,52$؛ ۴ حالت)، رقمِ $0$ هنوز در دسترس است و باید از سرِ عدد کنار گذاشته شود: از $P(4,3)=24$ آرایش، آن‌هایی که با $0$ شروع می‌شوند ($P(3,2)=6$) کم می‌شوند: $24-6=18$. جمعِ کل: $3\times24+4\times18=72+72=144$. (ب) «$48$»، «$72$» و «$96$» از فراموش‌کردنِ برخی از ۷ زوجِ معتبر یا از اعمال‌نکردنِ درستِ قیدِ صفرِ ابتدایی برایِ هر دسته ناشی شده‌اند. (ج) تلهٔ تستی: باید زوج‌هایِ دورقمیِ بخش‌پذیر بر ۴ را به دو دسته «شاملِ رقمِ ۰» و «فاقدِ رقمِ ۰» تقسیم کرد، چون فقط در دستهٔ دوم قیدِ صفرِ ابتدایی برایِ سه رقمِ باقی‌مانده فعال می‌شود؛ یکسان‌فرض‌کردنِ هر دو دسته، رایج‌ترین خطایِ این سؤال است.

پاسخنامه‌ی تحلیلی

«$3$» درست است. (الف) طبقِ نتیجهٔ قضیهٔ اردوس–سزکرس، هر دنباله‌ای با بیش از $(k-1)^2$ عددِ متمایز، یا زیردنباله‌ای صعودی به طولِ $k$ دارد یا زیردنباله‌ای نزولی به طولِ $k$. برایِ $k=3$ داریم $(3-1)^2=4$ و چون $8>4$، وجودِ زیردنباله‌ای یکنوا به طولِ $3$ در هر دنبالهٔ ۸تایی تضمین شده است. (ب) وارسیِ مستقل (کرانِ بالا): برایِ $k=4$ باید $8>(4-1)^2=9$ باشد که برقرار نیست، پس طولِ $4$ تضمین نمی‌شود؛ نمونهٔ نقض: $3,2,1,\;6,5,4,\;8,7$ که بلندترین زیردنبالهٔ صعودی‌اش $3,6,8$ (طولِ ۳) و بلندترین زیردنبالهٔ نزولی‌اش $3,2,1$ (طولِ ۳) است. پس عددِ تضمین‌شده دقیقاً $3$ است. ردِ سایرِ گزینه‌ها: «$2$» کرانِ تضمین‌شده نیست چون *بزرگ‌ترین* طولِ تضمین‌شده پرسیده شده و همان مثالِ بالا نشان می‌دهد ۳ هم تضمین است؛ «$4$» با نمونهٔ نقضِ بالا رد می‌شود؛ «$5$» به‌طریقِ اولی رد می‌شود چون حتی $4$ هم تضمین نیست. (ج) تلهٔ تستی: کرانِ تضمین‌شده برایِ دنبالهٔ $n$تایی برابرِ $\lceil\sqrt{n}\rceil$ است؛ برایِ $n=8$ داریم $\lceil\sqrt{8}\rceil=3$. به‌کاربردنِ فرمولِ دوپارامتریِ $mn+1$ بدونِ قراردادنِ $m=n$، عددِ نادرست می‌دهد.

پاسخنامه‌ی تحلیلی

«$\frac{1}{126}$» درست است. ابتدا تعداد کل حالات چیدن ۹ کتاب متمایز: $9!$. برای حالت مطلوب: شرط اول و آخر ریاضی باشد، پس ۲ کتاب ریاضی را در دو انتها قرار می‌دهیم: $5 \times 4 = 20$ حالت. ۳ کتاب ریاضی باقی‌مانده را می‌چینیم: $3! = 6$ حالت. این ۳ کتاب، ۴ شکاف (بین آنها و دو طرف خارجی) ایجاد می‌کنند. برای اینکه هیچ دو فیزیکی کنار هم نباشند، باید ۴ کتاب فیزیک را در ۴ شکاف مختلف قرار دهیم: $4! = 24$ حالت. تعداد حالات مطلوب: $20 \times 6 \times 24 = 2880$. احتمال: $\frac{2880}{9!} = \frac{2880}{362880} = \frac{1}{126}$. (ج) تلهٔ تستی: باید دقت کرد که قیدِ «اول و آخر ریاضی» و قیدِ «هیچ دو فیزیک کنارِ هم نباشند» هم‌زمان اعمال شوند، نه جداگانه؛ ترتیبِ اعمالِ این دو قید در محاسبه اهمیت دارد.

پاسخنامه‌ی تحلیلی

«$\binom{16}{3} - \binom{12}{3}$» درست است. کل جواب‌های نامنفی با $x_1 \geq 2$: قرار می‌دهیم $y_1 = x_1 - 2$، پس $y_1 \geq 0$ و معادله $y_1 + x_2 + x_3 + x_4 = 13$ می‌شود. تعداد جواب‌ها: $\binom{13+4-1}{4-1} = \binom{16}{3}$. حال جواب‌هایی که $x_4 \leq 3$ را نقض می‌کنند (یعنی $x_4 \geq 4$) از کل کم می‌کنیم. برای $x_4 \geq 4$: قرار می‌دهیم $y_4 = x_4 - 4$ و $y_1 = x_1 - 2$ داریم. معادله $y_1 + x_2 + x_3 + y_4 = 9$ می‌شود. تعداد: $\binom{9+4-1}{4-1} = \binom{12}{3}$. پس پاسخ $\binom{16}{3} - \binom{12}{3}$ است. (ج) تلهٔ تستی: برایِ نامعادلهٔ $x_4\le c$ باید نقضِ آن ($x_4\ge c+1$) را از حالتِ نامحدود کم کرد، نه $x_4\ge c$.

پاسخنامه‌ی تحلیلی

«$\binom{11+4-1}{4-1} = \binom{14}{3}$» درست است. (الف) با جایگزینیِ $y_1=x_1-1$، $y_2=x_2-2$، $y_3=x_3$، $y_4=x_4-1$ (هر $y_i\ge0$)، معادله به $y_1+y_2+y_3+y_4=15-1-2-0-1=11$ تبدیل می‌شود؛ تعدادِ جواب‌هایِ نامنفیِ این معادله برابرِ $\binom{11+4-1}{4-1}=\binom{14}{3}=364$ است. (ب) «$\binom{18}{3}$» اصلاً قیدهایِ حداقلی را از $N=15$ کم نکرده؛ «$\binom{15-4}{4-1} = \binom{11}{3}$» به‌جایِ کم‌کردنِ مجموعِ دقیقِ قیدها ($1+2+0+1=4$)، به‌اشتباه همان عددِ ۴ را به‌کار برده و فراموش کرده که پس از کم‌کردن باید $+k-1=+3$ هم به توانِ بالا اضافه شود؛ «$\binom{11+4}{4} = \binom{15}{4}$» فرمولِ ستاره‌وخط را نادرست به‌کار برده ($\binom{n+k}{k}$ به‌جایِ $\binom{n+k-1}{k-1}$). (ج) تلهٔ تستی: بعد از کم‌کردنِ مجموعِ کرانه‌هایِ پایین از $N$، حتماً باید $k-1$ (نه $k$) به آن عدد اضافه شود تا فرمولِ درستِ ستاره‌وخط به دست آید؛ فراموشیِ همین «منهای‌یک» رایج‌ترین خطایِ این خانواده از سؤال‌هاست.

پاسخنامه‌ی تحلیلی

«$60$» درست است زیرا تعداد جایگشت‌های $6$ شیء که $3$ تا از یک نوع ($3$)، $2$ تا از نوع دیگر ($2$) و $1$ تا از نوع سوم ($1$) هستند برابر است با $\frac{6!}{3!\,2!\,1!} = \frac{720}{12} = 60$. (ج) تلهٔ تستی: باید مخرجِ فرمولِ چندجمله‌ای شاملِ فاکتوریلِ *همهٔ* ارقامِ تکراری باشد، حتی رقمی که فقط یک‌بار آمده (که فاکتوریلش ۱ است).