سوالات ترکیبیات بسیج

[Goharshady]

سلام
تو دوره ی بسیج تعدادی سوال زیبای ترکیبیات مطرح شد که در ادامه اونا رو می نویسم. اکثر این سوالات در کلاسهای کامپیوتر مطرح شده. ممکنه بعضی از سوالات در حد ترکیبیات پیشرفته نباشه ولی در کل بهترین جا برای نوشتن سوالات اینجا بود(لا اقل از نظر من!).بعضی از سوالات ممکنه قبلا هم مطرح شده باشند که بابت طرح دوباره ی آنها معذرت می خواهم. در بین این سوالات جای سوالات امتحان آخر دوره خالیست. عزیزانی که برگه ی امتحانی (کامپیوتر) رو دارن لطفا اون سوالات رو هم بذارن. لطف کنید به سوالات جواب بدهید و موقع جواب دادن حتما شماره ی سوال را بنویسید. امیدوارم از حل این سوالات لذت ببرید.

1. 
   [*]
   
   9 ریاضی دان یکدیگر را در یک کنفرانس بین المللی ملاقات می کنند. معلوم شد از بین هر 3 ریاضیدان ، دست کم دو نفر با زبان مشترکی می توانند صحبت کنند. اگر هر ریاضیدان حداکثر با 3 زبان آشنا باشد ثابت کنید دست کم 3 ریاضیدان وجود دارند که می توانند با زبانی مشترک صحبت کنند.
   [*]
   
   فرض کنید خانه های یک جدول 7×4 به رنگهای سیاه و سفید در آمده باشند. ثابت کنید این جدول شامل مستطیلی است که هر چهارگوشه ی آن همرنگ هستند.ثابت کنید این قضیه برای 6×4 صادق نیست.
   [*]
   
   یک انتخابگر به صورت random و هم شانس یکی از اعداد صحیح 1 تا 9 را انتخاب می کند. احتمال این که بعد از n انتخاب ، حاصلضرب اعداد انتخابی مضربی از 10 باشد چه قدر است؟
   [*]
   
   شش نفر صندوقچه ای با ارزش دارند که می خواهند به آن قفل بزنند. هر کس می تواند کلید یک یا چند قفل را داشته باشد. آنها می خواهند هر 3 نفر دلخواه بتوانند قفل را باز کنند اما هیچ دو نفری نتوانند. حداقل چند قفل لازم است؟
   [*]
   
   تعداد زیرمجموعه های
   
   از مجموعه ی
   
   را بیابید که
   
   .
   [*]
   
   تعداد زیرمجموعه های m عضوی از مجموعه ی
   
   را بیابید که دو عضو پشت سرهم نداشته باشند.
   [*]
   
   سوال قبل را در حالتی حل کنید که 1,n پشت سر هم محسوب شوند.
   [*]
   
   چند تصاعد حسابی 3 عضوی در بین اعداد مجموعه ی
   
   وجود دارد؟
   [*]
   
   قطرهای یک n ضلعی را رسم کرده ایم.هیچ سه قطری از یک نقطه نمی گذرند . ثابت کنید تعداد ناحیه های ایجاد شده برابر است با »
   
   
   [*]
   
   برای هر جایگشت
   
   ،
   
   را برابر تعداد عددهایی تعریف می کنیم که در
   
   سر جای خودشان هستند. برای همه ی جایگشتهای متفاوت اعداد
   
   مقادیر
   
   را محاسبه و با هم جمع کرده ایم. حاصل جمع را بیابید.
   [*]
   
   در چند دنباله ی دودویی 15 رقمی ، تعداد زیردنباله های 01 دقیقا 3 تا ، 10 دقیقا 2 تا ، 00 شش تا و 11 سه تا است؟ (منظور از زیردنباله ، زیردنباله ی پشت سرهم است!!!)
   [*]
   
   به چند طریق می توان جدولی 4×4 را با اعداد 0و1و2و3 طوری پر کرد که جمع هر سطر و هر ستون 3 شود؟ (در هر سطر و ستون تکرار فقط برای 0 مجاز است.)
   [*]
   
   ثابت کنید با ارقام 1 و 2 می توان عددی n رقمی نوشت که بر 2[SUP]n[/SUP] بخشپذیر باشد.
   [*]
   
   به ازای هر عدد طبیعی n که عامل 2و5 ندارد ، ثابت کنید دنباله ای به طول کمتر از n+2 با استفاده از رقم 7 (یعنی فقط 7) وجود دارد که بر n بخشپذیر باشد.
   [*]
   
   در برج هانوی فرض کنید می خواهیم مهره ها را از میله ی A به B منتقل کنیم و انتقال مستقیم از A به B و بالعکس ممکن نیست. چند حرکت لازم است؟
   [*]
   
   در سوال قبل می خواهیم مهره ها را از A به C ببریم. آیا این کار ممکن است؟ اگر ممکن است چند حرکت لازم است؟
   [*]
   
   در یک شهر 128 نفره ، یک شخص عجیب کسی است که همه ی دیگران را بشناسد ولی کسی او را نشناسد. به یک شهر 128 نفره می رسیم. در هر مرحله می توانیم i بپرسیم که j را می شناسد یا نه. با 374 پرسش یا کمتر معین کنید آیا شخص عجیب وجود دارد یا نه و در صورت وجود او را مشخص کنید.
   [*]
   
   تعداد همه ی جایگشتهای
   
   روی n حرف را بیابید که
   
   همانی شود.
   [*]
   
   خانه های صفحه ی شطرنجی 100×100 را با 4 رنگ طوری رنگ آمیزی کرده ایم که در هر مربع 2×2 هر چهار رنگ وجود دارند. ثابت کنید خانه های 4 گوشه ی صفحه از 4 رنگ مختلف هستند.
   [*]
   
   n عدد حقیقی مثبت داریم که
   
   ثابت کنید :
   

