۱۰۰ هزار تومان هدیهٔ ثبت‌نام، تا ۱ میلیونبا ثبت‌نام گردونهٔ هدیه را بچرخان: دست‌کم ۱۰۰٬۰۰۰ تومان و تا ۱٬۰۰۰٬۰۰۰ تومان اعتبار هدیه، بدون کارت بانکیگردونهٔ هدیه۱ میلیون برای تو، ۱ میلیون برای دوستتدوستانت را دعوت کن: برای هر دوستی که فعال شود ۱٬۰۰۰٬۰۰۰ تومان اعتبار هدیه می‌گیری و خودش هم ۱٬۰۰۰٬۰۰۰ تومانجوایز
1xAi

خلاصه درس فصل ۳ ریاضیات گسسته دوازدهم؛ درسنامه و نکات مهم

«ترکیبیّات (شمارش)»: ۹ درس، هر کدام با توضیح مفاهیم، مثال حل‌شده و نکات مهم.

  • ریاضیات گسسته
  • پایهٔ دوازدهم
  • صفحهٔ ۵۵ تا ۸۶

این درسنامه را هوش مصنوعی 1xAi از روی صفحه‌های همان درس در کتاب درسی نوشته است (برچسب «تولید هوش مصنوعی»). کنار توضیح‌ها شمارهٔ صفحهٔ کتاب آمده تا با کتاب مقایسه کنی، و مثال حل‌شدهٔ هر درس یک بار دیگر جداگانه حل و بررسی شده؛ مثالی که درست درنیامده حذف شده است.

درس ۱ · صفحهٔ ۵۵ تا ۵۹ · حدود ۱۵ دقیقه · تولید هوش مصنوعی

درس ۱ مباحثی در ترکیبیات

در این درس یاد می‌گیری با دسته‌بندی اشیا، تشخیص الگوهای چیدن و حذف جابه‌جایی‌های تکراری یا بی‌اثر، مسئله‌های جایگشت و تقسیم افراد به گروه‌های مشخص را حل کنی.

پیش از شروع

اگر دو حرفِ یک رمز یکسان باشند، آیا جابه‌جا کردنشان واقعاً رمز تازه‌ای می‌سازد؟ این موضوع چه اثری روی شمارش رمزها دارد؟

جابه‌جایی دو حرف یکسان، رمز تازه‌ای نمی‌سازد؛ پس شمردن همهٔ جابه‌جایی‌ها می‌تواند باعث چندبارشماری شود. در این درس یاد می‌گیریم چه وقت اشیا را یک بسته حساب کنیم و چه وقت حالت‌های تکراری را با تقسیم کنار بگذاریم.

کنار هم، مثل یک بسته

کنار هم، مثل یک بسته

فرض کن چند دوست می‌خواهند برای عکس یادگاری در یک ردیف بایستند و بعضی از آن‌ها اصرار دارند کنار هم باشند. چطور این شرط را در شمارش رعایت کنیم؟

افرادی را که باید کنار هم بمانند، موقتاً یک بسته در نظر بگیر. حالا این بسته، درست مثل یک نفر، در کنار بقیه جابه‌جا می‌شود. اگر با این کار در مجموع mm شیء متمایز داشته باشیم، ترتیب آن‌ها m!m! حالت دارد.

اما بسته را نباید بسته نگه داریم! افراد داخل آن هم می‌توانند جای خود را عوض کنند، بدون اینکه شرط کنار هم بودن از بین برود. اگر بسته شامل rr فرد متمایز باشد، برای هر ترتیب بیرونی، r!r! ترتیب داخلی داریم. پس طبق اصل ضرب:

تعداد کل=m!×r!\text{تعداد کل}=m!\times r!

اگر چند گروه باید جداگانه کنار هم بمانند، هر گروه را یک بسته می‌گیریم و تعداد ترتیب‌های داخلی همهٔ بسته‌ها را در تعداد ترتیب‌های بیرونی ضرب می‌کنیم. اشتباه رایج این است که فقط جای بسته‌ها را بشماریم و ترتیب داخلشان را فراموش کنیم.

کتاب درسی، صفحهٔ ۵۶

چیدن یک‌درمیان

چیدن یک‌درمیان

فرض کن برای عکس یادگاری، دانش‌آموزان دو پایه باید طوری در یک ردیف بایستند که هیچ دو نفرِ هم‌پایه کنار هم نباشند. این بار به‌جای بسته‌سازی، ابتدا الگوی جای پایه‌ها را مشخص می‌کنیم؛ هنوز کاری نداریم چه کسی در هر جایگاه می‌ایستد.

اگر تعداد دو گروه برابر باشد، دو الگو داریم: ردیف یا با گروه اول شروع می‌شود یا با گروه دوم. پس از انتخاب الگو، افراد هر گروه را در جایگاه‌های مخصوص خودشان جابه‌جا می‌کنیم و تعداد حالت‌ها را طبق اصل ضرب به دست می‌آوریم.

اگر یک گروه دقیقاً یک نفر بیشتر داشته باشد، فقط یک الگو ممکن است: گروه پرجمعیت‌تر باید هم در ابتدای ردیف باشد و هم در انتهای آن. اگر اختلاف تعداد بیشتر از یک نفر باشد، چیدن یک‌درمیان ممکن نیست.

نکتهٔ کلیدی: تعداد الگوهای جای گروه‌ها را با تعداد ترتیب‌های افراد اشتباه نگیر؛ ابتدا الگو، سپس ترتیب افراد!

کتاب درسی، صفحهٔ ۵۷

حذف ترتیب‌های تکراری

حذف ترتیب‌های تکراری

فرض کن چند مهره را در یک ردیف می‌چینی و دو مهره کاملاً هم‌شکل و هم‌رنگ‌اند. اگر فقط جای این دو را عوض کنی، آیا ردیف تازه‌ای دیده می‌شود؟ نه! پس هر جابه‌جایی لزوماً یک حالت تازه نیست.

برای شمارش، ابتدا تصور می‌کنیم همهٔ اشیا برچسب دارند و متمایزند؛ در این صورت n!n! ترتیب داریم. حالا برچسب‌های اشیای یکسان را پاک می‌کنیم. اگر یک نوع شیء، kk بار تکرار شده باشد، هر ترتیب واقعی را k!k! بار شمرده‌ایم؛ بنابراین باید بر k!k! تقسیم کنیم، نه بر kk.

اگر چند نوع شیء تکراری داشته باشیم، همین کار را برای هر نوع انجام می‌دهیم. با تعدادهای n1,…,nkn_1,\ldots,n_k و شرط n1+⋯+nk=nn_1+\cdots+n_k=n، تعداد ترتیب‌های متمایز برابر است با:

n!n1!×n2!×⋯×nk!\displaystyle \frac{n!}{n_1!\times n_2!\times\cdots\times n_k!}

یادت باشد: اینجا اشیای یکسان مجبور نیستند کنار هم باشند؛ تقسیم می‌کنیم چون جابه‌جایی آن‌ها بی‌اثر است، نه چون یک بسته‌اند.

کتاب درسی، صفحهٔ ۵۸

افراد متفاوت، جابه‌جایی بی‌اثر

افراد متفاوت، جابه‌جایی بی‌اثر

فرض کن با دوستانت به اردو رفته‌ای. برای مشخص‌کردن محل اسکان، مهم است چه کسانی در هر اتاق‌اند؛ نه اینکه نامشان را با چه ترتیبی بنویسیم. پس حتی وقتی همهٔ افراد متفاوت‌اند، بعضی جابه‌جایی‌ها حالت تازه‌ای نمی‌سازند.

برای اسکان 99 نفر در سه اتاق مشخص با ظرفیت‌های 22، 33 و 44 نفر، می‌توانیم ابتدا افراد را به 9!9! ترتیب در یک صف بچینیم و به‌ترتیب به اتاق‌ها بفرستیم. اما جابه‌جایی افراد داخل هر اتاق، ساکنان آن را تغییر نمی‌دهد. بنابراین هر اسکان را 2!×3!×4!2!\times3!\times4! بار شمرده‌ایم و تعداد اسکان‌ها برابر است با:

9!2!×3!×4!\displaystyle \frac{9!}{2!\times3!\times4!}

راه دیگر، انتخاب پیاپی است: ابتدا ساکنان اتاق اول را انتخاب کنیم، سپس از افراد باقی‌مانده ساکنان اتاق دوم را؛ بقیه به اتاق سوم می‌روند:

(92)(73)(44)\displaystyle \binom{9}{2}\binom{7}{3}\binom{4}{4}

این دو روش یک نتیجه دارند. دقت کن: افراد یکسان نیستند؛ فقط ترتیبشان درون اتاق بی‌اثر است.

کتاب درسی، صفحهٔ ۵۹

مثال حل‌شده

با ارقام 1,1,1,2,2,3,41,1,1,2,2,3,4 چند عدد هفت‌رقمی می‌توان نوشت، اگر هر رقمِ داده‌شده دقیقاً یک بار استفاده شود؟

  1. در مجموع 77 رقم داریم؛ اگر همه متمایز بودند، تعداد ترتیب‌ها 7!7! بود.

  2. سه رقم 11 یکسان‌اند؛ جابه‌جایی آن‌ها عدد تازه‌ای نمی‌سازد، پس باید بر 3!3! تقسیم کنیم.

  3. دو رقم 22 نیز یکسان‌اند؛ برای حذف شمارش‌های تکراریِ آن‌ها، بر 2!2! هم تقسیم می‌کنیم.

  4. رقم‌های 33 و 44 هرکدام یک بار آمده‌اند و عامل تکرار دیگری نداریم؛ همچنین چون صفر نداریم، همهٔ ترتیب‌ها عدد هفت‌رقمی هستند.

  5. بنابراین تعداد عددها برابر است با 7!3!×2!=50406×2=420\frac{7!}{3!\times2!}=\frac{5040}{6\times2}=420.

جواب: تعداد عددهای متمایز برابر 7!3!×2!=420\frac{7!}{3!\times2!}=420 است.

نکات مهم

  • برای کنار هم نگه‌داشتن اشیا، آن‌ها را بسته‌بندی می‌کنیم و تعداد ترتیب‌های بسته‌ها را در تعداد ترتیب‌های داخلی ضرب می‌کنیم.
  • در چیدن یک‌درمیان، ابتدا الگوهای ممکنِ جای دو گروه را مشخص می‌کنیم و سپس ترتیب افراد هر گروه را می‌شماریم.
  • برای حذف شمارش‌های تکراری یا بی‌اثر، تعداد کل جایگشت‌ها را بر تعداد جابه‌جایی‌هایی تقسیم می‌کنیم که نتیجهٔ تازه‌ای نمی‌سازند.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۲ · صفحهٔ ۵۹ تا ۶۲ · حدود ۱۵ دقیقه · تولید هوش مصنوعی

درس اول: مباحثی در ترکیبیات

در این درس یاد می‌گیری با تشخیص جابه‌جایی‌های بی‌اثر و روش ستاره و جداکننده، انتخاب‌های با تکرار و جواب‌های صحیح معادله‌های جمع را بشماری و مربع لاتین را از روی شرط سطرها و ستون‌هایش تشخیص بدهی.

پیش از شروع

اگر گل‌فروش از هر نوع گل به‌اندازهٔ کافی داشته باشد، برای شمردن دسته‌گل‌های متفاوت باید شاخه‌ها را یکی‌یکی از هم تشخیص بدهیم؟ چطور می‌توانیم بدون فهرست‌کردن همهٔ دسته‌گل‌ها، تعدادشان را پیدا کنیم؟

وقتی فقط نوع گل‌ها مهم است، جابه‌جایی دو شاخهٔ هم‌نوع دسته‌گل تازه‌ای نمی‌سازد. می‌توانیم شاخه‌ها را با ستاره و مرز میان نوع‌ها را با خط عمودی نشان بدهیم؛ آن‌وقت مسئلهٔ انتخاب گل به مسئله‌ای آشنا در شمارش تبدیل می‌شود.

کدام جابه‌جایی حالت تازه می‌سازد؟

کدام جابه‌جایی حالت تازه می‌سازد؟

فرض کن همراه دوستانت به هتل رفته‌ای. اگر تو و دوستت در یک اتاق باشید و فقط جای نشستن‌تان را عوض کنید، آیا تقسیم افراد بین اتاق‌ها تغییر کرده است؟ نه؛ برای این مسئله، هم‌اتاقی‌ها مهم‌اند، نه ترتیب افراد داخل اتاق.

