គណិតវិទ្យា​អាស៊ីប៉ាស៊ីភិច​២០០៨


សំនួរ​២. សិស្ស​ក្នុង​ថ្នាក់​មួយ បាន​បង្កើតជា​​ក្រុម​ផ្សេងៗ ដែល​ក្រុម​និមួយៗ​មាន​សមាជិក​បី​នាក់​គត់ និង​​បណ្តា​ក្រុម​ពីរ​ៗ​ផ្សេង​គ្នា មាន​សមាជិក​រួម​គ្នា​យ៉ាង​ច្រើន​ម្នាក់​។ ចូរ​បង្ហាញ​ថា នៅ​ពេល​ដែល​ថ្នាក់​រៀន​មាន​សិស្ស​46នាក់, គេ​មាន​សំនុំ​មួយ​ មាន​សិស្ស​ចំនួន​ 10 នាក់ ដែល​គ្មាន​ក្រុម​ណា​មួយ​មាន​សិស្ស​ទាំង​នោះ​ទេ។

ចំលើយ

តាង C ជា​សំនុំ​នៃ​សិស្ស​ទាំង​ 46 នាក់​នៅ​ក្នុង​ថ្នាក់រៀន និង តាង ​ s = \max \{ \vert S \vert : S \subseteq C ដែល​ផ្ទៀងផ្ទាត់​ S គ្មាន​លក្ខណៈ​ក្រុម​ដូច​រៀបរាប់​ក្នុង​សំនួរ \}
ដូច្នេះ​យើង​ត្រូវ​បង្ហាញ​ថា s \geq 10។ (បើ \vert S \vert = s > 10, នោះ យើង​អាច​ជ្រើស​រើស​សំនុំ​រង​មួយ​​នៃ S ដែល​មាន​សិស្ស​10 នាក់។)
សន្មត​ថា​ s = 9 និង​ តាង S ជា​សំនុំ​មួយ​​ដែល​មាន​ទំហំ​ s ដែល​គ្មាន​ក្រុម​ណា​មួយ​ជា​សំនុំ​រង​របស់​សំនុំ​នេះ​ទេ។
Take any student, say v, from outside S. Because of the maximality of s, there should be a group containing the student v and two other students in S. The number of ways to choose two students from S is\binom{s}{2} \leq \binom{9}{2}=36

On the other hand, there are at least 37 = 46 - 9 students outside of S. Thus, among those 37 students outside, there is at least one student, say u, who does not belong to any group containing two students in S and one outside. This is because no two distinct groups have two members in common. But then, S can be enlarged by including u, which is a contradiction.

Advertisements

About វិចិត្រ

ជា​ខ្មែរ​ម្នាក់ ជា​មនុស្ស​ម្នាក់ ធម្មតា​ដូច​មនុស្ស​ឯ​ទៀត​ដែរ
អត្ថបទនេះត្រូវបាន​ផ្សាយក្នុង គណិតវិទ្យា​។ ប៊ុកម៉ាក តំណភ្ជាប់​អចិន្ត្រៃ​យ៍​

ឆ្លើយ​តប

Fill in your details below or click an icon to log in:

ឡូហ្កូ WordPress.com

អ្នក​កំពុង​បញ្ចេញ​មតិ​ដោយ​ប្រើ​គណនី WordPress.com របស់​អ្នក​។ Log Out / ផ្លាស់ប្តូរ )

រូប Twitter

អ្នក​កំពុង​បញ្ចេញ​មតិ​ដោយ​ប្រើ​គណនី Twitter របស់​អ្នក​។ Log Out / ផ្លាស់ប្តូរ )

រូបថត Facebook

អ្នក​កំពុង​បញ្ចេញ​មតិ​ដោយ​ប្រើ​គណនី Facebook របស់​អ្នក​។ Log Out / ផ្លាស់ប្តូរ )

Google+ photo

អ្នក​កំពុង​បញ្ចេញ​មតិ​ដោយ​ប្រើ​គណនី Google+ របស់​អ្នក​។ Log Out / ផ្លាស់ប្តូរ )

កំពុង​ភ្ជាប់​ទៅ​កាន់ %s