1

 

[Electron]

</IMG src=modules/forums/images/smiles/53.gif>

 

[Goharshady]

با کمال تاسف به دلیل هک شدن سایت نتونستم به صورت متن بذارم. این هم تصویر جواب سوال 1 و تصویر چگونگی هک سایت:

 

[Goharshady]

جواب سوال 3 امتحان پایانی:(همونطوری که من نوشتم)

به صورت استقرایی عمل می کنیم. پایه استقرا n=4 است (یعنی طراح سوال واقعا فکر کرده من برای 10 چک می کنم؟) __توضیح : در ادامه همه ی 34 جایگشت ممکن را به همراه طریقه ی تبدیل نوشتم

__
فرض کنیم برای n این کار ممکن باشد. ثابت می کنیم برای n+1 نیز ممکن است. توجه داریم که در گام استقرا می توانیم دو بار دیگر از معکوس کردن استفاده کنیم.ابتدا عدد سمت راست را کنار می گذاریم و بقیه اعداد را طبق فرض استقرا مرتب می کنیم. 3 حالت در نظر می گیریم. (در نظر گرفتن دو حالت اول هیچ لزومی ندارد اما به جهت توضیح بهتر آنها را نیز می آورم)
الف) اگر عددی که کنار گذاشتیم از همه ی اعداد دیگر بزرگتر باشد ، به جواب رسیده ایم و نیازی به هیچ حرکت دیگری نداریم.
ب) اگر عددی که کنار گذاشته ایم از همه ی اعداد دیگر کوچکتر باشد، ابتدا همه ی اعداد دیگر را برعکس می کنیم و سپس کل دنباله (یعنی n+1 عدد) را برعکس می کنیم. با این عمل عدد آخر به جای اول می رود و همه ی اعداد دیگر یک واحد به راست شیفت می شوند.
پ)اگر عدد کنارگذاشته شده دقیقا j امین عدد باشد ، در این صورت j-1 عدد ابتدایی را در نظر نمی گیریم و با دنباله ی باقیمانده عملی مشابه قسمت قبل انجام می دهیم. یعنی ابتدا n-j+1 عدد آخر (بدون احتساب آخرین عدد) را برعکس می کنیم سپس n-j+2 عدد آخر (با احتساب آخرین عدد) را برعکس می کنیم. در این صورت آخرین عدد به مکان j ام می رود ، j-1 عدد ابتدایی هیچ تغییری نمی کنند و سایر اعداد یک واحد به راست شیفت داده می شوند.
در هر یک از حالات بالا با حداکثر 2 حرکت گام استقرا پیموده شد ، پس حکم برقرار است.

 

[Goharshady]

جواب دو سوال دیگر را لطفا دیگران بگذارند چون من از آنها نمره ی کامل نگرفتم.

موفق باشید

 

[Electron]

سوال 2 بايد از هم زوجيت بودن m و n استفاده كنيد فقط چون من نمره كامل نگرفتم نمينويسم

سوال 4 هم چند مرحله استدلاله