برای اسکان 99 نفر در اتاق‌های 22، 33 و 44 نفره، می‌توانیم افراد را در یک صف بچینیم: 22 نفر اول برای اتاق اول، 33 نفر بعدی برای اتاق دوم و بقیه برای اتاق سوم. این صف 9!9! حالت دارد، اما چندین صف، یک اسکان یکسان را نشان می‌دهند.

جابه‌جایی افراد داخل اتاق‌ها، به‌ترتیب 2!2!، 3!3! و 4!4! حالت دارد و هیچ‌کدام اسکان تازه‌ای نمی‌سازد. بنابراین تعداد اسکان‌ها برابر است با:

9!2!×3!×4!\displaystyle \frac{9!}{2!\times3!\times4!}

دقت کن: اتاق‌ها مشخص‌اند؛ قرار نیست خودِ اتاق‌ها را جابه‌جا کنیم. فقط تکرار ناشی از ترتیب افراد داخل هر اتاق را حذف می‌کنیم.

کتاب درسی، صفحهٔ ۵۹

ستاره‌ها و جداکننده‌ها

ستاره‌ها و جداکننده‌ها

فرض کن می‌خواهی از مریم، رُز و میخک، دسته‌گل انتخاب کنی. فقط تعداد شاخه‌های هر نوع مهم است، نه ترتیب برداشتن شاخه‌ها. پس هر شاخه را با یک ستاره نشان می‌دهیم و نوع‌ها را با خط عمودی از هم جدا می‌کنیم.

ترتیب نوع‌ها را ثابت نگه دار: مریم، رُز، میخک. نمایش ⋆⋆∣∣⋆\star\star\mid\mid\star یعنی 22 شاخه مریم، هیچ شاخه رُز و 11 شاخه میخک. بخش خالی هم معنا دارد: از آن نوع گل انتخاب نکرده‌ایم. جداکننده می‌تواند ابتدا یا انتهای نمایش هم باشد.

برای kk نوع گل، به k−1k-1 جداکننده نیاز داریم. با انتخاب nn شاخه، در مجموع n+k−1n+k-1 جایگاه داریم. کافی است جای جداکننده‌ها را انتخاب کنیم؛ بقیهٔ جایگاه‌ها خودبه‌خود ستاره می‌شوند:

(n+k−1k−1)\binom{n+k-1}{k-1}

این همان شمارش جایگشت‌های دارای تکرار است:

(n+k−1)!n!(k−1)!\frac{(n+k-1)!}{n!(k-1)!}

چون عوض‌کردن ستاره‌ها با یکدیگر یا جداکننده‌ها با یکدیگر، انتخاب تازه‌ای نمی‌سازد. این روش وقتی به کار می‌آید که از هر نوع به‌اندازهٔ کافی موجود باشد و انتخاب‌نکردن یک نوع هم مجاز باشد.

کتاب درسی، صفحهٔ ۶۰

اول سهم اجباری، بعد انتخاب آزاد

اول سهم اجباری، بعد انتخاب آزاد

فرض کن می‌خواهی دسته‌گلی بسازی که از هر نوع گل، دست‌کم یک شاخه داشته باشد. این بار نمی‌توانی همهٔ شاخه‌ها را آزادانه انتخاب کنی؛ چون ممکن است یک نوع گل اصلاً در دسته‌گل نباشد.

راه ساده این است: اول شرط را تأمین کن، بعد باقی‌مانده را بشمار. از هر نوع گل یک شاخه کنار بگذار. اگر تعداد کل شاخه‌ها nn و تعداد نوع‌ها kk باشد، با این کار kk شاخه انتخاب شده و n−kn-k شاخه برای انتخاب آزاد باقی می‌ماند. البته باید n≥kn\ge k باشد؛ وگرنه تأمین شرط ممکن نیست.

حالا شاخه‌های باقی‌مانده را همچنان از میان همهٔ kk نوع گل انتخاب می‌کنی؛ چون «حداقل یک شاخه» به معنی «فقط یک شاخه» نیست. پس با روش ستاره و جداکننده، تعداد حالت‌ها برابر است با:

((n−k)+k−1k−1)=(n−1k−1)\binom{(n-k)+k-1}{k-1}=\binom{n-1}{k-1}

این کنارگذاشتن، یک روش شمارش است: از هر دسته‌گل مجاز، با برداشتن یک شاخه از هر نوع، دقیقاً یک انتخاب آزادِ باقی‌مانده به دست می‌آید و برعکس.

کتاب درسی، صفحهٔ ۶۰

از دسته‌گل تا جواب معادله

از دسته‌گل تا جواب معادله

معادلهٔ x1+x2+⋯+xk=nx_1+x_2+\cdots+x_k=n را مثل انتخاب دسته‌گل ببین: xix_i تعداد شاخه‌های نوع ii است. هر انتخاب، دقیقاً یک جواب می‌سازد و هر جواب صحیح و نامنفی، دقیقاً یک انتخاب. نامنفی یعنی صفر هم مجاز است؛ پس ممکن است از یک نوع گل چیزی انتخاب نکنیم. بنابراین تعداد جواب‌ها برابر است با:

(n+k−1k−1)\displaystyle \binom{n+k-1}{k-1}

حالا اگر جواب‌ها مثبت باشند، هر متغیر باید دست‌کم 11 باشد. با گذاشتن yi=xi−1y_i=x_i-1، متغیرهای تازه نامنفی می‌شوند و مجموعشان n−kn-k است. پس برای n≥kn\ge k تعداد جواب‌های مثبت می‌شود:

((n−k)+k−1k−1)=(n−1k−1)\displaystyle \binom{(n-k)+k-1}{k-1}=\binom{n-1}{k-1}

برای حداقل‌های دیگر هم همین فکر را به کار ببر: اگر xi≥aix_i\ge a_i، بگذار yi=xi−aiy_i=x_i-a_i. مجموع تازه برابر n−(a1+⋯+ak)n-(a_1+\cdots+a_k) می‌شود و حالا جواب‌های نامنفی را می‌شماری. حواست باشد در جواب‌های صحیح، شرط xi>2x_i>2 یعنی حداقل مقدار 33 است، نه 22!

کتاب درسی، صفحهٔ ۶۱

مربع لاتین و برنامهٔ بدون تداخل

مربع لاتین و برنامهٔ بدون تداخل

فرض کن می‌خواهیم برای سه کلاس، در سه نوبت، برنامهٔ تدریس بچینیم. هر مدرس باید در هر کلاس دقیقاً یک‌بار درس بدهد؛ همچنین نباید در یک نوبت، هم‌زمان در دو کلاس باشد!

نام مدرس‌ها را با عددهای 11، 22 و 33 نشان می‌دهیم. سطرها را به کلاس‌ها و ستون‌ها را به نوبت‌ها اختصاص می‌دهیم. حالا دو شرط داریم:

  • در هر سطر عدد تکراری نباشد: هیچ مدرس در یک کلاس دوبار تدریس نمی‌کند.
  • در هر ستون عدد تکراری نباشد: هیچ مدرس هم‌زمان در دو کلاس نیست.

این همان ایدهٔ مربع لاتین است: جدولی به اندازهٔ n×nn\times n که با عددهای 11 تا nn پر می‌شود و در هیچ سطر یا ستونش عدد تکراری ندارد. چون هر سطر و ستون nn خانه دارد، هر عدد در آن دقیقاً یک‌بار می‌آید.

حواست باشد شرط مربوط به سطرها و ستون‌ها است؛ تکرار یک عدد روی قطر، به‌خودی‌خود اشکالی ندارد.

کتاب درسی، صفحهٔ ۶۲

مثال حل‌شده

معادلهٔ x1+x2+x3+x4+x5=14x_1+x_2+x_3+x_4+x_5=14 چند جواب صحیح و نامنفی دارد، اگر x1>1x_1>1 و x3>3x_3>3 باشد؟

  1. چون متغیرها صحیح‌اند، شرط‌ها را به صورت x1≥2x_1\ge2 و x3≥4x_3\ge4 می‌نویسیم.

  2. حداقل‌های اجباری را کنار می‌گذاریم: y1=x1−2y_1=x_1-2 و y3=x3−4y_3=x_3-4؛ هر دو متغیر جدید صحیح و نامنفی‌اند.

  3. با جای‌گذاری، معادله به y1+x2+y3+x4+x5=8y_1+x_2+y_3+x_4+x_5=8 تبدیل می‌شود، زیرا 14−2−4=814-2-4=8.

  4. اکنون مجموع پنج متغیر صحیح و نامنفی برابر با 88 است؛ پس با هشت ستاره و چهار جداکننده، تعداد جواب‌ها (8+5−15−1)=(124)\binom{8+5-1}{5-1}=\binom{12}{4} می‌شود.

  5. حساب می‌کنیم: (124)=12×11×10×94×3×2×1=495\binom{12}{4}=\frac{12\times11\times10\times9}{4\times3\times2\times1}=495؛ با برگرداندن سهم‌های اجباری، هر جواب جدید دقیقاً یک جواب مطلوب می‌دهد.

جواب: تعداد جواب‌های مطلوب (124)=495\binom{12}{4}=495 است.

نکات مهم

  • برای تقسیم افراد متمایز میان اتاق‌های مشخص، جایگشت‌های بی‌اثر داخل هر اتاق را حذف می‌کنیم.
  • انتخاب دلخواه nn شیء از kk نوع و شمارش جواب‌های صحیح و نامنفیِ x1+⋯+xk=nx_1+\cdots+x_k=n هر دو با (n+k−1k−1)\binom{n+k-1}{k-1} انجام می‌شوند؛ اگر حداقل اجباری داریم، ابتدا آن را کنار می‌گذاریم.
  • در مربع لاتینِ n×nn\times n، هر یک از عددهای 11 تا nn در هر سطر و هر ستون دقیقاً یک‌بار می‌آید.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۳ · صفحهٔ ۶۲ تا ۶۴ · حدود ۱۳ دقیقه · تولید هوش مصنوعی

مربع‌های لاتین

در این درس یاد می‌گیری مربع لاتین را تشخیص بدهی و بسازی، توضیح بدهی چرا جابه‌جایی سطرها و ستون‌ها یا جایگشت عددها آن را لاتین نگه می‌دارد و متعامد بودن دو مربع لاتین را بررسی کنی.

پیش از شروع

چطور می‌توان برای سه مدرس، سه کلاس و سه جلسه برنامه‌ای چید که هر مدرس در هر کلاس دقیقاً یک‌بار تدریس کند و هیچ‌وقت هم‌زمان در دو کلاس نباشد؟

اگر نام مدرس‌ها را در جدولی بگذاریم که سطرهایش کلاس‌ها و ستون‌هایش جلسه‌ها باشند، کافی است هیچ نامی در یک سطر یا یک ستون تکرار نشود. با جایگزین کردن نام‌ها با عددها، به ساختاری می‌رسیم که «مربع لاتین» نام دارد.

جدولی بدون تکرار

جدولی بدون تکرار

برای برنامه‌ریزی مدرس‌ها، سطرها را کلاس‌ها و ستون‌ها را جلسه‌ها در نظر بگیر. نام سه مدرس را با عددهای 11، 22 و 33 نشان می‌دهیم. تکرار نشدن یک عدد در هر سطر یعنی هیچ مدرس در یک کلاس دوبار تدریس نمی‌کند؛ تکرار نشدن آن در هر ستون یعنی هیچ مدرس هم‌زمان در دو کلاس نیست.

مربع لاتین یک جدول n×nn \times n است که با عددهای 11 تا nn پر می‌شود و در هیچ سطر و هیچ ستونش عدد تکراری ندارد. به هر عدد داخل جدول، «درایه» می‌گوییم.

چرا هر عدد دقیقاً یک‌بار در هر سطر می‌آید؟ چون هر سطر nn خانه دارد و فقط nn عدد مجاز داریم؛ بدون تکرار، باید از همهٔ آن‌ها استفاده کنیم. همین استدلال برای ستون‌ها هم برقرار است.

پس برای تشخیص مربع لاتین، هم سطرها و هم ستون‌ها را بررسی کن. تکرار یک عدد در خانه‌های واقع بر یک قطر، به‌خودی‌خود اشکالی ندارد.

