امتحان پایانی ریاضیات گسسته ( سری A ) دکتر میرزاوزیری ۲۷/۱۰/۱۳۸۵

امتحان پایان ترم ریاضی گسسته (سری A)

دکتر میرزاوزیری

27/10/85

1.  فرض می کنیم A مجموعه ی همه ی کلمات n حرفی با حروف باشد. زیر مجموعه ی B از A  را خوب می نامیم هر گاه هر دو کلمه ی B  حداقل در دو مکان متفاوت باشند. بزرگترین Bی ممکن چند عضو دارد؟

۲.ثابت کنید در هر جمع ۶ یا سه نفر هستند که دو به دو یکدیگر را می شناسند یا سه نفری هستند که دو به دو یکدیگر را نمی شناسند .آیا برای

نیز حکم درست است ؟چرا؟ثابت کنید عدد بعدی  برای سه نفر ۱۷ است.این  مطلب را تعمیم دهید.

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

۴. می خواهیم  یال های گراف را با m رنگ، رنگ آمیزی کنیم به طوری که هیچ مثلثی با یال هایی  به رنگ های مختلف مشاهده نشود حداکثرm را با ذکر دلیل تعیین کنید.

5.  در یک امتحان تستی 5 سؤالی با 4 گزینه، 2000 دانشجو شرکت کرده اند . با ذکر دلیل ، کوچکترین  nی را تعیین کنید که بتوان به دانشجویان روشی برای پاسخ دادن را آموزش داد به گونه ای که در هر  n پاسخنامه بتوان4 پاسخنامه یافت که هر دو پاسخنامه از آنها حداقل به دو سؤال ، متفاوت جواب داده باشند.

6.  ثابت کنید اگر بتوانیم یک مستطیل  را با کاشی هایی به شکل  بپوشانیم آنگاه n باید زوج باشد . نشان دهید یک مستطیل را می توان با حداقلروش پوشاند .