====== دو مجموعه ======


$A$ و $B$‌ دو مجموعه‌ی متناهی و جدا از هم از عددهای صحیح هستند به طوری که برای هر $x \in A\cup B$ یا $x+1\in A$ و یا $x-2\in B$ است.

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



<پاسخ>

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

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

</پاسخ>

  * [[سوال ۶|سوال بعد]]
  * [[سوال ۴|سوال قبل]]