کتاب درسی، صفحهٔ ۶۲

جابه‌جاییِ مجاز

جابه‌جاییِ مجاز

اگر جای دو سطرِ یک مربع لاتین را به‌طور کامل عوض کنیم، آیا ممکن است عددی تکراری شود؟ بیایید سطرها و ستون‌ها را جدا بررسی کنیم.

  • در هر سطر: عددها همان عددهای قبلی‌اند؛ فقط سطر به جای تازه‌ای رفته است. پس تکراری ایجاد نمی‌شود.
  • در هر ستون: تنها جای دو عدد عوض شده است؛ نه عددی اضافه شده و نه عددی حذف شده است. پس اینجا هم تکراری نداریم.

برای جابه‌جایی دو ستون هم همین استدلال برقرار است: ستون‌ها دست‌نخورده جابه‌جا می‌شوند و در هر سطر فقط ترتیب عددها تغییر می‌کند.

در مثال برنامهٔ مدرس‌ها، عوض کردن دو سطر یعنی عوض کردن برنامهٔ کامل دو کلاس؛ این کار هیچ مدرسی را هم‌زمان به دو کلاس نمی‌فرستد.

نکتهٔ مهم: این نتیجه دربارهٔ جابه‌جایی دو سطر کامل یا دو ستون کامل است؛ جابه‌جایی دلخواه دو خانه لزوماً مربع را لاتین نگه نمی‌دارد.

کتاب درسی، صفحهٔ ۶۳

ساختن مربع چرخشی

ساختن مربع چرخشی

آیا برای ساختن مربع لاتین باید هر بار با آزمون‌وخطا خانه‌ها را پر کنیم؟ نه؛ یک روش منظم داریم: در هر سطر، عددهای سطر قبلی را یک خانه به راست بچرخان؛ عدد آخر هم به ابتدای سطر می‌آید. مثل چند نفر که دور یک میز، همگی یک صندلی جابه‌جا می‌شوند.

برای ساختن مربع n×nn \times n، سطر اول را با عددهای 11 تا nn پر می‌کنیم و همین چرخش را تا کامل شدن nn سطر ادامه می‌دهیم.

چرا نتیجه لاتین است؟

  • در هر سطر فقط جای عددها عوض شده است؛ پس هر عدد دقیقاً یک‌بار حضور دارد.
  • در هر ستون، با پایین رفتن از یک سطر به سطر بعد، عدد متفاوتی می‌بینیم. پس از nn سطر، همهٔ عددهای 11 تا nn دقیقاً یک‌بار در آن ستون آمده‌اند.

پس این روش برای هر عدد طبیعی nn جواب می‌دهد؛ ساختن مربع لاتین به چند اندازهٔ خاص محدود نیست!

کتاب درسی، صفحهٔ ۶۴

تغییر نامِ عددها

تغییر نامِ عددها

فرض کن به‌جای عوض کردن جای خانه‌ها، فقط «نامِ عددها» را عوض کنیم. مثلاً در یک مربع لاتینِ 3×33 \times 3، این قانون را در همهٔ خانه‌ها اجرا کنیم:

1↦2,2↦3,3↦11\mapsto 2,\qquad 2\mapsto 3,\qquad 3\mapsto 1

این قانون یک جایگشت است: هر عدد به یک عدد مشخص تبدیل می‌شود و عددهای متفاوت، نام‌های تازهٔ متفاوت می‌گیرند. درست مثل اینکه نام سه مدرس را با سه نام تازه عوض کنیم؛ برنامهٔ تدریس آن‌ها تغییری نمی‌کند.

چرا مربع تازه لاتین می‌ماند؟ در هر سطر و ستونِ مربع اولیه، همهٔ عددها دقیقاً یک‌بار حضور دارند. پس بعد از تغییر نام هم، همهٔ عددهای تازه دقیقاً یک‌بار ظاهر می‌شوند؛ نه عددی حذف می‌شود و نه تکراری به وجود می‌آید.

دو شرط مهم: قانونِ جایگزینی باید در سراسر جدول یکسان باشد و دو عدد متفاوت نباید به یک عدد تبدیل شوند. پس تغییر دلخواهِ چند خانه، لزوماً مربع لاتین نمی‌سازد.

کتاب درسی، صفحهٔ ۶۴

دو مربع متعامد

دو مربع متعامد

تا اینجا هر مربع را جداگانه بررسی می‌کردیم؛ حالا می‌خواهیم رابطهٔ دو مربع لاتین را بررسی کنیم. دو مربع باید متمایز و هم‌مرتبه باشند؛ یعنی تعداد سطرها و ستون‌هایشان برابر باشد.

مربع‌ها را AA و BB بنام. در هر خانه، عدد مربع AA را اول و عدد همان خانه از مربع BB را دوم بنویس تا یک زوج مرتب بسازی. مثلاً اگر این دو عدد 22 و 33 باشند، زوج آن خانه (2,3)(2,3) است. ترتیب مهم است: (2,3)(2,3) با (3,2)(3,2) فرق دارد.

اگر در کل جدولِ زوج‌ها هیچ زوجی تکرار نشود، دو مربع متعامدند. کتاب این کنار هم گذاشتن را با عددهای دورقمی نمایش می‌دهد؛ مثلاً زوج (2,3)(2,3) را به صورت 2323 می‌نویسد.

تصور کن یک جدول نوع غذا و دیگری نوع نوشیدنی را تعیین می‌کند؛ متعامد بودن یعنی هیچ ترکیب «غذا و نوشیدنی» دوباره ارائه نشود. دقت کن: لاتین بودنِ هر دو مربع به‌تنهایی کافی نیست؛ باید زوج‌های هم‌مکان را هم بررسی کنی.

کتاب درسی، صفحهٔ ۶۴

مثال حل‌شده

بررسی کن آیا دو مربع زیر لاتین و متعامدند:

A=(123231312)B=(123312231)A=\begin{pmatrix}1&2&3\\2&3&1\\3&1&2\end{pmatrix}\qquad B=\begin{pmatrix}1&2&3\\3&1&2\\2&3&1\end{pmatrix}

  1. ابتدا هر جدول را جدا بررسی می‌کنیم: در هر سطر و هر ستونِ هر دو جدول، عددهای 11، 22 و 33 دقیقاً یک‌بار آمده‌اند؛ پس هر دو مربع لاتین‌اند. همچنین هم‌مرتبه و متمایزند.

  2. در هر خانه، درایهٔ AA را مؤلفهٔ اول و درایهٔ هم‌مکانِ آن در BB را مؤلفهٔ دوم می‌گذاریم. مثلاً خانهٔ سطر دوم و ستون اول، زوج (2,3)(2,3) را می‌دهد.

  3. جدول زوج‌ها چنین می‌شود: ((1,1)(2,2)(3,3)(2,3)(3,1)(1,2)(3,2)(1,3)(2,1))\begin{pmatrix}(1,1)&(2,2)&(3,3)\\(2,3)&(3,1)&(1,2)\\(3,2)&(1,3)&(2,1)\end{pmatrix}.

  4. زوج‌ها را در کل جدول مقایسه می‌کنیم، نه فقط در هر سطر یا ستون: با مؤلفهٔ اولِ 11، زوج‌های (1,1)(1,1)، (1,2)(1,2) و (1,3)(1,3) آمده‌اند؛ برای مؤلفه‌های اولِ 22 و 33 نیز هر سه مؤلفهٔ دوم دقیقاً یک‌بار دیده می‌شوند. پس هیچ زوجی تکرار نشده و دو مربع متعامدند.

جواب: هر دو جدول مربع لاتین‌اند و چون هر 99 زوج مرتبِ حاصل متمایزند، مربع‌های AA و BB متعامدند.

نکات مهم

  • در مربع لاتین n×nn\times n، هر عدد از 11 تا nn در هر سطر و هر ستون دقیقاً یک‌بار می‌آید و روش چرخشی برای هر عدد طبیعی nn چنین مربعی می‌سازد.
  • جابه‌جایی سطرهای کامل یا ستون‌های کامل و نیز تغییر همهٔ عددها با یک جایگشت ثابت، لاتین بودن مربع را حفظ می‌کند.
  • دو مربع لاتین متمایز و هم‌مرتبه زمانی متعامدند که زوج‌های مرتبِ حاصل از درایه‌های هم‌مکانشان هیچ تکراری نداشته باشند.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۴ · صفحهٔ ۶۴ تا ۷۰ · حدود ۱۵ دقیقه · تولید هوش مصنوعی

فصل سوم: ترکیبیّات (شمارش)

در این درس یاد می‌گیری دو مربع لاتین متعامد را تشخیص بدهی، اثر جایگشت نمادها را توضیح بدهی و از تعامد و ایدهٔ ساخت مربع‌های فرد برای برنامه‌ریزی بدون تکرار استفاده کنی.

پیش از شروع

سه برادر می‌خواهند در سه روز، سه کت و سه پیراهن را طوری بپوشند که هر نفر هر لباس را یک‌بار استفاده کند و هر کت هم دقیقاً یک‌بار با هر پیراهن همراه شود. آیا می‌شود برنامه‌ای چید که همهٔ این شرط‌ها را هم‌زمان داشته باشد؟

بله؛ می‌توان برنامهٔ کت‌ها و برنامهٔ پیراهن‌ها را با دو مربع لاتین تنظیم کرد. اما لاتین بودن به‌تنهایی کافی نیست: این دو مربع باید «متعامد» هم باشند تا هیچ ترکیب کت و پیراهنی تکرار نشود.

دو جدول، یک شرط تازه

دو جدول، یک شرط تازه

فرض کن یک جدول برای انتخاب کت و یک جدول برای انتخاب پیراهن داریم. هر دو مربع لاتین هم‌مرتبه هستند؛ یعنی اندازهٔ یکسانی دارند و در هر سطر و هر ستونِ هر جدول، هر نماد دقیقاً یک‌بار آمده است. آیا این کافی است که ترکیب کت و پیراهن هم تکرار نشود؟ نه؛ این شرط تازه‌ای است!

برای بررسی آن، خانه‌های هم‌جایگاه دو جدول را جفت می‌کنیم: مثلاً سطر اول، ستون دومِ جدول AA با همان خانه در جدول BB. اگر در اولی 22 و در دومی 33 باشد، جفت (2,3)(2,3) را می‌نویسیم؛ کتاب آن را به صورت عدد دو رقمی 2323 نمایش می‌دهد، نه حاصل جمع یا ضرب.

دو مربع وقتی متعامدند که هیچ جفتی در کل جدول حاصل تکرار نشود؛ نه فقط در یک سطر یا ستون. در مثال لباس‌ها، یعنی هیچ ترکیب مشخصی از کت و پیراهن دوباره استفاده نشود. پس لاتین بودنِ هر جدول را با متعامد بودنِ دو جدول اشتباه نگیریم.

کتاب درسی، صفحهٔ ۶۴

راه میان‌بُر برای رد تعامد

راه میان‌بُر برای رد تعامد

آیا برای رد متعامد بودن باید همهٔ خانه‌ها را جفت کنیم؟ نه! پیدا کردن فقط یک جفتِ تکراری کافی است.

دو جایگاه متفاوت را در مربع AA در نظر بگیر که هر دو نماد aa دارند. حالا فقط همان دو جایگاه را در مربع BB نگاه کن. اگر آن‌ها هم با یکدیگر برابر باشند، مثلاً هر دو bb باشند، جفتِ (a,b)(a,b) در جدول ترکیبی دوبار ظاهر می‌شود؛ پس دو مربع متعامد نیستند.

دقت کن: لازم نیست a=ba=b باشد! برابری را درون هر مربع بررسی می‌کنیم، نه بین دو مربع. مثل دو نوبتِ برنامهٔ لباس که در هر دو، همان کت با همان پیراهن همراه شده باشد؛ همین تکرار برای نقض شرط کافی است.

اما اگر در دو جایگاه انتخاب‌شده، نمادهای مربع BB متفاوت باشند، هنوز نمی‌توانی متعامد بودن را نتیجه بگیری؛ شاید تکرار در جایگاه‌های دیگری پنهان باشد.

کتاب درسی، صفحهٔ ۶۵

تغییر نام، نه تغییر تعامد

تغییر نام، نه تغییر تعامد

فرض کن دو مربع لاتین متعامد داریم و می‌خواهیم در یکی از آن‌ها فقط «نام نمادها» را عوض کنیم؛ درست مثل عوض‌کردن برچسب وسایل، بدون جابه‌جاکردن خودشان.

