A و B دو مجموعهی متناهی و جدا از هم از عددهای صحیح هستند به طوری که برای هر x∈A∪B یا x+1∈A و یا x−2∈B است.
ثابت کنید که تعداد عناصر مجموعهی A دو برابر تعداد عناصر مجموعهی B است.
پاسخ
از استقرا روی تعداد عناصر B استفاده میکنیم. اگر تعداد عناصر B صفر باشد، یعنی B تهی باشد، نشان میدهیم که A نیز تهی است. چون برای هر عنصر x∈A، چون x∈A∪B است، باید داشته باشیم x+1∈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|.