ترکیبیات

[Only Math]

ترکیبیات ، ریاضیات انتخاب و یا آنالیزترکیبی یکی از شاخه های جذاب ریاضیات است که به بررسی مسائل شمارش ، گرافها ، بازیها و نیز مسائل ساختاری روی مجموعه ها متناهی می پردازد. از جمله کاربردهای مهم این شاخه میتوان به استفاده آن در برنامه نویسی کامپیوتر و الگوریتم ها اشاره کرد.
یکی از مسائلی که ترکیبیات را از دیگر شاخه های ریاضی متمایز میکند این است که آموختن آن نیاز به اطلاعات خاصی از ریاضیات ندارد و داشتن معلومات ریاضی دوره راهنمایی نیز برای درک آن کافی به نظر می رسد چرا که ریشه های ترکیبیات در واقع به مسائل معماگونه ریاضی و بازیها میرسد. بسیاری از مسائل ترکیبیات که در گذشته برای تفریح بررسی شده اند امروزه اهمیت زیادی در ریاضیات محض و کاربردی دارند.
در قرن اخیر ترکیبیات به یکی از مهمترین شاخه های ریاضیات تبدیل شده و مرزهای آن همواره گسترش پیدا می کند که یکی از مهمترین علل این گسترش سریع ، اختراع کامپیوتر می باشد:
به علت سرعت بالای کامپیوترها بسیاری از مسائلی که قبلا قابل بررسی نبودند ، بررسی شدند. البته تقابل کامپیوتر و ترکیبیات یک طرفه نبوده است و کامپیوترها نمی توانستند مستقل عمل کنند و برای عمل نباز به برنامه داشتند. اساس برنامه های کامپیوتری غالبا الگوریتمهای ترکیبیاتی اند و به همین دلیل اهمیت و کاربرد ترکیبیات پس از اختراع کامپیوتر چندین برابر معلوم شد و باعث شد تا ریاضیدانان بسیاری به تحقیقات گسترده در این زمینه رو آوردند.
مباحث ترکیبیان بسیار گسترده اند ولی اساس آن بر پایه روشهای شمارش است که از جمله این روش ها می توان به اصل جمع ، اصل ضرب و اصل متمم اشاره کرد .
در این تاپیک ابتدا به بررسی اصول مقدماتی و آموزش ترکیبیات در حد مقدماتی پرداخته و در صورت توجه و تمایل دوستان پس از اتمام بخش مقدماتی بخش پیشرفته را بررسی می کنیم.
بنابراین از دوستانی که به این مبحث علاقمندند و یا اطلاعات مفیدی دارند می خواهم تا در پاسخگویی به مسائل مطرح شده در این تاپیک شرکت کنند. جواب هر مسئله مطرح شده را یک روز بعد از طرح آن داده میشود. (در صورتی که حداقل دو نفر نظر خود را قرار داده باشند)
منابع مطالبی که در این تاپیک قرار میگیره علاوه بر جزوات درسی شامل:
کتاب ترکیبیات انتشارات فاطمی
کتاب استراتژی های حل مسئله انتشارات مبتکران
خواهد بود.
دوستان توجه داشته باشید که این تاپیک بدین شکل تنها در سایت njavan قرار دارد و استفاده از ان تنها باذکر این سایت به عنوان منبع بلامانع خواهد بود.

[Only Math]

دو مسئله ابتدایی :
فرض کنید دو گوشه مقابل صفحه شطرنجی 8 8x حذف شده باشد آیا میتوان شکل باقی مانده را با 31 مهره دو مینو پر کرد؟ (دو خانه قرار گرفته در دوسر یک قطر صفحه)


می خواهیم صفحه شطرنج 5 *5 را با 8موزائیک 1*3 و یک موزائیک1*1 بپوشانیم . ثابت کنید موزائیک باید در مرکز صفحه باشد.

[Only Math]