جایگشت نمادها یعنی هر نماد را در همهٔ خانه‌ها با نماد مشخصی عوض کنیم و نمادهای متفاوت هم جایگزین‌های متفاوت داشته باشند. پس دو نماد برابر، همچنان برابر می‌مانند و دو نماد متفاوت، متفاوت می‌مانند. این کار با جابه‌جایی دلخواه خانه‌های جدول فرق دارد!

چرا مربع جدید هنوز لاتین است؟ چون در هر سطر و ستون، نمادها پیش از تغییر نام متفاوت بودند و پس از آن هم متفاوت می‌مانند.

تعامد هم حفظ می‌شود. اگر پس از تغییر نام، یک جفت تکراری پیدا شود، بخش مربوط به مربع دست‌نخورده در دو جایگاه برابر است. بخش مربوط به مربع تغییریافته هم برابر است؛ اما جایگشت نمی‌تواند دو نماد متفاوت را یکسان کند. بنابراین پیش از تغییر نام هم همان دو جایگاه جفتی تکراری داشته‌اند؛ درحالی‌که فرض کرده بودیم دو مربع متعامدند!

کتاب درسی، صفحهٔ ۶۸

تعامد به چه کار می‌آید؟

تعامد به چه کار می‌آید؟

فرض کن مسئول برنامه‌ریزی یک کارگاه هستی: پنج کارگر، پنج ماشین و پنج نوع الیاف داریم و می‌خواهیم برای پنج روز برنامه بچینیم.

در مربع لاتین AA، سطرها روزها، ستون‌ها کارگران و درایه‌ها شمارهٔ ماشین‌اند. لاتین بودن هر ستون یعنی هر کارگر در طول هفته با هر ماشین دقیقاً یک‌بار کار می‌کند. لاتین بودن هر سطر هم یعنی در یک روز، ماشین یکسانی به دو کارگر داده نمی‌شود.

مربع لاتین BB را با همین سطرها و ستون‌ها برای نوع الیاف می‌سازیم؛ پس هر کارگر از هر نوع الیاف نیز دقیقاً یک‌بار استفاده می‌کند.

اما هنوز یک شرط باقی است: آیا ممکن است یک ترکیب ماشین و الیاف چند بار تکرار شود؟ لاتین بودنِ جداگانهٔ جدول‌ها جلوی این تکرار را نمی‌گیرد؛ اینجا تعامد لازم است.

اگر AA و BB متعامد باشند، هیچ جفت «ماشین، الیاف» تکرار نمی‌شود. چون 5×5=255\times5=25 خانه و دقیقاً 2525 ترکیب ممکن داریم، هر نوع الیاف با هر ماشین دقیقاً یک‌بار به کار می‌رود.

کتاب درسی، صفحهٔ ۶۹

ساختن با انتقال دوری

ساختن با انتقال دوری

تصور کن شخصیت یک بازی از لبهٔ راست صفحه بیرون می‌رود و از لبهٔ چپ برمی‌گردد؛ انگار دو لبه به هم وصل‌اند. انتقال دوری اعداد هم چنین ایده‌ای دارد.

در روش کتاب برای مرتبهٔ 55، ابتدا نمادها با آرایشی ویژه چیده می‌شوند. سپس یک مربع مرکزی 5×55\times5 در نظر می‌گیریم و اعداد بیرون آن را به داخل منتقل می‌کنیم:

  • اعداد سمت چپ، 55 خانه به راست؛
  • اعداد سمت راست، 55 خانه به چپ؛
  • اعداد بالا، 55 خانه به پایین؛
  • اعداد پایین، 55 خانه به بالا.

این انتقال‌ها همراه با چیدمان اولیهٔ مناسب، دو مربع لاتین متعامد می‌سازند. پس فقط برگرداندن اعداد به داخل کافی نیست؛ اگر چیدمان اولیه دلخواه باشد، تضمینی برای لاتین بودن یا تعامد نداریم.

همین ایده برای هر مرتبهٔ فردِ بزرگ‌تر از یک قابل استفاده است؛ در مرتبهٔ nn، فاصلهٔ انتقال nn خانه خواهد بود. برای مرتبه‌های زوج، این دستور را نمی‌توان بدون تغییر به کار برد.

کتاب درسی، صفحهٔ ۷۰

مثال حل‌شده

سه برادر، سه کت و سه پیراهن دارند. برای سه روز اول هفته برنامه‌ای بچین که هر نفر هر کت و هر پیراهن را دقیقاً یک‌بار بپوشد و هر ترکیب کت و پیراهن نیز دقیقاً یک‌بار استفاده شود.

  1. کت‌ها و پیراهن‌ها را جداگانه با نمادهای 11، 22 و 33 نام‌گذاری می‌کنیم. سطرها را روزها و ستون‌ها را برادران در نظر می‌گیریم.

  2. برای کت‌ها مربع A=(123231312)A=\begin{pmatrix}1&2&3\\2&3&1\\3&1&2\end{pmatrix} و برای پیراهن‌ها مربع B=(123312231)B=\begin{pmatrix}1&2&3\\3&1&2\\2&3&1\end{pmatrix} را انتخاب می‌کنیم. در هر سطر و ستونِ هر دو مربع، هر نماد دقیقاً یک‌بار آمده است.

  3. درایه‌های هم‌جایگاه را به ترتیب «کت، پیراهن» جفت می‌کنیم: (1,1)(2,2)(3,3)(2,3)(3,1)(1,2)(3,2)(1,3)(2,1)\begin{array}{ccc}(1,1)&(2,2)&(3,3)\\(2,3)&(3,1)&(1,2)\\(3,2)&(1,3)&(2,1)\end{array}.

  4. هر ستون در هر یک از مربع‌ها شامل همهٔ نمادهاست؛ پس هر برادر در طول سه روز، هر کت و هر پیراهن را دقیقاً یک‌بار می‌پوشد. همچنین لاتین بودن سطرها مانع اختصاص یک لباس به دو برادر در یک روز می‌شود.

  5. در جدول جفت‌ها، هر یک از 3×3=93\times3=9 ترکیب ممکن دقیقاً یک‌بار دیده می‌شود؛ بنابراین دو مربع متعامدند و شرط همراه شدن هر کت با هر پیراهن نیز برقرار است.

جواب: با خواندن هر جفت به ترتیب «کت، پیراهن»، برنامهٔ نهایی چنین است: برادر اولبرادر دومبرادر سومشنبه(1,1)(2,2)(3,3)یکشنبه(2,3)(3,1)(1,2)دوشنبه(3,2)(1,3)(2,1)\begin{array}{c|ccc} & \text{برادر اول}&\text{برادر دوم}&\text{برادر سوم}\\\hline \text{شنبه}&(1,1)&(2,2)&(3,3)\\ \text{یکشنبه}&(2,3)&(3,1)&(1,2)\\ \text{دوشنبه}&(3,2)&(1,3)&(2,1)\end{array}. هر برادر هر لباس را دقیقاً یک‌بار می‌پوشد و هر کت با هر پیراهن دقیقاً یک‌بار همراه می‌شود.

نکات مهم

  • دو مربع لاتین هم‌مرتبه زمانی متعامدند که هیچ جفتِ حاصل از درایه‌های هم‌جایگاهشان تکرار نشود؛ برای رد تعامد، یافتن یک جفت تکراری کافی است.
  • جایگشت یکسانِ نمادها در سراسر یکی از دو مربع، لاتین بودن و تعامد را حفظ می‌کند، چون برابری و نابرابری نمادها عوض نمی‌شود.
  • تعامد در برنامه‌ریزی، تکرار نشدن ترکیب‌ها را تضمین می‌کند و برای مرتبه‌های فرد بزرگ‌تر از یک می‌توان با چیدمان مناسب و انتقال دوری، دو مربع متعامد ساخت.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۵ · صفحهٔ ۷۰ تا ۷۳ · حدود ۱۵ دقیقه · تولید هوش مصنوعی

یک روش برای ساختن دو مربع لاتین متعامد از مرتبۀ یک عدد فرد۱

در این درس یاد می‌گیری روش انتقال عددهای بیرونی به داخل مربع را برای ساخت دو مربع لاتین متعامد دنبال کنی، نتیجه را بررسی کنی و ایدهٔ روش را به مرتبه‌های فرد تعمیم بدهی.

پیش از شروع

اگر عددی بیرونِ یک جدول مربعی قرار بگیرد، می‌توان آن را از لبهٔ مقابل وارد جدول کرد و با همین ایده دو مربع لاتین متعامد ساخت؟

بله؛ در روش این درس، عددهای بیرونِ مربع با جابه‌جایی مشخصی به داخل آن برمی‌گردند، انگار لبه‌های روبه‌روی جدول به هم وصل‌اند. البته چینش آغازین مهم است؛ انتقالِ یک چیدمان دلخواه لزوماً دو مربع لاتین متعامد نمی‌سازد.

هدف: دو مربع متعامد

هدف: دو مربع متعامد

قرار است دو جدول بسازیم؛ اما از کجا بفهمیم نتیجه درست است؟ باید دو شرط جداگانه را بررسی کنیم.

شرط اول: هر جدول، مربع لاتین باشد. در مرتبهٔ 55، هر سطر و هر ستون باید عددهای 11 تا 55 را دقیقاً یک‌بار داشته باشد. پس بررسی سطرها به‌تنهایی کافی نیست؛ ستون‌ها هم مهم‌اند.

شرط دوم: دو مربع با هم متعامد باشند. جدول‌ها را روی هم تصور کن. در هر خانه، عدد جدول اول را کنار عدد همان خانه از جدول دوم می‌نویسیم و یک زوج مرتب می‌سازیم. هیچ زوجی نباید در دو خانه تکرار شود؛ یعنی در مجموع، 2525 زوج متفاوت داریم.

مثلاً زوج (2،4)(2،4) با (4،2)(4،2) فرق دارد، چون ترتیب جدول‌ها ثابت است. شبیه این است که هر خانه یک کدِ دو‌بخشی داشته باشد: تکرار یک عدد در خانه‌های مختلف طبیعی است، اما تکرار کد کامل، تعامد را از بین می‌برد.

کتاب درسی، صفحهٔ ۷۰

برگشتن از لبهٔ مقابل

برگشتن از لبهٔ مقابل

مربع پررنگِ وسط را مثل صفحهٔ یک بازی تصور کن: وقتی مهره‌ای بیرونِ یک لبه است، از سمت مقابل وارد صفحه می‌شود. در این فعالیت، اندازهٔ جابه‌جایی دقیقاً برابر طول ضلع مربع، یعنی 55 خانه است؛ نه اینکه عدد را در نزدیک‌ترین خانهٔ خالی بگذاریم.

برای انتقال عددهای بیرونی، این چهار جهت را دنبال کن:

  • سمت چپ مربع: 55 خانه به راست؛
  • سمت راست مربع: 55 خانه به چپ؛
  • بالای مربع: 55 خانه به پایین؛
  • پایین مربع: 55 خانه به بالا.

در حرکت افقی، سطرِ عدد عوض نمی‌شود؛ در حرکت عمودی هم ستونش ثابت می‌ماند. خودِ عدد نیز تغییر نمی‌کند؛ فقط جای آن عوض می‌شود.

برای شمردن خانه‌ها، خانهٔ شروع را نشمار؛ هر بار رفتن به خانهٔ کناری یک گام است. این دستورها را برای هر دو شکل آغازین اجرا می‌کنیم. پس باید جای عددهای بیرونی را از همان چینش داده‌شده دنبال کنیم، نه اینکه عددها را به دلخواه وارد جدول کنیم.

کتاب درسی، صفحهٔ ۷۰

از مرتبهٔ پنج به مرتبهٔ فرد

از مرتبهٔ پنج به مرتبهٔ فرد

آیا این روش فقط برای مربعِ مرتبهٔ 55 است؟ نه؛ می‌توان همین ایده را برای هر مرتبهٔ فردِ nn به کار برد. در این حالت، مربع مرکزی n×nn\times n است و هر انتقال، به‌جای 55 خانه، nn خانه انجام می‌شود. جهت‌ها همان‌اند: عددِ بیرون‌مانده از لبهٔ مقابل وارد می‌شود.

