تالار گفتمان مانشت
سوال ۱۴ علوم کامپیوتر ۹۶ - نسخه‌ی قابل چاپ

سوال ۱۴ علوم کامپیوتر ۹۶ - ss311 - 23 دى ۱۳۹۶ ۰۱:۴۳ ب.ظ

[attachment=22285]

RE: سوال ۱۴ علوم کامپیوتر ۹۶ - بنده ی خدا - ۲۳ دى ۱۳۹۶ ۰۷:۳۰ ب.ظ

سلام
فکر می‌کنم که باید یک راه‌حل از طریق اصل لانه کبوتری داشته باشد، ولی مدت‌هاست که گسسته حل نکردم و خوب یادم نیست اما این راه حل دم‌دستی امیدوارم که به کار بیاید.
فرض کنید مجموعهٔ [tex]X[/tex] برابر باشد با [tex] \{ a_1\cdots,a_{20}\} [/tex].
بدون خلل در کلیت استدلال فرض کنید که [tex] a_i\leq a_j,\quad \forall i\leq j,\, i,j \in \{1,\cdots,20\} [/tex].
با توجه به فرض مسئله داریم
[tex] a_1 + \cdots +a_{10} \geq 10 [/tex]
توجه کنید که در بالا فرض کرده‌بودیم که [tex] a_1 [/tex] تا [tex] a_{10} [/tex] کوچک‌ترین عددهای متعلق به مجموعه X هستند. پس یقینا هر کدام از [tex] a_i[/tex] که [tex] i\in \{11,\cdots,20\} [/tex] به این مجموع اضافه شوند، باید اندازه مجموعه را از یازده بیش‌تر کنند.*
پس مجموع هر یازده عضو از این مجموعه از یازده کمتر نیست.
با همین تکنینک پیش‌برویم می‌بینیم که مجموع هر پانزده عضو از این مجموعه از پانزده کمتر نیست و همین‌طور مجموع هر شانزده عضو از این مجموعه از شانزده کمتر نیست.
از طرفی مثالی می‌توانیم بسازیم که قسمت ب صادق نباشد. کافی است [tex] a_1=\cdots=a_5=0[/tex] و [tex] a_6= \cdots =a_{20}=10[/tex] در نظر بگیریم. میبینیم که مجموع اعضای شماره یک تا پنج از پنج کمتر هست.

پس سه گزینه الف، ج و د صحیح هستند.

*پی‌نوشت: ممکن است بپرسید، چرا از یازده کمتر نیست؟ چرا مثلا نمی‌گوییم از ۱۰/۹ کمتر نیست؟ توجه‌کنید که می‌نیمم حالتی که برای [tex] a_{10}[/tex] وجود دارد عدد یک هست. اندکی فکر کنید تا این موضوع را درک کنید.

RE: سوال ۱۴ علوم کامپیوتر ۹۶ - ss311 - 24 دى ۱۳۹۶ ۰۱:۲۴ ب.ظ

سلام.ممنون.
ولی ببخشید متوجه نشدم. اصلا چرا باید فرض کنیم که [tex]a_i\le a_j[/tex]

RE: سوال ۱۴ علوم کامپیوتر ۹۶ - بنده ی خدا - ۲۶ دى ۱۳۹۶ ۰۹:۴۳ ب.ظ

(۲۴ دى ۱۳۹۶ ۰۱:۲۴ ب.ظ)ss311 نوشته شده توسط:  سلام.ممنون.
ولی ببخشید متوجه نشدم. اصلا چرا باید فرض کنیم که [tex]a_i\le a_j[/tex]

این فرض را برای راحتی استنتاج در مورد اعضای مجموعه X در نظر می‌گیریم. اعضای X یک سری عدد حقیقی هستند مثلا ۰.۱، ۱۲، ۷، ۰.۵ و ...
ما که نمی‌توانیم کلی در مورد آن‌ها نظر بدهیم. پس می‌آییم آن‌ها را توی خیال خودمان مرتب می‌کنیم یعنی به هر یک از اعضا یک برچسب [tex] a_i [/tex] می‌زنیم و قرارداد می‌کنیم که مقداری که درون برچسب [tex] a_1 [/tex] هست کوچکتر یا مساوی [tex] a_2 [/tex] هست و مقدار درون [tex] a_2 [/tex] کوچکتر یا مساوی [tex] a_3 [/tex] هست و به همین‌ترتیب الی آخر
حالا یک چیز خوب در دسترس داریم، اینکه می‌دانیم مجموع کوچترین اعضای X درون برچسب‌های [tex] a_1,\cdots , a_{10} [/tex] قرار گرفته!!
از اینکه مجموع کوچک‌ترین اعضای X بزرگ‌تر یا مساوی ۱۰ شده حالا استفاده می‌کنیم، یعنی چی؟
اولا اینکه باید این را بیابید که حداقل مقدار [tex] a_{10} [/tex] حتما یک هست. (از اصل لانه کبوتری روی آـیک تا آـده استفاده کنید)
دوما اینکه هر عضو دیگری را برداریم پس مقدارش از یک بیشتر می‌شود (چون فرض کردیم اعضا مرتب شده‌اند، پس عضو‌های با برچسب‌های بزرگ‌تر از ده مقدارشان هم بیش‌تر هست!!!)
به همین خاطر می‌توانیم نتیجه بگیریم که هر عضو دیگری به مجموع این ده عضو کوچک‌ترین اضافه کنیم، مقدارش از یازده بیش‌تر می‌شود.

اگر بازهم ابهامی هست بفرمائید تا بنده تلاش کنم یک‌طور دیگر توضیح دهم.

RE: سوال ۱۴ علوم کامپیوتر ۹۶ - ss311 - 26 اردیبهشت ۱۳۹۹ ۱۲:۳۳ ب.ظ

Huh