حل تشریحی سوالات سؤالات امتحان نهایی درس ریاضیات گسسته دوازدهم خرداد 1401 - امتحان نهایی دوازدهم خرداد 1401 (ریاضی)

درست یا نادرست بودن جملات زیر را مشخص کنید. (1)

الف) اگر $a|b$ و $b\ne 0$، در این صورت $\left|a\right|>\left|b\right|$.

ب) برای دو عدد صحیح و ناصفر $a$ و $b$ اگر $(a|c,b|c)$ و $(\forall m>0,a|m,b|m\Rightarrow c\le m)$ آن‌گاه $[a,b]=c$.

پ) برای هر دو عدد صحیح $a$ و $b$ و عدد طبیعی $m$، اگر باقی‌مانده تقسیم $a$ بر $m$ مساوی با $r$ باشد، در این صورت $a\stackrel{m}{\equiv }r$.

ت) بزرگ‌ترین مقسوم‌علیه مشترک دو عدد 4 و $-2$ برابر $-2$ است.

ثابت کنید برای هر عدد طبیعی زوج $n$، $n^2-5n+7$ عددی فرد است. (1)

اگر عددی مانند $k$ در $Z$ باشد، به‌طوری که $5|4k+1$، ثابت کنید $25|16k^2+28k+6$. (0/75)

باقی‌مانده تقسیم عدد $A={27}^{20}+18$ را بر 13 بیابید. (1)

اگر در یک سال، اول مهر شنبه باشد، در این صورت 12 بهمن در همان سال چه روزی است؟ (1/25)

جاهای خالی را با عدد یا کلمه مناسب پر کنید. (1)

الف) اگر درجه یک رأس فرد باشد، آن را رأس ............ می‌نامیم.

ب) گرافی را که تمام رئوس آن تنها باشد، هیچ یالی نداشته باشد، گراف ........... می‌نامیم.

پ) تعداد یال‌های گراف $K_4$، برابر با ............ است.

ت) گراف $G$ را ............ می‌نامیم هرگاه بین هر دو رأس آن حداقل یک مسیر وجود داشته باشد.

به سؤالات زیر کوتاه پاسخ دهید. (1)

الف) گراف $C_7$ را رسم کنید. سپس یک مسیر به طول 5 بنویسید.

ب) در گراف شکل زیر، $N_G(c)$ را با اعضا مشخص کنید.

الف) مجموعه احاطه‌گر مینیمال را تعریف کنید. (0/75)

ب) برای گراف شکل روبه‌رو، یک مجموعه احاطه‌گر با 4 عضو انتخاب کنید. (0/5)

عدد احاطه‌گری گراف شکل مقابل را با ارائه راه‌حل، تعیین کنید. (1/25)

ابتدا گراف $P_9$ را رسم کنید. سپس یک مجموعه احاطه‌گر مینیمم از آن را مشخص کنید. (1)

گراف شکل مقابل را در نظر بگیرید. (1/5)

الف) یک $-\gamma$مجموعه مشخص کنید.

ب) یک مجموعه احاطه‌گر مینیمال با 4 عضو بنویسید.

6 کتاب متفاوت تاریخ و 5 کتاب متفاوت ادبیات را به چند طریق می‌توان در یک ردیف کنار هم چید به‌طوری که: (1)

الف) کتاب‌های تاریخ همواره کنار هم باشند.

ب) به‌صورت یک در میان قرار بگیرند.

با ارقام 9، 7، 6، 5، 3، 3، 1، 1، 1 چند عدد 9 رقمی می‌توان نوشت؟ (1)

معادله $x_1+x_2+x_3+x_4+x_5+x_6=12$ چند جواب صحیح و نامنفی دارد به شرط آنکه $x_3=4$ و $x_5>2$  باشد؟ (1/5)

الف) مربع لاتین $A$ را در نظر بگیرید. با اِعمال جایگشت $\begin{array}{c}1\to 3\\ 2\to 2\\ 3\to 4\\ 4\to 1\end{array}$ مربع لاتین $B$ را به‌دست آورید. (0/75)

ب) آیا دو مربع لاتین $A$ و $B$ متعامدند؟ دلیل بیاورید. (1/25)

به چند طریق می‌توان 5 سیب را بین 3 نفر توزیع کرد، به‌طوری که هر نفر حداقل یک سیب داشته باشد؟ (1/25)

ثابت کنید اگر در یک دبیرستان حداقل 505 دانش‌آموز مشغول تحصیل باشند، لااقل 7 نفر از آن‌ها روز، هفته و ماه تولدشان یکسان است. (1/25)