مثلاً برای مرتبهٔ 77، عددِ سمت چپ را 77 خانه به راست می‌بریم؛ برای مرتبهٔ 33، فاصلهٔ انتقال 33 خانه است.

اما یک نکتهٔ مهم: انتقال، جای چینش آغازینِ مناسب را نمی‌گیرد. مثل تا کردن کاغذ از روی یک الگوست؛ اگر علامت‌ها از ابتدا در جای نامناسب باشند، درست تا کردن هم نتیجهٔ دلخواه را نمی‌سازد. پس نمی‌توان عددها را دلخواه چید و انتظار داشت فقط با انتقال، دو مربع لاتین متعامد به دست بیاید.

در پایان نیز باید لاتین بودن هر مربع و تکراری نبودن زوج‌های مرتبِ خانه‌های متناظر را بررسی کنیم.

کتاب درسی، صفحهٔ ۷۰

مثال حل‌شده

دو مربع لاتین متعامد از مرتبهٔ 33 بنویس و درستی پاسخ را بررسی کن.

  1. برای مربع اول، سطر نخست را 1،2،31،2،3 می‌گذاریم و در هر سطر بعد، عددها را یک خانه به چپ می‌چرخانیم: A=(123231312)A=\begin{pmatrix}1&2&3\\2&3&1\\3&1&2\end{pmatrix}.

  2. برای مربع دوم، سطر نخست را 1،3،21،3،2 می‌گذاریم و در هر سطر بعد، عددها را یک خانه به راست می‌چرخانیم: B=(132213321)B=\begin{pmatrix}1&3&2\\2&1&3\\3&2&1\end{pmatrix}.

  3. در هر سطر و هر ستونِ هر دو مربع، هر یک از عددهای 1،2،31،2،3 دقیقاً یک بار آمده است؛ پس هر دو مربع لاتین‌اند.

  4. با قرار دادن عددِ مربع AA در مؤلفهٔ اول و عددِ مربع BB در مؤلفهٔ دوم، جدول زوج‌ها به دست می‌آید: (1,1)(2,3)(3,2)(2,2)(3,1)(1,3)(3,3)(1,2)(2,1)\begin{matrix}(1,1)&(2,3)&(3,2)\\(2,2)&(3,1)&(1,3)\\(3,3)&(1,2)&(2,1)\end{matrix}.

  5. هر 99 زوج مرتب متفاوت‌اند؛ بنابراین دو مربع متعامدند. چرخاندن سطرها در این مثال پاسخ داده است، اما برای هر ساخت پیشنهادی باید لاتین و متعامد بودن را بررسی کنیم.

جواب: دو مربع A=(123231312)A=\begin{pmatrix}1&2&3\\2&3&1\\3&1&2\end{pmatrix} و B=(132213321)B=\begin{pmatrix}1&3&2\\2&1&3\\3&2&1\end{pmatrix} لاتین و متعامدند.

نکات مهم

  • در هر مربع لاتین، عددها در هیچ سطر یا ستونی تکرار نمی‌شوند و در دو مربع متعامد، زوج‌های مرتبِ خانه‌های متناظر نیز تکراری نیستند.
  • در روش انتقال، عددِ بیرونی را به اندازهٔ مرتبهٔ مربع به سمت داخل جابه‌جا می‌کنیم؛ از چپ به راست، از راست به چپ، از بالا به پایین و از پایین به بالا.
  • این الگوی ساخت برای مرتبه‌های فرد با چینش آغازینِ مناسب به کار می‌رود، نه با چیدن دلخواه عددها.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۶ · صفحهٔ ۷۳ تا ۷۵ · حدود ۱۵ دقیقه · تولید هوش مصنوعی

درس 2: روش‌هایی برای شمارش

در این درس یاد می‌گیری با اصل شمول و عدم شمول، اعضای اجتماع دو یا سه مجموعه و متمم آن را بشماری و این روش را در مسئله‌های بخش‌پذیری و رمز به کار ببری.

پیش از شروع

اگر تعداد فوتبال‌بازها و والیبال‌بازهای یک کلاس را با هم جمع کنی و حاصل از تعداد دانش‌آموزان کلاس بیشتر شود، حتماً اشتباه کرده‌ای؟

نه لزوماً! کسی که هر دو ورزش را انجام می‌دهد، در این جمع دو بار شمرده می‌شود. اصل شمول و عدم شمول کمک می‌کند این دوباره‌شماری را اصلاح کنیم.

هر عضو فقط یک بار

هر عضو فقط یک بار

اگر تعداد فوتبال‌بازها و والیبال‌بازهای یک کلاس را جمع کنیم و حاصل از تعداد دانش‌آموزان بیشتر شود، لزوماً اشتباه نکرده‌ایم! ممکن است بعضی‌ها هر دو ورزش را بازی کنند و نامشان در هر دو فهرست باشد.

مجموعهٔ فوتبال‌بازها را AA و مجموعهٔ والیبال‌بازها را BB بنامیم. اجتماع آن‌ها، یعنی A∪BA\cup B، شامل کسانی است که حداقل یکی از این دو ورزش را بازی می‌کنند؛ کسانی که هر دو را بازی می‌کنند هم عضو اجتماع‌اند.

در جمعِ ∣A∣+∣B∣|A|+|B|، هر عضوِ اشتراکِ A∩BA\cap B دو بار شمرده می‌شود؛ یک بار در فهرست اول و یک بار در فهرست دوم. برای اینکه هر نفر فقط یک بار حساب شود، تعداد اعضای اشتراک را یک بار کم می‌کنیم:

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A\cup B|=|A|+|B|-|A\cap B|

این همان اصل شمول و عدم شمول برای دو مجموعه است. دقت کن: اعضای مشترک را از اجتماع حذف نمی‌کنیم؛ فقط شمارشِ اضافهٔ آن‌ها را حذف می‌کنیم.

کتاب درسی، صفحهٔ ۷۳

آن‌هایی که در هیچ‌کدام نیستند

آن‌هایی که در هیچ‌کدام نیستند

فرض کن در یک کلاس، بعضی‌ها فوتبال بازی می‌کنند و بعضی‌ها والیبال. اگر بخواهیم کسانی را بشماریم که نه فوتبال بازی می‌کنند و نه والیبال، باید کدام بخش از نمودار ون را نگاه کنیم؟ بخش بیرونِ هر دو دایره، اما داخل مستطیل کلاس!

مجموعهٔ همهٔ دانش‌آموزان کلاس را SS می‌نامیم؛ این همان مجموعهٔ مرجع است. اگر فوتبال‌بازها در AA و والیبال‌بازها در BB باشند، اجتماع A∪BA\cup B همهٔ کسانی را شامل می‌شود که دست‌کم یکی از این دو ورزش را بازی می‌کنند. پس افراد موردنظر ما در متمم اجتماع هستند:

∣A∪B‾∣=∣S∣−∣A∪B∣|\overline{A\cup B}|=|S|-|A\cup B|

با جای‌گذاری اصل شمول، همین رابطه به شکل زیر درمی‌آید:

∣A∪B‾∣=∣S∣−∣A∣−∣B∣+∣A∩B∣|\overline{A\cup B}|=|S|-|A|-|B|+|A\cap B|

دقت کن: «در هیچ‌کدام نبودن» یعنی بیرونِ هر دو مجموعه بودن؛ کسی که فقط فوتبال بازی نمی‌کند، ممکن است والیبال‌باز باشد و جزو افراد موردنظر ما نباشد.

کتاب درسی، صفحهٔ ۷۳

چرا اشتراک سه‌تایی برمی‌گردد؟

چرا اشتراک سه‌تایی برمی‌گردد؟

فرض کن در مدرسه سه گروه کتاب‌خوانی، ورزش و نقاشی داریم و می‌خواهیم بدانیم چند دانش‌آموز حداقل در یکی از این گروه‌ها عضو است. مجموعهٔ اعضای گروه‌ها را AA، BB و CC می‌نامیم.

اول تعداد اعضای سه گروه را جمع می‌کنیم. اما اعضای مشترک، چند بار شمرده شده‌اند؛ پس تعداد اعضای هر اشتراک دوتایی را کم می‌کنیم. آیا کار تمام است؟

دانش‌آموزی را تصور کن که عضو هر سه گروه است. او در جمع اولیه 33 بار شمرده شده است. سپس چون در هر سه اشتراک دوتایی هم حضور دارد، 33 بار حذف می‌شود؛ یعنی سهمش در شمارش به 00 می‌رسد! برای اینکه او هم دقیقاً یک بار شمرده شود، باید اشتراک سه‌تایی را یک بار اضافه کنیم:

∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|

پس الگوی فرمول این است: جمع مجموعه‌ها، کم‌کردن اشتراک‌های دوتایی، برگرداندن اشتراک سه‌تایی.

کتاب درسی، صفحهٔ ۷۴

از بخش‌پذیری تا مجموعه‌ها

از بخش‌پذیری تا مجموعه‌ها

فرض کن می‌خواهیم شماره‌های بخش‌پذیر بر یک عدد را از میان شماره‌های یک فهرست جدا کنیم. لازم نیست تک‌تک آن‌ها را بررسی کنیم؛ کافی است مضرب‌ها را بشماریم.

در میان اعداد طبیعی از 11 تا kk، تعداد مضرب‌های عدد طبیعیِ dd برابر است با:

⌊kd⌋\left\lfloor\frac{k}{d}\right\rfloor

علامت ⌊ ⌋\lfloor\ \rfloor یعنی جزء صحیح؛ بخش اعشاریِ خارج‌قسمت را کنار می‌گذاریم، چون فقط مضرب‌های کامل را می‌شماریم. کتاب برای جزء صحیح از نماد [ ][\ ] استفاده می‌کند.

حالا اگر AA مجموعهٔ مضرب‌های 33 و BB مجموعهٔ مضرب‌های 44 باشد، عضوهای A∩BA\cap B باید بر هر دو عدد بخش‌پذیر باشند. این‌ها دقیقاً مضرب‌های کوچک‌ترین مضرب مشترک آن دو عدد، یعنی 1212 هستند. پس در بازهٔ 11 تا 400400 داریم:

∣A∩B∣=⌊40012⌋|A\cap B|=\left\lfloor\frac{400}{12}\right\rfloor

نکتهٔ مهم: برای اشتراک، همیشه سراغ کمم برو، نه لزوماً حاصل‌ضرب! حاصل‌ضرب فقط وقتی با کمم برابر است که دو عدد نسبت به هم اول باشند. برای اشتراک سه مجموعهٔ مضرب‌ها نیز همین روش را با کمم هر سه عدد به کار می‌بریم.

کتاب درسی، صفحهٔ ۷۴

گاهی برعکس بشمار!

گاهی برعکس بشمار!

فرض کن رمز قفلت باید هم رقم 77 داشته باشد و هم رقم 88. شمردن مستقیم رمزهای مجاز دردسر دارد؛ مثلاً اگر جای این دو رقم را انتخاب کنی، تکرارشان ممکن است باعث چندبار شمردن بعضی رمزها شود.

راه ساده‌تر این است که رمزهای نامناسب را بشماری. مجموعهٔ مرجع SS را همهٔ رمزهای چهاررقمی بگیر؛ صفر هم می‌تواند در ابتدای رمز باشد. حالا تعریف کن:

  • AA: رمزهایی که هیچ رقم 77 ندارند.
  • BB: رمزهایی که هیچ رقم 88 ندارند.

اجتماع A∪BA\cup B شامل رمزهایی است که دست‌کم یکی از دو رقم لازم را ندارند. پس رمزهای مطلوب، بیرون این اجتماع‌اند؛ یعنی در (A∪B)′(A\cup B)' قرار دارند.

برای شمارش، در هر جایگاهِ رمزهای AA یا BB، تعداد 99 انتخاب داریم. در اشتراک آن‌ها، نه 77 مجاز است و نه 88؛ پس هر جایگاه 88 انتخاب دارد. بنابراین:

∣(A∪B)′∣=104−94−94+84|(A\cup B)'|=10^4-9^4-9^4+8^4

نکتهٔ کلیدی: متممِ «حداقل یکی را ندارد»، همان «هر دو را دارد» است.

کتاب درسی، صفحهٔ ۷۵

مثال حل‌شده