پاسخ سوال اول :
ممکن است فکر کنید جواب مثبت است چون 62 خانه باقی مانده و با 31 دومینو پر میشود. اما اگر امتحان کرده باشید متوجه میشوید که در قرار دادن مهره آخر دچار مشکل میشوید. در واقع نمیتوان این شکل را با 31 مهره پر کرد چون:
در یک صفحه شطرنج کامل 32 خانه سفید و 32 خانه سیاه وجود دارد و میتوان آن را با 32 مهره دومینو پر کرد چون هر مهره یک خانه سفید و یک خانه مشکی را اشغال میکند این درحالی است که در سوال از ما خواسته شده تا دو خانه از دو سر یک قطر را حذف کنیم (2 خانه مشکی یا دو خانه سفید) :
فرض کنیددو خانه مشکی ک دو سر قطر قرار دار را حذف کرده ایم بنابراین در شکل حاصل ما 32 خانه سفید و 30 خانه مشکی داریم پس میتوانیم 30 مهره دومینو را به راحتی قرار دهیم اما در قرار دادن مهره آخر مشکل داریم چون دو خانه باقی مانده هر دو سفیدند درحالی که ما به یک خانه سفید و یک خانه مشکی نیاز داریم. پس نمیتوان چنین شکلی را با 31 مهره دومینو پوشاند.

[Only Math]

برای معرفی شمارش از چند مسئله مقدماتی شروع میکنیم:

بین دو شهر A و B سه جاده احداث شده است. به چند طریق میتوان از A به B رفت و به A برگشت ؟

راه حل : برای رفتن از A به B سه راه وجود دارد وبه ازای هریک از این 3 راه ، 3راه برای برگشت وجود دارد . پس به 9=3*3 طریق می توان از Aبه B رفت و به A برگشت.

در صفحه شطرنج 6*5 چند مربع 3*3 وجود دارد؟

راه حل : هر مربع 3*3 در صفحه شطرنجی از برخورد دو خط افقی به فاصله 3 و دو خط عمودی به فاصله 3 از صفحه صفحه شطرنجی حاصل میشود.
تعداد زوجهایی از خط های افقی که در صفحه شطرنجی مورد نظر به فاصله 3 از یکدیگر قرار دارند برابر 3 و تعداد زوجهایی از خط های عمودی که به فاصله 3 در این صفحه شطرنجی قرار دارند برابر 4 است. چون به ازای هر زوجی از خطهای افقی به فاصله 3 ، 4 مربع 3*3 وجود دارد ، پس در کل 3*4 مربع 3*3 در این صفحه وجود دارد.

قضیه 1 : تعداد مربعهای K*K در صفحه شطرنجی M،N<K ، M*N برابرست با :

(m-k+1)(n-k+1)

چند عدد دو رقمی وجود دارد ؟

راه حل : می توان اینگونه پرسید که به چند طریق می توان یک عدد دو رقمی نوشت؟
برای رقم دهگان می توان یک عدد را از مجموعه { 9 ، .... ، 2 ، 1 } و برای یکان یک عدد از مجموعه { 9 ، ... ، 1 ، 0 } انتخاب کرد . یعنی 9 انتخاب برای دهگان و 10 انتخاب برای یکان بنابراین به 9*10 طریق میتوان عدد دو رقمی ساخت پس 90 عدد دورقمی وجود دارد.

قضیه 2 : فرض کنید m ، n دو عدد صحیح باشند و m < n . در این صورت تعداد اعضای مجموعه { m , m+1 , .... , n } بربر است با :m + n - 1

[Only Math]

1 ) بین دو شهر a ، b سه جاده و بین دو شهر b ، c چهار جاده احداث شده است .

الف) به چند طریق میتوانیم از a به c برویم ؟
ب) به چند طریق می توان از a به c و به a برگشت ؟
ج) به چند طریق میتوانیم از a به c برویم و به a برگردیم به طوری که از هیچ جاده ای دو بار عبور نکنیم ؟

2) چند عدد سه رقمی بدون تکرار ارقام وجود دارد ؟

3) چند عدد 4 رقمی فرد میتوان ساخت؟ (تکرار اعداد مجاز است )

