Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۶:سوال ۵

دو مجموعه

A و B‌ دو مجموعه‌ی متناهی و جدا از هم از عددهای صحیح هستند به طوری که برای هر xAB یا x+1A و یا x2B است.

ثابت کنید که تعداد عناصر مجموعه‌ی A دو برابر تعداد عناصر مجموعه‌ی B است.

پاسخ

از استقرا روی تعداد عناصر B استفاده می‌کنیم. اگر تعداد عناصر B صفر باشد، یعنی B تهی باشد، نشان می‌دهیم که A نیز تهی است. چون برای هر عنصر xA، چون xAB است، باید داشته باشیم x+1A بنابراین اگر A‌ تهی نباشد، باید نامتناهی باشد که این خلاف فرض مسئله است.

حالا فرض می‌کنیم که مسئله برای |B|<n ثابت شده است و آن را برای |B|=n اثبات می‌کنیم. برای این منظور، کوچک‌ترین عنصر B را در نظر گرفته و آن را y می‌نامیم. چون y کوچک‌ترین عضو B است، y2 نمی‌تواند متعلق به B باشد؛ بنابراین y+1 متعلق به A است. به همین صورت چون y1 نمی‌تواند متعلق به B باشد، y+2 متعلق به A است. حالا مجموعه‌های A{y+1,y+2} و B{y} را در نظر می‌گیریم. به سادگی دیده می‌شود که این دو مجموعه در شرایط مسئله صدق می‌کنند. بنابراین با توجه به فرض استقرا داریم |A{y+1,y+2}|=2|B{y}|. پس |A|=2|B|.


ابزار صفحه