چند عدد طبیعی nn با شرط 1≤n≤3501\le n\le350 وجود دارد که بر هیچ‌یک از اعداد 44، 55 و 66 بخش‌پذیر نباشند؟

  1. مجموعهٔ مرجع را S={1,2,…,350}S=\{1,2,\ldots,350\} می‌گیریم و مجموعه‌های مضرب‌های 44، 55 و 66 را به‌ترتیب AA، BB و CC می‌نامیم؛ مطلوب، تعداد اعضای A∪B∪C‾\overline{A\cup B\cup C} است.

  2. تعداد مضرب‌های هر عدد را می‌شماریم: ∣A∣=⌊3504⌋=87|A|=\left\lfloor\frac{350}{4}\right\rfloor=87، ∣B∣=⌊3505⌋=70|B|=\left\lfloor\frac{350}{5}\right\rfloor=70 و ∣C∣=⌊3506⌋=58|C|=\left\lfloor\frac{350}{6}\right\rfloor=58.

  3. برای اشتراک‌های دوتایی، کوچک‌ترین مضرب مشترک‌ها به‌ترتیب 2020، 1212 و 3030 هستند؛ پس ∣A∩B∣=17|A\cap B|=17، ∣A∩C∣=29|A\cap C|=29 و ∣B∩C∣=11|B\cap C|=11.

  4. کوچک‌ترین مضرب مشترک هر سه عدد 6060 است؛ بنابراین ∣A∩B∩C∣=⌊35060⌋=5|A\cap B\cap C|=\left\lfloor\frac{350}{60}\right\rfloor=5.

  5. با اصل شمول، تعداد عددهایی که دست‌کم بر یکی از این اعداد بخش‌پذیرند برابر است با ∣A∪B∪C∣=87+70+58−17−29−11+5=163|A\cup B\cup C|=87+70+58-17-29-11+5=163.

  6. برای رسیدن به «هیچ‌کدام»، متمم می‌گیریم: ∣A∪B∪C‾∣=350−163=187|\overline{A\cup B\cup C}|=350-163=187.

جواب: در این بازه، 187187 عدد طبیعی بر هیچ‌یک از اعداد 44، 55 و 66 بخش‌پذیر نیستند.

نکات مهم

  • برای دو مجموعه، اعضای مشترک را که دوبار شمرده شده‌اند یک بار کم می‌کنیم: ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A\cup B|=|A|+|B|-|A\cap B|.
  • برای سه مجموعه، پس از جمع تعداد اعضا و کم‌کردن اشتراک‌های دوتایی، اشتراک سه‌تایی را یک بار اضافه می‌کنیم و برای شمارش «هیچ‌کدام»، تعداد اجتماع را از تعداد اعضای مرجع کم می‌کنیم.
  • در مسائل بخش‌پذیری، مضرب‌ها را با جزء صحیح و اشتراک‌ها را با کوچک‌ترین مضرب مشترک می‌شماریم؛ در مسائل رمز نیز گاهی شمردن حالت‌های نامطلوب و گرفتن متمم، راه ساده‌تری است.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۷ · صفحهٔ ۷۵ تا ۷۹ · حدود ۱۵ دقیقه · تولید هوش مصنوعی

کار در کلاس

در این درس یاد می‌گیری مسئله‌های شمارش را با اصل شمول، شمارش تابع‌های پوشا و یک‌به‌یک مدل‌سازی کنی و با اصل لانه‌کبوتری، وجود یک تکرار را تضمین کنی.

پیش از شروع

شمارش رمزهای یک قفل، طراحی جاده‌هایی که هیچ روستایی را تنها نگذارند و تقسیم خودکارها بدون دست‌خالی ماندن کسی، چه راه‌حل مشترکی دارند؟

گاهی شمردن حالت‌های نامطلوب از شمردن مستقیم حالت‌های مطلوب آسان‌تر است؛ کافی است حالت‌های نامطلوب را درست از کل کم کنیم. اصل شمول کمک می‌کند حالت‌های مشترک را اشتباهی چند بار حذف نکنیم.

نه مضرب این، نه مضرب آن

نه مضرب این، نه مضرب آن

فرض کن کارت‌هایی با شماره‌های 11 تا 350350 داریم و می‌خواهیم کارت‌هایی را نگه داریم که شماره‌شان بر هیچ‌یک از 44، 55 و 66 بخش‌پذیر نباشد. شمردن تک‌تک کارت‌ها لازم نیست؛ حالت‌های نامطلوب را بشمار و از کل کم کن.

مجموعهٔ مضرب‌های این سه عدد را به‌ترتیب AA، BB و CC بنام. تعداد مضرب‌های 44 برابر ∣A∣=⌊350/4⌋|A|=\lfloor350/4\rfloor است؛ علامت کف یعنی بزرگ‌ترین عدد صحیحِ کوچک‌تر یا مساوی مقدار داخل آن.

اگر تعداد اعضای این مجموعه‌ها را فقط جمع کنیم، مضرب‌های مشترک چندبار شمرده می‌شوند. برای یافتن اشتراک‌ها از ک‌م‌م کمک می‌گیریم: عددی که هم بر 44 و هم بر 66 بخش‌پذیر باشد، مضرب 1212 است، نه لزوماً مضرب 2424.

اصل شمول این دوباره‌شماری را اصلاح می‌کند:

∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|

اشتراک سه‌تایی را دوباره اضافه می‌کنیم، چون پس از کم‌کردن اشتراک‌های دوتایی، سهم آن صفر شده است. در پایان، تعداد مطلوب برابر 350−∣A∪B∪C∣350-|A\cup B\cup C| خواهد بود.

کتاب درسی، صفحهٔ ۷۵

از حالت‌های نامطلوب شروع کن

از حالت‌های نامطلوب شروع کن

گاهی شمردن حالت‌هایی که نمی‌خواهیم آسان‌تر است! مثلاً برای رمز چهاررقمی که باید هم رقم 77 و هم رقم 88 داشته باشد، انتخاب جای این رقم‌ها ممکن است باعث چندبار شمردن بعضی رمزها شود.

به‌جای آن، AA را مجموعهٔ رمزهای بدون رقم 77 و BB را مجموعهٔ رمزهای بدون رقم 88 بگیر. رمز نامطلوب دست‌کم یکی از این دو نقص را دارد؛ پس در A∪BA\cup B است. رمز مطلوب بیرون این اجتماع قرار دارد:

∣A∪B‾∣=∣S∣−(∣A∣+∣B∣−∣A∩B∣)|\overline{A\cup B}|=|S|-(|A|+|B|-|A\cap B|)

اشتراک، رمزهایی است که هیچ‌کدام از دو رقم را ندارند. چون این رمزها در هر دو مجموعه شمرده شده‌اند، هنگام محاسبهٔ اجتماع باید یک بار کم شوند.

در طراحی جاده هم همین نگاه کمک می‌کند: برای هر روستا، مجموعهٔ طرح‌هایی را تعریف کن که آن روستا در آن‌ها تنهاست. اجتماع این مجموعه‌ها یعنی «دست‌کم یک روستا تنهاست»؛ مکمل اجتماع یعنی «هیچ روستایی تنها نیست». پس اول نقص‌ها را مشخص کن، بعد حالت‌های دارای نقص را از کل کنار بگذار.

کتاب درسی، صفحهٔ ۷۵

تابع پوشا؛ هیچ‌کس دست‌خالی نماند

تابع پوشا؛ هیچ‌کس دست‌خالی نماند

فرض کن چند خودکار متفاوت را بین چند نفر تقسیم می‌کنی. هر خودکار دقیقاً به یک نفر می‌رسد؛ پس این تقسیم را می‌توان یک تابع دانست: خودکارها اعضای دامنه‌اند و افراد، اعضای مجموعهٔ مقصد.

اگر دامنه mm عضو و مقصد nn عضو داشته باشد، برای تصویر هر عضو دامنه، nn انتخاب داریم. انتخاب‌ها مستقل‌اند؛ بنابراین با اصل ضرب، تعداد کل تابع‌ها برابر nmn^m است.

اما پوشا بودن شرط اضافه‌ای دارد: هر عضو مقصد باید تصویرِ دست‌کم یک عضو دامنه باشد. در مثال خودکارها، یعنی هیچ‌کس دست‌خالی نماند؛ نه اینکه همه دقیقاً یک خودکار بگیرند!

برای شمارش تابع‌های پوشا، از حالت‌های نامطلوب شروع می‌کنیم. اگر مقصد B={b1,b2,b3}B=\{b_1,b_2,b_3\} باشد، AiA_i را مجموعهٔ تابع‌هایی بگیر که از bib_i استفاده نمی‌کنند. در این صورت ∣S∣=3m|S|=3^m و ∣Ai∣=2m|A_i|=2^m است؛ چون با کنار گذاشتن یک عضو مقصد، برای هر عضو دامنه دو انتخاب می‌ماند.

تابع‌های پوشا بیرونِ اجتماع این مجموعه‌های نامطلوب‌اند؛ پس تعدادشان برابر است با:

∣S∣−∣A1∪A2∪A3∣|S|-|A_1\cup A_2\cup A_3|

اجتماع را با اصل شمول می‌شماریم تا تابع‌هایی که چند عضو مقصد را استفاده نکرده‌اند، چندبار حذف نشوند.

کتاب درسی، صفحهٔ ۷۷

تابع یک‌به‌یک؛ بدون تکرار

تابع یک‌به‌یک؛ بدون تکرار

فرض کن چند خودکار متفاوت را بین چند نفر تقسیم می‌کنی و شرط این است که هیچ‌کس بیشتر از یک خودکار نگیرد. هر خودکار را یک عضو دامنه و هر نفر را یک عضو مجموعهٔ مقصد بگیر. در این مدل، دو خودکار نباید به یک نفر برسند؛ یعنی تصویر دو عضو متفاوت دامنه نباید یکسان باشد. این همان شرط یک‌به‌یک بودن تابع است.

اگر دامنه mm عضو و مقصد kk عضو داشته باشد، برای تصویر عضو اول kk انتخاب داریم. برای عضو دوم، مقصدِ انتخاب‌شدهٔ قبلی دیگر مجاز نیست؛ پس k−1k-1 انتخاب باقی می‌ماند. این روند ادامه دارد تا برای عضو آخر k−m+1k-m+1 انتخاب داشته باشیم.

با اصل ضرب، تعداد تابع‌های یک‌به‌یک برابر است با:

(k)m=k(k−1)⋯(k−m+1)=k!(k−m)!(k)_m=k(k-1)\cdots(k-m+1)=\frac{k!}{(k-m)!}

این رابطه برای m≤km\le k است؛ اگر دامنه بزرگ‌تر از مقصد باشد، تابع یک‌به‌یک نداریم. همچنین لازم نیست همهٔ اعضای مقصد استفاده شوند؛ یک‌به‌یک یعنی تصویر تکراری نداشته باشیم، نه اینکه همهٔ مقصد را پوشش دهیم.

کتاب درسی، صفحهٔ ۷۸

وقتی تکرار اجتناب‌ناپذیر است

وقتی تکرار اجتناب‌ناپذیر است

گاهی به‌جای پرسیدن «چند حالت داریم؟»، می‌پرسیم: آیا می‌توان مطمئن بود که تکراری رخ می‌دهد؟ اصل لانه‌کبوتری برای همین پرسش است.

فرض کن چند شیء را در چند دسته قرار می‌دهیم و هر شیء دقیقاً در یک دسته قرار می‌گیرد. اگر تعداد اشیا از تعداد دسته‌ها بیشتر باشد، دست‌کم یک دسته شامل حداقل دو شیء خواهد بود. چرا؟ چون اگر در هر دسته حداکثر یک شیء بگذاریم، تعداد اشیای جاگرفته نمی‌تواند از تعداد دسته‌ها بیشتر شود!

برای استفاده از این اصل، لازم نیست واقعاً کبوتر و لانه داشته باشیم. مثلاً افراد می‌توانند «کبوترها» و ماه‌های تولدشان «لانه‌ها» باشند. برای تضمین تکرار ماه تولد، تعداد افراد باید از تعداد ماه‌ها بیشتر باشد.

نکتهٔ مهم: این اصل نمی‌گوید کدام دسته تکرار دارد یا همهٔ دسته‌ها پر هستند؛ فقط وجود دست‌کم یک دسته با حداقل دو عضو را تضمین می‌کند. همچنین، برابر بودن تعداد اشیا و دسته‌ها به‌تنهایی برای تضمین تکرار کافی نیست.