4) در یک مربع 8*8 چند مربع وجود دارد ؟

[Only Math]

کسی در مورد سولات نظری نداره !؟

[kamanabroo]

چرا من مي خواستم بگم كه

خيلي سوالي خوبي هستند
و اگه ميشه وقتشو زيادتر كنين


الف: 12
ب:9*12


..
همشو من نگم بقيه رو شما ها بگين

[Only Math]

چرا من مي خواستم بگم كه

خيلي سوالي خوبي هستند
و اگه ميشه وقتشو زيادتر كنين


الف: 12
ب:9*12


..
همشو من نگم بقيه رو شما ها بگين

قسمت الف درست ولی قسمت ب نادرست:
طبق قسمت الف به 12 طریق میشه از a به c رفت و برای بگشت هم همینطور بنابراین جواب قسمت ب میشه 12 * 12

[AvAstiN]

ج) 9*10*10*5 = 4500

[Only Math]

1 ) بین دو شهر a ، b سه جاده و بین دو شهر b ، c چهار جاده احداث شده است .

الف) به چند طریق میتوانیم از a به c برویم ؟ 12= 4 * 3
ب) به چند طریق می توان از a به c و به a برگشت ؟ 144= 3 * 4 * 4 * 3
ج) به چند طریق میتوانیم از a به c برویم و به a برگردیم به طوری که از هیچ جاده ای دو بار عبور نکنیم ؟
برای رفتن از a به c طبق قسمت الف 12 راه وجود دارد اما در هنگام برگشت با توجه به صورت مسئله نباید از جادههایی که از آن برای رفت استفاده کرده ایم عبور کنیم بنابراین برای برگشت از a به b دو جاده و از b به c سه جاده وجود دارد : 72 = 2 * 3 * 4 * 3

2) چند عدد سه رقمی بدون تکرار ارقام وجود دارد ؟
برای رقم صدگان 9 انتخاب داریم .
در صورت مجاز بودن تکرار برای دهگان 10 انتخاب وجود داشت اما چون تکرار نامجاز است نمی توانیم از عددی که در صدگان استفاده شده استفاده کنیم پس 9 انتخاب داریم.
برای رقم یکان 8 انتخاب داریم چون از 10 عدد یک عدد در دهگان و یک عدد در صدگان استفاده شده پس تعداد اعداد سه رقمی بدون تکرار ارقام برابرست با : 648 = 8 * 9 * 9

3) چند عدد 4 رقمی فرد میتوان ساخت؟ (تکرار اعداد مجاز است )
فرد بودن یا زوج بودن یک عدد به رقم یکان آن بستگی دارد پس رقم یکان را باید از اعداد :
{9 ، 7 ، 5 ، 3 ، 1 } انتخاب کنیم پس برای یکان 5 انتخاب داریم.
چون تکرار مجاز است برای رقم دهگان 10 ، صدگان 10 و هزارگان 9 انتخاب داریم پس تعداد اعداد 4 رقمی فرد برابر است با : 4500 = 5 * 10 *10 * 9

4) در یک مربع 8*8 چند مربع وجود دارد ؟

چون تعداد کل مربع ها را خواسته پس باید تعداد مربع های 1*1 و 2*2 و 3*3 و .... و 8*8 را باتوجه به قضیه 1 بدست آورده و سپس مجموع آنها را حساب کنیم :

49 = (1+2-8) (1+2-8) : مربع 2*2 / 64 = (1+1-8) (1+1-8) : مربع 1*1

25 = (1+4-8) (1+4-8) : مربع 4*4 / 36 = (1+3-8) (1+3-8) : مربع 3*3

9 = (1+6-8) (1+6-8) : مربع 6*6 / 16 = (1+5-8) (1+5-8) : مربع 5*5

1 = (1+8-8) (1+8-8) : مربع 8*8 / 4 = (1+7-8) (1+7-8) : مربع 7*7

بنابراین تعداد کل مربع ها برابر است با : 204 = 64 + 49 + 36 + 25 + 16 + 9 + 4 + 1