کتاب درسی، صفحهٔ ۷۹

مثال حل‌شده

چهار خودکار متفاوت را بین سه نفر تقسیم می‌کنیم. اگر هر خودکار دقیقاً به یک نفر داده شود و هر نفر حداقل یک خودکار بگیرد، چند تقسیم ممکن است؟

  1. هر خودکار را یک عضو دامنه و هر نفر را یک عضو مقصد در نظر می‌گیریم. چون همه باید خودکار بگیرند، تابع متناظر باید پوشا باشد.

  2. بدون شرط دست‌خالی نماندن، هر خودکار سه گیرندهٔ ممکن دارد؛ پس تعداد کل تقسیم‌ها ∣S∣=34=81|S|=3^4=81 است.

  3. مجموعه‌های A1A_1، A2A_2 و A3A_3 را به‌ترتیب تقسیم‌هایی می‌گیریم که نفر اول، دوم یا سوم دست‌خالی بماند. با حذف هر نفر، برای هر خودکار دو انتخاب داریم؛ پس ∣A1∣=∣A2∣=∣A3∣=24=16|A_1|=|A_2|=|A_3|=2^4=16.

  4. اگر دو نفر مشخص دست‌خالی بمانند، همهٔ خودکارها به نفر سوم می‌رسد؛ پس هر اشتراک دوتایی یک عضو دارد. دست‌خالی ماندن هر سه نفر ناممکن است؛ بنابراین اشتراک سه‌تایی تهی است.

  5. با اصل شمول، تعداد تقسیم‌های نامطلوب 3×16−3×1+0=453\times16-3\times1+0=45 است. مکمل آن‌ها پاسخ مسئله است: 81−45=3681-45=36.

جواب: چهار خودکار متفاوت را به 3636 روش می‌توان بین سه نفر تقسیم کرد، به‌طوری که هیچ‌کس دست‌خالی نماند.

نکات مهم

  • برای حذف حالت‌های نامطلوب در مسئله‌های بخش‌پذیری، رمز و جاده، اجتماع آن‌ها را با اصل شمول می‌شماریم و از کل کم می‌کنیم؛ اشتراک مجموعه‌های مضرب‌ها با ک‌م‌م تعیین می‌شود.
  • تعداد کل تابع‌ها nmn^m است؛ در تابع پوشا هیچ عضو مقصد بی‌تصویر نمی‌ماند و در تابع یک‌به‌یک تصویرها تکرار نمی‌شوند.
  • طبق اصل لانه‌کبوتری، اگر تعداد اشیا از تعداد لانه‌ها بیشتر باشد، دست‌کم یک لانه شامل حداقل دو شیء است.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۸ · صفحهٔ ۷۹ تا ۸۱ · حدود ۱۵ دقیقه · تولید هوش مصنوعی

اصل لانه کبوتری¹

در این درس یاد می‌گیری با تشخیص کبوترها و لانه‌ها، اصل لانه کبوتری و تعمیم آن را برای اثبات وجود تکرار در مسئله‌های عددی، هندسی و گراف به کار ببری.

پیش از شروع

بدون پرسیدن تاریخ تولد هیچ‌کس، حداقل چند نفر باید در یک کلاس باشند تا مطمئن شوی دو نفر ماه تولد یکسانی دارند؟

با 1212 نفر هنوز ممکن است هر نفر در ماه متفاوتی متولد شده باشد. اما نفر سیزدهم در هر ماهی متولد شده باشد، ماه تولدش با یکی از بقیه مشترک است؛ همین فکر ساده، پایهٔ اصل لانه کبوتری است.

اشیای بیشتر، دسته‌های کمتر

اشیای بیشتر، دسته‌های کمتر

بدون دانستن تاریخ تولدها هم می‌توانی وجود دو هم‌ماه را تضمین کنی! ماه‌های سال را مثل 1212 لانه و افراد کلاس را مثل کبوترها در نظر بگیر؛ هر فرد در لانهٔ ماه تولد خودش قرار می‌گیرد.

با 1212 نفر، ممکن است در هر ماه فقط یک نفر متولد شده باشد؛ پس هنوز تکرار قطعی نیست. اما با ورود نفر سیزدهم، حتماً یکی از ماه‌ها دست‌کم دو نفر خواهد داشت.

این همان اصل لانه کبوتری است: اگر mm شیء را در nn دسته قرار دهیم و m>nm>n باشد، دست‌کم یک دسته دارای دو عضو یا بیشتر است. چرا؟ اگر هر دسته حداکثر یک عضو داشته باشد، مجموع اشیا نمی‌تواند از nn بیشتر شود!

برای استفاده از این اصل، اول مشخص کن «اشیا» و «دسته‌ها» چه هستند. لازم نیست واقعاً کبوتر و لانه‌ای در کار باشد. همچنین اصل نمی‌گوید کدام دسته تکراری است؛ فقط وجود آن را تضمین می‌کند.

کتاب درسی، صفحهٔ ۷۹

لانه‌هایی از جنس باقی‌مانده

لانه‌هایی از جنس باقی‌مانده

برای استفاده از اصل لانه کبوتری، لانه‌ها لازم نیست جای واقعی باشند؛ گاهی دسته‌های عددی هستند. مثلاً می‌توانیم عددها را براساس باقی‌ماندهٔ تقسیمشان بر یک عدد ثابت دسته‌بندی کنیم.

در تقسیم بر 44، فقط باقی‌مانده‌های 00، 11، 22 و 33 ممکن‌اند. پس هر عدد طبیعی، هرقدر هم بزرگ باشد، در یکی از این چهار لانه قرار می‌گیرد. اگر تعداد عددها از تعداد این لانه‌ها بیشتر شود، دیگر نمی‌توان همه را در لانه‌های جدا گذاشت؛ دست‌کم دو عدد باقی‌ماندهٔ یکسان خواهند داشت.

این همان معنای هم‌نهشتی است: اگر aa و bb هنگام تقسیم بر 44 باقی‌ماندهٔ یکسانی داشته باشند، می‌نویسیم a≡b(mod4)a\equiv b\pmod{4}. همچنین تفاضلشان بر 44 بخش‌پذیر است؛ چون با کم‌کردن دو عدد، باقی‌مانده‌های برابر حذف می‌شوند.

به‌طور کلی، برای تقسیم بر عدد طبیعیِ مثبت nn، لانه‌ها باقی‌مانده‌های 00 تا n−1n-1 هستند. نکتهٔ مهم این است: تعداد لانه‌ها را از روی باقی‌مانده‌های ممکن بشمار، نه بزرگی عددها.

کتاب درسی، صفحهٔ ۸۰

ناحیه‌ها به‌جای لانه‌ها

ناحیه‌ها به‌جای لانه‌ها

برای پیدا کردن دو نقطهٔ نزدیک، لازم نیست فاصلهٔ همهٔ جفت‌نقطه‌ها را حساب کنیم! می‌توانیم شکل را به ناحیه‌های کوچک تقسیم کنیم؛ درست مثل کف اتاقی که با کاشی پوشیده شده است.

در این روش، نقطه‌ها کبوترند و ناحیه‌ها لانه‌اند. اگر تعداد نقطه‌ها از تعداد ناحیه‌ها بیشتر باشد، دست‌کم دو نقطه در یک ناحیه قرار می‌گیرند. سپس از اندازه و شکل همان ناحیه برای محدود کردن فاصلهٔ آن دو استفاده می‌کنیم.

مثلاً فاصلهٔ دو نقطه در یک مربع، از طول قطر آن بیشتر نیست. پس اگر دو نقطه در مربعی به ضلع 11 باشند، فاصله‌شان حداکثر 2\sqrt{2} است، نه لزوماً حداکثر 11!

نکتهٔ مرزی: اگر نقطه‌ای روی مرز مشترک چند ناحیه باشد، آن را فقط به یکی از آنها نسبت می‌دهیم تا هر نقطه دقیقاً یک لانه داشته باشد. همچنین برای ادعای «کمتر از»، باید حالت برابری را جداگانه بررسی کنیم.

کتاب درسی، صفحهٔ ۸۰

چرا دو رأس هم‌درجه‌اند؟

چرا دو رأس هم‌درجه‌اند؟

در یک گراف ساده با P≥2P\geq 2 رأس، درجهٔ هر رأس تعداد همسایه‌های آن است؛ پس درجه‌ها از 00 تا P−1P-1 هستند. ظاهراً برای PP رأس، تعداد PP لانهٔ درجه داریم! اما یک نکته تعداد لانه‌ها را کم می‌کند.

درجه‌های 00 و P−1P-1 نمی‌توانند هم‌زمان وجود داشته باشند. رأس با درجهٔ P−1P-1 به همهٔ رأس‌های دیگر وصل است؛ بنابراین هیچ رأسی نمی‌تواند تنها و دارای درجهٔ 00 باشد.

حالا دو حالت داریم:

  • اگر رأس تنها نداشته باشیم، درجه‌ها در مجموعهٔ {1,…,P−1}\{1,\ldots,P-1\} هستند.
  • اگر رأس تنها داشته باشیم، درجهٔ P−1P-1 ناممکن است؛ پس درجه‌ها در مجموعهٔ {0,…,P−2}\{0,\ldots,P-2\} هستند.

در هر حالت، رأس‌ها کبوترند و مقدارهای ممکنِ درجه لانه‌اند: تعداد PP رأس در حداکثر P−1P-1 لانه قرار می‌گیرند. پس دست‌کم دو رأس هم‌درجه‌اند.

اگر هم از ابتدا دو رأس تنها داشته باشیم، همان دو رأس درجهٔ برابرِ 00 دارند و نتیجه مستقیم به دست می‌آید.

کتاب درسی، صفحهٔ ۸۰

بیش از دو کبوتر در یک لانه

بیش از دو کبوتر در یک لانه

اگر بخواهیم حضور دست‌کم k+1k+1 کبوتر در یک لانه را تضمین کنیم، چند کبوتر لازم داریم؟ به آخرین حالتی فکر کن که هنوز می‌توان از این اتفاق جلوگیری کرد: در هر لانه حداکثر kk کبوتر بگذاریم. با nn لانه، در مجموع حداکثر knkn کبوتر جا می‌گیرند. یک کبوتر بیشتر، ناچار تعداد اعضای یکی از لانه‌ها را به دست‌کم k+1k+1 می‌رساند.

پس تعمیم اصل لانه کبوتری می‌گوید: اگر دست‌کم kn+1kn+1 عضو را در nn دسته قرار دهیم، یک دسته دست‌کم k+1k+1 عضو دارد.

مثلاً برای بررسی تعداد دانش‌آموزانی که ماه تولد یکسان دارند، ماه‌ها لانه‌اند و دانش‌آموزان کبوتر. لازم نیست تعداد افرادِ همهٔ ماه‌ها برابر باشد؛ کافی است تعداد کل از ظرفیت حالتی بیشتر شود که هر ماه حداکثر kk نفر دارد.

دقت کن: این اصل وجود چنین لانه‌ای را تضمین می‌کند، نه اینکه لانه‌های دیگر حتماً کم‌جمعیت باشند.

کتاب درسی، صفحهٔ ۸۱

مثال حل‌شده

حداقل چند نفر باید در یک جمع باشند تا مطمئن شویم دست‌کم 33 نفر ماه تولد یکسانی دارند؟

  1. افراد را کبوترها و ماه‌های سال را لانه‌ها می‌گیریم؛ پس n=12n=12 لانه داریم.

  2. برای اینکه هنوز هیچ ماهی محل تولد 33 نفر نباشد، در هر ماه حداکثر 22 نفر می‌گذاریم؛ در نتیجه 2×12=242\times12=24 نفر می‌توانند بدون تشکیل گروه موردنظر حضور داشته باشند.

  3. با اضافه شدن نفر بعدی، هر ماهی که ماه تولد او باشد، تعداد افراد آن ماه به دست‌کم 33 نفر می‌رسد.

  4. پس طبق تعمیم اصل لانه کبوتری، حداقل تعداد لازم برابر است با kn+1=2×12+1=25kn+1=2\times12+1=25.

جواب: حداقل 2525 نفر لازم است تا وجود دست‌کم 33 نفر با ماه تولد یکسان تضمین شود.

نکات مهم

  • اگر تعداد اشیا از تعداد دسته‌ها بیشتر باشد، با در نظر گرفتن اشیا به‌عنوان کبوتر و دسته‌ها به‌عنوان لانه، وجود یک دسته با دست‌کم دو عضو تضمین می‌شود.
  • لانه‌ها را متناسب با مسئله انتخاب می‌کنیم؛ مثلاً باقی‌مانده‌های تقسیم، ناحیه‌های یک شکل یا درجه‌های ممکن رأس‌ها.
  • برای تضمین وجود لانه‌ای با دست‌کم k+1k+1 عضو در میان nn لانه، وجود حداقل kn+1kn+1 عضو کافی است.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۹ · صفحهٔ ۸۱ تا ۸۵ · حدود ۱۵ دقیقه · تولید هوش مصنوعی

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

در این درس یاد می‌گیری با تعمیم اصل لانه کبوتری و انتخاب دسته‌های مناسب، کمترین تعداد لازم برای یک تضمین را پیدا کنی و ادعاهایی دربارهٔ عددها، نقطه‌ها و تعداد دوستان را ثابت کنی.

پیش از شروع

چطور می‌توان بدون دانستن تاریخ تولد هیچ‌کس، مطمئن شد که در یک اردوی 7373 نفره، دست‌کم 77 نفر در یک ماه به دنیا آمده‌اند؟

اگر در هر ماه حداکثر 66 نفر متولد شده باشند، تعداد دانش‌آموزان از 12×6=7212\times6=72 نفر بیشتر نمی‌شود. پس با حضور نفر بعدی، حتماً تعداد متولدان یکی از ماه‌ها به دست‌کم 77 نفر می‌رسد؛ حتی اگر ندانیم کدام ماه!

یک نفر بیشتر از ظرفیت

یک نفر بیشتر از ظرفیت

فرض کن چند جعبه داریم و می‌خواهیم در هر جعبه حداکثر kk مهره بگذاریم. اگر تعداد جعبه‌ها nn باشد، تا وقتی این محدودیت را رعایت کنیم، مجموع مهره‌ها بیشتر از knkn نمی‌شود. حالا اگر یک مهرهٔ دیگر هم داشته باشیم، کجا می‌رود؟ هر جا قرارش بدهیم، دیگر نمی‌توانیم در همهٔ جعبه‌ها حداکثر kk مهره داشته باشیم!

این همان تعمیم اصل لانه کبوتری است:

اگر kn+1kn+1 شیء یا بیشتر را در nn دسته قرار دهیم، دست‌کم یک دسته دارای حداقل k+1k+1 شیء خواهد بود.

برای فهم دلیلش، خلاف نتیجه را تصور کن: اگر همهٔ دسته‌ها حداکثر kk عضو داشته باشند، تعداد کل حداکثر knkn است؛ پس وجود kn+1kn+1 عضو با این فرض سازگار نیست.

دقت کن: لازم نیست دسته‌ها را مساوی پر کنیم. این اصل برای هر نوع توزیعی برقرار است. همچنین «حداقل» یعنی ممکن است آن دسته بیش از k+1k+1 عضو داشته باشد؛ قرار نیست تعداد اعضایش دقیقاً همین باشد.

کتاب درسی، صفحهٔ ۸۱

از مسئله تا کبوتر و لانه

از مسئله تا کبوتر و لانه

در مسئله‌های واقعی، اولین کار تشخیص «چیزهایی که دسته‌بندی می‌شوند» و «دسته‌ها» است. مثلاً برای بررسی ماه تولد، دانش‌آموزان نقش کبوترها و ماه‌های سال نقش لانه‌ها را دارند؛ پس تعداد لانه‌ها 1212 است، نه تعداد دانش‌آموزان!

حالا اگر بخواهیم وجود دست‌کم rr عضو در یک دسته تضمین شود، تصور کن هنوز هیچ دسته‌ای به rr عضو نرسیده باشد. در این حالت هر دسته حداکثر r−1r-1 عضو دارد؛ بنابراین در nn دسته، حداکثر (r−1)n(r-1)n عضو جا می‌گیرد. یک عضو بیشتر کافی است تا این وضعیت ناممکن شود:

Nmin⁡=(r−1)n+1N_{\min}=(r-1)n+1

چرا این تعداد واقعاً «کمترین» است؟ چون با یک عضو کمتر، ممکن است همهٔ دسته‌ها دقیقاً r−1r-1 عضو داشته باشند و هنوز خواستهٔ ما برقرار نباشد.

پس موقع ترجمهٔ مسئله، دو چیز را مشخص کن: تعداد دسته‌ها یعنی nn و تعداد اعضای تضمین‌شده در یک دسته یعنی rr. یادت باشد تضمین یعنی در هر نوع توزیع، نه فقط در یک چیدمان دلخواه.

کتاب درسی، صفحهٔ ۸۲

لانه‌های هندسی

لانه‌های هندسی

چطور می‌شود اصل لانه کبوتری را برای نقطه‌هایی به کار برد که روی کاغذ پخش شده‌اند؟ نقطه‌ها کبوترند و ناحیه‌های کوچک‌تر، لانه‌ها. باید ناحیه‌ها را طوری بسازیم که قرار گرفتن دو نقطه در یک ناحیه، نزدیک بودن آن‌ها را تضمین کند؛ مثل تقسیم یک سالن به بخش‌های کوچک برای پیدا کردن دو نفر نزدیک به هم.

مثلث متساوی‌الاضلاعی با ضلع 22 را تصور کن. اگر وسط ضلع‌ها را به هم وصل کنیم، شکل به 44 مثلث متساوی‌الاضلاع با ضلع 11 تقسیم می‌شود. دو نقطه در یک مثلث کوچک، فاصله‌ای بیشتر از 11 ندارند. برای نقطه‌های داخل مثلث اصلی، فاصله حتی کمتر از 11 است؛ چون فاصلهٔ برابر با 11 فقط میان رأس‌های مثلث کوچک رخ می‌دهد و این رأس‌ها روی مرز مثلث اصلی‌اند.

اگر نقطه‌ای روی خط تقسیم بود، آن را فقط به یکی از ناحیه‌های مجاور نسبت می‌دهیم. پس هر نقطه دقیقاً یک لانه دارد و می‌توانیم اصل لانه کبوتری را به کار ببریم.

کتاب درسی، صفحهٔ ۸۲

تعداد دوستان و لانه‌ها

تعداد دوستان و لانه‌ها

آیا ممکن است در یک کلاس، تعداد دوستان هر دانش‌آموز با همهٔ بقیه متفاوت باشد؟ دوستی را دوطرفه در نظر می‌گیریم و کسی را دوست خودش نمی‌شماریم.

کلاس را به یک گراف ساده تبدیل کن: هر دانش‌آموز یک رأس است و بین دو دوست، یک یال می‌کشیم. پس درجهٔ هر رأس، همان تعداد دوستان آن دانش‌آموز است.

در کلاسی با nn دانش‌آموز و n≥2n\ge 2، تعداد دوستان هر نفر یکی از مقدارهای 0,1,…,n−10,1,\ldots,n-1 است. ظاهراً nn مقدار ممکن داریم؛ اما نکته اینجاست: مقدارهای 00 و n−1n-1 نمی‌توانند هم‌زمان وجود داشته باشند. اگر کسی دوستِ همه باشد، دیگر هیچ‌کس بدون دوست نیست!

بنابراین در هر کلاس، حداکثر n−1n-1 مقدار برای تعداد دوستان دیده می‌شود. دانش‌آموزان را کبوتر و مقدارهای ممکنِ تعداد دوستان را لانه بگیر. با قرار گرفتن nn دانش‌آموز در حداکثر n−1n-1 لانه، حتماً دو نفر تعداد دوستان برابر دارند؛ البته لازم نیست خودِ این دو نفر با هم دوست باشند.

کتاب درسی، صفحهٔ ۸۲

هنر ساختن دسته‌های مناسب

هنر ساختن دسته‌های مناسب

گاهی لانه‌ها در صورت مسئله آماده نیستند؛ باید خودت آن‌ها را بسازی! برای این کار، از خودت بپرس: کدام ویژگیِ عددها به نتیجه‌ای که می‌خواهم مربوط است؟

مثلاً اگر خواستهٔ مسئله دربارهٔ زوج بودنِ مجموع باشد، زوج یا فرد بودنِ عددها سرنخ خوبی است؛ چون جمع دو عدد زوج یا دو عدد فرد، زوج می‌شود. پس به‌جای دسته‌بندی بر اساس بزرگی عددها، دو لانهٔ «زوج» و «فرد» می‌سازیم. اگر بتوانیم حضور دو عدد در یک لانه را تضمین کنیم، به نتیجهٔ موردنظر نزدیک شده‌ایم.

در مسئله‌های دیگر، ممکن است باقی‌ماندهٔ تقسیم ویژگی مناسب باشد. مثلاً عددهایی که هنگام تقسیم بر 33 باقی‌ماندهٔ یکسان دارند، اختلافشان بر 33 بخش‌پذیر است.

پس مسیر فکر این است: خواستهٔ مسئله را بخوان، ویژگی مرتبط را پیدا کن و لانه‌هایی بساز که قرار گرفتن دو عدد در یکی از آن‌ها، نتیجهٔ دلخواه را بدهد. فقط کم بودن تعداد لانه‌ها کافی نیست؛ اعضای هر لانه باید رابطهٔ مفیدی هم داشته باشند.

کتاب درسی، صفحهٔ ۸۳

مثال حل‌شده

تعداد 5454 شاخه گل را حداکثر در چند گلدان قرار دهیم تا در هر نوع توزیع، مطمئن باشیم گلدانی با دست‌کم 55 شاخه گل وجود دارد؟

  1. گل‌ها کبوترند و گلدان‌ها لانه‌اند؛ تعداد گلدان‌ها را nn می‌نامیم.

  2. برای اینکه هیچ گلدانی به 55 شاخه نرسد، در هر گلدان حداکثر 44 شاخه می‌گذاریم؛ پس ظرفیت کل در این حالت 4n4n شاخه است.

  3. برای قطعی‌شدن وجود گلدانی با دست‌کم 55 شاخه، باید 54>4n54>4n باشد؛ یعنی n<13.5n<13.5، پس بزرگ‌ترین مقدار صحیحِ ممکن 1313 است.

  4. با 1313 گلدان، اگر هرکدام حداکثر 44 شاخه داشته باشند، فقط 5252 شاخه جا می‌گیرد؛ بنابراین با 5454 شاخه، حتماً گلدانی به دست‌کم 55 شاخه می‌رسد.

  5. برای بررسی بیشینه‌بودن پاسخ، در 1414 گلدان می‌توان 1212 گلدان را با 44 شاخه و 22 گلدان را با 33 شاخه پُر کرد؛ چون 12×4+2×3=5412\times4+2\times3=54، دیگر تضمینی برای وجود 55 شاخه در یک گلدان نداریم.

جواب: حداکثر 1313 گلدان؛ با این تعداد گلدان، وجود گلدانی با دست‌کم 55 شاخه گل حتمی است.

نکات مهم

  • اگر دست‌کم kn+1kn+1 شیء را در nn دسته قرار دهیم، وجود دسته‌ای با دست‌کم k+1k+1 عضو قطعی است.
  • برای تضمین دست‌کم rr عضو در یکی از nn دسته، کمترین تعداد کل (r−1)n+1(r-1)n+1 است؛ با یک عضو کمتر هنوز می‌توان در هر دسته فقط r−1r-1 عضو گذاشت.
  • کلید حل، ساختن لانه‌های مناسب است؛ این لانه‌ها می‌توانند دسته‌های تولد، ناحیه‌های هندسی، تعدادهای ممکنِ دوستان یا گروه‌هایی از عددها باشند.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس‌های فصل ۳ را تعاملی بخوان

در پنل یادگیری 1xAi هر کدام از این درس‌ها قدم به قدم پیش می‌رود: بعد از هر بخش یک سوال کوتاه، بعد مثال حل‌شده و در پایان برگهٔ خروج. جوابت ثبت می‌شود و سوال‌های هر درس در روزهای بعد برای مرور برمی‌گردند. درس‌های تعاملی رایگان‌اند؛ فقط تصحیح پاسخ کوتاه سهمیهٔ روزانهٔ رایگان دارد.

ساختن حساب رایگان است و بعد از ثبت‌نام مستقیم به همین بخش از پنل برمی‌گردی.

فصل ۳ ریاضیات گسسته دوازدهم · رایگان